Forking and Multiplicity in First Order Theories

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

May 13, 2001

The basic concepts of forking and multiplicity were introduced by Shelah around 1970. Two important facts were virtually unnoticed by the model theory community at the time. Although the main focus of Shelah’s work was on stable first order theories, the basic notions of stability were defined with respect to a model not a theory and the basic notions of forking were developed for arbitrary first order theories not just stable theories. In the middle 70’s Lascar and Poizat developed an alternative and apparently simpler approach to forking which was adopted in most textual treatments of the subject including my own. The work of Kim and Pillay [5] showed that this development depended on a conflation of the properties of forking and multiplicity which obscured the theory of forking in the more general case of simple theories; as we’ll see below Shelah’s exposition also obscured this distinction. In these notes, we will expound the basic principles of forking and multiplicity by first establishing results which hold in all first order theories, then restricting to simple theories and finally to stable theories. There is nothing original here other than the organization of the subject, which largely follows my model theory course given in Spring 2001 at UIC. We rely heavily on the exposition for simple theories of Grossberg, Iovino, and Lessmann; indeed Sections 2.1 and 3 are just a scholia on the first two sections of that paper. In the background, is the work of Buechler and Lessmann which put these results in what may turn out to be their proper context: homogeneous models. We feel that for learning purposes, the restriction to the first order context is valuable. The transition to stable theories consists of picking out the appropriate arguments from my book [1], Buechler’s [2] and Shelah’s [9]; recall that mine already synthesised Shelah with Lascar-Poizat. The basic innovations in simple theories occurred in [10, 6, 5].

Our style will be to write definitions and theorems. In most cases, we will only sketch the proofs and refer the reader to exactly where the proof can be found - usually in [1, 3, 9].

∗Partially supported by NSF grant DMS 9803496 and CDRF grant KM2-2246.

We work throughout in a very homogeneous monster model M. We write F (L) for the set of all formulas with no parameters and F (A) for the formulas with parameters from a subset A of M.

1 Historical Remarks

Despite Morley’s monumental proof of the categoricity theorem in the early 60’s; many sources (anecdotally - Morley, Shelah, Hodges etc.) report a feeling in the late 60’s that pure model theory of the Tarski-Vaught-Morley style was moribund. Fortunately for me, such rumors hadn’t reached Vancouver. However, in retrospect, causes for such a malaise are evident. Work in the middle 60’s focussed on two cardinal theorems and these results involved more and more interaction with set theory. Moreover, the interaction was not just with combinatorics (the Erdos-Rado theorem) but with deep independence results connected with Jenson’s fine structure of the constructible universe and the existence of Kurepa trees. It seemed that model theory had fallen into the morass of extensions of ZFC. Surely such endeavors had little connection with the intent of the Robinson school to investigate via model theoretic means ‘real’ mathematics. While Morley’s conjecture that I(λ, T), (the number of models of T of cardinality λ), is (with one obvious exception) a nondecreasing function seemed a difficult but conceptually reasonable question, Shelah’s proposal to solve it by simply calculating all such functions seemed to some to place undue importance on an arcane problem about largish cardinals. It turned out that this calculation can be seen as a precise phrasing for the question, ‘find a structure theory for models of a first order theory’. Two crucial conceptual breakthroughs of Shelah set the stage for solving this question. First, he saw that a ‘syntactic’ classification of first order theories was necessary in order to approach this problem. Thus, he developed the stability hierarchy. An immediate consequence was to break the bondage of model theory to axiomatic set theory: for stable theories, the two cardinal theorems are true in ZFC. While Shelah’s work involved difficult combinatorial techniques, the fear that one could not do model theory without being a set theorist vanished. Second, by introducing the notion of forking, he developed a vast generalization of the Van der Waerden theory of algebraic independence which is the key to ‘structure theory’. The aim of these notes is to outline a more modern exposition of the basic theory of forking.

Although Shelah clearly understood that many properties of forking did not depend on the hypothesis that T is stable (exemplified by the strange practice in Chapter III of [9] of starring those result which do not depend on T being stable (and Δ- finite)), he developed the properties of forking (symmetry, pairs lemma etc.) only after establishing in III.1.2 that every type in a stable theory has multiplicity bounded by 2^{|T |}. This depends on the early proof (I.2.8) that if |J| > λ and T is stable in λ, then T contains a set of indiscernibles of cardinality greater than λ. In contrast, we prove these properties, which don’t hold in arbitrary simple theories, (Corollary 4.14) only after proving the more ‘closure theoretic’ properties of forking in more general settings.

Although Shelah’s efforts in the early 70’s served to weaken the link between model theory and axiomatic set theory, his later work reestablished that link. But, with important additional insight. We now know that the basic properties of the spectrum problem for countable first order theories (e.g. the main gap) can be resolved within ZFC, while more arcane questions such as the number of non-embeddable (as opposed to non-isomorphic) models or questions about infinitary logic may require more set theoretic apparatus.

Many have complained about Shelah’s book. In my view many of the complaints are wrong-headed. The difficulty is not that the proofs are too sketchy or wrong; the difficulty is that the proofs are too detailed and there are too many of them. It is extremely difficult for mortals to find the real themes of the work. Both by predilection and intention, Shelah did not attempt to sort out the most important concepts and the smoothest exposition of the work. Rather he wrote that which he knew. After twenty five years, the merits of this approach are more clear (the demerits were always evident); many techniques for developing the theory in more generality – simple theories or homogeneous models – are still being mined from [9].

Here are some of the distinctive features of the Lascar-Poizat [7] approach to the fundamentals of forking: topological language, the fundamental order, the coheir/heir symmetry, a two stage approach: types over models followed by arbitrary types; forking defined first for types not formulas; emphasis on definability of types rather than indiscernible sequences, and clear discussion of the open mapping theorem. In this paper, we do not consider the fundamental order; otherwise we obtain the principal introductory results which appear in either school and close the survey with the deduction of the open mapping theorem from the finite equivalence relation theorem.

2 Arbitrary theories

Our aim is to develop a formal notion of a ‘good’ extension of a type. For arbitrary theories there are two such notions: nonforking and coheir. In stable theories, these notions coalesce. Informally, the multiplicity of a type is the number of distinct nonforking extensions it possesses.

2.1 Dividing and Forking

Recall that an ordered sequence I in M is indiscernible over a set A if any two finite increasing subsequences of I of the same length have the same type over A.

A type p (possibly in infinitely many variables) is a consistent set of formulas. We write p ∈ S(A) if p is a complete type over a set A; this notation indicates that p has only finitely many free variables.

For k < ω, a set of formulas q(x) is k-contradictory if every subset of q with k elements is inconsistent. Note that if I is an sequence of indiscernibles and the set { ϕ(x, a) | a ∈ I } is inconsistent, then it is k-contradictory for some k < ω.

We begin by introducing the fundamental notion of dividing. The easiest example is that a formula which specifies a class of an equivalence relation divides (with k = 2) over the set where the equivalence relation is defined.

Definition 2.1

1. A formula ϕ(x, b) divides over A if there exists an infinite sequence I and k < ω such that

(a) tp(c/A) = tp(b/A) for every c ∈ I;

(b) The set { ϕ(x, c) | c ∈ I } is k-contradictory.

2. A type p (possibly in infinitely many variables) divides over A if there exists a formula ϕ(x, b) such that p ⊢ ϕ(x, b) and ϕ(x, b) divides over A.

It is immediate from the definition that a type p does not divide over a set A iff every (some) A-automorphic image of p does not divide. Moreover, nondividing is monotonic in following sense.

Remark 2.2 (Monotonicity) Let A ⊆ B and suppose p ∈ S(B) does not divide over A then p does not divide over C for every A ⊆ C ⊆ B.

By compactness and Ramsey’s theorem, we can demand that the infinite set which witnesses ϕ(x, a) divides over A be indiscernible over A and (since they are the same for indiscernible sets) replace k-contradictory by inconsistent.

Lemma 2.3 A formula ϕ(x, b) divides over A if and only if there exist k < ω and an indiscernible sequence over A, ⟨ b_{i} | i < ω ⟩, such that b_{0} = b and { ϕ(x, b_{i}) | i < ω } is inconsistent.

In particular, if tp(a/B) divides over A, this is witnessed by a sequence indiscernible over A. But, more strongly, if we allow ourselves to replace a by an a′ still realizing the same type over A, we can demand that I be indiscernible over Aa′. We record this remark more precisely. From (2) to (1) follows quickly from the definition and the homogeneity. But (1) to (2) is a nontrivial compactness argument.

Lemma 2.4 (Basic Characterization of Dividing) Let A be a set, b be a finite sequence, and a be a (possibly infinite) sequence. The following conditions are equivalent.

1. tp(a/Ab) does not divide over A;

2. For every infinite sequence of indiscernibles I over A with b ∈ I there exists a′ realizing tp(a/Ab) such that I is indiscernible over Aa′.

The homogenity provides a third equivalent: For every infinite sequence of indiscernibles I over A with b ∈ I there exists an Ab-automorphism f such that I is indiscernible over Af(a). This symmetry is a crucial technical’ tool for some of the following arguments. The use of Ramsey’s theorem requires that b be finite in the previous argument. This propogates to the similar requirement on b in the following Lemma. But there is no such requirement on a_{0} and this will be crucial in the proof of Lemma 3.6.

Using Lemma 2.4, it is easy to obtain the following sufficient condition for a pair of sequences not to fork in terms of the properties of each component. Buechler dubbed this result ‘the pairs lemma’.

Lemma 2.5 (Pairs) If b is a finite sequence, tp(a_{0}/Ab) does not divide over A, and tp(a_{1}/Aba_{0}) does not divide over Aa_{0}, then tp(a_{0}a_{1}/Ab) does not divide over A.

Notation 2.6 Fix a sequence ⟨e_{i} : i ∈ I⟩. We write E_{i} for (the union of) ⟨e_{j} : j < i⟩. The sequence is coherent if i < j implies tp(e_{j}/E_{i}) = tp(e_{i}/E_{i}).

Morley [8] showed that one could construct indiscernible sequences by building coherent sequences which did not decline in rank or degree; Shelah embellished this construction by replacing constant rank with non-forking or even non-splitting. In time, the motivation and the method were reversed leading to the following definition, where the indiscernibility is a requirement not a conclusion. In order to conclude indiscernibility from the first two conditions, the type p needs to have multiplicity one; we are now developing the theory in a context where that restriction may not be possible. We define a Morley sequence in term of non-dividing instead of non-forking; this is a useful technical device which I believe is due to Buechler and Lessmann.

Definition 2.7 Let A ⊆ B and p be a type over B. Let (X, <_{X}) be an infinite linearly ordered set. Then, ⟨ a_{i} | i ∈ X ⟩ is a Morley sequence for p over A if

1. ⟨a_{i} : i ∈ X⟩ is a coherent sequence of realizations of p

2. For every i ∈ X the type tp(a_{i}/BA_{i}) does not divide over A;

3. ⟨ a_{i} | i ∈ X ⟩ is sequence of indiscernibles over B.

When A = B we say that the sequence is a Morley sequence for p.

Note that any subsequence of a Morley sequence is a Morley sequence (for the same type and set) and if ⟨a_{i}b_{i} | i ∈ X⟩ is a Morley sequence for tp(ab/B) over A, then ⟨a_{i} | i ∈ X⟩ is a Morley sequence for tp(a/B) over A and ⟨b_{i} | i ∈ X⟩ is a Morley sequence for tp(b/B) over A.

Let X be an infinite linear order. For Y, Z ⊆ X, we write Y < Z if each element of Y is less than all elements of Z. If ⟨a_{i} | i ∈ X⟩ is sequence indexed by X and Y ⊆ X, we write a_{Y} for ⟨a_{i} | i ∈ Y ⟩. Now, by induction using the pairs lemma we easily have.

Lemma 2.8 Let A ⊆ B and p ∈ S(B) be given. If ⟨a_{i} | i ∈ X⟩ is a Morley sequence for p over A, then for any Y, Z ⊆ X such that Y < Z, the type tp(a_{Z}/B ∪ a_{Y}) does not divide over A.

We can also establish the following technical lemma; [3] include the proof as part of the proof of Kim’s characterization of dividing in simple theories – but simplicity is not needed. The proof follows by use of Lemma 2.4.

Lemma 2.9 Let I = ⟨b_{i} | i ∈ X⟩ be a sequence of realizations of tp(b/A) such that tp(b_{i}/AB_{i}) does not divide over A. For each Y ⊆ X and each i ∈ X such that {i} < Y, the formula ϕ(x, b_{i}) divides over A ∪ ⋃_{j∈Y} b_{j}.

In various contexts we want to extend a type p which has a certain good property over a set A to a complete type which is also good. If the property of being ‘bad’ a) depends on individual formulas and b) the class of ‘bad’ formulas is closed under finite disjunction, this extension is easy to arrange. We can let

Γ := { ¬ψ(x, b) | b ∈ B, ψ(x, b) is bad over A }.

and show that p∪Γ is consistent by compactness. This closure under disjunction is obtained in different ways; here we do it by fiat.

Definition 2.10

1. A formula ϕ(x, b) forks over A if there exist n < ω and {ϕ_{i}(x, b^{i}) | i < n}, such that

(a) ϕ_{i}(x, b^{i}) divides over A for every i < n;

(b) ϕ(x, b) ⊢ ⋁_{i<n} ϕ_{i}(x, b^{i}).

2. A type p forks over A if there exists a formula ϕ(x, b) such that p ⊢ ϕ(x, b) and ϕ(x, b) forks over A.

The definition has some immediate consequences. Clearly, if ϕ(x, b) divides over A, then ϕ(x, b) forks over A. If ϕ(x, b) ⊢ ⋁_{i<n} ϕ_{i}(x, b^{i}), and ϕ_{i}(x, b^{i}) forks over A for every i < n, then ϕ(x, b) forks over A. By definition, forking has strong finite character in the sense that if tp(a/B) forks over A, then there exists ϕ(x, b) ∈ p which forces tp(a/b) (not just tp(a/Ab) to fork over A. Finally, if \overline{a} ∈ acl(A) ⊆ B then tp(a/B) does not fork over A. If p is a type over A then clearly p does not divide over A.

A formula can fork over A even when it is over A. Let A be ∅ and let T be the theory of circular order (R(x, y, z) is the relation on the circle which holds if y is on the shorter arc between x and z.) Now, R(a, x, b) divides over the empty set and x = x forks since x = x ⊢ ∨_{i<3}R(a_{i}, x, b_{i}) for appropriate a_{i}, b_{i}. (Note that Example V.3.12 which supposedly illustrated this phenomena is incorrect.) We will see that this anomaly disappears for simple theories. The technique that motivated our definition of forking easily yields:

Theorem 2.11 (Extension) If p does not fork over A and dom(p) ⊆ B, then there exists q ∈ S(B) extending p such that q does not fork over A.

Notation 2.12 For any linearly ordered set X ⊆ M we write D(X) (diagram) for the set of types of finitely properly ordered sequences from X.

Now an application of the Erdos-Rado theorem originally due to Morley shows:

Lemma 2.13 If (X, <) is a sufficiently long linearly ordered subset of M there is a countable set Y of indiscernibles (and hence one of arbitrary order type) such that D(Y) ⊆ D(X).

With this result it is easy to construct a Morley sequence in p ∈ S(B) over A if p does not fork over A. First, repeatedly apply the extension axiom to build a coherent sequence such that for each i, tp(e_{i+1}/BE_{i}) does not fork over A. This sequence can be built as long as you like; so Lemma 2.13 can be applied to find an indiscernible sequence with the same diagram. The finite character of forking guarantees the result in a Morley sequence. In sum,

Theorem 2.14 Let A ⊆ B. Suppose that p ∈ S(B) does not fork over A. Then for every linearly ordered set (X, <_{X}) there exists a Morley sequence ⟨b_{i} | i ∈ X⟩ in p over A.

2.2 Coheirs

Another method of generating indiscernibles also generalizes Morley’s technique. This method uses the notion of coheir. (This notion can also be phrased in terms of semidefinability: the average over an ultrafilter, [9] VII.4.)

Definition 2.15 Let M ⊧ T and M ⊆ A, p ∈ S(A) is a coheir of p|M if every formula ϕ(x, a) ∈ p is satisfied in M.

Let M ≺ N, p ∈ S(M) and X be the topological closure of the types in S(N) which are realized in M. Then X along with the clopen subsets of S(N) given by finite subsets of p is a family of closed subsets of S(N) which has the finite intersection property. A common solution of this family verifies the following result (without loss of generality, extend the A to an N which is an elementary extension of M:

Lemma 2.16 For any M any p ∈ S(M) and any structure A ⊇ M, p has a coheir on A.

Definition 2.17 Let B ⊆ A: p ∈ S(A) does not split over B if for any formula ϕ(x, y) and any a, b ∈ A which realize the same type over B, ϕ(x, a) ∈ p if and only if ϕ(x, b) ∈ p.

It is easy to see that a type (in an arbitrary theory) may have more than one coheir (let p be the type of an irrational cut in a dense linear order). Clearly, coheirs do not split so if p ∈ S(M) and M ⊆ A, p has at most 2^{|M|} coheirs over A – for any A and with no restriction on the theory of M. Now it easy to check the following lemma from the definitions.

Lemma 2.18 Let M be a model of an arbitrary theory T, M ⊆ B and p ∈ S(B) the coheir of p|M.

1. p does not divide over M.

2. If E = ⟨e_{i} : i ∈ I⟩ contained in MB is a coherent sequence such that tp(e_{i}/ME_{i}) is p|ME_{i}, then E is a sequence of order indiscernibles. We call E a coheir sequence in p.

3 Forking in Simple Theories

We note in this section that surprising ‘local’ properties of forking - e.g. symmetry, follow from assuming that forking has local character -that the theory is simple.

Definition 3.1

1. A complete first order theory T is simple if for some κ and each type p over a domain A there is an A_{0} ⊆ A such that p does not fork over A_{0} and |A_{0}| < κ.

2. \overline{κ}(T) is the least cardinal κ such that each finite type p over a domain A there is an A_{0} ⊆ A such that p does not fork over A_{0} and |A_{0}| < κ.

3. κ(T) is the least cardinal κ such that each finite type p over a domain A and each increasing sequence ⟨A_{i} : i < κ⟩ of subsets of A, for some i, p does not fork over A_{i}.

It is immediate that \overline{κ}(T) ≤ κ(T). Moreover, it easy to see that every regular cardinal less than κ(T) is less than \overline{κ}(T). So, if \overline{κ}(T) is regular, they are equal. It follows from Theorem 4.10 that they are equal for countable T.

Monotonicity easily yields that if T is simple then no type forks over its domain. Whence we have:

Lemma 3.2 Let T be simple. Then for every A and every p over A there is a Morley sequence in p over A.

Kim’s great discovery [6] is that while different indiscernible sequences in the type of b over A may give different answers to the question, ‘is the set of instances of ϕ(x, b) indexed by this set k-contradictory’; any two Morley sequences give the same answer. We sketch a proof due to Buechler and Lessmann.

Theorem 3.3 (Kim’s Characterization of Dividing in Simple Theories) Let T be simple. The following conditions are equivalent:

1. The formula ϕ(x, b) divides over A;

2. For every Morley sequence ⟨ b_{i} | i ∈ X ⟩ for tp(b/A), the set { ϕ(x, b_{i}) | i ∈ X } is inconsistent;

3. For some Morley sequence ⟨ b_{i} | i ∈ X ⟩ for tp(b/A), the set { ϕ(x, b_{i}) | i ∈ X } is inconsistent.

We sketch the proof. (3) ⇒ (1) is obvious and (2) ⇒ (3) is given by Corollary 3.2. To prove (1) ⇒ (2), choose a Morley sequence J for tp(b/A) with order type the inverse of κ(T)^{+} and suppose for contradiction that there is a d satisfying ϕ(d, c) for each c ∈ J. By simplicity tp(d/AJ) does not fork over AJ_{0} for some J_{0} ⊆ J with |J_{0}| < κ(T). Then there is a c′ ∈ J with {c′} < J_{0}. By Lemma 2.9 and (1), ϕ(x, c′) divides over AJ_{0}. This is a contradiction.

Since non-dividing can be checked on an arbitrary Morley sequence it is easy to deduce that dividing is symmetric and that forking and dividing are equivalent.

Theorem 3.4 (Symmetry) Let T be simple. Then tp(a/Ab) divides over A if and only if tp(b/Aa) divides over A.

If p = tp(b/Aa) does not divide over A choose a Morley sequence J in p over Aa. By indiscernibility over Aa, for any ϕ(x, y), ϕ(a, b) implies ϕ(a, c) for all c ∈ J. But, trivially, J is also a Morley sequence over A and by Theorem 3.3 we see tp(a/Ab) does not divide over A.

Theorem 3.5 Let T be simple. Then, ϕ(x, b) divides over A if and only if ϕ(x, b) forks over A.

We sketch the proof. Suppose ϕ(x, b) → ⋁_{j<n} ψ_{j}(x, c_{j}) and each ψ_{j}(x, c_{j}) divides over A. If for an infinite sequence J = ⟨b_{i} : i ∈ I⟩, the ϕ(x, b_{i}) for i ∈ I have a common solution d and for each i, ϕ(x, b_{i}) → ⋁_{j<n} ψ_{j}(x, c_{j}^{i}) then the pigeon hole principle yields that for an infinite subset I_{0} ⊆ I and fixed j < n, ϕ(d, c_{j}^{i}) for all i ∈ I_{0}. If J is merely indiscernible this proves nothing. But taking J as a Morley sequence, the associated J_{0} is also a Morley sequence and by Theorem 3.3 this implies ϕ(x, c_{j}^{i}) does not divide over A.

The last two results give symmetry for forking: Let T be simple. Then tp(a/Ab) forks over A if and only if tp(b/Aa) forks over A.

A purely abstract calculation shows that the pairs lemma plus symmetry implies transitivity of nonforking in the sense of Theorem 3.6. The argument is abstract but it must take into account the cardinality restrictions in Lemma 2.5. (Such an abstract argument for transitivity plus symmetry gives pairs appears in [1] II.2.5.)

Theorem 3.6 (Transitivity) Let T be simple and A ⊆ B ⊆ C. If tp(a/C) does not fork over B and tp(a/B) does not fork over A, then tp(a/C) does not fork over A.

As we see in the next section, in a stable theory types over models have a unique nonforking extension (to any larger domain). The independence theorem, foreshadowed by Hrushovski-Pillay [4] and proved by Kim-Pillay [5] is a weakening which holds in simple theories: Nonforking extensions to independent domains have a common nonforking solution. These notions correspond to the initial steps in Shelah’s hierarchy of amalgamation properties [11]. Before establishing the independence theorem we need to refine when types do not divide.

Let p(x, b) be a type over Ab which does not divide over A and let I = ⟨b_{i} | i < ω⟩ be a sequence of indiscernibles over A with b = b_{0}. We showed (Lemma 2.4) that with no hypothesis on the theory there exists a realizing p(x, b) such that ⟨b_{i} | i < ω⟩ is Aaindiscernible. Assuming simplicity we want to improve the result to tp(a/A ∪ {b_{i} | i < ω}) does not fork over A. A basic strategy is clear. If tp(a/A ∪ {b_{i} | i < ω}) divides over A, tp(a/A∪{b_{i} | i < n}) divides over A for some n. But the sequence {b_{in} … b_{(i+1)n−1} | i < ω}) is also a sequence of indiscernibles over Aa and it witnesses that no formula ϕ(x, b_{0}, … b_{n−1}) can be k-contradictory. If I is a Morley sequence, so is I’ and we finish by Theorem 3.3. Extending the result to an arbitrary sequence of indiscernibles I, requires a significant application of ‘forking calculus’; see [3] for the proof.

Lemma 3.7 Let T be simple. Let p(x, b) be a type over Ab which does not fork over A. Let ⟨b_{i} | i < ω⟩ be a sequence of indiscernibles over A with b = b_{0}. Then there exists a realizing p(x, b) such that ⟨b_{i} | i < ω⟩ is Aa-indiscernible and tp(a/A ∪ {b_{i} | i < ω}) does not fork over A.

Stable theories satisfy a much stronger condition: If I is a sequence of indiscernibles over A and tp(a/AI) does not fork over A then I is indiscernible over Aa (Corollary 5.8). This is false for an arbitrary simple theory. E.g, if I is an infinite set in a random graph, then tp(a/I) does not fork over ∅ for any a ∉ I.

Theorem 3.8 (The Independence Theorem) Let T be simple and M be a model of T. Let a and b be finite sequences such that tp(a/Mb) does not fork over M. Let p(x) ∈ S(M). Let q(x, a) be a nonforking extension of p over Ma and r(x, b) be a nonforking extension of p over Mb. Then q ∪ r is a consistent, nonforking extension of p over Mab.

Again we sketch the proof. Applying the forking calculus one can find a b′ ≡_{M} b such that q(x, a)∪r(x, b′) is a nonforking extension of p. Assume for contradiction that q(x, a)∪r(x, b) forks over M (perhaps is even inconsistent). Construct by Lemma 2.18 infinite indiscernible sequences I_{1} = ⟨b_{i} : i < ω⟩, I_{2} = ⟨b′_{i} : i < ω⟩ over M which are each a coheir sequence in tp(b/M). Applying Lemma 2.18 choose a coheir sequence J in tp(b/M) over MI_{1}I_{2} so that both I_{1}J and I_{2}J are indiscernible sequences over M. Suppose for example q(x, a) ∪ r(x, c) forks over M. Choose a_{n} for n < ω so that for each n < ω,

tp(c_{0}c_{1} … c_{n−1}a_{n}c_{n}c_{n+1} … /M) = tp(b′_{0}b′_{1} … b′_{n−1}ac_{n}c_{n+1} … /M).

It follows that q(x, a_{i}) ∪ r(x, c_{j}) forks over M iff i < j. Now by Ramsey’s theorem and compactness we may assume K = ⟨a_{i}c_{i} : i < n⟩ is a sequence of indiscernibles. Since, q(x, a) ∪ r(x, b′), applying Lemma 3.7 we can choose a d such that q(d, a_{0}) ∪ r(d, c_{0}) and such that tp(d/MK) does not fork over M and K is indiscernible over Md. But then we also have q(d, a_{0}) ∪ r(d, c_{1}) so tp(d/Ma_{0}c_{1}) forks over M. This contradiction yields the theorem.

4 Stable Theories

We fix on one of the many equivalent definitions of stable theories and show how it gives rise to a distinguished extension (definable, heir, coheir) of a type over a model. We show that every stable theory is simple and then apply the Independence theorem to show that this distinguished extension is exactly a non-forking extension.

Recall that for a finite subset Δ of formulas ϕ(x; y) in L(T), a Δ-type over A is a consistent set of formulas of the form ϕ(x, a) or ¬ϕ(x; a) with the a from A. (Strictly speaking we should speak of a Δ-m-type where m is the length of x. The m will be fixed in each context we consider so we suppress it.) A simple coding trick shows that we may consider Δ as {ϕ}. See [1] III.1, [9] or any other text with an introduction to stability theory to fill in details of the results here.

Definition 4.1 T is stable if for every infinite A and finite Δ, |S_{Δ}(A)| ≤ |A|.

By regarding each L-type as product over finite Δ of Δ-types we see immediately.

Lemma 4.2 A theory T is stable if and only if for every λ with λ^{|T |} = λ, if |A| = λ, |S(A)| = λ.

Definition 4.3 The formula ϕ(x, y) has the order property in T if there exist infinite sequences a_{i}, b_{i} for i < ω such that:

ϕ(a_{i}, b_{j}) iff i < j.

T has the order property if some formula does.

A trivial application of compactness shows that if T has the order property, T is not stable; the converse is true but requires serious combinatorial argument [9].

We say two Δ-types are explicitly contradictory if for some ϕ(x, y) ∈ Δ and some a, ϕ(x, a) is in one and ¬ϕ(x, a) is in the other.

Definition 4.4 Let p be a type and Δ a set of formulas. For λ a cardinal less than or equal to ℵ_{0},

1. R(p, Δ, λ) ≥ −1 if p is consistent.

2. R(p, Δ, λ) ≥ γ for limit γ if R(p, Δ, λ) ≥ β for each β < γ.

3. R(p, Δ, λ) ≥ γ + 1 if for every finite q ⊆ p there exist Δ-types q_{i} for i < λ such that

(a) the q_{i} are pairwise explicitly contradictory

(b) and for each i,

R(q ∪ q_{i}, Δ, λ) ≥ γ.

4. R(p, Δ, λ) = γ if R(p, Δ, λ) ≥ γ and R(p, Δ, λ) ≱ γ + 1.

By induction on rank, it is easy to check that each type has a finite subtype of the same rank (for any λ, Δ). Trivially, for any p, R(p, Δ, ℵ_{0}) ≤ R(p, Δ, 2). With only slightly more difficulty, this notion of rank can be developed for other infinite λ. We consider λ as either 2 or ℵ_{0} because we use certain properties that are easy for each rank: boundedness and definability is easy with 2-rank, extension in rank is easy with ℵ_{0}-rank. The following results on ℵ_{0}-rank are proved in detail in II.3 of [9].

Note that if T is the theory of an equivalence relation E with two infinite classes containing a and b, the 2 rank of each formula Exa and Exb is one but the 2-rank of their disjunction is 2. So the choice of λ infinite is essential for the following result, which is shown by a straightforward induction on rank using the pigeonhole principle.

Lemma 4.5 (Ultrametric Property) For formulas { ψ_{l}(x, b_{l}) | l < n } any type p, any finite set of formulas Δ, and k, n < ω we have

R[ p ∪ ⋁_{l<n} ψ_{l}(x, b_{l}) , Δ, ℵ_{0}] = max_{l<n} R[ p ∪ ψ_{l}(x, b_{l}) , Δ, ℵ_{0}].

Now by the same kind of compactness argument as we used to show nonforking types have nonforking extensions (Lemma 2.11), we get the following extension principle.

Lemma 4.6 If R(p, Δ, ℵ_{0}) < ∞ and A contains dom p, there is a q ∈ S(A) with p ⊆ q and R(p, Δ, ℵ_{0}) = R(q, Δ, ℵ_{0}).

With this in hand we can relate forking and ‘dropping of rank’. The converse of the following lemma is proved in III.4 of [9] but is not essential for our purpose here.

Lemma 4.7 If p is a type over A, R(p, Δ, ℵ_{0}) < ∞ and q is an extension of A which forks over A, then for some finite Δ, R(p, Δ, ℵ_{0}) > R(q, Δ, ℵ_{0}).

The proof proceeds, as one would expect, by induction on rank. Reduce to the case that q divides over A using the ultrametric inequality. The difficult step is to convert a family of k-inconsistent formulas witnessing dividing into a family of pairwise explicitly contradictory Δ-types; this step follows from Lemma 4.6. The following notation is used to prove the proof that in a stable theory, the two rank is defined for all types.

Notation 4.8 Γ_{p}(ϕ, κ) is the following set of sentences in the language obtained by adding constants a_{τ} for τ ∈ 2^{κ} and c_{s} for s ∈ 2^{<κ} to L(T):

Γ_{p}(ϕ, κ) = {p(a_{τ} : τ ∈ 2^{κ}} ∪ {ϕ(a_{τ}, c_{τ|i})^{τ(i)} : i < κ}

where ϕ^{τ(i)} denotes ϕ or ¬ϕ depending on whether τ(i) is 0 or 1.

An easy compactness argument shows Γ_{p}(ϕ, κ) is consistent for arbitrary κ if and only if Γ_{p}(ϕ, n) is consistent for all n < ω. Note that R(p, Δ, 2) ≥ n if and only if Γ_{p}(ϕ, n) is consistent (where ϕ codes Δ. This quickly implies:

Theorem 4.9 If T is stable, R(p, Δ, ℵ_{0}) ≤ R(p, Δ, 2) < ω for every Δ and p.

Theorem 4.10 If T is stable then T is simple.

In fact κ(T) ≤ |T |^{+}. If not there are a and A such that p = tp(a/A) forks over every subset of A which has cardinality at most |T |. Thus, we can find an increasing sequence of length |T |^{+} of small subsets A_{i} of A such that p_{i} = tp(a/A_{i}) is forking extension of p_{j} if j < i. By Lemma 4.7 and the pigeonhole principle, there is a single finite Δ and an infinite subset X of |T |^{+} such that for i < j in X, R(p_{i}, Δ, ℵ_{0}) > R(p_{j}, Δ, ℵ_{0}) which is clearly impossible.

Definition 4.11 Let p ∈ S(A); p is stationary if for any B ⊇ A, there is a unique extension of p in S(B) which does not fork over A.

The following result can be seen as a variant of the finite equivalence relation theorem which discuss in the next section; the proof here is from [3].

Theorem 4.12 If T is stable, complete types over models are stationary.

To see this, suppose for contradiction that neither tp(a/Mb) nor tp(a′/Mb) forks over M but q(x, y) = tp(ab/M) and r(x, y) = tp(a′b/M) are distinct. For a λ with λ^{|T ||} = λ, fix a Morley sequence B = ⟨b_{i} : i < λ⟩ in tp(b/M). By induction and the Independence Theorem for each X ⊆ λ there is an a_{X} such that tp(a_{X}/b_{i}M) = q(x, b_{i}) if i ∈ X and tp(a_{X}/b_{i}M) = r(x, b_{i}) if i ∉ X. Now there are 2^{λ} types over MB, which has cardinality λ, contrary to Lemma 4.2.

Corollary 4.13 If T is stable and I is an independent sequence of realizations of a type p ∈ S(M) then I is a set of indiscernibles and thus a Morley sequence in p.

Induct on the length of the sequence applying Theorem 4.12 to show that I is a sequence of indiscernibles. But an easy induction using symmetry and the pairs lemma, shows I is a Morley sequence in any ordering.

Corollary 4.14 If T is stable in |A| = λ and |B| > |A| ≥ |T | + κ(T), B contains a set J with |J| > |A| of indiscernibles.

This is Theorem V.1.28 of [1]; the idea of the proof is Lascar’s. In outline, without loss of generality A = M is a model. If ⟨E_{i} : i < λ⟩ are chosen so that E_{i+1} is a maximal subset of B which is independent over ME_{i}, then for some i, |E_{i}| > λ. Then a subset of at least λ^{+} elements of E_{i} realize the same type over A and we finish by Corollary 4.13.

We turn to the use of 2-rank and the definability of types. The next few results are proved in detail in III.1 of [1].

Definition 4.15 The map d from F (L) to F (A), taking ϕ(x, y) to dϕ(y) defines p ∈ S(A) if

ϕ(x, a) ∈ p iff dϕ(y).

Now, it easy to check that

Theorem 4.16 T is stable if and only if for every A and every p ∈ S(A), p is definable over A.

To define p, choose finite p_{0} with the same 2-rank, say n. Then ϕ(x, a) ∈ p if and only Γ_{p_{0}∪ϕ(x,a)}(ϕ, n) is consistent and this is expressed with a single formula. Thus, the parameters of dϕ are those which appear in p_{0}.

It is easy to check that there is essentially only one definition of a type over a model and it extends to any larger set in the following sense.

Notation 4.17 Let M ⊧ T, p ∈ S(M) and M ⊆ A. If d defines p, d(p, A) denotes the type over A defined by d.

Let p ∈ S(M) and M ⊆ A. We have three ‘nice’ extensions of p to A: nondividing, coheir, and definable. So far, only the last is uniquely determined. We will show that in a stable theory there is a unique extension which satisfies any and all of these conditions. One further concept is required: we say tp(a/Mb) is an heir of tp(a/M) if tp(b/Ma) is a coheir of tp(b/M). It is immediate that the definable extension is an heir. In order to obtain the equivalence we need Harnik’s uniformization of the definability.

Lemma 4.18 If T is stable then for every formula ϕ(y, z), for every A and every p ∈ S(A) there are formulas dϕ(y, z) and θ(x, z) such that

1. For some a ∈ A, θ(x, a) ∈ p.

2. For every a, b ∈ A, if θ(x, a) ∈ p then

ϕ(x, b) ∈ p iff dϕ(b, a).

To prove this, reexamine the proof of Theorem 4.16 and let θ_{0} be the conjunction of p_{0}(x, z), and get θ(x, z) by conjoining θ_{0} with the existential quantification of Γ_{θ_{0}(x,z)}(ϕ, R(p, ϕ, 2)). Then let dϕ(y, z) express the consistency of Γ_{{θ(x,z)}∪{ϕ(x,y)}}(ϕ, R(p, ϕ, 2)).

Now, just following the definitions and using the definition of p provided by Harnik’s lemma one can check part 1 of the following; part 2) is then immediate.

Corollary 4.19 Let M ⊧ T, T stable, p ∈ S(M) and M ⊆ A.

1. If d defines p, d(p, A) is the unique heir of p on A.

2. p has a unique coheir on A.

In the French school development, the following lemma had a very clever proof since it preceded the proof of symmetry of forking. Here we get it by just putting our earlier work together.

Theorem 4.20 Let M ⊧ T, T stable, p ∈ S(M) and M ⊆ A. If d defines p, d(p, A) is the coheir of p on A. Moreover, d(p, A) is the unique nonforking extension of p to A.

Let p = tp(a/M) and suppose d(p, A) = q = tp(a/bM). By Corollary 4.19, q is the heir of p on A. So r = tp(b/aM) is the coheir of tp(b/M) whence by Lemma 2.18 r does not divide over M. By symmetry, q does not divide (fork) over M. Thus we see definable extensions do not fork; but coheirs do not fork and there is a unique nonforking extension. Therefore, definable extensions are coheirs (and non-forking extensions and heirs).

5 Multiplicity

Definition 5.1 Let p be a type over A, the multiplicity μ(p) of p is the least μ such that there do not exist μ^{+} pairwise contradictory nonforking extensions of p.

It is immediate from Theorem 4.20 that if T is stable, μ(p) ≤ 2^{| dom p|}. To remove the dependence on | dom p|, we use the notion of a finite equivalence relation. The saturation of the monster model and compactness yields (in any theory) the fundamental definability lemma: if a definable set is A-invariant then it is definable with parameters in A. A conjugate (over A) of a (type)-definable subset of M is just an image under an automorphism of M which fixes A. We analyze sets with finitely many A-conjugates.

Definition 5.2 1. A finite equivalence relation over a set A is an equivalence relation on k-tuples for some k which is definable over A and has only finitely many classes.

2. A set X (formula ϕ(x, b)) is almost over A if X (the solution set of ϕ) has only finitely many images under A-automorphisms of M.

3. The type p is definable almost over A if it is defined over its domain by the map sending ϕ(x, y) to dϕ(y) and each dϕ(y) is almost over A.

Easy applications of the compactness theorem show that a formula has a bounded number of conjugates over A if and only if it is almost over A if and only if it equivalent to a union of equivalence classes of some finite equivalence relation over A.

We write q̂ to indicate that q is a global type - a type over M. If q̂ does not fork over A, then no conjugate of q̂ forks over A. But if M is any model containing A, each nonforking extension of q̂|A to a global type is determined by its restriction to M (Lemma 4.12). So,

Theorem 5.3 If T is stable and q̂ does not fork over A, then q̂ has bounded number of conjugates over A. Moreover, q̂ is definable almost over A. Thus, it has at most 2^{|T |} conjugates over A. Conversely, if q̂ is definable almost over A, q̂ does not fork over A.

The second sentence follows since if some defining formula were not almost over A, it would be easy to find a proper class of conjugates of q. But since there are only |T | defining formulas, we get the bound, 2^{|T |}. For the converse, first note that if I is a set of indiscernibles over A, I is also indiscernible for formulas which are almost over A. (If not, there is a finite equivalence relation which holds of one k-tuple from I and not another. But then it clearly has infinitely many classes.) Now suppose a set I of indiscernibles over A witnesses that ϕ(x, c) ∈ q divides over A. Since q is definable almost over A, dϕ(c) holds for all or none of the members of I; contradiction. With this remark in hand we establish the finite equivalence relation theorem.

Theorem 5.4 (finite equivalence relation theorem) If T is stable and p, q are distinct nonforking extensions of r ∈ S(A) to S(B), there is a finite equivalence relation E over A such that:

p(x) ∪ q(y) ⊢ ¬E(x, y).

Without loss of generality B = M is a model. Fix ϕ(x, m) which is in p and not in q. Choose, by extension, c realizing p and d realizing q such that tp(cd/M) does not fork over A. Then choose m′ so that s = tp(m′/Mcd) extends tp(m/Acd) and does not fork over A. By Theorem 4.20, s is defined by formulas dϕ(y) over M and by Theorem 5.3, s is almost over A so the dϕ are almost over A. We have dϕ(c) ∧ ¬dϕ(d). Since distinct formulas almost over A can be separated by a finite equivalence relation we have the result.

Definition 5.5 For any b and A, stp(b/A) is the

{E(x, c) : E is a finite equivalence relation over A and E(b, c)}.

Note that p = stp(b/A) is not in general a type over A but that dom p can be taken as a set of size at most |A| + |T |.

Theorem 5.6 (Conjugacy Theorem) If p̂_{1} and p̂_{2} are nonforking extensions of p ∈ S(A) to types over the monster model M, p̂_{1} and p̂_{2} are conjugate by an automorphism fixing A.

To see this, it is enough show that nonforking extensions of p to a sufficiently saturated model M are conjugate over M. If a and a′ realize two extensions there is an autorphism α of M taking a to a′ fixing A. But if both stp(a/A) and stp(a′/A) are realized in M (so this is the meaning of sufficiently saturated), α maps tp(a/M) to tp(a′/M) as required. This is the argument from [2]. Now the argument from [1] gives a similarly soft proof of

Theorem 5.7 (Open Mapping Theorem) If q ∈ S(B) does not fork over A and q is isolated then q|A is isolated.

It is enough to show that X, the collection of nonforking extensions of q|A to B, is an open set of the types in S(B) which do not fork over A. By the Conjugacy Theorem, X is the collection of types in S(B), which do not fork over A, that contain a conjugate of ϕ(x, b); by the last characterization X is open as required.

Noting that any two r-sequences c, d from an indiscernible set I over a set A realize the same strong type over A, the finite equivalence relation theorem yields immediately:

Corollary 5.8 If T is stable, I is an indiscernible set over A and tp(b/IA) does not fork over A then I is indiscernible over Ab.

References

[1] J.T. Baldwin. Fundamentals of Stability Theory. Springer-Verlag, 1988.

[2] S Buechler. Essential Stability Theory. Springer-Verlag, 1991.

[3] R. Grossberg, J. Iovino, and O. Lessmann. A primer of simple theories. preprint.

[4] E. Hrushovski and A. Pillay. Groups definable in local fields and pseudo-finite fields. Israel J. of Mathematics, 85:203–262, 1994.

[5] B. Kim and A. Pillay. Simple theories. Annals of Pure and Applied Logic, 88:149–164, 1997.

[6] Byunghan Kim. Forking in simple unstable theories. J. London Math. Soc. (2), 57:257– 267, 1998.

[7] D. Lascar and B. Poizat. An introduction to forking. J. Symbolic Logic, 44:330–350, 1979.

[8] M. Morley. Categoricity in power. Transactions of the American Mathematical Society, 114:514–538, 1965.

[9] S. Shelah. Classification Theory and the Number of Nonisomorphic Models. North-Holland, 1978.

[10] Saharon Shelah. Simple unstable theories. Annals of Mathematical Logic, 19:177–203, 1980.

[11] Saharon Shelah. Toward classifying unstable theories. Annals of Pure and Applied Logic, 80:229–255, 1995.