Introduction and notationLet L be the usual first order language of ordered rings together with a new unary function symbol e.We are interested in the L-structure R (R, 0, 1, …
Introduction and notationLet L be the usual first order language of ordered rings together with a new unary function symbol e.We are interested in the L-structure R (R, 0, 1, +,., -, <, e) consisting of the ordered field of real numbers with e(x) interpreted as the exponential function e (and we shall henceforth write e x for e(x) in any L-structure).We denote by T the L-theory of R e.This theory and its subtheories have been investigated by many authors and we refer the reader to Macintyre [4] for a comprehensive survey.We are con- cerned here with the problem of determining whether T is model complete, that is whether k, K T and k _ _ _ K imply k K, or equivalently k 1 K (i.e., existential formulas with parameters in k are preserved down from K to k).We shall prove the following: THEOREM 1. Suppose k, K Te, k c_C_ K and k is cofinal in K (i.e., if a K then b < a < c for some b, c k). Then k l K.(Unfortunately there seems to be no general model theoretic argument that allows us to deduce that k K here.)We shall actually prove a result slightly stronger than Theorem 1 which allows us to isolate a plausible conjecture that would imply the model completeness of T e.To state this result we require some notation.Let us fix a model K of T and a substructure k of K. We also assume that k is a field.For n N we denote by k[] the set of all terms of L(k) (defined as L together with a constant symbol for each element of k) in the variables ' x 1,..., x factored by the equivalence relation f-g iff Ter-Vf=g.Since it is known (see [4]) that f---g iff k Vf g it will be harmless to
On introduit la notion de theorie O-minimale des structures ordonnees, une telle theorie etant telle que les sous-ensembles definissables de ses modeles soient particulierement simples
On introduit la notion de theorie O-minimale des structures ordonnees, une telle theorie etant telle que les sous-ensembles definissables de ses modeles soient particulierement simples
This article points out some remarkable facts implicit in the results of Lojasiewicz [LI] and Gabrielov [Ga].An important consequence of Tarski's work [T] on the elementary theory of the reals …
This article points out some remarkable facts implicit in the results of Lojasiewicz [LI] and Gabrielov [Ga].An important consequence of Tarski's work [T] on the elementary theory of the reals is a characterization of the sets which are elementarily definable from addition and multiplication on R. Allowing arbitrary reals as constants, this characterization consists of the identification of the definable sets with the semialgebraic sets.(A semialgebraic subset of R m is by definition a finite union of sets of the form {x e R w : p(x) = 0, q x (x) > 0,...,q k (x) > 0} where p,q 1 ,...,q k are real polynomials.)The fact that the system of semialgebraic sets is closed under definability is also known as the Tarski-Seidenberg theorem, and this property, together with the topological finiteness phenomena that go with it-triangulability of semialgebraic sets [L2, Gi], generic triviality of semialgebraic maps [Ha]-make the theory of semialgebraic sets a useful analytic-topological tool.Below we extend the system of semialgebraic sets in such a way that the Tarski-Seidenberg property, i.e., closure under definability, and the topological finiteness phenomena are preserved.The polynomial growth property of semialgebraic functions is also preserved.This extended system contains the arctangent function on R, the sine function on any bounded interval, the exponential function e x on any bounded interval, but not the exponential function on all of R. (And it couldn't possibly contain the sine function on all of R without sacrificing the finiteness phenomena, and a lot more.)As a corollary we obtain that neither the exponential function on R, nor the set of integers, is definable from addition, multiplication, and the restrictions of the sine and exponential functions to bounded intervals.Questions of this type have puzzled logicians for a long time.(There still remain, of course, countless unsolved problems of this sort.)In a more positive spirit Tarski [T, p. 45] asked to extend his results so as to include, besides the algebraic operations on R, certain transcendental elementary functions like e x ; the theorem below is a partial answer.(More recently, Hovanskii [Ho, p. 562] and the author [VdDl, VdD2] asked similar questions, and in [VdD3] we
As a contribution to definability theory in the spirit of Tarski's classical work on ( R , <, 0, 1, +, ·) we extend here part of his results to …
As a contribution to definability theory in the spirit of Tarski's classical work on ( R , <, 0, 1, +, ·) we extend here part of his results to the structure Here exp ∣ [0, 1] and sin ∣ [0, π ] are the restrictions of the exponential and sine function to the closed intervals indicated; formally we identify these restricted functions with their graphs and regard these as binary relations on R . The superscript “RE” stands for “restricted elementary” since, given any elementary function, one can in general only define certain restrictions of it in R RE . Let ( R RE , constants) be the expansion of R RE obtained by adding a name for each real number to the language. We can now formulate our main result as follows. Theorem. ( R RE , constants) is strongly model-complete . This means that every formula ϕ ( X 1 , …, X m ) in the natural language of ( R RE , constants) is equivalent to an existential formula with the extra property that for each x ∈ R m such that ϕ ( x ) is true in R RE there is exactly one y ∈ R n such that ψ ( x, y ) is true in R RE . (Here ψ is quantifier free.)