Re: Cantor and the binary tree

In article <5rbmb11h2kph14fsjb57mfubs8pt5fcpm7@xxxxxxx>,
Martin Shobe <mshobe@xxxxxxxxxxxxx> wrote:

> On Wed, 22 Jun 2005 10:31:39 -0400, Tony Orlow (aeo6)
> <aeo6@xxxxxxxxxxx> wrote:
>
> >Virgil said:
> >> In article <MPG.1d22309d742aee97989e75@xxxxxxxxxxxxxxxxxxxxxxxxx>,
> >> Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx> wrote:
> >> > Excuse me Martin, but maybe you should have some of what I am smoking.
> >> > Every
> >> > path ends in a leaf node, which are half the nodes in the tree. You
> >> > start
> >> > with
> >> > one node that represents the root path. For each pair of nodes, you
> >> > create a
> >> > new path. A finite tree with n levels (including the root) has (2^n)-1
> >> > nodes,
> >> > (2^n)-2 branches, and only 2^(n-1), or (2^n)/2 paths, as denoted by its
> >> > leaf
> >> > nodes. This relationship is preserved through infinity, even in the
> >> > absence
> >> > of
> >> > identifiable leaf nodes.
> >>
> >> TO is right for finite trees but wrong for maximal binary trees.
> >No, this property holds for all balanaced binary trees.
>
> Can you prove that this relationshiop is preserved through infinity?
> That seems to be the real sticking point here.
>
> >> For any finite tree there is at least one more node than there are
> >> paths. If every path shares the root node, eachfinite path will also
> >> have a leaf node, so there is at least one extra node.
> >Incorrect. There is one more node than branches, and twice as many branches
> >as
> >paths.
>
> for finite trees this is true. For infinite trees it no longer holds.

Actually, it is not even true for finite trees.

For a binary tree in which every path is only one branch long, there the
same number of paths as branches, namely 2.

For a binary tree in which each path is two branches long, there are 4
paths and 6 branches.

If each path is 3 branches, there are 14 branches and 8 paths.

And in general if each path in n branches there are 2^n paths and and
2*(2^n-1) branches, which is never quite twice the number of paths.

So that TO's "TWICE as many" is always wrong.


>
> >> TO's mistake is to presume that what happens for finite trees must also
> >> be the case for (infinite) maximal binary trees. It is a presumption
> >> that can, in fact, be disproved, and has been disproved in these threads.
> >No it has not. Your various interpretations of the branches in the tree
> >don't
> >prove things about the structure of the tree itself, and your mishmoshed
> >judgement of "countability" doesn't hold water for me anyway. Have you ever
> >actually USED a binary tree for anything? I mean, weren't you the one that
> >told
> >me one can't insert a node in the middle of the tree, when computers do it
> >every single day?

TO gets it wrong, as usual. What I actually said was that a computer
cannot inset a node at an arbitrary poiition in a maximal binary tree,
the reason being that no computer with only a finite memory capacity can
deal with arbitrary positions in infinite trees.

Now a Turing machine acting on an infinite tape,...
.

Relevant Pages

  • Re: Cantor Confusion
    ... You need to assume that the complete union of ... The union of all finite trees is not an infinite tree. ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... > infinitely far from the root node in any binary tree, ... or infinite binary trees. ... > consecutive naturals. ...
    (sci.math)
  • Re: Cantor Confusion
    ... >>> The union of all finite trees is also the union of all last levels. ... The union of all finite trees is not an infinite tree. ...
    (sci.math)
  • Re: Cantor Confusion
    ... The union of all finite trees in R is ... the union of all finite trees in R is a finite tree.) ... Due to the schism "infinite set of finite numbers" there are two ...
    (sci.math)
  • Re: Cantor Confusion
    ... > from the union of all rational trees. ... In the union there is *no* infinite path. ... Each node is in one of the finite trees, so it is also in the union. ...
    (sci.math)
Quantcast