Dear Michael,

Is there a reference for the fact that a countable decidably ordered field has a constructable (and decidably ordered) real closure?

In my paper "Sheaves and Prime Model Extensions", J. of Algebra 68 (1981) 79-96, there is a proof of the existence of the real closure of an ordered field in any elementary topos, plus considerations about the failure of the existence of the algebraic closure. The context is more general (model theory in toposes), and there are other instances which I do not recall offhand. Maybe that is not what you are asking? I thought that I would mention it, just in case. Best, Marta

I don't think this is what I was asking, although it may be related. Certainly, the context I have is one in which if you have a real closure and adjoin i, you get an algebraic closure. And the real closure is unique because it is the usual real closure. In fact, the usual real closure is used to prove some things. As I said, the construction is constructive; the proofs are classical. Let me give an example of the flavor. Suppose you want to have a square root of a > 0. It is decidable (by hypothesis) if a > 0; what may not be decidable is whether a has a square root. What the student did (he credits Joyal with some of the main ideas, BTW, and this may be one of them) was to form F[x]/I where I is the ideal of all polynomials that vanish at sqrt(a). Even though it may not be decidable if sqrt(a) in F, it is still decidable if a polynomial vanishes there. First use Sturm's criterion to find an interval that contains exactly one root of f(x) = x^2 - a (in a real closure) and then for any polynomial g, g is in I iff gcd(f,g) has a root in that interval, again using Sturm's criterion. Clearly, F[x]/I contains a square root of a, even if it is not decidable whether that field is F. Michael On Thu, 4 May 2006, Marta Bunge wrote:

Dear Michael,

...

Is there a reference for the fact that a countable decidably ordered field has a constructable (and decidably ordered) real closure?

In my paper "Sheaves and Prime Model Extensions", J. of Algebra 68 (1981) 79-96, there is a proof of the existence of the real closure of an ordered field in any elementary topos, plus considerations about the failure of the existence of the algebraic closure. The context is more general (model theory in toposes), and there are other instances which I do not recall offhand. Maybe that is not what you are asking? I thought that I would mention it, just in case.

Best, Marta

Dear Mike: One reference is the work of M-F Coste-Roy and H. Lombardi in Real Algebraic Geometry; a quick Google search yielded: http://hlombardi.free.fr/publis/AMega90-1.html Also they have some papers in the J.ACM, apparently. In fact, it seems to be a huge area of model theory: see http://name.math.univ-rennes1.fr/michel.coste/Borel/w1abs.html Cheers, Phil On Thu, 4 May 2006, Michael Barr wrote:

Is there a reference for the fact that a countable decidably ordered field has a constructable (and decidably ordered) real closure?

Maybe 20 years ago, an undergraduate did a project under my supervision proving exactly that (although the proofs are not constructive). While I don't think it would prove feasible for actual computation, the fact that it exists is interesting. Finally, I have looked more closely at it and if it is not known, I think it publishable. Unfortunately, the student (who was a Commonwealth Fellow at Cambridge) lost interest in math and is doing other things. But I think I know how to get in touch with him.

Michael

Yes, that seems exactly the sort of thing I was asking about. Michael On Thu, 4 May 2006, Phil Scott wrote:

Dear Mike: One reference is the work of M-F Coste-Roy and H. Lombardi in Real Algebraic Geometry; a quick Google search yielded:

http://hlombardi.free.fr/publis/AMega90-1.html

Also they have some papers in the J.ACM, apparently.

In fact, it seems to be a huge area of model theory: see http://name.math.univ-rennes1.fr/michel.coste/Borel/w1abs.html

Cheers, Phil

Dear Michael, It is related to what I did, but in a different way. BTW, I remembered something incorrectly. In my J. Alg '81 paper, I actually use (not prove) Joyal's result on the existence of the real closure of an ordered field ("Cloture algebrique reelle d'un corps ordonne", Lecture, Universite de Montreal, January 1979). The proof is indeed classical, so this holds (at least) in any topos which is a BVMST (Boolean-valued-model of Set Theory), not in every topos. I show that for certain toposes E, the result is till true. I was mostly interested in toposes E which arise in sheaf represenation theorems for algebraic structures (such as von Neuman regular (differential) rings). First, I prove a general theorem for quotients T-->T* of coherent theories satisfying (what I call) the "Sturm property" in a topos E, to the effect that prime model extensions of Mod_{E}(T) in Mod_{E}(T*) exist and are preserved by continuous functors. For instance, I show that the real closure exists in toposes E = Sh_fc(B) (sheaves for finite covers in a Boolean algebra B). The example of T--->T* with T = {ordered fields} and T* = {real closed fields} is shown to have the Sturm property in E = Sh_{fc}(B) by resorting to a "mid-way-house method", first via the Gleason cover of E, and then taking its topos of double negation sheaves, which is a BVMST. By transfer, I obtain that every commutative regular f-ring (in Sets) has an (invariant, and an atomless) real closure. Another example is that of the differential closure of a differential field and a transfer to differential Von Neuman regular rings of non-zero characteristic. The question of characterizing toposes E for which a certain quotient T-->T* of coherent theories has the "Sturm property" is open. As I said, I was only interested in sheaf representations by global sections, so I only looked at such toposes. Best, Marta

I don't think this is what I was asking, although it may be related. Certainly, the context I have is one in which if you have a real closure and adjoin i, you get an algebraic closure. And the real closure is unique because it is the usual real closure. In fact, the usual real closure is used to prove some things. As I said, the construction is constructive; the proofs are classical.

Let me give an example of the flavor. Suppose you want to have a square root of a > 0. It is decidable (by hypothesis) if a > 0; what may not be decidable is whether a has a square root. What the student did (he credits Joyal with some of the main ideas, BTW, and this may be one of them) was to form F[x]/I where I is the ideal of all polynomials that vanish at sqrt(a). Even though it may not be decidable if sqrt(a) in F, it is still decidable if a polynomial vanishes there. First use Sturm's criterion to find an interval that contains exactly one root of f(x) = x^2 - a (in a real closure) and then for any polynomial g, g is in I iff gcd(f,g) has a root in that interval, again using Sturm's criterion. Clearly, F[x]/I contains a square root of a, even if it is not decidable whether that field is F.

Michael

Mike asks: Is there a reference for the fact that a countable decidably ordered field has a constructable (and decidably ordered) real closure? The expert on all such questions is Anil Nerode .See his Effective content of field theory (Ann. Math. Logic 17 (1979), no. 3, 289--320) for a collection of all the relevant results. 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. One way of naming an algebraic real number is with an ordered triple <l, P, r>, where l and r are rationals, P a monic polynomial with rational coeficients that is irreducible over the rationals (the decidablity of which can be found in van der Waerden) such that P(l)P(r) < 0 and R(l)R(r) > 0 for R any of the non-tivial iterated derivatives of P. Another such triple names the same element iff the polynomials are the same and the intervals overlap. Effective constructions for the ordered-field operations in this context are pretty standard.

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/ )

If memory serves me, Nerode proved years ago that the necessary and sufficient condition that all the algebraic closures of a field are effectively isomorphic is that its polynomials effectively factor into irreducibles. As for the later, the ancient theorem is that if a unique factorization domain has only finitely many units and if the factorization is effective then so it is for its polynomial ring. The condition on units pretty much forces the proof.

Hi! In 1978 Joyal gave a lecture in Montreal where he described a constructive construction of the pithagorean closure (every a > 0 has a square root > 0). This he does with a beautifully simple idea. Assume K is ordered decidable (in particular "=" is decidable) Using M. Barr wording: " Let me give an example of the flavor. Suppose you want to have a square root of a > 0. It is decidable (by hypothesis) if a > 0; what may not be decidable is whether a has a square root." Joyal simply construct the ring A = K[x]/(x^2 - a) = K[s] with s^2 = a. He then considers an equivalence relation in A: Consider J = {x + ys | x = 0, y = 0 or not(y = 0), -x/y > 0, (-x/y)^2 = a} the relation "\in J" is decidable, then if J is an ideal, the quotient by J will also have "=" decidable. J = {0} precisely if a does not have an square root in K, but it can be shown that J is an ideal without having to decide if a has or not a square root !! Furthermore, it can be shown (with some but not too much work) that the quotient K[s]/J is a order decidable field. This field is the solution to the universal problem of adding to K an square root of a, and it is obtained without the use of Gauss theorem !! (Notice that for non-ordered fields, the universal solution of adding a square root of a when a already has a square root DOES NOT EXIST (it is not given by K itself), while for ordered fields the solution of adding a positive square root does exist, and it is K itself) Algorithms for K[s]/J are easily obtained from the algorhitms for K !! We can iterate this, and then construct the filtered colimit. This filtered colimit is the pithagorean closure, and by construction of filtered colimits a rather simple description of its elements is there. Also algorithms for this colimit are rather easily obtained. All this is considerably simpler than other methods quoted in this thread, and certainly not " *unbelievably* painful". Actually, I believe it could be possible to write with reaonable trouble an actual computer program to calculate in the pithagorean closure of the rationals. I have an article written with an student for a journal on math teaching ("revista de educacion matematica" of the UMA, Union Matematica Argentina) with details of all this. The text is in spanish, in a .pdf file, and I will be happy to send it on request I do not know if Joyal had also a continuation of this story, meaning how to keep adding more roots without Gauss's theorem. e.d.

John's post was interesting, but a couple of things bother me. Since there are explicit enumerations of Q[x] and you can order the roots of any polynomial by their order and adjoin the roots in order, how can you get an uncountable closure? Another question (for Q, although any Archimedean field should work) what if you use Cauchy sequences generated by Newton iteration, having isolated the real roots using Sturm and sticking to an interval in which the derivative is positive (I am thinking of a monic polynomial that is increasing in the end)? Incidentally, AC doesn't bother me at all, but constructive methods are interesting in their own right. Michael

Dear Michael,

Incidentally, AC doesn't bother me at all, but constructive methods are interesting in their own right.

Constructive methods are sometimes more than "just interesting in their own right". If a certain theorem expressible in geometric logic can be proved constructibly, then it is true in any topos, and so amenable to a variety of interesting interpretations. I return to one of the examples I mentioned from my paper ("Sheaves and prime model extensions", J. Algebra 68, 1981) to illustrate how it works for the real closure, which has both a constructive and a non-constructive part. Preamble. The following theorem has been shown (Lipshitz, Trans AMS 211, 1975; van der Dries Ann. Math. 12, 1977) in order to solve the analogue of Hilbert's 17th problem for commutative (von Neumann) regular f-rings. Theorem. Any commutative regular f-ring has an atomless real closure. Using the Pierce representation of any commutative (von Neumann) regular f-ring R by an ordered field K in the (non-Boolean) topos E of sheaves on the spectrum of K, the above theorem can be shown more easily than in the above quoted sources, simply using the analogue for ordered fields, with some care, since we know that, although there is an algorithm for constructing the "real closure" of an ordered field, this does not automatically give that such is real closed. This is how I proceed, using the "mid-way house" method. The inclusion F = E_{not not} >---> E factors through the Gleason cover g:G--->E (g a surjection) via a flat inclusion i: F >---> G. Since F is a BVM/ST, i^*g^*K >---> K' has a real closure. Thus, since i_* preserves finitary logic, g^*K >---> i_*K' is an extension of g^*K into a real closed field i_*K'. Sturm's theorem gives an algorithm which makes sense in any topos, provided the ordered field one applies it to is already contained in some real closed field. From this follows first that g^*K has a real closure in G, and then, by the surjectivity of g (g^* faithful), follows that K has a real closure in E. By "transfer", the commutative regular f-ring R ( R = \Gamma (K)) has a real closure (in Sets). Other results (including classically new ones) in the case of differential rings are proved in that paper. Sheaf methods in the theory of commutative rings are very useful in classical mathematics. See for instance "Recent Advances in the Representation Theory of Rings and C*-Algebras by Continuous Sections", Memoirs AMS 148, 1973. In particular, C. Mulvey, "Intuitionistic Algebra and Representation of Rings" in that volume). Another source is "Applications of Sheaves" (Proceedings Durham 1977), LNM 753, Springer 1977. In particular, the papers by Fourman and Hyland, Fourman and D. Scott, and C. Rousseau. Anyway, this is a huge subject and hints at the usefulness of constructive methods in algebra and analysis, when available. Anhyway, trhis is old stuff. Best, Marta