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

On 29 Mrz., 05:00, "Peter Webb" <webbfam...@xxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:
Every binary sequence is used at least once when constructing the
tree. 0.111... is paved by all paths of the form 0.111...111000....
(where even arbitrarily many of the first ones can be left out).

******************************
OK, but what number (element of N) corresponds to 0.1111... ?

None. All those paths that have been used to construct the right hand
part of the binary tree that contains 0.111... are in this list:

0.1000...
0.11000...
0.111000...
....
But "the limit" 0.111... has not been used for construction.

Now we have two choices:
(I) Either we can say: There is no completed infinity. There is no
path at all with aleph_0 nodes and therefore there is no path 0.111...
with aleph_0 nodes = 1. Nothing has crept into the tree after
construction. For every path with n nodes = 1, there is a path with n
+1 nodes = 1. And this fact is what we call "the limit 0.111...". In
particular, there is no node that distinguishes 0.111... from all
paths used to construct it.

But then the same holds for Cantor's list, for instance a list like
this

0.000...
0.1000...
0.11000...
0.111000...
....

which is diagonalized by replacing 0 by 1. The diagonal number is
obviously the limit 0.111... But as this limit (under choice I) does
not differ by a bit (or digit) from all other entries of the list,
Cantor's proof does not hold. It only shows that the diagonal number
of the first n lines of the list is not in lines 1 to n. But in this
special example it is in line n+1. And as Cantor's proof is an
impossibility proof, one counter example is sufficient.

Concluding: potential infinity is not suitable to construct a diagonal
number that differs from every line of the list.

(II) Our second choice is to accept Cantor's proof that there is a
diagonal number that differs from every entry of the list by a bit (or
digit in the usual presentation). Of course it need not differ from
every entry by the same bit in usual representations. But in the
special list presented above, this is unavoidable. If 0.111... differs
from all finite sequences of nodes = 1, namely 0.111...111000...,
then this cannot happen by a node at a finite place, because for every
finite place there is a sequence of nodes = 1 that is identical to the
limit. Unless we go back to (I), we must assume that something that
has not been used to construct the tree has crept in. And this
something differs from all paths used for construction.

How can that happen? And if it can happen, why can't it happen in
Cantor's list, such that this list, after construction, is

0.000...
0.1000...
0.11000...
0.111000...
....
0.111...

Of course the last line is not subject to diagonalization, because it
has not a finite index. The diagonal number has crept in during
construction. It's the same effect as in the tree. Again there is no
reason to accept uncountability.

And if you consider my proofs (B) or (C) uncountability is obviously
impossible. A countable number of edges, each in a fixed position,
cannot lead to an uncountable number of paths (se my first remark).

Regards, WM
.

Relevant Pages

  • Re: An uncountable countable set
    ... But you still only have terminating paths. ... Indeed, in your tree with terminating edges, such numbers do not exist. ... there is *no* construction of the list given. ... But Cantor's list only contains numbers with an infinite binary ...
    (sci.math)
  • Re: The complete infinite binary tree has only countably many infinite paths.
    ... Construct the binary tree starting from a "tree" that has only one ... procedure all nodes and every infinite sequence of bits (including the ... have a construction of all paths that end by infinitely many zeros. ...
    (sci.logic)
  • Re: Binary Tree and Pairs of Nodes
    ... belongs to one of the mapped paths, ... By construction any labeled path will have either all 0's or all 1's ... the whole tree, any path would have been tagged. ... And again my point is that the case of the binary tree is somewhat ...
    (sci.logic)
  • Re: Answer to OJ
    ... Every infinitely-long binary string constructed this way has only ... but your construction will not create them ... All those with infinitely many 1's are missing. ... closer to finishing the tree - only further from starting. ...
    (sci.logic)
  • Re: The complete infinite binary tree has only countably many infinite paths.
    ... Construct the binary tree starting from a "tree" that has only one ... procedure all nodes and every infinite sequence of bits (including the ... have a construction of all paths that end by infinitely many zeros. ...
    (sci.logic)