Proof that the reals are not countable
Dick Batchelor
I would like to raise some questions about the proof that I was
given as an undergraduate that the real numbers are not countable. This
(usually called Cantor's diagonalization proof) is roughly:-
Suppose the real numbers are countable. Then they can all be written
in a single list. We now generate a new number not in the list thus
contradicting the premise that all real numbers are in the list. Each
number in the list has a decimal representation. Generate the new number
by writing a '4' for the n th digit if the n th digit of the b th number
in the list is not '4' and '3' otherwise. The new number is not in the
list since it differs from the n th number in the n th digit. Thus it
is not possible to produce such a list and so the totality of real
numbers is not countable.
T think that this argument has several flaws. (please note, I don't
dispute the conclusion that the reals are not countable, only the
validity of this particular 'proof'.)
A real number is defined by a Dedekind section that divides the rationals
into U and L classes. Each real number thus depends on an algorithm
to divide the rationals: one can think of it as the condition that the
number satisfies. Each of these algorithms can be defined; if you want
to be really precise, define it as a Turing machine. All these algorithms
can be ordered; by length and alphabetically among algorithms of the
same length.
The procedure given above for computing the new number is an algorithm
like this. It therefore has a position in the list say N. What is its
N th digit? If its '3' it must be '4' and if it's '4' it must be '3'!
The most obvious solution to the dilema is to say that the procedure is
not a valid one to apply to this set. However, if it isn't a valid
algorithm it can't be used to generate a number not in the list.
Let me put this argument another way. Cantor's procedure is a way to
compute a number. The number it generates must be a 'computable number.'
However, the set of computable numbers is countable, and so if we apply
Cantor's procedure to the set of all computable numbers we get a paradox:
the number must be in the list because it it computable but cannot be in
the n th position for any n since it differs from it in the n th digit.
Dick Batchelor
Neil Rickert
>
>I would like to raise some questions about the proof that I was
>given as an undergraduate that the real numbers are not countable. This
>(usually called Cantor's diagonalization proof) is roughly:-
>T think that this argument has several flaws. (please note, I don't
>dispute the conclusion that the reals are not countable, only the
>validity of this particular 'proof'.)
I believe you are missing the point. The usual definition of "countable"
requires that the numbers must be arrangeable in such a sequence. You
are confusing intuitive ideas of countability with the formal definition.
There might well be different models of the number systems such that
the reals in one model are countable in the other model.
>Let me put this argument another way. Cantor's procedure is a way to
>compute a number. The number it generates must be a 'computable number.'
>However, the set of computable numbers is countable, and so if we apply
>Cantor's procedure to the set of all computable numbers we get a paradox:
>the number must be in the list because it it computable but cannot be in
>the n th position for any n since it differs from it in the n th digit.
Sorry, but you lose on this one. The diagonal number would not be
computable unless you have a computable procedure for generating the list,
which must find a given diagonal element in a finite number of steps.
If your argument is just that Cantor's procedure is not computable, since
it relies on the axiom of choice, this is well known.
--
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
Neil W. Rickert, Computer Science <ric...@cs.niu.edu>
Northern Illinois Univ.
DeKalb, IL 60115 +1-815-753-6940
Mark E. Shoulson
>
>given as an undergraduate that the real numbers are not countable. This
>(usually called Cantor's diagonalization proof) is roughly:-
>T think that this argument has several flaws. (please note, I don't
>dispute the conclusion that the reals are not countable, only the
>validity of this particular 'proof'.)
>
>A real number is defined by a Dedekind section that divides the rationals
>into U and L classes. Each real number thus depends on an algorithm
>to divide the rationals: one can think of it as the condition that the
>number satisfies. Each of these algorithms can be defined; if you want
>to be really precise, define it as a Turing machine. All these algorithms
>can be ordered; by length and alphabetically among algorithms of the
>same length.
I think here is where you flaw has its flaw. Once you determine that each
number must be determinable and computable, you have limited your list of
numbers to the computable numbers, which as you pointed out, are countable.
It is true that every real number (by Dedekind's definition) divides the
set of rationals, but to say that each such division is Turing-computable
is the same as saying that the set of reals equals the set of computables,
which makes your argument circular. I mean, some real numbers aren't
Turing computable, as they require infinitely many steps to compute or
otherwise break the rules of Turing machines.
>
>The procedure given above for computing the new number is an algorithm
>like this. It therefore has a position in the list say N. What is its
>N th digit? If its '3' it must be '4' and if it's '4' it must be '3'!
>
>The most obvious solution to the dilema is to say that the procedure is
>not a valid one to apply to this set. However, if it isn't a valid
>algorithm it can't be used to generate a number not in the list.
>
No, the procedure is valid, it's the set that's not complete.
Basically, you wind up proving that if the set of computable numbers is
countable, then it's countable. Leastways, that's what it looks like to
me.
Did I miss anything? How silly do I sound?
~mark
o o o o o o o o o o o o
o o o o o o o
o o o o o o o o o o o N2KOT
Mark E. Shoulson: shou...@ctr.columbia.edu
John Merrill
There are, in fact, only countably many computable reals. Your
paradox arises from the fact that even though there is a canonical
listing of turing machines which lists all such (reals), there's an
important subtlety: not all of the computations in this list converge
everywhere. This leads to an escape from the paradox you propose.
Let us take the rule which computes the "Cantor computable rule."
It's got an index in the list---say 17. Aha! we say, let's go look at
the 17th digit of the seventeenth element. We turn the computer on,
sit down with a pizza, and wait for the machine to finish.
We finish the pizza, and it's still not done. So we order another
pizza, finish *it*...and the computation still isn't finished. In
fact, we would wait forever and still never find out what happens.
The process described does not ever complete; it's an infinite
regress:
compute the seventeenth digit of r_17,
compute the seventeenth digit of r_17,
compute the seventeenth digit of r_17,
.
.
.
take its complement
take its complement
take its complement
But the tower is infinitely deep, and we never start to pop the stack.
So the paradox is resolved by virtue of the fact the there is no value
to complement.
In fact, this is a sketch of the proof of a famous lemma of Kleene's
(and, yes, I know that I'm invoking Church's thesis in this statement,
so don't send me mail telling me so):
Lemma: If L is any computable function from NxN to N which contains
the graphs of all total computable functions from N to N as sections,
then L is not total: there is some pair (n, m) on which the
computation which defines L does not converge.
One obvious corollary of this statement is the Second Incompleteness
Theorem, which is why this is such an important lemma. In fact, this
is the first proof of the SIT that I ever learned; the more standard
proof never really made sense to me until after I understood this one.
--- John
--
John Merrill / mer...@cns.bu.edu / harvard!bu.edu!cns!merrill
Michael Weiss
You have not discovered a flaw in Cantor's diagonal argument, but you are
halfway to discovering the modification of Cantor's diagonal argument that
yields a number of classic results in computability theory and mathematical
logic. Goedel, Turing, Church and Kleene all played a role in exploring
this new territory in the '30s and '40s; I remember reading somewhere that
Kleene was at one point puzzled by essentially the same point you bring up
(except in the context of Church's lambda-calculus), and found the
resolution of the paradox one of the most satisfying discoveries of his
career.
By the way, Cantor's diagonal argument does not depend on the axiom of
choice, despite what one of the replies to your post stated.
I think it's easier to explore these topics with decimal sequences, rather
than Dedekind sections (granted we can easily associate a Dedekind section
with each decimal sequence in some standardized way.) I'm also going to
ignore the whole .10000... = .099999... problem, because it's an annoyance
that has nothing to do with the fundamental mathematics involved. Let's
just say we're interested in the set of all infinite sequences of decimal digits, so
that (1,0,0,...) and (0,9,9,...) are distinct.
Consider two sets:
S: the set of all infinite decimal sequences.
S-comp: the set of all computable infinite decimal sequences; that
is, for each sequence in this set, there must be an
algorithm that produces the successive digits.
If we have a sequence of elements of S, say P1, P2, ..., then Cantor's
argument shows how to construct a sequence Q of digits (i.e., Q is an
element of S) such that Q is not equal to any of the P's. Hence S is not
countable.
The puzzle you bring up arises from trying to apply the same argument to
S-comp. S-comp is clearly countable. Applying the diagonal argument to
S-comp yields a sequence Q that is not in S-comp. On the other hand, it
would seem that we have an algorithm for computing the successive digits of
Q, as you point out. Doesn't this mean that Q is in S-comp?
To resolve the paradox, we have to look more closely at how the listing of
all algorithms yields a listing of all elements of S-comp. As you note, we
can list Turing programs in order of length, and alphabetically within a
given length.
The problem is, not all programs give algorithms that specify an infinite
sequence of digits. A program may get into an infinite loop computing,
say, the 777-th digit, and never produce any digits after that. Call this
a "bad" program.
There is no computable way of eliminating the bad programs-- that is, there
is no algorithm for determining which programs are bad. If there were,
then Q would indeed be a computable sequence, and we would have a real
contradiction on our hands! This is the nugget that comes from your
puzzle.
Variations on this theme yield:
the undecidability of the halting problem
Kleene's second recursion theorem
Tarski's theorem on the undefinability of truth
Goedel's incompleteness theorem
and much more. See, for example, "Goedel, Escher, Bach", by Douglas
Hofstadter, "Theory of Recursive Functions", by Hartley Rogers, and any
book on mathematical logic.
I should note that the above discussion is the version accepted by most
mathematicians today, i.e., anyone whose philosophy of mathematics is
Platonist, formalist, or
I-don't-worry-about-these-things-I-just-prove-theorems. I don't know what
the intuitionist position on these matters is.
A quote from, I believe, Andre Weil:
We know God exists, because Mathematics is consistent; we know the
Devil exists, because we cannot prove it.
I don't know the source for this quote:
Kleeneness is next to Godelness.
rsilv...@eagle.wesleyan.edu
colu...@strident.dev.think.com (Michael Weiss) writes:
> ...
> The puzzle you bring up arises from trying to apply the same argument to
> S-comp. S-comp is clearly countable. Applying the diagonal argument to
> S-comp yields a sequence Q that is not in S-comp. On the other hand, it
> would seem that we have an algorithm for computing the successive digits of
> Q, as you point out. Doesn't this mean that Q is in S-comp?
>
> To resolve the paradox, we have to look more closely at how the listing of
> all algorithms yields a listing of all elements of S-comp. As you note, we
> can list Turing programs in order of length, and alphabetically within a
> given length.
>
I don't quite follow you here. You define S-comp to be the set of computable
decimal sequences. I interpret this to mean that for every sequence s in
S-comp, there is an algorithm A which generates the sequence, i.e., A will
produce any given finite initial segment of s within finite time. This
certainly guarantees that S-comp is countable, since the set of all algorithms
is countable and S is in 1-1 correspondence with a subset of this set - but
just that: a subset. I don't see why you pass to talking about a listing of
all algorithms. And by definition, the algorithms generating members of
S-comp do not have the infinite loop problem you go on to mention; otherwise,
how can they be said to "generate" a member?
I would say that the real flaw in this argument is just in the phrase "... it
would seem that we have an algorithm for computing the successive digits of Q,
..". I assume the suggested algorithm is
i := 0;
loop
compute the i-th digit of sequence i;
change this digit and output it;
i := i + 1;
end loop;
But this "algorithm" references all the (infinite number of) algorithms of
S-comp in the line "compute the i-th digit...". Thus it is in fact itself
infinite, that is, not an algorithm at all. So this argument does not show Q
to be computable.
- Richard
c...@ifi.unizh.ch
>
>given as an undergraduate that the real numbers are not countable. This
>(usually called Cantor's diagonalization proof) is roughly:-
>T think that this argument has several flaws. (please note, I don't
>dispute the conclusion that the reals are not countable, only the
>validity of this particular 'proof'.)
>
>A real number is defined by a Dedekind section that divides the rationals
>into U and L classes. Each real number thus depends on an algorithm
>to divide the rationals: one can think of it as the condition that the
>number satisfies. Each of these algorithms can be defined; if you want
>to be really precise, define it as a Turing machine. All these algorithms
>can be ordered; by length and alphabetically among algorithms of the
>same length.
>
To my opinion your argument is wrong and Cantor is right:
Not every real number depends on an algorithm in the Turing sense.
There are computable real numbers, which may be defined as follows:
A real number R is computable, iff there exists a Turing machine
which enumerates the decimal notation of R.
I will give an example of a non-computable real number N:
Lets order all Turing machines: T_1, T_2, T_3, etc. Then define
N as the real number with decimal representation
0.{a_1}{a_2}{a_3}{a_4} ....
where a_i is equal to 0 iff T_i halts and equal to 1 iff T_i does
not halt. If N were a computable real number in any reasonable
sense, then the halting problem could be solved.
The fact, that the decimal representation of the reals is not a
unique one (think of 0.999999999.... = 1.00000000 ) and is not
the preferred approach to the reals for a rigorous view does not
threaten my argument but just makes it more easy to write down.
--
* Dr. Clemens H. CAP c...@ifi.unizh.ch Phone +01 257-4326
* Dept. of Computer Science University of Zurich Winterthurerstr. 190
* CH-8057 Zurich, Switzerland #include<disclaimer.h> #exclude <flames.h>
fc...@ns1.cc.lehigh.edu
>Date: 3 Jan 92 15:54:34 GMT
>Organization: University of Zurich, Department of Computer Science
>
>In article <1992Jan2.1...@granite.ma30.bull.com> batc...@granite.ma30.bull.com (Dick Batchelor) writes:
>>
>>I would like to raise some questions about the proof that I was
>>given as an undergraduate that the real numbers are not countable. This
>>(usually called Cantor's diagonalization proof) is roughly:-
>
>[...]
>
>The fact, that the decimal representation of the reals is not a
>unique one (think of 0.999999999.... = 1.00000000 ) and is not
>the preferred approach to the reals for a rigorous view does not
>threaten my argument but just makes it more easy to write down.
At the risk of reinstigating the 0.999999... = 1 thread, I will point out that
every real number has a UNIQUE NON-TERMINATING decimal representation (or
binary representation, for that matter). A proof which takes this into
account is as rigorous as any other.
//////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
| Frederick W. Chapman | Campus Phone: 8-3218 | Junior Adult Men's |
| User Services Group | fc...@ns1.cc.lehigh.edu | Free-Skating Bronze |
| Computing Center | -.-. --.- -.. . | Medalist, Mid-Atlantic |
| Lehigh University | N3IJC (2m band, FM voice) | Competition, 1991! |
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\//////////////////////////////////////
fc...@ns1.cc.lehigh.edu
>From: fc...@ns1.cc.lehigh.edu
>Date: Sat, 04 Jan 1992 05:31:04 GMT
>Organization: Lehigh University
>
>At the risk of reinstigating the 0.999999... = 1 thread, I will point out that
>every real number has a UNIQUE NON-TERMINATING decimal representation (or
>binary representation, for that matter). A proof which takes this into
>account is as rigorous as any other.
It has been pointed out to me that my usage of the word "non-terminating"
here may possibly cause more confusion than illumination. To prevent any
possible misunderstandings, let me add the following explanation...
Definition:
A decimal representation for a real number will be called TERMINATING if
it contains a finite number of non-zero digits, and NON-TERMINATING
otherwise.
Here are some illustrative examples:
1.000.... contains 1 non-zero digit and is therefore TERMINATING.
0.999.... contains an infinite number of non-zero digits and is
therefore NON-TERMINATING.
0.5000.... is TERMINATING.
0.4999.... is NON-TERMINATING.
I offer my sincere thanks to Neil W. Rickert for drawing my attention to
this potential source of confusion.
Fred Chapman