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)!