Where are the non-computablesin the binary tree picture of the reals?

 

---

NOTE. Occasionally, over the years, I have published discussions of the binary tree picture of the reals. This post continues in that vein.

---

We accept the idea that the set of decimal extensions is bijective with the reals. For convenience, we convert to the base-2 number system, such that the reals are comprhended by the set of binary extensions.

To help us in our intuition, we employ a binary tree with a denumerable infinity of stages/levels. That is, at each level is a set of 2ⁿ nodes, or branching points. At level 1, there are 2 nodes...at level 10, 1024 nodes... Every left branch is designated 1 and every right branch 0.

Example: At level 3, we have,

  
  L R L R L R L R
  
  which is equivalent to
  
  1 0 1 0 1 0 1 0
  
  

The complete set of stages corresponds to the set of natural numbers N. The number of nodes in the "final" stage is taken to be 2^ℵ_o.

Hence, we see that every path is well-ordered. (But AC is needed to tell us those distinct paths reach the "bottom" stage.) Now we know from the Goedel and Turing theorems that the cardinality of the computables is ℵ_o, which is that of N.

It is also evident that every rational is represented as a finite digit string that recurs infinitely often. That is a set of all 0's means 0; a set of all 1's means 1; a finite string of 0's and 1's that is either followed by all 0's or that recurs infinitely often means some rational.

In addition, we have the set of computable irrationals. This means there exists at least one procedure that converts a numerical input into some 1's and-or 0's without ever doing so periodically and that this procedure is infinitely (or indefinitely) recursive, as in f(x) = x_next.

Now each path, up to any finite level, we must construe as a proto-number. All one can prove about any such path one follows is that if we know the algorithm, we can say whether the number is rational or irrational. And, if one does not know the algorithm, all one can say is that -- thus far -- the number is computable, as it can be defined stage by stage. In fact, at any finite level, the path has thus far been computed. So there is really no way to discern a noncomputable from the ordinary perspective.

But if we accept that the power set of N exists, in that case it must be that the "bottom line" point set of 2^ℵ_o "originates" the non-computables.

That could only mean, I suggest, that there must be many digit strings (from the "top" or "our" perspective) followed by an infinity of 0's that are then followed by a "finite" (from "bottom" perspective) string of 0's and 1's.

Such numbers are said to be undefined because their paths vanish as they climb skyward. Their paths all converge to the number 2. But they have vanished "before" coming into our finite range.

I concede such talk is inexact. Our language is unsuited for such conceptualization. Yet, I suggest, that intuitively we can discern that the "bottom up" paths must contain the non-computables, but that we cannot, from "top down" obtain them.

This picture does not suggest much beyond what is already known: that the continuum hypothesis is independent of the axioms of standard set theory.

A way to think about that is to note that the set of the computables K and its complement K^c comprise the reals. And R\K is equinumerous to R.

But we must use AC to "pick out" an arbitrary x ∈ K^c because there is no method in our posession for specifying any x. That is, if we define K^c by its elements, we say K^c is defined such that x is not definable. This is almost an abuse of the usual set notation {x|x ... }, which means that "any element x is defined..." So for K^c we have {x|x is undefinable}. That expression, to me, makes clear why CH is such an elusive beast.