length ω3. We ﬁrst describe the iteration. It will have two kinds of coordinates.
In each coordinate of the ﬁrst kind. of it we are given a name for a petition Γ on
the approximation family and we force to embed MΓ
By remarks above, for our ﬁnal universality result it will be suﬃcient
to ensure there are ℵ2 triangle-free graphs on ω1 which embed all MΓ∗ for
quorumed petitions Γ∗. By bookkeeping, we shall at each stage α ω2 of the main
iteration assure by Qα
of forcing that we have dealt with all quorumed petitions
. In fact we shall assure that there is in V
a single triangle-free graph
on ω1 which embeds all MΓ∗ for quorumed petitions
. This is where
the preliminary forcing of the block α comes in: in it we introduce a system Sα of
members of the approximation family indexed by the nodes in T in a such a way
that each branch through T gives a petition in the approximation family. It is easy
to see that the union of this system is a triangle-free graph on ω1, which will be
our Gα. ∗ In the second kind of coordinates in the block α we shall be embedding
a quorumed petition H
given by the bookkeeping into the subsystem of Sα given
by the elements indexed by the nodes on some branch of T . This assures that MH
The main point of the proof is to make sure that each individual forcing in a
block is ccc, and in assuring so in the second kind of coordinates we get to use an
amalgamation property possessed by the elements of the approximation family K:
Suppose that M0, N0, M1, M2, N1, N2 and M are in K such that
• M0 = M1 ∩ M2 and M1 is isomorphic with M2 by an isomorphism which
is identity on M0,
• N0 = N1 ∩ N2 and N1 is isomorphic with N2 by an isomorphism which is
identity on N0,
• each Mi is an induced subgraph of the corresponding Ni and the universe
of Ml consists of even ordinals in the universe of Nl,
• there are limit ordinals δ0 δ1 δ2 such that Nl ⊆ δl for each l 3,
• the universe of M is contained in the even ordinals and M1, M2 are induced
subgraphs of M.
Then there is N ∈ K whose induced subgraphs include M, N1 and N2.
This property is called workability in . Notice that checking that it is true
really uses the deﬁnition of the approximation family, not only the properties of
the class of triangle-free graphs.
The proof in the case
for λ =
in place of ℵ1 has to deal with a strong
needed in order to iterate, which introduces additional complica-
tions which we shall not describe here. The structure of the proof as described
above uses a tree of models rather than a linearly organised structure like in .
The price we have to pay is that the ﬁnal universe does not have one universal
model, rather just a small universal family. The following question is still open:
Question 3.6. Is it consistent to have a universal triangle-free graph on ℵ1
and not CH?
3.3. Linear orders. The next step to consider in our increasing level of com-
plexity of theories is a theory that does not have a workable approximation family.
Such a theory is the theory of dense linear orders. Namely, the main result of
Kojman-Shelah  is that this theory is highly non-amenable, and the proof we
presented for triangle-free graphs cannot be adopted to this case- as it would show