10 MIRNA
DZAMONJAˇ
length ω3. We first describe the iteration. It will have two kinds of coordinates.
In each coordinate of the first kind. of it we are given a name for a petition Γ on
the approximation family and we force to embed MΓ
˜
into MΓ∗
˜
for some
quorumed˜
petition Γ∗.
˜that
By remarks above, for our final universality result it will be sufficient
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 V
Pα
. In fact we shall assure that there is in V
Pα+1
a single triangle-free graph
Gα
∗
on ω1 which embeds all MΓ∗ for quorumed petitions
Γ∗
in V
Pα
. 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
embeds into
Gα.∗
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 [3]. Notice that checking that it is true
really uses the definition 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
version of
λ+-cc
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 [9].
The price we have to pay is that the final 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 [7] 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
10 10
DZAMONJAˇ
length ω3. We first describe the iteration. It will have two kinds of coordinates.
In each coordinate of the first kind. of it we are given a name for a petition Γ on
the approximation family and we force to embed MΓ
˜
into MΓ∗
˜
for some
quorumed˜
petition Γ∗.
˜that
By remarks above, for our final universality result it will be sufficient
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 V
Pα
. In fact we shall assure that there is in V
Pα+1
a single triangle-free graph
Gα
∗
on ω1 which embeds all MΓ∗ for quorumed petitions
Γ∗
in V
Pα
. 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
embeds into
Gα.∗
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 [3]. Notice that checking that it is true
really uses the definition 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
version of
λ+-cc
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 [9].
The price we have to pay is that the final 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 [7] 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
10 10
