STABLE AMALGAMATION

John T. Baldwin Department of Mathematics, Statistics and Computer Science University of Illinois at Chicago

January 5, 2000

Dedicated to the memory of A.I.Malcev.

In 1968, Grzegorczyk asked whether there were continuum many different ℵ_{0}-categorical theories. Within two years, three different positive solutions of this problem had appeared [16, 15, 14]. Henson’s clear exposition described the result as describing a family of continuum many distinct amalgamation classes of graphs –each of which had a countable, ℵ_{0}-categorical countable model. It was soon noticed that theories constructed in this way were inherently unstable; indeed they had the independence property.

In [21], Hrushovski discovered how to modify the amalgamation property through the use of a dimension function so as to create ‘exotic strongly minimal sets’; a short time later he modified the construction to obtain ℵ_{0}-categorical stable theories. In general, Hrushovski’s technique provides a way to form ‘stable amalgamations’ (a precise definition is in [8].) In this lecture, we review the many variants that have arisen on this construction and discuss its connection with random graph theory and the Cherlin-Zilber conjecture.

1 GENERIC STRUCTURES

L is a first order language possibly with function symbols. \overline{K}_{0} is the class of models of a universal theory T. K_{0} is the finitely generated members of \overline{K}_{0}. δ is a function from (quantifier free diagrams of) finite subsets of elements of \overline{K}_{0} into the real numbers. We will usually consider δ as applied to some realization A of the diagram. We write AB for the structure whose universe is (generated by) the union of A and B. We denote finite sequences of elements by, e.g. a and often interchange A and a where a is an enumeration of a finite set A. The axioms of \overline{K}_{0} forbid any structure containing a sequence a with δ(a) < 0. Usually, it will be possible to construe δ as having the form:

δ_{α}(A) = d_{1}(A) − αd_{2}(A)

where d_{1} and d_{2} are ‘dimension functions’ in a sense that we will leave informal for this article. In most specific applications, the α is fixed and so we often drop the subscript.

Define relative dimension δ(B/A) = δ(AB) − δ(A). We write A ≤ B, and say A is a strong substructure of B if

δ(b/a ∩ b) ≥ 0

for all a ∈ A, b ∈ B.

Fact 1.1 If K_{0} has amalgamation for strong substructures there is a generic (or ≤- homogeneous-universal) model.

In these contexts, the generic structure is always (first-order) homogeneous; it frequently is neither prime nor saturated. We discuss the many variants on the ‘Hrushovski construction in terms of two major dividing lines.

• ab initio versus expansion

• rational valued versus real valued

Even after both of these choices are made, the choice of the class K_{0} of the finite (dimensional) models is crucial. For example, in the rational-valued expansion case this choice distinguishes between structures of finite rank, those which are ω-stable of infinite rank, and some which are not even ω-stable [6]. And even when α is chosen as one, the choice of K_{0} can introduce such unpleasantness as non-saturated generics [1].

In the ab initio case we fix a class K of finite graphs and set

δ_{α}(B) = |B| − αe(B)

where e(B) is the number of edges of the graph. (The work extends by complication of notation to arbitrary finite relational languages. However, the requirement that the basic relations are ‘symmetric’ is an essential ingredient [9].) In the expansion case, the aim is to amalgamate expansions of models of a given well-behaved theory so as to obtain a new theory which is still well-behaved (e.g. rank 2) but has some new property (e.g. a field with an infinite definable subset). Again, a dimension function δ is central to the construction; now it arises from combining natural dimension(s) defined in one or more underlying theories.

Hrushovski initiated these two cases in [21] and [20]. The original constructions were rather dissimilar; the first focused on a class of models; the second was described dually in term of a theory. Holland [18] provided a common framework for describing the two cases.

In both cases δ can be seen as combining two dimensions (in the ab initio case one of the dimensions is cardinality, the second is the number of edges in the graph.) The second major dichotomy depends on whether the combination between the two is obtained with rational coefficients (whether the α above is rational). If the intent is to construct an ω-stable theory, the coefficients are chosen rational ([21, 20, 18, 23, 6, 12]. If the intent is to construct a strictly stable theory, the coefficients are chosen irrational ([9, 17, 11, 3]. When α is one, then a pregeometry is naturally associated to each structure (see [18] for the most general account); however such a global geometry does not exist when α is a different rational (i.e. 1/2) [5, 6].

We describe now a framework designed for the construction of a rank 2 field and, we hope, eventually a ‘bad’ field. It will be necessary to make monotonicity true at least on a definable set of tuples.

1. If Diag(\overline{a}) = Diag(\overline{b}) then δ(\overline{a}) = δ(\overline{b}).

2. (monotonicity) δ(\overline{a}/\overline{b}) ≥ δ(\overline{a}/\overline{b}\overline{c}) whenever \overline{c} ∩ \overline{a} = \overline{c} ∩ \overline{b}, or rather when the last equality holds for appropriate substructures generated by the finite sequences.

In order to carry out the construction in the expansion framework certain ‘definability conditions’ are required on δ which are automatic and thus invisible in the ab initio context. Before laying out these conditions we rehearse the more straightforward situation.

2 Ab Initio Case

In the ab initio case we fix a class K of finite graphs and as explained above set δ(B) = δ_{α}(B) = |B| − αe(B).

Let A and B be finite graphs and suppose A ⊆ B. Now δ(B/A) can be positive, 0, or negative. The crucial insight is that if δ(B/A) > 0 there will be many copies of B over A (in a generic model). If δ(B/A) < 0 there will be only finitely many copies of B over A (in a generic model). If δ(B/A) = 0 the number of copies of B over A (in a generic model) must be controlled if the rank is to be made finite.

2.1 Ab Initio: Rational α

We list a few of the theories constructed in this situation.

Theorem 2.1 (Hrushovski) There is a strongly minimal set whose geometry is not locally modular which is not biinterpretable with a field.

By similar methods, replacing α = 1 by α = 1/2, I obtained:

Theorem 2.2 (Baldwin) There is an almost strongly minimal nonDesarguesian projective plane.

Question 2.3 Are the strongly minimal sets constructed in these two examples ‘really different’?

This question has remained open since I first posed it in [2]. These methods have been extended:

Theorem 2.4 (Debonis-Nesin, Tent) There is an almost strongly minimal generalized n-gon which does not interpret a group

For odd n, this was shown by Debonis-Nesin [22], generalizing my argument [5]; Tent[25] proved the result for all n using the same general method but making a surprising innovation by switching to bipartite graphs instead of using Hrushovski’s trick of interpreting an arbitrary graph without 4-cycles as an (extemely symmetric) plane.

These constructions can be viewed as taking place in two steps.

A) Construct an ω-stable structure of infinite rank.

B) Collapse the rank to finite.

This analysis was suggested by Poizat. It is a convenient way to parse the problem but in fact the argument for the second case has in every case been a direct construction of a new theory – not a derivative from the infinite rank case.

The key technical step to control the situation is to obtain a ‘ uniform amalgamation’, i.e. to obtain: ‘quantifier separation’. This condition implies the generic is saturated, which makes stability and rank computations straightforward. The uniformity of the amalgamation is virtually automatic in the infinite rank case but not in finite rank. We make these concepts precise below.

To construct finite rank examples we need some notation. The structure B is primitive over A if it is minimal strong over A with δ(B/A) = 0. Fix a function μ taking pairs B/A, where B is primitive over A, to integers.

Let A, B be finite substructures of M ∈ \overline{K}_{0} with A ⊆ B then χ_{M}(B/A) is the number of distinct copies of B over A in M.

Let K_{μ} be the finite graphs such that

χ_{M}(B/A) ≤ μ(B/A)

for every primitive pair A, B.

This is a first order class. To show that the generic model is saturated and the theory ω-stable one must show K_{μ} has a uniform amalgamation property (separation of quantifiers, see Definition 3.4); just showing amalgamation will not do.

2.2 Irrational α

Let K_{α} be the class of finite graphs A with δ_{α}(A) hereditarily positive. K′_{α} is a subclass of K_{α} defined by strengthening the lower bound on δ_{α}(A) for A ∈ K′_{α}. The construction of this lower bound is an ingenious number-theoretic argument of Hrushovski; it is expounded well in [17].

Theorem 2.5 (Hrushovski) The theory T′_{α} of the generic structure for K′_{α} is ℵ_{0} categorical and strictly stable.

Theorem 2.6 (Baldwin-Shi) The theory T_{α} of the generic for K_{α} is stable. The theory is not small.

Since the generic is not ω-saturated; stability is much harder than in the ℵ_{0}-categorical case. Surprisingly, this theory is closely connected with almost sure theory of random graphs. Define a measure on the set of (isomorphism types of ) graphs of size n as follows. For any B with n-elements,

P_{n}(B) = n^{−α|e(B)|} · (1 − n^{−α})^{\binom{n}{2}−e(B)}.

Let α be irrational 0 < α < 1. The key observation connecting the model theoretic dimension with the probability theory is: The expected value of embedding B over A into a random graph of size n is n^{δ(B/A)}.

Theorem 2.7 (Spencer-Shelah) T^{α}, the sentences ϕ with lim_{n→∞} P_{n}(ϕ) = 1 is complete.

Theorem 2.8 (Baldwin-Shelah) The almost sure theory T^{α} is the theory T_{α}.

This argument leads us back into the model theoretic realm. The fact that Hrushovski had constructed a family of stable ℵ_{0}- categorical theories paramaterized (continuously) by irrational α led easily to the conclusion that they were not finitely axiomatized. However, we recently obtained a stronger result by relativizing the Spencer-Shelah measure.

Theorem 2.9 (Baldwin) The theory T′_{α} is the almost sure theory for the relativized measure on K′_{α}; thus the Hrushovski ℵ_{0}-categorical stable theory has the finite model property.

Baldwin and Shelah independently [3, 24] have shown that the 0-1 law holds for expansions of successor (for edge probability n^{−α}). Formally, this looks like an ‘expansion’ result but the techniques are more in the ab initio line. In still another direction, these methods apply to the elimination of generalized quantifiers on finite models.

Consider the quantifier (Q_{ram,f}) defined by Q_{f}^{n}xϕ(x, y) which holds in a finite model |A| if there is a homogeneous subset for ϕ of cardinality at least f(|A|).

Theorem 2.10 (Baldwin) If f is unbounded, the logic L_{ω,ω}(Q_{ram,f}) is almost everywhere equivalent to first order logic on graphs with respect to either the uniform distribution or edge probability n^{−α}.

Proof Sketch. The Ramsey quantifier is eliminable from T in the ℵ_{0}-interpretation if T is either ℵ_{0}-categorical or does not have the finite cover property [7]. The almost sure theory T^{α} does not have the finite cover property [10]. The two parts are put together in [4].

3 Expansions

By expansions we mean the line of work extending Hrushovski’s method of fusions. He originally showed any two strongly minimal sets (satisfying certain regularity conditions) had a joint expansion. We discuss here several applications of this method to obtain ωstable theories with specified properties. As mentioned near the end of the last section, what work has been done with α irrational is closer in spirit to the ab initio side; so we concentrate here on rational α. After some general considerations we proceed to expansions of fields.

3.1 Expansions: general rational α

Hrushovski’s fundamental result asserts

Theorem 3.1 (Hrushovski) Any two strongly minimal theories with the definable multiplicity property and elimination of imaginaries have a common extension.

Holland [18] provided a common framework for the ab initio strongly minimal set construction and fusions; she proved the resultant theories were model complete. Holland and I have extended this framework to include expansions of higher rank. The framework has not been widened to include the important result of Baudisch [12].

Theorem 3.2 (Baudisch) There is an almost strongly minimal two step nilpotent group which does not interpret a field.

In order to provide a general framework for constructing ω-stable expansions, we require the following definability constraint on δ. We write ⟨X⟩ for the substructure generated by X.

1. For any integer k and \overline{a}, \overline{b} ⊆ C ∈ K with δ(\overline{a}/\overline{b}) = k, there is a δ-formula for a over b, φ(\overline{x}; \overline{y}) ∈ Diag(\overline{a}; \overline{b}), such that the following hold for any \overline{a}′, \overline{b}′ ⊆ B ∈ K: if B ⊧ φ(\overline{a}′; \overline{b}′), then δ(\overline{a}′/\overline{b}′) ≤ k.

2. For any N ∈ K and \overline{a}, \overline{a′}, \overline{b} ⊆ N, if N ⊧ ϕ(\overline{a}; \overline{b}) ∧ ϕ(\overline{a′}; \overline{b}) and δ(\overline{a}/\overline{b}) = δ(\overline{a′}/\overline{b}) = k and \overline{b}\overline{a} ≤ ⟨\overline{b}\overline{a}⟩, \overline{b}\overline{a′} ≤ ⟨\overline{b}\overline{a′}⟩, then Diag(\overline{b}\overline{a}) = Diag(\overline{b}\overline{a′}).

In particular, under these conditions, ⟨\overline{b}\overline{a}⟩ ≃ ⟨\overline{b}\overline{a}′⟩ via \overline{b}\overline{a} ↦ \overline{b}\overline{a′}.

From these definability conditions, we are able to construct complete δ-formulas such that ϕ(a; m) describes upper bounds (which are achieved by generic solutions) on δ(b/c) for any bc contained in am. This makes it possible to ‘define’ such notions as intrinsic extension.

Definition 3.3 We say a is a minimal intrinsic extension of b if δ(a/b) < 0 but for every a′ properly contained in a, δ(a′/b) ≥ 0,

We denote by I(\overline{y}) the collection of all formulas ∀\overline{x}¬ϕ(\overline{x}; \overline{y}), where for some a and b, a is a minimal intrinsic extension of b and ϕ(x, y) is a complete δ-formula for a over b. Let b ∈ N ∈ \overline{K}_{0} with b ≤ ⟨b⟩ ≤ N and lg(y) = lg(b): I^{∗}(b) is I(\overline{y}) ∪ Diag(b). Note that if \overline{b} ⊆ B, then B ⊧ I(\overline{b}) if and only if \overline{b} ≤ B. These constraints on δ yield easily: If A, B ∈ K and A is an elementary submodel of B, then A ≤ B. If A ⊆ B ∈ K and \overline{b} ⊆ B, then \overline{b} is minimal strong over A if \overline{b} ⊈ A, A ≤ A\overline{b} and for any nonnull, proper subtuple \overline{c} from \overline{b}, A\overline{c} ≰ A\overline{b}.

The following definition isolates the property necessary to make the generic model saturated. The particular notion is from [6]; but Hrushovski had found a similar notion in defining a Robinson theory [19] and we appropriated the name.

Definition 3.4 We say that T has separation of quantifiers if for any

\overline{a} ≤ \overline{a}\overline{b} ≤ ⟨\overline{a}\overline{b}⟩ ∈ K

with \overline{b} minimal strong over ⟨\overline{a}⟩, for each ϕ(x, y) ∈ tp_{qf}(a, b) ∪ I(y),

T ∪ tp_{qf}(a) ∪ I(a) ⊢ (∃y)ϕ(a, y).

Now the following theorem provides a general technique for finding ω-stable expansions.

Theorem 3.5 The generic model M is ω-saturated if and only if T = Th(M) has separation of quantifiers

It is necessary to verify the definability constraints and ‘separation of quantifiers’ in each case.

3.2 Expansions: Rank 2 fields

The Cherlin-Zilber conjecture from the mid 70’s asserts that every simple ω-stable group of finite Morley rank is an algebraic group (over an algebraically closed field). Borovik, Cherlin, Nesin, Tuna [13] and others are attempting to prove the conjecture by providing a classification theory of groups of finite Morley rank in analogy with the one for finite simple groups. A crucial obstacle to this program is the possible existence of a ‘bad field’: an ω-stable field of finite Morley rank with a definable infinite subgroup of its multiplicative group. In fact, [13] an earlier definition of bad field meant any proper finite rank expansion of a field.

Poizat suggested focusing attention on adding a single unary predicate. A bicolored field is a structure in the language L, (+, 0, −, ∗, 1, B) which is an expansion of an algebraically closed field.

The natural choice for δ in this context (see [23] for an argument for the naturality) is: δ(a) is twice the transcendence degree of a minus the number of black points.

For bicolored fields the definability constraints are easy to satisfy: to say δ(a) ≤ k is to say t.d.(a) is at most (k + # black pts)/2.

If K is the class of all structures with non-negative dimension, ordinary amalgamation yields separation of quantifiers. In the case of bicolored fields, using linear disjointness and identifying maximal isomorphic strong substructures it is straightforward to get amalgamation. Thus,

Theorem 3.6 (Poizat)There is a field of rank ω · 2.

However, much more work is necessary to obtain a field of finite rank. Note that in bicolored fields a is primitive over A means all points in a are black and t.d.(a/A) is 1/2 lg(a) and no subset of a satisfies this condition.

A code c is a complete description of a primitive pair a/b. It includes field formulas ϕ_{c}(\overline{x}; \overline{u}) and θ_{c}(\overline{u}) which assert:

1. All the x_{i} are black.

2. Whenever θ_{c}(\overline{b}) holds, ϕ_{c}(\overline{x}; \overline{b}) has Morley degree 1, and δ(\overline{g}/\overline{b}) = k for a generic realization \overline{g} of ϕ_{c}(x; b).

3. If e_{i} for i < some fixed m(c) are independent realizations of ϕ_{c}(x; b) then b is algebraic in the e_{i}.

For any function μ from codes to natural numbers we define K^{μ} to be the members of K_{0} which have less than μ(c) independent realizations over the same canonical parameter of each code c.

Theorem 3.7 (Baldwin-Holland) If μ is finite-one and for each d, μ(d) ≥ m(d) + q(d) then K^{μ} has the separation of quantifiers property.

The requirement that μ be finite to one is not needed in the ab initio case but is required for fusions and the bicolored field case.

Corollary 3.8 (Baldwin-Holland) There is a rank two field.

This answers a question raised by Berline-Lascar in 1986.

Theorem 3.9 (Baldwin-Holland) For a particular μ which is not finite to one, the generic M of K^{μ} is not saturated.

A theory is small if for each n there are only countably many n-types over the empty set. By diagonalizing the previous construction we can show:

Theorem 3.10 (Baldwin-Holland) There exist μ (which are not finite to one) such that the theory T of the generic is not small and thus not ω-stable.

Question 3.11 Must such theories be stable?

3.3 On to bad fields?

A ‘bad field’ is an algebraically closed field k such that

1. There is a distinguished subset H which is a subgroup of the torsion free elements of the multiplicative group of the field.

2. (k, H) has finite Morley rank.

In this section we give some examples to illustrate some of the subtleties that arise in extending the construction of a rank 2 field to construct a bad field. Let [X] denote the algebraically closed field generated by X. For k ⊧ T and X ⊂_{ω} k,

δ(X) = 2 · d_{f}([X]) − d_{vs}([X] ∩ H(k)).

The choice of what subset generated by X is intersected with H in the definition of δ is subtle. Suppose the natural definition from the finite rank field case is carried over without change:

δ(X) = 2 · d_{f}(X) − d_{vs}(X ∩ H(k)).

Let c, cd, cd^{2} be white, d, d^{2} black.

δ(d/cd, cd^{2}) = 2(2) − 1 − (2(2) − 0) = −1;

while

δ(d/cd, cd^{2}, d^{2}) = 2(2) − 1 − (2(2) − 1) = 0.

Using this definition, monotonicity fails.

One cannot naively choose to define the dimension of a by using (as in the rank two field case) the formula defining the annihilating ideal of a. A second example illustrates this difficulty.

Let a_{1}, a_{2}, a_{3}, a_{4}, a_{5} be black points which are generic for the variety defined by the equations:

x_{1} · x_{2} − x_{2} · x_{3} = 2;
x_{4} · x_{5} − x_{2} · x_{3} = 2.

Then δ(a) = 2(3) − 5 = 1.

Now specialize a to b by imposing the equation

x_{2} · x_{3} = 1.

This implies the equations

x_{1} · x_{2} = 1;
x_{4} · x_{5} = 1;

So δ(b) = 2(2) − 2 = 2.

An approach to these problems arises from work of Zilber and Hrushovski.

Let e be a matrix and c a vector. A torus T_{e,c} is the solution of a system of equation

x^{e_{i}} = c_{i}.

For an irreducible variety W, T_{W} is the minimal torus containing W. The following lemma of Zil’ber-Hrushovski (adapted by Baldwin-Holland-Marker) is crucial.

Lemma 3.12 Fix a variety W = W (x, y) defined over \overline{Q}. There is a finite set σ of matrices such that: for any b, and W = W (b) if S ⊂ T_{W} is a torus with

d_{f}(W) − d_{f}(W ∩ S) < d_{f}(T_{W}) − d_{f}(S)  (1)

then for some e ∈ σ and some c,

W ∩ S ⊆ T_{e,c} ⊂ T_{W} .

The sequence a is normal if a ∩ H is a vector space basis for [a] ∩ H.

Lemma 3.13 (Baldwin-Holland) For any normal sequence a, ∈ H, there is a formula ϕ(x) which is a δ-formula for a over ∅.

Many more complications arise in trying to prove specializations of ab can be forbidden to increase δ(a/b). There seems to be considerable work left in giving a full proof of the existence of a bad field even though the general program has been clear for sometime.

References

[1] Roman Aref’ev, J.T. Baldwin, and M. Mazzucco. δ-invariant amalgamation classes. Journal of Symbolic Logic, 199? to appear JSL.

[2] John T. Baldwin. Problems on ‘pathological structures’. In Helmut Wolter Martin Weese, editor, Proceedings of 10th Easter Conference in Model Theory, Wendisches Rietz, April 12-19, (1993), pages 1–9, 1993.

[3] J.T. Baldwin. Random expansions of geometries. submitted.

[4] J.T. Baldwin. Stability, the finite cover property and 0-1 laws. to appear.

[5] J.T. Baldwin. An almost strongly minimal non-desarguesian projective plane. Transactions of the American Mathematical Society, 342:695–711, 1994.

[6] J.T. Baldwin and K. Holland. Constructing ω-stable structures: Rank 2 fields. to appear: JSL, 199x.

[7] J.T Baldwin and David Kueker. Ramsey quantifiers and the finite cover property. Pacific Journal of Mathematics, 90:11–19, 1980.

[8] J.T. Baldwin and S. Shelah. The primal framework: I. Annals of Pure and Applied Logic, 46:235–264, 1990.

[9] J.T. Baldwin and S. Shelah. Randomness and semigenericity. Transactions of the American Mathematical Society, 349:1359–1376, 1997.

[10] J.T. Baldwin and S. Shelah. DOP and FCP in generic structures. Journal of Symbolic Logic, 63:427–439, 1998.

[11] J.T. Baldwin and Niandong Shi. Stable generic structures. Annals of Pure and Applied Logic, 79:1–35, 1996.

[12] A. Baudisch. A new uncountably categorical group. Transactions of the American Mathematical Society, 348:889–940, 1995.

[13] A. Borovik and A. Nesin. Groups of Finite Morley Rank. Oxford University Press, 1994.

[14] A. Ehrenfeucht. There are continuum ω_{0}-categorical theories. Bulletin de l’Acadamie Polonaise des sciences math. , astr., et phys., XX:425–427, 1972.

[15] W. Glassmire. There are 2^{ℵ_{0}} countably categorical theories. Bulletin de l’Acadamie Polonaise des sciences math. , astr., et phys., XIX:185–190, 1971.

[16] W. Henson. Countable homogeneous relational structures and ℵ_{0}-categorical theories. The Journal of Symbolic Logic, 37:494–500, 1972.

[17] B. Herwig. Weight ω in stable theories with few types. J. Symbolic Logic, 60:353– 373, 1995.

[18] Kitty Holland. Model completeness of the new strongly minimal sets. J. Symbolic Logic, 199? to appear.

[19] E. Hrushovski. Simplicity and the Lascar group. preprint.

[20] E. Hrushovski. Strongly minimal expansions of algebraically closed fields. Israel Journal of Mathematics, 79:129–151, 1992.

[21] E. Hrushovski. A new strongly minimal set. Annals of Pure and Applied Logic, 62:147–166, 1993.

[22] A. Nesin M. J. De Bonis. There are 2^{ℵ_{0}} many almost strongly minimal generalized n-gons that do not interpret an infinite group. preprint.

[23] Bruno Poizat. Le carré de l’egalité. to appear JSL, 199?

[24] S. Shelah. Zero-one laws with probability varying with decaying distance. Shelah 467, 199?

[25] Katrin Tent. A note on the model theory of generalized polygons. to appear, 200x.