## Archive for **July 2016**

## What is Wrong with Cantor’s Diagonal Argument?

Cantor gave two 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 Cantor’s table for ease of exposition and give Table 1 as an example:

1 0.**1**0111011000 …

2 0.1**1**010111000 …

3 0.11**0**10001110 …

4 0.011**0**1110001 …

5 0.1000**0**100011 …

6 0.00111**1**11111 …

7 0.001011**1**0001 …

8 0.1100011**0**100 …

9 0.11101100**1**01 …

10 0.011110111**0**0 …

11 0.0101010101**0** …

.

.

.

*d* = 0.11000110100 …

*i* = 0.00111001011 …

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 numbers on the diagonal of the list (boldfaced in Table 1) give us the infinitely long number *d*. He then constructs a new number 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. He asserts that this constructed number is a real number in [0, 1) which cannot be found in the putatively complete list, because *i* is guaranteed to differ from each number in the list since the number’s digit that falls on the diagonal is changed in *i*. Since no list of real numbers (in this example the reals in [0, 1)) to be constructed in the same fashion will manage to include all of the real numbers in [0, 1), it follows, according to Cantor, that no such table will have the items in it being enumerable by natural numbers. His conclusion is that there have to be more real numbers than natural numbers. Hence the size, or cardinality, of the set of real numbers is greater than that of natural numbers.

Let me point out an immediate puzzle with Cantor’s argument. 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 in there, like every other pair of inverses.[1]

I see two flaws in Cantor’s diagonalization procedure. Let me illustrate the first one 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.**1**0111011000 …

2 0.1**1**010111000 …

3 0.11**0**10001110 …

4 0.011**0**1110001 …

5 0.1000**0**100011 …

6 0.00111**1**11111 …

7 0.001011**1**0001 …

8 0.1100011**?**100 …

9 0.11101100**1**01 …

10 0.011110111**0**0 …

11 0.0101010101**0** …

.

.

.

*d* = 0.1100011?100 …

*i* = 0.0011100?011 …

Table 2

The *n*-th digit of *d* after the decimal point comes from 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.

This of course entails that the value of the 8th digit of *d*’s inverse *i* is also indeterminate. Thus it appears that not only *i*, but—unfortunately for Cantor—even *d* cannot be included in the table, for both *d* and *i* fail to satisfy a necessary condition for being reals in [0, 1), viz. having determinate digits.

Let us forget about the first flaw for now and assume that there is a determinate diagonal of the Cantorian table (thus I disregarded the first flaw in Table 3 below and assigned 0 to the 8th digit of line 8, just as I did earlier in Table 1, for illustration’s sake). The second flaw arises from the following phenomenon: the diagonal and its inverse clash at some digit. Suppose the inverse *i* of the diagonal were on line 10 in Table 3:

1 0.**1**0111011000…

2 0.1**1**010111000…

3 0.11**0**10001110…

4 0.011**0**1110001…

5 0.1000**0**100011…

6 0.10111**1**11111…

7 0.001011**1**0001…

8 0.1100011**0**100…

9 0.01110011**1**00…

10 0.001110011**!**1…

11 0.0101000101**0**…

.

.

.

*d* = 0.110001101**!**0…

*i* = 0.001110010**!**1…

Table 3

Now, if the diagonal’s 10th digit (marked with ‘!’ on line 10) is 1, *i*’s 10th digit has to be 0, and if the diagonal’s 10th digit is 0, *i*’s 10th digit has to be 1. In other words, since the diagonal’s and *i*’s 10th digits coincide, we get the result that their shared 10th digit can be neither 0 nor 1. Hence inclusion of *i* in Cantor’s table leads to paradox! But as we have argued earlier, *i* *must* be included (assuming *d* could) in a table that claims to be complete—complete even if only for *reductio* purposes.

It is obvious that at the root of these two flaws is the fact that Cantor lists real numbers in the form of a *table*. Such a table turns out to be a deceptively misleading way of displaying real numbers.[2]

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

[1] If *i* were not to be in the list although its inverse is, we could not assume the list was complete to begin with.

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