Non-existence of Universal Orders in Many Cardinals Menachem Kojman and Saharon Shelah† Department of Mathematics, Hebrew University 91904 Jerusalem, Israel ABSTRACT Our theme is that not every interesting question in set theory is independent of ZF C. We give an example of a first order theory T with countable D(T) which cannot have a universal model at ℵ_{1} without CH; we prove in ZF C a covering theorem from the hypothesis of the existence of a universal model for some theory; and we prove — again in ZFC — that for a large class of cardinals there is no universal linear order (e.g. in every ℵ_{1} < λ < 2^{ℵ_{0}}). In fact, what we show is that if there is a universal linear order at a regular λ and its existence is not a result of a trivial cardinal arithmetical reason, then λ “resembles” ℵ_{1} — a cardinal for which the consistency of having a universal order is known. As for singular cardinals, we show that for many singular cardinals, if they are not strong limits then they have no universal linear order. As a result of the non existence of a universal linear order, we show the non-existence of universal models for all theories possessing the strict order property (for example, ordered fields and groups, Boolean algebras, p-adic rings and fields, partial orders, models of PA and so on).

Key words: Universal model, Linear Order, Covering Numbers, Club guessing, Strict Order Property Subject Classification: Model Theory, Set Theory, Theory of Orders

0. Introduction General Description This paper consists entirely of proofs in ZFC. We can even dare to recommend reading it to

anybody who is interested in linear orders or partial orders in themselves, and to whom axiomatic set teory and model theory are of less interest. Such a reader should, though, consult the appendix to this paper, or a standard textbook like [CK] for the notion of “elementary submodel”, and confine his reading to sections 3, 4 and 5.

The general problem addressed in this paper is the computation of the universal spectrum of a theory (or a class of models), namely the class of cardinals in which the theory (the class) has a universal model. (A definition of “universal model” is found below). As the universal spectrum of a theory usually depends on cardinal arithmetic, and even on the particular universe of set theory in which a given cardinal arithmetic holds (see below), the problem of determining the universal spectrum of a theory must be rephrased as: under which cardinal arithmetical assumptions can a given theory (class) possess a universal model in a given cardinality λ?

All results in this paper are various negative answers in ZFC to this question, namely theorems of the form “ if C(λ) (some cardinal arithmetic condition on a cardinal λ) then there is no universal model of T at cardinality λ”. In general, it is harder to prove such theorems when the cardinal λ in question is singular. Such theorems are first proved for the case where T is the theory of linear orders, and then are shown to hold also for a larger class of theories, including the theory of Boolean algebras, the theory of ordered fields, the theory of partial orders and others.

† Supported by a BSF grant. Publication No. 409 1

Background and detailed content A universal model at power λ, for a class of models K, is a model M ∈ K of cardinality λ with the property that for all N ∈ K such that |N| ≤ λ there is an embedding of N into M. At this point let us clarify what “embedding” means in this paper. If K = MOD(T) is the class of models of a first order theory T, then “embedding” should be understood as “elementary embedding” when T is complete, and “universal” is with respect to elementary embeddings; when T is not complete (e.g. the theory of linear orders, the theory of graphs or the theory of Boolean algebras), “embedding” is an ordinary embedding, namely a 1-1 function which preserves all relations and operations, and “universal” is with respect to ordinary embeddings. This distinction is necessary, because there are theories for which universal models in the sense of an ordinary embedding exist, whereas universal models in the sense of an elementary embedding do not exist (see appendix for such an example).

Although the notion “universal model” is older then its relative, “saturated model”, and arises more often and more naturally in other branches of mathematics, it has won less attention, perhaps because answers to questions involving the former notion were harder to get. As one example of a contribution to the theory of universal models we can quote [GrSh 174], in which it is shown that the class of locally finite groups has a universal model in any strong limit of cofinality ℵ_{0} above a compact cardinal. The class {λ : T has a saturated model of cardinality λ} has been characterized for a first order theory T (See the situation — with history — in [Sh-a] or [Sh-c], VIII.4).

Saturated models are universal, and their existence in known at cardinals λ such that λ = λ^{<λ} > |T | or just λ = λ^{<λ} ≥ |D(T)| (D(T) is defined below) for every T; furthermore, when λ = 2^{<λ}, essentially the same proof gives a “special model”, which is also universal (for these results see [CK]). Therefore the problem of the existence of a universal model for a first order theory remains unsettled in classical model theory only for cardinals λ < 2^{<λ}.

The consistency of not having universal models at such λ’s for all theories which do not have to have one at every infinite power is very easy (see appendix). In the other direction, the second author proved in [Sh 100] the consistency of the existence of a universal order at ℵ_{1} with the negation of CH, and, in [Sh 175], [Sh 175a], proved the consistency of the existence of universal graph at λ, if there is a κ such that κ = κ^{<κ} < λ < 2^{κ} = cf(2^{κ}). One could expect at that point to prove that every theory T which has no trivial reason for not having a universal model at ℵ_{1} < 2^{ℵ_{0}}, can have one. (By a “trivial reason” we mean an uncountable D(T). D(T) is the set of all complete n-types over the empty set, n < ω; it is known and easy to prove that if D(T) is uncountable, it is of size 2^{ℵ_{0}}; and every type in D(T) must be realized in a universal model). But this is not the case. In Section 1. we show that there is a first order theory T with |D(T)| = ℵ_{0} (which is even ℵ_{0}-categorical) which has a universal model in ℵ_{1} iff CH.

An attempt to characterize the class of theories for which it is consistent to have a universal model at ℵ_{1} < 2^{ℵ_{0}} was done by Mekler. Continuing [Sh 175] he has shown in [M] that it is consistent with the negation of CH that every universal theory of relational structures with the joint embedding property and amalgamation for P^{−}(3)-diagrams and only finitely many isomorphism types at every finite power, has a universal model at ℵ_{1}. He has also shown, continuing [Sh 175a], that it is consistent with κ^{<κ} = κ < cf(2^{κ}) < λ < 2^{κ} that every 4-amalgamation class, which in every finite power has only finitely many isomorphism types, has a universal structure in power λ.

In Section 2 we prove a covering theorem which shows, as one corollary, that if 2^{ℵ_{0}} = ℵ_{ω_{1}}, there are no universal models for non-ω-stable theories in every regular λ below the continuum.

In Section 3 we prove in ZF C several non-existence theorems for universal linear orders in regular cardinals. We show that there can be a universal linear order at a regular cardinal λ only if λ = λ^{<λ} or if λ = μ^{+} and 2^{<μ} ≤ λ. In Section 5 we prove non-existence theorems for universal linear orders in singular cardinals. For example, if μ is not a strong limit and is not a fix point of the ℵ function, then there is no universal linear order in μ.

In Section 5 we reduce the existence of a universal linear order in cardinality λ to the existence of a universal model for any theory possessing the strict order property. Thus the non existence theorems from Sections 3 and 4 which were proven for linear orders are shown to hold for a large collection of theories.

The combined results from Sections 3, 4 and 5 show that it is impossible to generalize [Sh 100] in the same fashion that [Sh 175a] and [M] generalize [Sh 175]: While the proof of the consistency of having a universal graph in ℵ_{2} < 2^{ℵ_{0}} generalizes the proof for the case ℵ_{1} < 2^{ℵ_{0}}, the consistency of universal linear order is true for the former case and is false for the latter. This points out an interesting difference between the theory of order and the theory of graphs.

The second author is interested in the classification of unstable theories (see [Sh 93]). With respect to the problem of determining the stability spectrum of a theory T (namely the class K_{T} = {λ : T has a universal model at λ}), there are several more results which were obtained, in addition to what is published here: the main one is a satisfactory distinction between superstabele to stable-unsuperstable theories. Notation and Terminology: By “order” we shal mean linear order. |M| denotes the universe of a model M and ||M|| denotes its cardinality.

Section 1: A theory without universal models in ℵ_{1} < 2^{ℵ_{0}}.

We present a theory T. In the language L(T) there are two n-ary relation symbols, R_{n}(⋯) and P_{n}(⋯) for every natural number n ≥ 2. T has no constants or function sumbols. The axioms of T are:

1. The sentences saying that P_{n} and R_{n} are invariant under permutation of arguments and that P_{n}(x_{1}, ⋯, x_{n}) and R_{n}(x_{1}, ⋯, x_{n}) do not hold if for some 1 ≤ i < j ≤ n, x_{i} = x_{j}, for all n ≥ 2 2. For each n the sentence saying that there are no 2n−1 distict elements, x_{1}, ⋯, x_{n}, y_{1}, ⋯, y_{n−1}

such that P_{n}(x_{1}, ⋯, x_{n}) and for all 1 ≤ i ≤ n, R_{n}(y_{1}, ⋯, y_{n−1}, x_{i})

Fact 1.1: 1. There are only finitely many quantifier free n-types of T for every finite n.

2. T has the joint embedding property and the amalgamtion property.

Proof: 1. is obvious. Suppose that M, N are two models of T which agree on their intersection. As T is universal, the intersection is also a model of T. Define a model M′ such that |M′| = |M|∪|N| and such that P_{n}^{M′}, R_{n}^{M′} equal, respectively, P_{n}^{M} ∪P_{n}^{N} and R_{n}^{M} ∪R_{n}^{N}. Suppose to the contrary that M′ does not satisfy T. So for some n there are a,_{1} , ⋯, a_{n}, b_{1}, ⋯, b_{n−1} which realize the forbidden type. Certainly, {a_{1}, ⋯, a_{n}, b_{1}, ⋯, b_{n−1}} ⊈ M, as M ⊧ T, and {a_{1}, ⋯, a_{n}, b_{1}, ⋯, b_{n−1}} ⊈ N as N ⊧ T. So either

(a) there is some a_{i} ∉ M and a_{j} ∉ N,

(b) there is some a_{i} ∉ M and b_{j} ∉ N or

(c) there is some b_{i} ∉ M and b_{j} ∉ N. If (a) holds this contradicts P (a_{1}, ⋯, a_{n}); if (b) holds this contradicts R(b_{1}, ⋯, b_{n−1}, a_{i}); and

if (c) holds this contradicts R(b_{1}, ⋯, b_{n−1}, a_{1}). ⊣

Fact 1.2 T has a universal homogeneous model M at ℵ_{0}.

This should be well known, but for completeness of presentation’s sake we give:

Proof: Construct an increasing sequence of finite models M_{n}:

1. M_{n} ⊧ T and M_{n} is finite.

2. M_{n} ⊂ M_{n+1}.

3. In M_{n+1} \ M_{n} all quantifier free types (of T) over M_{n} are realized.

As T has only finitely many quantifier free types over every finite set, and because of fact 1.1, this construction is possible. The model M = ∪M_{n} clearly satisfies T.

Suppose that h is a finite embedding from any other model N into M and that a ∈ N \dom(h). There is some n_{0} such that ran(h) ⊆ M_{n_{0}}. In M_{n_{0}+1} there is some b such that its relational type over ran(h) (in M) equals the relational type of a over dom(h) (in N). Set h′ = h ∪ ⟨a, b⟩ to obtain an embedding with a in its domain. By this observation it is immediate that every countable model of T is embeddable into M. Hence the universality of M in ℵ_{0}.

As there are no unary relation symbols in T, any h = {⟨a_{1}, a_{2}⟩}, where a_{1}, a_{2} ∈ M is an embedding. Suppose that h is a finite embedding, dom(h), ran(h) ⊆ M and that b ∈ M \ ran(h). Pick, as before, some a ∈ M \dom(h) such that its relational type over dom(h) equals the relational type of b over ran(h), and extend h to include b in its range. These observations show that for every two sequences \overline{a}, \overline{b} ∈ M^{n} there is an automorphism f of M with f(\overline{a}) = \overline{b}. Hence M is homogeneous. ⊣

Denote by T_{1} the theory T h(M), the theory of the model M. Then

1.3 Fact T_{1} is a complete theory extending T, which admits elimination of quantifiers and is ℵ_{0}-categorical.

Proof Clearly, every simple existential formula is equivalent to a quantifier free formula in T_{1}. Hence the elimimation of quantifiers. By fact 1.1 there are only finitely many n-types of T over the empty set. Therefore T is ℵ_{0}-categorical (see [CK] for details). ⊣

1.4 Fact (1) For every infinite model M ⊧ T there is a model M′ such that M ⊆ M′ ⊧ T_{1} and ||M|| = ||M′||.

(2) T and T_{1} have the same spectrum of universal models, namely for every cardinal λ, T has a universal model in λ (with respect to ordinary embeddings) iff T_{1} has a universal model in λ (with respect to elementary embeddings).

Proof: (1) follows by the compactness theorem, as every finite submodel of M (even countable) satisfies T, and is therefore embeddable into the countable model of T_{1}. For (2), we may forget about finite cardinals, as neither of both theories has universal finite models (in fact T_{1} has no finite models at all). Suppose first that M ⊧ T is universal for T in power λ. Then by 1. there is some M′ ⊇ M, a model of T_{1} of the same cardinality. Let N ⊧ T_{1} be arbitrary of power λ. As N ⊧ T, there is an embedding h : N → M. h is also an embedding into M′. As T_{1} has elimination of quantifiers, h is an elementary embedding of N into M′. So M′ is a universal model of T_{1} in λ. Conversely, suppose that M ⊧ T_{1} is universal for T_{1} in power λ. In particular, M ⊧ T. Let N ⊧ T be arbitrary of power λ. By (1) there is some N′ ⊇ N of cardinality λ, N′ ⊧ T_{1}. Let h : N′ → M be an elementary embedding. h N is an embedding of N into M. So M itself is universal for T. ⊣ 1.5 Remark: 1. T does not satisfy the 3-amalgamation property, as seen by a simple example.

2. Also T_{1} has the joint embedding property. 1.6 Theorem T has a universal model in ℵ_{1} iff ℵ_{1} = 2^{ℵ_{0}}. Proof: If ℵ_{1} = 2^{ℵ_{0}} then all countable theories have universal models in ℵ_{1}. We proceed now to prove that 2^{ℵ_{0}} > ℵ_{1} implies that T has no universal model at ℵ_{1}. Suppose to the contrary that CH fails, but that M is a universal model at ℵ_{1}. Without loss of generality, |M| = ω_{1}. We define now 2^{ℵ_{0}} models of T: for each η ∈ ^{ω}2 let M_{η} be a model with universe ω_{1} such that

a . P_{n}^{M_{η}} = [ω_{1}]^{n} iff R_{n}^{M_{η}} = ∅ iff η(n) = 0 b . R_{n}^{M_{η}} = [ω_{1}]^{n} iff P_{n}^{M_{η}} = ∅ iff η(n) = 1

For each η the model M_{η} trivially satisfies T.

As M is universal, we can choose for each η an embedding h_{η} : M_{η} ⟶ M. Let M_{η}^{∗} be the model obtained from M by enriching it with the relations of M_{η} and the function h_{η}. Let C_{η} be the closed unbounded set {δ ∈ ω_{1} : M_{η}^{∗} δ ≺ M_{η}^{∗}}, and let δ_{η} ∈ C_{η}.

As we have 2^{ℵ_{0}} η’s, by the pigeon hole principle there are more than ℵ_{1} sequences, ⟨η_{i} : i < i(∗)⟩, such that for all i < i(∗) δ_{η_{i}} = δ_{0}. As there are only ℵ_{1} possible values to h_{η_{i}}(δ_{0}), we may assume that for all i < i(∗), h_{η_{i}}(δ_{0}) = γ_{0} for some fixed γ_{0} and that η_{i} 2 is fixed. (Note that by elementarity, and as h is one to one, γ_{0} ≥ δ_{0}). Pick now i < j < i(∗). There exists an n > 1 with η_{i}(n) ≠ η_{j}(n), and assume by symmetry η_{i}(n) = 0. This means that every n-tuple of distinct members of the range of h_{η_{i}} satisfies the relation P_{n}^{M}, while every n-tuple of distinct members of the range of h_{η_{j}} satisfies the relation R_{n}^{M}. We intend now to derive a contradiction by constructing the forbidden type inside M. Pick any n − 1 points, b_{1}, ⋯, b_{n−1} ∈ δ_{0} in the range of h_{η_{j}}. Notice that M ⊧ R_{n}(b_{1}, ⋯, b_{n−1}, γ_{0}). Work now in M_{η_{i}}^{∗}.

M_{η_{i}}^{∗} ⊧ ∃(x)R_{n}(b_{1}, ⋯, b_{n−1}, h_{η_{i}}(x)) as δ_{0} witnesses this.

So by elementarity there is such an c_{1} below δ_{0} with a_{1} = h_{η_{i}}(c_{1}) also below δ_{0}.

M_{η_{i}}^{∗} ⊧ ∃(x ≠ c_{1})R_{n}(b_{1}, ⋯, b_{n−1}, h_{η_{i}}(x)) as δ_{0} witnesses this.

So by elementarity we can find c_{2}, a_{2} below δ_{0}. We proceed by induction, each time picking a_{i+1} differrent from all the previous a’s. So when i = n we have constructed the forbidden type, as a_{1}, ⋯, a_{n}, being in the range of h_{η_{i}}, satisfy the relation P_{n}^{M}. This contradicts M ⊧ T. ⊣

The proof above tells us a bit more than is stated in theorem 1.6: what was actualy done, was to construct 2^{ℵ_{0}} models of T, each of size ℵ_{1}, such that no 2^{ℵ_{0}} can be embedded into a single model of T. But this construction uses no special feature of ℵ_{1} and the models as defined above can be defined in any cardinality. Let us state the following. 1.7 Theorem: Let T be the theory in 1.6. If ℵ_{0} < λ = cfλ < 2^{ℵ_{0}} and μ < 2^{ℵ_{0}} are cardinals, then for every family of models of T {M_{i} : i < μ}, each M_{i} of cardinality λ, there is a model M of T which cannot be embedded into any M_{i} in the family. Proof: Suppose such a family is given. As in the previous proof, there are 2^{ℵ_{0}} trivial models of T, each with universe λ. Suppose that each of them is embedded into some member of the family. As μ < 2^{ℵ_{0}}, there must be a fixed member M_{i(∗)} of the family into which more than λ such models are embedded. The contradiction follows now as above. ⊣

Section 2: A covering theorem

We prove here a theorem that as one consequence puts a restriction on the cofinality of 2^{λ} — provided there is a universal model for a suitable theory in some cardinality κ ∈ (λ, 2^{λ}).

2.1 Theorem Let T be a first order theory, λ < κ < μ cardinals. Suppose that T has a universal model at κ and that there is a model M of T, |M| = μ, with a subset A ⊆ μ, |A| = λ such that |S(A)| ≥ μ, namely there are μ complete 1-types over A. Then there is a family ⟨B_{i} : i < κ^{λ}⟩ ⊆ [μ]^{κ} which covers [μ]^{κ}, namely for every C ∈ [μ]^{κ} there is an i < κ such that C ⊆ B_{i}.

As corollaries we get

2.2 Corollary : If cf(2^{λ}) ≤ κ < 2^{λ} and T is a first order theory possessing the independence property then T has no universal model at κ.

2.3 Corollary : Suppose that 2^{ℵ_{0}} = ℵ_{ω_{1}}. Then all theories unstable in ℵ_{0} (e.g. the theory of graphs, the theory of linear order and so on) do not have a universal model in any cardinal κ ∈ [ℵ_{1}, ℵ_{ω_{1}}).

Proof of Corollary 2.2 from Theorem 2.1: If T possesses the independence property, then there is a model of T in which 2^{λ} types over a set of size λ are realized. By Theorem 2.1, if there were a universal model for T at κ, then there would be a covering family of [2^{λ}]^{κ} of size 2^{λ}; but as cf(2^{λ}) ≤ κ, this is clearly impossible. ⊣

Proof of Corollary 2.3 from Theorem 2.1: If a countable theory T is not stable at ℵ_{0} then T has a model in which 2^{ℵ_{0}} complete 1-types over a countable set are realized. So a universal model at κ ∈ [ω_{1}, 2^{ℵ_{0}}) would imply, by Theorem 2.1, that there is a covering family of [2^{ℵ_{0}}]^{κ} of size 2^{ℵ_{0}}, which is impossible as cf(2^{ℵ_{0}}) ≤ κ. ⊣

Proof of theorem 2.1: Let U be a universal model for T with universe κ and let M be a model of T with a subset A ⊂ |M| of size λ with ⟨p_{i} ∈ S(M) : i < μ⟩ a sequence of distinct complete types over A. Without loss of generality M is of size μ and in M all p_{i}’s are realized. We can further assume (by enumerating |M|) that |M| = μ + μ, that p_{i} is realized by the element i and that A = {α : μ ≤ α < μ + λ}. For each submodel N, A ∪ B ⊆ N ≺ M of size κ pick an embedding h_{N} : N → U. For each function f : A → κ let C_{f} be the set of submodels {N ⊆ M : |N| ≤ κ, A ⊆ N, and h_{N} A = f}. 2.4 Claim: For each f ∈ κ^{A}, | ∪ C_{f} ∩ μ| ≤ κ.

Proof: Enumerate all members of C_{f} in a sequence ⟨N_{α} : α < α(∗)⟩ and define a function g : ∪C_{f} ∩ μ → κ by induction on α as follows: g (N_{α} \ ∪_{β<α}N_{β}) = h_{N_{α}} (N_{α} \ ∪_{β<α}N_{β}). We are done if g is a 1-1 function. This follows from

2.5 Fact If i ∈ N_{α}, j ∈ N_{β}, and i < j < μ then h_{N_{α}}(i) ≠ h_{Nβ}(j).

Proof of Fact: As both embeddings aggree on the image of A and i, j realize different types over A, the fact is immediate. 2.6 Claim: The family {(∪C_{f}) ∩ μ : f ∈ ^{A}κ} is a covering family of [μ]^{κ} of size λ^{κ}.

Proof of claim: Clearly the size of the family is as stated. Let B ∈ [μ]^{κ} be any set. Then it is a subset of some elementary submodel N ⊆ M which contains A as a subset. So it is a subset of ∪C_{f_{N} A} ∩ μ. ⊣

Section 3: Non-existence of universal linear orders

In this section we prove some non-existence theorem for universal linear orders in regular cardinals. We start by showing that there is no universal linear order in a regular cardinal λ if ℵ_{1} < λ < 2^{ℵ_{0}}. We shall generalize this for more regular cardinals later in this section. The combinatorial tool which enables these theorems is the guessing of clubs which was introduced in [Sh-e] and can be found also in [Sh-g], which will, presumably, be available sooner. Proofs of the relevant combinatorial principles are repeated in the appendix to this paper for the reader’s convenience. 3.1 Definitions

1. If C is a set of ordinals, δ an ordinal, we denote by δ_{C}^{s} the element min{C \ (δ + 1)} when it exists.

2. a cut D of a linear order O is pair ⟨D_{1}, D_{2}⟩ such that D_{1} is an initial segment of O, namely D_{1} ⊆ |O| and y < x ∈ D ⇒ y ∈ D_{1}, D_{2} is an end segment, namely D_{2} ⊆ |O| and y > x ∈ D_{2} ⇒ y ∈ D_{2}, D_{1} ∩ D_{2} = ∅ and D_{1} ∪ D_{2} = |O|. If O_{1} ⊆ O_{2} are linear orders, then an element x ∈ O_{2} \ O_{1} realizes a cut D of O_{1} if D_{1} = {y ∈ O_{1} : y < x}.

3. Let O = ∪_{j<λ}O_{j} be an increasing continuous union of linear orders, let δ ∈ λ be limit, and let C ⊆ δ be unbounded in δ. Let x ∈ (O \ ∪_{j<δ}O_{j}). Define Inv_{O}(C, δ, x), the invariance of x in O with respect to C, as {α ∈ C : ∃y ∈ O_{α_{C}^{s}} such that y and x realize the same cut of O_{α}}. Note that this definition is applicable also to cuts (rather than only to elements).

4. A κ-scale for λ is a sequence \overline{C} = ⟨c_{δ} : δ ∈ S⟩ where S = \{α < λ : cfα = cfκ\} and for every δ ∈ S, c_{δ} is a club of δ or order type κ, c_{δ} = ⟨α_{j}^{δ} : j < κ⟩ is an increasing enumeration of c_{δ}. If O = ∪_{i<λ}O_{i} is a linear order represented as a continuous increasing union of smaller orders, and \overline{C} is a κ-scale for some κ < λ, let INV(O, \overline{C}) =^{def} \{X ⊆ κ : (∃δ ∈ S)(∃x > δ)Inv(c_{δ}, δ, x) = \{α_{j}^{δ} : α ∈ X\}\}. So INV(O, \overline{C}) is the set of all subsets of κ which are obtained as an invariance of some element in O with respect to some c_{δ} in the scale.

3.2 claim: Suppose h : O_{1} → O_{2} is an embedding of linear orders, ||O_{1}|| = ||O_{2}|| = λ = cfλ > ℵ_{0}. Then for any representations O_{i} = ∪_{j<λ}O_{j}^{i}, i = 1, 2, the union increasing and continuous and each |O_{j}^{i}| < λ, there exists a club E ⊆ λ such that for any δ < λ and C ⊆ δ a club of δ which satisfies C ⊆ E, we have

(∗) (∀x ∈ O_{1} \ O_{δ})(Inv_{O_{1}}(C, δ, x) = Inv_{O_{2}}(C, δ, h(x))

Proof of Claim: without loss of generality we may assume that |O_{1}| = |O_{2}| = λ. Define the model M = ⟨λ, <_{O_{1}}, <_{O_{2}}, ∈, h⟩. Let E = {δ < λ : M δ ≺ M and for all δ ∈ E, δ = ∪_{j<δ}O_{j}^{i}, i = 1, 2}. Let x ∈ (O_{1} \O_{δ}^{1}). Note that by elementarity h(x) ∈ (λ\δ). Suppose first that α belongs to the left hand side of the equality in (∗) and let y ∈ [α, α_{C}^{s}) demonstrate this. So x and y realize the same cut of O_{1} α. As h is an embedding, h(x), h(y) satisfy the same cut of h′′(O_{1} α) (which equals, by elementarity, (h′′(O_{1})) α). If h(x), h(y) satisfy also the same cut of O_{2} α we are done, but the problem is, of course, that h is not necessarily onto. Otherwise suppose that (w.l.o.g) h(y) < h(x) and that there is an element z ∈ O_{2} α such that h(y) <_{O_{2}} z <_{O_{2}} h(x). Define in M the set D = {t : there is no q such that z ≤_{O_{2}} h(q) ≤_{O_{2}} t}. D is definable in M with parameters in M α^{s}. By elementarity the definition is absolute between M and M α^{s}, that is D ∩ α^{s} is the same as D interpreted in M α^{s}. D is a cut of O_{2} α. Let D′ be D ∩ α. D′ is definable in M α^{s}.

3.2.1 subclaim: h(x) satisfies the cut D′ determined by D. Proof of Subclaim: let z <_{O_{2}} β <_{O_{2}} h(x). As there are no points in the range of h α between z and h(x), there are certainly none between z and β. So β ∈ D′. Conversely, suppose h(x) <_{O_{2}} β. Then M satisfies that there is an image under h (namely h(x)) between z and β. By elementarity there is such an image h(x′) where x′ ∈ α. So β ∉ D′. As D′ is a cut of O′ α definable in M α^{s} which is realized by h(x), elementarity assures us that is it is realized by some y′ ∈ [α, α_{C}^{s}). So α belongs to the right hand side of (∗). Assume that α belongs to the right hand side of (∗). Then there is an element y ∈ [α, α^{s}) which satisfies the same cut of O_{2} α as h(x). If y = h(y′) for some y′ we are done. Else, we note that the cut of O_{2} α which y determines is definable in M α^{s}. Now clearly h(x) and y satisfy the same cut of O_{2} α. By elementarity there is an element y′ such that h(y′) satisfies the same cut as y, therefore as h(x). In other words, α belongs to the left hand side of (∗). ⊣ 3.3 Fact If O is an order with universe λ and \overline{C} is a κ-scale, then |INV(O, \overline{C})| ≤ λ Proof: Trivial. 3.4 Lemma (the construction lemma): If λ < 2^{ℵ_{0}} is a regular uncountable cardinal, \overline{C} is an ω-scale, and A ⊆ ω is given, then there is an order O with universe λ, O = ∪_{i<λ}O_{i}, increasing continuous union of smaller orders, such that for every δ < λ with cfδ = ℵ_{0}, Inv(c_{δ}, δ, δ) = {α_{n}^{δ} : n ∈ A}. Proof: We define by induction on 0 < α < λ an order O_{α} with the properties listed below. We denote by Q the order of the rationals. If O_{1} ⊆ O_{2} are linear orders, D a cut of O_{1} and D′ a cut of O_{2}, we say that D′ extends D if D′_{1} |O_{1}| = D_{1} and D′_{2} = D_{2}. Also note that if O_{1} ⊆ O_{2} are linear orders and D^{1} is a cut of O_{1} which is not realized in O_{2} then it corresponds naturally to a cut D^{2} of O_{2}. In such a case we say that D^{1} is (really) also a cut of O_{2}.

1. O_{α} has universe |O_{α}| ∈ λ.

2. If β + 1 = α and x ∈ (O_{α} \ O_{β}), then {y ∈ O_{α} \ O_{β} : x and y satisfy the same cut of O_{β}} has order type Q.

3. If α < β < γ, γ is a successor, and there is a cut D of O_{α} which is realized by an element of O_{β} but is not realized by no element of O_{ν} for α < ν < β, then there is a cut D′ of O_{β}, which extends D, which is realized in O_{γ} but is not realized in O_{ν} for all β < ν < γ. Also for every successor α there is a cut of O_{0} which is realized in O_{α} but is not realize in O_{β} for every β < α.

4. If α is limit then O_{α} = ∪_{β<α}O_{β}.

5. If cfδ = ℵ_{0} and for all β ∈ C_{α}, |O_{β}| = β, then Inv_{O_{δ+1}}(c_{δ}, δ, δ) = {α_{n}^{δ} : n ∈ A}.

There should be no problem taking care of 1–4. Assume that the conditions of 5. are satisfied. We wish to define the order O_{α+1}. Let C_{α} = ⟨β_{n} : n < ω⟩. By induction on A = ⟨a_{n} : n < ω⟩ define an increasing sequence of cuts, ⟨D_{α_{n}} : n ∈ ω⟩ such that D_{a_{n}} is a cut of O_{a_{n}} which is realized for the first time in O_{a_{n+1}}. Demand 3. enables this. In O_{α+1} let α satisfy ⋃ D_{n} to get 5. ⊣

We are almost ready to prove the non existence of a universal order in a regular λ, ℵ_{1} < λ < 2^{ℵ_{0}}. We recall from [Sh-e] chapter III.7.8 (see also [Sh-g]), 3.5 Fact: If λ > ℵ_{1} is regular, then there is a sequence \overline{C} = ⟨c_{δ} : δ < λ, cfδ = ℵ_{0}⟩, such that c_{δ} ⊆ δ is a club of δ of order type ω_{0}, with the property that for every club E ⊆ μ the set S_{E} = {δ < λ : cfδ = ℵ_{0} and c_{δ} ⊆ C} is stationary. ⊣

A proof of this fact is found in the appendix. 3.6 Theorem If ℵ_{1} < λ = cfλ < 2^{ℵ_{0}}, then there is no universal order in cardinality λ. Proof: Suppose to the contrary that UO is a universal order in cardinality λ. Without loss of generality, |UO| = λ. Fix some club guessing sequence \overline{C} = ⟨c_{δ} : δ < λ, cfδ = ℵ_{0}⟩. This is known to exist by the previous fact. As |INV(UO, \overline{C})| ≤ λ, there is some A ⊆ ω, A ∉ INV(UO, \overline{C}). Use the construction lemma to get an order M with universe λ and with the property that for every δ < λ, cfδ = ℵ_{0} implies that Inv_{M}(c_{δ}, δ, δ) = {α_{n}^{δ} : n ∈ A}. Let h : M → UO be an embedding. Let E_{h} be the club given by 3.2. As \overline{C} guesses clubs, there is some δ(∗) with c_{δ(∗)} ⊆ E_{h}. Therefore, by 3.2, Inv_{M}(c_{δ(∗)}, δ(∗), δ(∗)) = Inv_{UO}(c_{δ(∗)}, δ(∗), h(δ(∗))). But Inv_{M}(γ_{δ(∗)}, δ(∗), δ(∗)) = {α_{n}^{δ} : n ∈ A}. This means that A ∈ INV(UO, \overline{C}), a contradiction to the choice of A ∉ INV(UO, \overline{C}). ⊣

We wish now to generalize Theorem 3.6 by replacing ω_{0} by a more general κ. As the proof of 3.6 made use of both club guessing and the construction lemma, we should see what remains true of these two facts for κ > ℵ_{0}. The proof of the construction lemma does not work when replacing ℵ_{0} by some other cardinal. We need some extra machinery to handle the limit points below κ.

3.7 Lemma (the second construction lemma) Suppose κ < λ = cfλ are cardinals, 2^{κ} ≥ λ and that there is a stationary S ⊆ λ and sequences ⟨c_{δ} : δ ∈ S⟩ and ⟨P_{α} : α < λ⟩ which satisfy:

(1) otpc_{δ} = κ and sup c_{δ} = δ;

(2) P_{α} ⊆ P(α) and |P_{α}| < λ;

(3) if α ∈ nacc c_{δ} then c_{δ} ∩ α ∈ ∪_{β<α}P_{β}, THEN when given such sequences and a closed A ⊆ Limκ there is a linear order O with

universe λ with the property that for every δ ∈ S, Inv(c_{δ}, δ, δ) = A_{δ}, where A_{δ} is the subset of c_{δ} which is isomorphic to A.

Proof We pick some linear order L of cardinality smaller than λ which has at least λ cuts. We assumme, without loss of generality, that P_{α} ⊆ P_{β} whenever α < β, that for limit α P_{α} = ∪_{β<α}P_{β} and that if α ∈ nacc c_{δ} then A_{δ} ∩ α ∈ P_{α}. Next we construct by induction on α < λ an order O_{α} and a partial function F with the following demands:

(1) the universe of O_{α} is an ordinal below λ.

(2) α < β ⇒ O_{α} ⊆ O_{β}, and if α is limit, then O_{α} = ∪_{β<α}O_{β}.

(3) If x ∈ O_{β} \ O_{α}, then the order type of {y ∈ O_{β} : x and y satisfy the same cut of O_{α}} contains L as a suborder. Also, if α is a successor, then there is an element in O_{α} which satisfies a new cut of O_{0}.

(4) If α < β < γ and γ is a succsessor, then if D is a cut of O_{α} which is realized in O_{β} but not in an earliert stage, then there is a cut D′ of O_{β} which extends D and is realized in O_{γ} but is not realized in O_{δ} for any δ < γ.

(5) F is a partial function, domF ⊆ S × (λ \ Lim λ). A pair ⟨δ, α⟩ ∈ domF iff α < δ, ∅ ≠ A_{δ} ∩ α ∈ P_{α} \ P_{α−1}. F (δ, α) is a pair ⟨β(δ, α), D(δ, α)⟩, where β < α and D is a cut of O_{β} which is realized in O_{α}. If β is not a limit of A_{δ} then D is not realized in O_{γ} for any γ < α. F (δ, α) depends only on A_{δ} ∩ α, namely if A_{δ_{1}} ∩ α = A_{δ_{2}} ∩ α then F (δ_{1}, α) = F (δ_{2}, α). If α < γ and F (δ, α), F (δ, γ) are both defined, then β(δ, α) < β(δ, γ) and D(δ, γ) extends D(δ, α).

(6) If δ ∈ S then Inv_{O_{δ+1}}(c_{δ}, δ, δ) = A_{δ}.

As O_{0} we pick L. When α is limit, we define O_{α} as the union of previous orders. When α is a successor we add less then λ elements to take care of demands 3 and 4. If A_{δ} ∩ α ∈ P_{α} \ α − 1 we must define F (δ, α). If A_{δ} ∩ α contains exactly one member, let β(δ, α) = 0 and as D(δ, α) pick (by(3)) a cut of O_{0} which is realized in O_{α} but is not realize in O_{γ} for any γ < α. In case the order type of {γ < α : F (δ, γ) is defined } is limit, we let D(δ, α) = ∪_{γ<α}D(δ, γ) and β(δ, α) = ∪_{γ<α}β(δ, γ). Note that β(δ, α) < α, because it is limit. Add more elements to O_{α} to realize D. Since |P_{α}| < λ, this requirement of addition of elements is satisfied by adding less than λ new elements. In case there is a last γ < α for which F (δ, γ) is defined, let this γ be β(δ, α) and pick (by (4)) a cut D or O_{γ} which extends D(δ, γ) and is realized in O_{α}, but is not realised earlier, as D(δ, α). When α = δ + 1 and δ ∈ S, let the element δ realize, in O_{α} the cut ∪_{γ<α}F (δ, γ).

Having added less than λ new elements, we fulfill demand (1). (2) and (3) are obvious, and (4) and (5) have been taken care of.

Claim: demand (6) holds.

Proof: Suppose that δ ∈ S. We show by induction that for every x ∈ A_{δ}, for every y ≤ x in c_{δ} there is some γ < y_{c_{δ}}^{s} which satisfies the cut of δ over O_{y} iff y ∈ A_{δ}. Suppose x is the first member of A_{δ}. Then the first γ for which F (δ, γ) is defined satisfies x < γ < x_{c_{d}}^{s} by the assumptions on ⟨P_{α} : α < λ⟩. F (δ, γ) is a cut of O_{0} which is realized in O_{γ} but not before. If y ∈ c_{δ} ∩ x, as x is a limit of c_{δ}, y_{c_{d}}^{s} < x. The cut of δ over O_{0} is F (δ, γ). And the cut of δ over O_{y} extends this cut. As F (δ, α) is not realized by the stage O_{y}, certainly the cut of δ over O_{y} is not realized by this stage either. So y ∉ Inv(C_{δ}, δ, δ). As the cut of δ over O_{0} is not realized in O_{x}, it is really also a cut of O_{x}. This cut is realized in O_{γ}, where γ < x_{γ_{d}}^{s}. So by definition, x ∈ Inv(c_{δ}, δ, δ).

In the case x is a successor of A_{δ}, denote by z its predecessor in A_{δ}. The minimal γ above x for which F (δ, γ) is defined is smaller than X_{γ_{δ}}^{s}, and β(δ, γ) is in the interval (z, z_{c_{d}}^{s}). The same argument as in the previous case shows that for every y ∈ (z, x], y ∈ Inv(γ_{δ}, δ, δ) iff y ∈ A_{δ}. When x is a limit of A_{δ}, by the induction hypothesis, for every y < x the required holds. As for x itself, if γ is the minimal above x for which F (δ, γ) is defined, γ < x_{c_{δ}}^{s} and F (δ, γ) is realized in O_{γ}. Therefore x ∈ Inv(c_{δ}, δ, δ). ⊣ By [Sh 420] we know: 3.8 Fact If κ is a cardinal and κ^{+} < λ = cfλ, then there is a stationary set S and sequences

⟨c_{δ} : δ ∈ S⟩, ⟨P_{α} : α ∈ λ⟩ as in the assumptions of 3.7.

What is still lacking is the appropriate club guessing fact, which we quote now from [Sh g]:

3.9 Fact: If κ is a cardinal, κ^{+} < λ = cfλ and there is a stationary set S ⊆ λ and sequences ⟨c_{δ} : δ ∈ S⟩, ⟨P_{α} : α < λ⟩ as in 3.7, then there are such with the additional property that ⟨c_{δ} : δ ∈ S⟩ guesses clubs. ⊣

3.10 Theorem Suppose λ = cfλ and there is some cardinal κ such that κ^{+} < λ < 2^{κ}, then there is no universal linear order in cardinality λ. ⊣

Proof: Suppose O is any order of cardinality λ, and assume without loss of generality that its universe is λ. Pick a stationary set S and sequences as in 3.7, with the a property that \overline{C} = ⟨c_{δ} : δ ∈ S⟩ guesses clubs. Pick a closed set A ⊆ Lim κ which is not in INV(O, \overline{C}). Use 3.7 to construct an order O′ with unierse λ and the property that for every δ ∈ S, Inv_{O′}(c_{δ}, δ, δ) ≃ A. If O′ where embedded into O, some c_{δ} would guess the club of the embedding, what would lead to a contradiction. So O′ is not embeddable into O, and therefore there is no universal linear order in λ. ⊣

Section 4: Singular cardinals

We shall state now a theorem which concerns the non-existence of universal linear orders in singular cardinals. Let us note, though, the following well known fact first: 4.1 Fact If μ is a strong limit, then for every first order theory T such that |T | < μ there is a special model of size μ, and therefore also a universal model in μ. ⊣

For the defintion of special model see the appendix. A special model is universal. For more details see [CK] p. 217.

This means that for non existence of universal models we must look at singulars which are not strong limits. We will see at the end of this section that if, e.g., ℵ_{ω} is not a strong limit, then there is no universal linear order at ℵ_{ω}.

We recall from [Sh-g 355,5] 4.2 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. 4.3 Theorem: Suppose θ = cfθ < θ^{+} < κ are regular cardinals, κ < μ and there is a binary tree T ⊆ ^{<θ}2 of size < κ with > μ^{∗} := cov(μ, κ^{+}, κ^{+}, κ) branches of length θ. Then (∗)_{μ,κ} There is no linear order of size μ which is universal for linear orders of size κ (namely that every linear order of size κ is embedded in it). Proof: Let \overline{A} = ⟨A_{i} : i < μ^{∗}⟩ ⊆ [μ]^{<κ^{+}} demonstrate the definition of μ^{∗}. Without loss of generality, |A_{i}| = κ for all i. Suppose to the contrary that there is an order UO = ⟨μ, <_{UO}⟩ into which every order of size κ is embedded. Let M_{i} be UO A_{i} for every i < μ^{∗}. Then every M_{i} is isomorphic to some M′_{i} with universe κ, and for every order O of size κ there is a set J ⊆ μ^{∗}, |J| < κ such that O is embedded into ∪_{i∈J}M_{i}.

We fix a club guessing sequence, \overline{C} = ⟨c_{δ} : δ < μ and cfδ = θ⟩, and an increasing continuous sequence ⟨P_{α} : α < κ⟩ such that P_{α} is a family of subsets of α, |P_{α}| < κ and for all α < μ if δ ∈ S and α ∈ nacc c_{δ}, then (c_{δ} ∩ α) ∈ P_{α}. For the existence of these, see [Sh 420].

For each δ ∈ S enumerate c_{δ} as ⟨a_{i}^{δ} : i < θ⟩ in an increasing continuous fashion. Now T can be viewed as T_{δ}, a tree of subsets of c_{δ}. Under the assumptions we already have, it is no lose of generality to assume that for every α ∈ κ, if α ∈ nacc (c_{δ}), then T_{δ} ∩ P(α) ⊆ P_{α}. The reason is that there are θ possibilities for the unique i such that α = α_{i}^{δ}, and for each such possibility there are < κ subsets in T ∩ P(i); So we can add all the required sets into P_{α} without changing the fact that |P_{α}| < κ.

So by now we have the assumptions of 3.7. Using it we construct a linear order O on κ, with A ⊆ κ not in {Inv_{M′_{i}}(c_{δ}, δ, x) : i < μ^{∗}, x ∈ κ}.

Suppose now that there is an embedding h : O → UO. The image of h is covered by ∪{O_{i} : j ∈ J} for some J of size < κ. Let S_{j} = {x ∈ κ : h(x) ∈ M_{j}}. Then there is some j_{0} such that S_{j_{0}} ∉ \overline{id}^{a}(\overline{C}), (the latter is the ideal of non-guessing, namely X ∈ \overline{id}^{a}(\overline{C}) iff there is a club E such that ∀(δ ∈ S ∩ X)(c_{δ} ⊈ E). This ideal is clearly κ-complete.)

Let O′ be O S_{j_{0}}. Let O′_{i} = O′ i for i < κ. Then this is a presentation of L′ as an increasing continuous union of small orders. By 3.2, and the fact that the identity map embeds O′ into O, almost everywhere the invariance with relation to O is the same as with relation to O′. So we can get again the same contradiction as in previous proofs by inspecting the embedding h O′. ⊣

We wish now to obtain the same results using more concrete assumptions. We first review some facts concerning covering numbers.

Recall the well known (see e.g. [Sh-g 355,5]) 4.4 Fact If δ < κ = cfκ < μ = ℵ_{δ} then cov(μ, κ^{+}, κ^{+}, κ) = μ. Proof: By induction on χ, a cardinal, κ < χ ≤ μ.

(a) χ = θ^{+}. For every α < χ fix a family P_{α} ⊆ [α]^{κ} with the proprty that for every set A ∈ [α]^{κ} there is a

set X ⊆ P_{α}, |X| < κ and A ⊆ ∪X. Let P be the union of P_{α} for α < χ. The size of P is clearly χ, and clearly for every set A ⊆ χn of size κ there is a covering of A by less than κ members of P.

(b) χ = ℵ_{β} is a limit cardinal. As μ = ℵ_{δ} with δ < κ, certainbly β < κ. Let ⟨χ_{i} : i < cfβ⟩ be increasing and unbounded

below χ. Let P_{i} demonstrate that cov(χ_{i}, κ^{+}, κ^{+}, κ) = χ_{i}, and let P = ∪_{i}P_{i}. Then |P | = χ. If A ∈ [χ]^{κ}, cover A ∩ χ_{i} by less than κ members of P. Thus to cover A we need less than κ members of P.

4.5 Improved fact

If μ is a fix point of the first order (i.e. λ = ℵ_{λ}), but not of the second order, i.e. |{λ < μ : λ = ℵ_{λ}}| = σ < μ, and σ + cfμ < κ < μ, then cov(μ, κ^{+}, κ^{+}, κ) = μ.

Proof: Suppose that κ < χ < μ and cfχ = κ. By the assumptions, χ ≠ ℵ_{χ}, say χ = ℵ_{δ}. By [Sh 400], section 2, pp(χ) < ℵ_{|δ|^{+4}} < μ. By [Sh-g 355, 5.4], and the fact that χ is arbitrarily large below μ, we are done. ⊣

We see that we can have arbitrarily large κ below a singular μ with μ = cov(μ, κ^{+}, κ^{+}, κ), when μ is a limit which is not a second order fix point of the ℵ function. But for applying theorem 4.3 we need also a binary tree of height and size < μ with > μ branches. This happens if there is some σ < μ with 2^{<σ} < μ and 2^{σ} > μ. So we can state 4.6 Corollary: If μ is a singular cardinal which is not a second order fix point, and there is some σ < μ such that 2^{<σ} < μ < 2^{σ}, then there is no universal linear order of power μ. Proof: Let T be the tree ^{<σ}2. By the fact on covering numbers, pick σ < σ^{+} < κ such that cov(μ, κ^{+}, κ^{+}, κ) = μ, and apply theorem (*).

As for no μ with cfμ = ℵ_{0} is there a σ < μ with 2^{σ} = μ, we can weeken the assumptions to get 4.7 Corollary If ℵ_{μ} > μ or μ is not a second order fix point, cfμ = ℵ_{0} or 2^{<cfμ} < μ, and μ ≠ 2^{<μ}, then there is no universal linear order at μ. ⊣

Section 5 Generalizations:

In this section we prove that if there is no universal linear order in a cardinal λ then there is no universal model in λ for any countable theory T possessing the strict order property (e.g. there is no universal Boolean algebra in λ). This means that all the non-existence theorems in Section 3 and Section 4 hold for a large class of theories.

5.1 Definition 1. A formula φ(\overline{x}; \overline{y}) has the strict order property if for every n there are \overline{a}_{l} (l < n) such that for any k, l < n,

⊧ (∃x)[¬φ(\overline{x}; \overline{a}_{k}) ∧ φ(\overline{x}; \overline{a}_{l})] ⇔ k < l

2. A theory T has the strict order property if some formula φ(\overline{x}; \overline{y}) has the strict order property. This definition appears in in [Sh-a] p. 68, or [Sh-c] p. 69. Every unstable theory posseses the

strict order property or posseses the independence property (or both). For details see [Sh-a] or [Sh-c].

5.2 Fact 1. Suppose T has the strict order property, with φ(\overline{x}; \overline{y}) witnessing this, and let M ⊧ T. Then φ defines a partial order P_{M} = ⟨|M|^{n}, ≤_{φ}⟩, where n = lg(\overline{y}), the length of \overline{y}, the order being given by \overline{y}_{1} ≤_{φ} \overline{y}_{2} ⇔ M ⊧ φ(\overline{x}; \overline{y}_{1}) → φ(\overline{x}; \overline{y}_{2}). In this order there are arbitrarily long chains.

2. If h : M_{1} → M_{2} is an embedding between two models of T which preserves φ, then h′ : P_{M_{1}} → P_{M_{2}} is an embedding of partial orders, where h′(x_{1}, ⋯, x_{n}) = (h(x_{1}), ⋯, h(x_{n})). Proof: Immediate from the definition. ⊣

5.3 Lemma Suppose T has the strict order property, with φ(\overline{x}; \overline{y}) witnessing this. If L is a given linear order, then there is a model M of T such that L is isomorphic to a suborder of P_{M} and ||M|| = |L| + ℵ_{0}. Proof: As there are arbitrarily long chains with respect to ≤_{φ}, this is an immediate corollary of the compactness theorem. ⊣

5.4 Lemma If there is a partial order of size λ with the property that every linear order of size λ can be embedded into it, then there is a universal linear order in power λ. Proof: Suppose that P = ⟨|P |, ≤⟩ is a partial order of size λ with this property. Divide by the equivalence relation x ∼ y ⇔ x ≤ y ∧ y ≤ x, to obtain P′, a partial order in the strict sense. There is some linear order < on |P′| which extends ≤. Let UO = ⟨|P′|, <⟩. Let L be any linear order, and let h : L → P be an embedding. Whenever x ≠ y are elements of L, h(x) ≁ h(y) in P. Therefore h′ : L → P′ defined by h′(x) = [h(x)] is still an embedding. h′ is an embedding of L into UO. So UO is universal. ⊣

5.5 Theorem Suppose that T has the strict order property, λ is a cardinal, and that T has a universal model (with respect to elementary embeddings) in cardinality λ. Then there exists a universal linear order in cardinality λ. Proof: By 5.4 it is enough to show that there is a partial order of size λ which is universal for linear orders, namely that every linear order of the same size is embedded into it. Let M be a universal model of T, and let φ witness the strict order property. We check that P_{M} is a partial order universal for linear orders. Suppose that L is some linear order of size λ. By 5.3 L is isomorphic so some suborder of P_{M_{L}}. Pick an elementary embedding h : M_{L} → M. In particular, h preserves φ. So by 5.2, there is an embedding of P_{M_{L}} into P_{M}. The restriction of this embedding to (the isomorphic copy of) L is the required embedding. ⊣

5.6 Remark If there is a quantifier free fomula in T which defines a partial order on models of T with arbitrarily long chanins, then also a universal model of T in power λ in the sense of ordinary embedding implies the existence of a universal linear order in λ.

5.7 Conclusions Under the hypotheses of 3.6, there are no universal models in λ for the following theories: Partial orders (ordinary embeddings) Boolean algebras (ordinary embeddings). lattices (ordinary embedding) ordered fields (ordinary embeddings) ordered groups (ordinary embeddings) number theory (elementary embeddings) the theory of p-adic rings (elementary embeddings)

Proof All these theories have the strict order property, and most have a definable order via a quantifier free formula. ⊣

Appendix

We review here several motions and definitions from set theory and model theory. Set theory A set of ordinals C is closed if sup(C ∩ α) = α implies α ∈ C. A club of a cardinal λ is a closed unbounded set of λ. When λ is an uncountable cardinal, the intersection of two clubs contains a club. For details see any standard textbook like [Le]. Model theory A model M is a submodel of N if |M| ⊆ |N| (the universe of M is a subset of the universe of N) and every relation or function of M is the restriction of the respective relation or function of N. A model M is an elementary submodel of N if it is a submodel of N, and for every formula φ with parameters from M, M ⊧ φ ⇔ N ⊧ φ. An embedding of models h : M → N is an elementary embedding if its image is an elementary submodel. A model M is λ-saturated if for every set A ⊆ |M| with |A| < λ and a type p over A, p is realized in M. A model M is saturated if it is ||M||-saturated. A model M is special if there is an increasing sequence of elementary submodels ⟨M_{λ} : λ < ||M|| is a cardinal ⟩, M = ∪_{λ}M_{λ} and every M_{λ} is λ^{+}-saturated.

A formula φ(\overline{x}; \overline{y}) has the independence property if for every n < ω there are sequences \overline{a}_{l} (l < n) such that for every w ⊆ n, ⊧ (∃\overline{x}) ∧_{l<n} φ(\overline{x}; \overline{a}_{l})^{ifl∈w} A first order theory T has the independence property if some formula φ(\overline{x}; \overline{y}) has the independence property. A theory with universal models with respect to ordinary but not elementary embeddings

Let T be the theory of the following model M: the universe is divided into two infinite parts, the domain of the unary predicate P and its complement. The domain of P is the set ⟨x_{i} : i < ω + ω⟩. There are two binary relations R_{1}, R_{2}. For every pair ⟨α, β⟩ of ordinals below ω + ω there is a unique element y ∈ M such that ¬P (y) (think of y as an ordered paire) which satisfies R_{1}(y, x_{α}) ∧ R_{2}(y, x_{β}) iff α < β < ω or α < ω ≤ β or α ≥ ω and β ≥ ω. So for the elements above ω in the P part all possible ordered pairs exist, while those below ω are linearly ordered by the existence of ordered pairs. Let φ(x_{1}; x_{2}) = P (x_{1}) ∧ P (x_{2}) ∧ (∃y)(¬P (y) ∧ R_{1}(y, x_{1}) ∧ R_{2}(y, x_{2}). This formula witnesses that T has the strict order property. By Theorem 3.5 and Theorem 5.5 T has no universal model with respect to elementary embeddings in any regular λ, ℵ_{1} < λ < ℵ_{0}. But with respect to ordinary embeddings T has a universal model in every infinite cardinality λ: let M be any model of T of cardinality λ in which there is a set X = {x_{i} : i < λ} of elements in the domain of P for which all possible ordered pairs exist. If M′ is any other model of cardinality λ, and h is a 1-1 function which maps the domain of P in M′ into X, then h can be completed to an embedding of M′ into M. ⊣ The consistency of not having universal models Let us state it here, for the sake of those who read several times that was is easy but are still interested in the details: Fact If λ regular, V ⊧ GCH, for simplicity, and P is a Cohen forcing which adds λ^{++} Cohen subsets to λ, then in V^{P} there is no universal graph (linear order, model of a complete first order T which is unstable in λ) in power λ^{+}. Proof Suppose to the contrary that there is a universal graph G^{∗} of power λ^{+}. We may assume, without loss of generality, that its universe |G^{∗}| equals λ^{+}. As G is an object of size λ^{+}, it is in some intermediate universe V′, V ⊆ V′ ⊆ V^{P}, such that there are λ^{++} Cohen subsets outside of V′. So without loss of generality, G ∈ V. Let G be the graph with universe λ^{+} defined as follows: fix a 1-1 enumeration ⟨A_{α} : λ ≤ α < λ+⟩ of λ^{+} Cohen subsets of λ. A pair α, β is joined by an edge iff β ≥ λ and α ∈ A_{β}, or α ≥ λ and β ∈ A_{α}. By the universality of G^{∗}, there should exist an embedding h : G → G^{∗}. Consider h λ. This is an object of size λ, and therefore is is some V′, V ⊆ V′ ⊆ V^{P}, where in V′ there are at most λ of the Cohen subsets. For every y ∈ G^{∗}, the set {x ∈ λ : h(x) is joined by an edge to y} is in V′. Pick an α ≥ λ such that A_{α} is not in V′ and set y = h(α) to get a contradiction. ⊣

The same proof is adaptable to the other cases. Guessing clubs Proof of Fact 3.3 Let S_{0} be {δ < λ : cfδ = ℵ_{0}}. Suppose to the contrary that for every sequence \overline{C} as above there is a club C ⊆ λ such that for every δ ∈ S_{0} ∩ C, c_{δ} ⊈ C. We construct by induction on β < ℵ_{1} \overline{C}_{β}, C_{β}. \overline{C}_{β} = ⟨c_{δ}^{β} : δ ∈ S_{0}⟩ is such that for every δ ∈ C_{β} ∩ S_{0}, c_{δ}^{β} is a club of δ of order type ω, and c_{δ}^{β} ⊈ C_{β}. Furthermore, letting c_{δ}^{β} = ⟨α_{n}^{β,δ} : n < ω⟩, where α_{n}^{β,δ} ≤ α_{m}^{β,δ} if n < m, we demand that α_{n}^{β+1,δ} = sup{α_{n}^{β,δ} ∩ C_{β}} if this intersection is non-empty, and α_{n}^{β+1,δ} = 0 otherwise. When β is limit, we demand that α_{n}^{β,δ} = min\{α_{n}^{γ,δ} for γ < β\}. Let \overline{C}_{0} be arbitrary. At the induction step pick C_{β} which demonstrate that \overline{C}_{β} is not as required by the fact and define each c_{d}^{β+1} by the demand above. Note that for club many δ’s the resulting c_{δ}^{β+1} is cofinal in δ, so without loss of generality this is so for every δ ∈ C′_{β+1}.

It is straightforwaed to verify that for all β < γ < ω_{1}, δ ∈ S_{0}

1. For all δ ∈ S_{0} ∩ C_{β}, c^{β,δ} ⊆ δ is a club of δ of order type ω.

2. For all δ ∈ S_{0}, c_{δ}^{β} \ {0} ⊆ C_{β+1}.

3. For all δ ∈ S_{0} ∩ C_{β}, c_{δ}^{β} ⊈ C_{β}

4. α_{n}^{γ,δ} ≤ α_{n}^{β,δ} Let C = ⋂_{β<ω_{1}} C_{β}. Pick δ_{0} ∈ C ∩ S_{0}. Then C ∩ δ is unbounded in δ and of order type ω.

Furthermore, for every β < ω_{1}, c_{δ_{0}}^{β} ⊈ C_{β}.

But on the other hand, there is a β_{0} such that for all β_{0} < β < γ, c_{δ_{0}}^{β} = c_{δ_{0}}^{γ}, because of 4. - a contradiction. ⊣

Now for the case of uncountable cofinality. We recall 3.4 Fact: If cfκ = κ < κ^{+} < λ = cfλ, then there is a sequence \overline{C} = ⟨c_{δ} : δ ∈ S_{κ}^{λ}⟩, S_{κ}^{λ} being the set of members of λ with cofinality κ, where c_{δ} is a club of δ of order type κ with the property that for every club E ⊆ λ the set S_{E} = {δ ∈ S_{κ}^{λ} : c_{δ} ⊆ E} is stationary. Furthermore, if there is a square sequence on S_{κ}^{λ}, \overline{C} can be chosen to be a square sequence. Proof: This proof is actually simpler than that of the previous fact. Start with any sequence \overline{C}_{0} = ⟨c_{δ}^{0} : δ ∈ S_{κ}^{λ}⟩. By induction on i < κ^{+} define \overline{C}_{i} as follows: if \overline{C}_{i} has the property of guessing clubs, we stop. Otherwise there is a club E_{i} such that E_{i} is not guessed stationarily often. This means there is a club C_{i} such that δ ∈ C_{i} implies that c_{i_{δ}} ⊈ E_{i}. We may assume that C_{i} = Ei. Let c_{δ}^{i+1} = c_{δ}^{i} ∩ E_{i}. If i is limit, c_{λ}^{i} = ∩_{j<i}c_{δ}^{j}. Suppose the inductions goes on for κ^{+} steps. Let E = ∩E_{i}. For every δ ∈ E ∩ S_{κ}^{λ}, E ∩ C_{δ}^{0} is a club of δ. Therefore for stationarily many points δ, c^{κ^{+}} is a club of δ, say that this holds for all δ ∈ S ⊆ S_{κ}^{λ}. Clearly, for every δ there is an i such that for every i < j C_{δ}^{i} = c_{δ}^{j}, because the size of c_{δ}^{0} is κ and κ^{+} is regular. But on the other hand, for every δ ∈ S and ⊂< κ^{+}, c_{δ}^{i} ⊈ E_{i}, while c_{δ}^{i+1} ⊆ E_{i}. A contradiction. Thus the induction stops before κ^{+}, and the resultiong sequence guesses clubs.

What about the square property? If there is a square sequence on S_{κ}^{λ}, let in the proof \overline{C}_{0} be a square sequence. Notice that the operation of intersecting the c_{δ} with a club E preserves the property: suppose δ_{1} < δ_{2} amd δ_{1} ∈ acc(γ_{d_{2}}) ∩ E. The clearly δ_{1} ∈ acc(c_{δ_{2}}). Therefore, by the square property, c_{δ_{1}} = γ_{δ_{2}} ∩ δ_{1}. Intersecting both sides of the equation with E yields that c_{δ_{1}} ∩ E = c_{δ_{2}} ∩ E ∩ δ_{1}. Therefore the proof is complete. ⊣

References

[Le] Azriel Levy, Basic Set Theory, Springer Verlag, 1979.

[CK] C. C Chang and J. J. Keisler Model Theory, North Holland 1973.

[Sh-a] Saharon Shelah, Classification Theory and the Number of non-Isomorphic Models, North Holland, 1978.

[Sh-c] Saharon Shelah, Classification Theory and the Number of non-Isomorphic Models, Revised, North Holland Publ. Co., 1990.

[GrSh 174] R. Grossberg and S. Shelah, On universal locally finite groups, Israel J. of Math. 44 , (1983), 289-302.

[Sh-g] Saharon Shelah, Cardinal Arithmetic, to appear.

[Sh 93] Saharon Shelah, Simple Unstable Theories, Annals of Math. Logic 19 (1980), 177–204. [Sh 175] Saharon Shelah, On Universal graphs without instances of CH Annals of Pure and

Applied Logic 26, (1984), 75–87.

[Sh 175a] Saharon Shelah, Universal graphs without instances of CH, revised, Israel J. Math, 70 (1990) 69–81.

[M] Alan H. Mekler, Universal Structures in Power ℵ_{1} Journal of Symbolic Logic, accepted.