Re: Why are reals uncountable yet algorithms countable (long)?

From: Ray Whitmer (ray_at_xmission.com)
Date: 11/15/04 

Date: Mon, 15 Nov 2004 07:16:38 -0700

On Sun, 14 Nov 2004 22:08:08 +0100, Hibernatus wrote:

>
> "Ray Whitmer" <ray@xmission.com> a écrit dans le message de news:
> cn85rn$ecb$1@news.xmission.com...
>
>> [quoted text muted]
>
> There's a point that has to be settled before trying to understand how
> "diagonalisation" works, and that is "Do we agree about the meaning of the
> words 'real number' ?". Most people trying to prove on s.m. that Cantor
> was wrong obviously think that a number is just a finite or infinite
> sequence of digital figures. Then they argue (and they are right) that
> only those with a finite decimal expansion can actually be "produced",
> that they can list all these numbers, and hence that there are as much
> real numbers as integers.

I believe I have not taken that approach. I only disputed whether it was
possible to generate an infinite sequence such that it had one digit
different from all other reals, because that number is a real itself:
Regardless of whether you try to do this by means of counting.

> The classical reply is to ask "what about 1/3", "what about 1/9", and so
> on, since all these numbers have no finite decimal expansion and will be
> missed by any algorithm like those you consider. But if you change your
> system, using basis 3 instead of basis 10, 1/3 and 1/9 will show up in
> your algorithm's output (since 1/3 = 0.1 and 1/9 = 0.01 in basis 3), while
> 1/2 (decimal 0.5), 1/4 (decimal 0.25), 1/5 (decimal 0.2) will not ! 1/2 =
> 0.111111...., 1/4 = 0.0202020202... and 1/5 = 0.012101210121....

Again, this does not answer my argument. My argument was that since
algorithms are countable (because Turing machines are, or for my
convenience, I might model a PDP-11 or Java VM with unlimited memory (but
finite programs in each case), the states of which seem to be clearly
countable), I think there are algorithms that produce the digital
sequences of all reals you can describe, and these algorithms are
countable.

> So, there's no hope in defining "real numbers" in terms of decimal
> expansion, or expansion in any basis. Even setting "a real number is
> something that has a finite expansion in *some* basis" will give you
> nothing more than the set of rational numbers.

I think I included all infinite sequences you can describe by counting
algorithms, which was the subject line of the question. If I discard
all but programs producing the digits, either finite or infinite, of
reals, then I can count all the reals I can produce with such a machine
by counting the algorithms which produce them, which I believe includes,
in a single counting scheme, all the reals you can possibly describe.

> Let's look back at the original problem. Why do we have to define real
> numbers ? Because the greeks noticed that the dioganal's length in a
> side-1 square, which is sqrt(2), is *not* a rational number. Same problem
> with the circumference of a radius-1 circle, pi. We cannot brutally decide
> that the square' diagonal is of an other kind as its edges are, so we have
> to find a definition of numbers that includes these, the rationals, the
> integers.
>
> The basic idea of the most commonly used constructions of real numbers is
> the following : while sqrt(2), sqrt(3), pi, ... are *not* rational, it is
> possible to find rational numbers arbitrarily close to them. Digital
> expansion is a good illustration of this : sqrt(2) is neither equal to 1,
> nor to 1.4, nor to 1.41, but each of these rationals comes closer to
> sqrt(2) then the preceeding one does. Hence the idea of limit and of
> *infinite* decimal expansion. But we have to accept that some numbers have
> an infinite expansion and that does not keep them from "existing" nor from
> being taken into account.

I am not sure whether to quote this or not, because it seems unrelated to
any argument I made, but I may have missed the connection.

> Back to Cantor : he assumes he is able to list all real numbers. Then,
> using his diagonal method, defines a number that cannot be in the list
> (for each number in the list, they differ at one decimal place at least).
> Hence the real numbers are not countable.

But the contradicting number seems to be self-referential,
self-contradicting, by saying that, by definition, some digit of the
number has to be unequal to itself, since it is a member of the reals.
This seems like a clever proof.

> There's actually no hope in finding an algorithm that could produce *any*
> real number in finite time, and that's what Cantor's diagonal proof is all
> about !

If you are talking about producing the digits of the real number in finite
time, then that is even true of the rational number 1 with repeating 0,s
or 1/3 with repeating 3's. I see no reason to believe that producing all
of the infinite digits in real time should be a requirement of the
algorithm. That is even true of integers -- you can never produce all the
trailing 0's of the numbers as reals -- even though they are clearly
countable.

I believe it is sufficient to have an algorithm in my countable set that
can be proven to produce the digits in infinite time, because at that
point, we have uniquely counted the real number and can move on to the
next one.

I believe a counterexample would be a simple way to refute my notion: some
real that is unambiguously described without self-contradiction that
cannot be produced by these general-purpos computers, whose finite
programs are countable.

Cantor's counter-example seems to me to fail, because it seems to be
self-contradicting and is therefore not a real number if the countable
numbers contain them all. In machine terms, it means you reach a certain
state (the algorithm itself) and the result of the algorithm is undefined
because it is required to contradict itself.

Ray Whitmer
ray@xmission.com

Relevant Pages

  • Re: Cantor and the binary tree
    ... >>>List all the infinite binary sequences with a bijection to the integers. ... to be referring to the "proof" of uncountability of the reals. ... By traversing the list diagonally ... the sense that there are as many digits in each number as numbers in the list. ...
    (sci.math)
  • Re: Dial 999 for the real number line
    ... length n as initial strings followed by the expansion of pi after the nth ... long decimal expansion followed by an infinite expansion. ... for producing successive digits of pi without end. ... There are no other reals at the end of or besides this list. ...
    (sci.math)
  • Re: 10 Questions Concerning Numbers
    ... I only asked whether one can obtain from an infinite sequence, ... If two infinite strings (using "infinite" in the same sense as in decimal ... digits d_1, ..., d_n which is shared by infinitely many different ... Not in Reals, no. ...
    (sci.logic)
  • Re: On Well-Ordering(s) and Sets Dense in the Reals, Infinity
    ... > If the reals are well-orderable, then I have some considerations of how ... something different in the finite scope doesn't mean that at infinite ... algorithm does exist to handle all those cases? ... thereby you could obtain a well-ordering by lexically ordering ...
    (sci.math)
  • Re: On Well-Ordering(s) and Sets Dense in the Reals, Infinity
    ... > If the reals are well-orderable, then I have some considerations of how ... something different in the finite scope doesn't mean that at infinite ... algorithm does exist to handle all those cases? ... thereby you could obtain a well-ordering by lexically ordering ...
    (sci.logic)