Re: Approaching the infinite binary tree


"LudovicoVan" <julio@xxxxxxxxxxxxx> wrote in message news:85a88c3e-0e26-4b34-9c7c-5f5b7645ec71@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I am thinking along the following lines, and I'd greatly appreciate
some feedback.

Given the set of the extended naturals: N* := N u {w}, where
'w' (omega) is the limit ordinal.

Let's consider the infinite binary tree, that is -informally- a binary
tree with w levels. We can represent, in bilogarithmic scale, this
tree embedded in half of a unit square, as follows:

k = 0 _ _ 0
/\
/ \
/ \
1 _ / \ _ 1
/\ /\
2 _ / \ / \ _ 2
... /\ /\ /\ /\ ...
w _ /______________\ _ w

Every binary sequence can be associated to a specific path in this
tree by the following sequential (in fact, inductive) rule over the
levels of the tree:

-- Base case: start from point (0,0) at level 0, written (0;0)_[0]

-- Successor case: from point (m,n)_[k-1],
go to point (m + 1/[2^(-k)] , n)_[k]
if the next (the k-th, counting from 1) digit
in the sequence is "0",
go to point (m , n + 1/[2^(-k)])_[k]
otherwise.

We are, equivalently, embedding the infinite binary tree into a half
of a square lattice with -informally- 2^w points per side, normalized
to the unit square. Other mappings were possible, but this is
irrelevant up to constant factors.


Gee, I hope you aren't going to try and use this to well order the Reals?

I imagine the first number is zero, but what is the second number? I am having a bit of trouble locating the (w-1)th digit to increment.


Here the limit point for any given sequence provably exists and is
unique(*), it corresponds to a point on the limit diagonal:
specifically, to one of the -informally- 2^w points that make up the
limit diagonal in our lattice. (In fact, we have used *finite*
induction, which works for all finite though *unbounded* processes.
We'll need *transfinite* induction to get "all w levels" and properly
talk about *infinite* strings, or lists.)

In any case, a non-standard result seems already here: the uniqueness
of our limits implies a *bijection* between sequences and limit
points. To each binary sequence corresponds one and one only limit
point.


Well, duh, its a tree, so of course there is only path between the root and end nodes.


So, for instance, here it is *not* correct to take the sequence
"0(1)" to be equal to (to correspond to the same limit point as)
"1(0)", there are no such equalities. Indeed, even just geometrically,
from the diagram above we can see that *all* distances get halved at
each step, so that the distances between the points on the limit
diagonal tend *uniformly* to zero, and all points remain uniformly
distributed and distinct.

Whether you take 0(1) to be the same as 1(0) is really a matter of what you are doing. I commonly think of Reals as subsets of N, in which case 0(1) is different to 1(0), but it seldom makes any real (!) difference.


I need solid ground to proceed further, so I'd appreciate some
feedback as to the soundness of the construction and the (few, basic)
results given here.


The weeding out process where you lop off branches of the form .xxx(0)1 cuts out only countable duplicates - for only those reals which have terminating binary expansion. There are however uncountably many Reals that don't terminate.



Thank you,

-LV

(*) If we consider our construction as providing the points over
successive diagonals in the given lattice (the dotted lines in the
diagram below), we have an iterated function system (IFS) that
provably converges to a specific attractor, here the set of points on
the limit diagonal.

k = 0 _ _ 0
/\
/ \
/ \
1 _ /......\ _ 1
/\ /\
2 _ /..\..../..\ _ 2
/\ /\ /\ /\

The number of points on a diagonal at step k is 2^k, and they delimit
(2^k)-1 equal intervals, each of (normalized) length equal to 1/
[(2^k)-1]. In the limit case we can -informally- say that we have 2^w
limit points delimiting (2^w)-1 equal intervals, each of length 1/
[(2^w)-1]. With the theory of IFS we can prove (I won't try) that a
distance function expressed in these geometrical terms provides a
*complete* metric space.

.

Relevant Pages

  • Approaching the infinite binary tree
    ... Let's consider the infinite binary tree, ... Every binary sequence can be associated to a specific path in this ... limit points delimiting -1 equal intervals, ...
    (sci.math)
  • Re: OT? evolution explains what?
    ... > tree ring info but I'm wondering if there is anything more you can add ... > original starting cell, right? ... Best evidence at the moment is that it was RNA, ... sequence 18S rna genes, common to all living things (apart from viruses, ...
    (uk.philosophy.atheism)
  • Re: The complete infinite binary tree has only countably many infinite paths, says WM.
    ...   That is not what you must do. ... Denote the leading node of any sequence of nodes by its number followed ... In that infinite tree, ...
    (sci.logic)
  • Re: Compact subsets of {0,1}^N
    ... > the case where a is the empty sequence, ie a sequence of length 0: ... > T be the tree of all finite sequences a such that S_a intersect K ... > f(every finite initial segment of a) is an initial segment of f. ... each of which is a sibling. ...
    (sci.math)
  • Re: Approaching the infinite binary tree
    ... Let's consider the infinite binary tree, ... Every binary sequence can be associated to a specific path in this ... To each binary sequence corresponds one and one only limit ...
    (sci.math)