THE EQUALITY S1 = D = R

R. GROSSBERG, A. KOLESNIKOV, I. TOMAŠIĆ, AND M. VANDIEREN

Abstract. The new result of this paper is that for θ(x; a)-stable (a weakening of “T is stable”) we have

S1[θ(x; a)] = D[θ(x; a), L, ∞] = R[θ(x; a), L, ∞].

S1 is Hrushovski’s rank. This is an improvement of a result of Kim and Pillay, who for simple theories under the (strong) assumption that either of the ranks be finite obtained the same identity. Only the first equality is new, the second equality is a result of Shelah from the seventies.

We derive it by studying localizations of several rank functions, we get:

Theorem 0.1 (Main Theorem). Suppose that μ is regular satisfying μ ≥ |T |^{+}, p is a finite type, and Δ is a set of formulas closed under Boolean operations. If

(1) R[p, Δ, μ^{+}] < ∞ or

(2) p is Δ-stable and μ satisfies: for every sequence of cardinals {μ_{i} < μ | i < |Δ| + ℵ_{0}} we have that ∏_{i<|Δ|+ℵ_{0}} μ_{i} < μ holds,

then S[p, Δ, μ^{+}] = D[p, Δ, μ^{+}] = R[p, Δ, μ^{+}].

The S rank above is a localized version of Hrushovski’s S1 rank. This rank, as well as our systematic use of local stability, allows us to get a more conceptual proof of the equality of D and R, which is an old result of Shelah. A particular (asymptotic) case of the theorem offers a new sufficient condition for the equality of S1 and D[·, L, ∞]. We also manage, due to a more general approach, to avoid some combinatorial difficulties present in Shelah’s original exposition.

Introduction

Historically the introduction and implementation of several rank functions have led to significant developments in the classification of theories. In 1965, Morley published a partial solution to Łǒs’ conjecture [Lo], requiring that the similarity type of the theory be countable [Mo]. Later in the seventies, Saharon Shelah solved Łǒs’ conjecture in full generality [Sh31]. Although Morley and Shelah’s approaches are structurally different, they implement a common tool, a rank function. Morley introduced a rank function which is now referred to as the Morley rank and is often denoted by RM(p), where p is set of formulas (RM(p) := R[p, L, ℵ_{0}] see Definition 1.1).

Date: March 28, 2002. AMS Subject Classification: Primary: 03C45, 03C52. Secondary: 03C05 and 03C55.

Keywords: Stable theory, stable formula, Rank, Degree.

For the general solution to Łǒs’ conjecture, Shelah identified an important class of theories, the superstable theories. To study these theories, he introduced several tools in [Sh 10], including a rank called Deg[p] (Deg[p] := Deg[p, L, |T |^{++}] see Definition 1.11), and, to characterize stable theories, the function R[p, Δ, ℵ_{0}] for p a set of formulas and Δ a finite set of formulas.

The introduction of these rank functions caught the attention of model theorists. Daniel Lascar in his review of [Sha] for the Mathematical Reviews wrote: “Ranks are the main combinatorial device in stability.” John Baldwin investigated the Morley rank, and in his Ph.D. thesis Baldwin proved that an ℵ_{1}-categorical theory has finite Morely rank (see [Ba1]). For his solution, Baldwin introduced a rank function which was later named D[x = x, L, ∞] by Shelah. Among other results Baldwin showed that D[p, L, ∞] and RM[p] coincide and are finite for ℵ_{1}-categorical theories (this was a predecessor of Theorem 0.1).

Daniel Lascar in [La2] introduced the Lascar rank, U(p) (defined for complete types p), suitable for the study of superstable theories (it is denoted by L(p) in [Sha]). Lascar’s rank is different than the ranks we discuss here (even for differentially closed fields, see [HS]).

In 1974, Baldwin and Blass introduced the basic axiomatic properties of rank functions in [BaBl]; the connected property appears in Lascar [La2]. Later (in his book [Sha] from 1978), Shelah presented two other families of rank functions D[p, Δ, λ] and R[p, Δ, λ]. The first is a generalization of Deg[p] (as Deg[p] = D[p, L, |T |^{++}]) and the latter is a generalization of the Morley rank (as RM[p] = R[p, L, ℵ_{0}]). The functions D[p, L, ∞] and R[p, L, ∞] (the latter often denoted by ∞-rank[p]) are well understood and their basic properties appear in several monographs (e.g. John Baldwin’s book [Ba2], Steve Buechler’s book [Bu] and Anand Pillay’s [Pi]). Shelah’s [Sh 10] ends with the question about the relation of R[p, Δ, ∞] and Deg[p]. The question was answered by him in his book. Unfortunately, the deep results in Section 3 of Chapter II [Sha] relating the rank functions R[p, Δ, λ] and D[p, Δ, λ] were not covered by any of the subsequent expositions known to us. (E. g. if T is superstable, then R[x = x, L, ∞] < |T |^{+}.)

In the early nineties, Ehud Hrushovski [Hr] introduced the function S1 that he used to study simple unstable groups. Hrushovski’s S1 was defined only for finite values. In the unpublished paper [Hr], he introduced and proved the independence theorem for theories with finite S1 rank. This theorem was later generalized by Kim and Pillay [KP] for all simple theories. Some of Hrushovski’s early results concerning this rank appeared in a restricted form in his papers with Pillay [HP1] and later with Chatzidakis [CH].

This paper started by our attempt to understand some of the more difficult results in Section 3 of Chapter II [Sha]. To our surprise, after writing up complete proofs to Shelah’s theorems, we realized that the main combinatorial dividing line is an implicit use of a rank function similar to the rank S1; and the latter rank function was introduced explicitly only more than 20 years later in a geometric context by Ehud Hrushovski. More precisely, we introduce and study a new rank function S[p, Δ, λ]. It turns out that S[p, L, λ] = S1[p] for sufficiently large λ. This gives a more conceptual proof of R = D than Shelah had.

Equality of D[p, L, ∞] and S1[p, L] was previously shown to be true by Kim and Pillay [KP] under the assumption that T is simple when either D[p, L, ∞] or S1[p] are finite. Here we get equality also for infinite valued rank, but we assume local stability.

From Shelah’s proofs we extract relativized notions of Δ-stability and Δsuperstability that clarify the arguments significantly (compare with Harnik and Harrington [HH], Bouscaren [Bo] and with Grossberg and Lessmann [GrLe]). The use of local stability has paid off as we can avoid the combinatorial difficulties in the proof of the asymptotic behavior of R, see our Proposition 3.4 and Shelah’s Theorem II.3.13 in [Sha].

To lower the complexity of Shelah’s original treatment, we introduce the rank function Deg (which generalizes Shelah’s function from [Sh 10] and is closely related to D). We show that under local stability the D-rank has a simpler equivalent definition that is “almost like” the definition of Deg.

Lastly, a function S2 is introduced, it relates to the S1-rank in a similar way as Deg[p, Δ, λ] relates to R[p, Δ, λ]. It is shown that when S1[p] = R[p, L, ∞] then also S1[p] = S2[p].

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 ℭ.

We thank John Baldwin and Olivier Lessmann for reading a preliminary version of this paper and offering us their comments. We also thank Ehud Hrushovski for clarifying the history of the S1-rank.

1. Local stability and the R-rank

We start by recalling the definitions of existing rank functions. We quote their basic properties and connections with (local) stability.

Recall from [Sha]:

Definition 1.1. Let p be a set of formulas in x, Δ ⊆ {φ(x; y) | φ ∈ F ml(L(T))} and λ a cardinality (can be finite) or ∞.

(1) R[p, Δ, λ] ≥ α is defined by induction on α:

(a) R[p, Δ, λ] ≥ 0, if p is consistent;

(b) for α limit, R[p, Δ, λ] ≥ α if R[p, Δ, λ] ≥ β for every β < α

(c) R[p, Δ, λ] ≥ α + 1 if for every finite q ⊆ p and every μ < λ there are {q_{i} | i ≤ μ} explicitly contradictory Δ-types such that R[q ∪ q_{i}, Δ, λ] ≥ α for every i ≤ μ. (When λ = ∞ we interpret it as no restriction on μ).

(2) For an ordinal α denote by R[p, Δ, λ] = α the statement

R[p, Δ, λ] ≥ α and R[p, Δ, λ] ≱ α + 1.

(3) We write R[p, Δ, λ] = ∞ if R[p, Δ, λ] ≥ α for every ordinal α.

Remarks 1.2. (1) R[p, L, ℵ_{0}] is Morley’s rank often denoted by RM[p].

(2) R[p, L, ∞] is often called infinity rank, Buechler (in [Bu]) denotes it by R^{∞}[p].

(3) R[p, Δ, ℵ_{0}] is denoted in Pillay ([Pi]) by R_{ℵ_{0}}^{Δ}[p].

(4) A word on Δ: While many results apply for arbitrary Δ and in developing the basics of stability theory the case when Δ = {φ(x; y)} is quite important. In this paper our focus is in a fairly large Δ. Especially the case when Δ = L or Δ is a countable fragment of L containg a given formula.

The following are the basic well known properties of the R-rank:

Fact 1.3. For sets of formulas, p and Δ, and a cardinal λ Invariance: For f ∈ Aut(ℭ), R[p, Δ, λ] = R[f(p), Δ, λ]. Monotonicity: For sets of formulas, p and q, whenever p ⊢ q, μ ≤ λ

and Δ_{1} ⊆ Δ_{2}, we have that R[p, Δ_{1}, λ] ≤ R[q, Δ_{2}, μ]. Finite character: There is a finite subset q ⊆ p, such that R[p, Δ, λ] =

R[q, Δ, λ]. Ultrametric property: For λ ≥ ℵ_{0}

R[p ∪ { ⋁_{1≤l≤n} ψ_{l}}, Δ, λ] = Max_{1≤l≤n} R[p ∪ {ψ_{l}}, Δ, λ].

Extension property: For λ ≥ ℵ_{0} and a set A ⊇ dom(p), there exists a

complete type q ⊇ p with domain A such that R[p, Δ, λ] = R[q, Δ, λ]. Connected: Let p be a finite set of formulas in x. If

R[p, Δ, λ] = α < ∞ then for every β < α there exists a Δ-type q such that R[p ∪ q, Δ, λ] = β.

As we point out below, the R-rank can be used to capture stabilitytheoretic properties of theories, including local stability and superstability. In order to establish the framework, recall:

Definition 1.4. Let p be a type in x and let Δ be a set of formulas such that for all φ ∈ Δ, φ = φ(x; y_{φ}).

(1) A type q ∈ S_{Δ}^{ℓ(x)}(A) is called a (p, Δ)-type if p ∪ q is consistent. The set of all (p, Δ)-types is denoted by S_{p,Δ}(A);

(2) p is (Δ, λ)-stable if for all A, |A| ≤ λ, we have |S_{p,Δ}(A)| ≤ λ;

(3) p is Δ-stable if there is λ such that p is (Δ, λ)-stable;

(4) p is Δ-superstable if there is λ such that p is (Δ, μ)-stable for all μ ≥ λ;

(5) φ(x; y) has the order property over p if there is a set {a_{n} | n < ω} with ℓ(a_{n}) = ℓ(y) such that p ∪ {φ(x; a_{n})^{if k≤n} | n < ω} is consistent for all k < ω;

(6) Δ has the order property over p if there is φ(x; y) ∈ Δ that has the order property over p.

It turns out that such a definition of local stability is well-behaved, generalizes the usual definitions (as x = x being L-(super)stable coincides with T being (super)stable), and allows us to develop the theory in a standard way; see e. g. [Sha] I.2.10, II.2.14, II.3.13. We can get:

Theorem 1.5. Let p be a type in x and let Δ be a set of formulas. The following are equivalent:

(1) For all λ ≥ ℵ_{0} such that λ = λ^{|Δ|}, p is (Δ, λ)-stable;

(2) p is Δ-stable;

(3) Δ does not have the order property over p.

By using the standard tree characterization for the R-rank as in [Sha] II.2.2, it is possible to characterize local stability of types in the following way:

Theorem 1.6. Suppose p is a set of formulas in x and φ(x; y) is a formula. The following are equivalent

(1) R[p, φ, 2] < ω,

(2) R[p, φ, 2] < ∞,

(3) R[p, φ, ℵ_{0}] < ∞,

(4) R[p, φ, ∞] < ∞,

(5) the formula φ does not have the order property over p,

(6) p is {φ}-stable.

Corollary 1.7. Suppose p and Δ are sets of formulas in x. If R[p, Δ, ∞] < ∞, then p is Δ-stable.

Proof. Suppose R[p, Δ, ∞] < ∞. By monotonicity, R[p, φ, ∞] < ∞ for every φ ∈ Δ. Theorem 1.6 implies that for all φ ∈ Δ, φ does not have the order property over p. Thus Δ does not have the order property. By Theorem 1.5 we get that p is Δ-stable. ⊣

Remark 1.8. In fact R[p, Δ, ∞] < ∞ is equivalent to Δ-superstability of p, for Δ closed under Boolean operations (see Theorem 2.16).

The following was introduced by Shelah (in [Sha]) to study superstable theories

Definition 1.9. D[p, Δ, λ] ≥ 0 if p is consistent. D[p, Δ, λ] ≥ α, for α limit, if for every β < α, D[p, Δ, λ] ≥ β. D[p, Δ, λ] ≥ α + 1 if for every finite q ⊆ p, for every μ < λ, there are a finite r ⊇ q, φ(x; y) ∈ Δ, n < ω, and {a_{i} : i ≤ μ} such that:

(1) set {φ(x; a_{i}) : i ≤ μ} is n-contradictory over r;

(2) for every i ≤ μ, D[r ∪ φ(x; a_{i}), Δ, λ] ≥ α.

Remarks 1.10. (1) Buechler [Bu] denotes by D^{∞}[p] the function D[p, L, ∞]

from Definition 1.9.

(2) One of the reasons to require the formulas {φ(x; a_{i}) | i ≤ μ} to be contradictory over some extension of q, is to make sure the rank has the monotonicity property. Clearly, when Δ = L this requirement can be dropped. In the next section we prove that we don’t need to consider the arbitrary finite extension in the definition of D if p is finite, Δ is closed under Boolean operations and p is Δ-stable.

(3) It is well-known that the D-rank is not equal to R-rank in some situations.

(4) The D rank obeys most of the basic properties of the R-rank from Fact 1.3.

We introduce the Deg-rank, which is a simplification of the D-rank. The motivation is to eliminate the extra requirement of having to look at all possible finite extensions of q in the definition of D. We succeed in using Deg, instead of D, to characterize local superstability of types, to find bounds for the D-rank and to eventually prove the equality of S1, R, and D under certain conditions. The price to pay for using Deg instead of D is the extra requirement: θ(x; y) ∈ Δ. At the end of Section 2 we show how to remove it and still have the above mentioned equalities.

The Deg-rank is an interpolant of Shelah’s ranks: D[p, Δ, λ] (from [Sha]) and Deg[p] (from [Sh 10]).

Definition 1.11. Deg[p, Δ, λ] ≥ 0 if p is consistent. Deg[p, Δ, λ] ≥ δ, for δ limit, if for every α < δ, Deg[p, Δ, λ] ≥ α. Deg[p, Δ, λ] ≥ α + 1 if for every finite q ⊆ p, for every μ < λ, there exist φ(x; y) ∈ Δ, n < ω and {a_{i} : i ≤ μ} such that:

(1) set {φ(x; a_{i}) : i ≤ μ} is n-contradictory, namely, for all i_{1} < ⋯ < i_{n} ≤ μ we have that ⊧ ¬∃x ⋀_{k=1}^{n} φ(x; a_{i_{k}});

(2) for every i ≤ μ, Deg[q ∪ {φ(x; a_{i})}, Δ, λ] ≥ α.

Remarks 1.12. (1) The rank Deg[p, L, |T |^{++}] is Deg[p] in [Sh 10].

(2) When Δ = L, then trivially Deg[p, Δ, λ] = D[p, Δ, λ]. When Δ is a proper subset of the set of formulas of L, then the ranks D and Deg are different even for some totally categorical theories.

(3) Deg[p, L, (2^{|T |})^{++}] is what Baldwin in [Ba2] calls the continuous rank, denoted by R_{C}[p]. The same rank is denoted by Pillay (in page 72 of [Pi]) as D(p). Notice that by the Normalization lemma, Lemma 1.16 and Proposition 1.15, Deg[p, L, (2^{|T |})^{++}] = Deg[p, L, |T |^{++}].

It is not difficult to verify that the analogs to properties in Fact 1.3 also hold for Deg.

The following is a routine exercise (the first inequality being trivial):

Proposition 1.13. For every p, Δ and λ ≥ ℵ_{1},

Deg[p, Δ, λ] ≤ D[p, Δ, λ] ≤ R[p, Δ, λ].

The Deg-rank can be used to characterize (local) superstability, under the assumption of (local) stability. To show that, we need the tree-characterization and normalization lemmas for Deg-rank. First we define the trees.

The following is a special case of Definition II.3.3 of [Sh 10]:

Definition 1.14. Let α be an ordinal and μ a cardinal. We call h is (Δ, α)-function for x iff h : ds(α) → Δ × ω, where

ds(α) := {η ∈ ^{ω>}α : ∀ℓ < ℓ(η) − 1 (η[ℓ] > η[ℓ + 1])} and h(η) = ⟨ψ_{η}(x; y), n_{η}⟩.

For U ⊆ ds(α) define

Γ_{μ}^{U}(θ(x; a), h) :=

{∃x[θ(x; a) ∧ ⋀_{0<ℓ≤ℓ(η)} ψ_{η↾ℓ}(x; y_{η↾ℓ,ν↾ℓ})] | η ∈ U ∪ {⟨⟩}, ν ∈ ^{ℓ(η)}μ}∪

{¬∃x[⋀_{i∈w} ψ_{η}(x; y_{η,νˆ i}) | η ∈ U, w ⊆ μ, |w| = n_{η}, ν ∈ ^{ℓ(η)−1}μ}.

The following is an important technical property of the previous trees, obtained by using Compactness:

Proposition 1.15. Let α, μ, θ(x; a), Δ and h be as in the previous definition.

Γ_{μ}^{ds(α)}(θ(x; a), h) is consistent ⟺ Γ_{λ}^{ds(α)}(θ(x; a), h) is consistent ∀λ ≥ ℵ_{0}.

A proof similar to the one of Theorem II.3.6 in [Sh 10] gives:

Lemma 1.16 (Tree characterization lemma for Deg). Let θ(x; a) be given and let cf μ > |α| + |T |. The following are equivalent:

(1) Deg[θ(x; a), Δ, μ^{+}] ≥ α;

(2) There exists a (Δ, α)-function h in x such that Γ_{μ}^{ds(α)}(θ(x; a), h) is consistent.

Corollary 1.17. Let μ > |T | + ℵ_{0} be a regular cardinal. If Deg[θ(x; a), Δ, μ^{+}] ≥ μ then there exists a (Δ, μ)-function h such that Γ_{μ}^{ds(μ)}(θ(x; a), h) is consistent.

The following lemma asserts that when α ≥ |T |^{+}, the tree of formulas given by h in the Lemma 1.16 depends only on the length of η.

Lemma 1.18 (Normalization Lemma). Let θ(x; a) be given. Deg[θ(x; a), Δ, |T |^{++}] ≥ |T |^{+} iff there exists {ψ_{k}, n_{k} | 0 < k < ω} such that for every α the set Γ_{|T |^{+}}^{ds(α)}(θ(x; a), h) is consistent for a (Δ, α)-function h satisfying h(η) = ⟨ψ_{ℓ(η)}(x; y), n_{ℓ(η)}⟩ ∀η ∈ ds(α).

We omit the proof since it is similar to the proof of Lemma II 3.7 in [Sh 10].

Corollary 1.19. Let θ(x; a) be given.

(1) Deg[θ(x; a), Δ, |T |^{++}] ≥ |T |^{+} iff Deg[θ(x; a), Δ, |T |^{++}] = ∞.

(2) Deg[θ(x; a), Δ, |T |^{++}] = ∞ iff there exists {⟨ψ_{k}, n_{k}⟩ | 0 < k < ω} ⊆ Δ × ω and there are {a_{η} | η ∈ ω>| T |^{+}} such that

∀η ∈ ^{ω}| T |^{+} {θ(x; a)} ∪ {ψ_{k}(x; a_{η↾k}) | k < ω}

is consistent and for every 0 < k < ω and for every η ∈ ^{k−1}| T |^{+} we have that

{ψ_{k}(x; a_{ηˆ i}) | i < |T |^{+}} is n_{k}-contradictory.

Proof. (1) Suppose that Deg[θ(x; a), Δ, |T |^{++}] ≥ |T |^{+}. By the Normalization Lemma there is h such that for every α the set Γ_{μ}^{ds(α)}(θ(x; a), h) is consistent. Using now the Compactness Theorem and Lemma 1.16 we get that Deg[θ(x; a), Δ, |T |^{++}] ≥ α for every α, namely Deg[θ(x; a), Δ, |T |^{++}] = ∞.

The converse is trivial.

(2) Apply the Normalization Lemma to Deg[θ(x; a), Δ, |T |^{++}] ≥ |T |^{+} to produce a (Δ, |T |^{+})-function h as there. Let {a_{η}} ⊧ Γ_{μ}^{ds(α)}(θ(x; a), h).

For the converse, use h(η) := ⟨ψ_{ℓ(η)}, n_{ℓ(η)}⟩ to show that Γ_{μ}^{ds(α)}(θ(x; a), h) is consistent for every infinite α and apply Lemma 1.16. ⊣

Definition 1.20. Let p be a type. We say that p has the λ-weak tree property over Δ if there are {φ_{n}(x; y_{n}) ∈ Δ | n < ω} ⊆ L(T) and {a_{η} | η ∈ ^{ω>}λ} such that the set p ∪ {φ_{n}(x; a_{η↾n}) | n < ω} is consistent for all η ∈ ^{ω}λ, and for all η ∈ ^{ω>}λ and all infinite S ⊆ λ the set {φ_{ℓ(η)+1}(x; a_{ηˆ α}) | α ∈ S} is inconsistent.

Using the compactness theorem from Corollary 1.19 we get:

Corollary 1.21. Let θ(x; a) be given. If Deg[θ(x; a), Δ, |T |^{++}] ≥ |T |^{+} then θ(x; a) has the λ-weak tree property over Δ for every λ ≥ ℵ_{0}.

Corollary 1.22. (1) If Deg[x = x, L, |T |^{++}] ≥ |T |^{+} then T is not su-

perstable.

(2) If Deg[θ(x; a), Δ, |T |^{++}] ≥ |T |^{+} then θ(x; a) is not Δ-superstable.

Proof. Let μ be given. By the previous corollary applied to λ := ℶ_{ω}(μ) we get that the theory is not stable in λ. ⊣

2. The main theorem

To prove Theorem 0.1 it suffices (by Proposition 1.13) to show that R[p, Δ, λ] ≤ D[p, Δ, λ]. To do this we introduce the S-rank and show that under certain conditions, R[p, Δ, λ] ≤ S[p, Δ, λ] and S[p, Δ, λ] ≤ D[p, Δ, λ]. The S-rank is a close relative of the rank function S1 introduced by Hrushovski in the early nineties, see [Hr], [HP1] and [CH]. The definition of S1-rank (see Section 3) is motivated by algebraic dimension theory. We find it surprising that in the quest to settle a combinatorial problem – the Main Theorem – one naturally discovers such a geometric object.

Definition 2.1. Let p be a set of formulas, not necessarily finite. Let Δ be a set of formulas, and let λ be a cardinal. In most of what follows, λ is an infinite uncountable cardinal; however, the definition makes sense for finite and countable λ as well.

S[p, Δ, λ] ≥ 0 if p is consistent. S[p, Δ, λ] ≥ α, for α limit, if for every β < α, S[p, Δ, λ] ≥ β. S[p, Δ, λ] ≥ α + 1 if for every finite p_{0} ⊂ p and for every μ < λ there exist ψ(x; y) ∈ Δ and {b_{i} | i < μ} such that

(1) S[p_{0} ∪ {ψ(x; b_{i})}, Δ, λ] ≥ α for every i < μ and

(2) S[p_{0} ∪ {ψ(x; b_{i}) ∧ ψ(x; b_{j})}, Δ, λ] < α for i ≠ j < μ. (When λ = ∞ we interpret it as no restriction on μ).

Similarly to Fact 1.3 we get Invariance, Monotonicity, Finite Character, Ultrametric and Extension properties for S-rank, provided we use Δ-types only.

Lemma 2.2. Given sets of formulas p, q, and Δ; Δ closed under Boolean operations:

Invariance of S rank: For f ∈ Aut(ℭ), S[f(p), Δ_{1}, λ] = S[p, Δ_{1}, λ]. Monotonicity of S rank: If q is a Δ-type, then S[p∪q, Δ, λ] ≤ S[p, Δ, λ]. Finite Character for S rank: There exists p_{0} ⊆_{finite} p such that S[p, Δ, λ] =

S[p_{0}, Δ, λ]. Ultrametric property for S rank: Let λ be infinite uncountable. For

n < ω and {ψ_{l} | l ≤ n} ⊂ Δ,

S[p ∪ { ⋁_{1≤l≤n} ψ_{l}}, Δ, λ] = Max_{1≤l≤n} S[p ∪ {ψ_{l}}, Δ, λ].

Extension property for S rank: Suppose Δ is closed under disjunctions. Given a set A ⊇ dom(p), there exists q ∈ S_{Δ}(A) such that S[p, Δ, λ] = S[p ∪ q, Δ, λ].

Theorem 2.3. Let Δ be a set of formulas in x closed under Boolean operations, θ(x; y) ∈ Δ; and let μ ≥ |T |^{+} be a regular cardinal. If θ(x; a) is Δ-stable, then S[θ(x; a), Δ, μ^{+}] ≤ Deg[θ(x; a), Δ, μ^{+}].

Proof. By induction on ordinals α, we show for all finite p that

S[p, Δ, μ] ≥ α ⇒ Deg[p, Δ, μ] ≥ α. (∗)_{α}

We show that it suffices to prove (∗)_{α} just for α < |T |^{+}:

Claim 2.4. Suppose that (∗)_{α} holds for every α < |T |^{+}. If S[p, Δ, μ^{+}] ≥ |T |^{+} then Deg[p, Δ, μ^{+}] = ∞

Proof. Since S[p, Δ, μ^{+}] ≥ |T |^{+} we have by the definition of S that S[p, Δ, μ^{+}] ≥ α for every α < |T |^{+}. By (∗)_{α} and the definition of Deg this gives Deg[p, Δ, μ^{+}] ≥ |T |^{+}. By an application of Corollary 1.22(1) we are done. ⊣

If α = 0, then (∗)_{α} holds by the definitions of the ranks. For α a limit ordinal, (∗)_{α} follows from the continuity of the ranks and the induction hypothesis. Let α = β + 1 be such that S[θ(x; a), Δ, μ] ≥ α and (∗)_{β} is true. By the definition of the S rank, there are {b_{i} | i < μ} and a formula φ(x; y) ∈ Δ such that (1) S[θ(x; a) ∧ φ(x; b_{i}), Δ, μ] ≥ β for every i < μ and

(2) S[θ(x; a) ∧ φ(x; b_{i}) ∧ φ(x; b_{j}), Δ, μ] < β for i ≠ j < μ.

Since θ(x; a) is Δ-stable, by Theorem 1.5 no formula in the set Δ has the order property over θ(x; a). Therefore, there is a number n < ω witnessing the failure of the order property for φ(x; y), i. e. , for no {b_{k} | k < n}

⋀_{l<n} ∃x [θ(x; a) ∧ ⋀_{k<n} φ(x; b_{k})^{if (k≥l)}]

holds.

For every ī = ⟨ī[0], …, ī[n]⟩ ∈ [μ]^{n+1} define:

ψ(x; cī) := ⋀_{l<n} ¬φ(x; b_{ī[l]}) ∧ φ(x; b_{ī[n]}).

Since S[θ(x; a) ∧ φ(x; b_{ī[n]}), Δ, μ^{+}] ≥ β and φ(x; b_{ī[n]}) is logically equivalent to

ψ(x; cī) ∨ ([⋁_{l<n} φ(x; b_{ī[l]})] ∧ φ(x; b_{ī[n]})) ,

by the ultrametric property of S rank, we obtain

β ≤ S[θ(x; a) ∧ φ(x; b_{ī[n]}), Δ, μ^{+}]
= max{S[θ(x; a) ∧ ψ(x; cī), Δ, μ^{+}],
S[θ(x; a) ∧ [⋁_{l<n} φ(x; b_{ī[l]})] ∧ φ(x; b_{ī[n]}), Δ, μ^{+}]}.

Notice that the second argument in the above maximum is less than β. Indeed, applying the ultrametric property again, by the choice of φ(x; y) and parameters b_{i}, we get

S[θ(x; a) ∧ [⋁_{l<n} φ(x; b_{ī[l]})] ∧ φ(x; b_{ī[n]}), Δ, μ^{+}]

= max{S[θ(x; a) ∧ φ(x; b_{ī[l]}) ∧ φ(x; b_{ī[n]}), Δ, μ^{+}] | l < n} < β.

Therefore, S[θ(x; a) ∧ ψ(x; cī), Δ, μ^{+}] ≥ β for every ī ∈ [μ]^{n+1}. Clearly, all the formulas θ(x; a) ∧ ψ(x; cī) are Δ-stable. Applying the induction hypothesis to θ(x; a) ∧ ψ(x; cī), we get

∀ī ∈ [μ]^{n+1} Deg[θ(x; a) ∧ ψ(x; cī), Δ, μ^{+}] ≥ β.

By the Tree Characterization Lemma for Deg, for every ī there is a (Δ, β)- function hī such that Γ_{μ}^{ds(β)}(θ(x; a) ∧ ψ(x; cī), hī) is consistent.

Also, since S[θ(x; a), Δ, μ^{+}] ≥ β, by the induction hypothesis, Deg[θ(x; a), Δ, μ^{+}] ≥ β. So there is a (Δ, β)-function h_{∗} such that Γ_{μ}^{ds(β)}(θ(x; a), h_{∗}) is consistent.

Now for every ī define a (Δ, α)-function hī:

for η ∈ ds(α) hī(η) := \{ \begin{matrix}h_{∗}(η) & if η ∈ ds(β); \\ hī(ν) & if η = ⟨β⟩ˆ ν; \\ ⟨ψ, n⟩ & if η = ⟨β⟩. \end{matrix}

It is enough to show that there is an ī ∈ [μ]^{n+1} such that Γ_{μ}^{ds(α)}(θ(x; a), hī) is consistent. Moreover, by compactness, it is enough to show Γ_{ℵ_{0}}^{ds(α)}(θ(x; a), hī) is consistent.

Suppose Γ_{ℵ_{0}}^{ds(α)}(θ(x; a), hī) is not consistent; then for each ī there is a finite u(ī) ⊆ ds(α) such that Γ_{ℵ_{0}}^{u(ī)}(θ(x; a), hī) is inconsistent. Define, for ī ∈ [μ]^{n+1},

F (ī) := ⟨u(ī), hī ↾ u(ī)⟩.

Now applying the Combinatorial Lemma from Appendix B to the function F, where | dom(F)| = μ (regular ≥ |T |^{+}) and | rge(F)| ≤ |T | (since |α| ≤ |T |), we get δ < μ and an increasing sequence {γ(k) < δ : k < ω} such that for every l_{0} < ⋯ < l_{n} < ω,

⟨u, h⟩ := F (γ(l_{0}), …, γ(l_{n−1}), γ(l_{n})) = F (γ(l_{0}), …, γ(l_{n−1}), δ).

Claim 2.5. For l < ω, let d_{l} := c^{⟨γ(0),... ,γ(n−1),γ(n+l)⟩}. The set {ψ(x; d_{l}) | l < ω} is n-contradictory over θ(x; a).

Proof. By Ramsey’s Theorem we may assume that the sequence {b_{γ(l)} | l < ω} is such that for all i(0) < ⋯ < i(n) < ω and for all k ≤ n

∃x [θ(x; a) ∧ ⋀_{l≤n} φ(x; b_{γ(l)})^{if (l≥k)}] ⇔ ∃x [θ(x; a) ∧ ⋀_{l≤n} φ(x; b_{γ(i(l))})^{if (l≥k)}] (∗)

If {ψ(x; d_{l}) | l < ω} is not n-contradictory over θ(x; a), then there are {l(k) | k < n} such that

⊧ ∃x [θ(x; a) ∧ ⋀_{k<n} ψ(x; d_{l(k)})] ,

i. e. , by the definition of ψ and d_{l(k)},

⊧ ∃x [θ(x; a) ∧ ⋀_{k<n} ¬φ(x; b_{γ(k)}) ∧ ⋀_{k<n} φ(x; b_{γ(n+l(k))})] .

In particular, for every m ≤ n,

⊧ ∃x [θ(x; a) ∧ ⋀_{k<m} ¬φ(x; b_{γ(k)}) ∧ ⋀_{k=m}^{n−1} φ(x; b_{γ(n+l(k))})] .

Now by (∗) we get

⊧ ∃x [θ(x; a) ∧ ⋀_{k<m} ¬φ(x; b_{γ(k)}) ∧ ⋀_{k=m}^{n−1} φ(x; b_{γ(k)})] ,

which is a contradiction to the choice of n, which was chosen to witness the failure of the order property over θ(x; a) for φ. ⊣

We may assume that u is closed under taking initial segments and Γ_{ℵ_{0}}^{u}(θ(x; a), h) is consistent: putting ī_{l} := ⟨γ(0), …, γ(n_{1}−1), γ(n_{1}+l)⟩, d_{l} := cī_{l} for l < ω, and

b_{η,ν} := \{ \begin{matrix}d_{l} & if η = ⟨β⟩, ν = ⟨l⟩; \\ bī_{l} ; ξ,ζ & if η = ⟨β⟩ˆ ξ, ν = ⟨l⟩ˆ ζ; \\ b_{η,ν}^{∗} & if η ∈ ds(β), \end{matrix}

for η ∈ u, ν ∈ ^{ℓ(η)}ℵ_{0}, we have {b_{η,ν}} ⊧ Γ_{ℵ_{0}}^{u}(θ(x; a), h). This contradicts the choice of u and we are done.

⊣

The following fact now trivially follows from Theorems 2.3 and 1.13.

Corollary 2.6. Let Δ be a set of formulas in x closed under Boolean operations, θ(x; y) ∈ Δ; and let μ ≥ |T |^{+} be regular. If θ(x; a) is Δ-stable, then

S[θ(x; a), Δ, μ^{+}] ≤ Deg[θ(x; a), Δ, μ^{+}] ≤ D[θ(x; a), Δ, μ^{+}] ≤ R[θ(x; a), Δ, μ^{+}].

In order to prove the main theorem, we need to show that R[θ(x; a), Δ, λ] ≤ S[θ(x; a), Δ, λ] under appropriate assumptions. The following lemma will provide the link between the R-rank and the S-rank. It fuels the successor stage of an induction proof of Theorem 2.12.

Lemma 2.7. Suppose that μ is a regular cardinal, μ ≥ |T |^{+}, and Δ is a set of formulas which is closed under Boolean operations. If R[θ(x; a), Δ, μ^{+}] ≥ β + 1 and

(1) R[θ(x; a), Δ, μ^{+}] < ∞ or

(2) θ(x; a) is Δ-stable and for every set {μ_{i} | i < |Δ|+ℵ_{0}} of cardinalities all less than μ, we have ∏_{i<|Δ|+ℵ_{0}} μ_{i} < μ (e.g. μ = (2^{|T |})^{+} is such a cardinality),

then there is a formula φ^{∗}(x, y) ∈ Δ and a set {c_{i} | i < μ} such that (1) R[θ(x; a) ∧ φ^{∗}(x, c_{i}), Δ, μ^{+}] ≥ β for all i < μ;

(2) R[θ(x; a) ∧ φ^{∗}(x, c_{i}) ∧ φ^{∗}(x, c_{j}), Δ, μ^{+}] < β for i ≠ j < μ.

Proof. Since R[θ(x; a), Δ, μ^{+}] ≥ β + 1, there are {p_{i} | i ≤ μ} explicitly contradictory Δ-types such that R[{θ(x; a)} ∪ p_{i}, Δ, μ^{+}] ≥ β for all i ≤ μ. Using the hypothesis of the lemma, we get

Claim 2.8. There are a set A, a formula φ(x; y) ∈ Δ and {p_{i} | i < μ} ⊆ S_{Δ}(A) such that p_{i} ↾ φ ≠ p_{j} ↾ φ for every i ≠ j and R[{θ(x; a)} ∪ p_{i}, Δ, μ^{+}] ≥ β holds for every i < μ.

Proof. The argument is by cases corresponding to the hypotheses of the lemma.

(1) Suppose that R[θ(x; a), Δ, μ^{+}] < ∞. Using Theorem 1.3 (by replacing the p_{i}’s by extensions) we may assume that R[{θ(x; a)} ∪ p_{i}, Δ, μ^{+}] = β for all i ≤ μ. By the finite character there are q_{i} ⊆_{finite} p_{i} such that R[{θ(x; a)} ∪ q_{i}, Δ, μ^{+}] = β for all i ≤ μ.

Subclaim 2.9. For every i < μ the set {j < μ | q_{i} ⊆ p_{j}} is bounded.

Proof. Otherwise, there is S ⊆ μ of cardinality μ such that there exists i_{0} satisfying q_{i_{0}} ⊆ p_{j} for all j ∈ S. Namely by monotonicity we have that R[{θ(x; a)} ∪ q_{i_{0}} ∪ p_{j}, Δ, μ^{+}] = β for every j ∈ S. This, by the definition of R, implies that R[{θ(x; a)} ∪ q_{i_{0}}, Δ, μ^{+}] = β + 1 in contradiction to the choice of q_{i}. ⊣

By induction on i < μ we can now define an increasing sequence {j(i) < μ | i < μ} such that q_{ξ} ⊈ p_{j(i)} for all ξ ≤ i. By renumerating the set {p_{j(i)} | i < μ} we may assume that {p_{i} | i < μ} also satisfies q_{i} ⊈ p_{j} for all i < j. Since Δ is closed under Boolean operations, the formula φ_{i} := ⋀ q_{i} is a Δ-formula. Consider the mapping i ↦ φ_{i}. Since the domain is a regular cardinal larger than |T |, there are a formula φ(x; y) ∈ Δ and a set S ⊆ μ of cardinality μ such that φ_{i} = φ for all i ∈ S. Since q_{i} ⊈ p_{j} for j > i, we have that φ_{i} ∉ p_{j}, and since the types are complete this entails that ¬φ_{i} ∈ p_{j}.

We have shown that i ≠ j implies that p_{i} ↾ φ ≠ p_{j} ↾ φ.

(2) For this part we do not use the local stability assumption; we just use that ∏_{i<|Δ|+ℵ_{0}} μ_{i} < μ for every {μ_{i} < μ | i < |Δ| + ℵ_{0}}. If there is no set of μ many types as required then let

μ_{φ} := |{p_{i} ↾ φ : i < μ}| < μ for every φ ∈ Δ.

However, the mapping i ↦ (p_{i} ↾ φ)_{φ∈Δ} is an injection from μ into ∏_{φ∈Δ}{p_{i} ↾ φ : i < μ}, which contradicts the above cardinal arithmetic assumption.

⊣

Claim 2.10. R[θ(x; a), φ(x; y), 2] < ω.

Proof. We have two arguments according to the hypothesis of the lemma:

(1) By monotonicity, R[θ(x; a), φ, ∞] ≤ R[θ(x; a), Δ, μ^{+}], and by Theorem 1.6 (1), R[θ(x; a), φ, 2] < ω.

(2) Since θ(x; a) is Δ-stable, it is {φ}-stable for every φ ∈ Δ. By Theorem 1.6 this entails R[θ(x; a), φ, 2] < ω. ⊣

By the above claim, R[θ(x; a), φ(x; y), 2] is a natural number. Let n_{0} := R[θ(x; a), φ, 2].

Claim 2.11. If the set Φ ⊆ {q ∈ S_{φ}(A) | θ(x; a) ∪ q is consistent} has cardinality κ ≥ ℵ_{0} then there exists {r_{i}, p_{i} | i < κ, r_{i} ⊆ p_{i}, p_{i} ∈ Φ} such that

(1) |r_{i}| = n_{0} + 2,

(2) for every i < κ if q ∈ Φ and r_{i} ⊆ q then q = p_{i}, and

(3) i ≠ j implies p_{i} ≠ p_{j}.

We present the proof of Claim 2.11 in the Appendix.

For every i < μ, we have that R[θ(x; a) ∪ p_{i} ↾ φ, Δ, μ^{+}] ≥ β. Thus for Φ := {q ∈ S_{φ}(A) | R[θ(x; a) ∪ q, Δ, μ^{+}] ≥ β}, it follows that |Φ| ≥ μ. Applying the previous claim to Φ, let {r_{i} : i ≤ μ} be as in the claim.

For i < μ define φ^{∗}(x; c_{i}) := ⋀ r_{i} (since μ ≥ |T |^{+}, we may assume that φ^{∗}(x; y) does not depend on i).

Since r_{i} ⊆ p_{i}, for all i < μ, and R[θ ∪ p_{i}, Δ, μ^{+}] ≥ β, we get

R[θ(x; a) ∧ φ^{∗}(x; c_{i}), Δ, μ^{+}] ≥ β.

However, if i ≠ j, then

R[θ(x; a) ∧ φ^{∗}(x; c_{i}) ∧ φ^{∗}(x; c_{j}), Δ, μ^{+}] < β.

Otherwise, by the Extension Property there would be a q ∈ S_{φ}(A) extending φ^{∗}(x; c_{i})∧φ^{∗}(x; c_{j}) such that R[θ(x; a)∪q, Δ, μ^{+}] ≥ β, which would contradict the uniqueness clause (2) from the construction of r_{i}’s from Claim 2.11. ⊣

Theorem 2.12. Suppose that μ is regular cardinal satisfying μ ≥ |T |^{+} and Δ is a set of formulas which is closed under Boolean operations, with θ(x; y) ∈ Δ. If

(1) R[θ(x; a), Δ, μ^{+}] < ∞ or

(2) θ(x; a) is Δ-stable and for every {μ_{i} | i < |Δ| + ℵ_{0}} cardinalities all less than μ, ∏_{i<|Δ|+ℵ_{0}} μ_{i} < μ

holds, then S[θ(x; a), Δ, μ^{+}] ≥ R[θ(x; a), Δ, μ^{+}].

Proof. We show that for all ordinals α,

(∗)_{α} R[θ(x; a), Δ, μ^{+}] ≥ α ⇒ S[θ(x; a), Δ, μ^{+}] ≥ α.

We proceed by induction on α. For α = 0, (∗)_{α} holds by the definitions of ranks. For α a limit ordinal, (∗)_{α} follows from the continuity of the ranks and the induction hypothesis. Suppose R[θ(x; a), Δ, μ] ≥ α = β + 1 and that (∗)_{β} holds. Then by Lemma 2.7 we have a formula φ^{∗}(x; y) ∈ Δ and a set {c_{i} | i < μ} such that

(1) R[θ(x; a) ∧ φ^{∗}(x; c_{i}), Δ, μ^{+}] ≥ β for all i < μ;

(2) R[θ(x; a) ∧ φ^{∗}(x; c_{i}) ∧ φ^{∗}(x, c_{j}), Δ, μ^{+}] < β for i ≠ j < μ.

By induction hypothesis (1) gives us S[θ(x; a) ∧ φ^{∗}(x; c_{i}), Δ, μ^{+}] ≥ β for all i < μ. And (2) together with Corollary 2.6 imply

S[θ(x; a) ∧ φ^{∗}(x; c_{i}) ∧ φ^{∗}(x; c_{j}), Δ, μ^{+}] < β for i ≠ j ∈ I.

By the definition of S rank, we have S[θ(x; a), Δ, μ^{+}] ≥ α, completing the induction. ⊣

Corollary 2.6 and Theorem 2.12 give the following

Theorem 2.13. Suppose that μ is regular satisfying μ ≥ |T |^{+} and Δ is a set of formulas closed under Boolean operations with θ(x; y) ∈ Δ. If

(1) R[θ(x; a), Δ, μ^{+}] < ∞ or

(2) θ(x; a) is Δ-stable and μ satisfies: for every sequence of cardinals {μ_{i} < μ | i < |Δ| + ℵ_{0}} we have that ∏_{i<|Δ|+ℵ_{0}} μ_{i} < μ holds,

then S[θ(x; a), Δ, μ^{+}] = Deg[θ(x; a), Δ, μ^{+}] = D[θ(x; a), Δ, μ^{+}] = R[θ(x; a), Δ, μ^{+}].

Now we show how to remove the assumption θ(x; y) ∈ Δ and get Theorem 0.1. First we prove

Lemma 2.14. ^{1} Suppose θ(x; a) is Δ-stable, where Δ is closed under Boolean operations. Suppose λ ≥ ℵ_{1}. If D[θ, Δ, λ] ≥ α + 1 for α ≥ 0, then for every μ < λ there are ψ̄ ∈ Δ, k < ω, and {b_{i} | i < μ} such that

(1) the set {ψ̄(x; b_{i}) | i < μ} is k-contradictory over θ(x; a);

(2) for every i < μ, D[θ(x; a) ∧ ψ̄(x; b_{i}), Δ, λ] ≥ α.

Proof. Suppose D[θ(x; a), Δ, λ] ≥ α + 1 for α ≥ 0. By the definition, for all ℵ_{0} ≤ μ < λ, μ limit, there is a formula φ(x; c) with ⊧ φ(x; c) → θ(x; a), there are ψ ∈ Δ and {a_{i} | i < μ} such that for some n < ω

(1) D[φ(x; c) ∧ ψ(x; a_{i}), Δ, λ] ≥ α and

(2) {ψ(x; a_{i}) | i < μ} is n-contradictory over φ(x; c).

Clearly,

D[θ(x; a) ∧ ψ(x; a_{i}), Δ, λ] ≥ α for all i < μ,

so if {ψ(x; a_{i}) | i < μ} is k-contradictory over θ(x; a) for some k < ω, then we are done. Otherwise, we may assume that the set {θ(x; a)} ∪ {ψ(x; a_{i}) | i < ω} is consistent. Since {ψ(x; a_{i}) | i < μ} is n-contradictory over φ(x; c), we have

⊧ φ(x; c) → φ(x; c) ∧ ¬ ⋀_{j<n} ψ(x; a_{j}).

Hence D[φ(x; c) ∧ ¬[⋀_{j<n} ψ(x; a_{j})] ∧ ψ(x; a_{i}), Δ, λ] ≥ α for i < μ. By the ultrametric property for the D-rank and the pigeon-hole principle, refining {a_{i} | i < μ} if necessary we may assume that

D[φ(x; c) ∧ ¬ψ(x; a_{0}) ∧ ψ(x; a_{i}), Δ, λ] ≥ α for 1 ≤ i < μ. (∗_{0})

By monotonicity

D[θ(x; a) ∧ ¬ψ(x; a_{0}) ∧ ψ(x; a_{i}), Δ, λ] ≥ α for 1 ≤ i < μ.

If {ψ(x; a_{i}) | 1 ≤ i < μ} is k-contradictory over θ(x; a) ∧ ¬ψ(x; a_{0}) for some k < ω, then we are done. Otherwise, {θ(x; a) ∧ ¬ψ(x; a_{0})} ∪ {ψ(x; a_{i}) | 1 ≤ i < ω} is consistent. Now we replace φ(x; c) in (∗_{0}) by φ(x; c) ∧ ¬ ⋀_{1≤i<n+1} ψ(x; a_{i}), and get as above

D[φ(x; c)∧¬ψ(x; a_{0})∧¬ψ(x; a_{1})∧ψ(x; a_{i}), Δ, λ] ≥ α for 2 ≤ i < μ. (∗_{1})

Observe that since we are only refining the sequence {a_{i} | i < μ}, after the second step we get that both {θ(x; a)} ∪ {ψ(x; a_{i}) | i < ω} and {θ(x; a) ∧ ¬ψ(x; a_{0})} ∪ {ψ(x; a_{i}) | 1 ≤ i < ω} are consistent.

Repeat this process.

1The statement of this Lemma appears as Exercise II.3.10 in [Sha]. In a preliminary version of this paper we stated it without proof. One of the readers doubted the correctnes of this, so we have included a complete proof for completness.

Subclaim 2.15. The above process terminates in finitely many steps, i.e., there is l < ω and a sequence {a_{i} | i < μ} such that

D[φ(x; c) ∧ ⋀_{j≤l} ¬ψ(x; a_{j}) ∧ ψ(x; a_{i}), Δ, λ] ≥ α for l + 1 ≤ i < μ. (∗_{l})

and {ψ(x; a_{i}) | l+1 ≤ i < μ} are k-contradictory over θ(x; a)∧⋀_{j≤l} ¬ψ(x; a_{j}) for some k.

Proof. Since θ is Δ-stable, the formula ψ ∈ Δ does not have the order property over θ(x; a). Let N < ω witnes failure of the order property for ψ. We claim that the above process terminates after at most N steps. Indeed, otherwise we would have a sequence {a_{i} | i < μ} such that

⊧ ∃x[θ(x; a) ∧ ⋀_{j≤l} ¬ψ(x; a_{j}) ∧ ⋀_{l<i<N} ψ(x; a_{i})] for all l < N,

which contradicts the choice of N. ⊣

Let {a_{i} | i < μ}, l < ω and k be as in the subclaim, let

ψ̄(x; y_{0}, …, y_{l}, y_{l+1}) := ⋀_{j≤l} ¬ψ(x; y_{j}) ∧ ψ(x; y_{l+1}),

and let b_{i} := a_{0}ˆ a_{1}ˆ …ˆ a_{l}ˆ a_{l+1+i} for i < μ. Since Δ is closed under Boolean operations, ψ̄ ∈ Δ. By (∗_{l}) and monotonicity D[θ(x; a)∧ψ̄(x; b_{i}), Δ, λ] ≥ α, and clearly {ψ̄(x; b_{i}) | i < μ} is k-contradictory over θ(x; a). ⊣

The above lemma shows that we can don’t need to consider arbitrary finite extensions of θ(x; a) to compute D[θ(x; a), Δ, λ]. This allows us to get the Main Theorem from the abstract.

Proof of the Main Theorem. Let p be a finite type, let θ(x; a) := ∧p. Prove (1) S[θ(x; a), Δ, μ^{+}] ≤ D[θ(x; a), Δ, μ^{+}],

(2) R[θ(x; a), Δ, μ^{+}] ≤ S[θ(x; a), Δ, μ^{+}].

In view of Lemma 2.14, the proof of (1) repeats almost word-for-word that of Theorem 2.3. Proof of (2) is the same as the proof of Theorem 2.12 except one needs to use (1) and Proposition 1.13 instead of Corollary 2.6. ⊣

As a byproduct of our results, we get the following characterization of local superstability (notice the alanogy to Theorem II 3.14 from [Sha]):

Theorem 2.16. Let p be a finite type and let Δ be a set of formulas closed under Boolean operations. The following conditions are equivalent:

(1) p is Δ-superstable,

(2) p is Δ-stable and D[p, Δ, |T |^{++}] < |T |^{+},

(3) p is Δ-stable and D[p, Δ, ∞] < |T |^{+},

(4) R[p, Δ, ∞] < |T |^{+},

(5) R[p, Δ, ∞] < ∞,

(6) p is Δ-stable and Deg[p, Δ, ∞] < ∞.

If in addition ∧p ∈ Δ, then any of (1)–(6) above is equivalent to

(7) p is Δ-stable and Deg[p, Δ, |T |^{++}] < |T |^{+}, Remark 2.17. Even more is true in the above: we can add the condition R[p, Δ, (2^{|T |})^{++}] < |T |^{+}; see Proposition 3.4.

3. Bounds on ranks

As we mentioned above, the following rank was introduced by Hrushovski in the context of geometric dimension theory. We describe the connection between the ranks S, R, D, and S1.

Definition 3.1. S1[p, Δ] ≥ 0 if p is consistent. S1[p, Δ] ≥ α, for α limit, if for every β < α, S1[p, Δ] ≥ β. S1[p, Δ] ≥ α + 1 if for every finite p_{0} ⊂ p there exists ψ(x; y) ∈ Δ and {b_{n} | n < ω} indiscernibles over dom(p_{0}) such that

(1) S1[p_{0} ∪ {ψ(x; b_{n})}, Δ] ≥ α for every n < ω and

(2) S1[p_{0} ∪ {ψ(x; b_{n}) ∧ ψ(x; b_{m})}, Δ] < α for m ≠ n < ω.

The S1 rank has all the properties of the S rank, and they can be proved in a completely analogous way.

Claim 3.2. There is a cardinal κ such that for any type p, set of formulas Δ, and λ ≥ κ^{+} we have S1[p, Δ] = S[p, Δ, λ]. In particular, S1[p, Δ] = S[p, Δ, ∞].

Proof. We use the fact that there exists a cardinal κ such that for any countable set A and any sequence {b_{i} | i < κ} there is a sequence {c_{n} | n < ω} of indiscernibles over A such that for all n < ω there are i(0) < ⋯ < i(n − 1) < κ with tp(c_{0} … c_{n−1}/A) = tp(b_{i(0)} … b_{i(n−1)}/A). Namely, κ := ℶ_{(2^{|T |})^{+}}^{2}.

We prove by induction

S1[p, Δ] ≥ α ⇔ S[p, Δ, λ] ≥ α (∗)_{α}

for every λ ≥ κ^{+} and every finite type p. Let θ(x; a) := ⋀ p.

If α = 0, then (∗)_{α} holds by the definitions of the ranks. For α a limit ordinal, (∗)_{α} follows from the continuity of the ranks and the induction hypothesis.

Let α = β + 1, S1[θ(x; a), Δ] ≥ α and (∗)_{β} is true. By the definition of the S1 rank, there are ψ(x; y) ∈ Δ and {b_{n} | n < ω} indiscernibles over a as in the definition. By invariance of the S1 rank and Compactness Theorem, there is an indiscernible sequence {b_{i} | i < λ} over a, such that

(1) S1[θ(x; a) ∧ ψ(x; b_{i}), Δ] ≥ β for every i < λ and

(2) S1[θ(x; a) ∧ ψ(x; b_{i}) ∧ ψ(x; b_{j}), Δ] < β for i ≠ j < λ. By (∗)_{β} we obtain

(1) S[θ(x; a) ∧ ψ(x; b_{i}), Δ, λ] ≥ β for every i < λ and

(2) S[θ(x; a) ∧ ψ(x; b_{i}) ∧ ψ(x; b_{j}), Δ, λ] < β for i ≠ j < λ.

2This fact appears in [Sh93], Lemma 6.3; for a more detailed account and an improvement of the bound see [GIL], Theorem A1.

Note that we use both directions of (∗)_{β} here. By the definition, we see that S[θ(x; a), Δ, λ] ≥ α.

Suppose now that S[θ(x; a), Δ, λ] ≥ α and fix {b_{i} | i < κ} such that

(1) S[θ(x; a) ∧ ψ(x; b_{i}), Δ, λ] ≥ β for every i < κ and

(2) S[θ(x; a) ∧ ψ(x; b_{i}) ∧ ψ(x; b_{j}), Δ, λ] < β for i ≠ j < κ. We certainly can find such b_{i}’s because λ ≥ κ^{+}. By the choice of κ, there is a sequence {c_{k} | k < ω} of indiscernibles over a such that for every n < ω there are i(0) < i(1) < ⋯ < i(n − 1) < κ such that tp(c_{0} … c_{n−1}/a) = tp(b_{i(0)} … b_{i(n−1)}/a). By invariance of the S rank, we have

(1) S[θ(x; a) ∧ ψ(x; c_{n}), Δ, λ] ≥ β for every n < ω and

(2) S[θ(x; a) ∧ ψ(x; c_{n}) ∧ ψ(x; c_{m}), Δ, λ] < β for n ≠ m < ω.

Using (∗)_{β}, we get

(1) S1[θ(x; a) ∧ ψ(x; c_{n}), Δ] ≥ β for every n < ω and

(2) S1[θ(x; a) ∧ ψ(x; c_{n}) ∧ ψ(x; c_{m}), Δ] < β for m ≠ n < ω which shows (∗)_{α}.

⊣

The following theorem describes the asymptotic behaviour of the ranks and shows that S1 is equal to S, R, and D under the local stability assumption.

Theorem 3.3. Suppose Δ is closed under Boolean operations. If θ(x; a) is Δ-stable, then

S1[θ(x; a), Δ] = S[θ(x; a), Δ, ∞] = D[θ(x; a), Δ, ∞] = R[θ(x; a), Δ, ∞].

Moreover, for every λ ≥ (2^{|T |})^{++}

S1[θ(x; a), Δ] = S[θ(x; a), Δ, λ] = D[θ(x; a), Δ, λ] = R[θ(x; a), Δ, λ].

Proof. The first set of equalities and

S[θ(x; a), Δ, (2^{|T |})^{++}] = D[θ(x; a), Δ, (2^{|T |})^{++}] = R[θ(x; a), Δ, (2^{|T |})^{++}]

follow from Theorem 0.1, clause (2), and Claim 3.2.

The rest follows from monotonicity of the ranks in the third argument and

Proposition 3.4. For a finite type p and Δ closed under Boolean operations, for every λ ≥ (2^{|T |})^{++}

R[p, Δ, λ] = R[p, Δ, ∞].

Proof. By monotonicity, R[p, Δ, λ] ≥ R[p, Δ, ∞]. If R[p, Δ, ∞] = ∞, we have nothing to prove. Otherwise, by Theorem 1.7 we get that p is Δ-stable and we are in the conditions of Theorem 0.1, clause (2). Taking into account the equality D[p, Δ, |T |^{++}] = D[p, Δ, ∞] from [Sha], II.3.8, by the choice of λ we get R[p, Δ, λ] = D[p, Δ, λ] = D[p, Δ, ∞] = R[p, Δ, ∞]. ⊣

⊣ Theorem 3.5. Suppose Δ is closed under Boolean operations.

(1) Suppose that θ(x; a) is Δ-stable. If any of the ranks in Theorem 3.3 is bounded (i.e. is less than ∞), then all the ranks there are less than |T |^{+}.

(2) If p is a type, not necessarily finite, and R[p, Δ, ∞] < ∞, then R[p, Δ, ∞] < |T |^{+}.

Proof. (1) If any of the ranks in Theorem 3.3 is bounded, then D[θ(x; a), Δ, ∞] < ∞. By Theorem II.3.8 in [Sha], we have then D[θ(x; a), Δ, ∞] < |T |^{+}. Applying Theorem 3.3 again, we see that all the ranks must be less than |T |^{+}.

(2) By finite character, there is a finite p_{0} with R[p, Δ, ∞] = R[p_{0}, Δ, ∞] < ∞. By Theorem 2.16 we get R[p_{0}, Δ, ∞] < |T |^{+} and the assertion follows.

⊣
4. S2-rank

The following is a generalization of the S1 rank.

Definition 4.1. Let p be a set of formulas in x. S2[p, Δ] ≥ 0 if p is consistent. S2[p, Δ] ≥ α, for α limit, if for every β < α, S2[p, Δ] ≥ α. S2[p, Δ] ≥ α + 1 if for every finite p_{0} ⊂ p there exists ψ(x, y) ∈ Δ, l < ω and {b_{n} | n < ω} indiscernibles over dom(p_{0}) such that

(1) S2[p_{0} ∪ {ψ(x, b_{n})}, Δ] ≥ α for every n < ω and

(2) S2[p_{0} ∪ {⋀_{n∈u} ψ(x, b_{n})}, Δ] < α whenever u ∈ ^{l}ω.

Remark 4.2. Given Δ ⊆ {φ(x; y) | φ ∈ F ml(L(T))} closed under Boolean operations and containing all the formulas of a type p in x, if p is Δ-stable, one can show that S2[p, Δ] = S1[p, Δ].

The inequality S1[p, Δ] ≤ S2[p, Δ] is trivial and holds without any restrictions on Δ and p.

One then can show that S2[p, Δ] ≤ Deg[p, Δ, λ], where λ is infinite cardinal, using a similar argument to that which was used to prove Theorem 2.3.

Appendix A. Proof of Claim 2.11

Proof. (Of the Claim 2.11) Define r_{i}, p_{i} by induction on i < κ. Suppose we have defined {r_{j}, p_{j} : j < i}. Now define an equivalence relation E_{i}:

for a, b ∈ ^{ℓ(y)}A, aE_{i}b ⇔ (∀j < i)[φ(x; a) ∈ p_{j} ⇔ φ(x; b) ∈ p_{j}].

Subclaim A.1. |^{ℓ(y)}A /E_{i}| < κ.

Proof. For every j < i, let c_{j} ⊧ p_{j}. Suppose for the sake of contradiction that {a_{k}/E_{i} | k < κ} are distinct equivalence classes. Let q_{k} := tp_{φ}(a_{k}/∪_{j<i} c_{j}). Let k ≠ l < κ be given. Then a_{k}/E_{i} ≠ a_{l}/E_{i}. By the definition of E_{i}, there is a j < i such that ¬(φ(x; a_{k}) ∈ p_{j} ↔ φ(x; a_{l}) ∈ p_{j}). Without loss of generality we may assume that φ(x; a_{k}) ∈ p_{j} and ¬φ(x; a_{l}) ∈ p_{j}. Since c_{j} ⊧ p_{j}, we have that φ(c_{j}; y) ∈ q_{k} and ¬φ(c_{j}; y) ∈ q_{l}. Thus for k ≠ l < κ, q_{k} ≠ q_{l}.

Since i < κ, we get that | ∪_{j<i} c_{j}| < κ. But {q_{k} : k < κ} witnesses that |S_{φ}(∪_{j<i}c_{j})| ≥ κ, which contradicts our stability assumption. ⊣

Subclaim A.2. |{q ∈ Φ : aE_{i}b ⇒ [φ(x; a) ∈ q ⇔ φ(x; b) ∈ q]}| < κ.

Proof. Let S := {q ∈ Φ | ∀a, b ∈ ^{ℓ(y)}A (aE_{i}b ⇒ (φ(x; a) ∈ q ⇔ φ(x; b) ∈ q)}. For the sake of contradiction, suppose that |S| = κ. Let Ā := ^{ℓ(y)}A /E_{i}. By subclaim A.1, we have that |Ā| < κ; but, we have an obvious injection S → S_{φ}(Ā), so |S_{φ}(Ā)| ≥ κ, which is a contradiction to the stability assumption. ⊣

By induction on l ≤ n_{0} define p^{l} ∈ Φ, a_{l+1}^{i} and t(l) ∈ {0, 1} such that:

· r_{l}^{i} := {φ(x; a_{0}^{i}), φ(x; a_{1}^{i})^{t(0)}, …, φ(x; a_{l+1}^{i})^{t(l)}} ⊆ p^{l}; · R[θ(x; a) ∪ r_{l}^{i}, φ, 2] ≤ n_{0} − l or ∃!q ∈ Φ, q ⊇ r_{l}^{i}.

For l = 0, by Subclaims A.1 and A.2 there exists p^{0} and a_{0}^{i}, a_{1}^{i} such that a_{0}^{i}E_{i}a_{1}^{i} and φ(x; a_{0}^{i}) ∈ p^{0}, ¬φ(x; a_{1}^{i}) ∈ p^{0}. Put t(0) := 1.

Suppose we have defined everything for l. If ∃!q ∈ Φ, q ⊇ r_{l}^{i}, let a_{l+1}^{i} = a_{l}^{i}, t(l+1) = t(l) and p^{l+1} = q. If |{q ∈ Φ : r_{l}^{i} ⊆ q}| > 1, then, since Φ ⊆ S_{φ}(A), for some a_{l+1}^{i} ∈ ^{ℓ(y)}A there are q_{0}, q_{1} ∈ Φ, r_{l}^{i} ∪ {φ(x; a_{l+1}^{i})^{t})} ⊆ q_{t}. From definition of R, there is t(l + 1) ∈ {0, 1} such that

R[{θ(x; a)} ∪ r_{l}^{i} ∪ {φ(x; a_{l+1}^{i})^{t(l+1)}}, φ, 2] < R[{θ(x; a)} ∪ r_{l}^{i}, φ, 2] ≤ n_{0} − l

and put p^{l+1} := q_{t(l+1)}.

Now, it is clear from the construction that r_{n_{0}+1}^{i} has a unique extension in Φ and |r_{n_{0}+1}^{i}| ≤ n_{0} +2. Put r_{i} := r_{n_{0}+1}^{i}, adding eventually some formulas from the unique extension of r_{n_{0}+1}^{i} to satisfy the requirement |r_{i}| = n_{0} + 2. ⊣

Appendix B. A combinatorial theorem

Claim B.1 (A combinatorial lemma). Let κ ≥ ℵ_{0} and suppose that μ > κ is regular. For every n < ω and every F : [μ]^{n+1} → κ there exists a limit ordinal δ < μ such that for every ξ < μ satisfying ξ ≥ δ there exists an increasing {γ(k) | k < ω} ⊆ δ such that for any ℓ_{0} < ⋯ < ℓ_{n} < ω we have that

F (γ(ℓ_{0}), …, γ(ℓ_{n})) = F (γ(ℓ_{0}), …, γ(ℓ_{n−1}), ξ).

Proof. Let χ > ℵ_{0} be a regular cardinal large enough such that {μ, F } ⊆ H(χ). Let 𝔅 := ⟨H(χ), ∈, μ, F, α⟩_{α<κ}, where μ stands for a unary predicate interpreted by the set of ordinals less than μ, F is interpreted by the function F and α is an individual constant interpreted by the corresponding ordinal.

By the Downward Löwenheim-Skolem-Tarski theorem pick an increasing and continuous elementary chain {𝔅_{i} ≺ 𝔅 | i < μ} satisfying

(1) ∥𝔅_{i}∥ < μ and

(2) i ⊆ μ^{𝔅_{i}} for all i < μ. Since we have that μ = ⋃_{i<μ} μ^{𝔅_{i}}, there is a closed unbounded subset C of the set {δ < μ | δ = μ^{𝔅_{δ}} ∧ δ is limit}.

The definition of {γ(k) | k < ω} is by induction on k: Fix any γ(0) < γ(1) < ⋯ < γ(n − 1) < δ. Suppose {γ(j) | j ≤ k} are defined (for k ≥ n − 1). Let ψ(x) be the following formula (with parameters γ(0), …, γ(k)):

⋀{F (γ(ℓ_{0}), …, γ(ℓ_{n−1}), x) = α | ℓ_{0} < ⋯ < ℓ_{n−1} ≤ k, α < κ,
𝔅 ⊧ F (γ(ℓ_{0}), …, γ(ℓ_{n−1}), ξ) = α}.

Since 𝔅 ⊧ ψ(ξ), we have that 𝔅 ⊧ ∃xψ(x). Since all the parameters of ψ are in 𝔅_{δ}, 𝔅_{δ} ≺ 𝔅 and ξ > γ(k) there exists γ(k + 1) < δ such that γ(k + 1) > γ(k) and 𝔅 ⊧ ψ(γ(k + 1)). ⊣

References

[Ba1] John T. Baldwin. α_{T} is finite for ℵ_{1}-categorical T. Transactions of the AMS, 181, 37–53, 1973.

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

[BaBl] John T. Baldwin and Andreas Blass, An axiomatic approach to rank in model theory, Annals of Mathematical Logic, 7, (1974) pages 295–324.

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

[Bo] Elisabeth Bouscaren, An introduction to independence and local modularity, in Algebraic Model Theory edited by B. Hart, A. Lachlan and M. Valeriote, NATO ASI Series, Mathematical and Physical Sciences - Vol 496, Kluwer Academic Publishers 1997.

[Bu] Steven Buechler. Essential Stability Theory. Springer-Verlag, Berlin, 1996.

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

[CH] Zoe Chatzidakis and Ehud Hrushovski. Model theory of difference fields. T rans. Amer. Math. Soc. 351 (1999), no. 8, 2997–3071.

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

[GIL] Rami Grossbberg, José Iovino and Olivier Lessmann. A primer of Simple theories, (40 pages), Archive for mathematical Logic, to appear.

[GrLe] Rami Grossberg and Olivier Lessmann. The local order property in non elementary classes, Arch Math Logic 39 (2000) 6, 439-457.

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

[Hr] Ehud Hrushovski. Pseudofinite fields and related structures. Unpublished Manuscript.

[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.

[HS] Ehud Hrushovski and Thomas Scanlon, Lascar and Morley ranks differ in differentially closed fields. Preprint

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

[Ki] Byunghan Kim. Forking in simple unstable theories. J. of London Math. Society, (2) 57 (1998) 257-267.

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

[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.

[LaPo] Daniel Lascar and Bruno Poizat. Fundamentals of forking. J. Symbolic Logic, 1977.

[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.

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

[Saf] Jürgen Saffe. Categoricity and ranks. J.S.L., 49, 1379–1392, 1970/1971.

[Sh3] Saharon Shelah. Finite diagrams stable in power. Ann. Math. Logic, 2, 69–118, 1970. [Sh 10] Saharon Shelah. Stability, the f.c.p., and superstability; model theoretic properties

of formulas in first order theory. Annals of Mathematical Logic, 3:271–362, 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. E-mail address, Rami Grossberg: rami@cmu.edu

E-mail address, Alexei Kolesnikov: alexei@cmu.edu

E-mail address, Ivan Tomašić: itomasic@maths.ed.ac.uk

E-mail address, Monica VanDieren: monicav@cmu.edu

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