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 , but unfortunately there is an
error, which was noted and corrected by Shelah in . The same year Mekler 
found a diﬀerent proof using, unlike , 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
on ω1 by ﬁnite conditions. Note that
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
: i ω1 of countable elementary submodels
of H(χ), ∈, . . . with
and Pβ, Qβ
: β α , Pα ∈ N0
(so α ∈ N0
For η ω1 let i(η) denote the ﬁrst i such that η ∈
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(η) ∈
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 τα
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
is a condition and it determines the τβ-structure
: (ii) if r ∈
extends p β ∩
and 1 ≤ γ β then ran(fr(γ)) ∩ p(0) ⊆
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 =
: α ω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