Re: Cantor and the binary tree

Virgil said:
> In article <1117020437.377622.305540@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
> mueckenh@xxxxxxxxxxxxxxxxx wrote:
>
> > Robert Kolker wrote:
> > > Tony Orlow (aeo6) wrote:
> > > >
> > > > That's all very well and good, if you specify f anf g and figure those
> > > > functions into your comparison. It's a mistake to ignore them.
> > >
> > > Are you capable of following a proof? Even a three line proof?
> >
> > Are you capable to follow a five lines proof without referring to "Big
> > Brother" Cantor? Consistency of set theory is questioned, hence I do
> > not accept Cantor's proof as an argument.
> >
> > line number n
> > 0 0.
> > 1 0 1
> > 2 0 1 0 1
> > ... ..................
> >
> >
> > 1) Each real number of (0,1) is given by a path stretching over
> > infinitely many nodes (bits).
> > 2) All nodes (bits) of the tree belong to a countable set.
> > 3) A node can only exist within a path.
> > 4) Any node increases the number of paths by 1 from 1 coming in, to 2
> > going out. 2 - 1 = 1.
> > 5) Any node increases the number of nodes by 1.
> >
> > Please point out which step is wrong.
>
> WM's "proof" disproved"
>
> WM conflates bounded paths, having terminal or leaf nodes with unbounded
> unending paths which have no terminal or leaf nodes, but contain
> infinitely many intermediate nodes.
>
> 1) Each number of (0,1) is given by an UNENDING path stretching over
> infinitely many nodes (bits).
And yet you claim that no node is infinitely far from the root? Wrong.
besides, I thought you were objecting earlier to appending trailing
zeroes....maybe you changed your mind.
>
> 2) All nodes (bits) of the tree belong to a countable set.
Sure.
>
> 3) A node can only exist within a path.
Of course.
>
> 4) Any node increases the number of ENDING paths, having terminal or
> leaf nodes, by 1 from 1 coming in, to 2> going out. 2 - 1 = 1.
You are really hung up on this lack of end. That's your problem, whether it has
to do with paths on a tree, or the "greatest finite natural". You need to look
where you can actually see something for once.

Anyway, one path is added for any TWO nodes. But do go on.....
>
> 5) Any node increases the number of nodes by 1, but have absolutely
> nothing to do with the number of unending paths.
Actually, if you have an infinite binary tree, with all paths unending, it's
rather difficult to add a node, isn't it? I suggest we would have a more
fruitful conversation talking about inserting nodes in the middle of an
infinite tree, and see what that does for us.
>
>
> All unending paths in an unending binary tree contain infinitely many
> nodes.
Most of which are infinitely far from the root.
>
> The number of leaf nodes exactly equals the number of ending or finite
> paths in any finite binary tree (in which all paths end).
And which you have conveniently dispensed with for the sake of your argument.
Typical Cantorian prestadigitation.
>
> Considering the binary tree whose root is "." and each branch is
> indicated by a "0" or a "1", each leaf node, and therefore each path, is
> represented by a terminating binary fraction , but each unending path is
> represented by a non-terminating binary fraction.
>
> There are moreof the non-terminating than of the terminating.
>
> So WM is wrong yet again.
>
And again you miss the point entirely, but will probably repeat the same
nonsense at least 6 more times, as is your tendency.

Let's put this baby to bed. See if you can poke a hole in this:


Let us consider the middle of a tree, finite or infinite, and what happens when
we insert a node. We have the following tree, where each node has two children,
2x and 2x+1 where the parent node is x:

1
2 3
4 5 6 7
8 9 10 11 12 13 14 15

Let's insert a node between 2 and 5. Sure, this will break the pattern I just
mentioned; that was just so you could make sure you knew whose children were
whose. We'll call our new node X, and say for argument that 5 will be its right
child node. This leaves X with no left child node (I put a period where one
would be):

1
2 3
4 X 6 7
8 9 . 5 12 13 14 15
10 11


Notice that we have not added a path yet, but only extended the paths that
include the branch between 2 and 5, by one branch. Every time we add a node, we
add a branch, but not necessarily a path. Not every node MUST have two
children. In fact, if one creates a binary "tree" with no left nodes, we have a
linked list which consists of a single path, even if it is infintiely long. It
is only when we add a second child to a node that we create a new path. It
takes two nodes to add a path. So, if we then add another element, Y, as the
left child of X, THEN we have produced a new path, ending in Y, a new leaf
node:

1
2 3
4 X 6 7
8 9 Y 5 12 13 14 15
10 11

So, it takes two nodes to add a path. Note that node 1 may have a parent node,
and nodes 8,9,10,11,12,13,14,15 all may have children. It doesn't matter
whether this is a finite tree, or an infinite one. It doesn't matter whether
any leaf nodes existed previously, or whether the paths are finite or infinite.
In all cases, the addition of a node adds one branch, and MAY add a path, but
no more than one additional path for every two nodes or branches. Therefore,
there are ALWAYS fewer paths than nodes, and the proposition that any binary
tree has more branches than nodes is clearly wrong.

If someone wants to tell me that one can't insert a node in the tree, I suggest
they ask their programmer friends, before wasting my time.

--
Smiles,

Tony
.

Relevant Pages

  • Re: Cantor and the binary tree
    ... >> unending paths which have no terminal or leaf nodes. ... >> paths in any finite binary tree. ... >> There are more of the non-terminating than of the terminating. ... > and if one is infinite, ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... >> one of these numbers becomes uncountably infinite while the other ... > 2) All nodes of the tree belong to a countable set. ... nothing to do with the number of unending paths. ... There are moreof the non-terminating than of the terminating. ...
    (sci.math)
  • Re: Binary Tree and Pairs of Nodes
    ... was an infinite countable set of nodes" and "iff infinite sets could ... entire infinite complete binary tree. ... This shows that there is no set of all reals. ...
    (sci.logic)
  • Re: Cantor and the binary tree
    ... >>> unending paths which have no terminal or leaf nodes. ... >> and if one is infinite, ... Finite tree only have finite numbers of nodes and paths. ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... Rather, each one leads to another (unending, infinite) subtree. ... But for this new tree and each of its nodes 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)