Search All of the Math Forum:

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

Topic: On the infinite binary Tree
Replies: 64   Last Post: Dec 17, 2012 11:06 AM

 Messages: [ Previous | Next ]
 ross.finlayson@gmail.com Posts: 2,578 Registered: 2/15/09
Re: On the infinite binary Tree
Posted: Dec 17, 2012 11:06 AM

On Dec 16, 2:16 pm, forbisga...@gmail.com wrote:
> On Saturday, December 15, 2012 1:27:08 PM UTC-8, Ross A. Finlayson wrote:
> > On Dec 15, 9:08 am, forbisga...@gmail.com wrote:
>
> > > On Friday, December 14, 2012 10:34:33 PM UTC-8, Ross A. Finlayson wrote:
>
> > > > On Dec 14, 10:17 am, forbisga...@gmail.com wrote:
>
> > > > > On Friday, December 14, 2012 6:30:11 AM UTC-8, Charlie-Boo wrote:
>
> > > > > > On Dec 12, 5:26 am, Zuhair <zaljo...@gmail.com> wrote:
>
> > > > > > > Lets take the third degree binary tree
>
> > > > > > >      0
>
> > > > > > >    /    \
>
> > > > > > >   0     1
>
> > > > > > >  / \    / \
>
> > > > > > > 0  1 0  1
>
> > > > > > > Now this has 7 nodes BUT 8 paths, those are
>
> > > > > > > 0-0
>
> > > > > > > 0-1
>
> > > > > > > 1-0
>
> > > > > > > 1-1
>
> > > > > > > 0-0-0
>
> > > > > > > 0-0-1
>
> > > > > > > 0-1-0
>
> > > > > > > 0-1-1
>
>
>
> > > > > > in your manipulations of the tree.
>
> > > > > four of his paths start at second level nodes.
>
> > > > > > You need to diagonalize the binary tree rather than the list of real
>
> > > > > > numbers - and account for multiple trees representing the same
>
> > > > > > number.  Or just ignore the real number interpretation and deal with
>
> > > > > > binary strings without regard to numbers.
>
> > > > > > My many examples of diagonalization in different contexts is a model
>
> > > > > > to do just that.  It's always good to generalize.
>
> > > > > My concern is how one shows there are countably many paths through
>
> > > > > the infinite nodes.  I can't move to the second path though infinity
>
> > > > > until I've completed the first, that is unless an algorith is proposed
>
> > > > > that lets me idenify which infinite paths I've taken without completely
>
> > > > > taking them.  I might identify a path by its representation as a rational
>
> > > > > number.  Unfortunately that leaves out the irrational numbers.
>
> > > > In the binary tree, of nodes of finite distance from the root, it
>
> > > > takes all the nodes to represent the rationals, of the unit
>
> > > > interval.
>
> > > > Now, consider diagramming the tree this way, in a breadth-first
>
> > > > traversal, lay out each row in the y-axis at the corresponding x-
>
> > > > coordinate of the row, with its y value being the rational value of
>
> > > > the expansion.  Then, the maximum value of this point set at each x is
>
> > > > max(x) = 1- 1/2^x.  In the limit that's one.  Now, the paths are
>
> > > > ordered lexicographically, in the breadth first traversal, for each
>
> > > > they are.  And, at each row, the difference and distance between paths
>
> > > > is constant.  Then, the infinite binary tree, would have that, in the
>
> > > > limit or asymptotically, there are are infinitely many paths,
>
> > > > lexicographically ordered, in the unit interval, in their natural
>
> > > > ordering as representations of reals, or rationals and irrationals, in
>
> > > > the unit interval.  These paths are dense in the unit interval.  And,
>
> > > > for any node, there is the simple branch to the left or right that
>
> > > > represents a rational.
>
> > > > Now this is all without some completed infinity or "at least
>
> > > > infinitely many" number of rows or here columns.  Yet, as a function,
>
> > > > modeled by each row, the function so standardly modeled has range
>
> > > > [0,1], here without simply declaring that at the point at infinity the
>
> > > > range is the continuous line segment.  Via Cauchy, these expansion are
>
> > > > all the real numbers of the unit interval, and then some, with dual
>
> > > > representation of real in their binary expansions.
>
> > > > Then, one way to look at the rows of the binary tree is as a family of
>
> > > > functions BT_p = b^p for b as the domain from zero to 2^p. Then,
>
> > > > connecting the dots of each BT_p(n) to BT_p+1(2(n+1)) and BT_p(2(n
>
> > > > +1)-1), or along those lines, the resulting diagram, has that the
>
> > > > infinite trees are rooted in those.
>
> > > > So, there doesn't exist a breadth-first traversal of the infinite
>
> > > > binary tree.  Yet, that is a countable enumeration, of the nodes in
>
> > > > breadth first order, and the paths in their natural order, of their
>
> > > > values.
>
> > > > There are infinitely many natural integers.
>
> > > > Regards,
>
> > > > Ross Finlayson
>
> > > And yet when you do this you never get to an
>
> > > infinite binary tree because every leaf expanded so
>
> > > far is finite.  There is a dual representation of
>
> > > (some?) rationals but not of any irrational.
>
> > > My concern is about the countability of the paths
>
> > > through the infinite binary tree.  Every path is
>
> > > an infinite expansion.  Some numbers have two paths
>
> > > that represent them.  I don't see how you get from
>
> > > countable nodes to countable paths.  Cantor showed
>
> > > any algorith for counting paths can be shown to not
>
> > > count many paths.
>
> > (....)
>
> > Let's look at what Cantor showed us:  combined with that there isn't a
>
> > function from naturals to reals in their usual order:  none of the
>
> > other functions are a bijection from naturals to a continuous line
>
> > segment of the reals.  A function from naturals to reals in their
>
> > usual order doesn't see the same results.
>
> > For example, imagine lining up the real numbers from zero to one in
>
> > their normal order.  The expansions in binary would look like:
>
> >    .0000...
>
> >    .0000...
>
> >    .0000...
>
> >    ...
>
> >    .1111...
>
> >    .1111...
>
> >    .1111...
>
> Not so fast here.  Those ellipse are the problem.  Cantor applies to
> an enumerated set.  It can be infinte but it must be countable.  If you
> assume the set is uncountable then you needn't worry about Cantor but
> if you assert it countable it falls to you to show how to count the members
> and Cantor's diagonalization will apply.
>

> > Here, the ellipse in the middle has that the values go from zero, to
>
> > one, here with EF or BT (EF_oo and BT_oo, where BT_oo is EF_2^oo).
>
> > Then, with the antidiagonal argument, starting from the beginning, and
>
> > different at a place for each, "the" antidiagonal:
>
> >    .111(1) = 1.0
>
> > is at the "end" of the list of those values.
>
> There is no end and the diagonalization differs from every indexed
> path at the indexed node.  Since you are talking about an "infinite
> binary tree" there is only one way to traverse the nodes to achieve
> a particular path and the nth node differs from that of the diagonal
> because it's value differs from the value at the nth node.
>

> > With Cantor's first, also called nested intervals, with that there is
>
> > a way to naturally or lexicographically order the expansions, these
>
> > are the same elements as all that comprise the complete ordered field,
>
> Not so fast here either.  Cantor didn't order the set of rationals in
> numeric order when he produced his bijection with the set of natural
> numbers and he certainly didn't just assert there was a bijection.
>

> > because they are between zero and one, and there are none not in it.
>
> But are the countable?
>

> > Here, via the total ordering of the elements in the path, and that
>
> > they are only constructed in that order, they go from zero to one, and
>
> > then as inputs to the algorithm of nested intervals:  there aren't
>
> > any.
>
> > Then of course there are the powerset results, for these there is a
>
> > set-theoretic recourse, about how the reals aren't just the complete
>
> > ordered field, but the continuum, then also about how the infinite is.
>
> > Then, for each node in the tree, finitely distant from the root, and
>
> > there are infinitely many:  those are countable.  Here, Cantor's
>
> > results about the binary tree, are not via a direct anti-
>
> > diagonalization, instead, that the reals biject to to {0,1}^w as does
>
> > P(N) that transitively they have the same cardinal (Cantor-Schroeder-
>
> > Bernstein theorem generally), and that the paths do to the Cauchy
>
> > expansions of the unit line segment, of real numbers.
>
> >    |{0,1}^w| = |R_[0,1]| = |R| = |{0,1}^w| = |P(N)| > |N|
>
> > It would be of interest to see an actual diagonalization of the tree,
>
> > the constructive argument.  Because, in the breadth-first traversal of
>
> > the paths, the order of the expansions is the same as the order of the
>
> > natural integers.
>
> There is not breadth-first traversal of "the paths" because every
> breadth-first traversal is of uncountably infinite paths.  Every node
> has an infinite set of paths passing through it.  This is always true
> no matter how big the node number.  The set of paths passing through
> a given node is never finite.
>

> > Draw a line:  that's what Cantor shows:  the line is drawn without
>
> > lifting the pencil.  It's drawn:  from the origin, its origin.
>
> > There are infinite integers, are there not:  infinite integers?
>
> But there aren't enough to uniquely index all the reals.

That's reasonable. The count or enumeration begins, and follows a
course, and it ends.

Here, we know that it begins with elements that start with as finitely-
many zeros as would have 1-values for each, and it ends with
infinitely many ones.

Then, applying diagonalization to describe an anti-diagonal: it's
found at the end.

There is an end to the paths from the left: it's at the right, just
as the end of the paths from the right is at the left. Starting a
breadth-first traversal at zero, it goes to one, starting at one, it
goes to zero. The expansion values it covers in its course-of-passage
have that we know how those begin, as the course proceeds.

Are they infinite?

The point of the diagonal method is to establish whether they're
countable. Here, with the consideration that there exists a bread-
first traversal of the tree, it is a feature of the tree.

Then, for uniquely indexing the reals, here this BT function, as an
example of EF, the function, has that EF, standardly modeled by real
functions, meets conditions of continuity for its range, AND: when
used in the antidiagonal or nested intervals theorems: sees different
results, than any other function. It uniquely indexes, and is unique.

Draw the line. That isn't done with stippling points until its
complete: it's drawn.

Regards,

Ross Finlayson

Date Subject Author
12/12/12 Zaljohar@gmail.com
12/12/12 mueckenh@rz.fh-augsburg.de
12/12/12 Virgil
12/12/12 mueckenh@rz.fh-augsburg.de
12/12/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 trj
12/13/12 Virgil
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/13/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/13/12 Virgil
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/13/12 Virgil
12/13/12 Virgil
12/13/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/13/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/14/12 mueckenh@rz.fh-augsburg.de
12/13/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 Virgil
12/14/12 Zaljohar@gmail.com
12/14/12 Zaljohar@gmail.com
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Virgil
12/14/12 mueckenh@rz.fh-augsburg.de
12/14/12 Tanu R.
12/14/12 Virgil
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Virgil
12/12/12 Virgil
12/13/12 mueckenh@rz.fh-augsburg.de
12/12/12 george
12/13/12 Zaljohar@gmail.com
12/13/12 mueckenh@rz.fh-augsburg.de
12/13/12 george
12/14/12 mueckenh@rz.fh-augsburg.de
12/14/12 Virgil
12/14/12 mueckenh@rz.fh-augsburg.de
12/14/12 Tanu R.
12/14/12 Virgil
12/15/12 mueckenh@rz.fh-augsburg.de
12/15/12 Virgil
12/15/12 Tanu R.
12/14/12 Charlie-Boo
12/14/12 forbisgaryg@gmail.com
12/15/12 ross.finlayson@gmail.com
12/15/12 forbisgaryg@gmail.com
12/15/12 ross.finlayson@gmail.com
12/16/12 forbisgaryg@gmail.com
12/17/12 ross.finlayson@gmail.com
12/16/12 Ciekaw
12/16/12 Virgil