Re: abundance of irrationals!)

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

> Virgil said:
> > In article <1115808674.466909.326260@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
> > mueckenh@xxxxxxxxxxxxxxxxx wrote:
> >
> > > Russell wrote:
> > >
> > > > No. The obvious linear enumeration of *nodes* is not an
> > > > enumeration of the reals. For that, you need to enumerate
> > > > the different paths. That's not merely a rearrangement of
> > > > the enumeration of nodes; if you think it is, then please
> > > > tell us how you associate each node with one and only one
> > > > path. Can't be done.
> > >
> > > Tell us how you associate Cantor's antidiagonal with one and only one
> > > line, e.g., where it ends. Cant't be done.
> > >
> > > But the nodes can be shown to be not less than the paths.
> >
> > I challenge you to show this. I claim that one can ennumerate the nodes
> > but not the paths.
> >
> > Each node can be represented by a finite string of zeros and ones, the
> > root node by one digit string, "1", and given any finite string, "s",
> > representing a node, the left and right nodes at the next level by "s0"
> > and "s1", respectively.
> >
> > Since interpreting these as binary integers counts them, they are
> > countable.
> >
> > For the infinite strings needed to represent paths, a somple diagonal
> > costruction will show that no list can be complete.
> >
> >
> >
> > > It is not
> > > possible to say which node belongs to some single path.
> >
> > Why not?
> >
> There is a 1-1 correspondence between the points and lines, the nodes and
> branches. You have not specified exactly what you mean by branch, so i will
> define it as a line connecting two nodes.

In a binary tree, a "branch" is a directed line segment joining two
nodes, with the direction being away from the root node.

> Perhaps you mean a string of such
> connections, in which case that is also specified by the string of digits
> denoting each number, 0 for left branch and 1 for right.

That would be a path. A maximal path is one which starts at the root
node and either ends at a terminal node from which no further branches
extend, or does not stop at all.

In an infinite binary tree (with no finite maximal paths) every maximal
path contains an infinite sequence of branches.

Each node corresponds to the finite path starting at the root node and
ending at the given node, so there are only countably many nodes
coreesponding to those countably many finite paths.

But there are uncountably many maximal ( and therefore inifinte) paths
in an infinite binary tree as defined above.
.

Relevant Pages

  • Re: Cantor and the binary tree
    ... 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 ... And if the binary tree is maximal as described, for each natural, there ... Given any maximal path in this maximal binary tree, ...
    (sci.math)
  • Re: Cantor Confusion
    ... The union of all finite trees and the complete infinite tree are ... We may embed every finite binary tree in a complete infinite binary tree ... branching left endlessly. ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... 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 ... And if the binary tree is maximal as described, for each natural, there ... Given any maximal path in this maximal binary tree, ...
    (sci.math)
  • Re: Java Interview Questions: Am I Being Too Difficult?
    ... > and I have generally ask a range of OO, Java, and "good programming ... > Create one or more classes that represent a binary tree. ... > A node in this tree holds only a single, String, value. ... > As an added exercise, how would you make this code thread-safe? ...
    (comp.lang.java)
  • Re: Java Interview Questions: Am I Being Too Difficult?
    ... > and I have generally ask a range of OO, Java, and "good programming ... > Create one or more classes that represent a binary tree. ... > A node in this tree holds only a single, String, value. ... > As an added exercise, how would you make this code thread-safe? ...
    (comp.lang.java.programmer)
Loading