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

On Dec 13, 4:13 am, George Greene <gree...@email.unc.edu> wrote:
> On Dec 12, 12:07 pm, WM <mueck...@rz.fh-augsburg.de> wrote:
> The point here is that EVERY finite binary tree has EXACTLY THE SAME
> number of nodes as paths,
> since EVERY PATH ENDS AT A NODE, injectively&surjectively&bijectively.
> There is an obvious and natural bijection between a path and the node
> where it ends.

It really depends on how to do you define "Path", if you assert that
it must begin with 0 and if you assert that it must be undirectional
then YES you are correct (given the degenerate path is there).
However lets examine removing the condition of "beginning with 0" and
lets examine its effect, note I'll keep the condition of
undirectionality of a path, Also note that the paths in the below tree
are in reality directed paths (although I didn't represent them by
arrows which I should do) and the direction is from above downwards.
Now lets examine the binary tree at level 2, (or actually 3 if we

0
/ \
0 1
/ \ / \
0 1 0 1

This has 7 nodes, BUT it has "8" paths other than the degenerate path!
those are:

0-0
0-1
1-0
1-1
0-0-0
0-0-1
0-1-0
0-1-1

So we have 9 paths and 7 nodes.

However If we stipulate that a path must begin from 0, then you are
right the number of paths is the same as the number of nodes.

In the diagonal argument usually the binary sequences refer to the
string of decimals AFTER the decimal point, so it can begin with 0 or
it can begin with 1, so limiting the first decimal to be 0 is not in
correspondence with Cantor's argument, simply you cannot define a
diagonal by changing the first element of the first string? So this
limitation of the beginning of a path to be 0 is not necessary and it
only serves to give a some false impression of an argument.

Anyhow in the INFINITE case a path corresponds to the set of all nodes
in it, and so the total number of paths in the infinite binary tree
corresponds to the power set of N. And this was proved by Cantor to be
uncountable.

So the INFINITE binary tree have UNCOUNTABLY many paths (All beginning
with 0 and are unidirectional)!

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