Re: Cantor and the binary tree

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

> *** T. Winter wrote:
>
> > > There can be no node at the end, because there is no end. We do not
> > > need any node at the end in order to show that the set of nodes is
> > > equivalent to that of paths. It is shown by the following steps. Please
> > > point out which step is wrong.
> > >
> > > 1) Each real number of (0,1) is given by a path stretching over
> > > infinitely many nodes (bits).
> >
> > Yup.
> >
> > > 2) All nodes (bits) of the tree belong to a countable set.
> >
> > Yup.
> >
> > > 3) A node can only exist within a path.
> >
> > Yup.
> >
> > > 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.

Not very carefully, it appears.

> In this ever lasting and
> always existing tree I consider one branching, selected by sheeer
> accident. I see that it contributes to the set of all paths 1 element
> and to the set of all nodes 1 element. (You must know, I am just
> interested how the elements of this ever lasting tree are generated.)
> Whereever I look, I make this same observation. Thre is not one single
> deviation in this tree!
>
> > > 5) Any node increases the number of nodes by 1.
> >
> > Same remark here.
>
> Same remark here.
> >
> > So what does that prove about infinite trees?
>
> Roughly the same number of paths and nodes.

Consider a binary tree for which there are no terminal or leaf nodes, in
other words, each maximal path from the root node passes through
infinitely many nodes and along infinitely many branches but never
terminates.

(1) Given any finite path, let the root node be labeled 1 and
thereafter, let each left child in that path be labeled 0 and each right
child in that path labeled 1.
Then the last node in that finite path is represented by the binary
integer formed by the sequence of binary digits for all those nodes
taken in order from root to the node in question.

And if the binary tree is maximal, having no leaf nodes, there will also
be a node for each binary integer.

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

(2) 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.

And since Card(N) < Card(P(N)), there can be o bijection between the set
of odes and the set of maximal (unending) paths in such a tree.
.