
Distinguishability of paths of the Infinite Binary tree???
Posted:
Dec 23, 2012 3:20 PM


This is just a minor conundrum that I want to discuss about WM's argument about the complete Infinite binary tree (CIBT). It is really about Cantor's argument. But the discussion here will be at intuitive level rather than just formal level.
Let's start with "distinguishability" at finite binary trees, and then make some rough analogy with the infinite binary tree.
Let's take the binary tree with two levels below the root node level which is the following:
0 / \ 0 1 / \  \ 0 1 0 1
Now with this three one can say that distinquishability is present at all levels below the root node level, so we have two distinguishable paths at level 1 that are 00 and 01. While at level 2 we have four distinguishable paths that are 000, 001, 010, 011. However the reason why we had increased distinguishability at level 2 is because we had differential labeling of nodes at that level! Now if we remove that differential labeling we'll see that we can only distinguish two longer paths by the labeling of their nodes, like in the following tree:
0 / \ 0 1 / \  \ 0 0 0 0
Now clearly the only distinguishability present in that tree is at level 1 because all nodes at level 2 are not distinguished by their labeling. So the result is that there is no increase in the number of distinguishable paths of the above tree when we move from level 1 to level 2. See:
Paths at level 1 are: 00 , 01. Only Two paths. Paths at level 2 are : 000, 010. Only Two paths.
Similarly take the tree:
0 / \ 0 1 / \  \ 1 1 1 1
Paths at level 1 are: 00 , 01. Only Two paths. Paths at level 2 are : 001, 011. Only Two paths.
So the increment in number of paths in the original binary tree of level 2 after the root node, is actually due to having distinct labeling of nodes at level 2. If we don't have distinct labeling at a further level the number of distinguished longer paths stops at the last level where distinguished labeling is present.
This is obviously the case for FINITE binary trees.
Now lets come to the complete infinite binary tree, which is an actual infinite tree where at each level a node have two path each down to one node below and each one of those below nodes is having a distinct label from the other, and labeling of any node of that tree is restricted to either 1 or 2.
Now at FINITE level of the infinite binary tree, we only have countably many finite paths down from the root node. i.e. the set of all distinguishable (by labeling of their nodes) finite paths of the CIBT is actually COUNTABLE. BUT the set of all Paths that are distinguishable on finite basis is UNCOUNTABLE. Furthermore the subtree of the CIBT that have all finite paths of the CIBT as initial segments of its paths is actually the CIBT itself according to Cantor, all of those uncountably many infinitely long paths are distinguishable at finite level! But distinguishability at finite level is COUNTABLE?
To clarify any two paths P1, P2 of the CIBT are said to be distinguishable on finite basis iff there exist an n_th far node down from the root node of P1 that is labeled differently from the n_th far node down from the root node of P2. Of course P1,P2 might be infinite paths, or might be finite.
Of course we know that every node in any path of the CIBT is at finite distance down from the root node, so there is no node of the CIBT that lies at some infinite distance down from the root node, so there is no distingushiability of paths of the CIBT beyond that occurring at finite level, so the total number of infinite paths of the CIBT must be the same as the total number of distinguished finite paths of the CIBT. So it must be countable. But that is not the case?
Also the proof of Cantor is actually about uncountability of paths that are distinguishable on finite basis.
So how come we can have uncountably many distinguishable paths on finite basis while finite distinguishability itself is countable? what is the source for the extra distinguishability over the finite level? we don't have any node at infinite level???
One of course can easily say that at actual infinity level some results are COUNTERINTUITIVE, and would say that the above aspect is among those counterintuitive aspects, much like a set having an equal size to some proper superset. But I must confess that the above line of counterintuitiveness is too puzzling to me??? There must be something that I'm missing?
Any insights?
Zuhair

