|
|
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 "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
|
|
