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: On the infinite binary Tree
Replies: 64   Last Post: Dec 17, 2012 11:06 AM

 Messages: [ Previous | Next ]
 mueckenh@rz.fh-augsburg.de Posts: 18,076 Registered: 1/29/05
Re: On the infinite binary Tree
Posted: Dec 13, 2012 1:56 AM

> Ah I see, so you are imposing another condition on the definition of a
> path,

No, that is *the* definition of a path in a Binary Tree.

> that it must begin with 0 since it is representing a number in
> the interval [0,1], that's OK, then according to that I can see that
> you are correct since the number of paths do corresponds to the number
> of ending node, and with my calculation it would be less than the
> total number of nodes by one. I'll need to check this again, but let
> me agree with you on that for the current moment.
>
> But still you have a problem. What you really managed to prove is that
> the total number of FINITE undirectional paths beginning from 0 in the
> infinite binary tree is countable, since we can simply draw an
> injective map from those paths to their ending nodes.

No. I proved that the number of infinite paths is countable by
constructing all nodes of the Binbary Tree by a countable set of
infinite paths.

> This is clear.
> But the problem that you will face is with the INFINITE undirectional
> paths beginning from 0 of the infinite binary tree, now those paths
> cannot be identified with the nodes at their ends because they simply
> have no ending nodes because they are infinite, so you need to
> calculate another way to map those kinds of paths to nodes.

> The only
> one I can think of really is to map each infinite path to the
> COLLECTION of all nodes in it, which is to say we map each infinite
> path to the subset of all nodes of the binary tree that simply have
> all and only those nodes in that path as elements of. Now this will
> bring us again to Cantor, how many subsets of nodes of the infinite
> binary tree do we have?

No again. The number of subsets of the set of naural numbers is of
interest. Every subset of N is represented by one and only one single
infinite path. It is not interesting to find out the set of subsets of
nodes - at least not for our question.

> Cantor says it is uncountable, therefore the
> total number of INFINITE paths in the binary tree can be uncountable!

And it is countable too. Therefore countability is not well defined.

> However I think you are claiming that each infinite path is to be
> mapped to the Godel number of the defining formula of it (which is a
> finite parameter free formula), and of course by then we'll be having
> only countably many such infinite paths of the binary tree. And also
> this is well known since definable sets in this way are always
> countable (this is pretty much standard). Now the real point is what
> if there is a path for which we cannot find a finite parameter free
> formula that define it, by then those kinds of paths cannot be proved
> countable in this way. However you seem to dismiss that possibility as
> nonsensical.

It is nonsensical because the same could be assumed for Cantor's
diagonal. It would be undefinable and it would be impossible to prove
that it differs from all lines of the list - in particular if
undefinable reals exist and are members of the list.

However, this question is irrelevant. It stands that the complete
Binary Tree can be constructed by countably many paths. That's enough

Regards, WM

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