Diagonalization and the Continuum Hypothesis
Posted on May 27, 2011
by Tommy McGuire
I have recently been reading Gödel's Theorem: An Incomplete Guide to its Use and Abuse, by Torkel Franzén, which is very good even though Franzén's attempts to explain Gödel's theorems in natural language frequently feel like he is tap-dancing around the theorems themselves; when your explanation of a formal proof is more complex than the proof itself, something is wrong. On the other hand, his discussion the various philosophical (and other) conclusions that have been drawn from Gödel's theorems (and what is wrong with them) is very, very good.One thing that Franzén mentions that I had not known before is that Cantor's Continuum Hypothesis is one of the most rare things in mathematics: a statement that is undecidable in Zermelo-Fraenkel set theory (with the axiom of choice) and one which is not specifically constructed to be undecidable in ZFC.
Now, my purpose here is not really to talk about the Continuum Hypothesis (a.k.a. CH), nor about incompleteness, Gödel, or Franzén. Instead, I want to talk about some of the background to the CH and one of the top five mathematical proofs of the last, say, 200 years.
To start with, say I have a set of three apples, a Red Delicious, a Fuji, and an Arkansas Black, and a set of three people: Alice, Bob, and Georg. How would I know whether or not the two sets are the same size, or cardinality? Simple. I need to put the two sets into a relationship where exactly one object from one set is associated with exactly one object from the other. If Alice eats the Red Delicious, Bob eats the Fuji, and Georg has the Arkansas Black flung at his head, then I know the two sets are the same size. What I have done is to put the two sets into a one-to-one relation. (Technically, my one-to-one correspondence is a bijection; it needs to be both injective and surjective.)
You might point out that I could just count the two sets to know if they were the same size. But that is ultimately the same thing: instead of putting a set of people in a one-to-one relation with a set of apples, I would be putting both sets of people and apples in a one-to-one relation with numbers. In fact, those are typically the counting numbers: 1, 2, 3, .... Counting the objects in a set simply amounts to putting the objects in a one-to-one relation with an initial-prefix subset of the counting numbers.
At this point, I feel the need to toss out a couple of factoids that you may (or may not) already be aware of:
- The counting numbers are infinite. That "..." indicates they continue forever.
- There are (many) different kinds of numbers, including counting numbers, natural numbers (0, 1, 2, 3,...), integers (..., -2, -1, 0, 1, 2,...), rational numbers (x/y, where x and y are integers), and real numbers (0, 4, pi, e, 34.56,...).
And here is a neat point that is the crux of this whole post: by explicitly setting things in one-to-one relations, you can compare the sizes of infinite sets.
But wait, you say, what the heck does that mean? Here is a question for you: are there as many counting numbers as there are natural numbers. It does not seem like there should be, because the naturals have that extra 0 that is not included in the counting numbers. But infinite sets are weird. For one thing, I can't show you a one-to-one mapping, like I could with people and apples. Instead, I can exhibit a relation: \[ \forall n : n \in \textrm{natural} : (\exists c : c \in \textrm{counting} : n = c - 1) \] \[ \wedge \] \[ \forall c : c \in \textrm{counting} : (\exists n : n \in \textrm{natural} : n = c - 1) \] Or, in English, for any natural number \(n\) you can give me, I can give you back a counting number \(c\) such that \(n\) is \(c - 1\) and vice-versa. I'll spare you the demonstration that this relation is suitably one-to-one and just point out that it shows that the counting numbers and the naturals have the same cardinality, or size. Like I said, infinite sets are weird: one of the defining characteristics is that an infinite set can be put in a one-to-one correspondence with a proper subset of itself.
So, if that is the case, how do the counting numbers and the naturals compare with the integers? It turns out that they are the same size, too. Consider the following two functions, nat, which converts any integer to exactly one natural number, and int, which converts any natural number to an integer.
\[ \textrm{nat}(n) = \begin{array}{cl} 2n & \textrm{if } n \geq 0 \\ -2n - 1 & \textrm{if } n < 0 \end{array} \] \[ \textrm{int}(n) = \begin{array}{cl} n/2 & \textrm{if } n \textrm{ even} \\ {-(n + 1) \over 2} & \textrm{if } n \textrm{ odd} \end{array} \] Without any particular argument that these two functions are inverses, I assert that they define a one-to-one relationship and therefore demonstrate that the natural numbers and the integers are the same cardinality. The rationals? This is where things start to get tricky. Consider for a moment the relationship I defined between the integers and the naturals above; what I did was to effectively take the integer number line, fold it in half between -1 and 0, and then alternately take one number from each half to match each natural number:
| 0, | 1, | 2, | 3, | 4, | ... | (the naturals) |
|---|---|---|---|---|---|---|
| 0, | -1, | 1, | -2, | 2 | ... | (the integers) |
A similar trick can be done with the rationals by, first, only looking at the positive, natural numbers. (If I can put the positive fractions in a one-to-one relationship with natural numbers, I can use the same folding argument to include the negative fractions in the same sort of relationship.) Then, make a table with the numerators starting at 0 on the horizontal axis and the denominators starting at 1 on the vertical axis. (Obviously, the denominators cannot include zero.) Starting from the upper left cell, 0/1, zig-zag out one cell at a time, producing 1/1, 0/2, 2/1, 1/2, 0/3, collecting each upper-right-to-lower-left diagonal.
| 0/1 | 1/1 | 2/1 | 3/1 | ... |
| 0/2 | 1/2 | 2/2 | 3/2 | ... |
| 0/3 | 1/3 | 2/3 | 3/3 | ... |
| ... | ... | ... | ... |
Based on the table and the diagonal paths, I assert
- Every positive rational number shows up at least once in this table, and by multiplying each entry by -1, I can construct another table where every negative rational number shows up, and so that every rational number appears in one of the two tables at least once.
- By taking the diagonals in order, I can create a single list of the positive rationals, where each cell shows up in exactly one place in my list. By alternating between tables, I can construct a list containing every cell in both tables.
- And therefore, the set of rational numbers is not larger than the set of natural numbers.
| 1 | 0.435246687003... |
| 2 | 0.076201826664... |
| 3 | 0.000000000000... |
| 4 | 0.999999999999... |
| ... | ... |
- Take the first digit after the decimal point of the first number on the list.
- Add one to this digit, wrapping around to 0 if the digit is 9.
- Make this new digit the first digit after the decimal in my new number.
- Repeat with the second digit after the decimal point of the second number, creating the second digit of my new number.
- And so on, incrementing the next digit of the next number to get the corresponding digit of the new number.
(Feel smarter yet? I know I do.)
So, what's this continuum hypothesis, then? Cantor identified the size, or cardinality, of the integers as the transfinite number \(\aleph_0\). He went further to identify other transfinite numbers \(\aleph_1\), \(\aleph_2\), and so on, using completely different definitions. Now, we now know that the cardinality of the reals between 0 and 1, call it C, is greater than \(\aleph_0\), but the open question is whether C is less than or equal to \(\aleph_1\).
