Re: Cantor and the binary tree

In article <1117381085.891784.283560@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
mueckenh@xxxxxxxxxxxxxxxxx wrote:

> *** T. Winter wrote:
> > In article <1117175027.610055.60140@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>
> > mueckenh@xxxxxxxxxxxxxxxxx writes:
> > > *** T. Winter wrote:
> > ...
> > > > > 4) Any node increases the number of paths by 1 from 1 coming in, to
> > > > > 2
> > > > > going out. 2 - 1 = 1.
> > > >
> > > > Eh? Now you are talking about an ever increasing finite tree, not
> > > > about
> > > > an infinite tree. If you are talking about an infinite tree it may be
> > > > allowable, but because the number of paths is infinite, so it stays
> > > > the
> > > > same when you add 1 to it.
> > >
> > > Quite wrong! I consider an infinite tree.
> >
> > What do you mean when you write "any node increases the number of paths by
> > 1",
> > etc. when you are talking about an infinite tree?
>
>
> n tree
>
> 0 0.
> / \
> 1 0 1
> / \ / \
> 2 0 1 0 1
> /\ /\ /\ /\
> ..... ...................
>
> Every path starts at 0. at level n = 0 and does never end.
> Every path is isomorphic to a real number of (0,1).

If you mean that there is a bijection between paths and reals, you
cannot arrive at it by the method you are describing.

> Every path exists in that tree but not every path can be distinguished
> at level n from every other path.
> Every node increases the number of paths which are visible, at level n,
> as being different from each other.
> This property can be utilized to set up a bijection between nodes and
> paths as follwos:
> Every path which distinguishes itself from the others by branching off
> to the right hand side is bijected to that node where this happens.

This is hardly a bijection as infintely many paths get mapped to each
node

> Every path which distinguishes itself from the others by branching off
> to the left hand side is considered to be the continuation of the
> incoming one.
>
> Examples.
> Path 0,1000...is mapped on the node on level n = 0.
> Path 0,01000... is mapped on the left node on level n = 1.
> In this way all numbers (except 0 = 0.000...) which differ from all
> other numbers by at least one digit are mapped on the nodes.
>
> Regards, WM


Assume a binary tree in which each node is a parent and has a left-child
and a rght-child, but with one unique root node.

(1) To show the set of nodes has a bijection to N:

Given any node, let the root node be labeled 1 and thereafter, on the
path connecting the root to the given node let each left branch in that
path be labeled 0 and each right branch in that path labeled 1.
Then the given node is represented by the binary integer formed by the
finite sequence of binary digits taken in order from root to the given.

This shows that for each node there is a (binary) natural.

And if the binary tree is maximal as described, for eqch natural, there
will be a node, by following the appropriate branches from the root.

Thus, I have created a bijection from the set of nodes to the set of
naturals, N = {1,2,3,...}. QED

(2) To show that there is a bijection between the set of all (unbounded)
paths of such a binary tree and P(N), the set of subsets of N, .

Given any infinite path in a maximal binary tree,
create a subset S of N as follows:
if the nth child node of the tree is on a right branch from
its parent node, n is to b a member of s, but if on a left branch,
n is to be excluded.

It is easily seen that
every infinite path defines a subset of N,
different infinite paths define different subset of N
every subset of N is created by some infinite path

Thus I have constructed a bijection from the set of infinite paths to
the set of all subsets of N, i.e., to P(N). QED.

Both bijections constructed as requested.
.