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 Definition 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 different 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 fix a sequence : α ω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α,
˜
: α ω2, β ω2 with finite supports
such that each is ccc. The first coordinate will have a special role: it will add
a generic graph
G∗
on ω1 by finite conditions. Note that
G∗
is a model of T . We
define the other coordinates by induction on α.
For α 1, if has been defined and is ccc, suppose that a bookkeeping gives
us a name τ
˜
α, which is a Pα-name of a model of T . We first define Qα.
˜
In V we
fix a continuous sequence
¯
N
α
=
Niα
: i ω1 of countable elementary submodels
of H(χ), ∈, . . . with
Niα

Niα
+1
and Pβ,
˜
: β α , N0
α
(so α N0
α).
For η ω1 let i(η) denote the first i such that η
Niα.
Then consists of pairs
q = (Xq, fq) such that X = Xq is a finite subset of ω1 and f = fq is finite function
from ω1 to whose range is disjoint from X and which satisfies
η dom(f) =⇒ f(η)
Niαη)+1
(
\
Niαη).(
The idea is that adds an embedding of τα into G∗. To say this precisely, we
define Pα+1 to consists of elements in
˜
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
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 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 is a
complete condition and N (H(χ), ∈, N , . . .) countable with α N, then p N
6 6
Previous Page Next Page