×

zbMATH — the first resource for mathematics

Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function. (English) Zbl 0892.03013
This paper establishes in its 11 sections two major model completeness results. In the first 8 sections the First Main Theorem is proved, whereas the last 3 sections are devoted to the proof of the Second Main Theorem (see below). Wilkie first studies expansions of \(\mathbb R\) by a Pfaffian chain of functions: Fix \(m,l\in {\mathbb{N}}\) and an open set \(U\subset \mathbb R ^m\) containing the closed unit box \([0,1]^m\). A Pfaffian chain of functions on \(U\) is a sequence \(G_1\),…,\(G_l: U \rightarrow \mathbb R\) of analytic functions for which there exist polynomials \(P_{i,j} \in {\mathbb{R}} [z_1,\dots,z_{m+i}]\) (for \(i = 1,\dots,l\), \(j = 1,\dots,m\)) such that \(\frac{\partial G_i}{\partial x_j} (x)=P_{i,j}(x,G_1(x),\dots,G_i(x))\) for all \(x \in U\). The First Main Theorem states that the expansion of \(\mathbb R\) by Pfaffian functions restricted to the closed unit box (i.e. the functions are set to be identically zero outside the unit box) has a model complete theory. This result may be viewed as a strong refinement of Gabrielov’s theorem, which states that the class of sub-analytic sets is closed under taking complements. Wilkie’s theorem shows that if the restricted analytic functions used to describe a given sub-analytic set \(A\) are Pfaffian, then the complement of \(A\) may also be described by Pfaffian functions. The First Main Theorem implies that the expansion \((\mathbb R , \exp|_{[0,1]})\) of \(\mathbb R\) by the restricted exponential function has a model complete theory. Further, this theory is smooth (Def. 10.2). In particular, it is polynomially bounded (i.e. in any model \(K\), every \(K\)-definable function is ultimately bounded by a power of \(x\)), and o-minimal (i.e. every \(K\)-definable subset is a finite union of intervals and points). For o-minimal \(K\), there is a well-defined (model-theoretic) dimension, and Wilkie establishes that if the theory of \(K\) is smooth, then the rational rank of the value group of \(K\) (with respect to the natural valuation) is bounded from above by this dimension. Using this crucial result, Wilkie deduces the model completeness of the elementary theory Th\((\mathbb R ,\exp)\) of \({\mathbb R}\) with the real exponential function \(\exp\) (Second Main Theorem). This theorem has an important geometric interpretation (cf. p. 1054): call a subset of \(\mathbb R ^n\) semi-exponential-algebraic (semi-EA) if it is defined by exponential-polynomial equations and inequalities, and a map from \(\mathbb R ^n\) to \(\mathbb R ^m\) semi-EA if its graph is so, and finally a set to be sub-EA if it is the image of a semi-EA set under a semi-EA map. Then the theorem is equivalent to the assertion that the complement of a sub-EA set is a sub-EA set. This, as for the semi-algebraic case, implies that the class of sub-EA sets is also closed under taking closures, interiors and boundaries. An alternative proof of the model completeness, and an axiomatization of Th\((\mathbb R ,\exp)\) over Th\((\mathbb R ,\exp|_{[0,1]})\) was found by J. P. Ressayre in 1991 (see L. van den Dries, A. J. Macintyre and D. Marker: “The elementary theory of restricted analytic fields with exponentiation” [Ann. Math., II. Ser. 140, 183-205 (1994; Zbl 0837.12006)], for a generalization of Ressayre’s result). The study of Th\((\mathbb R ,\exp)\) was originally motivated by Tarski’s question whether Th\((\mathbb R ,\exp)\) is decidable. In “On the decidability of the real exponential field” [in: P. Odifreddi (ed.), Kreiseliana: about and around Georg Kreisel, 441-467 (1996)], A. Macintyre and A. J. Wilkie show that this is the case, provided that the real version of Schanuel’s conjecture is true. Recently (“A general theorem of the complement and some new o-minimal structures”, submitted), A. J. Wilkie proved a very general result from which it follows that the expansion of the reals by total Pfaffian functions is o-minimal as well, but the model completeness is still an open problem.

MSC:
03C60 Model-theoretic algebra
12L12 Model theory of fields
32B20 Semi-analytic sets, subanalytic sets, and generalizations
14P15 Real-analytic and semi-analytic sets
12J10 Valued fields
12J15 Ordered fields
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Jane Bridge, Beginning model theory, Clarendon Press, Oxford, 1977. The completeness theorem and some consequences; Oxford Logic Guides. · Zbl 0361.02064
[2] Bernd I. Dahn, The limit behaviour of exponential terms, Fund. Math. 124 (1984), no. 2, 169 – 186. · Zbl 0581.03026
[3] J. Denef and L. van den Dries, \?-adic and real subanalytic sets, Ann. of Math. (2) 128 (1988), no. 1, 79 – 138. · Zbl 0693.14012
[4] J. Dieudonné, Foundations of modern analysis, Academic Press, New York-London, 1969. Enlarged and corrected printing; Pure and Applied Mathematics, Vol. 10-I. · Zbl 0176.00502
[5] A. M. Gabrièlov, Projections of semianalytic sets, Funkcional. Anal. i Priložen. 2 (1968), no. 4, 18 – 30 (Russian).
[6] A. G. Hovanskiĭ, A class of systems of transcendental equations, Dokl. Akad. Nauk SSSR 255 (1980), no. 4, 804 – 807 (Russian).
[7] Anand Pillay and Charles Steinhorn, Definable sets in ordered structures. I, Trans. Amer. Math. Soc. 295 (1986), no. 2, 565 – 592. , https://doi.org/10.1090/S0002-9947-1986-0833697-X Julia F. Knight, Anand Pillay, and Charles Steinhorn, Definable sets in ordered structures. II, Trans. Amer. Math. Soc. 295 (1986), no. 2, 593 – 605. · Zbl 0662.03023
[8] S. Łojasiewicz, Ensembles semi-analytiques, mimeographed notes, IHES, 1965.
[9] L. Mirsky, Introduction to linear algebra, Oxford Univ. Press, 1955. · Zbl 0066.26305
[10] Anand Pillay and Charles Steinhorn, Definable sets in ordered structures. I, Trans. Amer. Math. Soc. 295 (1986), no. 2, 565 – 592. , https://doi.org/10.1090/S0002-9947-1986-0833697-X Julia F. Knight, Anand Pillay, and Charles Steinhorn, Definable sets in ordered structures. II, Trans. Amer. Math. Soc. 295 (1986), no. 2, 593 – 605. · Zbl 0662.03023
[11] A. Tarski, A decision method for elementary algebra and geometry, 2nd revised ed., Berkeley and Los Angeles, 1951. · Zbl 0044.25102
[12] R. G. Downey, A note on decompositions of recursively enumerable subspaces, Z. Math. Logik Grundlag. Math. 30 (1984), no. 5, 465 – 470. · Zbl 0535.03022
[13] Lou van den Dries, A generalization of the Tarski-Seidenberg theorem, and some nondefinability results, Bull. Amer. Math. Soc. (N.S.) 15 (1986), no. 2, 189 – 193. · Zbl 0612.03008
[14] Lou van den Dries, On the elementary theory of restricted elementary functions, J. Symbolic Logic 53 (1988), no. 3, 796 – 808. · Zbl 0698.03023
[15] ——, Tame topology and \(0\)-minimal structures, mimeographed notes, University of Illinois at Urbana-Champaign, 1991.
[16] A. J. Wilkie, On the theory of the real exponential field, Illinois J. Math. 33 (1989), no. 3, 384 – 408. · Zbl 0659.03013
[17] Helmut Wolter, On the model theory of exponential fields (survey), Logic colloquium ’84 (Manchester, 1984) Stud. Logic Found. Math., vol. 120, North-Holland, Amsterdam, 1986, pp. 343 – 353. · Zbl 0639.03037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.