Stable theories with a new predicate ^{∗}

Enrique Casanovas^{†} and Martin Ziegler^{‡}

January 21, 2000

∗Preliminary version 8 †Partially supported by grant HA1996-0131 of the Spanish Government. ‡Partially supported by a grant of the DAAD.

1 Introduction

Let M be an L-structure and A be an infinite subset of M. Two structures can be defined from A:

• The induced structure on A has a name R_{φ} for every ∅–definable relation φ(M) ∩ A^{n} on A. Its language is

L_{ind} = {R_{φ} | φ = φ(x_{1}, …, x_{n}) an L–formula}.

A with its L_{ind}–structure will be denoted by A_{ind}.

• The pair (M, A) is an L(P)–structure, where P is a unary predicate for A and L(P) = L ∪ {P }.

We call A small if there is a pair (N, B) elementarily equivalent to (M, A) and such that for every finite subset b of N every L–type over Bb is realized in N.

A formula φ(x, y) has the finite cover property (f.c.p) in M if for all natural numbers k there is a set of φ–formulas

{φ(x, m_{i}) | i ∈ I}

which is k–consistent^{1} but not consistent in M. M has the f.c.p if some formula has the f.c.p in M. It is well known that unstable structures have the f.c.p. (see [6].)

We will prove the following two theorems.

Theorem A Let A be a small subset of M. If M does not have the finite cover property then, for every λ ≥ |L|, if both M and A_{ind} are λ–stable then (M, A) is λ–stable.

Corollary 1.1 (Poizat [5]) If M does not have the finite cover property and N ≺ M is a small elementary substructure, then (M, N) is stable.

Corollary 1.2 (Zilber [7]) If U is the group of roots of unity in the field ℂ of complex numbers the pair (ℂ, U) is ω–stable.

Proof. (See [4].) As a strongly minimal set ℂ is ω–stable and does not have the f.c.p. By the subspace theorem of Schmidt [3] every algebraic set intersects U in a finite union of translates of subgroups definable in the group structure of U alone. Whence U_{ind} is nothing more than a (divisible) abelian group, which is ω–stable.

In [4] Pillay proved for strongly minimal M that (M, A) is stable whenever A is stable. The smallness of A is not needed. We will give an account of Pillay theorem in the last section of the paper (5.4).

Theorem B Let A be a small subset of M. If M is stable and A_{ind} does not have the finite cover property then (M, A) is stable.

1i.e. every k–element subset is consistent.

In both cases the theory of (M, A) depends only on the theory^{2} of A_{ind}: If B is a small subset of N ≡ M and B_{ind} ≡ A_{ind} then (M, A) ≡ (N, B) (Corollary 2.2).

While theorem A may have been part of the folklore theorem B seems to be new. It provides a new proof of the following theorem of Baldwin and Benedikt:

Corollary 1.3 (Baldwin–Benedikt [1]) If M is stable and I ⊂ M is a small set of indiscernibles, then (M, I) is stable.

This result has motivated our investigation. In section 2 our proof owes much to their paper.

Let A be a small subset of M. In section 2 we relativize the f.c.p to the (stronger) notion of the f.c.p over A and prove that every L(P)–formula is equivalent to a bounded formula if M does not have the f.c.p over A. In section 3 we conclude from this that (M, A) is κ–stable if M and A_{ind} are κ–stable. This implies theorem A.

For theorem B we show that M does not have the f.c.p over A if M is stable and A does not have the f.c.p (section 4). We do this using a simplified version of Shelah’s proof of his f.c.p theorem (4.5 and 4.6).

We thank Jörg Flum for bringing the problem to our attention.

2Note that the theory of M can be read off from the theory of A_{ind}.

2 Bounded formulas

M has the f.c.p over A if there is a formula φ(x, α, y) such that for all k there is a tuple m and a family (a_{i})_{i∈I} of tuples from A such that the set

{φ(x, a_{i}, m) | i ∈ I}

is k–consistent but not consistent in M. Note that if M has the f.c.p over A and (N, B) is elementarily equivalent to (M, A), then N has the f.c.p over B.

An L(P)–formula Φ(x_{1}, …, x_{m}) is bounded if it has the form

Q_{1}α_{1} ∈ P … Q_{n}α_{n} ∈ P φ(x_{1}, …, x_{m}, α_{1}, …, α_{n}),

where the Q_{i} are quantifiers and φ is an L–formula.

Proposition 2.1 Let A be a small subset of M. If M ist stable and does not have the finite cover property over A then in (M, A) every L(P)–formula is equivalent to a bounded formula.

Proof. We show by induction on the number of quantifiers in φ that every L(P)–formula φ is in (M, A) equivalent to a bounded one. The induction starts with the observation that P (x) is equivalent to ∃α ∈ P α = x, which is bounded. For the induction step we show that for all tuples x of variables and all bounded Φ(x, y), the formula ∃y Φ(x, y) is equivalent to a bounded one.

Write

Φ(x, y) = Qα ∈ P φ(x, y, α),

where Qα ∈ P is a block

Q_{1}α_{1} ∈ P Q_{2}α_{2} ∈ P …

of bounded quantifiers and φ(x, y, α) belongs to L. Since M is stable for all m, n from M there is an L–formula θ(α, β) and a parameter tuple b in A such that

(M, A) ⊧ ∀α ∈ P (φ(m, n, α) ↔ θ(α, b)).

Since this is also true in all (M′, A′) which are elementarily equivalent to (M, A) a compactness argument shows that there is a finite number of formulas θ which serve for all m, n. We may assume that A has at least two elements, which allows us to code everything in just one formula θ. This gives

(M, A) ⊧ ∀xy ∃β ∈ P ∀α ∈ P (φ(x, y, α) ↔ θ(α, β)).

It follows easily that Φ(x, y) is equivalent in (M, A) to

∃β ∈ P (∀α ∈ P (φ(x, y, α) ↔ θ(α, β)) ∧ Qα ∈ P θ(α, β)).

Set ψ(x, y, α, β) := (φ(x, y, α) ↔ θ(α, β)). Since M does not have the f.c.p over A, there is some k < ω such that for all m, b from M, the set

{ψ(m, y, a, b) | a ∈ A}

is consistent if it is k-consistent. Now, A is small in M and this implies that the following sentence holds in (M, A):

∀x β ((∀α_{0} ∈ P … ∀α_{k−1} ∈ P ∃y ⋀_{i<k} ψ(x, y, α_{i}, β)) → ∃y ∀α ∈ P ψ(x, y, α, β)).

Hence ∃y Φ(x, y) is equivalent to the bounded formula

∃β ∈ P ((∀α_{0} ∈ P … ∀α_{k−1} ∈ P ∃y ⋀_{i<k} ψ(x, y, α_{i}, β)) ∧ Qα ∈ P θ(α, β)).

This proves the proposition. □

Corollary 2.2 Let M and A be as in 2.1. If B is a small subset of N ≡ M and B_{ind} ≡ A_{ind} then (M, A) ≡ (N, B)

Proof. We know that both in (M, A) and in (N, B) every L(P)–sentence is equivalent to a bounded one. The obtainment of the bounded equivalent for a given L(P)–sentence depends on a finite number of choices, the choice of the formulas θ(α, γ) and the choice of the numbers k < ω associated to the failure of the relativized f.c.p. These choices can be different in (M, A) and in (N, B). But it is clear that in each case we can make a common choice for both structures: For θ we take a formula which codes the two formulas θ’s which serve for (M, A) and (N, B) respectively, and for k we take the maximum of both k′s. Therefore we have a uniform procedure in (M, A) and (M, B) to obtain a bounded equivalent of each L(P)–sentence. But bounded sentences speak only about the induced structure of A and B respectively.

The reader may note that the corollary implies that the bounded formulas of proposition 2.1 can be chosen to depend only on the theory of A_{ind}. □

3 The Stability of (M, A)

We fix an L–structure M and a subset A.

Proposition 3.1 If in (M, A) every L(P)–formula is equivalent to a bounded formula, then for every λ ≥ |L|, if both M and A_{ind} are λ–stable then (M, A) is λ–stable.

Before giving the proof of the proposition we need some lemmas. We say that a mapping f between two subset of M is bounded if it preserves all bounded formulas.

Lemma 3.2 If f is an L–elementary mapping and extends a permutation of A, then f is bounded.

Proof. Left to the reader. □

Lemma 3.3 Assume M is stable and A_{ind} is saturated. Let B, C be subsets of M and let B_{0} = B ∩ A and C_{0} = C ∩ A. Assume |B_{0}|, |C_{0}| < |A|, and that tp(B/A) is the only non-forking extension of tp(B/B_{0}) to A and tp(C/A) is the only non-forking extension of tp(C/C_{0}) to A. If f : B → C is an L–elementary mapping such that f(B_{0}) = C_{0}, and f ↾ B_{0} is bounded, then f is bounded.

Proof. Since f ↾ B_{0} preserves bounded formulas, it is elementary in A and can be extended to an automorphism g of A_{ind}, i.e, to an L-elementary permutation of A. Since tp(B/A)^{g} is the only non-forking extension of tp(B/B_{0})^{g} = tp(C/C_{0}) to g(A) = A, we see that tp(B/A)^{g} = tp(C/A). This means that f ∪ g is Lelementary. By Lemma 3.2 f ∪ g is bounded. □

We define the bounded type of a tuple m over B to be the set tp_{b}(m/B) of all bounded formulas over B which are satisfied by m.

Proof of Proposition 3.1.

Let B be a set of cardinality λ. We show that there are ≤ λ bounded types over B. Since A_{ind} is stable we may assume that A_{ind} is saturated and |B| < |A|^{3} Extending B if necessary we may assume that tp(B/A) is the only non-forking extension of tp(B/B_{0}) to A, where B_{0} = A ∩ B. Also, without loss of generality, (M, A) is λ^{+}–saturated.

Let T be the complete theory of M. For each b ∈ M, choose a sequence b_{0} of length < κ(T) (^{4}) in A such that tp(b/BA) does not fork over over Bb_{0}. It follows that tp(bB/A) does not fork over B_{0}b_{0}.

3Choose a suitable cardinal κ > λ such that Th(A_{ind}) is κ–stable and (M, A) has a special extension (M′, A′) of cardinality κ. Since then Th(A_{ind}) has a saturated model of cardinality κ, A′_{ind} is must be saturated.

4κ(T) is the smallest cardinal κ with the property that in models of T every type tp(b/B)

does not fork over some B_{0} ⊂ B with fewer than κ elements. κ(T) is bounded by |T |^{+}.

Claim For any sequence d of length < κ(T) in A there are at most λ many bounded types over B of tuples b such that tp_{b}(b_{0}/B_{0}) = tp_{b}(d/B_{0}) and tp(b_{0}/B) = tp(d/B).

Proof. Let tp(b_{0}/B) = tp(d/B) and tp_{b}(b_{0}/B_{0}) = tp_{b}(d/B_{0}). This implies that the mapping f which is the identity on B and transforms b_{0} in d is L–elementary and, restricted to B_{0}b_{0}, is bounded.

Observe that tp(Bb_{0}/A) is the only non-forking extension of tp(Bb_{0}/B_{0}b_{0}) to A and that tp(Bd/A) is the only non-forking extension of tp(Bd/B_{0}d) to A. By Lemma 3.3 f is bounded, and therefore tp_{b}(b_{0}/B) = tp_{b}(d/B). Since in (M, A) every L(P)–formula is equivalent to a bounded one, these are complete L(P)–types over B and we can find b′ ∈ M such that

tp_{b}(b′d/B) = tp_{b}(bb_{0}/B).

This implies that tp(b′/BA) does not fork over Bd since tp(b/BA) does not fork over Bb_{0}. By Lemma 3.2 the bounded type tp_{b}(b′/Bd) is determined by tp(b′/AB). But each type tp(b′/Bd) has at most λ many non-forking extensions to AB. (Multiplicities are bounded by λ if T is stable in λ and λ ≥ |L|.) And since there are at most λ many types tp(b′/Bd), the claim is proved.

By the claim we have to show that λ is a bound for both

• the number of all types tp(d/B)

• the number of all bounded types tp_{b}(d/B_{0})

where d ranges over all tuples of length < κ(T) from A. Since M is stable in λ, λ^{<κ(T)} = λ. This shows that it is enough to bound the number of types of single elements. But now λ bounds the number of the tp(d/B) since T is λ–stable and the number of the tp_{b}(d/B_{0}) (d ∈ A) since A_{ind} is λ–stable. □

We conclude

Theorem A Let A be a small subset of M. If M does not have the finite cover property and A is stable then (M, A) is stable.

4 Proof of Theorem B

Let again M be an L–structure with an infinite subset A.

By Shelah’s f.c.p–theorem (Theorem II.4.3 in [6]) M does not have the f.c.p iff M is stable and for every ϕ(x, y, z) there is a bound l such that whenever ϕ(x, y, m) defines an equivalence relation with more than l classes then there are infinitely many classes.

We call M to be stable over A if in every (N, B) elementarily equivalent to (M, A) every type over B is definable by a bounded formula with parameters from B. Clearly, if M is stable, it is stable over every subset A.

We show here that if M is stable over A and if A_{ind} does not have the f.c.p, then M does not have the f.c.p over A. We will also see (in a remark after Corollary 4.4) that conversely M being unstable over A implies the f.c.p over A.

Let φ = φ(x, y) be in L and C a subset of M. A φ–formula over C is a formula of the form φ(x, c) where c is a tuple in C. A φ–type over C is a maximally consistent set of φ–formulas and negated φ–formulas over C. We denote by S_{φ}(C) the set of all φ–types over C.

Lemma 4.1 If M is stable over A, for every bounded formula Φ(x, α) there is a bounded Θ(α, β) such that

(M, A) ⊧ ∀x ∃β ∈ P ∀α ∈ P (Φ(x, α) ↔ Θ(α, β)).

Proof. Let Φ(x, α) = Q_{1}γ_{1} ∈ P … Q_{n}γ_{n} ∈ P φ(x, α, γ) where γ = γ_{1}, …, γ_{n}, each Q_{i} is a quantifier and φ(x, α, γ) ∈ L. By definability of types over A, for each tuple m ∈ M there exists a bounded formula Ψ(α, β, γ) and some b ∈ A such that Ψ(α, b, γ) defines the φ–type of m over A, that is, for all a, c ∈ A, (M, A) ⊧ φ(m, a, c) ↔ Ψ(a, b, c). By compactness there is a finite set of bounded formulas such that for each m ∈ M the φ-type of m over A can be defined by a formula in this set using some parameter b ∈ A. This finite set can be reduced to a single formula by the usual trick (see [6], Lemma II.2.1). Hence there is a fixed bounded Ψ(α, β, γ) such that for all m ∈ M there is some b ∈ A such that for all a, c ∈ A, (M, A) ⊧ φ(m, a, c) ↔ Ψ(a, b, c). We put Θ(α, β) := Q_{1}γ_{1} ∈ P … Q_{n}γ_{n} ∈ P Ψ(α, β, γ). □

Before entering the proof of Proposition 4.6, we need a relativized version of Shelah’s φ–rank. Assume (M, A) is ω–saturated, let φ(x, α, y) ∈ L, and m a tuple in M. Working in Th(M, m) we can consider φ(x, α, m)–types over A, which are maximal consistent sets of formulas (¬) φ(x, a, m) with parameters a ∈ A. Let S_{φ(x,α,m)}(A) be the boolean space of all φ(x, α, m)–types over A. The rank

R_{φ,m}^{A}(ψ(x))

is the Cantor–Bendixson rank of the closed subspace

{q ∈ S_{φ(x,α,m)}(A) | q is consistent with ψ}.

The multiplicity Mlt_{φ,m}^{A}(ψ(x)) is defined as the Cantor–Bendixson degree of this space. Note that R_{φ,m}^{M} is Shelah’s φ–rank.

If (M, A) is not ω–saturated, we compute R_{φ,m}^{A} in an ω–saturated elementary extension (M′, A′). It is easy to see that this rank does not depend on the choice of (M′, A′).

The next lemma is easy. But it is this lemma which allows us to give a short proof of Lemma 4.5.

Lemma 4.2 Assume (M, A) is ω-saturated. Let m be a tuple of elements of M, ψ(x) an L–formula with parameters from M and n a natural number. Then:

1. R_{φ,m}^{A}(ψ) ≥ n + 1 if and only if there is a family (a_{i})_{i<ω} in A such that for all i < j < ω

R_{φ,m}^{A}(ψ(x) ∧ (φ(x, a_{i}, m)Δφ(x, a_{j}, m))) ≥ n. (^{5})

2. Let R_{φ,m}^{A}(ψ) = n and let Mlt_{φ,m}^{′A}(ψ) be the biggest k < ω for which there exist a_{0}, …, a_{k−1} in A such that for all i < j < k

R_{φ,m}^{A}(ψ(x) ∧ (φ(x, a_{i}, m)Δφ(x, a_{j}, m))) ≥ n.

Then Mlt_{φ,m}^{A}(ψ) ≤ 2^{Mlt_{φ,m}^{′A}(ψ)} and Mlt_{φ,m}^{′A}(ψ) ≤ 2^{Mlt_{φ,m}^{A}(ψ)}.

Proof. Let X be the space of all φ(x, α, m)–types over A which are consistent with ψ and X^{(n)} the set of all elements of X of Cantor-Bendixson at least n. Let χ(x) be a boolean combination of φ(x, α, m)–formulas over A. Then

X = {p ∈ X | p ⊢ χ} ∪ {p ∈ X | p ⊢ ¬χ}

is a clopen partition of X. This implies

R_{φ,m}^{A}(ψ ∧ χ) ≥ n iff p ⊢ χ for some p ∈ X^{(n)}.

Define on (a suitable power of) A the binary relation

a_{1} ∼ a_{2} iff R_{φ,m}(ψ(x) ∧ (φ(x, a_{1}, m)Δφ(x, a_{2}, m))) < n.

From the last observation follows that

a_{1} ∼ a_{2} iff {p ∈ X^{(n)} | φ(x, a_{1}, m) ∈ p} = {p ∈ X^{(n)} | φ(x, a_{2}, m) ∈ p},

which implies that

• ∼ is an equivalence relation in A,

• a/∼ is determined by the set of all p ∈ X^{(n)} which contain φ(x, a, m),

• p ∈ X^{(n)} is determined by the set of all a/∼ where φ(x, a, m) ∈ p.

5We write (φΔψ) for the formal symmetric difference ¬(φ ↔ ψ).

Whence X^{(n)} is infinite iff ∼ has infinitely many classes, which is the content of 1.

If R_{φ,m}^{A}(ψ) = n we have Mlt_{φ,m}^{′A}(ψ) = |A/∼| and Mlt_{φ,m}(ψ) = |X^{(n)}|, which implies 2. □

The following lemma can be proved like Theorem II.2.2 and Theorem II.2.13 in [6].

Lemma 4.3 The following are equivalent.

1. M is stable over A.

2. For some cardinal number λ there are at most λ types over B for every B and N such that (N, B) ≡ (M, A) and |B| ≤ λ.

3. The following does not exist: A model (N, B) ≡ (M, A), an L–formula φ(x, α), a family (m_{i})_{i<ω} of elements of N and a family (a_{i})_{i<ω} of elements of B such that for all i, j

N ⊧ φ(m_{i}, a_{j}) iff i < j.

4. For all ψ, φ, R_{φ}^{A}(ψ) < ω. □

From condition 3. of this lemma it is clear that M is stable over A iff (M, m) is stable over A. Hence:

Corollary 4.4 M is stable over A if and only if R_{φ,m}^{A}(ψ) < ω for all ψ, φ and m. Furthermore, if M is stable over A, R_{φ,m}^{A}(ψ) can be bounded by a number which depends only on φ.

Proof. Only the second part of the assertion deserves a demonstration. If a formula φ = φ(x, α, y) is given, we denote by φ′ the same formula, but considered as a formula in two sets of variables, xy and α. It is easy to see that for all ϕ = ψ(x, y) and all m

R_{φ,m}^{A}(ψ(x, m)) ≤ R_{φ′}^{A}(ψ(x, y)).

This shows that R_{φ′}^{A}(true) is the desired bound. □

One can easily see that if M does not have the f.c.p over A, M is stable over A: In the same way as the presence of a formula with the order property gives the finite cover property, a formula φ(x, α) with the order property “over” A gives the finite cover property over A.

Lemma 4.5 Assume M is stable over A and A_{ind} does not have the f.c.p. Then the relativized rank is definable: Let the L–formulas φ(x, α, y) and ψ(x, β, z) be given and let k be a natural number . Then there is a bounded Θ(β, γ) such that for all m, n ∈ M there is a c ∈ A such that for all b ∈ A

R_{φ,m}^{A}(ψ(x, b, n)) = k iff (M, A) ⊧ Θ(b, c).

Moreover there is a bound l < ω for the multiplicity. That is, for all m, n ∈ M and all b ∈ A

Mlt_{φ,m}^{A}(ψ(x, b, n)) < l.

Proof. We may assume that (M, A) is ω–saturated. It is enough to show that we can find a bounded Θ(β, γ) which defines “rank ≥ k”.

First consider the case k = 0. We have R_{φ,m}^{A}(ψ(x, b, n)) ≥ 0 if and only if M ⊧ ∃x ψ(x, b, n). Choose Θ(β, γ) with Lemma 4.1 such that

(M, A) ⊧ ∀z ∃γ ∈ P ∀β ∈ P (∃x ψ(x, β, z) ↔ Θ(β, γ)).

Assume now inductively that we can define “rank ≥ k” and let ψ(x, β, z) ∈ L. Given m, n ∈ M and b ∈ A, consider the following relation on tuples of A:

a_{1} ≡ a_{2} (mod m, n, b) iff R_{φ,m}^{A}(ψ(x, b, n) ∧ (φ(x, a_{1}, m)Δφ(x, a_{2}, m))) < k.

It is an equivalence relation and by the inductive hypothesis there is a bounded formula Φ(α_{1}, α_{2}, β, γ) such that for all m, n ∈ M there exists c ∈ A such that for all a_{1}, a_{2}, b ∈ A,

a_{1} ≡ a_{2} (mod m, n, b) iff (M, A) ⊧ Φ(a_{1}, a_{2}, b, c).

From this follows that, since A_{ind} does not have the finite cover property, there is some l < ω such that for all m, n ∈ M and all b ∈ A, if equivalence modulo (m, n, b) has more than l equivalence classes on A, it has infinitely many. In this case the condition R_{φ,m}^{A}(ψ(x, b, n)) ≥ k + 1 is equivalent to

∃α_{0} ∈ P … ∃α_{l} ∈ P ⋀_{i<j≤l} ¬α_{i} ≡ α_{j} (mod m, n, b).

Observe that the l above bounds the multiplicity in rank k. □

Proposition 4.6 If M is stable over A and if A_{ind} does not have the f.c.p then M does not have the f.c.p over A.

Proof. Let φ = φ(x, α, y) ∈ L be given. By Corollary 4.4 there is a number k_{0} such that R_{φ,m}^{A}(x = x) < k_{0} for all m. By Lemma 4.5 this rank is definable and for every ψ(x, z) there is a bound for the φ-multiplicity of ψ-formulas.

We show by induction on k the following: For each k and each ψ(x, z) there is a bound N such that for all m and n in M the following is true: If R_{φ,m}^{A}(ψ(x, n)) = k and Σ(x) is a set of φ(x, α, m)–formulas over A such that {ψ(x, n)} ∪ Σ(x) is inconsistent then there is a subset Σ_{0} ⊂ Σ of at most size N such that {ψ(x, n)} ∪ Σ_{0}(x) is inconsistent. Applied to all k below k_{0} and x = x this implies the proposition.

The induction starts with the trivial case k = −1, where N = 0 suffices. Now suppose the claim is true for all k′ < k.

Let l be a bound for the φ–multiplicity of ψ–formulas. This means that for all m and n Mlt_{φ,m}^{A}(ψ(x, n)) ≤ l. Now, if {ψ(x, n)} ∪ Σ(x) is inconsistent, there must be a formula φ(x, a_{1}, m) ∈ Σ(x) such that ψ(x, n) ∧ φ(x, a_{1}, m) has either a smaller rank than ψ(x, n) or a smaller multiplicity. If the rank remains the same we continue and find a φ(x, a_{2}, m) ∈ Σ(x) such that ψ(x, n)∧φ(x, a_{1}, m)∧ φ(x, a_{2}, m) has smaller rank or smaller multiplicity.

This process must stop after at most l steps when we have found formulas φ(x, a_{1}, m), …, φ(x, a_{l}, m) in Σ(x) such that the conjunction

ψ′(x, m, n, a_{1}, …, a_{l}) = ψ(x, n) ∧ φ(x, a_{1}, m) ∧ … ∧ φ(x, a_{l}, m)

has a φ(x, α, m)–rank k′ which is smaller than k. By induction there is a bound N′ attached to k′ and ψ′(x, y, z, u_{1}, …, u_{l}). Then N = l + N′ is the desired bound for k and ψ(x, z). □

Theorem B Let A be a small subset of M. If M is stable and A_{ind} does not have the finite cover property then (M, A) is stable.

Proof. If M is stable it is also stable over A. By 4.6 M does not have the f.c.p over A. By 2.1 every L(P)–formula is equivalent to a bounded formula. A_{ind}, not having the f.c.p, is stable. Thus (M, A) is stable by 3.1. □

5 Further results

A look at the proof of Proposition 4.6 shows that actually something stronger was proved.

Lemma 5.1 Assume M is stable over A ⊂ M. If M has the f.c.p over A, then there is some bounded Ψ(α_{1}, α_{2}, β) and a family of parameters (b_{i})_{i<ω} in A such that

1. For every b ∈ A, Ψ(α_{1}, α_{2}, b) defines an equivalence relation on tuples of A.

2. For each i < ω, Ψ(α_{1}, α_{2}, b_{i}) has more than i but only finitely many equivalence classes.

Proof. By the hypothesis and the proof of 4.6 the relativized rank is not definable. The proof of 4.5 shows that this implies that the conclusion holds. Actually the formula Ψ constructed in the proof of 4.5 contains a parameter c from A, but c can be incorporated in the parameters b. □

The converse of Lemma 5.1 is not true. Take a structure M with an equivalence relation which has infinitely many classes all of which are infinite. Let A be a subset of M which has finite intersection with each class, in such a way that for each n there is a class which intersects A in more than n elements. M does not have the f.c.p, A_{ind} is stable and has the f.c.p.

The next three propositions give an alternative proof of 2.1.

Proposition 5.2 Let A be a small subset of M and (M, A) be |L|^{+}–saturated. Then M not having the f.c.p over A implies that, for every finite tuple m from M, every type over Am is realized in M.

Proof. Assume that M does not have the f.c.p over A and let p(x) be a type over Am. We prove first that for all φ(x, α, y) the φ(x, α, m)–part

p_{φ(x,α,m)} = {(¬)φ(x, a, m) | (¬)φ(x, a, m) ∈ p}

of p is realized in M. Let θ(α, b) (for some b ∈ A) define the φ(x, α, m)–part. This means that p_{φ(x,α,m)} is equivalent to

Φ_{m,b} = {φ(x, a, m) ↔ θ(a, b) | a ∈ A, (M, A) ⊧ θ(a, b)}

Now argue as in the proof of 2.1. Since M does not have the f.c.p over A the fact that a consistent set of this form is always realized is expressible by an L(P)–sentence, which is true since A is small.

Choose a realization c_{φ} of p_{φ(x,α,m)} for all φ. Then use the |L|^{+}–saturation of (M, A) and realize the set

{∀α ∈ P (φ(x, α, m) ↔ φ(c_{ϕ}, α, m)) | φ an L–formula}.

□

We do not know if the non–f.c.p over A can be characterized by this condition. But note that the conclusion of the proposition implies the equivalent conditions of 5.3.

Proposition 5.3 Let M be stable over A ⊂ M. Then the following are equivalent.

1. Every L(P)–formula is in (M, A) equivalent to a bounded formula.

2. If (N, B) ≡ (M, A), every elementary mapping in N extending a permutation of B is elementary in (N, B).

3. Let (N, B) ≡ (M, A) be |L|^{+}–saturated and let h be an elementary mapping in N which is a finite extension of a permutation of B. Then for every a ∈ N there is b ∈ N such that h ∪ {(a, b)} is elementary in N.

Proof. By Lemma 3.2 it is clear that 1. implies 2.

To show that 3. follows from 2. we write h = f ∪ {(m, n)} where f is a permutation of B and m, n are tuples in N. Let a ∈ N be given.

We prove first that for each φ(x, y, γ) ∈ L there is a b_{φ} ∈ N such that for each c ∈ B,

(N, B) ⊧ φ(a, m, c) iff (N, B) ⊧ φ(b_{φ}, n, f(c)).

Let Θ(α, γ) ∈ L(P) and d ∈ B be such that Θ(d, γ) is a definition of the φ-type of am over B, that is,

(N, B) ⊧ ∀γ ∈ P (φ(a, m, γ) ↔ Θ(d, γ)).

Hence

(N, B) ⊧ ∃x∀γ ∈ P (φ(x, m, γ) ↔ Θ(d, γ)).

By 2. h is elementary in L(P) and therefore for some b_{φ} ∈ N,

(N, B) ⊧ ∀γ ∈ P (φ(b_{φ}, n, γ) ↔ Θ(f(d), γ)).

Clearly b_{φ} is as required.

Since we can code a finite sequence of formulas \overline{φ} = φ_{1}, …, φ_{k} in one, we find for each such sequence a b\overline{φ} such that for each i and c ∈ B,

(N, B) ⊧ φ_{i}(a, m, c) iff (N, B) ⊧ φ_{i}(b\overline{φ}, n, f(c)).

This shows that the set

{φ(x, n, f(c)) ↔ φ(b_{φ}, n, f(c)) | φ(x, y, γ) ∈ L, c ∈ B}

is finitely satisfiable. Since (N, B) is |L|^{+}-saturated the set is realized by some b ∈ B.

If 3. is true the system of elementary mappings which are finite extensions of permutations of B is a back and forth system, which shows that these mappings preserve L(P)–formulas. This proves that 3. implies 2.

We prove finally that 2. implies 1. Assume that (N, B) ≡ (M, A) and m, m′ are tuples in N such that m satisfies the same bounded formulas as m′. We obtain an |L|^{+}–saturated elementary extension (N′, B′) of (N, B) and an elementary permutation h of B′ such that h(m) = m′. By 2. h preserves L(P)– formulas. Whence m and m′ satisfy the same L(P)–formulas. □

Since 3. is true for strongly minimal N, we conclude

Corollary 5.4 (Pillay [4]) Let M be strongly minimal and A an arbitrary subset of M. Then every L(P)–formula is in (M, A) equivalent to a bounded formula. If A_{ind} is stable then also (M, A) is stable.

The corollary can also be proved in the style of 2.1. There are two cases: If A is small the result follows directly from 2.1. If A is not small then M is algebraic over A in a definable manner. In this case one uses a variant of the proof of 2.1.

For A an elementary substructure of M the next proposition follows from Théorème 4 in [5].

Proposition 5.5 For i = 1, 2, let M_{i} be stable and A_{i} a subset of M_{i} such that (A_{i})_{ind} is |L|^{+}–saturated. Assume also that for every finite f ⊂ M_{i} every type over A_{i}f is realized in M_{i}. If (A_{1})_{ind} ≡ (A_{2})_{ind}, then (M_{1}, A_{1}) ≡ (M_{2}, A_{2}).

Proof. Let I be the set of all partial isomorphisms of the form {(a, b)} where a, b are tuples in M_{1}, M_{2} respectively such that tp(aa_{0}) = tp(bb_{0}) and tp_{b}(a_{0}) = tp_{b}(b_{0}) for some sequence a_{0} of length ≤ |L| in A_{1} such that tp(a/A_{1}) is the only nonforking extension of tp(a/a_{0}) to A_{1} and some sequence b_{0} of length ≤ |L| in A_{2} such that tp(b/A_{2}) is the only nonforking extension of tp(b/b_{0}) to A_{2}.

We claim that I is a back and forth system between (M_{1}, A_{1}) and (M_{2}, A_{2}). From this it will follow that these models are elementarily equivalent. We check first that every {(a, b)} ∈ I is a partial isomorphism between (M_{1}, A_{1}) and (M_{2}, A_{2}). Let a = a_{1}, …, a_{n} and b = b_{1}, …, b_{n}. It suffices to show that for each i = 1, …, n, b_{i} ∈ A_{2} if a_{i} ∈ A_{1}. Choose sequences a_{0}, b_{0} for a, b as in the definition of I. Suppose a_{i} ∈ A_{1}. By |L|^{+}–saturation of (A_{2})_{ind} there is an a′_{i} ∈ A_{2} such that tp_{b}(a_{0}a_{i}) = tp_{b}(b_{0}a′_{i}). Let f be an elementary mapping taking a_{0}a_{i} onto b_{0}a′_{i}. Since tp(a/a_{0}a_{i})^{f} is the only nonforking extension of tp(a/a_{0})^{f} = tp(b/b_{0}) to b_{0}a′_{i}, it must coincide with tp(b/b_{0}a′_{i}). Hence b_{i} = a′_{i} ∈ A_{2}.

By symmetry it is now enough to show that if {(a, b)} ∈ I and c is an element of M_{1} we can find an element d of M_{2} such that {(ac, bd)} ∈ I. Choose a_{0} and b_{0} for a and b as in the definition of I and let c′ be a sequence of length ≤ |L| in A_{1} such that tp(c/A_{1}a) is the only nonforking extension of tp(c/c′a) to A_{1}a. Hence tp(ac/A_{1}) is the only nonforking extension of tp(ac/a_{0}c′) to A_{1}. Since tp_{b}(a_{0}) = tp_{b}(b_{0}), by |L|^{+}–saturation of (A_{2})_{ind} we can find a sequence d′ in A_{2} such that tp_{b}(a_{0}c′) = tp_{b}(b_{0}d′). As above, tp(aa_{0}c′) = tp(bb_{0}d′). Let f be an elementary mapping taking aa_{0}c′ onto bb_{0}d′ and let p(x) be a nonforking extension of tp(c/aa_{0}c′)^{f} to A_{2}b. By assumption there is some realization d of p in M_{2}. It is clear that tp(ac) = tp(bd) and that tp(bd/A_{2}) is a nonforking extension of tp(bd/b_{0}d′). Now we show that in fact it is the only nonforking extension of tp(bd/b_{0}d′) to A_{2}. This will imply that {(ac, bd)} ∈ I. Since tp(b/A_{2}) is the only nonforking extension of tp(b/b_{0}) to A_{2}, we only have to prove that tp(d/b_{0}d′) has at most one nonforking extension to A_{2}b. Assume that, on the contrary, for some finite sequence e in A_{2}, tp(d/b_{0}d′) has two nonforking extensions to b_{0}d′eb. By |L|^{+}–saturation of (A_{1})_{ind} there is some f in A_{1} such that tp(a_{0}c′f) = tp(b_{0}d′e). Hence tp(aa_{0}c′f) = tp(bb_{0}d′e), and this implies that tp(c/a_{0}c′) has two nonforking extensions to a_{0}c′fa, a contradiction. □

For indiscernible A the next proposition is contained in [1].

Proposition 5.6 Assume that M is stable, A is small, A_{ind} does not have the f.c.p and that (M, A) is saturated. Then every L–elementary permutation of A extends to an automorphism of M.

Proof. If f : A → A is an L–elementary permutation it preserves bounded formulas. By 2.1 f preserves all L(P)–formulas. Since (M, A) is stable and saturated f extends to an automorphism.

For A ≺ M the next proposition was proved in [5].

Proposition 5.7 If M does not have the f.c.p, A ⊂ M is small and if A_{ind} does not have the f.c.p, then (M, A) does not have the f.c.p.

Proof. Let T be the theory of M, T′ the theory of (M, A) and let T′′ be the theory of all beautiful pairs of T′ in the sense of [5]. Hence T′′ is the theory of all models (M_{2}, A_{2}, M_{1}, A_{1}) where (M_{2}, A_{2}) ⊧ T′, (M_{1}, A_{1}) is a |L|^{+}–saturated elementary substructure of (M_{2}, A_{2}) and for each finite f ⊂ M_{2}, each L(P)– type over M_{1}f is realized in (M_{2}, A). The predicate P is interpreted as the set A_{2} in the structure (M_{2}, A_{2}, M_{1}, A_{1}) and we have a new unary predicate Q to be interpreted as the set M_{1}. The set A_{1} is given only as the intersection of M_{1} with A_{2}. Since T′ is stable, we can apply Theorem 6 of [5] to show that T′ does not have the f.c.p. We have to prove that in every |L|^{+}–saturated model (M_{2}, A_{2}, M_{1}, A_{1}) of T′′ for every finite m ⊂ M_{2} every L(P)–type over M_{1}m is realized in (M_{2}, A_{2}). Let p(x) be an L(P)–type over M_{1}m. Let a be a realization of p(x) in an elementary extension (M_{3}, A_{3}) of (M_{2}, A_{2}). We will find some b ∈ M_{2} with the same L(P)–type over M_{1}m as a.

We can assume (M_{3}, A_{3}) is |L|^{+}–saturated. By Proposition 5.2 for every finite f ⊂ M_{3}, every L–type over A_{3}f is realized in M_{3} and for every finite f ⊂ M_{2}, every L–type over A_{2}f is realized in M_{2}. By this and by the stability of M_{3} and M_{2} we can use the back and forth system presented in the proof of Proposition 5.5 to determine equality of L(P)–types of tuples in (M_{3}, A_{3}) and in (M_{2}, A_{2}): if we find Y ⊂ A_{3}, Z ⊂ A_{2} and b ∈ M_{2} such that tp(M_{1}ma/A_{3}) is the only nonforking extension of tp(M_{1}ma/Y) to A_{3}, that tp(M_{1}mb/A_{2}) is the only nonforking extension of tp(M_{1}mb/Z) to A_{2}, that tp_{b}(Y) = tp_{b}(Z) and that tp(M_{1}maY) = tp(M_{1}mbZ), then we can conclude that M_{1}ma and M_{1}mb have the same L(P)–type and hence that b realizes p(x).

We start by choosing U ⊂ A_{2}∖A_{1} of cardinality ≤ |L| such that tp(m/M_{1}A_{2}) is the only nonforking extension of tp(m/M_{1}U) to M_{1}A_{2}. Observe that the fact that (M_{1}, A_{1}) ≺ (M_{2}, A_{2}) implies that tp(M_{1}/A_{2}) is the only nonforking extension of tp(M_{1}/A_{1}) to A_{2} and hence that tp(M_{1}m/A_{2}) is the only nonforking extension of tp(M_{1}m/A_{1}U) to A_{2}. From this it follows also that tp(M_{1}m/A_{3}) is the only nonforking extension of tp(M_{1}m/A_{1}U) to A_{3}. Let V ⊂ A_{3} be an extension of U of cardinality ≤ |L| and such that tp(a/M_{1}mA_{3}) is the only nonforking extension of tp(a/M_{1}mA_{1}V) to M_{1}mA_{3}. Then tp(M_{1}ma/A_{3}) is the only nonforking extension of tp(M_{1}ma/A_{1}V) to A_{3}. We claim that we can find a realization V′ of tp_{b}(V/A_{1}U) in (M_{2}, A_{2}). Note that (A_{2}, A_{1}) is a model of the theory of all beautiful pairs of the theory of A_{2} and that it is |L|^{+}–saturated. Since (A_{2})_{ind} does not have the f.c.p, by Theorem 6 of [5] for every finite f ⊂ A_{2} every type over A_{1}f is realized in A_{2}. By |L|^{+}–saturation of (A_{2}, A_{1}) this is also true for types in |L| variables over A_{1}W for any W ⊂ A_{2} of cardinality ≤ |L|. Hence every bounded type over A_{1}U in |L| variables is realized in (M_{2}, A_{2}) and we can choose V′ ⊂ A_{2} as claimed above.

The next step is to observe that for every finite f ⊂ M_{2}, every L–type over M_{1}A_{2}f is realized in M_{2}. Clearly it is enough to show that for each φ(x, y) ∈ L we can realize in M_{2} each φ–type q(x) over M_{1}A_{2}f. Let θ(w, y) ∈ L and c ∈ M_{2} be such that θ(c, y) is a definition of q(x), let κ = |M_{2}| + |A_{2}| and let N be a κ^{+}–saturated elementary extension of M_{2}. By Proposition 5.5 (N, A_{2}) is an elementary extension of (M_{2}, A_{2}). By choice of N, for each finite g ⊂ N the φ– type over M_{2}A_{2}g defined by θ(c, y) is realized in N. This fact can be expressed in the language L(P) ∪ {Q} and hence the φ–type q(x) over M_{1}A_{2}f defined by θ(c, y) is realized in M_{2}.

Since V and V′ have the same type over A_{1}U and tp(M_{1}m/A_{1}U) has only one nonforking extension to A_{3} we can conclude that tp(M_{1}V m) = tp(M_{1}V′m). Thus we can choose b ∈ M_{2} such that tp(M_{1}V′mb) = tp(M_{1}V ma) and b is independent from M_{1}A_{2}m over M_{1}V′m. Also, since A_{1}V and A_{1}V′ have the same bounded type, tp(M_{1}mb/A_{2}) is the only nonforking extension of tp(M_{1}mb/A_{1}V′) to A_{2} and from this it follows that M_{1}mb and M_{1}ma have the same L(P)–type. □

If M is stable, A ⊂ M small and A_{ind} does not have the f.c.p, the next proposition implies that every L(P)–formula is equivalent to a bounded formula of the type indicated below. For elementary submodels this is due to Bouscaren and Poizat [2].

Proposition 5.8 If M is stable over A every bounded formula is equivalent to a boolean combination of bounded formulas of the form

∃α_{1} ∈ P … ∃α_{n} ∈ P (φ(x, α_{1}, …, α_{n}) ∧ Φ(α_{1}, …, α_{n})),

where φ is in L and Φ is bounded.

Proof. Let p be a (complete) type over A and φ(x, α) be an L–formula. We define R_{φ}^{A}(p) as the minimal rank R_{φ}^{A}(ψ) of a formula ψ in p. Since every formula is equivalent to disjunction of formulas with relative φ–multiplicity 1 one can find a ψ_{p,φ} ∈ p such that

R_{φ}^{A}(p) = R_{φ}^{A}(ψ_{p,φ}) and Mlt_{φ}^{A}(ψ_{p,φ}(x)) = 1.

If B is a subset of A and if ψ_{p,φ} is over B for all φ we call B a base of p. If B is a base of p, p is the only extension of p ↾ B to A with the same φ–ranks for all φ since

θ(x, a) ∈ p ⟺ R_{θ}^{A}(θ(x, a) ∧ ψ_{p,θ}(x)) = R_{θ}^{A}(p).

Let (M, A) be |L|^{+}–saturated. We have to show that two finite tuples b and c from M satisfy the same bounded formulas whenever they satisfy the same formulas of the type described in the proposition. For this we choose a basis B of tp(b/A) of cardinality ≤ |L|. The assumption implies that there is a subset C of A such that tp_{b}(B) = tp_{b}(C) and tp(bB) = tp(cC).

Fix an L–formula φ(x, α) and let p denote tp(b/A). Write ψ_{p,φ} as ψ(x, b′) for an L–formula ψ(x, β). Let c′ be the tuple in C which corresponds to b′. Then ψ(x, c′) belongs to tp(c/A), has the same relative φ–rank as p and multiplicity 1. It follows that R_{φ}^{A}(tp(c/A)) ≤ R_{φ}^{A}(tp(b/A)) and, by symmetry,

R_{φ}^{A}(tp(c/A)) = R_{φ}^{A}(tp(b/A)).

Whence tp(c/A) is the only extension of tp(c/C) to A with the same φ–ranks as tp(c/C).

If A_{ind} were saturated we could use the reasoning of the proof of Lemma 3.3 to see that tp_{b}(bB) = tp_{b}(cC). But |L|^{+}–saturation of A_{ind} suffices: If B′ ⊂ A and C′ ⊂ A are two extensions of B and C which have the same bounded type then tp(bB′) = tp(cC′). Hence the system of all maps f : B′ ∪ {b} → C′ ∪ {c} where

• B′ and C′ are contained in A and at most of cardinality |L|,

• f maps B to C and preserves the respective enumerations,

• f is bounded on B′

• f(b) = c

is a back and forth system, which implies that all f are bounded. This implies tp_{b}(bB) = tp_{b}(cC). □

References

[1] J. Baldwin and M. Benedikt, Stability theory, Permutations of Indiscernibles, and Embedded Finite Models, to appear in Trans. AMS

[2] E. Bouscaren et B. Poizat, Des belles paires aux beaux uples, The Journal of Symbolic Logic 53 (1988), 434-442

[3] J.H. Evertse, The Subspace theorem of W.M.Schmidt in Diophantine equations and Abelian varieties, Springer Lecture Notes 1566 (1993), 31-50

[4] A. Pillay, The model-theoretic contents of Lang’s conjecture, in E. Bouscaren (ed.) Model Theory and Algebraic Geometry, Lectures Notes in Mathematics 1696 (1998), 101-106.

[5] B. Poizat, Paires de structures stables, The Journal of Symbolic Logic 48 (1983), 239-249.

[6] S. Shelah, Classification Theory, 2nd ed., North Holland P.C., Amsterdam, (1990).

[7] B. Zilber, Unpublished