Re: Construction of a real closure

["John Baez" <baez@math.ucr.edu>]

Peter Freyd writes:

>John writes:

>>  Briefly, while the existence of an algebraic closure of Q
>>  can be shown without choice, it uniqueness-up-to-isomorphism
>>  seems to require choice.  Also, while arithmetic operations
>>  in Qbar are computable, they seem to present interesting challenges.

>The need for choice could hardly arise when working with a decidable
>countable structure such as  Q.

Above I was reporting what David Madore wrote.  He indeed claims
that in ZF without C one cannot prove the uniqueness of the algebraic
closure of Q.  He also said some other interesting stuff, so I might
as well quote it verbatim:

 From: david.madore@ens.fr (David Madore)
 Newsgroups: sci.math.research
 Subject: Re: The algebraic closure of the rationals
 Date: Fri, 7 Apr 2006 14:12:15 +0000 (UTC)
 Organization: Ecole Normale Superieure, Paris

John Baez in litteris <e13l06$sr9$1@glue.ucr.edu> scripsit:
> 1) Is there a way to enumerate the elements of Qbar such that
> relative to this enumeration, the field operations are computable?
> If so, how efficiently can they be computed?  If not, how far
> up the hierarchy of impossible-to-actually-compute functions do
> we have to go?

The usual manner is to represent a real element of Qbar by

* its minimal polynomial over Q (or perhaps, some polynomial, not
necessarily minimal, but probably at least separable, of which it is a
root),

* an interval which isolates the root from all other roots (or the
number of the root in the usual order on the reals).

Basically the trick is that sums and products can be computed by
universal rules (if P1 and P2 are polynomials over Q, there is a
polynomial, which can be given universally in function of the
coefficients of P1 and P2, whose roots are the sums of roots of P1 and
P2, and ditto for the product), and roots can always be isolated using
Sturm-Liouville (in other words, you can narrow the interval as much
as you want since Sturm-Liouville lets you count the number of roots
in any given interval).

This is for real algebraics; for the full Qbar, you just represent a
complex number by its real and imaginary parts (both of which are
algebraic if the complex is algebraic).

Actually programming this is *unbelievably* painful.  As for the
algorithmic complexity, I think it's not that bad, in the sense that
if x and y have small height (for any reasonable definition of
"height") then computing x+y can be done in a reasonable time, but
there's a catch: the height of x+y grows considerably larger than that
of x or y, so any actual computation can become terribly difficult.
(The same problem happens for rationals: computing r+s where r and s
are rationals is polynomial in the height of r and s, but try
computing something like 1/2+1/3+1/5+1/7+1/11+1/13+1/17...)

For some specific uses it is better to use the p-adics than the reals:
the advantage is that p-adic approximation is *much* easier than real
approximation (thanks to the ultrametric properties); the disadvantage
is that whereas the reals are "almost" algebraically closed, the
p-adics are quite far from it, and representing elements of the
algebraic closure of Q_p is again quite a nuisance.

> 2) On the other extreme: can we even prove the existence of Qbar
> without the axiom of choice, or perhaps countable choice?

Yes, the *existence* of Qbar, or of any countable or even
well-orderable field (and various others, such as Q_p), can be shown
without the axiom of choice.  However, the *uniqueness* of Qbar
requires the axiom of choice: it is consistent in ZF alone that there
exists an uncountable algebraic closure of Q.  (Basically it's true in
ZFA because you can create atoms for elements of Qbar and let Galois
act on them and take the usual permutation model, and then some
embedding theorem gives the result in ZF.)  I'm not sure about whether
one needs AC to show that the algebraic closure of Q constructed using
the reals and the p-adics as explained above actually give the same
thing.

> 3) I've heard that it's even hard to get an "explicit" description
> of the algebraic closures of finite fields - are there any
> theorems to this effect?

I don't think it's hard.  In fact, here's a very elegant and
intriguing explicit construction of the algebraic closure of F_2,
which is due to Conway:

Define two binary operations, '#' and '@', on the class of ordinals,
by transfinite induction, by letting:

  x # y  =  mex ( { x'#y | x'<x } union { x#y' | y'<y } )

  x @ y  =  mex { (x'@y)#(x'@y')#(x@y') | x'<x and y'<y }

(respectively called the "Nim sum" and "Nim product" by Conway).

Then:

* the operation '#' coincides with the "exclusive or" on the binary
representation of ordinals (= unique representation as decreasing sum
of distinct powers of 2),

* the operations '#' and '@' make various ordinals (such as omega,
omega^omega, epsilon_0, omega_1, and in fact a closed unbounded class
of ordinals, or even "the class of all ordinals") into a field of
characteristic 2, which for some well-known ordinal (I think it is
omega^(omega^omega) or omega^omega or epsilon_0 or some such thing -
you can find the correct version in Conway's "On Numbers and Games")
is exactly the algebraic closure of F_2.  (As for omega, i.e., the set
of natural numbers, it is the quadratic closure of F_2, this one I'm
sure about.  Somewhere far beyond that we get the algebraic closure of
F_2(t), which is a much nastier beast than that of F_2, but I think
nobody knows exactly which ordinal that is - possibly the
Feferman-Schuette ordinal.)

This is as explicit as you might wish: there are no choices to be
made, everything is well-defined.  It is not too computational,
however, because in principle to compute x@y for two ordinals x and y
you need to know x'@y' for every pair (x',y') with x'<=x and y'<=y and
(at least one not being equal): in fact, it's not that bad, and at
least up to omega the Nim product ('@') can be computed fairly
efficiently, I don't know what about higher ordinals but I suspect it
is reasonalby well-behaved at least as far as defining the algebraic
closure of F_2 goes.

I hope this answers your question.

-- 
     David A. Madore
    (david.madore@ens.fr,
     http://www.dma.ens.fr/~madore/ )