Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
mueckenh@rz.fh-augsburg.de

Posts: 15,737
Registered: 1/29/05
Re: On the infinite binary Tree
Posted: Dec 13, 2012 1:56 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

> 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.


I did it already.

> 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
to have a contradiction.

Regards, WM


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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.