|
|
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
adopt empty set approach)
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
|
|
