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 (, - ) 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 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 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( 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 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 f(u) = / (x))) V3y(y > x A Mu(x f(u) = f(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 = x V / ( u ) > / (x)))) ( 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) \ / ( x ) } ) X- = {ye(a,b):f(y) x. The four cases, where (a, x) € X^ and (x, 8) e X^, correspond to the four cases, 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'(yf{x)). (1.2) Now fix some x £ I", and let X+ = {yel":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 /(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 (a^ , 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 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 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 - V 3 x A j=0 i=0 j=Q i=0 where each 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 0. Let CQ < c\ < ... < Ck be a list of all roots of the p^ lib € Ji realizes

max{y : tp(x, y)} are continuous, and if a is good for cp, for all a, € X, then \ 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 : ]N. (*) Set JV g(x) = min{y : 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 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 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 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 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 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*^ 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 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 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) 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 ip(x,y). As Ji <; Ji, f^(a) G Ji. But Ji f= ^ 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 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 \= ^(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 (x, b) A b),ip2(x, b),..., f^c(a;, 5). By the induction hypothesis, 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= 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 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 0. Of course, if there are any formulas of the first form then f(Ji) = 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 0) V VxVfo(a 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 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, 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) © = (half(A(M(a0,&i), Af(, {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, ©, ) 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, ©, ) to (R, +, •). From this we can then use Lemma 1.5.2 to find a definable transversal for ~ in R 2 making (Y, ©, ) 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) 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 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 = {(E^ '*):^€(M> then •z = Q^S+1uO{(E^' 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) 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 (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 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, £ = (, +, <). • 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 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.