Cantors Proof

GeorgCantor's 'diagonal' proof is a surprising and elegant argument which was first used by Cantor to prove that irrational numbers exist (and variants pop up here and there in analysis). It goes roughly like this (I will try to be a bit verbose, this is much easier to see on a board or paper):

Let I be an interval of R (the real numbers)
suppose that I is a CountablyInfinite set.
then we may enumerate R: r1, r2, r3, ...
choose a1,b1 in R s.t. r1 ne (a1,b1) subset I
choose a2,b2 in R s.t a1 < a2 < b2 < b1 and r2 ne (a2,b2)
Continue in this manner, so that having chosen a_n,b_n in R, we choose a_(n+1_, b_(n+1) in R s.t. a_n < a_(n+1) < b_(n+1) < b_n
Consider the set {a1, a2, ...}. It is bounded above by b, so the lub, call it r, of this set exists. It follows that a_n < r for all n in Z+. On the other hand, r < b_n for all n in Z+, since if b_m <= r for some m in Z+, we would have: a_n < b_(m+1) < b_m <= r for all n in Z+.
Thus b_(m+1) would be an upper bound for {a1,a2,...} but since b_(m+1) < r this is impossible.
Therefore r in (a_n, b_n) for all n in Z+
It follows that r != r_n for every n in Z+, and r in I. This is a contradiction, so our supposition is false, and I is not countable.

Cantor was very surprised (as were his peers) by this result, as it proves the existence of irrational numbers, without demonstrating a single irrational number.

The existence of irrational numbers was well-known even to the ancient Greeks. What Cantor proved was that (correctly discussed above) the integers and rationals are in 1-1 correspondence, and that the integers and reals are not. The proof by contradiction is as follows:

I didn't mean (above) to suggest that Cantor was the first to prove the existence of irrationals (that was a Pythagorean, as far as we know), only that he was the first to use this elegant argument - with the surprising result that you may show the existence of the irrationals, without *knowing* any of them. I should have been clearer about that!

Suppose the real numbers were countable, and so one could list them, say as follows:

1: 0.1234567890... 2: 0.2431874592... 3: 0.7902943124... 4: 1.3239846830... 5: 8.9392493872... 6: 9.2929292929... 7: 8.2343212123... 8: 0.9876532838... 9: 8.9292983829... 10: 0.2378652101...

No. Using the ordinary order, there is no smallest or largest. Choosing an arbitrary order is fine too. But this argument shows that you can't count them. The point is that you cannot exhaust all the real numbers in such an enumeration. Switch two or more entries in the list, and you'll get a (possibly) different real number not in the list by the procedure below.

The particular numbers don't matter. Terminating rationals like 1.0 we replace with 0.99999999.... Now, take the diagonal I highlighted, and write down the number whose nth decimal digit is 1 if the nth diagonal term is anything other than 1, and 2 if the nth diagonal term is 1. In this case, that's

0.2111111112...

This number can never appear on the list; if it were the mth entry, what is its mth digit?

Therefore, the integers are not in 1-1 correspondence with the reals. Various arguments similar to the proof that the rationals are in 1-1 correspondence with the integers show that the algebraic numbers (roots of polynomials with integer coefficients) are in 1-1 correspondence with the integers, and so almost all numbers are transcendental (not algebraic). A slight rework of this argument shows that for any set A, A and its power set P(A) [The set of all subsets of A.] are not in 1-1 correspondence. On the other hand, it isn't hard to show that the reals are in 1-1 correspondence to the power set of the integers.

This leads to Cantor's conjecture, the ContinuumHypothesis?. Without equations, this states that for any set of real numbers, S, one of three things happen:

1. S is finite. 1. S has a 1-1 correspondence to the integers. 1. S has a 1-1 correspondence to the reals.

There is nothing in between the integers and reals. KurtGoedel showed that this was consistent with set theory, and PaulCohen? showed that its negation was consistent. In other words, CH is an undecidable proposition of Zermelo-Frankel set theory (and of ZFC, ZF with the AxiomOfChoice). Ditto for the GeneralizedContinuumHypothesis?. -- EricJablow

Here is another CantorsProof that demonstrates that the space occupied by the rational numbers is the same as the space occupied the integers (There's a related demonstration that the space of irrational numbers is larger, but I don't remember it).

Whatever it is that Cantor proved, the proof goes something like this:

1. Enumerate the positive integers along the x-axis 2. Enumerate the positive integers along the y-axis 3. Mark the point (0, 0). 4. Mark the point (1, 1). 5. Draw a horizontal vector one unit to the right. 6. Draw a diagonal (up and to the left) vector to the line at x=1, marking each intersection. 7. Draw a vertical vector one unit up. 8. Draw a diagonal (down and to the right) vector to the line at y=1, marking each intersection. 9. Go to step 5.

This algorithm traverses the following points (in Quadrant I):

 (0,0), (1,1), (2,1), (1,2), (1,3), (2,2), (3,1), (4,1), (3,2), (2,3), (1,4), ...

Treating each x-coordinate as the numerator, and y-coordinate as the denominator (and removing duplicates), this algorithm traverses the following rational numbers:

 (0), (1), (2), (1/2), (1/3), (3), (4), (3/2), (2/3), (1/4), ...

By construction, this algorithm traverses every point in Quadrant I for which the ratio of x/y is defined.

By symmetry, this algorithm also traverses every point in Quadrant II for which the ratio of x/y is defined.

Every ratio is touched, and every intersection traversed contains a ratio.

Therefore the size of the rational numbers is the same as the size of the natural (positive and negative) "counting numbers".