Ki Song
Posts:
287
Registered:
9/19/09


Re: Distinguishability of paths of the Infinite Binary tree???
Posted:
Dec 24, 2012 10:20 AM


On Sunday, December 23, 2012 3:20:35 PM UTC5, zuhair wrote: > 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
Hi Zuhair,
This is the first time I'm responding to you.
I really don't see the conundrum you are having. I mean, this is what it sounds like you are trying to do: constructing a bijection between a "countably infinite product of finite sets" and the natural numbers.
Let T = {0,1}, K_n = Union T x i, i=1,2,3,4,... n, K = Union T x i, i = 1,2,3,4,...
(If you want to start from 0, then I guess you can append {0} x {0} or something.)
Your argument sounds like:
Each K_n is finite. So K must be countable.
First, we map the elements of K_1 to the initial segment of N with f_1. Second, we map K_2 to the initial segment of N shifted by the final element of f_1 with f_2. Third, we map K_3 to the initial segment of N shifted by the final element of f_1 with f_3. ...etc.
Conclusion: K is countable.
Of course, this argument makes no sense, since the map f constructed from pasting together f_1, f_2, f_3 ... is not going to be welldefined.

