4 MIRNA DZAMONJAˇ κ++ Cohen subsets to V . Then in V [G], in power κ+, there is no universal graph, linear order, or generally model of a complete first order T which is unstable in κ. (3) (Kojman-Shelah, [7]) Suppose κ is a regular cardinal and there is some cardinal λ such that λ+ κ 2λ. Then there is no universal linear order of cardinality κ. Note that if T is stable in κ then it follows by an argument analogous to that of Theorem 2.8 below that T has a saturated model of size κ. 2.2. Countable universal models. Countable universal models are abun- dant in mathematics. For example, in addition to the examples we mentioned in the Introduction there are examples in topology: any countable dense subset of the Urysohn space is countably universal in the class of metric spaces with almost isometric embedding. In model theory however, the theory of countable models is different from the theory of the uncountable ones - as is most strikingly wit- nessed by the well developed classification theory using the number of pairwise non-isomorphic models [11], versus the still unresolved Vaught conjecture about countable models. In the theory of universal models it is similarly the case that countable models have a special role. Specifically, the methods presented in the rest of this paper tend to apply only to uncountable models. However, this is not the case with the concept of saturated models, which makes perfect sense in the case of κ = ℵ0, see Definition 2.1. In fact, the concept of saturation was first introduced in the countable case, by Vaught. Exactly the same proof as in the uncountable case applies to show that saturated models are universal. For example, a well known example of a countable universal model is the linear order of the rationals, and the rationals are an example of a saturated model. In the case of countable models there is a syntactic characterisation of the existence of saturated models, due to Vaught in [17]. It also appears as Theorem 2.3.7 in [1]. Theorem 2.8. (Vaught, [17]) T has a countable saturated model iff for every n ω, T has only countably many complete types in n-variables. Proof. In the forward direction, let M be a countable saturated model of T . Then for every n and complete type Γ in n variables, Γ is realised by an n-tuple in M. Since there are only countably many such tuples and none of them can realise more than one complete type, the conclusion follows. In the other direction, we shall expand T to a maximal consistent theory T ∗ in an expanded language, such that any countable model of T ∗ gives us a saturated model of T . Let us form the language L∗ by adding countably many new constant symbols {cn : n ω} to L. Let {ϕn : n ω} be an enumeration of all sentences in L∗. For every m-element subset Y of {cn : n ω}, the complete types Γ(x) of T in LY are in one-to-one correspondence with the complete types Σ(x0, . . . xm−1, x) of T in L, and hence there are only countably many of them by the assumption. We let {Γn(x) : n ω} enumerate all such types Γ(x), where Y ranges over all finite subsets of {cn : n ω}. By induction on n ω we choose an increasing sequence Tn of consistent theories with T0 = T , such that : (1) each Tn contains only finitely many symbols from L∗ \ L, : (2) either ϕn ∈ Tn+1 or ¬ϕn ∈ Tn+1, : (3) if ϕn ∈ Tn+1 and ϕn = (∃x)ψ(x), then ψ(c) ∈ Tn+1 for some c ∈ L∗ \L,

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2011 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.