TRANSFERING SATURATION, THE FINITE COVER PROPERTY, AND

STABILITY ^{∗}

John T. Baldwin^{†} Department of Mathematics University of Illinois at Chicago

Chicago, IL 60680

Rami Grossberg Department of Mathematics Carnegie Mellon University

Pittsburgh, PA 15213

Saharon Shelah^{‡} Institute of Mathematics

The Hebrew University of Jerusalem

Jerusalem, 91094 Israel

&

Department of Mathematics

Rutgers University New Brunswick, NJ 08902

May 29, 1998

Abstract

\underline{Saturation is (μ, κ)-transferable in T} if and only if there is an expansion T_{1} of T with |T_{1}| ≤ |T | + ℵ_{0} such that if M is a μ-saturated model of T_{1} and |M| ≥ κ then M|L(T) is κ-saturated.

Theorem A. The following are equivalent for a complete theory T. (1) T does not have the finite cover property.

(2) ∀λ ≥ |T |^{+}, saturation is (|T |^{+}, λ)-transferable in T.

(3) ∃λ > 2^{|T |} such that saturation is (|T |^{+}, λ)-transferable in T. Theorem B. Suppose that there exists a cardinal μ ≥ |T | such that 2^{μ} > μ^{+}. For a complete theory T, the following are equivalent:

(1) T is stable.

(2) ∀μ ≥ |T |, saturation is (μ^{+}, 2^{μ})-transferable in T.

(3) ∃μ ≥ |T |, saturation is (μ^{+}, μ^{++})-transferable in T.

1 Introduction

The finite cover property (f.c.p.) is in a peculiar position with respect to the stability hierarchy. Theories without the f.c.p. are stable; but f.c.p. is independent from ω-stability or superstability. We introduce a notion of transferability of saturation which rationalizes this situation somewhat by placing f.c.p. in a natural hierarchy of properties. For countable theories the hierarchy is ω-stable without f.c.p., (superstable) without f.c.p., not f.c.p., and stable. In Section 3 we identify the latter notions with increasingly weaker degrees of transferability without regard to the cardinality of the theory. For appropriate (μ, κ) each of these these classes of theories is characterized by (μ, κ)-transferability of saturation in following sense.

Definition 1.1 \underline{Saturation is (μ, κ)-transferable in T} if and only if there is an expansion T_{1} of T with |T_{1}| = |T | such that if M is a μ-saturated model of T_{1} and |M| ≥ κ, then M|L(T) is κ-saturated.

∗The authors thank the United States - Israel Binational Science foundation for supporting this research as well as the Mathematics department of Rutgers University where part of this research was carried out.

†Partially supported by NSF grant 9308768

‡This is item # 570 on Shelah’s list of publications.

The finite cover property was introduced by Keisler in [Ke] to produce unsaturated ultrapowers and one of his results and a slightly later set theoretic advance by Kunen yield (3) implies (1) of Theorem A immediately. The finite cover property was also studied extensively by Shelah in [Sh 10] and chapters II, VI and VII of [Sh c]; those techniques are used here.

Our notation generally follows [Sh c] with a few minor exceptions: |T | is the number of symbols in |L(T)| plus ℵ_{0}. We do not distinguish between finite sequences and elements, i.e. we write a ∈ A to represent that the elements of the finite sequence a are from the set A. References of the form IV x.y are to [Sh c].

Extending the notation we write saturation is (0, κ)-transferable in T if and only if there is an expansion T_{1} of T with |T_{1}| = |T | such that if M ⊧ T_{1} and |M| ≥ κ, M|L(T) is κ-saturated. In particular, taking |M| = κ, P C(T_{1}, T) is categorical in κ. Now, Theorems VI.5.4 and VIII.4.1 yield.

Fact 1.2 For a countable theory T, the following are equivalent.

(1) T does not have the finite cover property and is ω-stable.

(2) ∀λ > ℵ_{0}, saturation is (0, λ)-transferable in T.

(3) ∃λ > ℵ_{0} such that saturation is (0, λ)-transferable in T.

We thank the referee for the formulation of Theorem 2.3 which generalizes our earlier version and for correcting an oversight in another argument.

2 (κ(T), λ)-transferability and the f.c.p

There are several equivalent formulations of the finite cover property. The following, which looks like a strengthening of the compactness theorem, is most relevant here.

Definition 2.1 The first order theory T does not have the \underline{finite cover property} if and only if for every formula ϕ(x; y) there exists an integer n depending on ϕ such that for every A contained in a model of T and every subset p of {ϕ(x, a), ¬ϕ(x, a); a ∈ A} the following implication holds: if every q ⊆ p with cardinality less than n is consistent then p is consistent.

The main consequence of f.c.p. used here is the following easy fact.

Fact 2.2 (II.4.6) Let T be a complete first order theory without the f.c.p. If M ⊧ T is a saturated model (and A ⊆ M with |A| < |M|) at least k_{Δ} then there exists J ⊆ M a set of Δ-indiscernibles (over A) extending I of cardinality |M|.

The principal tool for establishing the transfer of saturation is Theorem III.3.10 which asserts that a model M of a stable theory is λ-saturated if M is F_{κ(T)}^{a}-saturated and for each set of indiscernibles I contained in M there is an equivalent set of indiscernibles J with |J| = λ. This is the key to the following result. The idea for guaranteeing F_{κ(T)}^{a}-saturation is taken from Proposition 1.6 of [Ca]; the referee suggested moving it from a less useful place in the argument to here.

Theorem 2.3 If T does not have the f.c.p. then for any λ > |T |, saturation is (κ(T), λ)-transferable.

Proof: Let T be a theory without the f.c.p.. By II.4.1, T is stable. Let λ ≥ |T |^{+} be given. We must find a T_{1} to witness (κ(T), λ)-transferability. Form L_{1} by adding to L an n + 2-ary function symbol F_{n} for each n and new k-ary function symbols f_{i}^{θ,E}, for i < m = m(θ, E), for each pair of formulas θ(z), E(x, y, z) with lg(z) = k such that for any M ⊧ T and a ∈ M, if M ⊧ θ(a) then E(x, y, a) is an equivalence relation with m classes. The theory T_{1} consists of T and the following axioms:

1. For each k-ary sequence z such that θ(z), the elements f_{i}^{θ,E}(z), i < m provide a complete set of representatives for E(x, y, z).

2. For each x and n-ary sequence z, the function F_{n}(x, z, ·) is injective.

3. For every finite Δ ⊆ L(T) and n-ary sequence z, let k_{Δ} be the integer from Fact 2.2. If I is a finite set of Δ-indiscernibles over zof cardinality at least k_{Δ} then there exists an x_{I} such that

(a) the range of F_{n}(x_{I}, z, ·) contains I,

(b) the range of F_{n}(x_{I}, z, ·) is a set of Δ-indiscernibles over z and

It should be clear that the above axioms can be formulated in first order logic in the language L_{1}.

Claim 2.4 The theory T_{1} is consistent.

Proof: To see that T_{1} is consistent, consider a saturated model N of T. It is easy to choose Skolem functions f_{i}^{θ,E}(z) to give sets of representatives for the finite equivalence relations. Fix a 1 − 1 correspondence between finite sets of Δ-indiscernibles I with |I| ≥ k_{Δ} and elements x_{I} of N. By Fact 2.2, each sufficiently large finite sequence of Δ-indiscernibles I in N extends to one with |N| elements. Fix a 1 − 1 correspondence between the universe of N and this sequence. Interpret F_{n}(x_{I}, z, x) as this correspondence. Thus, we expand M to a model of T_{1}. _{2.4}

Now suppose that N^{∗} ⊧ T_{1} is a κ(T)-saturated model of cardinality at least λ. Let N be the reduct of N^{∗} to L(T). We will show N is F_{κ(T)}^{a}- saturated and for each set of indiscernibles I contained in N there is an equivalent set of indiscernibles J with |J| = λ.

For the first, for any q = stp(d/C) with |C| < κ(T), note that q is equivalent to the L_{1}-type over C consisting of the formulas E(x, f_{i}^{θ,E}(c)) for E a finite equivalence relation defined over the sequence c ∈ C and E(d, f_{i}^{θ,E}(c)).

Now let I = {b_{n} : n < ω} be an infinite set of indiscernibles in N. Let p^{∗} = Av(I, N) and, since N is F_{κ(T)}^{a}-saturated, choose C with |C| < κ(T) such that p^{∗}|C is stationary and p^{∗} does not fork over C. Now we show there is a sequence J of indiscernibles based on p^{∗}|C with |J| = |N|. Let q_{1}(x) be a type over C that contains for all m < ω and all subsets c of C with |c| = m, first, the collection of formulas (∀y_{1}) … (∀y_{n})ϕ(F_{m}(x, c, y_{1}), … F_{m}(x, c, y_{n})) where N ⊧ ϕ(b_{0}, … b_{n−1}) for arbitrary ϕ defined over c and with n < ω and secondly, the assertion that F_{m}(x, c, ·) is injective.

To show q_{1}(x) is consistent, fix a finite q^{∗} ⊆ q_{1}(x) and let Δ be a finite subset of L(T) such that all the L(T)-formulas from q^{∗} appear in Δ. Let k < ω be sufficiently large so that all the elements of C appearing in q^{∗} are among {c_{0}, …, c_{k−1}} and k ≥ k_{Δ}. By the second and third conditions defining T_{1}, there is a sequence of size |N| of Δ-indiscernibles contained in N extending b_{1}, … b_{n−1}. Thus, there exists an element a ∈ N^{∗} and interpretations of the F_{ℓ} with ℓ < k which satisfy q^{∗}. Finally, a realization of q_{1} is a type over a set of cardinality less than κ(T), and a realization of q_{1} guarantees the existence of a set of |N|-indiscernibles equivalent to I as required. _{2.3}

3 The transferability hierarchy

Theorem A. The following are equivalent for a complete theory T.

(1) T does not have the finite cover property.

(2) ∀λ ≥ |T |^{+}, saturation is (|T |^{+}, λ)-transferable in T.

(3) ∃λ > 2^{|T |} such that saturation is (|T |^{+}, λ)-transferable in T.

It is obvious that (2) implies (3). Since a |T |^{+}-saturated model is κ(T)-saturated, (1) implies (2) follows from Theorem 2.3. Now we show (3) implies (1).

Lemma 3.1 If T has the f.c.p. and 2^{|T |} < λ then saturation is not (|T |^{+}, λ)- transferable in T.

Proof: Let T_{1} be any extension of T and N_{0} an arbitrary model of T_{1} with cardinality at least λ. By Kunen’s theorem (see [Ku], or Theorem 6.1.4 in [CK]) there exists an ℵ_{1}-incomplete |T |^{+}-good ultrafilter D on |T |.

Denote by N_{1} the ultrapower N_{0}^{|T |}/D. By [Ke] 1.4 and 4.1 or VI.5.3, N_{1} is |T |^{+}-saturated but not (2^{|T |})^{+}-saturated. _{3.1}

The proof of Theorem A yields somewhat more than is necessary. The theory T_{1} which is found in the implication (1) implies (2) does not depend on λ and contains only a single additional function symbol. We could obtain a stronger result than (3) implies (1) with the same proof by demanding in a modified (3) that the model witnessing (|T |^{+}, λ)-transferability have cardinality λ = λ^{|T |} > 2^{|T |}.

Theorem B. Suppose that there exists a cardinal μ ≥ |T | such that 2^{μ} > μ^{+}. For a complete theory T, the following are equivalent:

(1) T is stable.

(2) ∀μ ≥ |T |, saturation is (μ^{+}, 2^{μ})-transferable in T.

(3) ∃μ ≥ |T |, saturation is (μ^{+}, μ^{++})-transferable in T.

The condition μ^{+} < 2^{μ} is used only for (2) implies (3) (which is obvious with that hypothesis). We now prove in ZFC that (1) implies (2), and that (3) implies (1). This shows in ZFC that stability is bracketed between two transferability conditions. This is carried out in the following two lemmas.

Lemma 3.2 If T is stable and μ ≥ |T |, saturation is (μ^{+}, 2^{μ})-transferable in T.

Proof: We must find an expansion T_{1} of T such that if M is a μ^{+}-saturated model of T_{1} and |M| ≥ 2^{μ}, M|L is 2^{μ}-saturated. Form L_{1} by adding one additional binary predicate E(x, y) and add axioms asserting that E codes all finite sets. (I.e., for every set of k elements x_{i} there is a unique y such that E(z, y) if and only if z is one of the x_{i}.) For any model M_{1} of T_{1} and any element b of M_{1}, let [b] := {a ∈ M_{1} : M_{1} ⊧ E[a, b]}.

Now let M_{1} be a μ^{+}-saturated model of T_{1} and M the reduct of M_{1} to L. Suppose A ⊆ M has cardinality less than 2^{μ} and p ∈ S^{1}(A). We must show p is realized in M. By the definition of κ(T) there exists B ⊆ A of cardinality less than κ(T) such that p does not fork over B. Since M_{1} is |T |^{+}- saturated, we may take p|B to be stationary. Let p̂ ∈ S(M) be an extension of p that does not fork over B. Since μ^{+} > |T | ≥ κ(T), by μ^{+}-saturation of M there exists I := {a_{n} : n < ω} ⊆ M such that a_{n} ⊧ p̂|(B ∪ {a_{k} : k < n}). Since the sequence is chosen over a stationary type, I is a set of indiscernibles.

We now define an L_{1}-type q over I so that if b realizes q, [b] ⋃ I is a set of indiscernibles over the empty set. Let q(x) be:

{∃y_{0} ⋯ ∃y_{n−1}[ ⋀_{i<j<n} y_{i} ≠ y_{j} ∧ ⋀_{i<n} E(y_{i}, x)|n < ω} ∪

{∀y_{0} ⋯ ∀y_{n−1}[[ ⋀_{i<j<n} y_{i} ≠ y_{j} ∧ ⋀_{i<n} E(y_{i}, x) →

{y_{0}, …, y_{n−1}, a_{0}, …, a_{n−1}} is a set of ϕ-indiscernibles | n < ω, ϕ ∈ L(T)}.

Since the relation E codes finite sets, and I is a set of indiscernibles q is consistent. By the ℵ_{1}-saturation of M_{1} there exists b ∈ M realizing the type q. If [b] has 2^{μ} elements we are finished since for each formula ϕ(x, \overline{y}) and each \overline{a} ∈ A with ϕ(x, \overline{a}) ∈ p, only finitely many elements of [b] satisfy ¬ϕ(x, \overline{a}). To show [b] is big enough, using the μ^{+}-saturation of M, we define inductively for η ∈ 2^{≤μ} elements c_{η} ∈ M such that

1. c_{∅} = b

2. For any η, [c_{η⌢0}] and [c_{η⌢1}] are disjoint subsets of [c_{η}].

3. If lg(η) is a limit ordinal α, [c_{η}] ⊆ ∩_{i<α}[c_{η|i}]

Now for s ∈ 2^{μ}, the c_{s} witness that |[b]| = 2^{μ}. _{3.2}.

Lemma 3.3 If μ ≥ |T | and saturation is (μ^{+}, μ^{++})-transferable in T then T is stable.

Proof: For the sake of contradiction suppose T is an unstable theory and that there is a T_{1} ⊇ T such that if M is a μ^{+}-saturated model of T_{1} with cardinality at least μ^{++}, M|L(T) is μ^{++}-saturated. Fix M_{0} ⊧ T_{1} with cardinality at least μ^{++}. Let D be a μ-regular ultrafilter on I = μ. Construct an ultralimit sequence ⟨M_{α} : α < μ^{+}⟩ as in VI.6 with M_{α+1} = M_{α}^{I}/D and taking unions at limits. By VI.6.1 M_{μ^{+}} is μ^{+}-saturated. But by VI.6.2, since T is unstable, M_{μ^{+}} is not μ^{++}-saturated. _{3.3}

Theorem 3.4 The following are equivalent.

1. T is superstable without the f.c.p.

2. For every λ > |T |, saturation is (ℵ_{0}, λ)-transferable in T.

3. For some λ > 2^{|T |}, saturation is (ℵ_{0}, λ)-transferable in T.

Proof: Theorem 2.3 yields (1) implies (2). (2) implies (3) is obvious. From (3) by Theorem A we deduce that T does not have the f.c.p. (using λ > 2^{|T |}) and by Theorem B, (3) implies T is stable. Suppose for contradiction there are a stable but not superstable T and a T_{1} which witnesses (ℵ_{0}, λ)- transferability in T. Apply VIII.3.5 to PC(T_{2}, T) taking κ = ℵ_{0}, μ = (2^{|T |})^{+} and λ ≥ μ. There are 2^{μ} models of T_{2} with cardinality λ, which are ℵ_{0}- saturated, whose reducts to L(T) are nonisomorphic. So some are not λsaturated. _{3.4}.

In view of Theorem 2.3 and as pointed out by the referee, the result of Theorem 3.4 holds whenever κ(T) satisfies the set-theoretic conditions of Theorem VIII.3.5. For example, under the GCH this holds if κ(T) is the successor of a singular cardinal.

The methods and concerns of this paper are similar to those in the recent paper of E. Casanovas [Ca]. He defines a model to be expandable if every consistent expansion of Th(M) with at most |M| additional symbols can be realized as an expansion of M. His results are orthogonal to those here. He shows for countable stable T that T has an expandable model which is not saturated of cardinality greater than the continuum if and only if T is not superstable or T has the finite cover property.

By varying the parameters in (μ, κ)-transferability of saturation we have characterized four classes of theories: ω-stable without f.c.p., superstable without f.c.p., not f.c.p., and stable. For countable T and uncountable λ, they correspond respectively to: (0, λ)-transferability, (ℵ_{0}, λ)-transferability, (ℵ_{1}, λ)-transferability, (ℵ_{1}, 2^{ℵ_{0}})-transferability.

References

[Ca] Enrique Casanovas, Compactly expandable models and stability, Journal of Symbolic Logic 60 , 1995, pages 673–683.

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

[Ke] H. Jerome Keisler, Ultraproducts which are not saturated, Journal of Symbolic Logic 32 , 1967, pages 23–46.

[Ku] Kenneth Kunen, Ultrafilters and independent sets, Trans. Amer. Math. Soc., 172, 1972, pages 199–206.

[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, pages 271–362, 1971. — MR: 47:6475, (02H05)

[Sh c] Saharon Shelah, Classification Theory and the Number of Nonisomorphic Models, Rev. Ed., North-Holland, 1990, Amsterdam.