Thesis

Extended Abstract of my Thesis

1. Definably complete structures
2. Noetherian differential rings of functions
3. Effective o-minimality
4. On exponential terms and the decidability problem
5. Axiomatizations of the real exponential field

1. Definably complete structures We take into consideration every expansion of an ordered field such that every definable subset of the domain, which is bounded from above, has a least upper bound. We call such structures {\em definably complete structures}. They form a recursively axiomatized class which includes, in addition to the real exponential field, all the following: any expansion of the real field (for example the real field with the sine function); any o-minimal expansion of a real closed field; any model of a suitable recursive fragment of the complete theory of real exponentiation (or, of the real numbers with a pfaffian chain of functions, or even of with the sine function. We develop the theory of basic calculus in this setting. Subsequently we prove a uniqueness result for the definable solutions of linear differential equations, with an elementary proof which does not use o-minimality. We prove an effective version of Newton's method for the existence of nonsingular zeroes of C² definable maps.
2. Noetherian differential rings of functions We consider the basic differential topology of C^∞ definable functions in definably complete structures. We concentrate, then, on those sets of definable functions which form a noetherian ring closed under differentiation. We prove that the zero-set of a function belonging to such a ring can be decomposed into a finite union of smooth manifolds, defined via functions from the same ring. Here we do not assume Khovanskii-type finiteness properties, hence this decomposition theorem holds for a wide class of functions, which includes non-tame examples like sin(x) and may include some C^∞ but non analytic examples. We apply our decomposition theorem to prove a Khovanskii-type finiteness theorem: given a noetherian differential ring M of functions, if every zero-dimensional zero-set of functions in M consists of finitely many points, then the zero-set of any function in M has finitely many connected components.
3. Effective o-minimality The following results are due to A.Beraducci and myself, and appear in the following paper. We try to answer the following question: under which hypotheses is a definably complete structure o-minimal? The answer we find has the following form: under certain assumptions (which we will not discuss here, but which are for example satisfied by the real exponential field), we can find a recursive scheme of axioms which, added to the axioms of definably complete structure, ensures the o-minimality of all models.
   In this paper Wilkie proved a general ``theorem of the complement'' which in particular implies that in order to establish the o-minimality of an expansion of the reals with C^∞ functions it suffices to prove uniform (in the parameters) bounds on the number of connected components of quantifier free definable sets.
   We prove an effective version of Wilkie's theorem of the complement. In particular we prove that, given an expansion of the reals with finitely many C^∞ functions, if there are uniform and computable upper bounds on the number of connected components of quantifier free definable sets, then there are such uniform and computable bounds for all definable sets. In such a case the theory of the structure is effectively o-minimal: there is a recursively axiomatized subtheory such that all the models are o-minimal. The hypotheses of our theorem hold in the case of an expansion of the reals with Pfaffian functions, so in particular we obtain a proof of the effective o-minimality of any expansion of the reals by finitely many Pfaffian functions.
4. On exponential terms and the decidability problem It is well known that the problem of the decidability of the theory of the real exponential field is extremely hard to solve. This remains true if we consider fragments of the complete theory, such as the Quantifier Free Part, or the Existential Part. It follows that a better understanding of the algebra of exponential terms is crucial. We first prove that the set of all closed exponential terms t such that t < 0, is recursively enumerable. We use this result to prove that the set of all systems of n term-defined equations in n variables which have a nonsingular solution is recursively enumerable (these results are obtained using our effective version of Newton's method and hold for exponential terms and for a much wider class of functions, which we call "effectively" C²
5. Axiomatizations of the real exponential field We simplify the candidate for a complete and recursive axiomatization of the real exponential field which was provided by Macintyre and Wilkie: We show that some of the axioms they propose are superfluous, and we simplify, using a result of Ressayre, their argument which, assuming Schanuel's Conjecture, ensures the completeness of this candidate. We observe that, for the simplified recursive axiomatization T , the following result holds (here we are not assuming any unproven conjecture): If every model of T has an archimedean submodel, then T is complete.

• A. Berarducci, T. Servi, An effective version of Wilkie's theorem of the complement and some effective o-minimality results. Ann. Pure Appl. Logic 125 (2004), no. 1-3, 43--74.
• A. J. Wilkie, A theorem of the complement and some new o-minimal structures, Selecta Math. (N.S.) 5 (1999) 397--421.
• A. Macintyre, A. Wilkie, On the decidability of the real exponential field, in: Kreiseliana, A. K. Peters, Wellesley, MA, 1996, pp. 441--467.