1. The Theory of Infinite Sets - Part 4

In the last class we proved that |N| = |O| = |I| = |Q| = À₀. Today we will prove that the Reals are uncoutable, i.e., |R| > À₀ Then we will prove another theorem due to Cantor: that for every set, there is a bigger one. Thus there are an infinity of infinities, each bigger than the last.

Even though the rationals are dense, we know they have holes, e.g., Ö 2. The theory of analysis requires a continuum of numbers with no holes, and such a continuum is called the Real numbers. Instead of constructing them rigorously, which is a task in itself and wasn’t really understood until Dedekind in the 19th Century, we will look only at the reals between 0 and 1 and assume that each real number can be expressed as an infinite enumeration of digits between 0 and 9. E.g., 1/3 = .333333333.......

We will show that this set of reals, which we will call R_(0,1) , is still strictly bigger than the naturals.

-Recall the key definition for cardinality:

Cantor showed that the reals are bigger than the naturals by showing that there is no 1-1 function f: R_(0,1) ® N. To show that there can be no such function, he assumed that there was such a function and proved a contradiction from this assumption.

His argument is famous for introducing a technique called "diagonalization" which is now used routinely in mathematics. Here is the proof.

Theorem 4: |R_(0,1) | > À₀

Proof: |R_(0,1) | > À₀ if it is not the case that |R_(0,1) | ≤ |N|. Assume the opposite, i.e., that |R_(0,1) | ≤ |N|, which means that there is a 1-1 function from R_(0,1) to N. Take any such function F:

where dij = the jth digit for the real number that maps to natural number i.

For example:

where d05 = 9, i.e., the 5th digit in the real that maps to 0.

Cantor now created the following real number from the 'diagonal' of the table for F:

rx = d11' d22' d33' d44' d55' .......

where dii' = 1 if dii ≠ 1, and dii' = 2 if dii =1, thereby ensuring that dii' ≠ dii for all i. Since two real numbers are different if any of their digits are different, then rx is different from any real in the table for F. It is different from r65 in the 65th digit, and different from r23 in the 23rd digit. rx clearly is a real number, yet no matter what table F consists of, it will be left out of this table, which means F cannot even be a function from R to N. Q.E.D.

-----------

Cantor not only proved that there are different sizes of infinities, e.g., R and N, he generalized the result to show that there are an infinity of different size infinities! He did this by showing that the power set of any set is bigger than the set itself. This means that for any infinite set there is a bigger one.

The power set of A is written: Ã(A) and is defined as the set of all subsets of A.

A is a subset of B, written A Í B, if every member of A is also a member of B.

For example, if A = {1,3,{2,4}}, then

Ã(A) = {{1},{3},{{2,4}},{1,3},{1,{2,4}},{3,{2,4}}, {1,3,{2,4}} }

Theorem 5: (Cantor's Theorem): If A is a set, then |Ã(A)| > |A|

Proof: Assume the opposite, so that there is some set A and some 1-1 function F from Ã(A) to A. Like the diagonalization argument in his previous theorem, Cantor will show that no matter what function F we write that pairs members of Ã(A) with members of A, F leaves out some member of Ã(A).

Any 1-1 function F from Ã(A) to A pairs each member of Ã(A), i.e., each subset of A, with some member of A. Whatever the function table, we will use it to construct a set C as follows. Put any e Î A into C if it is not in the member of Ã(A) paired with e by the function f.

For example, if a,b,c Î A, the function f and the set C might look like

Ã(A) A C

{a,b,c...} ® a Is a in {a,b,c...}? Yes - don't put a into C

{a,....} ® b Is b in {a,...}? No - put b into C

Æ ® c Is c in Æ? No - put c into C.

. . .

Since the only members of C are members of A, C Í A and thus C Î Ã(A)

So C must be included in the function f and thus must map to some member of A, call it x.

C ® x

Clearly x Î C or x Ï C. We will prove with an argument by cases that x Î C & x Ï C

Case 1) Assume x Î C. But we built C so it only included members of A not in their corresponding subset:

C ® x Is x in C? Yes - so x is not in C

So if x Î C then x Ï C, which is an absurdity.

Case 2) Assume x Ï C. But again, C is built so it only includes members of A not in their corresponding subset:

C ® x Is x in C? No - so x is in C

So if x Ï C then x Î C, which is also an absurdity. So in either case we have a contradiction and therefore the function F cannot include C and thus cannot exist.