6 MIRNA

DZAMONJAˇ

3.1. Graphs. The goal of this section is to present a consistency result show-

ing that it is possible to force over a model of GCH to obtain a model with a large

continuum and a small universal family of graphs at ℵ1. In fact, we shall demon-

strate that the theory of graphs is amenable at ℵ1, in the sense of Deﬁnition 3.1.

The earliest theorem to this extent is in Shelah’s [13], but unfortunately there is an

error, which was noted and corrected by Shelah in [14]. The same year Mekler [9]

found a diﬀerent proof using, unlike [14], a ccc forcing. We shall present Mekler’s

proof. Let T in this section stand for the model completion of the theory of graphs,

so T is a complete model complete theory and we shall show that it is consistent

that CH fails and there is a universal model of T of size ℵ1.

To start with let V be a model of GCH and let us ﬁx a sequence Aα : α ω1

of subsets of ω1 with pairwise intersections countable. Let χ be a large enough

cardinal and we shall work with with elementary substructures of H(χ), ∈, . . .).

The forcing will be an iteration Pα, Qβ

˜

: α ≤ ω2, β ω2 with ﬁnite supports

such that each Pα is ccc. The ﬁrst coordinate will have a special role: it will add

a generic graph

G∗

on ω1 by ﬁnite conditions. Note that

G∗

is a model of T . We

deﬁne the other coordinates by induction on α.

For α ≥ 1, if Pα has been deﬁned and is ccc, suppose that a bookkeeping gives

us a name τ

˜

α, which is a Pα-name of a model of T . We ﬁrst deﬁne Qα.

˜

In V we

ﬁx a continuous sequence

¯

N

α

=

Niα

: i ω1 of countable elementary submodels

of H(χ), ∈, . . . with

Niα

∈

Niα

+1

and Pβ, Qβ

˜

: β α , Pα ∈ N0

α

(so α ∈ N0

α).

For η ω1 let i(η) denote the ﬁrst i such that η ∈

Niα.

Then Qα consists of pairs

q = (Xq, fq) such that X = Xq is a ﬁnite subset of ω1 and f = fq is ﬁnite function

from ω1 to Aα whose range is disjoint from X and which satisﬁes

η ∈ dom(f) =⇒ f(η) ∈

Niαη)+1

(

\

Niαη).(

The idea is that Qα adds an embedding of τα into G∗. To say this precisely, we

deﬁne Pα+1 to consists of elements in Pα ∗ Qα

˜

such that p α decides the τ

˜

α

structure of dom(fp(α)), ran(fp(α)) ⊆ p(0) and fp(α) is an embedding of the τ

˜

α

structure of dom(fp(α)) into p(0).

Easy density arguments show that the P = Pω2 adds an embedding of each τα

into

G∗

and that if the forcing is indeed ccc, we can do the bookkeeping so to cover

all models of T of size ℵ1 in the extension. The main point of the proof is to show

that the forcing has ccc. The proof uses a certain amalgamation property that is

present in the theory of graphs, but not for example in the theory of triangle-free

graphs or the theory of linear orders. We shall describe this amalgamation property

at the point of the proof where we use it.

We need to pass to a dense set of conditions. Say that for 1 ≤ α ≤ ω2, p ∈ Pα

is complete if for every β α and i ω1

: (i) p

β∩Niβ

is a condition and it determines the τβ-structure

˜

of dom(fp(β))

and

: (ii) if r ∈

Niβ

extends p β ∩

Niβ

and 1 ≤ γ β then ran(fr(γ)) ∩ p(0) ⊆

ran(fp(γ)).

It can be proved that the set of complete conditions in Pα is dense, for all α. Both

this and the fact that the forcing is ccc are essentially implied by the following

Lemma 3.2, which is the main point of the argument.

Let N =

¯

N

α

: α ω2 . For the Lemma we need to note that if p ∈ Pα is a

complete condition and N ≺ (H(χ), ∈, N , . . .) countable with α ∈ N, then p ∩ N

6 6

DZAMONJAˇ

3.1. Graphs. The goal of this section is to present a consistency result show-

ing that it is possible to force over a model of GCH to obtain a model with a large

continuum and a small universal family of graphs at ℵ1. In fact, we shall demon-

strate that the theory of graphs is amenable at ℵ1, in the sense of Deﬁnition 3.1.

The earliest theorem to this extent is in Shelah’s [13], but unfortunately there is an

error, which was noted and corrected by Shelah in [14]. The same year Mekler [9]

found a diﬀerent proof using, unlike [14], a ccc forcing. We shall present Mekler’s

proof. Let T in this section stand for the model completion of the theory of graphs,

so T is a complete model complete theory and we shall show that it is consistent

that CH fails and there is a universal model of T of size ℵ1.

To start with let V be a model of GCH and let us ﬁx a sequence Aα : α ω1

of subsets of ω1 with pairwise intersections countable. Let χ be a large enough

cardinal and we shall work with with elementary substructures of H(χ), ∈, . . .).

The forcing will be an iteration Pα, Qβ

˜

: α ≤ ω2, β ω2 with ﬁnite supports

such that each Pα is ccc. The ﬁrst coordinate will have a special role: it will add

a generic graph

G∗

on ω1 by ﬁnite conditions. Note that

G∗

is a model of T . We

deﬁne the other coordinates by induction on α.

For α ≥ 1, if Pα has been deﬁned and is ccc, suppose that a bookkeeping gives

us a name τ

˜

α, which is a Pα-name of a model of T . We ﬁrst deﬁne Qα.

˜

In V we

ﬁx a continuous sequence

¯

N

α

=

Niα

: i ω1 of countable elementary submodels

of H(χ), ∈, . . . with

Niα

∈

Niα

+1

and Pβ, Qβ

˜

: β α , Pα ∈ N0

α

(so α ∈ N0

α).

For η ω1 let i(η) denote the ﬁrst i such that η ∈

Niα.

Then Qα consists of pairs

q = (Xq, fq) such that X = Xq is a ﬁnite subset of ω1 and f = fq is ﬁnite function

from ω1 to Aα whose range is disjoint from X and which satisﬁes

η ∈ dom(f) =⇒ f(η) ∈

Niαη)+1

(

\

Niαη).(

The idea is that Qα adds an embedding of τα into G∗. To say this precisely, we

deﬁne Pα+1 to consists of elements in Pα ∗ Qα

˜

such that p α decides the τ

˜

α

structure of dom(fp(α)), ran(fp(α)) ⊆ p(0) and fp(α) is an embedding of the τ

˜

α

structure of dom(fp(α)) into p(0).

Easy density arguments show that the P = Pω2 adds an embedding of each τα

into

G∗

and that if the forcing is indeed ccc, we can do the bookkeeping so to cover

all models of T of size ℵ1 in the extension. The main point of the proof is to show

that the forcing has ccc. The proof uses a certain amalgamation property that is

present in the theory of graphs, but not for example in the theory of triangle-free

graphs or the theory of linear orders. We shall describe this amalgamation property

at the point of the proof where we use it.

We need to pass to a dense set of conditions. Say that for 1 ≤ α ≤ ω2, p ∈ Pα

is complete if for every β α and i ω1

: (i) p

β∩Niβ

is a condition and it determines the τβ-structure

˜

of dom(fp(β))

and

: (ii) if r ∈

Niβ

extends p β ∩

Niβ

and 1 ≤ γ β then ran(fr(γ)) ∩ p(0) ⊆

ran(fp(γ)).

It can be proved that the set of complete conditions in Pα is dense, for all α. Both

this and the fact that the forcing is ccc are essentially implied by the following

Lemma 3.2, which is the main point of the argument.

Let N =

¯

N

α

: α ω2 . For the Lemma we need to note that if p ∈ Pα is a

complete condition and N ≺ (H(χ), ∈, N , . . .) countable with α ∈ N, then p ∩ N

6 6