- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- O-minimal expansions of the reals
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
O-minimal expansions of the reals 2002
pdf
Page Metadata
Item Metadata
Title | O-minimal expansions of the reals |
Creator |
Ingram, Patrick Malte Josef |
Date Created | 2009-10-07T20:49:44Z |
Date Issued | 2009-10-07T20:49:44Z |
Date | 2002 |
Description | We survey recent results on o-rninimal theories, and in particular o-minimal expansions of real closed fields. The recent work in the classification of reducts of the field of real numbers, largely the work of Peterzil, is presented, as is the basic groundwork of o-rriinimality. It is shown that if X ⊆ℝⁿ is semialgebraic, but not semilinear, then multiplication on ℝ may be defined locally in terms of X, modulo the vector space properties of the reals. If X \ K is not semilinear for any compact K, then the condition of locality can be removed. |
Extent | 3568227 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | Eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project [http://www.library.ubc.ca/archives/retro_theses/] |
Date Available | 2009-10-07T20:49:44Z |
DOI | 10.14288/1.0079363 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of |
Degree Grantor | University of British Columbia |
Graduation Date | 2002-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
URI | http://hdl.handle.net/2429/13735 |
Aggregated Source Repository | DSpace |
Digital Resource Original Record | https://open.library.ubc.ca/collections/831/items/1.0079363/source |
Download
- Media
- ubc_2002-0430.pdf [ 3.4MB ]
- Metadata
- JSON: 1.0079363.json
- JSON-LD: 1.0079363+ld.json
- RDF/XML (Pretty): 1.0079363.xml
- RDF/JSON: 1.0079363+rdf.json
- Turtle: 1.0079363+rdf-turtle.txt
- N-Triples: 1.0079363+rdf-ntriples.txt
- Citation
- 1.0079363.ris
Full Text
O-MINIMAL EXPANSIONS OF THE REALS by PATRICK MALTE JOSEF INGRAM B.Sc. (Mathematics) Simon Fraser University, 1999 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES Department of Mathematics We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA October 2002 © Patrick Malte Josef Ingram, 2002 In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for exten- sive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Mathematics The University of British Columbia Vancouver, Canada Date Qfjr tO , ZOOT^ Abstract We survey recent results on o-rninimal theories, and in particular o-minimal expansions of real closed fields. The recent work in the classification of re- ducts of the field of real numbers, largely the work of Peterzil, is presented, as is the basic groundwork of o-rriinimality. It is shown that if X C R n is semialgebraic, but not semilinear, then multiplication on R may be defined locally in terms of X, modulo the vector space properties of the reals. If X \ K is not semilinear for any compact K, then the condition of locality can be removed. ii Table of Contents Abstract » Table of Contents iii Acknowledgments iv Introduction v Chapter 1. O-minimal structures 1 1.1 Introduction 1 1.2 The Tarski-Seidenberg theorem 13 1.3 The proof - 1 6 1.4 Algebraic structures 24 1.5 Prime models 27 Chapter 2. The real numbers 30 2.1 Archimedean ordered groups 30 2.2 Semilinear and semibounded sets 38 2.3 Defining fields • • • 44 2.4 Nonlinear structures — 51 2.5 Multiplicative reducts 66 2.6 Polynomially unbounded structures 69 2.7 O-minimal expansions of (Q, +, <) 70 2.8 End extensions 71 Bibliography 74 iii Acknowledgments I would primarily like to thank Dr. Andrew Adler and Dr. Alistair Lachlan for their time and support, without which this thesis would not have been possi- ble. I would also like to thank Dr. Ya'acov Peterzil for providing a number of reprints, and suggesting some directions for future inquiry. iv Introduction The aim of this thesis is to explore the subject of o-minimal structures, and in particular survey the use of o-minimal structure theory to classify reducts of the field of real numbers. The thesis itself is written with the assumption that those reading it will have a basic understanding of model theory, but we will lay out here the requisite fundamentals informally. Initially we should attempt to define model theory. Wilfrid Hodges1 de- scribes model theory as 'algebraic geometry minus fields.' This is a rather good description both because it gives a fairly good idea of what the subject is, and because it makes model theory seem very cutting-edge. Indeed, model theory was recently used to solve a significant problem in algebraic geome- try [Bou98]. One wanting a description more thorough (and less glib) might like this: Model theory is the subject in mathematics interested in determin- ing what mathematical structures exist, and what mathematical structures are worth studying, primarily by examining the subsets definable in structures by first-order sentences. In the classical sense, a 'structure' is a non-empty set with certain distinguished relations, functions, and elements. For exam- ple, a group, (G, •, e) is a structure. A definable set in a structure is the set of tuples from the structure satisfying some first order formula, with possi- ble additional constants from the structure. If any additional constants used come from the set A, the set is said to be A-definable. The center of G is a definable subset of G, namely the set of all x satisfying \fy(xy = yx). In fact, it is 0-definable. For those unfamiliar with the concept of a first-order formula, it suffices to consider any coherent string of symbols either from the 'language' of the structure (the distinguished relations, functions, and con- stants) or from the language of logic: A (and), V (or), —• (implies), -> (not), V (for all), 3 (there exists), and variables. The variables which are not bound by quantifiers are 'free variables' and we can view a first order formula as a condition on elements (or tuples of elements) in the structure. If cp is such a formula, and Jfrisa structure, ip(JZ) is exactly that set of elements (or tuples) MHod93] v Introduction vi from the structure of which yp is true. We use a great deal the fact that first order formulas are of finite length. We use = to denote equivalence of first order formulas to avoid confusion with the uses of = in the formula. This symbol also has another important us- age, however: we say that two structures Jt and are elementarily equiva- lent, written = JV , if they have the same language, and the same first or- der sentences (formulas without free variables) are true in and JV. An em- bedding of J£ into JV is an injective function from Jt to JV which sends the various constants of Jt to the appropriate constants in JV, commutes with all of the distinguished functions, and preserves the distinguished relations (i.e., a tuple a € Jtn is related by R if and only if ( / ( a n ) , / ( a n ) ) G JVn is related by R). An elementary embedding is an injective function which preserves the relations defined by any first order formulas. We say that J£ is a substruc- ture of J/ (resp. elementary substructure), ^ ^ JV (resp. ^ JV), if it is a subset and the identity map is an embedding (resp. elementary embedding). If Jt is a substructure of JV, J/ is an extension of Jt. An isomorphism is a surjective embedding. A first order theory T is a set of first order sentences (formulas without free variables), and a model of a theory is a structure J£ which makes each of these sentences true, denoted J6 [= T. It is common, however, in modern model theory to view a structure some- what differently. We typically consider two structures on the same underly- ing set to be 'the same' if the same sets are 0-definable (or even, for some purposes, simply definable) in both. Thus ( Q , + ) and (<Q>, - ) are more or less the same structure. A strong reduct of a structure Jt is another structure JV on the same set with every 0-definable set in JV being 0-definable in Jt'. A structure JV is simply a reduct of Jl', jY <C Ji', if every definable set in Jf is definable in Jt. If Jf is a reduct of Jl', J( is an expansion of jV. As a more general sense of reduct, the structure JV is said to be 'definable' in j% if Jf C j ( n is definable, and each definable subset of jVm is a definable subset of ^ m n . For example, the group of invertible 2 x 2 matrices over some field F (viewed as a subset of F 4 ) is definable in F. We also make use of a sort of infinite conjunction: an n-type over A C Jt is an ultrafilter of A-definable subsets of J£n, the set of all such being denoted Sn(A). The realizations of p (the intersection of all of the definable sets) is p(j%). In a given structure, and for a given type, this may or may not vi Introduction vii be empty, but the compactness theorem ensures that every type is realized in some elementary extension. A type p is atomic if it is generated (as an ultra- filter) by a single formula, or definable set. Atomic types are always realized. The type of a tuple a over a set A is denoted tp(a/A). A great deal of work has been completed in an attempt to separate those structures which are easy study in some sense or other, and those that are not. One particular class of structure which has been studied is that of minimal structures: a structure Ji is minimal if for any definable X C Ji, either X or Ji \ X is finite. Note that in any structure Ji the set { a o , a n } is defined by the formula x = ao V .. . V x = an, and Ji \ { a o , a n } is defined by the negation of this formula, so a minimal structure is a structure in which only those subsets of Ji which must be defin- able are definable. However, this does not mean that there are no interesting definable subsets of Jin for n > 1. It is not true that any structure elemen- tarily equivalent to a minimal structure is again minimal, but structures with that property form an even more interesting class, called strongly minimal structures. The archetypical example of a strongly minimal structure is an algebra- ically closed field. It is easy to show (using, say, Theorem 1.2.2) that if Tp is the set of axioms for an algebraically closed field of characteristic p, then Tp is complete (that is, any two models of Tp are elementarily equivalent) and has elimination of quantifiers (any definable set is definable using a formula with- out V or 3 ) . In particular, the definable subsets of k \= Tv are simply boolean combinations of zero sets of polynomials, and so are finite or cofinite. And it is rather easy to study models of Tp as there is exactly one, up to isomor- phism, for each cardinal number K, namely the algebraically closed field with transcendence degree K over the prime field of characteristic p. More generally, interest has recently been focussed on structures which show strong geometric properties and independence relations. Given a set AC. Ji (definable or otherwise) we define the algebraic closure of A to be the union of all finite yl-definable sets. In algebraically closed fields this corre- sponds to algebraic closure in the usual sense2; in vector spaces, span. Several 2Precisely: the 'algebraic closure' of a set is the algebraic closure of the field generated vii Introduction of the familiar properties from these settings transfer to more general settings: • if A C acl(J5) then ac\(A) C acl(B) • for all A, AC acl(v4) • if x 6 acl(.A) then x <E acl(A)) f ° r some finite3 AQ C. A In certain structures, however, we have another useful property. We say that a is independent from b over A, denoted a [A b, if a g acl({6} U A ) \ acl(-A). If this relation is symmetric (for any A) in a given structure, we say that this structure satisfies the exchange law. In structures with this property we can define a reasonable sense of algebraic dimension. The dimension of a tuple a € Jtn over A, dim(a/A), is the number of elements in any algebraically independent (over A)a' C.a such that acl(a U A) = acl(a' U A). If X C Jtn is A-definable, then dim(X) = max{dim(a/.A) : a € X} (which turns out to be independent of A). Another related tool used to study structures is Morley dimension or rank. If M is a structure we may define a relation R between nonempty definable subsets of JZ and ordinals by transfinite induction, using • R(X, 0) for all definable X • R(X, A) if and only if R(X, a) for all a < A, when A is a limit ordinal • R(X, a + 1) if and only if there is a countable family XQ, X\,... of defin- able disjoint subsets of X such that R(XN, a) for all n. It is a simple observation that if R(X, a) fails for some ordinal then there is a greatest ordinal for which it is true, and this ordinal is the Morley rank of X, Mrank(X). If R(X, a) is true for all a then we put Mrank(X) = oo. Thus R(X, a) is equivalent to a < Mrank(X), and Mrank(X) = 0 if and only if X is finite. Structures of finite Morley rank have been studied at great length. Note that if ./# is strongly minimal (and infinite), then Mrank(^) = 1. We know that i?(^#, 1) because Jt is infinite, but if we have infinitely many disjoint de- finable subsets of J<t', at most one may be mfinite (as that one will be cofinite) by that set. 3This is because x is in some finite set defined using constants from A, and the defining formula is of finite length. viii Introduction ix and so it is false that R(Jf, 2). It is currently conjectured (Cherlin's conjec- ture) that every simple group of finite rank is an algebraic group. As it is also true that any structure definable in a structure of finite Morely rank is again of finite Morely rank, the truth of this conjecture would imply that any simple group definable in a strongly minimal structure is an algebraic group. Many other conjectures have been put forward regarding strongly minimal struc- tures. In particular, it was conjectured that the only non-degenerate exam- ples of strongly minimal structures arose from vector spaces and algebraically closed fields. This turned out to be true given additional assumptions. In this thesis we will study o-minimal structures. An ordered structure is, for us, one in which one may define a dense linear ordering without end- points. Such a structure cannot be strongly minimal as one may define open intervals, which are infinite but not cofinite. But here again we introduce a subfamily of 'minimal' structures, where only the bare minimum of sets may be defined. In the case of ordered structures, at minimum we may define boolean combinations of singletons and open intervals, and so a structure in which only sets of this form may be defined is called order-minimal, or o-minimal. Again, this does not prohibit interesting behaviour in higher di- mensions. Although the study of o-minimal structures is much younger than the study of strongly minimal structures, progress has been rapid. A version of the conjecture above, called the trichotomy theorem, has been proven. Any o-minimal structure is, locally, either trivial, a vector space, or an expansion of a real-closed field. It is also known that the only simple groups definable in o-minimal structures are algebraic groups, either over real closed fields or algebraically closed fields. Vaught's conjecture and several other well known model theoretic claims have been demonstrated in the o-minimal case. O- minimal structures provide a natural context for studying structures over R, and so are a natural class to consider. By a 'structure over R ' , here, we mean an expansions of (R, <). Indeed, as we shall see, many familiar structures over R are o-minimal. As we are allowing (in fact insisting on) consideration of the order on R, we may also study some topological properties of struc- tures over R. Recently some work has been done on the fundamental groups of sets definable in o-minimal structures over M. Another way of viewing the study of o-minimal structures is as a gen- ix Introduction eralization of semialgebraic geometry (geometry in the field4 (R, +, •)). Any subset of R n constructible in this field turns out to have a very simple form. A cell is defined recursively to be a singleton or open interval, or the graph of a continuous rational function on a cell, or the region above or below the graph of some continuous rational function on a cell, or the region between two continuous, nonintersecting rational functions on a cell. Every semial- gebraic set then turns out to be a finite union of cells. A similar statement is true in the study of subanalytic geometry. If one makes the same definition of a cell in an o-minimal structure, replacing 'rational' with 'definable', the analogous theorem can be derived (Theorem 1.1.2). Sets and functions defin- able in o-minimal structures over R can then be shown to have various nice topological and analytic properties. Recent work has used strong minimality to classify, to some extent, the reducts of (C, +, •)• It was shown by Marker and Pillay in [MP90] that for algebraic sets X C C " , (C, +, X) is either locally modular5 or defines all alge- braic sets6. Of course, it suffices to show that one can recover multiplication from X. One of the more concrete reasons to study o-minimal structures is that it allows us to make great strides towards classifying the reducts of the field of real numbers. This may seem, as we are working within (R, +, •), to be a question of semialgebraic geometry, but a significant amount of model theory is required as well. It was conjectured by van den Dries that there was no nontrivial reduct of the field of reals which properly expanded the vector space of real numbers. The motivation for this is obvious: given many sim- ple rational functions it is possible to recover multiplication using only vector space algebra. For example, if f(x) = x2, xy = \(f(x + y) - f(x) - f(y)); if g(x) = 1/x, x2 = g(g{x) — g(x + 1)) — x, and so on. The conjecture, how- ever, turns out not to be true. The structure = (R, +, *, <), where * is the restriction of multiplication to [0, l] 2 , is one such proper reduct, but this is the only counterexample. We can then show, using similar methods, that the 4 Although not explicitly an ordered structure, the field of real numbers defines the usual ordering on the reals, by x < y <-> 3z(z2 = y — x). 5See [Bou98]. A structure is modular if for any sets A and B, dim(A) + d\m(B) = dim(A d B) + dim(A U B). A structure is locally modular if it is modular in terms of the closure operator cly (A) = acl(A U Y) for some large set Y. 6I.e., is the same structure as (C, +, •)• Introduction xi only proper reduct of (R, +, •) which properly expands (R, •, <) is (R, ©, •, <), where © is the restriction of + to [1,2]2. These facts can be expressed in terms of growth rates of functions, as can a similar fact about exponentiation. The limits of space and time restrict our ability to prove certain results. For the most part, any result which is not model theoretic is deferred. Well-known results of model theory which do not require knowledge of o-rrunimality are also assumed without proof. We will also omit the proof that (R, +, •, x t-> ex) is o-minimal, a result shown by Wilkie. The main substance of this rather long proof is the proof of model completeness. This tells us that every definable set is the projection of some quantifier-free definable set. As we do demon- strate the o-minimality of (R, +, •) we can take this result to be a corollary of Speissegger's theorem on Pfaffian differential equations ([Spe99, LSOO]): if & is an o-minimal expansion of (R, +, •), U is an open, connected, ^-definable subset of R n and / : U —> R is a C 1 function satisfying a system of differential equations |£(s) = W(S),*) with each Fi : M x U -> R definable in ̂ and C 1 then (M, f) is o-minimal. Applying this to f(x) = ex, U — R, Fi (y, x) = y we have our result. The proof of Speisseger's theorem requires a great deal of heavy differential geometry, and not a great deal of model theory. Current research in o-minimal structures is too broad to survey succinctly, but there are a few large questions which remain unanswered. Possibly the greatest of these is whether or not there are any examples of o-minimal struc- tures not arising from the real numbers. So far all known examples are gen- erated in a simple fashion7: one constructs some o-minimal structure on R, builds an elementary extension, adds constants from the new structure, and then restricts attention to an elementary substructure. There is no proof, how- ever, that this generates all o-minimal structures. There are also some ques- tions regarding proper o-minimal expansions of the prime models8 of cer- tain theories. It is, for example, widely conjectured that there is no proper o-minimal expansion of (Q, +, <). In [LS95] the question is widened to the 7 With the possibility of some steps being trivial. 8 A (the) prime model of a theory is a model which elementarily embeds into every other model. xi Introduction xii field of algebraic numbers and the prime model of the theory of the exponen- tial field of real numbers. The general statement, however, cannot be true as the ordered vector space (M, +, <, AQ : a € R), where Xa(x) = ax, is prime and o-minimal, but properly expanded by (R, +, •). xii Chapter 1 O-minimal structures 1.1 I n t r o d u c t i o n A structure is o-minimal if it defines a linear ordering < and, modulo this fact, has the smallest possible class of definable subsets. Stated formally: Definition 1.1.1. Let be an ordered structure, and X C Ji be definable. We say that X is of finite type if X is a boolean combination of sets of the form (a , b) = {x : a < x < b} (—00, a) = {x : x < a} (b, 00) = {x : b < x} and { a } , with a , 6 e Jt is said to be o-minimal if every definable X C J£, is of finite type. We will consider only o-minimal structures whose underlying order is a dense linear order with no endpoints. It was shown by Pillay and Steinhorn that any o-minimal structure can be definably 'split' into a trivial part, and a part with the above order. Note also that every ordered structure J6 comes 1 Chapter 1. O-minimal structures 2 equipped with a natural topology, generated by the open intervals (a, b) = {x : a < x A x < b}, where a, b E JiU{±oo}, and where ±00 are imaginary elements added above and below the structure. Similarly, we form a topology on Ji n in the usual way, by taking products. Unless noted, all topological references will be to these topologies. One should also note that while an o-minimal structure may not be complete, it must be definably complete. That is, for every definable set X C Ji, both inf (X) and sup(X) must exist in Ji U {±00}. Lemma 1.1.1. Let int(X), cl(X), and bd(X) denote the interior, closure, and boundary of a set X, in the usual topological sense. Then ifX is a definable subset of Jin,for some o-minimal structure Ji, int(X), cl(X), and bd(X) are definable. Proof. Let (p(x) define X C Ji. Then the formula 3y3z(y < x < z A Vu;(y < w < z —> (f(w))) defines the interior of X. Then, cl(X) is the complement of the interior of the complement of X, and bd(X) is the closure of X less the interior of X. Now, if X C Ji n is defined by ip(x\,...,xn), it is enough to point out that (ai,...,an) € mt(X) if and only if a* € int(</?(ai,a^-i, Ji, a j + i , a n ) ) for each i, simply by the definition of the product topology. • Notice, in fact, that all three sets are definable using only the parameters used to define X and that they are all 'uniformly' definable, in that each op- eration is given by a scheme in the formula defining the set. Chapter 1. O-minimal structures 3 The groundwork for the study of o-minimal structures was set down in [PS86, KPS86, PS88], with perhaps the most key theorem being the cell decom- position theorem. This theorem allows us to perform many useful inductions on the definable sets in an o-minimal structure, by building these definable sets in a simple, recursive fashion. The theorems and lemmas in this section are all contained in the three papers listed above. Definition 1.1.2. Let JZ be an ordered structure. Any singleton subset of JZ will be called a O-dimensional cell, and any open interval a 1-dimensional cell. If C C JZn is a fc-dimensional cell, and / , g : C —• JZ are continuous, definable functions with f < g then / C JZn+l (viewed as a set of tuples) is a fc-dimensional cell, and .(/, 9) = { (* ,y) : f (x )<y< g(x)} c j Z n + l is a k + 1-dimensional cell. In the latter we allow / = —oo and/or g = oo. Theorem 1.1.2. Let JZ be an o-minimal structure, and let X C JZn be a definable set. Then there are cells C i , C k C J£n such that X = C\ U . . . U Cfc. Furthermore, if' f : X —> JZ is definable, the Ci may be chosen such that f \ Ci is continuous for each i. This theorem cannot be proven right away. Its proof is a rather complex induction, intertwined with the following, very useful, result. Theorem 1.1.3 (Uniform bounds). Suppose JZ is an o-minimal structure, and that X C JZn+1 has the property that each fibre Xa = {x:(x,a)eX}, Chapter 1, O-minimal structures 4 a E Jin, is finite. Then there is a uniform bound on the sizes of the Xa. Note that the theorem extends easily to X C Ji^n+k">. It is well known that not every minimal structure is strongly minimal. As a witness to this, (co, <) is minimal, but is not strongly minimal as (u, <) = (w x {0}) U (Z x {1}), ordered reverse lexicographically, and x < (0,1) defines a set in the latter which is neither finite nor cofinite. Assuming the above theorem we may easily prove that such an example cannot be constructed in the o-minimal case. 'Strongly o-minimal' is equivalent to 'o-minimal.' Theorem 1.1.4. Let Ji be o-minimal, and JY = Ji. Then jV is o-minimal. Proof. We will assume Theorem 1.1.3. Suppose that ip(x, y) is a formula in the language of Ji. Let Ji (= Vv(a' ^ o n t y if a is 3 boundary point of <p(Ji, b), and let a £ = Vy3^x(Vv(z,y))- As Ji is o-minimal, i\)^(Jib) is finite for all b, and so, by the theorem on finite bounds, there is some n for which Ji (= crJJ. But then Ji (= cr™, and so each fibre oiip'vtxjV is of finite type. As <p was arbitrary, Ji is o-minimal. • Theorem 1.1.2 also allows us to define a reasonable dimension for defin- able sets: if Ji is o-minimal and X C Jin is a definable set, then dimpO = max{dim(C) : C C X, C is a cell}. Chapter 1. O-minimal structures 5 It is easy to verify that this is defined for all definable sets X, in particular be- cause C C X implies dim(C) <: n. By a curve in J£ we mean a 1-dimensional subset of J£2. We will prove Theorems 1.1.2 and 1.1.3 in Section 1.3. First, however, we will establish a technical lemma needed in the result. This lemma is clearly the base case for the induction to prove Theorem 1.1.2. Lemma 1.1.5. Assume that Jt is o-minimal, and that f : (a,b) —> Jt is definable, where a, b e U { ± o o } . Then there exist a = an < a i < • • • < an = b such that for all i, f \ (a^ ai+i) is either constant, or a bijection which preserves or reverses order. Proof. To simplify the proof we introduce a claim. Also, for the remainder of this proof, a function which is either constant or strictly monotone on a given interval is said to be basic on that interval. Claim. Let f and J( be as in the lemma. Then there is an interval I C (a, b) such that f is basic on I*. Chapter 1. O-minimal structures 6 Proof of claim. Let <po(x) = a < x < b A 3y(y < x A \/u(y < u < x —> f(u) = / (x))) V3y(y > x A Mu(x <u<y^> f(u) = f(x))) <pi(x) = a < x < b A 3y, z(y < x < z A Vix(y <: u < x —> f(u) < / (x ) ) AVu(x < u <; 2 -+ / ( x ) < /(tt))) cp2(x) = a < x < b A 3y, z(y < x < z A W(y < u < x —> /(it) > /(a;)) AVit(x < « < 2 -> / ( x ) > / ( « ) ) ) <£>3(x) = a < x < b A3y,z(y < x < z A\/u(y <u< z —> (u = x V / ( u ) > / (x)))) <p^(x) = a < x < b A3y, z(y < x < z A Vu(y < « < 2 - > ( u = i V f(u) < f(x)))) We first need to show that (a, b) = IPQLJK) U . . . U ip\LJ£). Suppose that x e (a, b) \ <po(J?)- Let X + = { y 6 ( a , 6 ) : / ( y ) > / ( x ) } ) X- = {ye(a,b):f(y)<f(x)}. Then for all y £ (a, b), y < x, either X+ or X ~ must intersect (y, x), or else that y witnesses <po(x). By o-rmnimality,.then, either X+ or X~ must contain an interval of the form (a, x), with a < x. Similarly, either X+ or X~ must contain an interval of the form (x, B), with B > x. The four cases, where (a, x) € X^ and (x, 8) e X^, correspond to the four cases, </?i(x),..., 934(x). Thus one of the sets <pi(JS) must contain an interval / . Chapter 1. O-minimal structures 7 Suppose that / C tpo{JZ) (indeed, suppose po(JZ) 0). If x € ^>Q(JZ) then there is an interval to the left or right of x on which / is constant, and so basic. We have our I. Suppose that I Qip\ (JZ), let x € I be arbitrary, and let X = {y:yel' Ay>xA f(x) > f(y)}. If there is some y > x with f(y) ^ f(x) then I / I. If y € X then, as y € ip\(JZ), there is an interval to the left of y which is also contained in X. As X is definable, then, it must be a finite union of intervals. Also note that there is, by (fi(x), some z > x such that X is disjoint from (—oo, z) n / . So let c = inf(X). Of course, c £ X, as any element of X has an interval to its left contained in X. Thus f(x) < /(c). But because <̂ i(c), there is some interval J to the right of c such that j e J —* f(c) < f(j). Clearly J must be disjoint from X, contradicting the assumption that c was the left endpoint of an interval in X. So X is empty and, as x was arbitrary, / is increasing (whence basic) on I. Suppose that I C ip2(J/). Repeating the proof in the above paragraph with the order reversed, we see that / is decreasing on I. Suppose that I C (p^(JZ). Let X = {x € I : Vy € I(x < y - f(x) < f(y))}. . If X contains an interval then / is clearly increasing on this interval, and we are done. As X is definable, if it does not contain an interval it is finite, so let I' = {x € I: x > max(X)}. Then I' is a subinterval of J, and JZ |= Vx € I'3y e I'(y > x A f(y) ^ f(x)). Chapter 1. O-minimal structures 8 Suppose that for some XQ G I' there is no y such that the above statement holds with strict inequality. Then there is some x\ € x\ > XQ, with f(x{) = f(xo). There can be no y for x\ for which the inequality is strict (or this y would also serve for xo), so there is an #2 € I', X2 > x\, with / (x 2 ) = f(x\) = f(xo). Continuing this way we have an infinite set, and so an interval, on which / is constant. So we may assume that Jt \= Vx e I'3y € I'(y > x A f(y) < /(:r)). (1.1) By a similar argument, and another refinement of the interval, to I", we may also assume that J<\=\/xeI'3yel'(y<xAf{y)>f{x)). (1.2) Now fix some x £ I", and let X+ = {yel":f(x)<f(y)} X° •= {y E I" : f{x) = /(»)} X- = {y el" : f(x) > f(y)}. Clearly these three sets are definable and partition I", and clearly X° is finite, or we are done. Thus either X+ or X~ must contain an interval (c, d), where d is the right endpoint of I". Take c to be the least such point, and suppose (c, d) C X + . We cannot have /(c) > f(x), as </?3(c) implies that there is some u < c with u < v < c —• /(v) > /(c) > /(x), and so (u, d), a proper superset of (c,d), would be contained in X+. So we must have /(c) ^ f(x). By 1.1 there is some y > c (in /") with /(c) > f(y). But then f(y) < f(x), and so Chapter \. O-minimal structures 9 y e X~, contradicting (c, d) n l " = 0. If we assume that (c, d) C X~, for some c < d, then the same argument (reversing inequalities and replacing 1.1 with 1.2) we also get a contradiction. Finally, if / C ip^JC), we can modify the proof above in the obvious way to see that the claim is true. • Note that any subinterval of (a , b) meets the criteria in the lemma, and so will contain a subinterval on which / is basic. Now let tp(x) be a formula saying that x is the left endpoint of some interval J C (a , b) such that / is basic on / and for no I' D I is / basic on /' . Suppose x € ip(jK). Then there is some y > x such that / is basic on ( x , y). If z € (x, y), then, we cannot have tp(z), because if J is the interval witnessing i])(z), I is properly expanded by I U ( x , y) which leads to a contadiction1. So tyLJC) contains no interval. Let ip(J/) = { a n , a i , ••••,an} where a* < a j + i . We claim that / is basic on each (di, ai+\). If not, let (a, 3) be a maximal subinterval of (au at+i) on which / is basic. We know by the claim that there must be one such interval, say / ' , and we know that there must be a maximal such as it is defined by X(x) = 3u, v((u, v) ~D I' A x £ (u, v) A /is basic on(u, v)).2 If a > ai then, since a < a^+i , we have missed a member of ip(j&) in our list. If a = at then 8 < a j + i , and so there must be a maximal subinterval of (8, ai+i) on which / is basic, and again we have missed a point on our list. 1It is clear that if / is basic on I\ and Ii, and I\ n h ^ 0, then / is basic on 7 i U h 2We can take the union of all intervals extending / ' on which / is basic, but it is not clear a priori that this set has endpoints in JM. Chapter 1. O-minimal structures 10 Similarly, if ao > a then we are missing a point on our list, and so a = ao and b = a n . Thus / is basic on each (a*, aj +i). Now, finally, suppose that / is strictly increasing on (â , aj+i). Then Y = { / ( x ) : a.i < x < ai+i}, being definable, is a finite union of points and open intervals. Let {B\, ...,3m} be the points, and let f(ctj) = Bj, ao = a$, and a m + i = aj+i. Then the image of / over each (aj, ay+1) is an interval, and / is strictly increasing on each ( Q J , Q j + i ) , so / must be an order preserving bijection on each of these intervals. By performing a similar refinement on the intervals of decrease for / , we can expand our list { a o , a n } to the list described in the lemma. • This lemma, at first glance, may make o-minimal structures seem like a rather trivial class, but we shall see that many important structures fall into this family. The class of o-minimal structures can also be shown, from this lemma, to have a very important geometric property. Definition 1.1.3. In a structure (ordered or otherwise) Ji', we. say that an el- ement a is algebraic over a set (not necessarily definable) A C J{ if there is a formula with constants from A which a and only finitely many other elements of ^satisfy. The set of all elements algebraic over A is ac\(A). The element a is further said to be definable over A if there is some formula with constants from A which a, and only a, satisfies. The set of elements definable over A is dc\(A). Note that both aci and del are closure operators in the algebraic sense. It is clear, for example, that acl(̂ 4) and dcl(A) both contain A, and that A C acl(B) Chapter 1. O-minimal structures 11 implies acl(A) C acl(5) (similarly for del). It is also true that these closure op- erators are finitary (i.e., if a € acl(̂ 4) then a G acl(^o) for some finite AQ C A), as any formula may contain only finitely many symbols. In o-minimal struc- tures, as in strongly minimal structures, we have another important property: Theorem 1.1.6 (The exchange law). Let Jt be an o-minimal structure, A C J( (possibly not definable), and a,b e Jt. Then if a e acl({6} U A) \ acl(A), then b G acl({a} U A). What this theorem says is that if there is a dependence of a on b over the set A that is more than simply a dependence of a on A, then there is a symmetric dependence of b on a (over the same set). Proof. The first step in the proof of this theorem is to note that in an o-minimal structure (indeed, any linearly ordered structure), acl(-) = dcl(-). If a is one of only n realizations in M of <p(x), where the constants in ip come from A, then a is the sole realization of one of the formulae "a is the first realization of ip," "a is the second realization of <p," et cetera. Now we wish to show that a is definable over Al) {b} if and only if there is an A-definable interval or singleton X, and an A-definable function / : X —»' JZ with f(b) = a. One direction is clear, so suppose (p(JZ, a, b) = {a}, where a 6 A. Let f(x) = mi{y : <p{y,a,x)}. Then / is clearly A-definable, as is dom(/), and f(b) = a. As shown above, the boundary points of dom(/) are ^-definable, and so dom(/) is a union of points and intervals, each of which is A-definable. Let X be the point or Chapter 1. O-minimal structures 12 interval containing b. So suppose X is an ^-definable point or interval, / : X —> an id- definable function, and f(b) = a. Because dcl(dcl(A)) = dcl(i4), we cannot have b e dcl(A) (or dcl({6} U i ) \ dcl(vl) = 0), and so X is an interval. Let a o , a n be as in Lemma 1.1.5. A close examination of the proof of the lemma shows that these elements are also definable over A, and so we cannot have b = ai for any i. Suppose b G (a*, a j + i ) . If / is constant on this interval, then a is the sole realization of 3y € (ai, ai+i)(f(y) = x), and so is in Ac\(A). So / must be a bijection of ( a j , a j + i ) onto some open interval containing a which either preserves or reverses order, and thus is invertible. This inverse is definable over A by "f(y) = x," and shows that b e dcl({a} U A). • Chapter 1. O-minimal structures 13 1.2 The Tarski-Seidenberg theorem Before continuing, we wish to give at least one example of an o-minimal struc- ture. Of course, quantifier elimination tells us that (Q, <) is o-minimal, but the following example is somewhat less trivial (and somewhat more interest- ing). Theorem 1.2.1. Let X C R n be definable in the field R. Then X is a boolean combination of sets of the form {x:f(x)>0} {x : f(x) = 0}, as f runs through R[x]. In particular, the field of real numbers is o-minimal. Sets definable in this structure are called semi-algebraic. To prove this the- orem, we will quote the following from [Hod93]. Theorem 1.2.2. If T is a theory satisfying a. if Jt, J/\=T,Jt <: JY', and (p(x) is a quantifier free formula with parame- ters from Jl then J/ \= 3xtp(x) implies Jt (= 3x<p(x) b. if JV \=T and Jt < J/ then there is an Jt \=T such that J/ ^ Jt ^ J/ and if J / ' |= T contains Ji then Ji may be embedded into J / ' over J( then T has elimination of quantifiers. If in addition T has a model which can be embedded into all others (an algebraically prime model) then T is complete. For what follows, we take a real closed field to be a structure J£ = (j?,+,;0, 1, <) Chapter 1. O-minimal structures 14 such that a. (Ji,+,-,0,1) is a field b. < is a linear ordering on Ji which preserves the field structure, in the sense that if x < y, then x + z < y + z for all z and xz < yz or yz < xz if z > 0 or z < 0 respectively c. for all / € Ji[x] and a < b G if f(a)f(b) < 0 then for some a < c < b, m = o. Clearly we can give a(n infinite) set of first order axioms equivalent to the above. One can reformulate these axioms in an entirely field-theoretic way, but this is the most convenient context for our purposes. Proof of Theorem 1.2.1. The proof here follows the proof in [Hod93]. Let Ji and Ji be as in part b of Theorem 1.2.2, with T the theory of real closed fields (described above). Let Ji be the set of elements from which are algebraic over Ji (in the usual, field-theoretic, sense). It is known (see, for example, [Fra93]) that this is a field. As it is a substructure of J/', all of the universal axioms of Jf hold in J(. It is also clear that < induces a dense linear order without endpoints on Ji', as x + y x < y -> x < < y. Now suppose / G J?[x], and that f(a)f(b) < 0. Then there is some c € Ji with a < c < b and / ( c ) = 0. But then c is algebraic over Ji, and so over Ji (again, see [Fra93]). Thus c e Ji. Chapter 1. O-minimal structures 15 To show a, let <p(x) be a quantifier-free formula with parameters from Ji', and suppose 'Ji (= 3xp(x). Using basic logic, we may rearrange 3x<p(x) into the form n m,i n m* 3a: V A <Pi^x> - V 3 x A j=0 i=0 j=Q i=0 where each <pji(x) is either an atomic formula, or the negation of one. In this structure each negated atomic formula is a disjunction of atomic formulae, and so by rearranging each <pji (and possibly factoring out disjunctions in the negated case) we see that each ipji may be taken to be pji(x) = 0 or Pji(x) > 0 for some pji € Ji[x]. We clearly need only show the result when n = 0. So let (writing m for mo and i for (0,«)) • 771 tp(x) = / \ tpi(x) i=0 where each </?j is atomic or negated atomic. If, for some i, we have <pi (x) = 'pi(x) = 0' then, as Ji is real closed, any realization of tp is already in Ji. Thus we may suppose that for each i, tpi(x) is Pi(x) > 0. Let CQ < c\ < ... < Ck be a list of all roots of the p^ lib € Ji realizes <p then b is on one of the intervals (—oo, co), (co, c i ) , ( c ^ , oo). By the reasoning above, Cj 6 Ji for all j. Now simply notice that any c in the same interval as b must also satisfy ip, by the intermediate value property. So we choose one such c e Ji and we are done. • Notice also that the field of real algebraic numbers is an algebraically prime model of the theory of real-closed fields, and so this theory is complete, and any real closed field is o-minimal. Chapter 1. O-minimal structures 16 1.3 The proof In this section we will complete the proofs of the Cell Decomposition Theo- rem and the Theorem on Uniform Bounds. In what follows, T(f) will denote the graph of a function/. Definition 1.3.1. Let X C J(n be an open cell, and let ip(x, y) be a formula (with parameters from Jt) such that for each a G Jtm, tp(J0', a) is finite. We will say that o € l i s good for tp(x, y) if for all b G Ji', there is an open box (i.e., a product of intervals) B C X containing a and an interval / containing b such that (i) Jt j= <p(a, b) implies that <p(J() f l ( B x I ) is the graph of a continuous function from B to I and (ii) J{ Via, b) implies that -o(J£) f l ( B x / ) = fl. The proof is a simultaneous induction of the following claims: I n Given any cell X C Jin, and finite collection {Xi} of definable subsets of X, there is a (finite) partition of X into cells which partitions each Xi' l\n If X C Jtn is definable and / : X —* J£ a definable function, there is a partition of X into cells such that the restriction of / to each cell in the partition is continuous. IIIn Let X C Jtn be definable, and <p(x, y) a formula where x is an n-tuple. Then if for each a G Jtn, <p(a, Jt) is finite, the set {|y(a, JK)\ : a G Jtn} is bounded. Chapter 1. O-minimal structures 17 I V n Let X C Jtn be an open cell, and tp(x, y) a formula where x is an n- tuple. Then if for each a € JKn, ip{a, J() is finite, if the mappings x^mm{y:ip(x,y)} and x i-> max{y : tp(x, y)} are continuous, and if a is good for cp, for all a, € X, then \<p(ai,JZ)\ = \cp(a2,Ji)\(or all a,i,a,2 E JZ. The Base Case. First note that Ii follows from the definition of an o-minimal structure, and Hi follows from Lemma 1.1.5. Let us now show I V i . Assume that X = (a, b), each c e l i s good for <p, each ip(c, J£) is finite, and that fF(x) = mm{y : ip(x,y)} and fL(x) = max{y : ip(x,y)} are continuous. If the statement is false, then there is some k € u for which the set X\ = {c : 3=kytp(c, y)} is non-empty, but not all of X. Let c € X be a boundary point of X\. Our aim is to show that c is not good for </?, which contradicts an hypothesis. Let (p(c,Ji) = {do, ...,dN}, where di < a\+i- We may inductively choose disjoint intervals JQ,...,JN, such that dj 6 Ji for all i, and an interval I containing c, such that for each i, ip(Ji) n (7 x Jj) is the graph of the continuous function Qi : I —> Ji. So for all del, \ip(d, J/)\ ^ N. If there were an interval I' QI containing c such that for all d G I', \ip(d, J()\ = N, Chapter 1. O-minimal structures 18 then we would have J ' n X i 7̂ 0, whence N — k, whence c is interior to X\, not a boundary point. As {d : ]<p(d, J/)\ = N} is definable, there must be an interval to the left or right of c which is not contained in it. Suppose, without loss of generality, that there is an interval / ' on the right of c with Vd-el',\ip(d,je)\ >N. (*) Set JV g(x) = min{y : <p(x,y) A f\y # By * and by the fact that ip(d, JZ) is finite for all d € X, g is defined (and definable) on /' . As fp < g < fh on lima,_).c+ 5(0;) exists, say d. If ->y?(c, d), then c is not good for ip as any box containing (c, d) also contains part of the graph of g. If <p(c, d) then d = dj for some i But p gi, and lim;i._^c+ Pi(a;) = limx_>c+ p(x), so no box about (c, d) intersects ip(Jt) as the graph of a contin- uous function. Finally, we will prove I I I i . Let X, tp be as in the statement. Note that we can get away with proving the statement for each of the cells in some finite decomposition of X, as the maximum of the uniform bounds on the sizes of fibres on each cell in the decomposition will serve as a bound on the sizes of the fibres over all of X. If X is a singleton the result is trivial, so let X = ( a , b), where we may have a, b — ±00. We may assume, by I i and the above remark, that X = dom(ip), and so fp and fr, are defined. By Hi we may also assume that these two functions are continuous. Let Y be the (definable) set of points which are not good for <p. If Y = { a n , a n } then on each interval (a^, 04+1), where a _ i = a and an+i = b, the size of the fibres of ip is a constant by I V i , Chapter 1. O-minimal structures 19 and so we are done. We shall prove, by contradiction, that Y is indeed finite. Suppose that ( 0 1 , 6 1 ) C Y. We say that (c,d) € JI2 is type I nasty for ip if tp(c, d) and for all boxes B about (c, d), tp(JC) D B is not the graph of a continuous function. We say that (c, d) is h/pe 77 nasty for <p if -icp(c, d) and for all boxes B about (c, d), 75 fl ip(^) 7̂ 0. Thus for each c eY there is at least one d such that (c, d) is nasty for tp (type I or II). Claim. For all c e ( 0 1 , 6 1 ) r/zere is fl /eflsf d e JC such that (c, d) is nasty for tp. Proof of the claim. As we are assuming that tp has finite fibres on X, tp may only have finitely many type I nasty points for each c, thus it remains only to show that if (di, d 2) is an interval such that for all d € (di, d 2), (c, d) is type II nasty for tp then (c, di) is nasty (type I or II) as well. First we establish that di is, in fact, finite. If not, let ao > 0 1 > ... be elements of (—00, d 2), decreasing without bound. We may inductively construct boxes B{ about (c, a*) with Bi n Bj = 0 whenever i ^ j and, as tp(J{) fl Bi ^ 0 for all i, conclude that tp(c, JK) ~D (—00, a) for some a. But then cp(c, ^#) is not finite. If ->tp(c, di) then let B be a box containing (c, di). Of course, B contains (c, d) for some d e (di,d2), and so, by hypothesis, tp(J/) n £ / 0. On the other hand, if </?(c, di) then take I and J to be intervals containing c and di respectively. If (7 x J) D tp(J%) = T(f) for some continuous / : 7 —• J , let d' .€ (di, d 2). For any box B C (7 x J) containing (c, d'), T(/) n 73 7̂ 0. Thus limx^c f(x) = d'. But d' was arbitrary, contradicting the uniqueness of limits. Thus (7 x J)C\tp(JK) is not the graph of a continuous function, and again (c, d) is nasty for tp. • Chapter 1. O-minimal structures 20 Let min{d : (x, d) is nasty for <p} 9i{x) max{y : (p{x,y) Ay < g(x)} 92{x) min{y : ip(x,y) Ay > g(x)}, allowing g\ and g2 to take the values —co, oo when undefined. By applying H i , we may refine our interval to one on which g, g\, and gi are continuous (or ±00, in the latter two cases). Suppose that there is a sub-interval / of this interval such that for all eel, (c, g(c)) is type I nasty. Fix some eel, and choose d i , d 2 such that g\(c) < d\ < g(c) < d<i < 52(c). By the continuity of these functions on this interval, we may choose a sub-interval / ' such that for all x e I', gi(x) < di < g(x) < d 2 < gi{x). But then (/' x (di,d 2 )) n tp(JS) = T{tg), which is a contradiction. So suppose that there is a sub-interval J such that for all eel, (c, g(c)) is type II nasty3. Construct c, d i , d2, and I' as above. To prove the inductive step we require the following, useful, lemma: Lemma 1.3.1. Let C C J£n be a cell, k = dim(C) ^ 1. Then there is a cell C C J£k definably homeomorphic toC. Proof. If n = 1 the result is trivial. Suppose that C i C Jtn is a cell, suppose that / : C i —> J( is continuous and definable, and let C* = T(f). Let h:C\^> C* be given by h(x) = (x, f(x)). Then clearly h is a bijection. Also, if B is an open box about some x € Jin, and / C JZ is an open interval containing 3There must be one or the other, as nastiness is definable. Then (/' x {di,d2))n<p(JZ) = $. a Chapter 1. O-minimal structures 21 f(x), then h~1(B x I) = B(~\f x(7) is open. Conversely, 1 is continuous as h(B) = (B x JT) n Now suppose that C* = (/, g), where f,g : C\ Jt are continuous and definable {C\ a cell), and suppose that h : C\ —> C2 is a definable homeomor- phism. Then define h* : (f,g) —> ^#n + 1 by (x, y) »-»• (/i(x),y). Again, this is clearly a bijection from (/, g) onto ( / o h'1, g o hr1). If B x 7 C (/, then x I) = h(B) x 7, and vice versa, so /i* is a homeomorphism. The lemma follows. • The Inductive Case. In light of Lemma 1.3.1, and the observation that cell de- compositions will carry through a definable homeomorphism, we can as- sume that the statement I n holds for any cell X with dimension less than n. So suppose X — (f,g), where / , g : X* —> J£ are continuous and de- finable, X* a cell in J£n-X. For a given Xt C X, let X* C X* be the pro- jection of Xi. We may choose some partition {Cj} of X* which partitions each XI. Let Cj = (/ \ C*,g \ C*) for each j. Fix some C = Cj and let r = {i:X*nc*^<b}. Claim. If C is open then it admits a partition partitioning each Xi, % e I'. Proof of the claim. Let (X)a = {b e Jt: (a, b) e X} for all definable sets X. By the induction hypothesis, the boundary of (Xi)a is uniformly finite. By using cell decomposition for Jt', we can clearly assume that each (Xi)a (as a ranges through JZn~l) is of the same type4. Let / / (a ) , / f* (a ) be the boundary points of (Xj) a and, again using cell decomposition at lower levels, assume 'Here type refers to the set's representation as a union of points and intervals. Chapter 1. O-minimal structures 22 that the set of functions {// : 1 <: ^ j ^ h} can be rewritten as a sequence gi < g2 <•••.< 9k- Note that each of these functions is definable. One more application of the induction hypothesis allows us to assume that each is continuous on its domain, and then k • k U(gi\C,gi+- \C)u\jT(9i), i=0 i = l where go = f and gu+\ = g, is a cell decomposition of C partitioning each Xir ie I'. . . • The result follows by the fact that the non-open cells are of dimension at most n — 1. In order to prove IIn, suppose X C J6n is a cell and / : X —• Jt a definable function. Again, if X has dimension less that n a definable home- omorphism with a cell in JZn~- shows the result. So assume X is open, and set Xi = {(a, b) € X : f(xi,xn-\,b) is cts on some box Bad with B x {b} C X) X2 — {(a, b) 6 X : /(a, xn) is constant or a monotone bijection on some interval I 3b with {a} x I C X}. Let ^ be a cell decomposition of X which partitions both X\ and X2, and let C £ ^ be open. We intend to prove that / \ C is continuous. Suppose C = (/i,/2) for some / i , / 2 : C* -> Jt. If (a,b) € C then /(xi, ...,xn-i,b) is defined on some open subset of C*. By the induction hypothesis, there is ah open cell D C C* such that f(x, b) is continuous of D. Now, if a' e D, Chapter 1. O-minimal structures 23 (a1, b) E X\. Since X\ n C j- 0, we have C C X\. A similar proof shows that C C X 2 . Now, if f(a, x) is not constant or a monotone bijection on (/i(a), /2(a))/ the let /i(a) < 61 < ... < 6 m < /2(a) be the points shown to exist in the monotonicity lemma, with m minimal. Then there can be no / 3 b\ with f(a, x) constant or a monotone bijection on / , so (a, b\) g X2. But C C X 2 , so this is impossible. Let (a, 6) € C, and let J 3 f(a, b). We want to find an open box about (a, b) which / maps into J . We can find a closed interval J = [bi, b2] C (/i(a), /2(a)) such that /(a, J) C J by continuity. As (a, 61), (a, fe2) G X i we can find open boxes Bi and B2 with /(5i,fei) C J and f(B2,b2) C J . Let £?' = Bi n 5 2 . Then 5' x int(J) C C. Also, if (a', b') e B' x I, we have /(a', b') G J as f(a',bi),f(a',b2) G J and /(a', x) is constant or monotone on I. Thus / is continuous on every open cell in & , and is continuous on every other cell as well (by the induction hypothesis). To show III n, let <p(x\,xn, y) be a formula (with parameters from J{) and X C Jtn an open cell. Suppose <p is finite on X, and let Xi = {(a, 6) G X : a is good for (p(xi,...,xn--,b,y)} ' X2 = {(a, b) € X : bis good for <̂ (a, x n, y)}. Again let & be a cell decomposition of X partitioning both X i and X 2 , and let C G ^ be open. We shall show that C C Xx n X 2 . Let B C C be an open box, (a, 6) G £?, and B* C J(n~- be its projection. Then ip(xi,xn-i, fe, y) is uniformly finite on B*. By cell decomposition, pick Chapter 1. O-minimal structures 24 some open cell D C B* such that for all a! G D, \<p(a', b, Jt)\ = k and such that the first, second,fcth points functions are continuous. Clearly if a! G D, then a' is good for tp(x, 6, y), so (a', b) G X\. But then C C X j , The proof is the same to show that C C I 2 . The following claim proves IIIn. It also finishes the theorem, as the as- sumptions of IV n imply X — X\ = X2. Claim. If C C X is an open cell and C C X\ n Xi then for all c~uc<i G C, \(p(5i,J?)\ = \(p(c2,J?)\. Proof of the claim. Suppose that for some k < to, Ck = {c G Y : \(p(c, ^#)| = k} is a nonempty, proper subset of C. Then there is a boundary point c of Cfc in C. Let B be an open box in C containing c, choose (ai, 6i), (a2) 62) G B , and let B * be the projection of B (in ^ n _ 1 ) . By hypothesis every a G B * is good for <p(x, 6i, y), and so |cp(ai,6i,^#)| = \ip(a2,bi,^)\, by I V n _ i . Similarly, by IVi, \<p(a2,bi,JK)\ = \(p(a2,b2,J?)\. But then B cannot contain both points in Ck and points not in Ck- • • 1.4 Algebraic structures In Section 1.2 we saw that the field of real numbers, and hence the ordered group of real numbers, is o-minimal. Here we will see that these are, from the Chapter 1. O-minimal structures 25 view point of first order logic, the only o-minimal ordered rings and groups. For the remainder of this section we will lift the restriction that ordered struc- tures have a dense underlying order. The structures below are only assumed to be ordered linearly. Theorem 1.4.1. Let $ be an o-minimal ordered group. Then & is abelian and divis- ible. In particular, <S = (R, <, +). Proof. We will prove that §f must be abelian and divisible, and let folklore take care of the completeness of these axioms (see, e.g., [Hod93]). The key is that if H C <g is a definable subgroup, then H is trivial. If H / {0}, let h > 0 be in H. If there is some g e (0,h)\H then nh € H for all n, and g + nhg H for all n, but ... < nh < g + nh< (n + l)h < g + (n + l)h < ..., so H must have infinitely many connected components, which is impossible. Thus H is connected. Now let h = sup(/f), and suppose that h < oo. Clearly we cannot have h e H, or 2h <I h as 2h € H, whence h < 0. So h H. Let 0 < g < h, so that g G H. Then 0 < h - g < h, and so h - g € H. But this would mean that (h - g) + g = h e H, which is a contradiction. So h = oo, and consequently H = We can now easily show that is abelian and divisible simply by noting that the centralizer of any element of <S is a nontrivial definable subgroup of as is n£f, for each n. • Theorem 1.4.2. Let & bean o-minimal ordered ring. Then ̂ is a real closed field (and hence £$ = (R, +, •)). Chapter 1. O-minimal structures 26 To prove this we will need a version of the intermediate value property that will hold in all o-minimal structures. Definition 1.4.1. Let J( be a structure, and X C J{n be a definable set. X is said to be definably connected if there do not exist two open, definable sets U and V not disjoint from X such that X C U U V, but X n Z7 n V = 0. It should be noted right away that open and closed intervals are definably connected, even though they may not be connected. The interval (0,1) in (Q, <) is diconnected by the open sets (0, l/7r) n Q and (1/7T, 1) D Q, but any definable pair of open subsets of (0,1) would themselves have to be finite unions of open intervals, and so could not disjointly cover (0,1). Lemma 1.4.3. If X C J{n is definable and definably connected, Y C JSm is de- finable, and f : X —> Y is definable, continuous, and surjective, then Y is definably connected. Proof. The standard topological proof works, just noting that the inverse im- age of a definable set by a definable map is definable. • Proof of Theorem 1.4.2. It was shown above that (Si, <, +) must be an abelian group. Also, if x € Si, xS% is a subgroup of the additive group of Si, and so is the entire group. This implies that Si has inverses and an indentity. Now consider the group $ whose underlying set is {x €. Si : x > 0}, and whose op- eration is the multiplication operation in Si. The sets definable in this group are clearly all definable in the ring SS, so is an o-minimal ordered group. Thus Si is a field. Now all that needs to be shown is that every polynomial assuming both positive and negative values has a root. But it is clear that any Chapter 1. O-minimal structures 27 f e @[x] is definable and continuous. If /(a) < 0 and f(b) > 0 suppose, w.l.o.g., that a < b. Then, as (a, b) is definably connected, the image under / of (a, b) must also be, and so / has a root. • 1.5 Prime models For the remainder of the section we fix some o-minimal L-theory T. Definition 1.5.1. A model Jt |= T is prime over the set A C J£ if whenever there is an elementary map of A into J/ |= T, the map can be extended to an elementary embedding of Jt into JV. The existence and uniqueness of prime models over arbitrary sets, demon- strated in [PS86], shows a strong similarity between o-minimal structures and strongly minimal structures. The proof presented here is much simpler and, we feel, more intuitive than the original, but requires an extra hypothesis. Theorem 1.5.1. IfJ( (= T and there are ^-definable functions f : Jt"1 —> Jt and g : Jt —» J( satisfying \/xVy{x < y -> x < f(x, y) <y) Vx(g(x) > x) then there is, for any nonempty A C Ji', a unique prime model over A. The hypothesis above requires that we have Skolem functions demon- strating the order type of the structure. The added hypothesis does not weigh us down too much, however, as any group satisfies this requirement (using f(x,y) = (x + y)/2, g(x)=x + l). Chapter 1. O-minimal structures 28 Proof. Let T have the special property above. For the remainder of this proof, an o-minimal theory will be called regular if every 0-definable n-ary partial function definable in T is already represented by a function symbol in L. Of course, if T is not regular, we may expand the language to a new one L* which contains a function symbol for every 0-definable function, and extend T and its models in a unique way to L* structures. It is clear that the concepts of elementary embeddings, isomorphisms, et cetera are not changed by doing this. The concepts of embedding and substructure, however, are. Claim. Let J? \= T and let Ji Ji (not necessarily a model ofT). Then ifT is regular, Ji -4 Ji. Proof of the claim. By the Tarski-Vaught criterion, we must check that if <p(x, y) is an L-formula (without parameters) and a G Ji with Ji |= 3y(p(a, y) then there is a d G Ji with Ji |= (p(a,d). Suppose Ji \= 3y<p(a,,y). By o- minimality, X — (p(a, Ji) is a finite union of points and intervals. Sup- pose that 'mi(X) is in X, and let ip(x,y) = "y = m({z : ip(x, z)}". Clearly ip defines a function (where it is defined), and so there is an n-ary function symbol such that fy(x) = y <-> ip(x,y). As Ji <; Ji, f^(a) G Ji. But Ji f= <p(a, fxj;(a)). Now suppose that inf(X) is not in X. Then set ip(x, y) as above, and x(x,y) = "y = sup{2 : (U(x),z) C X)}". Then both b = fo(a) and c = fx(a) are in Ji. As Ji is a dense order (by our added hypothesis), let d G (b, c) n Ji. Then d G (6, c) = (U{a), fx(a)) C X , and ̂ |= <p(a, d). • Now assume T is regular, let A C. Ji \= T, let be the substructure of Ji generated by A, and let Ji be a structure into which A may be elemen- Chapter 1. O-minimal structures 29 tarily mapped. Without loss of generality, we can assume that A C j/. Then srf < Ji, and so $4 ^ jV. For uniqueness, suppose SB is another structure prime over A, A C S8. Then, again, -4 SB. Let / : ^ —> ^ be an elemen- tary embedding fixing A. Then / must also fix the structure generated by A, namely srf. So we have srf = SB. • Note that the claim in the proof is not true if the special assumption is dropped. In particular, if f(x) — x, the theory of (Q, <, / ) is regular. We may use similar ideas to prove the following useful lemma which will be needed in Chapter 2: Lemma 1.5.2. Let M be an o-minimal expansion of a group, and let ~ be a de- finable equivalence relation on some definable X C JKn. Then there is a definable transversal for X, that is, a function f : X —• X such that x ~ y <-> f(x) = f(y). Proof. We will deal first with the case where n = 1, X = Jt'. For each x, let 5a; =. {y : x ~ y}, ax = inf5 x, and bx = sup{y : (ax,y) C Sx}, and let c > 0 be an arbitrary point. We will define f(x) as follows if ax -£ —oo: if ax ~ x then f(x) = ax; if ax x and bx < oo, /(s) = (ax + &x)/2; if frx = oo, f(x) = a x + c. If ax is —oo, we define f(x) by: if 6̂ 7̂ 00, f(x) = bx — c; if 6X = 00, f(x) — c. It has been engineered such that f(x) ~ x for all x. It is also clear that f(x) = f(y) +-> x ~ y, as x ~ y <-> Sx = Sy. If X is a proper subset of J( we may extend ~ to the rest of Jt by setting Sx = {x} for a: € Jt \ X. If n > 1 we may use the same definition of f(x) using the lexicographical ordering. • Chapter 2 The real numbers One of the goals of this chapter is to examine reducts of the field of real num- bers. In particular, we will outline the work leading to the classification of all reducts of this structure. We will also look at some important o-minimal expansions of the reals. We begin, however, with a justification of our focus on the real numbers. 2.1 Archimedean ordered groups Recall that an ordered group <£ is Archimedean if for any gi,g2 S where gi > 0, there is a natural number n such that ngi > g2. It is well known that any abelian Archimedean ordered group may be embedded into the group of real numbers. Laskowski and Steinhorn [LS95] extended this result using the strong structure of o-mirumal ordered groups. Theorem 2.1.1. Let Ji be an o-minimal expansion of an Archimedean ordered group. Then Ji can be elementarily embedded in an o-minimal expansion of the group (S,<,+,0). In fact, if c € Ji is positive, we will construct a'unique elementary em- 30 Chapter 2. The real numbers 31 bedding of (Ji, c) into a unique expansion of (R, <, +, 0,1). This has the im- portant consequence that, to study o-minimal expansions of Archimedean ordered groups, we need only study o-minimal expansions of the real group. Definition 2.1.1. For any structure Ji', let qf(Ji) be the set of elements of Ji definable over 0 by quantifier free formulas. An ordered structure Ji is standard if qf( Ji) is dense in Ji. • •• Lemma 2.1.2. Let& = (G, <, +, 0,1) be o-minimal. Then & is Archimedean if and only if it is standard. Proof. If we embed the rational numbers into in the canonical way, note that qf (&) = Q. Suppose Q is dense in , and let gx, g2 € <£, g\ > 0. If there is no positive integer m with g2 < m, then (52,00) n Q = 0, contradicting the hypothesis, so let g2 < m. By the density of the rationals, let 0 < | < g\ (where p and q are positive integers). From the Archimedean property of the integers, there is an n with qm < pn. Thus ^ < | < g\, and so g2 < m < ng\. Now suppose that <S is Archimedean, and let a < b be elements of §f. Also suppose, without loss of generality, that a > 0. Then there is some natural number n such that n(b—a) > 1, and thus 1+na < nb. Also, na > 0, so we may choose a natural number m with m—1 ^ na < m. Then na < m ^ na+1 < nb, so a < ^ < b, as desired. • Notice that if Ji and Ji are elementarily equivalent, there is a unique elementary map fo : qi( Ji) —* qf(Ji). Chapter 2. The real numbers 32 Lemma 2.1.3. If Jt and J/ are elementarily equivalent and o-minimal, fo is the map above, and J/ is standard, then an order preserving map f : —> extend- ing fo is an elementary embedding. Proof. Note that / would be trivially injective, and unique by the density of qf(J/). All that remains to be shown is that if ip(x) is any formula (without parameters), and a G Jt', then Jt \= <p(a) implies J/ (= tp(f(a)). We will proceed by induction on n, the number of free variables in ip. If n = 0, the claim reduces to Jif = J/. Suppose the remark is true for all formulae with at most n free variables, and let <p(x,y) have n + 1. As a first case, suppose that <p(Jf,b) is a sin- gleton, {a}. Then, by the induction hypothesis on 3=1xip(x, y), <p(<sV,f(b)) is a singleton. Suppose c € J/, and c < f(a). Then, by the density of qf(^K), let q € qf(^) D (c,/(a)). As q < /(a), q* < a, where by qM we mean the interpretation of q in Jt. If ib(x) is a quantifier (and parameter) free formula defining q, then, Jt f= -<3x3y(x < y A ip(y) A y?(x, 6)). But then J/ |= -i3a;3y(x < y A >̂(y) A y>(a;, f(b))) by the induction hypothesis, and so Jf |= -iy?(c,/(&)). Similarly, if /(a) < c, •/K |= -np(c, f(b)), and so we must have ^h</>( / (a) , / (b)) . Now suppose that ip(J?, b) defines an interval (oi, a2) in Ji. Let i/>i(x, b) say that x is the infimum of realizations of <p(JK,b), and ip2(x,b) that x is the supremum. By the above, applied to ipi and tp2, /(^l) is the infimum of 'ip(Jr', f(b)), and f{a2) the supremum. But ^ |= \/xVy\/z((x < y < z A y>(x, b) A <p(z, b)) —> </?(y, 6)) Chapter 2. The real numbers 33 so by the induction hypothesis JT VxVyVz((z < y < z A <p(x, /(&)) A <p(z, /(&))) -> <p(y, /(&))), whence <p(Ji, f(b)) is convex, and equal to (/(ai), /(a2)). By the order pre- serving property, then, #̂ |= </?(a, 6) implies (= ip(f(a), /(b)). Finally, let (p(Ji,b) be any finite union of points and intervals, defined by V î(£> b),ip2(x, b),..., f̂c(a;, 5). By the induction hypothesis, <p(</K, f(b)) is the union of the sets defined by ip\(x, f(b)),ipk(x, f(b)), and by the above work, Ji |= t/>i(a, b) if and only if Ji |= ^(/(a), / ( & ) ) , for each i So we are done. • Definition 2.1.2. A type p € is an irrational cut if C = {c: (c<x) e p(x)} is a nonprincipal Dedekind cut, that is, if C has no least upper bound. Any other nonprincipal type in S\(Ji) is a noncut. A type p E S\(Ji) is uniquely realizable if for any Ji !>= Ji and any a e p(Ji), p is realized by only a in some (the, up to isomorphism) prime model over Ji U {a}. The following lemma is from [Mar86]. Lemma 2.1.4. Suppose Ji is o-minimal, and p,q e Si (Ji) (not necessarily dis- tinct). If Ji' :>= Ji is a model prime over a realization a ofp and b € q(Ji') is not a then there is an Ji-definable function f such that f(a)^a realizes q. Proof. The Omitting Types Theorem (see [Hod93]) shows that b must realize an atomic type1 over Ji U {a}, and so (by o-minimality) we must have either l A type in which one formula implies all others. Chapter 2. The real numbers 34 b E dcl(^# U {a}) or there is some J£ U {a}-atomic interval (Pi, fo) containing b. In the latter case, note that Pi, 81, and b must all realize the same type over Jt. Otherwise there is some ̂ -definable interval I C (81,82), contradicting either the atomicity of (Pi, 62) in JV or the non-principality of q. Thus there is some realization of q in dcl(^# U {a}). But we cannot have either Pi or 82 definable over J£', ox Pi E and q is not a type. So without loss of generality, assume b E &c\(JZ U {a}) \ dcl(Jf). By the proof of the exchange law, we see that there is an ^-definable interval J and a function / : I —> Jt' such that f(a) = b. • In the above we can, of course, assume that / is a bijection preserving or reversing order by the monotonicity lemma. Lemma 2.1.5. Let Jt be an o-minimal structure on a dense subset ofR (with the usual ordering), and suppose that every irrational cut in JC is uniquely realizable. Then Jthasa unique extension to R. Proof. We use Zorn's lemma. Let Jt =<: JV c R, and let a e R \ JV. We claim that the prime model JV' over JV U {a} may be (order) embedded in R over JV. If this is true, then any maximal elementary extension of Jt on a subset of R must have all of R as its underlying set. The uniqueness is then not hard to prove. Claim. Let JV and JV' be as above. Then JV' realizes no non-cut q over JV. Proof of the claim. Suppose JV' realizes some non-cut q E S\(JV). By Lemma 2.1.4 there is an ,/K-definable function / : I —* JV' such that f(a) realizes q. Chapter 2. The real numbers 35 Case 1: q = {"n < x < rq" : m < rq,n € JY} for some rq G JY. Without loss of generality, assume that / is increasing, and let I = (a, 8) (where a, 8 € . JY). As / is ^-definable and rg € JY', let c € JY satisfy a < c < Then JY, and so JY', models Vx(a < x < c —»• f(x) < / (c ) < q). But a < c, and so / (a ) < / (c) < g, and so it is false that g(/(a)). Case 2: q = {"n < x" : n € JY}. Again assume that / is increasing, and let I = (a, 3). Again, as p is a cut, pick some c € {a, 3) fl JY. Because / is increasing, JY (and hence JY') models Va;(a < x < c —> / ( x ) < / (c)) . But then f(a) cannot realize q. The other two cases (for the other two types of noncut) are the same. • The following is assumed without mention in [LS95], but we feel that it is not trivial, and warrants proof. Claim. Suppose Then every cut in JY is uniquely realizable. Proof of the claim. First we prove that if J/[ has this property, then a model JY2 prime over a realization of some cutp € S\(JY\) has the property as well. Let a € p(JY2), and let b € JY2 \ JY\. Then, using Lemma 2.1.4 we can find a function / such that / is a bijection between realizations of p and realization of the type of b over JY\. In particular, as a is the only realization of p, b is the only realization of its type, f(a) = b, and b G d c ^ ^ U {a}). Now let JY% be the prime model over JY2 U {&}, and let there be another realization in JY% of the type of b over JY2. Then we can find a function f2 such that f2(b) ^ b realizes this type. As f2 is definable over JY2 = dc\(JYi U {a}) we can find a function g(x, y) such that g(a, y) = f2(y). Assume (by refining if necessary) Chapter 2. The real numbers 36 thatg(x,y) / y. Then set h(x) = f~log(x, f(x)). We can see that his Aj.U{a}- definable, and that h(a) / f(a) = b are two distinct realizations of t p ( 6 / ^ i ) - This is a contradiction. By induction, if A C R is a finite set then the prime model over JZ U A has the property in question. Now, suppose / ^ / C M has a cut p which is not uniquely realizable. Again, there is an ^-definable function / such that in any JV' J/, if p(a) then p(f{a)) (/(a) ^ a). Let A C R be a minimal set of parameters used to define / . As A is finite, the prime model over JZ U A has uniquely realizable cuts. But / contradicts this, by the density of JZ in R. • So now we are essentially done. If JZ J/ C R then we have shown that the prime model over J/ realizes only cuts, and realizes them uniquely. Each cut p over J/ can be realized by a unique real r, specifically the supremum of {c : c <x €. p(x)}. Now let and £%i be two elementary expansions of JZ to R, and let @[ = (Mi, a : a € JZ). Then clearly M[ = &2 and both are standard. By Lemma 2.1.3, applied to the identity map from JZ to JZ, we have that ^ 1 = ^ 2 - • Lemma 2.1.6. Let JZ be an o-minimal expansion of& = (G, <, +, 0,1). Then <S is Archimedean if and only if every irrational cut in JZ is uniquely realizable. Proof. First we will assume that is Archimedean, and suppose that the cut p G Si (JZ) is not uniquely realizable. Let / : J —»I be the function described in Lemma 2.1.4 and assume, without loss of generality, that / is increasing. Chapter 2. The real numbers 37 Set g(x) = f{x) — x. We can assume again, without loss of generality, that gix) > 0 on J. Let C = {c G JZ': c < x G p(x)}. Claim. For all e > 0 there isac G C such that x > c implies g(x) < e. This claim clearly implies that for all x £ C, g(x) ^ 0, which is a contra- diction. Proof of the claim. Let e > 0 and let cn G C be arbitrary. As <£ is Archimedean, let n G u be the least n such that CQ + (ra + l)e 0 C. Since we must have f(C) C C, x > co + ne —> 5(2;) < e, or else /(a;) — x = g(x) ^ e, and so / ( x ) ^ x + £ ^ C . • Now suppose that is not Archimedean, and select a > 0 and 6 > 0 such that b < na for no n G w. Now let C = {na : n G w}, and let p be the cut determined by C, i.e., the unique type extending {c < x : c € C}. We can see that p is a cut, and not a non-cut, as if x < d G p(x), X < d — a is as well. But if p is realized by d in some extension of J£', p is also realized by a + d, and so p is not a uniquely realizable type. • This proves the Theorem 2.1.1. If Jt = (JZ, +, <, 0,1,...) is as in the the- orem, and JV — (JZ, +, <, 0,1) is the reduct of JZ to the language of groups, then JY = (R, +, <, 0,1) as both are divisible, abelian ordered groups on dense linear orderings. By quantifier elimination, qf(JV) = {q • 1 : q G Q}, and so the unique order-preserving extension of fo(q -1) = q is an elementary embedding / of JV into (R, +, <, 0,1). If JZ' is the expansion of the image Chapter 2. The real numbers 38 f(Ji) which is isomorphic to Ji', Lemma 2.1.6 and Lemma 2.1.5 give us an elementary extension of Ji' to M. 2.2 Semi l inear and semibounded sets We will be viewing the real numbers in several different ways: as a group, a vector space, a field, or a few other, unnamed, structures. We will always, however, include the order on R, and use properties of o-minimality. Let Jz? be the structure (R, <, +, 0,1, A a : a € R) , where Aa(x) = ax. This is the set of real numbers viewed as an ordered vector space over the field of real numbers. One can look at the additive group of real numbers as the vector space of real numbers over the field of rationals. Definition 2.2.1. A set X C R n is semilinear if it is definable in . Theorem 2.2.1. J£ is exactly the structure generated on R by the sets • {x€Rn :^2aiXi = b}, as b and the ai run through R. Proof. One direction is trivial. The other direction requires a quantifier elimi- nation result. For an arbitrary subfield2 F C R, let 2> be the axioms for the group (R, +, 0,1, <) plus the universal closures of the following axioms: VI \a(x + y) = \a(x)+\a(y) 2 We are proving a more general result which will be used later. Chapter 2. The real numbers 39 V2 Xa+b(x) = Xa(x) + Xb{x) V3 Xab(x) = Xa(Xb(x)) for all a, b € F. We now suppose we have some Ji |= Tp and some Ji ^ Ji. As the additional axioms here are universal, Ji \= Tp. Now suppose Ji ^ ^K, Ji (= I > , and </?(x) is a quantifier free formula with parameters from Ji with <p(Ji) 7^ 0. As in the proof in Section 1.2, we will assume that ip(x) is a conjunction of atomic formulas of the form Xa(x) + b = 0 or Xa(x) + 6 > 0. Of course, if there are any formulas of the first form then f(Ji) = <p(Ji) as, if x 6 ip(Ji),x = A_1/0(fe) € Butthesetof solutions to a system of equations of the second form will be an interval with endpoints in Ji, and so again we have <p(Ji) ^ 0. So Tp is complete. Also, F, as a vector space over itself, must certainly embed into each model of Tp, so the theory admits elimination of quantifiers as well. Taking F = R we have the result we require. • It was conjectured by van den Dries that there is no structure properly in between (in the sense of reduction) and &. This question was answered negatively by Pillay, Steinhorn, and Scowcroft. Definition 2.2.2. Suppose X is definable in the structure (R, +, <, Bj : i € /), where {Bi : i G /} is the collection of all bounded subsets of R n for any n. Then we say that X is semibounded. We denote by SB the expansion of j£f generated by all bounded semialgebraic sets (that is, the structure whose definable sets are exactly the semibounded semialgebraic sets)3. 3Perhaps not a priori true, but true. Chapter 2. The real numbers 40 As we will see in subsequent sections, it is possible to characterize SB as the structure (R, +, *, <) where * is the restriction of multiplication to [0, l] 2 . In this language one can prove elimination of quantifiers, although we will not do so here. It is clear that SB is a proper expansion of .£? (by the quantifier elimination result above), but what is not clear is that SB is a proper reduct of This was shown by Pillay, Steinhorn, and Scowcroft in [PSS87]. The following result gives a simple proof. Once one has shown elimination of quantifiers (also in [PSS87]) it is simple to show directly that any curve (in R 2 ) definable in this structure is semilinear outside of some bounded set, which gives another proof that multiplication is not definable. Theorem 2.2.2. Let JZ J/ be two u-saturated o-minimal structures, and ipbea formula with parameters from JZ such that ip(JZ) = <p(JY). Then if X C tp(JZ), (JZ,X) 4 (JY,X). Notice that the above theorem does not assume that X has any nice prop- erties of its own. A lemma is needed: Lemma 2.2.3. Let JZ be an o-minimal structure, X an ̂ -definable subset of JZ, and a G JZn. Then there is some finite A C X such that whenever a and b share the same type over A, they share the same type over X. Proof. We will first assume that a is algebraically independent over X and show that if tp(a/0) = tp(6/0) then tp(a/X) = tp(b/X). We will derive the result from this. Let £(a) denote the length of the tuple a. We will proceed by induction on Chapter 2. The real n umbers 41 £(a). If £(a) = 1 then a is a single element a. Assuming that tp(a/0) = tp(6/0) we will show, now by induction on n, that for any formula ip with n + 1 free variables and no parameters, <p(a, c) *-> <p(b, c), Vc G Xn. Starring with n = 1, let C = {c G X : ip(a,c)}, and let C* = cl(C) \ int(C). Note that as X is 0-definable, both C and C* are {o}-definable. Suppose C* is not 0-definable. Then there is some d G C* such that d G acl(a) \ acl(0). Note that d cannot be in X* = c\(X) \ int(X), as this set is 0-definable and finite, so d G X. By the exchange law, a G acl(d). But this contradicts our assumption of algebraic independence as d G X. Thus C*, and so C, is 0- definable, and the statement holds for n = 1. Now suppose the statement holds for n, and let c G Xn+1, and let ip have n + 2 free variables. Again we assume that tp(a/0) = tp(6/0). Let C = {d G X : <p(a,c,c')}, and C* be as before. The points in C* are now {a, c}-definable. Suppose that there is some d G C* which is not {c}-definable. Then d G acl(a, c) \ acl(c). The exchange law says that a G acl(d, c) \ acl(c) C acl(X). Again this is a contradiction. So C is c-definable and, by the induction hypothesis, ip(a, c, c') <-> <p(b, c, c1). Now suppose that the result holds when £{a) = n, and let a, a' G ', al- gebraically independent over X. If tp(a, o'/0) = tp(6,6'/0) then the induction hypothesis tells us that tp(a/X) = tp(b/X). Then there is some elementary extension, say JY, of and an automorphism g of JY such that g(b) = a (see [Hod93]). So we need only prove that tp(a, a'/X) = tp(a, g(b')/X). But, adding new symbols to the language for a, this reduces to the previous case (where 1(a) = 1). Chapter 2. The real numbers 42 We will now show that, given any a G JZ and any 0-definable X C JZ there is some finite (possibly empty) A C JC such that a is algebraically inde- pendent over X in (JZ, A). The lemma will then follow as the type of d over A in JZ is the type of d over 0 in (JZ, A). Again we can proceed by induction on (.(d). If 1(d) = 1 and d = a is algebraically dependent over X, a G acl(X). By the properties of algebraic closure there is some finite A C X such that a € acl(yl). Now suppose the result is true for £(d) = n, and let a, a' G JZ. By the induction hypothesis there is some finite AQ C X such that d is inde- pendent over X in (JZ, AQ). If a, a' is independent over X in this structure then we are done. Otherwise, a' G acl(a U X). But then there is some finite Ai C (d U X) such that a' G ac l (^i ) . Let A = AQ U (AI D X) . • . Proof of Theorem 2.2.2. Let F be the set of functions from <p(JZ) U { a n , a ^ } C ^ to </?M0 U { 6 0 , C JY such that a. / is the identity on <p(JZ) b. tp(d/ip(JZ)) = tp(b/ip(JY)) c. V i , /(a*) = fej. We will show that, for every / G F and a' € JZ there is an extension g'€F of / such that a' G dom(g). We will also show that for every b' G JV there is an extension h G F of / such that b' G rng(/i). As the identity map on <p(JZ) demonstrates that F ^ 0, F forms a back and forth system4 which fixes X C ip(M), and consequently (̂ #, X) is elementarily embedded in (JY, X). . 4See[Hod93] Chapter 2. The real numbers 43 If a' G JZ, and / G F , we need to find a b' G JV such that tp(a, a'/(p(JZ)) = tp(b, b'/(p(JV)). By the lemma above, there is a finite yi C tp(JZ) = ip(JY) such that if tp(a, a'/A) = tp(c, c ' / A ) , tp(a, a'/<p(JV)) = tp(c, d/<p(JV)). As </K is w-saturated, we can find some b' £ J/ such that tp(b'/A U {fen, — , fefc}) = tp(a'/A U { a n , a * } ) , and we may extend / by adding the point (a', fe')- T h e construction of h is identical (resting on the cu-saturation of JZ). • By a pole in a structure 3% we mean a bijection between a bounded interval (an interval with endpoints in &) and an unbounded interval (an interval with an endpoint = ± o o ) . If a structure J ' o n R defines multiplication then it must define a pole, namely x t-> l/x (from (0,1) to (1, oo)). Corollary 2.2.4. If X C Rn is bounded then (R, +, 1, <, X ) de/i'rces no pole. Proof. Let be an ^-saturated extension of (R, +, 1, <) and JV = JZ x JZ equipped with the product group operation and lexicographical order. If we identify JZ and JZ x {0}, it is true that JZ ^> J/ (as both are divisible, abelian ordered groups and so eliminate quantifiers). It is simple to show that JZ is oi-saturated, in particular because it is definable in JZ. Now, if X is a bounded set, X C [—c, c ] n for some c G JZ. As JZ is an end-extension of JZ, the interval [—c, c] is the same in both structures, so (JZ, X) is elementarily equivalent to (JZ, X). But if (JZ, X) defines a pole, say f(x), (JZ, X) must as well. By the cell decomposition theorem we can assume that / is a decreasing bijection, and by scaling we may assume that / : (0, e) —> (a, oo), e < c. But then if a G JZ is larger than any element of JZ C J/, f~x(a) must be smaller than Chapter 2. The real numbers 44 any positive element of JY but still positive. This contradicts the fact that {x e JY : 0 < x < e} = {x € JY : 0 < x < e). • Strictly speaking, this does not prove our result. But building a similar end-extension of «£? and using the same proof we get our result. 2.3 Defining fields The goal of the next two sections is to prove that the only nontrivial reduct of & which properly expands Jzf is SS. In what follows we will need to know something about the smoothness of functions definable in o-minimal expansions of (M, +, <). Theorem 2.3.1 (Laskowski, Steinhorn [LS95]). Iff : (a, b) -> R is definable in some o-minimal expansion of (R, +, <) then f is piecezvise Cn,for all n. Proof. We define a sequence of functions by A°hf(x) - f(x) Akh+1f(x) = Akhf(x + h)-Akhf(x). Intuitively, Aklf(x) w hkf(k\x). We also define the formula $/,fc,a,6 to be VxV7i(a <x<x + kh<b-+ Akhf(x) > 0) V VxVfo(a <x<x + kh<b-+ Akhf(x) < 0). Chapter 2. The real numbers 45 It is a theorem of Boas and Widder [BW40] that if $ f}k,a,b holds, /(fc~2) exists and is continuous on (a, b). We will first show that there is a subinterval (c, d) of (a, 6) such that $ f j k ^ d . Let X = {(x, h) : x e (a, 6), fo € (0, (6 - x)/(n + 2))}, and let X+ = {(x,h)eX:An+2f(x)>0} X _ = {(x,fo) e X : A £ + 2 / ( x ) < 0}. By cell decomposition, there is a partition of X into cells which partitions both X + and X-. We can clearly find a cell which contains a subset of the form {{x, fo) : x e (c, d), fo G (0, c — x/(n + 2))} for some (c, d). So then $/,n+2,c,d- So now we know that the set on which / is not n-times differentiable is finite, or it would contain an interval and the above argument would show a contradiction. • We will also need to refer to the following theorem of semialgebraic geom- etry, by Pillay and Nesin [NP91]. By a one-dimensional semialgebraic field, we mean a field definable in & whose underlying set is one-dimensional. Theorem 2.3.2. Let F be a one-dimensional semialgebraic field. Then there is a semialgebraic isomorphism f : R -* F. Note that the theorem implies that a one-dimensional semialgebraic field is pure. If X C Fn is semialgebraic then f~l(X) C Rn is semialgebraic (as / is). But then X — f(f~1(X)) is definable in F, by / being an isomorphism. Chapter 2. The real numbers 46 In this section we will show that if a reduct of & is not a reduct of Jzf, one can use this structure define on an interval of R a real closed field (with the usual ordering). This field will allow us to construct all semibounded sets. We first need a reduction lemma. Lemma 2.3.3 (Laskowski, Steinhorn [LS95]). Suppose an o-minimal expansion SiofJif defines no function f : R —• R which is not semilinear. Then it defines no semialgebraic subsets of W1, for any n, which are not semilinear. Proof. By cell decomposition we need to show that every cell definable in Si is semilinear. It suffices to show that for every semilinear cell C and continu- ous, definable function / : C —• R, the graph of / is semilinear, and we will prove this by induction on the dimension of the cell. For zero-dimensional cells (singletons), the result is trivial. We saw in Chapter 1 that if C C R n is a semilinear cell then there is a semilinear cell in R d i m ( c ' ) to which C is semilin- early homeomorphic, so we need only prove our claim for open cells in R n . Assume the claim holds for all cells of dimension less than n, and let C C R n be an open cell, / : C —> R definable and continuous. Let B C R n _ 1 be an open box, and a, b € R such that B x (a, b) C C. Write / as f(x,y), and for each c € B let g5 — f(c,y). By the induction hypothesis, each gz is semilinear, or piecewise linear, on (a, 6). Let h(x) be the least d € (a, 6) such that g% is linear on (a, d). Again, h is semilinear by the induction hypothesis. So there is a Bo C B and a d € (a, b) such that each g5, c € Bo, is linear on (a, d). Let m(c) be the slope of g5. This is definable as £(<7c(<* + r) — gc{o)) for some fixed a G (a, d) and sufficiently small rational r. Again, m is semilinear. We reduce to a smaller box, B\ C BQ on which m is Chapter 2. The real numbers 47 linear, m(x) = 'Y^\ai(xi) + d. As <?g is linear on (a, d), we can find a definable function e such that 9x(y) = m(x)y + e(x). Consider the function k(x,y) = f(x,y) — \d{y) — e(x). This function, on Bi x (a, d) is definable and equal to (_̂ \aiXi)y. If oij ^ 0 for some i, then fc(0,0, A i / a i x , 0 , 0 , x) defines x i-> x 2 on some interval, contradicting the induction hypothesis. So m is constant on B\, and f(x, y) = Am(i) + e(x), and e is semilinear by the induction hypothesis, therefore / is semilinear. The above shows that given any open subset U of C there is an open sub- set of U on which / is semilinear. Using cell decomposition, then, there is a partition of C into cells such that on all open cells / is semilinear. On non- open cells the induction hypothesis applies. • Theorem 2.3.4 (Marker, Pillay, Peterzil [MPP92]). If X C R n is not semilinear then there is a real-closed field on some subinterval ofR whose ordering is the usual ordering and which is definable in (J?, X). To prove this theorem we will also need the following lemma on analytic functions: Lemma 2.3.5. Suppose f and g are analytic on {—a, a) and /(0) = g(0) — 0, /'(0) = g'(0) and /"(0) + 0. Then there is a 60 > 0 such that for all 6 e (0, <J0) there is an eo > 0 such that for all s € (0, £n) there is anx e (—6, S) such that f(x + e)=g(x) + f(e). Chapter 2. The real numbers 48 Proof of Theorem 2.3.4. We will assume that X is a curve, and in particular the null set of a nonlinear function F(x, y). We write F'(p), where p e R 2 , for the slope of F at p. Because F is a non-linear function, we can find an interval in the set of F'(p), and a rational number a such that F'{p) = a and F"(p) ^ 0. We may then translate F linearly that F(0,0) = 0, F'(0,0) = 0, F"(0,0) 0, and the range of F' contains an interval around 0. Using the implicit function theorem5 we may shrink to an interval (—a, a) on which X is the graph of some analytic function, g. By shrinking again if required, we can also assume that g' is an injection from (—a, a) into (-6, b) for some 0 < b < 1, g" ^ 0 on (-a, a). Claim. There is some c e (0, a) and two definable functions, A and M, such that for all x,y € (—c, c), g'(A(x,y)) = g'(x) + g'(y) • g'(M(x,y)) = g'(x)g'(y). Given the claim we will finish the result by defining a field of fractions using A and M. Let Z — {(a,b) € (—c,c)2 : b ^ 0}, and define (ao,&o) ~ (ai, 6i) if and only if M(ao, &i) = M(ai, OQ)- Let Y = Z/ ~ , let (a, 6) denote the residue of (a, 6) in Y, and define two operations on Y by (ao.bo) © <ai,6i> = (half(A(M(a0,&i), Af(<n,6o)),half(M(60,&i))>, {a0,b0)®(ai,bi) = (M(ao,ai),M(b0,bi)), 5See[Che01]. Chapter 2. The real numbers 49 where half (a;) is the unique y such that A(y, y) = x. Then (Y, ©, <g>) is a real closed field. To show this we will simply prove that o{(a,b))=g'{a)/g\b) is an isomorphism from (Y, ©, <g>) to (R, +, •). From this we can then use Lemma 1.5.2 to find a definable transversal for ~ in R 2 making (Y, ©, <g>) de- finable in (R, +, <, X). First we should note that {a, b) = (c, d) <-• Af (a, d) = M{c, b) ~ g'(M(a,d))=g'(M(c;d)) <- g'{a)g'{d) = g'{e)g'{d) ^ a{(a,b)) = a((c,d)). So a is well defined and injective. If we fix some 8 e (0, c), and 0 < x < 1, pick a such that g'(a) = xg'(8), and then cr((a, 8)) = x. If g'{8) < x, choose a so that g'(a) = ^g'(/3), and o((B, a)) — x. Thus, multiplying by —1 if required, a is onto. Notice that x = half (y) iff A(x, x) = y iff g'(x) = \g'(y)- Now, finally, Chapter 2. The real numbers 50 <7«ao,6o>® (ai,6i)) = a((M(a 0, ai), M(b0, h))) = P'(M(ao,a1))/5'(M(60,&i)) = (g'(ao)9'(a1))/(g'(b0)g'(b1)) = a({a0,b0))a((ai,bi)), a « a o , 6 o ) © ( a i , 6 i » = (^(A(M(a 0,6i),M(ai >6o))))/(^(6o,6i)) g'(ao)g'(b1)+g,(ai)g,(b0) = a{{ao,bo)) + a((ai,bi)). Now all that remains is to check the claim. Proof of the claim. Let c € (0, a) be small enough that for any u, v e (—c, c) there are y, z € (—a, a) such that g\u)+g'{v)=g'{y) g'(u)g'(v)=g'(z). For each a G (—c, c) let 3a = 9(x + a) -g{a). Then we want A{u, v) to be the unique w such that for all sufficiently small 8 and all sufficiently small e, gu + gv and gw+e have at least two points of intersection with ^-coordinate in (—6,6). So A(u, v) = w will be equivalent to the formula 3S0 > 0V<5 e (0,60)3e0 > OVe e (0, e0) ((gu + gv) fi gw+£ fl ((—5, (5) x R) contains ^ 2 points), Chapter 2. The real numbers 51 taking the functions to be set of ordered pairs. Our claim is, of course, that this w is precisely the w for which g'iu) + g'(v) = g'(w). Note that this is the unique w for which gu + gv and gw are tangential at 0. For any e, gw(x + e) - gw(e) = g(x + w + e) - g{w) - g(w + e)+ g{w) = gw+e(x). So Lemma 2.3.5 guarantees that w will satisfy the formula above, taking / = gw, 9 = 9u + 9v Now suppose z is some number other than w above. Then gu + gv is not tangential to gz, and so we can see that for small enough e, gu + gv and gz+e have only one point of intersection near 0. We can define M(u, v) in the same way, using gv o gu. • • Note in particular that if X is semialgebraic but not semilinear, we may define in (Jf,X) a real-closed field on some interval I C R . Every ]R-semi- algebraic subset of / must also be /-semialgebraic as / is a pure field. By linear translations we may construct in (JC, X) any bounded semialgebraic set. 2.4 Nonlinear structures Our next theorem towards this classification of reducts was shown by Peterzil [Pet92]. Theorem 2.4.1. Let C R 2 be a curve definable in some o-minimal expansion of Then ifctf\I is not semilinear for any bounded interval I C R, a bijection between a bounded and an unbounded interval is definable in (R, +, <, c€). Chapter 2. The real numbers 52 To prove this we will need a few lemmas about growth rates of real func- tions. We will say that / grows like g towards oo, denoted / ~ gr if Urn f(x)/g(x) = c^0. oo We will say that / grows less than g towards oo, / -C g, if lim f(x)/g(x) = 0. x—>oo Note that ~ is an equivalence relation and «l a partial ordering. Moreover, if / and g are definable in o-minimal structures, the monotonicity theorem OO OO oo gives us the trichotomy / < g, g < / , or / ~ g. Lemma 2.4.2. If I : (a, oo) —> R is definable in an o-minimal expansion of & and lim a ;_ ).oo l{x) — c then l im a ; _ 0 0 xl'(x) = 0 and l i m ^ o o x2l"(x) = 0. Proof Of course we are done if l'(x) = 0 eventually. We can assume, by the monotonicity theorem, that / and I1 are eventually strictly monotone (I' is also definable). By the mean value theorem, there is some yx €. (x, 2x) (for any x) such that l(2x) — l(x) = xl'(yx). Thus l i m ^ o o xl'(yx) — 0. By the eventual monotonicity of /' we have either xl'(x) < xl'(yx) < xl'(2x) or xl'(x) > xl'(yx) > xl'(2x) for large enough x. But l im^^oo xl'(x) = 2 limaj-^oo xl'(2x), so if the first limit is negative, so is l i m ^ o o xl'(yx), by the squeeze theorem. Similarly, the first limit cannot be positive. Thus l im x _»oo xl'(x) = 0. Chapter 2. The real numbers 53 Now we apply the above result to xZ'(x). This tells us that 0 = lim x(xl'(x))' x—»oo = lim x{l'(x) + xl"(x)) x—•OO = lim xl'(x) + lim x2l"(x), x—>oo a:—•oo and so we are done. • Lemma 2.4.3. Let f : (o, oo) —> R be definable in some o-minimal expansion of & and let a e Q. Then • if a ^ 0 and f ~ x a , then f{x + 1) - f(x) ~ xa~l OO OO , • iff < xa, then f{x + 1) - f(x) < a;"- 1 • iflim^oo f(x) = oo, a > 0, and xa < /, then f~l < x1^. Proof Let l(x) = f(x)/xa. By the mean value theorem we can find, for each x, a yx G (x, x + 1) such that / ( x + 1) - / ( x ) = f'(yx). Thus / ( x + l ) - / ( x ) = f ^ ) ^a—1 ^.a—1 ayrlKyx) + y^i'(yx) xa-l which tends to the same thing as al(yx) by the previous lemma and because yx/x —> 1. But in the first case al(yx) —> ac ^ 0 and in the second case od(yx) —* 0, so the first two statements are true. Chapter 2. The real numbers 54 Now notice that, in the third claim, as / is increasing, so is / 1 . Thus we have (under the hypothesis) 0 = lim - T - - T - x—>oo J[x) = lim (f-'wr lim X—+00 x 1/a and so we are done. • We may now complete the proof of the theorem. Proof cf Theorem 2.4.1. Let ̂ be non-linear outside of every bounded rectan- gle, as in the theorem. We may assume, without loss of generality, that "if is the graph of some eventually non-linear function / . We may also assume that / has no vertical or horizontal asymptotes, or the monotonicity theorem would allow us to find a bounded interval on which either / or / _ 1 would be a pole. As / is definable in an o-minimal expansion of the reals, we know that either /(x) ~ x , f(x) < x, or x < f(x). In the final case Lemma 2.4.3 allows us to conclude that f (x) <C x, so without loss of generality we may assume that one of the first two cases occurs. If f{x) ~ x , then Lemma 2.4.3 tells us that fix + 1) - fix) 22 x° = 1. Thus lim^oo fix + 1) - fix) = c ^ 0 . Suppose /(x + 1) - fix) is eventually constant. Then, fixing some XQ after which / (x+l)- /(x) is constant, we know that there is, by the mean value theorem, some yXo G (xo, xo + 1) such that fiVxo) = f(xo + l)-f(xo) = c. There is also some yXo+i 6 (x 0 + l , x 0 + 2) such that /'(j/xo+i) = c, and so on. As {x : f'(x) = c} is definable, and contains Chapter 2. The real numbers 55 arbitrarily large reals, / ' is eventually constant. But this contradicts the non- linearity of/. The f(x-rl)—f{x) is non-constant, and lima;_>00/(a;-|-l)—/(a;) = c, and so we have a horizontal asymptote. Now,if/(x) < x we have f(x+l)-f(x) < l ,solim a ; ^ 0 0 /(x + l ) - / (x) = 0. As above, f(x+\)—f(x) is not eventually constant, and so we are done. • With one further lemma this theorem will allow us to conclude that there is no proper reduct of & which properly expands SB. This lemma gives us insight into the structure of semibounded sets definable in a certain class of o-minimal structures. We say that an o-minimal structure satisfies the par- tition condition if for any ^-definable set I C R ™ there are disjoint analytic sets (perhaps not definable) Xi,...,Xn C X such that X \ ((J Xi) has no inte- rior in X. It is well known that & and (R, +, •,<,!!-> ex) satisfy the partition condition. Lemma 2.4.4 (Peterzil, [Pet92]). Let X be a definable in an o-minimal expansion of the reals satisfying the partition condition and suppose that every curve (in R 2 ) definable in (R, +, <, X) is semilinear outside of some rectangle. Then there are bounded sets B\,B^ and scalings A a i , A a f c definable in (R, +, <, X) such that X is definable in (R, +, <, A a i , A 0 j , Bi,Bk). In particular, X is semibounded. We know already that X being semibounded implies that every curve de- finable in (R, +,<,X) is semilinear outside of some rectangle. Otherwise, the lemma above would allow us to construct a pole from X, which is in turn constructed from a bounded set (or several bounded sets, but the difference is superficial) which would contradict an earlier result. So this lemma proves, Chapter 2. The real n umbers 56 for example, that the structure of semibounded semialgebraic sets is the same as the structure generated over by the bounded semialgebraic sets: if X is semialgebraic and semibounded then (R,+,<,X) is a reduct of J*", and the bounded sets needed to define X are definable in this reduct of It also proves that if X is not semibounded, then a curve such as that needed in the hypothesis of the lemma above is definable, offering a converse to the state- ment made above. Proof. In this proof we will treat tuples of reals as vectors to ease notation. In particular, if a, b are n-tuples, (a, b) = YA=I a A - A set X definable in an o-minimal expansion Si of (R, +, <) is said to be almost linear if there is a bounded Si-cell C and vectors ui, •..., ujj. e l " such that X = ^c + ^2tiVi:ti>(Ni,ceC^ (2.1) = C + span+{vi,...,vk}. If the vectors are linearly independent and the scalars representing each point are unique we say that X is in normal form. If X is as above, we let X be the set defined as in 2.1 but with the scalars possibly 0. If / : X —> R is a continuous function (and X is almost linear), we say that (X, f) is almost linear if / can be extended to / : X —• R in such a way that / is bounded on C and there are scalars a with j(c + Y,tiv?J =/(c) + (t,a>. Note that if (X, f) is almost linear, then the graph of / over X is almost linear, as exhibited by the cell C", the graph of / over C, and the vectors . u i ' , V k ' Chapter 2. The real numbers 57 which are obtained by concatenating Vi and Oj for each i, denoted (vi,a,i). Also, if Y is an almost linear subset of X then (Y, /) is also almost linear. Fix the structure Si meeting the conditions of the theorem. We will show that, if X is a cell, X can be written as a finite disjoint union of almost linear sets in normal form. This will, of course, cover the case of any definable set. We will prove this by induction on the n such that X C R n . If X is a bounded cell, then the statement is trivial. In particular, if X C R we need only consider the case where X = (a, oo) (or (—00, a)) in which case X = {a} + span+{l} (or {a} + span+{—1}). The induction step will be demonstrated modulo the following claim, which is the real content of the result. Claim. Suppose Y is almost linear in normal form, and f : Y —> R is definable and continuous. Then there is a partition Y\,Yk ofY such that (Yi, f) is almost linear6 for each i. Proceeding with the induction, suppose that the claim is true for all sub- sets of R n , and let X C R n + 1 . There are two cases for dim(X): If dim(X) < n + 1 then X is (up to permutation of co-ordinates) the graph of a continuous, definable function g on some cell 7 C R n . By the induction hypothesis and the claim, we may partition Y into almost linear sets in nor- mal form, and then partition those sets further until we have X represented as the union of the graphs of g over some Yi where each pair (Yi, g) is almost linear. If dim(X) = n+1 then X is the region between the graphs of two functions 6We will be sloppy with domains of functions in this proof. Chapter 2. The real numbers 58 g, h : Y —> R , where Y C R n is an open cell. By the induction hypothesis and the claim, we may partition Y = Y\ U ... U Yk such that (Yi, g) is almost linear for each i. We may then partition each Tj = y^i U ... U Yiti so that (Yitj, h) is. almost linear for all i, j. By the comment at the end of the first paragraph of this proof, (Yij,g) is still almost linear. So assume without loss of generality that Y = C + span+{?7i, . . . , « * } . g^c + Yl tiiJ^j = + h(^ + Y^Uvij =h(c) + (b,F) for some tuples o, b. Note that we are dropping the distinction between g and g. As 3 < h on Y, continuity tells us that g <: ft. on C. In fact, g <honC. This implies that ^ 6j for all i If <Xj = 6j for all i then X = C* + span+{(wi, a i ) , (v*, , ak)}, where C* is the cell between the graph of g and the graph of h over C. The new vectors are clearly linearly independent, as their projections to a lower dimension are. If (c, d) + _] = (c', a") + _] i ' ^ * for some c, d, etc, then, because Y is in normal form, c = c' and tj = t't for all i But then d + (£, a) = d' + (F, a), and so d = d'. Thus points in X have unique representation. If ai < bi for some % then we will re-arrange indices such that a^ < bi for alU <i I and ai = bi for all i > I. By definition, X = | (c + ^ I/) : 5 € C> *i > 0 V i> 2/ 6 (5(c) + (a, i), h(c) + (6, i » Chapter 2. The real numbers 59 We will definably split X into three pieces: X\, X2, X3. In each the defining condition will remain the same except for the range of ys. Xi = j (c + E y)-ceC,U> 0V», y e (h(c) + (a, t), fc(c) + (6, «>) | X 2 = | (c + ^ t i t ; i , y ) : c e C , ^ > 0 V t , y = Mc) + <5,t)| ^ 3 = | ( c +J^t<«i,y) : c E C,ti > m,y E (g(c) + {a,?),h(c) + (a,*))J . X2 is the graph of an almost linear function over Y and so is almost linear in normal form. Also, X3 is the case above. All that remains to be shown is that X\ can be written as an almost linear set in normal form. Let 2 = { £ ¥ i ) ! / ) : ! / e ( ( a ) i ) , ( M " ) ) , < i > 0 } . Then X\ is the graph of h over C shifted by Z. In particular, if Z is almost lin- ear in normal form, so is X\. Let d\ — ( a i , a 2 , a k ) = ( a i , . . . , a / . _ i , f y , •••,bk), ®2 — (ai, ^-2,^-1, f̂e) a n d so on. Then by construction, (67i,t) < (o72,t) < ... <(o7/, t) , for? e (M +) f c. If we set Af = {(Ê '*):^€(M> then •z = Q̂S+1uO{(Ê'<fi*'*»}-i = l i=l Chapter 2. The real n umbers 60 The second type of set is clearly almost linear in normal form. So we need only show that the A^- are as well. Suppose y G ({a~i,t), (af+i, £)). Then a\t\ + ... + ai-iU-i + bi-i+iti-i+i + ... + bktk < y < a\t\ + ... + aj_t-i*f-i-i + + ••• + Mfc- Writing y2 = y - (axtx + ... + a/_;_ii/_i_i + + ... + bktk) we have ai-iti-i < y2 < bi-iti-i. Choose 0 < t' < 1 such that y2 = ai-iti-itf + fy_^_;(l - 0 . Now (^TUv^y) -(ii(ui,ai) + ...+t/_i_i(uiJ"i^ = ti-i(vf-i,y2) = t'ti-i{vr-u ai-i) + (1 ~ t')ti-i(yr-i, bi-i). So A*£r is the positive span of (vj,a,j), for 0 ^ j ^ / — i, and (vj,bj), for Z - t < jf < Jfe. Proof of the claim. Again we proceed by induction, this time on dim(Y) and the n such that Y C R n , and again we assume that Y is a cell. If dim(Y) < n, then Y is the graph of some function g on a cell Z C R n _ 1 . Let h : Z —> R be givenby fo(xi,...,xn_i) = /(xi, ..,x n_i,5(xi, ...,xn_i)). By the induction hypothesis we can partition Z into Zj such that (Zj, 5) and (Zj, fo) are almost Chapter 2. The real numbers 61 linear. Fixing an index, let Zj = jc + J_ Uvi : c E C, U > 0 } g{c + 53 = 9{c) + («,*)• /i(c+53*̂ ) = Mc) + <&,*>•• Of course, d, b, and the Vi depend on j. Let Yj = {(c, 5(c)) + ^(^i. °<) : c e C, ti > 0 } . By construction, on Yj we have f((c,g(c)) + 53fi(^'ai)) .= /(c + __]**^'5(c) + (t,a)) = /(c + 53 *i*>i> 0(c+ 53 = /i(c+53 )̂ = fc(c) + (6,t) = /(c) + (b, t>. Also, as the Zi partition Z, the l i partition Y. Now suppose that dim(Y) = n. By the partition condition there are open, connected (not necessarily definable) sets Ui,...,Ur and analytic functions /1, f r defined on the Ui such that fi — fj on Ui n for all i and j , and Y\{J Ui is contained in a definable set of dimension less than n. We will abbre- viate this by saying dim(Y \ _) Ui) < n. We will prove the result by induction on r(Y, /), the minimum number of Ui required. If r(Y, f) = 0 then dim(Y) < n, so this case has been dealt with. Now let Y = C + span + {?7i , ir f c } . For Chapter 2. The real numbers 62 each t G (R + ) f c - 1 and c G C, set k F{c,t)(t) = fic+^tiVi + m). 1=1 It is our aim to use these functions to show that / is essentially linear in the v~k direction. We will then apply induction to complete the proof. By hypothesis, FSj (for fixed c and t) is eventually linear. Let Z(c, t) be the least t such that for all s > 0 and ti,t2 > t, %t)(*i + a) - Fm(h) = Fm(t2 + s) - F ( c- t-)(t2). This is the (or a) point after which F^i) is linear, and the function is definable. Finally, let s(c, t) be the eventual slope of F ^ . This is definable as Fm(t + 1)-Fm(t), for some t > l(c, t). We claim that the range of s is finite. If not, then it contains some inter- val. As dim(Y) = dim(C) + k, we will assume, to simplify matters, that C is an open subcell of M.n~k. If it is not we can find a definable homeomor- phism between C and such a cell, and examine the images of s, etc through this homeomorphism. So s is defined on C x ( R + ) f e _ 1 . By cell decompo- sition we can find an open, connected cell V on which s is continuous and has infinite range. Suppose that for all i and ai,a2, . . . ,a n_i G C x (R+) f c _ 1, s*(x) — s ( a i , . . . , a j _ i , £ , a j + i , . . . , a n _ i ) has finite range. Then, by continu- ity and by following paths along axes, we can show that s(a) = s(a') for any a,a' G V. This is a contradiction, so for some a i , s * ( x ) has mfinite range. Choose, by the monotonicity lemma, some [a, b] C R on which s* is Chapter 2. The real numbers 63 strictly monotone, and let M = sup{Z(ai,aj_i, x, a j + i , a n _ i ) : x € [a, b]}. Because there are no poles definable in the structure, M is finite. For any x E [a,b], i ?(oi,...,x,...,o t l_i)(* + -W) i s defined on R + and is linear (in t) with slope s*(x). Let gb(x,i/) = -F,(a1,...,:c,...,an-1)(y + -W) = s*(x)y + g0(x,0). Nowlet#i(x,y) - go(x,y) - g0(x,0) = s*(x)y. Now let 92(x,y) = 9i(s*~1(x),y) = xy. If we reduce [a, b] to a subinterval with rational endpoints, we can now define, using only the group structure, g3 : [0, b - a] x R + -> R by 53(x, y) = g2(x + a, y) - ay, as a and b are rational. Again, 53(x, y) = xy, now defined on [0, b — a]. We can define 54(x) on [1/(6 - a), co) to be the (unique) y such that gz(x, y) = 1. This is a pole (namely x H So s has finite range, say {mi, ...,mp}. Let m be the least rrn such that s - 1(mj) is n — 1-dimensional, and set fe-i G = {c + 53 + f̂c : c € C, ^, £ > 0, F(5)j) is linear with slope m on some interval containing £}. Then G is, as shown above, definable. We will show that either Y = G or r(G, f) and r(Y \ G, f) are both less than r(Y, /). Chapter 2. The real numbers 64 Let fc-i Yc,i = {c + ^ + : * > 0}. i=l If (c, i) 7^ (c', £') then, by unique representation, Y5j n Yg',F = 0. Let fc-i and fc-i = {c + E tjiTj € Z : s(c, rf) = m}. i=l If c+Ef=i trfi € Z m then Y g ] t -nG is infinite. So the Y g i f n G with C+YAZI UK € Z m is a family of infinite subsets, and since dim(Zm) = n — 1, the dimension of G must be7 n. Suppose that dim(Y \ G) = n. Let Ui,..,Ur, / i , . . . , / r be witnesses to r(Y, f) = r. As dim(G) = n, there is some in with dim(G D C/i0) = n (that is, this set has non-empty interior). Similarly, there must be some jo with dim((Y \ G) fl Uj0) = n. But if, for some given i , Ui fl G contains an open set then, fi must be vk -linear (with slope m) on Ui n G by the defining con- dition of G. But /* is analytic on Ui, so the same is true on [/*. In particular, £/j D (Y \ G) = 0, and in 7^ jo- Re-arranging the indices, we may assume that, for some s,i < s implies Ui fl Y C G, and s < i implies dim(£/j fl G) < n. Thus d im((Y\G) \ [J Ui)<n i=s+l s dim(G \ (J [/;) < n, 7See [P1188]. i=l Chapter 2. The real numbers 65 demonstrating r(Y \ G,f)^r-s<r and r(G, f) ^ s < r as desired. Now suppose that dim(Y \ G) < n. In this case we will have Y = G, and the result will follow. If, for some c, i we have Y^i \ G finite then, as F5j is continuous and linear of slope m on G, Y^i C G. So we can define the set Zi = jc + Ĵ tiffi 6 Z : yc,t \ G is finite I Note that the set of Y^i\ G with c + YltZi Uv% € Zi partitions a subset of Y \ G which, by hypothesis, has dimension < n, so dim(Zi) < n — 1. Now let { As—i fc-1 c + ^ + tujfe : c + 53 6 Z i> f > 0 f • 2=1 1=1 ) So dim(Yi) = dim(Zi) + 1 < n. Now if Y 2 = Y \ Yi, Y 2 C G and if c + E t i *<«i + Mk e Y 2 , fc-i fc-i /(e+53 +^)= /(g+XI + t = l i=l But as dim(Y2 \ Y) < n - 1, Y 2 is dense in Y, so the above equation holds throughout Y (as both sides are continuous). By the induction hypothesis, we can assume that (Z, /) is almost linear, and so we are done. • We can now prove that SB is the only structure 'between' J*f and &, as observed in [Pet93]. Theorem 2.4.5. SB is the only proper reduct of' & which properly expands 5£. Chapter 2. The real numbers 66 Proof. Let ̂ be a reduct of & which properly expands ££. Because Si prop- erly expands J£, we know from Theorem 2.3.4 there there is an interval I such that every semialgebraic subset of In is ^-definable. If X is any bounded semialgebraic subset of R n we can linearly translate X into In, so X is S&- definable as well. Thus SB < Si. If Si is not SS then the theorems of this section tell us that there is an ^"-definable bijection from a bounded interval to an unbounded interval. Linearly scaling and pasting as needed, we may assume that there is an ^"-definable bijection / : I —> R. Now, if X is any semialgebraic subset of R n , f_1(X) is a semialgebraic subset of In, and so is ^-definable. So X is ^"-definable, and Si is • • 2.5 Multiplicative reducts A similar result to those above can be had when considering reducts of & which expand S& = (R, •, <), as in [Pet93]. The only reduct of & which prop- erly expands & is (R, +*, -, <), where +* is the restriction of + to the interval [1,2]. In order to prove the following results we will need to assume that the structure (R,+,-,x i-> ex) is o-minimal. This was shown by Wilkie in [Wil96] by demonstrating that every definable set is the projection of some quantifier-free definable set (model completeness). It also follows that this structure satisfies the partition condition. We will work over £?+ = ( R + , •, <) for the most part, but this is for ease of notation. The results transfer readily to ^ . Definition 2.5.1. A set X C (R+) n will be called p-bounded if X C [a, b]n for some 0 < a < b. We call X C R n p-semibounded if it is definable in a Chapter 2. The real numbers 67 structure (R, •, <, B) where the B is a p-bounded set. We will let ^ p denote the structure generated on & by the p-semibounded sets. Lemma 2.5.1. Let X be a p-bounded set. Then in (R, •, <, X) one cannot define a bijection between a p-bounded interval and a p-unbounded interval. Proof. Let a(x) = \n(x). Note that a provides a natural isomorphism between and (R, +, <). Note that X C is p-bounded if and only if a(X) is bounded. Consequently, by the isomorphism, X is p-semibounded if and only if a(X) is semibounded. So if there is a bijection / between a p-bounded interval and a p-unbounded interval definable in (^ + , X) then there is a bi- jection between a bounded interval and an unbounded interval definable in (R, +, <, a(X)). By Theorem 2.2.2, then, a(X) is not semibounded, whence X is not p-semibounded. • Lemma 2.5.2. Suppose X C (R+) n is semialgebraic but not ^+-definable. Then a(X) is not definable. Proof. Suppose that o(X) is jSf-definable. Then there are certain ai,...,ctk such that o(X) is definable in (R, +, A Q l , A Q f c , <). Notice that cr is a nat- ural isomorphism to this structure from = ( R + , - , / i a i , . . . , / j a f c , <), where Hp(x) = x&. By Lemma 2.4.4, the A a i are all (R, +, <, a(X))-definable, and so the ixai are X)-definable. Now, if X is semi-algebraic, the p,ai need all be semi-algebraic, and so the ai are all rational. But then the / i a i are definable. • Lemma 2.5.3. Let X C ( R + ) n be ^-definable. Then ifa(X) is semibounded, X is p-semibounded. Chapter 2. The real numbers 68 Proof. As X is ^"-definable, o(X) is ( R , + , •, x i-> ex)-definable. So the struc- ture ( R , + , < , o(X)) is o-minimal and satisfies the partition condition. If o(X) is semibounded then there are Xai, A a f c and bounded sets B\,P>i defin- able in ( R , + , < , cr(X)) such that o(X) is definable in ( R , +, <, A Q l , A Q f c , Bi,Bi). If we let Ci = o~l(Bi) for each i, we see as above that X is ( R , - , / i a i , . . . , / i a j t , C i , . . . , C / ) -definable. As above, the Ci are all p-bounded and the p,ai must all be S&+ definable, and so X is p-semibounded. • Theorem 2.5.4. The only proper expansion of S? which is a proper reduct of & is Proof We let Si be some proper reduct of & properly expanding S? and demonstrate that Si = SS9. First suppose that X C R n is ^-definable but not ^-definable. Without loss of generality, we can assume that X C ( R + ) n . Then ( R , + , < , o{X)) is o-minimal (it is a reduct of the exponential field) but terval of ( R , + , < , o{X)). Let I = (a, b) be the a_ 1-image of this interval. By Theorem 2.3.2 every semialgebraic subset of In is (S?, X)-definable. If (7,6) is any other interval in R + , and a e (a, b) then there is a rational number q p- not semilinear. In particular, we can define a real closed field on some subin- sufficiently small such that if 8 = a(<5/7)9, (a, 8) C (a, b). Then ln(*/7) Chapter 2. The real n umbers 69 is a ^-definable bijection from (a, 8) to (7,6), and so every semialgebraic subset of (7,6) is definable. In particular, 3§p <C<̂ . Now suppose that some non-p-semibounded X is ̂ -definable. Again we may assume that X C (R + ) n , and again we may apply previous theorems to (R, +, <, or(X)). As a(X) is not semibounded we may, in (R, +, <, a(X)), de- fine a bijection between a bounded interval and an unbounded interval. This translates in X) to a bijection / between a p-bounded interval and a non- p-bounded interval. But any non-p-bounded interval is either of the form (a, 00) , or of the form (—00, —a) or contains 0 in its closure. Using I H 1/a; if required, we can assume that rng(/) = (a, 00). We may then also construct8 bijections with range (0,1/a), (-1/a, 0), and ( - 0 0 , -a). Now any semialge- braic set F a ™ may be divided into Yf)(a, oo)m, Y n [1/a, a]m, Y n (0, l / a ) m , et cetera, each of which is (0s, X)-definable. So S% = J5". • The lemmas above show that both of these reductions are strict. 2.6 Polynomially unbounded structures As in the previous section, the natural isomorphism (R, +, <) —> (R + , •, <) yields useful results. We will here prove a result due to Miller [Mil94], but in a form presented by Poston [Pos95]. Theorem 2.6.1. Let & be an o-minimal expansion of ^ in which some definable function is not bounded by any polynomial. Then x H-> ex is definable in 8$. 8The function x H-> —X is definable as for all x ^ 0, —x is the unique y such that x2 = y2 and xy < 0. Chapter 2. The real numbers 70 Proof. We will prove that (x, y) i-> x l n ^ is definable in Si. Then, if g(x) — x l n x = e(ln^2, g'(x) = 2\n(x)e^n(-x^2/x is definable in Si, and then so is \xg'(x)/g(x) = ln(x). Let 3» = (R+, •, <), and # = (R, +, <). Then =< by x i-» ln(x). Now, if / is definable in an o-minimal expansion of (^ + , /) is also o-minimal. Let g be the image of / in <S, so that (S?,f) = g). If g(x) < nx for any n, we have /(x) < xn, so g is not linearly bounded. Thus multiplication is definable in (&,g). Lifting through the isomorphism, (x, y) H-> x l n ^ is definable in ( ^ , / ) - • 2.7 O-minimal expansions of (Q, +, <) Though it is widely believed that there is no proper o-minimal expansion of (Q> +) <)/ it is n o t known. The evidence mounting towards this conjecture is quite convincing, though, and the above sections allow us to put some restric- tions on possible counterexamples to the conjecture. Theorem 2.7.1 (Laskowski, Steinhorn [LS95]). There is no proper semialgebraic o-minimal expansion of (Q, +, <). By a semialgebraic expansion we mean an expansion by a set X D Q n , where X C R n is semialgebraic. Proof. Suppose X is a semialgebraic set, let XQ = X C\ Q n , and suppose that J? = (Q, +, <, XQ) is o-minimal. As shown at the beginning of this chapter, 2 can be elementarily embedded in a unique o-minimal expansion Si of R (unique assuming 1 1, in which case the embedding is the identity map). Chapter 2. The real numbers 71 Claim. For every semialgebraic set Y C R f c , ifYq = Y n Q f c is definable in £? then the interpretation ofYq in (denoted Y^) is simply Y. Proof. We proceed by induction on the dimension of Y, and restrict our at- tention to cells. As seen before, we need only demonstrate the case where Y is the graph of a continuous, definable / : C —> R, for some dim(Y) — 1- dimensional cell C. Given the induction hypothesis (which is trivial for 0- dimensional cells), CQ = C. Also, YQ is the graph of / restricted to CQ. Let g : C —• R be the function whose graph YQ is. Then / = g on CQ, a dense subset of C. This tells us that / = g on C (see, for example, [Kel55]). • If X is not semilinear, then multiplication is definable on [—2,2] in and hence in B. But this is impossible, as £ = Si would imply that Q contains a square root for 2. Thus @ is a reduct of ̂ . Again, if a € R \ Q, then A a cannot be ^-definable, as Xa(q) is irrational for any rational q. But if a is rational, \ a is already definable in (Q, +, <). Thus, if £? is o-minimal, £ = (<Q>, +, <). • In fact, in light of the theorems above, if £ is an o-minimal expansion of (Q, +, <) then £ S&, for some o-minimal & on R. If £ is proper, S% cannot be semilinear, by the argument above. So there must be be some © and <g> definable in £ which make some interval of £ into a real closed field. Although it seems unlikely, it has not yet been shown that this cannot happen. 2.8 End extensions We conclude with a simple observation on the nature of non-Archimedean o- minimal groups. Theorem 2.2.2 allowed us to conclude that in any o-minimal Chapter 2. The real numbers 72 structure for which we may construct end-extensions, multiplication cannot be definable. We can give a sort of converse to this in light of the theorems above. Definition 2.8.1. Let Ji be an o-rninimal structure. We define two types in S\(Ji): Poo(x) is the type generated by the formulae x > a for all a € Ji, and pe(x) is the type generated by 0 < x < a for all a € Ji, a > 0. We say that Ji admits end-extensions if there is an elementary extension of Ji in which is realized but pe is not. Lemma 2.8.1. Let Ji be an o-minimal expansion of a group. Then if Ji does not admit end-extension, there is a definable pole in Ji. Proof. Suppose Ji does not admit end-extension. By Lemma 2.1.4 there is a definable function / : Ji —> Ji such that in any elementary extension of Ji, Poo{o) implies pe(f(a)). By cell decomposition there are —oo = ao,...,an = oo such that the restriction of /"to (a$,Oj+i) for any i is either constant or a bijection between intervals. If I — (a n_i, an) we cannot have / constant on I, as in elementary extensions of Ji, f(I) contains realizations of pe (and in particular elements outside Ji). So / is a bijection. Similarly, the closure of /(/) must contain 0. Suppose / is increasing, and let c € /(/) fl (0, oo). Then there is a b G / such that x > b —> f(x) > c. But if a realizes p^ in an elementary extension of Ji, a > b and /(a) < c. So / is decreasing. Finally, suppose that lim^oo f(x) — L < 0. Then there is some c € (L, 0) and some b e I such that x > b —• f(x) < c. Again this is a contradiction, and so lim^oo f(x) = 0. Thus / restricted to some subinterval of I is a pole. • Chapter 2. The real numbers 73 Applying the theorems above, if JZ is Archimedean, JZ is an elementary substructure of some o-minimal expansion of (R, +, <). Our pole above will allow us to define multiplication in this structure if the corresponding struc- ture on R is semialgebraic, or at least a real-closed field on some subinterval otherwise. Note that Lemma 2.1.4 also tells us that if JZ is end-extendible, there must also be an elementary extension of JZ realizing pe and not p^. Also, every noncut over JZ is a translation of pe or a reflection across 0 of such a translation, and so an end-extension may realize no non-cuts. Bibliography [Bou98] Elisabeth Bouscaren, editor. Model theory and algebraic geometry: An introduction to E. Hrushovski's proof of the geometric Mordell-Lang con- jecture. Number 1696 in Lecture Notes in Mathematics. Springer, 1998. [BW40] R. P. Boas and D. V. Widder. Functions with positive differences. Duke Mathematical Journal, 7,1940. [CheOl] E.W.Cheney. Analysis for Applied Mathematicians. Springer-Verlag, New York, 2001. [Fra93] John Fraleigh. A First Course in Abstract Algebra. Addison-Wesley, fifth edition, 1993. [Hod93] Wilfrid Hodges. Model Theory. Cambridge University Press, 1993. [Kel55] John L. Kelley. General Topology. Number 27 in Graduate Texts in Mathematics. Springer, 1955. [KPS86] Julia F. Knight, Anand Pillay, and Charles Steinhorn. Definable sets in ordered structures. II. Transactions of the American Mathematical Society, 1986. [LS95] Michael Laskowski and Charles Steinhorn. On o-minimal expan- sions of archimedean ordered groups. Journal ofSymoblic Logic, 60, 1995. [LS00] Jean-Marie Lion and Patrick Speissegger. Analytic stratification in the Pfaffian closure of an o-minimal structure. Duke Mathematical Journal, 103,2000. [Mar86] David Marker. Omitting types in o-minimal structures. Journal of Symbolic Logic, 51,1986. [Mil94] Chris Miller. Exponentiation is hard to avoid. Proceedings of the American Mathematical Society, 122,1994. 74 Bibliography 75 [MP90] David Marker and Anand Pillay. Reducts of (C, + , •) that contain +. Journal of Symbolic Logic, 55,1990. [MPP92] David Marker, Ya'acov Peterzil, and Anand Pillay. Additive reducts of real closed fields. Journal of Symbolic Logic, 57,1992. [NP91] A. Nesin and A. Pillay. Some model theory for compact Lie groups. Transactions of the American Mathematical Society, 326,1991. [Pet92] Ya'acov Peterzil. A structure theorem for semibounded sets in the reals. Journal of Symbolic Logic, 57,1992. [Pet93] Ya'acov Peterzil. Reducts of some structures over the reals. Journal of Symbolic Logic, 58,1993. [Pil88] Anand Pillay. On groups and fields definable in o-minimal struc- tures. Journal of Pure and Applied Algebra, 53,1988. [Pos95] Robert Poston. Defining multiplication in o-minimal expansions of the additive reals. Journal of Symbolic Logic, 60,1995. [PS86] Anand Pillay and Charles Steinhorn. Definable sets in ordered structures. I. Transactions of the American Mathematical Society, 295, 1986. [PS88] Anand Pillay and Charles Steinhorn. Definable sets in ordered structures. III. Transactions of the American Mathematical Society, 309, 1988. [PSS87] A. Pillay, P. Scowcroft, and C. Steinhorn. Between groups and rings. Rocky Mountain Journal of Mathematics, 9,1987. [Spe99] Patrick Speissegger. The Pfaffian closure of an o-minimal structure. Journal fur die Reine und Angewandte Mathematik, 508,1999. [Wil96] A. J. Wilkie. Model completeness results for expansions of the or- dered field of real numbers by restricted Pfaffian functions and the exponential function. Journal of the American Mathematical Society, 9, 1996.
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
China | 9 | 0 |
Japan | 2 | 0 |
City | Views | Downloads |
---|---|---|
Beijing | 9 | 0 |
Tokyo | 2 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Share to: