Set Theory History

111 downloads 214 Views 1MB Size Report
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?