An algorithm to imply the set of reals

I have reconsidered my initial idea that the algorithm I give proves non-denumerability of the reals, an idea which I based on the fact that there is no n for which a cellular diagonal exists that intercepts every row of cells. However, despite intuition, it does not immediately follow that no such diagonal exists for the infinite set.

---

An algorithm to imply the set of reals

We present an algorithm for "constructing" the entire set of reals and find that our intuition suggests that no diagonal can exist, which accords with Cantor's proof.

Cantor's diagonalization proof says that if it were possible that all reals were listed, then one could create an anti-diagonal number from the diagonal that intersects all the listed numbers. Hence, no such diagonal exists and the set of reals is not 1-to-1 with the set of naturals.

However, we are assuming that there is a set N containing all naturals. We are also assuming that because a finite n x n square always has a (non-Pythagorean diagonal of n cells) that intersects every row, then the same holds for the tiled quarter-plane.

However, the infinity axiom says that N exists, in which case we may say that the set of X axis integers is 1-to-1 with the set of Y axis integers, and further that the cellular diagonal with a cell vertex at (0,0) has cardN and intersects every horizontal string of cells bounded by y and y+1. In that case, we may use Cantor's argument to say that the reals can't be mapped 1-to-1 onto this tiling.

Interestingly, our algorithm for constructing all the reals intuitively says that such a set has no diagonal. But, that intuition is simply an intuition until we apply Cantor's proof and the infinity axiom.

We write an algorithm for determining the set of reals, thus:

We have the set of 1x1 square cells in a quadrant of the Cartesian grid. Each square is eligible to contain a digit. We consider only the horizontal strings of cells.

Suppose we use a base 2 system. We begin at step 0 using 2 consecutive spaces and obtaining 4 possible combinations, to wit: 00, 11, 10, 01. For step 1 (3 spaces), the number of combinations is 2*4 and for step n the number of combinations is 2ⁿ⁺².

At lim_n->inf. 2ⁿ⁺², we have established all base 2 infinite digit strings, expressing the entire set of reals greater than an arbitrary j e Z and less than or equal to j+1.

Remark: Our algorithm does not compute reals sequentially. It only computes 'pre-reals,' since a real is defined here as an infinite digit string. No element "materializes" prior to the entire set's establishment at (denumerable) infinity.

The algorithm above requires that for any step n, the set of digit strings is a rectangle n2ⁿ⁺².

But lim_n->inf. n/2ⁿ = 0, meaning the rectangle elongates and narrows toward a limiting form of a half-line.

For an integer diagonal to include an element of all horizontal digit strings, we must have a square of n columns and n rows. But such a square of the reals is never attainable. It would then seem safe to say that the set of reals, expressed as infinite digit strings, has no diagonal, which is equivalent to saying the set of reals is non-denumerable.

However, our intuition that the set of reals so constructed should have no diagonal is provable by agreement to the infinity axiom, which permits the cardN diagonal, and by Cantor's anti-diagonal result.

It also follows that no exponentially defined set of tiles n x kⁿ has a cellular diagonal at the tiling algorithm's infinite limit.

On the other hand, a tiling defined by n^k can be said to have k cellular diagonals, such that collectively the k diagonals intersect every horizontal cellular string. It then can be shown that such a tiling is one-to-one with N.

Interestingly, the power set of any n e N has card2ⁿ, which corresponds to step n of our algorithm, in which we have a set of 2ⁿ⁺² pre-reals.

Additional remark:

Lemma: Any set with lim_n->inf kⁿ elements has the cardinality of the reals, with k =/= 0, -1, 1 and k e Z.

Proof:

The set of reals is 1-to-1 with a set that has lim_n->inf 2ⁿ elements. Hence the cardinality of each set is identical. Similarly, the algorithm above can be rewritten as ckⁿ, with c a nonzero integer constant, meaning that all real digit strings are established at lim_n->inf ckⁿ.

Theorem: Some non-enumerable reals can be approximated with explicit rationals to any degree of accuracy in a finite number of steps.

Proof:

Construct n Turing machines consecutively, truncating the initial integer, and compute each one's output as a digit string n digits long. Use some formula to change each diagonal digit.

The infinite diagonal cannot be encoded as a Turing machine number, so it is not enumerable. Yet a computer can compute its approximation as a rational up to n. (The accuracy of this approximation is the same as the accuracy obtainable, in principle, for an enumerable irrational.)

Comment: The denumerable set of computables implies an extension of the concept of denumerability.

Justification:

We give these instructions for diagonalizing Turing computables:

Up to and including the nth diagonal space, follow this rule: if a digit is not 0, replace it with 0; if 0, replace it with 1. After the nth diagonal space, follow this rule: if a digit is not 2, replace it with 2; if it is 2, replace it with 3.

None of these diagonals is enumerable with respect to the Turing numbers. Yet we have a countably infinite set of diagonals. Hence, non-denumerability implies the existence of two denumerable sets of reals which are not denumerable with respect to each other.

If we diagonalize the diagonals, it is not apparent to me that this real is not a member of the computables.

Definition of choice sequence:

If f(n) gives a_n of cauchy sequence {a_n}, then {a_n} is a choice sequence if f(n) --> a_on+1 or a_1n+1 or . . . or a_mn+1.

Note i.Since a choice sequence is cauchy |a_m - a_n| <= 1/k for all m and n after some n_o. However, the rule for determining step n+1 means that more than one choice sequence is possible for every n after some n_o. That is, a choice sequence's limiting value must fall within an upper and lower bound.

Note ii: It may be that a_xn+1 is non-randomly determined. Yet, there exists an infinity of choice sequences such that the limiting value of {a_n} is an effectively random element of some infinite subset of reals (known as a 'spread') bounded by a least upper bound and a greatest lower bound.

Remark: Though choice sequences are primarily of interest to intuitionists, here we require that they be governed by ZFC.

Theorem: The question of whether the set of choice sequences contains an element with a non-enumerable limiting value is not decidable.

Proof:

We first prove (Lemma i) that within a spread (x,y), with x the GLB and y the LUB, a non-enumerable exists.

Use a diagonalization formula on the digit string outputs from the set of Turing machines, obtaining one non-enumerable real. Prefix, in turn, every rational digit string to this real and then move the decimal point to the front of each new string. Lemma i is proved.

So then suppose x and y are irrational enumerables. Rationals arbitrarily close to x from above and to y from below can be found.

Let x < p and q < y. So calling the choice sequence limit L, we have

Case i: (x < p < L < q < y).

Case ii: The possibility x < L < p exists, but then a smaller rational can be found between x and L.

Case iii: Likewise for the possibility q < L < y.

It is now straightforward that if L is a choice function limit, there is an effectively random possibility that L is enumerable or non-enumerable. This possibility is in principle undecidable.

Though probability laws suggest that the set of choice sequences includes a sequence with a non-enumerable limit, this suggestion is undecidable.