FOM: Precision and Turing-computability

[Insall]

I had to work out an attempted proof to see why you say the computable reals
do not form an ``effective field''.  First, I had to figure out what you
meant by ``effective field''.  I looked everywhere for a definition, then I
looked back at your recent posting, and saw that you said you mean that
equality in the computable reals is not decidable.  After trying to prove
that it was, I saw why you made that claim, and I now agree that it in the
computable reals, it is likely that one can be given an algorithm for
computing the individual digits of a specific real number r, but not have an
algorithm for that particular real number that decides whether it is
nonzero.  However, I still do not see that this answers my question about
``the real numbers of classical analysis''.  You seem to believe that those
real numbers form an effective field, and you base this on Lang's Intro to
Transcental Numbers.  I do not have his book, but I can take your word for
it that he says what you stated.  I am not sure that I would agree with Lang
on that point either, but in any case, I will here argue that even the real
numbers of which Lang speaks do not form an effective field.

To this end, let me make more precise what I understand (you? and) Lang to
mean by ``the numbers of classical analysis''.  (I would prefer to be even
more precise than I will be here, but in the interest of brevity, I shall
cut to the chase.):



Definition:  Let z be a complex number, and let p(n,w) be a formula in the
language of fields, of characteristic zero, with exponentiation and
logarithm.  We say that p(n,w) computes z provided that the following hold:

1.  For each nonnegative integer, n, the set of all complex numbers w, such
that p(n,w) holds for w, is provably a nonempty subset of the set of
algebraic numbers.

2.  The complex number z is the only ``limit'' of the sets generated in 1.,
in the following sense:  Given a positive integer m, there is an effectively
obtainable nonnegative integer N such that if n>N, then for each algebraic
number w such that p(n,w) holds, the euclidean distance, in the complex
plane, between w and z, is provably smaller than 1/m.

(As is done in analysis, if you have a problem believing that it is
appropriate to even recognize the existence of z prior to the statement of
this definition, one may replace 2. above with a Cauchy type of condition,
and then postulate a type of completeness relative to that, namely that all
``nice'' Cauchy sequences converge.)

Now, we say that a complex number z is a number of classical analysis if
there is a formula of the form p(n,w) in the language of fields of
characteristic zero that computes z.


Proposition:  Every computable (complex) number is a number of classical
analysis.

Proof:
     We show that every computable real number is a number of classical
analysis.  Thus, wolog, let r be such a real number in the open interval
(0,1), and let R be an algorithm that computes the digits of r.  Denote
these digits by r_1, r_2, ...  For each nonnegative real number n, let S_n
denote the set of all algebraic numbers that agree in the first n decimal
digits with r.  Then each set S_n is easily seen to be definable by a
formula in the appropriate language, but even better, because of the
existence of the algorithm R, we can find a single formula p(n,s) with two
parameters, such that the algebraic number s is in the set S_n if and only
if p(n,s) holds.  Clearly, in the topology of the algebraic real numbers,
the diameters of the sets S_n form a descending Cauchy sequence whose
infimum is zero, so that r is computed by the formula p(n,s).  Once we can
compute with a formula of the specified type any computable real in the open
interval (0,1), it then follows that we can compute any computable number
with the same type of formula.  Hence the proposition holds.

QED


Now, if there is a hole in that argument, I do not see it at the moment.
Perhaps you can point it out to me, if there is a problem with it.  Of
course, my claim then follows, so long as you still agree with your own
claim that the computable numbers do not form an effective field.

Now, if you agree that my proof is solid, but you disagree with my
definition, then I would like to know what I have erroneously assumed about
Lang's concept of a ``number of classical analysis''.  Let me caution you,
though, that if you deny that limits are allowed, then you have eliminated
the ``analysis'' from it, and you are merely discussing a form of universal
algebra, or an extremely mild generalization thereof, and that is not what
any serious mathematician I know of means by ``classical analysis''.

Don't get me wrong.  I like universal algbera.  (In fact, my dissertation
dealt with that subject.)  But it is not exactly the same as classical
analysis, because universal algebra involves finitary operations, and
usually, papers in that area of mathematics are concerned essentially only
with finitely many finitary operations.  Many people working in that area
work only with finite algebras.  When some analysis does actually creep in,
it is not in as limited a form as you seem to think is tying the hands of
analysts, just because of a quote from Lang's book.  I guess it is possible
that Lang meant that limits could not be used to generate ``the numbers of
classical analysis'', but to an analyst, I would expect the idea of not
being able to compute serious limits would be perverse.


Matt Insall