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.