Re: Construction of a real closure

Re: Construction of a real closure

[Peter Freyd]

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.

RE: Construction of a real closure

[Marta Bunge]

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

Re: Construction of a real closure

[Michael Barr]

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

Construction of a real closure

[Eduardo Dubuc]

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.

Re: Construction of a real closure

[Peter Freyd]

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.

Re: Construction of a real closure

[John Baez]

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

RE: Construction of a real closure

[Marta Bunge]

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
>

Re: Construction of a real closure

[Michael Barr]

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
>

Re: Construction of a real closure

[Phil Scott]

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

RE: Construction of a real closure

[Michael Barr]

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

RE: Construction of a real closure

[Marta Bunge]

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

RE: Construction of a real closure

[Marta Bunge]

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

Construction of a real closure

[Michael Barr]

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