The Universality Spectrum of Stable Unsuperstable Theories By Menachem Kojman and Saharon Shelah† Mathematics Department, The Hebrew University of Jerusalem, Jerusalem ABSTRACT It is shown that if T is stable unsuperstable, and ℵ_{1} < λ = cfλ < 2^{ℵ_{0}}, or 2^{ℵ_{0}} < μ^{+} <

λ = cfλ < μ^{ℵ_{0}} then T has no universal model in cardinality λ, and if e.g. ℵ_{ω} < 2^{ℵ_{0}} then T has no universal model in ℵ_{ω}. These results are generalized to κ = cfκ < κ(T) in the place of ℵ_{o}. Also: if there is a universal model in λ > |T |, T stable and κ < κ(T) then there is a universal tree of height κ + 1 in cardinality λ.

§1. Introduction

We handle the universal spectrum of stable-unsuperstable first order theories. This continues [KjSh 409] and adds information the picture started up in [Sh 100]. The general subject addressed here is the universal model problem, which although natural and old, was not treated very extensively in the past. For background, motivation and history of the subject see the introduction to [KjSh 409], a paper in which unstable theories with the strict order property are handled (e.g. the class of linear orders).

When looking at a class K of structures together with a class of allowed embeddings — say all models of some first order theory (T) with elementary embeddings — we get a partial order: A ≤ B if there is a mapping of A into B in the class of allowed mappings.

† Partially supported by the Binational Science Foundation. Publication No. 447 The universal model problem can be phrased, in this context, as a question about this partial order: is there in {M ∈ K : ||M|| ≤ λ} a “greatest” element — which we call “universal” — namely one such that all other elements M ∈ K, ||M|| ≤ λ are smaller than or equal to it. This question can be elaborated: what is the cofinality, i.e. the minimal cardinality of a subcollection of elements such that every element is smaller than or equal to one of the elements in this subcollection? Can a universal object be found outside our collection? (for instance, is there a model of T of cardinality μ > λ such that every model of T of cardinality λ is elementarily embeddable into it). How does the existence, or nonexistence, of universal objects in one collection of structure influence the existence or non existence of universal objects in related collections?

In this paper we prove that if T is stable unsuperstable, and μ^{+} < λ = cfλ < μ^{ℵ_{0}} then T has no model of cardinality λ into which all models of T of the same cardinality are elementarily embeddable, not even a family of models ⟨M_{i} : i < λ′⟩, λ′ < μ^{ℵ_{0}}, each of cardinality λ such that every model of T of cardinality λ is elementarily embedded into some model in the family. It follows from the theory of covering numbers that certain singular cardinals are also not in the universality spectrum of stable unsuperstable theories.

Also, it is shown that a certain theory (the “canonical” stable unsuperstable theory) is “minimal” with respect to the existence of universal models, namely that whenever some stable unsuperstable theory T has a universal model in cardinality λ, also this theory has one.

We mention here without proof that GCH implies that all first order theories have universal models in all uncountable cardinals (above the cardinality of the theory), and that the question whether ℵ_{1} is in the universality spectrum of a countable, stable but not superstable theory is independent of ZF C + 2^{ℵ_{0}} = ℵ_{2} (see [Sh 100] §2). At this point it is interesting to note that it is consistent that there is a universal graph in ℵ_{2} < 2^{ℵ_{0}} (see [Sh 175a]), but it is not consistent to have a universal model for some countable, stable unsuperstable T. So in this respect, stable unsuperstable theories are not “≤” all unstable theories.

In subsequent papers, universality spectrums of some classes of infinite abelian groups, and complementary consistency results to the negative results known so far will be dealt with. (Note: if T is countable first order, stable unsuperstable theory, and μ = Σ_{n}μ_{n}^{ℵ_{0}}, then there is a universal model for T in μ; if, say, _{ω}^{+} < μ < _{ω+1} there isn’t; and we do not settle here the case μ = _{ω}^{+}.)

We assume some familiarity with the definitions of stability and superstability, as well as with fundamentals of forking theory (to be found in e.g. [ [Sh-c],III).

Lastly, those reader who speculate that _{⌣} · · * is some inexplicable whim of the laser printer are wrong. Smileys indicate ends of proofs, and replace the old and square boxes.

§2. Preliminaries and Setup

Having fixed attention on a given T, we work in some “monster model” C, which is a * We thank Martin Goldstern for the smiley TEXnology and for ⋃. big saturated model, of which all the models we are interested in are elementary submodels of smaller cardinality. 2.1 Definition: for a complete first order theory T,

(0) A model M ⊧ T is ≺-universal in cardinality λ if ||M|| = λ and for every N ⊧ T such that ||N|| = λ there is an elementary embedding h : N → M. It is <-universal, if we omit “elementary” from the definition.

(1) Univ(T, ≺) = {λ : λ is a cardinal and T has a universal model in λ} is the universality spectrum of T.

(2) Univ_{p}(T, ≺) is the family of pairs (λ, μ) such that there is a family of μ models of T each of cardianlity λ, such that any model of T of cardianlity λ can be elelmentarily embeded into one of them.

(3) Univ_{t}(T, ≺) is the family of triples (λ, κ, μ) such that there is is a family of μ models of T each of cardianlity ≤ κ and any model of T of cardianlity λ can be elemntarily embeded into one of them. In this paper “universal” means ≺-universal and Univ(T) means Univ(T, ≺) unless

otherwise stated. 2.2 Definition:

(0) A Theory T is stable in λ if for every model N and set A ⊆ N, |A| ≤ λ ⇒ |S(A)| ≤ λ. For equivalent definitions see [Sh-g ],II.2.13.

(1) κ(T), the cardinal of T is as defined in [Sh-c],III,§3. We recall from [Sh-c]III that for

a countable, complete first order T, T is stable unsuperstable iff κ(T) = ℵ_{1}.

(2) The notation a N ; ⋃ ; B A means “the type of a over the set A in the model N does not fork over the set B”. The notation a \begin{matrix}N \\ & ⋃ \\ B \end{matrix} A means “the type of a over the set A in the model N forks over the set B”. When the model N in which the relation of forking exists is clear from context, it is omitted. By small bold faced letters we shall denote finite sequences of elements from a model.

Following a widely spread abuse of notation we shall not write a ∈ |N|^{<ω}, but write a ∈ N, and even refer to a as “element”. This is perfectly all right with what is about to be done here, because we may add the finite sequences as elements into the model and work in T^{eq} (or C^{eq}), or replace a type of an n-tuple by a 1-type when necessary.

The forking facts which we shall need are summarized in the following quotation from [Sh-c] p.84:

2.3 Theorem:

(0) (finite character of forking) If a \begin{matrix} & ⋃ \\ B \end{matrix} A then there is some finite set A′ ⊆ A such that

a \begin{matrix} & ⋃ \\ B \end{matrix} A′. Also a \begin{matrix} & ⋃ \\ B \end{matrix} A iff a \begin{matrix} & ⋃ \\ B \end{matrix} A ∪ B.

(1) (symmetry) a ⋃ ; A A ∪ b iff b ⋃ ; A A ∪ a.

(2) (transitivity) if A ⊆ B ⊆ C and a ⋃ ; B C and a ⋃ ; A B then a ⋃ ; A C

(3) Let B ⊆ A , then: b ⋃ ; B ∪ A A ∪ a and a ⋃ ; B A iff a b ⋃ ; B A

(4) When M is a model, the type p does not fork over |M| iff p is finitely satisfiable in

M.

(5) if A ⊆ B ⊆ C, p ∈ S(B) does not fork over A, then there is some q ∈ S(C),p ⊆ q and q does not fork over A.

(6) ([Sh-c] p.113) If p ∈ S(|M|) is definable over A where A ⊆ M then p does not fork over A. We need a few facts about sets of indiscernibles. We denote sets of indiscernibles by

I and J. We say that tp(I) = tp(J) if for every n, formula φ and elements a_{1}, ⋯, a_{n} ∈ I, b_{1}, ⋯, b_{n} ∈ J, tp(a_{1}, ⋯, a_{n}, ∅) = tp(b_{1}, ⋯, b_{n}, ∅). 2.4 Theorem:

(1) ([Sh-c],III,4.13, p.77) If T is stablle, φ(\overline{x}, \overline{y}) a formula, then there is some natural number n(φ) such that for every set of indiscernibles I and parameters c, either |{a ∈ I :⊧ φ(a, c)}| < n(φ) or |{a ∈ I :⊧ ¬φ(a, c)}| < n(φ)

(2) ([Sh-c],III, 1.5 p.89) Let I be an infinite set of indicernibles. Av_{Δ}(I, A), the average of I over the set of formulas Δ and over the set of parameters A, is the set of all fomulas φ(\overline{x}, c) such that φ ∈ Δ, c ∈ A and ⊧ φ(a, c) for all but finitely many a ∈ I.

(3) ([Sh-c],III,, 3.5 p. 104) If J is an indiscernible set over A, B is any set, then there is I ⊆ J such that J − I is indiscernible over A ∪ B ∪ ⋃ I, and

(a) |I| ≤ κ(T) + |B|.

(b) If |B| < cf(κ(T)) then |I| < κ(T). (The interesting case is when |J| is large enough with relation to |B|.)

(4) ([Sh-c],III,4.17 p.117) If I, J are infinite indiscernible sets, and Av(I, ⋃ I) = Av(J, ⋃ I) and Av(J, ⋃ J) = Av(I, ⋃ J) then Av(I, C) = Av(J, C).

(5) ([Sh-c] p.112),III, 4.9 If Δ is finite and p ∈ S^{m}(|M|), then for every type q ∈ S^{m}(B) extending p which does not fork over M there is an infinite Δ-indiscernible set I ⊆ M such that q = Av_{Δ}(I, B).

(5) ([Sh-c],III,1.12 p.92) For every β and set A there is an indiscernible sequence I over A and based on A (= for every B Av(I, B) does not fork over A) such that b ∈ I.

The interested reader is welcome to inquire [Sh-c] for more details and/or results. We recall some combinatorics which we need:

2.5 Definition:

Suppose λ is a regular uncountable cardinal, and S ⊆ λ is stationary.

(1) A sequence \overline{C} = ⟨c_{δ} : δ ∈ S⟩ is a club guessing sequence on S if c_{δ} is a club (=closed unbounded subset) of δ for every δ ∈ S and for every club E of λ the set S_{E} = {δ ∈ S : c_{δ} ⊆ E} is stationary.

(2) For \overline{C} as in (1), id^{a}(\overline{C}) =^{def} \{A ⊆ S : there is a club E ⊆ λ such that δ ∈ A ∩ S ⇒ c_{δ} ⊈ E} is a λ-complete proper ideal.

(3) a sequence ⟨P_{δ} : δ ∈ S⟩, S ⊆ λ, is a weak club gueesing sequence if P_{δ} = ⟨c_{i}^{δ} : i < i(δ)⟩, i(δ) ≤ λ, for each i < i(δ), c_{i}^{δ} is a club of δ and for every club E ⊆ λ, the set S_{E} = {δ ∈ S : (∃i < i(δ))(c_{i}^{δ} ⊆ E)} is stationary. The existence of a weak club guessing sequence is clearly equivalent to the existence of a sequence ⟨c_{β} : β < λ⟩ such that c_{δ} ⊆ β and for every club E ⊆ λ the set {α < λ : (∃β)(sup c_{β} = α) & c_{β} ⊆ E} is stationary. We call such a sequence also a weak club guessing sequence.

(4) If \overline{P} = ⟨P_{δ} : δ ∈ S⟩ is a weak club guessing sequence, then id^{a}(\overline{P}) = \{A ⊆ S : (∃E)(E ⊆ λ is club such that (∀δ ∈ E ∩ S)(¬∃i < i(δ))(c_{i}^{δ} ⊆ E)} is a proper λcomplete ideal. _{⌣} · · _{2.5}

2.6 Fact:

(1) If λ = cfλ > ℵ_{1} then there are a stationary S ⊆ λ and a club guessing sequence \overline{C} = ⟨c_{δ} : δ ∈ S⟩ on S such that for every δ ∈ S the order type of c_{δ} is ω.

(2) If κ is regular and uncountable, κ^{+} < λ = cfλ, then there are sequences \overline{C} = ⟨c_{δ} : δ ∈ S⟩, S ⊆ λ stationary, and ⟨P_{α} : α ∈ λ⟩ such that otp c_{δ} = κ, sup c_{δ} = δ, \overline{C} is a club guessing sequence, |P_{α}| < λ and for every δ ∈ S and α ∈ nacc c_{δ}, c_{δ} ∩ α ∈ P_{α}.

(3) Suppose μ^{+} < λ = cfλ and cfμ ≤ μ. Then there is a weak club guessing sequence \overline{C} = ⟨c_{β} : β < λ⟩ such that for every β < λ the order type of c_{β} is μ and for every α < λ the set {c_{β} ∩ α} has cardinality smaller than λ.

Proof: See [Sh-g], [Sh 365] or the appendix to [KjSh 409] for a proof of (1) and see [Sh 420]§1 for the proofs of (2) and (3). _{⌣} · · _{2.6}

On covering numbers see [Sg-g]. We refer the reader to [KjSh 409],§4, for a detailed exposition of covering numbers of singular cardinals, in particular to Theorem 4.5 there. Here we quote 2.7 Definition: cov(λ, μ, θ, σ) is the minimal size of a family A ⊆ [λ]^{<μ} which satisfies that for all X ∈ [λ]^{<θ} there are less than σ members of A whose union covers X. 2.8 Theorem: If μ is not a fix point of the second order, i.e. |{λ < μ : λ = ℵ_{λ}}| = σ < μ, and σ + cfμ < κ < μ, then cov(μ, κ^{+}, κ^{+}, κ) = μ. _{⌣} · · _{2.8}

For example, for every ℵ_{n} it is true that cov(ℵ_{ω}, ℵ_{n+1}, ℵ_{n+1}, ℵ_{n}) = ℵ_{ω}.

§3. The Machinery

In this section T denotes a first order, countable, stable but unsuperstable theory. 3.1 Definition: Suppose that N ⊧ T, and that \overline{N} = ⟨N_{i} : i < λ⟩ is given, N_{i} ≺ N_{i+1} ≺ N, ||N_{i}|| < λ and N_{j} = ∪_{i<j}N_{j} for limit j. \overline{N} is called a representation of N.

Suppose c ⊆ λ is of limit order type and is enumerated (continuously and increasingly) by ⟨α_{i} : i < otp c⟩.

(0) for an element a ∈ N, Inv\overline{N}(a, c) =^{def} \{α_{i} : a \begin{matrix}N \\ & ⋃ \\ N_{α_{i}} \end{matrix} N_{α_{i+1}}\};

(1) Inv∗ ; \overline{N}(a, c) =^{def} \{i : a \begin{matrix}N \\ & ⋃ \\ N_{α_{i}} \end{matrix} N_{α_{i+1}}\}

(2) P (\overline{N}, c) =^{def} \{Inv\overline{N}(a, c) : a ∈ N\}

(3) P^{∗}(\overline{N}, c) =^{def} \{Inv∗ ; \overline{N}(a, c) : a ∈ N\} 3.2 Definition: Suppose that \overline{C} = ⟨c_{δ} : δ ∈ S⟩ is a club guessing sequence on some staitonary S ⊆ λ and that that \overline{N} is as in 3.1.

(4) INV^{a}(\overline{N}, \overline{C}) is the sequence ⟨P (\overline{N}, c_{δ}) : δ ∈ S⟩ modulo the ideal id^{a}(\overline{C}).

(4) Assuming that for all δ ∈ S, otp c_{δ} is some fixed δ(∗), INV^{b}(\overline{N}, \overline{C}) =^{def} \{Y ⊆ δ(∗) :

\{δ ∈ S : Y ∈ P^{∗}(\overline{N}, c_{δ})\} ∉ id^{a}(\overline{C})\}

(5) Under the assumptions of (4), INV_{(\overline{N},\overline{C})}^{c} =^{def} \{Y ⊆ δ(∗) : \{δ ∈ S : Y ∉ P^{∗}(\overline{N}, c_{δ})\} ∈ id^{a}(\overline{C})\}

3.3 Remark: We shall not use 3.2 much, but our results can be interpreted as saying that those invariants do not depend on the representation \overline{N} but just on the model N, and that we can prove non universality by just looking at one of these invariants. 3.4 Lemma: Suppose λ = cfλ > ℵ_{1}, N, M are models of T, ||N|| = ||M|| = λ with given representations \overline{N}, \overline{M}. If h : N → M is an elementary embedding, then there is some club E ⊆ λ such that for every a ∈ N and c ⊆ E, Inv\overline{N}(a, c) = Inv\overline{M}(h(a), c). Proof: Let E_{h} = {i < λ : ran(h N_{i}) ⊆ M_{i}}. Clearly E_{h} is a club of λ. Dnote by N_{i}^{∗} the set ran(h N_{i}). So for δ ∈ E_{h}, N_{i}^{∗} is the universe of an elementary submodel of M_{i}. Denote by N^{∗} the image of N under h. 3.5 Claim: The set E_{1} = {δ ∈ E_{h} : (∀a ∈ M_{δ})(a ⋃ ; N_{δ}(∗) N^{∗})} is a club. Proof: As T is countable, stable but unsuperstable, κ(T) = ℵ_{1}. Therefore for every a ∈ M, there is a countable set A_{a} ⊆ N^{∗} such that a ⋃ ; A_{a} N^{∗}. Let i(a) be the least i such that A_{a} ⊆ N_{i}^{∗}. For α ∈ E_{h} let j(α) be the least j ∈ E_{h} such that for all a ∈ [α]^{<ω}, i(a) ≤ j. E′ = {δ ∈ E_{h} : α < δ ⇒ j(α) < λ} is club. If δ ∈ E′ and a ∈ [δ]^{<ω}, then A_{a} ⊆ N_{δ}(∗). So as a ⋃ ; A_{a} N^{∗}, also a ⋃ ; N_{δ}(∗) N^{∗}. So E′ ⊆ E_{1}. E_{1} is closed, for if δ ∈ acc E_{1} and a ∈ M_{δ}, then there is some α < δ such that sup a < α and α < i < δ such that i ∈ E_{1}. a ⋃ ; N_{i}^{∗} N^{∗},

therefore a ⋃ ; N_{δ}(∗) N^{∗}. _{⌣} · · _{3.5}

Let ⟨α_{i} : i < λ⟩ be its increasing enumeration of E_{1}. We show that for every a ∈ N

and i < λ, a \begin{matrix}N \\ & ⋃ \\ N_{α_{i}} \end{matrix} N_{α_{i+1}} ⇔ h(a) \begin{matrix}M \\ & ⋃ \\ M_{α_{i}} \end{matrix} M_{α_{i+1}}.

As E ⊆ E_{1}, for every α_{i} and b ∈ M_{δ},

b M ; ⋃ ; N_{α_{i}}^{∗} N^{∗}

This can be written as

⋆_{1}  M_{α_{i}} M ; ⋃ ; N_{α_{i}}^{∗} N^{∗}

By monotonicity, for a given a ∈ N,

⋆_{2}  M_{α_{i}} M ; ⋃ ; N_{α_{i}}^{∗} h(a)

Symmetry of non-forking gives

⋆_{3}  h(a) M ; ⋃ ; N_{α_{i}}^{∗} M_{α_{i}}

Suppose now, first, that

a N ; ⋃ ; N_{α_{i}} N_{α_{i+1}}.

As h is an elementary embedding,

⋆_{4}  h(a) M ; ⋃ ; N_{α_{i}}^{∗} N_{α_{i+1}}^{∗}

By ⋆_{3}, h(a) ⋃ ; N_{α_{i+1}}^{∗} M_{α_{i+1}} (we omit M, in which we work from now on). By ⋆_{4}, and the transitivity of non forking, h(a) ⋃ ; N_{α_{i}}^{∗} N_{α_{i+1}}. By monotonicity, h(a) ⋃ ; M_{α_{i}} M_{α_{i+1}}.

For the other direction, suppose that h(a) ⋃ ; M_{α_{i}} M_{α_{i+1}}. By monotonicity, h(a) ⋃ ; M_{α_{i}} N_{α_{i+1}}^{∗}. By ⋆_{3} and the transitivity of non forking, h(a) ⋃ ; N_{α_{i}}^{∗} N_{α_{i+1}^{∗}}, which is what we want. _{⌣} · · _{3.4} 3.6 Corollary: Suppose \overline{N} and \overline{M} are as above and that h : N → M is an elementary embedding. Let E be the club given by the previous lemma. If c ⊆ E then

(1) for every a ∈ N, Inv\overline{N}(a, c) = Inv\overline{M}(h(a), c);

(2) P (\overline{N}, c) ⊆ P (\overline{M}, c).

We will need a slight generalization of 3.4: 3.7 Lemma: Suppose N ⊧ T is with universe λ, \overline{N} is a representation of N. Suppose L ≺ M are models of T, L is of cardinality λ, its universe is B and \overline{L} is a representation. If h : N → M is an elementary embedding, then there is some club E ⊆ λ such that for every c ⊆ E and a ∈ h^{−1}(B), Inv\overline{N}(a, c) = Inv\overline{L}(h(a), c). Proof: Denote by N_{i}^{∗}, N^{∗} the images of N_{i}, N under h respectively. Let A_{i} = |N_{i}^{∗}| ∩ B. Let A = ∪A_{i}. We prove 3.8 Claim: There is a club E_{1} ⊆ λ such that i ∈ E implies N_{i}^{∗} ⋃ ; A_{i} A and L_{i} ⋃ ; A_{i} A Proof: Same as in 3.5. _{⌣} · · _{3.8}

For the rest of the proof, show, precisely as in 3.5, that

h(a) ⋃ ; B_{α_{i}} B_{α_{i+1}} ⇔ h(a) ⋃ ; A_{α_{i}} A_{α_{i+1}} ⇔ h(a) ⋃ ; N_{α_{i}}^{∗} N_{α_{i+1}}^{∗}

When ⟨α_{i} : i < otp c⟩ is the enumeration of c. _{⌣} · · _{3.7} 3.9 Lemma: (the construction Lemma) Let λ be uncountable and regular. Suppose that \overline{C} is a club guessing sequence on some stationary S ⊆ λ and for every δ ∈ S, otp c_{δ} = μ for some fixed μ with cfμ = ℵ_{0}. Suppose Y ⊆ μ is a given set of order type ω. Then there is a model M ⊧ T of cardinality λ and a representation \overline{M} such that for every δ ∈ S, Y ∈ P^{∗}(\overline{N}, c_{δ}). Proof: We work in the monster model, C. By κ(T) > ℵ_{0}, there is some b and M with the property that for every finite set A, b \begin{matrix}C \\ & ⋃ \\ A \end{matrix} M. Pick by induction on n a finite sequence a_{n} such that

(i) a_{n} is a proper initial segment of a_{i+1};

(ii) b \begin{matrix} & ⋃ \\ a_{n} \end{matrix} a_{n+1}.

Let a_{0} = ⟨⟩. The induction step: as b \begin{matrix} & ⋃ \\ a_{n} \end{matrix} M, by the choice of b, and the finite character of forking, there is some finice c ∈ M such that b \begin{matrix} & ⋃ \\ a_{n} \end{matrix} c. Let a_{n+1} = a_{n} c. By monotonicity,

b \begin{matrix} & ⋃ \\ a_{n} \end{matrix} a_{n+1}.

Now, we know that b ⋃ ; ∪_{n}a_{n} ∪_{n}a_{n}. By the existence of non-forking extensions, we may assume that b ⋃ ; ∪_{n}a_{n} M.

We construct now by induction on i < λ a continuous increasing chain of models with the following properties:

(1) α_{0} = ω and α_{i+1} = α_{i} + |α_{i}|; if i is limit, α_{i} = sup_{j<i} α_{j}.

(2) The universe of N_{i} is α_{i}. N_{i} ⊧ T and N_{i} ≺ N_{i+1}. If i is limit, \overline{N}_{i} is the representation N_{i} = ⋃_{j<i} N_{j}.

(3) For every η ∈ ^{<ω}i, strictly increasing, a_{η} ∈ N_{i}. tp(a_{η 0} a_{η 1} ⋯ a_{η lg η}) = tp(a_{0} a_{1} ⋯ a_{lg η});

(4) If η = ν ⟨i⟩, then a_{η} N_{i+1} ; ⋃ ; a_{ν} N_{i}.

(5) If i = δ ∈ S satisfies that for every j < δ, α_{j} < δ, then there is some element b ∈ N_{δ+1}

such that \{α_{i} ∈ c_{δ} : b \begin{matrix}N_{δ+1} \\ & ⋃ \\ N_{α_{i}} \end{matrix} N_{α_{i+1}}\} = Y.

At the induction stage, when given ν ∈ ^{<ω}i and increasing, denoting by η the sequence ν i, we should say who a_{η} is. There is an elementary mapping h such that for every k < lg η, h(a_{k}) = a_{ν k}. Therefore h[tp(a_{lg η}, ∪_{l<lg η})] is a complete type over ⋃_{l<lg η} a_{η l}. By the existence of non forking completion of a partial non forking type, there is some type p over N_{i} which does not fork over ⋃_{l<lg η} a_{η l}. Let a_{η} realize p in N_{i+1}.

In case i = δ ∈ S_{0}^{λ} is as in (5), we should also take care of (5).

Let Y (δ) = ⟨α_{i(n)}^{d} : i ∈ Y ⟩. Let η = ⟨α_{i(n)}^{δ} : n ∈ ω⟩, and let h be an elementary mapping such that h(a_{l}) = a_{η l}. Then in N_{δ+1} we add an element b_{δ} which realizes h(tp(b, ∪_{l<ω}a_{l})) and b_{δ} N_{δ+1} ; ⋃ ; ∪_{l<ω}a_{η l} N_{δ} (due the existence of non forking extentions of types). We have to show

3.10 Lemma: \{α_{i} : b \begin{matrix}N_{δ+1} \\ & ⋃ \\ N_{α_{i}} \end{matrix} N_{α_{i+1}}\} = Y (δ).

We first need 3.11 Lemma: If η^{δ}(k) = α_{m}, then ∪_{l<ω}a_{η l} ⋃ ; a_{η k} N_{α_{m}}.

Proof: By induction on r, k ≤ r < ω, we see that ∪_{l≤r}a_{η l} ⋃ ; a_{η} k N_{α_{m}}.

r = k: ∪_{l≤k}a_{l} ⋃ ; a_{η k} N_{α_{m}} is trivial, as ∪_{l≤k}a_{η l} = a_{η k}.

r + 1: By the induction hypothesis,

(a)  ∪_{l≤r}a_{η l} ⋃ ; a_{η^{d} k} N_{α_{m}}

By the construction,

(b)  a_{η (r+1)} ⋃ ; a_{η r} N_{η(r)}

Monotonicity gives

(c)  a_{η (r+1)} ⋃ ; a_{η} (r) N_{α_{m}}

(a) and (c) give

a_{η (r+1)} ⋃ ; a_{η k} N_{α_{m}}

By the finite character of non forking Lemma 3.11 is proved. _{⌣} · · _{3.11} Suppose now, first, that α_{i} ∉ Y (δ). Let η(k − 1) < α_{i} < η(k). We know that

b ⋃ ; ∪_{l<ω}a_{η} l N_{δ}. So by monotonicity b ⋃ ; ∪_{l<ω}a_{η} l N_{α_{i+1}}. By 3.11, ∪_{l<ω}a_{η} l ⋃ ; a_{η (k)} N_{η(k)}. By

monotonicity and the fact that a_{η k} ∈ N_{α_{i}} we get ∪_{l<ω}a_{η l} ⋃ ; N_{α_{i}} N_{α_{i+1}}. By transitivity of non forking, b_{δ} ⋃ ; N_{α_{i}} N_{α_{i+1}}, namely α_{i} ∉ Inv_{\overline{N}_{δ+1}}(b_{δ}, c_{δ}).

For the other direction: suppose that α_{i} ∈ Y (δ) and that α_{i} = η(k). We know that b \begin{matrix} & ⋃ \\ a_{η} k \end{matrix} a_{η} (k + 1). Therefore by monotonicity, b \begin{matrix} & ⋃ \\ a_{η k} \end{matrix} N_{α_{m+1}}. By 3.11, as in the previous case, b ⋃ ; a_{η} k N_{α_{i}}. Suppose to the contrary that b ⋃ ; N_{α_{i}} N_{α_{i+1}}. Then by transitivity we get

b ⋃ ; a_{η k} N_{α_{i+1}} — a contradiction. _{⌣} · · _{3.10,3.9}

We will need also

3.12 Lemma: (the second construction Lemma)

Suppose λ is uncountable regular, and \overline{C} = ⟨c_{β} : β < λ⟩ is a weak club guessing sequence, such that for every β < λ the order type of c_{β} is some fixed μ with cfμ = ℵ_{0}. Suppose that Y (∗) ⊆ μ is given and of order type ω_{0}. There is some model M of T with universe λ and representation \overline{M} such that Y (∗) ∈ P^{∗}(\overline{M}, c_{β}) for every β < λ.

Proof: The proof is essentially the same as this of 3.9. The only difference is in the construction: we add the witness not in stage δ + 1 but in stage β + 1, where sup c_{β} = δ.

⌣ · · _{3.12}

3.13 Lemma:(the third construction lemma) Suppose T is a stable first order theory, cfλ = λ ≥ |T |, cfκ = κ < κ(T) and \overline{C}, \overline{P} are as in 2.6 (2). Suppose Y (∗) ⊆ κ is given. Then there is a model M ⊧ T of cardinality λ and representation \overline{M} such that fore every δ ∈ S, Y (∗) ∈ P^{∗}(\overline{M}, c_{δ}).

Proof: We work in a monster model C and construct a sequence ⟨a_{α} : α < κ⟩ and an element b such that a_{α} is an infinite sequence, increasing with α, namely a_{α} is is a proper initial segment of a_{β} whenever α < β and b \begin{matrix} & ⋃ \\ a_{α} \end{matrix} a_{α+1} for all α < κ. This is possible because κ < κ(T). Without loss of generality, b ⋃ ; ∪_{α}a_{α} ∪_{α}a_{α}. Let Y (∗)_{δ} ⊆ c_{δ} for δ ∈ S be the isomorphic image of Y (∗) under the enumeration of c_{δ}. We may assume, without loss of generality, that for every α ∈ nacc c_{δ} for δ ∈ S, Y (∗)_{δ} ∩ α ∈ P_{α}. Construct by induction on α < λ an elementary chain of models M_{α} with the following properties:

(1) : for every η ∈ P_{α}, η ∈ [α]^{<κ} there is a sequence \overline{a}_{η} such that a_{η}(β) ∈ N_{α} and tp(⋯ a_{η}(β) ⋯) = tp(⋯ a(β) ⋯).

(2) If α = δ ∈ S then there is an element a_{δ} ∈ N_{δ+1} such that Inv_{\overline{M}_{δ+1}}^{∗}(a_{δ}, c_{d}) = Y (∗). We let the reader verify that the analogs of 3.10 and 3.11 are true. _{⌣} · · _{3.13}

§4. The Main Results 4.1 Theorem: Suppose T is a complete, countable, stable but unsuperstable first order theory, and that ℵ_{1} < λ = cfλ < 2^{ℵ_{0}}. Then λ ∉ Univ(T). Furthermore, for every family {M_{i}}_{i∈I}, M_{i} ⊧ T, ||M_{i}|| = λ and |I| < 2^{ℵ_{0}} there is a model N ⊧ T, ||N|| = λ and N is not elementarily embeddable into M_{i} for all i ∈ I. Proof:

Clearly, it is enough to prove the “furthermore” part of the theorem. Suppose that \{M_{i}\}_{i∈I} is a family of less then 2^{ℵ_{0}} moels of T, each of cardinality λ. Let \overline{N}_{i} represent M_{i}. Use 2.6 part 1 to pick some club guessing sequence \overline{C} on S ⊆ λ with all c_{δ} of order type ω. Pick some set Y (∗) ⊆ ω such that Y (∗) ∉ ⋃_{i∈I,δ∈S} P^{∗}(\overline{N}_{i}, c_{δ}). This is possible, because the size of this union is smaller than 2^{ℵ_{0}}. Use the construction lemma to get a model M of size λ and a representation \overline{M} such that for every δ ∈ S, Y (∗) ∈ P^{∗}(\overline{M}, c_{δ}). Suppose to the contrary that for some i ∈ I, h : M → M_{i} is an elementary embedding. By 3.4, there is a club E ⊆ λ such that for every δ ∈ S such that c_{δ} ⊆ E, P (\overline{M}, c_{δ}) ⊆ P (\overline{M}_{i}, c_{δ}). Pick some δ_{0} ∈ S_{E}. So Y (∗) ∈ P^{∗}(\overline{M}, c_{δ_{0}}) ⊆ P^{∗}(\overline{M}_{i}, c_{δ_{0}}) – a contradiction to Y (∗) ∉ ⋃_{i∈I,δ∈S} P (\overline{M}_{i}, c_{δ}). _{⌣} · · _{4.1} 4.2 Theorem: Suppose 2^{ℵ_{0}} < λ = cfλ < λ^{ℵ_{0}} and there are no μ_{n} such that λ = (Σμ_{n}^{ℵ_{0}})^{+}. Then if T is a stable unsuperstable theory, |T | ≤ λ, then λ ∉ Univ(T). Furthermore, for every family {M_{i}}_{i∈I}, M_{i} ⊧ T, ||M_{i}|| = λ and |I| < λ^{ℵ_{0}} there is a model M ⊧ T, ||N|| = λ such that M is not elementarily embeddable into M_{i} for all i ∈ I. Proof: Again, the “furthermore” part is enough.

Let μ be the least cardinal such that μ^{ℵ_{0}} > λ. Since λ is uncountable and regular, λ^{ℵ_{0}} = ∪_{α<λ}α^{ℵ_{0}}. If for every cardinal κ < λ κ^{ℵ_{0}} = κ, we should have had λ^{ℵ_{0}} = λ. Therefore μ is stricly smaller than λ. If cfμ > ℵ_{0}, then μ^{ℵ_{0}} = ∪_{α<μ}α^{ℵ_{0}}. By the minimality of μ, for every α < μ, α^{ℵ_{0}} ≤ λ. This contradicts μ^{ℵ_{0}} > λ. We conclude that cfμ = ℵ_{0}. Lastly, if λ = μ^{+}, then, μ being of cofinality ω, there would be μ_{n} increasing to μ such that μ_{n}^{ℵ_{0}} < μ. This contradicts the assumptions on λ.

Use 2.6 part 3 to pick some weak club guessing sequence \overline{C} = ⟨c_{β} : β < λ⟩ with all c_{δ} of order type μ. Suppose to the contrary that {M_{i}}_{i∈I} is as stated above. By the assumption λ < μ^{ℵ_{0}}, we can find some Y (∗) ⊆ μ of order type ω such that Y (∗) ∉ ⋃_{i∈I,β<λ} P^{∗}(\overline{M}_{i}, c_{β}). By the construction lemma there is some model M and representation \overline{M} such that for every β < λ, Y (∗) ∈ P^{∗}(\overline{M}, c_{β}). Suppose to the contrary that for some i ∈ I there were an elementary embedding h : M → M_{i}. By 3.4 there is a club E ⊆ λ such that if c_{β} ⊆ E then P^{∗}(\overline{M}, c_{β}) ⊆ P^{∗}(\overline{M}_{i}, c_{β}). As \overline{C} is a weak club guessing sequnce there is such a c_{β}, and the contradiction to the choice of Y (∗) follows as before. _{⌣} · · _{4.2} 4.3 Theorem: Assume T is first order complete countable stable unsuperstable theory. Suppose μ is singular, and there is some σ < μ and κ < μ such that σ^{+} < κ = cfκ and σ^{ℵ_{0}} > cov(μ, κ^{+}, κ^{+}, κ), then there is no model of T in cardinality μ into which all models of T of cardinality κ are elementarily embeddable. In particular μ ∉ Univ(T). Proof: We may assume that cfσ = ℵ_{0}. Suppose to the contrary that M ⊧ T is of cardinality μ and that every N ⊧ T of cardinality κ is elementarily embeddable into it. Without loss of generality the universe of M is μ. Let θ =^{def} cov(μ, κ^{+}, κ^{+}, κ), and let ⟨B_{i} : i < θ⟩ demonstrate the definition of θ. Without loss of generality, each B_{i} is the universe of some M_{i} ≺ M of cardinality κ. By 2.6 part 3 pick some weak club guessing sequence \overline{C} with all c_{β} of order type σ. Pick a presentation \overline{M}_{i} for every M_{i}. Pick some Y (∗) ⊆ μ of order type ω such that Y (∗) ∉ ⋃_{i<θ,β<κ} P^{∗}(\overline{M}_{i}, c_{δ}), and use 3.9 to construct a model N ⊧ T of cardinality κ presetation \overline{N} such that for every β < κ, Y (∗) ∈ P^{∗}(\overline{M}, c_{β}). For every β < κ there is some element a_{β} such that Inv∗ ; \overline{N}(a_{β}, c_{β}) = Y (∗). Suppose that h : N → M is an elementary embedding. There is some set of indices X ⊆ θ such that |X| < κ and ranh ⊆ ∪_{i∈X}B_{i}. Since id^{a}(\overline{C}) is κ-complete, there is a set S′ ⊆ S, S′ ∉ id^{a}(\overline{C}), and a fixed i_{0} ∈ X such that (∀δ ∈ S′)(f(a_{δ}) ∈ B_{i_{0}}). Denote B_{i_{0}} by B for notational simplicity, and let L ≺ M be the model with universe B. Use 3.7 to get the usual contradiction. _{⌣} · · _{4.3}

§5. Generalizations

We wish now to generalise the discusstion of stable unsuperstable theories — namely those T with κ(T) = ℵ_{1} — to stable theories with κ(T) arbitrary. 5.1 Theorem: Suppose that T is stable and that λ ≥ |T | is an uncountable regular cardinal. Suppose that κ < κ(T), and κ^{+} < λ < 2^{κ}. Then λ ∉ Univ(T). Furthermore, for every family {M_{i}}_{i∈I} with |I| < 2^{κ} of models of T. each of cardinality λ, there is a model M ⊧ T of cardinality λ which is not elementarily embeddable into M_{i} for all i ∈ I. Proof: By 2.6 part 2 there is a club guessing sequence \overline{C} = ⟨c_{δ} : δ ∈ S⟩ on some stationary set S ⊆ λ and a sequence \overline{P} = ⟨P_{α} : α < λ⟩ such that the order type of each c_{δ} is κ, for every α ∈ S and α ∈ nacc c_{δ}, c_{α} ∩ α ∈ P_{α}, and each P_{α} has cardinality < λ. Pick a Y (∗) ⊆ κ such that Y (∗) ∉ ⋃_{δ∈S,i∈I} Inv^{∗}(\overline{M}_{i}, c_{δ}) and use the third construction lemma to find a model M ⊧ T of cardinality λ and a representation \overline{M} such that for every δ ∈ S, Y (∗) ∈ P^{∗}(\overline{M}, c_{δ}). Suppose to the contrary that there are i ∈ I and an elementary embedding h : M → M_{i}. By 3.4 and the fact that \overline{C} guesses clubs we obtain the usual contradiction. _{⌣} · · _{5.1} 5.2 Theorem: Assume κ = cf(κ) < κ(T), κ ≤ μ, μ^{+} < λ = cf(λ) < χ < μ^{κ}. Suppose also that T is first order complete and κ < κ(T). Then there is no model M of T of cardianlity χ universal for models of T of cardianlity λ. Proof: : similar. 5.3 Remark: This means that (λ, 1, χ) ∉ Univ_{t}(T, ≺).

§6. A theory with a maximal universality spectrum

In [KjSh 409], 5.5 it was shown that whenever λ ∈ Univ(T), T a theory having the strict order property, then there is a universal linear order in λ. We prove now an analogous theorem for stable unsuperstable theories. 6.1 Definition: for a cardinal κ,

(1) T_{κ} = T h(⟨^{κ}ω, E_{ζ}⟩_{ζ<κ}) where ηE_{ζ}ν ⇔ η ζ = ν ζ ( so T is a first order complete theory of cardianlity κ with κ(T) = κ^{+}, and in fact is the canonical example of such a theory)

(2) K_{κ} is the class of all trees of height κ + 1.

(3) K_{κ}^{+} is the class of all trees of height κ + 1 such that above every member thee is one of height κ

6.2 Fact: Univ(K_{κ}, <) ∩ (κ, ∞) = Univ(K_{κ}^{+}, <) ∩ (κ, ∞) = Univ(T_{κ}, ≺) ∩ (κ, ∞) = Univ(T_{κ}, ≤). Proof: Easy exercise. _{⌣} · · _{6.2} 6.3 Theorem: Suppose that T is stable, κ = cfκ < κ(T), κ ≤ λ and |T | < λ ∈ Univ(T). Then λ ∈ Univ(T_{κ}). 6.4 Remark: Similarly for Univ_{p}, Univ_{t} Proof: Without loss of generality, |T | = κ, for this may only increase Univ(T). So |T | < λ. Suppose that N ⊧ T is universal in power λ. We define a model M which we shall prove to be universal in λ for K_{κ}^{+}. By κ < κ(T) we can find an element a and an elementary chain ⟨M_{i} : i ≤ λ⟩ such that a \begin{matrix} & ⋃ \\ M_{i} \end{matrix} M_{i+1}. Let M_{κ}^{+} be such that M_{κ} ≺ M_{κ}^{+} and such that there is I ⊆ M_{κ}^{+}, |I| = λ and I an indiscrenible set based on M_{κ}, i.e. Av(I, C) extends the type of a over M_{κ} but does not fork over M_{κ}.

The universe of M will be B = {p ∈ S^{1}(N) : p = Av(J, N) for some J, J ⊆ N, |J| = λ, tp(J) = tp(I)}. 6.5 Lemma: |B| ≤ λ Proof: Suppose to the contrary that there are λ^{+} types ⟨p_{i} : i < λ^{+}⟩ and λ^{+} indiscernible sets J_{i} ⊆ N, |J_{i}| = λ such that p_{i} = Av(J_{i}, N). Pick a representation \overline{N} = ⟨N_{α} : α < λ⟩ of N as an elementary chain. For every i < λ there is some α_{i} < λ such that |J_{i} ∩ N_{α_{i}}| ≥ ℵ_{0}. Also, by 2.4 (3) it follows that there is some c_{i} ∈ J_{i} which realizes Av(J_{i}, N_{α_{i}}). By the pigeon hole principle there are some i < j < λ such that α_{i} = α_{j} and c_{i} = c_{j}. This contradics the fact that p_{i} ≠ p_{j} by 2.4 (4). _{⌣} · · _{6.5}

By 2.4,(5), for every p ∈ S(M_{κ}) and a finite set of formulas Δ there is an infinite set of indiscernibles I ⊆ M_{κ} such that p = Av_{Δ}(I, M_{κ}). By the stability of T and 2.4,(1), there is some n_{Δ} such that for every J ⊆ I which satisfies |J| > 2n_{Δ},

(∗)  (∀b ∈ M_{κ})(∀φ ∈ Δ)(φ(\overline{x}, b) ∈ p ⇔ |\{c ∈ J : ¬φ(c, b)\}| ≤ n_{Δ}

For every φ ∈ L there is a minimal α_{φ} such that there is a set J′_{φ} ⊆ M_{α_{φ}} of size > 2n_{{φ}} which satisfies (∗). Clearly, as J′_{φ} is finite, α_{φ} is a non limit ordinal. By 2.4 there is an infinite J_{φ} ⊆ M_{α_{φ}} with Av(J, M_{α_{φ}}) = p M_{α_{φ}}. By 2.4, p M_{α_{φ}} = Av(J, M_{α_{φ}}).

If sup{α_{φ} : φ ∈ L} = α^{∗} < κ, then p were definable over M_{α^{∗}}, and therefore, by 2.3, would not fork over M_{α^{∗}}, contrary to its choice. We can, therefore, find a sequence of formulas ⟨φ_{ζ} : ζ < κ⟩ with ⟨α_{φ_{ζ}} : ζ < κ⟩ strictly increasing. We shall assume, by re-enumeration, if necessary, that α_{φ_{ζ}} = ζ + 1.

We define now the relations on our universe B. For every pair p_{1}, p_{2} ∈ B and φ_{ζ} the following is an equivalence relation: p_{1}E^{ζ}p_{2} ⇔ p_{1} {φ_{ξ} : ξ ≤ ζ} = p_{2} {φ_{ξ} : ξ ≤ ζ}. Clearly, these are κ nested equivalence relations. We view the structure we defined as a tree of height κ + 1 with no short branches, i.e. is a member ofK_{χ}^{+}.

To show that M is universal, we will show that for every tree S of size λ with all branches of length κ + 1 we can find a model of T, N_{S} of the same cardinality, such that the elementary embedding of N_{S} into the universal model N will give an embedding of S into M.

We work by induction on i ≤ κ and for every η ∈ ^{i}λ construct an elementary embedding f_{η} : M_{i} → C with image M_{η}. We demand:

(1) ν ◁ η ⇒ f_{ν} ⊆ f_{η}.

(2) for every η ∈ ^{i}λ and α < λ, M_{η ⟨α⟩} ⋃ ; M_{η} ⋃{M_{ν ⟨β⟩} : ν ⟨β⟩ ∈ ^{i}λ, ν ⟨β⟩ ≠ η ⟨α⟩} ∪ M_{η}

At limit i we take unions. For i + 1: M_{η ⟨α⟩} exists by 2.3.

For every η ∈ ^{κ}λ extend f_{η} to f_{η}^{+} : M_{ν}^{+} → C.

6.6 Claim: Suppose that ν ≠ η ∈ ^{κ}λ and that ζ is the least such that η(ζ) ≠ ν(ζ). Suppose that N ≺ C and that M_{η}^{+}, M_{ν}^{+} ⊆ N. Then Av(I_{η}, N)E^{ξ}Av(I_{ν}, N) ⇔ ξ < ζ. Proof: Let ξ < κ. Let f ∈ Aut(C) map M_{η}^{+} onto M_{ν}^{+}. For simplicity we assume that

f_{η} M_{ζ} = f_{ν} M_{ζ} = id. We know that M_{η} C ; ⋃ ; M_{ζ} M_{ν}.

First case: ζ > ξ. (∗) gives a definition of Av_{φ_{ξ}}(I, N) with set of parameters J′_{φ_{ξ}}. In C this definition gives, with respective sets of parameters I_{η}, I_{ν}, the types p_{1}, p_{2}, which extend, respectively, Av_{φ_{ξ}}(I_{η}, M_{η}^{+}) and Av_{φ_{ξ}}(I_{ν}, M_{ν}^{+}). Let I_{η} be I_{1} and let I_{ν} be I_{2}. 6.7 Fact: for l = 1, 2, Av_{φ_{ξ}}(I_{l}, C) = Av_{φ_{ξ}}(J_{φ_{ξ}}, C). Proof: Suppose to the contary that c ∈ C demonstraes otherwise. Then by 2.4, there is someh is I′_{l} ⊆ I_{l} of size < κ(T) such that the set (I_{l} \ I′_{l}) ∪ {c} is independent over M_{l}. Thereforee c ⋃ ; M_{l} M_{l} + ∪(I_{l} \ I′_{l}). By 2.3(4), the type of c is finitely satisfiable over M_{l}. There is finite information saying that φ(−, c) behaves ddifferently in Av_{φ_{ξ}}(J_{φ_{ξ}}, C) than in Av|φ_{ξ}(I_{l}, C). So there is a counterexaample inside M_{l} — a contradiction. _{⌣} · · _{crux}

By this fact we conclude that Av(I_{η}, C)E^{ξ}Av(I_{ν}, C).

Second case: ξ ≥ ζ. We extend Av(I_{η}, M_{η}) to a non-forking extention p ∈ S(C). So p ⋃ ; M_{ζ} M_{ν}. In particular P φ_{ξ} ⋃ ; M_{ζ} M_{ν}. Therefore there is some J′_{ζ} as in (∗) — contradiction to α_{ξ} = ξ + 1. _{⌣} · · _{ccc}

Suppose now that S is a given tree in K_{κ}^{+} of size λ. Without losssof generality, S < ^{κ}λ. Pick a model N_{S} ≺ C such that for every η ∈ S, M_{η} ⊆ N and such that ||N|| ≤ λ. An elementary embedding of N_{S} into N easily gives an embedding of S into M. _{⌣} · · _{6.3}

REFERENCES

[KjSh 409] M. Kojman and S. Shelah, Non-existence of universal orders in many cardinals, ac-

cepted to the Journal of Symbolic Logic [Sh-c] Sahron Shelah, Classification theory: and the number of non- isomorphic

models, revised, North Holland Publ. Co., Studies in Logic and the Foundation of Math vol. 92, 1990, 705 + xxxiv.

[Sh-g] Saharon Shelah, Cardinal Arithemetic, to appeare. [Sh 100] Saharon Shelah, Independence results, Journal of Symbolic Logic 45 No. 3 (1980)

pp. 563–573.

[Sh 175a] Saharon Shelah, Universal graphs without CH: revisited, Israel Journal of Math

70 (1990) pp. 69–81

[Sh 420] Saharon Shelah, Cardinal arithmetic, to appear in Proceedings of the Banff conference, April 1991.