Re: Earliest example of an incomputable real

briggs_at_encompasserve.org
Date: 06/14/04 

Date: 14 Jun 2004 07:47:14 -0600

In article <566rc05bhc99vb9p8bbid4ru9tpgi87ifn@4ax.com>, David C. Ullrich <ullrich@math.okstate.edu> writes:
> On 14 Jun 2004 02:32:34 -0700, Ckwop@hotmail.com (Simon Johnson)
> wrote:
>
>>I'm trying to find the earliest example of an incomputable real used
>>in mathematics. The don't have to know at the time what exactly they
>>were using. I'm just looking for the earliest use.
>>
>>Can anyone think of one earlier than this:
>>
>>Remember Cantor's diagonal proof of the difference in size of the
>>reals and the integers? The hypothetical number constructed during the
>>proof, to complete the theorem, is incomputable.
>
> Well, no. There is no such number - the proof starts with an
> enumeration of the reals, and there's no such thing as that.

Of course, this is only true for the proof when it is structured as
a proof by contradiction --

        Suppose there is a complete enumeration of the reals
        Select one.
        Diagonalize and demonstrate contradiction
        Conclude that there is no such complete enumeration

We have a second grave issue as well. The supposed complete enumeration
is arbitrary. If there were a complete enumeration of the reals, then
all finite permutations of this enumeration would also be complete
enumerations. It trivial to show that not all of them would have the
same diagonal. So the supposed uncomputable number defined by the
diagonalization is not well defined -- if it existed at all, it would
be ambiguous.

If the proof is structured directly as a proof that all enumerations
are incomplete (and thus that no enumerations are complete) then
we have:

        Select an arbitrary enumeration of at least some reals
        Diagonalize and demonstrate that the enumeration is incomplete
        Conclude that all enumerations are incomplete

Here we have no problem with existence. There are enumerations of
subsets of the reals. But we still have the problem of ambiguity.
The diagonal number generated by the proof is arbitrary.

        John Briggs

Relevant Pages

  • Re: Earliest example of an incomputable real
    ... It contains a countable sequence of reals. ... The assumption that the enumeration contains all reals has no role ... to play in the diagonalization argument. ...
    (sci.math)
  • Re: Cardinality of Set of Computable Numbers?
    ... > the diagonal proof shows the rationals to be uncountable. ... diagonalization process would generated a rational number not in the ... is incomplete or the diagonal is not rational. ... When applied to an allegedly complete list of the reals in [0,1), the ...
    (comp.theory)
  • Re: Skolems Paradox and why is math the way it is?
    ... They can have theorems proved about them. ... you have to have some axioms. ... > reals that has no preimage. ... > between the reals is incomplete because our axioms made it so. ...
    (sci.math)
  • Re: Well Ordering the Reals
    ... > extended reals, of course, instead of the real numbers, or by ... point for the enumeration of the finite reals, if that makes you feel better. ... strings is always longer than it is wide. ... "uncountability" of the real numbers, and the impossibility of a well ordering, ...
    (sci.math)
  • Re: Request for Peer Review - Refutation of Cantor Theorem Conclusion
    ... that applied to set theory mean the same thing. ... iff there does not exist an enumeration of the set. ... "existence" in set theory is not obvious at all. ... all reals, although we know none for which it's true. ...
    (sci.logic)