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: 16,051
Registered: 1/29/05
Re: On the infinite binary Tree
Posted: Dec 12, 2012 12:07 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On 12 Dez., 11:26, Zuhair <zaljo...@gmail.com> wrote:
> WM has presented the idea that the infinite binary tree must have
> countably many paths. It seems that he thinks that the total number of
> paths in a binary tree is always smaller than or equal to the total
> number of nodes. So since obviously the number of nodes in an infinite
> binary tree is countable, then the number of paths must be so. But
> since each real can be represented by a path in a 0,1 labeled infinite
> binary tree, then we must have countably many reals thus defying
> Cantor.


Correct. It is nice that there are mathematician who have grasped it.
The issue is this:
Every partial tree from level 0 to level n has
-1 + 2^(n+1) nodes.
The number of all finite paths is the same, because every finite path
ends at some node.
The number of all path traversing the complete partial tree and
branching after that in two paths is
2^(n+1).
In the limit we have
numbers of paths traversing the complete tree (and after that
branching in two paths) divided by number of nodes of the complete
tree = 1.

>
> The 0,1 labeled infinite binary tree he is speaking of is the
> following:
>
>      0
>    /    \
>   0     1
>  / \    / \
> 0  1 0  1
> .  .  .     .


Correct!

> Answer: in order to justify this claim one must first see what is
> happening at the finite level. And make a simple check of the number
> of nodes and the number of paths through those nodes. If that
> confirmed that the total number of nodes is more or equal to paths
> then there would be some justification for that claim.
>
> Let's see:
>
> Lets take the first degree binary tree which is the following
>
> 0.  One node, no paths


We could say 1 degenerated or empty path. Set theorists like empty
things.
>
> The second degree binary tree is:
>
>  0
> /  \
> 0 1
>
> This has three nodes and two paths.


or three nodes and three paths, respectively.
>
> 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
>
> Of course I'm treating paths as directed paths away from the root
> node, and so a path contain edges linking nodes in the SAME direction.


You should count them again. There cannot be more endings of paths
than nodes, namely 7.
>
> IF we remove the directional requirement matters would really differ,


but that does not matter because the real numbers in the unit interval
always start with "0."

> However we will not adopt that,

That's a good idea.

> As the degree of the binary tree increase the total number of paths
> increases more and more relative to the total number of nodes, as
> shown above this begins with the third degree binary tree (8 paths
> with 7 nodes).
>
> So the impression we have from the finite world is that of paths being
> actually MORE in number than nodes in any binary tree of a degree
> higher than 2.


You made an error, but your arguing is very sconsistent. If we are to
believe that there are more paths than nodes, then we should be able
to prove this from the finite world. Because also Cantor's list is
completely caught in the finite world. No line is "infinite".

I am extremely satisfied that you recognize these facts. Your little
error is not important. On the contrary, it is helpful. Without having
made this error you hardly would have dared to publish your sober but
extremely non-matheological thoughts.

> So there is NO justification at intuitive level for the idea that the
> number of paths of a binary tree must be smaller than or equal the
> total number of nodes in it.


Why do you say intuitive level here? Every sober mathematics
calculates limits from only the finite terms of a sequence as you have
attempted here. That is the way mathematics runs. To call that
"intuitive" and to call the infinitary nonsense of matheology
mathematics is really the height of impudence.

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.