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 ﬁrst 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 diﬀerent from the theory of the uncountable ones - as is most strikingly wit-

nessed by the well developed classiﬁcation 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. Speciﬁcally, 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 Deﬁnition 2.1. In fact, the concept of saturation was ﬁrst 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 iﬀ 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

ﬁnite 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 ﬁnitely 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,

4 4

DZAMONJAˇ

κ++

Cohen subsets to V . Then in V [G], in power

κ+,

there is no universal graph,

linear order, or generally model of a complete ﬁrst 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 diﬀerent from the theory of the uncountable ones - as is most strikingly wit-

nessed by the well developed classiﬁcation 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. Speciﬁcally, 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 Deﬁnition 2.1. In fact, the concept of saturation was ﬁrst 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 iﬀ 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

ﬁnite 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 ﬁnitely 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,

4 4