Ki Song
Posts:
221
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 UTC-5, 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 "distinguish-ability" 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 distinquish-ability is present at
>
> all levels below the root node level, so we have two distinguishable
>
> paths at level 1 that are 0-0 and 0-1. While at level 2 we have four
>
> distinguishable paths that are 0-0-0, 0-0-1, 0-1-0, 0-1-1. However the
>
> reason why we had increased distinguish-ability 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: 0-0 , 0-1. Only Two paths.
>
> Paths at level 2 are : 0-0-0, 0-1-0. Only Two paths.
>
>
>
> Similarly take the tree:
>
>
>
> 0
>
> / \
>
> 0 1
>
> / \ | \
>
> 1 1 1 1
>
>
>
> Paths at level 1 are: 0-0 , 0-1. Only Two paths.
>
> Paths at level 2 are : 0-0-1, 0-1-1. 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 COUNTER-INTUITIVE, and would say that the above aspect is
>
> among those counter-intuitive aspects, much like a set having an equal
>
> size to some proper superset. But I must confess that the above line
>
> of counter-intuitiveness 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 well-defined.
|
|
