Re: Cantor and the binary tree

On 13 Jun 2005 03:21:03 -0700, mueckenh@xxxxxxxxxxxxxxxxx wrote:

>
>
>Martin Shobe wrote:
>> On 11 Jun 2005 06:29:14 -0700, mueckenh@xxxxxxxxxxxxxxxxx wrote:
>>
>> >
>> >
>> >Randy Poe wrote:
>> >> mueckenh@xxxxxxxxxxxxxxxxx wrote:
>> >> > Is here a bijection possible between uncountable sets?
>> >>
>> >> Sometimes.
>> >>
>> >> There exist bijections between R and C, for instance. But
>> >> not between R and P(R).
>> >>
>> >> > Can you enumerate R <--> R?
>> >>
>> >> I can construct a bijection from R to R, if that is what
>> >> you are asking.
>> >>
>> >> Here's one: f(x) = x.
>> >
>> >And I can construct a bijection from nodes to paths:
>> >
>> > 0.
>> > / \
>> > 0 1
>> > /\ /\
>> > 0 1 0 1
>> > /\ /\ /\ /\
>> > ...................
>> >
>> >Everywhere a path branches off, it gets the node. The other one keeps
>> >that node which already was mapped on it before. I need not knwow which
>> >path gets which node, because all are of similar value. And so on in
>> >infinity.
>>
>> That is not a bijection.
>>
>> If you compare, '000...' with '010...', you would map '000...' to '0'
>> and '010...' to '01'. If you compare '000...' with '011...', you
>> would map '000...' to '0' and '011...' to '01'. QED.
>
>There is a path P (for instance 1/3 = 0.010101... = P) This path has
>got a node (a node is mapped on it). In the same edges there are many
>other paths, but that does not bother us. They will get their nodes
>later on. From the path P and its companions many other paths separate
>in the next node. Among them is the path P'. The node, where this
>happens, is mapped on P'. Its companions remain nodeless nude.
>So we have two nodes mapped on two paths, P and P'. The next time when
>a bunch of paths separates from P, *one* of those gets the node where
>that happens. (Same for separation of a bunch from P' and that bunch
>remaining with P'.) The others do not yet get nodes but will have to
>wait until their turn will have come. So every path is either equipped
>with a node or it has not yet been separaed from other paths or it has
>alreay its node but is not yet separated from all others. In any case
>we make sure that an individual path cannot exist separated from all
>others without carrying a node. Whether individual paths separated from
>all others do exist at all, that is another question.

You still do not have a bijection, as this will not assign a node to
every path.

Proof.

Let N be the set of nodes, and P be the set of Paths.

Let f:N->P be a function described above. For all n in N, n is on
f(n). (I.e. the path f(n) goes through the node it is assigned to).
Construct a path p as follows. Start at the root. If the node
assigned to the root goes to the left, got to the right. After this,
as you visit each node, go the way that the path assigned to that node
does not go. Because the tree is maximal, we can always go the other
way. Therefore, this path exists.

There is no n in N such that f(n) = p. If n is on p, we can see by
the construction of p, that f(n) =/= p. If n is not on p, we can see
by the definition of f, that f(n) =/= p. Therefore, f is not a
bijection.

>There is no loophole: An individual path separated from all the others
>cannot exist without its node.

The loophole is that the individual paths never seperate from *all*
the others. There will always be an uncountable number of paths left
to seperate from.

Martin

.