SHELAH’S STABILITY SPECTRUM AND HOMOGENEITY SPECTRUM IN FINITE DIAGRAMS.

RAMI GROSSBERG AND OLIVIER LESSMANN

Abstract. We present Saharon Shelah’s Stability Spectrum and Homogeneity Spectrum theorems, as well as the equivalence between the order property and instability in the framework of Finite Diagrams. Finite Diagrams is a context which generalizes the first order case. Localized versions of these theorems are presented. Our presentation is based on several papers; the point of view is contemporary and some of the proofs are new. The treatment of local stability in Finite Diagrams is new.

1. Introduction

Saharon Shelah’s Finite Diagrams Stable in Power [Sh3], published in 1970, is one of the seminal articles in model theory. It contains a large number of key ideas which have shaped the development of classification theory. The model-theoretic framework of the paper is more general than the first order case. However, while all the particular cases of the results in the first-order case can be found in several more recent publications of Saharon Shelah as well as countless expositions, the non first-order content of [Sh3] is still not available in a concise form.

The primary purpose of this paper is to present, in this more general framework, most of the stability results of [Sh3], together with the order/stability dichotomy from [Sh12], and the homogeneity spectrum appearing in The Lazy Model Theorist’s Guide To Stability [Sh54]. A secondary purpose is to present the necessary background to [Le1] and [GrLe2]. This is done in a contemporary and self-contained manner, and includes improvements and techniques from [Sh b], [Sh300], and [Gr1]. Finally, with little additional work, we localize all the theorems and obtain local versions of the Stability Spectrum Theorem and the Homogeneity Spectrum in Finite Diagrams. This study of local stability in more general frameworks has been started in [GrLe1].

The framework introduced by Shelah in [Sh3] is the study of classes of models of a finite diagram. These classes are described in more detail below. Such classes are examples of nonelementary classes and the results presented in this paper belong to a subfield of pure model theory named by Shelah: classification theory for nonelementary classes. The word nonelementary refers to the fact that the class does not have a first-order axiomatization. The interesting cases are when the compactness theorem fails (like in a the class of models of an L_{ω_{1},ω}-theory). While many of the questions of classification theory for first order theories have been solved (see [Sh b]), classification theory for nonelementary classes is still under-developed. This is not to say that the subject is small or not interesting. Thousands of pages have been devoted to its questions: See for example [BaSh1],[BaSh2], [BaSh3], [Gr1], [Gr2], [GrHa], [GrLe1], [GrLe2], [GrSh1], [GrSh2], [HaSh], [HySh], [Ke], [Ki], [KlSh], [Le1], [Le2], [MaSh], [Sh3], [Sh48], [Sh87a], [Sh87b], [Sh88], [Sh tape], [Sh299], [Sh300], [Sh394], [Sh472], [Sh576], [Sh 600], [ShVi], and Shelah’s forthcoming book [Sh h]. The techniques used are usually set-theoretic and combinatorial in nature, although more recently, new ideas coming from geometric stability theory are being imported (E.g. [Le1] and [Le2]). The failure of the compactness theorem for a class of models makes their model theory delicate and sometimes sensitive to the axioms of set theory. This is one of the reasons why some additional assumptions are often made; a “monster model”, set-theoretic assumptions, amalgamation properties, and so on.

Date: June 27, 2000.

The second author wishes to thank the first author wholeheartedly for his kind guidance and support during his Ph.D. thesis.

For an updated version see www.math.cmu.edu/~ rami.

Let us describe briefly what is meant by the class of models of a finite diagram. Two perspectives are given below.

Given a first order theory T and a model M of T, the finite diagram of the model M is the set of complete types over the empty set realized in M. Recall that for a first-order theory T

D(T) := ⋃_{n<ω} D_{n}(T), where D_{n}(T) := {p | p is a complete T -type in n-variables}.

Fix a set D ⊆ D(T) and consider the class of models whose finite diagram is a subset of D. Such models are called D-models for convenience. In another language, we study the class of models omitting all the types over the empty set which do not belong to D. There are several connections between the class of D-models and the class of models of some theory T^{∗} ⊆ L_{λ^{+},ω}, for a cardinal λ. First, the class of D-models can be axiomatized by some theory T ⊆ L_{λ^{+},ω}, provided λ ≥ |D(T)\D|. On the other hand, from the point of view of Shelah’s conjecture (see below) for example, the class of models of a countable theory T^{∗} ⊆ L_{ω_{1},ω} is equivalent to the class of D-models of a countable first order theory T, where D is the set of isolated types over the empty set.

Both in [Sh3] and [Sh54], Shelah studied these classes under an additional assumption. Let us say a few words about exactly what this additional assumption is (it takes two equivalent forms in [Sh3] and [Sh54], and yet another equivalent formulation is given here). Since the compactness theorem fails for this class of models, it is crucial to have a good understanding of what the meaningful types are, i.e. which types can be realized by D-models. A corollary of the compactness theorem is that given a model M and a type p over a subset A of M, it is possible to find an elementary extension N of M in which p is realized. This fails, in general, for the class just described. There is a natural obstacle why this cannot work in general: Suppose p is a complete type over a set of parameters A, where A is a subset of a D-model M. Suppose there is a D-model N containing M in which p is realized, say by the sequence c̄. Then, since A ∪ c̄ ⊆ N and N is a Dmodel, necessarily, all the subsequences of the set A ∪ c̄ realize (over the empty set) types that belong to D. The assumption that Shelah made (although not in those terms) is that this is the only restriction. This class of models, with the additional assumption on types, is the framework that Shelah calls finite diagrams. Note that when D is the set D(T) of all complete T -types over the empty set, then this is the first order case.

An alternative way of looking at this framework is as follows. Given a theory T, fix a large homogeneous model ℭ of T. In general, ℭ is not saturated. Let D be the diagram of ℭ. Then, the class of D-models can be assumed to be the class of elementary submodels of ℭ and above meaningful types are the ones realized in ℭ. Note that when ℭ is saturated, then this is the first order case.

Using the first order case as a guide, there are four important results in Stability Theory all due to Shelah. See [Sh b].

• A theory T is stable if and only if it does not have the order property.

• If a theory T is stable in λ, then given any set of finite sequences I of cardinality λ^{+} and a set A of cardinality λ there exists a subset J ⊆ I of cardinality λ^{+} indiscernible over A.

• (The Stability Spectrum) For a theory T, either T is not stable or T is stable and there exist cardinals κ(T) and λ(T) satisfying κ(T) ≤ |T |^{+} and κ(T) ≤ λ(T) ≤ 2^{|T |} such that T is stable in μ if and only if μ ≥ λ(T) and μ^{<κ(T)} = μ.

• (The Saturation Spectrum) A theory T has a λ-saturated model of cardinality λ if and only if λ ≥ |D(T)| and either λ^{<λ} = λ or T is stable in λ.

This paper contains Shelah’s generalizations of above theorems to the class of models of finite diagrams. The first two results use the notion of splitting and can be generalized without too much difficulty to this context. As to the last two, the optimal versions rely on the notion of forking. Forking seems to rely on some form of compactness, and Shelah proved the last two theorems for this context using the notion of strong splitting (introduced before forking and dividing). Since strong splitting does not satisfy all the properties of forking, the proofs are more intricate and combinatorial in flavor.

Classes of models of a finite diagram are important also because they provide a natural test-case to generalize ideas from first order logic to more general nonelementary classes. On the one hand, many of the technical difficulties arising from the failure of the compactness theorem are present. On the other hand, the model theory is more manageable as we have a good understanding of types. It is still quite general and many natural nonelementary classes fit within this framework; for example the class of existentially closed models of an inductive theory, studied by the school of model theorists around Abraham Robinson. Note also that, in contrast to other nonelementary contexts, this work is completely done within ZFC. We added a discussion on the strength of the main assumption of Finite Diagrams after Hypothesis 2.5. Much work was done by Shelah and his collaborators on several more general contexts, including work toward Shelah’s conjecture, which is the parallel of Łoś conjecture for L_{ω_{1},ω} and abstract elementary classes.

Finite diagrams are much easier to deal with than abstract elementary classes. E.g. Shelah’s conjecture (see 2.6 below) holds for finite diagrams but is still open for abstract elementary classes.

The classification theory for finite diagrams has been the focus of some activity recently. The focus of [Sh3] was stable diagrams. In [HySh], Tapani Hyttinen and Shelah and develop a context corresponding to superstability. They prove the existence of types over the realization of which strong-splitting satisfies the axioms of a pregeometry. In [Le1], Olivier Lessmann introduced a rank for the ℵ_{0}-stable case. The finite diagrams for which the rank is bounded are called totally transcendental. Totally transcendental diagrams behave surprisingly like totally transcendental first order theories; there is a nicely behaved dependence relation, pregeometries and the methods of John T. Baldwin and Alistair Lachlan [BaLa] can be adapted to give geometric proofs of categoricity, construct nonisomorphic models, as well as other applications. In a work in preparation [GrLe2], we prove the Main Gap for totally transcendental diagrams. The decomposition theorem is in fact an application of a more general decomposition theorem. Finally we would like to mention a forthcoming paper by Steve Buechler and Lessmann [BuLe] as another continuation of this paper, where dividing is studied.

2. The Framework of Finite Diagrams

The notation is standard. Abbreviations like AB stands for A ∪ B, and Ab̄ for A ∪ {ran(b̄)}. When M is a model, ∥M∥ stand for the cardinality of M. The notation A ⊆ M means that A is a subset of the universe of M.

Let T be a first order complete theory in a language L. Denote by L(T) the set of first order formulas in L. Let M̄ be the a very saturated model of T. For Δ ⊆ L, A ⊆ M, and a (not necessarily finite) sequence ā ∈ M, define the Δ-type of ā over A in M by

tp_{Δ}(ā/A, M) = {ϕ(x̄, b̄) | b̄ ∈ A, ϕ(x̄, ȳ) or ¬ϕ(x̄, ȳ) ∈ Δ, and M ⊧ ϕ[ā, b̄]}.

When Δ is L(T) it is omitted and when M is M̄, it is omitted also.

Definition 2.1.

(1) The finite diagram of A is

D(A) = {tp(ā/∅) | ā ∈ A, ā finite }.

Such sets will be denoted by D and called finite diagrams.

(2) The set A is a D-set if D(A) ⊆ D. The model M is a D-model if D(M) ⊆ D.

(3) We let S_{Δ}^{n}(A) = {tp_{Δ}(c̄/A) | c̄ ∈ M̄, ℓ(c̄) = n}, for Δ ⊆ L(T). When Δ = L(T) it is omitted. When n = 1 it is omitted. A type p ∈ S^{n}(A) is called a D-type if and only if A ∪ c̄ is a D-set, for every c̄ realizing p. S_{D}^{n}(A) will denote the set of D-types over A in n variables.

When D = D(T), then S_{D}(A) = S(A).

Definition 2.2. The model M is a (D, λ)-homogeneous model if M realizes every p ∈ S_{D}(A) for A ⊆ M with |A| < λ.

When D = D(T), then a model is (D, λ)-homogeneous if and only if it is λ-saturated.

The next lemma shows that if M is (D, λ)-homogeneous, then it is λuniversal for the class of D-models.

Lemma 2.3. Let M be (D, λ)-homogeneous and A be a D-set of cardinality λ. Let B ⊆ A such that |B| < λ. Then for every elementary mapping f: B → M, there is an elementary mapping g: A → M extending f.

Proof. Write A = B ∪ {a_{i} : i < λ}. Construct an increasing sequence of elementary mappings ⟨f_{i} | i < λ⟩ by induction on i < λ, such that f_{0} = f,

B ∪ {a_{j} : j < i} ⊆ dom(f_{i}) and ran(f_{i}) ⊆ M.

In case i = 0 or i a limit, it is obvious. Assume f_{i} is constructed. Define q_{i} = f_{i}(tp(a_{i}/B ∪ {a_{j} : j < i})). By induction hypothesis q_{i} ∈ S_{D}(f_{i}(B ∪ {a_{j} : j < i})). Hence, since M is (D, λ)-homogeneous, q_{i} is realized by some b_{i} ∈ M. Let f_{i+1} = f_{i} ∪ ⟨a_{i}, b_{i}⟩. The elementary mapping g = ⋃_{i<λ} f_{i} is as required.

Recall from the first order case that a model is λ-homogeneous, if for any partial elementary mapping f from M into M with | dom(f)| < λ and c ∈ M, there is an elementary extension g of f from M into M such that dom(g) ⊇ dom(f) ∪ c. The next lemma is an extension of the familiar first order result that a model M is λ-saturated if and only if M is λ-homogeneous and < ℵ_{0}-universal if and only if M is λ-homogeneous and λ-universal.

Lemma 2.4. M is a (D, λ)-homogeneous model if and only if D(M) = D and M is λ-homogeneous.

Proof. The only if part follows from the previous lemma. To see the converse, we show that M is (D, μ)-homogeneous for every μ ≤ λ by induction on μ.

For the base case, assume that μ < ℵ_{0}. Let p ∈ S_{D}(c̄), where c̄ ∈ M is finite. Let a be any element realizing p. By assumption tp(a ˆ c̄/∅) ∈ D. Since D(M) = D, there exist a′ and c̄′ ∈ M realizing tp(a ˆ c̄/∅). Let f be a partial elementary mapping such that f(c̄) = c̄′ and f(a) = a′. Then, by λ-homogeneity of M, there is a partial elementary mapping g from M to M, extending f^{−1} ↾ c̄′, with dom(g) ⊇ c̄′ ∪ a′. Then we have that a′ realizes f(p), and so g(a′) realizes g(f(p)) = p. Hence, p is realized in M.

By induction, let C ⊆ M of cardinality μ < λ and assume that we have already shown that M is (D, μ)-homogeneous. Let p ∈ S_{D}(C) and a be any element realizing p. Then C ∪ a is a D-set of cardinality μ, so by (D, μ)-homogeneity of M, using the previous lemma, there exists an elementary mapping f sending C ∪a into M. Hence, by λ-homogeneity of M, there is g, an elementary mapping from M into M, extending f^{−1} ↾ C with dom(g) ⊇ f(C) ∪ f(a). To conclude, notice that since a realizes p, f(a) realizes f(p) and g(f(a)) realizes g(f(p)) = p. This shows that M realizes p, since g(f(a)) ∈ M, and completes the proof.

The following hypothesis is made throughout the paper. It is equivalent to Shelah’s original assumption in [Sh3] and [Sh54]. Also, the same assumption was made by H. Jerome Keisler in his categoricity theorem [Ke].

Hypothesis 2.5. There exists a (D, κ̄)-homogeneous model ℭ, with κ̄ much larger than any cardinality mentioned in this paper.

In view of the preceding lemma, we may assume that any D-set lies in ℭ. Also, satisfaction is with respect to ℭ. Notice also that for any D-set A

S_{D}^{n}(A) = {tp(ā/A, ℭ) | ā ∈ ℭ and A ∪ ā is a D-set}.

The study of a finite diagram D is thus the study of the class of D-models under the additional assumption that there exists a (D, κ̄)-homogeneous model ℭ, with κ̄ very large.

Hypothesis 2.5 is a natural assumption to make. Let us say a few words about why we feel this is so. The most outstanding test question in the classification theory for nonelementary classes is a conjecture of Shelah, made in the mid-1970s:

Conjecture 2.6 (Shelah). Let T be a countable L_{ω_{1},ω} theory. If there exists a cardinal λ ≥ ℶ_{ω_{1}} such that T is categorical in λ, then T is categorical in every μ ≥ ℶ_{ω_{1}}.

As we mentioned in the introduction, it is equivalent to solve this conjecture for the class of D-models of a countable first order theory, where D is the set of isolated types over the empty set (whence the relevance of this discussion here). Most experts agree that the full conjecture seems currently out of reach. However, several attempts to solve the conjecture since the late 1970s have indicated that categoricity (sometimes in several cardinals and sometimes under additional settheoretic axioms ) implies the existence of various kinds of amalgamation properties and the existence of monster models (see for example [Sh48], [Sh87a], [Sh87b], [Sh88], or [BaSh3]). By monster model, we mean a large model with universal or homogeneous properties. By amalgamation properties we mean that the class of models of T satisfies the μ-amalgamation property for a class of cardinals μ. Recall that a class of models K has the μ-amalgamation property if for every triple of models M_{0}, M_{1}, M_{2} ∈ K of cardinality μ such that M_{0} ≺ M_{1}, M_{0} ≺ M_{2}, and M_{0} ⊆ M_{1}∩M_{2}, there exist a model N ∈ K and embeddings f_{i}: M_{i} → N for i = 1, 2 such that f_{1} ↾ M_{0} = f_{2} ↾ M_{0}. For example, by Robinson’s Consistency Lemma, the class of model of a first order theory T has the μ-amalgamation property, for every cardinal μ ≥ |T |.

While Shelah observed from the work of Leo Marcus [Mr], that the existence of a monster model quite as in Hypothesis 2.5 does not follow from the assumption of Shelah’s conjecture, it is certainly reasonable to conjecture that it implies the existence of a monster model with a similar flavor. Thus, experience gained in this framework can shed light on the potentially more general framework. These results are additional motivations to develop classification theory either inside a homogeneous model [Sh3], [Sh54], [Gr1], [Gr2], [HySh], [GrLe2], [Le1], or for nonelementary classes with amalgamation properties [Sh48], [Sh87a], [Sh87b], [GrHa], [Sh394]. In fact, under monster model or amalgamation properties several approximations of Shelah conjecture are known: for example [Ke], [Sh48], [Sh87a], [Sh87b], [Le1] and [Sh472].

In this vein, the two following conjectures were made by Rami Grossberg in 1989, in an email communication with Baldwin:

Conjecture 2.7. Let T be a countable L_{ω_{1},ω} theory. If T is categorical is some large enough λ, then there exists a μ_{0} such that the class of models of T has the μ-amalgamation property for every μ greater than μ_{0}.

Amalgamation properties are closely related to monster model hypotheses: When T is a Scott sentence, the conclusion of the previous conjecture implies the existence of arbitrarily large model-homogeneous models

Conjecture 2.8. Let T be a countable L_{ω_{1},ω} theory such that there exists a μ_{0} such that the class of models of T has the μ-amalgamation property for every μ greater than μ_{0}. If T is categorical in some λ ≥ ℶ_{ω_{1}}, then T is categorical in every cardinal μ ≥ ℶ_{ω_{1}}.

Before finishing this discussion, we can ask the following related question:

Question 2.9. Let T be a countable theory in L_{ω_{1},ω}. Is there a cardinal μ(T) with the property that if the class of models of T has the μ(T)-amalgamation property then it has the λ-amalgamation property for arbitrarily large λ?

3. Stability and Order in Finite Diagrams

In this section, we present the equivalence between stability and the failure of the order property in the context of finite diagrams (Corollary 3.12).

Definition 3.1. Let D be a finite diagram.

(1) The diagram D is said to be stable in λ if for every A ⊆ ℭ of cardinality at most λ and for every n < ω we have |S_{D}^{n}(A)| ≤ λ.

(2) We say that D is stable if there is a λ such that D is stable in λ.

By the pigeonhole principle, it is enough to consider n = 1, i.e. D is stable in λ if and only if for all A ⊆ ℭ of cardinality at most λ, we have |S_{D}(A)| ≤ λ.

Definition 3.2. Let D be a finite diagram.

(1) D has the λ-order property if there exist a D-set {ā_{i} | i < λ}, and a formula ϕ(x̄, ȳ) ∈ L(T) such that

⊧ ϕ[ā_{i}, ā_{j}] if and only if i < j < λ.

(2) D has the order property if D has the λ-order property for every cardinal λ.

Notice that the order property is formulated differently from the order property used by Shelah in [Sh b]. The formulation given here is equivalent to the usual order property in the first order case, and is more natural in nonelementary cases; when it holds there are many nonisomorphic models (see [Sh12], [GrSh1], and [GrSh2]).

Recall some standard definitions. A set of finite sequences {ā_{i} | i < α} is said to be an n-indiscernible sequence over A, for n < ω if tp(ā_{0}, …, ā_{n−1}/A) = tp(ā_{i_{0}}, …, ā_{i_{n−1}}/A). for every i_{0} < ⋯ < i_{n−1} < α. Then {ā_{i} | i < α} is an indiscernible sequence over A, if it is an n-indiscernible sequence over A for every n < ω. It is said to be an indiscernible set, if in addition, the ordering does not matter. We will not have to distinguish between the two, as in the presence of stability, every indiscernible sequence is, in fact, an indiscernible set (Remark 3.4 and Corollary 3.12). Hence, we will often say indiscernible for indiscernible sequence, or set when they coincide or when it does not matter.

Remark 3.3. If there exists a D-set {ā_{i} | i < ω}, which is an indiscernible sequence, and a formula ϕ(x̄, ȳ) such that

⊧ ϕ[ā_{i}, ā_{j}] if and only if i < j < ω,

then D has the order property.

Proof. Let λ be an infinite cardinal. Let {c̄_{i} | i < λ} be new constants. Consider the union of the following sentences:

• ϕ(c̄_{i}, c̄_{j}), if i < j < λ;
• ¬ϕ(c̄_{i}, c̄_{j}), if i ≥ j, i, j < λ;

• ψ(c̄_{i_{0}}, …, c̄_{i_{n}}), for each ψ(x̄_{0}, … x̄_{n}) ∈ tp(ā_{0}, …, ā_{n}/∅), and each n < ω,

and each i_{0} < ⋯ < i_{n} < λ.

The above set of sentences is consistent (use {ā_{i} | i < ω}). Let b̄_{i} be the interpretation of c̄_{i} in M̄, the monster model for T. The last clause implies that {b̄_{i} | i < λ} is a D-set. By the first two clauses, we have

⊧ ϕ[b̄_{i}, b̄_{j}] if and only if i < j < λ.

Hence, D has the λ-order property. We are done since λ was arbitrary.

Remark 3.4. Suppose D does not have the order property. Let {ā_{i} | i < α} be an infinite indiscernible sequence over A. Then {ā_{i} | i < α} is an indiscernible set over A.

Proof. Suppose that the conclusion fails. Then, there exist an integer n < ω, a permutation σ ∈ S_{n}, and indices i_{0} < ⋯ < i_{n} < α such that

tp(ā_{0}, …, ā_{n}/A) ≠ tp(ā_{i_{σ}(0)}, …, ā_{i_{σ}(n)}/A).

Since {ā_{i} | i < α} is an indiscernible sequence over A, we have tp(ā_{0}, …, ā_{n}/A) ≠ tp(ā_{σ(0)}, …, ā_{σ(n)}/A). Since any permutation is a product of transpositions, we may assume that there exist k_{0} < k_{1} ≤ n such that σ(k_{0}) = k_{1}, σ(k_{1}) = k_{0} and σ(i) = i, otherwise. Hence, there exists ϕ(x̄, ȳ, b̄), where b̄ ∈ A ∪ {ā_{i} | i ≤ n, i ≠ k_{0}, k_{1}} such that ⊧ ϕ[ā_{k_{0}}, ā_{k_{1}}, b̄] and ⊧ ¬ϕ[ā_{k_{1}}, ā_{k_{0}}, b̄]. Then, the D-set {ā_{i} ˆ b̄ | n < i < α} is an infinite indiscernible sequence (over ∅). Hence ⊧ ϕ[ā_{i}, ā_{j}, b̄] if and only if n < i < j < α. This implies that D has the order property by the previous remark.

The main tool to prove that the failure of the order property implies stability (Theorem 3.9) is splitting. Recall the definition.

Definition 3.5. Let Δ_{1} and Δ_{2} be sets of formulas. Let A be a set and B ⊆ A. For p ∈ S^{n}(A), we say that p (Δ_{1}, Δ_{2})-splits over B if there are b̄, c̄ ∈ A and ϕ(x̄, ȳ) ∈ Δ_{2} such that tp_{Δ_{1}}(b̄/B) = tp_{Δ_{1}}(c̄/B) with ϕ(x̄, b̄) ∈ p and ¬ϕ(x̄, c̄) ∈ p.

When Δ_{1} = Δ_{2} = L(T), we just say that p splits over B. When Δ_{1} = {ϕ(x̄, ȳ)} and Δ_{2} = {ψ(x̄, ȳ)}, we write (ϕ(x̄, ȳ), ψ(x̄, ȳ))-splits, omitting the parentheses.

For a statement t and a formula ϕ, the following convention is made: ϕ^{t} = ¬ϕ if the statement t is false and ϕ^{t} = ϕ, if the statement t is true. The same notation is used when t ∈ {0, 1}, where 0 stands for falsehood and 1 stands for truth.

The next two lemmas give sufficient conditions guaranteeing the existence and uniqueness of nonsplitting extensions.

Lemma 3.6. Let A ⊆ B ⊆ C be sets such that B realizes all the Δ_{1}-types over A that are realized in C. Assume p_{1},p_{2} ∈ S_{Δ_{2}}(C) and p_{1} ↾ B = p_{2} ↾ B. If p_{1}, p_{2} do not (Δ_{1}, Δ_{2})-split over A, then p_{1} = p_{2}.

Proof. By symmetry, it is enough to show that p_{1} ⊆ p_{2}. Let ϕ(x̄, b̄) ∈ p_{1}. By assumption tp_{Δ_{1}}(b̄/A) is realized by some c̄ ∈ B. Hence ϕ(x̄, c̄) ∈ p_{1} since p_{1} does not (Δ_{1}, Δ_{2})-split over A, and ϕ(x̄, ȳ)^{t} ∈ Δ_{2} for t = 0 or 1. Thus ϕ(x̄, c̄) ∈ p_{2} and so ϕ(x̄, b̄) ∈ p_{2} also since p_{2} does not (Δ_{1}, Δ_{2})-split over A.

Lemma 3.7. Let A ⊆ B ⊆ C be D-sets, such that B realizes every D-type over A, which is realized in C. Suppose p ∈ S_{D}(B) does not split over A. Then, there is a unique type q ∈ S_{D}(C) extending p that does not split over A.

Proof. Uniqueness was proved in the previous lemma. Hence, it is enough to show existence. Define q explicitly by setting:

q := {ϕ(x, c̄) | There exists b̄ ∈ B realizing tp(c̄/A) and ϕ(x, b̄) ∈ p}.

This is well-defined. By assumption p does not split over A and so the definition does not depend on the choice of b̄ ∈ B.

First notice that q is complete. Suppose c̄ ∈ C and ϕ(x, ȳ) ∈ L(T). Suppose ϕ(x, c̄) ∉ q. Let b̄ ∈ B realize tp(c̄/A). By definition, we have ϕ(x, b̄) ∉ p. Hence, ¬ϕ(x, b̄) ∈ p, since p ↾ B is complete. Thus, ¬ϕ(x, c̄) ∈ q, by definition of q. Also, q is consistent. Let ϕ_{1}(x, c̄_{1}), …, ϕ_{n}(x, c̄_{n}) ∈ q. Then ϕ_{i}(x, b̄_{i}) ∈ p, for b̄_{1}ˆ … ˆ b̄_{n} ∈ B realizing tp(c̄_{1}ˆ … ˆ c̄_{n}/A). Since p is consistent, we have

⊧ ∃x[ϕ_{1}(x, b̄_{1}) ∧ ⋯ ∧ ϕ_{n}(x, b̄_{n})].

Then, by an elementary mapping sending each b̄_{i} to c̄_{i} fixing A we conclude that

⊧ ∃x[ϕ_{1}(x, c̄_{1}) ∧ … ∧ ϕ_{n}(x, c̄_{n})].

Hence, the set {ϕ_{1}(x, c̄_{1}), …, ϕ_{n}(x, c̄_{n})} is consistent.

Now let us see that q does not split over A. Otherwise, there are c̄_{1}, c̄_{2} ∈ C, and ϕ(x, ȳ) such that tp(c̄_{1}/A) = tp(c̄_{2}/A) and ϕ(x, c̄_{1}), ¬ϕ(x, c̄_{2}) ∈ q. Choose b̄_{1}, b̄_{2} ∈ B, such that tp(b̄_{1}/A) = tp(c̄_{1}/A) = tp(c̄_{2}/A) = tp(b̄_{2}/A). We have ϕ(x, b̄_{1}), ¬ϕ(x, b̄_{2}) ∈ p, by definition of q. Hence p splits over A, contradiction.

Finally, let us show that q is a D-type. Suppose not. Then, there is a realizing q and c̄ ∈ C such that tp(a ˆ c̄/∅) ∉ D. Let b̄ ∈ B realize tp(c̄/A). Since a realizes p, we have tp(ab̄/∅) ∈ D. Hence, in particular

tp(ab̄/∅) ≠ tp(ac̄/∅).

Hence there is ϕ(x, ȳ), with ⊧ ϕ[a, b̄], and ⊧ ¬ϕ[a, c̄]. This implies that ϕ(x, b̄), and ¬ϕ(x, c̄) ∈ q. This shows that q splits over A, a contradiction.

We will use the following notational convention: For Δ a set of formulas, we write

S_{D,Δ}(B) = {tp_{Δ}(c/B, ℭ) | c ∈ ℭ and B ∪ c is a D-set}.

When Δ = {ϕ(x̄, ȳ)}, we write S_{D,ϕ}(B) instead of S_{D,{ϕ}}(B).

Corollary 3.8. Let A ⊆ B be D-sets. Then

|{p ∈ S_{D,Δ_{2}}(B) : p does not (Δ_{1}, Δ_{2})-split over A}| ≤ 2^{|D|^{|A|}}.

Proof. Since |S_{D}(A)| ≤ |D|^{|A|}, we can find C, with |C| ≤ |D|^{|A|} such that C realizes all the types in S_{D,Δ_{1}}(A). Then, by Lemma 3.6, we have

|{p ∈ S_{D,Δ_{2}}(B) : p does not (Δ_{1}, Δ_{2})-split over A}| ≤
≤ |{p : p ∈ S_{D,Δ_{2}}(C)}| ≤ |D|^{|C|} ≤ |D|^{|D|^{|A|}} ≤ 2^{|D|^{|A|}}.

The proof of the next theorem follows [Gr1].

Theorem 3.9. Let λ ≥ |L(T)|. If D is not stable in 2^{2^{λ}}, then D has the λ^{+}-order property.

Proof. We first claim that there exist a D-set A of cardinality 2^{2^{λ}} and a formula ϕ(x, ȳ) such that

|S_{D,ϕ}(A)| > |A|.

Since D is not stable in 2^{2^{λ}}, there is a D-set A of cardinality 2^{2^{λ}} such that |S_{D}(A)| > |A|. Define

f: S_{D}(A) → Π_{ϕ(x,ȳ)∈L}S_{D,ϕ}(A), by f(p) = (p ↾ ϕ)_{ϕ∈L}.

Then, f is injective and since λ ≥ |L(T)|, by the pigeonhole principle, there must be ϕ(x, ȳ) ∈ L such that |S_{D,ϕ}(A)| > |A|. This proves the claim.

Let A and ϕ be as in the claim, we will show that

ψ(x_{0}, x̄_{1}, x̄_{2}, y_{0}, ȳ_{1}, ȳ_{2}) := ϕ(x_{0}, ȳ_{1}) ↔ ϕ(x_{0}, ȳ_{2})

demonstrates the order property. For convenience, let μ = 2^{2^{λ}}. Let {a_{i} : i < μ^{+}} ⊆ ℭ be such that i ≠ j < μ^{+} implies tp_{ϕ}(a_{i}/A) ≠ tp_{ϕ}(a_{j}/A). This is possible since |S_{D,ϕ}(A)| > |A|. Let χ(ȳ, x) = ϕ(x, ȳ) and n = ℓ(ȳ). Define an increasing continuous chain of sets ⟨A_{i} : i < μ⟩ such that:

(1) A_{0} = ∅ and |A_{i}| ≤ μ, i < μ.

(2) For every B ⊆ A_{i} of cardinality at most λ and every type p ∈ S_{D,ϕ}(A_{i}) ∪ S_{D,χ}^{n}(A_{i}), p ↾ B is realized in A_{i+1}.

This is possible since there are at most μ^{λ} = λ subsets of A_{i} of cardinality λ and at most |S_{D}(B)| ≤ |D|^{λ} ≤ (2^{|L(T)|})^{|B|} ≤ (2^{λ})^{λ} < μ possible types for each set B.

Claim. For every j < μ^{+}, there is i with j < i < μ^{+} such that for all l < λ^{+} the type q_{i} = tp(a_{i}, A_{l}) (χ, ϕ)-splits over each B ⊆ A_{l} of cardinality at most λ.

Proof. Otherwise, there is j < μ^{+} such that for every i with j < i < μ^{+}, there is l < λ and B^{i} ⊆ A_{l} of cardinality at most λ such that q_{i} does not (χ, ϕ)-split over B^{i}. Since μ^{+} > λ, by the pigeonhole principle, we can find l < λ such that μ^{+} many q_{i}’s do not (χ, ϕ)-split over a subset of A_{l}. By a second application of the pigeonhole principle, since μ^{+} > μ ≥ |A_{l}|^{λ} = |{B ⊆ A_{l} : |B| ≤ λ}|, we can find μ^{+} > (2^{2^{λ}}) many types that do not (χ, ϕ)-split over a set of cardinality at most λ. This contradicts Corollary 3.8. Hence, the claim is true.

Among the i’s satisfying the claim, pick one such that a_{i} ∉ ⋃_{l<λ} A_{l}. This is possible since | ⋃_{l<λ} A_{l}| ≤ μ. Then, by construction, for every l < λ^{+}, the type tp_{ϕ}(a_{i}/A_{l}) (χ, ϕ)-splits over every B ⊆ A_{l} of cardinality at most λ. Define ā_{l}, b̄_{l} and c_{l} in A_{2l+2}, as well as B_{l} = ∪{ā_{k}, b̄_{k}, c_{k} : k < l} by induction on l < λ^{+} such that

(1) B_{l} ⊆ A_{2l} and |B_{l}| ≤ λ;

(2) tp_{χ}(ā_{l}/B_{l}) = tp_{χ}(b̄_{l}/B_{l});

(3) Both ϕ(x, ā_{l}) and ¬ϕ(x, b̄_{l}) belong to tp(a_{i}/A_{2l});

(4) c_{l} ∈ A_{2l+1} realizes ϕ(x, ā_{l}) ∧ ¬ϕ(x, b̄_{l}).

This is possible: Set B_{0} = ∅. If B_{l} is constructed, since B_{l} ⊆ A_{2l} of cardinality at most λ, tp_{ϕ}(a_{i}/A_{2l}) (χ, ϕ)-splits over B_{l}, hence we can find ā_{l} and b̄_{l} in A_{2l} such that tp_{χ}(ā_{l}/B_{l}) = tp_{χ}(b̄_{l}/B_{l}) and both ϕ(x, ā_{l}) and ¬ϕ(x, b̄_{j}) belong to tp(a_{i}/A_{2j}). Then, by construction of A_{2l+1}, we can find c_{l} ∈ A_{2l+1}, realizing tp_{ϕ}(a_{i}/A_{2}) ↾ {ā_{l}, b̄_{l}} and hence realizing ϕ(x, ā_{l}) ∧ ¬ϕ(x, b̄_{l}). When l is a limit ordinal, we define B_{l} by continuity.

Now, let d̄_{l} = c_{l} ˆ ā_{l} ˆ b̄_{l}. It is easy to see from (2), (3) and (4) that {d̄_{l} : l < λ^{+}} and ψ(x_{0}, x̄_{1}, x̄_{2}, y_{0}, ȳ_{1}, ȳ_{2}) = ϕ(x_{0}, ȳ_{1}) ↔ ϕ(x_{0}, ȳ_{2}) together demonstrate the (D, λ^{+})-order property.

The next theorem is a converse of Theorem 3.9. The proof uses Hanf number techniques. For a first order theory T and Γ a set of T -types over the empty set, the class EC(T, Γ) is the class of models of T omitting every type in Γ.

For cardinals λ and κ, the Hanf-Morley number μ(λ, κ) is defined to be the smallest cardinal μ with the property that for every EC(T, Γ) with |T | ≤ λ and |Γ| ≤ κ, if EC(T, Γ) contains a model of cardinality μ then EC(T, Γ) contains models of arbitrarily large cardinality. Clearly, when κ = 0, μ(λ, κ) = ℵ_{0}; this is the first order case. When κ ≥ 1, the notion of wellordering number δ(λ, κ) needs to be introduced. For cardinals λ, κ, the number δ(λ, κ) is the smallest ordinal δ with the property that for every EC(T, Γ) with |T | ≤ λ and |Γ| ≤ κ, if EC(T, Γ) contains a model with a predicate of order type δ, then EC(T, Γ) contains a model where this predicate is not wellordered. If κ ≥ 1, it is a standard result that μ(λ, κ) = ℶ_{δ(λ,κ)}. (Note that the methods of the proof below show μ(λ, κ) ≤ ℶ_{δ(λ,κ)}.) A standard result on wellordering numbers states that δ(λ, κ) ≤ (2^{λ})^{+}. This will be used in the proof and explains the cardinal ℶ_{(2^{|T |})^{+}} appearing in the statement.

Theorem 3.10. If D has the λ-order property for every λ < ℶ_{(2^{|T |})^{+}}, then D is not stable and D has the ω-order property witnessed by an indiscernible sequence.

Proof. We will show first that D has the ω-order property witnessed by an indiscernible sequence. By assumption, for each α < (2^{|T |})^{+}, we can find a D-set

P_{α} = {ā_{α,j} | j < (ℶ_{α})^{+}}

and a formula ϕ_{α} witnessing the order property. Hence, by the pigeonhole principle, we may assume that ϕ_{α} = ϕ is fixed for all α.

Notice that M is a D-model of T if and only if M ∈ EC(T, Γ), with Γ = D(T) \ D. But |D(T) \ D| ≤ 2^{|T |}, and so the well-ordering number for this class is at most δ(|T |, 2^{|T |}) = (2^{|T |})^{+}.

For α < (2^{|T |})^{+}, define M_{α} ≺ ℭ containing {ā_{α,j} : j < (ℶ_{α})^{+}} of cardinality (ℶ_{α})^{+}. This is possible by the downward Löwenhweim-Skolem Theorem. Each M_{α} belongs to EC(T, Γ). Define F: (2^{|T |})^{+} → {M_{α} | α < (2^{|T |})^{+}}, by F (α) = M_{α}.

Consider the following model

M = ⟨H(χ̄), ∈, F, (2^{|T |})^{+}, T, P, ⊧, ψ⟩_{ψ∈L},

where χ̄ is a regular cardinal big enough so H(χ̄) contains everything that has been mentioned so far in this proof. The predicates (2^{|T |})^{+} and T are unary predicates whose interpretations are the corresponding sets. The meaning of the binary predicates ⊧ and ∈ and of the constants ψ, for each ψ ∈ L is their true meaning in H(χ). Also F is a unary function and the interpretation of F is the one we just defined. P is a unary predicate, whose interpretation in each M_{α} is the D-set P_{α} witnessing the order property. More precisely, we have that

M ⊧∀α ∈ (2^{|T |})^{+}(ā_{α,i} ∈ F (α) ∧
ā_{α,j} ∈ F (α) ∧ P ā_{α,i} ∧ P ā_{α,j}] → (F (α) ⊧ ϕ[ā_{α,i}, ā_{α,j}] ↔ i ∈ j).

Let N ≺ M such that (2^{|T |})^{+} ⊆ N of cardinality (2^{|T |})^{+}. Therefore, we can fix a bijection G: |N| → (2^{|T |})^{+}. Define a < b if and only if G(a) ∈ G(b).

Form N′ = ⟨N, <, G⟩ an expansion of N. Let T′ = T h(N′) and for each ψ(x̄) ∈ L define ψ′(x̄, y) by ∃α ∈ (2^{|T |})^{+}(y = F (α) ∧ x̄ ∈ F (α) ∧ F (α) ⊧ ψ[x̄]). Let Γ′ = {{ψ′(x̄, y) : ψ(x̄) ∈ p} : p ∈ Γ}. Then, we have that |T′| = |T | and |Γ′| = |Γ|, so δ(|T′|, 2^{|T′|}) = (2^{|T |})^{+}.

We first claim that N′ omits every type in Γ′.

Suppose not. There is p′ ∈ Γ′ such that for some c̄ˆ a ∈ N′ we have that ⊧ ψ′[c̄, a], for all ψ′ ∈ p′. But then, by definition c̄ is in some M_{α} and c̄ realizes every ψ(x̄) in p. But p ∈ Γ so this contradicts the fact that M_{α} ∈ EC(T, Γ). Hence, we have a model N′ ∈ EC(T′, Γ′) well-ordered by < and of order-type (2^{|T |})^{+}. Thus, we can find a model N′′ ∈ EC(T′, Γ′), whose universe is not wellordered by <. Therefore, by taking away elements if necessary, there exists elements b_{n} ∈ N′′ such that N′′ ⊧ b_{n+1} + n + 1 < b_{n} and N′′ ⊧ b_{n} ∈ (2^{|T |})^{+} for n < ω.

Define a sequence of sets ⟨X_{n} | n < ω⟩ such that

(1) N′′ ⊧ “X_{n} is an n-indiscernible sequence in M_{b_{0}} of cardinality ℶ_{b_{n}}”.

(2) N′′ ⊧ “X_{n} has the D-order property”

This is possible. Construct the X_{n} by induction on n < ω. For n = 0, let X_{0} = {ā_{b_{0},j} : j < ℶ_{b_{0}}}, i.e. the interpretation in N′′ of the interpretation of the predicate P in M_{α}. Then the first requirement is satisfied since X_{0} has the right cardinality and there is nothing to check for 0-indiscernibility. The second requirement is also satisfied since M and so N′′ knows that they witness the order property.

Assume X_{n} has already been constructed. Define

f : [X_{n}]^{n+1} → S_{L(T)}^{n+1}(∅), by (c_{1}, …, c_{n+1}) ↦ tp(c_{1}, …, c_{n+1}/∅).

We know by Erdős-Rado that

ℶ_{n}^{+}(ℶ_{b_{n+1}}) → (ℶ_{b_{n+1}}^{+})_{ℶ_{b_{n+1}}}^{n+1}

and we have ℶ_{b_{n}} ≥ ℶ_{b_{n}+n+1} ≥ ℶ_{n}^{+}(ℶ_{b_{n+1}}), so we can find a subset X_{n+1} of X_{n} of cardinality ℶ_{b_{n+1}} such that every increasing (n + 1)-tuple from it has the same type. This implies that X_{n+1} is an (n + 1)-indiscernible sequence with the right cardinality. Since the second requirement is preserved by renumbering if needed, we are done.

This is enough. Let {c̄_{i} : i < ω} be a new set of constants. Define T_{1} to be the union of the following set of sentences:

• T;
• c̄_{i} ≠ c̄_{j}, whenever i ≠ j;
• ϕ(c̄_{i}, c̄_{j})^{i<j}, for every i, j < ω;
• χ(c̄_{i_{1}}, …, c̄_{i_{n}}), for every χ ∈ tp(ā_{1}, …, ā_{n}/∅), i_{1} < ⋯ < i_{n} and n < ω;

• ψ(c̄_{i_{1}}, … c̄_{i_{n}}) ↔ ψ(c̄_{j_{1}}, …, c̄_{j_{n}}), whenever i_{1} < ⋯ < i_{n} and j_{1} < ⋯ < j_{n}, n < ω and ψ ∈ L(T).

By the Compactness Theorem and the definition of X_{n}, T_{1} has a model N_{1}. Call ā_{i} = c̄_{i}^{N_{1}} Notice also that the construction ensures that {ā_{i} : i < ω} is a D-set. Hence we have the ω-order property witnessed by indiscernibles.

We will use these to show that D is not stable. Let μ be a given cardinality. Define κ = min{κ : 2^{κ} > μ}. By compactness, using the indiscernibility of {ā_{i} : i < ω}, we can get a D-set {ā_{η} : η ∈ ^{κ≥}2} such that ⊧ ϕ[ā_{η}, ā_{ν}] if and only if η ≺ ν. Let A = ⋃_{η∈ κ>2} ā_{η}. Then |A| ≤ μ, by choice of κ, and for η ≠ ν ∈ ^{κ}2, we have that tp(ā_{η}/A) ≠ tp(ā_{ν}/A). Indeed, there is a first i < κ such that η[i] ≠ ν[i], say η[i] = 0. But then ψ(ā_{ηˆ 0}, x̄) ∈ tp(ā_{η}/A) and ¬ψ(ā_{ηˆ 0}, x̄) ∈ tp(ā_{ν}/A). Thus |S_{D}(A)| ≥ 2^{κ} > μ and so D is not stable in μ.

The next corollary tells us that if D is stable, we can find λ < ℶ_{(2^{|T |})^{+}} demonstrating this. Notice that if D = D(T) we are in the first order case and the bound on the first stability cardinal is actually 2^{|T |}.

Corollary 3.11. If D is stable, then there exists λ < ℶ_{(2^{|T |})^{+}} such that D is stable in λ.

Proof. Suppose that D is not stable in any λ < ℶ_{(2^{|T |})^{+}}. Then, since ℶ_{(2^{|T |})^{+}} is a strong limit, for each λ < ℶ_{(2^{|T |})^{+}}, we have 2^{2^{λ}} < ℶ_{(2^{|T |})^{+}} and so D is not stable in 2^{2^{λ}}. Hence by Theorem 3.9, D has the λ^{+}-order property for all λ < ℶ_{(2^{|T |})^{+}} and so by Theorem 3.10 D is not stable.

The next corollary is the order/stability dichotomy.

Corollary 3.12. D is stable if and only if D does not have the order property.

Proof. If D is not stable, then it is not stable in 2^{2^{λ}} for any λ ≥ |L(T)| so by Theorem 3.9, D has the λ-order property for every cardinal λ. For the converse, we use Theorem 3.10.

4. The Stability Spectrum for Finite Diagrams

In the first part of this section, combinatorial properties related to splitting are introduced for finite diagrams. They can be used to give another characterization of stability (see Corollary 4.7). In the second part, the focus is on a more delicate tool; strong splitting. It is a substitute for the notion of forking. The appropriate cardinal invariant and combinatorial property related to strong splitting are introduced. They are used to derive the Stability Spectrum Theorem (Theorem 4.17).

Definition 4.1. (1) D satisfies (∗λ) if there exists an increasing continuous chain of D-sets {A_{i} : i ≤ λ} and p ∈ S_{D}^{n}(A_{λ}) such that

p ↾ A_{i+1} splits over A_{i}, for all i < λ.

(2) D satisfies (B ∗ λ) if there exists a tree of types {p_{η} ∈ S_{D}(B_{η}) | η ∈ ^{λ>}2}, and formulas ϕ_{η}(x̄, ā_{η}) such that p_{η} ⊆ p_{ν} if η ≺ ν and

ϕ_{η}(x̄, ā_{η}) ∈ p_{ηˆ 0} and ¬ϕ_{η}(x̄, ā_{η}) ∈ p_{ηˆ 1}.

The next two remarks are routine induction using the definition. As an illustration we prove the first one.

Remark 4.2. If there exists a type p ∈ S_{D}(A) that splits over every subset of A of cardinality less than λ, then D satisfies (∗λ).

Proof. Let p ∈ S_{D}(A) be such that p splits over every subset B of A of cardinality less than λ. Construct an increasing continuous chain of sets {A_{i} : i ≤ λ} of cardinality less than λ demonstrating (∗λ) as follows. Let A_{0} = ∅ and A_{δ} = ⋃_{i<δ} A_{i}, if δ is a limit ordinal. If A_{i} is constructed of cardinality less than λ, then by assumption p splits over A_{i}. Hence, we can find b̄, c̄ ∈ A and ϕ(x̄, ȳ) such that tp(b̄/A_{i}) = tp(c̄/A_{i}) and ϕ(x̄, b̄) ∈ p and ¬ϕ(x̄, c̄) ∈ p. Let A_{i+1} = A_{i} ∪ b̄ ∪ c̄.

Remark 4.3. In the definitions of (∗λ) and (B ∗ λ) we may assume that |A_{i}| < |i|^{+} + ℵ_{0} and similarly that |B_{η}| < |ℓ(η)|^{+} + ℵ_{0}.

Lemma 4.4. If D satisfies (∗λ), then D satisfies (B ∗ λ).

Proof. We first show that if p ∈ S_{D}^{n}(A) splits over B ⊆ A, then there is a partial elementary mapping f such that f ↾ B = id_{B} and p and f(p) are contradictory types:

If p splits over B, then there are b̄, c̄ ∈ A and ϕ(x̄, ȳ) such that tp(b̄/B) = tp(c̄/B) and ϕ(x̄, b̄) ∈ p and ¬ϕ(x̄, c̄) ∈ p. Hence there is an elementary mapping f such that f ↾ B = id_{B} and f(b̄) = c̄. Then clearly p and f(p) are contradictory types.

Now assume that D satisfies (∗λ). By definition, there exists an increasing continuous chain of sets {A_{i} | i ≤ λ} and p ∈ S_{D}^{n}(A_{λ}) such that p ↾ A_{i+1} splits over A_{i} for i < λ. By Remark 4.3, we may assume that |A_{i}| < |i|^{+} + ℵ_{0}. By the first paragraph, for each i < λ there exists an elementary mapping f_{i} such that A_{i} ⊆ dom(f_{i}) ⊆ A_{i+1} and f_{i}(p ↾ A_{i+1}) and p ↾ A_{i+1} are contradictory types.

Define G_{η}, p_{η}, B_{η} and F_{η} by induction on η ∈ ^{λ≥}2 such that:

(1) p_{η} ∈ S_{D}(B_{η}).

(2) G_{η} is an elementary mapping with dom(G_{η}) = A_{ℓ(η)} and ran(G_{η}) = B_{η}.

(3) If ν ≺ η then G_{ν} ⊆ G_{η}, p_{ν} ⊆ p_{η}, B_{ν} ⊆ B_{η} and F_{ν} ⊆ F_{η}, and if ℓ(η) is a limit ordinal, we set G_{η} = ⋃_{i<ℓ(η)} G_{η↾i}, p_{η} = ⋃_{i<ℓ(η)} p_{η↾i}, and B_{η} = ⋃_{i<ℓ(η)} B_{η↾i}.

(4) p_{η} = G_{η}(p ↾ A_{ℓ(η)}), and the types p_{ηˆ 0} and p_{ηˆ 1} are explicitly contradictory.

(5) F_{η} is an elementary mapping extending G_{ηˆ 1}∘f_{ℓ(η)}∘(G_{ηˆ 0})^{−1} with dom(F_{η}) = B_{ηˆ 0}, such that F_{η} ↾B_{η} = id_{B_{η}} and F_{η}(p_{ηˆ 0}) = p_{ηˆ 1}.

This is enough. The tree of types {p_{η} | η ∈ ^{λ≥}2} shows that D satisfies (B ∗ λ).

The construction is by induction on ℓ(η): For η = ⟨⟩, let B_{⟨⟩} = A_{0}, G_{⟨⟩} = id_{A_{0}} and p_{⟨⟩} = p ↾ A_{0}. If ℓ(η) is a limit ordinal use (3). Now assume that G_{η}, p_{η}, B_{η} are constructed for ℓ(η) = i. Let G_{ηˆ 0} be an extension of G_{η} with domain A_{i+1}. Define B_{ηˆ 0} = ran(G_{ηˆ 0}) and p_{ηˆ 0} = G_{ηˆ 0}(p ↾ A_{i+1}). Now G_{ηˆ 1} ∘ f_{ℓ(η)} ∘ (G_{ηˆ 0})^{−1} is an elementary mapping with domain ⊆ B_{ηˆ 0} which is the identity on B_{η}. Let F_{η} be an elementary mapping extending it with domain B_{ηˆ 0}. Set B_{ηˆ 1} = ran F_{η} and p_{ηˆ 0} = F_{η}(p_{ηˆ 1}).

The following theorem shows that the combinatorial properties (∗λ) and (B ∗ λ) contradict stability in λ.

Theorem 4.5. If D satisfies (∗λ) or (B ∗λ) then for every μ < 2^{λ}, D is not stable in μ.

Proof. By the previous lemma, it is enough to show that if D satisfies (B ∗ λ) then for every μ < 2^{λ}, D is not stable in μ.

Let μ < 2^{λ}. Let κ = min{κ | 2^{κ} > μ}. Then λ ≥ κ so D satisfies (B ∗ κ).

By definition, there exists p_{η} ∈ S_{D}(B_{η}) and ϕ_{η}(x̄, ā_{η}) for η ∈ ^{κ>}2, such that p_{η} ⊆ p_{ν} if η ≺ ν and ϕ_{η}(x̄, ā_{η}) ∈ p_{ηˆ 0} and ¬ϕ_{η}(x̄, ā_{η}) ∈ p_{ηˆ 1}. By Remark 4.3, we may assume that |B_{η}| < |ℓ(η)|^{+} + ℵ_{0}.

Let B = ⋃_{η∈ κ>2} B_{η}. Then |B| ≤ ∑_{η∈ κ>2} |B_{η}| ≤ κ · 2^{<κ} ≤ μ, by choice of κ and assumption on |A_{i}|. Now for each η ∈ ^{κ}2, let a_{η} realize p_{η}. Define q_{η} = tp(a_{η}/B). Then for ν ≠ η ∈ ^{κ}2, there is a first i < κ such that η[i] ≠ ν[i], say η[i] = 0 and ν[i] = 1. Hence p_{ηˆ 0} ⊆ q_{η} and p_{ηˆ 1} ⊆ q_{ν}, so q_{η} and q_{ν} are contradictory types. Therefore |S_{D}(B)| ≥ |{q_{η} | η ∈ ^{κ}2}| = 2^{κ} > μ, so D is not stable in μ.

The next theorem is a sort of converse.

Theorem 4.6. If there is a D-set A such that

|S_{D}(A)| > |A|^{<λ} + ∑_{μ<λ} 2^{|D|^{μ}}

then D satisfies (∗λ).

Proof. Let μ_{0} = |A|^{<λ} + ∑_{μ<λ} 2^{|D|^{μ}}. By Remark 4.2 it is enough to find a type p ∈ S_{D}(A) which splits over every subset B ⊆ A of cardinality less than λ.

Such a type p always exists: Otherwise for every p ∈ S_{D}(A), there exists B_{p} ⊆ A of cardinality < λ such that p does not split over B_{p}. Since |S_{D}(A)| > μ_{0} ≥ |A|^{<λ}, by the pigeonhole principle, we can find S ⊆ S_{D}(A) of cardinality μ_{0}^{+} and B such that p does not split over B, for each p ∈ S. But, by Corollary 3.8,

|{p ∈ S_{D}(A) : p does not split over B}| ≤ 2^{|D|^{|B|}} ≤ ∑_{μ<λ} 2^{|D|^{μ}} ≤ μ_{0},

a contradiction.

This gives another characterization of instability. This characterization will be used in the Homogeneity Spectrum Theorem (Theorem 5.9). Notice that (B ∗λ) can be used in lieu of (∗λ) in the following corollary.

Corollary 4.7. D is not stable if and only if D satisfies (∗λ), for every cardinal λ.

Proof. If D satisfies (∗λ) for every λ, then Theorem 4.5 implies that D is not stable in λ for every λ. Hence D is not stable.

For the converse, suppose that D is not stable and let λ be given. Then D is not stable in 2^{2^{λ}}. Hence, there exists a D-set A of cardinality 2^{2^{λ}} such that |S_{D}(A)| > 2^{2^{λ}} = |A|^{<λ} + ∑_{μ<λ} 2^{|D|^{μ}}. Therefore D satisfies (∗λ) by the previous theorem.

For the second part, we will focus on strong splitting.

Definition 4.8. A type p ∈ S^{n}(A) splits strongly over B ⊆ A if there exists {ā_{i} : i < ω} an indiscernible sequence over B and ϕ(x̄, ȳ) such that ϕ(x̄, ā_{0}) and ¬ϕ(x̄, ā_{1}) ∈ p.

A combinatorial property similar to (∗λ) is now defined in terms of strong splitting.

Definition 4.9. D satisfies (C ∗ λ) if there exists an increasing continuous chain of sets {A_{i} | i ≤ λ} and p ∈ S_{D}^{n}(A_{λ}) such that

p ↾ A_{i+1} splits strongly over A_{i}, for each i < λ.

Clearly if D satisfies (C ∗ λ), then it satisfies (∗λ) and similarly to Remark 4.3, we may assume that |A_{i}| < |i|^{+} + ℵ_{0} in the definition of (C ∗ λ).

The next cardinal invariant plays the role of κ(T) for the notion of strong splitting. It appears in the Stability Spectrum theorem.

Definition 4.10. Let

κ(D) = min{κ : For all p ∈ S_{D}(A) there is B ⊆ A, |B| < κ such that

p does not split strongly over B }.

If it is undefined, we let κ(D) = ∞.

Theorem 4.11. Let D be stable in λ. Then κ(D) is well-defined and κ(D) ≤ λ.

Proof. Suppose that κ(D) > λ. Then, by definition of κ(D), there exists a D-set A and a type p ∈ S_{D}(A) such that p splits strongly over every subset B of A of cardinality at most λ. Similarly to Remark 4.2 this implies that D satisfies (C ∗ λ). Hence, D satisfies (∗λ). By Theorem 4.5 D is not stable in λ, a contradiction.

To deal with strong splitting, some understanding of indiscernibles is needed. Theorem 4.13 is one of the main results to produce indiscernible sequences in the presence of stability. Recall Lemma I.2.5 of [Sh b].

Fact 4.12. Let B and let {ā_{i} | i < α} be given. Consider q_{i} = tp(ā_{i}/B ∪ {ā_{j} | j < i}) ∈ S_{D}(B ∪ {ā_{j} | j < i}) and suppose that

(1) If i < j < α then q_{i} ⊆ q_{j};

(2) For each i < α the type q_{i} does not split over B.

Then {ā_{i} | i < α} is an indiscernible sequence over B.

Theorem 4.13. Let D be stable in λ. Let I be a set of finite sequences and let A be a set such that I ∪ A is a D-set. If |A| ≤ λ < |I| then there exists a subset of I of cardinality λ^{+} which is an indiscernible set over A.

Proof. By the pigeonhole principle, there exists a subset J of I of cardinality λ^{+} and n < ω such that ā ∈ J implies ℓ(a) = n. Write J = {ā_{i} : i < λ^{+}}.

Claim. There are D-sets B and C, A ⊆ B ⊆ C, such that every type in S_{D}(B) is realized in C, and there exists a type p ∈ S_{D}^{n}(C) such that for every D-set C_{1} containing C of cardinality λ, there exists an extension p_{1} ∈ S_{D}^{n}(C_{1}) of p such that p_{1} does not split over B and is realized in J \ C.

Proof of the Claim. Assume that B, C and p as in the claim cannot be found. For each i < λ construct D-sets A_{i} of cardinality at most λ such that every p ∈ S_{D}(A_{i+1}) which is realized in J \ A_{i+1} splits over A_{i}.

This is possible: Let A_{0} = ∅ and A_{δ} = ⋃_{i<δ} A_{i} for δ a limit. Now assume A_{i} of cardinality at most λ is already constructed. Then |S_{D}(A_{i})| ≤ λ by stability in λ. Hence, there exists a D-set A^{i} of cardinality λ, containing A_{i}, realizing all the types over A_{i}. Now for any p ∈ S_{D}^{n}(A^{i}), A_{i}, A^{i} and p do not satisfy the assumptions of the claim. Therefore, there exists C_{p}, a D-set, C_{p} ⊇ A^{i} of cardinality λ such that every extension of p in S_{D}^{n}(C_{p}) that is realized in J \ C_{p} splits over A_{i}. Let A_{i+1} = ⋃_{p∈S_{D}^{n}(A^{i})} C_{p}. Then A_{i+1} is a D-set of cardinality at most λ with the desired property.

Let A_{λ} = ⋃_{i<λ} A_{i}. Since J has cardinality λ^{+}, there is ā ∈ J \ A_{λ}^{n}. Let p = tp(ā/A_{λ}). By construction p ↾ A_{i+1} splits over A_{i} so D satisfies (∗λ). Hence, D is not stable in λ by Theorem 4.5, a contradiction.

Let B, C and p ∈ S_{D}^{n}(C) be as in the claim. Construct {b̄_{i} : i < λ^{+}} ⊆ J by induction on i < λ^{+} as follows. If b̄_{j} is defined for j < i let C_{i} = C ∪ {b̄_{j} | j < i} and p_{i} ∈ S_{D}^{n}(C_{i}) be an extension of p which does not split over B and is realized in J \ C_{i}^{n}. Let b̄_{i} be in J \ C_{i}^{n} realizing p_{i}. Then {b̄_{i} | i < λ^{+}} is an indiscernible sequence by Fact 4.12. Since D is stable, then it does not have the order property by Corollary 3.12 and hence {b̄_{i} | i < λ^{+}} is an indiscernible set, by Remark 3.4.

The next two theorems prepare for the Stability Spectrum Theorem.

Theorem 4.14. Let D be stable in λ. Let μ ≥ λ be such that μ^{<κ(D)} = μ. Then D is stable in μ.

Proof. Suppose that D is not stable in μ. Let A be a D-set of cardinality μ such that |S_{D}(A)| > |A|. By assumption, |S_{D}(A)| > |A|^{<κ(D)}. Hence |S_{D}(A)| ≥ λ^{++}. Since D is stable in λ, then that κ(D) ≤ λ by Theorem 4.11. Hence, for each p ∈ S_{D}(A) there exists a subset B_{p} ⊆ A of cardinality less than κ(D) such that p does not split strongly over B_{p}. Since there are |A|^{<κ(D)} = |A| such B_{p}’s, by the pigeonhole principle, there exists a set S ⊆ S_{D}(A) of cardinality λ^{++} and a D-set B ⊆ A of cardinality less than κ(D) such that p does not split strongly over B, for each p ∈ S.

Construct {ϕ_{i}(x, ā_{i}) | i < λ^{+}} and p_{i} ∈ S, for i < λ^{+} such that

{ϕ_{j}(x, ā_{j}) : j < i} ∪ {¬ϕ_{i}(x, ā_{i})} ⊆ p_{i}. (*)

To do this, define S_{i} ⊆ S and A_{i} ⊆ A for i < λ^{+} such that

(1) A_{0} = ∅, A_{δ} = ⋃_{i<δ} A_{i} for δ limit, and A_{i} ⊆ A_{i+1};

(2) |A_{i}| ≤ λ, for each i < λ;

(3) S_{i} = {p ∈ S | p is the unique extension of p ↾ A_{i}};

(4) A_{i+1} is a subset of A such that if q ∈ S_{D}(A_{i}) has at least two contradictory extensions in S, then it has at least two extensions q, r ∈ S such that q ↾ A_{i+1} ≠ r ↾ A_{i+1}.

For i = 0 or i a limit ordinal, do (1). For the successor stage: If A_{i} is constructed and q ∈ S_{D}(A_{i}) has two extensions q_{1}, q_{2} ∈ S, then there is ϕ_{q}(x, ȳ) and ā_{q} ∈ A such that ϕ_{q}(x, ā_{q}) ∈ q_{1} and ¬ϕ_{q}(x, ā_{q}) ∈ q_{2}. Since |S_{D}(A_{i})| ≤ λ, A_{i+1} of cardinality λ as in (4) can be found.

Notice that since |S| = λ^{++} and | ⋃_{i<λ^{+}} S_{i}| ≤ ∑_{i<λ^{+}} |S_{D}(A_{i})| ≤ λ^{+} · λ = λ^{+}, there exists p ∈ S \ ⋃_{i<λ^{+}} S_{i}. For each i < λ^{+} consider p ↾ A_{i}. Since p ∉ S_{i}, by definition of S_{i} the type p ↾ A_{i} has at least two contradictory q, r ∈ S. By (4), we may assume that q ↾ A_{i+1} ≠ r ↾ A_{i+1}. Hence, either p ↾ A_{i+1} ≠ q ↾ A_{i+1}, or p ↾ A_{i+1} ≠ r ↾ A_{i+1}. Thus, in either case, there is p_{i} ∈ S such that p ↾ A_{i+1} ≠ p_{i} ↾ A_{i+1}. Hence, there exist ā_{i} ∈ A_{i+1} and ϕ_{i}(x, ȳ) ∈ L(T) such that ϕ_{i}(x, ā_{i}) ∈ p and ¬ϕ_{i}(x, ā_{i}) ∈ p_{i}. This establishes (*)

Now for each i < λ^{+}, let b_{i} realize p_{i}. The set {b_{i} ˆ ā_{i} : i < λ^{+}} has cardinality λ^{+} and B has cardinality less than κ(D) ≤ λ, so by Theorem 4.13 there is a subset of {b_{i} ˆ ā_{i} | i < λ^{+}} of cardinality λ^{+} which is indiscernible over B. Without loss of generality, we may assume that {b_{i} ˆ ā_{i} | i < λ^{+}} is indiscernible over B. By stability in λ we have |S_{D}(⋃_{k<λ} ā_{k})| ≤ λ. Hence, by the pigeonhole principle, there exist i and j with λ < j < i < λ^{+} such that p_{i} ↾ ⋃_{k<λ} ā_{k} = p_{j} ↾ ⋃_{k<λ} ā_{k}. By choice of j, we have ϕ_{j}(x, ā_{j}) ∈ p_{i} and ¬ϕ_{j}(x, ā_{j}) ∈ p_{j}. Now if ϕ_{j}(x, ā_{0}) ∈ p_{i} then since ¬ϕ_{j}(x, ā_{j}) ∈ p_{j}, p_{j} splits strongly over B, since {ā_{0}, ā_{j}, ā_{j+1}, ...} is indiscernible over B. And if ϕ_{j}(x, ā_{0}) ∉ p_{i} then ¬ϕ_{j}(x, ā_{0}) ∈ p_{i}, and since ϕ_{j}(x, ā_{j}) ∈ p_{i} then p_{i} splits strongly over B, since {ā_{j}, ā_{0}, ā_{1}, ...} is indiscernible over B. This contradicts the choice of S and B.

Theorem 4.15. Let D be stable in λ. Let μ ≥ λ be such that μ^{<κ(D)} > μ. Then D is not stable in μ.

To prove this theorem, a proposition is needed.

Proposition 4.16. Let D be stable in λ. Let χ ≤ λ be a cardinal such that λ^{χ} > λ. Let I be an indiscernible sequence. Then, for every c̄ ∈ ℭ and ϕ(x̄, ȳ) ∈ L(T) either

|{ā ∈ I : ⊧ ϕ[ā, c̄]}| < χ or |{ā ∈ I : ⊧ ¬ϕ[ā, c̄]}| < χ.

Proof. Let I and ϕ(x, c̄) contradict the conclusion of the proposition. Then, without loss of generality |I| = χ. Write I = {ā_{i} | i < χ}. Since I is indiscernible, there exists J = {ā_{i} | i < λ} containing I, indiscernible of cardinality λ. By the pigeonhole principle, either {i < λ : ⊧ ϕ[ā_{i}, c̄]} or {i < λ : ⊧ ¬ϕ[ā_{i}, c̄]} has cardinality λ. Without loss of generality, assume that it is the second. Hence, by a re-enumeration (recall that J is necessarily an indiscernible set), define J_{1} = {ā_{i} : i < χ + λ} such that ⊧ ϕ[ā_{i}, c̄] if and only if i < χ. Let q = tp(c̄/J_{1}). Then for any E ⊆ J_{1} of cardinality χ with complement of cardinality λ we can find a function f_{E}: J_{1} → J_{1} with f(ā_{i}) ∈ E if and only if i < χ. Then, for two such sets E_{1} ≠ E_{2}, we have f_{E_{1}}(q) ≠ f_{E_{2}}(q). Hence |S_{D}(J_{1})| ≥ λ^{χ} > λ, contradicting the stability in λ.

Proof of the Theorem. By assumption, there exists κ < κ(D) such that κ = min{κ | μ^{κ} > μ}. Let χ ≤ λ such that χ = min{χ | λ^{χ} > λ}. Observe that μ^{κ} > χ^{κ}: Otherwise, λ ≤ μ < μ^{κ} ≤ χ^{κ} ≤ λ^{κ}, and so χ ≤ κ by minimality of χ. Hence λ < μ^{κ} ≤ χ^{κ} = 2^{κ}. But (C ∗ κ) holds and λ ≤ 2^{κ}, so D is not stable in λ by Theorem 4.5, a contradiction.

Now, by definition of (C ∗ κ), there exists an increasing, continuous chain of D-sets {A_{i} | i ≤ κ} and a type p ∈ S_{D}(A_{κ}) such that |A_{i}| ≤ |i| + ℵ_{0} and

p ↾ A_{i+1} splits strongly over A_{i}, for each i < κ.

By definition of strong splitting, for each i < κ, there exist {ā_{α}^{i} | α < ω} indiscernible over A_{i} and ϕ_{i}(x, ȳ) ∈ L(T) such that both ϕ_{i}(x, ā_{0}^{i}), and ¬ϕ_{i}(x, ā_{1}^{i}) belong to p ↾ A_{i+1}.

For each η ∈ ^{κ>}μ, construct a type p_{η}, a D-set B_{η} and an elementary mapping G_{η}, by induction on ℓ(η) such that:

(1) p_{η} ∈ S_{D}(B_{η}) and if η ≺ ν then p_{η} ⊆ p_{ν} and B_{η} ⊆ B_{ν};

(2) G_{η} is an elementary mapping from A_{ℓ(η)} onto B_{η};

(3) |B_{η}| ≤ κ;

(4) For each c ∈ ℭ the set {α < μ | c realizes p_{ηˆ α}} has cardinality less than χ.

Let B_{⟨⟩} = A_{0}, G_{⟨⟩} = id_{A_{0}} and p_{⟨⟩} = p ↾ A_{0}. For η such that ℓ(η) is a limit ordinal, define everything by continuity. For the successor case, suppose that p_{η}, B_{η} and G_{η} have been constructed for η, with ℓ(η) = i. Let F be an elementary mapping extending G_{η} with domain A_{κ}. Let b̄_{α}^{i} = F (ā_{α}^{i}), for α < ω. Then {b̄_{α}^{i} | α < ω} is indiscernible over B_{η}. Hence, we can extend this set to {b̄_{α}^{i} | α < μ} such that {b̄_{α}^{i} | α < μ} is also indiscernible over B_{η}. For α < μ, let G_{ηˆ α} be an elementary mapping extending G_{η}, with domain A_{i+1} such that G_{ηˆ α}(ā_{0}^{i}) = b̄_{α}^{i} and G_{ηˆ α}(ā_{1}^{i}) = b̄_{α+1}^{i}. This is possible by indiscernibility. Let p_{ηˆ α} = G_{ηˆ α}(p ↾ A_{i+1}) and B_{ηˆ α} = ran G_{ηˆ α}. Hence (1)–(3) are satisfied. To see (4), observe that for each α < μ, both ϕ_{i}(x, b̄_{α}^{i}) and ¬ϕ_{i}(x, b̄_{α+1}^{i}) belong to p_{ηˆ α}. Since {b_{α}^{i} | α < μ} is indiscernible and χ ≤ λ < λ^{χ}, ( 4) follows from the previous proposition.

The construction implies the conclusion. Let B = ⋃_{η∈ κ>μ} B_{η}. Then |B| ≤ μ^{<κ} · κ = μ, by choice of κ. For each η ∈ ^{κ}μ, let p_{η} = ⋃_{i<κ} p_{η↾i}. By continuity, each p_{η} is a D-type and let a_{η} realize p_{η}. Then tp(a_{η}/B) ∈ S_{D}(B). By (4), for each c ∈ ℭ, the set {η ∈ ^{κ}μ | a_{η} = c} has cardinality at most χ^{κ} and we observed that χ^{κ} < μ^{κ}. Hence, |S_{D}(B)| > μ, so D is not stable in μ.

We finish this section with the Stability Spectrum Theorem.

Theorem 4.17 (The Stability Spectrum). Let D be a finite diagram. Either D is not stable, or D is stable and there exist cardinals κ ≤ λ < ℶ_{(2^{|T |})^{+}} such that for every cardinal μ, D is stable in μ if and only if μ ≥ λ and μ^{<κ} = μ.

Proof. If D is not stable, there is nothing to prove. If D is stable, let λ(D) be the first cardinal λ for which D is stable λ. Then λ(D) < ℶ_{(2^{|T |})^{+}} by Corollary 3.11. Moreover, κ(D) is defined and κ(D) ≤ λ(D) by Theorem 4.11.

Let μ be given. If μ < λ(D), then D is not stable in μ by choice of λ(D). Suppose that μ ≥ λ(D). If μ^{<κ(D)} = μ, then D is stable in μ by Theorem 4.14. If μ^{<κ(D)} > μ, then D is not stable in μ by Theorem 4.15.

5. The Homogeneity Spectrum

The section is devoted to the proof of the Homogeneity Spectrum Theorem (Theorem 5.9). The proof will proceed by cases, and is broken into several theorems. There are two types of results. On the one hand there are theorems showing the existence of a (D, λ)-homogeneous model of cardinality λ from assumptions like stability in λ and λ^{<λ}. On the other hand, there are results showing that such models do not exist from the failure of these conditions. The combinatorial properties defined in the previous section and parts of the Stability Spectrum Theorem will play a crucial role.

Theorem 5.1. Let λ ≥ |D| be such that λ^{<λ} = λ. Then there is a (D, λ)- homogeneous model of cardinality λ.

Proof. First, by Zermelo-König, λ is regular. By the downward Löwenheim-Skolem theorem, define an increasing continuous chain ⟨M_{i} | i < λ⟩ of D-models of cardinality λ, such that M_{i+1} realizes every D-type over every A ⊆ M of cardinality less than λ. This is possible since we have only λ^{<λ} = λ subsets of A of cardinality less than λ and only |D|^{|A|} ≤ λ^{<λ} = λ D-types over A. Let M = ⋃_{i<λ} M_{i}. Then M has cardinality λ, and since λ is regular, M is (D, λ)-homogeneous.

Theorem 5.2. Let λ ≥ |D| be such that λ^{<λ} > λ. If D satisfies (B ∗ λ) then there is no (D, λ)-homogeneous model of cardinality λ.

Proof. Suppose λ^{<λ} > λ ≥ |D|. Assume, by way of contradiction, that there is a (D, λ)-homogeneous model M of cardinality λ. Since D satisfies (B ∗ λ) there exist D-types p_{η} ∈ S_{D}(B_{η}) and ϕ_{η}(x̄, ā_{η}) for η ∈ ^{λ>}2 such that ϕ_{η}(x̄, ā_{η}) ∈ p_{ηˆ 0} and ¬ϕ_{η}(x̄, ā_{η}) ∈ p_{ηˆ 1}. In addition p_{η} ⊆ p_{ν} when η ≺ ν. By Remark 4.3, we may assume that |B_{η}| < |ℓ(η)|^{+} + ℵ_{0}. Hence, by (D, λ)-homogeneity of M, we may assume that B_{η} ⊆ M for each η ∈ ^{λ>}2.

For each μ < λ and η ∈ ^{μ}2, there are 2^{μ} types in S_{D}(B_{η}). Each such type is realized in M, since M is (D, λ)-homogeneous and so 2^{μ} ≤ λ, since M has cardinality λ. Hence, λ is singular, since otherwise λ^{<λ} = λ. Furthermore, λ is a strong limit (if there is μ < λ such that 2^{μ} = λ, then λ^{cf(λ)} = 2^{μ·cf(λ)} ≤ λ, contradicting Zermelo-König).

Let κ = cf(λ) and let λ_{i} < λ for i < κ be increasing and continuous such that λ = ∑_{i<κ} λ_{i}. Let A_{i} ⊆ M of cardinality λ_{i} for i < κ such that M = ⋃_{i<κ} A_{i}.

For each i < κ, define a sequence η_{i} ∈ ^{λ>}2 and a finite set C_{i+1} such that

(1) If i < j then η_{i} ≺ η_{j};

(2) C_{i+1} is a finite subset of B_{η_{i+1}};

(3) The type p_{η_{i+1}} ↾ C_{i} is not realized in A_{i}.

This is enough: Let p = ⋃_{i<κ} p_{η_{i}}. Then p ↾ ⋃_{i<κ} C_{i} is a D-type (by continuity) over a set of cardinality κ, which is not realized in M. This contradicts the (D, λ)-homogeneity of M since κ < λ.

This construction is possible. Define η_{0} = ⟨⟩, and for δ < κ a limit ordinal let η_{δ} = ⋃_{i<δ} η_{i}. For the successor case, assume that η_{i} ∈ ^{λ>}2 is constructed. Define τ_{α} = η_{i}ˆ 0_{α}, where 0_{α} is a sequence of zeroes of order type α, for α < 2^{λ_{i}}. Then τ_{α} ∈ ^{λ>}2, since λ_{i} < λ and λ is a strong limit.

We claim that there are α < β < (2^{λ_{i}})^{+} such that ⊧ ϕ_{τ_{α}}[c, ā_{τ_{α}}] ↔ ϕ_{τ_{β}}[c, ā_{τ_{β}}], for every c ∈ A_{i}.

Suppose that this is not the case. Let A_{i} = {c_{γ} | γ < λ_{i}}. Then, for every α < β < (2^{λ_{i}})^{+} there exists γ < λ_{i} such that ⊧ ¬(ϕ_{τ_{α}}[c_{γ}, ā_{τ_{α}}] ↔ ϕ_{τ_{β}}[c, ā_{τ_{β}}]). By the Erdős-Rado theorem, there is γ < λ_{i} and an infinite set S ⊆ (2^{λ_{i}})^{+} such that for every α < β in S we have ⊧ ¬(ϕ_{τ_{α}}[c_{γ}, ā_{τ_{α}}] ↔ ϕ_{τ_{β}}[c, ā_{τ_{β}}]). This is an immediate contradiction.

Hence, let α < β be as in (*). Let C_{i+1} = ā_{τ_{α}} ∪ ā_{τ_{β}} and let η_{i+1} = τ_{α}ˆ 1. Since ϕ_{τ_{α}}(x, ā_{τ_{α}}) and ¬ϕ_{τ_{β}}(x, ā_{τ_{β}}) are in p_{η_{i+1}} ↾ C_{i}, the type p_{η_{i+1}} is omitted in A_{i}. This finishes the construction and proves the theorem.

The next theorem is, in particular, an improvement of Proposition 4.16. It allows us to define averages (Definition 5.4). Averages are used in Theorem 5.6.

Theorem 5.3. Let D be stable. Let I be an infinite indiscernible set over A of cardinality at least κ(D). Let b̄ ∈ ℭ. Then there is J ⊆ I with |J| < κ(D) such that I \ J is indiscernible over A ∪ J ∪ b̄.

Proof. Let I = {c̄_{i} | i < α}. Since D is stable, κ(D) is defined by Theorem 4.11. Hence, there exists B ⊆ A ∪ I of cardinality less than κ(D) such that the type tp(b̄/A ∪ I) does not split strongly over B. Let J = B \ A. Then J ⊆ I has cardinality less than κ(D). We will show that I \ J is indiscernible over A ∪ J ∪ b̄. Clearly, I \ J is indiscernible over A ∪ J. If I \ J is not indiscernible over A ∪ J ∪ b̄, then, there exist an integer n < ω and indices i_{0} ⋯ < i_{n} such that tp(c̄_{0}, …, c̄_{n}/A∪J ∪b̄) ≠ tp(c̄_{i_{0}}, …, c̄_{i_{n}}/A∪J ∪b̄). Then ⊧ ϕ[c̄_{0}, …, c̄_{n}, ā, b̄, c̄] and ⊧ ¬ϕ[c̄_{i_{0}}, …, c̄_{i_{n}}, ā, b̄, c̄], for some formula ϕ ∈ L(T), parameters ā ∈ A and c̄ ∈ J. Let d̄_{0} = c̄_{0}ˆ … ˆ c̄_{n} and d̄_{1} = c̄_{i_{0}}ˆ … ˆ c̄_{i_{n}}. By taking sequences from I \ J, it is easy to find {d̄_{i} | i < ω} indiscernible over A ∪ J. Thus {d̄_{i} ˆ ā ˆ c̄ | i < ω} is indiscernible over A ∪ J. Hence, the type tp(b̄/A ∪ I) splits strongly over A ∪ J, a contradiction to the choice of B.

Definition 5.4. Let I be an indiscernible sequence of cardinality at least κ(D). Let A be such that A ∪ I is a D-set. Define the average of I over A, by

Av(I, A) = {ϕ(x̄, ā) | ϕ(x̄, ȳ) ∈ L(T), ā ∈ A, and ⊧ ϕ[b̄, ā],

for at least κ(D) elements b̄ ∈ I}.

Theorem 5.5. Let D be stable. Let I be an indiscernible sequence of cardinality at least κ(D) and A be such that A ∪ I is a D-set. Then Av(I, A) ∈ S_{D}^{n}(A), where n = ℓ(ā) for ā ∈ I. In addition, if |I| > |A|, then Av(I, A) is realized in I.

Proof. Averages are complete: Assume ϕ(x̄, c̄) ∉ Av(I, A), with c̄ ∈ A. Then by definition, the set J ⊆ I of elements realizing ϕ(x̄, c̄) has cardinality less than κ(D). Thus, since I \ J has cardinality at least κ(D), and all elements in I \ J realize ¬ϕ(x̄, c̄), necessarily ¬ϕ(x̄, c̄) ∈ Av(I, A). Averages are consistent: Let ϕ_{1}(x, c̄_{1}), …, ϕ_{n}(x, c̄_{n}) ∈ Av(I, A). Then, if c̄ = c̄_{1}ˆ … ˆ c̄_{n}, by Theorem 5.3, there is Jc̄, Jc̄ ⊆ I of cardinality less than κ(D) such that I \ Jc̄ is indiscernible over c̄. Hence, since each ϕ_{i}(x, c̄_{i}) was realized by at least κ(D) elements of I, we can find one in I \ Jc̄. But then, all elements in I \ Jc̄ realize ϕ_{i}(x, c̄_{i}) by indiscernibility (1 ≤ i ≤ n), so {ϕ_{1}(x, c̄_{1}), …, ϕ_{n}(x, c̄_{n})} is consistent. The last sentence follows similarly: For any c̄ ∈ A, every element of I \ Jc̄ realizes Av(I, A) ↾ c̄, since they realize every formula in it, and so if |I| > |A|, we can find b̄ ∈ I \ ⋃_{c̄∈A} Jc̄ realizing Av(I, A). It remains to show that Av(I, A) is a D-type: Notice that if we stretch I to J, I ⊆ J indiscernibles of cardinality greater than |A|, we have Av(I, A) = Av(J, A). Then Av(I, A) is realized in J, thus in ℭ, since J is a D-set, and so Av(I, A) is a D-type.

Theorem 5.6. Let λ ≥ |D|. If D is stable in λ, then there is a (D, λ)-homogeneous model of cardinality λ.

Proof. Suppose first that λ is regular. Define an increasing continuous chain ⟨M_{i} | i < λ⟩ of models of cardinality λ, such that M_{0} realizes all the types in D, and M_{i+1} realizes all the D-types over M_{i}. Such a construction is possible since D is stable in λ and λ ≥ |D|. Let M = ⋃_{i<λ} M_{i}. Then, M has cardinality λ and M is (D, λ)-homogeneous by regularity of λ.

Now suppose that λ is singular. Construct an increasing continuous chain of models ⟨M_{i} | i < λ · λ⟩ as above of length λ · λ. Let M = ⋃_{i<λ·λ} M_{i}. Notice that M has cardinality λ. We now show that it is (D, λ)-homogeneous. Let A ⊆ M of cardinality less than λ and p_{0} ∈ S_{D}(A). We will find I indiscernibles of cardinality greater than |A| with p_{0} = Av(I, A). Let p ∈ S_{D}(M) extending p_{0} and choose C ⊆ M of cardinality less than κ(D) such that p does not split strongly over C. Since D is stable in λ, then λ^{<κ(D)} = λ by Theorem 4.15. Hence, cf(λ) ≥ κ(D). Thus, considering the sequence ⟨M_{λ·i} | i < λ⟩ we can find i < λ such that C ⊆ M_{λ·i}.

We claim that p does not split over M_{λ·i+λ}. Otherwise, there are b̄ and c̄ in M and ϕ(x̄, ȳ) such that ϕ(x̄, b̄) ∈ p, ¬ϕ(x̄, c̄) ∈ p and

tp(b̄/M_{λ·i+λ}) = tp(c̄/M_{λ·i+λ}).

Let q := tp(b̄/M_{λ·i+λ}). Now, since λ is singular, we have ω < λ. Consider the following set

{j < λ : q ↾ M_{λ·i+ω·(j+1)} splits over M_{λ·i+ω·j}}.

Since D is stable in λ, in particular (∗λ) fails so we can find γ with

λ · i < γ < γ + ω < λ · λ

such that q ↾ M_{γ+ω} does not split over M_{γ}. For each n < ω, we can choose b̄_{n} ∈ M_{γ+n+1} realizing tp(b̄/M_{γ+n}). Now, tp(b̄_{n}/M_{γ+n}) does not split over M_{γ} (∀n < ω) by monotonicity. Hence {b̄_{n} | n < ω} are indiscernible over M_{γ}, by Fact 4.12. Similarly, both {b̄_{0}, b̄_{1}, …, b̄} and {b̄_{0}, b̄_{1}, …, c̄} are indiscernible over M_{γ}. In fact, since D is stable, D does not have the order property by Corollary 3.12, and thus they are indiscernible sets by Remark 3.4. Now suppose that for some n < ω, the formula ϕ(x̄, b̄_{n}) ∈ p. Then p splits strongly over C since

{b̄_{n}, c̄, b̄_{n+1}, … } is indiscernible over C.

Otherwise ¬ϕ(x̄, b̄_{0}) ∈ p. Then p splits strongly over C because

{b̄, b̄_{0}, b̄_{1}, … } is indiscernible over C.

We have a contradiction in both cases, which proves the claim.

We now use the claim to prove the conclusion of the theorem. First, we may assume that λ · i = 0, so p does not split over M_{0}. Now for each α < λ · λ, choose a_{α} ∈ M_{α+1} realizing p ↾ M_{α}. Since p does not split over M_{0} the sequence I := {a_{α} | α < λ · λ} is indiscernible. Let ϕ(x, ā) ∈ p_{0}. There is α_{0} < λ^{2} such that ϕ(x, ā) ∈ p_{0} ↾ M_{α_{0}}, so we have that ⊧ ϕ[a_{α}, ā] for every α ≥ α_{0}. Hence there are λ ≥ κ(D) many elements of I realizing ϕ(x, ā), showing that ϕ(x, ā) ∈ Av(I, A). So Av(I, A) ⊇ p_{0} and since both types are complete, we have p_{0} = Av(I, A). Thus since |I| > |A|, there are elements of I realizing p_{0}. This shows that p_{0} is realized in M. Hence M is (D, λ)-homogeneous.

The next lemma is an improvement of Corollary 3.8. It is needed in the proof of Theorem 5.8.

Lemma 5.7. Let D be stable. Let A ⊆ B be D-sets such that every D-type over A is realized in B. Fix n < ω and define

Γ := {p ∈ S_{D}^{n}(B) | p does not split over A}.

Then, for each p ∈ Γ, there is a sequence ⟨ā_{i}^{p} | i ≤ ω⟩ indiscernibles over A such that

(*) p ≠ q ∈ Γ implies tp(⟨ā_{i}^{p} : i < ω⟩/A) ≠ tp(⟨ā_{i}^{q} : i < ω⟩/A).

Moreover,

|Γ| ≤ | ⋃_{m<ω} S_{D}^{m}(A)|^{ℵ_{0}} ≤ |D|^{|A|+ℵ_{0}}.

Proof. It is enough to establish (*), since the last statement follows from (*) by a computation.

For each p ∈ Γ, define

I_{p} := ⟨ā_{i}^{p} : i < κ(D)⟩,

by induction on i < κ(D) such that tp(ā_{i}^{p}/B ∪ {ā_{j}^{p} : j < i}) extends p and does not split over A. This is possible by Lemma 3.7. By Fact 4.12 the sequence I_{p} is indiscernible over A. Hence, it is enough to show that

tp(⟨ā_{i}^{p} : i < κ(D)⟩/A) ≠ tp(⟨ā_{i}^{q} : i < κ(D)⟩/A), for p ≠ q ∈ Γ.

We will use the following claim.

Claim. If b̄ ∈ B and b̄_{1} ∈ ℭ such that tp(b̄/A) = tp(b̄_{1}/A), then

|{i < κ(D) : tp(b̄ˆ ā_{0}^{p}/A) ≠ tp(b̄_{1}ˆ ā_{i}^{p}/A)}| < κ(D)

Proof of the Claim. To show this, define {ā_{i}^{p} : κ(D) ≤ i < κ(D)^{+}}, by induction on i (κ(D) ≤ i < κ(D)^{+}) such that tp(ā_{i}^{p}/B ∪ {ā_{j}^{p} : j < i} ∪ b̄_{1}) extends p and does not split over A. Hence, by Fact 4.12, I′ = {ā_{i}^{p} : i < κ(D)^{+}} is indiscernible. By construction

tp(b̄_{1}ˆ ā_{i}^{p}/A) = tp(b̄ˆ ā_{i}^{p}/A) = tp(b̄ˆ ā_{i}^{p}/A), for i ≥ κ(D),

since b̄ ∈ B and I_{p} is indiscernible over B. Thus

|{i ∈ I′ : tp(b̄ˆ ā_{0}^{p}/A) = tp(b̄_{1}ˆ ā_{i}^{p}/A)}| > κ(D),

but then, all ā_{1} ∈ I′ but a subset of cardinality less than κ(D) are indiscernibles over b̄ ∪ b̄_{1} and so

|{i ∈ I′ : tp(b̄ˆ ā_{0}^{p}/A) ≠ tp(b̄_{1}ˆ ā_{i}^{p}/A)}| < κ(D).

The claim follows since I_{p} ⊂ I′.

Suppose by way of contradiction that there are p ≠ q ∈ Γ with

tp(⟨ā_{i}^{p} : i < κ(D)⟩/A) = tp(⟨ā_{i}^{q} : i < κ(D)⟩/A).

Since p ≠ q, there is b̄ ∈ B and ϕ(x̄, ȳ) such that ϕ(x̄, b̄) ∈ p and ¬ϕ(x̄, b̄) ∈ q. By construction, ⊧ ϕ[ā_{i}^{p}, b̄] and ⊧ ¬ϕ[ā_{i}^{q}, b̄], for all i < κ(D). Let f be an elementary mapping such that f ↾ A = id_{A} and f(ā_{i}^{p}) = ā_{i}^{q} for i < κ(D). Clearly, f exists by assumption on p and q. Call b̄_{1} = f^{−1}(b̄). By applying the claim, we know that |{i < κ(D) : tp(b̄ˆ ā_{0}^{p}/A) ≠ tp(b̄_{1}ˆ ā_{i}^{p}/A)}| < κ(D), hence let ā_{i}^{p}, (i < κ(D)) such that tp(b̄ˆ ā_{0}^{p}/A) = tp(b̄_{1}ˆ ā_{i}^{p}/A). But, by definition of f, we know that tp(b̄_{1}ˆ ā_{i}^{p}/A) = tp(b̄ˆ ā_{i}^{q}/A). Hence tp(b̄ˆ ā_{0}^{p}/A) = tp(b̄ˆ ā_{i}^{q}/A). Since ϕ(x̄, b̄) ∈ tp(b̄ˆ ā_{0}^{p}/A), we then must have ⊧ ϕ[ā_{i}^{q}, b̄], the desired contradiction.

We now prove the last significant ingredient of the Homogeneity Spectrum Theorem.

Theorem 5.8. Let λ ≥ |D| be such that λ^{<λ} > λ. Suppose that D is stable but not in λ If D does not satisfy (∗λ) then there is no (D, λ)-homogeneous model of cardinality λ.

Proof. By way of contradiction, assume that M is a (D, λ)-homogeneous model of cardinality λ. Let {A_{α} | α < cf(λ)} be an increasing continuous chain of sets such that |A_{α}| < λ and M = ⋃_{α<cf(λ)} A_{α}.

Since D is not stable in λ, there is a D-set B of cardinality λ such that |S_{D}(B)| > λ. Then, by Lemma 2.3 we may assume that B ⊆ M since M is (D, λ)-homogeneous. Hence |S_{D}(M)| > λ.

We first claim that for each p ∈ S_{D}(M), there is α < cf(λ) such that p does not split over A_{α}.

Suppose not. Let p ∈ S_{D}(M) such that p splits over every A_{α}. If λ is regular, then λ = cf(λ) and this implies that D satisfies (∗λ), a contradiction. Suppose that λ is singular. For each α < cf(λ), choose b̄_{α}, c̄_{α} in M and ϕ_{α}(x, ȳ) such that tp(b̄_{α}/A_{α}) = tp(c̄_{α}/A_{α}) and ϕ_{α}(x, b̄_{α}) ∈ p and ¬ϕ_{α}(x, c̄_{α}) ∈ p. Then p ↾ {b̄_{α}, c̄_{α}} is not realized in A_{α}. Set A := ⋃_{α<cf(λ)}{b̄_{α}, c̄_{α}}. Then p ↾ A is not realized in ⋃_{α<cf(λ)} A_{α} = M. This contradicts the (D, λ)-homogeneity of M since |A| ≤ cf(λ) < λ. This proves the claim.

Now since |S_{D}(M)| > λ, by the pigeonhole principle, there exists Γ ⊆ S_{D}(M) of cardinality λ^{+} and α < cf(λ), such that if p ∈ Γ, then p does not split over A_{α}. Since A_{α} ⊆ M of cardinality less than λ and M is (D, λ)-homogeneous, we are in the situation of the previous lemma. Thus for each p ∈ Γ there is {ā_{i}^{p} : i ≤ ω} an indiscernible set over A_{α} such that

p ≠ q if and only if tp(⟨ā_{i}^{p} : i < ω⟩/A_{α}) ≠ tp(⟨ā_{i}^{q} : i < ω⟩/A_{α}).

Using the (D, λ)-homogeneity of M and the fact that |A_{α}| < λ, construct {b̄_{i}^{p} : i ≤ ω} ⊆ M for each p ∈ Γ with the following two properties:

(1) tp(⟨b̄_{j}^{p} : j ≤ i⟩/A_{α}) = tp(⟨ā_{j}^{p} : j ≤ i⟩/A_{α})

(2) If tp(⟨ā_{j}^{p} : j ≤ i⟩/A_{α}) = tp(⟨ā_{j}^{q} : j ≤ i⟩/A_{α}), then b̄_{j}^{p} = b̄_{j}^{q} for every j ≤ i.

We now show that

b̄_{ω}^{p} ≠ b̄_{ω}^{q}, if p ≠ q ∈ Γ. (*)

Let p, q ∈ Γ such that p ≠ q. By construction, we have that

tp(⟨ā_{j}^{p} : j < ω⟩/A_{α}) ≠ tp(⟨ā_{j}^{q} : j < ω⟩/A_{α}).

Hence, there is a minimal i < ω such that

tp(ā_{0}^{p}, …, ā_{i}^{p}ā_{i+1}^{p}/A_{α}) ≠ tp(ā_{0}^{q}, …, ā_{i}^{q}ā_{i+1}^{q}/A_{α}).

By minimality of i and (1), we have

tp(b̄_{0}^{p}, …, b̄_{i}^{p}/A_{α}) = tp(b̄_{0}^{q}, …, b̄_{i}^{q}/A_{α}). (**)

Now, we have the following equations

tp(b̄_{0}^{p}, …, b̄_{i}^{p}b̄_{ω}^{p}/A_{α}) = tp(ā_{0}^{p}, …, ā_{i}^{p}ā_{ω}^{p}/A_{α})  (by definition (1))
= tp(ā_{0}^{p}, …, ā_{i}^{p}ā_{i+1}^{p}/A_{α})  (by indiscernibility)
≠ tp(ā_{0}^{q}, …, ā_{i}^{q}ā_{i+1}^{q}/A_{α})  (by choice of i)
= tp(ā_{0}^{q}, …, ā_{i}^{q}ā_{ω}^{q}/A_{α})  (by indiscernibility)
= tp(b̄_{0}^{q}, …, b̄_{i}^{q}b̄_{ω}^{q}/A_{α})  (by definition (1))

Hence (*) follows from the previous equations, definition (2) and (**).

Therefore (*) implies that we have |Γ| many different elements b̄_{ω}^{p} ∈ M. This is a contradiction, since

|Γ| = λ^{+} > λ = ∥M∥.

This finishes the proof.

We can now present the Homogeneity Spectrum Theorem.

Theorem 5.9 (The Homogeneity Spectrum). There exists a (D, λ)-homogeneous model of cardinality λ if and only if λ ≥ |D| and either D is stable in λ or λ^{<λ} = λ.

Proof. The proof is divided into 5 cases.

Case 1: λ < |D|. Then, there can be no (D, λ)-homogeneous model M of cardinality λ, since we require that D(M) = D, and there are not enough elements in M to realize all the types in D.

Case 2: λ ≥ |D| and λ^{<λ} = λ. Then, there exists a (D, λ)-homogeneous

model M of cardinality λ by Theorem 5.1. Case 3: λ ≥ |D| and D is stable in λ. Then, there is a (D, λ)-homogeneous

model M of cardinality λ by Theorem 5.6. Case 4: λ ≥ |D|, λ^{<λ} > λ and D is not stable. Then, by Corollary 4.7, D satisfies (∗λ). Hence D satisfies (B ∗ λ) by Lemma 4.4. Therefore, there is no (D, λ)-homogeneous model M of cardinality λ by Theorem 5.2.

Case 5: λ ≥ |D|, λ^{<λ} > λ and D is stable but not in λ. This case is divided into two sub-cases according to whether D satisfies (∗λ). If D does satisfy (∗λ), then D also satisfies (B ∗λ) by Lemma 4.4. Therefore the result follows from Theorem 5.2. If D does not satisfy (∗λ), then by Theorem 5.8 we have no (D, λ)-homogeneous model of cardinality λ.

The proof is complete.

6. Local Stability and Local Homogeneity in Finite Diagrams

In this section, we set the necessary definitions to localize the results of this paper. We fix a type and show that all the results of this paper hold inside the set of realizations of this fixed type, with the appropriate local definitions.

Fix Σ(x̄) a set of L(T)-formulas, maybe over a D-set of parameters. We localize the notion of types with respect to Σ. For a model M, denote by Σ(M) the set of realizations of Σ(x̄) in M. In the following definition, Σ is used as a superscript to avoid clashes with the notation set so far.

Definition 6.1. For A a D-set, let

S_{D}^{Σ}(A) = {tp(c/A) | A ∪ c̄ is a D-set and c realizes Σ}.

Although the definition makes sense for any A ⊆ M, it will only be used when A ⊆ Σ(M).

Definition 6.2. A model M is (D, λ, Σ)-homogeneous, if M realizes every type in S_{D}^{Σ}(A), for each A ⊆ Σ(M) of cardinality less that λ.

We can relax the monster model assumption to:

Hypothesis 6.3. There exists a D-model ℭ such that ℭ is (D, κ̄, Σ)-homogeneous, for some κ̄ larger than any cardinal needed in this paper.

We will work inside Σ(ℭ). The results of Section 2 hold relativized to realizations of Σ. Thus, ℭ can be assumed to contain every D-set A ⊆ Σ(M), for any D-model M. And also ℭ is homogeneous with respect to subsets of Σ(ℭ). Write S_{D}^{Σ}(A) for S_{D}^{Σ}(A, ℭ), (note A ⊆ Σ(ℭ) is always assumed).

Here are the local version of stability and order:

Definition 6.4. (1) D is (λ, Σ)-stable if |S_{D}^{Σ}(A)| ≤ λ for every A ⊆ Σ(ℭ) of

cardinality λ.

(2) D is Σ-stable if D is (λ, Σ)-stable for some cardinal λ.

Definition 6.5. (1) D has the (λ, Σ)-order property if there exist a formula ϕ(x̄, ȳ) ∈ L(T) and a set {ā_{i} | i < λ} ⊆ Σ(ℭ), such that

⊧ ϕ[ā_{i}, ā_{j}] if and only if i < j < λ.

(2) D has the Σ-order property if D has the (λ, Σ)-order property for every cardinal λ.

Then, all the statements of Section 3 are true provided all the sets mentioned are taken inside Σ(ℭ) and the local notions S_{D}^{Σ}(A), Σ-order property, Σstability are used instead. Most of the proofs can be used without modification. The only kind of changes which are occasionally required are the obvious ones, for example: In the proof of Remark 3.4 add the requirement Σ(c̄_{i}) for i < λ in the list of conditions, as well as a requirement that {c̄_{i} | i < λ} be indiscernible over the parameters of Σ. In the proof of Theorem 3.9, choose {ā_{i} | i < μ^{+}} ⊆ Σ(ℭ) etc. The main result is Section 3 is the local version of the stability/order dichotomy. Note that the local version of the stability/order dichotomy is known in more general cases [GrLe1].

Theorem 6.6. D is Σ-stable if and only if D does not have the Σ-order property.

The definition of splitting is unchanged. The difference is that only types inside S_{D}^{Σ}(A) for subsets A ⊆ Σ(ℭ) are considered. Here is the (local) definition of strong splitting:

Definition 6.7. Let A ⊆ Σ(ℭ) and p ∈ S_{D}^{Σ}(A). The type p splits strongly over B ⊆ A if there exist {c̄_{n} | n < ω} ⊆ Σ(ℭ), an indiscernible sequence over B, and a formula ϕ(x̄, ȳ) such that ϕ(x̄, c̄_{1}) ∈ p, ¬ϕ(x̄, c̄_{2}) ∈ p.

Define the localized version of (∗λ) as follows:

Definition 6.8. D satisfies (Σ ∗ λ) if there exists an increasing and continuous chain {A_{i} | i ≤ λ}, with A_{i} ⊆ Σ(ℭ), and a type p ∈ S_{D}^{Σ}(A) such that p ↾ A_{i+1} splits over A_{i}.

The localized version of (B ∗ λ) is defined similarly using subsets of Σ(ℭ), call it (ΣB∗λ). For (C ∗λ), use subsets of Σ(ℭ) and the definition of strong splitting above for (C ∗ λ), call it (ΣC ∗ λ)

The same lemmas can be shown with very similar proofs using the homogeneity of ℭ inside Σ(ℭ). We obtain:

Theorem 6.9. D is not Σ-stable if and only if (Σ ∗ λ) holds for every cardinal λ if and only if (ΣB ∗ λ) holds for every cardinal λ.

Definition 6.10. Let

κ(Σ, D) = min{κ | For all p ∈ S_{D}^{Σ}(A), A ⊆ Σ(ℭ), there is B ⊆ A, |B| < κ such that

p does not split strongly over B }.

If it is undefined, we let κ(D, Σ) = ∞.

Theorem 6.11. If D is (λ, Σ)-stable, then κ(Σ, D) ≤ λ.

This allows us to obtain a local version of the stability spectrum. The cardinal κ in the statement below is κ(Σ, D) and the cardinal λ the first cardinal such that D is (λ, Σ)-stable.

Theorem 6.12. Either D is not Σ-stable or D is Σ-stable and there exists cardinals κ ≤ λ < ℶ_{(2^{|T |})^{+}} such that for every cardinal μ D is (μ, Σ)-stable if and only if μ ≥ λ and μ^{<κ} = μ.

Again making the necessary adaptations, the local homogeneity spectrum follows:

Theorem 6.13. There exists a (D, λ, Σ)-homogeneous model of cardinality λ if and only if λ ≥ |S_{D}^{Σ}(∅)| and λ^{<λ} = λ or D is (λ, Σ)-stable.

The last four theorems are new.

References

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

[BaSh1] John T. Baldwin and Saharon Shelah. The primal framework. I. Annals of Pure and Applied Logic, 46:235–264, 1990.

[BaSh2] John T. Baldwin and Saharon Shelah. The primal framework. II. Smoothness. Annals of Pure and Applied Logic, 55:1–34, 1991.

[BaSh3] John T. Baldwin and Saharon Shelah. Abstract classes with few models have ‘homogeneous-universal’ models. Journal of Symbolic Logic, 60:246–265, 1995.

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

[Gr1] Rami Grossberg. Indiscernible sequences in a model which fails to have the order property, Journal of Symbolic Logic 56 (1991) 115-123.

[Gr2] Rami Grossberg. On chains of relatively saturated submodels of a model without the order property, Journal of Symbolic Logic 56 (1991) 123-128.

[GrHa] Rami Grossberg and Bradd Hart, The classification theory of excellent classes, Journal of Symbolic Logic 54 (1989) pages 1359–1381.

[GrLe1] Rami Grossberg and Olivier Lessmann, Remarks on local stability and the local order property. Archive for Mathematical Logic in press.

[GrLe2] Rami Grossberg and Olivier Lessmann, The main gap for totally transcendental diagrams and abstract decomposition theorem. In preparation.

[GrSh1] Rami Grossberg and Saharon Shelah. On the number of nonisomorphic models of an infinitary theory which has the infinitary order property. I. Journal of Symbolic Logic, 51:302– 322, 1986.

[GrSh2] Rami Grossberg and Saharon Shelah. A nonstructure theorem for an infinitary theory which has the unsuperstability property. Illinois Journal of Mathematics, 30:364–390, 1986. Volume dedicated to the memory of W.W. Boone; ed. Appel, K., Higman, G., Robinson, D. and Jockush, C.

[HaSh] Bradd Hart and Saharon Shelah. Categoricity over P for first order T or categoricity for ϕ ∈ L_{ω_{1},ω} can stop at ℵ_{k} while holding for ℵ_{0}, ⋯, ℵ_{k−1}. Israel Journal of Mathematics, 70:219–235, 1990.

[HySh] T. Hyttinen and S. Shelah. Strong splitting in stable homogeneous models preprint.

[Ke] H. Jerome Keisler, Model theory for infinitary logic , North-Holland, 1971, Amsterdam.

[Ki] Henry A. Kierstead, Countable models of ω_{1}-categorical theories in admissible languages, Annals Math. Logic 19(1980), pages 127–175.

[KlSh] Oren Kolman and Saharon Shelah. Categoricity for T ⊆ L_{κ,ω}, κ measurable. Fundamenta Mathematicae.

[Le1] Olivier Lessmann, Ranks and Pregeometries in Finite Diagrams, Annals of Mathematical Logic, submitted.

[Le2] Olivier Lessmann, Abstract group configuration, Preprint.

[MaSh] Michael Makkai and Saharon Shelah. Categoricity of theories in L_{κω}, with κ a compact cardinal. Annals of Pure and Applied Logic, 47:41–97, 1990.

[Mr] Leo Marcus, A prime minimal model with an infinite set of indiscernibles, Israel Journal of Mathematics, 11, (1972), 180-183.

[Sh b] Saharon Shelah, Classification Theory and the Number of Nonisomorphic Mod-

els, Rev. Ed., North-Holland, 1990, Amsterdam. [Sh h] Saharon Shelah. Universal classes, in preparation.

[Sh3] Saharon Shelah, Finite diagrams stable in power, Annals Math. Logic 2, (1970), pages 69–118.

[Sh12] Saharon Shelah, A combinatorial problem, stability and order in infinitary languages, Pacific Journal of Math. (1972) pages 23–31.

[Sh48] Saharon Shelah, Categoricity in ℵ_{1} of sentences in L_{ω_{1},ω}(Q), Israel Journal of Math. 20 (1975), pages 127–148.

[Sh54] Saharon Shelah, The lazy model theorist’s guide to stability, Proc. of a Symp. in Louvain, March 1975, ed. P. Henrand, Logique et Analyse, 18eme annee, 71-72 (1975), pages 241–308.

[Sh87a] Saharon Shelah. Classification theory for nonelementary classes. I. The number of uncountable models of ψ ∈ L_{ω_{1},ω}. Part A. Israel Journal of Mathematics, 46:212–240, 1983.

[Sh87b] Saharon Shelah. Classification theory for nonelementary classes. I. The number of uncountable models of ψ ∈ L_{ω_{1},ω}. Part B. Israel Journal of Mathematics, 46:241–273, 1983.

[Sh88] Saharon Shelah. Classification of nonelementary classes. II. Abstract elementary classes. In Classification theory (Chicago, IL, 1985), volume 1292 of Lecture Notes in Mathematics, pages 419–497. Springer, Berlin, 1987. Proceedings of the USA–Israel Conference on Classification Theory, Chicago, December 1985; ed. Baldwin, J.T.

[Sh tape] Saharon Shelah. Classifying general classes. ICM Series. American Mathematical Society, Providence, RI, 1 videocassette (NTSC; 1/2 inch; VHS) (60 min.); sd., col, $49.00, 1988.

[Sh299] Saharon Shelah. Taxonomy of universal and other classes. In Proceedings of the International Congress of Mathematicians (Berkeley, Calif., 1986), volume 1, pages 154–162. Amer. Math. Soc., Providence, RI, 1987.ed. Gleason, A.M.

[Sh300] Saharon Shelah. Universal classes. In Classification theory (Chicago, IL, 1985), volume 1292 of Lecture Notes in Mathematics, pages 264–418. Springer, Berlin, 1987. Proceedings of the USA–Israel Conference on Classification Theory, Chicago, December 1985; ed. Baldwin, J.T.

[Sh394] Saharon Shelah. Categoricity of abstract classes with amalgamation. preprint.

[Sh472] Saharon Shelah. Categoricity for infinitary logics II. preprint.

[Sh576] Saharon Shelah. On categoricity for abstract elementary classes: in three cardinals implies existence of a model in the next. To appear in Israel Journal of Mathematics

[Sh 600] Saharon Shelah. Categoricity in abstract elementary classes: Going up inductive step. in

preparation.

[ShVi] Shelah, Saharon and Villaveces, Andrés. Toward categoricity for classes with no maximal models. Ann. Pure Appl. Logic 97 (1999), 1–25.

Department of Mathematical Sciences, Carnegie Mellon University, Pitts-

burgh, PA 15213

    E-mail address: rami@andrew.cmu.edu
    E-mail address: lessmann+@andrew.cmu.edu