Countability of Infinite Paths in the Infinity Tree: Proof of the Continuum Hypothesis in a Non-Cantorian Infinity Theory ()
1. Introduction
A previous paper discussed how the infinite set of real numbers between 0 and 1 could be represented by a tree structure with a countably infinite number of nodes, called the ‘infinity tree’. [1] There is a one-to-one correspondence between infinite paths from the root node of the tree and infinite decimal expressions for numbers in the interval [0, 1). That paper did not claim to prove that the number of infinite paths is countably infinite, and noted that such a proof would contradict Cantor's diagonalization argument [2] that the real numbers in the interval [0,1] are uncountably infinite.
This present paper shows that a Turing machine could write all the infinite paths of the infinity tree to a constant, finite set of countably infinite tapes, if it performs a countably infinite number of processing steps, requiring only a constant finite set of processing states. Hence this paper finds that the real numbers in the interval [0,1] are countably infinite, and proposes a non-Cantorian theory of infinity based on Turing machines using countably infinite space and time. In this theory, Cantor’s Continuum Hypothesis is true, since there is no set with cardinality between that of the integers and the real numbers. And in this theory, the power set of the natural numbers P(ℕ) is countably infinite, which contradicts the claim of Cantor’s Theorem for the natural numbers.
However, this paper does not claim there is an error in Cantor’s arguments that [0, 1] is uncountably infinite. Rather, this paper considers the situation as a paradox, resulting from different choices about how to represent and count the continuum of real numbers.
2. Types of Infinity Discussed in This Paper
It may help to briefly list the different kinds of infinity discussed in this paper, and briefly describe how this paper discusses them:
The “countable infinity” of the natural numbers: 0, 1, 2, 3, 4, …
The “countable infinity” of spaces on a Turing machine’s tape. I shall consider a Turing machine which has twelve tapes, with each tape having a countable infinity of spaces. I will discuss an “infinite time Turing machine” which performs a countable infinity of processing steps. (A tape may be regarded as countably infinite in both directions. However, my discussion will only use a countably infinite number of cells in a single direction from a starting point on each tape).
The “infinity tree” [1] which has a countable infinity of nodes, a countable infinity of arcs, and an infinity of infinite paths descending from the root node, each path corresponding to an infinite decimal expression in the range [0, 1), i.e., [0.0000…, 0.9999…].
It should be noted that this paper includes 0 in the natural numbers.1 However, we shall later see that this doesn’t matter when considering Cantor’s Theorem.
The central question studied in this paper will be whether the number of infinite paths in the infinity tree is countably infinite or is an uncountable infinity. This paper will show that all the infinite paths in the infinity tree could be written onto a countably infinite tape of a Turing machine, in countably infinite Turing machine state transitions. Hence it will be argued that the set of infinite paths in the infinity tree is countably infinite, and that the set of infinite decimal expressions in the interval [0, 1) is countably infinite.
It should be noted that this paper does not use ‘limit equivalences’, such as “0.3999… = 0.4000…”. This paper is not concerned with such equivalences, which would only reduce the number of decimals to be considered in the range [0, 1). Hence such equivalences would work in favor of this paper’s argument that the set of decimals in the range [0, 1) is countably infinite.
This paper refers to the interval [0, 1] in several places, where it is making the claim that the set of numbers in the range [0, 1] is countably infinite. If we accept this paper’s argument that the set of numbers in the range [0, 1) is countably infinite, then it follows that the range [0, 1] is also countably infinite, since we can add the number 1 to the set [0, 1) and the resulting set is still countably infinite. Indeed, the Turing machine described here always adds the number “1” to the list of decimals that it writes to a countably infinite tape.
3. Definition of the Infinity Tree
The ‘infinity tree’ [1] is defined as follows:
1. The root node has the label ●, representing a decimal point, implicitly preceded by 0. That is, the root node should be visualized as 0.
2. Each node in the tree has pointers to 10 different nodes below it, labeled with the digits 0 through 9. The 10 nodes are unique to the node above them. No other node points to any of them.
3. The tree is not reentrant. No two nodes point to the same other node. There is no circular path between nodes. No node points to itself.
This is a simple infinite tree, with a branching factor of 10 arcs from each node. Just a few of the nodes and branches of the first few levels of the ‘infinity tree’ are shown in Figure 1. For the infinite tree, the following assertions hold:
Figure 1. A partial illustration of the first 4 levels of the infinity tree.
1. Every finite path from the root node to a descendant corresponds to a finite decimal number between 0 and 1. Therefore, every node below the root node also corresponds to a finite decimal number between 0.0 and 1.0, indicated by the path reaching it from the root node.
2. The nodes in the tree are countably infinite, i.e., each node can be counted by a distinct, sequential natural number (1, 2, 3, …). This can be done by navigating the tree breadth-first: The root node is counted 1. Its descendants are counted 2 through 11. The nodes at the next level down are counted 12 through 111, and so forth counting nodes breadth-first throughout the tree. Therefore, the set of all nodes in the infinite tree is countably infinite.
3. The arcs in the tree are also countably infinite, in the same breadth-first manner since each node has exactly ten arcs going from it.
4. For each non-root node N, there is a unique, finite path from the root node to node N. So, the number of finite paths to nodes in the tree is also countably infinite.
5. Every infinite path descending from the root node of the tree corresponds to an infinite decimal fraction, from zero up to .99999999… Mathematically, “0.” followed by an infinite number of 9’s is considered equal to 1. However, the tree does not literally include the path “1.0”, nor does it need to, for the purpose of discussion in this paper.
6. Every infinite decimal from 0 up to but not including 1 corresponds to an infinite path in the tree descending from the root node.
7. So, a countably infinite set of nodes and arcs comprises the infinite set of infinite paths from 0 downward through the tree.
8. So, a countably infinite set of nodes and arcs in a tree represents the set of infinite decimals from 0 up to but not including 1.
9. Therefore, the set of infinite decimals between 0 and 1 can be mapped to and represented by a countably infinite set of nodes and arcs. Any number between 0 and 1 can be reached to any desired degree of precision, with countably many nodes and arcs.
The infinity tree shows something specific and non-ambiguous: that a countably infinite set of nodes and arcs can exactly represent the set of all infinite decimals in the range [0, 1).
The following sections will discuss in more detail whether the set of infinite paths in the tree is countably infinite, or uncountably infinite. This question was left open in [1].
4. The Real Numbers in [0, 1] Are Countably Infinite
4.1. The Basic Argument
To discuss this topic, we begin by considering just the first three levels of the infinity tree below its root node. A list of the paths from the root node to each node at the third level below the root would look like:
. 0 0 0
. 0 0 1
. 0 0 2
…
. 9 9 8
. 9 9 9
Now suppose we try to diagonalize this list. We can choose any number we like to replace the first 0 in “. 0 0 0”. Whatever number we choose for the first digit will select some other number already in the list. Then whatever number we choose for the second digit will select some other number already in the list. And whatever number we choose for the third digit will select some other number already in the list. This is what I mean by saying the infinity tree cannot be diagonalized to specify a number that it does not contain. This applies from the root node of the tree to any finite number of levels below the root node.
Now imagine that a Turing machine [3] is designed to simulate a breadth-first descent through the infinity tree and to write decimal expressions that correspond to paths from the root node to nodes at each level of the infinity tree below the root node.
After it has descended three levels through the tree, it will have written the above expressions on its tape. After it has simulated descent through four levels of the tree, it will have written expressions from .0000 to .9999 to its tape. And so on: As it simulates breadth-first descent through the tree, it always writes a complete set of finite expressions from the interval between 0 and 1 to its tape, and the set of finite expressions can never be diagonalized to find an expression it does not contain.
The machine only requires a finite amount of time and processing to simulate descent to any finite level of the tree, although the amount of time and processing goes up by a multiple of 10 for each level. To write the expressions for paths to the nth level of the infinity tree to a Turing machine tape, the machine requires space for representing paths from the root to 10n nodes of the tree. Each path is of the form “0.” followed by n digits for choices in the tree along the path. Including a blank space after each path, the path requires n + 3 cells on a tape, i.e., O(n) space on a tape. Representing all 10n paths to level n requires (n+3)10n = n10n + (3*10n) cells on a tape, i.e., O(n10n) space on a tape. Using one more cell for writing “1” after all the paths to level n, the space required on a tape is still O(n10n).
The Turing machine never runs out of space on the infinite tape to write the paths to each finite level of the infinity tree. The Turing machine never runs out of discrete time steps to continue processing. For a Turing machine, countably infinite time never ends.
Since the infinity tree has a countably infinite number of levels, and the machine only uses finite time to process each level, the machine requires only countably infinite time and processing to simulate descent through all the levels of the tree. Also, the machine only requires countably infinite space on its tape to write the expressions for all the paths that it generates, representing numbers in the interval [0, 1], if it always writes 1 after writing 0.999... 9 for each level of the tree.
So, in countably infinite time, the Turing machine would write to a countably infinite tape all the decimal expressions in the interval [0, 1), plus the number 1. The set of starting locations for all these numbers would always be a subset of the countably infinite spaces on the Turing machine tape. So, the set containing the starting points of all these numbers would be countably infinite.
Therefore, we can argue that the set of real numbers in [0, 1] is countably infinite. This of course is a surprising conclusion, since it contradicts Cantor’s arguments that the real numbers in [0, 1) are uncountably infinite. Cantor’s arguments are discussed in Section 7.
4.2. Use of Twelve Tapes
For simplicity and efficiency, the Turing machine could actually use twelve countably infinite tapes. One of these tapes would be designated as the “input level tape”, and the other as the “output level tape”.
The machine would simulate performing a series of passes through successive levels of the infinity tree. In each pass, the machine would use decimal expressions on the input level tape representing all paths from the root node to level n of the tree, to support generating decimal expressions on the output level tape representing all paths from the root node to level n+1 of the tree.
The machine would use the other ten tapes (the “branch tapes”) to write decimal expressions representing extensions from the path to an individual node of the tree to paths for its ten child nodes at the next level of the tree. Only one node of the tree is processed as a parent at a time using these branch tapes. The ten branch tapes are individually named the “branch0tape”, “branch1tape”, “branch2tape”, …, “branch9tape”. (Appendix A gives pseudocode defining the operation of the machine.)
After computing and writing all information for level n + 1 of the infinity tree to the output level tape, the machine copies the information from the output level tape back to the input level tape. Both tapes then have the same information written to them, and the machine is ready to compute the expressions representing paths from the root node to the next level n + 2 of the tree.
And so on, for the countably infinite set of levels of the infinity tree.
For a Turing machine ([4], p. 298), initially all the cells on the twelve infinite tapes are blank, except for at most a finite number of cells on each tape that are initially non-blank. Without loss of generality, each tape can have a first, left-most cell, and a countably infinite number of cells to the right, i.e., each tape can be “singly infinite” ([5], p. 129).
For the Turing machine described here, initially each tape would have the symbol ‘*’ on its first cell, to support the state-transition function recognizing that the machine is at the left-most cell of the tape.2 All tapes will have only blank spaces on every other cell, except for the machine’s ‘input-level’ tape, which initially has “0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1” on its left-most cells. That is, the input-level tape initially has 11 finite numerical expressions, separated by single blank spaces between them.
The Turing machine would effectively generate and write the continuum of real numbers in [0, 1] within a countably infinite set of cells on a tape, using a countably infinite number of processing steps.
So again, the Turing machine supports the conclusion that the continuum of real numbers in the interval [0, 1] is countably infinite. Likewise, it supports the conclusion that the infinity tree contains only a countable infinity of countably infinite paths descending from its root node. One cannot diagonalize the infinity tree to specify any real number in the interval [0, 1] that the Turing machine discussed here does not generate, in writing all real numbers in that interval to a countably infinite tape.
4.3. Infinite Time Turing Machines
The Turing machine discussed here may be considered as an “infinite time Turing machine” (ITTM). However, it should be noted that there are different treatments and discussions of the ITTM concept. Stannett [6] surveyed the topic. It appears that most (and perhaps all) previously published papers on ITTM’s do not challenge the thinking that Cantor was correct in arguing that the real numbers are uncountably infinite. It does not appear that previous papers on ITTM’s have discussed the Turing machine design presented here.
Regarding ITTM’s, Hamkins [7] wrote: “The idea is to allow a Turing machine to compute for infinitely many steps, preserving the information produced while doing so, and allowing the machine to continue with more computation afterwards.”
This description implicitly represents time by the computation steps of a Turing machine. A unit of time (a discrete time step) corresponds to a single computation step, within which: a) a Turing machine reads a symbol on a tape; b) based on the machine’s current state, the machine may write a symbol on a tape, and then optionally move one space left or right on a tape; and c) optionally the machine may change its state. Precisely what happens within each computation step is specified by the finite state transition table for the Turing machine. For example, the table could specify that the machine will in parallel write a different symbol on different tapes, and then move one space left or right on each tape, all within a single computation step. [4] [5]
For a Turing machine, countably infinite time corresponds to a countably infinite sequence of computation steps. Likewise, countably infinite space corresponds to a Turing machine’s constant, finite set of countably infinite tapes. This paper will not discuss or consider what happens “after” countably infinite time and will not rely on “limit states” for each cell on a tape. This paper contends only that a certain, specific Turing machine would be able to generate and write all the real numbers in [0, 1] within countably infinite computation steps, using a constant, finite number of countably infinite tapes.
4.4. Experimental Validation
The author has implemented a detailed simulation of a Turing machine for which pseudocode is given in Appendix A, in a computer program showing that with only a constant set of 24 states, a constant set of 227 state transition rules, and a constant set of twelve tapes, the Turing machine could iteratively generate all the paths in the infinity tree to each level of the tree. The simulation uses the symbol ‘*’ at the starting position on each tape. (Including headings, the state transition table has 41 rows and 229 columns of information. Including the state transition table and the Visual Basic code for this computer program as additional Appendices would more than double the length of this paper).
Admittedly, it is counterintuitive to find that a finite-state Turing machine can write a countable infinity of countably infinite decimal expressions to a single countably infinite tape, and also write copies of all these expressions to a second countably infinite tape, using only countably infinite discrete time steps and state transitions. Such is the power of combining countably infinite space with countably infinite time for a Turing machine.
5. Cantor’s Continuum Hypothesis
Cantor advanced the Continuum Hypothesis in 1878, which states that “there is no set whose cardinality is strictly between that of the integers and the real numbers.” [8] Establishing the truth or falsity of the hypothesis was the first of Hilbert’s 23 problems. [9] Cantor was unable to prove or disprove the hypothesis during his lifetime, and it has remained unproven until now. In 1940, Gödel showed that the hypothesis is consistent with the axioms of set theory, including the Axiom of Choice. [10] In 1963, Cohen showed that the hypothesis “cannot be derived from the other axioms of set theory, including the Axiom of Choice”. [11]
By showing in Section 4 above that the cardinality of the real numbers is the same as that of the natural numbers, this paper has also shown that there is no set with cardinality between that of the natural numbers and that of the real numbers. Hence Cantor’s Continuum Hypothesis is shown to be true, if one considers the possible computations of a Turing machine within countably infinite space and time, in a non-Cantorian theory of infinity.
6. Cantor’s Theorem
Cantor’s Theorem provides a proof that the power set of the natural numbers ℕ has cardinality greater than that of the natural numbers. In this paper’s non-Cantorian infinity theory, it follows that the power set of the natural numbers P(ℕ) is countably infinite, which contradicts the claim of Cantor’s Theorem for the natural numbers.
This paper considers zero to be a natural number, as noted in Section 2, although later in this section, we will see that it doesn’t matter whether zero is considered to be a natural number or not, for this paper’s conclusion about Cantor’s Theorem.
To represent sets of natural numbers which may include zero, we can map any subset S of the natural numbers ℕ = 0, 1, 2, 3, … to a real number 0.b1b2b3… where bi = 1 if i − 1 is in S and bi = 0 if i − 1 is not in S. That is, the first digit indicates whether 0 is a member of the subset or not, the second digit indicates whether 1 is a member or not, the third digit indicates if 2 is a member or not, etc. For example, the subset {0, 3, 5} would be represented by 0.100101 followed by infinite 0’s. Any set is considered a subset of itself, and ℕ would be represented by 0.111111…
By definition, the empty set is also an element of a power set. In this paper’s mapping, the empty set will be mapped to the infinite decimal 0.000… A non-empty subset of the natural numbers will not map to the infinite decimal 0.000….
This mapping gives us a way to represent the power set of natural numbers P(ℕ) by a subset of the real numbers in [0, 1). If the set of all real numbers in [0, 1) is countably infinite, as shown in Section 4 of this paper, then P(ℕ) would also be countably infinite.
However, this would contradict Cantor’s Theorem that the power set of the natural numbers ℕ has cardinality greater than that of the natural numbers. To address this contradiction, we need to discuss how Cantor’s Theorem is proved.
A standard proof of Cantor’s Theorem goes as follows:3
“Suppose that ℕ is equinumerous with its power set P(ℕ). Let us see a sample of what P(ℕ) looks like:
P(ℕ) = {Ø, {1, 2}, {1, 2, 3}, {4}, {1, 5}, {3, 4, 6}, {2, 4, 6, …}, …}.
P(ℕ) contains infinite subsets of ℕ, e.g. the set of all positive even numbers {2, 4, 6, …} = {2k: k in ℕ}, along with the empty set Ø.
Now that we have an idea of what the elements of P(ℕ) are, let us attempt to pair off each element of ℕ with each element of P(ℕ) to show that these infinite sets are equinumerous. In other words, we will attempt to pair off each element of ℕ with an element from the infinite set P(ℕ), so that no element from either infinite set remains unpaired. Such an attempt to pair elements would look like this:
1 ↔ {4, 5}
2 ↔ {1, 2, 3}
3 ↔ {4, 5, 6}
4 ↔ {1, 3, 5}
. . .
. . .
. . .
Given such a pairing, some natural numbers are paired with subsets that contain the very same number. For instance, in our example the number 2 is paired with the subset {1, 2, 3}, which contains 2 as a member. Let us call such numbers selfish. Other natural numbers are paired with subsets that do not contain them. For instance, in our example the number 1 is paired with the subset {4, 5}, which does not contain the number 1. Call these numbers non-selfish. Likewise, 3 and 4 are non-selfish.
Using this idea, let us build a special set of natural numbers. This set will provide the contradiction we seek. Let B be the set of all non-selfish natural numbers. By definition, the power set P(ℕ) contains all sets of natural numbers, and so it contains this set B as an element. If the mapping is bijective, B must be paired off with some natural number, say b. However, this causes a problem. If b is in B, then b is selfish because it is in the corresponding set, which contradicts the definition of B. If b is not in B, then it is non-selfish and it should instead be a member of B. Therefore, no such element b which maps to B can exist.
Since there is no natural number which can be paired with B, we have contradicted our original supposition, that there is a bijection between ℕ and P(ℕ).
Note that the set B may be empty. This would mean that every natural number x maps to a subset of natural numbers that contains x. Then, every number maps to a nonempty set and no number maps to the empty set. But the empty set is a member of P(ℕ), so the mapping still does not cover P(ℕ).
Through this proof by contradiction, we have proven that the cardinality of ℕ and P(ℕ) cannot be equal. We also know that the cardinality of P(ℕ) cannot be less than the cardinality of ℕ because P(ℕ) contains all singletons, by definition, and these singletons form a “copy” of ℕ inside of P(ℕ). Therefore, only one possibility remains, and that is that the cardinality of P(ℕ) is strictly greater than the cardinality of ℕ, proving Cantor’s theorem.”
The lines that I have underscored in the preceding quotation would not apply with the mapping that I’ve defined above, and the proof by contradiction would fail: The empty set Ø would map to the infinite decimal 0.000… Each subset S of the natural numbers ℕ = 0, 1, 2, 3, … would map to a real number 0.b1b2b3… where bi = 1 if i − 1 is in S and bi = 0 if i − 1 is not in S.
So, if the set of all real numbers in [0, 1) is countably infinite, then P(ℕ) would also be countably infinite. And Section 4 above argues that the set of all real numbers in [0, 1] is countably infinite, by considering the computations of a Turing machine to generate these numbers in countably infinite space and time. Thus, Cantor’s Theorem is contradicted within the non-Cantorian infinity theory presented in this paper: One can argue reasonably that ℕ is equinumerous with its power set P(ℕ), if the real numbers in [0, 1] are countably infinite.
“Hilbert’s Hotel” shows a 1-1 correspondence between the natural numbers 0, 1, 2, 3, … and 1, 2, 3, 4, …4 So, the argument presented in this paper also shows that the set 1, 2, 3, 4, … is equinumerous with its power set. Hence, it doesn’t matter whether 0 is included as a natural number, in considering Cantor’s Theorem.
Cantor’s Theorem is also contradicted by considering the possible computations of a Turing machine to generate the set of infinite paths in the infinity tree within countably infinite space and time: Recall that at each level of the infinity tree, the machine writes all the paths from the root of the tree to that level, to a tape. This is a finite list of finite length expressions. The number of expressions increases by 10 for each level. The length of each expression increases by 1 for each level. For level n of the tree, the machine writes 10n expressions, each of length n to the tape. The tree has a countably infinite number of levels. If the machine were to traverse א0 levels, it would write 10א0 expressions each of length א0 onto a tape with א0 squares. In effect, given countably infinite time, the machine would map the 10א0 expressions intoא 0.
It may seem impossible or paradoxical that a tape with א0 squares can hold 10א0 expressions, with each expression of length א0, yet that is precisely what would be accomplished in countably infinite time by the Turing machine. The Turing machine never runs out of space on a countably infinite tape, and infinite time never stops.
And it is well known that countable infinities can contain multiple countable infinities within them: For example, the countable infinity of natural numbers contains the countable infinities of even numbers, odd numbers, and prime numbers, and also countable infinities of randomly chosen natural numbers.
7. Cantor’s Arguments for Uncountability of Real Numbers
7.1. Cantor’s First Uncountability Argument
Before using diagonalization, Cantor [12] gave a different uncountability argument for the real numbers. He wrote:
“Suppose we have an infinite sequence of real numbers, ω1, ω2, …, ωv, … where the sequence is given according to any law and where the numbers are distinct from each other. Then in any given interval (α … β) a number η (and consequently infinitely many such numbers) can be determined such that it does not occur in the series; this shall now be proved. …”
This uncountability argument does not apply to the countably infinite sequence of real numbers in the interval [0, 1] that would be generated in a countably infinite sequence of steps by a Turing machine (and all of them written to a countably infinite tape) using the method discussed in this paper, because this paper’s approach agrees that there are no first and second numbers in the open interval (0, 1), and that for any pair of numbers α < β in the interval, there are infinitely many numbers between them. This can also be seen by considering the infinity tree for the interval [0, 1).
Yet for the infinity theory proposed by this paper, it doesn’t matter that there are no first and second numbers in the open interval (0, 1), nor in any open interval (α, β) within [0, 1). In countably infinite time, the Turing machine would write to a countably infinite tape all the decimal expressions in the interval [0, 1), plus the number 1. The set of starting points for all these numbers would always be a subset of the countably infinite spaces on the Turing machine tape. So, the set containing the starting points of all these numbers would be countably infinite. Therefore, the set of real numbers in [0, 1] is countably infinite, in the infinity theory advocated by this paper.
7.2. Cantor’s Diagonalization Argument
To begin, I do not claim to find an error in Cantor’s diagonalization argument. However, some discussion needs to be given in this paper.
Cantor’s diagonalization argument [2] considered infinite strings of two mutually exclusive characters, m and w. Essentially, he considered infinite binary strings: we could use m = 0 and w = 1. For any infinite sequence of such infinite strings, he defined a diagonal infinite string that differed on every diagonal element, by changing m to w and w to m, i.e., flipping the binary element. He then argued that the diagonal infinite string could not exist anywhere in the countably infinite sequence of infinite binary strings. He did not require or specify any particular order for the list of infinite binary strings.
However, if we consider a binary infinity tree, with only two branches, labeled 0 and 1 from each node, then the 2n paths from the root node to each level n >= 1 below the root node correspond to all the finite binary sequences of length n. A new number specified by flipping the first n characters of the first n rows in a list of binary sequences would always exist somewhere in a list that included all 2n initial sequences of the two characters 0 and 1. The new sequence would always exist in the binary infinity tree, and it would always exist somewhere on a countably infinite Turing machine tape, in the expressions written by a Turing machine running for infinite time, simulating a breadth-first navigation of the binary infinity tree. If the Turing machine writes “0.” at the start of each binary sequence that it writes to its tape, then if it runs for countably infinite time steps, simulating breadth-first descent through all the countably infinite levels of the binary infinity tree, it will never write more than a countably infinite number of “.” characters on its tape. So, the Turing machine’s execution would demonstrate that the set of all infinite binary sequences is a countably infinite set, contradicting Cantor’s diagonalization argument.
Similarly, the definition and design of the decimal infinity tree are such that it cannot be diagonalized: For any number p that Cantor specifies in diagonalizing a hypothetical countably infinite list of decimal numbers, p also specifies a path that exists in the decimal infinity tree. And each number in Cantor’s hypothetical countably infinite list of decimal numbers also specifies a path that exists in the decimal infinity tree.
So, if a Turing machine could run for countably infinite time, then it could simulate a breadth-first descent through the countably infinite levels of the decimal infinity tree and write a list of decimal expressions corresponding to all the infinite paths descending from the root node of the infinity tree. This would correspond to all the decimal numbers in the interval [0, 1], if the Turing machine always writes “1” after it writes the decimal expressions for each level of the infinity tree. The set of starting points for these decimal expressions would be countably infinite, since they are all written on a single countably infinite tape. Hence if a Turing machine could run for countably infinite time, then it would demonstrate that the number of decimal expressions in [0, 1] is א0, countably infinite.
However, since I do not claim to find an error in Cantor’s diagonalization argument yet reach a different conclusion by considering a Turing machine argument, we appear to have a paradox. This is further discussed in Section 9 below.
8. Computability of Real Numbers
This paper has focused on countability of the real numbers, yet it is appropriate to also discuss computability. A real number r is said to be computable if there is a Turing machine which, given n on its initial tape, prints the decimal expression of r to the nth digit on an output tape.5 That is, r is computable if it can be written to a tape to any desired finite degree of precision, by a finite-state Turing machine performing a finite number of computation steps.
There is a countable infinity of different Turing machines, so if we consider Turing machines which each only print out the decimal expression of a different real number r, then the set of real numbers that are computable is countably infinite. If the set of real numbers in the interval [0, 1) were uncountably infinite, then there would be uncountably many real numbers which are not individually computable by different Turing machines.
Yet the entire infinity tree is computable by a single Turing machine, with a constant finite set of states, a constant finite set of state transition rules, and a constant set of twelve countably infinite tapes, as discussed in Section 4 of this paper. All the numerical expressions to any finite level of the tree can be computed by the Turing machine and written on an output tape with a total number of symbols that is finite. The number of output symbols and computation steps required goes up by a factor of 10 for each level, yet these numbers are always finite at each level.
Since the infinity tree contains all the real numbers in [0, 1), each real number in [0, 1) can effectively be computed by a Turing machine which computes the entire infinity tree. Since the Turing machine always writes 1 after computing expressions at each level of the tree, it effectively computes all the real numbers in [0, 1].
When the infinity tree is computed in this manner, two reals are distinguished from each other even when they are arbitrarily close together, i.e. even when they differ by a branch at any finite depth in the infinity tree.
9. Accepting Paradoxes
In writing this paper, my strong preference has been to leave open the possibility that the proposed non-Cantorian theory of infinity and Cantor’s theory of infinity may be equally valid alternative theories.
An analogy is the acceptance and co-existence of alternative Euclidean and non-Euclidean theories of geometry, as another situation which also involves reasoning about infinity: In Euclidean geometries, parallel lines remain the same distance from each other when extended to infinity. In non-Euclidean geometries parallel lines can curve away or curve toward each other, when extended indefinitely. Yet these different geometries do not have anything specific to do with the countability or uncountability of real numbers.
There is a similar conflict between this paper’s proposed non-Cantorian theory of infinity and Cantor’s theory of infinity: Cantor claims to prove the proposition P that the real numbers in [0, 1] are uncountably infinite. I claim to prove the proposition ¬P, that they are countably infinite.
However, I do not claim there is an error in Cantor’s diagonalization argument. Yet I also claim that my argument based on a Turing machine computing paths in the infinity tree is correct. And my approach is consistent with Cantor’s first uncountability argument.
So, in this paper, I simply accept this situation as a paradox, resulting from different choices about how to represent and count the continuum of real numbers.
This paper also identifies and accepts another paradox, in claiming that a Turing machine tape with א0 squares can hold 10א0 decimal expressions, with each expression of length א0 symbols. There is no finite point in time where this paradox happens: At each finite step in the machine’s operation, it always has countably infinite empty space on the Turing machine’s output tape to write more expressions. This result is achieved if the machine performs countably infinite processing steps, i.e., if it runs for countably infinite time. And it is well known that countable infinities can contain multiple countable infinities within them: For example, the countable infinity of natural numbers contains the countable infinities of even numbers, odd numbers, and prime numbers, and also countable infinities of randomly chosen natural numbers. So, this paradox is not an impossibility, and not a self-contradiction.
This paper also has the hypothetical premise that a Turing machine can run for countably infinite time steps, a topic that has been previously studied by other researchers, as noted in Section 4.3.
10. Other Related Work
It does not appear that there has been any previously published work presenting the approach of this paper.
There has been a long history of attempts by others to refute Cantor’s arguments. Hodges [13] gave an analysis of errors in counter arguments to Cantor that were contained in papers he received either as a referee or as editor of the Journal of Symbolic Logic. It does not appear that Hodges’ paper covers the arguments presented here: His paper does not include any references to Turing, nor to Turing machines. Hodges’ paper includes only one use of the word “tree” which is metaphorical, not mathematical.
And again, to be clear, this paper does not claim there is an error in Cantor’s diagonalization argument that [0, 1] is uncountably infinite. Rather, this paper considers the situation as a paradox, resulting from different choices about how to represent and count the continuum of real numbers.
11. Conclusions
Considering the infinity tree [1], this paper has shown that all the real numbers in the continuum [0, 1] can be computed by a Turing machine and written to a countably infinite tape in a countably infinite number of state transitions. A computer program has been written which simulates the operation of such a Turing machine. Hence it is argued that the real numbers in the interval [0, 1] are countably infinite in a non-Cantorian theory of infinity based on a Turing machine with a constant finite set of states, a constant finite set of state transition rules, and a constant set of twelve countably infinite tapes, using countably infinite space and time to compute and write the decimal expressions of the real numbers in [0, 1].
In this theory, Cantor’s Continuum Hypothesis is true, since there is no set with cardinality between that of the integers and the real numbers. And in this non-Cantorian infinity theory, it follows that the power set of the natural numbers P(ℕ) is countably infinite, which contradicts the claim of Cantor’s Theorem for the natural numbers. In this theory, all the real numbers in [0, 1] are effectively computable by a Turing machine which computes the entire infinity tree.
However, this paper does not claim there is an error in Cantor’s arguments that [0, 1] is uncountably infinite. Rather, this paper considers the situation as a paradox, resulting from different choices about how to represent and count the continuum of real numbers.
Acknowledgements
The writing of this paper has benefitted from correspondences with two anonymous mathematicians, who both gave criticisms and disagreed with the conclusions of this paper. I believe their criticisms have been addressed throughout this paper, although they continue to disagree.
The publication of [1] led to a brief correspondence with a philosopher who has written a separate unpublished paper [14] that describes an algorithm for iterative generation “in א steps” of a list of all real numbers in [0, 1), but does not discuss Turing machines per se, and does not discuss Cantor’s Continuum Hypothesis or Cantor’s Theorem.
Appendix A. Pseudocode for a Turing Machine
The following is pseudocode for a Turing machine which this paper argues would generate the real numbers in [0,1] in countably infinite time and space.
create initial state
define tapes
'each tape has a countable infinity of cells
input level tape
output level tape
branch0tape, branch1tape, branch2tape, branch3tape,
branch4tape, branch5tape, branch6tape, branch7tape,
branch8tape, branch9tape
create / postulate initial starting state of tapes:
initially, all tapes have only blank spaces on every cell
position tape heads to start of all tapes
write 0.0, 0.1, 0.2, …, 0.9, 1 to the input level tape
‘i.e., 11 finite expressions, each followed by a blank space on the tape.
‘Commas and the ellipsis “...” would not be written to the tape.
‘A cell on the tape would only have a digit, the decimal point, or a blank
‘written to it.
position input level tape head to start of tape
loop
'an infinite loop to create expressions for paths from root to each level of infinity tree
for each expression on input level tape
‘at each finite step there are a finite number of finite expressions,
‘separated by spaces
if the first character of the expression is not "1" then
copy the expression to each branch tape
add 0 to end of expression on branch0tape
add 1 to end of expression on branch1tape
add 2 to end of expression on branch2tape
add 3 to end of expression on branch3tape
add 4 to end of expression on branch4tape
add 5 to end of expression on branch5tape
add 6 to end of expression on branch6tape
add 7 to end of expression on branch7tape
add 8 to end of expression on branch8tape
add 9 to end of expression on branch9tape
position branch tape heads to start of branch tapes
append copy of branch0tape expression to output tape
append " " (empty space) to output tape
append copy of branch1tape expression to output tape
append " " (empty space) to output tape
append copy of branch2tape expression to output tape
append " " (empty space) to output tape
append copy of branch3tape expression to output tape
append " " (empty space) to output tape
append copy of branch4tape expression to output tape
append " " (empty space) to output tape
append copy of branch5tape expression to output tape
append " " (empty space) to output tape
append copy of branch6tape expression to output tape
append " " (empty space) to output tape
append copy of branch7tape expression to output tape
append " " (empty space) to output tape
append copy of branch8tape expression to output tape
append " " (empty space) to output tape
append copy of branch9tape expression to output tape
append " " (empty space) to output tape
else 'expression is "1" on input level tape
append "1" to output level tape 'signifying end of new expressions
end if
end for
position input level tape head to start of input level tape
position output level tape head to start of output level tape
for each expression on output level tape ‘a finite number of finite expressions
copy expression to input level tape
end for
'at this point, both tapes have the same content
position input level tape head to start of input level tape
position output level tape head to start of output level tape
end loop 'infinite loop creating expressions for paths from the root
‘to each level of the infinity tree
NOTES
1Per Wikipedia: “In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0.” [Enderton, Herbert B. (1977) Elements of Set Theory, Academic Press, p. 66].
2The symbol ‘*’ at the starting position of each tape is not shown in the Appendix A pseudocode.
3This proof of Cantor’s Theorem is quoted from https://en.wikipedia.org/wiki/Cantor%27s_theorem, which says that “Cantor gave essentially this proof in a paper published in 1891 ‘Uber eine elementare Frage der Mannigfaltigkeitslehre’ … Ernst Zermelo has a theorem (which he calls ‘Cantor’s Theorem’) that is identical to the form above in the paper that became the foundation of modern set theory (‘Untersuchungen über die Grundlagen der Mengenlehre I’), published in 1908.”
4I thank an anonymous mathematician for noting this point about Hilbert’s Hotel.
5See Minsky (5), p. 159, and https://en.wikipedia.org/wiki/Computable_number.