Re: Cantor and the binary tree

In article <MPG.1cffeb3541bb0a9e989d50@xxxxxxxxxxxxxxxxxxxxxxxxx>,
Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx> wrote:

> Virgil said:
> > In article <MPG.1cffa061d4f6cb89989d2f@xxxxxxxxxxxxxxxxxxxxxxxxx>,
> > Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx> wrote:
> >
> >
> >
> > > Virgil, you're totally convoluted. Try to poke a hole in the argument I
> > > just
> > > posted regarding insertion of nodes in ANY tree. Sorry, the prior
> > > existence
> > > of
> > > leaf nodes is not a ruse that's available for you in this one.
> >
> > It is the absence, not existence, of leaf nodes that creates the
> > situation that TO does not comprehend.
> >
> > In such a maximal binary tree, where there are no leaf nodes since no
> > path ends, the number of nodes is Card(N) and the number of paths is
> > Card(P(N))
> >
> prove it.


(1) Given any finite path, let the root node be labeled 1 and
thereafter, let each left node be labeled 0 and each right node labeled
1.
Then the last node in that finite path is represented by the binary
integer of the 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.

Both bijections constructed as requested.
.

Quantcast