A SIMPLE ARGUMENT AGAINST
CANTOR'S DIAGONAL PROCEDURE

(Purportedly Proving that the Set of Real Numbers is Uncountable)
 

by

Ardeshir Mehta, N.D.

June 2001



1. Cantor's Diagonal Procedure

(I have adapted the following bit from the Mathematics Web pages of the Belleview Community College, Washington State, USA). 

Cantor argues as follows: 

Suppose that the infinity of real numbers is countable -- i.e., supposing, say, the set of decimal numbers between zero and one is the same as the infinity of counting numbers. Then the decimal numbers can be put in one-to-one correspondence with the decimal numbers in a list, and the list can be put in a table, thus: 

Table 1


 
Natural numbers Decimal Numbers Between 0 and 1
1 D1 = 0.d11d12d13d14 ... d1k ...
2 D2 = 0.d21d22d23d24 ... d2k ...
3 D3 = 0.d31d32d33d34 ... d3k ...
4 D4 = 0.d41d42d43d44 ... d4k ...
...  
n Dn = 0.dn1dn2dn3dn4 ... dnk ...
(etc.)  

Here, D represents any decimal number between 0 and 1, d represents any digit between 0 and 9 inclusive, the first subscript of any particular d is the natural number to which that particular d corresponds, and the second subscript of that same d is the number of places that particular d lies to the right of the decimal point. 

Now each row of the table represents, of course, a natural number put in one-to-one correspondence with a decimal number between 0 and 1. 

Now consider the decimal number X = 0.x1x2x3x4x5 ... xk ... , where x1 is any digit other than d11; x2 is different from d22; x3is not equal to d33; x4 is not d44; and so on. Now, X is a decimal number, and X is between 0 and 1, so it should be in our list. But where is it?

The decimal number X can't be the first in the list, since the first digit of X differs from the first digit of D1. Similarly, X can't be second in the list, because X and D2 have different hundredths-place digits; and X can't be third in the list, because X and D3 have different thousandth-place digits. In general, X can't be the nth in the list -- i.e., it cannot be equal to Dn -- since their nth digits are not the same. 

The decimal X is nowhere to be found in the list, no matter how large n gets. In other words, we have exhibited a decimal number that ought to be present in a huge humongous giganto list -- but it isn't. No matter how we try to list the decimal numbers, and how long the list gets, at least one decimal number will be left out. 

Therefore, argues Cantor, putting the decimal numbers in one-to-one correspondence with the natural numbers is impossible; and so the infinity of decimal numbers must be greater than the infinity of counting numbers. 
 

... Q.E.D. (Or so says Cantor).


2. Simple Argument Against Cantor's Purported Proof

But we can easily counter Cantor's argument. Yes, we can say, it is true that the decimal number X = 0.x1x2x3x4x5 ... xk ... is not in the part of the list above the natural number n. But there is an infinitely huge part of the list of natural numbers after n! This infinite list is compressed and almost hidden by those three small letters "etc." at the bottom of Table 1. They may be small, but those three small letters "etc." represent a list of naturals infinitely longer than the list above n. 

All that Cantor has proved is that X is not on the list above n, no matter how large n may be. But he has not proved that X is not in the (not-yet-listed -- and indeed unlistable, because infinitely large) part of the table after n ... and he cannot prove that! After all, no matter how large n gets, the part of the table afternstill remains infinitely larger than the part of the table beforen. 

And note that no matter how large n gets, the list after n can never be "brought up" to be included in the part of the list before n. This is because the part of the list before n is necessarily finite, while the part of the list after n must be infinitely long!

(That is, of course, if you really accept that the natural numbers are infinite -- because if, like the Intuitionists, Constructivists and Finitists, you don't accept that, this whole argument is moot.)

In any case, we have demonstrated above that Cantor has not proved his thesis, viz., that all the decimals between 0 and 1 cannot be put into one-to-one correspondence with the natural numbers. His entire argument is based on tricking you into believing that the list is complete, when in actual fact it isn't ... and never can be.

3. Argument Disproving Cantor's Diagonal Procedure

Now we admit that in Section 2 above we have not actually disproved Cantor's argument. But we have proved that Cantor has not proved his own thesis, namely that all the decimals between 0 and 1 cannot be put into one-to-one correspondence with the natural numbers.

In this Section we shall actually disprove Cantor's thesis: we shall show that the decimal number X = 0.x1x2x3x4x5 ... xk ... must be in Table 1 -- specifically, on the list after n.

To do this we calculate the probability of X existing on the list after n. Note that x1, x2, x3, x4, x5, ... xk ... are all digits from 0 to 9 inclusive. The probability of any permutation of digits from 0 to 9 inclusive existing in a list of such permutations of digits is non-zero. Thus no matter how large k gets, the probability of X = 0.x1x2x3x4x5 ... xk ... existing on the list after n must be a small but non-zero number.

But since the list of naturals is assumed to be infinite, the probability of the decimal number X = 0.x1x2x3x4x5 ... xk ... existing in this infinitely large part of the list after n must be 100%!

That is because given an infinite number of chances of something happening, no matter how small the probability of it happening just once, as long as its probability of happening even once is not absolutely zero, it must happen if there are an infinite number of chances of it happening.

It might be argued that xk is not the last digit in X = 0.x1x2x3x4x5 ... xk ..., and that there are an infinite number of digits after xk. This is true, but even so, the probability of the decimal number X = 0.x1x2x3x4x5 ... xk ... existing on the list after n is infinitesimally small; but small as it is, it is still not zero.

And by the laws of probability, a non-zero probability of anything happening, given an infinite number of chances for it to happen, requires us to concede that it must happen.

If X = 0.x1x2x3x4x5 ... xk ... must exist on the list after n, then given an infinite number of naturals, a natural can be found in this part of the list -- namely after n -- which can be put in one-to-one correspondence with it ... 


... Q.E.D. (And this time for real!)


 4. The Clinching Argument

It is to be noted that if we adapt Cantor's proof to natural numbers, we can "prove" that natural numbers themselves cannot all be put in one-to-one correspondence with (other) natural numbers! Talk about a reductio ad absurdum.

Note that if we put all the natural numbers in the left column of a table, and then put other natural numbers in the right column, just as we have done for Table 1, we would get Table 2, as follows:

Table 2


 
Natural Numbers Other Natural Numbers
1 D1 = d11d12d13d14 ... d1k ...
2 D2 = d21d22d23d24 ... d2k ...
3 D3 = d31d32d33d34 ... d3k ...
4 D4 = d41d42d43d44 ... d4k ...
...  
n Dn = dn1dn2dn3dn4 ... dnk ...
(etc.)  

In this table, D now represents any natural number, d again represents any digit between 0 and 9 inclusive, the first subscript of any particular d is the natural number to which that particular d corresponds, and the second subscript of that same d is the number of places that particular d lies to the right of the starting digit of the particular D to which that particular d belongs. (When we say "starting digit" we mean the first digit one normally writes down when one begins writing the natural number in question.)

Now each row of the table represents, of course, a natural number put in one-to-one correspondence with another natural number.

Now consider the natural number X = x1x2x3x4x5 ... xk ... , where x1 is any digit other than d11; x2 is different from d22; x3is not equal to d33; x4 is not d44; and so on. Now, X is a natural number, so it should be in our list. But where is it?

The natural number X can't be the first in the list, since the first digit of X differs from the first digit of D1. Similarly, X can't be second in the list, because X and D2 have different second-place digits; and X can't be third in the list, because X and D3 have different third-place digits. In general, X can't be the nth in the list -- i.e., it cannot be equal to Dn -- since their nth digits are not the same. 

The natural number X is nowhere to be found in the list, no matter how large n gets. In other words, we have exhibited a natural number that ought to be present in a huge humongous giganto list -- but it isn't. No matter how we try to list the natural numbers, and how long the list gets, at least one natural number will be left out. 

Therefore, using Cantor's own argument, we have "proved" that putting the natural numbers in one-to-one correspondence with the natural numbers themselves is impossible! 

But this is utterly absurd, and therefore something must be terribly wrong with Cantor's so-called "proof". 

(Actually, what's really absurd is the way people keep on repeating Cantor's argument, and affirming it to be a solid cast-iron proof, virtually ad nauseam, in all the high school, college and university mathematics textbooks -- and even in prestigious volumes such as those of the major Encyclopaedias. One wonders where their authors' and editors' heads are at!)

Acknowledgements

G. Walton's excellent page <http://home.btconnect.com/sapere.aude/page2.html> was the inspiration for the above argument.

I was also inspired by the page entitled "Problems with Cantor's Diagonal Method and Infinity in General" by Daniel Grubbs-Saleem. This page used to be at <http://users.javanet.com/~cloclo/infinity.html>,but it seems to have been taken down from the internet (as of July 2012).

Comments

Any comments? E-mail me.