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 ]
 Zaljohar@gmail.com Posts: 2,665 Registered: 6/29/07
Re: On the infinite binary Tree
Posted: Dec 12, 2012 3:40 PM

On Dec 12, 8:07 pm, WM <mueck...@rz.fh-augsburg.de> wrote:
> 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
>

Ah I see, so you are imposing another condition on the definition of a
path, 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. 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? Cantor says it is uncountable, therefore the
total number of INFINITE paths in the binary tree can be uncountable!

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. But the problem really lies in that point, if you think
there is no undefinable real, then of course it follows that all reals
are definable and thus it is clear that we have countably many of
them. However I don't see any reason other than a demand for clarity
for us to suppose that all reals are definable. Actually Cantor's
argument of uncountability of reals if one is to take it to its full
girth then it mounts to saying that MOST of reals are non definable!
So your objection to Cantor has nothing to do with thought about the
infinite binary tree actually, the core of your objection is against
non definable reals.

As regards properties of the reals, it is argued that a non definable
real would preserve all those properties, so trichotomy and all other
properties of the reals still survive in the non definable reals, but
WE cannot SEE this or show that, but it doesn't mean they are not
preserved by them. So if A,B,C are non definable reals, it is still
the case that A > B > C leads to A>C, etc... But we cannot show that,
this doesn't mean it is not there. Anyhow honestly the idea of non
definable reals is disgusting, but many times (probably most) reality
is so.

Zuhair

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