Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-19T09:51:50.445Z Has data issue: false hasContentIssue false

Arithmetization of the field of reals with exponentiation extended abstract

Published online by Cambridge University Press:  18 January 2008

Sedki Boughattas
Affiliation:
CNRS and Paris 7 University, France; [email protected]
Jean-Pierre Ressayre
Affiliation:
CNRS and Paris 7 University, France; [email protected]
Get access

Abstract

(1) Shepherdson proved that a discrete unitary commutative semi-ring A+ satisfies IE0 (induction scheme restricted to quantifier free formulas) iff A is integral part of a real closed field; and Berarducci asked about extensions of this criterion when exponentiation is added to the language of rings. Let T range over axiom systems for ordered fields with exponentiation; for three values of T we provide a theory $_{\llcorner} T _{\lrcorner}$ in the language of rings plus exponentiation such that the models (A, expA) of $_{\llcorner} T _{\lrcorner}$ are all integral parts A of models M of T with A+ closed under expM and expA = expM | A+. Namely T = EXP, the basic theory of real exponential fields; T = EXP+ the Rolle and the intermediate value properties for all 2x-polynomials; and T = Texp, the complete theory of the field of reals with exponentiation. (2)$_{\llcorner}$Texp$_{\lrcorner}$ is recursively axiomatizable iff Texp is decidable. $_{\llcorner}$Texp$_{\lrcorner}$ implies LE0(xy) (least element principle for open formulas in the language <,+,x,-1,xy) but the reciprocal is an open question. $_{\llcorner}$Texp$_{\lrcorner}$ satisfies “provable polytime witnessing”: if $_{\llcorner} $Texp$_{\lrcorner}$ proves ∀x∃y : |y| < |x|k)R(x,y) (where $|y|:=_{\llcorner}$log(y)$_{\lrcorner}$, k < ω and R is an NP relation), then it proves ∀x R(x,ƒ(x)) for some polynomial time function f. (3) We introduce “blunt” axioms for Arithmetics: axioms which do as if every real number was a fraction (or even a dyadic number). The falsity of such a contention in the standard model of the integers does not mean inconsistency; and bluntness has both a heuristic interest and a simplifying effect on many questions – in particular we prove that the blunt version of $_{\llcorner} $Texp$_{\lrcorner}$ is a conservative extension of $_{\llcorner} $Texp$_{\lrcorner}$ for sentences in ∀Δ0(xy) (universal quantifications of bounded formulas in the language of rings plus xy). Blunt Arithmetics – which can be extended to a much richer language – could become a useful tool in the non standard approach to discrete geometry, to modelization and to approximate computation with reals.


Type
Research Article
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Boughattas, S., Trois Théorèmes sur l'induction pour les formules ouvertes munies de l'exponentielle. J. Symbolic Logic 65 (2000) 111154. CrossRef
L. Fuchs, Partially Ordered Algebraic Systems. Pergamon Press (1963).
Mourgues, M.-H. and Ressayré, J.P., Every real closed field has an integer part. J. Symbolic Logic 58 (1993) 641647. CrossRef
S. Priess-Crampe, Angeordnete Strukturen: Gruppen, Körper, projektive Ebenen. Springer-Verlag, Berlin (1983).
A. Rambaud, Quasi-analycité, o-minimalité et élimination des quantificateurs. PhD. Thesis. Université Paris 7 (2005).
J.P. Ressayre, Integer Parts of Real Closed Exponential Fields, Arithmetic, Proof Theory and Computational Complexity, edited by P. Clote and J. Krajicek, Oxford Logic Guides 23.
J.P. Ressayre, Gabrielov's theorem refined. Manuscript (1994).
Shepherdson, J.C., A non-standard model for a free variable fragment of number theory. Bulletin de l'Academie Polonaise des Sciences 12 (1964) 7986.
van den Dries, L., Exponential rings, exponential polynomials and exponential functions. Pacific J. Math. 113 (1984) 5166. CrossRef
Wilkie, A., Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function. J. Amer. Math. Soc. 9 (1996) 10511094. CrossRef