R is uncountable Proof

Assume (for a contradiction) that R is countable. Each a R can be expressed as an infinite decimal. Suppose the 1-to-1 correspondence with N is :

1 n . a b c d.......( n Z,
2 n . a b c d....... a, b, c etc are
3 n . a b c d.......decimal digits )


such that every real number appears in the list on the right.

Now choose a real number 0 . a b c d .....

such that a a , b b , c c etc.

Then this real number is different from all those in the list, and hence there cannot exist such a 1-to-1 correspondence between N and the whole of R. So R is uncountable.

(This is Cantor's "diagonal argument").

So the cardinality of R is not . Cantor called it c (except that the symbol should be in copperplate typeface !) - the "cardinality of the continuum".

Cantor also showed :

1. The cardinality of A is - so there are many transcendentals (in fact c of them !).

2. If is the power set of S then the cardinality of is strictly greater than that of S.

If S is the cardinality of S then is 2S.

e.g. the set of subsets of N is and = , so > .

Hence we get a hierarchy of cardinals :

< < < < ..........

- there is no "largest" cardinal. 3. = c.

He also considered a list of infinite cardinals :

< < < < ......

where each is the smallest cardinal which is strictly greater than .

He asked : "Is equal to c ?" but could not find the answer.

Nowadays " = c" is called the "continuum hypothesis" and can be taken as an axiom of set theory. (It cannot be proved or disproved from the other set theory axioms).

Cantor also introduced ordinal numbers - a generalisation of our :

1st, 2nd, 3rd, 4th,.... etc

to infinite ordinals :

........, , +1, +2, ......., , ...., , ........., , ......, , ......, ,......

with strange properties like :

1+ = , +1 ; 2 = , 2 : etc

Some mathematicians (Kronecker, Poincare ) ridiculed this work of Cantor. Others ( Zermelo, Fraenkel, Russell, Hilbert ) thought it brilliant, and sought to base the whole of pure maths on a system of axioms for set theory. This was complicated by paradoxes which emerged in the theory.

Some Paradoxes

Cantor's Theory

Foundations of Mathematics

History of Mathematics Module

Links to other History of Mathematics sites

[ Comments ] [ Module Leader ]

These pages are maintained by M.I.Woodcock.