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 Definition 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 (∗).
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. 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 first concentrate on ℵ1. In the final 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 finite 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 finite 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 finite triangle-free graph
on ω1 through an isomorphism which moves every ordinal α to an ordinal β of
finite 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. We first 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α,
: α ω2 in
which each step
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
Previous Page Next Page