Re: The complete infinite binary tree has only countably many infinite paths.

On 25 Mrz., 21:55, "calvin.ost...@xxxxxxxxx" <calvin.ost...@xxxxxxxxx>
wrote:
On Mar 25, 11:50 am, WM <mueck...@xxxxxxxxxxxxxxxxx> wrote:

0  [say instead (0,1)

Agreed. But no path ends there. So it is not important.

(1,1), (1,2)
(2,1), (2,2), (2,3), (2,4)
 ...
(n,1), ..., (n, 2^n)

So those are the nodes.  {(n,m)| n,m in N, m<=2^n}

Every node with even second co-ordinate has value 1, every node with
odd second co-ordinate has value 0.

Labeling function L( (n,m) ) = m+1 mod 2

Construct the complete tree (from the path p_0 = 0.000...) by using
all paths that lead to a node with value 1 and afterward having only
nodes with value zero.

Okay, well, a tree is a set of edges.  Let us instead add the edges.
That is more definite and precise.   Paths result by supervening on
the pattern of edges.

That is possible. But it will refer to my proof (B).

Can you rigorously specify the edges that are being added, in
a manner such as I have done above (instead of just with pictures
and informal words).

As well as labelling the nodes you can also label the edges leading to
the nodes by the same scheme.
(1,1), (1,2)
(2,1), (2,2), (2,3), (2,4)
...
(n,1), ..., (n, 2^n)

So use just
the edges {(n,m)| n,m in N, m<=2^n}

When you do that, you will see there are more paths that you
attempted to limit the set of paths to.

I do not see that. I see that there is an nfinite but countable set of
lines. I wold be nice if you said whether you could agree.

Then all the paths (except  p_0) can be labelled by their last node
that has value 1.

Here, I think, is your problem.  You are not noticing that when
you add a single path, you are actually adding many paths.

What many of paths do I add when I add 0.1000...?

The net result in the end is that after all your paths have been
added, there are many other paths that exist, because of the
edges that have been added to make the paths, which you
have not noticed.

When you consider my proof (A), then you see that I add always exatly
one path.
You can even consider all paths that end on some node (regardless of
its value) and then always turn left. I this way many paths are added
infinitely often, like
0.1|000..., 0.10|000..., 0.100|000
where "|" appears behind the node of destination.

Perhaps the problem arises because of using the idea of one
tree as a limit of the other.  I don't think that is necessary here.
As above for the nodes, we should be able to define the final
tree explicitly without using a limit.

The tree consists of all lines that are constructed by paths that end
by infinitely many nodes. That is not a limit. Simply take the set of
all those paths.

Here is the problem you may have with using a limit.  The
limit tree is a union of all the edges in the sequence of trees.
That is indeed true.   If there is an edge in the limit tree, that
edge must exist in some tree in the sequence.   HOWEVER,
the same is not true about paths.   Paths exist in the limit
tree that do *not* exist in any tree in the sequence. This
is because the paths "interact" with one another in the way
edges do not.

For that argument I deviced my proof (A). Paths may be imagined to do
this or that. They cannot but follow one line in the tree. And there
ae all lines in the tree. There is no infinite sequence of bits that
is lacking. Neverteless all this is constructed by a countable number
of paths.

Every path you add is of the form a finite sequence of 0's
and 1's, following by infinite sequence of 0's.   However,
there are paths in the final tree that are not like this.   That is
because the paths interact with one another.  You must look
at the individual edges and how then can be made into
paths in the final tree.  You do not add paths, you add edges.
Paths come FOR FREE.  You cannot pick and choose the
paths you add.  They sneak in as sets of joined edges and
there is nothing you can do about it.

Please be more clear. And, as you criticize the edge construction,
please refer to proof (A).
You want to prove that there are more paths in the tree than lines
paved by a countable set of paths.

Regards, WM

.

Relevant Pages

  • Re: Cantor Confusion
    ... As an infinite bit sequence, yes, but there is *no* node in your tree ... is *no* node in your tree that represents an infinite sequence. ... And when you switch to paths representing numbers you have something ...
    (sci.math)
  • Re: OT? evolution explains what?
    ... > tree ring info but I'm wondering if there is anything more you can add ... > original starting cell, right? ... Best evidence at the moment is that it was RNA, ... sequence 18S rna genes, common to all living things (apart from viruses, ...
    (uk.philosophy.atheism)
  • Re: Cantor Confusion
    ... > Dik T. Winter schrieb: ... As an infinite bit sequence, yes, but there is *no* node in your tree ... is *no* node in your tree that represents an infinite sequence. ...
    (sci.math)
  • Re: Cantor Confusion
    ... As an infinite bit sequence, yes, but there is *no* node in your tree ... is *no* node in your tree that represents an infinite sequence. ... You do not require that one digit represents the number 1/3 in Cantor's ...
    (sci.math)
  • Re: The complete infinite binary tree has only countably many infinite paths, says WM.
    ...   That is not what you must do. ... Denote the leading node of any sequence of nodes by its number followed ... In that infinite tree, ...
    (sci.logic)