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 ]
Virgil

Posts: 9,012
Registered: 1/6/11
Re: On the infinite binary Tree
Posted: Dec 13, 2012 3:08 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

In article
<e981867a-a612-4c49-9241-a9b89124dee1@v7g2000yqv.googlegroups.com>,
Zuhair <zaljohar@gmail.com> wrote:

> On Dec 13, 9:56 am, WM <mueck...@rz.fh-augsburg.de> wrote:
> > > 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.
> >

> Actually it is not. There is no need at all to stipulate that a path
> must begin by 0. It is a fixed
> definition.
>
> I already showed you that the number of paths in a second degree
> binary tree (or third degree if you want to adop the empty path) IS
> larger than the total number of nodes.


Actually not!

For finite trees of more than one node there are always more nodes than
paths.

For COMPLETE finite binary trees (all paths of equal length):
1 node gives 1 path
3 nodes gives 2 paths
7 nodes gives 4 paths
...>
2^n -1 nodes gives 2^(n-1) paths

And what I mean by paths those
> that can start with 1 or with 0, but with the condition that it must
> be unidirectional. And showed it clearly and I've illustrated each
> path. You have 9 paths (inclusive of the empty path) and only 7 nodes.
>

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


That only shows that in a complete infinite binary treethe set of paths
surjects onto the set of nodes, which does not prove what WM claims it
proves.
> >
>
> This only means that you can have a bijective function from a
> countable subset of infinite paths of the binary tree to the set of
> all nodes, which everyone already know that this is possible, because
> we all agree that the total number of nodes of the infinite binary
> tree is countable.
>
> What would be a proof is if you manage to define an injection from the
> set of ALL infinite paths of the binary tree to the set of all nodes
> of the binary tree.
>
> If you managed to do that, the next question is:
>
> where is that proof? please show us


Note that WM's attempt at a such a proof above was, as usual, trivially
flawed
>
> Zuhair

--





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.