A Refutation of the Diagonal Argument

Show more

Received 27 June 2016; accepted 27 August 2016; published 30 August 2016

1. Introduction

The basic usage of numbers is counting objects, followed by measuring length. For the latter, this requires determining the unit of length. Then, the length can be quantified and represented by its ratio to the unit length. If we ignore the small error, this method is sufficient for practical usage. However, the ancient Greeks discovered a length that did not have a ratio of itself to the unit length. They named it the irrational magnitude. It can exist only in the theoretical sense. Even though the discovery was a big shock for rationalism, nobody had thought that real numbers were uncountable before the 19th century. Georg Cantor devised the diagonal argument in the 19th century (Cantor, 1890-91) , claiming that real numbers were uncountable. Subsequently, he constructed the theory of transfinite numbers (Cantor, 1952) . Furthermore, his set theory has influenced many areas of modern mathematics (Dauben, 1979) . However, this paper shows that the diagonal argument cannot be applied to the sequence of the potentially infinite number of potentially infinite binary fractions, which contains all n-bit binary fractions in the interval [0,1) for any n.

2. Cantor’s Diagonal Argument

First, we introduce the original form of Cantor’s diagonal argument. It is a very famous proof of the uncountability of real numbers, using an infinite binary representation of the real number. An outline is as follows. If real numbers are countable, they must be enumerable. Consider the sequence:

(1)

where F_{∞}(n) represents the infinite binary representation of the n-th real number, and a_{nm} represents the n-th bit of the m-th binary fraction with diagonal bits enclosed in square brackets. Suppose that all infinite binary representations of all real numbers in the interval [0,1] are enumerated in Sequence (1). Next, we can compose the anti-diagonal number X in the following manner.

(2)

We choose the n-th bit b_{n}, which is different from the n-th diagonal bit a_{nn}. As a result, X differs from F_{∞}(n) at a_{nn}. Thus, X does not exist in Sequence (1). This contradicts the premise that the above sequence contains all binary fractions in the interval [0,1]. Therefore, real numbers are uncountable.

3. Any Natural Number Is Finite

Next, we consider the meaning of the infinite decimal. Let us start with a simple example. Consider the equation: 1/3 = 0.333・・・. When we divide 1 by 3, the answer is 0.3 with a remainder of 0.1. Next, 0.1 is divided by 3equals 0.03 with a remainder of 0.01. Then, 0.01 is divided by 3 equals 0.003 with a remainder of 0.001 and so on. Thus, we get only one digit at one division. Furthermore, when we write a decimal, we write one digit at one time, and so the infinite decimal is made from a one-digit decimal repeatedly and without limit by adding a digit. Since this operation is endless, we never reach the infinite decimal. Moreover, the infinite decimal is physically impossible according to the following reasoning. Resources are surely required in order to hold a single digit. For example, we need a storage device like a hard disk for electronic records, or ink and paper for tangible records. That is, if we want to hold a single digit, we need a recording medium, which is made of matter. Regardless how technology progresses, a minimum substance will always be required as the recording medium of a single digit. However, our accessible universe is finite because our moving velocity is finite. Even with all the resources of our accessible universe, we could not use infinite resources. No matter how small the requirement to hold a single digit, it would be impossible to apply it to the infinite decimal, as our finite resources would necessarily be exhausted.

Next, any natural number is finite. The proof by mathematical induction is as follows.

1) 1 is finite.

2) If n is finite, then n + 1 is finite.

3) Any natural number is finite.

Surely, the infinite natural number cannot exist. However, there is no limit to how large a natural number can be. That is, we cannot simply say that the natural numbers are finite since we can always make a natural number larger than an arbitrary natural number by adding one, which can be repeated endlessly. Hence, there is an infinite possibility of the existence of natural numbers larger than any natural number. Aristotle named this possibility the potential infinity (Aristotle et al., 1996) .

4. Potential Infinity

According to these examples, the potential infinity is a dynamic state; it is always under construction. If the potential infinity were a static state, it would be finite or infinite. If it were finite, it would have a fixed value, which cannot be the potential infinity. If it were actually infinite, our resources would be insufficient. Hence, the potential infinity must be always under construction in reality.

The value of the potential infinity is undetermined because the potential infinity is always under construction. How is the value of the potential infinity determined? The typical example is Archimedes’ axiom. If ε and mare positive numbers such that ε < m, there is a natural number n such that nε > m. In this case, we can freely choose n after we know the value of ε and m. We are like unbeatable poker players who know all of our opponents’ cards.

The potential infinity is similar to the game, in which victory always goes to the player who makes the second move. For example, if two players compete to say the bigger number, the player making the second move is always the winner. After the first player says a number, the second player can easily win by choosing a larger number, even if it is only by adding one.

5. Potentially Infinite Decimal

Even though the infinite decimal is physically impossible, it is used in mathematics because it is convenient. Let us consider the meaning of the infinite decimal in mathematics. A simple example is shown in (3).

(3)

We often see the above example. If we regard 0.3333・・・ as the actually infinite decimal, then the above equation is completely true and the number of digits of the actually infinite decimal is not a natural number. However, we never reach the actually infinite decimal while the number of digits of the finite decimal is a natural number. A natural number plus a natural number is a natural number. If we add any number of digits to a finite decimal, we still cannot make an actually infinite decimal from a finite decimal. Further, we cannot make 1/3 from a finite decimal by adding digits to it. What is the difference between actually infinite decimal 0.3333・・・ and 1/3? They are the same thing. We can similarly discuss irrational numbers. For example, when we assume that π equals the actually infinite decimal 3.1415・・・, we regard 3.1415・・・ as another expression of π. That is, the actually infinite decimal is necessary for expressing numbers which cannot be expressed by the ordinal decimal. We should regard the actually infinite decimal, which expresses the irrational number, as the irrational number itself. Since we cannot make the actually infinite decimal from the ordinal decimal, we can consider that the actually infinite decimal is not the decimal. When we exclude the actually infinite decimal from the decimal, the number of digits of any decimal is a natural number.

When we accept the premise that the number of digits of a decimal is a natural number, the infinite decimal cannot exist. What does this mean for the right side of Equation (3)? A convincing answer is that it represents the potentially infinite decimal. That is, it can be the decimal, which has any large number of digits. However, the number of digits never reaches infinity. Hence, the potentially infinite decimal is always under construction.

We shall consider the justice of the Equation (3). The difference between then-digit decimal 0.333・・・3 and 1/3 is 1/3 × 1/10^{n}.

(4)

As n increases, the difference between the n-digit decimal 0.333 × 3 and 1/3 approaches 0 without limit.

(5)

However, the difference between the n-digit decimal 0.333・・・3 and 1/3 is not equal to 0. Unlike the actually infinite decimal, the potentially infinite decimal 0.3333・・・ is not exactly equal to 1/3 (Mueckenheim, 2015) . We may not use an equal sign in Equation (3).

6. The Diagonal Argument Cannot Be Applied to the Sequence of All n-Bit Binary Fractions

Next, we use binary fractions for simplification, and examine the applicable limit of the diagonal argument to finite binary fractions. To start, we enumerate all 1-bit binary fractions in the interval [0,1) in ascending order:

(6)

where F_{n}(m) is the m-th n-bit binary fraction and diagonal bits are enclosed in square brackets. Cantor’s diagonal argument is applied to Sequence (6). We can compose the anti-diagonal number X = 0.1. However, X equals F_{1}(2). Next, we shall expand the sequence of all 1-bit binary fractions to the sequence of all 2-bit binary fractions. For this purpose, 1-bit binary fractions have to be converted into 2-bit binary fractions. First, we add 0 as the last bit of each binary fraction of Sequence (6). Then, we get all 2-bit binary fractions whose last bits are 0. Next, we add 1 as the last bit of each binary fraction of Sequence (6), giving us all 2-bit binary fractions whose last bits are 1. As a result, Sequence (7) contains all 2-bit binary fractions.

(7)

Next, Cantor’s diagonal argument is applied to Sequence (7). We can compose the anti-diagonal number X = 0.11, which differs from the diagonal number in each bit. However, X is different from only the first two numbers in Sequence (7) and X equals F_{2}(4).

Now, we generalize the above procedure. Consider the following Sequence (8), which contains all n-bit binary fractions:

(8)

We can expand this by a two-step operation. First, we add 0 to the last bit of each binary fraction. Second, we add 1 to the last bit of each binary fraction. Finally, we get the following Sequence (9), which contains all (n + 1)-bit binary fractions:

(9)

Next, we apply Cantor’s diagonal argument to the sequence of all n-bit binary fractions:

(10)

where diagonal bits are enclosed in square brackets. In Sequence (10), the n-th bit of each binary fraction, from the 1-th binary fraction to the 2^{n}^{−1}-th binary fraction, is 0. Hence, any bit after the binary point of the anti-di- agonal number is 0. Obviously, the anti-diagonal X equals F_{n}(2^{n}).This is a clear counter-example of the diagonal argument. If a valid counter-example exists, the diagonal argument is false._{ }

If the n-bit binary fractions are shuffled, the diagonal number transforms into various numbers. However, we cannot make a new number that is not in the n × 2^{n} sequence because it contains all n-bit binary fractions. Furthermore, the diagonal number is only n-bits after the binary point. On the contrary, the sequence contains 2^{n} binary fractions. The ratio of n to 2^{n} is monotonously decreasing. As n increases, n/2^{n} approaches 0:

(11)

Therefore, Cantor’s diagonal argument has no application to all n-bit binary fractions in the interval [0,1).

7. The Diagonal Argument Cannot Be Applied to the Sequence of the Potentially Infinite Binary Fractions

Finally, we apply the diagonal argument to the sequence of the potentially infinite number of potentially infinite binary fractions. Considering Sequence (12), which contains all n-bit binary fractions in the interval [0,1), we can expand the sequence of all n-bit binary fractions by using the above method. When we increase bits one by one, we can make the (n + 1) × 2^{n}^{+1} sequence, the (n + 2) × 2^{n+}^{2} sequence, the (n + 3) × 2^{n}^{+3} sequence, and so on. No matter how large the sequence is, it is isomorphic. When this operation is continued endlessly, the sequence contains a potentially infinite number of binary fractions. Next, we add endlessly repeated zeros to each binary fraction of the sequence. Then, each binary fraction can be regarded as the potentially infinite binary fractions.

(12)

Now, we get the sequence of the potentially infinite number of potentially infinite binary fractions. Sequence (12) contains all n-bit terminating binary fractions for every n, and they are converted into potentially infinite binary fractions. Let us apply the diagonal method to Sequence (12). Diagonal bits are enclosed in square brackets. Obviously, any bit after the binary point of the anti-diagonal number is 1. No matter how large n is, the first n-bits portion of the anti-diagonal number is equal to that of the 2^{n}-th binary fraction in Sequence (12). This logic is the same as the logic applied to finite binary fractions. Therefore, the diagonal argument cannot be applied to Sequence (12). That is, we demonstrate that the diagonal argument cannot be applied to the sequence of potentially infinite binary fractions, which contains all n-bit binary fractions in the interval [0,1) for any n. Since the diagonal argument is the starting point of the set theory (Lavine, 1994) , which is the basis of many areas of modern mathematics, this paper questions the foundation of widely used and studied mathematical fields.

References

[1] Aristotle, Waterfield, R., & Bostock, D. (1996). Physics. Oxford: Oxford University Press.

[2] Cantor, G. (1890-91). über eine elementare Frage der Mannigfaltigkeitslehre, Jahresber [On an Elementary Question on Set Theory]. derDeutschen Math. Vereinigung Bd, 1, 75-78.

[3] Cantor, G. (1952). Contributions to the Founding of the Theory of Transfinite Numbers. New York: Dover Publications.

[4] Dauben, J. (1979). Georg Cantor. Cambridge, MA: Harvard University Press.

[5] Dehaene, S. (2002). Single-Neuron Arithmetic. Science, 297, 1652-1653. http://dx.doi.org/10.1126/science.1076392

[6] Lavine, S. (1994). Understanding the Infinite. Cambridge, MA and London: Harvard University Press.

[7] Mueckenheim, W. (2015). Sequences and Limits. Advances in Pure Mathematics, 5, 59-61.
http://dx.doi.org/10.4236/apm.2015.52007