Re: Cantor and the binary tree

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.

>> 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? Drop the bijections, and inspect the structure of the tree.

The trees do not change anymore than 3 changes to 4 when incremented.
(I.e. the value of a variable changes to *different* tree when you
insert, the tree does not.)

>>

.

Relevant Pages

  • Re: Cantor Confusion
    ... binary tree) the set of paths is uncountable but the set of edges is ... whole countably infinite path (the union of it`s all finite subpaths ... And some of what olds for finite trees cannot hold for infinite ones. ... every infinite path would also have to have a leaf node. ...
    (sci.math)
  • Re: Comments suck [Was: Length of variable names affect performance?]
    ... >On Tue, 12 Apr 2005, Dave Vandervies wrote: ... >tree of some kind, whose entries are ordered by increasing X or Y ... each leaf node to reduce the depth-increasing effects of poorly chosen ... but here (for internal nodes) and in the create_new_node ...
    (comp.programming)
  • Re: Approaching the infinite binary tree
    ... An infinite complete binary tree is a tree with Aleph_0 levels, ... path ends in a leaf node, but in the complete infinite binary  tree none ... just as endless strings of charactes do not ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... >>> This no more proves countability of the set of paths than the fact that ... >>non-empty subsets) of paths in the tree. ... path ends in a leaf node, which are half the nodes in the tree. ... one node that represents the root path. ...
    (sci.math)
  • Re: Mueckenherzs Confusion
    ... Set of nodes which belong to a tree or path or level. ... at least in finite trees. ... Is every ordered subset of nodes of a tree a path in that tree? ... For a path in a finite tree, one needs only to identify the leaf node. ...
    (sci.math)