8 MIRNA

DZAMONJAˇ

no such choice is possible, stop the induction. Note that m ≤ k =⇒ γm ≤ γk and

that the induction must be stopped at some stage k∗ as all ordinals that appear as

unused at any stage come from the ﬁnite set

γ∈dom(p)\{0}

dom(fp(γ)) (and once

an ordinal is used it remains so). Let

γ∗

= γk∗ .

We shall now proceed to deﬁne a condition q in Nγ∗ ∩

γ∗.

We shall need the

following claim.

Claim 3.4. For all k ≤

k∗,

m≤k

Nm ∩ γk ⊆ Nk.

Proof of the Claim. The proof is by induction on k. If k = 0, the situation is

clear. For the case of k + 1, we have by the induction hypothesis that for m ≤ k,

Nm ∩ γk ⊆ Nk. Since γk+1 ≤ γk, certainly Nm ∩ γk+1 ⊆ Nk and hence it suﬃces to

show that Nk ∩ γk+1 ⊆ Nk+1. This conclusion follows by the choice of Nk+1.

3.4

Suppose that k ≤

k∗

and m ≤ k. Then rm ∈ Nm so all the ﬁnitely many

ordinals involved in the construction of rm γk are in Nm ∩ γk, and hence in Nk

by Claim 3.4. Therefore rm γk ∈ Nk.

At this point of the proof we shall get to use the Amalgamation Condition

(∗), which we deﬁne in terms of a partially ordered class (K, ≤) of structures:

(K, ≤) satisﬁes a.c. (∗) if for any elements A, B, {Ci : i ∈ I} of K satisfying

• any two of these structures agree on their intersection

• whenever i = j then either Ci ∩ Cj ⊆ A or Ci ∩ Cj ⊆ B,

there is a structure in K which extends all A, B, {Ci : i ∈ I}.

Obviously, the class of graphs with the induced subgraph relation satisﬁes the

a.c. (∗) since we can simply take a union of all the graphs

involved.4

Suppose now that β = β ∈ ak∗ . By the induction hypothesis either Aβ ∩

Aβ δk∗ , in which case

sβ∗

k ∩

sβ∗

k ⊆ p(0) or Aβ ∩ Aβ ⊆ δk∗ and so

sβ∗

k ∩

sβ∗

k ⊆

rk∗ (0). This says that, according to the a.c. (∗) property, we can deﬁne a graph

that extends p(0)∩δk∗ ∪rk∗ (0)∪

β∈ak∗

sβ∗

k ∩δk∗ . Let s be such a graph. We deﬁne

q , a candidate for a condition in Pα. Let q (0) = s and for β ∈

k≤k∗

dom(rk)∪ak∗

let q (β) = p(β) ∩ δk∗ ∪

k≤k∗

rk(β). Note that q as a function is an element of

Nk∗ . We now claim that q is a condition in Pα. By induction on 1 ≤ β ≤ α we

prove that q β ∈ Pβ. For β = 1 this follows from the choice of s and for β limit

this is clear. Suppose that β = γ + 1 and γ is in dom(q ). If γ / ∈ dom(p) then

γ ∈

k≤k∗

dom(rk) and q (γ) =

k≤k∗

rk(γ). This is well deﬁned by the choice

of

rk’s. If γ ∈ dom(p) \

k≤k∗

dom(rk), then q (γ) = p(γ) ∩ δk∗ , so q β is a

condition because p satisﬁes (i) in the deﬁnition of completeness. Finally it may

happen that γ ∈ dom(p) ∩

k≤k∗

dom(rk). In particular we have β ∈ ak∗ . Let k be

maximal such that γ ≤ γk. We claim that dom(fp(γ)) ∩ δk∗ = dom(fp(γ)) ∩ δm. If

this were not to be the case then at the stage k of the induction there would be an

unused ordinal in dom(fp(γ)), so γ = γk+1, a contradiction. Having established the

existence of q we now need to keep going to extend to a condition which extends

each rk. This is done in stages using the assumptions of completeness, for which

we refer the reader to the original article.

3.2

We now indicate how Lemma 3.2 implies that the forcing is ccc. We assume

that we have proved that the set of complete conditions is dense, so we only work

4In

[9], Lemma 1, it is shown that a better known P(3−) amalgamation property implies

a.c. (∗).

8 8

DZAMONJAˇ

no such choice is possible, stop the induction. Note that m ≤ k =⇒ γm ≤ γk and

that the induction must be stopped at some stage k∗ as all ordinals that appear as

unused at any stage come from the ﬁnite set

γ∈dom(p)\{0}

dom(fp(γ)) (and once

an ordinal is used it remains so). Let

γ∗

= γk∗ .

We shall now proceed to deﬁne a condition q in Nγ∗ ∩

γ∗.

We shall need the

following claim.

Claim 3.4. For all k ≤

k∗,

m≤k

Nm ∩ γk ⊆ Nk.

Proof of the Claim. The proof is by induction on k. If k = 0, the situation is

clear. For the case of k + 1, we have by the induction hypothesis that for m ≤ k,

Nm ∩ γk ⊆ Nk. Since γk+1 ≤ γk, certainly Nm ∩ γk+1 ⊆ Nk and hence it suﬃces to

show that Nk ∩ γk+1 ⊆ Nk+1. This conclusion follows by the choice of Nk+1.

3.4

Suppose that k ≤

k∗

and m ≤ k. Then rm ∈ Nm so all the ﬁnitely many

ordinals involved in the construction of rm γk are in Nm ∩ γk, and hence in Nk

by Claim 3.4. Therefore rm γk ∈ Nk.

At this point of the proof we shall get to use the Amalgamation Condition

(∗), which we deﬁne in terms of a partially ordered class (K, ≤) of structures:

(K, ≤) satisﬁes a.c. (∗) if for any elements A, B, {Ci : i ∈ I} of K satisfying

• any two of these structures agree on their intersection

• whenever i = j then either Ci ∩ Cj ⊆ A or Ci ∩ Cj ⊆ B,

there is a structure in K which extends all A, B, {Ci : i ∈ I}.

Obviously, the class of graphs with the induced subgraph relation satisﬁes the

a.c. (∗) since we can simply take a union of all the graphs

involved.4

Suppose now that β = β ∈ ak∗ . By the induction hypothesis either Aβ ∩

Aβ δk∗ , in which case

sβ∗

k ∩

sβ∗

k ⊆ p(0) or Aβ ∩ Aβ ⊆ δk∗ and so

sβ∗

k ∩

sβ∗

k ⊆

rk∗ (0). This says that, according to the a.c. (∗) property, we can deﬁne a graph

that extends p(0)∩δk∗ ∪rk∗ (0)∪

β∈ak∗

sβ∗

k ∩δk∗ . Let s be such a graph. We deﬁne

q , a candidate for a condition in Pα. Let q (0) = s and for β ∈

k≤k∗

dom(rk)∪ak∗

let q (β) = p(β) ∩ δk∗ ∪

k≤k∗

rk(β). Note that q as a function is an element of

Nk∗ . We now claim that q is a condition in Pα. By induction on 1 ≤ β ≤ α we

prove that q β ∈ Pβ. For β = 1 this follows from the choice of s and for β limit

this is clear. Suppose that β = γ + 1 and γ is in dom(q ). If γ / ∈ dom(p) then

γ ∈

k≤k∗

dom(rk) and q (γ) =

k≤k∗

rk(γ). This is well deﬁned by the choice

of

rk’s. If γ ∈ dom(p) \

k≤k∗

dom(rk), then q (γ) = p(γ) ∩ δk∗ , so q β is a

condition because p satisﬁes (i) in the deﬁnition of completeness. Finally it may

happen that γ ∈ dom(p) ∩

k≤k∗

dom(rk). In particular we have β ∈ ak∗ . Let k be

maximal such that γ ≤ γk. We claim that dom(fp(γ)) ∩ δk∗ = dom(fp(γ)) ∩ δm. If

this were not to be the case then at the stage k of the induction there would be an

unused ordinal in dom(fp(γ)), so γ = γk+1, a contradiction. Having established the

existence of q we now need to keep going to extend to a condition which extends

each rk. This is done in stages using the assumptions of completeness, for which

we refer the reader to the original article.

3.2

We now indicate how Lemma 3.2 implies that the forcing is ccc. We assume

that we have proved that the set of complete conditions is dense, so we only work

4In

[9], Lemma 1, it is shown that a better known P(3−) amalgamation property implies

a.c. (∗).

8 8