The binary tree representation of the reals

Consider a binary tree that begins with 1 and 0 on the top horizontal line, whereby at every fork, the left node takes a 1 and the right node takes a 0.

Let us vertically list every stage with consecutive n's, in the usual order, so that for every n, we have 2ⁿ 0's and 1's on the nth horizontal.

At lim n -->inf. (that is at cardN or aleph_null, or being finicky, at ordN), we have the set of all real binary extensions, which, of course, is bijective to the set of all reals.

Thus at ordN, which we'll call the last step, there are two connected "actual infinities" on display: cardN for the vertical, and cardP(N), or 2^cardN, for the "bottom" horizontal [1]. So the ordNth horizontal contains 2^cardN 0's and 1's.

We see that there is a path from horizontal line 1 to the ordNth line that expresses any real binary extension, including those that are not finitely expressible (non-computables).

Now we can get a good intuition that, assuming the existence of the bottom line, the reals are well ordered. That is, for any finite path (or proto-real), that path is a member of a finite set where each element may be ordered as x < y or y < x, systematically until the entire finite set has been ordered. We may then apply mathematical induction to show that such ordering holds for any set with n-bit paths, where each such set holds 2ⁿ paths.

To wit, the induction basis:

Given a binary tree with path-length 2 bits, we have that:

Any path is a member of a set of 2² members, which implies that, given a binary tree of 3 bits, any path is a member of a set of 2³ members. This holds by inspection and by the structure of our binary tree.

Induction step:

Given a binary tree of path length n bits, any path is a member of a set with 2ⁿ members, which implies the same for n+1.

At this point, we remark that ordinary induction proves that if f(n) holds for f(n+1), then we know that our claim holds for any arbitrary finite n. Some see ordinary induction as implying "potential infinity," which simply means an unbounded finite recursion. Now if one follows a Cantorian line and argues that some successor operation on the positive integers holds for any natural number, then there is a set N -- of "actual infinite" size (cardN) -- that contains "all" these whole numbers. In that case, N -- or really, ordN -- exists by transfinite induction.

So it is clear of course that N is well-ordered. So R's well-ordering is strongly suggested by transfinite induction that accompanies in this case the ordinary induction for recursive sets 2ⁿ. That is, if R exists, then transfinite induction points from 2ⁿ n-bit paths to 2^cardN cardN-bit paths. (R's well-ordering can be proved definitively by other means.)

An objection might be that we cannot, at the ordNth step come up with an algorithm to do the ordering of the 2^cardN paths, though we can do so for any finite ordinal n. Yet note that the cardN-stage binary tree is a self-similar fractal. So if every finite path (1's to the left, 0's to the right) can be easily well-ordered, one would expect that the same, in principle, holds for the infinite fractal.

Appeal to the fractal nature of the binary tree might not persuade some, who would argue that simply because every finite set of 2ⁿ has a least element, it doesn't necessarily follow that the 2^cardNth set has a least element. But if we say that the sorting and ordering algorithm holds at every stage, then shouldn't it be allowed at the ordNth stage?

The fact that a constructive proof may not exist for the case of ordN --> ord2^cardN is, however, a problem for transfinite quantities in general. Something that seems to follow from a "Platonic" logic is drawn up short by the crowd from Missouri (the intuitionists, among others).

So in order to confirm that all the reals are represented and that a specific order is implied, we can cite transfinite induction to assert the well-ordering of the set of all paths. Of course, some may object to our "abuse" of transfinite induction.

The binary tree also says something about Cantor's continuum problem of whether there exists a cardX such that cardN < cardX < cardP(N) = 2^cardN = cardR. Note that we have the binary tree fractal -- or algorithm -- such that N --> R. So plainly any base number system can be used; i.e. a k-nary fractal where k is any positive integer will for any stage n, yield a set of kⁿ paths. So that k^cardN must equal 2^cardN.

So the cardinality of the reals can be "approached" (as n goes to infinity) by any kⁿ. This tends to suggest that functions that climb faster than such exponentials will not approach cardX. In fact, it's hard to think of a function other than kⁿ approaching the cardinal number of the paths of all the reals.

Because of its fractal nature, if we arbitrarily select any finite node on our k-nary tree and work downward, we get the entire k-nary tree, so that one gets nowhere with (lim n --> inf.) Kⁿ - j, as j vanishes in the limit. So we can't get a lower cardinality that way. If we try K^x such that x is not an integer, we won't successfully represent some fraction of paths.

That is, we get the impression that any such set X can't be approached "from below," which helps reinforce our acceptance of the combined result of Goedel and Cohen that the continuum hypothesis is independent of the axioms of standard set theories.

---

1. Sidelight: note that lim n--> inf. n/2ⁿ = 0, in accord with cardN/cardP(N) = 0.

A note on the continuum hypothesis

We can get a feel for why Cantor's continuum hypothesis is independent of standard set theory, both in the case of ZFC axioms and NBG axioms, by beginning with the fact that Cantor's theory, as modified by ZFC and NBG and other systems, implies the existence of non-specifiable numbers.

Cantor's diagonal proof requires that a real be definable as a denumerable infinite decimal (or n-nary) extension. From this he showed that listing the reals in some consecutive order yields a number that cannot be on that list. Hence, the reals must be non-denumerable, which he saw as a "larger" actual infinity than the actual infinity of the naturals. So a cardinal number is defined by equipollence with some representative set, such as N. CardN is not equipollent to CardR, or in Cantorian notation Aleph_null is equivalent to CardN.

So, for Cantor, the cardinal numbers should represent a discrete set of "infinite integers." He was unable to prove however that CardR = Aleph_1, the second infinite "integer" or cardinal number.

The general continuum hypothesis (GCH) is that only cardinals equipollent to power sets exist after Aleph_null, or cardN. For example, the reals are bijective with the power set of N, which reflects another proof that R is of a higher actual infinity than N. (Any proof or disproof of GCH would follow almost immediately from a proof or disproof of HC, in which R represents the real number line continuum [1a].)

Now consider that the Church-Turing thesis (which is a fundamental intuition or axiom) posits that any computation that can be done (whatever its practicality) may be put in Turing machine form. This certainly makes sense when one considers that we would expect that every mechanical, mindless computation can be encoded as a Boolean logic circuit. And any non-logical circuit would not reliably output a computation that could be used with other computations in coming up with another logical circuit that solves a problem.

So one can say that every Boolean logic circuit, can, following a similar procedure for a Turing machine, have every gate given a unique integer number. We then encode these numbers, perhaps in a Goedelian fashion. So then, every Boolean logic circuit is assigned a unique positive integer (it is irrelevant whether more than 1 circuit yields the same output). For both Turing machines and Boolean circuits, the initial conditions, including input code, are included in the encodement by what may be called a Description Number.

In that case, every computable number is associated with one or more unique integers. We shall call this the set of computables, or K. K is infinite, because, among other things there is some description number k that encodes an algorithm for yielding any integer. So K is an infinite subset of N, meaning that cardK = cardN.

We shall call K's complement W, the set of noncomputables. No w e W can be specified or identified, though the Axiom of Choice can be used to manipulate W in standard set-theoretic ways. And of course K U W = R. (So most of the reals have only a ghostly reality.)

Well, any subset of K is either bijective with N or with n e N. A mixed set, such as K' U Y' -- in which K' and Y' are subsets of K and Y -- is either bijective with N, bijective with R or is equipollent to card(K' U Y') but not to K or R. But how can we determine Y'? Well, at least we know that Y' is bijective with Y/K or K/Y. The latter case is possible but not germane to the argument, which is that the mixed case is equivalent to the case Y being composed of all non-computables.

So to the point: If cardN < cardY < cardR, we must find a subset X of Y that is neither bijective with K nor R. Likewise, to show that no subset of Y is bijective with K, we must exclude all subsets of Y such that one has cardY.

But of course a set is defined by its elements. What to do when each element is individually undefined? We know w e W can express some magnitude on the real line, conventionally between 0 and 1; the trouble is, in principle, no one can hone in on that real point. [1]

From this we can see intuitively that the probability of proving or disproving GCH is virtually nil. So we can see the enormous plausibility of the combined results of Kurt Goedel and Paul Cohen that GCH is independent of the axioms of modern set theory -- without actually examining their rigorous proofs.

Interestingly, the WOT version of AC requires that anything properly defined as a set can be well-ordered, as in a nested sequence of least elements descending to a secure bottom (of the well). So the reals are well-ordered, even though we know of no algorithm to yield an element by element well-ordering. So all the k's are in the well-ordering of R. Because R is bijective with the power set of N, proving GCH requires proving that Y is never bijective with any element of p e P(N). Note that if we exclude all members p that are bijective with either N or P(N), we would still be unsure that the result is the null set without the independence proofs of Goedel and Cohen.

---

1a. The continuum is an ancient concept and so is often taken to mean the mapping of all the positive integers onto a finite line segment. That is, the continuum is often identified with N mapped onto a finite magnitude, rather than the set R being so mapped. So then, the set of reals may be said to be the power of the continuum, or R is bijective with P(N).

1. See Kurt Goedel, 'What is Cantor's continuum problem?' in Philosophy of Mathematics, selected readings, 2d ed., Paul Benacerraf and Hilary Putnma, eds. (Cambridge 1984). In particular, see Page 278.