[FOM] query about complexity of the theory of [R,+, < ]

[John Baldwin]

At 11:01 AM 11/3/2003 -0800, Martin Davis wrote:
>A former colleague has asked me about the complexity of this theory:
>a) when R is the reals,
>b) when R is the rationals
>and has also asked whether the two are elementarily equivalent.

This these are models of the theory of divisible ordered abelian groups: it 
is complete.  In fact, as a reduct of (R, +, *,<)  we see the second
structure is o-minimal (and so the first).

Since I gave you an axiomatization the theory is decidable.  I don't know 
more refined bounds but Marker suggests there are at least exponential 
lower bounds
on the complexity.




>Information about the most recent results along these lines would be 
>appreciated.
>
>Martin
>
>
>_______________________________________________
>FOM mailing list
>FOM at cs.nyu.edu
>http://www.cs.nyu.edu/mailman/listinfo/fom