Hesperus is Bosphorus

A group blog by philosophers in and from Turkey

Archive for July 2016

What is Wrong with Cantor’s Diagonal Argument?

with 40 comments

Cantor gave two purported proofs that the cardinality of the set of real numbers is greater than that of the set of natural numbers. According to a popular reconstruction of the more widely known of these proofs, his diagonal argument, Cantor randomly tabulates the real numbers in the interval [0, 1) in an array. I will use a binary version of the Cantorian table for ease of exposition and give Table 1 as an example:

1    0.10111011000 …
2    0.11010111000 …
3    0.11010001110 …
4    0.01101110001 …
5    0.10000100011 …
6    0.00111111111 …
7    0.00101110001 …
8    0.11000110100 …
9    0.11101100101 …
10  0.01111011100 …
11  0.01010101010
                 .
                 .
                 .

          Table 1

Cantor asks us to assume for reductio purposes that this table is “complete” in the sense that it lists every real number in the interval [0, 1). The items in this list are enumerated by natural numbers shown in the column on the left-hand side of the table. The digits on the diagonal of the list (boldfaced) give us the infinitely long number d:

d = 0.11000110100 …

He then constructs a new number i from the diagonal of the table by substituting every 0 after the decimal point in d by 1, and every 1 in d by 0:

i = 0.00111001011 …

He asserts that this constructed number i is a real number in [0, 1) but it cannot be found in the putatively complete list, because i is guaranteed to differ from each number in the list as the number’s digit that falls on the diagonal is changed in i. For example, i differs from the number on the 7th line in at least in its 7th digit: the 7th digit of the number, viz. 1, which is also the 7th digit of the diagonal, is turned into 0 in the 7th digit of i. Similarly for each and every one of the other numbers in the list. So i cannot be a member of the list, even though we assumed initially that the list was complete.

No list of real numbers in [0, 1) to be set up in a similar table (but with a different ordering of reals) will manage to include all of the real numbers in [0, 1), for we can always construct some number i for any given list, which will be left out in the list. It follows, according to Cantor, that no such list will have the items in it being enumerable by natural numbers. Hence, there can be no bijection between the set of natural numbers and the set of real numbers in [0, 1). His conclusion is that the size, or cardinality, of the set of reals even only in the interval [0, 1) is greater than the cardinality of the whole set of naturals. This suffices to establish that the entire set of real numbers are also nondenumerably infinite.

Let me point to an immediate puzzle with Cantor’s argument above. I will call two binary numbers in [0, 1) “inverses” of each other if one number has 1 in a certain location after the decimal point, the other number has 0 in the corresponding location; and if it has 0 in that location, the other number has 1. Thus the numbers on lines 3 and 7, for example, are inverses of each other. So are the numbers on lines 5 and 10.  Crucially, d and i are also inverses of each other. If we are to assume this list is complete, every number in the list must have its inverse also included in the list. Cantor says i is not included in the list. But how come? The number i’s inverse, namely d, is in the list—it is on line 8. Since its inverse is in there, i must also be somewhere there, like every other pair of inverses. But if i cannot be in the list, as Cantor insists, then perhaps there is something wrong with his entire procedure.

I see a clear flaw in Cantor’s diagonalization procedure. This flaw makes it infeasible to construct the number i and thereby invalidate his proof. Let me illustrate the flaw on Table 2. It is obvious that, since d is a real number in the interval [0, 1), d must be included in the list—if we are to assume the list is complete. Suppose it is on line 8.

1    0.10111011000 …
2    0.11010111000 …
3    0.11010001110 …
4    0.01101110001 …
5    0.10000100011 …
6    0.00111111111 …
7    0.00101110001 …
8    0.1100011?100 …
9    0.11101100101 …
10  0.01111011100 …
11  0.01010101010
                  .
                  .
                  .
d = 0.1100011?100 …
 i = 0.0011100?011 …

            Table 2

The n-th digit of d after the decimal point comes from (is the same as) the n-th digit, after the decimal point, of line n in the table. Thus the first digit of d, namely 1, comes from the first digit of line 1. The fourth digit of d, namely 0, comes from the fourth digit of line 4, and so on. It will be noticed that the 8th digit of d (marked with ‘?‘ on line 8) is indeterminate: unlike the other digits of line 8, the 8th digit of line 8 does not come from any other line than line 8 itself. But then there is nothing to determine whether the 8th digit of line 8 must be 0 or 1. [1]

Thus, if d is included in the supposedly complete table, d will fail to satisfy a necessary condition for being a real number in [0, 1), viz. having all determinate digits. This of course entails that the value of the 8th digit of d’s inverse i will also be indeterminate, and hence i too fails to be a real number in [0, 1). The upshot is that Cantor’s supposition that he can unproblematically take the inverse of the diagonal of the table is false.

Actually not only the diagonal, but infinitely many other lines in a Cantorian table also give rise to a similar problem. In the example in Table 3 one of the lines that run parallel to the diagonal, call it a “quasi-diagonal line,” is indicated with boldface. Let the number d* consist of the first two digits of the first line appended to the digits of the quasi-diagonal line. If the table is to be assumed complete, the number d* will have to be a member of the table. Suppose it is on line 6. For reasons similar to the ones given for d above, the 8th digit of d* after the decimal point is indeterminate. (The corresponding digit of i*, which is the inverse of d*, will also be indeterminate, of course.)

1    0.101110110001 …
2    0.110101110000 …
3    0.110100011101 …
4    0.011011100010 …
5    0.100001000111 …
6    0.1011010?0010 …     =d*
7    0.001011100010 …
8    0.110001101000 …
9    0.111011001011 …
10  0.011110111000 …
                 .
                 .
                 .

`         Table 3

So, Cantor’s table involves an indeterminacy not only on the path of its diagonal. Since there are infinitely many quasi-diagonal lines in the table (only one of which is shown in Table 3), the Cantorian table contains infinitely many indeterminacies.

These problems arise from the fact that Cantor lists real numbers in the form of a table. Such a table appears to be a natural and innocuous way of displaying the totality of real numbers, but this appearance is deceptive. For, in a putatively exhaustive table of reals, there would have to be numbers—the diagonal number d, d* and infinitely many numbers like d*—that must cross each of the other numbers, including themselves and their inverses, at some digit, and this gives rise to the flaws we have pointed out. There is an alternative way of displaying the totality of real numbers, which raises no indeterminacies or contradictions. Moreover, as I show elsewhere, the reals (not only those in the interval [0, 1) but the entire set of real numbers) can be enumerated by natural numbers by using this alternative method. [2]

——————————————–

[1] I concealed the first flaw when setting up Table 1 earlier, for convenience of exposition.

[2] My much more detailed criticisms of Cantor’s arguments and my way of showing that reals cannot have a higher cardinality than naturals can be found at: https://www.academia.edu/36976458/CONTRA_CANTOR_HOW_TO_COUNT_THE_UNCOUNTABLY_INFINITE_

Advertisements

Written by Erdinç Sayan

July 31, 2016 at 1:55 pm