Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: The uncountability infinite binary tree.
Replies: 118   Last Post: Dec 17, 2012 8:49 PM

 Messages: [ Previous | Next ]
 ross.finlayson@gmail.com Posts: 2,720 Registered: 2/15/09
Re: The uncountability infinite binary tree.
Posted: Dec 16, 2012 5:29 PM

On Dec 16, 12:39 pm, Rupert <rupertmccal...@yahoo.com> wrote:
> On Dec 16, 7:47 pm, "Ross A. Finlayson" <ross.finlay...@gmail.com>
> wrote:
>
>
>
>
>
>
>
>
>

> > Al-Jofar writes:
>
> > 1: "This is a simple Corollary of Cantor's diagonal argument actually.
> > Proof: Let G be any countable subtree of the infinite binary tree that
> > is 0 rooted and such that all paths ending by 0-0-0-... or by
> > 1-1-1-...are among the paths of G. "

>
> > 'Let G be a subtree of the IBBT including all expansions representing
> > fractions by powers of two (there are two of those for each of those
> > values).'

>
> > 2: "Let f be a bijective function from the domain N of all
> > naturals(except 0) to the set of all infinite paths of G. "

>
> > For the countable subtree only containing fractions by powers of two
> > and their dual representations, that's countable (and not obviously
> > all the paths).

>
> > 3: "Construct the diagonal path d_f in the following manner: The root
> > (i.e. the 1st) node of d_f is 0 labeled. Now for n=1,2,3,.. ; The n
> > +1_th node of d_f is labeled by a label that is opposite to the label
> > of the n+1_th node of the path of G that f sends n to. "

>
> > Let G be all the paths.  In lexicographic order, here as described as
> > BT _oo (binary tree's breadth-first traversal at infinity), augmented
> > with .0111... being first to reflect the modification of "the" anti-
> > diagonal, the generated anti-diagonal path is .0111..., that is the
> > least element of G in the ordering.

>
> No, it's not.
>

> > With an un-modified construction of the antidiagonal, the generated
> > anti-diagonal path is .111... and at the end of any course-of-passage
> > through the paths in their natural order, i.e., never before the end.
> > That is, there's a simpler corollary that is the same as the binary
> > anti-diagonal argument.

>
> > 4:  "Now clearly the diagonal d_f (actually the anti-diagonal but it
> > shall be called the diagonal for short) is a path and clearly it is
> > labeled in a way that is different from labeling of all paths of G. So
> > d_f is missing from G. "

>
> > In the course of passage with the natural order of the paths, d_f =
> > f(0) or here f(1) and is not missing from G.

>
> Nonsense.
>

> > 5:  "So any countable subtree of the infinite binary tree, that is 0
> > rooted and that has all paths ending with 0-0-0-.. or with 1-1-1..
> > among its paths; would be missing a path of the infinite binary tree.
> > "

>
> > That doesn't follow for the natural ordering of the paths by their
> > content as expansions.  Then though while the paths are totally
> > ordered, well-ordering them would be as well-ordering the reals.

>
> That's irrelevant.
>
>
>
>
>
>
>

> > Then I'll happily accept that the anti-diagonal argument is much the
> > same for the list of expansions or the tree of expansions, then that
> > EF's antidiagonal is .111... and at the end of the list and BT's
> > antidiagonal is .111... and rightmost of the tree.

>

In the breadth-first ordering, after 0 = .000..., we don't
(standardly) have a proof that there's a least element in the normal
ordering (or they'd be well-ordered by their normal ordering), but we
do have a proof that there's a well-ordering for each level of the
tree. So, we can select from G\0 (here being all the paths setminus
zero's) all those less than .1 then all those less than .01 and so on,
where then obviously, from the finite to the infinite, there are never
none left, but, as well, there isn't a level or row such that there
isn't an element starting with that many zeros that would be lesser in
the normal or usual or natural breadth-first ordering. So, as we know
that all the elements of the bread-first traversal would be starting
with zero at each relevant place, the only way for it to be different
at that place and be part of the anti-diagonal, is for the value to be
one.

Paths:

.000... = BT(0)
.000... = BT(1)
.000... = BT(2)
...
.111... = BT(2^w)

Anti-diagonal, from the beginning:

.111... = BT(2^w)

Then it's quite relevant in as to well-ordering the reals, well-
ordering the paths.

Regards,

Ross Finlayson

Date Subject Author
12/14/12 Zaljohar@gmail.com
12/14/12 Virgil
12/15/12 Zaljohar@gmail.com
12/14/12 William Elliot
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Rupert
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 trj
12/15/12 Zaljohar@gmail.com
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Zaljohar@gmail.com
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Zaljohar@gmail.com
12/15/12 Zaljohar@gmail.com
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Zaljohar@gmail.com
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Virgil
12/16/12 Zaljohar@gmail.com
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Zaljohar@gmail.com
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Zaljohar@gmail.com
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Virgil
12/16/12 ross.finlayson@gmail.com
12/16/12 Virgil
12/16/12 Zaljohar@gmail.com
12/16/12 Zaljohar@gmail.com
12/16/12 Virgil
12/17/12 mueckenh@rz.fh-augsburg.de
12/17/12 Virgil
12/15/12 Zaljohar@gmail.com
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Virgil
12/15/12 Tanu R.
12/15/12 Virgil
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Virgil
12/17/12 mueckenh@rz.fh-augsburg.de
12/17/12 Virgil
12/15/12 Virgil
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Virgil
12/17/12 mueckenh@rz.fh-augsburg.de
12/17/12 Virgil
12/15/12 Virgil
12/15/12 Rupert
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 netzweltler
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Virgil
12/15/12 Tanu R.
12/15/12 Zaljohar@gmail.com
12/15/12 Virgil
12/15/12 Tanu R.
12/15/12 namducnguyen
12/15/12 Tanu R.
12/15/12 namducnguyen
12/15/12 Tanu R.
12/16/12 Rupert
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Rupert
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Rupert
12/16/12 ross.finlayson@gmail.com
12/16/12 Rupert
12/16/12 ross.finlayson@gmail.com
12/16/12 Rupert
12/16/12 ross.finlayson@gmail.com
12/16/12 Rupert
12/16/12 ross.finlayson@gmail.com
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Rupert
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Rupert
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Rupert
12/17/12 mueckenh@rz.fh-augsburg.de
12/17/12 Virgil
12/17/12 mueckenh@rz.fh-augsburg.de
12/17/12 Virgil
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Rupert
12/17/12 mueckenh@rz.fh-augsburg.de
12/17/12 fom
12/17/12 Virgil
12/17/12 Virgil
12/16/12 Virgil
12/16/12 Virgil
12/16/12 m. m. m.
12/16/12 Virgil
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Rupert
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Rupert
12/17/12 mueckenh@rz.fh-augsburg.de
12/17/12 Roland Franzius
12/17/12 Virgil
12/17/12 mueckenh@rz.fh-augsburg.de
12/17/12 Virgil
12/17/12 fom
12/16/12 Virgil
12/16/12 m. m. m.
12/16/12 Virgil
12/16/12 m. m. m.
12/16/12 Virgil
12/16/12 ross.finlayson@gmail.com
12/16/12 trj
12/16/12 Zaljohar@gmail.com
12/16/12 mueckenh@rz.fh-augsburg.de
12/16/12 Virgil
12/16/12 Virgil
12/15/12 Virgil
12/15/12 Tanu R.
12/15/12 Virgil
12/15/12 Virgil
12/15/12 Virgil