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 onetoone correspondence with the decimal numbers in a list, and the list can be put in a table, thus: Table 1
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 onetoone correspondence with a decimal number between 0 and 1. Now consider the decimal number X = 0.x_{1}x_{2}x_{3}x_{4}x_{5} ... x_{k} ... , where x_{1} is any digit other than d_{11}; x_{2} is different from d_{22}; x_{3}is not equal to d_{33}; x_{4} is not d_{44}; 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 D_{1}. Similarly, X can't be second in the list, because X and D_{2} have different hundredthsplace digits; and X can't be third in the list, because X and D_{3} have different thousandthplace digits. In general, X can't be the n^{th} in the list  i.e., it cannot be equal to D_{n}  since their n^{th} 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 onetoone 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).
But we can easily counter Cantor's argument. Yes, we can say, it is true that the decimal number X = 0.x_{1}x_{2}x_{3}x_{4}x_{5} ... x_{k} ... 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 (notyetlisted  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 onetoone 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 onetoone correspondence with the natural numbers. In this Section we shall actually disprove Cantor's thesis: we shall show that the decimal number X = 0.x_{1}x_{2}x_{3}x_{4}x_{5} ... x_{k} ... 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 x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, ... x_{k} ... 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 nonzero. Thus no matter how large _{k }gets, the probability of X = 0.x_{1}x_{2}x_{3}x_{4}x_{5} ... x_{k} ... existing on the list after n must be a small but nonzero number. But since the list of naturals is assumed to be infinite, the probability of the decimal number X = 0.x_{1}x_{2}x_{3}x_{4}x_{5} ... x_{k} ... 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 x_{k} is not the last digit in X = 0.x_{1}x_{2}x_{3}x_{4}x_{5} ... x_{k} ..., and that there are an infinite number of digits after x_{k}. This is true, but even so, the probability of the decimal number X = 0.x_{1}x_{2}x_{3}x_{4}x_{5} ... x_{k} ... 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 nonzero 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.x_{1}x_{2}x_{3}x_{4}x_{5} ... x_{k} ... 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 onetoone correspondence with it ... ... Q.E.D. (And this time for real!)
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 onetoone 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
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 onetoone correspondence with another natural number. Now consider the natural number X = x_{1}x_{2}x_{3}x_{4}x_{5} ... x_{k} ... , where x_{1} is any digit other than d_{11}; x_{2} is different from d_{22}; x_{3}is not equal to d_{33}; x_{4} is not d_{44}; 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 D_{1}. Similarly, X can't be second in the list, because X and D_{2} have different secondplace digits; and X can't be third in the list, because X and D_{3} have different thirdplace digits. In general, X can't be the n^{th} in the list  i.e., it cannot be equal to D_{n}  since their n^{th} 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 onetoone correspondence with the natural numbers themselves is impossible! But this is utterly absurd, and therefore something must be terribly wrong with Cantor's socalled "proof". (Actually, what's really absurd is the way people keep on repeating Cantor's argument, and affirming it to be a solid castiron 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 GrubbsSaleem. 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? Email me.
