Cantor's Diagonal Proof

A re-formatted version of this article can be found here.

Simplicio: I'm trying to understand the significance of Cantor's 
diagonal proof. I find it especially confusing that the rational 
numbers are considered to be countable, but the real numbers are
not.  It seems obvious to me that in any list of rational numbers
more rational numbers can be constructed, using the same diagonal 
approach.

Salviati: This is a common question, Simplicio, and a good one to 
ask when you first hear about Cantor's diagonal proof.  No one can 
claim to understand the proof unless they can explain clearly why 
it works for reals and not for rationals.

A set of objects is said to be countably infinite if the elements 
can be placed in a 1-to-1 correspondence with the integers 0,1,2,3,..
Some examples of countably infinite sets are illustrated below

             Even                             Positive
       N     Magnitudes  Integers   Squares   Rationals
      ---    ---------   -------    -------   ---------
       0        0           0          0         1
       1        2          -1          1        1/2
       2        4           1          4        2/1
       3        6          -2          9        1/3
       4        8           2         16        3/1
       5       10          -3         25        1/4
       6       12           3         36        2/3
       8       14          -4         49        3/2
       9       16           4         64        4/1
      etc.     etc.        etc.      etc.       etc.

In each case we can show that every element of the set appears
exactly once in the list.  You mentioned that you were particularly
interested in the rational numbers.  The pattern we've chosen is
to take k=1,2,3,... and for each value of k list all the fractions 
n/d  with  n + d = k  and  gcd(n,d)=1, in increasing order of n.
Most people are fairly satisfied that each rational number will
appear exactly once on this list.  (Note that the ordering we've 
chosen is not unique, but a single successful ordering is enough 
to prove that it can be done.)

Now your question is, if we list the rationals in the form of decimal
expansions, and apply Cantor's diagonal argument, won't we construct
another rational number that is NOT contained in the above sequence?
If so, we would have a contradiction, and something would be seriously 
wrong somewhere.

Fortunately, the diagonal argument applied to a countably infinite 
list of rational numbers does not produce another rational number.  
To understand why, imagine you have expressed each rational
number on the list in decimal notation as follows

                       Positive
       N               Rationals
      ---             -----------
       0          1  =  1.00000...
       1         1/2 =  0.50000...
       2         2/1 =  2.00000...
       3         1/3 =  0.33333...
       4         3/1 =  3.00000...
       5         1/4 =  0.25000...
       6         2/3 =  0.66666...
       8         3/2 =  1.50000...
       9         4/1 =  4.00000...
       etc.              etc.

As you know, each of these numbers ends in an infinitely repeating
finite sequence of digits.  For example, 1/7 = 0.142857 142857 142857
and so on.  Conversely, if the decimal representation of a number
does NOT eventually turn into a repetition of a finite sequence of
digits, then (by definition) it's not a rational number.  (It's
important to keep this in mind.)

Now, let's apply Cantor's procedure to an infinite list of rational
numbers.  There are many different ways we can choose the digits of
this new number, the only requirement being that the number must differ 
in at least one decimal place from each number on the list.  (There's 
also a technical requirement to avoid any of the alternate decimal 
representations of numbers, because for example 1=0.9999... but God 
knows we don't want to get into that here.) The digits of our new 
number are shown in square brackets on the diagonal

  [3]. 0 0 0 0 0 0 0 0 0...
   0 .[1]0 0 0 0 0 0 0 0...
   2 . 0[4]0 0 0 0 0 0 0...
   0 . 3 3[1]3 3 3 3 3 3...
   3 . 0 0 0[5]0 0 0 0 0...
   0 . 2 5 0 0[9]0 0 0 0...
   0 . 6 6 6 6 6[2]6 6 6...
   1 . 5 0 0 0 0 0[6]0 0...
   4 . 0 0 0 0 0 0 0[5]0...
            etc.

So our new number starts out as 3.14159265...  (Incidentally, does
anyone know at what point we would have to deviate from the digits
of pi as we continue down this list?  For the answer, see 
Interfering With PI).

Anyway, the point is that in order to prove that we have constructed 
a new RATIONAL number we need to prove that the number on the diagonal 
eventually falls into a pattern of a repeating finite string of 
digits.  Without being able to prove this, all we can say is that 
we've produced a new number that was not on the original list, but 
we can't claim to have produced a new RATIONAL number.

Now you might wonder, given the fact that we have quite a bit of
free choice in selecting the digits of our new number, if we couldn't
somehow choose the digits so that they do eventually repeat.  After
all, every number of the original list eventually repeats in a finite
number of digits, so why can't our "sidestepping" repeat with a period 
equal to the least common multiple of all the finite periods of the 
rational numbers on the list?  

The answer to that question is the key to the entire discussion.
The digits of every rational number repeat after some finite number
of digits, so the "period" of every rational number is finite.  
However, there is no upper bound on the period of rational numbers,
i.e., the periods are all finite, but there is no largest period.
Thus, in a manner of speaking, the least common multiple of this set
of strictly finite things is infinite.  So there's really no hope
that our diagonal digits will have a finite period.  From this we
conclude that our original listing of the rationals that seemed to
include all of them, really does include all of them.  Cantor's
diagonal argument has not led us to a contradiction.

Of course, although the diagonal argument applied to our countably
infinite list has not produced a new RATIONAL number, it HAS produced
a new number.  The new number is certainly in the set of real numbers,
and it's certainly not on the countably infinite list from which it
was generated.  This applies to any countably infinite list that
contains at least all the rational numbers: the new number we produce
will be a real and irrational number.  From this we conclude, perhaps
surprisingly, that no countably infinite list of numbers can include 
all the real numbers.  It was from this that Cantor realized it's
possible to speak meaningfully about different kinds of infinities.

Various philosophical objections can be (and have been) raised against 
this kind of reasoning.  Some mathematicians gone so far as to deny 
the "existence" of irrational numbers, and it's certainly true that
this kind of reasoning about infinities eventually leads to results 
that are genuinely counter-intuitive, if not actually paradoxical 
(such as the Banach-Tarski Theorem), but it hasn't been shown to be 
internally inconsistent.

Simplicio:  You said there is no upper bound on the size of natural 
numbers, and thus the least upper bound on the naturals is infinite, 
even though every natural number is finite.  To me this implies that
there can be numbers which do not have such a bound.  Is that not so?

Salviati: It sounds like you're trying to invent a kind of "number" 
that has infinitely many digits in the direction of geometrically 
increasing significance, somewhat analagous to the reals, which have
infinitely many digits in the direction of geometrically decreasing 
significance.  Number systems like what you are talking about have 
actually been developed, Simplicio, (see p-adic numbers) but the 
crucial difference is that the infinite sequence of digits is in 
the direction of increasing, not decreasing, significance, so the 
resulting implied "sum" does not converge to a value that behaves 
consistently like a magnitude.  (The valuations are said to be "non-
Archimedian".)  There's nothing wrong with conceiving new forms of 
numbers like this, but we need to be clear about how they differ 
from other forms of numbers.

Simplicio: Irrational numbers, such as the square root of 2, are 
suggested as, in the number of digits in their decimal expansion, 
not having this bound.  I suggest that it reflects a misunderstanding
of infinity to believe that such numbers can be exactly represented 
by an infinite decimal expansion, since the existence of numbers 
with such expansions is purely hypothetical, and that it is better 
to say that such numbers can only be closely approximated by a finite
decimal expansion.

Salviati:  You're certainly free to admit into your mathematics only 
those things that you see fit, Simplicio.  However, limiting yourself 
to only magnitudes whose decimal expansions are finite is a somewhat 
arbitrary restriction.  Many magnitudes have infinite expansions 
in base 10 (such as 1/3 = 0.33333....) whereas they have finite 
expansions in some other base (e.g., 1/3 = 0.1 in base 3).  This 
might lead you to modify your restriction to allow only magnitudes 
whose expansions are, in some sense, definable.  For example, even 
though there are infinitely many digits in 0.33333.... we know clearly
the "rule" that determines what those digits are, so we accept the 
completed infinity of digits, even though we can't type them all out.
But if you use this as your criterion, then you are hard pressed not 
to accept sqrt(2) as an acceptable magnitude, because we also know 
the "rule" for determining those digits.  Admittedly the "rule" is 
much simpler in the case of 0.33333...., so you might try to restrict
your "acceptable magnitudes" based on the complexity of the rule.  

Overall, it sounds like you're trying to define a class of numbers 
that includes the rationals plus all the irrational magnitudes that 
have some acceptably simple definition.  You would then call this 
overall set "the real numbers", and assert that Cantor's diagonal 
argument does not apply (because any acceptably simple definition is
presumably one of at most a countably infinite set of definitions).
You would be right in asserting that your set of numbers has the
same cardinality as the integers, but I think you would be better
advised not to call them "the real numbers", so as to avoid
confusion with a set that has previously been postulated by other 
people on somewhat different premises.  Think of a new name for 
your set of numbers, and call yourself a constructivist, and most 
of your critics will leave you alone.

Simplicio: Cantor's diagonal proof starts out with the assumption 
that there are actual infinities, and ends up with the conclusion 
that there are actual infinities.

Salviati: Well, Simplicio, if this were what Cantor had done, then 
surely no one could disagree with his result, although they may 
disagree with the premise.  What he actually did was somewhat more
ambitious, and quite a bit more interesting.  He started with the 
assumption of actual infinity and ended up showing that this implies
more than one kind of infinity!  Again, you may disagree with the 
premise, but given the premise his conclusion follows, and it is 
really quite an interesting conclusion.

Return to MathPages Main Menu