10 MIRNA

DZAMONJAˇ

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Γ

˜

into MΓ∗

˜

for some

quorumed˜

petition Γ∗.

˜that

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 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 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

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 ﬁ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 [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 ﬁ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Γ

˜

into MΓ∗

˜

for some

quorumed˜

petition Γ∗.

˜that

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 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 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

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 ﬁ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 [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