A PRIMER OF SIMPLE THEORIES

RAMI GROSSBERG, JOSÉ IOVINO, AND OLIVIER LESSMANN

Abstract. We present a self-contained exposition of the basic aspects of simple theories while developing the fundamentals of forking calculus. We expound also the deeper aspects of S. Shelah’s 1980 paper Simple unstable theories. The concept of weak dividing has been replaced with that of forking. The exposition is from a contemporary perspective and takes into account contributions due to S. Buechler, E. Hrushovski, B. Kim, O. Lessmann, S. Shelah and A. Pillay.

Introduction

The question of how many models a complete theory can have has been at the heart of some of the most fundamental developments in the history of model theory. The most basic question that one may ask in this direction is whether a given first order theory has only one model up to isomorphism in a given cardinal. Erwin Engeler, Cesław Ryll-Nardzewski, and Lars Svenonius (all three independently) published in 1959 a complete characterization of the countable theories that have a unique countable model (see Theorem 2.3.13 of [CK]). The next landmark development occurred in 1962, when Michael Morley proved in his Ph.D. thesis that if a countable theory has a unique model in some uncountable cardinality, then it has a unique model in every uncountable cardinality. (See [Mo].) This answered positively a question of Jerzy Łǒs [Lo] for countable theories. Building on work of Frank Rowbottom ([Ro]) the conjecture of Łǒs in full generality (including uncountable theories) was proved by Saharon Shelah in 1970.

The problem of counting the number of uncountable models of a first order theory led Shelah to develop an monumental body of mathematics which he called classification theory. A fundamental distinction that emerges in this context is that between two classes of theories: stable and unstable theories. For a cardinal λ, a theory T is called stable in λ if whenever M is a model of T of cardinality λ, the number of complete types over M is also λ. A theory is called stable if it is stable in some cardinal.

The stability spectrum of T is the class of cardinals λ such that T is stable in λ. In his ground-breaking paper [Sh3], Shelah gave the first description to the stability spectrum of T. He characterized the class of cardinals λ ≥ 2^{|T |} such that T is stable in λ. For the combinatorial analysis of models involved, he devised an intricate tool which he called strong splitting. Later, in order to describe the full stability spectrum (i.e., include the cardinals λ < 2^{|T |} such that T is stable in λ), he refined the concept of strong splitting, and introduced the fundamental concept of forking.

Date: May 1, 2002.

The most recent version is available from www.math.cmu.edu/~rami.

Between the early 1970’s and 1978, Shelah concentrated his efforts in model theory to the completion of his treatise [Sha]. The complete description of the stability spectrum of T is given in Section III-5. Shelah, however, realized quickly that the range of applicability of the concept of forking extends well beyond the realm of the spectrum problem.

Intuitively, if p is a type over a set A, an extension q ⊇ p is called nonforking if q imposes no more dependency relations between its realizations and the elements of A than those already present in p. This yields a general concept of independence in model theory, of which the concepts of linear independence in linear algebra and algebraic independence in field theory are particular examples.

Shelah’s original presentation of the basics of forking appeared to be complicated and required time for the reader to digest. This fact, combined with the rather unique exposition style of the author, made [Sha] difficult to read, even by experts.

In 1977, Daniel Lascar and Bruno Poizat published [LaPo] an alternative approach to forking which appeared more understandable than Shelah’s. They replaced the original “combinatorial” definition with one closely related to Shelah’s notion of semidefinability in Chapter VII of [Sha]. The approach of Lascar and Poizat had a remarkable impact on the dissemination of the concept of forking in the logical community. Several influential publications, such as the books of Anand Pillay [Pi] and Daniel Lascar [La3] and the papers of Victor Harnik and Leo Harrington [HH] and Michael Makkai [Ma], adopted the French approach and avoided Shelah’s definition of forking. Both of these approaches were presented in John Baldwin’s book [Ba].

Parallel to these events, Shelah isolated a class of first-order theories which extends that of stable theories, the class of simple theories. This concept originated in the study of yet another property of theories motivated by combinatorial set theory, namely,

(λ, κ) ∈ SP(T): Every model of T of cardinality λ has a κ-saturated elementary extension of cardinality λ.

For stable T, the class of pairs λ, κ such that (λ, κ) ∈ SP(T) had been completely identified in Chapter VIII-4 of [Sha] (using the stability spectrum theorem and some combinatorial set theory). Notice that the question when κ = λ is equivalent to the existence of saturated model of cardinality λ^{1}.

1Suppose N ⊧ T is saturated of cardinality λ and let M ⊧ T be a given model of cardinality λ, since saturated models are universal there exists N′ ≻ M saturated and isomorphic to N.

Some of the basic facts about existence of saturated elementary extensions are stated as Fact 4.11.

Shelah wondered whether there is a natural class of theories extending the class of stable theories where a characterization of the class of pairs λ, κ such that (λ, κ) ∈ SP(T) holds is still possible. In order to prove a consistency result in this direction, he introduced in [Sh93] the class of simple theories, and showed that a large part of the apparatus of forking from stability theory could be developed in this more general framework. Hrushovski later showed [Hr 1] that it is also consistent that Shelah’s characterization may fail for simple theories.

Some of the complexity of the paper is due to the fact that Shelah did not realize that, for simple theories, the notion of forking is equivalent to the simpler notion of dividing. (An exercise in the first edition of his book asserts that these two concepts are equivalent when the underlying theory is stable.)

It should be remarked that Shelah’s main goal in [Sh93] was not to extend the apparatus of forking from stable to simple theories, but rather to prove the aforementioned consistency result (Theorem 4.10 in [Sh93]). In fact, after the proof of the theorem, he adds

This theorem shows in some sense the distinction between simple and not simple theories is significant.

In the early 1990’s, Ehud Hrushovski noticed that the first order theory of an ultraproduct of finite fields is simple (and unstable) (See [Hr].) Hrushovski’s spectacular applications to Diophantine geometry, as well as his collaboration with Anand Pillay [HP1], [HP2] and Zoe Chatzidakis [CH] attracted much attention to the general theory of simple theories.

Anand Pillay subsequently prompted his Ph.D. student Byunghan Kim to study in the general context of simple theories a property that he and Hrushovski (see [HP1]) isolated and called the Independence Property.

Kim found a new characterization in terms of Morley sequences (see Definition 1.7 below) for the property φ(x̄, ā) divides over A (see Theorem 2.4 below). From this important characterization he derived that for simple theories forking is equivalent to dividing and forking satisfies the symmetry and transitivity properties, generalizing Shelah (who proved these in the stable context making heavy use of the equivalence relation theorem). The proofs we present here are simpler than Kim’s original arguments. The proof we present for Kim’s basic characterization of dividing via Morley sequence is due to Buechler and Lessmann and the elegant argument that forking implies dividing is due to Shelah.

The purpose of this paper is to present a self contained introduction to the basic properties of simple theories and forking. The presentation should be accessible to a reader who has had a basic course in model theory, for example, little more than the first three chapters of [CK] will suffice or alternatively the first three sections of Chapter 2 of [Gr]. We also assume that the reader is accustomed to using the concept of monster model.

The notation is standard. Throughout the paper, T denotes a complete first order theory without finite models. The language of T is denoted L(T). The monster model is denoted by ℭ. If A is a set and ā is a sequence, Aā denotes the union of A with the terms of ā. By type, we always mean a consistent (not necessarily complete) set of L(T)-formulas with parameters from ℭ which is realized in ℭ. Types are generally over finite tuples, unless indicated otherwise. The most fundamental fact connecting complete types and the monster model is the following:

For every subset A of the model ℭ and any pair of sequences ā and b̄ of elements of ℭ of the same length (not necessarily finite) we have

tp(ā/A) = tp(b̄/A) ⟺ ∃f ∈ Aut_{A}(ℭ)[f(ā) = b̄].

The paper is organized as follows:

Section 1: We introduce dividing, forking and Morley sequences, and present the main properties of forking that hold when there is no assumption on the underlying theory: Finite Character, Extension, Invariance, and Monotonicity.

Section 2: We define simple theories and continue the treatment of forking under the assumption that the underlying theory is simple. We prove that forking is equivalent to dividing. We then prove Symmetry, Transitivity, and the Independence Theorem.

Section 3: We introduce the main rank and prove several alternative combinatorial characterizations of simplicity, e.g., in terms of the boundedness of a rank and in terms of the tree property. We also show that, in a simple theory, a type forks if and only if the rank drops. Finally, we study Shelah’s original rank (which includes a fourth parameter) and show that stable theories are simple.

Section 4: We show that for simple theories it is consistent to have a “nice” description of the class SP(T): There is a model of set theory where there are cardinals λ > κ such that λ^{<κ} > λ and λ^{|T |} = λ. (Thus, it is not possible to use cardinal arithmetic to show that (λ, κ) ∈ SP(T).) It is shown that for some λ and κ as above. (λ, κ) ∈ SP(T). The model theoretic content of this section is the fact that the set of nonforking extensions of a type p ∈ S(A) (up to logical equivalence) forms a partial order, satisfying the (2^{|T |+|C|})^{+}-chain condition. This partial order is embedded into a natural complete boolean algebra. We then use a set-theoretic property of boolean algebras satisfying a chain condition to construct κ-saturated extensions of cardinality λ.

Appendix A: We present an improvement of Theorem 1.13. The theorem is a revision of a Theorem of Morley within the more modern setting of Hanf numbers (following Barwise and Kunen). The result has been included here because we could not find the precise statement needed in the literature.

Appendix B: Here we have included several historical remarks, as well a list of credits.

In the last week of 1997 we sent a draft of this paper to John Baldwin and Saharon Shelah. We are grateful for several comments we received and incorporated them in the text. Especially to Shelah for communicating to us his Theorem 4.9 in January 1998. In January 2000 Buechler and Lessmann informed us that they obtained a further simplification in treating the basic properties of dividing (to appear in [BuLe]), and kindly allowed us to include some of their results. We also thank Alexei Kolesnikov and Ivan Tomašić for pointing out several errors in earlier versions of the manuscript.

1. Forking

In this section, T is an arbitrary first order complete theory.

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

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

We begin by introducing the fundamental notion of dividing.

Definition 1.1.

(1) A formula φ(x̄, b̄) divides over A if there exist 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.

Let us start by stating some immediate but fundamental properties of the concept of dividing.

Remark 1.2 (Invariance). Let p be a type and A a set. The following conditions are equivalent:

(1) The type p does not divide over A;

(2) For every A-automorphism f, the type f(p) does not divide over A;

(3) There exists an A-automorphism f such that the type f(p) does not divide over A.

Remark 1.3 (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.

Now we turn to a characterization of dividing that will be invoked several times the paper (Lemma 1.5).

Lemma 1.4. A formula φ(x̄, b̄) divides over A if and only if there exist k < ω and an indiscernible over A ⟨ b̄_{i} | i < ω ⟩ such that b̄_{0} = b̄ and { φ(x̄, b̄_{i}) | i < ω } is k-contradictory.

Proof. Necessity is clear. We prove sufficiency. Assume that φ(x̄, b̄) divides over A and take k < ω and I = { b̄_{i} | i < ω } such that tp(b̄_{i}/A) = tp(b̄/A) for every i < ω and { φ(x̄, b̄_{i}) | i < ω } is k-contradictory. Expand the language with names for the elements of A and let { c̄_{n} | n < ω } be constants not in the language of T. Consider the union of the following sets of sentences:

· T;

· ¬∃x̄ [φ(x̄, c̄_{i_{0}}) ∧ ⋯ ∧ φ(x̄, c̄_{i_{k−1}})], whenever i_{0} < ⋯ < i_{k−1} < ω; · ψ(c̄_{0}, …, c̄_{n}, d̄) ↔ ψ(c̄_{i_{0}}, …, c̄_{i_{n}}, d̄), whenever i_{0} < ⋯ < i_{n} < ω, d̄∈ A, and ψ is in the language of T; · ψ(c̄_{0}, d̄), for every ψ(x̄, d̄) ∈ tp(b̄_{0}/A).

An application of Ramsey’s Theorem shows that this set of sentences is consistent.

Let N be a model for it and let d̄_{n} be the interpretation of c̄_{n} in the model N. Then, ⟨ d̄_{n} | n < ω ⟩ is a sequence indiscernible over A and the set { φ(x̄, b̄_{n}) | n < ω } is k-contradictory. Furthermore, there exists an Aautomorphism f such that f(d̄_{0}) = b̄. Therefore, ⟨ f(d̄_{n}) | n < ω ⟩ satisfies the requirements of the lemma. ⊣

The next lemma appeared in Shelah’s original article [Sh93] and is crucial to analyze forking and dividing. It will be used in the proof Theorem 2.4, the Independence Theorem (Theorem 2.11), and the characterization of forking through the rank (Theorem 3.21).

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

(1) tp(ā/Ab̄) does not divide over A;

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

(3) 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(ā).

Proof. The equivalence between (2) and (3) is a consequence of the homogeneity of ℭ.

(2) ⇒ (1): By contradiction, suppose tp(ā/Ab̄) divides over A and take φ(x̄, c̄, b̄) ∈ tp(ā/Ab̄) with c̄ ∈ A such that φ(x̄, c̄, b̄) divides over A. Lemma 1.4 provides a sequence I = ⟨ b̄_{i} | i < ω ⟩ indiscernible over A such that b̄ = b̄_{0} and { φ(x̄, c̄, b̄_{i}) | i < ω } is k-contradictory. By (2) there exists ā′ realizing tp(ā/Ab̄) such that I is indiscernible over Aā′. But then ⊧ φ[ā′, c̄, b̄_{0}], and ⊧ φ[ā′, c̄, b̄_{i}] for every i < ω by indiscernibility. This contradicts the fact that { φ(x̄, c̄, b̄_{i}) | i < ω } is k-contradictory.

(1) ⇒ (2): Let I = ⟨ b̄_{i} | i < ω ⟩ be a sequence of indiscernibles over A and b̄ ∈ I. Denote p(x̄, b̄) := tp(ā/Ab̄) and let q := ⋃_{b̄_{i}∈I} p(x̄, b̄_{i}). We claim that q is consistent.

If q is inconsistent, there exist a finite I^{∗} ⊆ I, c̄ ∈ A and a formula φ(x̄, c̄, b̄) ∈ tp(ā/Ab̄) such that { φ(x̄, c̄, b̄_{i}) | b̄_{i} ∈ I^{∗} } is inconsistent. By the indiscernibility of I over A, { φ(x̄, c̄, b̄_{i}) | b̄_{i} ∈ I } is |I^{∗}|-inconsistent, so tp(ā/Ab̄) divides over A. But this is a contradiction.

Now let Γ(x̄) be the union of the following formulas:

· q(x̄);

· ψ(x̄, b̄_{0}, …, b̄_{n−1}, d̄) ↔ ψ(x̄, b̄_{i_{0}}, …, b̄_{i_{n−1}}, d̄), whenever ψ ∈ L, n < ω,

i_{0} < ⋯ < i_{n−1} < ω, and d̄∈ A.

We show that Γ(x̄) is consistent, which implies (2). The proof is by induction on the cardinality of the finite subsets of Γ(x̄). For the induction step, it is sufficient to show that for any d̄ ∈ A, i_{0} < ⋯ < i_{n} and φ(x̄, b̄_{0}, b̄_{1}, …, b̄_{i_{n−1}}, d̄) ∈ q(x̄) we have

(**)  ⊧ ∃x̄ [ φ(x̄, b̄_{0}, b̄_{1}, …, b̄_{i_{n−1}}, d̄) ∧
[ψ(x̄, b̄_{0}, …, b̄_{n−1}, d̄) ↔ ψ(x̄, b̄_{i_{0}}, …, b̄_{i_{n−1}}, d̄)] ].

Fix ā′ realizing q. By Ramsey’s Theorem there is an infinite subsequence I′ of I which is ψ-indiscernible over d̄ā′. Take b̄′_{0}, …, b̄′_{n−1}, b̄′_{i_{0}}, …, b̄′_{i_{n−1}} ∈ I′. Then,

⊧ φ[ā′, b̄′_{0}, …, b̄′_{i_{n−1}}, d̄] ∧ [ ψ[ā′, b̄′_{0}, …, b̄′_{n−1}, d̄] ↔ ψ[ā′, b̄′_{i_{0}}, …, b̄′_{i_{n−1}}, d̄] ].

Therefore,

⊧ ∃x̄[ φ(x̄, b̄′_{0}, …, b̄′_{i_{n−1}}, d̄) ∧ [ψ(x̄, b̄′_{0}, …, b̄′_{n−1}, d̄) ↔ ψ(x̄, b̄′_{i_{0}}, …, b̄′_{i_{n−1}}, d̄)] ],

which implies (**) by the indiscernibility of I over A. ⊣

The next lemma is sometimes called the Pairs Lemma, or Left Transitivity. It is also from [Sh93]:

Lemma 1.6 (Left Transitivity). Let ā_{0}, ā_{1}, and b̄ be possibly infinite sequences. If tp(ā_{0}/Ab̄) does not divide over A and tp(ā_{1}/Ab̄ā_{0}) does not divide over Aā_{0}, then tp(ā_{0}ā_{1}/Ab̄) does not divide over A.

Proof. By Finite Character, we may assume that b̄ is finite. Let I be a sequence indiscernible over A such that b̄ ∈ I. By Lemma 1.5, showing that tp(ā_{0}ā_{1}/Ab̄) does not divide over A is equivalent to finding c̄_{0}c̄_{1} realizing tp(ā_{0}ā_{1}/Ab̄) such that I is indiscernible over Ac̄_{0}c̄_{1}. By Lemma 1.5, since tp(ā_{0}/Ab̄) does not divide over A, we can find c̄_{0} realizing tp(ā_{0}/Ab̄) such that I is indiscernible over Ac̄_{0}. Take an Ab̄-automorphism f such that f(ā_{0}) = c̄_{0}. Since tp(ā_{1}/Ab̄ā_{0}) does not divide over Aā_{0}, the type tp(f(ā_{1})/Ab̄c̄_{0}) does not divide over Ac̄_{0}. Since I is indiscernible over Ac̄_{0}, by Lemma 1.5 we can choose c̄_{1} realizing tp(f(ā_{1})/Ab̄c̄_{0}) such that I is indiscernible over Ac̄_{0}c̄_{1}. We have tp(c̄_{0}c̄_{1}/Ab̄) = tp(f(ā_{0})f(ā_{1})/Ab̄) = tp(ā_{0}ā_{1}/Ab̄), so we are done. ⊣ Definition 1.7. Let A ⊆ B and p be a type over B. Let (X, <_{X}) be an infinite linearly ordered set. Then, ⟨ ā_{i} | i ∈ X ⟩ is a Morley sequence for p over A if

(1) For every i ∈ X, ā_{i} realizes p;

(2) For every i ∈ X the type tp(ā_{i}/B ∪ {ā_{j} | j <_{X} i}) does not divide over A;

(3) ⟨ ā_{i} | i ∈ X ⟩ is sequence of indiscernibles over B. When A = B we say that the sequence is a Morley sequence for p.

The following are easy but important consequences of the definition.

Remark 1.8. (1) Any subsequence of a Morley sequence is a Morley

sequence (for the same type and set).

(2) An A-automorphic image of a Morley sequence for p is a Morley sequence for the image of p under the automorphism.

(3) If ⟨ā_{i}b̄_{i} | i ∈ X⟩ is a Morley sequence for tp(āb̄/B) over A, then ⟨ā_{i} | i ∈ X⟩ is a Morley sequence for tp(ā/B) over A and ⟨b̄_{i} | i ∈ X⟩ is a Morley sequence for tp(b̄/B) over A.

(4) If ⟨ā_{i} | i ∈ X⟩ is a Morley sequence for tp(ā/B) over A and b̄ ∈ B then ⟨b̄ā_{i} | i ∈ X⟩ is a Morley sequence for tp(b̄ā/B) over A.

The following remark will be used in the proof of Theorem 2.5. 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 ⟨ā_{i} | i ∈ X⟩ is sequence indexed by X and Y ⊆ X, we write ā_{Y} for ⟨ā_{i} | i ∈ Y ⟩.

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

Proof. By definition of dividing, we may assume that both Y and Z are finite. But then the follows easily by induction on |Z|, using Lemma 1.6 for the induction step. ⊣

We now introduce the main concept of this paper.

Definition 1.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.

Remark 1.11.

(1) If φ(x̄, b̄) divides over A, then φ(x̄, b̄) forks over A;

(2) 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; (3) (Finite Character of Forking) If p ∈ S(B) forks over A, then there

exists φ(x̄, b̄) ∈ p such that φ(x̄, b̄) forks over A.

(4) If ā ∈ acl(A) ⊆ B then tp(ā/B) does not fork over A.

The reader can observe that the advantage of forking over dividing is exactly that the argument below can be carried out.

Theorem 1.12 (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.

Proof. Consider

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

Let us show that p ∪ Γ is consistent. If p ∪ Γ is inconsistent, then there is { ¬ψ_{i}(x̄, b̄_{i}) | i < n } ⊆ Γ such that p ∪ { ¬ψ_{i}(x̄, b̄_{i}) | i < n } is inconsistent. But then, p ⊢ ⋁_{i<n} ψ_{i}(x̄, b̄_{i}) and every ψ_{i}(x̄, b̄_{i}) forks over A. Hence, p forks over A, which is a contradiction.

Choose a complete extension q ∈ S(B) of p ∪ Γ. If q forks over A, there exists ψ(x̄, b̄) ∈ q such that ψ(x̄, b̄) forks over A. By the definition of Γ, we have ¬ψ(x̄, b̄) ∈ Γ ⊆ q, which is a contradiction. Hence, q does not fork over A. ⊣

The following theorem is used to produce Morley sequences much in the same way that Ramsey’s Theorem is used to produce indiscernibles. A sharper upper bound for the length of the initial sequence is given in Appendix A.

Theorem 1.13. Let (X, <_{X}) be a linearly ordered set. For every sequence ⟨ ā_{i} | i < ℶ_{(2^{|T |})^{+}} ⟩ there exists an sequence of indiscernibles ⟨ b̄_{i} | i ∈ X ⟩ with the following property: for every n < ω and every j_{0} <_{X} ⋯ <_{X} j_{n−1} ∈ X there are ordinals i_{0} < ⋯ < i_{n−1} such that

tp(b̄_{j_{0}}, …, b̄_{j_{n−1}}/∅) = tp(ā_{i_{0}}, …, ā_{i_{n−1}}/∅).

Proof. Fix ⟨ ā_{i} | i < ℶ_{(2^{|T |})^{+}} ⟩ in order to find an sequence of indiscernibles as in the statement of the theorem. For n ≥ 1 let

Γ_{n} := { p ∈ S(∅) | There exist i_{1} < ⋯ < i_{n} < (2^{|T |})^{+} such that ⊧ p(ā_{i_{1}}, …, ā_{i_{n}}) }.

Let { c̄_{i} | i ∈ X } be constants not in the language of T. We will find a sequence of types

⟨ p_{n}(x̄_{1}, …, x̄_{n}) | n < ω ⟩, p_{n} ∈ Γ_{n} (*)

such that the union of the following sets of sentences is consistent:

· T;

· p_{n}(c̄_{i_{1}}, …, c̄_{i_{n}}), whenever i_{1} <_{X} ⋯ <_{X} i_{n} ∈ X.

This will clearly prove the proposition.

To prove the consistency of above sentences, we will construct, by induction on n, a sequence of cofinal subsets of (2^{|T |})^{+},

⟨ F_{n} | n < ω ⟩,

a family of subsets of ℶ_{(2^{|T |})^{+}},

{ X_{ξ,n} | ξ ∈ F_{n}, n < ω },

and a sequence of types (*) such that the following conditions hold: (1) F_{n+1} ⊆ F_{n};

(2) |X_{ξ,n}| > ℶ_{λ}(2^{|T |}), where ξ is the λth element of F_{n};

(3) ⊧ p_{n}(ā_{i_{1}}, …, ā_{i_{n}}), whenever i_{1} < ⋯ < i_{n} are in X_{ξ,n}.

We let F_{0} = (2^{|T |})^{+} and X_{ξ,0} = ℶ_{(2^{|T |})^{+}} for every ξ ∈ F_{0}. Then, (1)–(3) are obvious. Assume, then, that F_{n} and the X_{ξ,n}’s have been defined, and let us define F_{n+1} and the X_{ξ,n+1}’s.

Let α be the order type of F_{n}, and let g: α → F_{n} be the unique order isomorphism. Define

G_{n} = { g(λ + n) | λ < α }.

Then G_{n} is also cofinal in (2^{|T |})^{+}. Furthermore, if ξ = g(λ + n),

|X_{ξ,n}| > ℶ_{λ+n}(2^{|T |}). (**)

The map

(ā_{i_{1}}, …, ā_{i_{n}}) ↦ tp(ā_{i_{1}}, …, ā_{i_{n}}/∅)

is a partition of [X_{ξ,n}]^{n} into 2^{|T |}-many classes. Hence, by (**) and the Erdős-Rado theorem (see, for example, [CK] Theorem 7.2.1), there exist X_{ξ,n+1} ⊆ X_{ξ,n} with

|X_{ξ,n+1}| > ℶ_{λ}(2^{|T |})

and a type p_{ξ,n+1} ∈ Γ_{n+1} such that (3) holds with p_{ξ,n+1} in place of p_{n+1}. Now the pigeonhole principle allows us to find a cofinal F_{n+1} ⊆ G_{n} and a type p_{n+1} such that p_{ξ,n+1} = p_{n+1} for every ξ ∈ F_{n+1}. Renumbering the X_{ξ,n+1}’s with respect to the ordering of F_{n+1} preserves (2). This concludes the construction. ⊣

We show that Morley sequences exist for nonforking types.

Theorem 1.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⟩ for p over A. Moreover, if p = tp(b̄/B), the Morley sequence can be chosen such that b̄ = b̄_{i} for some i ∈ X.

Proof. Let us first expand the language with constants for the elements of B and call T^{∗} the resulting expansion T. Now we use Theorem 1.12 to construct by induction a sequence ⟨ ā_{i} | i < ℶ_{(2^{|T^{∗}|})^{+}} ⟩ such that ā_{i} ⊧ p and tp(ā_{i}/B ∪ { ā_{j} | j < i }) does not fork over A.

By Theorem 1.13, there exists a sequence I = ⟨ b̄_{i} | i ∈ X⟩ indiscernible over B (since L(T^{∗}) has names for the elements of B) such that for every n < ω and any j_{0} <_{X} ⋯ <_{X} j_{n} ∈ X there are i_{0} < ⋯ < i_{n−1} < ℶ_{(2^{|T^{∗}|})^{+}} satisfying

tp(b̄_{j_{0}}, …, b̄_{j_{n−1}}/B) = tp(ā_{i_{0}}, …, ā_{i_{n−1}}/B).

We claim that I is a Morley sequence for p over A. First, I is a indiscernible over B and every b̄_{i} realizes p. Now suppose, by contradiction, that tp(b̄_{j}/B ∪ { b̄_{i} | i <_{X} j }) divides over A and fix a formula φ(x̄, c̄, b̄_{j_{1}}, …, b̄_{j_{n−1}}) ∈ tp(b̄_{i}/B∪{ b̄_{j} | j <_{X} i }) such that φ(x̄, c̄, b̄_{j_{1}}, …, b̄_{j_{n−1}}) divides over A. Choose i_{0} < ⋯ < i_{n} such that tp(b̄_{j_{1}}, …, b̄_{j_{n}}, b̄_{i}/B) = tp(ā_{i_{0}}, …, ā_{i_{n}}/B). Then φ(x̄, c̄, ā_{i_{0}}, …, ā_{i_{n−1}}) ∈ tp(ā_{i_{n}}/B ∪ { ā_{j} | j < i_{n} }), and φ(x̄, c̄, ā_{i_{0}}, …, ā_{i_{n−1}}) divides over A. Thus, tp(ā_{i_{n}}/B ∪ { ā_{j} | j < i_{n} }) divides over A, which is a contradiction.

Pick c̄ ∈ I since tp(c̄/B) = tp(b̄/B) there is f ∈ Aut_{B}(ℭ) such that f(c̄) = b̄. It is now easy to check that f(I) is as required. ⊣

Remark 1.15 (Existence of Morley Sequences for Infinitary Types). We leave to the reader the verification that. If C is an arbitrary set, C̄ is an enumeration of C such that tp(C̄/B) does not for over a subset A of B then for any linearly ordered set (X, <_{X}) there exists a Morley sequence ⟨C̄_{i} | i ∈ X⟩ for tp(C̄/B) over A.

2. Forking in Simple Theories

In this section we will prove the main properties of forking which hold when the theory T is simple. Shelah’s original definition of simple theories was requiring that a certain rank be bounded. The definition given here is different. The equivalence will be proved in Section 3.

We start with the main definitions.

Definition 2.1.

(1) A complete first order theory T is said to be simple if each type does not fork over some subset of its domain of size at most |T |.

(2) κ(T) is the least cardinal κ such that every type does not fork over some subset of its domain of cardinality less than κ.

The definition of simplicity implies that κ(T) ≤ |T |^{+}. We will show in the next section that κ(T) < ∞ implies κ(T) ≤ |T |^{+} (Theorem 3.9 and Corollary 3.10). The existence of κ(T) is called Local Character for forking.

Theorem 2.2 (Existence). If T is simple then no type forks over its domain.

Proof. By Monotonicity (Remark 1.3). ⊣

Corollary 2.3. Let T be simple. Then for every p over A there exists a Morley sequence for p over A.

Proof. By Theorem 2.2 the type p does not fork over A, so a Morley sequence for p over A exists by Theorem 1.14. ⊣

The following result discovered by Kim in his thesis, appeared in [Ki], and is central to be able to remove the stability assumption from several of Shelah’s theorems of forking. Kim’s original proof used an argument from page 198 of [Sh93]. The argument presented here is based on an idea of Buechler and Lessmann [BuLe].

Theorem 2.4 (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.

Proof. (3) ⇒ (1) is obvious and (2) ⇒ (3) is given by Corollary 2.3. Let us prove (1) ⇒ (2).

Claim. Let I = ⟨b̄_{i} | i ∈ X⟩ be any Morley sequence for tp(b̄/A). For each Y ⊆ X such that inf(Y) exists and each i ∈ X such that i < inf(Y), the formula φ(x̄, b̄_{i}) divides over A ∪ ⋃_{j∈Y} b̄_{j}.

Proof. Recall that b̄_{Y} stands for ⟨b̄_{i} | i ∈ Y ⟩. Let q(x̄, ȳ) = tp(b̄_{i}, b̄_{Y} /A). First, by using an automorphism we have that φ(x̄, b̄_{i}) divides over A. Let J be an infinite sequence of indiscernibles over A such that { φ(x̄, c̄) | c̄ ∈ J } is inconsistent and b̄_{i} ∈ J. By Proposition 1.9, the type q(b̄_{i}, ȳ) does not divide over A. Hence, by Lemma 1.5, there exists b̄′ ⊧ q(b̄_{i}, x̄/A) such that J is an sequence of indiscernibles over Ab̄′. Since tp(b̄′/Ab̄_{i}) = tp(b̄_{Y} /Ab̄_{i}) there is f ∈ Aut_{Ab̄_{i}}(ℭ) such that f(b̄′) = b̄_{Y}. The sequence f(J) witnesses that φ(x̄, b̄_{i}) divides over Ab̄_{Y}. ⊣

Let I be a Morley sequence for tp(b̄/A). Assume, for a contradiction, that { φ(x̄, c̄) | c̄ ∈ I } is consistent. Let X be the reverse order of (κ(T) + ℵ_{0})^{+}. Use Theorem 1.13 to fix an sequence of indiscernibles J = ⟨b̄′_{i} | i ∈ X⟩ such that for any finite increasing sequence from J there is a finite sequence of elements of I that realize the same type over A. Then J is a Morley sequence for tp(b̄/A). Furthermore, by compactness, since { φ(x̄, c̄) | c̄ ∈ I } is consistent, then so is r := { φ(x̄, b̄_{j}) | j ∈ X }. Choose c̄ realizing r. By simplicity, there exists a set Y of cardinality less than κ(T) such that tp(c̄/AJ) does not fork over Ab̄_{Y}. Choose i ∈ X such that i < min(Y). Then φ(x̄, b̄_{i}) divides over Ab̄_{Y} by the Claim applied to J. But c̄ realizes φ(x̄, b̄_{i}), so tp(c̄/AJ) forks over Ab̄_{Y}, which contradicts the choice of Y. ⊣

We can now prove the equivalence of forking and dividing under simplicity.

Theorem 2.5. Let T be simple. The following conditions are equivalent: (1) φ(x̄, b̄) divides over A;

(2) φ(x̄, b̄) forks over A.

Proof. (1) ⇒ (2) is obvious. We prove (2) ⇒ (1): Since φ(x̄, b̄) forks over A, there exist m < ω and ψ_{i}(x̄, ā^{i}) such that ψ_{i}(x̄, ā^{i}) divides over A for i < m and

φ(x̄, b̄) ⊢ ⋁_{i<m} ψ_{i}(x̄, ā^{i}). (*)

Let ā := ⟨ ā^{0}, …, ā^{m−1} ⟩. By Corollary 2.3 we can fix a Morley sequence for tp(āb̄/A),

⟨ ā_{n}b̄_{n} | n < ω ⟩, with ā_{0} = ā, b̄_{0} = b̄.

Let us write ā_{n} = ⟨ ā_{n}^{0}, …, ā_{n}^{m−1} ⟩ for every n < ω.

Since ⟨b̄_{n} | n < ω⟩ is indiscernible over A, to show that φ(x̄, b̄) divides over A, it suffices to show that the set { φ(x̄, b̄_{n}) | n < ω } is inconsistent. Assume that it is consistent and let c̄ realize it. By the definition of Morley sequence,

tp(āb̄/A) = tp(ā_{n}b̄_{n}/A), for every n < ω.

Hence, using an A-automorphism and (*), we conclude that

(**) φ(x̄, b̄_{n}) ⊢ ⋁_{i<m} ψ_{i}(x̄, ā_{n}^{i}), for every n < ω.

By the choice of c̄, we have ⊧ φ[c̄, b̄_{n}] for every n < ω. Therefore, (**) implies that for every n < ω there exists i(n) < m such that ⊧ ψ_{i(n)}[c̄, ā_{n}^{i(n)}]. By the pigeonhole principle, there exist an infinite S ⊆ ω and a fixed k < m such that

(†) ⊧ ψ_{k}[ c̄, ā_{n}^{k}], for every n ∈ S.

But ⟨ā_{n}^{k} | n ∈ S⟩ is a Morley sequence for tp(ā_{0}^{k}/A). Furthermore, (†) shows that the set { ψ_{k}(x̄, ā_{n}^{k}) | n ∈ S } is consistent. Thus, ψ_{k}(x̄, ā^{k}) does not divide over A by Theorem 2.4. This contradicts the choice of ψ_{k}(x̄, ā^{k}). ⊣

Theorem 2.6 (Symmetry). Let T be simple. Then tp(ā/Ab̄) forks over A if and only if tp(b̄/Aā) forks over A.

Proof. It is, of course, sufficient to prove one direction. Suppose tp(ā/Ab̄) forks over A and take φ(x̄, c̄, b̄) ∈ tp(ā/Ab̄) with c̄ ∈ A such that φ(x̄, c̄, b̄) forks over A. By Theorem 2.5, the formula φ(x̄, c̄, b̄) divides over A. If tp(b̄/Aā) does not fork over A, we can choose I = ⟨ b̄_{n} | n < ω ⟩, a Morley sequence for tp(b̄/Aā) over A such that b̄_{0} = b̄. We have ⊧ φ[ā, c̄, b̄], so, by the indiscernibility of I over Aā, we also have ⊧ φ[ā, c̄, b̄_{n}] for every n < ω. Thus, { φ(x̄, c̄, b̄_{n}) | n < ω } is consistent (as it is realized by ā). Notice that ⟨ c̄b̄_{n} | n < ω ⟩ is a Morley sequence for tp(c̄b̄/A). But then the set { φ(x̄, c̄, b̄_{n}) | n < ω } must be inconsistent, by Theorem 2.4. We have a contradiction, so tp(b̄/Aā) forks over A. ⊣

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

Proof. We use the fact that forking is equivalent to dividing. Let b̄ enumerate B and c̄ enumerate C \B. By Symmetry and Finite Character, we have that tp(b̄/Aā) does not divide over A and that tp(c̄/Ab̄ā) does not divide over Ab̄. Hence, by Lemma 1.6, tp(c̄b̄/Aā) does not divide over A. Another use of Symmetry finishes the proof. ⊣

The next two lemmas will be used to prove Corollary 2.10. We first prove Corollary 2.10 for Morley sequences.

Lemma 2.8. Let T be simple. Let p(x̄, b̄) be a complete type over Ab̄ which does not fork over A. Let ⟨b̄_{i} | i < ω⟩ be a Morley sequence for tp(b̄/A) with b̄ = b̄_{0}. Then there exists ā realizing p(x̄, b̄) such that ⟨b̄_{i} | i < ω⟩ is Aā-indiscernible and tp(ā/A{b̄_{i} | i < ω}) does not fork over A.

Proof. By Lemma 1.5, there exists ā realizing p(x̄, b̄) such that ⟨b̄_{i} | i < ω⟩ is Aā-indiscernible. We now show that tp(ā/A ∪ {b̄_{i} | i < ω}) does not fork over A. It is enough to show that tp(ā/A∪{b̄_{i} | i < ω}) does not divide over A, and by Finite Character, it is enough to show that tp(ā/A ∪ {b̄_{i} | i < n}) does not divide over A, for each n < ω.

Fix n < ω and let

q(x̄, b̄_{0}, …, b̄_{n−1}) = tp(ā/A ∪ {b̄_{i} | i < n}).

By Transitivity and Symmetry, for each n < ω the sequence

⟨b̄_{nk} … b̄_{nk+n−1} | k < ω⟩

is a Morley sequence for tp(b̄_{0} … b̄_{n−1}/A). Now by indiscernibility of ⟨b̄_{i} | i < ω⟩ over Aā, the type q(x̄, b̄_{nk}, …, b̄_{nk+n−1}) is realized by ā, for every n < ω. Therefore ⋃_{k<ω} q(x̄, b̄_{nk}, …, b̄_{nk+n−1}) is consistent, and hence q(x̄, b̄_{0}, …, b̄_{n−1}) does not divide over A, by Theorem 2.4. ⊣

Lemma 2.9. Let T be simple. Let ⟨b̄_{i} | i < ω + ω⟩ be indiscernible over A. Then ⟨b̄_{ω+i} | i < ω⟩ is a Morley sequence for tp(b̄_{ω}/A ∪ {b̄_{i} | i < ω}).

Proof. Let I = ⟨b̄_{i} | i < ω⟩. By indiscernibility of ⟨b̄_{i} | i < ω + ω⟩, each b̄_{ω+i} realizes tp(b̄_{ω}/A ∪ {b̄_{i} | i < ω}), and ⟨b̄_{ω+i} | i < ω⟩ is indiscernible over AI. We now show that for each i < ω,

tp(b̄_{ω+i+1}/AI ∪ {b̄_{ω}, … b̄_{ω+i}})

does not fork over AI. By Symmetry and Finite Character, it is enough to show that the type

p(x̄, b̄_{0}, …, b̄_{n}, b̄_{ω+i+1}) = tp(b̄_{ω}, …, b̄_{ω+i}/A ∪ {b̄_{0}, …, b̄_{n}, b̄_{ω+i+1}})

does not divide over AI, for each n < ω. Let J be indiscernible over AI and containing b̄_{ω+i+1}. We must show that ⋃_{c̄∈J} p(x̄, b̄_{0}, …, b̄_{n}, c̄) is consistent. Notice that b̄_{n+1}ˆ … ˆ b̄_{n+1+i} realizes p(x̄, b̄_{0}, …, b̄_{n}, b̄_{ω+i+1}) by indiscernibility of ⟨b̄_{i} | i < ω + ω⟩. Hence, b̄_{n+1}ˆ … ˆ b̄_{n+1+i} realizes p(x̄, b̄_{0}, …, b̄_{n}, c̄), for each c̄ ∈ J, by indiscernibility of J over AI, so ⋃_{c̄∈J} p(x̄, b̄_{0}, …, b̄_{n}, c̄) is consistent. ⊣

The key improvement in the next Corollary over Lemma 1.5 is that ⋃_{i<ω} p(x̄, b̄_{i}) does not fork over A.

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

Proof. Let I = ⟨b̄_{i} | i < ω⟩ be an sequence of indiscernibles over A with b̄ = b̄_{0}. By compactness, extend I to ⟨b̄_{i} | i < ω + ω⟩ indiscernible over A. By the preceding lemma, we have

(*) ⟨b̄_{ω+i} | i < ω⟩ is a Morley sequence for tp(b̄_{ω}/AI).

By indiscernibility, p(x̄, b̄_{ω}) does not fork over A, and by Extension, there exists ā′ ⊧ p(x̄, b̄_{ω}), such that tp(ā′/AIb̄_{ω}) does not fork over A, and hence does not fork over AI. Thus, by Lemma 2.8 and (*), there exists ā′′ realizing tp(ā′/AIb̄_{ω}), such that ⟨b̄_{ω+i} | i < ω⟩ is indiscernible over Aā′′ and tp(ā′′/AI ∪ {b̄_{ω+i} | i < ω}) does not fork over AI. By Monotonicity, tp(ā′′/AI ∪ {b̄_{ω+i} | i < ω}) does not fork over AIb̄_{ω}. Hence, by Transitivity, tp(ā′′/AI ∪ {b̄_{ω+i} | i < ω}) does not fork over A, since tp(ā′′/AIb̄_{ω}) = tp(ā′/AIb̄_{ω}). This implies in particular that tp(ā′′/A ∪ {b̄_{ω+i} | i < ω}) does not fork over A.

Let f ∈ Aut_{A}(ℭ) be such that f(b̄_{ω+i}) = b̄_{i} for i < ω and let ā = f(ā′′). Then ⟨b̄_{i} | i < ω⟩ is indiscernible over Aā and ā ⊧ p(x̄, b̄_{0}), since f(b̄_{ω}) = b̄_{0}. Furthermore, tp(ā/AI) does not fork over A. ⊣

When the theory is stable, the next theorem follows from Shelah’s fact that types over models are stationary (see Theorem 2.12 below). The theorem is due to Kim and Pillay and generalizes a result of Hrushovski and Pillay in [HP1]). The Independence Theorem is to simple theories what the stationarity of types over models is to stable theories. Similarly, the Chain Condition (Theorem 4.9) is to simple theories what to the bound on the number of nonforking extensions is to stable theories.

Theorem 2.11 (The Independence Theorem). Let T be simple and M be a model of T. Let A and B be sets such that tp(A/MB) does not fork over M. Let p ∈ S(M). Let q be a nonforking extension of p over MA and r be a nonforking extension of p over MB. Then q ∪ r is consistent, moreover q ∪ r is a nonforking extension of p over MAB.

Proof. Write ā for an enumeration of A and b̄ for an enumeration of B. By Extension, there exist c̄ realizing q(x̄, ā) such tp(c̄/Mā) does not fork over M and d̄ realizing r(x̄, b̄) such that tp(d̄/Mb̄) does not fork over M. By assumption, tp(c̄/M) = p = tp(d̄/M), so we can find b̄′ such that tp(c̄b̄′/M) = tp(d̄b̄/M). By Invariance and choice of d̄ and b̄′, we have that tp(c̄/Mb̄′) does not fork over M. By Symmetry we have that tp(b̄′/Mc̄) does not fork over M, so by Extension we may assume that tp(b̄′/Māc̄) does not fork over M. By Symmetry and Monotonicity, tp(c̄/Māb̄′) does not fork over Mā. By choice of c̄ and Transitivity, we finally have that tp(c̄/Māb̄′) does not fork over M. Since c̄ realizes q(x̄, ā) and r(x̄, b̄′), we have that q(x̄, ā) ∪ r(x̄, b̄′) does not fork over M.

Suppose, by contradiction, that q(x̄, ā) ∪ r(x̄, b̄) forks over M. We will eventually contradict the following claim.

Claim. There does not exist a sequence ⟨ ā_{i}, c̄_{i} | i < ω ⟩ indiscernible over M such that

· q(x̄, ā_{0}) ∪ r(x̄, c̄_{0}) does not fork over M, and
· q(x̄, ā_{0}) ∪ r(x̄, c̄_{1}) forks over M.

Proof of the claim. Suppose that there is ⟨ ā_{i}, c̄_{i} | i < ω ⟩ as above. By Corollary 2.10, there exists d̄ realizing q(x̄, ā_{0}) ∪ r(x̄, c̄_{0}) such that ⟨ ā_{i}, c̄_{i} | i < ω ⟩ is indiscernible over Md̄ and tp(d̄/M ∪ { ā_{i}, c̄_{i} | i < ω }) does not fork over M. By Monotonicity, q(x̄, ā_{0}) ∪ r(x̄, c̄_{1}) does not fork over M, a contradiction. ⊣

Since M is a model, the set F := {φ(M, c̄) : φ(x̄, c̄) ∈ tp(b̄/M)} has the finite intersection property. Let D be an ultrafilter over M extending F such that tp(b̄/M) = tp(b̄′/M) = Av(D, M) ^{2}. Define ⟨ b̄_{i} | i < ω ⟩ such that b̄_{0} = b̄ and b̄_{i} realizes Av(D, M ∪ { b̄_{j} | j < i }). Then ⟨ b̄_{i} | i < ω ⟩ is indiscernible over M. By Lemma 1.5, since forking is the same as dividing, we may assume, by using an Mb̄-automorphism, that ⟨ b̄_{i} | i < ω ⟩ is indiscernible over Mā. Similarly, we define ⟨ b̄′_{i} | i < ω ⟩ such that b̄′_{0} = b̄′ and b̄′_{i} realizes Av(D, M ∪ { b̄′_{j} | j < i }). Again, we may assume, that ⟨ b̄′_{i} | i < ω ⟩ is indiscernible over Mā. Now, let us construct a third indiscernible sequence ⟨ c̄_{i} | i < ω ⟩, but now such that c̄_{i} realizes

Av(D, M ∪ { b̄_{i} | i < ω } ∪ { b̄′_{i} | i < ω } ∪ { c̄_{j} | j < i }).

Then, both ⟨ b̄_{i} | i < ω ⟩ + ⟨ c̄_{i} | i < ω ⟩ and ⟨ b̄′_{i} | i < ω ⟩ + ⟨ c̄_{i} | i < ω ⟩ are indiscernible over M. Furthermore, by taking a longer sequence if necessary, we may assume that

tp(āc̄_{i}/M) = tp(āc̄_{j}/M), for every i, j < ω.

Suppose that for some (and hence all) i < ω the type q(x̄, ā)∪r(x̄, c̄_{i}) does not fork over M. We will find an infinite sequence ⟨ā_{i} | i < ω⟩ such that q(x̄, ā_{i}) ∪ r(x̄, c̄_{j}) forks over M if and only if i < j. By Ramsey’s Theorem and Compactness, we may assume that ⟨ ā_{i}, c̄_{i} | i < ω ⟩ is indiscernible over M. This contradicts the claim.

Since ⟨ b̄_{i} | i < ω ⟩ + ⟨ c̄_{i} | i < ω ⟩ is indiscernible over M, then for each i < ω, we have

tp(b̄_{0}, b̄_{1}, …, b̄_{i−1}, c̄_{0}, c̄_{1}, … /M) = tp(c̄_{0}, c̄_{1}, …, c̄_{i−1}, c̄_{i}, c̄_{i+1}, … /M).

Hence, by homogeneity, for each i < ω, we can find ā_{i} such that

tp(b̄_{0}, b̄_{1}, …, b̄_{i−1}, ā, c̄_{0}, c̄_{1}, … /M) = tp(c̄_{0}, c̄_{1}, …, c̄_{i−1}, ā_{i}, c̄_{i}, c̄_{i+1}, … /M).

Notice that for i ≤ j, we have tp(ā_{i}, c̄_{j}/M) = tp(ā, c̄_{j−i}/M) = tp(ā, c̄_{j}/M). Hence, by Invariance, we have q(x, ā_{i}) ∪ r(x, c̄_{j}) does not fork over M. Now if i > j, then tp(ā_{i}, c̄_{j}/M) = tp(ā, b̄_{j}/M) = tp(ā, b̄/M), so by Invariance, q(x, ā_{i}) ∪ r(x, c̄_{j}) forks over M.

In case q(x̄, ā) ∪ r(x̄, c̄_{i}) forks over M, for some i < ω, we use the b̄′_{i}s, rather than the b̄_{i}s, to derive a similar contradiction.

⊣

2Recall: If I ⊆ ^{m}| ℭ| and D is an ultrafilter on I then for x̄ such that ℓ(x̄) = m Av(D, M) := { φ(x̄; ā) | ā ∈ A, {b̄ ∈ I : ℭ ⊧ φ[b̄; ā]} ∈ D }.

The purpose of the rest of this section is to convince the reader familiar with stability that Shelah’s Finite Equivalence Relation theorem is a particular case of the Independence Theorem. One of the many equivalent versions of the Finite Equivalence Relation Theorem is as follows.

Theorem 2.12 (Finite equivalence relation theorem). Suppose that T is stable and let M ⊧ T. If p ∈ S(M), then p is stationary (i.e. has a unique non forking extension).

First notice the following application of the independence theorem:

Corollary 2.13. Suppose T is simple and that {B_{i} | i < λ} and p ∈ S(M) are such that

tp(B_{i}/M ∪ {B_{j} | j < i}) does not fork over M for each i < λ.

If p_{i} ∈ S(MB_{i}) is a nonforking extension of p then the set ⋃_{i<λ} p_{i} is consistent and does not fork over M.

Proof. By Finite Character we may assume that λ is finite. But then the Independence Theorem can be used to prove the statement by induction on λ. ⊣

Now to the proof of Theorem 2.12. We shall use the fact that T is stable then T is simple. This is proved in the next section (Theorem 3.13).

Proof of Theorem 2.12. Suppose for the sake of contradiction that M, B ⊇ |M| and that q, r ∈ S(B) are are distinct nonforking extensions of the type p := q ↾ M = r ↾ M. Let λ ≥ |T | + ℵ_{0}, we will show that T is unstable in λ. By the Extension and Finite Character properties and the downward Löwenhweim-Skolem theorem we may assume that ∥M∥ = |B| = λ. Let ⟨B_{i} | i < λ⟩ be a Morley sequence for tp(B/M) (see Remark 1.15). Since tp(B/M) = tp(B_{i}/M), there exists f_{i} ∈ Aut_{M}(ℭ) such that f(B) = B_{i}.

Given S ⊆ λ consider

q_{S} := ⋃_{i∈S} f_{i}(q) ∪ ⋃_{j∉S} f_{j}(r).

By Corollary 2.13, q_{X} is consistent. Now S_{1} ≠ S_{2} implies q_{S_{1}} ≠ q_{S_{2}}. Hence

|S(⋃_{i<λ} B_{i})| ≥ |{q_{S} : S ⊆ λ}| = 2^{λ}.

while | ⋃_{i<λ} B_{i}| = λ, so T is unstable. ⊣

The reader familiar with the independence property (See [Sha]) will notice that what we have used in the proof is that T is simple and does not have the independence property.

3. Ranks and Simple Theories

Shelah’s original definition of simple theories was requiring that a certain rank be bounded. In this section, we introduce a rank that captures simplicity, give several characterizations of simplicity and forking and show that they coincide with the one from the previous section.

Definition 3.1. Let p(x̄) be a set of formulas, possibly with parameters. Let Δ be a set of formulas without parameters and let k < ω. We define the rank D[p, Δ, k]. The rank D[p, Δ, k] is either an ordinal, or −1, or ∞. The relation D[p, Δ, k] ≥ α, is defined by induction on α.

(1) D[p, Δ, k] ≥ 0 if p is consistent;

(2) D[p, Δ, k] ≥ δ when δ is a limit if D[p, Δ, k] ≥ β for every β < δ;

(3) D[p, Δ, k] ≥ α + 1 if for every finite r ⊆ p, there exist a formula φ(x̄, ȳ) ∈ Δ and a set { ā_{i} | i < ω } with ℓ(ā_{i}) = ℓ(ȳ) such that:

(a) D[r ∪ φ(x̄, ā_{i}) , Δ, k] ≥ α for every i < ω;

(b) The set { φ(x̄, ā_{i}) | i < ω } is k-contradictory. We write

D[p, Δ, k] = −1 if p is not consistent;

D[p, Δ, k] = α when D[p, Δ, k] ≥ α but D[p, Δ, k] ≱ α + 1; D[p, Δ, k] = ∞ when D[p, Δ, k] ≥ α for every ordinal α.

The next propositions establish some of the most basic properties of the rank. The proofs are rather easy exercises. They are included for completeness.

Proposition 3.2.

(1) (Monotonicity) If p_{1} ⊢ p_{2}, Δ_{1} ⊆ Δ_{2}, and k_{1} ≤ k_{2}, then D[p_{1}, Δ_{1}, k_{1}] ≤ D[p_{2}, Δ_{2}, k_{2}];

(2) (Finite Character) For every type p there exists a finite r ⊆ p such that D[p, Δ, k] = D[r, Δ, k]

(3) (Invariance) If f is an automorphism, then D[p, Δ, k] = D[f(p), Δ, k].

Proof. (1) We prove by induction on the ordinal α, that

D[p_{1}, Δ_{1}, k_{1}] ≥ α implies D[p_{2}, Δ_{2}, k_{2}] ≥ α.

If D[p_{1}, Δ_{1}, k_{1}] ≥ 0, then p_{1} is consistent, so p_{2} is consistent since p_{1} ⊢ p_{2}, and hence D[p_{2}, Δ_{2}, k_{2}] ≥ 0.

When α is a limit ordinal, the implication is immediate from the induction hypothesis.

Suppose D[p_{1}, Δ_{1}, k_{1}] ≥ α + 1 and let r_{2} ⊆ p_{2} be finite. Since p_{1} ⊢ p_{2}, there is a finite r_{1} ⊆ p_{1} such that r_{1} ⊢ r_{2}. By the definition of the rank, there exist φ(x̄, ȳ) ∈ Δ_{1} and { ā_{i} | i < ω } with ℓ(ā_{i}) = ℓ(ȳ) such that D[r_{1} ∪ φ(x̄, ā_{i}) Δ_{1}, k_{1}] ≥ α for every i < ω and { φ(x̄, ā_{i}) | i < ω } is k_{1}-contradictory. Now, r_{1} ∪ φ(x̄, ā_{i}) ⊢ r_{2} ∪ φ(x̄, ā_{i}), so D[ r_{2} ∪ φ(x̄, ā_{i}) , Δ_{2}, k_{2}] ≥ α for every i < ω by induction hypothesis. But φ(x̄, ȳ) ∈ Δ_{2} (since Δ_{1} ⊆ Δ_{2}), and { φ(x̄, ā_{i}) | i < ω } is k_{2}-contradictory (since k_{2} ≥ k_{1}). Hence, D[ p_{2}, Δ_{2}, k_{2}] ≥ α + 1, by definition of the rank.

(2) If D[ p, Δ, k] = −1, then p is inconsistent and by the compactness theorem there is an inconsistent finite r ⊆ p. Then, D[ r, Δ, k] = −1.

If D[ p, Δ, k] = ∞, then for every finite r ⊆ p, D[ r, Δ, k] = ∞ by Monotonicity.

If D[ p, Δ, k] = α, then D[ p, Δ, k] ≥ α and D[ p, Δ, k] ≱ α + 1, so there exists a finite r ⊆ p with D[ r, Δ, k] ≥ α such that there are no φ(x̄, ȳ) ∈ Δ and { ā_{i} | i < ω } such that { φ(x̄, ā_{i}) | i < ω } is k-contradictory and D[ r ∪ φ(x̄, ā_{i}) Δ, k] ≥ α for every i < ω. But this demonstrates that D[ r, Δ, k] ≱ α + 1. Thus, D[ r, Δ, k] = α.

(3) Immediate. ⊣

Lemma 3.3 (Ultrametric Property). For every p, Δ, k, n < ω and formulas { ψ_{l}(x̄, b̄_{l}) | l < n }, we have

D[ p ∪ ⋁_{l<n} ψ_{l}(x̄, b̄_{l}) , Δ, k] = max_{l<n} D[ p ∪ ψ_{l}(x̄, b̄_{l}) , Δ, k].

Proof. By Monotonicity, for every l < n we have

D[ p ∪ ψ_{l}(x̄, b̄_{l}) , Δ, k] ≤ D[ p ∪ ⋁_{l<n} ψ_{l}(x̄, b̄_{l}) , Δ, k].

Hence,

max_{l<n} D[ p ∪ ψ_{l}(x̄, b̄_{l}) , Δ, k] ≤ D[ p ∪ ⋁_{l<n} ψ_{l}(x̄, b̄_{l}) , Δ, k].

To prove the reverse inequality, we show by induction that for every ordinal α and every type p,

D[ p ∪ ⋁_{l<n} ψ_{l}(x̄, b̄_{l}) , Δ, k] ≥ α implies max_{l<n} D[ p ∪ ψ_{l}(x̄, b̄_{l}) , Δ, k] ≥ α.

When α = 0 or α is a limit ordinal, the implication is easy. For the successor stage suppose, for contradiction, that

D[ p ∪ ⋁_{l<n} ψ_{l}(x̄, b̄_{l}) , Δ, k] ≥ α + 1, but max_{l<n} D[ p ∪ ψ_{l}(x̄, b̄_{l}) , Δ, k] ≱ α + 1. (*)

Then, for every l < n we have D[ p ∪ ψ_{l}(x̄, b̄_{l}) , Δ, k] ≤ α. Choose a finite r_{l} ⊆ p such that

D[ r_{l} ∪ ψ_{l}(x̄, b̄_{l}) , Δ, k] ≤ α

and let r := ⋃_{l<n} r_{l}. Then r ⊆ p is finite, so, by (*) and the definition of the rank, there exist φ(x̄, ȳ) ∈ Δ and { ā_{i} | i < ω } with ℓ(ā_{i}) = ℓ(ȳ) such that { φ(x̄, ā_{i}) | i < ω } is k-contradictory and for every i < ω

D[ r ∪ ⋁_{l<n} ψ(x̄, b̄_{l}) ∪ φ(x̄, ā_{i}) , Δ, k] ≥ α.

By induction hypothesis, for every i < ω

max_{l<n} D[ r ∪ ψ_{l}(x̄, b̄_{l}) ∪ φ(x̄, ā_{i}) Δ, k] ≥ α,

so there exists l_{i} < n such that

D[ r ∪ ψ_{l_{i}}(x̄, b̄_{l_{i}}) ∪ φ(x̄, ā_{i}) , Δ, k] ≥ α.

By the pigeonhole principle, we may assume that l_{i} = l^{∗} < n is fixed and

D[ r ∪ ψ_{l^{∗}}(x̄, b̄_{l^{∗}}) ∪ φ(x̄, ā_{i}) , Δ, k] ≥ α,

for every i < ω. By definition of the rank,

D[ r ∪ ψ_{l^{∗}}(x̄, b̄_{l^{∗}}) , Δ, k] ≥ α + 1,

and by Monotonicity,

D[ r_{l^{∗}} ∪ ψ_{l^{∗}}(x̄, b̄_{l^{∗}}) , Δ, k] ≥ α + 1.

But this contradicts the choice of r_{l^{∗}}. Therefore,

max_{l<n} D[ p ∪ ψ_{l}(x̄, b̄_{l}) , Δ, k] ≥ α + 1.

⊣

The proof of the following lemma is similar to that of Theorem 1.12.

Lemma 3.4. Let p be a type, Δ and Φ be sets of formulas and k < ω. Suppose that D[ p, Δ, k] < ∞. Then, for every set B there exists a type q ∈ S_{Φ}(B) such that

D[ p, Δ, k] = D[ p ∪ q, Δ, k].

Proof. We may assume that Φ is closed under conjunction. Suppose that D[p, Δ, k] = α. Consider

Γ := { ¬ψ(x̄, b̄) | b̄ ∈ B, ψ(x̄, ȳ) ∈ Φ, D[p ∪ ψ(x̄, b̄), Δ, k] < α}.

Let us show that p ∪ Γ is consistent. If p ∪ Γ were inconsistent, there would be { ¬ψ_{i}(x̄, b̄_{i}) | i < n } ⊆ Γ such that p∪{ ¬ψ_{i}(x̄, b̄_{i}) | i < n } is inconsistent. But then, p ⊢ ⋁_{i<n} ψ_{i}(x̄, b̄_{i}). By Monotonicity and Lemma 3.3, we have

α = D[p, Δ, k] ≤ D[p ∪ ⋁_{i<n} ψ_{i}(x̄, b̄_{i}), Δ, k] = max_{i<n} D[ p ∪ ψ_{i}(x̄, b̄_{i}) , Δ, k] < α,

which is, of course, a contradiction.

Choose q ∈ S_{Φ}(B) extending Γ. If D[p ∪ q, Δ, k] < α, then by Finite Character, there exists ψ(x̄, b̄) ∈ q such that D[p∪ψ(x̄, b̄), Δ, k] < α. Hence, by definition of Γ, we must have ¬ψ(x̄, b̄) ∈ Γ ⊆ q, which is a contradiction.

⊣

Lemma 3.5. Suppose that D[ p, Δ, k] < ∞, for each finite Δ and each k < ω. Suppose that p is a type over A and that φ(x̄, ā) forks over A. Then there are Δ_{0} finite and k_{0} < ω such that

D[ p ∪ φ(x̄, ā) , Δ, k] < D[ p, Δ, k],

for every Δ ⊇ Δ_{0} finite and every k ≥ k_{0}.

Proof. Suppose first that φ(x̄, ā) divides over A. By lemma 1.4 there exist a set { ā_{i} | i < ω } and k < ω such that ā_{0} = ā, tp(ā/A) = tp(ā_{i}/A) for every i < ω, and { φ(x̄, ā_{i}) | i < ω } is k-contradictory. Let Δ_{0} := { φ(x̄, ȳ) } and k_{0} := k. Suppose that there exist a finite Δ ⊇ Δ_{0} finite and l ≥ k_{0} such that

D[ p ∪ φ(x̄, ā) , Δ, l] ≮ D[ p, Δ, l].

By Monotonicity,

D[ p ∪ φ(x̄, ā) , Δ, l] = D[ p, Δ, l].

By assumption, there is an ordinal α such that D[ p, Δ, l] = α. By Finite Character, there is a finite r ⊆ p such that D[ r, Δ, l] = D[ p, Δ, l] = α. Since p ⊢ r ∪ φ ⊢ r, we have

D[ r ∪ φ(x̄, ā) , Δ, l] = α. (*)

Since tp(ā_{i}/A) = tp(ā/A), there exists an A-automorphism f such that f_{i}(ā) = ā_{i}. By Invariance of the rank,

(**)  D[ f_{i}(r) ∪ φ(x̄, f_{i}(ā)) , Δ, l] = α,  for every i < ω.

Since f_{i} fixes A pointwise and dom(r) ⊆ A, from (**) we obtain

D[ r ∪ φ(x̄, ā_{i}) , Δ, l] = α, for every i < ω,

but φ(x̄, ȳ) ∈ Δ and { φ(x̄, ā_{i}) | i < ω } is l-contradictory (since l ≥ k). Hence, D[ r, Δ, l] ≥ α + 1, which is a contradiction.

The lemma is therefore true if φ(x̄, ā) divides over A. If φ(x̄, ā) forks over A, there exist n < ω and φ_{i}(x̄, ā^{i}) for i < n, such that φ(x̄, ā) ⊢ ⋁_{i<n} φ_{i}(x̄, ā^{i}) and φ_{i}(x̄, ā^{i}) divides over A, for every i < n. By the preceding argument, for every i < n there exist a finite Δ^{i} and k^{i} < ω such that

D[ p ∪ φ_{i}(x̄, ā^{i}) , Δ, l] < D[ p, Δ, l], for every Δ ⊇ Δ^{i} finite and k^{i} ≤ l < ω. (†)

Let Δ_{0} := ⋃_{i<n} Δ^{i}, k_{0} := max_{i<n} k^{i}. We prove that these Δ_{0} and k_{0} satisfy the conclusion of the lemma.

Suppose Δ ⊇ Δ_{0} is finite and k_{0} ≤ l < ω. We have

D[ p ∪ φ(x̄, ā) , Δ, l] ≤ D[ p ∪ ⋁_{i<n} φ_{i}(x̄, ā^{i}) , Δ, l] (since φ(x̄, ā) ⊢ ⋁_{i<n} φ_{i}(x̄, ā^{i}))
= max_{i<n} D[ p ∪ φ_{i}(x̄, ā^{i}) , Δ, l]  (by Lemma 3.3)
< D[ p, Δ, l]  ( by (†) ),

which is what we sought to prove. ⊣

Theorem 3.6. Suppose that D[ x̄ = x̄, Δ, k] < ∞ for each finite Δ and k < ω. Then T is simple.

Proof. Let p be a given type. By Monotonicity, we have D[ p, Δ, k] < ∞ for every Δ finite and k < ω. Fix Δ finite, k < ω, and a finite type q_{Δ,k} ⊆ p, such that

D[ p, Δ, k] = D[ q_{Δ,k}, Δ, k]. (*)

Let

q := ⋃{ q_{Δ,k} | Δ ⊆ L(T), Δ finite, k < ω } ⊆ p  and  B := dom(q).

Then |B| ≤ |T |, and since p ⊢ q ⊢ q_{Δ,k}, by (*) we have

(**) D[ p, Δ, k] = D[ q, Δ, k], for every finite Δ and k < ω.

We will show that p does not fork over B.

Suppose p forks over B. Then there exists φ(x̄, ā) such that p ⊢ φ(x̄, ā), and φ(x̄, ā) forks over B. Since p ⊢ q ∪ φ(x̄, ā) ⊢ q,

D[ p, Δ, k] ≤ D[ q ∪ φ(x̄, ā) , Δ, k] ≤ D[ q, Δ, k], for every finite Δ and k < ω.

Therefore, by (**),

D[ q ∪ φ(x̄, ā) , Δ, k] = D[ q, Δ, k], for every finite Δ and k < ω.

This contradicts Lemma 3.5 since q is over B. ⊣

Lemma 3.7. Let p(x̄) be a set of formulas, possibly with parameters, let φ(x̄, ȳ) be a formula, k < ω, and α be an ordinal. The following conditions are equivalent:

(1) D[ p, φ, k] ≥ α;

(2) There exists { ā_{η} | η ∈ ^{α>}ω } such that (a) For every η ∈ ^{α}ω, the set p ∪ { φ(x̄, ā_{η↾β}) | β < α} is consistent;

(b) For every η ∈ ^{α>}ω, the set { φ(x̄, ā_{ηˆ n}) | n < ω} is k-contradictory.

Proof. By induction on α. ⊣

To show a rather strong converse of Theorem 3.6, we make the next definition.

Definition 3.8. A theory T had the tree property if there exist a formula φ(x̄, ȳ), an integer k < ω, and { ā_{η} | η ∈ ^{ω>}ω } such that

(1) For every η ∈ ^{ω}ω, the set { φ(x̄, ā_{η↾l}) | l < ω} is consistent;

(2) For every η ∈ ^{ω>}ω, the set { φ(x̄, ā_{ηˆ n}) | n < ω} is k-contradictory.

Theorem 3.9. Suppose that T has the tree property. Then, for every cardinal κ there exists a type p such that p forks over all subsets of cardinality κ of its domain.

Proof. Let κ be given and let μ = (2^{κ+|T |})^{+}. Let φ and k < ω witness this. By compactness, we can find { ā_{η} | η ∈ ^{κ^{+}>}μ } such that

(1) For every η ∈ ^{κ^{+}}μ, the set { φ(x̄, ā_{η↾β}) | β < κ^{+}} is consistent;

(2) For every η ∈ ^{κ^{+}>}μ, the set { φ(x̄, ā_{ηˆ i}) | i < μ} is k-contradictory.

By the pigeonhole principle and compactness, there exist { b̄_{η} | η ∈ ^{κ^{+}>}ω } such that

(3) For every η ∈ ^{κ^{+}}ω, the set { φ(x̄, b̄_{η↾β}) | β < κ^{+}} is consistent;

(4) For every η ∈ ^{κ^{+}>}ω, the set { φ(x̄, b̄_{ηˆ n}) | n < ω} is k-contradictory;

(5) For every η ∈ ^{κ^{+}>}ω and every n < ω,

tp(b̄_{ηˆ 0}/ ⋃{ b̄_{ν} | ν ≤ η }) = tp(b̄_{ηˆ n}/ ⋃{ b̄_{ν} | ν ≤ η }).

Let η ∈ ^{κ^{+}}ω and consider the set p := { φ(x̄, b̄_{η↾β}) | β < κ^{+}} (which is a type by (3)). For every subset A of dom(p) of cardinality at most κ there is α < κ^{+} such that p ↾ A ⊆ { φ(x̄, b̄_{η↾β}) | β ≤ α}. By (4) and (5), p divides, and hence forks over A. ⊣

The next corollary gathers several characterizations of simplicity.

Corollary 3.10. The following conditions are equivalent:

(1) T is simple;

(2) κ(T) < ∞;

(3) T does not have the tree property;

(4) D[ x̄ = x̄, Δ, k] < ∞, for every finite Δ and every k < ω;

(5) D[x̄ = x̄, Δ, k] < ω, for every finite Δ and k < ω.

Proof. (1) implies (2) is trivial. The equivalence of (3), (4), and (5) is by the compactness theorem and Lemma 3.7 (and coding finite sets of formulas by a single formula). (4) implies (1) is Theorem 3.6. ¬ (3) implies ¬ (2) is Theorem 3.9. ⊣

We now turn to the connection with stability. As we will see in Theorem 3.13, any stable theory is simple. However, there are important examples of simple unstable theories. Historically, the motivating example was T_{ind}, the theory of the countable random graph.

There are several equivalent formulations of model theoretical stability. One of them is via the following rank. Recall that the types p and q are explicitly contradictory if there exists φ(x̄, b̄) such that φ(x̄, b̄) ∈ p and ¬φ(x̄, b̄) ∈ q (or vice versa).

Definition 3.11. Let p(x̄) be a set of formulas, possibly with parameters. Let Δ be a set of formulas. We define the rank R[p, Δ, ℵ_{0}]. The rank R[p, Δ, ℵ_{0}] is either an ordinal, or −1, or ∞. The relation R[p, Δ, ℵ_{0}] ≥ α, is defined by induction on α.

(1) R[p, Δ, ℵ_{0}] ≥ 0 if p is consistent;

(2) R[p, Δ, ℵ_{0}] ≥ δ when δ is a limit if R[p, Δ, ℵ_{0}] ≥ β for every β < δ;

(3) R[p, Δ, ℵ_{0}] ≥ α + 1 if for every finite r ⊆ p there exists a set of Δ-types { q_{i} | i < ω } such that:

(a) R[r ∪ q_{i}, Δ, ℵ_{0}] ≥ α for every i < ω;

(b) The types q_{i} and q_{j} are explicitly contradictory if i ≠ j < ω. We write R[p, Δ, ℵ_{0}] = −1 if p is not consistent; R[p, Δ, ℵ_{0}] = α when R[p, Δ, ℵ_{0}] ≥ α but R[p, Δ, ℵ_{0}] ≱ α + 1; R[p, Δ, ℵ_{0}] = ∞ when R[p, Δ, ℵ_{0}] ≥ α for every ordinal α.

The following fact follows from Theorems 2.2 and 2.13 of Chapter II in [Sha].

Fact 3.12. T is stable if and only if R[x̄ = x̄, Δ, ℵ_{0}] < ω for every finite set of formulas Δ.

Theorem 3.13. Let T be a (complete) first order theory. If T is stable, then T is simple.

Proof. Using Fact 3.12 it suffices to show that for every finite Δ and every k < ω,

D[x̄ = x̄, Δ, k] ≤ R[x̄ = x̄, Δ, ℵ_{0}].

We shall show by induction on the ordinal α that for every type p, every finite set of formulas Δ, and every k < ω

D[p, Δ, k] ≥ α implies R[p, Δ, ℵ_{0}] ≥ α.

When α = 0 or α is a limit ordinal, the implication is obvious. Suppose D[p, Δ, k] ≥ α + 1. Let r ⊆ p be finite subtype. Then there exist a formula φ ∈ Δ and { ā_{i} | i < ω } such that the set { φ(x̄, ā_{i}) | i < ω } is k-contradictory, and D[r ∪ φ(x̄, ā_{i}), Δ, k] ≥ α for every i < ω. Let A := ⋃{ ā_{i} | i < ω }. By Lemma 3.4, for every i < ω there exists q_{i} ∈ S_{Δ}(A) such that

D[r ∪ φ(x̄, ā_{i}) ∪ q_{i}, Δ, k] ≥ α, for every i < ω.

Therefore, by the induction hypothesis,

R[r ∪ φ(x̄, ā_{i}) ∪ q_{i}, Δ, ℵ_{0}] ≥ α, for every i < ω.

Now, since { φ(x̄, ā_{i}) | i < ω } is k-contradictory and φ(x̄, ā_{i}) ∈ q_{i}, any k-element subset of { q_{i} | i < ω } contains two types that are explicitly contradictory. Hence, there exists an infinite S ⊆ ω such that for any i ≠ j in S the Δ-types q_{i} and q_{j} are explicitly contradictory. By definition, we must have R[r, Δ, ℵ_{0}] ≥ α + 1, which finishes the induction. ⊣

Shelah’s original definition of the rank in [Sh93] is more general than that in Definition 3.1. We now compare both definitions and derive a few facts.

Definition 3.14. Let p(x̄) be a set of formulas, possibly with parameters. Let Δ be a set of formulas, k < ω and λ a cardinality (not necessarily infinite). We define the rank D[p, Δ, k, λ]. The rank D[p, Δ, k, λ] is either an ordinal, or −1, or ∞. The relation D[p, Δ, k, λ] ≥ α, is defined by induction on α.

(1) D[p, Δ, k, λ] ≥ 0 if p is consistent;

(2) D[p, Δ, k, λ] ≥ δ when δ is a limit if D[p, Δ, k, λ] ≥ β for every β < δ; (3) D[p, Δ, k, λ] ≥ α + 1 if for every finite r ⊆ p and every μ < λ there

exist a formula φ(x̄, ȳ) ∈ Δ and a set { ā_{i} | i < μ } with ℓ(ā_{i}) = ℓ(ȳ) such that:

(a) D[r ∪ φ(x̄, ā_{i}) , Δ, k, λ] ≥ α for every i < μ;

(b) The set { φ(x̄, ā_{i}) | i < μ } is k-contradictory. As usual, we write

D[p, Δ, k, λ] = −1 if p is not consistent;

D[p, Δ, k, λ] = α when D[p, Δ, k, λ] ≥ α but D[p, Δ, k, λ] ≱ α + 1; D[p, Δ, k, λ] = ∞ when D[p, Δ, k, λ] ≥ α for every ordinal α.

Remark 3.15. Clearly, we have the equality D[p, Δ, k] = D[p, Δ, k, ℵ_{1}], and the function D[p, Δ, k, ·] is nonincreasing. The statements of Proposition 3.2 are also true for this new definition. The Ultrametric Property (Lemma 3.3) holds for D[p, Δ, k, λ], when λ is uncountable.

Proposition 3.16. Let p be finite, φ be a formula, k < ω, n < ω and λ = μ^{+} (or μ + 1 when μ is finite). Then D[p, φ, k, λ] ≥ α if and only if the union of the following sets of formulas is consistent:

· { p(x̄_{η}) | η ∈ ^{α}μ };

· { ¬∃x̄ ⋀_{i∈w} φ(x̄; ȳ_{ηˆ i}) | w ⊆ μ, |w| = k, η ∈ ^{α>}μ };
· { φ(x̄_{η}; ȳ_{η↾(l+1)}) | η ∈ ^{n}μ, l < α }.

Proof. Immediate from Definition 3.14. ⊣

Corollary 3.17. Let p be a type, Δ be a finite set of formulas and k < ω. The following conditions are equivalent:

(1) D[p, Δ, k] ≥ n;

(2) D[p, Δ, k, m] ≥ n for every m < ω.

Proof. When p is finite, the statement follows from from Proposition 3.16. The general case follows immediately by compactness. ⊣

Corollary 3.18. Let p be a type, Δ be a finite set of formulas, and k < ω.Then,

D[p, Δ, k, λ] = D[p, Δ, k], for every λ > ℵ_{0}.

Proof. We may assume that Δ = {φ}. Clearly D[p, Δ, k, λ] ≤ D[p, Δ, k]. The reverse inequality follows by Finite Character and Proposition 3.16. ⊣

Remark 3.19. Proposition 3.16 implies that if λ, Δ, and α are finite, then for every ψ(x̄; ȳ) the set

{ b̄ | D[{ψ(x̄; b̄)}, Δ, k, λ] = α }

is first order definable in ℭ.

Corollary 3.20. In Definition 3.1 we can add at the successor stage the condition

(c) ⟨ ā_{i} | i < ω ⟩ is indiscernible over dom(p).

Proof. We wish to prove that if D[p, Δ, k] ≥ α+1, then for every finite r ⊆ p there exist φ ∈ Δ and a sequence ⟨ ā_{i} | i < ω ⟩ indiscernible over dom(p) such that { φ(x̄, ā_{i}) | i < ω } is k-contradictory and

(1) D[r ∪ φ(x̄, ā_{i}), Δ, k] ≥ α, for every i < ω.

Let A := dom(p) and fix k < ω. Let χ := (2^{|A|+|T |})^{+} and λ := (ℶ_{χ})^{+}. By Corollary 3.18, we have

D[p, Δ, k, λ] = D[p, Δ, k] ≥ α + 1.

Hence, for every finite r ⊆ p there exist a formula φ ∈ Δ and a set { b̄_{i} | i < ℶ_{χ} } such that { φ(x̄, b̄_{i}) | i < ℶ_{χ} } is k-contradictory and

(*) D[r ∪ φ(x̄, b̄_{i}), Δ, k, λ] ≥ α, for every i < ℶ_{χ}.

Theorem 1.13 provides a sequence ⟨ ā_{i} | i < ω ⟩ indiscernible over A such that for every n < ω there exist i_{1} < ⋯ < i_{n} < ℶ_{χ} satisfying

tp(ā_{0}, …, ā_{n−1}/A) = tp(b̄_{j_{1}}, …, b̄_{j_{n}}/A). (**)

Clearly, (∗∗) guarantees that { φ(x̄, ā_{i}) | i < ω } is k-contradictory. Now, (∗), (∗∗), and Invariance imply

D[r ∪ φ(x̄, ā_{i}), Δ, k] ≥ α, for every i < ω.
⊣

We can now show the converse of Lemma 3.5. This provides an alternative characterization of forking in simple theories.

Theorem 3.21. Let T be simple. Let p be a type over B and A ⊆ B. The following conditions are equivalent:

(1) p does not fork over A;

(2) D[p, Δ, k] = D[p ↾ A, Δ, k], for every k < ω and Δ finite.

Proof. (2) ⇒ (1) is Lemma 3.5.

(1) ⇒ (2). By Finite Character, we may assume that B = A ∪ b̄ for some tuple b̄. We show by induction on α that

D[p ↾ A, Δ, k] ≥ α implies D[p, Δ, k] ≥ α.

When α = 0 or α is a limit ordinal, the implication is easy. Suppose that

D[p ↾ A, Δ, k] ≥ α + 1.

By Corollary 3.20, we can find a formula φ ∈ Δ and a sequence ⟨ ā_{i} | i < ω ⟩ indiscernible over A such that { φ(x̄, ā_{i}) | i < ω } is k-contradictory and

(*) D[(p ↾ A) ∪ φ(x̄, ā_{i}), Δ, k] ≥ α, for every i < ω.

By the definition of the rank, it suffices to show that the sequence ⟨ ā_{i} | i < ω ⟩ can be chosen so that

(**) D[p ∪ φ(x̄, ā_{i}), Δ, k] ≥ α, for every i < ω.

Using Lemma 3.4, we find c̄_{i} for i < ω realizing (p ↾ A) ∪ φ(x̄, ā_{i}) such that

D[tp(c̄_{i}/A ∪ ā_{i}), Δ, k] ≥ α.

Now, using Theorem 1.13 (as in the proof of Corollary 3.20), we may assume that the sequence ⟨ c̄_{i}, ā_{i} | i < ω ⟩ is indiscernible over A. Let d̄_{0} realize p and take f ∈ Aut_{A}(ℭ) be such that f(c̄_{0}) = d̄_{0}. By replacing c̄_{i} and ā_{i} with f(c̄_{i}) and f(ā_{i}), we may also assume that c̄_{0} realizes p. Since, by hypothesis, tp(c̄_{0}/Ab̄) does not fork over A, the type tp(b̄/Ac̄_{0}) does not fork over A by Symmetry. Now, using Extension and an Ac̄_{0}-automorphism, we may further assume that tp(b̄/Ac̄_{0}ā_{0}) does not fork over A. Since forking and dividing are equivalent for simple theories, we can use Lemma 1.5 and an Ac̄_{0}ā_{0}-automorphism to assume that

(†) ⟨ c̄_{i}, ā_{i} | i < ω ⟩ is indiscernible over B.

Using now Extension and an Ac̄_{0}ā_{0}-automorphism, we may further assume that

(‡) tp(b̄/A ∪ { c̄_{i}, ā_{i} | i < ω }) does not fork over A.

¿From (†) and the fact that c̄ realizes p, we conclude that c̄_{i} realizes p for every i < ω. By (‡) and Symmetry, the type tp(c̄_{i}/Bā_{i}) does not fork over A for any i < ω. Therefore, by Monotonicity, p ∪ φ(x̄, ā_{i}) does not fork over A, for any i < ω. Thus, by induction hypothesis, D[p, Δ, k] ≥ α + 1. ⊣

4. Shelah’s Boolean Algebra

The argument we present in this section differs from [Sh93] only in that we use a different partial order. The partial order considered in [Sh93] is defined through weak dividing; here we use forking. The proof of the chain condition was communicated to us by Shelah in a recent correspondence. It uses the Independence Theorem (Theorem 2.11). We are grateful to Shelah for allowing us to include it here.

Recall that a pair of cardinals (λ, κ) is in SP(T) if every model of cardinality λ has a κ-saturated elementary extension of the same cardinality. (See the introduction.)

Definition 4.1. Let p(x̄) be a type over C and A be a set containing C. We define

W (p, A) := { φ(x̄; ā) | φ(x̄; ā) ∪ p is a non-forking extension of p, ā ∈ A }.

We identify two formulas φ(x̄; b̄) and ψ(x̄; c̄) when φ(ℭ; b̄) = ψ(ℭ; c̄). By abuse of notation we denote by φ(x̄; b̄) the above equivalence class determined by the formula φ(x̄; b̄) in W (p, A).

The set W (p, A) is partially ordered by

φ(x̄; b̄) ≤ ψ(x̄; c̄) if and only if ψ(x̄; c̄) ⊢ φ(x̄; b̄).

Remark 4.2. Notice that meet in the poset W (p, A) corresponds to logical disjunction of formulas. Thus for φ, ψ ∈ W (p, A) the expression φ · ψ stands for the definable set defined by the formula φ ∨ ψ.

Proposition 4.3. Suppose C ⊆ A and p ∈ S(C). Then the partially ordered set

⟨W (p, A), ≤⟩

is a distributive lower semi-lattice.

Proof. It suffices to show that W (p, A) is closed under finite disjunctions, but this is an obvious property of forking. ⊣

We will say that two formulas φ, ψ ∈ W (p, A) are incompatible if there is no ρ ∈ W (p, A) such that ρ ≥ φ and ρ ≥ ψ, i.e., there is no ρ ⊢ φ and ρ ⊢ ψ such that p ∪ ρ is a nonforking extension of p.

Proposition 4.4. The formulas φ(x̄; b̄), ψ(x̄; c̄) ∈ W (p, A) are compatible if and only if φ(x̄; b̄) ∧ ψ(x̄; c̄) ∈ W (p, A).

Proof. Sufficiency is trivial. To prove the converse, let ρ(x̄; d̄) be such that ρ ≥ φ and ρ ≥ ψ. By definition, ρ(x̄; d̄) ⊢ φ(x̄; b̄) and ρ(x̄; d̄) ⊢ ψ(x̄; c̄). Therefore, ρ(x̄; d̄) ⊢ [φ(x̄; b̄) ∧ ψ(x̄; c̄)]. Since ρ(x̄; d̄) does not fork over p, also φ(x̄; b̄) ∧ ψ(x̄; c̄) does not fork over p. ⊣

We will use some facts about the completion of partially ordered sets to boolean algebras. In particular, we need to recall the following notion. A partially ordered set ⟨P, ≤⟩ is separative if for every p, q ∈ P such that p ≰ q there exists r ∈ P with r ≰ q and p ≰ r.

Fact 4.5. If ⟨P, ≤⟩ is separative, there exists a unique complete boolean algebra B containing P such that

(1) The order of B extends that of P;

(2) P is dense in B.

For the proof, see Lemma 17.2 in Thomas Jech’s book [Je].

Notice that since the W (p, A) is in general not closed under conjunctions, the partially ordered set W (p, A) is not separative. However, the following fact (Lemma 17.3 of [Je]) allows us to circumvent this difficulty.

Fact 4.6. Let ⟨P, ≤_{P} ⟩ be an arbitrary partially ordered set. Then there exist a unique separative partially ordered set ⟨Q, ≤_{Q}⟩ and a function h : P → Q such that

(1) h[P] is dense in Q;

(2) If p ≤_{P} q, then h(p) ≤_{Q} h(q);

(3) p and q are compatible in P if and only if h(p) and h(q) are compatible in Q.

¿From Facts 4.5 and 4.6 one gets:

Corollary 4.7. Let C ⊆ A be sets and p ∈ S(C). Then there exist a unique complete boolean algebra B_{p,A} and a function e_{p}: W (p, A) → B_{p,A} such that

(1) If φ(x̄; b̄) ⊢ ψ(x̄; c̄), then e_{p}(ψ) ≤_{B_{p,A}} e_{p}(φ); (2) The formulas φ(x̄; b̄) and ψ(x̄; c̄) are compatible in W (p, A) if and

only if in B_{p,A}

e_{p}(φ(x̄; b̄)) · e_{p}(ψ(x̄; c̄)) ≠ 0;

(3) The image of W (p, A) under e_{p} is dense in B_{p,A}.

In [Sh 80], Shelah introduced a generalization of Martin’s Axiom that consistently holds above the continuum. He denotes that principle by (Ax_{0}μ). The tradeoff is that the countable chain condition is replaced by stronger requirements, namely,

· The forcing notion is complete, and

· The forcing conditions are essentially compatible on a club. For a more complete description see [Sh 80]. The proof is a variant of the traditional finite support iteration used to show that the consistency of ZFC+GCH implies the consistency of ZFC+¬CH + MA.

In [Sh93] Shelah claims that if the ground model satisfies GCH, then for a class of regular cardinalities R (such that for every μ ∈ R the next element of R is much larger than μ) there exists a generic extension preserving cardinals and cofinalities such that

(1) (Ax_{0}μ) holds;

(2) 2^{μ} >> μ^{+} and μ^{<μ} = μ, for every cardinal μ ∈ R. The construction is by class forcing.

Recall that a boolean algebra is said to have the μ-chain condition if the size of every antichain is less than μ.

Rather than stating (Ax_{0}μ) specifically, we will quote as a fact the only consequence of it that we will use. The enthusiastic reader can find a complete proof of the following in Lemma 4.13 of [Sh93].

Fact 4.8. Suppose (Ax_{0}μ) and μ^{<μ} = μ holds. Let B be a boolean algebra of cardinality less than 2^{μ} satisfying the μ-chain condition. Then B − {0} is the union of μ ultrafilters.

Corollary 4.7 will be used together with Fact 4.8 to find κ-saturated elementary extensions of models of a simple theory.

In order to apply Fact 4.8 we need to show that for C ⊆ A and p ∈ S(C), the boolean algebra B_{p,A} has the μ^{+}-chain condition. Notice that, below, μ is independent of A and depends only on |C| + |T |.

Shelah [Sh93] had characterized simplicity in terms of a bound on the number of pairwise inconsistent types of size μ over a set of cardinality λ. Casanovas [Ca] extended this and characterized supersimplicity. In [Le] the third author used an extension of the chain condition to improve those bounds and characterize not only simplicity, but also κ(T): If a theory T is simple then the number of pairwise inconsistent types of size μ over a set of cardinality λ is at most λ^{<κ(T)} + 2^{μ+|T |}. Conversely, the existence of such a bound (for a given cardinal κ instead of κ(T)) implies that the theory is simple and κ(T) ≤ κ. Furthermore, similarly to [KP1], it is shown in [Le] that a theory is simple if and only if it has a dependence relation satisfying Invariance, Finite Character, Extension, Local Character, Symmetry, Transitivity, and the Chain Condition.

Theorem 4.9 (Shelah 1998). Let T be simple. For every C, A such that C ⊆ A and every p ∈ S(C) the partially ordered set W (p, A) has the (2^{|T |+|C|})^{+}-chain condition.

Proof. Let λ = (2^{|T |+|C|})^{+} and fix { φ_{i}(x̄; ā_{i}) | i < λ } ⊆ W (p, A). We will show that { φ_{i}(x̄; ā_{i}) | i < λ } is not an antichain by finding i < j < λ such that

p ∪ { φ_{i}(x̄; ā_{i}), φ_{j}(x̄; ā_{j}) } does not fork over C.

To this end, choose ⟨M_{i} | i < λ⟩ an increasing, continuous chain of models such that:

(1) C ⊆ M_{0};

(2) ā_{i} ∈ M_{i+1}, for i < λ;

(3) ∥M_{i}∥ = 2^{|T |+|C|}, for i < λ; Consider the following stationary subset of λ.

S := { δ < λ | cf δ = |T |^{+} }.

Define a function f: S → λ by

f(δ) := min{ j | tp(ā_{δ}/M_{δ}) does not fork over M_{j} }.

Since T is simple, for every δ ∈ S there exists B ⊆ M_{δ} of cardinality at most |T | such that tp(ā_{δ}/M_{δ}) does not fork over B. Since cf δ = |T |^{+}, there is j < δ such that B ⊆ M_{j}. This shows that f(δ) < δ for every δ ∈ S. Hence, by Fodor’s Lemma ([Je], Theorem 1.7.22), there exists a stationary S^{∗} ⊆ S and a fixed j < λ such that tp(ā_{δ}/M_{δ}) does not fork over M_{j}, for every δ ∈ S^{∗}. Without loss of generality, we may assume that S^{∗} = λ and j = 0, i.e.,

tp(ā_{i}/M_{i}) does not fork over M_{0}, for every i < λ.

By simplicity (see Theorem 3.6), for every i < λ there exists N_{i} ≺ M_{0} of cardinality |C| + |T | such that N_{i} contains C and tp(ā_{i}/M_{i}) does not fork over N_{i}. But, there are at most 2^{|C|+|T |} subsets of M_{0} of cardinality |C|+|T |. Hence, by the pigeonhole principle, there exists a subset S^{∗} ⊆ λ of cardinality λ and a model N ≺ M_{0} of cardinality |C|+|T | such that N_{i} = N for every i ∈ S^{∗}. Without loss of generality, we may assume that S^{∗} = λ, i.e.,

(*) tp(ā_{i}/M_{i}) does not fork over N, for every i < λ.

Now, p ∪ φ_{i}(x̄; ā_{i}) does not fork over C by definition. Hence, by Extension, we can find q_{i} ∈ S(Nā_{i}) extending p ∪ φ_{i}(x̄; ā_{i}) such that

(**) q_{i} does not fork over C, for every i < λ.

But, |S(N)| ≤ 2^{|C|+|T |}, so, by the pigeonhole principle again, there exists a subset S^{∗} ⊆ λ of cardinality λ and a type q ∈ S(N) such that q_{i} ↾ N = q for every i ∈ S^{∗}. Without loss of generality, we may assume that S^{∗} = λ, i.e.,

q_{i} ↾ N = q, for every i < λ.

Thus, by the choice of q_{i},

q ∪ φ_{i}(x̄; ā_{i}) is a nonforking extension of q ∈ S(N),  for every i < λ. (***)

Now, fix i < j < λ. Recall that ā_{i} ∈ M_{j} (by (2)) and N ≺ N_{j}. Therefore, by (*) and Monotonicity, we conclude that

(†) tp(ā_{j}/Nā_{i}) does not fork over N.

But now, the Independence Theorem (Theorem 2.11) applied to (***) and (†) shows that

(‡) q ∪ { φ_{i}(x̄; ā_{i}), φ_{j}(x̄; ā_{j}) } does not fork over N.

By (**), (‡) and Transitivity,

q ∪ { φ_{i}(x̄; ā_{i}), φ_{j}(x̄; ā_{j}) } does not fork over C.

Thus, p ∪ { φ_{i}(x̄; ā_{i}), φ_{j}(x̄; ā_{j}) } does not fork over C by Monotonicity. ⊣

Corollary 4.10. Let T be simple. Let C ⊆ A and p ∈ S(C). Then the boolean algebra B_{p,A} has the (2^{|T |+|C|})^{+}-chain condition.

Proof. By Theorem 4.9 and Corollary 4.7. ⊣

The following facts are fairly well-known.

Fact 4.11. Let λ and κ be infinite cardinals.

(1) Let λ ≥ 2^{|T |}. If λ^{<κ} = λ, then (λ, κ) ∈ SP(T).

(2) Let λ ≥ 2^{|T |}. If λ^{<λ} > λ, then (λ, λ) ∈ SP(T) if and only if T is stable in λ.

(1) Holds just by the standard construction of saturated model using only cardinal arithmetic (without assumptions on the theory T), see Theorem I.1.7(2) of [Sha]. Victor Harnik in [Ha] have shown that if T is stable in λ then it has a saturated model of cardinality λ (this result is reproduced as Theorem III.3.12 in [Sha]). The argument can be used to show that when T is stable in λ then (λ, κ) ∈ SP(T) for all κ ≤ λ, and that the case λ = κ is completely understood. The other implication in (2) follows from Theorem VIII.4.7 of [Sha].

Observe that (1) below implies that the problem of characterizing when (λ, κ) ∈ SP(T) is open only when λ^{<κ} > λ. (2) implies that the problem of characterizing the pairs (λ, κ) such that (λ, κ) ∈ SP(T) is interesting only for κ < λ with λ^{<κ} > λ and T unstable. Observe also that (λ, κ) ∈ SP(T) implies λ ≥ |D(T)|.

We now proceed to the proof of the main theorem. We will first prove three simple propositions. The reader may want to skip to Theorem 4.16 below before reading the proofs of Propositions 4.12, 4.14, and 4.15.

Proposition 4.12. Let λ > κ. Then (λ, κ) ∈ SP(T) if and only if the following property holds.

(♦): For every set A of cardinality λ there exists S ⊆ S(A) of cardinality λ such that every type over a subset of A of cardinality less than κ has an extension in S.

Proof. Sufficiency is clear. To prove necessity, let M be a model of cardinality λ and construct an increasing and continuous sequence of models ⟨M_{i} | i < κ^{+}⟩, such that

(1) M_{0} = M;

(2) ∥M_{i}∥ = λ, for every i < κ^{+};

(3) M_{i+1} realizes every type over subsets of M_{i} of cardinality less than κ. We let N = ⋃_{i<κ^{+}} M_{i}. Then N is a κ-saturated extension of M of cardinality λ. ⊣

Remark 4.13. Proposition 4.12 can be regarded as a statement about the boolean algebras B_{p,A} as follows. Let p ∈ S(C) and suppose q ∈ S(A) extends p and does not fork over C. Then, q ⊆ W (p, A) ⊆ B_{p,A}, and q has the finite intersection property. Conversely, if F ⊆ B_{p,A} is an ultrafilter, then the set of formulas

q_{F} = { φ(x, ā) ∈ W (p, A) | There exists e ∈ F with φ(x, ā) ≤ e }

is a complete type extending p which does not fork over C.

Proposition 4.14. Suppose that T is simple, and let λ and κ be cardinals such that λ, κ ≥ κ(T) and λ^{<κ(T)} = λ ≥ |D(T)|. Then (λ, κ) ∈ SP(T) if the following property holds.

(♦♦): For every set A of cardinality λ and every complete type p over a subset of A of cardinality less than κ(T) the boolean algebra B_{p,A} contains a family 𝔇_{p,A} of cardinality λ of ultrafilters of B_{p,A}, such that every subset of B_{p,A} of cardinality less than κ with the finite intersection property can be extended to an ultrafilter in 𝔇_{p,A}.

Proof. We show that Condition (♦♦) implies Condition (♦) of Proposition 4.12. Since λ^{<κ(T)} = λ, there are only λ subsets of A of cardinality κ(T). Since λ ≥ |D(T)|, there are at most λ complete types over every of these subsets. Therefore there are only λ boolean algebras of the formB_{p,A}. Thus,

| ⋃_{p,A} 𝔇_{p,A}| = λ (†)

Now let S ⊆ S(A) be the set of types of the form

q_{F} = { φ(x, ā) ∈ W (p, A) | There exists e ∈ F with φ(x, ā) ≤ e },

where F ∈ ⋃_{p,A} 𝔇_{p,A}. We claim that S satisfies Condition (♦). By (†), S has cardinality λ. Now, let q be a type over a subset of A of cardinality less than κ. Then, q does not fork over a subset C of A of cardinality less than κ(T). Let p = q ↾ C. Thus, q is a subset of W (p, A) of cardinality less than κ with the finite intersection property, so by (♦♦), there exists an ultrafilter F in D_{p,A} extending q. This implies that q_{F} extends q, as required. ⊣

Proposition 4.15. Suppose that μ = μ^{<κ}. Let B be a boolean algebra. Assume that there exists a family 𝔉 of cardinality μ of ultrafilters of B such that B − {0} = ⋃ 𝔉. Then, there exists a family of ultrafilter 𝔇 of B of cardinality μ satisfying the following property.

(♦♦♦): Every subset of B of cardinality less than κ with the finite intersection property can be extended to an ultrafilter in 𝔇.

Proof. Let 𝔉 be as in the hypothesis. Let us write 𝔉 = { F_{i} | i < μ }. To construct 𝔇, let us consider for every χ < κ the family I_{χ} of finite subsets of χ, and for α < κ let I_{χ}(α) be the set { t ∈ I_{χ} | α ∈ t }. Notice that { I_{χ}(α) | α < κ } is closed under finite intersections, so we can pick an ultrafilter E_{χ} ⊆ P(I_{χ}) extending { I_{χ}(α) | α < κ }.

Given χ < κ and a function f : I_{χ} → μ, define D_{f} ⊆ B as follows:

a ∈ D_{f} if and only if { t ∈ I_{χ} | a ∈ F_{f(t)} } ∈ E_{χ}.

We prove that D_{f} is an ultrafilter of B.

Given a ∈ B, let S_{a} = { t ∈ I_{χ} | a ∈ F_{f(t)} }. We show that D_{f} is upwardly closed. Suppose that a ∈ D_{f} and b ≥ a is in B. Since F_{f(t)} is a filter, a ∈ F_{f(t)} and a ≤ b, imply b ∈ F_{f(t)}. Thus, S_{a} ⊆ S_{b}. But E_{χ} is a filter, so S_{a} ∈ E_{χ}, implies S_{b} ∈ E_{χ}. Therefore, b ∈ D_{f}.

D_{f} is also closed under ∧. Suppose a, b ∈ D_{f}. Then S_{a}, S_{b} ∈ E_{χ}, so S_{a} ∩ S_{b} ∈ E_{χ} since E_{χ} is a filter. But, a, b ∈ F_{f(t)}, implies a ∧ b ∈ F_{f(t)} since F_{f(t)} is a filter. Hence, S_{a} ∩ S_{b} ⊆ S_{a∧b} and S_{a∧b} ∈ E_{χ}, since E_{χ} is a filter. Thus, a ∧ b ∈ D_{f}.

Now we show that D_{f} is maximal: Suppose a ∈ B −D_{f}. By the definition of S_{a} and since E_{χ} is an ultrafilter, we have S_{a} ∉ E_{χ}. Therefore, we must have { t ∈ I_{χ} | a ∉ F_{f(t)} } ∈ E_{χ}. Since F_{f(t)} is an ultrafilter, we must have S_{1−a} ∈ E_{χ}, that is, 1 − a ∈ D_{f}.

Thus, D_{f} is an ultrafilter. Define

𝔇 := { D_{f} | χ < κ, f : I_{χ} → μ }.

Notice that |𝔇| ≤ κ · ∑_{χ<κ} μ^{χ} ≤ μ^{<κ} = μ. It remains to show that 𝔇 satisfies (♦♦♦).

Suppose that D := { a_{i} | i < χ < κ } ⊆ B has the finite intersection property. For every t ∈ I_{χ} let a_{t} := ⋀_{j∈t} a_{j}. Then a_{t} ≠ 0. Let f: I_{χ} → μ be defined by

f(t) := min{ i < μ | a_{t} ∈ F_{i} }.

(Our assumption on on 𝔉 guarantees that fis well-defined.) We now check that D ⊆ D_{f}. Take a_{i} ∈ D. Then a_{i} ≥ a_{t}, for t ∈ I_{χ}(i). But a_{t} ∈ F_{f(t)} by the definition of f, so a_{i} ∈ F_{f(t)} since F_{f(t)} is a filter. We have shown that

I_{χ}(i) ⊆ { t ∈ I_{χ} | a_{i} ∈ F_{f(t)} }.

But I_{χ}(i) ∈ E_{χ} and E_{χ} is a filter, so

{ t ∈ I_{χ} | a_{i} ∈ F_{f(t)} } ∈ E_{χ}.

Hence, a_{i} ∈ D_{f}. ⊣

We can now prove the theorem.

Theorem 4.16. Let T be simple. Let λ = λ^{|T |} > κ > |D(T)| and suppose that there exists μ > 2^{|T |} such that (Ax_{0}μ) holds and μ = μ^{<μ} ≤ λ < 2^{μ}. Then (λ, κ) ∈ SP(T).

Proof. By Theorem 3.6 κ(T) ≤ |T |^{+}, so the assumption on λ, guarantees that λ^{<κ(T)} = λ. Therefore, by Proposition 4.14 it suffices to show that given A of cardinality λ, C ⊆ A of cardinality κ(T) and p ∈ S(C) there is a family of ultrafilters satisfying Condition (♦♦) of Proposition 4.14. By Proposition 4.15, it suffices to show that for any boolean algebra B_{p,A} and any subalgebra B′_{p,A} ≤ B_{p,A} of cardinality λ containing W (p, A) there exists a family of ultrafilters 𝔉 of B′_{p,A} of cardinality μ such that B′_{p,A} −{0} = ⋃ 𝔉.

Since T is simple, the boolean algebra B_{p,A} satisfies the (2^{|C|+|T |})^{+}-chain condition by Corollary 4.7. Since |C| ≤ |T |, |B′_{p,A}| = λ < 2^{μ} and μ > 2^{|T |}, the algebra B′_{p,A} satisfies the μ-chain condition. But, since |W (p, A)| = λ, Fact 4.8 implies the existence of a family of ultrafilters 𝔉 as desired. ⊣

Appendix A. A Better Bound for Theorem 1.13

Theorem 1.13 had a crucial role in producing Morley sequences. In this Appendix we improve the bound on the length of the sequence in the hypothesis of the theorem. This also improves Shelah’s result from [Sh93].

We find it interesting to note that potentially there is here an interesting issue for Friedman’s reverse mathematics: While all the classical results about the main dichotomies (stability, superstability, dop, otop, independence property etc) depend on the existence of very small cardinals. Namely, all the theory can be developed inside the structure ⟨H(χ), ∈⟩ for χ = (ℶ_{2}(|T |))^{+}. It seems to be strange that a basic fact like existence of a Morley sequence requires existence of relatively large cardinals like ℶ_{(2^{|T |})^{+}}. We think that in either case an answer to the following question is interesting.

Question A.1. Is it possible to carry out the arguments of the first 3 sections in ⟨H(χ), ∈⟩ for χ = (ℶ_{2}(|T |))^{+}?

Notice that the question is a distant relative of Problem 2.20 from Shelah’s list of open problems ([Sh 702]).

Below is an attempt to make progress on this question. We do manage to lower much (in some cases) the bound ℶ_{(2^{|T |})^{+}} but we are still very far from being able to answer the above question.

Given a first order complete theory T and a set Γ of (not necessarily complete) types over the empty set, we let

EC(T, Γ) = { M ⊧ T | M omits every type in Γ }.

For a cardinal λ, the ordinal δ(λ) is defined as the least ordinal δ such that for any T and Γ and M, if

|T | ≤ λ,

T ⊢ (P, <) is a linear order,

M ∈ EC(T, Γ), and

(P^{M}, <^{M}) has order type at least δ, then there exists N ∈ EC(T, Γ), such that (P^{N}, <^{N}) is not well-ordered.

Theorem A.2. Let T be any theory. For every ⟨ a_{i} | i < ℶ_{δ(|T |)} ⟩ there exists an sequence of indiscernibles ⟨ b_{n} | n < ω ⟩ with the following property: for every n < ω there are i_{0} < ⋯ < i_{n−1} satisfying

tp(b_{0}, …, b_{n−1}/∅) = tp(a_{i_{0}}, …, a_{i_{n−1}}/∅).

Theorem A.2 is an improvement of Theorem 1.13. We prove below that δ(|T |) < (2^{|T |})^{+}. Furthermore, when T is countable or |T | is a singular strong limit of countable cofinality, then δ(|T |) < |T |^{+} (Theorem VII 5.5(5) of [Sha]).

The following theorem is well-known. E.g. see Theorem 11.5.1 in Wilfrid Hodges’s book[Ho].

Theorem A.3. Let P be a unary predicate and < a binary predicate in L(T) such that

T ⊢ “< is a linear order on P ”.

Suppose M ∈ EC(T, Γ) with P^{M} = { a_{i} : i < (2^{|T |})^{+} } is such that

M ⊧ a_{i} < a_{j} if and only if i < j < (2^{|T |})^{+}.

Then there exists N ∈ EC(T, Γ) such that P^{N} is not well-ordered by <^{N}.

Corollary A.4. δ(|T |) < (2^{|T |})^{+}.

We could not find a proof of Theorem A.2 in the literature, so we have included a complete proof here:

Proof. Let I = ⟨ a_{i} | i < ℶ_{δ(|T |)} ⟩. We define the following functions: · For every n < ω, functions f_{n}: [ℶ_{δ(|T |)}]^{n} → D(T) given by

f_{n}(i_{0}, …, i_{n−1}) = tp(ā_{i_{0}}, …, ā_{i_{n−1}}/∅);
· A bijection g: ℶ_{δ(|T |)} → I, defined by g(i) = ā_{i};
· A bijection h: D(T) → κ, where κ = |D(T)|;

Let χ be a regular cardinal large enough so that H(χ) contains L(T), D(T), I, ℶ_{δ(|T |)} and the functions f_{n}, g and h as subsets. Assume in addition that H(χ) “knows” the Erdős-Rado Theorem; more precisely:

H(χ) ⊧ ℶ_{n}(ℶ_{α}) → (ℶ_{α}^{+})_{ℶ_{α}}^{n+1} ∀α ∈ δ(|T |) ∀n ∈ ω.

Next, choose new predicates J, D, λ, μ; new constants κ and φ for every φ ∈ L(T); and new function symbols f_{n} for every n ∈ ω, g,h, and b. Now form the following expansion of H(χ).

V = ⟨ H(χ), ∈, J, D, , λ, μ, κ, f_{n}, g, h, b, φ ⟩_{φ∈L(T),n∈ω},

where J^{V} = I, D^{V} = D(T), λ^{V} = ℶ_{δ(|T |)}, μ^{V} = (2^{|T |})^{+}, f_{n}^{V} = f_{n}, g^{V} = g, h^{V} = h, b(α)^{V} = ℶ_{α}, κ^{V} = κ, and φ^{V} = φ for φ ∈ L(T).

Let T^{∗} = Th(V). Then T^{∗} contains the following sentences (written informally for readability):

· |J| = λ; · |D| = κ < μ; · ∀α ∈ μ b(α + n + 1) → (b(α))_{κ}^{n+1}, for every n ∈ ω;

We define a set of types Γ in the language of T^{∗} as follows:

(*) Γ := {p ∈ S(∅) | no ā ∈ I realizes p }.

Then V ∈ EC(T^{∗}, Γ) and μ^{V} > δ(|T |), so by CorollaryA.4, there is V′ ∈ EC(T^{∗}, Γ) such that μ^{V′} is not well-ordered. Let { α_{n} | n < ω } ⊆ μ^{V′} witness this. We may assume that V′ ⊧ α_{n} > α_{n+1} + n + 1.

We now construct sets X_{n} ⊆ λ^{V′} for n < ω such that

(1) V′ ⊧ |X_{n}| ≥ b(α_{n}) for every n < ω;

(2) V′ ⊧ f_{n}(g(i_{0}), …, g(i_{n−1})) = f_{n}(g(j_{0}), …, g(j_{n−1})), for i_{0} < ⋯ < i_{n−1} ∈ X_{n} and j_{0} < ⋯ < j_{n−1} ∈ X_{n}.

The construction is by induction on n. Let X_{0} = λ^{V′} and clearly V′ ⊧ |X_{0}| ≥ b(α_{0}) since V′ ⊧ b(α_{0}) ∈ λ.

Having constructed X_{n}, notice the following.

(i) V′ ⊧ |X_{n}| ≥ b(α_{n}); (ii) V′ ⊧ c: [X_{n}]^{n+1} → D, with c(i_{0}, …, i_{n}) := f_{n+1}(g(i_{0}), …, g(i_{n})); (iii) V′ ⊧ |D| = κ; (iv) V′ ⊧ b(α_{n}) → (b(α_{n+1}))_{κ}^{n+1}.

Then (iv) applied to (1) and (2) implies that there is X_{n+1} ⊆ X_{n} such that V′ ⊧ |X_{n+1}| ≥ b(α_{n+1}) monochromatic with respect to c, so X_{n+1} is as required.

Since every φ ∈ L has a name in L(T^{∗}), there are p_{n} ∈ D(T) for n ∈ ω such that tp(g(i_{0}), …, g(i_{n})/∅) = p_{n} for ā_{i_{0}} = g(i_{0}), …, ā_{i_{n−1}} = g(i_{n−1}) ∈ J^{V′}, and i_{0} < ⋯ < i_{n−1} ∈ X_{n}.

Now let { c_{n} | n < ω } constants not in L(T^{∗}) and let T_{1} be the union of the following set of sentences:

· T^{∗}; · p_{n}(c_{0}, …, c_{n−1}), for every n < m; · g(c_{n}) < g(c_{m}), for every n < m; · φ(c_{0}, …, c_{n−1}) ↔ φ(c_{i_{0}}, …, c_{i_{n−1}}), whenever φ ∈ L(T), i_{0} < … i_{n−1}, and n < ω.

Then T_{1} is consistent: for every finite subset of T_{1} use g(X_{n}) to realize the c_{k}’s.

Let N_{1} ⊧ T_{1} and b_{n} = c_{n}^{N_{1}} for every n ∈ ω. Certainly { b_{n} | n < ω } is indiscernible (in L(T)). Now we show that for every n < ω there exist i_{0} < ⋯ < i_{n−1} < ℶ_{(2^{|T |})^{+}} such that

tp(a_{i_{0}}, …, a_{i_{n−1}}/∅) = p_{n}.

But by construction, there are j_{0} < ⋯ < j_{n−1} such that

q_{n} = tp_{L(T^{∗})}(g(j_{0}), …, g(j_{n−1})/∅) = p_{n}.

Hence, { x_{i} ∈ J } ∈ q_{n} for every i < n, and since { J, g, ∈ } ⊆ L(T^{∗}), we have

{ g(x_{0}) < g(x_{1}), …, g(x_{n−2}) < g(x_{n−1}) } ⊆ q_{n}

But since V′ ∈ EC(T^{∗}, Γ), we must have q_{n} ∉ Γ. Thus, by (*), there are a_{i_{0}}, … a_{i_{n−1}} in I realizing q_{n}. ⊣

Appendix B. Historical Notes

Introduction: Important progress toward a solution of Łǒs’ conjecture was made by Frank Rowbottom who in 1964 introduced the notion of λ-stability (see [Ro]) and J. P. Ressayre in [Re]. Shelah’s 1970 proof of Łǒs’ conjecture never appeared in print. A “simplified” was published in 1974 in [Sh31]. Another proof (which is more conceptual but uses deeper machinery) appeared in 1978 in [Sha].

Although Baldwin’s book [Ba] was published in 1988, early versions of it circulated since 1980 and had significant influence on several publications with earlier publication dates.

We have learned from Baldwin that a preliminary version of [Sh93] was titled “Treeless unstable theories”.

Section 1: The concept of Definition 1.7 was introduced in [Sha] and [Sh93], where it is called indiscernible based on (A, B). However, since the name “Morley sequence” has become standard since the 1970’s (see[Sa] and [Po]), we have departed from Shelah at this point.

We do not know of any complete proof of Theorem 1.13 in print. It is stated as Lemma 6.3 in [Sh93] and used heavily in the proof of Claim 6.4, the precursor of Kim’s proof. The scant proof of Theorem 1.13 offered in [Sh93] contains the line “by the method Morley proved his omitting types theorem”.

Section 2: The equivalence between forking and dividing for stable theories was discovered by Baldwin and Shelah in 1977 while discussing a preliminary version of [Sh93]. It appears in print for the first time as Exercise III.4.15 in [Sha].

The characterization of dividing through Morley sequences (Theorem 2.4), the equivalence between forking and dividing (Theorem 2.5), the Symmetry and Transitivity properties of forking in simple theories, and Corollary 2.10 are due to Kim [Ki]. The proof we present of Theorem 2.4 is from Buechler and Lessmann [BuLe], where this is done in an infinitary context. The argument for the equivalence between forking and dividing is new and is due to Shelah in a private communication.

The Symmetry property for strongly minimal sets was discovered by William Marsh [Mar] and used by Baldwin and Lachlan in [BaLa]. Lascar discovered the Symmetry property for superstable theories [La1, La2]. Independently, Shelah generalized it to stable theories. The implication (1) ⇒ (2) of Theorem 3.21 is from [KP1]. This theorem is an analog of Shelah’s characterization of non-forking extension via local rank for stable theories (see Theorem III.4.1 of [Sha]).

The Independence Theorem 2.11 for simple theories is due to Kim and Pillay [KP1] and is a generalization of a result of Hrushovski and Pillay about S1-structures ((i)⇒(ii) in Lemma 5.22 of [HP1]).

Section 3: Our D[p, Δ, k] is Shelah’s D^{m}[p, Δ, ℵ_{1}, k] in [Sh93]. All the material in this section is due to Shelah and is taken from [Sh93] and Chapter III of [Sha], where the facts are often stated without proof. Occasionally, we have chosen more modern language. The implication (2) ⇒ (1) of the characterization of forking in terms of a drop in the rank (Theorem 3.21) is due to Shelah. The direction (1) ⇒ (2) of is from Kim and Pillay [KP1].

Section 4: The boolean algebra introduced here is different than that in [Sh93] it is a variation of that in [Sh93]; we have replaced weak dividing with forking. The proof that this boolean algebra satisfies the chain condition is not from [Sh93] it was communicated to us by Shelah 1998.

Appendix A: The theorems and the proofs are new and based on the approach of Barwise and Kunen [BaKu] for computing Hanf numbers.

References

[Ba] John T. Baldwin. Fundamentals of Stability Theory. Springer-Verlag, Berlin, 1988.

[BaLa] John T. Baldwin and Alistair H. Lachlan. On strongly minimal sets. J. Symbolic Logic, 36, 79–96, 1971.

[BaKu] K. Jon Barwise and Kenneth Kunen, Hanf numbers for fragments of L_{∞,ω}, Israel J. of Mathematics, 10, 306–320, 1971

[Bu1] Steven Buechler. Lascar strong types in some simple theories, Journal of Symbolic Logic, 64, (1999), no. 2, 817–824.

[Bu2] Steven Buechler. Canonical bases in some supersimple theories, preprint 1998.

[BuLe] Steven Buechler and Olivier Lessmann. Simplicity inside a Homogeneous Model. Preprint.

[BPW] Steven Buechler, Anand Pillay and Frank F. Wagner. Supersimple theories. J. Amer. Math. Soc., 14 (2001), no. 1, 109–124 .

[Ca] Enrique Casanovas. The number of types in simple theories. Ann. Pure Appl. Logic, 98 (1999), no. 1-3, 69–86.

[CK] C. C. Chang and H. Jerome Keisler. Model Theory. North-Holland Publishing .Co., Amsterdam, 1990.

[CH] Zoe Chatzidakis and Ehud Hrushovski. Algebraically closed fields with an automorphism. Trans. of AMS.

[Gr] Rami Grossberg. A course in model theory. Book in preparation.

[GrSh] Rami Grossberg and Saharon Shelah. Semisimple theories. in preparation.

[Ha] Victor Harnik. On the existence of saturated models of stable theories. Proc of AMS, 52, 361–367, 1975.

[HH] Victor Harnik and Leo Harrington. Fundamentals of forking. Ann. Pure Appl. Logic, 26, 245–286, 1984.

[Ho] Wilfried Hodges. Model theory. Cambridge University Press, 1993 772 pages.

[Hr] Ehud Hrushovski. Pseudofinite fields and related structures. Manuscript. [Hr 1] Ehud Hrushovski. Simplicity and the Lascar group. Preprint.

[HP1] Ehud Hrushovski and Anand Pillay, Groups definable in local fields and pseudofinite fields, Israel J. of Mathematics, 85, 203–262, 1994.

[HP2] Ehud Hrushovski and Anand Pillay, Definable groups of algebraic groups over finite fields. Crelle’s Journal, 462, 69–91, 1995.

[Je] Thomas Jech. Set Theory. Academic Press, New York, 1978.

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

[KP1] Byunghan Kim and Anand Pillay. Simple theories Annals of Pure and Applied Logic, 88, (1997), 149–164.

[KP2] Byunghan Kim and Anand Pillay. From stability to simplicity. Bull. Symbolic Logic 4, (1998), no. 1, 17–36.

[La1] Daniel Lascar. Types définissables et produit de types. C. R. Acad. Sci. Paris Sir. A-B, 272, A1233–A1236, 1971.

[La2] Daniel Lascar. Ranks and definability in superstable theories. Israel J. Math., 23, 53–87, 1976.

[La3] Daniel Lascar. Stability in Model Theory. John Wiley & Sons, Inc., New York, 1987.

[LaPi] Daniel Lascar and Anand Pillay. Forking and fundamental order in simple theories. J. Symbolic Logic, 64, (1999), no. 3, 1155–1158.

[LaPo] Daniel Lascar and Bruno Poizat. An introduction to forking. J. Symbolic Logic, 44, 330–350, 1979.

[Le] Olivier Lessmann. Counting partial types in simple theories. Colloq. Math., 83 (2000), no. 2, 201–208.

[Lo] Jerzy Łǒs. On the categoricity in power of elementary deductive systems and related problems. Colloq. Math. , 3, (1954) 58–62.

[Ma] Michael Makkai. A survey of basic stability theory, with particular emphasis on orthogonality and regular types. Israel J. Math., 49, 181–238, 1984.

[Mar] William Marsh. On ω_{1}-categorical and not ω-categorical theories. PhD thesis, Dartmouth College, 1966.

[Mo] Michael Morley. Categoricity in power. Trans. Amer. Math. Soc., 114, 514–538, 1965.

[Pi] Anand Pillay. An Introduction to Stability Theory. Clarendon Press, Oxford University Press, New York, 1983.

[Po] Bruno Poizat. Suites d’indiscernables dans les théories stables. Technical report, Univ. Pierre et Marie Curie, Paris, 1978.

[Re] J. P. Ressayer. Sur les théories du premier ordere catégorique en un cardinal. Trans. of A.M.S., 142, 481–505, 1969.

[Ro] Frank Rowbottom. The Łǒs conjecture for uncountable theories. Notices of A.M.S., 11, 248, 1964.

[Sa] Gerald Sacks. Saturated Model Theory. W. A. Benjamin, Inc., Reading, 1972.

[S] Z. Shami. A natural finite equivalence relation definable in low theories, Journal of Symbolic Logic, 65, (2000), no. 4, 1481–1490.

[Sh3] Saharon Shelah. Finite diagrams stable in power. Ann. Math. Logic, 2, 69–118, 1970/1971.

[Sh31] Saharon Shelah. Categoricity of uncountable theories. In L.A. Henkin et al., editors, Proceedings of the Tarski Symposium, pages 187–203, Providence, R.I, 1974.

[Sha] Saharon Shelah. Classification Theory and the Number of Nonisomorphic Models. North-Holland Publishing Co., Amsterdam, 1978.

[Sh 80] Saharon Shelah. A weak generalization of MA to higher cardinals. Israel Journal

of Mathematics, 30:297–306, 1978.

[Sh93] Saharon Shelah. Simple unstable theories. Ann. Math. Logic, 19, 177–203, 1980. [Sh 126] Saharon Shelah. On saturation for a predicate. Notre Dame Journal of Formal

Logic, 22:239–248, 1981. [Sh 500] Saharon Shelah. Toward classifying unstable theories. Annals of Pure and Applied

Logic, 80:229–255, 1995. [Sh 702] Saharon Shelah. On what I do not understand (and have something to say),

model theory. Math. Japon., 51, (2000), no. 2, 329–377.

[Wa] Frank O. Wagner. Simple Theories, Kluwer Academic Publishers, 260 pages, 2000. E-mail address, Rami Grossberg: rami@cmu.edu

Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213

   E-mail address, José Iovino: iovino@sphere.math.utsa.edu

Department of Mathematics, The University of Texas at San Antonio, 6900 North Loop 1604 West, San Antonio, Texas 78249-0664

E-mail address, Olivier Lessmann: lessmann@uic.edu

Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL 60607