This says that for every property a(x) there is a set y that has all the elements that satisfy a(x). Notation: this y =
Set Theory History Martin Bunder
September 2015
What is a set? Possible Definition A set is a collection of elements having a common property
Abstraction Axiom If a(x) is a property (∃y )(∀x)(x ∈ y ⇔ a(x)) This says that for every property a(x) there is a set y that has all the elements that satisfy a(x). Notation: this y = {x∣a(x)}
Comprehension Axiom (Cantor 1874, Frege (Begriffsschrift) 1879, 1903) (∀z)(z ∈ {x∣a(x)}) ⇔ a(z)
What is a set? Possible Definition A set is a collection of elements having a common property
Abstraction Axiom If a(x) is a property (∃y )(∀x)(x ∈ y ⇔ a(x)) This says that for every property a(x) there is a set y that has all the elements that satisfy a(x). Notation: this y = {x∣a(x)}
Comprehension Axiom (Cantor 1874, Frege (Begriffsschrift) 1879, 1903) (∀z)(z ∈ {x∣a(x)}) ⇔ a(z)
What is a set? Possible Definition A set is a collection of elements having a common property
Abstraction Axiom If a(x) is a property (∃y )(∀x)(x ∈ y ⇔ a(x)) This says that for every property a(x) there is a set y that has all the elements that satisfy a(x). Notation: this y = {x∣a(x)}
Comprehension Axiom (Cantor 1874, Frege (Begriffsschrift) 1879, 1903) (∀z)(z ∈ {x∣a(x)}) ⇔ a(z)
What is a set? Possible Definition A set is a collection of elements having a common property
Abstraction Axiom If a(x) is a property (∃y )(∀x)(x ∈ y ⇔ a(x)) This says that for every property a(x) there is a set y that has all the elements that satisfy a(x). Notation: this y = {x∣a(x)}
Comprehension Axiom (Cantor 1874, Frege (Begriffsschrift) 1879, 1903) (∀z)(z ∈ {x∣a(x)}) ⇔ a(z)
Examples of Sets
{x∣x = a} = {a} {x∣x 2 = 1} = {1, −1} {x∣x = 1 ∨ x = −1} = {1, −1} {x∣x ∈ Z ∧ (∀y )(y ∈ Z ⇒ (∃z)(z ∈ Z ∧ y = zx)} = {1, −1} ⇑ x∣y {x∣x ∈ R ∧ 0 < x < 1} = (0, 1)
Extensionality Axiom
A = B ⇔ (∀x)(x ∈ A ⇔ x ∈ B) Sets are equal if they have the same elements. Assume if a(x) is a property of x: A = B ⇒ (a(A) ⇔ a(B))
Special Sets
{x∣x ≠ x} = {x∣x ∈ R ∧ x 2 = −1} = ∅
Empty Set
{x∣x = x} = V
Universal Set
{x∣x ∈ A ∨ x ∈ B} = A ∪ B
Union of A and B
{x∣x ∈ A ∧ x ∈ B} = A ∩ B Intersection of A and B {x∣¬x ∈ A} = A′
Complement of A
Subsets Definition A is a subset of B A ⊂ B ⇔ (∀x)(x ∈ A ⇒ x ∈ B)
{x∣x ⊂ A} = P(A)(the powerset of A) {x∣x ⊂ ∅} = {∅} {x∣x ⊂ {∅} = {∅, {∅}} {x∣x ⊂ {a, b, c}} = { ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}
The Properties of Sets Come from Logic e.g. A ∪ B = B ∪ A Proof A ∪ B = {x∣x ∈ A ∨ x ∈ B} B ∪ A = {x∣x ∈ B ∨ x ∈ A} By the Comprehension Axiom: x ∈A∪B ⇔x ∈A∨x ∈B ⇔ x ∈ B ∨ x ∈ A by logic ⇔x ∈B ∪A So (∀x)(x ∈ A ∪ B ⇔ x ∈ B ∪ A). By the Extensionality Axiom A ∪ B = B ∪ A.
Similarly . . .
A∩B =B ∩A (A ∪ B) ∪ C = A ∪ (B ∪ C ) A ∩ (B ∩ C ) = (A ∩ B) ∩ C A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ) A ∪ (B ∩ C ) = (A ∩ B) ∪ (A ∩ C ) (A ∪ B)′ = A′ ∩ B ′ (A ∩ B)′ = A′ ∪ B ′
Comparing Sets People People People Chickens Chickens
– – – – –
Heads Brains Chairs Beaks Tails
Definition Equivalent Sets are sets that have elements matched by a one to one mapping. A ≈ B ⇔ (∃f )f ∶ A → B ∧ f is 1-1 and onto (a bijection) A is equivalent to B A ⪯ B ⇔ (∃f )f ∶ A → B ∧ f is 1 -1 A ≺ B ⇔ A ⪯ B ∧ ¬A ≈ B
Examples
{+, −, ÷} ≈ {2, , ,}
{+, −, ÷} ≺ {2, , ,, /}
Defining Natural Numbers
0=∅ 1 = {0} = {∅} 2 = {0, 1} 3 = {0, 1, 2} etc.
Note 0 ≺ 1 ≺ 2 ≺ 3 ≺ ... {+, −, ÷} ≈ {0, 1, 2} = 3.
Definition If A ≈ n, n is the cardinal number of A, or n = #A. So, #{+, −, ÷} = 3.
Cardinal Arithmetic Definition Addition: If A ∩ B = ∅, #A + #B = #(A ∪ B). e.g. 3 + 2 = #{0, 1, 2} + #{3, 4} = #{0, 1, 2, 3, 4} = 5.
Definition Multiplication: #A ⋅ #B = #(A × B) where A × B = {(a, b)∣a ∈ A, b ∈ B}. e.g. 3 ⋅ 2 = #{0, 1, 2} ⋅ #{0, 1} = #({0, 1, 2} × {0, 1}) = #{(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)} =6
Infinite Cardinal Numbers
Let #{1, 2, 3, 4, . . . } = ℵ0 . If N = {1, 2, 3, 4, . . . }, E = {2, 4, 6, 8, . . . }. then if f (n) = 2n, f ∶ N → E , f is 1-1 and onto. So N ≈ E and #E = ℵ0 . Also Q = {0, −1, 1, − 21 , 21 , −2, 2, − 13 , 13 , − 32 , 23 , −3, 3, . . . }. So N ≈ Q and #Q = ℵ0 .
Some Arithmetic
For n ∈ N: ℵ0 + n = ℵ0 nℵ0 = ℵ0 ℵn0 = ℵ0 What about nℵ0 ? Is N ≈ [0, 1) ≈ R?
nℵ0 Assume N ≈ [0, 1). Then there is an f ∶ N → [0, 1). f is 1-1 and onto f (1) = .a11 a12 . . . So:
f (2) = .a21 a22 . . . f (3) = .a31 a32 . . .
⋮ Let b = .b1 b2 b3 . . . ⎧ ⎪ ⎪aii + 1 if aii = 0 where bi = ⎨ ⎪aii − 1 if aii = 0 ⎪ ⎩ Then b ≠ f (n) for any n So N ≺ [0, 1) ≈ R #[0, 1) = #R = 2ℵ0 .
These must all be different (for 1-1) and use up all of [0, 1) (for onto)
Cantor #N = ℵ0 is the smallest infinite cardinal number. ℵ1 is the next smallest, then ℵ2 , etc. Continuum 2ℵ0 = ℵ1
Hypothesis:
Generalised Continuum Hypothesis: 2ℵn = ℵn+1 Unresolved 1964. Georg Cantor (1845 - 1918) 1874
problem
till
Cantor’s Theorem A ≺ P(A) (Like the proof of N ≺ [0, 1)) Cantor’s Paradox, 1899 V = {x∣x = x} So
P ⊂V
So
P ⪯V
But
V ≺ P(V )
i.e.
¬P(V ) ⪯ V .
Burali-Forti Paradox, 1897 Involves Ordinal Numbers.
Russel and Frege
Bertrand Russell (1872 1970)
Gottlob Frege (1845 - 1925)
Russell sent his paradox to Frege when volume 2 of his Begriffsschrift was about to be published.
Russel’s Paradox (1903)
If R = {x∣x ∈/ x}, then by the Comprehension axiom: y ∈ {x∣a(x)} ⇔ a(y )
R ∈ R ⇔ R ∈/ R A contradiction! (Gives: R ∈ R ∧ ¬R ∈ R)
Hilbert at the 1900 International Congress of mathematics in Paris What would be the major problems of interest in mathematics in the 20th century? Hilbert listed 23: 1 The Continuum hypothesis, is 2ℵ0 = ℵ1 ? 2 Prove that the axioms of arithmetic are consistent. David Hilbert (1862 - 1943)
The Hilbert Programme
Aim: To ground all existing theories (including set theory) to a finite, complete set of axioms, and prove that these are consistent.
G¨odel’s Incompleteness Theorems 1931 1. In any axiomatic systems, strong enough to include arithmetic, there is always an arithmetical statement that can neither be proved nor disproved.
Kurt G¨ odel (1906 - 1978)
2. A statement saying such a system is consistent can neither be proved nor disproved.
Ways of Beating the Paradoxes: Change the Logic
Intuitionistic Logic
Luitzen Brouwer (1881 1966) - 1908
Arend Heyting (1898 - 1980) - 1930
Don’t allow ⊢ P ∨ ¬P, so you don’t have ⊢ V ≺ V ∨ ¬V ≺ V or ⊢ R ∈ R ∨ ¬R ∈ R.
Paraconsistent Logic
Newton da Costa (1929 - !)
Allow ⊢ R ∈ R and ⊢ ¬R ∈ R, but not ⊢ P ∧ ¬P ⇒ Q. (This doesn’t work, Curry’s Paradox, 1942 - IF C = {x∣x ∈ x ⇒ X } then ⊢ X .)
Logic and Aritmetic based on Combinatory Logic
Moses Schonfinkel (1887 1942) - 1924
Haskell Curry (1900 - 1982) 1930
Logic and Arithmetic based on Lambda Calculus
Alonzo Church (1903 - 1995) - 1933
Ways of Beating the Paradoxes: Change the Set Theory
Change the Set Theory
Ernst Zermelo (1871 - 1953) - 1908
Abraham Fraenkel (1891 1965) - 1921
Axioms
(∀z)(z ∈ x ⇔ z ∈ y ) ⇒ x = y
Extensionality
(∃y )(∀x)(x ∈ y ⇔ x ∈ z ∧ P(x)) Substitution of Specification (Defines subsets of z) (∃z)(x ∈ z ∧ y ∈ z)
Pairing (defines {x, y })
(∃z)(∀x)(x ∈ y ∧ y ∈ w ⇒ x ∈ z)
Union
(z is the set of the elements of the elements of w .)
+ Others
von Neumann, Bernays and G¨odel
John von Neumann (1903 1957) - 1925, 1928
Paul Bernays (1888 - 1977) 1937, 1945
G¨ odel - 1940 Has sets and classes (only sets can be elements of classes.)
Axioms
(∀z)(z ∈ X ⇔ z ∈ Y ) ⇒ X = Y
(X, Y classes)
(∃Y )(x ∈ Y ⇔ a(x)) (Y is a class)
Extensionality comprehension Only y ∈ X if y is a set
+ Axioms for sets
Continuum Hypothesis
2ℵ0 = ℵ1 Can neither be proved or disproved in NBG or ZF!
Paul Cohen (1934 - 2007)
Cardinal Numbers and Measures The measure, or length, of: [m, m + n] = n #[m, m + n] = 2ℵ0 #[0, a] = 2ℵ0 if a > 0 IF #A = ℵ0 , the measure A = 0 1 2 3 , n+1 , n+2 , . . . } n 10 10 10 k can be made arbitrarily small for n large 10n+k−1
N≈{
Question:If #A = 2ℵ0 is a measure for A > 0?