Das Kalenderblatt 100612

11/06/2010 - 12:05 von WM | Report spam
A lesson for set theorists

The complete infinite binary tree contains, by definition, all real
numbers between 0 and 1 as infinite paths, i. e., as infinite
sequences { 0, 1 }^N of bits.

0,
/ \
0 1
/ \ / \
0 1 0 1
/
0 ...

The set { a_k | k in N } of nodes a_k of the tree is countable.

a0,
/ \
a1 a2
/ \ / \
a3 a4 a5 a6
/
a7 ...

If every node a_k is covered by an arbitrary infinite path p_k
containing that node, then no further node is remaining to distinguish
any further path from the paths p_k of the countable set P = { p_k | k
in N }. This proves that it is impossible to distinguish more than
countably many paths by infinite sequences of bits.

FIRST COUNTER ARGUMENT

All nodes of a path are covered by other paths. Therefore covering all
nodes of the binary tree by a countable set of paths does not show
that all paths of the binary tree form a countable set.

Here is an example for the counter argument: We can cover every node
of path p = 0.111... by means of covering every path p# of the set
{
0.000...
0.1000...
0.11000...
0.111000...
...}

No. Every path p# of the form 0.111...111000... has at least one node
0 at a position where p = 0.111... has a node 1. So when covering, in
the binary tree, all nodes of path p none of the paths p# has been
covered. In other words: every p# has an uncovered node after all
nodes of p have been covered.
Vice versa, when all p# have been covered, then p has not yet been
covered. Every path p# deviates from p leaving at least one of its
nodes 1 uncovered.

Of course this is only an existence proof. After covering all paths
p#, an uncovered node of p cannot be named. But if no such node
existed, p would have been written down (= covered in the tree) by
writing down (= covering in the tree) all paths p#.

Then, however, Cantor's diagonal proof would fail because then the
possible antidiagonal p = 0.111... of the above list was in the list.

SECOND COUNTER ARGUMENT

In order to save Cantor's diagonal proof, it must be claimed that
although all nodes of p are covered by the set of paths p#, there is
no path p# = p. That means:
I) All nodes 1 of p = 0.111... are in the list of all paths p# above.
II) No line p# contains all these nodes 1, i.e., the limit p is not in
the list.

These two assertions cannot be satisfied simultaneously.

Proof by complete induction. If the existence of all nodes 1 in
different lines of the list is claimed, then at least two lines must
be shown which, with respect to their contents of nodes 1, cannot be
replaced by one line. This is obviously impossible.

On the contrary, it can be proved by complete induction, hence for
every line of the list, that all nodes which are in that line and in
all previous lines, also are in the next line. (Complete induction
holds for all natural numbers, though not for the set of them. But
that ist not required here.)

Proof by construction of an infinite set. Construct the above
list, but remove always line number n after having constructed the
next line number n + 1. Then the list shrinks to a single line but
this single line contains the same as the list because never anything
has been removed that had not been added before to an existing line.

Therefore this single line contains all nodes 1. It is the limit p 0.111... If, however, line number n is not removed after line number n
+ 1 has been constructed, there cannot be an effect of this marginalia
on line n + 1 and later lines.

If a single line p = 0.111... can be constructed at all (otherwise it
was impossible to construct a complete Cantor list) then this line
must also be in the complete list.

When imaging all nodes 1 in one single line, then nobody will complain
about all nodes existing in one single line. When imaging all nodes 1
written as in the above list, then the existence of all nodes 1 in a
single line is denied.

This result appears paradoxical. But the only paradoxical is the
assumption that infinity can be finished and that thousands of rather
intelligent people have been believing that for more than 100 years.


THIRD COUNTER ARGUMENT

All this binary tree twaddle does not apply because real numbers are
only limits and Dedekind-cuts.

Fine. Limits and Dedkind-cuts have to be defined. The number of all
definitions is countable, in fact it is finite and will remain so for
ever.

[This lesson was inspired by a discussion with William Hughes in
sci.math on June 9, 2010.]
http://groups.google.com/group/sci....ing=d&

Gruß, WM
 

Lesen sie die antworten

#1 Carsten Schultz
11/06/2010 - 12:18 | Warnen spam
Am 11.06.10 12:05, schrieb WM:
A lesson for set theorists

The complete infinite binary tree contains, by definition, all real
numbers between 0 and 1 as infinite paths, i. e., as infinite
sequences { 0, 1 }^N of bits.

0,
/ \
0 1
/ \ / \
0 1 0 1
/
0 ...

The set { a_k | k in N } of nodes a_k of the tree is countable.

a0,
/ \
a1 a2
/ \ / \
a3 a4 a5 a6
/
a7 ...

If every node a_k is covered by an arbitrary infinite path p_k
containing that node, then no further node is remaining to distinguish
any further path from the paths p_k of the countable set P = { p_k | k
in N }. This proves that it is impossible to distinguish more than
countably many paths by infinite sequences of bits.



Geschwàtz.

Viel Spaß weiterhin dabei, Dich làcherlich zu machen!

Carsten

Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.

Ähnliche fragen