Continuum Hypothesis

Georg Cantor’s conjecture, the Continuum Hypothesis

Without equations, this states that for any set of real numbers, S, one of three things happen:

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

There is nothing in between the integers and reals. Kurt Goedel showed that this was consistent with set theory, and Paul Cohen 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 Axiom Of Choice). Ditto for the Generalized Continuum Hypothesis. — Eric Jablow

Here is a proof 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”.