1.**Russell's Paradox** Let S be the set of all sets which are NOT members of themselves.

i.e. S = { X X X }

Is S S ?

- If it is then it shouldn't be

- If it isn't then it should !

(c.f. the barber who claims to shave all who don't shave themselves.

2. **Cantor's Paradox** Let C be the set of all sets.

Every subset of C is then a member of C i.e. C so C

- but we also have >C.

( The upshot of all this is that what constitutes a valid "set" in the theory must be carefully defined ).

3. **Berry's Paradox** Every integer in N can be described in n words for some n **N**.

e.g. 300 : three hundred (2 words)

5832 : eighteen cubed (2 words)

Let x be "the smallest positive integer which cannot be described in fewer than twenty words" - then x has just been described in 13 words ! Hmmmmmmmmmm....

Frege (1848-1925) was the prime mover in the field of axioms of set theory - until Russell told him of his paradox. Frege's "naive" set theory was thus inconsistent.

Others (e.g. Russell himself) sought consistent sets of axioms for sets.

Generally accepted now are the Zermelo-Fraenkel axioms :

1. **Axiom of extensionality**

:
**x,y** (**z** (**z** ** x** ** z** **y**) ** x = y** )

(says when two sets are equal).

2.** Axiom of the null set**

:
**x** **y** ( **~ y** **x**)

(there exists a set with no members).

3. & 4. (unions of sets are sets).

5. (guarantees existence of infinite sets).

6. **Axiom of replacement**:

(properties can be used to define sets).

7. (power sets are sets).

8. **Axiom of choice**:
(Given a set of sets : {A : I} we can choose an element from each non-empty set A ).

9. **Axiom of regularity**:

(prohibits things like XX ).

Then Russell and Whitehead in "Principia Mathematica" (1910) aimed to formalise the whole of mathematics from these axioms (result - it's totally unreadable).

At the time (and to a certain extent still today) mathematicians fell into three "schools of thought" :

**Platonists** believed mathematics already exists and waits to be discovered. Objects such as groups, sets, numbers etc. have a real existence.

**Formalists** believed mathematical objects don't exist - maths is just axioms, definitions and theorems.

**Constructivists** (= Intuitionists) only believed in mathematical objects which can be "constructed".

- e.g. Cantor's non-constructive proof of the existence of transcendentals was rejected,

as was any proof by contradiction (i.e. they did not agree that ~ ~ p implies p).

The foremost formalist (and foremost mathematician of the early 20th century) was Hilbert (1862-1943). His aim was to prove two things :

1. Axiomatic set theory is consistent ( i.e. it is impossible to derive contradictions like 0 0 from them).

2. There is a definite procedure whereby one could decide in advance whether or not a problem could be solved.

He believed these to be possible, but his work came to an abrupt end when Godel (1906-1978) showed in 1931 that:

1. If axiomatic set theory is consistent, there exist theorems which can neither be proved nor disproved.

2. There is no way to prove axiomatic set theory to be consistent.

**Godel's Work**
First consider :

THIS SENTENCE IS FALSE

- a paradox

Now :

THIS THEOREM CANNOT BE PROVED

- also a paradox (it cannot be false, so it must be true - this proves it - so it's false)

Now :

THIS THEOREM CANNOT BE PROVED IN AXIOM SYSTEM S

- this now must be true (as before) but our "intuitive" proof wasn't using system S - so no paradox

The difficulty comes in stating this latest version in the language of the system S. Godel showed that this can be done, providing that the system S is powerful enough to allow arithmetic in N to be defined, by "coding" the statement into numbers in such a way as to get the theorem to refer to it's own number (Godel numbering).

The actual maths was complicated, but the result was clear, and has rather unsettled the present foundations of mathematics.

[ Comments ] [ Module Leader ]

These pages are maintained by M.I.Woodcock.