O. For simplicity we limi t ourselves t o p = 1, v = 2; indeed what we are going to say in t his case applies to any p > 0 as well, a nd so is ge nerally valid . First use ind ep endence t heory, mo re precisely (13) an d (14), and find an isomorph ic copy B~ of B l inside n, correspond ing t o B l by a n isom orphism fixin g Ba poin t wise, and satisfying B~ ../.-Bo Bi . To build B~ , consider a language L * enlargin g L by a constant b* for eve ry b E B l , and in L * t he t heo ry T * saying th at , for eve ry bin B l ,
b* satisfies t he non -forking extension of tp(bj Ba) over Bi . Any finit e por tion To of T* has a mode l; in fact , let bglue all t he t upIes from B l a rising in t he sent ences of To, use (14) and obtain a t upIe b* realizing t he non-forking extension of tp(bj Ba) over Bi ; recall that every subseq uence of b* has t he sa me prop erty. By com pactness , T* has a mod el. T he elements b' em bo dy ing t he constants b* in t his mod el form a st r uct ure B~ isomo rphic t o B l over Ba (as, for every L (Bo)-formul a
n F x ( b~, b)
<=?
n F dx(b).
7.8. MORLEY'S THEOREM
277
This remains true if we enlarge Ba to B~ U {d} : for every also for b= (iJi, d) with iJi in B~ ,
n F= X(b~ , Let us see why. Oth erwise n
iJi , d)
{:?
F= -' (X ( b~ ,
b in
B~ U {d} , so
n F= dX(iJi, d).
iJi , d) H dX(iJi , d)) a nd consequentl y
n F= 3z(a( z, ii) 1\ -'(x (b~ ,
b', z)
H
dx(b' , z)));
in other word s,
3z(a (z, ii)
1\
-' (x (v, iJi , z) H dx(iJi , z))) E tp(b~ / BD.
As B, an d B~ a re ind epend en t over Ba , there is som e b in Ba for which " n F= :3z(a (z, ii) 1\ -' (x (b~ , b , z) H dx(b , z))).
"
"
Then t here is some d" E B l (and indeed in a (Bl , ii) ) such t hat
81
F= -' (X (b~ ,
b , d") "
H
dX(b , d")). "
Recall a( Bl , ii) = a (Bo, ii), so d" E B a. Bu t t his cont radicts t he choice of dX over B a. Now apply what we have j ust observed to t he formul a 1/;(v, b~ , d). As n F= 1/; ( b~, b~ , d), it follows n F= d1/; (b~ , d), where d1/; is t he defining formula. So 8~ F= 3zd1/; (b1 , z), and we find d' E B~ such t hat B~ F= d1/; (b1, d'), a nd hence n F= 1/; (b~ , b1 , d'). T his means that d' has t he same ty pe as d over B l U B~ , a nd so d = d' E B~ ; bu t a (B~, ii) = a (Bo , ii), hence d E a (Bo , ii) . This accomplishes our proof. .. Now we are in a position to show, as promised Lemma 7.8.6 Let A be a model ofT p rim e ov er 0. Th en th ere is a strongly m in imal f orm ula ep (v) in T with parameters from A . Proof. Proceed as in Lemma 7.8.5 , but work in A instead of n. Using w-stability, find again a formul a ep (v) with pa ramet ers in A such t hat ep(A) is infinite but has no par ti t ion into 2 A-definable infinite s ubsets. This do es not mean a priori t hat ep ( v) is strongly mini mal , as in general we cannot imagin e what happens if we allow parameters out of A . However we claim t hat in our parti cul ar setting , for a JL-categorical T, ep( v) is ju st strongly minimal. Let us see why. Suppose not , so, enla rging ou r perspective to n, we ca n find a n L-for mula 1/; (v, Z) and par a meters b in n such that both
278
CHA P T ER 7. CLASSIF YING
1\ 'IjJ (v, b) and
1
However , ju st owing t he choice of
..
Bu t we ca n even ass ume t hat our strongly mini mal
The read er may t ry to check t his as a n exercise. In pa rticular , if T is J.Lcategorical, t hen T' is; a nd, if we succeed in proving t hat T ' is categorica l in every uncountable power A, th en we can say t he same of T . So, wit h no loss of genera lity, we ca n replace T by T', in other words to assu me t hat T is a J.L-categorical t heory wit h a strongly mini mal L-formula
7.9. BIIN TERPRE TABILITY AND ZILBER CONJECTURE
279
to ad , a nd so (at least in uncount a ble powers) t he cardi nality of
Lemma 7.8.8 For eve ry model B of T , B is prim e over
P roof. As T is w-stabl e, t he re ex ists a mo de l B' of T pr ime over
P roof. (Morley 's Theor em) . Let B o a nd B 1 be t wo models of T having the same unco unt abl e power ).. . Owing to Lemma 7.8.8, each B, (i = 0, 1) is prime over ~o. T hen X o a nd X l correspond to each other by some elementary biject ion , which enlarges t o a n eleme ntary bijection h between
7.9
Biinterpretability and Zilber Conjecture
We have devoted several sections t o t he problem of classifying struct ures up to isomorphism an d to Shelah 's analysis of this qu estion. But , needl ess to say, iso mo rphism is not the onl y pos sible classifying eq uivalence relation , even within structures. Anot he r possible criterion , deeply related to Model Theory, is interpret abili ty. The following t wo examples illustrate t his alternative persp ective a nd it s underl ying idea.
280
CHA PTER 7. CLA SSIF YING
Examples 7 .9.1 1. Natur al numbers (viewed as non-negati ve int egers) form a definable set in t he ring (Z, +, .) of integers: as recall ed in Chapter 1, a celebrated T heorem of Lagr an ge says t hat they are exactly t he sums of four squa res in (Z, +, .). So t he whole struct ure (N, +, .) is definabl e in (Z, +, '), because t he addit ion and multipli cation in N ar e ju st t he rest rict ions of t he corres ponding op erations of Z . This is a fund am en t al result: in fact , as (N , +, .) lives in (Z , +, .) as a definable struct ure , (Z, +, .) inh erits its und ecid abili ty phenomena related t o God el Incompleteness Theor ems , and in this sense is a "wild" st ructure.
2. In t he same way (N, +, .) lives in the ration al field (Q, +, .) as a definable structure. This is a deep theor em of Julia Robinson . So even the rational field inherits th e complexity of (N , +, .) and its und ecidability. So, genera lly speaking, when we meet a st ruct ure A in a lan guage L and we realize t hat A defines, or also interprets anoth er structure A' (possibly of a different lan guage L'), t hen we ca n reason abl y ag ree t hat A inh erits th e full complexity of A' , and conseq uent ly is at leas t as difficult to dominate as A' is. Of course t his ca n be extended t o classes of st ruct ures . In t his enla rged fram ework , we com pa re two classes of struct ures, K in a lan gu age L and K' in a lan guage L' resp ecti vely. For simplicity, we can ag ree t hat both K and K' are elementary. We ass ume t hat t here ar e suitable L-formulas defining , or also int erpreting, in a ny structure A E K a struct ure A' E K' and t hat, conversely, every A' E K' ca n be recovered by some A E K in t his way; we ass ume also that t hese formul as do not depend on t he choice of A in K . Then we say t hat K interprets K' and in t his case we ca n agree that K inh erits t he complexity of K' . Here are some furth er exam ples illustratin g this point. Examples 7.9 .2 1. Recall that a graph is a st ruct ure (G , R) where R is a sy mmet ric irr eflexive binary relation , usu ally ca lled adja cency . T he (elemen tary) class of graphs interprets a ny class of structures, and so inherits in t his way t he full complexity of math em at ics . The proof of thi s fact requires patience rath er t ha n ingenu ousness . To avoid t oo many te dious det ails , let us illustrate its idea in a par t icular case, and see how graphs int erpret arbitrar y binar y rela tion s. So take any struct ure (A, R ) where R is a binary relation on A , and form a graph (A', R' ) as follows. Let A' include A. Moreover, for every a E A, add t wo new vertices ao and al in A', both adjacent t o a (so
7.9. BIINTERPRETABILITY A ND ZILBER CONJECTURE
281
(a, ao ), (a, ad E R' ). Finally, for every pair e = (a, b) E R, add in A' t wo new ver tic es eo, el sat isfying (a, eo), (eo, el ), (el , b) E R', t hree more ver tic es adjacent to eo, and four mor e vertices adj acent t o el . For inst an ce, here is a pictur e of (A', R' ) when A = {a , b, c} and R = { (a, b)} .
bo
A
Co
It is an easy exercise to realize that a ny (A, R) ca n be definably recovered inside t he cor res ponding (A' , R' ) in a way ind ep end ent of t he particul ar choice of (A, R). In fact , A is ju st t he set of t he ver tic es in A' having eit her 2 adjacent nod es , or 3 adjacent nod es such t hat 2 of t hem have no fur th er adjacent nod e, while R is t he set of t he pairs (a, b) E R such t hat t he re a re eo, el E A' for which (a, eo), (eo, el) (el, b) E R' , eo has t hree adjacent nod es in addit ion to a and el has four adj acent nod es besides eo and b. 2. T he same can be said of t he class of groups, a nd even of the class of nilpoten t groups of class 2 (a compa rat ively slight generalizat ion of a belia n groups) . This is a beautiful result of A . Mekler , s howing that nilpotent groups of class 2 int epret graphs a nd so, t hrough them , any class of structures. The proof uses brilliantly some non -trivial notions and tools from group th eory. T he conclusion is clear: groups, and even nilpotent groups of class 2, are a class as bad as possible, and inherits t he full complexity of mathematics. 3. We said in 7.1 that , for a given (count a ble) field K , K(x , y)-modules (i. e. K-v ectorspaces with two distinguished endomo rphism s x and y) ar e a n intractable class: no classification ca n be ex pected, even for finit e dim ension al objects , otherwise the word problem for grou ps would be solvable. Of course, every class interpretin g K (x , y)-modules is at least as complicat ed as t hey a re, a nd hence definiti vely a bad class. Several not abl e clas ses of modules share t his negative fea ture. For instance,
282
CHAP TER 7. CLASSIF YING
t his is t he case of K[x , y]-m odules (wit h t wo commuting unknowns x an d y), or Z[x]-modules, an d so on. The book of Prest quoted in t he references at t he end of t he cha pter includ es a discussion of t his point and a great deal of notewort hy examples. So a possible way of classifying st ructures, or even classes of st ructur es, is up t o mutual interpretability (biinterpretability) . Accordingly, one could t ry t o characterize struct ures by looking at what is definabl e, or also int erpretable, in t hem : gro ups , fields, a nd so on. Incident ally notice t hat a relevan t emphas is on t he role of definabilit y already a rises within Shelah 's classification analysis (for instan ce, t hink of th e ord er property, lookin g at t he orders definable in a given struct ure ). However the st udy of mu tual int erpretability in mathem atics did pr ecede Mod el Theory , or , at least , mod ern Model Th eory. For exam ple, let us mention t he celebrated Malcev corres ponde nce between groups a nd rings , essent ially showing t hat t he class of uni t ary rings is biint erpret a ble with a suitable class of nilpotent groups of class 2, a nd confirming in this way how complicated t hese groups are. Bu t who mainly developed t he biint erpretabilit y program in Mo del T heory was Boris Zilber. Zilber 's orig inal project concerned t he class ification of uncou nt abl y categorical t heories (t hose where Morley 's Theorem a pplies) by lookin g at which gro ups, or fields , an d so on , are definabl e in t hem. As already observed, uncoun tabl y categorica l t heories includ e the stro ngly minim al ones, a nd t he lat ter t heories a re t he simplest possible (if we excludes finite structures) . Acco rdingly t heir exam is a reason abl e first step t owa rds a genera l approach. So t he qu estion is: what stro ngly minimal struct ures look like? Ca n we reason abl y classify t hem by lookin g at what t hey int erpret ? Let us outline Zilber an alysis in t he strongly minim al setting. Recall t hat a st ruct ure A is said to be st rongly minimal if it s complete theory is: so, for every B element arily equivalent to A , the only definable subsets of B a re t hose finit e or cofinite . We introdu ced in Cha pte r 5 several examples of strongly minim al struct ures . To summa rize them , let us work inside a fixed algebraically closed fi eld A. Examples 7.9.3 1. Firstl y view A as a struct ure in t he lan gu age 0, so as a mere infinite set . In t his case , t he t heory of A equa ls t hat of infinite sets , and is strongly minimal. T he st ruct ure of A is very poor , and no (infinite) gro up is definable here. Mo reover • for every subset X of A , acl (X ) = X ,
7.9. BIINTERPRETABJLITY AND ZJLBER CONJECTURE
283
• for every positive int eger n , the defina ble s ubset s of An are the finit e Boolean com binations of
with i, j = 1, .. . , n, bE M . 2. Let A a be t he pr ime subfield of A, and look at A as a vectorspace over Aa in the appropriate language. Now t he complete theory of A is t hat of infinite vectorspaces over Aa, and is again strongly minimal. But t his time • for every subset X of A , acl(X) is the subspace of A spa nned by X, • for every positive integer n, the definable subsets of A n a re t he finite Boolean combinat ions of cosets of pp-definable subgroups of A , and for n > 1 their class is larger t han in Example 1. Notice that an infinite group is trivially definable in A, but no field ca n be interpreted inside A . 3. At last , view A just as a n algebraically closed field. If p is its characteristic, then the complet e theory of A is ACFp and is strongly minimal. Moreover • for every subset X of A, acl(X) is t he algebraic closure of A in the field theoretic sense, • for every positive integer n, t he definabl e su bsets of A n a re the construct ible ones , in other words t he finite Boolean combinations of algebraic varieties of A n . Now take any strongly minimal st ruct ure A.
Definition 7.9 .4 A is called trivial if, for every X
~
A,
acl (X) = UxEXacl(X) .
Every (pu re) infinit e set is trivial. But, of course, vectorspaces and algebraically closed fields are not. Moreover no trivial st rongly minimal structure ca n interpret an infinite group.
Definition 7.9.5 A is called locally modular if, for eve ry choice of X , Y ~ A suc h that X n Y i= acl (0),
(*)
dim (X U Y)
+ dim (X n Y) =
dimX
+ dim Y.
CHA PTER 7. CLASSIFYING
284
Every t rivial structure A is locally modular (in fact , for every X and Y , acl (X U Y ) = acl (X ) U acl (Y ), so a basis of X U Y ca n be form ed by taking a basis a X n Y , extending it t o a basis of X a nd a basis of Y , and gluin g t hese bases together). Bu t also vect orspaces a re modular: in fact , in t his case , (*) is ju st t he Grassm an formula (and do es not need t he ass umpt ion X n Y :f: acl (0)) . On t he cont ra ry, no algebraically closed field A (of t ra nscende nce degree 2': 4) is locally modular. In fact, choose ao, aI , a2, a3 E A alge braically ind epend ent over the prim e subfield Aa , and form th e extensions
Then dim X = dim Y = 3 but dim(X n Y) = dim Ao(aa) = 1, whence X n Y :f: acl(0) , and dim(X U Y) = dim(Aa(ao , aI , a2, a3)) = 4. So (*) fails. Wha t is t he significa nce of local modularity? Basically a locally modular A eit her is triv ial or ca n define an infinite group. Furth ermore one obser ves th at a ny group 9 definabl e in a locally modular A is a belia n-by-finite (in other wor ds , it has a normal abelia n subgroup of finit e index); and every subset of any ca rtesia n power definabl e in A is a finite Boolean combination of cosets of definable subgroups of Accordingly, no infinite field is definable in A. In t his setting Zilber raised in 1984 t he following problem , generally called Zilb er Tricho tomy Conject ure.
en
en.
Conjecture 7.9.6 (Zilber ) Let A be a st rongly m in imal non locally modular struct ure. T hen A interprets an infi ni te fi eld K . Furthermore, for eve ry posit ive integer n , the subsets of K " definable in A are ju st thos e definable in K (and hence coin cide with the construciible ones). Recall that , owing to Macintyr e's Theor em , any infinite field interpretable in a n w-stabl e st ruct ure must be algebraically closed. Hence the importance of this conj ecture is clear: according to it any st rongly minim al st ruct ure A eit her is t rivial, and so looks like an infinite set (as in Exa mple 7.9.3.1) , or is locally modular and not t rivial, and t hen resembl es a module (as in Example 7.9.3.2), or looks like a n algebraically closed field , becau se it interpret s s uch a field (Example 7.9. 3.3). Hence t he conj ecture would pro vide a qui te sat isfactory classification of strongly minim al struct ures (and t heories) up to biinterpret abili ty. Bu t in 1993 Hru shovski showed t ha t Zilber 's Conjecture is false.
7.9. BIINTERPRETABILITY AND ZILBER CONJECTURE
285
Theorem 7 .9.7 (Hrushovski) Th ere do exist strongly minimal structures A which are not trivial but cannot int erpret any infinite group.
Clearly such a structure A is not locally modular and does not interpret any infinite field. However Zilber Conjecture (more precisely, a suitable restatem ent) do es hold in certain topological structures deeply related to st rongly minimal mod els: the so called Zariski geometries . To introduce them, let us come back to Example 7.9.3.3 , so dealing with algebraically closed fields A. We know that , for every positive integer n, the algebraic varieties of A n a re preserved und er finite union and arbit rary intersection , and form the closed sets in the Zariski topology on A n. These topologies a re Noeth eri an: none of them admits a ny infinite strictly decre asing sequence of closed sets. Moreover they sat isfy th e following properties (m and n denote below positive integer s) .
Ut, ... , f m) be a function from A n in A m . Assume that eac h component f i (1 ~ i ~ m), as a function from An in A , either projects A n onto A or is constant . Then f is continuous.
(Zl ) Let f =
( Z2 ) Every set {iI EA : a; = aj} with 1
~
i, j ~ n is closed.
(Z3) The projection of a closed set of A n+! onto A n is a constructible set in A n. (Z4) A , as a closed set, is irr educible.
(Z5) Let X be a closed irreducible subset of A n. For every ii E An-I , let X (iI) denote th e set of the elements b E A such that (iI, b) EX . T hen there is a natural N such t hat, for every ii E An -I, either IX (iI) I ~ N or XCiI) = A. In particular, when n = 1, every closed proper subset of A must be finite. (Z6 ) Let X be a closed irreducible subset of A n, d denote the (topological) dimension of X. Then, for every i, j a mong 1, . . . , n, X n {iI E A n : ai = aj} has dimension 2 d - 1. (Zl) - (Z6) restate in a topological style some properties which are well know n, or easy to check. For inst a nce (Z5) follows directly from some simple algebraic facts and the st rong minimality of A by a compactness argument: the reader may check this in detail as an exercise. Now it is easy to realize that even infinite sets a nd vectorspaces over a countable field satisfy (Zl) - (Z6) provided one takes as closed subsets the finite Boolea n com binations of t he following sets:
286
CHAPTER 7. CLASSIFYING
• the sets of the tuples ad mit t ing a fixed coordinate in a given plac e, or equal coordinates in two different places, when dealing with pur e infinite sets; • the cosets of pp-definabl e subgroups when dealing with vectorspaces. It is easy to control t hat in both cases t hese sets ar e actually t he closed sets in a su it a ble topology.
D efinition 7.9.8 A Za riski st ructure (or geometry ) is a collection (A, {Tn : n positive integer}) where A is a non-empty se t, for eve ry n T n is a No eth erian topology on A n and (Zl) - (Z6) hold. Hence the examples 7.9 .3 produce Zariski structures. Conversely, let (A, {Tn n positive integer} ) be any Zari ski structure. Assum e t hat A is t he domain of some st ruct ure A (in a language L) such that, for every positive integer n , the subsets of A n defin abl e in A are j ust the finit e Boolean combina t ions of closed sets in T'; (and so coincide with th e construct ible sets in T n ) . Then it is easy to check that A is st rongly minimal; mor eover t he possible triviality, or local modulari ty of A do es not depend on L , or on t he L-structure of A , bu t only relies upon th e charac terizat ion of th e definabl e sets of A and so, afte r all, upon (Zl ) - (Z6) . More notably, in t he restricted fram ework of Zari ski struct ures, t he Zilber Trichotomy Conjecture is t rue, as shown by Hru sho ski and Zilber himself.
T heor em 7.9.9 (Hr ushovski-Zilber) Let (A, {T n : n posit ive intege r}) be a Zarisk i struct ure, A be a strongly m inimal st ru cture with domain A such that, for eve ry posit ive in teger n , th e su bsets of A n definable in A are ju st th e cons iructible sets in T n . If A is not locally modular, th en A interprets an algebraically clos ed fi eld J( , and J( is unique up to definable isomorphism. Moreover, for eve ry positive integer n , th e subsets of K " definable in A coinc ide with the on es definable in J(.
7.10
Two algebraic examples
Let us s ummarize briefly some of the main notions introdu ced in t his chapter by examining t wo relevant classes of algebraic struct ures, and their first order th eori es: differentially closed fields of characteristic 0, and existent ially closed fields with an automorphism (again in charact eristic 0). Both these examples play an important role in the mod el t heoretic solution of some not abl e qu estions of Algebraic Geom et ry: we will describe t hese probl ems and t heir solut ion in t he next cha pter.
:
7.10. T WO A LGEBRA IC EXA M PLES
287
1. D C Fa . F irst let us deal wit h differenti ally closed fields of characterist ic O. Let us recall once again t hat t heir t heory D C Fo is complete and quantifier elimina ble in its natur al lan gu age L , containing the sy m0, 1, D and nothing mor e. So definabl e sets are easy t o bols classify: as we saw in Chapter 3, t hey includ e t he zero sets of (finite) systems of differenti al polyn omials - in oth er words, t he closed sets in t he Kolchin t opology - as well as t heir finite Boolean combinat ions t he construct ible sets in t his topology -, bu t nothin g else. As a ty pica l Kolchin closed set in a different ially closed field (K, D ) let us mention t he field of const an t s C (K ) = {a E K : D a = O}. T his is an algebraically closed field - ju st as K -, and is strongly minim al even in L; in fact , D is identically 0 on C (K ) a nd so adds no fur ther definabl e objects to th e field st ruct ure on C (K ).
+, " - ,
DC Fa eliminates the imagin aries, t oo. Mo reove r DC Fa is w-st able with Morley rank w, so ind ependence makes sense in D C Fa , and ind eed it is ruled by Morley rank: for ii , A and B as in Section 7.2,
s +A B
{:::=;>
R M (tp (il/ B )) = R M (tp (il/A )).
Of course t his raises t he question of characterizing algebraic ally Mo rley ra nk wit hin differenti ally closed fields of cha racterist ic O. Bu t t here are also oth er ways of describing forking an d inde pendence in DC Fa, having a pret ty algeb ra ic fl avour. For inst an ce, one can pr elimin arily obser ve t hat , for every small A , acl (A) - in t he model t heo ret ic sense - is ju st t he (field t heo retic) algebra ic closure of t he different ial subfield generated by A Q(Dia : a E A , i EN); at t his point , B ju st means one ca n realize t hat, for ii, A and B as usu al , ii t hat acl(AUil) and acl(B) are (algebraically) ind epend ent over acl( A). Among other things, this cha racterization sugges ts a n alternative rank notion, specifically concerning th e differential fr am ework: this is called differential degree or D-degree and denoted D-dg: for H a differential field a nd ii a tuple of elements in n, D-dg(il/H) is th e t ranscende nce degre of the differenti al field generated by H U ii over H . So, for ii, A an d B as before, and A and B differential subfields for simplicity,
+A
il
+AB
{:::=;>
D-dg(il/B ) = D-dg (il/A ).
However we have t o be ca reful here: t he last equivalence does not mean t hat R M a nd D -dg coincide . Their relationshi p, an algebra ic cha racterization of R M in D C Fa and t he con nection amo ng differenti al
288
CHAPTER 7. CLASSIFYING
degr ee, Morley rank and other possib le ranks in D C Fo a re described in the refer ences ment ioned at the end of th e chapte r. Now let us deal with biinterpret ability, in particula r let us consider st ro ngly minimal sets in differ entially closed fields IC of charact eristic O. They include the cons tant s ubfield C (IC ) (which also has different ial degree 1, as it is easy to check). C (IC ) is not locally modular, in fact the a rgume nt prop osed in t he last sect ion for algebra ically closed fields applies to C (IC ) as well. But what is most remarkabl e in this sett ing is a theorem of Hru shovski and Sokolovic sayi ng that Zilber Trichot omy Conjecture holds withi n strongly minimal sets in DCFo. In fact all t hese sets are Zariski structures, and so obey the Hru shov skiZilber Th eor em . We can say even more: any strongly minimal set S which is not locally modular, and henc e interprets an infinite field, doe s interpret t he field of constants C(IC) up to a definable isomorphism . We will provide more details about t hese mat te rs in Section 8.7 .
2. AC F A. Now we deal with existe nt ially closed fields with a n autom orphism . For simplicit y, we still work in cha racterist ic o. Let AD F A o denote the corresponding theory in the natural language L = {+ , ., - , 0, 1, O" } where 0" is the sy mbol representing the a utomorphism . Recall that, t his ti me , fixing t he characteristic is not sufficient to ensure com pleteness: in order to characterize a mod el of AC FAo up to element a ry equivalence, one has also to describe the act ion of t he a ut om orphism on th e prime subfield Q. Moreover ACF A o does not eliminate t he qu an tifiers in L, alt hough it is obviously model complete (as a mod el companion) . Accordingly definabl e sets exhibit some more complications than in the differential case. In fact , t hey include the zero sets of (finite) syst ems of difference polynomials , as well as their finite Boolean combinat ions; the former are the closed set s, a nd t he lat ter t he constructible ones in a suitable topology. But now , as qu an tifier eliminat ion fails, we have to conside r also the projections of const ruct ible sets - a nd nothing else, owing to model completeness - to ca pt ure the whole class of definabl e sets. An exam ple of a closed set in a mod el (IC , 0") of AC F A o is it s fixed su bfield Fix (O" ) = {a E I< : er(a) = a}. This is not algebraically closed (in particular it is not st rongly minimal); but one can see t hat it is a pseudofinite field , so an infinite model of the theory of finite fields. ACF A o elimi nat es the imaginaries. T his time no existentially closed field (IC, 0") with an au t omor phism is w-st able , or even st able. How-
289
7.11. REFERENCES
ever (K, a) is sim ple (as well as its fixed su bfield , a nd a ny pseudofinite field) . So ind ep end ence makes sense in ACFAa, and comes directl y from forkin g, bu t ca nnot be ruled by Morley ran k. Any how an explicit algebraic characterization ca n be don e as follows. We work for simplicity in a big saturated mod el (K , a) of AC F Aa. F irst one obser ves t hat, for every small A, acl(A) coincides wit h t he algebra ic closure in t he field t heoret ic sense - of t he differ ence subfield generated by A Q (a i (a ) : a E A, i E Z )
(here we use t he cha racterist ic 0 assu mp t ion; prim e cha racterist ics cau se some major trouble). At thi s point one shows th at, for ii, A a nd B as usu al , ii t A B ju st means that acl(A U il) and acl(B) are (algebraically) ind epend ent over acl (A). This yields an appropriate notion of rank , of a pret t y algebraic flavour , called difference degree or a -d egree and deno ted o-dq: for H a difference fi eld a nd ii a t uple of elements in n, a -dg (il/ H ) is t he t ra nsce nde nce degree of t he difference fi eld generated by H U ii over H . When finite, t he difference degree can reason abl y repl ace Mo rley rank and provides a good notion of dimension in t his unstable setting; on t he oth er side , when a-dg (il/ H ) is infinite, t hen clearly t he a i (a) 's (when i ra nges over integers) are algeb raic ally inde pe ndent over H. So, for d, A an d B as before, a nd A and B difference s ubfields for simp licity, ii
tA B
{:::::::?
a - dg (il/B ) = a - dg (il/A )
at least when t he la t ter degrees are finite. Wh en X is a ny definabl e set in f{ n , the difference degree of X over H a - dg (X/H) is t he maximal difference degree of a t uple ii in X over H . In particul ar the fixed subfield of K get s difference degr ee 1. In this sense, Fi x (a) is a "minimal" definabl e infinite set of K. Notably, an adapte d version of Zilber Trichotomy Conj ecture holds for these "minimal" sets in ACFAa, a nd even ensur es in part icular t hat, very roughly speaking, Fix (a) is t he only non "locally modul ar" exam ple among t hese structures.
7.11
References
T he classification issue fro m t he point of view of Descripti ve Set T heory is treated in [68]; t he par ticul ar and int riguin g case of torsionfree a belian groups of finit e rank is dealt wit h in [163]. Finite dim ension al vect orspaces
290
CHAPTER 7. CLASSIFYING
wit h two distinguished endomorphisms over a fixed field, and the wildness of t heir classification problem are described in [136] or, more specifically, in [137]. The mai n references on Shelah's classificat ion theory are just t he Shelah book [149] and its revised and up dated version [151]. Most of t he topics of this chapter are treated there in detail. Another good an d per haps mor e accessible source on classification and stability t heory is [8]. See also Makkai's paper [101] . Vaught's Conjecture is proposed in [174], and its solution in the w-stable fram ework ca n be foun d in [152]. Lascar's pap er [84] provides an enjoyable disc ussion of t his matter. The (uncountable) spectrum problem for complet e countable first order theor ies is fully solved in [53]. Simple theor ies were introduced in [149], but it was Kim who showed, together with Pill ay, t heir relevance within the classification program: see [71] and [73]. Kim again observed the key role of symmetry, transitivity a nd local character [72]. Wagner's book [175] provides a general a nd exhaustive report on this theme. As already said , stability, superst ability and the further dichotomies ari sing in t he classification program are treated in Shelah books [149, 151], in [8] or also in [101]. [85] provides a nice and terse introd uction to stability, using and emphasizing t he notion of heir and coheir. [83] pursues t his approach and deals in particular wit h Rudin-Keisler order and strong regu larity. The effectiveness aspects of Shelah 's classification progr am is discussed in [114], while [2] examines its connect ions with Stationary Logic. Turning our attention to t he algebraic examples, let us mention [136] or also [56] for modules, a nd [19] for pseudofinite fields . [110] treats differentially closed and separably closed fields, and includes a wide bibliographical list on them . [62] a nd [155] provide ot her key references on DCFo; see also [134]. Existentially closed fields wit h an automorphism are j ust t he su bject of [20]. An explicit exa mple of such a field can be found in [58] and [88]; see also [95]. Shelah's uniqueness theorem is in [148], Morley's theorem in [117]. Anot her proof of Morley 's Theorem is given in [9]; see also Sack's book [146], or [57]. T he Ehrenfeucht - Mostowski models quoted in Sect ion 7.8 are int roduced in [38]. Finally, let us deal with biinterpretability. Malcev 's correspondence is in [102] while Mekler's th eorem on nilpotent groups of class 2 is in [113]. Zilber 's program is developed in [182], where Zilber's Conjecture is also proposed . The negative solution of this conjecture is in [59], and the HrushovskiZilber theorem on Zar iski structures in [64].
Chapter 8
Model Theory and Algebraic Geometry 8 .1
Int roduction
We have often emphasized in t he pas t chapters t he deep relati onship bet ween Model Theor y and Algebra ic Geometry : we have see n, a nd we are going t o see also in t his cha pter t hat seve ra l relevan t notions a rising in Algebra ic Geom etry (like variet ies, morphisms, manifolds, algebraic gro ups over a field K ) are definabl e object s a nd are conseq uent ly concerne d wit h t he mod el t heor etic machinery develop ed in t he previous pages. For inst an ce, when K is algebraicall y closed , t hey a re w-stable st ruct ures.T his connection ca n yield, a nd is act ually yielding, significa nt frui ts in both Mod el T heory and Algebr aic Geom etry. On th e one hand , seve ral t echniques a nd ideas originated a nd employed within t he specific sett ing of Algebraic Geome t ry ca n inspire a more abstract model th eor etic treatment , applying to a rbit ra ry classes of st ruct ures. In this sense Algebraic Geometry over algebra ically closed fields can suggest new directions in th e study of w-stability: we will describe this connection in many sect ions of t his chapter. However a parallel analysis ca n be developed inside other relevant areas, like differentia lly closed fi elds (and Differential Algebraic Geom etry) , or existe nt ially closed fields with a n a ut omor phism , and so on . On t he oth er hand , it is right t o observe that t he benefits of t his relationship regard not only Model Theor y, bu t also, and releva nt ly, Algebraic Geomet ry. In particular, we will propose some prominent problems in Algebra ic Geometry, whos e solution do es profit by Model Theor y and its t echniques. This will be the aim of t he final section of this cha pte r.
291
292 CHAPTER 8. MODEL THEORY AND ALGEBRAIC GEOMETRY
8.2
Algebraic varieties, ideals, types
Let J( be a field , n be a positive integer. We already introduced in th e past chapters the (algebraic) varieties of K" : They a re t he zero sets of finite systems of polynomials of J([X] (where x abbreviates, as usual, (Xl , .. . , x n)), a nd so are definabl e in J(. Moreover they form the closed sets in the Zari ski t opology of K"; accordingly even the Zariski open or const ructible sets ar e defina ble in J( . But the varieties of K" are also closely related to the ideal s of J([X]. In fact one can define a function I from vari eties to ideals mapping a ny variety V of K" into the ideal I(V) of t he polynomials f(x) in J([X] such that f(a) = 0 for every a in V . Checking that I(V) is ind eed a n ideal is straight for war d; I(V) is even a radical ideal , in other words it coincides with its radical rad I (V ): if f(x) E [([X] and , for some positive int eger k, fk( x) E I(V) , t hen f (x) already occurs in I (V). In particular I is not onto. Bu t there is also a nother function V in the other direction , from ideals to varieties, mapping any ideal 1 of J([X] (in pa rt icular a ny ra dical ideal) into t he set V(I) of t hose elements a E K" a nnihilating all the polynomials of I
V (1) = {a E J(n : f (a)
= 0 vf (x)
El}.
Due to t he Hilbert Basis T heorem, I is finit ely generated , and so V(I) is a variety. Ind eed , any vari ety V can be ob t ained in this way by definition; in oth er word s V is onto. Not ice also t ha t V(I) = V(rad I) for every ideal I . The definition of I an d V trivially impli es t ha t, for every ideal I of J([X] , I(V(1)) "2 I. As I(V(I)) is a radical ideal , I(V(I)) "2 rad T, Hilbert 's Nullstellensatz (see Ch apt er 3) ensur es that , when J( is an algebraically closed field, eq uality hold s: fo r every ideal I of J([X] ,
I(V(1)) = rad I , It is easy t o deduce that , if J( is algebraically closed , t hen I a nd V deter mine t wo bijections, the one inverse of t he other, betw een varieties of K" and radical ideals of J([X] . We will st ill den ote these restricted bijections by I , V respectively. Notice t hat both reverse inclusion : for instan ce if V , W a re two varieties of K" , then
I(V) "2 I(W)
~
V
~
W.
We assume from now on that J( is a n algebraically closed field. By t he way recall that, under t his condit ion , what is definable in J( is w-stable of finite Morley rank , becau se J( is st rongly minimal.
8.2. ALGEBRAIC VARIETIES, IDEALS, TYPES
293
Let us restrict our at tention from radical ideal s of K[X] t o prime ideals (t hose ideals I in K[X] such that , if a product of two polynomials of K[XJ lies in I , th en at least one factor polynomial is in I as well) . Parallely we con sider, among vari eties of K" , the irreducible ones , so t he non-empty vari eties V t hat ca nnot decompose as a union of two proper subvariet ies . It is easy to check that the previous bijections I and V betwe en vari etie s of K" and rad ical ideals of K[X] link irreducible varieties of K" and prime ideals of K[XJ: for every vari ety V of K"; V is irreducible if and only if I(V) is prime. Notice also that I(0) = K[XJ . A closer relationship links irreducible varieties and prime ideals. For inst a nce, it is known that every non-empty variety V of K " ca n be expressed as a finite irredundant union of irreducible varieties, and that this decomposit ion is unique up to permuting the involved irreducible varieties (which ar e con sequ ently called the irreducible components of V) ; th e irredundancy of the decomposit ion just means that no irreducible component of V is included in t he union of the other components. Sp ecularly, every proper radi cal ideal I of K[XJ can be expressed as a finit e int ersection of prime ideals minimal with resp ect t o inclusion ; even t his representation is uniqu e up to permuting the involved minim al prime ideals. On e ca n also realiz e th at , und er t his poi nt of view , for every non- empty vari ety V in K " , t he irredu cible components of V correspond to t he minimal prime ideals occurring in th e decomposit ion of I (V ). So far we have summa rized -some very famili ar t opics of basic Algebraic Geom etry. Now let Model Theor y intervene. As we saw in Section 5.3, prime ideals of K[XJ - a nd hence, through t hem , irreducible variet ies of K" - directly and na turally corres pond to n-types over I< . In fact , for a n algebraically closed field K , th er e a re t wo bijections i and p , one inverse of the other, between n-types over I< and prime ideals of K[XJ. Basically, for every n-type p over I<,
i(p) is the ideal of the polynomials f(x)
E
I<[XJ such that the formula
f(11) = 0 is in p,
a nd, conversely, for every prime ideal I of K[XJ ,
{J(11) = 0 : f( x) E I} U {.(g(iJ) = 0) : g( x) E I<[XJ - I} enl arges t o a unique n-typ e p(I) over I<. Accordingly, for every irred ucible variety V of K " and polynomial f (x) E I<[ xl, f (ii) = 0, Vii E V {::} f (x) E I(V) {::} " f(11) = 0" E p (I (V) );
294 CHAPTER 8. MODEL THEORY A ND ALGEBRAIC GEOME Tny p(I(V)) is called a generic type of the variety V . More gen erally a generic type of an arbit ra ry non- empty variety V of K" is a ge ne ric type of an irr educible compon ent of V . T his model t heoretic notion of generic type just corresponds to the idea of a ge neric poin t of a n irreducible variety V int roduced in Algebraic Geometry: the latter is a po int just a nnihilat ing t he polynomials in I(V) a nd not hing more , and so can be eq uivalent ly defined as a realizati on of the generic type p(I(V)). It can be obtained as follows. As V is irreducible, I( V) is prime an d conseq uent ly t he quotient ring /C[X] /I(V) is an integral domain ; /C[X]/I( V) contains a subring {k + I(V) : k E I<} isomorphic to /C and a t uple + I( V) a nn ihilat ing just the polynomials of I(V) ; so t he field of fractions /C(V) of /C[X]/I(V) extends /C - up to isomorphism - a nd includes a generic point a(V) = x + I(V) of V . To conclude this section let us observe what follows.
x
Proposition 8.2 .1 Let n be a positive integer, /C be an algebraically closed fie ld, V be an irreducible variety of K" , 0 be a Za riski open set of K " satisf ying V nO ::j:. 0. T hen th e generic typ e p of V con tains th e formula "v EO".
Proof. In fact V - 0 is a variety properly included in V ; conse quently I( V - 0) =:> I(V). If p does not con t ain "v E 0 " , then p has t o include "v E V - 0 " , a nd hen ce ever y formula "f (v) = 0" when f (x) ranges over I(V -0) ; accor dingly, for some polynomial f( x) (j. J(V) , "J(v) = 0" belo ngs to p: a contrad iction . .,.
8.3
Dimension and Morley rank
We main t ain throughou t t his section our assumption t hat /C is a n algebr aically closed field . Let V be an irreducible variet y of K" : Algebraic Geometry equ ips V with a dimension in the followig way. As we saw in the last section , there is a minimal field /C (V) extend ing /C by a realization a(V) of the generic type of V , in other words by a generic point of V . The dim ension of V (dim( V)) is just t he transcendence deg ree of /C CV) over /C . T his m ak es sense for a n irred ucible V , bu t can be eas ily extended t o an y non-em pty variet y V of K", In this en larged setting the dim ension of V (dim(V)) is t he maximal di mension of a n irr educible component of V. F inally, t he dim ension of a con structible no n-empty set X dim (X) is the dime nsion of t he closure of X in t he Zariski t opology (a non-em pt y variety) .
295
8.3. DIMENSION AND MORLEY RANK
On the other side every vari ety V of K" (irreducible or not) and, more generally, every constructible set X ~ K " is definable in K; K is algebraically closed, hence w-stable; accordingly V and X have th eir Morley rank . We want t o compare the dimension and the Morley rank of V , or X , and to show that they coincide. We start by examining an irreducible var iety V. Lemma 8 .3.1 Let V be an irreducible variety of K" , p be its generic type.
Then dim (V) = RM(p) .
Proof.
p is realized by a(V) in K (V) . So the MorIey rank of p equals the transcendence degree of K(V) over K (see Section 6.1), and hence the dim ension of V.
•
Lemma 8.3.2 Let V , W be two irreducible varieties of
their generic types. If V C W , then RM(p) > RM(q).
x»,
p, q denote
Proof. V C W impl ies I(W) "2 I (V) and hence (*) for every f(x) E K[X] , if f (a(V))
= 0, t hen
f(a(W))
= 0 as well.
In particular t he t ranscende nce degree of K(V ) over K is not smaller t ha n that of K (W ) over K , and so RM (p) 2: RM(q) . Now ass ume RM(p) = RM(q), t hen K (V) , K(W) have the same transcend ence degr ee over K. Recall t hat K (V) = K (a(V )), and similarly for W . (*) impli es that , if i }, .. . , i m ~ n and ail (W ), , aim(W) form a t ransce ndence basis of K (W ) over K , t hen ail (V ), , aim(V) are algebraically independent over K and so form a transcendence basis of K(V) over K. Accordingly one can define an isomor phism of Kw = K (ail (W ), .. . , aim(W)) onto Kv = K(a il (V) , . .. , aim (V )) fixing K pointwise and mapping ai(W) into ai(V) for every i = i}, .. . , i m . This isomo rphism can be enlarged in t he usu al way to an isomorphism between Kw [x] and Kv [X]. By using (*) once again, one sees t hat , for every j = 1, ... , n with j =I- i} , ... , i m , the mini mum polynom ial of aj(W) over Kw must correspond to the minimum polynomial of aj(V) over Kv in this isomorphism. Acco rd ingly we obtain an isomorphism of K (W) onto K (V) fixing tc pointwise and mapping a j (W) into a j (V) for every j = 1, . . . , n. Bu t a(V) realizes p and a(W) realiz es q, when ce p = q and , in conclusion , V = W. • Now we can show t hat dim ension and Morley rank coincide for a n irreducible variety V.
296 CHA P TER 8. M ODEL THEORY A ND A L GEBRA IC GEOMETRY Theor e m 8.3.3 Let V be an irreduci ble varie ty of K", dim( V ), GM(V) = 1.
T hen RM(V ) =
Proof. Let p be t he generic ty pe of V . p is t he only n-type over /C containing t he formul a "5 E V " th at define s V, and satisfying V( i(p)) = V. If q is another n-ty pe over /C cont aining "5 E V" , t hen i(q) :J i(p), whence V (i (q)) C V (i (p)) = V. By Lemma 8.3.2, RM (q) < R M (p). T hen R M (V ) = R M (p) and GM(V) = 1. By Lem ma 8.3.1, R M (V ) = R M (p ) = dim (V ). • C o r o llary 8.3 .4 Let V be an irreducible varie ty of K " (with the relat ive topology of th e Zariski topology) . If 0 is a no n-empty open set of V , then RM (O ) = RM(V ) . IfW C V is a closed se t of V, th en RM(W) < R M (V).
Proof. T he forme r claim follows from Proposition 8.2.1 and t he fact t hat, if p is t he generic point of V , t hen R M (p) = R M (V ). At t his poi nt t he lat ter clai m is a consequ ence of t he fact t hat V has Morley degree 1. ... C oro llary 8. 3.5 Le t V be a no n- empty variet y of K", Th en R M (V) = dim(V), furth ermore G M (V ) equals the number of th e irredu cible com ponents of V having th e same dim en sion as V.
P roof. V is t he (finite) union of its irreducible components. Then t he Morley ra nk of V coincides wit h t he maximal ra nk of its com po nents. So by T heore m 8.3.3 and the definition of dim (V) R M (V ) = di m (V ). Moreover, if Vo a nd VI are two different irr edu cible components of maximal rank of V, t hen Vo n VI is a closed subset of Vo properly includ ed in Vo. By Corollary 8 .3.4, R M(VonVI) < R M(Vo). This implies t hat G M (V) equals the number ... of the irr educible components of maximal rank in V.
Dim ension and Morl ey rank coincide even for constr uct ible sets X ~ K" : Recall t hat, owing to Tarski's qu an tifier elimination Theor em, constructible just mean s defina ble in /C . Furth ermore a const ruct ible X ~ K " ca n be re presented as a union of finit ely many sets, which are in t heir t urn t he intersection of a variety W - so a Zariski closed set, t he zero set of a finite system of eq uations - a nd a Zari ski open set 0 - t he set of t he elements of K " satisfying finit ely many inequ ations
8.4. MORPHISMS A ND DEFINABLE F UNCTIONS
297
with 90(£), " " 9s(£) E K[Xj, or also, equivalent ly, a single inequa tion
II9j(£)
#0
- .
j ss
An open set defined by a unique inequation is called principal. Corollary 8.3.6 Let X ~ tc- be construct ible (hence definable). Th en RM(X) = dim (X) . Moreover, if X denotes th e Z aris ki closure of X , th en R M(X) = R M(X) and RM(X - X) < RM(X). Proof. We know dim(X) = dim(X) , and dim(X) = RM(X) (by Co rollary 8.3. 5) . So the form er claim is don e if RM(X) = RM(X). As observed befo re, X a finite union of sets of t he form W nOwher e W is a nonempty variety of JCn and 0 is op en in JC n. As a ny non- empt y variety of JCn decompo ses in its t urn as the union of its irredu cible components, we ca n assume th at every variety W occurring in t he above representation of X is irreducible. By Corolla ry 8.3.4, RM(W n 0) = RM(W) = dim(W). Con sequ ently the Morl ey rank of X (that equa ls the maxim al rank of the sets W n 0) coincides with the Morley rank of X . This proves t he former claim. Bu t , by Corollary 8.3.4 once again, RM(WnO) < RM(W) for Wand 0 as before and W irreducible. So, in conclusion, RM(X - X) < RM(X) . ...
8.4
Morphisms and definable functions
JC still denotes an algeb raically closed field. Let n , m be positive integers , V , W be two algebr aic vari et ies in JCn, JCm respectively. Algebraic Geomet ry defines what a morphism from V to W is: it is a function f from V int o W such t hat, for every i = 1, . .. , m, t he com posit ion f i of f a nd t he ith projection of K m onto K is a polynomial map. One easil y sees that a mo rphism is a cont inuous fun ction with resp ect to the to pology ind uced on V a nd W by the Za riski topology. But what is rem arkabl e for our purposes is t hat a variety morphism is always defin abl e in JC. For inst an ce, if f is, as above, a morphism from V to W , t hen "f (v) = W" is defined by the formula
"v E V"
1\ " $ E
W"
1\
1\
" f i(V) = uu",
l
Conversely what ca n we say about an arbitrary defin able fun ction f in JC? Certainly both t he domain and the image of f a re definab le sets . Furthermo re, if the image of f is a subset of K m, t hen, for every i = 1, . .. , m,
298 CHAPTER 8. MODEL THEORY AND ALGEBRAIC GEOMETRY
the composit ion f i of f and t he i-th projection of K ": onto J( is definable. So we are restricted to characterize definable functions from a subset of K " into J( , for some positive integer n. In this framework one ca n observe what follows . Theorem 8.4.1 Let f be a definable fun ction from K " into K.. . Th en th ere are a non-empty open subse t 0 of K.. n, a rational fun ction r and (wh en K.. has a prime characteristic) a positive integer h suc h that • if car K.. = 0, th en f equals r on 0; • if car K.. is a prime p and Fr denotes th e Frobenius map from K.. to K.. (that mapping any a E J( into Fr(a) = a/'], th en f coincides with r -:>. r on O .
Just to underline th e power of this result, let us recall that , owing to Corollary 8.3.4, every non- empty op en subset 0 of K" has th e sa me Morley rank n as K" ; while th e Morley rank of K.. n-o is smaller (for , K" is an irreducible vari ety of rank n). Secondly, it is worth recalling th e general fact that , if f is a fun ction from a vari ety V of K " into K.. and , for every a E V , there is an op en neighbourhood 0 of a such t hat f equa ls some ration al funct ion in O n V , t hen f ca n be globa lly expressed as a polynomial fun ction . Now let us show Theor em 8.4. l. Proof. Let Q be the uni verse of the theory of K.. , t} , .. . , t« E Q be algebraically independent over K.. . As f is J(-definabl e , an y a utomorphism of n fixing K.. and t l , • • • , t n pointwise acts identically also on f(i) (f denote s here th e tuple (t}, ... , tn)). Whence j(i) is in dclt K n i) . So, if K.. has cha racterist ic 0, then f(i) = r(i)
for some suitable rational function r with coefficients in prime characteristic p , then
J(,
while, if K.. has
where r is as before and hp is a positive integer. Put s = r when car K.. = 0, s = r otherwise. The eleme nts in K " where f coincides with s form a set X definable in K.. (just as f and s) , and th e form ula "s (v) = f (v)" defining it is in th e type of f over J(. As t} , ... , t n are algebraically independent over K.. , t his t ype has Morley rank n . Hence RM(X ) 2: n . As X ~ K" ; t he Morl ey rank of X must equa l n , a nd RM (J( n - X ) < n. It follows th at t he
r -:» .
299
8.5. MA NIFOLDS Zari ski closure of K " - X has Morley ra nk an open set 0 in X of Morley rank n where
8.5
< n , and so its complement is f = s. •
Manifolds
Throughout this section IC still denotes an algebra ically closed field and n a positive integer. We deal here with (ab stract) manifolds in IC n a nd we show that th ey are defin abl e objects. F irst let us recall their definition . Definition 8 .5.1 A manifold of IC n is a structure V = (V, (Vi, f i) i5: m ) where m is a natural and • V is a subset of K " (called atlas); • V o, ... , V m are subsets of V , and V is th e union Ui<m Vi ; • fo r every i ~ m , f i is a bijection of Vi onto a Zariski closed set Vi (a coordinate chart of th e atlas V) ; • for i ,j ~ m and i
i- i , f i(Vi n Vj)
=
o.,
is an open sub set of Vi;
• for i, j ~ m and i i- i . f ij = fi . f T 1 (a biject ion between Vji and V ij ) can be locally exp ressed as a tu ple of rat ional fu n ct ions.
Manifolds include several familiar exa mples. Examples 8.5.2 1. Every algebraic vari ety (so every Zari ski closed set ) V of IC n is a manifold , provid ed we set m = 0 a nd choose Ui, = Vo = V as the only coordinat e cha rt of t he atlas; the res ulting man ifold is called affine . 2. Let 0 be an op en principal set of IC n; 0 is defined by a single inequ at ion -' ''g(v) = 0" ; notice that the formula "g(v) . V n +l = 1" defines a closed V in IC n+l , a nd it is easy to control t hat the projection of K n +l onto K " by t he first n coordina te s determines a bijection f of V onto O . Accordingly (V , (V , f -l )) is a manifold with t he only chart O . Such a manifold is called sem ia ffine . 3. Also the projective space p n(IC) can be equipped with a manifold structure. In fact, view p n(IC) as t he quo tient set of K n+l - {a} with resp ect to the equivalence relation rv linking two non zero tu ples x = (xo , Xl, . . . , x n) a nd fl = (Yo, YI , . .. , Yn) in K n+l if and only
300 CHAPTER 8. MODEL T HEORY AND ALGEBRAIC GEOMETRY
if t here is some k E J( such that Xi = kYi for every i ~ n. For x E J( n+l - {O} , let (xo : X l : •• . : x n ) be t he class of x with resp ect t o t his relation . Moreover , for i ~ n , let
• A i de note th e set of th e elements (x o : such that Xi i= 0,
Xl : • • • :
x n ) in p n(!C )
• f i be the function of A i int o K " mapping any (xo : X l
.In (3Zll. Xi '
Xi _l
· · · , ~,
5.±.!. xi
~)
, •• . , xi
: ... :
xn )
•
It is st ra ight forward to check that (pn(!C), (A i, Ji)i5:. n ) is a manifold .
Notice t hat affine and semiaffine var iet ies are definable -even as structuresin /C . Moreover p n(!C ) is interpretable in !C both as a set (since t he relation rv is 0-definable) and as a manifo ld . But a lgebraically closed fields uniformly eliminate th e imaginaries, so we can view p n(!C) even as a definable st ructur e in !C. Mor e gen er ally one can show T heo rem 8.5.3 Let V = (V, (Vi , Ji) i5:. m ) be a manifold of a structure defina ble in !C.
«» .
T he n V is
Proof. As algebraically closed fields have t he uniform eliminat ion of imaginari es , it is sufficient t o show t hat V is a struct ure interpretable in !C . In fact, every map U, of t he atlas V (i ~ m) is definable in !C . V ca n be rega rded as the quotient set of t he disjoint union of t he cha rts U, (wit h i ~ m) with respect to the equivalence relat ion ident ifying Uij and Uji via f ij for every i < j ~ m; moreover , for every i ~ m , Vi can be definably recovered as t he image of U, by th e projection into the quotient set V , and f i is given by the invers e funct ion of this projection (restrict ed to Ui) . So our claim is proved if we show t hat, for every i, j ~ m with i i= i , f ij is definable. But f ij can be locally expressed as a rat ional function, and its domain Uij is an open subset of U, and accordingly can be written as a finit e union of principal open sets. So th e th eor em is a direct con sequence of the next resu lt.
Lemma 8.5.4 Let 0 be a prin cipal open of !C n, and let q(x ) E [([X] be a polynomial satisfying 0 = {ii E K " : q(ii) i= O}. Let f be a funct ion of 0 in to K" which can be locally expressed as a ratio nal fun ct ion. T hen there are a polynomial r( x) E [([X] and a positive integer m such that f(ii) = r(ii)/qm(ii) for eve ry ii EO . In particular f is defi nabl e.
8.6. ALGEBRAIC GROUPS
301
Proof. We know that 0 is canonically homeomorphic to the closed subset V of K n+l defin ed by q(v) . Vn+l = 1. Under this per spective f can be replaced by the functi on 1* of V into 1< mapping any tuple (ii, an+d E V in f(ii) . Eve n 1* ca n be locally expressed as a rational function , and hence as a polynomial function in (x, xn+d (by th e general fact we recalled before the proof of Theorem 8.4.1). So th ere is some polynomial s(x , xn+I} E 1<[x, xn+l ] such t hat
J*(ii, (q(ii))-l) = s(ii, (q(ii))- l)
vs En.
Let m deno te t he degree of s(x, Xn+l ) with resp ect t o Xn+l' T hen there is some polynomial r (x) E 1<[X] such that , for every ii EO ,
f(ii)
= J*(ii, (q(ii))-l) = qm r (a(-a~) .
..
Notice th at a manifold , when regarded as a definable structur e, may lose part of it s geometric features. For instan ce the Za riski closed subset of K 2 defined by Xl . (X2 - 1) = X2 . (X2 - 1) = 0 is an affine manifold , form ed by the line X2 = 1 and t he poin t (0,0) , a nd hence is th e disjoint union of tw o closed sets. However , consider the manifold given by t he proj ective line pl(K) (as seen in Exam ple 8.5.2, 3). Fro m the definable point of view, its atl as has two charts, each of them is a line and th ese lines coincide excep t a single point . So the resulting manifold is again the union of a line {(1 : x I) : X l E 1<} and a poin t (0 : 1), a nd as a definabl e object is qui te similar to the previous one. Bu t p l (K) is not the union of two distin ct closed sets. On t he oth er side, it is noteworthy t hat every defin able subset X ~ K " can be easily equipped with a manifold st ruct ure. In fact X decomposes as a union Ui<m (Vi n Oi) where m is a natural a nd, for every i ::; m , Vi is a Za riski closed of K" and O, is a pr incipa l open set , so th at Vi n O, is canonica lly hom eomorphic to a closed U, of K n+l , as observ ed before. On this basis, it is easy t o build a manifold structure on X (with Uo, ... , Um as atl as maps) . Furt her more a man ifold V , viewed as a definable structure, is w-stable.
8.6
Algebraic groups
A basic example of algebr aic group over a field K is the linear group of degree n over K GL(n, K) , where n is a positive integer. Observe:
302 CHAPTER 8. MODEL THEORY AND ALGEBRA IC GE OMETRY 2
• G L(n , /C) is a prin cipal op en of /C n , because it is defined by the diseq uat ion -, (det ( if) = 0) ; hence G L(n , /C) is canonically homeomorphic 2 t o t he Zariski closed of /C n +1 given by t he equat ion det( if) . vn2+ 1 = 1;
• t he product op er ation· in GL (n , /C) is a morphism of variet ies and so is definable. Accordingly the group G L (n, /C) is a st ructure definable in /C . Moreover , if we ass ume /C algebraically closed , GL(n, /C) is an w-st a ble group of finit e Morley rank . Also linea r algebraic groups are examples of algebraic groups. Recall t hat a linear algebraic group over a field /C is a closed subgroup 9 of some linea r group G L (n , /C ). In particular a linear algebraic group 9 is a variety over /C, hence is defina ble (as a grou p) in /C a nd is w-stable of finite Morley rank when /C is alg ebraically closed . Under t he last ass um ption, we can say even more: ind eed , for an algebraic ally closed /C , t he linear algebra ic gro ups are ju st t hose subgro ups of t he linear groups GL(n , /C ) which a re definable in /C . Let us see why. Theorem 8 .6 .1 Let /C be an algebraically closed fi eld, n be a posit ive integer, 9 be a subgroup of G L( n, /C ). Th en 9 is closed if and only if 9 is defi nable (in /C) .
Proof. Clea rly, if 9 is closed -in other word s 9 is a variety- , then 9 is definabl e. Con versely suppose t hat 9 is a definabl e group; let C be t he closure of G with resp ect to t he Zari ski topology, and let a be an elemen t of 2 C. Every open set of /C n containing a overlaps G. Conseq uent ly, for bE G , every open 0 including ba overlaps G; in fact , if ba E 0 , then a E b-10 ; b-10 is open because th e left multiplication by b is a morphism of varieties, and so is cont inuous; whence (b- 10) n G i= 0 and so 0 n bG i= 0; as bEG, bG is ju st G, hence 0 n G i= 0. In conclu sion , for every a E C, Ga < C. If th ere is any a E C - G, then Ga ~ C is disjoint from G and has the same Morl ey rank as G . So RM (G - G) ~ RM(G) , which contradicts Corollary 8.3.6. Hence C ~ G and G is closed . ..
As alread y said, linear groups a nd linear algebraic gro ups exe mplify algebraic gro ups. In fact an algebraic group over a field /C is defined as a manifold over /C ca rrying a group str uct ure whose product a nd inverse operations a re (manifold) morphism s . Of course, understanding t his definition preliminarily requires to stat e what a prod uct of t wo manifolds is, a nd t o realize th at t his produ ct is a manifold
8.6. ALGEBRAIC GRO UPS
303
as well; mo reover we should specify what a manifold mo rph ism is. We omit here the det ails. The former point is comparat ively simple and natural to cla rify, while the concept of morphism is more complex t o introduce; but , once this is done, one ca n easily show th at manifold morphism s a re defin able (as it is reason abl e to ex pect) . Hence, if K is algebraically closed , t hen every algebra ic group g over K is a st r ucture defin able in K an d so w-stable of finite Morley rank. As already said, linear algebraic groups are algebraic gr oups; in fact they just correspond to affine (or also semiaffine) manifolds. And indeed Theorem 8. 6.1 ca n be regarded as a parti cular cas e of a general result ensuring that every group definabl e in an algebraically closed field K is an algebraic group over K up t o definabl e isomorphism. This fact was shown by Hrushovski (and Van den Dries) , who observ ed t hat it is impli citl y contained in some results of A. Weil. So it is commonly quoted as the Hrushovski-Weil Theorem. Theorem 8 .6 .2 (Hrushovski-Weil) Let K be an algebraically closed field and g be a group definable in K. Th en g is isomorphic to an algebrai c group over K by a fun ction definable in K
Let us spe nd some more words about the connection between algebraic groups a nd w-st a ble groups. We have seen that every algebraic group over a n algeb raically closed field K is w-st abl e of finit e Morley ra nk . Of course w-st able groups include furt her relevant examp les: for ist an ce, a ny divisible torsionfree abelian group - so basically an y vectorsp ace over Q - is w-stable, a nd even stro ngly min imal. More generally, it was shown by Angus Macintyre that the w-stable (pure) abelian groups are just the direct sums of a divisible abelia n group and a n abelian group of finite exponent . However the techniques used in t he investiga t ion of a belia n groups do not seem appropriat e to handle w-stable groups. On the cont ra ry, algebraic groups and t heir t heory fit very well for w-stable groups. This is not surprising. In fact , even neglecting the sim ila rit ies we emphasized in t he last sect ions between va rieties an d definabl e sets, or dimension and Morl ey rank , and so on , we can recall t ha t several notions introduced in Chapter 6 for st udy ing w-st abl e groups clearly come from Algebraic Geometry. In this sett ing , it is worth me nt ioning t he following conjecture, proposed by Ch erlin in 1979. Conjecture 8 .6 .3 (Cherlin) Let g be an w- slable group of finit e Morley rank. If g is si mple, then g is an algebraic group over an algebraically clos ed field.
304 CHA PTER 8. M ODEL T HE ORY AND A LGEBRA IC GEOMETRY
Ch erlin 's Conje cture is still an op en qu esti on. We should also point ou t t hat some remarka ble pro gress in st udying w-stable groups of finit e Morley rank has been obtained by using ideas and tec hniques coming from finite groups, in particular from t he classification program of finite simpl e groups.
8.7
The Mordell-Lang Conjecture
Every promise must be honoured . And consequently, after em phasizing so man y t imes t hat Mo del Theor y does significant ly a pply t o Alge bra ic Geo met ry, here we are t o propose one a pplication (indeed a beau tiful and deep application, in our opinion ): Hru shov ski 's proof of a qu estion of Lan g usually called Mordell-Lan g Conjecture. Wh y is this solut ion notewor thy? Basically because it is t he very first proo f of t his conject ure, at least in t he genera l for m we will state in 8.7.6 below; bu t also, an d mainly, becau se it la rgely involves Model Theor y (strongly min imal sets, Zari ski str uct ures , differentially closed a nd separably closed fields , as well as the materi al of t his chapter). So let us introd uce t he Mordell-Lang Conject ure, and briefly sket ch its hist ory. We assume some acqua intance with Algeb raic Geometry. T he qu estion originally rose within Diophantine Geo met ry, which deals wit h the roo t s of sys te ms of polynomials over th e ra tion al field Q or also over a number field F (that is a n extension F of Q of finite degree). T his was t he setting where Mordell ra ised in 1922 t he following problem. Conjecture 8.7.1 (Mo rdell) Let F be a number field, X be a curve of genus > l over F. T hen X has only finit ely m any F -rationals points. Incident ally recall t hat a curve X of genus 1 is an ellipt ic curve, a nd so is naturally equipped with a gr oup structure . In a mor e abstract persp ective, on ca n obser ve what follows . Remarks 8.7.2 1. A curve X of genus 2': lover F is a Za riski closed subset of it s J acob ian J (X ). 2. A t heorem of Riema nn says t hat t he J acobian J (X ) is an ab elian variety (t hat is a connected complete algeb ra ic group); by t he way, every a belia n variety is actua lly a n abelian group. 3. A t heorem of Mordell and Weil ensures t hat, if A is an abelia n vari ety in t he complex fi eld defined over our number field F , t hen t he set 9 of t he F-rational points in A is a finit ely generated subgroup.
8.7. THE MORDELL-LA NG CONJECT URE
305
So Mordell's Conj ecture ca n be restated mor e genera lly as follows. C onjecture 8 .7 .3 Let A be an abelian varie ty of C , X be a curve of C em bedded in A , 9 be a fi nit ely generated subgroup of A . T hen either X is an elliptic curve , or X n G is fi nite. A simila r qu estion was raised by Manin a nd M umford in 1963. C onject ure 8. 7 .4 (Manin-M umford) Let A be an abelian variety ofC , X be a curve of C em bedded in A , 9 = Tor A be the torsion subgroup of A. T hen either X is an elliptic curve, or X n G is fi nite. Actually the orig inal form of Manin-M umford Conjecture said that, if X is a cur ve of genus > 1 and A = J( X) is its J acobian , th en X n Tor A is finit e. Bu t t he more general stateme nt given in 8.7.4 is eas ily obt aine d as in th e Mordell case . A possible unifying approac h covering both the Mordell a nd t he ManinMumford problem uses t he notion of gro up of finite type: in our characte ristic 0 fr am ework, t his ca n be introduced as an abelia n gro up 9 wit h a finitely generated subgroup S such t hat, for every g E G , t here is some posit ive int eger m for which mg is in S . In fact , every finite ly gene rated abelian gro up 9 is of finit e type (just take S = G) , a nd every to rsio n group is of finite ty pe as well (via S = {O}) . Accord ingly the conjectures of Mordell an d Manin-Mu mford can be rega rded as two parti cular cases of t he following mo re ge nera l qu estion. C onject ure 8 .7 .5 Let A be an abelian varie ty over C , X be a Zari ski closed s ubset of A , 9 be a su bgroup of finit e type of A. T hen X n G is a (possibly empt y) fin it e uni on of cosets of su bgroups of g. T his statement was formul at ed by Lang in t he sixt ies, and is usually called th e Mordell-Lang Conjecture. As underlined before, it impli es a positi ve a nswer t o Mordell's Conjec t ure: to see this, ju st take a curve X o of genu s > lover a number field F , embed X = Xo(C) int o its J acobian A = J(X ) a nd apply t he Mordell-Weil T heore m ensuring th at t he group 9 of F-ration al points in A is finitely generate d . Accordingly decomp ose X o = X n G as a finite union of cosets a + H where a E G and H is a subgroup of g. Take a coset a + H . Its closure a + H is includ ed in X o - an irr edu cible set of di mension 1 -. Conse quent ly, if a + H is infinit e, then X o ju st equa ls a + H an d so inherit s a group st ructure , and genus S; 1. T his means t hat, if t he gen us of X o is > 1, t hen every coset a + H must be finite, whence X o itself is finite .
306 CHAPTER 8. MODEL THEORY AND ALGEBRAIC GEOMETRY
These are the questions we wish to deal with. Now let us report about their solution. Mordell's Conjecture was proved by Faltings in 1983. The echoes of this result spread far and wide, also because it implied an asymptotic solution of Fermat's Last Theorem: in fact, by applying Mordell's Conjecture (or , more precisely, Falting's Theorem) to the projective curve over Q
for n ;::: 3, one gets only finitely many zeros for every n. Also the Manin-Mumford Conjecture was positively answered by Raynaud in 1983. The Mordell-Lang Conjecture (as stated before) was solved just a few years ago: first Faltings handled the particular case when the group 9 is finitely generated , and then McQuillan provided a general positive solution , using Falting's work and other contributions of Hindry. So far we have limited our analysis essentially to the characteristic 0, and to number fields. What can we say when passing to function fields, or prime characteristics? First let us deal with function fields . Still working in characteristic 0, Manin had proved in the sixties the following analogue of Mordell's Conjecture in this setting: if K is a function field over an algebraically closed field Ko (of characteristic 0) and X is a curve of genus> 1 over K, then either X does not descend to Ko (in which case X(K) is finite), or X is isomorphic to a curve X o defined over Ko (and all but finitely many points of X(K) come from elements of X(K o)). When considering prime characteristics p, even the notion of group 9 of finite rank must be rearranged. In fact, what we have to require now is that 9 has some finitely generated subgroup 5 such that, for every g E G, there exists a positive integer m prime to p satisfying mg E S . However 8.7.5 - as it was stated before - does not hold any more. In fact A itself is a torsion group without elements of period p; but there may exist some curves of A which are not finite unions of cosets of subgroups of A. A reasonable restatement of 8.7.5 in the general setting, for an arbitrary characteristic (0 or prime), is the following. Conjecture 8.7.6 Let Ko -< K be algebraically closed fields, A be an abelian variety over K having trace 0 over Ko (this means that A has no non-zero abelian subvarieties isomorphic to abelian varieties over Ko). If X is a Zariski closed subset of A and 9 is a subgroup of A of finite rank, then X n G is a (possibly empty) finite union of cosets of subgroups of g.
In 1994 A. Buium proved this form of the Mordell-Lang Conjecture in characteristic O.
8.7. T HE M ORDELL-LANG CONJECTURE
307
Theorem 8.7.7 (Buium) 8. 7.6 is a true statement when /Co -< /C are algebraically closed fields of characteristic o. What is not eworth y for our purposes in Buium 's line of proof is his use of Differenti al Algebraic Geometry; ind eed Differenti al Alge bra promptl y recalls Mo de l T heory a nd its treatment of differenti ally closed fields. So it is righ t t o spe nd a few words to desc ri be Buium 's strategy : one equips /C wit h a deri vation D whose constant fi eld is ju st /Co, one embeds 9 in a differenti al algebra ic gro up 91 and, finally, one shows by ana lytic arguments th at X n C l is a finite union of cosets of 91 a nd one t ra nsfers this proper t y to 9. But it was Ehud Hru shovski who first proved t he Mo rdell-Lang Conjecture in it s more general form , in any cha racterist ic, following the initial Buium a pproac h and then using mod el th eor etic methods an d , above all, Zari ski geom etries , differentially closed fields in cha rac te rist ic 0 and separably closed fields in prime cha racteristic, in addit ion t o Morley ra nk, elimin ation of im aginari es and t he defina bilit y resul ts of t his chapte r. It should be emphasized t hat no alte rnative genera l proof of the conjecture is known ; and ind eed Hrushovski proposed , so me time lat er , a new mod el t heoretic proof of t he Manin-M um ford Co njecture, based on a cruc ial use of existentially closed fields with an aut om orphism (in pa rticula r Zilber 's Trichotomy in ACFAa) , a nd getting in t his way nice effective bo und s of the number of involved cosets in a decomposition of X n C. Coming back t o t he Mordell-La ng conjecture , we ca n say
Theorem 8 .7 .8 (Hr ushovs ki) 8. 7.6 is a true statem ent in any charact eristic. T his concludes our short and lacu nose history of Mo rdell-Lan g, Morde ll and Manin-Mumford Conjectures. Which is our purpose now? Ce rtainly we do not aim at providing a complete report of Hru shovski 's proof: t his would requ ire man y pages and serious efforts; moreover th ere do exist sever al nice ex pos itory pap ers a nd books wholly devoted to a det ailed ex posit ion (some of t hem are mentioned a mong the references at t he end of th is chapter) . On t he oth er hand , we would like t o spe nd a few words abo ut Hrushovski 's a pproach, ju st to explain where Mo del T heory int ervenes an d why it plays a decisive role. W ith t his in mind , we will sketch Hru shovski 's proof in t he characterist ic 0 case, where so me old frie nds of ours - differenti ally closed fi elds - a re involved. Then we will shortly comment the prime characteristic case, where differenti ally closed fields a re profitably replaced by the separa bly closed ones.
308 CHAPTER 8. MOD EL T HE ORY AND ALGEBRAIC GEOMETRY
So take t wo alge braically closed fields 1(0 -< I( of charact eristic o. Let A be an ab elian variety over I( wit h trace 0 over 1(0 , X be a Zari ski closed set in A , y be a su bgroup of A of finit e rank. Our claim is that X n G is a (possibly empt y) finit e union of cosets of subgroups of y. (a) W ithout loss of generality one ass umes that I( has infinite tra nscende nce degree over 1(0. Then one equips I( with a derivation D making I( a differential field , and even a differenti ally closed field, whose constant subfield C (I( ) coincides with 1(0. J ust to fix our symbols, let L deno te from now on th e usua l language for fields, and L' = L U {D} that of differential fields. So 1(0 is strongly minimal both as a str uctu re of Land L': in fact D is identically 0 on 1(0 and so adds no definable objects to the pure field 1(0 . On t he cont rary, I( is a st rongly minimal struct ure in L , as an algebraically closed field, but it is not any more as a differenti ally closed field; indeed 1( , although w-stable, has Morley rank w in L'. Not ice also t hat, owing to what we saw in t he past sect ions, the a belian variety A is definable (even in L) in 1(. (b) At this poin t one recalls a general resu lt of Manin on differenti al fields: the derivation D yields a group homomorph ism p (definabl e in L') from A onto (I(+) d , where 1(+ is the addit ive group of I( and d is t he dim ension of A. The kernel of p is definabl e in L' a nd has a finite Morley ra nk. Now we deal with y . As y has finite rank and 1(+ has no non zero torsion elements, t he grou p p( G) is finitely generated and t here are go, . . . , gm E K such that
p(G) ~
L
i<m -
Q . s. ~
L
](0 ·
gi·
i<m -
Let II denote L i<m ](0 . gi. H is definabl e (in L' ) and has finite Morley ra nk. Hence p-l (H) is a subgroup of A exte nding y; moreover p-l(H) is definabl e (in L') and has finite Morley rank because both H a nd t he kern el of p are definabl e of finite Morley rank. Without loss of gener alit y for ou r purposes , we ca n replace Y by p-l(H). In fact , if X n p-l (H) is a finit e union of cosets of subgroups of p-l (H) , t hen t he same can be said about X n G a nd G . So we can ass ume t hat y itself is definabl e a nd has a finit e Morley rank. Now, ju st to explain Hr ushov ski's ap proac h in a mor e accessible way, let us restrict a little mo re ou r framework to the particular case when X is an irreducible curve (the setting of the original Mordell Conjecture). If X n G is finite , then we are don e. Otherwise X n G - as a definabl e
8.7. T HE M ORDEL L-LANG CONJECTURE
309
set of finit e Mo rley rank - contains a defina ble strongly minimal subset 5 . As usual, 5 can be viewed as a strong ly minimal str ucture. (c) Now we use t he result of Hr ushovski a nd Sokolovic saying that Zilber's Tri chot om y Conjecture holds for strongly min imal sets definabl e in differenti ally closed fields of characteristic O. In fact , t hese strongly minim al sets a re Zariski struct ures , a nd so obey t he Hru sho vski-Zilber Theor em. T his a pplies to 5, of course . Bu t what Hru sho vski also poin ts out is t hat 5, as a Zariski st ruct ure , is locally modular. In fact, as 5 is st rongly minimal, it suffices to exclude finitely many points fro m 5 to get an ind ecomposable set . So t here is no loss of genera lity in ass uming th at 5 itself is indecomposable, a nd conseque nt ly each t ranslate bS with bE G is also ind ecomposable. Up to replacing 5 by b- 1 5 for a suitable bE G we ca n even assum e t hat t he identi ty element 1G of G is in 5 . Hence we are ju st in a positi on to a pply Zilber 's Ind ecomposability T heorem; accordingly, one ded uces t hat the subgrou p generated by 5 in g is definab le, and ind eed every element in t his subgrou p ca n be ex presse d as a ·c- 1 wit h a and c in 5. Hence 5 interprets an infinite gro up an d so, as a Za riski struct ure , it ca nnot be t rivial. T his means t hat eit her 5 is locally mod ula r or 5 interprets an infinite (algebraically closed) field. We have to exclude t he lat t er opt ion . To obtain t his, one uses a result of Sokolovic already ment ioned in 7.10 and saying what follows. (d) An infinit e field definable in a differenti ally closed field of characte rist ic 0 a nd having finit e Morley rank is isomorphi c to t he constant subfield by a definable fu nction . Recall t hat, owing to t he elimination of imagin aries , t here is no difference between definabl e or interpretable wit hin different ially closed fields. So, if 5 int erpret s a ny infinite field, t hen it defines even C (K ) = Ko up to an £I-definabl e isomorphism. Consequent ly the subgroup t hat 5 generates is isomorphi c t o some group go £I-definable in Ko by a function I also definabl e in L'. As D = 0 in [(0 , go is definable even in L (just as I and 1-1 ). T hen we can a pply t he Hru shov ski-Weil T heorem and dedu ce t hat go is an algebraic gro up over Ko up t o a n L-definabl e isomorphi sm. At t his point one checks t hat go defines a n abelia n subva riety of A in K , which cont radict s the hyp oth esis t hat A has t race 0 over Ko. In concl usion, 5 must be locally modu la r. Now 5 is of t he form (a + L ) - {bo, .. . , btl for some strongly minimal subgroup L of g and suitable a, bo, . . . , b, E G . X is Za riski
310 CHAPTER 8. MODEL THEORY AND ALGEBRAIC GEOMETRY
closed , a nd so contains t he closure a + L of S as well. Hence X equals a + L and consequently inherits a group structure, as Mordell 's Conjecture requires. This concludes our outline of Hru shovski 's proof in cha ract erist ic 0 (when X is a curve). Bu t , as already said , the real novelty of Hru shov ski 's T heorem concerns prime characterist ics p. So it is worth spending some word s also on this case. The pla n of the proof is simila r, but requires some necessary rearrangements. In particular, one can avoid to refer to differentially closed fields and directly handle sepa rably closed fields (with no derivation) . (a) F irst one replaces with no loss of gene rality K by a separably closed non algeb raically closed extension having finit e degree over KP. O bserve that now the theory of K is not w-stable, although it is stable. (b) T he role of the kernel of J-L is now played by n npn A , which is not a definable set, but is the intersection of infinitely many definable sets. The other crucial points in th e proof a re: (c) any strongly minimal struct ure definabl e in K is st ill a Zari ski st ructure (so Zilber's Trichotomy holds);
(cl) a field definable in K and having Morl ey rank 1 is isomorphic to Ko by a definabl e function (a result of M. Messmer). For more details, look at the referen ces quoted below.
8.8
References
The con nection between Mod el T heory a nd Algebraic Geometry is clearl y explained by Poiz at's book [131] (recentl y translated in English [135]): this is a very rich reference on t his matter. In particular it includes a proof of Hru shovski-Weil Theorem 8.6.2 . Cherlin's Conjectu re was raised in [24]. The classification of w-stable groups was given by Macintyr e in [89]. Grou ps of finit e Morl ey rank a re exam ined in [15]. Now let us deal with Mordell-Lang Conjecture and Manin-Mumford Conjecture. A geom etrical int roduction ca n be found in Lang's book [80]; a short but reson abl y ex ha ust ive history of these two questions is also in the recent Pillay paper [128]. Pillay's book [126] explains the main model theoretic techniques involved in Hru shovski's approach. Hrushovski 's original proof
8.8. REFERENCES
311
of t he Mo rdell-Lang Conjecture is in [60]. A det ailed exposit ion is in th e book [16]. [50] and [127] a re shorter surveys , both very read abl e. As already said , Hrushovski 's proof in cha racteristic 0 case is based on some pr elimin ari es concern ing differenti ally closed fields: t hey ca n be found in [155] and [62]. For a prime characterist ic, separa bly closed fields are enough: th e basic prelimin ari es are desc ribed in [115]. Finally, let us deal with Manin-M umford Conjecture: Hru sho vski 's proof is now in [61] . It is based on t he mod el t heory of ACFA, as develop ed in [20] a nd [21] .
Chapter 9
O-minimality 9.1
Introduction
The last part of this book is devoted to o-minimal st ructures . As we saw in t he past chapt ers , t hey a re the infini t e expansion s M = (M , :S; , . . .) of linear orderings such that th e subsets of M definabl e in M are as t rivia l as possibl e, and restrict to th e finit e unions of singlet ons and open int ervals, possibly with infinite end points ± oo (eq uivalent ly to t he finit e unions of op en , closed , ... int ervals in th e broad sen se including half-lin es and the whole M ). a-minimal str uct ures are not sim ple according to t he definition provided in Ch ap ter 7, ju st because t hey define and even expand infinite linear orders; conseq uent ly no good ind ep endence system can be develop ed inside th em , and t hey are not clas sifiable in She lah 's sense. Despi t e thi s, and just owing th e relative triviality of th eir 1-ary definable sets , one ca n see that t hey enjoy several relevant model th eor etic properties and , among th em , a sat isfact or y notion of independence with a related dimension partly resembling Morley rank . Furthermore, they include a lot of noteworthy algebraic exampies. Ind eed we hav e already seen that th e ordered field of real s (R , +, " - , 0, 1, :S;), as well as any real closed field , is o-rninimal; discrete or dense infinit e linear orders, like (N , :S; ), or (Z , :S;), or (Q, :S;), or (R , :S; ), ar e o-minimal as well; and one ca n show t ha t even divi sib le ordered abelian groups, such as (Q, +, 0, :S; ) and (R , +, 0, :S; ), are o-rninimal. In particular , consid ering t he order of th e reals, or expa nding it by addition , or addit ion and multiplication together , yield o-rninimal st ruct ures. On the oth er side, t here do exist some ex pansion of (R, :S;) which are not o-rninimal.
313
314
CHA PTER 9. O-MINIM ALITY
For inst ance, ext end the ord er of reals by t he sinus fun ction si n; in t his enlarged structure, Z -a denumer abl e set of isolated points- get s defin abl e (by sin 1r V = 0) , and so o-mi nimality get s lost. Of course the same argument applies to cos . T his cha pter has a two fold aim. On t he one hand , we will provide a n a bstract structure t heory for o-minimal models M. The sta rt ing poi nt will be ju st the definit ion of o-mi nimality, and t he consequent class ification of t he defina ble subsets of M . But we will see t hat, on t hese seemingly poor grounds , one ca n develop a sign ificant t heory, including a nice characterization of definable subsets of M " for every positi ve int eger n, as well as of definabl e function s from M" into M . This will also lead t o the alr ead y recalled notion of dim ension, satisfying several rem arkable properties resembling those of Morley rank in w-st abl e t heories. Act ually th ere is a good deal of similarity bet ween t he o-mini mal framewor k and t he w-stable set t ing, ju st in t hese di men sions, but also in definabl e groups and in other matters. We will em phasize t hese connections in Sections 9.2-9.6. In part icular Section 9.4 and Section 9.5 will prove, among other th ings, t he already ment ioned a nd not ewor th y fact t hat o-minimalit y, unlik e minimality, is preserved by elementary eq uivalence : if M is a n o-minimal st ructure, t hen every mod el of the t heory of M is o-minimal as well. Accordingly a complete th eory T is said to be o-minimal whe n some (equivalently every) model of T is o-minimal. T he subseq uent section 9.6 will treat definabl e groups, definabl e manifolds , and so on, in o-minim al st ruct ures. On t he other side , we will prop ose ot her relevan t exam ples of o-minim al struct ures (t o which t he previous gene ral t heorems apply) . T his will be t he t heme of Section 9.7, where we will see t hat certain ex pa nsions of t he rea l field by fam ilia r functions , such as ex ponent iation, or suitably restrict ed a nalytic functions, are o-minimal. Here o-minimality largely overla ps real algebraic geomet ry a nd real a nalytic geomet ry, both in acquiring tec hniques and constructi ons fro m t he geomet ric framework towards a general and lar ger spect re of applications, and in providing a new light and in op ening new per sp ecti ves wit hin t he geometrical setting itself. The subseq uent section 9.8 will deal with some variations on t he o-minimal t heme, most not ably wit h a notion of wea k o-m inimality , enla rging t he 0 minimal setting an d intensively st udied in t he latest years. At las t , t he final section 9.9 will int rodu ce very shortly t he qui te recent and attracti ve work of A. On shuus a bo ut a notion of ind ependence enla rging both forkin g ind epend ence in simple t heor ies and algebra ic ind ependence in o-minim al th eories t owards a common general fram ework. Now a few historical not es. O-minimality began its life in th e eight ies; its
9.1. INTRODUCTION
315
origin refers to a classical problem of Tarski, asking whether the real field, expanded by the exponential function x t--+ eX, still has a decidable theory. As we know, decidability closely overlaps definability, so a deeply related question is what is definable in (R, +, " -, 0, 1, :S, exp): is the theory of this structure quantifier eliminable, or model complete? This was the scenery where 1. Van Den Dries introduced o-minimality at the beginning of the eighties. But who gave a considerable impulse to this notion were A. Pillay and C. Steinhorn, who proved the basic structure theorems on o-rninimal structures and greatly developed their abstract theory. In 1991 A. Wilkie partly solved Tarski's Conjecture, showing that the theory of (R, +, " -, 0, 1, :S, exp) is model complete, and even o-minimal (as we will see in 9.7, decidability is still an open question, involving a deep number theoretic problem, usually known as Schanuel's Conjecture, while quantifier elimination fails). This emphasized t he connection with analytic geometry, mentioned some lines ago. And indeed o-minimality became, and still is, a matter of interest not only to model theorists, but to geometers and analysts as well. To conclude this section, we give the proof that any o-rninimal ordered field is real closed. This is the converse of a result we already know, ensuring that every real closed field is o-minimal, and can be viewed as the o-rninimal analogue of Macintyre's theorem saying that any w-stable field must be algebraically closed. The proof requires a very basic machinery from 0minimality -just the definition itself- in addition to the necessary algebraic grounds. Let us preliminarily examine o-minimal groups. Here (and later in this chapter) intervals possibly admit infinite endpoints, and so include half-lines, and the whole line, in case. Lemma 9.1.1 Let A = (A, 0, +, -, :S , . ..) be an o-minimal structure expanding an ordered group (A, 0, +, -,:S) and let H be a subgroup of (A, 0, :S) definable in A. Then H = {U} oppure H = A.
+, -,
Proof. Suppose towards a contradiction that there exists some subgroup H i- {O}, A of (A, 0, +, -, :S) definable in A. Owing to o-minimality, H decomposes as a finite union of pairwise disjoint intervals (possibly closed, or with infinite endpoints). Accordingly write
(0)
H =
U t, j :::; s
where 10, ... , Is are intervals and s is minimal. Notice that H is infinite, because it must contain all the multiples nh of any nonzero element h E H
CHAPTER 9. O-MINIMALITY
316
when n ranges over int egers. Hence t here is j ::; s for which I j is infinite. Without loss of generality pu t j = O. Moreover we ca n even ass ume th at l a contains 0 a nd is sy mmetric with respect to 0 (in t he sense t hat -c E l a for every c E la). This is becau se H is a subgro up, and so includes 0 and is preser ved under + a nd -. As H =f:. A, la is [-a , a] or] - a, a[ for some a > 0 in A. In t he form er case , eve ry b in A satisfying a < b ::; 2a decomposes as b = a + (b - a) where a E la ~ Hand 0 < b - a ::; a , so even b - a is in 10 a nd conseq uently in H ; hence b E H. Therefor e [-2a , 2a] is an interval in H properly including 10' T his impli es t hat [-2a , 2a] shares at least one element with some interval Ij where 0 < j ::; s , say with I s. Put I~ = [-2a , 2a]Uls .
So
Jb
is an interval including 10 U I s and contain ed in H . Co nseq uent ly
H = I~ U
U
O<j<s
i.,
a nd t his cont ra dicts t he choice of s in (0). In t he lat t er case, fix b E A such t hat 0 < b < a, t he n 0 < a - b < a , and consequent ly even a - b is in l a. It follows a = b + (a - b) E H. We get in t his way an interval [- a, a] properly including l a and contained in H . But t his contradicts as before t he minim alit y of s in (0). ., As a conseq uence, one ca n give a full characterization of o-minima l ordered groups. They ar e exa ctl y t hose listed before, namely t he ord er ed div isibl e a belia n groups. Theor em 9 .1.2 An o-m in imal ordered group A = (A , 0, and divi sibl e.
+, - , ::;) is abelian
Proof. For every a EA , th e cent ralizer C (a) of a is a definable subgrou p of A , a nd consequently equ als eit her {O} or A. If a = 0, then clearly C(a) = A. On t he other side, when a =f:. 0, C (a) = A as well, becau se a E C (a) and t his excludes C (a) = {a}. Hence C (a) = A for every a E A, a nd A is abelian . Now take a positive int eger n : n A is a definabl e subgro up of A , clearl y eq ualling A when A = {a}; on t he ot her side, if A =f:. {a}, t hen nA =f:. {a} an d consequent ly nA = A . Then n A = A for every positi ve int eger n , III other words A is divisibl e. .,
Coming back t o ordered fields, we ca n eventua lly pro ve
9.1. INTRODUCTION
317
Theorem 9.1.3 Let /C = (K, 0, 1, +, " -,::;) be an a-minimal ordered ring with identity 1 (in particular let /C be an a-minimal ordered field). Then /C is a real closed field.
Proof. First we claim that /C is an ordered field, in other words the set /C* of the nonzero elements in K is an abelian group with respect to -, It suffices to show that the set «> of the elements > 0 of K is so. In fact, for every a E «>, aK is a definable subgroup of (K , 0, +, -, ::;), and aK -I {O} because a > O. So, owing to Lemma 9.1.1, aK = K, and in particular there exists some b E K satisfying ab = 1. As a > 0, b is positive as well. This proves that x> is a(n ordered) group with respect to -, It remains to check that «> is also abelian. To show this, it suffi ces to observe that «> is o-minimal , and then to use Theorem 9.1.2. In fact «> is definable (as a group) in /C, and consequently every subset X of «> definable in «> is also definable in /C, and hence is a finite union of non-empty intervals of K. All the end points of these intervals lie in «> U {+oo}, with the only possible exception of the left most end point in the first interval, that might equal 0, but can be replaced in this case by -00 in «>. In conclusion, X is actually a finite union of intervals in «>. Hence «> is o-minimal and consequent ly abelian, as claimed. Now let us prove that /C is real closed. Accordingly take a polynomial f(x) E K[x] and two elements a < b in K satisfying f(a) . f(b) < 0, for example f(a) < 0 < f(b). We have to show t hat there is some c E K such th at a < c < band f(c) = O. Recall that /C is an ordered field, and hence ::; is dense in K and in la , b[. The polynomial function that f defines is continuous (with respect to the order topology) , so both la, b[+= {d E K : a < d < b, f(d) > O} and
la, b[-= {d E K : a < d < b, f(d) < O} are open sets. If la, b[-= 0, then the continuity of f is contradicted in a. Hence la, b[- and similarly la, b[+ are not empty. Moreover both la, b[+ and la, b[- are definable, and accordingly decompose as finite unions of intervals, indeed of open intervals. As la, b[+ and la, b[- are disjoint , t here is some c E]a, b[ out of both la, b[+ and la, b[-: so c is a root of [, f( c) = O. '"
318
9.2
CHA PTER 9. O-MINIMALITY
The Monotonicity Theorem
Let M = (M, ~ , . ..) be an a-minimal struct ure . First obser ve t hat M is a t o pological space with resp ect to t he ord er t opology a nd so, for every positi ve int eger n , M " is a topological space as well, with resp ect t o th e product t opology. As already recalled , t he o-minimalit y of M ju st requires t hat t he only definabl e subsets are th e finit e union of singlet ons a nd op en inter vals (possibly including half-lin es and t he whole M) . Bu t what ca n we say abou t th e defina ble subsets of M " when n > I ? We give here a very partial and pr eliminary an swer , dealing with l-ary definable functions f. We show t hat, if the domain of f is an open interval la , b[ with a < b in M U {±oo} , then one can partition la , b[ into finitely many intervals such that, in each of t hem, f is either const ant , or strict ly incr easing , or strict ly decreasing, and a nyhow cont inuous according to t he orde r topology. T his is t he so-called Monotonicity Theorem , say ing in detail what follows. Theorem 9.2.1 Let A1 be an o- m inimal structure, X ~ M, a, b E M U {±oo}, a < b, a an d b be X -defi nabl e when belonging to M . Let f be an X -defi nable f unction of la , b[ in to M . Th en there are a posit ive in teger n and aD, al , .. . , an E MU {±oo} suc h that
1. a = aD < al < ... < an = b, and aI , ... , an- l are X -defi nable;
2. fo r eve ry i < n , f is eithe r constant or strictly m on otonic in ]ai , ai+d; 3. fo r every i < n , if f is strictlu mono to nic in uu, ai+l[, then f( ]ai, ai+l [) is also an in terval, and f con tains a biject ion preserving or reversing ~ bet ween ]ai , ai+d and f (]ai' ai+d ) · In particular f is conti n uous in every inter val ]ai , ai+d for i
< n.
Notic e t ha t, when mor e genera lly f is an arbitrary definable function with both domain an d image in M , t hen the domain of f is definable as well, a nd conseq uent ly is a finit e union of singletons and op en int erval s. Each of t hese intervals satisfies t he ass umpt ions of Theorem 9.1.2 , and hence inh erits its conclusions. Notice also t hat Theor em 9.1.2 implies, as a simple conseq uence, t hat, if M is a n a-minimal structure, a, b E M U {±oo} , a < b a nd f is a definabl e function from la, b[ into M , t hen f (x) has a limit in MU {±oo} when x -T a+ and x -T b>. A full proof of Theorem 9.1.2, as stated before, would require seve ral tec hnical det ails a nd would be quite long. We prefer to propose here a simpler
9.2. THE MONOTONICITY THEOREM
319
argument showing only the continuity result when M expands (R, :S;) (actually this is more or less what we will need later). Proposition 9.2.2 Let M be an o-minimal structure expanding (R, :S;) , X ~ M, f be an X -definable function from ]a, b[ into R . Then th ere are aI, ... , an E]a, b[ such that al < ... < an, aI, ... , an are X -definable and f is continuous in ]a, al [, ]an, b[ and each interval ]ai, ai+l [ for 1 :s; i < n. Proof. Let S denote the set of the points in ]a, b[ where f is not continuous. It is an easy exercise to prove that S is X -definable. If S is finite , then we are done: for, aI, .. . , an are just the elements of S. Hence suppose S infinite. So S contains an infinite open interval I. For every natural n, build two infinite open intervals In and I n such that, for every n,
(i) In
~
I,
(ii) the (topological) closure I n+l of I n+l is included in In'
(iv) the length of I n is smaller than
nil'
Let us see how to define these intervals. First put ID = I. Then take any natural n , suppose In given and form I n and I n+l as follows. If f(In) is finite , then for some d E f(1n) the preimage {c E In : f(c) = d} is infinite. But {c E In : f( c) = d} is definable, and hence includes some infinite interval; f is const a nt , hence continuous, on this interval, which contradicts In ~ I ~ S. Accordingly f(In) must be infinite. But f(In) is definable, too, and hence includes in its turn an infinite interval; let I n be such an interval, notice that we can assume with no loss of generality that the length of I n is < The preimage of I n in In is also definable, and contains some infinite interval. Let I n+l denote such an interval; we can assume In+! ~ In. This determines the In's and the In's for every n. Now put I' = nnEN In. Clearly I' = nnEN In' whence I' =1= 0 because R is compact. Pick d E 1', we claim that f is continuous in d (this contradicts dES and so accomplishes our proof). Take any interval U containing f(d). Owing to (iv), there is some natural n for which U ;2 I n. But this implies U;2 f(In+l) where I n+l is an open neighbourhood of d. ...
nil'
A final remark. When M expands the field of reals, we can say even more, and state a smooth version of the theorem: in fact, one can partition ]a, b[ into finitely many intervals where f is of class cm for every positive integer m.
320
9 .3
CHAPTER 9. O-MINIMALITY
Cells
Now we move to characterize in an o-minimal struct ure M = (M, :S , . . .) th e definable subsets of M": in particular t he definable n-ary function s, for every positive int eger n . To make our life easier , we assume all throughou t t his sect ion (and also in th e following ones) t hat :S is dense without end points: in particular every interval ]a, b[ with - 00 < a < b < + 00 in M must be infinite. As alr ead y said , the reason of t his restriction is ju st to make our treatment and our proofs sim pler; in fact , all th e results we will show below ca n be extend ed -by the appropriate a rr ange ments- to any o-rninimal st ruct ure M. On the other side , t he ord er of reals is j ust dense without end point s, so our fram ework include all the exp an sions of (R , :S ), in particular all the st ruct ures enlarging t he real field; as we said befo re, the notab le o-minimal exam ples we will propose in Section 9.7 lie in t his set t ing. We know that the basic definable subsets of M are t he int ervals and t he singlet ons. More gener ally, th e basic definable subsets of M " are t he cells. So let us define what a cell is, mor e precisely what a k-cell in M " is.
Definition 9 .3 .1 First suppose n = 1. A sub set C of M is a O-cell if an d only if C is a si ngleton, and a 1-cell if and only if C is a non- empty open in ter val, possibly with infi nite endpoints . N ow let n > 1, and let k a natu ral number :S n. A subse t C of M " is called a k -cell if and only on e of the follo wing conditions hold: 1. there are a k- cell D of M n - 1 and a contin uous and defi nable fun ct ion f of D into M such that C is the graph of I, namely
C = {(11, b) E M " : 11 E D , b = f(I1)} ; 2. k ~ 1 and th ere are a (k - I )-ce ll D of M n-l and two fun ctions f and g with domain D such that
(i) eithe r the image of f is a subset of M and f is both continuous and definable, or f(l1) =
-00
VI1 E D ,
(ii) either th e im age of g is a subset of M and g is both continuous and definable, or g(l1) = + 00 VI1 E D , (iii) f(l1) < g (l1) VI1 E D , (iv) C
=
{(11, b) E M n : 11 E D , f (l1)
< b < g (I1)}.
On e eas ily sees t hat every k-cell of Mn is defin able, and t hat a k-cell of jU n is op en in M " if and only if k = n . One can also observe
9.3. CELLS
321
Proposition 9.3.2 Let M be an o-minimal str ucture, k S; n be posit ive integers. For every k-cell C of M" , there is a definable homeomorphism of C onto a k- cell of M k • Proof. It suffices to see , for n > k a nd n > 1, how to det ermine, for every k-cell C of M n , a definable homeomorphism 1re onto some k-cell C' of Mr:" , and then t o iterate th is procedure as long as one needs. First ass ume that C is t he gr aph of some cont inuos definable func tio n fro m a k-cell D of M n-l into M. In this case it suffices to put C' = D , and choose as 1re th e proj ection of C onto C' . Now ass ume
C = {(a , b) E M n
:
a E D , f (a)
< b < 9 (a)}
where D is a (k - I)-cell of M n-l , and I, 9 sat isfy the cond it ions in 9.3.1 , 2. We pro ceed by ind uction on n , If n = 2, then k - 1 = 0, and D red uces t o a single point a of M. P ut C' =JJ(a) , g(a)[ , 1rc(a , b) = b for every b E C '. Now let n > 2. We know th at there is some definabl e homeomorphism 1rD of D onto a (k - 1)-cell D' of M n-2. Consider the two fu nctions one gets by composing l , 9 respectively a nd the inver se of 1rD . T hey have dom ain D' a nd sat isfy t he ass um pt ions in 9.3.1,2. Accordingly they define a k-cell C ' of M n - l ; further mo re 1rc(a , b) = (1rD(a) , b)
V(a , b) E C
det ermines a definab le homeomorphism of C onto C'.
...
When M expands a real closed field (for instance, when M is the real field , or even a n expansion of it) , the cells in M ca n be charact erized as follows. Proposition 9.3.3 Let M be an o-minimal expansion of a real closed fiel d, k , n be two natural nu mbers satisf ying n 2:: k , 1. If C is a k -cell of M n, th en th ere exis ts a definable homeomorphism of C onto ]0, I [k. Proof. When k = 0, our claim is trivial, becau se a O-cell reduces t o a singlet on. So t ake k > 0. Owing to the previous proposition, we can assume n = k. We proceed by induction on n . If n = 1, t hen C = ]a, b[ where a , b EMU {±oo} a nd a < b. So the required homeomorphism between C and ]0, I[ is easily obtain ed: for instance, if both a an d b are in M , th en it suffices to map every x in C = ]a, b[ into x - a b- a'
322
CHAPTER 9. O-MINIMALITY
in t he remaining cases one proceeds in a simila r way. Now s uppose n > 1 (a nd our claim true for n - 1). Let C be an n-cell of M n. There do exist an (n -I )-cell D of M n-l and two functions f and 9 as in 9.3.1 ,2 such t hat C is t he set of t hose t uples (ii, b) in M " for which ii E D a nd f (ii) < b < g(ii). By induction , t here is a defina ble homeomorphism h of D ont o ]0, l[n-l. If both f and 9 take th eir values in 1\1, t hen
( a,~ b) ~
(h ( ~)
b - f (ii) ) V(ii, b) E C
a , g(ii) _ f(ii)
is th e required hom eomorphism. All t he other cases ca n be handled simila r way, ju st as when for n = 1. •
III
a
In particular, when M expands th e real field Rand k > 0, every k-cell of M is connecte d in th e ord er topology ; for, ]0, l[k is. This do es not hold any longer when R is replaced by any real closed field. For instance, if Ra is t he orde red field of real algebraic numbers, th en Ra is real closed , and hence o-minimal; Ra is a Lcell of itself, but is not connected becau se, for every real t rascende ntal t , Ra pa rti tion s as R a = {r E R a : r < t } U {r E R a : r > t}. Hence connect ion gets lost. However ever y cell in an o-minimal st ruct ure M sa t isfies a wea k form of con nection, wit h resp ect to ope n definable sets . In fact , conside r t he following notion. Definition 9.3.4 Let M be an o-m inimal structure, n be a posit ive integer. A defi nable set X ~ M " is said to be definably connected if and only if X cannot part it ion as the disjo int un ion of two non-empty open definable subsets . Wh at we will see now is t hat every cell in an o-minimal struct ure M is definably connected . First we give an equivalent charact erization of defin abl y connecte d sets. An open box of M n is t he ca rtes ia n product of n op en int erval s of M . Hence op en boxes form a basis of op en neighbourhoods of t he product topology of M n. Furthermore, for Y ~ X ~ u», an element s of X is called a boundary point of Y in X if a nd only if every op en box of M n containing ii overlaps both Y a nd X - Y. Lemma 9.3.5 Let A1 be an o-m inimal structure, n be a posit ive in teger, X be a definable su bset of M": T hen X is defi nably connected if and only if, fo r every proper non-em pty defi nable subset Y di X , X contains at least one bounda ry point of Y in X.
9.3. CE LLS
323
Proof. X is definably connected if a nd only if, for every definable Y ~ X such t hat Y =1= 0, X , eit he r Y or X - Y is not op en , in other words ther e is eit her a point a E Y such that every open box cont aining a overl aps X - Y , or a point E X - Y such that every open box cont aining overl aps Y . Accordingly X is defin ably connected if a nd only if, for every Y as a bove, t here is a E X which is a bound ary poin t of Y in X . ..
a
a
Now we can show, as promised, T h e orem 9.3.6 Let M be an a-minimal structure, n be a posit ive integer. T hen every cell C of M n is defi nably connec ted.
Proof. We proceed by induction on n . If n = 1, t he n t he claim is trivial becau se the cells of M red uce to singletons a nd open intervals. Hen ce assume n > 1. Let C be a cell of J\;f n . If C is a O-cell, so a singleton, t he n C is definably connected . If C is a k-ce ll for some positi ve int eger k < n, t hen, owin g t o Corollary 9.3.3 , C is defin ably hom eomor phi c t o a cell C' of M k ; by t he induction hypothesis , C' is defin ably co nnected, wh en ce C is defin ably connected , t oo . Fin ally suppose t hat C is a n n-cell of M n. Then ther e exist a cell D of M n-l a nd two fun ctions 1 and 9 as in 9.3.1, 2 such th a t C = {( a, b) E M n : a E D , 1(a) < b < 9 (a) } . D is definably connected by t he induction hyp oth esis. To deduce that even C is defin ably connected we use Lem ma 9.3.5 . Accordingly take a definabl e subset Y of C such t hat Y =1= 0, C . F irst sup pose t hat, for some a E D , t here a re t wo eleme nts b an d b' in M suc h t hat (a, b) E Y a nd (a, b') E C - Y. Then t he int erval ]1(a), g(a)[ contains at leas t one boundary poin t bo of t he definable set {b E M : (a, b) E Y}; t his implies t hat (a, bo) is a bo und ary po int of Y in C . Now suppose t hat , for every a E D , either
{ (a, b) E C : bE M} or
{ (a, b) E C : s « M }
~
~
Y
C - y.
Let Z den ot e t he set of t he eleme nts a of D satisfying t he for mer cond it ion. Y =1= 0, C implies Z =1= 0, D . As D is defin abl y connected, t here is some boundary point ao of Z in D. Let b E M sat isfy (aa , b) E C, we claim th at (aa, b) is a boundary point of Y in C . Let B a n op en box of M n containing (aa, b). As C is open , we can suppose B ~ C . Let B ' denote the projection
CHAPTER 9. O-MINIMALITY
324
of B in M n - 1. Then ao E B ' a nd B ' ~ D. Since ao is a boundary point of Z in D, there are a1 and a2 in B ' such t hat a1 E Z a nd a2 tj Z . Con sequently, if b1, b2 E M satisfy (a1 ' b1), (a2 ' b2) E C respectively (in particular (a1 ' b1), (a2 ' b2) E B) , then (a1' b1) E Y, (a2' b2) tj Y . Hence (ao, b) is a bou ndary poin t of Y in C . In conclusi on , C is defina bly connect ed . ..
9.4
Cell decomposition and other theorems
The aim of this section is to introduce and to state t he basic general theorems for o-rninimal struct ures M = (M , ~ , . . .): we want to characterize all the defin a ble sets and funct ions in M , a nd we wan t also to emphas ize some relevant consequences a nd, am ong t hem, the already ment ioned fact t hat 0minimality is preserved und er elementary equivalence. As th e proofs of t hese fundamental results a re qui te long and intricate, we will defer part of t hem, a nd t he cor responding de tails, to t he next section ; here we provide ju st a basic outline, illustrating these cent ral core s of the theory of o-minimalit y. So a reader simply int erested in a general view may limit her , or his attent ion t o t his section, and to skip the next one. Let us remind once again that , for simplicity 's sake, we a re assuming that (M , ~) is dense without endpoints: this is tacitly acce pted all throughout these sections, unless otherwise stated. The first result we prop ose j ust describes definabl e sets (and functi ons) in o- rnini mal struct ur es. It is a beau ti ful a nd powerful cha racterization, called Cell Decomposition Theorem. In fact , it says t hat every definabl e set decomposes as a fi nite union of cells. Theorem 9.4.1 Let A1 be an o-m inimal structure, n be a positive integer. 1. Eve ry definable set X uni on of cells in M n.
~
M " can be expressed as a fi nit e (disjo int)
2. Furthermore, if X is the domain of a definable fun ction f with values in M , then on e can decompose X as a fin it e disjo int union of cells, such that f is contin uous on each of them . Not ice that t his generalizes what we know when n = 1; in fact, in that case every definable X ~ M is a finit e union of point s and open intervals (in other words, of O-cells a nd I-cells respectively), a nd, when X is th e do main of some definable fu nction I, one can also suppose that f is continuous on eac h of these pieces, owing to the Monotonicity Theorem. But now we can ext end t hese results t o any n .
9.4. CELL DECOMPOSITION AND OTHER THEOREMS
325
As already said , t he proof of the Cell Decomposition Theorem will be given in detail in t he next sect ion. But Cell Decomposition , and it s a nalysis of definable sets, is also t he key t ool in showing another basic fact in 0minimality, that is it s preserving under elementary equivalence. Theorem 9.4.2 If M is an a-minimal structure, then the theory of M a-minimal.
is
In fact , which is t he trouble in this claim ? Actually we do know th at, for a n o-minimal M, for every formula O( v, w) in the lan gu age L of M a nd t uple d in M , O(M , il) is a finite union of (possibly closed) intervals . But suppose th at , when ii ranges over M, the minimal number of t he intervals involved in these decompositions of O(M , il) cannot be upperly bounded , and so, for every natural N, on e find s some tuple il( N) in M such that any decomposition of O(M , il( N )) requires at least N intervals. If this is t he case , then it suffices a st raightforward application of Compactness Theorem to provide some M' == M and some t uple a' in M' for which O(M' , a') can not be expressed as a finite union of int ervals , and con sequently to conclude t hat the t heory of M is not o-rninimal. Hence the cr ucial point in showing that the o-rninimality of A1 is preserved by element ary equivalence is to uniformly bound , for every form ula O( v, w) as befor e, the minimal number of intervals necessary to decompose O(M , il) wh en il ranges over M. T his is a definability que stion concerning formulas in arbitrarily many free vari ables, and so directly refers to Cell Decomposition. On the other hand, boundi ng t he number of the invol ved int ervals in O(M , il) is the same as bounding the total number of their end points (forming a defina ble, and finite set). So the key ste p towards the proof of Theor em 9.4 .2 is Theorem 9.4.3 Let M be an a-minimal structure in L , Ifl(V, w) be an Lformula such tha t, for all il in M , Ifl(A1, il) is finit e. Th en there is a positive integer N such that, for eve ry il in M , IIfl(M , il) I ::; N.
The proof of Theorem 9.4.3 will be deferr ed until the next section. But , as we have just pointed ou t , T heorem 9.4.2 is an almost immedi ate conseq uence of Theorem 9.4.3. Let us see in detail why.
Proof. (Theorem 9.4 .2) Let L be the language of M , and let 7)( v , w) be an L-formula ; in pa rticular, let n deno te the lengt h of w. For every d E M"; O(M, il) is a finit e union of intervals. Let Ifl(v, w) be t he L-formula saying v is an end point of 0(... , w).
326
CHAPTER 9. O-MINIMALITY
T hen, for every ii E M."; cp(M, ii) is finite; hence, by Theor em 9.4.3 , there exists a positive integer N such that , for every ii E M" , cp(M, ii) cont ains at most N elements, whence B(M , ii) has at most N end poin ts. Bu t t he sentence ViiEj ~ N v cp( v, w) remain s t rue in every struct ure M' == M. Accordingly, for every A1' == M and bE B(M' , b) has at most N end poin ts, and hence is a finit e unio n of intervals. In conclusion t he t heory of M is o-minimal. ..
u»,
The bounds given by Theor em 9.4.3 on formul as B( v, w) ca n be extended to formulas B(V, w) with an a r bit rarily long v. In fact the following result holds . Theore m 9 .4.4 Let M be an o-minimal structure in L , B( V, w) an L formula (n be the length of v and m be that of w) . Th en there exists a posit ive integer N such that , for every M' == M and tuple ii in M ' , B(M, n, ii) is the un ion of at most N cells in M' . Before beginning t he proof, a nd ju st for pr eparing it , let us premi t a sim ple exa mple. Ass ume n = 2. Let B(V I, V2, w) be a n L-formul a , ii be a t uple in M. Suppose t hat t he definabl e set B(M 2 , ii) decomposes as a disjoint union of 2 cells in NI : the form er is a singlet on, so a O-cell, while t he lat ter is a I-cell, a nd more precisely is t he graph of a cont inuous definable func tion f whose dom ain is t he open int erval ]a, b[ wit h a < bin M . Notice t hat t here a re a n L-formula 1]( V I, V2 , Z) a nd a sequence e in J\1 such t hat, for every Cl and C2 in M with a < Cl < b,
Now consider the L-formula
1\
"1](', " Z) defines a cont inuous function of dom ain ]u, w[" 1\ 1]( V l, V2,
Z))) 1\ -, (u <
UI
<W
1\ 1]( UI ' U2,
Z) ))).
b in M , or even in a mod el M' of t he t heory of M , satisfying N F B(i (b) are ju st t hose for which B(M ,2, b) has a cell decomposit ion as 'l9(M 2, ii) (t he disjoint union of a singlet on and a gra ph of
It is clear t hat t he t uples
9.4. CELL DECOMPOSITION AND OTHER THEOREMS
327
a definabl e continuous function) . It is also obvious t hat t his is quite gener al: given an L-formula B(v, w) as in t he statement of 9.4.4, a t uple 5 of th e same length as w in t he univ erse n of t he t heory of M and a cell decomposition of 'l9(nn , 5), one can build a n L-formula Bii ( w) such t hat a t uple bin n satisfies Bii if and only 'l9(nn , b) has a cell decomposition just as 'l9(n n, 5). Proof. (T heorem 9.4.4). Owing to Theorem 9.4.2 , a ny structure M' element aril y equivalent to M is o-m inima l, and hence, by Theorem 9.4.1, a ny definable subset of (in part icular B(M m , 5) for 5 E M' m) is a finite union of cell. We have seen t ha t t here is an L-formula Bii ( w) (without paramet ers) describ ing t he form of a given cell decomposition of B(M,n, 5). Let denote the (countabl e) set of all these formul as Bii (1V) when 5 ranges over M' n a nd M' is a model of th e th eory of M. Use Com pactness Theorem a nd get finitely many formulas
u»
such t hat
Vw
V 'l9i(W) E Th (M ). i «:s
Co nseq uent ly t here is a positi ve int eger N s uch th at , for every M' == M and 5 E M'?" , B(M,n, 5) decomposes as the union of at most N cells: N is just t he maxim al num ber of involved cells in t he decom posit ions described by 'l9 o(w), ... , 'l9 s (w). • Recall t hat , when A1 ex pan ds t he real field R , every cell of M is also connected . Hence in t his case, for every formul a B(V, w), t here is a positiv e integer N such that , for a t uple 5 in M m, B(M n , 5) is t he union of ~ N connected components . vVe will see in Section 9.7 several relevant examples of o-rninimal exp ansions of t he real field R. In this fr am ework it is worth stat ing the following result of Wilki e' s. Theorem 9.4.5 (Wilkie) Let M expand the ordered field of reals by C oo fu nctions from some cartesi an powers R t of R into R. Assume that, for every quantifier free fo rmula B(v, w) in the languag e L of M , there is a posit ive integer N such that, for any tuple 5 E Mm, B(M n, 5) decomposes as the union of ~ N connected compone nts . T hen the same is true fo r every fo rm ula of L. In part icular, M is o-m inimal. Cell Decomposition is an import an t tool also in developin g a dim ension t heory inside o-minimal structures M , a nd in equ ipping every definable X
328
CHAPTER 9. O-MINIMALITY
in M with a natural number (its dim ension). Recall t hat no o-minimal M is simple, and hence w-stable; accordingly t he Morley ra nk of X might be 00 . More generally, as simplicity fails, other possible rank notions ari sing wit hin simple, or stable, or supersta ble settings and replacing R M in t hese enla rged fr am eworks lose t heir interest in o-minimal mod els. Bu t Cell Decomposition do es assign a dim ension to X in a qui te reasonabl e way. Let us see how. Definition 9.4.6 Th e dimension of a k- cell of M n is k. Th e dimension of a definabl e X in M is the maximal dim en sion of a cell arising in a cell decomposition of X. Of course, a cell decomposition of X is not unique; but th e maximal dimension of an involved cell is, and do es depend only on X. So the previous definition makes sense for every X. There is another alte rn at ive way t o introd uce a dimension notion in M. In fact , as we saw in C hapt er 5, t he alge braic closure acl determines a dependence relation ~ in M (and in every mod el M' of t he t heory of M ). T his relation generates in its t urn an ind epend ence system as ax iomatized in sect ion 7.2 , so satisfying t he condit ions (11)-(16) (but not t he fur th er requirement (17) )). Wi th resp ect to this indep end ence notion , we ca n define the dim ension of a t upie ii = (al' . . . , am) in M'": as t he size of a minimal subsequence b suc h t hat ii lies in acl(b) . T hen we ca n introduce, ju st as in t he st rongly mini mal case , t he dim ension of a definable set
9.5. THEIR PROOFS
329
The uncountable sp ectrum of an o-m inimal T th eory takes everywhere t he maximal value I(T, >.) = 2" V>. > ~o . With respect to th e count a ble framework , it is wort h emphasizing t ha t Vaught 's Conject ure holds, in t he following st ro ng form. Theorem 9 .4.8 (Mayer) Let T be a (com plete) o-m in imal theory. Th en, up to isomorphism, either T has conti nuum many countable mod els, or there are two naturals n and m such that T has 3n . 6m countable models. Of course, one might get curious in reading t he st ate ment of this th eorem: why, and where, do n and m arise? Basically, they depend on a careful a nalysis of types in o-minimal structures. The interested read er may directly consult Laura Mayer 's work , quoted below .
9.5
Their proofs
This section provides t he proofs of Theorems 9.4.1 and 9.4.3 , stat ed in Section 9.4. As said, th ey are long and intrica t e. In spit e of this, we think it right to propose th em for at least two reason s. Th e form er (and th e principal) is t hat we believe t hat T heorem 9.4 .1 (t he Cell Decomposition Theorem) and T heor em 9.4.2 (the one saying t ha t o-rnin imalit y is pres erv ed under element a ry equivalence) a re two beau tiful and fundamental results and deserv e a full report , including a t echni cal preliminary like Theorem 9.4 .3. The la tter reason just concerns t he intricacy of t he proof; actually this is du e t o it s length and ingenui ty, bu t do es not depend on a relevan t a nd deep t heory, ind eed t he premises it needs a re rather element ary and accessible (they ju st include the definition of o-minimality, t he Monotonicity T heor em, some properties of cells and an induction argument). So our ex position should require no pa rticular efforts but a lit tl e attention and pat ience . And anyhow the reader who is not intere sted in th ese details may neglect this section and proceed directly to th e next ones, t hat will not use these proofs. So conside r a n o-minimal st ructu re A1 in a lan gu age L ; for simplicity, we keep our ass umption t hat t he order of A1 is dense withou t end poin ts. W hat we said in the last section in introducing Theorem 9.4.3 s uggests t he followin g definition . Definition 9.5.1 Let
CHAPTER 9. O-MINIMALITY
330
• tp(v, w ) is finite in X if an d only if, for every ii E X, tp(M, ii) is fin it e; • tp(v, w) is uniformly finite in X if and only if there is a pos it ive in teger h such that , fo r every ii EX , the size of tp(M, ii) is at mo st h.
When tp(v, w) is finite in X , we can introduce two parti al functions tp_ a nd tp+ mapping any ii E X into t he minimal and the maximal element in tp(M, ii) resp ectively -provided t ha t tp(M, ii) is not empty, of course-. If X is definab le, then tp_ a nd tp+ a re definable as well.
Definition 9.5.2 Let n be a positive integer, X be a definable su bse t of M": A decomposition of X is a part it ion of X into fin itely many cells. If y ~ X is defi nable, we say that a decomposition P of X partitions Y when no cell in P overlaps both Y and X - Y. Here is a not her t echnical preliminary notion.
Definition 9 .5 .3 Let C be an open cell of M n (so an n-cell} , tp(v, w) be a fo rm ula fin ite in C . Call a point ii E C good for' tp(v, w) if and only if the following conditions hold : 1. for every b E tp(M , ii), there are an open box B ~ C containing ii and an open interval I containing b such that tp(A1 n+l ) n (I X B) is the graph of some continuous funct ion of B in I ; 2. fo r every b E M - tp(M, ii) , there is an open neighbourhood of (ii, b) in lU n+1 disjo int f rom tp(Mn+l ).
A poin t ii E C which is not good for tp(v, w) is called (with no particular imaginat ion) nasty for tp(v, w). Not ice t hat both good and nasty poin ts for tp(v, w) form definabl e subsets of t he cell C . At this point we ca n begin our proof. The followin g lem ma is its crucial step .
Lemma 9 .5.4 Let M be an o-minim al structure, n be a positive integer, C be a cell of M n.
(l) n For eve ry eleme nt i in a fin ite set I of indexes, let X i denote a definable subset of C . T hen there exists a decomposition of C partitioning each
X i.
9.5. THEIR PROOFS
331
(2)n Let f be a definable function of C into M . Then there is a decomposition P of C such that f is continuous on any cell of P. (3)n A formula
Lemma 9.5.4 immediately implies both Theorem 9.4.1 and Theorem 9.4.3.
Proof. (9.4 .1.1) M" is an n-cell. If X is a definable subset of M", then (l)n in Lemma 9.5.4 provides a decomposition P of M" partitioning X. Hence X is the (finite) union of the cells of P it contains. .. Proof. (9.4.1.2) Just apply (2)n to the cells of the decomposition of X given by 9.4.1 , 1. .. Proof. (9.4.3) This is just (3)n when C = M":
..
Now let us show Lemma 9.5.4. We proceed by induction on n .
(1 h This just rephrases o-rninimality. (2h This is the Monotonicity Theorem (in the weak form we saw in 9.2).
(4h If C reduces to a singleton , then the claim is trivial. Hence assume that C is an open interval ]a, b[ where -00 ::; a < b ::; +00. Suppose that, for some positive integer h, the set Y of the points c in ]a, b[ such that 1 1. Let c be an end point of Y in C, and put
L + 1, 'Vc' El'. Assume for simplicity that c is a left endpoint of 1'. Define the following function 9 in 1': for every c' E 1',
332
CHAPTER 9. O-MINIMALITY
g(c') is the least element d'
E
tp(M, c') such that d' =F gi(C') for every i
~
L.
9 is definable and its domain coincides with the whole interval I'. So, as observed in § 2, 9 has a limit in MU {±oo} when x -+ c+ . d
Moreover
= lim x --+ c+ g(x).
tp_(c') < g(c') < tp+(c')
Vc' El' ,
and so d cannot equal +00 or -00, in other words d E M. If then d = d; for some i ~ L , and consequently
1=
tp(d, c),
on the other side , we know that, for every c' E I' ,
g(c') =F gi(C') ,
g(c'), gi(C') E tp(M, c').
But we contradict in this way the fact that c is good for tp (recall Definition 9.5.3 , 1). Accordingly 1= -.tp(d, c), which again excludes that c is good for tp (this time by 9.5.3 ,2) . This yields the required contradiction. Hence (4h holds.
(3h The claim is trivial when C is a singlet on. Accordingly suppose C =
la,
b[ where -00 ~ a < b ~ +00. The set of th e elements c of C for which f/J is definable, and consequently is a finite union of singletons and open intervals in C. Of course, it is enough to show that tp(v, w) is uniformly finite on every interval in this decomposition. Accordingly we can even assume tp(M , c) =F f/J Vc E]a, b[;
tp(M, c) =F
in particular tp_ and tp+ are defined throughout ]a, b[. Owing to (2h , we can even suppose (up to replacing again la, b[ with a suitable subinterval) that both ip: and tp+ are continuous in ]a, b[. Now let Y denote the set of those points in C =la, b[ that are nasty for tp. If Y is finite , say Y = {co , ... , Ct } with a < Co < .. . < Ct < b, then ip: a nd tp+ are cont inuous in each interval la, co[, ]Ci, ci+d for i < t, ]Ct, b[, and every point in these int ervals is good for tp. So we are just in a position to apply (4h, and accordingly the size of tp(M, c) is constant throughout every interval, and, in conclusion, tp(v , w) is uniformly finite in la, b[. Hence it suffices to show that Y is finite. Suppose not. Anyhow Y is definable, and hence, by o-rninimality, it contains some infinite int erval.
9.5. THEIR PROOFS
333
Without loss of generality, we can assume that this interval just equals
C =]a, b[, and so that every point e of ]a, b[ is nasty for <.p. Then, for every e E]a, b[, there exists d E M satisfying one of the following conditions:
(i) d E <.p(M, e) but, for no pair of open intervals I and J containing e and d respectively, <.p(M 2) n (J X 1) is the graph of a function of I in J; (ii) d rJ. <.p(M, e) but every open box B containing (d, e) overlaps <.p(M)2 as well.
In both cases we say that (d, e) is a black sheep of <.p (of type (i) or (ii) according to whether (i), or (ii), holds). Observe that, for every e E]a, b[, there is a minimal dE M for which (d, e) is a black sheep of <.p. In fact , as <.p( v , w) is finite in ]a, b[, there are at most finitely many d E M such that (d, e) is a black sheep of type (i). Consequently it suffices to prove that , if dl, d2 E M, dl < d2 and, for every d E]d l , d2 [, (d, e) is a black sheep of type (ii) of ip, then also (d l , e) is a black sheep of <.p. This is certainly true when d l does not belong to <.p(M, e) (in this case (dl , e) is a black sheep of type (ii)). Accordingly assume d l E <.p(A1, e) and fix two open intervals I and J containing e and d l respectively. If d E In]d l, d2[, then d rJ. <.p(M, e) and any open box including (d, e) -in particular, any open box in J X I including (d, e)- intersects <.p(M 2). Then <.p(M 2) n (J X 1) cannot be the graph of a continuous function of J in J , and (dl, e) is a black sheep of type (i) of <.p. Therefore we can consider the function g mapping any e E]a, b[ into the minimal d E M for which (d, e) is a black sheep of <.p. g is definable, and so, owing to (2h, we can find an open interval I in ]a, b[ such that g is continuous in I and one of the following conditions holds:
(iii) for every e E 1, (g(e), e) is a black sheep of type (i) of sp; (iv) for every eEl, (g(e), e) is a black sheep of type (ii) of <.p. As before, we can suppose that I is just ]a, b[. Assume (iii). Introduce two functions gl and g2 as follows. For every e E]a, b[,
• glee) is the maximal element dE <.p(M, e) satisfying d < gee), if such an element exists, and is
-00
otherwise;
• g2(e) is the minimal element dE <.p(M, e) satisfying d > gee), if such an elements exists, and is
+00
otherwise.
CHAPTER 9. O-MINIMALITY
334
Both gl a nd g2 are definable (in the obvious sen se) ; moreover we can suppose that gl is cont inuous or const a nt ly -00 in ]a, b[ and , simila rly, g2 is continuous or constant ly +00 in ]a, b[. C hoose c E]a, b[, d1 , d2 E M such that By the definit ion of gl , g2 and the continuity of gl, g2, g, t here exists a n int erval I ~ ]a, b[ containing c s uch t hat, for every c' E J,
Hence again t he definition of gl and g2 implies that
• gl (c) is the maximal elem ent d E g(c). Both gl a nd g2 have do mai n ]a, b[ becau se, for every c E]a , b[, .p: (c) < g(c) <
9 (c') E .I,
gl (c'} , g2 (c') rJ. J.
Hen ce
ti
>
1. Ass ume
(l) j , (2) j , (3) j and (4)j for 1 ::; j < n .
(l) n Let C be a cell of M n. For every i E I let X i be a definable subset of C. We a re looking for a decomposition of C part it ion ing each X i. If C is a k-cell for k < n , then there is some defin ab le hom eomorphism ITa of C onto a cell C' of M n-1 . By (1)n- 1 t here is a decomposition p I of C' part ition ing
9.5. T HEIR PROOFS
335
eac h 7!'C (Xi ). Through 71'01 , p' can be lifted to a decomposition P ofC partitioning every X i. So ass ume t hat C is ju st an n-cell . Consequ ently t here are a n (n - I )-cell C' of A1n - 1 and two funct ions f and 9 satisfying 9.3.1, 2; in part icular
C = Ha , b) E M " : a E C', f(a) < b < g(a)}. Let 7!'C be the projection of C onto C'. By (1)n-1 there exists a decomposition P' of C ' partitioning each 7!'c(Xi)' For every Y' E P' , let Y = {(a,
b) E C : a E Y'} .
Clearl y these sets Y partition C when Y' ra nges over P'. So it suffices to show that , for every Y ,
(v) t here is a decomposition of Y partitioning eac h set X i for which 7!'c(Xi)n
Y'-# 0.
To simplify t he notation , assume without loss of generality that 7!'c(Xi) Y' -# 0 for every i E I. Fi x i E I and , for ever y a E Y' , conside r
n
X i(a) = {b E M: (a, b) E Xi} ' Th ere is a formu la
ft , ... ,
n,
mapping any a E Y' int o t he first , . .., t he hi-th eleme nt of Bi (a). All t hese functi ons a re definable; by (2) n-1, we ca n assume that t hey are cont inuous on Y'. Unless partitioning agai n each X i, we ca n also s uppose t hat, for every i and j in I , h = 1, .. . , hi and h' = 1, ... , hj , exactly one of t he following cases holds: Va E Y' , f i(a) = f~/(a) ,
336
CHAPTER 9. O-MINIMALITY
vs E Y' , vs E Y' ,
f~(a) < f~,(a) , f~(a) > f~/(ii) .
Accordingly we can rearrange t he fun ctions f~ (i E I , 1 ~ h ~ hi ) and form a new sequence
go , . .. , gt s uch t hat, for r ~ 8 ~ t, gr(a) < gs(a) for every a E Y'. But t his implies th at t he sets of t he tuples (a, b) E Y s uch that a E Y' a nd
f(a) < b < go(a), gs(a) < b < gs+t{a) (8 < t) , gt(a) < b < g(a) , b=gs(a)
( 8 ~t)
resp ecti vely, form a decomposition of Y parti tioning each X i , as claim ed. This concludes t he proof of (l)n . Acco rdingly ass ume fro m now on also (l)n .
(2)n Let C be a cell of A1n a nd let f be a definabl e function from C into
M . Wh at we have t o find is a decomposition P of C in cells wh er e f is continuous . If C is a k-cell for so me k < n , t hen t here exists a defin able hom eom orphism KC of C on to a cell C ' of J\I1 n- l . By (2)n-I ' ther e is a decomposition P' of C ' in cells such that f K CI is continuous on each of them , and K CI lift s P' to a decomposition P as required . So assume that C is an n- cell, in other words an op en cell in M n . Let
Cl be the set of tuples (a, b) E C such th at
defines a continuous fun ction f b on some op en box B of M n-l cont aining a and satisfying B X {b} ~ C, C 2 be t he set of tu pies (a, b) such t hat X n J----7 f (a, x n ) defines a function fa eit her constant or strictly monotonic on some op en int er val I con t aining b and satisfying {a} x I ~ X , a nd, in t he lat t er case, also f(l ) is an op en interval and f is a bijection bet ween I a nd f(l ).
9.5. THEIR PROOFS
337
Use (l)n and get a decomposition P of X partitioning both Cl and C 2 • So it is enough to show that f is continuous on every cell of P, and even on every open cell D of P, owing to what we observed at the beginning of this point. Then there are a cell D' of Mn-l and two functions ft, h satisfying 9.3.1,2 and
D = {(a, b) E l'vr
a E D' , ft(a)
< b < h(a)}.
Notice:
(vi) D < Cl . In fact let b E M satisfy (a, b) E D for some suitable a E u»:', As the domain of 9 includes D, fb is defined in some open subset of D'. By (l)n-l and (2)n-l, there is some open cell in D' where fb is continuous. For a in this cell, (a, b) E Cl. Hence D n Cl =I- 0. As P partitions Cl, D ~ Cl. Now we claim
(vii) D
~ C 2 and, for every a E D' , fit is either constant or strictly monotonic in]ft (a), h(a)[ (and, in the latter case, the image of]ft (a), h(a)[ is an open interval and fit is a bijection between these intervals).
D ~ C 2 can be shown by proceeding as for Cl. Now take the Monotonicity Theorem, there are a natural m and bl , that fl(a) < bl < .. . < b-: < ft(a),
a E D'. ... ,
Owing to bm E M such
fit is either constant or strictly monotonic in each interval J among jjj (a), bl [, ]bj, bj+l[ (for 1 ::; j < m) and ]bm , h(a)[, and, in the latter case, even fit(J) is an interval and fit induces a bijection between J and fit (J). Choose m minimal. If m = 0, then the only involved interval J is just ]fl(a), h(a)[, and (vii) is trivial. On the other side, if m > 0, then fit is neither constant nor strictly monotonic in any open interval containing bl ; as (a, bd E D and D ~ C 2 , (a, bt) E C 2 , which contradicts the definition of C 2 • So m = 0, and we are done. At this point, we are in a position to conclude the proof of (2)n' In fact, let (a, b) E D, J be an open interval containing f(a, b); we are looking for an open box B of Mn including (a, b) and satisfying f(B) ~ J. Owing to (vii), there is a closed interval I = [bl , b2 ] of M such that b is in the interior of I, I ~]ft(a), h(a)[ and fit(I) ~ J. By (vi) there exist two open boxes n, and B 2 of M n - l both containing a, and satisfying the additional conditions
n. X
{bi} ~ D,
f(Bi ' bi) ~ J
Vi = 1, 2.
CHAP TER 9. O-MINIM ALITY
338
Let B' be an open box of M n- 1 such that B' ~ B 1 n B 2 , ii E B'. Then f (B'x 1) ~ J . In fact, let a E B' , b' E I , so f( al ) < b1 becau se B' x{bd ~ D a nd b2 < 12 (;' ) because B'' X {b 2 } ~ D . Consequent ly
it (a < b1 < b' < b2 < 12 (al ) . ') Furthermore f (;' , bt) E J , f(;' , b2 ) E J. As fa! is eit her con stant or st rictly monotonic in ]f1(;') , 12(;')[, f (;' , b') E J. Accordingly f(B' X 1) ~ J. T his accom plishes our proof of (2)n. So we ca n ass ume even (2) n tr ue from now on. At t his point let us deal with
(3)n. (3)n Let i.p (v, W1 , ... , w n ) be a formula, C be a cell of M n such t hat i.p (v, W1, . . . , w n ) is finite in C . The case when the dim ension of C is strictly
smaller t ha n n ca n be handled as befor e. So we ca n limit our a na lysis to t he case when C is a n n-cell, in other words is op en. Let
Cl be t he set of those poin ts (ii, b) E C suc h t hat ii is good for i.p (v , W1 , ... , W n-1 , b) , C 2 be t he set ot the point s (ii, b) E C such t hat b is good for i.p (v, ii, w n ) resp ectively (ii a bbreviat es here (a1 ' . . . , an-1)). By (l) n' there is a decomposition P of C parti tioning both Cl an d C 2 • We claim
(viii) for every open Y in P, Y
~
Cl and Y
~
C2 •
In fact , let (ii, b) E Y , and let B be an open box in Y including (ii, b). Th e projecti on B' of B onto t he first n - 1 coordinates is an open box of M n- 1. By (3)n-1 , i.p (v, W1, . . . , Wn-1 , b) is un iforml y finite in B' . By (1)n-1 and (2) n-1, there are a n op en cell C ' ~ B' an d a posi t ive integer h such t hat, for everya E C', i.p (M, ai, b) has size h a nd t he functions mapping an y;' E C ' into ' the first , ..., the h-th elem ent of i.p(M, ai, b) resp ectively are continuous. Let;' E C'. It is easy to see t ha t ;' is good for i.p(v, W1 , . . . , W n-1 ,
b).
T hen (;', b) E Cl, and Y n Cl =1= 0. Hence Y ~ Cl . Y < C 2 is show n in a similar way. In conclusion, if Y is an open set of P, then for ever y (ii, b) E Y , d is good for i.p (v, W l , . . . , Wn-l , b), b is good for i.p(v, ii, w n). So it suffices to show wh at follows.
9.6. DEFINABLE GRO UPS IN O-MINIMAL S T RUCTURES
339
(ix) IfY is an op en cell of M n,
Simila rly (4)1 implies
In co nclusion
1
a nd t his accomplishes t he proof of (3)n' T he last claim t o be examined is (4)n' Bu t now t he proof is a direct con sequ ence of what we have just obse rved . In fact, recall t hat, if Y is an op en box of M n and t he poin ts (a, b) of Y a re good for
9.6
Definable groups in a-minimal structures
Which st ruct ures are definable in o-minimal models? The aim of this sect ion is ju st t o measure how complicated o-mini mal struct ures are up t o biin t erpret a bility, a nd so t o answer t he previou s q uestion , and to reali ze which groups , or rin gs, or ma nifold s are definabl e in t hem . In par t icul ar t he int er est in definable manifolds arises qui t e naturally from t he connection bet ween o-minimality and (a nalytic) geometry und erli ned at t he beginning
340
CHAPTER 9. O-MINIMALlTY
of this cha pt er. We saw what a manifold is (inside a n algebraically closed field K) in Section 8.5 , where we observed that every manifold in K is definable in K. In an ar bitrary o-rnin im al st ruct ure M a manifold may not be definable. Accordingly, first we fix wh at definable manifold means. It is just a finite family (V, (Vi, f;)i~ m) where m is a natural number a nd
* *
*
V =
Ui ~ m Vi
is t he at las,
each f i is a bijection from Vi onto a definable open subset U, = f i(Vi) of M" for some natural n independent of i , for i, j ~ m and i =Iin Ui;
* for
i , Ui,j
= f i( Vi n\!j) is, again, definable and op en
i, j ~ m and i =I- i , f i,j = f i between Ui,j and Uj,i'
i;'
is a definable hom eomorphism
After fixing this definition, let us look for groups and manifolds definable in o-rninim al st ructur es. Even at a first superficial sight on e can meet some non-trivial exam ples: for instance, it is quite obvious t hat , for a real closed field K, the linear groups GL(n , K) a re definable in K. Indeed , a sharp analysis displays some notable similarities with the w-stable framework. In particular, by ad apting the Hru shovski-Weil Theorem 8.6.2, Pillay showed Theorem 9.6.1 Let M be an o-m inimal st ructure, and g be a group definable in M. Th en g can be equipped with a (uniqu e) definable manifold structure mak ing it into a topological group. When M expands th e real field , t he manifold topology makes g into a locally E uclidean t opological group an d in conclusion, owing to the Montgomery, Zippen an d Gleason solut ion of Hilb er t 's Fifth Problem , into a Lie group. Definable groups hav e been intensively studied in o-rninimal st ructures . In particular we would like to mention an o-rninimal analogue of Cherlin 's Conjecture, proved by Peterzil , Pillay and Starchenko. Theorem 9.6.2 Let M be an o-m inimal structure, g be a connected group definable in M and having no definable non-trivial normal abelian subgroup. Then there is a definable isomorphism of g onto the conn ected component of an algebraic group over a real closed field. Not ably, a local version of Zilb er 's Conjecture is t rue in t he o-rninimal sett ing, as shown by Peter zil and Starchenko. Let us discuss briefly t his matter.
9.7. O-MINIMALITY AND REAL ANALYSIS
341
Giv en an o-rninimal M, call an element a E M trivial when there are no open interval/including a and no definable f from / 2 into I which is st rictly monotone in each variable. T heore m 9.6.3 (Tri chotomy Theorem ) Let M be an 'No-saturated o-minimal structure, a E M . T hen exactly one of the follow ing conditi ons holds :
(i) a is tri vial, (ii) there is some convex neighbourhood of a where M induces a structure of an ordered vectorspace over an ordered divi sion ring,
(iii) there is some open interval including a where M induces a structure of a real closed field .
9.7
0-minimality and Real Analysis
In t his section, we introduce some new examples of o-minimal st r uctures . They concern some expansions of t he real field closely related t o Real An alysis and Geometry. Ind eed Model Theory meets t hese areas within o-rninimali ty, and provide s new ideas , new t ools and, definit ively, new pers pectives in studying t he involv ed st ructures . 1. R ex p
The first exam ple we wish to deal with is the most famous as well. It concern s the exponent iat ion in t he real field . We have seen in Ch apt er 2 Tarski 's Theorem showing that the t heory of th e real field R has the elimination of quantifiers in the lan guage L of ordered fields: accordingly
definable = sem ialgebraic in this set t ing. Tarski also gav e an effective procedure reducing an y formula
342
CHA PT ER 9. O-MINIMALITY
Tarski also proposed t he following que stion . Expan d R to a st ruct ure R ex p = (R, 0, 1,
+, " - , ~ ,
exp)
where ex p is the l-ary function mapping any real x into eX. Accordingly add a l-ary operation symbol (for exp ) t o L and denote by L ex p t he enla rged lan gu age: hence L ex p = L U {exp} = {O, 1,
+, " - , ~ ,
ex p }.
Conjecture 9 .7.1 (Ta rski) T he theory of R ex p is decidable.
On e ca n observ e t ha t the th eor y of R ex p is not qu an t ifier elimina ble in L ex p : this was shown by Van den Dries in 1982. However in 1991 Wilkie proved it s model completeness. Theorem 9.7.2 (Wilkie) T he th eory of R ex p is model complet e.
In particular , the definable sets in R ex p ca n be obt ained as follows. For n any positive integer , call a subset E of R " expon ential when it has t he form
for a suit able real polynomial f wit h 2n unknowns. Notice t hat expon enti al sets are closed und er finite un ion and intersect ion (as the points a nnihilating at least one of finit ely man y polynomials a re ju st the zeros of their product , and the poin t s annihilating a finite system of real polynomials are just the zeros of the sum of their squa res). But , according to the Van den Dries remark on (the failure of) qu antifier eliminat ion, the definable sets in R ex p are something larger than the finit e Boolean combinat ions of exp onent ial sets. So let us introduce subexpon ential sets. A subexponent ial set in R " is just t he image of an exponential set of R n +m (for som e m) und er t he proj ection map of R n +m onto the first n coordinat es in R " . Clea rly exponential an d subexponent ial sets are definable. What Wilkie showed is that s ubexponent ial sets are closed under complement. This implies model com plete ness, a nd prov es that in R ex p
definable = s ubexponential.
9.7. O-MINIMALJTY AND REAL ANALYSIS
343
At this point, one can use a theorem of Khovan skii saying that every exponential set, and consequently every subexponent ial set , has only finitely many connected components. Just apply this result to definable (equivalently subexponential) subsets of R and get Corollary 9 .7 .3 R exp (and its theory) are o-minimal. Later Ressayre gave a nice axiomatization of T h( R exp), showing t hat its mode l theory requires very simple global infor mat ion a bout exponentiation. But now let us come back to Tarski's Conjecture. W hat can we say about it ? Well, there is a famous conjecture in transcendental number theory, due to Schanu el a nd saying: Conjecture 9 .7.4 (Schanuel) Let n be a positive integer', al, .. . , an be complex numbers lin early independent over th e rational fi eld Q . Then the transcendence degree of Q (al ' .. . , an, e a j , •• • , e a n ) over Q is at least n. Remarks 9 .7 .5 (a) Schanuel's Conjecture has been proved in some particular cases, for exa mple when n = 1, or al , . .. , an are algebraic (Lindemann) . (b) 1, e are linearly independent over Q . Hence Schanuel's Conjecturewould imply t hat Q (l , e, el, ee), in other words Q (e, ee),has transcendence degree 2 over Q , and hence e, e" are algebraically independent. Nevertheless, as far as one presently knows, it is still an open question whet her e" is irrational. (c) 1, in are linearly independent over Q . Hence Schanuel's Conject ure would imply that Q (l , in , el , ei 7l" ) , hence Q (e, i1r) (as e i 7l" + 1 = 0), has transcend ence degree 2 over Q , and conseque nt ly that e and n are algebraically independent: but this is still an open question, as well know n. It is generally felt that a solution of Scha nuel's Conjecture is vary far , and should go beyo nd the present knowledge in Mathematics. However a positive answer to the qu estion of Schanuel would imply a solution of Tarski's Conjecture as well.
Theorem 9 .7.6 (Macintyre-Wilkie) If Schanuel's Conjecture holds, then Th( R exp) is decidable.
CHAPTER 9. O-MINIMALITY
344
2. R an
Now we deal with real an alytic fun ctions f. Her e we have t o be very ca reful in fixing our setting. In fact , we hav e t o recall what happens when we expa nd the reals by sin (or cos ): o-minim ality gets lost. However one sees t hat o-rninimality is preserved if we restrict t he dom ain of t he sinu s function t o a su itable interval] - ~ , ~ [ . Accordingly one takes a language L an enlarging the language L of ord ered fields by a l-ar y op eration sy mbol j for every function f a nalytic on som e op en subset U of R " containing th e cube [0, l]n (n ran ges , as usual , over positiv e integers , and th e only reason to choose [0, 1] instead of another interval is ju st to fi x and normalize our set t ing); th en one t akes the Lan-structure R an expanding the real fi eld R a nd int erpreting any symbol j in t he funct ion equalling f in [0, I]" a nd ass uming th e constant value 0 elsewhere . Notic e that L an is uncoun t abl e. R an is called t he real field with restri cted analytic function s. Theorem 9.7.7 (Van den Dri es) Th(R an ) is o-min imal.
model complete and
Van den Dri es ' a nalysis also determines what is definabl e in R an . In fact , t he definable sets a re exactly t he so called globally s ubanalytic sets. They are ob t ained as follows. Call a subset A of an a na lyt ic manifold X semian aly tic in X if t here is a n op en covering U of X s uch t ha t , for ever y U E U , A n U is a finite union of sets {a E U : f (a ) = 0, 9o(a), ... , 9k(a )
> O}
where f and t he 9 'S ar e ana lyt ic function s on U . At t his point call a subset B of X suban aly tic in X if there is a n op en covering U of X such that, for every U E U , B n U is th e image of some A semia nalyt ic in U X R'" by t he projection map from U X R '" onto U (here m may depend on Band U ). F ina lly call S ~ R " globally subanaly tic if it is suba nalyt ic in th e analyt ic manifold (P 1 (R) )n (where P 1 (R) is t he real projective line). Gabrielov showed a "theo rem of t he complement" for subanalyt ic sets in an analyt ic manifold X, ensuring th at t hey are ju st closed und er com plement . This is t he key result in showing t he mod el completeness and t he o-minimality of the t heory of R an' a nd also in proving th at
definabl e = globally s ubanalytic
9.7. O-MINIM ALIT Y AND REA L ANALYSIS
345
in R an. Does Th( R an) admit quantifier elimination? Denef and Van de n Dri es showed t hat the answer is positive, provided one extends the language L an by a symbol - I for the inverse function (with the usual convention 0- 1 = 0). Theorem 9.7.8 (Denef-Van den Dries) Th( R an) elim inates the quantifiers in t.. ; U {-I} . 3. R an,exp
F inally let us examine what happ ens when we expand t he reals bot h by t he exponent ial fun ct ion a nd t he rest rict ed analytic functions . Let L an ,exp = L an U { exp} the corresponding language, R an,exp t he result ing struct ure in Lan ,exp. First Van den Dri es and Miller, adapting Wilkie's wor k on exponentiation, pr oved Theorem 9.7.9 (Van den Dri es-Miller ) Th e theory oj R an,exp is model complete and o-minimal. Subsequently, Van den Dries, Macintyre and Marker fou nd a different proof providing a nice axiomatization of the theory of R an,exp in Ressayre's style. They got also quantifier elimination in a language extending L an ,exp by the logari th m function log . Theorem 9.7.10 (Van den Dries-Macintyre-Ma rker ) Th e theory o] R an,exp eliminates the quantifiers in the language L an,exp U {log} . Notably, t he logari t hm function cannot be ignored to obtain qu an tifier elimina t ion . T he Van de n Dri es-M acint yr e-Marker approac h also provides an explicit desc ript ion of t he definabl e sets in R an, ex p , following t he sa me lines as in t he cases before . Of course t hese examples are very far from exhausting a general displ ay of t he a-m inimal ex pansions of the real field (a wider information ca n be foun d in the references quoted at the end of t he chapter) . But t hey ca n illust rate how rich and int eresti ng t his research field is. Let us conclu de t his section with some final remarks partly exceeding the a-minimal limits. In fact, it is noteworthy that , although Model Theory and Real Analysis closely interact via o-minimality, Complex Analysis has
346
CHAPTER 9. O-MINIM A LIT Y
raised a lot of difficulties to a model t heoret ic t reatment . For inst a nce, whi le expanding the reals by exponentiation gives an o-mi nimal structure (by Wilkie's Th eo rem), (C , +, " - , 0, 1, ex p) defines the integers by the formula exp(27riv) = 1, so t hat there is a very lit tle hope to dominat e its first order t heory, its definable sets, a nd so on. Indeed , the zero sets of com plex an alytic fun ctions can be quite pathological. Some years ago , Boris Zilber proposed a satisfactory st rategy to develop th e mod el theory of the complex exponentiation, but his program needs som e very strong conjectures on t ranscendental numbers (even beyond Schanuel's P roblem). Zilber also followed a more successful approach, looking at analytic compact manifolds X rather than at an alytic function s: in fact , t hese manifolds can be viewed as first order structures in a language with a relat ion for any su banalytic subset of every power of X. In this setting one shows Theorem 9 .7.11 (Zilber) T he theory of a compact complex manifold eliminates the quantifiers and has a finite Morley rank.
9 .8
Variants on the a-minimal theme
Strongly min imal theories have a natural en largement to totally transcenden t al (i. e. w-stable) theories via Morley ra nk. In the ordered setting nothing is known ext ending sistematically o-minimality in a parallel way. However just the ord ered framework suggests several notions widen ing 0 minimality : they have been intensively studied in th e latest years. In pa rticular we want to discuss here briefly weak o-minimality. As said, we still work wit hin linearly ordered structures M = (M , ::; , ...). Recall that M is o-minimal when every definable subset D of M is a finite union of interval s (possibly with infinite endoints); not ice t hat intervals ar e convex. Definition 9 .8 .1 M is called weakly a-minimal when every definable subs et D of M is a finit e union of con vex (definable) sets. Remark 9.8.2 Of course, o-rnin imality implies weak o-minim ality. Moreover , among exp ansions of the real line (R, ::;), the converse is also true, and weak ly o-minimal just means o-m inimal. This is because (R , ::;) is Ded ekind comp lete, and every bo unded set has its own least upper bound and its own
9.9. N O ROSE WITHO UT THORNS
347
greatest und er bound ; in particular every convex set is an interval (in t he broader sense recalled before). However t here do exist weakly a-minimal structures which are not a-mini mal. Example 9.8.3 Take t he ordered field of real algebra ic numbers Ra. This is a real closed field , an d so an a-minimal st ruct ure. Add a 1-ar y relation select ing t he elements of Ra lying between - IT and IT (or, if you like, bet ween a ny two reals a < b wit h a or b t ranscende ntal) . The resulting st ruct ure is not a-minimal an y more, because D = {r E R a : -IT < r < IT} is convex and definable, but ca nnot be expressed as a finit e union of intervals with real algebraic end points. But act ua lly D is convex, and ind eed one can see that t he new structure is weakly a-minimal. Notably, every expa nsion of an a- minimal struct ure by convex subsets is wea kly o-minimal. This is a beau tiful result of Baisalov-Poizat , generalizing t he las t exa mple and answering in t his way a question of Cherlin. Oth er releva nt exam ples, ar ising from several frameworks in Algebra , ca n be proposed. By t he way, weak o-rninimality was first introduced by M. Dickmann in 1985, dealing wit h certain ord ered rings extending real closed fields. Not surprisingl y, weakl y a-minimal st ruct ures do not behave so well as 0 minimal do. In particular weak o-minimality is not preserved by eleme ntary equivalence (so t here are wea kly a-minimal struct ures whose t heo ry has some non wea kly a-minimal models) . Furt hermore Monotonicity and Cell Decomposition fail as well as existence and uniqueness of prim e mode ls. However some " wea ker" versions of these results ca n be recovered , and a relevant, alt hough not so fluent , th eory has been developed.
9.9
No rose without thorns
We have seen t hat a- minimal t heo ries admit an ind ep endence noti on related to algebraic closure and satisfying t he same basic proper ties (11 )-(16) forkin g ind epend ence has in sim ple t heor ies. However t hese ind ependence notions -forking indipend ence in sim ple t heories and algebraic ind epend ence in a-minimal th eories- were introduced in a different way and were develop ed ind epend ently. So a natural qu estion arises in Mod el Theory, Le. to
CHA PTER 9. O-MINIM ALIT Y
348
find a new conce pt of ind ep end ence so con vincing t o satisfy (11)-(16) in most t heo ries and so general t o enla rge bo th t he pr eviou s cases. This is the cont ent of a recent work of Alf On shuus wh o, following suggest ions from Thomas Sca nlon, int ro du ced • a new noti on of indep endence (ca lled thorn-independence) a nd • a related class of t heor ies (named rosy theories) whe re t horn-i nde pe nde nce enjoys all t he bas ic ass umptions (11 )-(16) , so local character, sym met ry a nd so on. Rosy t heories include both sim ple and 0 minim al t heories, as well as fur ther relevant examples. Thorn-indep endence agrees wit h algebraic indep endence in t he o-minimal case a nd with forking ind ep endence in stable t heo ries: in fact , wh en t hese pages are written (at t he end of 2002 ) , it is not clear whether t horn- indepe nde nce eq ua ls forkin gindep endence even in the simple setting, although t his has been checked to be t rue in all t he known key examples of sim ple t heor ies. Notably symmetry, or also local character, is a key property towards ros iness. In fact , a t heo ry T is rosy if a nd onl y if t ho rn- inde pe nde nce satisfies sy mmet ry or local character .
9.10
References
O- minim al t heories where introdu ced by Van den Dries [166] a nd extensively st ud ied by Pill ay and Steinhorn in [129] and (together with J. Knight ) in [74]. Van den D ries' book [169] provides a nice a nd stim ulating treatment of o-rnini mality, also describing it s genesis a nd moti vat io ns, a nd em phas izing it s con nect ions wit h real analysis and real alge braic geometry. T hese int er acti ons ar e illust rat ed in t he mor e recen t survey [170], where t he 0 minimal ex pa nsions of t he real field are examined. Also [109] gives a sho rt, but captivating introd uction to o-rninim ality, A ge neral proof of Monotonicity Theorem 9.2.1 can be found in [129]. Wilki e 's Complement T heorem 9.4 .5 is show n in [178], a nd t he Pill ay-St einhorn T heorem 9.4.7 on prime models in o-rnin imal t heories is in [129] again . Laura Mayer 's sol ution of Vaug ht Conjectu re in t he o-rn inimal setting is in [111]. Pill ay 's a na lysis of t he groups defina ble in o-minimal struct ures (T heorem 9.6.1) is in [125], while t he o-rninimal analogue of C herlin Conjecture shown by P et erzil , Pill ay and Starchenko (9.6.2) is in [123] a nd the P et erzilStarchenko Theorem 9.6.3 is in [124].
9.10. REFERENCES
349
As already said [170] provides a general sur vey of the main o-minimal expansions of the real field, and a rich and detailed bibliography on this matter. In particular Wilkie's Theorem 9.7.2 on R ex p is in [177], and the Khovanskii's results on exponential sets in [70]; Ressayre's approach to the theory of R ex p can be found in [139]; the Macintyre-Wilki e Theorem on the decidability of the theory of R ex p and its relationship to Schanuel's Conjecture is in [99]. The o-minimality of the theory of Ran is proved in [167], using [49], while the Denef- Van de n Dries treatment -including the quantifier elimination result in a language with the inverse operation- is in [30]. The o-minimality of the theory of Ran,exp is already shown in [171], but the subsequent analysis of Macintyre, Marker and Van den Dries is in [97]. Zilber 's Theorem 9.7.11 on compact complex manifolds can be found in [183]; see also [128] . Now let us deal with weak o-minimality. This was introduced in [32], and extensively examined by Macpherson, Marker and Steinhorn in [100]. The nice theorem of Baisalov-Poizat (mentioned at the end of Section 9.8) is in
[7]. Rosy theories and thorn-independence are just the matter of [122].
Bibliography [1] J . W . Addison , L. Henkin , and A. Tarski, editors. Nort h Holland , Amsterdam , 1965.
Th e theory of models.
[2] F . App enzeller . Classification Theory through St at ionar y Logic. A nn. P ure Appl. Logic, 102:27-68 , (2000) . [3] J . Ax. T he elementary th eory of fi nite fields. A nn. Math ., 88:239-271 , (1968) .
[4] J . Ax and S. Kochen . Dioph an ti ne probl ems over local fields I. Amer. J. Math ., 87:605-630, (1965) . [5] J . Ax and S. Kochen . Dioph antine problems over local fields 11: A complete set of axioms for p-adic number th eory. A mer. J. Math ., 87:631-648 , (1965) . [6] T . Ax and S. Kochen . Diophantine pr oblems over local fields Ill: Decidabl e fields . A nn. Math ., 83:437-456, (1966). [7] Y . Baisalov and B. Poizat . Paires de structures o-minirnales. J. S ymbolic Logic, 63:570 -578 , (1998) . [8] .1. Baldwin . Fundam entals of Stability Theory. Spr inger Verlag, Berlin , 1988.
[9] J . Bald win and A. Lachlan. On strongly minim al sets. 1. Symbolic Logic, 36:79-9 6, (1971) . [10] J . Barwise, edit or . Handbook of Math ematical Logic. Nort h Holland , Amsterd am , 1977 .
[11] .1. Barw ise and S. Feferman , editors. Model-theoretic logics. Springer, New York , 1985. [12] L. Blum . Generalized Algebraic Theories. PhD th esis, M.I.T., Ca mbridge, 1968 . [13] L. Blum , F . Cucker , M. Shub, and S. Sm ale. Complexit y and Real computation. Springer, New York , 1998. [14] L. Blum, M. Shub, and S. Sm ale. On a t heory of com put at ion and complexity over t he real numbers. Bull. Amer. Moth . Soc., 21:1-46 , (1989) .
351
352
BIBLIOGRAPHY
[15] A. Borovik and A. Nesin . Groups of finite Morl ey rank. Oxford Univ ersity Press, Oxford , 1994. [16] E. Bous caren , edit or . M odel Th eory and Algebraic Geom etry, volume 1696 of Lecture N otes in Math ematics. Springer , Berlin , 1998. [17] A. B. Ca rson. The m od el complet ion of the th eory of com mut ative regul ar rin gs. J. Alg ebra, 27:136-146 , (1973). [18] C . Chang and H. Keisler. Model Th eory. North Holland , Am st erdam, third edition , 1990. [19] Z. Chatzidakis. Theorie des rnod eles des corps finis et pseudo-finis. Prepublications 59, Equipe de Logique Mathematique, Universite Paris VII , (1996) . [20] Z. Chat zidakis and E. Hrushovski. The model th eory of difference fields . Trans . Amer. Math . Soc., 351:2997-3071 , (1999) . [21] Z. Chat zidakis, E . Hrushovski , and Y . Pet erzil. Mod el t heory of difference fields , 11: Periodi c ideals and th e trichotomy in all characte rist ics. Preprint . [22] G . Cherlin. Algebraically closed com mut ative rin gs. 38:493- 499 , (1973) .
J. Symbolic Logic,
[23] G. Cherlin . M odel Theoretic Algebra, volume 521 of Lecture No tes in Math ematics. Springer Verlag, Berlin , 1976. [24] G . Cherlin. Groups of small Morley rank. A nn . M ath. Logic, 17:1-28, (1979). [25] G. Cherlin and S. Shelah. Superstable fields and rin gs. A nn. Math . Logic, 18:227-270 , (1980). [26] P. Clote and J . Kr aji cek, editors. A rithmeti c, Proof Th eory and Computational Complexity. Oxford University Press, Oxford , 1993. [27] P. Cohen . Decision procedures for real and p-adic fields . Com m . Pure Appl. Math ., 22:131-151, (1969). [28] R. M. Cohn. Difference algebra, volume 17 of Tracts in Math ematics. Interscience , New York , 1965. [29] G . E. Collins. Quantifier elim inat ion for real closed fields by cylindrical algebr aic decomposition. In A utom ata Th eory and Formal Language, volume 33 of Lecture N otes in Computer Science, pages 134-1 83, Berlin , 1975. Second GI Conference, Kai serslautern, Springer . [30] J. Denef and 1. Van den Dries. p-adi c and real subanaly ti c sets . A nn. Math ., 128:79-138, (1988). [31] K . Devlin . The j oy of sets. Undergraduate Text s in Math . Springer Verlag, Berlin, 1993.
BIBLIOGRA PH Y
353
[32] M. Dickmann. Elimination of quantifiers for ord ered val uation rings . In Proceedings 3rd Easter Model T heor y Confer ence, Humb oldt Unive rsitiit, pages 64-88, 1985. [33] A. Dolzm ann , T . Sturm , and V . Weispfenn ing. Real quantifier elim inat ion in pra cti ce. In A lgorithmic A lgebra and number theory, pag es 221-247. Springer , Berli n , 1999. [34] J. Doner and W . Hodges. Alfred Tarski and decidable th eori es. J. Symbolic Logic, 53:20-35 , (1988) . [35] J. 1. Duret . Les corps pseud o-finis ont la propriet e d 'independence. C. R. A cad. Sci., 290:98 1-983 , (1980) . [36] H. D. Ebbinghaus. Nu m bers, volum e 123 of Graduate Texts in Ma th. Springer Verl ag, New York , 1990. [37] H. D. Ebbingha us , J . Flum , and W. T homas. Ma thema ti cal Logic. Undergrad uate Text s in Ma t h . Spri nger Verlag, Berlin , 1979. [38] A. Ehrenfeucht and A. Mostowski. Mod els of axiom atic th eori es admitting automo rphisms . Fund. Math., 43:50-68 , (1956) . [39] P. Eklof. Ultraproducts for Alg ebraist s, pages 105- 137. In Barw ise [10], 1977. [40] P. Eklof and E. Fis her. T he eleme nt ary t heory of abelia n gro ups . A nn . Ma th. Logic, 4:115- 171, (1972). [41] P. Eklof and G . Sabbagh. Mod el com pletions an d modules. Ann. Math . Logic, 2:251-295, (1970-71). [42] H. Enderton. Elem ents of recursion theory, pag es 527-566. In Barwise [10], 1977. [43] E . Engeler. A characterization of th eories with isomorphic denumerable models. N otices Amer . Ma th. Soc., 6:161, (1959). [44] Vu. L. Ershov. On th e eleme nt ary theory of maximal norm ed fields . A lgebra i Logika, 4:31- 70, (1965). [45] Vu . L. Ershov. On t he eleme ntary theory ofmaxim alnormed fields 11 . A lgebra i Logika, 5:5-40, (1966). [46] Vu . L. Ershov. Fields wit h a solvab le theory . So viet Ma th. Dokl., 8:575-576 , (1967) . [47] M. Fisher and M. Rabin. Super exponent ial com plexity of Presburger 's arit hmeti c. S IAM-AMS Proc ., 7:27- 41, (1974). [48] J. Flum . First order Logic and its exte nsions. Number 499 in Lecture Notes in Math em atics. Springer Verl ag, Berlin, 1975. [49] A. Gabrielov. Proj ections of semianalytic sets . Functional A nalysis and its Applications, 2:282-291, (1968).
354
BIBLIOGRAPHY
[50] J . B . Goode. H.L.M. (Hrushovski-Lang-Mordell) . Technical Report 48m e annee, Serninaire Bourbaki, 1995-96 . [51] R . C. Gunning and H. Rossi . Analytic functions of several complex variables. Princeton Hall Inc ., 1965. [52] P. Halmos. Lectures on Boolean Algebras. Van Nostrand, Princeton, 1963. [53] B. Hart , E. Hrushovski , and M. Laskowski . The uncountable spectrum of countable complete theories. Ann. Math ., 152:207-257, (2000) . [54] D. Haskell, A. Pillay, and C . St einhorn, editors. Model Th eory, Algebra and Geometry. MSRI Publ. , Cambridge UP, 2000. [55] L. Henkin. The com plete ness of t he first order functional calculus. J. Symbolic Logic, 14:159-166 , (1949) . [56] W . Hodges. Model Theory . Cambridge University P ress, Cambridge, 1993. [57] W . Hodges. A shorter model theory. Cambridge University Press, Cambridge, 1997. [58] E. Hru shovski . T he eleme ntary theory of the Frobenius. Preprint. [59] E . Hrushovski. A new strongly minimal set . Ann. Pure Appl. Logic, 62:147166, (1993) . [60] E. Hrushovski . The Mord ell-Lang Conjecture for fun ct ion fields. J. Amer. Math . Soc., 9:667-690 , (1996) . [61] E. Hru shovski. The Manin - Mumford conjecture and the model theory of difference fields. Ann. Pure Appl. Logic, 112:43-115 , (2001) . [62] E. Hrushovski and Z. Sokolovic. Minimal subsets of differentially closed fields . (to appear) . [63] E. Hrushovski and B. Zilber . Zaris ki 's geom etries. Bull. Amer. Math. Soc., 28:315-324 , (1993) . [64] E. Hru shovski and B. Zilber. Zariski 's geom etries. J . Amer. Moth . Soc., 9:1-56 , (1996). [65] N. .Jacobson . Basic Alg ebra. Freeman, San Francisco, 1974-1980. [66] T . J ech. Set Th eory. Academic Press, New York - London, 1978. [67] I. Kaplansky. Differential A lgebra. Hermann, 1957. [68] A. Kechris . New dir ections in Descriptive Set Theory. B ull. Symbolic Logic, 5:161-1 74, (1999) . [69] J. Ketonen . The structure of countable Boolean algebras. Ann. Math ., 108:4189, (1978) . [70] A. Khovanskii . On a class of systems of transcendental equations. Sovie t Math . Doklady , 22:762- 765, (1980) .
BIBLIOGRAPHY
355
[71] B. Ki m . Forking in simple unst able t heories. 1. London Mat h. Soc., 57:257267, (1998) . [72] B. Kim . Simplicity and stability in there. J. Symboli c Logic, 66:822-836 , (2001). [73] B. Kim and A. Pillay. Simple t heories. Ann. Pu re Appl. Logic, 88:149- 164, (1997) . [74] J . Knight , A . Pi llay, and C. St einhorn . Definable sets in ordered struct ures 11. Trans. Amer. Math. Soc., 295:593- 605, (1986). [75] R . Knight . T he Va ught Conj ect ure : a count erexample. Techni cal repor t , Oxford University , 2002. [76] E. Kolchin . Differential A lgebra and A lgebraic Groups. Academi c P ress, 1973. [77] T. Kucera and M. P rest o Im aginary modules. J. S ymbolic Logic, 57:698- 723, (1992) . [78] K . Kun en . Set Theory. An introductio n to in dependence proofs. North Holland , Amsterdam , 1983. [79] S. Lang. Algebra. Add ison-Wesley, Reading, 1971. [80] S. Lang. Number Theory Ill: Diophantine Geom etry. Encyclopedia of Mat hem at ical Sciences. Spring er , Berl in , 1991. [81] C. H. Lan gford. Som e theorems on deducib ility . Ann. Mat h., 28:16-40, (1926) . [82] C . H. Langford . T heorems on ded ucibility. Ann. Math., 28:459-471 , (1926). [83] D. Lascar. Ordre de Ru din-K eisler et 'poids dans les t heories w-st ables. Zeits chr. Math. Logik, 28:413- 430, (1982) . [84] D. Lascar . Wh y some people are excited by Va ught 's Conje ct ure. J. S ymbolic Logic, 35:973- 982, (1985) . [85] D. Lascar and B . Poiza t . An intod uct ion to forkin g. J. Sy mbolic Logic, 46:781- 788, (1981). [86] L. Lipschitz and D. Sar acino . T he mod el companion of the t heory of com m utative rings without nilpotent element s. P roc. Amer. Math . Soc., 37:381-387, (1973). [87] L. Lowenh eim . Uber Moglichkeit en in Relat iv Kalkiil. Moth. Ann., 76:447470, (1915). [88] A. Macintyre. Non-standard Frob enius and generic automorphisms . Preprin t . [89] A. Macintyre. On wt-categor ica l t heories of abelia n gro ups . Fund. Mat h. , 70:253-270, (1971) . [90] A. Macintyre. On wt -categorical t heories of fields. Fund. Math., 71:1- 25, (1971).
356
BIBLIOGRAPHY
[91] A . Ma cintyre. On alg ebraicall y closed groups. Ann. Math., 95:53-97 , (1972) . [92] A . Macintyr e. Mod el com plete ness for sheaves of structures. Fund. Math. , 81:73- 89, (1973). [93] A. Ma cintyre. On definable subsets of p-ad ic fields . J. S ym bolic Logic, 4 1:605610, (1976). [94] A . Ma cintyre. Model- compl eteness, pages 139- 180. In Barwise [10], 1977. [95] A . Ma cinty re. Gen eric automorphisms of fields . A nn . P ure A ppl. Logic, 88:165- 180, (1997) . [96] A. Macintyre , ed itor. Connecti ons between Model Th eory and Alg ebraic and A nalytic Geometr y, volu m e 6 of Quaderni di Mat ematica. Dipartimento di Matem at ica II Universita di Napoli, 2000. [97] A . Macin tyre, D. Marker , and L. Van den Dries . The eleme nt ar y theory of restrict ed analyt ic fields with expo nentiation . A nn. Math ., 140:183- 205, (1994) . [98] A. Mac intyre, K. McKenna, and L. Van den Dries . Elimination of quantifiers in algebraic st ruct ures . Adv. Math. , 47:74-87 , (1983) . [99] A. Macinty re and A. Wilkie. On t he decid ability of the real exponential field . In Kreiseliana (P . Odifreddi ed.), pages 441-467. A. K. Peters , Wellesley, 1996. [100] D. Macph erson, D. Marker , and C. Steinhorn. Weakly o-rninimal st ructures and rea l closed fields . Trans. A me r. Math. Soc., 352:5435-5483, (2000). [101] M. Makkai . A survey of basic stability theo ry, with particular emphasis on or thogonalityand regular typ es. Israel J. Math., 49:181- 238, (1984) . [102] A . Malcev . A correspondence between groups an d rin gs. In The metamathem atics of algebraic syst ems , pages 124-137. North Holland , Amsterdam , 1971. [103] J . Mali tz. Int roduction to Math ematical Logic. Unde rgraduate T exts in Math . Springer Verlag, Berlin , 1979. [104] A . Marcja and P . Mangani . Shelah ra nk for Boolean algebras and som e applications to elem ent ary t heories. Alg. Univ ., 10:247- 257, (1980) . [105] A. Marcja and C . Toffalori. On pseud o-No-cat egorical t heo ries. Zeilschr. Math. Logik, 30:533- 540, (1984) . [106] A. Mar cja and C. Toffalori. On t he Cantor-Bendixson Spect ra containing (1,1)-1. In Logic Colloquium '83, pages 331-350, Berlin , 1984. Spri nger . [107] A. Marcja and C. Toffalori . On t he Cant or-Bendixson Sp ect ra containing (l ,l)-II. J. S ym bolic Logic, 50:611-618 , (1985) .
BIBLIOGRAPHY
357
[108] A. Marcja and C. Toffalori . Introdu zion e alta T eoria dei Mod elti, volume 43 of Quad erni dell'Unione Matematica Italiana . Pitagora Editrice, Bologna, 1998. [109] D . Marker . Model theory and exponentiation . Notices Amer . Math . Soc., 43:753-759, (1996) . [110] D . Marker , M . Messmer , and A. Pillay. Model Th eory of fields . Lecture Notes in Logic . Springer, Berlin, 1996. [111] L. May er. Vaught 's conjecture for o-minimal theories. J. Symbolic Logic, 53:146-159, (1988) . [112] K. Meer. A note on a P =F N P result for a restricted class of real machines. J. Complexity, 8:451-453 , (1992). [113] A. Mekler. Stability of nilpotent groups of class 2 and prime exponent . J. Symbolic Logic , 46:781-788 , (1981) . [114] G. Melles. An exposition of Shelah's classification theory and classification by set recursive functions (More for Thomas the doubter) . Preprint. [115] M. Messmer. Groups and fields interpretable in separably closed fields. Trans. Amer. Math . Soc., 344:361-377, (1994). [116] M. Morl ey. On theories categorical in uncountable powers. Proc. Nat. Acad. Se . U.S.A ., 49:213-216 , (1963) . [117] M. Morley. Categoricity in power. Trans . Amer. Math . Soc., 114:514-538 , (1965). [118] M. Morley. Omitting classes of elements, pages 265-273. In Addison et al. [1], 1965. [119] M. Morley . Countable models of 5:65-72, (1967) .
~ l-categorical
theories. Israel J. Math .,
[120] M. Morley. The number of countable models. J. Symbolic Logic, 35:14-18, (1970). [121] P. Odifreddi. Classical recursion theory. North Holland, Amsterdam, 1989. [122] A . Onshuus. 2002.
Thorn-independence in rosy theories. PhD thesis , Berkeley,
[123] Y. Peterzil, A . Pillay, and S. Starchenko. Definably simple groups in minimal structures. Trans. Amer. Math . Soc., 352:4397-4419 , (2000).
0-
[124] Y. Pet erzil and S. Starchenko. A Trichotomy Theorem for o-minirnal structures. Proc. London Moth. Soc., 77:481-253 , (1998). [125] A. Pillay. On groups and fields definable in o-rninimal structures. J . Pure Appl. Algebra , 53:239-255, (1988) .
358
BIBLIOGRAPHY
[126] A. Pillay. Geometric Stability Th eory. Oxford University Press, Oxford, 1996 . [127] A. Pillay. Mod el Theory and Diophantine Geom etry. Bu ll. Amer. Math. Soc., 34:405-422 , (1997) . [128] A. P ill ay. Som e m od el th eory of com pact complex spaces. Contemp. Math ., 270:323-328 , (2000). [129] A. P illay and C. Steinhorn . Definabl e sets in ordered st ructures I. Trans. A m er. Math. Soc., 295:565- 592, (1986) . [130] B . Poizat. Une th eorie de Galois im aginaire. J. S ymbolic Logic, 48:1151- 1170, (1983) . [131] B. Poizat . Cours de Th eorie des Modeles. Nur Al - Mantiq Wal - Ma 'rifah , Villeurbanne, 1985. [132] B . Poizat . Groupes S tables. Nur Al - Mantiq Wa l - Ma 'rifah , Villeurbanne, 1987. [133] B. Poizat . Les peti ts cailloux, volume 3. Nur Al - Man tiq Wal - Ma 'rifah , Aleas , Lyon , 1995. [134] B. Poizat. Cours e in Model Th eor y: An introductio n in Con temporary Mathem atical Logic. Springer Verl ag, 1999. [135] B . Poizat. Stabl e groups . Am erican Mathem ati cal Society , 2001. [136] M. P rest o Model Th eory and Modul es. London Math. Soc. Colloquium Publicat ions. Cambridge Universit y Press, Cambridge, 1988. [137] M. Pr est o Mod el th eory and represent ati on typ e of algebras . In Logic Colloquium '86, pages 219- 260, Am sterd am , 1988. Nort h Holland . [138] M. Rabin . Decidable Theories, pages 595-629. In Barwise [10], 1977. [139] J. P. Ressayre. Int eger parts of real closed exponential fields, pages 278-288. In Clote and Kr aji cek [26], 1993. [140] A. Robinson. On the metamathematics of A lgebra. North Holland , Am st erdam , 1951. [141] A. Robinson . Complete theories. North Holland , Amsterdam , 1956. [142] A. Robinson . On th e concept of differenti all y closed field. Bull. R es. Council Israel, 8F :1l3- 128, (1959) . [143] A. Robin son . Introduction to Model Th eory and to the Metama thema ti cs of A lgebra. North Holl an d , Am sterd am , 1963. [144] H. Rogers. T heory of recursive fun ctions and effe ctive computabilit y. MIT Press, Cambridge, 1988. [145] C. Ry ll-Nardzewski . On the categoricity in power x, No. Bull. Aca d. Pol on. Sciences, 7:545-548, (1959) .
BIBLIOGRAPHY
359
[146] G. E . Sacks. Saturated model theory. W . A . Benjarnin, Reading , 1972 . [147] T . Scanlon . Diophantine Geometry from Model T heory. Bull. Symbolic Logic, 7:37- 57, (2001) . [148] S. Shelah . Uniqueness and chara cte rizat ion of prime models over sets for totally transcend ental first ord er th eory . J. Symbolic Logic, 37:107-113 , (1972) . [149] S. Shelah . Classification theory and the number of non-isomorphic models. North Holl and, Amsterd am , 1978. [150] S. Shelah . Simple unstable theori es. Ann. Math . Logic, 19:177-203 , (1980) . [151] S. Shelah. Classifi cation theory. North Holland, Amsterdam , 1990. [152] S. Shelah, L. Harrington , and M. Makkai . A proof of Vaught 's Conjecture for w-st abl e theories. Israel J. Math. , 49 :259-280 , (1984) . [153] J .R . Sho enfield . Math ematical logic. Addison-Wesley, Read ing , 1967. [154] T . Skolem. Untersuchungen iib er die Axiome des Klassen Kalkiils and iib er Produktations-und Summationsprobleme, welche gewisse Klassen von Aussag en betreffen . Skrifter Vindenskapsakademiet i Kristania, 3:37-71 , (1919). [155] Z. Sokolovic. Model theory of different ial fields . PhD th esis , Notre Dame, 1992 . [156] L. Svenonius. No-categoricity in first ord er predicate calcu lus . Th eoria , 25:8294, (1959). [157] A . Tarsk i. A decision m ethod for elem entary algebra and geometry. University of California Press , Berk eley and Los Ang eles, second edition, 1951. [158] A. Tarski . Contributions to the Theory of Mod els 1. Indag. Math ., 16:572-58 1, (1954) . [159] A . Tarski . Contributions to t he Theory of Mod els 11. Indag. Math., 16:582588 , (1951) .
[160] A. Tarski . Foundations of th e calculus of systems . In Logic, semantics, metamathematics. Papers from 1923 to 1938, pages 342- 383. Clar endon Press, Oxford , 1956. [161] G . Terjanian . Un con tre-exam ple a une conjecture d 'Artin . C. R . Acad. Se. Paris Ser A , 262 :612, (1966) .
La stabilite topologique des applications po lynomiales. [162] R. Thorn. L'Einseignem en t Ma themaiiqu es, 8:21-33 , (1962) . [163] S. Thomas. On the com plexity of th e classification problem for to rsion-free abelia n groups of finit e rank . Bu ll. Sym bolic Logic, 7:329- 344, (2001) . [164] C . Toffalori . Strutture esistenzialme nte complet e per certe classi di an elli. Rend. Sem. Mat. Unio. Padova , 66:51-71, (1981) .
360
BIBLIOGRAPHY
[165] C. Toffalori . On pseud o ~o - categorical structures. In Logic Colloquium '84 , pages 303- 327, Amsterdam, 1986. North Holland. [166] L. van den Dri es . Rem arks on Tarski 's problem con cern ing (R , +, ', e x p) . In Logic Colloquium '82, pages 97-121. Nor th Holland, 1984. [167] L. van den Dries . A genera lization of the Tarki-Seid enb erg Theore m and some nondefinability results . B ull. Amer. Math . So c., 15:189-193, (1986) . [168] L. van den Dries. Alfred Tarski 's elim inat ion theory for real closed fields. J . Symbolic Logi c, 53:7-19 , (1988) . [169] L. van den Dries. Tam e Topology and o-minimal Structures, volume 248 of London Math. Soc . Lecture N ote S eries. Cambridge University Press, Cambridge, 1998. [170] L. van den Dri es. a-minim al St ru ctures and Rea l Analytic Geometry. In Current Developmen ts in Math ematics (B . Ma zur ed.) , pages 105-152. Int . Press, Sommerv ille MA , 1999. [171] L. van den Dries an d C . Miller . On the real exponent ial field with restricted analytic fu nctions . Israel J . Math ., 85:19-56, (1994) . [172] L. van den Dries and K. Schmidt . Boun ds in the polynomial rings over fields . A non standard approach. Inu . Ma th. , 76:77-91 , (1984). [173] B . L. van den Waerden . Modern e Algebra. Springer, Berlin , 1930-31. [174] R . Vaught . Denumerable m odels of complet e theories . In Infi nitistic M ethods, pages 303-321. Pergamon Press, London , 1961. [175] F . Wagner . Simple theories. Kluw er , Dordrecht , 2000. [176] A. Weil. Foundations of algebrai c geom etry, volume 29 of Arn er. Ma th. So c. Colloquium Pubblics. Amer . Math. Soc ., New York , 1946. [177] A . Wilkie. Mod el com plete ness results for expansions of the ordered field of real numbers by rest rict ed Pfaffian functions and the exponenti al function . J . Amer. Math . So c., 9:1051-1094 , (1996) . [178] A. W ilkie. A general theorem of th e com plement and some new o-minimal structures. S electa Math.(N.S.) , 5:397-421, (1999) . [179] C . Wood . The model t heory of differential fields of charact erist ic p Amer. Math . So c., 40:577-584, (1973).
i
O. Proc.
[180] C . Wood. P rime model exte nsions for differential fields of characteristic p J. Symbolic Logi c, 39:469-477 , (1974) .
i o.
[181] M. Ziegler. Mod el theory of modules. Ann. Pure Appl. Logic, 26 :149-213 , (1984) . [182] B . Zilb er . The structure of models of uncountably categorical theories. In ICM- Varsavia 1983, pages 359-368 . North Holland, 1984.
BIBLIOGRAPHY
361
[183] B. Zilber. Model Theory and Algebraic Geometry. In Proceedings 10th Easter Conference, Berlin, 1993.
Index Cherlin 's conject ur e, 303, 310 Ch evalley 's theorem , 59 Church-Turing thesis , 39, 80 class eleme nt ary, 22, 105, 221 of fields, 25, 103 of finite sets, 22 of graphs , 280 of infini te sets , 22 of mo d ules, 27 of nilpote nt groups of class 2, 281 of ordered fields , 26 classifi cation problem, 20, 221-227 , 289 closure algebraic, 133, 172, 287, 328 definable, 133, 172 differential , 209 real, 175 cohe~, 238, 252, 290 com pact ness, 18 theorem of, 18, 243, 325, 327 connecte d com ponent , 189 constructible set , 38, 58, 118, 134, 198, 199, 220, 271, 292, 295 construc t ion , 199 coordinate chart , 299 cylindrical algebra ic decomposition, 80
adiacency relation , 280 algebraic geometry, 291 complex , 37 real , 38, 341 algebra ic numbers com plex, 87 real, 87 algebraica lly ind ep endent set , 170 alg orithm , 39, 80 amalgamation, 231, 234 analysis complex, 345 annihilator , 42 Artin 's conj ect ure , 86, 96-103 Art in 's theorem , 95 atl as , 299 atomi c set , 198 automorphism , 5 Ax 's theorem , 60 Ax-K ochen-Ershov theorem , 100 back-an d-forth property, 10 basis , 169 Baur-Monk theorem , 70, 74 biinterpretability, 279-286 , 288, 290, 339 Boolean space, 136, 180 boundary point, 322
definable manifold , 340 definable sets, 35-42 , 45, 59, 78, 112, 121, 126, 129, 133-136 , 222, 280, 320, 344, 345 Boolean algebra of, 36, 134, 143, 219 conv ex , 346 definably connected , 322
Canto r 's t heorem , 12 Cant or-Bendixson rank , 155, 159 cell, 320 cell decompositi on th eorem , 324, 329 charact er finit e, 228, 233 local , 228, 233
363
364
INDEX
ind ecomposable, 190 dep end ence, 227 depend ence relation, 180, 184, 328 algebraic, 170 linear , 169 derivation , 109, 307 descriptive set th eory , 222, 289 difference degree, 289 differential algebra, 209 differential degree , 287 differentially algebraic, 210 differentially transcendental , 210 dimension, 294-297 of a definable set, 328 of a tuple, 328 of a vectorspace, 169 dimension theory , 327 effect ive pro cedure, 40 , 44 , 79 Ehrenfeucht-Mosto wski mod el, 274, 290 eleme nt ary cha in t heorem , 18, 144 eleme nt ary equivalence, 324, 347 eliminat ion of im agin ari es, 125, 194, 307 uniform , 125, 300 elim inat ion sets, 43 embedding, 4,9-18 , 85, 88, 103 elementary, 13, 85, 103 existe nt ial, 14, 89, 105 endomorphism, 5 exist ence property, 270 expo nent ial set , 342 extension , 5, 228, 234 eleme nt ary, 14 non forking, 237, 238, 240 field w-stable, 220 algebra ic closure of, 33, 86, 93, 103, 117 algebraically closed , 26, 32, 45 , 80- 82, 86, 103,105, 117, 134, 160, 184, 230, 239, 255, 284, 287, 291, 294
elim ination of im aginaries for , 126 mod el com pleteness of, 91 qu an tifier elim inat ion for , 5461 with an automo rphism, 117 com plex elim inat ion of quantifiers for , 82 const ant subfi eld of, 110, 116 difference, 115 existe ntially closed , 117 inversive, 116 differential , 109, 209 existe nt ially closed , 110, 115, 209 differential closure of, 111, 115 differenti ally closed , 106, 109-11 5, 119, 134,211 ,220 ,239 ,242 , 290, 291, 304, 307 axioms for, 111 existe ntially closed , 239 ,290 , 307 with an automo rphism , 291 fixed subfield of, 116 formally real , 95 Henselian , 99 imperfecti on degree of, 114 locall y com pact, 98 of complex numbers, 33 of meromorphic fun cti ons , 110 of ra ti on al fun ct ions , 109 ord ered , 129, 316 , 327 o-minimal ,317 real closure of, 180 p-adic, 86 perfect , 113 pseud ofinite, 26, 102, 118, 288, 290 real , 321 elim ination of quantifiers for , 82 real closed , 43 , 78- 82 , 87, 95,104, 105, 129, 134, 239, 313, 317 elim ination of im aginaries of, 129-131
365
INDEX model completeness of, 93 quantifier elim inat ion for , 6168 theory of, 27 residue, 101, 102 separably closed , 112-115 , 119, 239, 242, 290, 307 structure of, 3 superstable, 220 transcenden ce basis of, 33 transcendence degree of, 33, 86, 184 valued , 99, 100, 102 of p-adi c numbers, 102 field of definition , 194 finite in uniformly, 330 Fi scher-Rabin theorem , 80 forking, 233, 237, 287 formal Laurent ser ies, 98 formul a , 5 positive primitive, 41 atomic , 6 existential, 8, 88 finite, 330 normal form of, 8 quantifier free , 8 T -equivalent , 43 true in a structure, 5, 7 universal , 8, 88 Fr aisse's th eorem, ] 3 Frobenius morphism, 113, 116, 118, 174 function definable, 297-299 elementary, 16, ]35 , 196 function field , 306 generic element , 190 geometry, 286 graph , 280 random , 231 structure of, 3 group pp-definable , 283
w-st abl e, 184-192 , 220, 302, 303, 310 abelian- by-finite , 284 algebraic, 301-304 cent re of, 121 definable, 302, 317 existe nt ially closed, 106, 119 lin ear, 121,301 linear alg ebraic, 302 o-minimal, 315 of finit e Morl ey rank , 303, 310 of finit e type, 305 ord ered abelian , 101 divisible , 313 quotient , 122 sp ecial, 122 structure of, 3 torsionfree abelian, 222, 289 groups elementary class of, 105 Godel Incomplet eness theorem , 40, 280 heir , 238, 252, 290 Hensel's lemma , 98 Herbrand universe , 19 Hilbert 's Basis t heorem , 38, 292 Hilbert 's Nullstellens atz , 82, 86, 93, 119, 292 Hilbert's Seventeent h problem , 86, 95, 119 homomorphism, 4 pure, 151 Hrushovski- Weil theorem , 303, 310, 340 ideal differ ential , 210 prime , 210 prime , 293 radica l, 292 ideal eleme nt , 139 indep endence, 287 independence system , 236 good , 231, 249 ind ep end ent set , 177
366 Ind uct ion Principle, 7, 29 infinite sets theory of , 22 inj ectivity-implies-surj ectivity th eorem , 60 interpret ability, 279 invariance, 228, 233 invariant statement , 70 , 73 invariant system , 225 irr edu cible components , 293 isomorphism , 5 partial , 10 Knight - P illay - St einhorn th eorem, 78 Kolchin constructible, 112 , 134 Kolchin topology, 112 Lagrange's th eorem , 43 , 280 language, 1 Lindstrorri's theorem , 7, 29 linear order expansion of, 313 linear orders , 78 class of, 23 dense, 52-54 , 93 elim inat ion of qu an tifiers for , 52 dense wit hout end points, 24, 32 d~ c ret e , 24, 47-52 , 93 elimination of qu antifiers for , 48 th eory of , 23, 218 linearl y independe nt set, 169 locall y modular , 288 Lowen heim-Skolem theorem , 28, 85, 182, 226, 274, 275 downward , 19, 29 Macintyre's theorem , 192, 284 manifold , 299-302 affine, 299 sem iaffine, 299 Manin-Mumford conj ecture, 305 ,310 model, 8
INDEX A-satu rated , 144 A-universal, 145 homogeneous, 147 minimal , 87 pri me, 87, 133, 196-209 ,216 ,220 , 254, 270, 328 saturated , 133, 143-150 , 180 weakly A-hom ogeneous, 145 model com panion , Ill , 115, 117, 215 module, 239 algebraically com pact, 152 ind ecomposable, 153 pure inj ective, 152 pure inj ect ive hull of, 152 modules, 27, 41 , 290 theory of, 68-76 monotonicity th eorem , 348 Mord ell's conjecture , 304 Mord ell-Lang conj ect ure , 304-310 Morl ey degree, 161, 189, 220, 241 of a type, 165 Morl ey rank , 158-168 , 180, 220, 230 , 241, 288, 294, 298, 307 , 313 , 346 of a ty pe, 165 Morley 's existe nce t heorem , 271 Morl ey 's th eorem , 133, 181,271 ,273279, 290 mor ph ism , 297, 302 n- typ e , 293
com plet e, 137 Neumann's lem m a , 70,72 nilradical, 108 non -for king extension , 252, 259 number field , 304 om itting types th eorem , 157, 198, 217 op en box , 322 open mapping th eorem , 259, 273 ord er property, 237, 243 ordered field , 104, 313 of rea ls, 65, 95 real closur e of, 93 st ructur e of, 3
INDEX
367
orthogonality, 255 p-adic topology, 96 p-b asis , 114 P=NP problem , 80 parameters , 35 partition , 330 polish space, 222 polynomial , 110 difference, 116 differential, 110, 115 sep arable, 113 pp-elimination of quantifiers , pp-formula, 41, 69, 151 pp-type, 152 pr edecessor , 47, 263 presentation , 264 proj ective space, 299 Priifer group, 155 pure injectivity, 150
70~ 76
quantifier elimination , 43-82 , 87, 88, 345 random graph t heory of, 239 rank , 158 real analysis , 341 recursive sets, 39 recursively enumerable set , 40 residue field , 99 Ressayre's Uniqueness theorem , 202,
271
ring commutative, 107 different ial , 109 existe nt ially closed , 106 ordered , 317 reduced , 109 rmgs eleme ntary class of, 105 Robinson 's test , 88-91 Rudin-Keisler relation, 254, 290 Ryll-Nardzewski 's theorem , 217, 220 Schanuel's Conjecture, 343
semialgebraic set , 38, 67, 134 sem idefinite positive, 95 sentence, 5, 7 separant , 211 Shelah's uniqueness theorem , 220, 270273,290 sign change prope rty, 98 small subset of n, 148 smooth equivalence relation , 223 spectrum function , 226 stationarity over models , 236 stationary logic, 290 strong homogeneity th eorem, 147 strongly minimal set , 163, 168-172, 288, 304 structure X-definable, 121 X-interpr etable, 123 w-stable , 185, 220, 291, 308 R an,etcp, 345 Ran , 344 R exp , 341 basis of, 177 definable, 40, 121, 302 dimension of, 177 existent ially closed , 105, 110, 119 expansion of, 5 exte nsion of, 85 interpretable, 123 locally modular, 283 minimal , 77, 168, 176, 179 o-minimal, 78, 178, 179, 313, 318 restriction of, 5 simple, 232 stable, 236 strongly minimal, 168, 256, 282, 287, 292, 308 superstable, 241 trivial , 283 two-sorted , 100 universe of, 2 unstable, 236 structures, 2 elementarily equivalent , 10 subanalytic set, 344
368 globally, 344 subexpon ential set , 342 subgroup definable connecte d, 188 pp-d efinabl e, 41, 69 submodule pure, 151 subst ructure , 5, 85 element ary, 14 existe nt ial, 15 finitely generated , 5 generated, 5 successor , 47, 263 symmet ry, 228, 234 Tarski 's t heorem, 54, 296, 341 Tarski-Seidenb erg th eorem , 38, 67 Tarski-Vaught th eorem , 17, 158 Terj ani an 's counte rexa mple, 100, 102 terms, 6 t heory, 21,22 A-categorical , 28 of vecto rspaces, 34 ACF, 26,45 , 54, 58, 88, 91, 111 ACFA, 117, 118, 131,231,288 ACFo, 33, 57,87 ACF p , 26, 32, 33, 45, 57,77 , 88, 149, 169, 184, 197,21 9, 261 D C F o, Ill , 112, 197, 209-217 , 287 D CFp ,115 dLO ,52 dLO+, 48, 50, 51, 77, 87 DLO- , 24, 32, 52, 53, 160, 174, 181, 182, 217, 218, 226 RC F , 27, 33, 61, 65, 66, 80, 87, 88,9 1, 93, 95, 104, 111, 129, 175, 197, 341 SCFp, 114 T p , 102 Tn, 27 w-stable, 181-184,220 ,230,242261, 270, 346 K. T ' , 169
INDEX n T , 68, 70, 73 Booleanl y A-categorical , 219 categorical, 133, 274 classifiabl e, 225, 227, 261-270 complete , 19, 30, 102 complet ions of, 31, 45 consistent, 21 decidable, 40, 44, 342 deep , 268 depth of, 268 ind epend ence syst em of, 228 model companion of, 105, 117 mod el complete, 34, 46, 85-96, 102, 103, 117, 119, 212, 288, 342, 344, 345 not classifiable, 237 o-minima l, 78-79,178 ,226 ,234 , 313, 344, 345, 348 of a 1-ar y function , 262 of a class of models, 21 of a model, 31 of an equivalence rela tion , 256 of infinite sets , 32, 282 of two equivalence relations, 265 present abl e, 264 rich, 19 rosy, 348 shallow, 268 simp le, 227- 235, 249, 289, 290, 328 st abl e, 235-239 , 243 strongly minimal , 76-77,163 ,168 , 182, 184,220 ,221 ,225 ,227 , 236, 239, 261, 274, 346 sup erstable, 239-242 , 252 totally t ranscendent al, 133, 181184, 346 un stable, 236, 237 weakly o-minimal, 346 t horn-i ndependence, 348 top ological space com pact , 140 Hausdorff, 140 totally disconn ected , 140 t ra nscendence bas is, 170, 295
369
IND EX t ra nscendence degree, 33, 92, 149, 170, 294 transitivity, 228, 234 tree, 264 rank of, 267 well founded , 267 trichotomy t heorem , 341 Turing machine , 39, 79, 80 ty pe, 133, 136-1 43 RK-m inim al , 255 algebraic, 141, 166 complet e, 137 consiste nt , 137 definabl e, 238, 244 dep th of, 268 gen eric, 190, 294 isolated , 141, 156, 198 reali zati on of, 139 regular , 241 stabilizer of, 188 stationary , 240 st rongly regul ar , 256 type of, 138 ultrafilter , 136 uniqueness theorem , 146 un iversal domain , 86 un iversal ity t heorem , 145 valuation map , 99, 101 valuation rin g, 99 variety abelian , 304 algebra ic, 37, 285, 292, 299 irredu cibl e, 293, 294, 298 Vau gh t 's conject ure , 290, 329 Vau ght 's t heorem , 32 vectorspace, 230, 239 st ructure of, 4 theory of quant ifier elim inat ion for , 75 weak homogeneity th eorem , 145 well ordered sets class of, 24
word probl em , 107 Zar iski geome t ries, 285 Zariski st ruct ure, 286 Zari ski to pology, 38, 117, 292, 296, 297, 302 Ziegler sp ect ru m , 154 Zilber 's conject ur e, 279-286 ,289 ,309 , 340 Zilber 's Indecomposability theorem , 190, 309 Zorn 's lemma, 94
TRENDS IN LOGIC 1.
G. Schurz: The Is-Ought Problem. An Investigation in Philosophical Logic . 1997 ISBN 0-7923-4410-3
2.
E. Ejerhed and S. Lindstrom (eds.): Logic, Action and Cognition . Essays in Philosophical Logic. 1997 ISBN 0-7923-4560-6
3.
H. Wansing: Displaying Modal Logic. 1998
ISBN 0-7923-5205-X
4.
P. Hajek: Metamathematics of Fuzzy Logic . 1998
ISBN 0-7923-5238-6
5.
HJ. Ohlbach and U. Reyle (eds.): Logic, Language and Reasoning. Essays in Honour of Dov Gabbay. 1999 ISBN 0-7923-5687-X
6.
K. Dosen: Cut Elimination in Categories. 2000
7.
R.L.O. Cignoli, LM.L. D'Ottaviano and D. Mundici: Algebraic Foundations ofmanyvalued Reasoning. 2000 ISBN 0-7923-6009-5
8.
E.P. Klement, R. Mesiar and E. Pap: Triangular Norms . 2000
ISBN 0-7923-5720-5
ISBN 0-7923-6416-3 9.
Y.E Hendricks : The Convergence of Scientific Knowledge. A View From the Limit. 2001 ISBN 0-7923-6929-7
10.
J. Czelakowski: Protoalgebraic Logics. 2001
11.
G. Gerla: Fuzzy Logic. Mathematical Tools for Approximate Reasoning. 2001 ISBN 0-7923-6941-6
12.
M. Fitting : Types, Tableaus, and Godel's God. 2002
ISBN 1-4020-0604-7
13.
E Paoli: Substructural Logics: A Primer. 2002
ISBN 1-4020-0605-5
14.
S. Ghilardi and M. Zawadowki: Sheaves , Games, and Model Completions. A Categorical Approach to Nonclassical Propositional Logics. 2002 ISBN 1-4020-0660-8
15.
G. Coletti and R. Scozzafava: Probabilistic Logic in a Coherent Setting. 2002 ISBN 1-4020-0917-8; Pb: 1-4020-0970-4
16.
P. Kawalec: Structural Reliabilism. Inductive Logic as a Theory of Justification. 2002 ISBN 1-4020-1013-3
17.
B. Lowe, W. Malzkorn and T. Rasch (eds.): Foundations of the Formal Scien ces II. Applications of Mathematical Logic in Philosophy and Linguistics, Papers of a conference held in Bonn, November 10-13,2000.2003
ISBN 0-7923-6940-8
ISBN 1-4020-1154-7
18.
R.J.G.B. de Queiroz (cd.): Logic for Concurrency and Synchronisation. 2003 ISBN 1-4020-1270-5
19.
A. Marcja and C. Toffalori: A Guide to Classical and Modern Model Theory. 2003 ISBN 1-4020-1330-2; Pb 1-4020-1331-0
KLUWER ACADEMIC PUBLISHERS - DORDRECHT / BOSTON / LONDON