Cantor’s Diagonal Argument - University of Kansas

1 Cantor s Diagonal ArgumentRecall that.. A setSis finite iff there is a bijection betweenSand{1,2,..,n}for some positive integern, andinfinite otherwise. ( , if it makes sense to count its elements.) Two sets have the same cardinality iff there is a bijection between them. ( Bijection , remember,means function that is one-to-one and onto .)A setSis calledcountablyinfinite if there is a bijection betweenSandN. That is, you can label theelements ofS1, 2, .. so that each positive integer is used exactly once as a countably infinite ?

2 Such a set is countable because you can count it (via the labeling just mentioned).Unlike a finite set, you never stop counting. But at least the elements can be put in correspondence the other hand,not all infinite sets are countably infinite. In fact, there are infinitely manysizes of infinite Cantor proved this astonishing fact in 1895 by showing that thethesetofrealnumbersisnotcountable. That is, it is impossible to construct a bijection betweenNandR. In fact, it s impossible toconstruct a bijection betweenNand the interval [0,1] (whose cardinality is the same as that ofR).

3 Here s Cantor s thatf:N [0,1] is any function. Make a table of values off, where the 1st row contains thedecimal expansion off(1), the 2nd row contains the decimal expansion off(2), .. thenth row contains thedecimal expansion off(n), .. Perhapsf(1) = /10,f(2) = 37/99,f(3) = 1/7,f(4) = 2/2,f(5) = 3/8,so that the table starts out like (n) 1 4 1 5 9 2 6 5 7 3 7 3 7 3 7 3 4 2 8 5 7 1 4 2 0 7 1 0 6 7 8 1 7 5 0 0 0 0 0 0 course, only part of the table can be shown on a piece of paper it goes on forever down and to be onto?

4 That is, can every number in [0,1] appear somewhere in the table?In fact, the answer is no there are lots and lots of numbers that can t possibly appear! For example, let shighlight the digits in the main Diagonal of the (n) 4 1 5 9 2 6 5 7 3 7 3 7 3 428 5 7 1 4 2 0 710 6 7 8 1 7 5 000 0 0 0 highlighed digits are Suppose that we add 1 to each of these digits, to get the , this number can t be in the table.

5 Why not? Because it differs fromf(1) in its first digit; it differs fromf(2) in its second digit; .. it differs fromf(n) in itsnth digit; ..So it can t equalf(n) for anyn that is, it can t appear in the looks like a trick, but in fact there are lots of numbers that are not in the table. For example, wecould subtract 1 from each of the highlighted digits (changing 0 s to 9 s), getting by the sameargument, this number isn t in the table. Or we could subtract 3 from the odd-numbered digits and add 4to the even-numbered digits.

6 Or we could even highlight a different set of digits:nf(n) 1 5 9 2 6 5 3 7 3 7 3 7 3 4 285 7 1 4 2 071 0 6 7 8 1 7 5 000 0 0 0 long as we highlight at least one digit in each row and at most one digit in each column, we can changeeach the digits to get another number not in the table. Here, if we add 1 to all the highlighted digits, weend up with there s a real number that does not equalf(n) for any positive is the point of all this?

7 Precisely that the functionfcan t possibly be onto there will always be(infinitely many!) missing values. Therefore, there does not exist a bijection betweenNand [0,1].IfSis a set, then thepowersetP(S) is defined as the set of all subsets ofS. For example, ifS={1,3,4},thenP(S) ={{},{1},{3},{4},{1,3},{1,4},{3,4},{1,3, 4}}.2 WhenSis finite, it s not hard to see that|P(S)|= 2|S|: (because to choose a subsetRofS, you needto decide whether each element ofSdoes or does not belong toR).

8 In the above example,|S|= 3 and|P(S)|= 8 = about infinite sets? Using a version of Cantor s Argument , it is possible to prove the following theorem:Theorem every setS,|S|<|P(S)|. :S P(S) be any function and defineX={s S|s6 f(s)}.For example, ifS={1,2,3,4}, then perhapsf(1) ={1,3},f(2) ={1,3,4},f(3) ={}andf(4) ={2,4}. Inthis caseXdoes not contain 1 (because 1 f(1)),Xdoes contain 2 (because 26 f(2)),Xdoes contain 3(because 36 f(3)), andXdoes not contain 4 (because 4 f(4)), soX={2,3}.Now, is it possible thatX=f(s) for somes S?

9 If so, then eithersbelongs toXor it doesn t. But bythe very definition ofX, ifsbelongs toXthen it doesn t belong toX, and if it doesn t then it does. Thissituation is impossible soXcannot equalf(s) for anys. But, just as in the original Diagonal Argument ,this proves thatfcannot be example, the setP(N) whose elements are sets of positive integers has more elements thanNitself;that is, it isnot countably a consequence of this result, the sequence of infinite setsN,P(N),P(P(N)),P(P(P(N))).

10 Must keep increasing in cardinality. That is, there are infinitely many different sizes of infinity!3