Up to previous page:
March 2000 / Homepage / Paola Cattabriga
Re: 0.999..., 1.000... and Cantor's proof sci.math 26 Jun 1998
In article , [email protected] writes:
> I'm not sure whether you're asking why the proof fails
>in binary. In case yes: Whoever started this thread pointed out
>that the traditional proof is wrong because of the ambiguity
>in a number's decimal representation: we get a new sequence
>of digits from the diagonal argument, but it might be a digit
>sequence not on the list that represents a number already on
>the list.
> This is not right, there's no problem with the proof,
>only with sloppy versions of it. If a number has two decimal
>expansions there are a lot of 0's in one of the expansions -
>we arrange so that the new digit sequence contains no 0's
>and then the fact that it's a sequence of digits not on
>the list implies that it's a real not on the list, since
>it has only one decimal expansion.
*> The problem with doing
>the same thing in binary notation is that there are
>fewer digits to choose from, so we _can't_ arrange that
>there are no 0's in the new digit sequence (or at least
>not as obviously as in base ten.)*
>
>David C. Ullrich
I disagree about **.
Cantor's diagonalization on reals 'assumes' a '^'complete'^' list of
the reals, except that at the time when Cantor conceived his 'slot-machine'
there were no idea about recursiveness, computability, generability.
Indeed reals can 'equivalently' be generated (for the computability
theory a generable set is equivalent to an enumerable set and to
a semi-recursive set) by binary and by decimals code and
the fact "there are no 0's in the new digit sequence" absolutely does not
depend on there are fewer digits to choose from. On the contrary it
depends on the semi-recursive method of generating '^'all'^' the digits.
Let me show how, by means of the decimals (for binary see Nico Benshop method).
Let us recall here the classical Cantor's argumentation on R (the slot-machine).
1 <--> |0,1| 1 1 1 1 .....
2 <--> 0,3 |0| 1 0 2 .....
3 <--> 0,4 7 |7| 1 2 .....
4 <--> 0,6 0 2 |0| 5 .....
5 <--> 0,6 9 8 9 |7| .....
. .
. .
. .
----------------------------------
0,9 1 1 1 1 .....
Supposing there were an enumeration of '^'all'^' the real
numbers there would be a one-one correspondence with the
naturals. It is always possible to construct a new decimal
which defines a real number not included in the list. From
the digits along the diagonal of this array we construct a
new real number between 0 and 1 writing as the first decimal
a 9 if the first digit is 1 otherwise we write 1. We do the
same for the second digit and so on. Thus the written real
number differs from '^'all'^' the real numbers included in the
list in at least one decimal place. This contradicts our
supposition that the enumeration included '^' all'^' real numbers.
QED---
Let us show now how '^'all'^' the decimal can be generated
(i.e. semi-recursively given, i. e. enumerated). There is
a very simple way to do that: let it be a procedure which takes
in input the set {0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,........}
and which gives in output the following generated subsets.
Step 0
1 |emptyset|
Step 1
2 |0|
Step 2
3 0, |1|
4 |01|
Step 3
5 0,1, |2|
6 01, |02|
7 |12|
8 |012|
Step 4
9 0,1,2, |3|
10 01,02, |03|
11 12, |13|
12 |23|
13 012, |013|
14 |023|
15 |123|
16 |0123|
Step 5
17 0,1,2,3, |4|
18 01,02,03, |04|
19 12,13, |14|
20 23, |24|
21 |34|
22 012,013, |014|
23 023, |024|
24 |034|
25 123, |124|
26 |134|
27 |234|
28 0123, |0124|
29 |0134|
30 |0234|
31 |1234|
32 |01234|
Step 6
33 0,1,2,3,4, |5|
34 01,02,03,04, |05|
35 12,13,14, |15|
36 23,24, |25|
37 34, |35|
38 |45|
39 012,013,014, |015|
40 023,024, |025|
41 034, |035|
42 |045|
43 123,124, |125|
44 134, |135|
45 |145|
46 234, |235|
47 |245|
48 |345|
49 0123,0124, |0125|
50 0134, |0135|
51 |0145|
52 0234, |0235|
53 |0245|
54 |0345|
55 1234, |1235|
56 |1245|
57 |1345|
58 |2345|
59 01234, |01235|
60 |01245|
61 |01345|
62 |02345|
63 |12345|
64 |012345|
Step 7
.
|
.
|
.
.
.
were the lists in brackets '|x_1 x_2 x_3 ...|' are the new generated lists.
Let us suppose that the above generated lists are lists of decimals and each
one of them is an abbreviation of 0, x_1 x_2 x_3 ... .
Since each new section expands of a digit the lists of decimals of the
preceding section, the above procedure is a construction of all the
combinations of decimals to infinity. It is easy to see that it blocks
the diagonalization. It is not possible to construct a real number that
differs from all 0, x_1 x_2 x_3 ... . If we try to
construct a new list of decimal writing 9 in the place of 1 ,
then the above process will *certainly* give a list with the digit 9 in
the same position. For example for the first 1, 9 will appear at
the Step 11 (not represented for reason of space).
The same holds for 1 otherwise, and for all the positions of the decimals.
---------QED-----------
I wont conclude saying that at the light of the more recent theory
of computability the Cantor 'assumption' of a '^'complete'^' list
of reals is given incorrectly, as its 'assumption' has in itself
a presumption of NO-ORDER (no-arrangement no-array no-ordinals).
Please observe that Cantor's diagonalization is the only reason
(theorem, see Cantor's theorem, cardinal(A)
Up to previous page:
March 2000 / Homepage / Paola Cattabriga