SOME POSITIVE RESULTS IN THE CONTEXT OF UNIVERSAL MODELS 9

with them. So assume that A is a maximal antichain of complete conditions and

let N be a rich enough countable elementary submodel with A ∈ N. We claim

A = A ∩ N, so A is countable. For this we have to show that A ∩ N is a maximal

antichain. Let p be any complete condition. By elementarity there is r ∈ N ∩ A

which extends p ∩ N. By Lemma 3.2 there is a common extension of p and r. This

proves the statement we claimed.

We remark that the above result, as it involves ccc forcing iteration, can be

easily generalised to cardinals of the form λ+ for some λ satisfying λλ = λ, as

Mekler does in Theorem 8 of [9]. Therefore the theory of random graphs is amenable

in the sense of Deﬁnition 3.1.

3.2. Triangle-free Graphs. Having established that the theory of graphs

is amenable the next natural question to ask to what extent the amalgamation

condition (∗) was necessary for this conclusion. A very good example to consider

is that of the model completion of the theory of triangle-free graphs. In the sense

of model-theoretic complexity, this theory provides a prototypical example of a

non-simple ’simple enough’ theory, but also because this theory fails the a.c (∗).

Namely

Example 3.5. Let Cl be a graph consisting of the edge (cl, cl+1/mod3), for l 3,

let A = C0 and B = C1. These structures satisfy the premises of the condition a.c

(∗) but any graph extending C0, C1 and C2 contains the triangle {c0, c1, c2}.

Therefore methods of [9] do not apply to triangle-free graphs. Dˇ zamonja and

Shelah proved in [3] that the theory of the model completion of triangle-free graphs

is nevertheless amenable. We explain the main ideas of this proof.

Let us ﬁrst concentrate on ℵ1. In the ﬁnal extension we shall have 2ℵ0 = 2ℵ1 =

ℵ3 and the universality number of the class of the triangle free graphs of size ℵ1

will be ℵ2. The values ℵ2 and ℵ3 are rather flexible, but we concentrate on these

for concreteness. We consider the class K all ﬁnite triangle-free graphs G whose

universe is a subset of ω1 and that have the property that for every non-zero limit

δ ω1, G δ is a ‘reflection’ of G in the sense that for every pair a0, a1 ∈ G δ,

if there is c with alRc for l 2, then there is such c in G δ. We can order

this class by the relation of being an induced subgraph. Let us call this partially

ordered class the approximation family. A petition on the approximation family is

a directed subset of it of size ℵ1. Notice that if we are given a petition Γ then its

union is a graph of size ℵ1, and by directedness, this graph is triangle-free. We

call this graph MΓ. Notice that by reenumerating, every triangle free graph of

size ℵ1 is isomorphic to one whose family of ﬁnite subgraphs forms a petition on

the approximation family. We shall be interested in quorumed petitions, which are

those petitions that contain an isomorphic copy of every ﬁnite triangle-free graph

on ω1 through an isomorphism which moves every ordinal α to an ordinal β of

ﬁnite distance with α. The existence of such quorumed petitions is not something

we prove in ZFC, but we force them.

Let us now describe the forcing. We start with a model of GCH an in it

we denote by T the tree

ω1

ω1. We ﬁrst add ℵ3 many Cohen subsets of ω1 by

countable conditions. Notice that this introduces ℵ3 many branches to T . Call

the resulting universe V . We follow this with an iteration Pα, Qα

˜

: α ω2 in

which each step Qα

˜

is itself an iteration of ω3 steps, of ccc forcing, which we shall

call a block. In each block we shall have a preliminary forcing and an iteration of

9 9

with them. So assume that A is a maximal antichain of complete conditions and

let N be a rich enough countable elementary submodel with A ∈ N. We claim

A = A ∩ N, so A is countable. For this we have to show that A ∩ N is a maximal

antichain. Let p be any complete condition. By elementarity there is r ∈ N ∩ A

which extends p ∩ N. By Lemma 3.2 there is a common extension of p and r. This

proves the statement we claimed.

We remark that the above result, as it involves ccc forcing iteration, can be

easily generalised to cardinals of the form λ+ for some λ satisfying λλ = λ, as

Mekler does in Theorem 8 of [9]. Therefore the theory of random graphs is amenable

in the sense of Deﬁnition 3.1.

3.2. Triangle-free Graphs. Having established that the theory of graphs

is amenable the next natural question to ask to what extent the amalgamation

condition (∗) was necessary for this conclusion. A very good example to consider

is that of the model completion of the theory of triangle-free graphs. In the sense

of model-theoretic complexity, this theory provides a prototypical example of a

non-simple ’simple enough’ theory, but also because this theory fails the a.c (∗).

Namely

Example 3.5. Let Cl be a graph consisting of the edge (cl, cl+1/mod3), for l 3,

let A = C0 and B = C1. These structures satisfy the premises of the condition a.c

(∗) but any graph extending C0, C1 and C2 contains the triangle {c0, c1, c2}.

Therefore methods of [9] do not apply to triangle-free graphs. Dˇ zamonja and

Shelah proved in [3] that the theory of the model completion of triangle-free graphs

is nevertheless amenable. We explain the main ideas of this proof.

Let us ﬁrst concentrate on ℵ1. In the ﬁnal extension we shall have 2ℵ0 = 2ℵ1 =

ℵ3 and the universality number of the class of the triangle free graphs of size ℵ1

will be ℵ2. The values ℵ2 and ℵ3 are rather flexible, but we concentrate on these

for concreteness. We consider the class K all ﬁnite triangle-free graphs G whose

universe is a subset of ω1 and that have the property that for every non-zero limit

δ ω1, G δ is a ‘reflection’ of G in the sense that for every pair a0, a1 ∈ G δ,

if there is c with alRc for l 2, then there is such c in G δ. We can order

this class by the relation of being an induced subgraph. Let us call this partially

ordered class the approximation family. A petition on the approximation family is

a directed subset of it of size ℵ1. Notice that if we are given a petition Γ then its

union is a graph of size ℵ1, and by directedness, this graph is triangle-free. We

call this graph MΓ. Notice that by reenumerating, every triangle free graph of

size ℵ1 is isomorphic to one whose family of ﬁnite subgraphs forms a petition on

the approximation family. We shall be interested in quorumed petitions, which are

those petitions that contain an isomorphic copy of every ﬁnite triangle-free graph

on ω1 through an isomorphism which moves every ordinal α to an ordinal β of

ﬁnite distance with α. The existence of such quorumed petitions is not something

we prove in ZFC, but we force them.

Let us now describe the forcing. We start with a model of GCH an in it

we denote by T the tree

ω1

ω1. We ﬁrst add ℵ3 many Cohen subsets of ω1 by

countable conditions. Notice that this introduces ℵ3 many branches to T . Call

the resulting universe V . We follow this with an iteration Pα, Qα

˜

: α ω2 in

which each step Qα

˜

is itself an iteration of ω3 steps, of ccc forcing, which we shall

call a block. In each block we shall have a preliminary forcing and an iteration of

9 9