Re: Cantor and the binary tree

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

> Virgil said:
> > In article <MPG.1cffa39924382800989d30@xxxxxxxxxxxxxxxxxxxxxxxxx>,
> > Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx> wrote:
> >
> > > Virgil said:
> > >
> > > > So WM is wrong yet again.
> > > >
> > > > And TO too!
> > > >
> > > Virgil, you have repeated this nonsense now six or so times verbatim. If
> > > you
> > > were paying attention, I think you'd realize this is not related to what
> > > WM
> > > is
> > > claiming. Look at my argument concerning insertion of a node, and respond
> > > to
> > > that. It's the relative number of paths vs. nodes that WM is addressing,
> > > in
> > > response to your claims that you have an infinite tree with uncountable
> > > paths
> > > (because you're hung up on leaf nodes for some reason) and countable
> > > nodes,
> > > when paths are always less numerous than nodes. Pay attention. It's no
> > > wonder
> > > these discussions with you go around in circles, when you don't even know
> > > what
> > > they're about.
> >
> > Each node in a maximal binary tree is the end node of a finite path from
> > the root node, but no node is the end node of an infinite path from the
> > root node,
> >
> > So that any assumption that the number of nodes equals the number of
> > unending paths requires proofs that neither WM nor TO have produced, or
> > can produce.
> >
> > I can produce a bijection between the number of nodes in such a tree and
> > N, and I can produce a bijectin between the number of unending paths and
> > P(N).
> >
> Do it.



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

Both bijections constructed as requested.
.

Relevant Pages

  • Re: Cantor and the binary tree
    ... >>> In a maximal binary tree, the set of nodes easily bijects to N and the ... > Given any infinite path in a maximal binary tree, ... > Thus I have constructed a bijection from the set of infinite paths to ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... But I later supplied that easy bijection to "found" my assertion. ... > In a maximal binary tree, the set of nodes easily bijects to N and the ... And if the binary tree is maximal, having no leaf nodes, there will also ... Given any infinite path in a maximal binary tree, ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... >> Then the last node in that finite path is represented by the binary ... >> And if the binary tree is maximal, having no leaf nodes, there will also ... >> Given any infinite path in a maximal binary tree, ... >> Thus I have constructed a bijection from the set of infinite paths to ...
    (sci.math)
  • Re: Binary Tree and Pairs of Nodes
    ... It differs from the path you map to 0 digit-position 0. ... that every infinite path that exists ... in the infinite binary tree has one node mapped onto it. ...
    (sci.logic)
  • Re: Cantor and the binary tree
    ... >> Why should I describe a single infinite path? ... Therefore I have constructed all reals by a brief ... > Looking at nodes you only discuss terminating representations ... tree can be easily seen with a slight adjustment to the binary tree. ...
    (sci.math)