MORE SET-THEORY FOR TOPOLOGISTS

ALAN DOW

Abstract. Basic applications in topology of ♢, elementary submodels and forcing are illustrated. Finite and countable supported forcing iterations are reviewed. Also there are two new applications of Prikry forcing to preservation results.

This article was written for those who will be attending the 1995 Summer Conference on General Topology and Applications. During the conference I will no doubt not be able to cover all of the material that is in this article, but the article and the talks are meant to give a broad introduction of the tools of set-theory that are most commonly applied to General Topology (as judged by me of course). I have tried to illustrate the techniques in the context of proving results which are interesting in their own right. We cover some basic combinatorial tools such as ♢ and □ and discuss mad families, gaps and coherent sequences as well as giving proofs of two interesting results from ♢ in section 3. In section 4 we begin a more detailed, but introductory, discussion of Logic and Model Theory, although set-theorists would say that it is just set-theory. In section 5 we prove some basic results about sets in which we use elementary submodels in the proofs for illustrative purposes. In section 6 we very briefly discuss large cardinals and finally in section 7 we begin forcing. In section 8 we do two case studies of iterated forcing, the first with finite supported ccc forcing, and the second with countable support proper forcing. In section 9, we are attempting to look to the future of set-theory in topology and we are fortunate to be able to present a result of Avraham and Todorcevic which uses Shelah’s method of D-completeness. Two new results in the paper concern (the failure of) certain preservation properties in forcing. A first countable non-Lindelöf space is constructed which can be made Lindelöf with cardinal preserving forcing and a non-separable space is found which can be made separable by a cardinal preserving forcing. These answer questions from the Open Problems in General Topology book.

1. Basics

Recall that an ordinal α is equal to the set of all ordinals β which are less than α (where 0 is the empty set and, e.g. 1 = {0}, 2 = {0, {0}} etc. . A cardinal is an initial ordinal, i.e. an ordinal α such that if β is less than α then there is no function from β onto α. However the least ordinal (in fact cardinal) δ which will map cofinally into α is called the cofinality, denoted cf(α), of α. A cardinal or ordinal is called regular if it is equal to its cofinality and singular otherwise. If an ordinal α (usually a cardinal) has uncountable cofinality then the set of closed and unbounded subsets of α generate a filter, called the cub or club filter. A subset S of α is stationary in α if it meets every set which is cub in α. The ideal which is dual to the cub filter is called the non-stationary ideal and, for a given α, is denoted NS_{α}. One of the most basic facts about stationary sets is the pressing down lemma which we postpone to Lemma 5.6. First one of the most basic facts about cubs.

1980 Mathematics Subject Classification (1985 Revision). Primary 54-02, 54A35.

Key words and phrases. diamond, elementary submodels, forcing.

Proposition 1.1. If cf(α) > ω, then the cub filter on α is cf(α)-complete, that is, the intersection any family of fewer than cf(α) many cubs in α is again a cub.

Proof. Let δ < cf(α) and fix a family {C_{β} : β < δ} of cubs in α. Of course the intersection of any family of closed sets is again closed hence it suffices to show that ⋂_{β<δ} C_{β} is unbounded. Fix any γ_{0} < α. Inductively define γ_{n+1} > γ_{n}, so that C_{β} ∩ [γ_{n}, γ_{n+1}) is not empty for each β < δ. Note that, given γ_{n}, C_{β} − γ_{n} is not empty for each β < δ, and, since δ < cf(α), {min(C_{β} − γ_{n}) : β < δ} is not cofinal in α. Therefore γ_{n+1} can be found. Next we use the fact that cf(α) > ω to deduce that {γ_{n} : n ∈ ω} is not cofinal in α. Let ξ be the supremum of the sequence {γ_{n} : n ∈ ω} (i.e. ξ is the minimum of the non-empty set of ordinals which are greater than every γ_{n}; in fact, ξ is equal to ∪_{n}γ_{n}). To finish the proof, we show that ξ ∈ C_{β} for each β < δ. Indeed, for each n, choose ξ(β, n) ∈ C_{β} ∩[γ_{n}, γ_{n+1}) and observe that {ξ(β, n) : n ∈ ω} is cofinal in ξ. Since {ξ(β, n) : n ∈ ω} is contained in the closed set C_{β} it follows that ξ ∈ C_{β}.

The standard notation, see [6], for the set of finite subsets of a set I, is [I]^{<ω}, and similarly, [I]^{λ} and [I]^{<λ} denote the set of sets of cardinality λ, and less than λ, respectively. Kunen uses lim(α) to indicate that α is a limit ordinal and we will use Lim (α) to denote the set of limit ordinals less than α. The context should be sufficient to decide if κ^{λ} is used to denote cardinal exponentiation or the set of functions from λ into κ although sometimes we will use ^{λ}κ to denote this latter set. If f and g are in ^{ω}ω, then f <^{∗} g means that {n ∈ ω : f(n) ≥ g(n)} is finite. Similarly, if A, B are sets, then A ⊂^{∗} B indicates that A − B is finite.

Lemma 1.2. If g : [κ]^{<ω} → κ, for a regular cardinal κ, then there is a cub C in κ such that α ∈ C implies that g(F) < α for all F ∈ [α]^{<ω}.

Proof. We first reduce to a function h : κ → κ. For each α < κ, [α]^{<ω} has cardinality less than κ, hence there is an ξ < κ such that g(F) < ξ for all F ∈ [α]^{<ω}; let h(α) be the minimal such ξ which is at least as large as α. Note that, by the minimality condition, if α < β, then h(α) ≤ h(β). We can simply define C to be the set of α such that h(β) < α for all β < α. We show that C is closed and unbounded in κ. First assume that C ∩ α is cofinal in α. Let β < α and since C ∩ α is cofinal in α, there is a γ ∈ C such that β < γ < α. But now, γ in C implies that g(β) < γ. Thus, α ∈ C and C is closed. Now to show that C is unbounded. Fix any ξ_{0} ∈ κ and define ξ_{n+1} = h(ξ_{n}) + 1. Let α be the supremum of the increasing sequence {ξ_{n} : n ∈ ω} and let β < α. Since ξ_{n} is cofinal in α, there is an n such that β < ξ_{n}, in which case, h(β) ≤ h(ξ_{n}) < ξ_{n+1} < α, hence α is in C and C is unbounded.

Definition 1.3. ♢^{∗} is the statement that there is a sequence {A_{α} : α ∈ ω_{1}} such that A_{α} is countable and for each X ⊂ ω_{1}, S_{X} = {α : X ∩ α ∈ A_{α}} is a cub.

♢ is the statement that there is a sequence {a_{α} : α ∈ ω_{1}} such that for each X the set S_{X} = {α : X ∩ α = a_{α}} is stationary.

Kunen has shown that ♢^{∗} implies ♢. See Lemma 5.10 for the consistency of ♢^{∗}. Standard coding techniques (e.g. in this case, the function Φ introduced below) allow things like ♢ to take many forms.

Proposition 1.4. ♢ implies there is a sequence {a_{α} : α ∈ Lim (ω_{1})} so that (1) for each function f ∈ ^{ω_{1}}ω_{1}, S_{f} = {α : f ↾ α = a_{α}} is stationary;

(2) for each n ∈ ω and each A ⊂ [ω_{1}]^{<ω}, S_{A} = {α : A ∩ [α]^{<ω} = a_{α}} is stationary.

Proof. Let Φ be any bijection from ω_{1} × ω_{1} to ω_{1}. If f ∈ ^{ω_{1}}ω_{1}, then f can be regarded as a subset of ω_{1} × ω_{1}; hence Φ(f) can be regarded as a subset of ω_{1}. The set S_{Φ(f)} = {α : Φ(f) ∩ α = a_{α}} is stationary. We finish by showing that coding behaves well on a cub. First of all, there is a cub C_{1} so that Φ(α × α) ⊂ α for each α ∈ C_{1} (see Lemma 1.2). In addition, for each γ, we can define g(γ) to be minimal so that there is a pair (α, β) ∈ g(γ) × g(γ) so that Φ(α, β) = γ (if γ happened not to be in the range of Φ, set g(γ) = 0). So we may as well asume that g(γ) < α for all γ < α and α ∈ C_{1}. Next, again by Lemma 1.2, there is a cub C_{2} such that f ↾ α : α → α for all α ∈ C_{2}, i.e. f(γ) < α for all γ < α. So if α is in the stationary set C_{1} ∩ C_{2} ∩ S_{Φ(f)}, it follows that

Φ(f ↾ α) = Φ(f ∩ (α × α)) = Φ(f) ∩ α = a_{α} .

Therefore we will get the desired sequence {f_{α} : α < ω_{1}} if we define it as follows. Let I = {α ∈ Lim (ω_{1}) : Φ^{−1}(a_{α}) is a graph of a function from α to α }, and for α ∈ I, let f_{α} ⊂ α × α be such that Φ(f_{α}) = a_{α}. For α ∈ Lim (ω_{1}) − I, fix any function f_{α} from α to α. The previous paragraph shows that for each f : ω_{1} → ω_{1} there is a stationary subset of I (C_{1} ∩ C_{2} ∩ S_{Φ(f)}) so that for each α in this set, f ↾ α = f_{α}.

2. βω to βω_{2}

In this section we give some applications of the previous concepts to Stone-Čech compactifications of discrete spaces as well as introduce some concepts which we will need later. Recall that βκ is simply the Stone space of ultrafilters of the Boolean algebra P(κ) where the fixed ultrafilter {A ⊂ κ : α ∈ A} is identified with α. We let κ^{∗} denote the remainder βκ − κ and for a set A ⊂ κ, A^{∗} is the clopen subset of κ^{∗} consisting of those ultrafilters on κ for which A is an element.

Recall that a mad family on ω is a set A of infinite subsets of ω such that the members of A are almost disjoint from one another (i.e. have finite intersection) and are maximal in this sense (i.e. for each infinite Y ⊂ ω, there is an A ∈ A such that |Y ∩ A| = ω). Recall that the cardinal 𝔞 is the least cardinal such that there is a mad family of that size. Other well studied cardinals are: 𝔟 (the least cardinality of an unbounded family in (ω^{ω}, <^{∗})), 𝔲 (the minimum character of an ultrafilter on ω), 𝔡 (the minimum cardinality of a cofinal family in (ω^{ω}, <)), 𝔱 (the least cardinal of a maximal descending mod finite family of infinite subsets of ω), and 𝔭 (the least cardinal of a filter base B of infinite subsets of ω which has no pseudo-intersection, i.e. no infinite Y such that Y − B is finite for each B ∈ B).

Proposition 2.1. There is a mad family of cardinality 𝔠.

Proof. A standard and useful trick is to choose some other countable set to work with instead of ω. Consider the set ⋃_{n} ^{n}2 = 2^{<ω}, where ^{n}2 denotes the set of functions from n into 2. For each f ∈ ^{ω}2, let A_{f} = {f ↾ n : n ∈ ω}. It is easy to see that A_{f} ∩ A_{g} is finite for each f ≠ g in 2^{ω}. So we can take A to be any maximal almost disjoint family containing {A_{f} : f ∈ 2^{ω}}.

We feel compelled to mention P. Simon’s wonderful result on products of compact Fréchet spaces. Call an almost disjoint family, A, \underline{nowhere mad} if for each X ⊂ ω such that X is not in the ideal generated by A∪[ω]^{<ω}, X contains an infinite subset which is almost disjoint from every member of A. There is a natural first countable locally compact topological space associated with an almost disjoint family A: we put a topology on ω∪A in which ω is dense open discrete and {A}∪{A−n : n ∈ ω} is a neighbourhood base for the point A. This space is pseudocompact iff A is a mad family and the one point compactification is Fréchet iff A is nowhere mad.

Proposition 2.2. There are compact Fréchet spaces X, Y such that X × Y is not Fréchet.

Proof. The plan is to show that there is a mad family A which can be partitioned into two nowhere mad families. It will suffice, of course, to find a set X ⊂ ω and a mad family A so that A_{X} = {A ∩ X : A ∈ A} − [ω]^{<ω} has such a partition.

This is remarkably simple but quite clever. Let A be a mad family of cardinality 𝔠 and let {A_{f} : f ∈ 2^{ω}} be an enumeration. For each n, we have the partition P_{n}, Q_{n}, where A_{f} ∈ P_{n} iff f(n) = 0. Assuming that there is no mad family and partition as desired we inductively define infinite sets X_{n} for n ∈ ω. First of all, by assumption, either P_{0} or Q_{0} is “somewhere” mad so fix a set X_{0} witnessing this. Now either (P_{0})_{X_{0}} is an infinite mad family on X_{0}, in which case we set g(0) = 0, or (Q_{0})_{X_{0}} is one and we set g(0) = 1. At stage n < ω, we have chosen X_{n−1}, and for each k < n, g(k) = 0 implies that (P_{k})_{X_{n−1}} is an infinite mad family on X_{n−1} and g(k) = 1 implies that (Q_{k})_{X_{n−1}} is such a family. Just as in the n = 0 step, we can find X_{n} an, infinite subset of X_{n−1}, and g(n) ∈ {0, 1} so that g(n) = 0 implies (P_{n})_{X_{n}} is an infinite mad family on X_{n}, and similarly for (Q_{n})_{X_{n}} if g(n) is set to 1. In the end, we have defined g ∈ 2^{ω} and the sequence {X_{n} : n ∈ ω}.

Now we must prove that there is a Y such that Y − X_{n} is finite for all n and such that Y meets infinitely many A in A in an infinite set. Simon attributes this fact to J. Dočkálková. For each n, choose A_{n} ∈ A − {A_{0}, …, A_{n−1}}, so that A_{n} ∩ X_{n+1} = {a(n, m) : m ∈ ω} is infinite. Observe that if h ∈ ^{ω}ω, then Y_{h} = {a(n, m) : m ≤ h(n)} has the property that Y_{h} − X_{n} is finite for each n. We must simply choose an h so that Y_{h} meets infinitely many A_{f}. Let h ∈ ^{ω}ω be arbitrary and fix any f_{0} so that A_{f_{0}} ∩ Y_{h_{0}} is infinite. Since the A_{n}’s are distinct there is an h_{1} ∈ ^{ω}ω so that, for all but at most one n, A_{f_{0}} ∩ {a(n, m) : m ≥ h_{1}(n)} is empty. Find another f_{1} so that A_{f_{1}} ∩ {a(n, h_{1}(n)) : n ∈ ω} is infinite and choose h_{2} > h_{1} so that (A_{f_{0}} ∪ A_{f_{1}}) ∩ {a(n, m) : m ≥ h_{2}(n)} is empty for all but at most two n’s. Continue in this manner until we have chosen f_{n} and h_{n} for all n. Finally, define h(n) = max{h_{k}(n) : k ≤ n} and note that Y_{h} ∩A_{f_{k}} is infinite for each k since {a(n, h_{k}(n)) : k ≤ n ∈ ω} is contained in Y_{h} and A_{f_{k}} ∩ {a(n, h_{k}(n)) : k ≤ n ∈ ω} is infinite.

Now that we have Y_{h}, we know there is an f ≠ g (g constructed above) such that Y_{h} ∩ A_{f} is infinite. However, let n be such that f(n) ≠ g(n) and note that A_{g} and A_{f} are on different sides of the partition P_{n}, Q_{n}. We leave the reader to check that A_{f} is therefore almost disjoint from X_{n+1}, e.g. if g(n) = 0 then P_{n} ↾ X_{n+1} is a mad family in X_{n+1} but A_{f} is not a member of P_{n} and is therefore almost disjoint from A for all A ∈ P_{n}, from which it follows that A_{f} ∩ X_{n+1} must be finite. This of course contradicts the facts that Y − X_{n+1} is finite and A_{f} ∩ Y is infinite.

Therefore there is a mad family A which can be partitioned into B and C each of which is nowhere mad. Let X be the one point compactification of the space constructed from B and let Y be that constructed from C. We leave as an exercise to show that, in X × Y, {(n, n) : n ∈ ω} has the point (∞, ∞) as a limit point but has no subsequence converging to it.

We would like to construct a special mad family for later use. We will need the assumption that 𝔭 = 𝔠. Bell has shown that 𝔭 = 𝔠 is equivalent to the statement that Martin’s Axiom holds for σ-centered posets, MA_{σ}. Those familiar with Martin’s Axiom will find MA_{σ} much easier to apply than 𝔭 = 𝔠. However the two statements are, after all, equivalent and the statement 𝔭 = 𝔠 is much easier to understand. In the following proof we will be able to get away with using 𝔭 = 𝔠 directly.

Lemma 2.3. If 𝔭 = 𝔠, then there is a mad family {A_{α} : α < 𝔠} such that, if {{B_{n}^{α} : n ∈ ω} : α < 𝔠} is a fixed enumeration of [ [ω]^{<ω} ]^{ω} and if I_{α} is the ideal generated by {A_{β} : β < α} ∪ [ω]^{<ω}, then for each α, the following holds: If β < α is such that |{n : B_{n}^{β} ∩ I = ∅}| = ω for all I ∈ I_{α} , then |{n : B_{n}^{β} ⊂ A_{α}}| = ω .

Proof. Let {A_{n} : n ∈ ω} be any partition of ω into infinite sets. Suppose that {A_{β} : β < α} have been chosen. Rather than using ω as our countable set on which we will apply 𝔭 = 𝔠, we will use [ω]^{<ω}. For ease of notation, we may assume that {n : B_{n}^{β} ∩ I = ∅} is infinite for all β < α and I ∈ I_{α} (just throw away those β which do have the property). We define a filter base. For each finite sequence β_{0} < ⋯ < β_{n} < α, let F (⟨β_{0}, …, β_{n}⟩) = {x ∈ [ω]^{<ω} : x ∩ ⋃_{i≤n} A_{β_{i}} = ∅ and (∀i ≤ n) (∃m > n) B_{m}^{β_{i}} ⊂ x}. It is easy to check that every finite intersection of F (⟨β_{0}, …, β_{n}⟩)’s is infinite, in fact, equal to another F (⟨β_{0}, …, β_{n}⟩). Since this filter base has cardinality less than 𝔭, there is an infinite Y ⊂ [ω]^{<ω} such that Y − F (⟨β_{0}, …, β_{n}⟩) is finite for all finite sequences β_{0} < ⋯ < β_{n} < α. Simply define A_{α} to be the union of the members of Y. To see that A_{α} ∩A_{β} is finite, notice that it is contained in the union of the members of Y − F (⟨β⟩). In addition, to see that {m : B_{m}^{β} ⊂ A_{α}} is infinite for each β (we threw away the ones for which this did not need to hold), simply find any sequence β_{0} < ⋯ < β_{n} so that n is arbitrary and β is equal to one of the β_{i}’s and let y ∈ Y ∩ F (⟨β_{0}, …, β_{n}⟩). Since y contains B_{m}^{β} for some m > n and n was arbitrary, it follows that A_{α} contains B_{m}^{β} for infinitely many m.

Next we consider \underline{gaps}. A pair of sequences \{a_{α} : α < ω_{1}\} and \{b_{α} : α < ω_{1}\} form an (ω_{1}, ω_{1})-gap (usually these are all subsets of ω) if for all β < α < ω_{1}, a_{β} ⊂^{∗} a_{α}, b_{β} ⊂^{∗} b_{α}, and a_{α} ∩ b_{β} =^{∗} ∅. The interest in a gap is whether or not it can be \underline{filled}: a set A ⊂ ω fills the above gap, if a_{α} ⊂^{∗} A and A ∩ b_{α} =^{∗} ∅ for all α < ω_{1}. In applications, one is also interested in knowing whether the gap can be filled in some larger universe of sets (see section 4). As is well known, if ω_{1} is relaced by ω in the definition of gap, then every gap can be filled, but Hausdorff showed that there is a Hausdorff gap.

Proposition 2.4. There is an (ω_{1}, ω_{1})-gap which cannot be filled.

Proof. As mentioned above, every (ω, ω)-gap can be filled, so together with the fact that there are no countably infinite mad families, one can easily inductively construct an (ω_{1}, ω_{1})-gap. In order to make it unfillable, we add the following condition to the inductive hypotheses: first of all a_{α} − a_{β} and b_{α} − b_{β} are both infinite for β < α and

(∀n) {β < α : a_{α} ∩ b_{β} ⊂ n} is finite .

Let us define a_{α} for a limit α. Fix β_{n} increasing cofinal in α. We will choose k_{n} inductively and then set a′_{α} = ⋃_{n}(a_{β_{n}} − k_{n}); we will then find a set Y and define a_{α} = a′_{α} ∪ Y. The purpose of a′_{α} is to ensure that a_{β} ⊂^{∗} a_{α} for all β < α, the purpose of k_{n} is to ensure that a′_{α} ∩ b_{β} is finite for all β < α, and the purpose of Y will be to satisfy the additional inductive hypothesis. Set k_{0} = 0 and having defined k_{n}, choose k_{n+1} > k_{n} large enough so that a_{β_{n+1}} ∩ b_{β_{m}} ⊂ k_{n+1} for each m ≤ n. Let γ < α and choose n so that γ < β_{n}. Since b_{γ} −b_{β_{n}} is finite and a′_{α} ∩b_{β_{n}} is contained in ⋃_{i≤n}(a_{β_{i}} ∩ b_{β_{n}}), it follows that a′_{α} ∩ b_{γ} is finite. Now for the set Y. Fix m and suppose that a′_{α} ∩ b_{γ} is contained in m. First of all, there are only finitely many γ < β_{m} such that (a_{β_{m}} − k_{m}) ∩ b_{γ} is contained in m so forget about those. Let F_{m} be the finite set of γ ∈ [β_{m}, β_{m+1}) such that (a_{β_{m+1}} − k_{m+1}) ∩ b_{γ} ⊂ m and fix m ≤ y_{m} ∈ (⋂_{γ∈F_{m}} b_{γ})−(⋃_{i<m} b_{β_{i}}). Note that Y = {y_{m} : m ∈ ω} is almost disjoint from b_{β_{n}} for each n. Therefore, Y is almost disjoint from b_{β} for all β < α. Now, fix n and let γ ∈ [β_{m}, β_{m+1}) with m ≥ n. Then either (a_{β_{m+1}} − k_{m+1}) ∩ b_{γ} ⊄ m or y_{m} ∈ b_{γ}. Therefore the final inductive hypothesis holds. To choose b_{α}, we note that ω − a_{α} contains, mod finite, each b_{β} with β < α. Clearly if we were to let b_{α} = ω − a_{α} we could not continue the induction. So, find any infinite X ⊂ ω − a_{α} which is almost disjoint from each b_{β} (β < α) and let b_{α} = ω − (a_{α} ∪ X).

Now suppose that A ⊂ ω fills the gap. Let Y_{0} be an uncountable subset of ω_{1} such that there is a k_{0} such that for each α ∈ Y_{0}, a_{α} ∩b_{α} ⊂ k_{0} (usually one assumes that a_{α} and b_{α} are disjoint). Next find Y_{1} ⊂ Y_{0}, uncountable, so that there is a k_{1} such that a_{α} − A ⊂ k_{1} and b_{α} ∩ A ⊂ k_{1}, for all α ∈ Y_{1}. Let α ∈ Y_{1} be such that Y_{1} ∩ α is infinite. Therefore, by our final inductive hypothesis, there is a β ∈ Y_{1} ∩ α and an m > k_{1} such that m ∈ a_{α} ∩ b_{β}. But now m ∈ a_{α} − k_{1} implies that m ∈ A and m ∈ b_{β} − k_{1} implies that m ∉ A.

Martin’s Axiom (plus the negation of CH) implies that every unfilled (ω_{1}, ω_{1})-gap contains a Hausdorff sub-gap (in the sense that there is an uncountable subset I so that {a_{α} : α ∈ I}, {b_{α} : α ∈ I} satisfy the condition that {β < α ∩ I : a_{α} ∩ b_{β} ⊂ n} is finite for all n and α ∈ I). Let us use ♢ to construct a gap which is unfilled but does not contain a Hausdorff subgap. Kunen has shown that, for each unfilled (ω_{1}, ω_{1})-gap, there is a ccc poset which introduces a Hausdorff subgap (hence the above Martin’s Axiom result). The interested reader can return to this section after reading later sections and prove that for the gap we are about to construct there is a ccc forcing which introduces a set which fills the gap. Combining this, Kunen’s result, and the results of section 7, this same reader can prove that ♢ implies there are ccc posets whose product is not ccc.

Proposition 2.5. ♢ implies there is an unfilled gap {a_{α} : α < ω_{1}}, {b_{α} : α < ω_{1}} such that a_{α} ∩ b_{α} = ∅ for all α and for every uncountable F ⊂ [ω_{1}]^{<ω}, there are F ≠ G ∈ F such that either A_{F} ∩ B_{F} is not empty or A_{F ∪G} ∩ B_{F ∪G} is empty, where A_{F} = ⋃_{α∈F} a_{α} and B_{F} = ⋃_{α∈F} b_{α}.

Proof. Let {c_{α} : α ∈ Lim ω_{1}} enumerate the infinite subsets of ω – we will ensure that (a_{α} − c_{α}) ∪ (b_{α} ∩ c_{α}) is infinite, hence c_{α} will not split the gap. Using a coding technique such as in Proposition 1.4, let F_{α} ⊂ [α]^{<ω} for limit α be such that for all F ⊂ [ω_{1}]^{<ω} there are stationarily many α such that F ∩ [α]^{<ω} = F_{α}.

We inductively construct a_{α} and b_{α} such that

(1) a_{α} and b_{α} are disjoint and ω − (a_{α} ∪ b_{α}) is infinite;

(2) β < α implies a_{β} ⊂^{∗} a_{α} and b_{β} ⊂^{∗} b_{α};

(3) if β is a limit and if F_{β} has the property that for each G ∈ [β]^{<ω} either A_{G} ∩ B_{G} is not empty or there is an F ∈ F_{β} such that A_{F ∪G} is disjoint from B_{F ∪G}, then for each G ∈ [α]^{<ω} and each finite H, J ⊂ ω and integer i, either A′ = A_{G} ∪H ∪(a_{α}−i) is not disjoint from B′ = B_{G} ∪J ∪(b_{α}−i) or there is an F ∈ F_{β} such that A′ ∩B_{F} and B′ ∩A_{F} are empty; in particular, for each G ∈ [α]^{<ω} such that A_{G} ∩ B_{G} = ∅, there is an F ∈ F_{β} such that A_{F ∪G} ∩ B_{F ∪G} = ∅;

(4) if α is a limit and β < α, then for each disjoint finite H, J and integer i > max(H ∪ J) there is a ξ < α such that H = i ∩ a_{ξ}, J = i ∩ b_{ξ}, and a_{ξ} − i = a_{β} and b_{ξ} − i = b_{β}.

Condition 3 is slightly stronger than it appears it needs to be because we have to anticipate the successor steps after α. Indeed, if we have picked a_{α} for a limit α, then we can just define a_{α+n} = H_{n} ∪ a_{α} − J_{n} and b_{α+k} = (J_{n} ∪ b_{α}) − H_{n} under some enumeration {(H_{n}, J_{n}) : n ∈ ω} of [ω]^{<ω} × [ω]^{<ω}. It should be clear that all but possibly 3 of the inductive hypotheses hold for each α + k. Since each a_{α+k} is almost equal to a_{α} and similarly for b_{α+k}, condition 3 for α+k follows immediately from the fact that it holds at α.

Let {(β_{k}, G_{k}, H_{k}, J_{k}) : k ∈ ω} be an enumeration of α × [α]^{<ω} × [ω]^{<ω} × [ω]^{<ω}. For convenience, we assume that F_{β_{k}} has the property in 3 for each k, and that H_{k} ∩ J_{k} is empty. To construct a_{α} and b_{α} we will construct an increasing and, cofinal in α, sequence {ζ_{k} : k ∈ ω} by induction and let a_{α} = ⋃{a_{ζ_{k}} : k ∈ ω} and b_{α} = ⋃{b_{ζ_{k}} : k ∈ ω}. At stage k, we have ζ_{k−1} and we are looking to ensure that condition three holds for β = β_{k}, G = G_{k}, H = H_{k} and J = J_{k}. We may as well assume that (A_{G} ∪ H) ∩ (B_{G} ∪ J) is empty. Fix i large enough so that, for each j < k − 1, a_{ζ_{j}} − i ⊂ a_{ζ_{k−1}}, b_{ζ_{j}} − i ⊂ b_{ζ_{k−1}}, and, (a_{ζ_{k−1}}−i) ∩ (B_{G} ∪ J) and (b_{ζ_{k−1}}−i)∩(A_{G} ∪J) are both empty. Apply condition 4, to find a ξ so that H ⊂ a_{ξ}, J ⊂ b_{ξ}, a_{ξ} − i ⊂ a_{ζ_{k−1}}, and b_{ξ} − i ⊂ b_{ζ_{k−1}}. Let G′ = G ∪ {ξ}, and note that A_{G′} is disjoint from B_{G′}, so there is an F ∈ F_{β}, which we fix, with A_{F ∪G′} ∩ B_{F ∪G′} = ∅. Choose a ζ large enough so that A_{F ∪G′} ⊂^{∗} a_{ζ} and B_{F ∪G′} ⊂^{∗} b_{ζ}. Next consider the set c_{α}; if possible find n_{1} ∈ ω − (c_{α} ∪ B_{F ∪G′} ∪ k) and n_{2} ∈ c_{α} − (A_{F ∪G′} ∪ k). Let j be large enough so that i, n_{1}, n_{2} < j, A_{F ∪G′}−j ⊂ a_{ζ}, and B_{F ∪G′}−j ⊂ b_{ζ}. Note that so long as a_{α} − i ⊃ A_{F ∪G′}, and b_{α} − i ⊃ B_{F ∪G′}, we will have that A′ = A_{G} ∪ H ∪ (a_{α}−i) is disjoint from B_{F} and B′ = B_{G} ∪ J ∪ (b_{α}−i) is disjoint from A_{F} as required in 3. In addition, if c_{α} contains mod finite a_{β} for all β < α then we will always be able to choose n_{2} and, similarly, if c_{α} is almost disjoint from b_{β} for all β < α, then we can choose n_{1}. If we ensure that n_{1} ∈ a_{α} and n_{2} ∈ b_{α}, then neither a_{α} − c_{α} nor b_{α} ∩ c_{α} will be contained in k.

Now, using condition 4, there is a ζ_{k} such that a_{ζ_{k}} − j = a_{ζ} − j, b_{ζ_{k}} − j = b_{ζ} − j, a_{ζ_{k}} ∩ [i, j) = ({n_{1}} ∪ A_{F ∪G′}) ∩ [i, j), b_{ζ_{k}} ∩ [i, j) = ({n_{2}} ∪ B_{F ∪G′}) ∩ [i, j), a_{ζ_{k}} ∩ i = a_{ζ_{k−1}} ∩ i, and b_{ζ_{k}} ∩ i = b_{ζ_{k−1}} ∩ i. This completes the construction. One thing we have neglected to do is to ensure that ω − (a_{α} ∪ b_{α}) is infinite. This can easily be done by choosing i at stage k larger than it was chosen at stage k − 1 and large enough so that i − (a_{ζ_{k−1}} ∪ b_{ζ_{k−1}}) has size at least k. By the construction and this additional assumption on i, this k sized set will be disjoint from a_{α} ∪ b_{α}.

Now we show that the we have proven the lemma. Suppose that F ⊂ [ω_{1}]^{<ω} is uncountable and that A_{F} ∩ B_{F} is empty for all F ∈ F. If F has the property that A_{F ∪G} ∩ B_{F ∪G} is not empty for all F ≠ G ∈ F, then we may use Zorn’s Lemma to enlarge F to a maximal family with these two properties: i.e. A_{F} ∩ B_{F} is empty for each F ∈ F and, for G ∈ F − {F }, A_{F ∪G} ∩ B_{F ∪G} ≠ ∅. Therefore, by the maximality, it follows that for each G ∈ [ω_{1}]^{<ω} there is an F ∈ F such that A_{F ∪G} ∩ B_{F ∪G} is empty. Therefore, for each α < ω_{1}, there is a g(α) < ω_{1} such that for each G ∈ [α]^{<ω}, there is an F ∈ F ∩ [g(α)]^{<ω} such that A_{F ∪G} ∩ B_{F ∪G} is empty. By Lemma 1.2 there is a cub C ⊂ ω_{1} such that g(β) < α for all β < α with α ∈ C. Now by ♢, there is a β ∈ C such that F_{β} = F ∩ [β]^{<ω}. But now, F_{β} has the property in condition 3, so fix any G ∈ F − [β]^{<ω} and let α = max G. Since G ∈ F, A_{G} ∩ B_{G} is empty, so we can apply 3 for the case α, H = ∅, J = ∅ and i = 0 to obtain that there is an F ∈ F_{β} such that A_{F ∪G} ∩ B_{F ∪G} is empty – contradicting the assumption on F.

Next we turn to P(ω_{1}). Call a sequence \{a_{α} : α < ω_{1}\} a \underline{coherent sequence} if a_{α} ⊂ α and α < β implies a_{β} ∩ α is almost equal to a_{α}. These coherent sequences correspond naturally to clopen subsets of ω_{1}^{∗} − U(ω_{1}) where U(ω_{1}) is the set of uniform ultrafilters on ω_{1}. Clearly if {a_{α} : α < ω_{1}} is a coherent sequence then so is {α − a_{α} : α < ω_{1}}. Say that a coherent sequence is non-trivial if, for each β < ω_{1}, there is an α such that a_{α} − β is infinite. The pair {a_{α} : α < ω_{1}} and {α − a_{α} : α < ω_{1}} form an unfillable gap iff the clopen subset of ω_{1}^{∗} − U(ω_{1}) given by ⋃_{α} a_{α}^{∗} does not extend to a clopen subset of βω_{1}.

Proposition 2.6 (Warren). There is a non-trivial coherent sequence {a_{α} : α < ω_{1}} such that if A ∈ [ω_{1}]^{ω_{1}}, then there is an α such that A ∩ (α − a_{α}) is infinite.

Proof. Fix a partition {A_{n} : n ∈ ω_{1}} of ω_{1} consisting of uncountable sets. We will construct a_{α}, by induction, so that a_{α} ∩ A_{n} is finite for each n. If we do so then suppose that A is an uncountable subset of ω_{1}. There is an n so that A ∩ A_{n} is uncountable, hence there is an α < ω_{1} so that (A ∩ α) ∩ A_{n} is infinite. It follows then, that (A ∩ α) − a_{α} is infinite as required.

We simply construct a_{α} by induction on α. If α = β + 1, then let a_{α} = a_{β}. If α is a limit then fix {β_{n}}_{n} increasing cofinal in α with β_{0} = 0. For each n, if A_{n} ∩ α is cofinal in α, let γ_{n} be the minimal element of (A_{n} ∩ α) − β_{n} otherwise ignore γ_{n}. Define

a_{α} = ⋃{{γ_{n}} ∪ a_{β_{n}} − (β_{n−1} ∪ ⋃_{k<n} A_{k}) : 0 < n ∈ ω} .

By the induction hypothesis, it is easily checked that a_{α} ∩ A_{k} is finite for each k. Similarly, a_{α} ∩ β_{n} is almost equal to a_{β_{n}} since, a_{β_{n}} ∩ [β_{k}, β_{k+1}) is almost equal to a_{β_{k+1}} − β_{k} for each k < n. There are cub many α such that A_{n} ∩ α is cofinal in α for each n, and for each such α, the sequence {γ_{n} : n ∈ ω} witnesses that a_{α} − β is infinite for each β < α.

Call a coherent sequence \underline{big} if for each A ∈ [ω_{1}]^{ω_{1}}, there is an α so that both A ∩ a_{α} and A ∩ (α − a_{α}) are infinite.

Proposition 2.7. ♢ implies there is a big coherent sequence.

Proof. Let {b_{α} : α < ω_{1}} denote a ♢-sequence. For each α such that b_{α} is cofinal in α, choose disjoint ω sequences S_{α} and T_{α} each of which are cofinal subsets of b_{α}. Again inductively construct a_{α}, where a_{α} = a_{β} if α = β + 1 and for α a limit, let T = {β_{n} : n ∈ ω} and define a_{α} = S_{α} ∪ a_{β_{0}} ∪ ⋃{a_{β_{n}} − (β_{n−1} + 1) : n ∈ ω}. Notice that T_{α} ∩ a_{α} is empty, and, of course S_{α} ⊂ a_{α}. The proof that {a_{α} : α < ω_{1}} is a coherent sequence is again straightforward. To show that it is big, let A be an uncountable subset of ω_{1}. There is a cub C so that A ∩ α is cofinal in α for each α ∈ C. Therefore there is an α ∈ C such that A ∩ α = b_{α}. But now S_{α} ⊂ a_{α} ∩ A and T_{α} is contained in A − a_{α}.

The final set-theoretic principle we would like to introduce is □.

Definition 2.8. A □-sequence on ω_{2} is a sequence {C_{α} : α ∈ Lim (ω_{2})} such that

(1) C_{α} is a cub subset of α;

(2) if β is a limit point of C_{α}, then C_{β} = C_{α} ∩ β;

(3) if α has countable cofinality, then C_{α} is countable.

Proposition 2.9. □ implies there is a stationary set E ⊂ ω_{2} so that cf(α) = ω for all α ∈ E and E ∩ λ is not stationary in λ for all λ < ω_{2}.

Proof. Let S_{0}^{2} denote the set of α in ω_{2} which have countable cofinality. For each α ∈ S_{0}^{2}, let g(α) denote the order type of C_{α}. Since g(α) is countable for each α in S_{0}^{2}, there is a ξ < ω_{1} so that E = {α ∈ S_{0}^{2} − ω_{1} : g(α) = ξ} is stationary; i.e. otherwise, for each ξ fix a cub D_{ξ} in ω_{2} so that D_{ξ} ∩ g^{−1}(ξ) is empty, and then apply Proposition 1.1, to deduce that ⋂_{ξ∈ω_{1}} D_{ξ} is a cub missing the stationary set S_{0}^{2}. To finish, we must show that E ∩ λ is not stationary in λ for arbitrary λ < ω_{2}. If cf(λ) is countable then there is nothing to show so assume λ has uncountable cofinality. In this case, C′_{λ} (the limit points) is a cub in λ and since α ∈ C′_{λ} implies C_{α} = C_{λ} ∩ α, there is at most one α ∈ C′_{λ} such that g(α) = ξ.

The principle “square” or box, □, is used to get inductions to go past ω_{1}-limits. To illustrate we give another application of □.

Proposition 2.10. □ implies there is a sequence {Z_{α} : α < ω_{2}} such that each Z_{α} is a zero set of α^{∗}, α < β implies Z_{α} = Z_{β} ∩ α^{∗}, and there is no zero set Z of ω_{2}^{∗} such that Z ∩ α^{∗} = Z_{α} for α < ω_{2}. If, in addition, GCH holds then we can ensure that each Z_{α} is clopen in ω_{2}^{∗}.

Proof. Define, by induction on α < ω_{2}, functions g_{α} from α into ω so that if α < β, then there is an n_{α,β} so that g_{α}(ξ) < g_{β}(ξ) + n_{α,β} and g_{β}(ξ) < g_{α}(ξ) + n_{α,β} for all ξ < α. We will define

Z_{α} = ⋂_{n} {ξ < α : g_{α}(ξ) > n}^{∗}

and note that Z_{α} = Z_{β} ∩ α^{∗} since {{ξ < α : g_{α}(ξ) > n} : n ∈ ω} and {{ξ < α : g_{β}(ξ) > n} : n ∈ ω} generate the same filter.

If α has countable cofinality, and g_{β} has been chosen for β < α, then there is no difficulty in defining a g_{α} so as to satisfy the inductive hypotheses. Indeed, choose β_{n} increasing cofinal in α and piece the g_{β_{n}} together in a manner similar to the construction of coherent sequences. However this is not always possible if cf(α) = ω_{1} so we must make preparations at β < α with countable cofinality. This is where C_{α} comes in. Suppose we ensure that if γ < β are both members of C′_{α}, then g_{β} is simply an extension of g_{γ}. If we do this, then we may let g_{α} be equal the union of {g_{β} : β ∈ C′_{α}}. In actual fact, it will suffice to ensure this for all β ∈ C′_{α} above some fixed member of C′_{α}. This is where the stationary set E from Proposition 2.9 comes in. In 2.9, we found a ξ < ω_{1} so that E = {β : C_{β} has order type ξ} is stationary. For ordinals α in E we will do something special in order to ensure there is no Z as in the Lemma. If α is such that C_{α} has order type less than ξ, then let g_{α} be any function which satisfies the induction hypotheses. If C_{α} has order type greater than ξ, then let γ_{α} ∈ C_{α} be such that C_{α} ∩ γ_{α} has order type ξ and define g_{α} to be any extension of ⋃{g_{β} : β ∈ C′_{α} − γ_{α}}. If C′_{α} is cofinal in α, then g_{α} is uniquely defined, if C′_{α} is bounded in α, then C′_{α} has a maximum β and g_{α} is any extension of g_{β} satisfying the inductive hypothesis, i.e. pieced together from {g_{ζ} : ζ ∈ C_{α} − β}.

Now suppose that α ∈ E. In this case, we choose β_{n} increasing cofinal in α with β_{0} = 0, and we define

g_{α} = ⋃_{n} (g_{β_{n+1}} ↾ [β_{n}, β_{n+1})) + n .

It is very easy to check, by the inductive hypothesis, that for each β < α, there is an n_{β,α} as required. Note that if S ⊂ α is an increasing ω sequence cofinal in α, then S^{∗} ⊂ Z_{α} since g_{α} diverges to infinity on S.

Now suppose that g is a real-valued function on β(ω_{2}) such that Z = g^{−1}(0) is a zero-set such that Z ∩ α^{∗} = Z_{α} for all α < ω_{2}. First of all assume that Z ∩ ω_{2} has cardinality ω_{2}. There is then a cub C in ω_{2} such that Z ∩ ω_{2} is cofinal in α for each α ∈ C. Fix an α ∈ C ∩ E and observe that Z ∩ α − {ξ < α : g_{α}(ξ) > 0} is infinite and so (Z ∩ α)^{∗} − Z_{α} is not empty. Since (Z ∩ α)^{∗} is a subset of Z, we have that Z ∩ ω_{2} is bounded. For each n, let A_{n} = \{ξ : g(ξ) ∉ (\frac{−1}{n}, \frac{1}{n})\}, hence ∪_{n}A_{n} is most of ω_{2}. Again, there is an α ∈ ω_{2} and an n so that A_{n} ∩ α is cofinal in α. Let S be any ω sequence contained in A_{n} which is cofinal in α. Clearly g[S^{∗}] ∩ (\frac{−1}{n}, \frac{1}{n}) is empty and so S^{∗} ∩ Z is empty, while, as discussed above, S^{∗} ⊂ Z_{α}.

We will just briefly mention how we can use GCH to obtain a clopen sequence of Z_{α} as above. This is equivalent to finding Z_{α} ⊂ α so that Z_{β} =^{∗} Z_{α} ∩ β for β < α (i.e. a coherent sequence). In order to keep the same notation, we will use ω_{2} ×ω as our underlying set and again define functions g_{α} as above and then we will define Z_{α} = {(ξ, m) : m < g_{α}(ξ)}. Now we will need that g_{α} ↾ β is almost equal to g_{β} for β < α. The procedure is exactly as above except for α ∈ E. We will again choose β_{n} increasing cofinal in α and we will let g_{α} ↾ (β_{n−1}, β_{n}) = g_{β_{n}} ↾ (β_{n−1}, β_{n}). Except that we now change g_{α} on just the points β_{n} – we define g_{α}(β_{n}) = n. In addition the sequence {β_{n} : n ∈ ω} is not just any old sequence this time but is chosen using ♢ on ω_{2}. Suprisingly GCH implies that, for any stationary set S ⊂ S_{0}^{2}, there is a sequence {b_{α} : α ∈ S} such that for each A ⊂ ω_{2}, there is a stationary set S_{A} such that A ∩ α = b_{α} for each α ∈ S_{A}. So, if b_{α} is cofinal in α, then {β_{n} : n ∈ ω} is chosen as a subset of b_{α}, arbitrary otherwise. The proof that this works proceeds just as above except that we use S = {β_{n} : n ∈ ω} in the above argument.

Remarks: The failure of □ implies that ω_{2} is a Mahlo cardinal in L (see section 6). Therefore any statement that follows from □, the consistency of its negation implies the existence of “large” cardinals. Todorcevic has proven the first statement in 2.10 follows from the hypothesis that ω_{2} is not weakly compact in L.

3. Two more proofs from ♢

Naturally everyone should know Ostaszewski’s construction so we will include the following construction.

Theorem 3.1 (Fedorcuk). ♢ implies that there is a compact hereditarily separable space containing no converging sequences and no isolated points.

Proof. Define X_{α} a closed subset of 2^{α} by induction on α ≤ ω_{1} so that α < β implies X_{β} projects onto X_{α}. The plan: if Y ⊂ X_{ω_{1}} then Y has a dense subset {y_{β} : β ∈ ω_{1}}. We can code {y_{β} : β < ω_{1}} as a subset of ω_{1} × ω_{1}; call it A. For a partial function φ from ω_{1} into 2, let [φ] denote the set of elements of 2^{ω_{1}} which contain φ. Of course if φ is finite, then [φ] is a basic clopen set. Define a function g: [ω_{1}]^{<ω} → ω_{1} so that for each F ∈ [ω_{1}]^{<ω} and φ ∈ 2^{F}, if Y ∩ [φ] ≠ ∅, then there is a β < g(F) such that y_{β} ∈ [φ]. Fix a cub C as in 1.2. Then there is a δ ∈ C so that A∩δ ×δ = a_{δ}, where a_{δ} is from a suitable ♢-sequence. Given that a_{δ} will be a subset of δ×δ, let a(δ, β) denote the subset of δ so that {β}×a(δ, β) = a_{δ}∩({β}×δ). The definition of C guarantees that {y_{β} ↾ δ : β < δ} is dense in the projection of Y into 2^{δ}, denoted P_{δ}^{ω_{1}}[Y]. The inductive construction will need to guarantee that Y ⊂ \overline{\{y_{β} : β ∈ δ\}}. However, the only thing we know about \{y_{β} : β ∈ δ\} is that its projection is {a(δ, β) : β < δ} (the ♢-sequence element), so the requirement (at first glance, too ambitious) is that Y should be contained in the closure of ANY sequence {z_{β} : β < δ} such that z_{β} ↾ δ = a(δ, β) for each β < δ. In addition, since we really don’t know much about Y except its projection, this is going to have to be true about any Y with the same projection.

This translates to the following inductive assumption: for any y ∈ X_{γ} such that y ↾ δ is a limit point of {a(δ, β) : β < δ}, each neighbourhood U of y must contain, for some β < δ, all z ∈ X_{γ} such that a(β, δ) = z ↾ δ. That is, in this case, U must contain (P_{δ}^{γ})^{−1}(a(δ, β)) ∩ X_{γ}.

The other, much easier thing that we must accomplish is to guarantee that there are no converging sequences and no isolated points. For this it will suffice to ensure that {a(δ, n) : n ∈ ω} is not the image of a converging sequence in X_{δ+1} and that a(δ, 0) is the image of at least two points in X_{δ+2}. We will not use δ for this so that we can stay with Fedorcuk’s original idea of using a minimal extension when passing from X_{δ} to X_{δ+1} – that is, there is a unique point of X_{δ} which has more than one point in X_{δ+1} mapping onto it.

Having minimal extension in mind, we know that we must choose one point x ∈ X_{δ} and partition X_{δ} − {x} into two disjoint clopen sets U_{0} and U_{1}. Then X_{δ+1} will be defined as (U_{0} × {0}) ∪ (U_{1} × {1}) (a moment’s thought will convince the reader that this is exactly what must take place). For limit δ, we simply define X_{δ} = ⋂{(P_{γ}^{δ})^{−1} (X_{γ}) : γ < δ}. The above inductive hypothesis is easily checked. The inductive hypothesis for X_{δ+1} is only a problem for the two points (x, 0) and (x, 1) where x is the point we chose to “double”. What is required is, for each α < δ such that x ↾ α is a limit point of {a(α, β) : β < α} and each neighbourhood W of x (in X_{δ}) each of U_{0} ∩W and U_{1} ∩W contain a full preimage of some a(α, β). Let I be the set of α < δ such that x ↾ α is a limit of {a(α, β) : β ∈ α}. By the inductive hypothesis, we can, for each α ∈ I, fix a sequence {β(α, n) : n ∈ ω} ⊂ α so that {X_{δ} ∩ (P_{α}^{δ})^{−1} (a(α, β(α, n))) : n ∈ ω} converges to x. Let f be a function from ω onto I so that f^{−1}(α) is infinite for each α ∈ I. Note that X_{δ} is homeomorphic to a compact subset of the Cantor set hence it is a simple matter to cover X_{δ} −{x} with a pairwise disjoint sequence, W_{n}, of compact open subsets of X_{δ} −{x} so that both W_{2n} and W_{2n+1} contain some member of {X_{δ} ∩ (P_{α}^{δ})^{−1} (a(α, β(α, n))) : n ∈ ω} where α = f(n). Letting U_{0} = ⋃_{n} W_{2n} and U_{1} = ⋃_{n} W_{2n+1} are as required.

The final detail is how to choose x. If δ is a limit, then choose x a limit point of {a(δ, n) : n ∈ ω} and ensure that each of U_{0} and U_{1} contain infinitely many elements of {a(δ, n) : n ∈ ω}. This ensures that any sequence in X_{δ+1} which maps onto {a(δ, n) : n ∈ ω} will have each of (x, 0) and (x, 1) as a limit point. If δ = λ+1 for some limit λ, then choose x so that it maps onto a(λ, 0). For any other δ, the choice of x is arbitrary.

We check that this works. Let x ∈ X_{ω_{1}} and let us see that x is not isolated in X. If it were, then, as X_{ω_{1}} is simply a subspace of 2^{ω_{1}}, there would be a λ < ω_{1} so that x is the unique member of X extending x ↾ λ. However it is easily seen that there are stationarily many δ > λ so that a(δ, 0) = x ↾ δ. By construction, there are two points in X_{δ+2} which map onto x ↾ δ. Since P_{δ}^{ω_{1}} is onto, there are two points in X which extend x ↾ δ - a contradiction.

Suppose that {x_{n} : n ∈ ω} is a converging sequence in X. Again, there are stationarily many δ so that {a(δ, n) : n ∈ ω} = {x_{n} ↾ δ : n ∈ ω}. Apparently {x_{n} ↾ δ + 1 : n ∈ ω} is a converging sequence in X_{δ+1} which maps onto {a(δ, n) : n ∈ ω}, but, by the construction there is no such sequence.

The fact that X is hereditarily separable follows from the fact that we carried out the “plan” outlined above.

Theorem 3.2 (Fleissner, Shelah, Taylor). ♢^{∗} implies that first countable normal spaces are ℵ_{1}-collectionwise Hausdorff.

Proof. Let ω_{1} be embedded as a closed discrete subspace of a normal space X of character ω_{1}. Assume that there is no separation of ω_{1} in X. For each α ∈ ω_{1}, let {U(α, β) : β ∈ ω_{1}} enumerate a neighbourhood base at α. A potential separation of ω_{1} would correspond to a function f ∈ ^{ω_{1}}ω_{1}. For brevity, given a partial function f from ω_{1} to ω_{1}, let U_{f} = ⋃\{U(β, f(β)) : β ∈ dom f\}; \overline{U}_{f} will denote the closure.

We will use the ♢-principle to define a subset E of ω_{1} so that E and ω_{1}−E cannot be separated by predicting all potential separations and adjusting the definition of E accordingly.

The basic fact needed for this to work is the following: for each f ∈ ^{ω_{1}}ω_{1}, the set

S_{f} = \{α : \overline{U}_{f↾α} ∩ ω_{1} − α ≠ ∅\}

is stationary.

Here is the plan which almost works. We define a chain E_{α} ⊂ α by induction and let E = ⋃_{α} E_{α}. For each α, suppose we are given, by ♢, a function f_{α} ∈ ^{α}α. If f_{α} separates E_{α} and α − E_{α} we look to see if there is a δ_{α} ≥ α which is a limit point of U_{f↾α}. If there is then put δ_{α} in E iff it is a limit of U_{f↾α−E}. Note that no f which extends this f_{α} will be a separation of E and ω_{1} − E. This defines E_{β} for all β ≤ δ_{α} + 1.

Why does this almost work. Suppose that f separates E and ω_{1} − E. Since S_{f} is stationary and, by the ♢ property, T_{f} = {α : f ↾ α = f_{α}} is stationary so there is a chance that S_{f} ∩ T_{f} is not empty. If α were in S_{f} and T_{f} we would have a contradiction since δ_{α} was carefully put in the wrong side of E so that f_{α} would not extend to a separation of E. This is Fleissner’s approach, he defines a stronger version of ♢ which does guarantee that S_{f} ∩ T_{f} is not empty.

We will take a different approach however. We follow Taylor’s approach which is modelled after Kunen’s proof that ♢^{∗} implies ♢; i.e. there is a way of choosing just one f_{α} when you have countably many. Before doing so however, let us note that if, for each f ∈ ^{ω_{1}}ω_{1},

S̄_{f} = \{α : (ω_{1} − α) ∩ \overline{U}_{f↾α} is infinite\}

then we could get away with ♢^{∗} directly. Therefore we may assume that there is a cub C and a sequence H_{α} of pairwise disjoint finite sets such that for every f : ω_{1} → ω_{1} and α ∈ C, \overline{U}_{f↾α} ∩ (ω_{1} − α) is contained in H_{α}.

Let F_{α} = {f_{α,n} : n ∈ ω} (for α ∈ Lim (ω_{1})) be a ♢^{∗} sequence. Fix a definable coding of ω_{1} × ω in type ω_{1}; e.g. Φ(β, n) = β · ω + n. Roughly speaking, we will assume that the sequence {f_{α,n} : α ∈ Lim (ω_{1})} is not a suitable ♢-sequence for each n in the sense that there there is a function f_{n} coding a separation of X_{n}, ω_{1} − X_{n} where X_{n} is constructed as E was above. We use Φ to code the sequence of f_{n}’s into one function f, and obtain a contradiction from the fact that this f should have been predicted lots of times.

For technical reasons we do not use f_{α,n} but rather what we will call h_{α,n}. Looking ahead to the final step of the proof we want to think of f_{α,n} as coding countably many functions, so we let h_{α,n} be the n-th one of these countably many functions. More precisely,

h_{α,n}(β) = f_{α,n}(Φ(β, n)) .

For each n, let X_{n} be the subset of ω_{1} which we get by following the plan laid out above in which we use h_{α,n}. That is, if ω_{1} ∩ \overline{U}_{h_{α,n}} goes above α, then one of these elements is put on the wrong side of the partition X_{n}, ω_{1} − X_{n} so that no extension of h_{α,n} is a separation of X_{n} and ω_{1} − X_{n}.

By the normality of X, fix, for n ∈ ω, a separating function f_{n} for X_{n} and ω_{1} − X_{n}. Using Φ we code these countably many functions into one: f(α) = f_{n}(β) where Φ(β, n) = α. By ♢^{∗}, there is a cub C so that C ⊂ {α ∈ Lim (ω_{1}) : (∃n) f ↾ α = f_{α,n}}. If we assume that α ∈ C implies that Φ(β, n) < α for all β < α, we then have that C ⊂ {α ∈ Lim (ω_{1}) : (∃n) f_{n} ↾ α = h_{α,n}}. Let Y_{n} = {α ∈ C : f_{n} ↾ α = h_{α,n}}; hence C = ⋃_{n} Y_{n}.

Now we have to do a little topology (because ♢^{∗} does not imply Fleissner’s ♢ principle).

Define an ideal I ⊂ P(C) by a ∈ I iff (∃g ∈ ^{ω_{1}}ω_{1}) such that S_{g} ∩ a is empty (i.e. U_{g} does not go “up” at any member of a). Recall that α ∈ S_{g}∩C iff H_{α}∩\overline{U}_{g↾α} is not empty. Easy topology tell us that if there is a cub in I, then there is a separation of ω_{1}. We need that I is countably complete. Fix {a_{n} : n ∈ ω} ⊂ I and functions g_{n} witnessing that a_{n} ∈ I. Without loss of generality the a_{n}’s are pairwise disjoint. Fix pairwise disjoint open subsets U_{n} of X, so that ⋃_{α∈a_{n}} H_{α} ⊂ U_{n} for each n (using the normality of X). Define a function g : ω_{1} → ω_{1} so that, if β ∈ U_{n} then g(β) ≥ g_{n}(β). Assume that α ∈ S_{g} ∩ a_{n}; hence \overline{U}_{g↾α} ∩ H_{α} is not empty. But then \overline{U_{g↾α} ∩ U_{n}} must meet H_{α}, which contradicts that g refines g_{n} on U_{n}.

We are finally ready for our contradiction. Since I does not contain a cub (i.e. C) and is countably complete, there is an n so that Y_{n} ∉ I. Therefore for every g : ω_{1} → ω_{1}, there is an α ∈ Y_{n} so that \overline{U}_{g↾α} ∩ H_{α} is not empty. In particular, this is the case for g = f_{n}. But this contradicts that f_{n} is a separation of X_{n} and ω_{1} − X_{n}.

4. Some Logic

We do not intend to go far without resorting to elementary submodels. One’s first reaction to elementary submodels is concern that something so mysterious cannot be understood. This is consistent with a Platonic view of the universe and the clear knowledge that we do not understand the universe. In reality, however, there is absolutely nothing mysterious about an elementary submodel. First one must be clear on “What is the language of set theory?”. It is nothing but the binary relation ∈! When specifying a model of set-theory then, one must specify a set M and then an interpretation ∈^{M} of ∈. However we shall assume that V, the universe of sets, is a model of ZFC in which ∈ is the usual set membership and every model M will be a subset or subclass of V and will inherit the usual set membership relation. If φ is a formula of set theory then the truth of φ refers to its truth in V. If M is contained in V, then M ⊧ φ denotes the satisfaction relation for M (defined recursively in any standard logic book). More exactly, we write φ(v_{1}, …, v_{n}) to mean that the free variables of φ are among {v_{1}, …, v_{n}} and we may write, let x, y, x_{1}, …, x_{n} be sets (or elements) and speak of φ(x, y, x_{1}, …, x_{n}) and we mean, as is standard, that φ has the form φ(v_{1}, …, v_{n+2}) and that v_{1} now denotes the set x, v_{2} the set y, and v_{i+2} the set x_{i}.

Now consider a quantifier-free formula, φ(v_{1}, …, v_{n}) and a sequence of elements m_{1}, …, m_{n} of a model M. The validity of φ(m_{1}, …, m_{n}) (in V) is based simply on a Boolean combination of assertions that certain of the m_{i} are members (or not) of other of the m_{j}’s. In addition, by our definition of submodel, the assertion M ⊧ φ(m_{1}, …, m_{n}) is exactly the same, i.e. ∈^{M}=∈ ∩M × M. We might say that φ is preserved when passing from M to V (and reflected when passing from V to M). Kunen ([6]) makes the definition that a formula φ(v_{1}, …, v_{n}) is absolute for M ⊂ N (a pair of models) if for each sequence, m_{1}, …, m_{n}, of elements of M,

M ⊧ φ(m_{1}, …, m_{n}) iff N ⊧ φ(m_{1}, …, m_{n}) .

Formulas certainly do not need to be preserved when passing from one model to the next. Consider the two very simple formulas v_{1} = v_{2} and v_{1} ⊂ v_{2}. The first thing to ask is if they are formulas of set-theory. The informal language of settheory is greatly expanded but one should simply adopt an acceptable translation (although there are often many defined symbols such as the empty set, ω, the Cartesian product, and ordered pairs which require certain formulas (e.g. axioms) to be valid for the formula to make sense). Usually one considers ‘=’ to be a logical symbol hence v_{1} = v_{2} is a formula of set theory and is preserved; however ((∀x)(x ∈ m_{1} ↔ x ∈ m_{2})) ↔ m_{1} = m_{2} is a substitution instance of the axiom of extensionality and if m_{1} and m_{2} are distinct members of a model M which does not contain any elements of m_{1} − m_{2} ∪ m_{2} − m_{1}, then this axiom would not be hold in M, hence the truth value is not preserved when passing from V to M. On the other hand v_{1} ⊂ v_{2} is an abbreviation for (∀x)(x ∈ v_{1} → x ∈ v_{2}) and for M and V to agree on this formula it is sufficient (and necessary) that they agree on the formula (∃x)(x ∈ v_{1} ∧ x ∉ v_{2}). However, (x ∈ v_{1} ∧ x ∉ v_{2}), being quantifier-free, is preserved, hence it is sufficient to have that

(∃x)(x ∈ v_{1} − v_{2}) ⇒ (∃x ∈ M)(x ∈ v_{1} − v_{2})

is valid. This latter example is a special case of the Tarski-Vaught criterion (the hypothesis of Proposition 4.1) – the emphasis being on the fact that the whole assertion takes place in V and the idea that all we needed to do was to pick one witness from V and add it to M.

Proposition 4.1. Suppose that φ_{1}, …, φ_{m} is a sub-formula closed list of formulas such that the symbol ∀ does not appear. Suppose that M is a set or class such that whenever φ_{i} is of the form (∃x)φ_{j}(x, v_{1}, …, v_{n}) and m_{1}, …, m_{n} are members of M, the following implication holds:

(∃x)φ_{j}(x, m_{1}, …, m_{n}) ⇒ (∃x ∈ M)φ_{j}(x, m_{1}, …, m_{n}) .

Then, for each φ_{i} and m_{1}, …, m_{n} ∈ M,

M ⊧ φ_{i}(m_{1}, …, m_{n}) iff V ⊧ φ(m_{1}, …, m_{n}) .

While it is very difficult to know which (substitution instances of) formulas an arbitrary model M may or may not satisfy, an elementary submodel is simple in the sense that its truths are the same as those for V. If the role of V in 4.1 is replaced by a model N containing M and if the list of formulas is expanded to all formulas, then M is said to be an elementary submodel of N, denoted M ≺ N. Gödel’s second incompleteness theorem implies that the existence of sets M which are elementary submodels of V is not provable. However interesting, this is not a practical limitation to the use of elementary submodels because of the following two facts. Levy reflection implies that for every formula (hence every finite set of formulas) there is an abitrarily large set H for which the formula is reflected. The Axiom of Choice implies that, for every set H, there are many elementary submodels M of every conceivable size (including countable!). Still further simplifications are possible if one is only worried about practical applications. Given a set X under consideration there will be sufficiently large θ so that the properties of X in the model H(θ), defined below, are of sufficient interest.

Definition 4.2. A set H is transitive if every one of its elements is a subset. The transitive closure of a set H exists and is defined as the smallest transitive set which contains H. For an infinite cardinal θ, H(θ) is defined as the \underline{set} of all sets whose transitive closure has cardinality less than θ.

Proposition 4.3. If θ is a regular cardinal, then H(θ) is a model of each of the axioms of ZFC except for the power set axiom - denoted ZF-P.

We will return to the existence of elementary submodels in Section 5 but we first continue our discussion of preservation. The question of preserving formulas or properties is certainly of interest in many more instances than in defining the notion of an elementary submodel. The greatest source of confusion in using submodels is that M ⊧ φ(X) is not the same as V ⊧ φ(X ∩ M). For example one can easily have an ordinal α ∈ M such that M ⊧ α is the first uncountable cardinal, we would say that α = ω_{1}^{M}, while in fact α is a countable ordinal of V. However this does not happen in an elementary submodel (even a countable one), since the statement that asserts a certain ordinal α is the ω_{1} of the model would have to be true of the same α in both models. However, if M is countable such that ω_{1}^{M} = ω_{1}, then ω_{1} ∩ M would be a countable set in V and not even an element of M.

Recall that a tree is a poset in which the set of predecessors of an element is well-ordered. Of particular interest about trees is when they have branches going through every level. Suppose that M is a model and T ∈ M is such that M ⊧ T is a tree. Is T really a tree? In the future we will always assume that our models M satisfy enough of the axioms so that basic notions need not concern us. E.g. the separation axiom scheme (or the Comprehension Scheme in [6]) is needed to talk about the set of predecessors of t ∈ T, many axioms are needed to talk about whether this set is well-ordered, and to define the levels of T etc. However we also want certain “elementary” or “first-order” notions to have the right meaning in M such as the property of being an ordered pair, being a function, being an ordinal. If M is transitive this is true of many properties. We call (∃x ∈ y) and (∀x ∈ y) bounded quantifiers and a formula in which all quantifiers are bounded is called a Δ_{0} formula. If φ is a Δ_{0} formula and M is transitive, then M ⊧ φ(m_{1}, …, m_{n}) iff V ⊧ φ(m_{1}, …, m_{n}) for all m_{1}, …, m_{n} ∈ M. Also note that if M is a transitive model of ZF-P, for example, and ZF-P⊢ φ ↔ ψ for some Δ_{0} formula ψ, then the above preservation property also hold for φ. This handles a great deal of properties.

We do not expect the property of being a cardinal to be preserved, more generally if the power set operation is involved in a formula then there is no reason to expect that it will be preserved. However some sets are considered definable (by parameters and the other axioms) – e.g. {s ∈ T : s <_{T} t} is definable from t and ⟨T, <_{T} ⟩. If M is a model of ZF-P, then there will be some set x ∈ M such that M ⊧ x = {s ∈ T : s <_{T} t} (more precisely M ⊧ (∀z)(z ∈ x ↔ (z ∈ T ∧ z <_{T} t)) ). The existence of such sets follows from the separation axiom and does not require the power set axiom. The problem of whether T is really a tree simply boils down to the properties, in V, of these sets x.

We are not, however, interested in such technical questions. This type of question goes away if we assume that, either M is a transitive model of ZFC-P or M is an elementary submodel of some transitive model of ZFC-P (such as an H(θ)).

The question of new branches of T is a question that does not go away and is of great interest. In the simplest case, assume that T is an Aronszajn tree and that T ∈ M ≺ H(ω_{2}) with |M| = ω. Since V ⊧ T has no ω_{1}-branches, M ⊧ T has no ω_{1}-branches. However let us consider the situation starting with the following useful lemma (note ω + 1 is contained in every model of ZF-P).

Lemma 4.4. If M ≺ H(θ) (with θ regular) is such that κ+1 ⊂ M, then M ∩κ^{+} ∈ κ^{+} + 1. More generally, if X ∈ M and |X| ≤ κ, then X ⊂ M.

Proof. In the case κ^{+} ⊂ M, this is trivial, so assume that κ^{+} − M is not empty. Let δ be the minimal element of κ^{+} − M and we will show that M ∩ κ^{+} = δ, i.e. M ∩κ^{+} ⊂ δ. Assume that β ∈ M ∩κ^{+}; we show that β ⊂ M. Since β < κ^{+} there is a function f from κ onto β. By elementarity, M ⊧ (∃f)f : κ → → β. Therefore, by definition of “M ⊧”, there is an f ∈ M such that M ⊧ f : κ → → β. Run through all the properties that f is to have in M to see that f must “really” have them: f is a set of ordered pairs, f is a function, the domain of f is κ, the range of f is β. Each of these, in turn, must be true of f or else M would possess a witness to the failure. Now it is not enough to know that M ⊧ “range f = β” in order to deduce that β ⊂ M. However, we have assumed that dom f is a subset of M. Fix any ξ < β and pick γ < κ so that f(γ) = ξ. We cannot yet refer to ξ as a member of M, but we can recall that M ⊧ (∃α)f(γ) = α. The α that M contains which witnesses that f(γ) has a value must really have the (elementary) property that f(γ) = α, hence α must equal ξ.

Therefore, by the previous proposition, δ = M ∩ω_{1} is an element of ω_{1}. For each α < ω_{1}, let T_{α} denote the α-th level of T, i.e. all those t ∈ T such that the order type of {s ∈ T : s < t} is α. It follows that every b ∈ M such that M ⊧ b ⊂ T is a branch, there is a β < δ such that b∩T_{β} = ∅. Since T is Aronszajn, T_{α} is countable for each α, hence T_{α} ⊂ M for each α < δ. Clearly, then, the tree T ∩ M = ⋃_{α<δ} T_{α} has branches meeting each level, but M ⊧ T has no such branches. Of course this simply means that M itself does not contain any of the branches (in particular {s ∈ T : s < t} ∉ M for each t ∈ T_{δ}).

Now consider the transitive collapse of M. This is defined recursively, by Mostowski, where G(x) = {G(y) : y ∈ x ∩ M} for each y ∈ x. The axiom of foundation guarantees that this is well-defined. In fact every set x has a \underline{rank}, which is the least ordinal α such that each member of x has rank less than α. The axiom of foundation is essentially equivalent to the assertion that the rank function is well-defined. The function G is an ∈-isomorphism from M to N = G(M) = {G(x) : x ∈ M}. Therefore N is a transitive model ZFC-P (since M was assumed to be). If we assume, without loss of generality, that T is a subtree of ^{<ω_{1}}ω, then it turns out that G is the identity on T ∩M = ⋃_{α<δ} T_{α}, hence T′ = G(T) = ⋃_{α<δ} T_{α} is a member of N. Furthermore, ω_{1}^{N} = M ∩ ω_{1} ( but N ∩ ω_{1} ≠ M ∩ ω_{1}, e.g. δ = G(ω_{1}) ∈ N). Now T′ is a tree in the transitive model N and N is a model of “T′ has no \underline{uncountable} branches”. Clearly, in V, T′ has branches hitting every level of T′ but, being countable, certainly no uncountable branches. Can there be a model N′ ⊃ N (of ZFC-P) such that N′ ⊧ “T′ has uncountable branches”? If T contains a Souslin tree, M would model this and so N would model that T′ contains a Souslin tree. One can check with the method of forcing, discussed later, that, then, there is such a model N′. On the other hand, we often use a kind of relative preservation in the sense that the property is preserved in certain extensions, e.g. those that also preserve certain cardinals. For example, if T is a special Aronszajn tree then there is no such extension (T is special if there is an order-preserving function into the rationals). Indeed, fix such a specializing function f, which, by elementarity, may be assumed to be in M; hence G(f) ∈ N. Assume that N′ ⊃ N and b ∈ N′ is a branch of T′. It follows that G(f) ↾ b : b ↦ ℚ is order-preserving, hence one-to-one. Therefore b is not uncountable (however it may still meet every level of T′, in which case N′ ⊧ ω_{1}^{N} is countable).

5. Fun with Elementary submodels

As mentioned before, each set has an abundant supply of elementary submodels of every smaller cardinality.

Lemma 5.1. For any set M, there are countably many \underline{Skolem} functions H_{m}^{n} so that H_{m}^{n} : M^{n} → M and for each N ⊂ M such that H_{m}^{n}[N^{n}] ⊂ N for all n, m ∈ ω, N is an elementary submodel of M.

Corollary 5.2. For each set M and each X ∈ M and each infinite cardinal κ < |M|, there is an elementary submodel N ≺ M such that X is a member of N.

The following basic result is really only a corollary if we restrict to elementary submodels of the type given by Lemma 5.1, but it holds for any chain.

Corollary 5.3. If N is chain of elementary submodels of M, then ⋃ N is also an elementary submodel of M.

Lemma 5.4. If g : [κ]^{<ω} → κ, for some n ∈ ω, and g ∈ M ≺ H(κ^{+}), then g(β_{1}, …, β_{n}) ∈ M for all β_{1}, …, β_{n} ∈ M ∩ κ.

Proof. By elementarity, M ⊧ (∀F ∈ [κ]^{<ω}) (∃ξ ∈ κ) (F, ξ) ∈ g (i.e. g(F) = ξ). The definition of M ⊧ φ is φ^{M}, hence, for all F ∈ [κ]^{<κ} ∩ M, there is a ξ ∈ κ ∩ M, such that g(F) = ξ.

Lemma 5.5. Elementary submodels, stationary sets and Cubs: Let S, C, X be subsets of a regular cardinal κ and let θ > κ be a regular cardinal.

(1) If S is stationary then for any A ∈ H(θ) there is an M ≺ H(θ), including A, so that M ∩ κ ∈ S.

(2) If C ∈ M ≺ H(θ) and C is cub, then M ∩ κ ∈ C.

(3) If X ∈ M ≺ H(θ) and sup(M ∩ κ) ∈ X, then X is stationary.

(4) Let X ⊂ κ such that both X and κ are members of M ≺ H(θ). If ∀α ∈ M ∩ κ, ∃β ∈ X − α, then X is cofinal in κ. Similarly, if ∃β ∈ X such that M ∩ κ ⊂ β, then X ∩ M is cofinal in M ∩ κ and X is cofinal in κ.

A function f on a set S of ordinals is regressive if f(α) < α for all α ∈ S − {0}. A function f on a tree T will be called regressive if f(t) < t for all t ∈ T which are not minimal.

Lemma 5.6 (Pressing down lemma). If S is a stationary subset of a regular cardinal κ and if f is a regressive function on S, then there is an α ∈ κ so that f^{−1}(α) is stationary. Hence if S is written as a union of fewer than κ sets, one of them is stationary.

Proof. This can be deduced from the previous lemma as follows. Fix f as in the statement and by 5.5.1, fix an elementary submodel M ≺ H(θ) so that δ = M ∩κ ∈ S. Since ξ = f(δ) is less than δ, it is a member of M. Now set X = f^{−1}(ξ) and apply 5.5.3 to deduce that X is stationary in κ.

Theorem 5.7 (Todorcevic). Suppose that f is a regressive function on a tree T so that for each t ∈ T, f^{−1}(t) is special. Then T is special.

Proof. Fix θ large enough so that f, T, P(T) ∈ H(θ) and let M ≺ H(θ) be countable and f, T, P(T) ∈ M. Let A ⊂ P(T) denote the family of antichains. Clearly if

H(θ) ⊧ (∃A′ ∈ [A]^{ω}) T = ⋃ A′ ,

then, by elementarity, there would be such a countable family A′ in M. That is, it is necessary and sufficient to show that

T = ⋃ (A ∩ M) .

This gets us to thinking about which antichains of T are in M and how f will help put them there. Obviously f^{−1}(t), for t ∈ M ∩ T, is the union of countably many (assigned) antichains which will be in M. Maybe f(s) will be a member of M for each s ∈ T. Obviously not, but a moment’s reflection convinces us that, for each s ∈ T, there is an n so that t = f^{n}(s) is in M (there’s no infinite descending sequence of ordinals – hence levels of T). Now we ask if (f^{n})^{−1}(t) will be special. The answer is easy: since f is regressive, if A ⊂ T is special, then so is f^{−1}(A) (because if A_{a} ⊂ f^{−1}(a) is an antichain for each a ∈ A, then ⋃{A_{a} : a ∈ A} is again an antichain). Since M ∩ T is countable, this completes the proof. However, we can in hindsight, recognize that T = ⋃_{n}(f^{n})^{−1}(0) (where 0 is the root of T) and prove the theorem without using M.

Theorem 5.8 (Solovay). If S is a stationary subset of a regular cardinal κ, then S contains κ disjoint stationary subsets.

Proof. Without loss of generality we may assume that S contains no successor ordinals. We first show that

W = {α ∈ S : either cf(α) = ω or S ∩ α ∈ NS_{α}}

is stationary. Assume that C is cub and is disjoint from W. Let δ = min(S ∩ C′) where C′ is the set of limits of C. Clearly C ∩δ is closed and unbounded in δ. Since δ has uncountable cofinality, C′ ∩ δ is a cub in δ. Since C′ ∩ (S ∩ δ) is empty, it follows that S ∩ δ is non-stationary in δ.

For each α ∈ W choose an continuous increasing sequence {a_{ξ}^{α} : ξ ∈ cf(α)} cofinal in α and, since α ∈ W, disjoint from W (note that W contains no successor ordinals, so there’s no problem if cf(α) = ω). Fix M ≺ H(θ) (for some suitable θ) so that δ = M ∩ κ ∈ W (by item 1 of Lemma 5.5).

Define, for ξ, β ∈ κ,

S(ξ, β) = {α : a_{ξ}^{α} ≥ β} .

The plan is to show that there is a ξ so that S(ξ, β) is stationary in κ for every β < κ. If ξ is such an ordinal, then it follows easily from the pressing down lemma that there are κ many ζ such that T (ξ, ζ) = {α : a_{ξ}^{α} = ζ} is stationary; and this is the desired family of disjoint stationary sets.

Again, by elementarity, if there is such a ξ then there is one in M, so we can hope to find it there. Assume, to the contrary, that there is no such ξ. It follows then, that there is a definable function ξ → β_{ξ} where β_{ξ} is the minimum ordinal such that S(ξ, β_{ξ}) is not stationary. Therefore, for each ξ in M, β_{ξ} ∈ M. For each ξ ∈ cf(δ), a_{ξ}^{δ} ≥ a_{ξ}^{δ} hence δ ∈ S(ξ, a_{ξ}^{δ}) and so S(ξ, a_{ξ}^{δ}) is stationary by Lemma 5.5. Therefore β_{ξ} > a_{ξ}^{δ} for each ξ ∈ cf(δ).

To see that δ′ = cf(δ) must equal δ, note that otherwise {β_{ξ} : ξ ∈ δ′} (which we now know to be cofinal in δ) would be a member of M which would have to be bounded in M, since H(θ) ⊧ (∃γ ∈ κ) {β_{ξ} : ξ < δ′} ⊂ γ.

Our final contradiction will be to find an α with cofinality bigger than δ so that a_{δ}^{α} = δ; the contradiction being that δ ∈ W and a_{δ}^{α} ∉ W. Notice that since δ ∈ T = {α ∈ W : cf(α) = α}, and T ∈ M, it follows that T is stationary. Clearly then, T −δ is stationary. But now, by the definition of β_{ξ}, S(ξ, β_{ξ}) is non-stationary for each ξ ∈ M, hence we may choose an α ∈ T − ⋃{S(ξ, β_{ξ}) : ξ ∈ δ} with α > δ. Therefore, for each ξ ∈ δ, a_{ξ}^{α} < δ and, clearly, {a_{ξ}^{α} : ξ ∈ δ} is cofinal in δ. It follows that a_{δ}^{α} = sup{a_{ξ}^{α} : ξ ∈ δ} is equal to δ.

Proposition 5.9 (Baumgartner). Suppose that T is a tree with uncountably many levels but no uncountable branches. Suppose that F_{α} is a finite subset of T_{α} for each α ∈ ω_{1}, then there are α < β so that F_{α} ∪ F_{β} is an antichain.

Proof. Fix a countable elementary submodel M of H(θ) with T and {F_{α} : α ∈ ω_{1}} in M and let δ = M ∩ ω_{1}. We will find α ∈ M so that F_{α} ∪ F_{δ} is an antichain. Let n = |F_{δ}| and for α ∈ I_{n} = {α : |F_{α}| = n}, let {F_{α}(0), …, F_{α}(n − 1)} = F_{α}. Note that I_{m} ∈ M for each m. Since δ is a limit ordinal, there is a β < δ so that x⃗_{0} = {F (i) ↾ β : i < n} has cardinality n. Let Γ′ ∈ M denote the set of x⃗ ∈ [T]^{n} such that {α : (∃β) x⃗ = {F_{α}(i) ↾ β : i < n}} is uncountable and Γ = {x⃗ ∈ Γ′ : {α : (∃x′ ∈ Γ′ ∩ [T_{α}]^{n}) x⃗ < x′ (ordered coordinatewise)} is uncountable}. Using the elementarity of M we show that x⃗_{0} is a member of Γ. Indeed, the set {α : (∃x⃗ ∈ Γ′ ∩ [T_{α}]^{n}) x⃗_{0} < x⃗} is a member of M. If it were countable it would have a bound in M. However the existence of F_{δ}, implies that for each β < δ, (F_{δ}) ↾ β ∈ Γ′.

Suppose that i is maximal so that there exist x⃗_{1} ∈ Γ∩M so that x_{0}(j) ≤ x_{1}(j) for j < n and x_{1}(j) is incomparable with F_{α}(j) for j < i. We prove that i = n. If not, let Γ_{1} = {x⃗ ∈ Γ : x⃗_{1} < x⃗ coordinatewise}. Observe that if x⃗ ∈ Γ_{1}, then for every α, there is a y⃗ ∈ Γ ∩ T_{α} such that x⃗ < y⃗; note that y⃗ ∈ Γ_{1}. Therefore, {x⃗(i) : x⃗ ∈ Γ_{1}} cannot form a chain because it has members on cofinally many levels of T – in addition M will “know” this. Choose a β ∈ M and y⃗_{1}, y⃗_{2} ∈ Γ_{1} ∩ T_{β} so that y_{1}(i) is incomparable with y⃗_{2}(i). Certainly either y_{1}(i) or y_{2}(i) is incomparable with F_{α}(i) so let it be y_{1}(i). Since x_{1}(j) < y_{1}(j), y_{2}(j), it follows that y_{1}(j) is incomparable with F_{α}(j) for each j < i. Therefore, i is equal to n. Now, x_{1} ∈ Γ ∩ M, hence x_{1} ∈ Γ′ ∩ M; thus there are α, β in M such that x⃗_{1} = {F_{α}(i) ↾ β : i < n}. Clearly F_{α} ∪ F_{δ} is an antichain.

Elementary submodels and the preservation of formulas are is essential in the study of L and can be used to prove the following which we then use to show that ♢^{∗} is consistent.

Fact 1 (Condensation Lemma). If M is a transitive set model of ZF-P + V = L then there is an α such that M = L(α).

We will certainly not attempt to give the many details leading to the previous result (see [6]), however we should say that the class {L(α) : α an ordinal } is a definable class in L such that L(α) ⊂ L(β) for α < β, L(α) = ⋃_{β<α} L(β) for limit α, |L(α) ≤ |α · ω| and if θ > ω is regular, then L(θ) ⊧ZF-P + V=L.

Lemma 5.10. If θ ≥ ω_{2} is regular, and {M_{α} : α ∈ ω_{1}} is a chain of countable elementary submodels of L(θ) such that α ∈ M_{α+1} for each α < ω_{1}, then

{M_{α+1} ∩ P(α) : α ∈ ω_{1}}

forms a ♢^{∗}-sequence in L.

Proof. Fix X ⊂ ω_{1} and S a stationary subset of ω_{1}. We will find α ∈ S so that X ∩ α ∈ M_{α+1}. Let C be a cub set of α such that M_{α} ∩ ω_{1} = α. By Lemma 1, there is a countable M ≺ L(θ) so that X ∈ M and M ∩ ω_{1} ∈ S ∩ C. Since L(θ) models V = L, so does M. Let α = M ∩ ω_{1} and by the previous Fact, fix δ so that the transitive collapse of M is equal to L(δ). Since α = M ∩ ω_{1}, it follows that L(δ) ⊧ α = ω_{1}. Also, following the transitive collapsing function, we see that X ∩ α is in L(δ). It suffices to show that δ ∈ M_{α+1}. Now this follows from the fact that M_{α+1} ⊧ α < ω_{1}. Indeed, L(θ) ⊧ “(∃γ < ω_{1}) L(γ) ⊧ α < ω_{1}”. Therefore there is a such a γ ∈ M_{α+1}. Since γ ≤ δ implies that L(γ) ⊂ L(δ) it follows that δ < γ and so L(δ) ⊂ M_{α+1}.

6. Large cardinals

A cardinal κ is said to be (strongly) inaccessible if it is a regular (strong) limit cardinal. Many inductive proofs get stuck at inaccessible cardinals. For example a proof in which one can handle singular limits and successor cardinals would be complete if there were no inaccessible cardinals. Hausdorff’s proof that there are no measurable cardinals gets stuck at a strong limit since it shows that a measurable cardinal is regular and that if α is not measurable, then neither is 2^{α}. As is wellknown the consistency of the existence of an inaccessible cardinal cannot be shown from the consistency of ZFC. This is basically because the statement

κ strongly inaccessible → H(κ) ⊧ ZFC

can be formalized and if provable in ZFC would violate Gödel’s second incompleteness theorem.

A Mahlo cardinal is a cardinal in which the set of regular cardinals is stationary. Since the set of successor cardinals is not stationary in any ordinal it follows that the set of inaccessible cardinals is stationary in a Mahlo cardinal.

A cardinal κ is \underline{weakly compact} if κ > ω and κ → (κ)_{2}^{2}. This means that if the two element subsets of κ are partitioned into two sets, then there is a homogeneous set I ⊂ κ of size κ, i.e. [I]^{2} is completely contained in one of the sets.

Proposition 6.1. If κ is weakly compact, then κ has the tree property, i.e. there are no κ-Aronszajn trees.

Proof. A tree T is a κ-Aronszajn tree if levels and branches of T have cardinality less than κ. Suppose that κ is weakly compact and that T is a tree in which levels have cardinality less than κ. Let {t_{α} : α < κ} enumerate ⋃{T_{α} : α < κ} such that t_{α} < t_{β} implies α < β. For t, s ∈ T define Δ(s, t) = δ as follows: if s ≤ t or t ≤ s, then s ∈ T_{δ} or t ∈ T_{δ} respectively, otherwise, δ is the minimum such that there are incomparable s′, t′ ∈ T_{δ} such that s′ ≤ s and t′ ≤ t. Define s ◁ t if either t ≤ s or ξ < η where t_{ξ} ≤ t and t_{η} ≤ s where t_{ξ} and t_{η} both come from T_{Δ(s,t)}. Define {α, β} ∈ P_{0} iff α < β and t_{α} ◁ t_{β}. Let I ∈ [κ]^{κ} be such that either [I]^{2} ⊂ P_{0} or [I]^{2} ∩ P_{0} = ∅. We suppose that [I]^{2} ⊂ P_{0} and leave the symmetric case. Claim: for each δ < κ, there is a β(δ) such that t_{β(δ)} < t_{α} for all but fewer than κ many α ∈ I. Indeed, for all but fewer than κ many α ∈ I, there is some β such that t_{β} ∈ T_{δ} and t_{β} < t_{α}. This follows from the facts that |T_{δ}| < κ and that, since I is homogeneous, α ≤ α′ implies β < β′ where t_{β} < t_{α} and t_{β′} ≤ t_{α′} and t_{β}, t_{β′} ∈ T_{δ}.

It follows that {t_{β(δ)} : δ < κ} is a κ-chain in T.

We will skip the proofs that a weakly compact cardinal is strongly inaccessible and that the strongly inaccessible cardinals below κ are cofinal in κ (see Kunen’s article in the Handbook of Logic [5]).

Proposition 6.2. If κ is weakly compact and S ⊂ κ is stationary, then there is a strongly inaccessible λ < κ such that S ∩ λ is stationary in λ.

Proof. By Solovay’s theorem (5.8) we may assume that the set, Y, of strongly inaccessible cardinals less than κ which are not in S is cofinal in κ. Assume that for every λ ∈ Y, we may fix C_{λ} ⊂ λ such that C_{λ} ∩ S is empty – note that \overline{C_{λ}} ∩ S is also empty. The C_{λ}’s form κ-tree when ordered by end-extension, hence there is a set I ∈ [Y]^{κ} such that {C_{λ} : λ ∈ I} forms a κ-chain. Clearly ⋃_{λ∈I} C_{λ} is a cub in κ which is disjoint from S.

Next up in the (my) large cardinal hierarchy is a measurable cardinal. A cardinal κ is measurable if there is a κ-complete free ultrafilter on κ. An ultrafilter U is said to be \underline{normal} if for each regressive function f on κ there is a ξ < κ such that f^{−1}(ξ) is a member of U. Scott showed that if κ is measurable, then κ carries a normal ultrafilter (sometimes called a normal measure). Clearly a normal ultrafilter is κ-complete.

Lemma 6.3 (Rowbottom). If U is a normal ultrafilter on a measurable cardinal κ, then κ → (U)_{2}^{<ω}, where this means that if f : [κ]^{<ω} → 2, then there is a U ∈ U such that for any n ∈ ω and s, t ∈ [U]^{n}, f(s) = f(t).

Proof. Let f : [κ]^{<ω} → 2. We wish to find a U ∈ U so that |s| = |t| implies f(s) = f(t) for all s, t ∈ [U]^{<ω}. We prove, by induction, that for each f and n < ω, there is a U_{n} ∈ U so that |s| = |t| implies f(s) = f(t) for all s, t ∈ [U_{n}]^{≤n}. If this is proven, then U = ⋂_{n} U_{n} is the desired set. The case n = 1 follows simply from the fact that U is an ultrafilter. For each α < κ, define f_{α}(s) = f(s ∪ {α}) for s ∈ [κ − (α + 1)]^{<ω}. By inductive assumption, there is a U_{α,n} and a sequence e_{0}^{α}, …, e_{n−1}^{α} so that f_{α}(s) = e_{i}^{α} for all s ∈ [U_{α,n}]^{i} for i ≤ n. Since there are only finitely many choice for e_{0}^{α}, …, e_{n−1}^{α}, there is a U′ ∈ U so that e_{i}^{α} = e_{i}^{β} = e_{i} and, by the n = 1 case, f({α}) = f({β}), for all α, β ∈ U′ and i < n.

Define △{U_{α,n} : α < κ} to be the set {α : β < α → α ∈ U_{β,n}}. Since U is normal, △{U_{α,n} : α < κ} is a member of U; indeed, suppose that Y = κ − △{U_{α,n} : α < κ} is a member of U and define g(α) to be 0 if α ∉ Y and to be the minimum β < α such that α ∉ U_{β} otherwise. Fix ξ such that g^{−1}(ξ) ∈ U and note that this means that U(ξ, n) ∉ U.

Let U = U′ ∩ △{U_{α,n} : α < κ} and fix s ∈ [U]^{≤n+1}. We complete the inductive step by showing that f(s) = e_{i−1}. Let α = min(s) and recall that s − {α} ⊂ U_{α,n} and α ∈ U′. Therefore, e_{i−1} = f_{α}(s − {α}) = f(s ∪ {α}) = f(s).

If a cardinal κ is supercompact then for each λ and X ∈ V_{λ}, there is a μ ≥ λ such that V_{μ} has an elementary submodel M such that X ∈ M, |M| < κ, M ∩κ ∈ κ, and G(M ∩ V_{λ}) = V_{β} for some β, where G is the Mostowski collapsing function. This characterizes the smallest supercompact cardinal (see [7]) but we will not give the definition of a supercompact cardinal. We refer the interested topologically inclined reader to [3] for more details and applications to topology. However we have not defined V_{α}: V_{α} is the set of all sets with rank less than α; it follows that if x ∈ V_{α}, then P(x) is a subset of V_{α} and a member of V_{α+1}.

As an example, suppose that κ is supercompact and that X is a space with character less than κ which is not metrizable. We show that X has a subspace of cardinality less than κ which is not metrizable. Find M as above with λ, hence β, a limit. We first claim that G(X) is not metrizable. Assume that there is a σ-discrete base B for G(X). Since X ∈ V_{λ}, G(X) is in V_{β}, and so B is also a member of V_{β}. Therefore B is equal to G(B′) for some B′ in M. Since G is an isomorphism it follows that M ⊧ B′ is a base for X, in fact a σ-discrete one, but by elementarity, B′ would, in fact, be a σ-discrete base for X. What we want to now show is that X ∩ M is non-metrizable. Here is where the character assumption comes in. For each x ∈ X ∩ M, there is a local base B_{x} of x, such that B_{x} ∈ M and |B_{x}| < κ. By Lemma 4.4, M contains B_{x} and this guarantees that τ ∩ M and τ ↾ (X ∩ M) are the same topology on X ∩ M. Therefore G(X) is homeomorphic to X ∩ M.

7. Basic Forcing

Forcing divides topology – those that aren’t familiar with it do not embrace the work of those that utilize it. This is very unfortunate and quite unnecessary. There are a few basic principles, one or two technical facts and forcing becomes quite understandable and it should be an integral part of set-theoretic topology. This is not to say that forcing arguments are easy but, rather, that (once beyond Cohen’s fundamental theorem) the understanding of forcing itself is easy. Forcing \underline{arguments} involve well-ordering, induction, and other combinatorial tools – the heart and soul of General Topology.

As most people know, one starts with a countable transitive model M of ZFC and add to M a P -generic filter (defined below) G of some poset P ∈ M so as to define a model M[G] (all this taking place in some larger universe V). M[G] is the smallest countable transitive model of ZFC which contains M and G but this doesn’t tell us much about how to construct M[G]. What makes forcing work is that every member of M[G] can be constructed from a member of M and G by the most basic of prescriptions. For example, given a set X ∈ M, every subset of X in M[G] can be obtained from some τ ∈ M such that τ ⊂ P × X and the new set is simply equal to {x ∈ X : (∃p ∈ G) (p, x) ∈ τ} (see 7.3); this latter set might be denoted τ_{G} and τ could be called a name or P -name for τ_{G}. Clearly all such sets must be added to M[G] given the above requirements, but there are no more that are added. One can formalize the notion of a P -name and let M^{P} denote the class (contained in M) of all P -names τ and also the definition of a valuation by G, τ_{G} (see e.g. [6] or [10]).

It is not usually necessary to know the precise definition of a P -name but simply the existence of the class M^{P} and the basic forcing theorems listed below. Settheorists ofter work with simpler more natural descriptions of the members of M[G] such as the τ we mentioned above.

Definition 7.1. A set G ⊂ P ∈ M is P -generic for M, if G is a filter (i.e. closed upwards and the elements of G pairwise have lower bounds in G) and if G meets every set in M which is a dense subset of P (a set A ⊂ P is dense if every element of P is greater than some member of A).

The remarkable forcing theorem states that if G is a generic subset of a poset P ∈ M and M is a countable transitive model of (a sufficient fragment of ZFC) then

M[G] = {τ_{G} : τ ∈ M^{P} }

is also a countable transitive model of (a similar fragment) of ZFC which contains M and G.

The very important thing then about M[G] is that every element of M[G] has a name from M and the second forcing theorem holds:

Lemma 7.2. Suppose that M is a countable transitive model of ZFC and G is P - generic for M for some poset P ∈ M. Then for any τ_{1}, …, τ_{n} all in M^{P} and any formula φ(v_{1}, …, v_{n}), M[G] ⊧ φ((τ_{1})_{G}, …, (τ_{n})_{G}) if and only if there is a p ∈ G so that p ⊩ φ(τ_{1}, …, τ_{n}) .

The notation p ⊩ φ has two equally important meanings: Semantic: for every generic filter G such that p ∈ G,

M[G] ⊧ φ((τ_{1})_{G}, …, (τ_{n})_{G}) .

Syntactic (and therefore subject to detailed combinatorial analysis). One of our goals is to show that it is not necessary to work with such technical definitions so we will not give it. We will only use the fact that the existence of a syntactic definition implies that the ⊩_{P} relation is definable in M and for everything else we will use the semantic definition. For example, it follows that τ_{G} = {σ_{G} : (∃p ∈ G) p ⊩ σ ∈ τ}.

Most forcing arguments involve subsets of members of M or sets of subsets of members of M and for these we introduce very simple descriptions or what we might call unofficial names. We need names to do combinatorial analysis and to make statements in the forcing language, i.e. p ⊩ φ(τ). Our first unofficial name convention is that we will use members of M as names for themselves. If there is a potential for confusion then it is common to use x̌ as a P -name for the set x ∈ M.

When a set A ∈ M[G] is being discussed it is also common to let Ȧ denote a P - name for A. Now suppose that τ ∈ M^{P} and p ∈ P are such that p ⊩ τ ⊂ M. Let us show that there is an X ∈ M and (unofficial name) σ ∈ M such that σ ⊂ P × X and, for every P -generic G with p ∈ G,

τ_{G} = {x : (∃p ∈ G) (p, x) ∈ σ} .

This latter set is just the projection of σ along G. Let us agree that if σ is a subset of P × X (for any set X), then σ_{G} denotes this projection. We can treat σ as a name and note that we are claiming that p ⊩ τ = σ. To find X and σ simply use the forcing relation in M. For each q ∈ P, {x : q ⊩ x ∈ τ} is a set in M (it is definable in M and it is a set since if q ∈ G, then this set is a subset of τ_{G}). Let X = ⋃_{q<p}{x : q ⊩ x ∈ τ} and define σ = {(q, x) : q < p, q ∈ P, x ∈ X, and q ⊩ x ∈ τ}. The forcing theorem 7.2, implies directly that σ_{G} is equal to τ_{G} for all generic G which contain p. We will consider sets of subsets of X in 7.3.

When it is necessary to refer to G in a a forcing sentence, e.g. p ⊩ G ⊂ P, it is common to use Γ to denote a P -name for G (we cannot use G itself because names must be in M).

Before stating the next result let us make some remarks on some common conventions which reduce the verbiage in stating forcing results. We have been using M to denote the original (ground) model and thus M[G] to denote the extension. The implicit assumption is that M is a countable transitive model of ZFC in the “real” universe of sets, hence for each P ∈ M there is a P -generic filter for M, and thus M[G] is another countable transitive model of ZFC in V (and the process could continue). However, in practice, it is common to let V denote the ground model and to not mention that V is a countable transitive submodel of the real universe. We will now switch to using V to denote the ground model so that we will have the letter M available to denote submodels of V. With this understanding we will also assume that given any poset P ∈ V, there is a P -generic filter for V.

The key combinatorial notion for forcing is when a set is dense in the forcing poset P. Related notions are dense below p and predense below p. A set A is dense below p if for every q ≤ p, there is an a ∈ A such that a ≤ q, and A is predense below p, if {q ∈ P : (∃a ∈ A) q ≤ a} is dense below p. Also the notion of incompatible elements is important (but incomparable is not): p ⊥ q if there is no r ∈ P such that r ≤ p and r ≤ q. A set A ⊂ P is an antichain if it consists of pairwise incompatible elements. A maximal antichain is dense below each element and every dense set contains maximal (in P) antichains. Similarly if p ∈ G and D is predense below p then G ∩ D is not empty (i.e. p ⊩ G ∩ D ≠ ∅). Another simplification we will make is that we will assume that all our posets have a largest element denoted by 1 and that poset means separative poset, i.e. if p ≰ q then there is an r ≤ p such that r ⊥ q.

We return to our unofficial names. This is as technical as we will have to get with names.

Proposition 7.3. If τ is a P -name and p ∈ P is such that p ⊩ “∅ ≠ τ ⊂ P(X)” for some set X ∈ V, then there is a family S ∈ V such that σ ⊂ P × X for all σ ∈ S and for every P -generic G containing p, V [G] ⊧ τ_{G} = {σ_{G} : σ ∈ S}.

Proof. Assume that ρ is a P -name for B and let p ∈ G be such that p ⊩ “ρ ≠ ∅ and (∀y)(y ∈ ρ → y ⊂ X)” (since B ⊂ P(X)).

Let S be the set of all (unofficial names) σ ⊂ P × X such that p ⊩ σ ∈ τ. It is clear that p forces that {σ_{G} : σ ∈ S} is a subset of τ_{G} but it is not clear that p forces the two sets are equal. To see this, suppose that G is P -generic (p ∈ G) and that A is a member of τ_{G} (in V [G] of course). We have already shown that there is a σ_{0} ⊂ P ×X such that (σ_{0})_{G} = A; hence there is some q_{0} ∈ G such that q_{0} ⊩ σ_{0} ∈ τ. However, it does not follow that p ⊩ σ_{0} ∈ τ (thus σ_{0} ∈ S). We need what is called the maximum principle (see 7.4) but we will prove it in this special case. We may assume that we chose q_{0} ≤ p and suppose that we have chosen q_{β} < p (for β < α) together with σ_{β} such that q_{β} ⊩ σ_{β} ∈ τ and {q_{β} : β < α} is an antichain. If {q_{β} : β < α} is a maximal (below p) antichain, we stop. Otherwise we find some q′ below p which is incomparable with each q_{β}. Since q′ < p, q′ ⊩ τ ≠ ∅, hence there is some q_{α} < q′ and a σ_{α} such that q_{α} ⊩ σ_{α} ∈ τ. There is some α < |P |^{+} such that {q_{β} : β < α} is maximal. Recall that if G′ is a generic filter containing p, then there is exactly one β < α such that q_{β} ∈ G′. To get our σ ∈ S (which names A) we “glue” all the σ_{α} together as follows:

σ = ⋃_{β<α}{(q, x) : q ≤ q_{β} and q ⊩ x ∈ σ_{β}} .

The main thing to show (which we skip because it is easy) is that if q_{β} is in a generic filter G′, then σ_{G′} = (σ_{β})_{G′}. Therefore, p ⊩ σ ∈ τ and q_{0} ⊩ σ_{0} = σ. From this latter fact, it follows that σ_{G} = A. Thus A ∈ {σ_{G} : σ ∈ S}.

Another fundamental forcing theorem is called the maximum principle.

Lemma 7.4. If τ_{1}, …, τ_{n} are P -names and p ⊩ (∃x) φ(x, τ_{1}, …, τ_{n}), then there is a name τ, such that p ⊩ φ(τ, τ_{1}, …, τ_{n}). Furthermore, if {p_{i} : i ∈ I} ⊂ P is a maximal antichain, and if {τ_{i} : i ∈ I} is a family of P -names, then there is a name τ such that for every P -generic G, if p_{i} ∈ G, then τ_{G} = (τ_{i})_{G}.

A lot of forcing can be learned by forcing with Fn(I, 2), defined below, which adds what are called Cohen reals (and they are by far the simplest). Another thing one needs to do is to get some practice with the kind of combinatorics on posets that is most relevant to forcing (as in Kunen’s book doing MA first). Recall that P satisfies the κ-chain condition (κ-cc) if every antichain in P has cardinality less than κ. A poset is ccc if it satisfies the ℵ_{1}-cc. A poset is said to be κ-directed closed, or usually just κ-closed for short, if every directed set of size less than κ has a lower bound.

Examples: If I, J are sets then Fn(I, J) denotes the set of finite partial functions, ordered by reverse inclusion, whose domain are contained in I and whose range are contained in J. If κ is a cardinal then Fn(I, J, κ) is the same except that “finite” is replace by “cardinality less than κ”.

Proposition 7.5. If λ^{<κ} ≤ κ for each λ < κ, then Fn(I, 2, κ) satisfies the κ^{+}-cc for each set I.

We can make use of the following useful strengthening of Lemma 5.2

Lemma 7.6. Given a set X in a set model H and a regular cardinal κ, there is an elementary submodel M ≺ H such that X ∈ M, |M| ≤ κ^{<κ}, and M^{<κ} ∩ H ⊂ M.

Proof. Inductively use Lemma 5.2 to find an increasing sequence {M_{α} : α < κ} of elementary submodels of H so that X ∈ M_{0} and for each α < κ, |M_{α}| ≤ κ and M_{α}^{<κ} ∩ H ⊂ M_{α+1}. By Lemma 5.3, M = ⋃_{α<κ} M_{α} is the desired model.

Proof. (of Lemma 7.5) Let A be a maximal antichain of Fn(I, 2, κ) and fix a regular θ much larger than |I ∪ κ| so that H(θ) is closed under κ sequences and I ∈ H(θ). Use the previous lemma to find M ≺ H(θ) so that I, κ are both in M, |M| ≤ κ, and M^{<κ} ⊂ M. We finish by proving that A ∩ M is a maximal antichain of Fn(I, 2, κ) (hence A ⊂ M). One can, in fact, prove that M ∩ Fn(I, 2, κ) is a complete subalgebra of Fn(I, 2, κ), see Definition 7.21. Let f ∈ Fn(I, 2, κ) be arbitrary and let g = f ∩ M = f ↾ (M ∩ I). Since M^{<κ} ⊂ M, g ∈ M. Now since M ⊧ A is a maximal antichain, there is an a ∈ A ∩ M such that g ∪ a ∈ Fn(I, 2, κ). Since dom (f − g) ∩ dom (a) is empty, it follows that f ∪ a is also a function, hence f is compatible with A. Therefore A ∩ M is a maximal antichain.

We return to the discussion of our example. If G ⊂ Fn(ω, 2), then ⋃ G is a partial function from ω to 2.

Exercise: if G is P -generic over V, then dom (⋃ G) = ω.

Lemma 7.7. ∀y ∈ V, ⋃ G ≠ y

Proof. The simplest method is to observe that for each y ∈ V ∩^{ω}ω, the set D_{y} = {p ∈ Fn(ω, 2) : (∃n ∈ dom p) p(n) ≠ y(n)} is a dense subset of Fn(ω, 2). Since D_{y} ∈ V, G will meet D_{y} and so ⋃ G will not equal y.

Lemma 7.8. For all y ∈ V ∩ 2^{ω}, the set {n : ⋃ G ↾ [2^{n}, 2^{2n}) = y ↾ [2^{n}, 2^{2n})} is infinite.

Proof. We could proceed by defining a set of dense sets as in the previous proof but we’ll use this as an opportunity to introduce another common method. Frequently to show that a set in the forcing extension is infinite, it is best to show that it is not finite. Assume that y ∈ V ∩ 2^{ω} is such that V [G] ⊧ there are only finitely many n such that y ↾ [2^{n}, 2^{2n}) agrees with ⋃ G ↾ [2^{n}, 2^{2n}). Use the forcing lemma 7.2 to obtain a p ∈ Fn(ω, 2) so that p ⊩ (∃m)(n > m → y ↾ [2^{n}, 2^{2n}) ≠ ⋃ Γ ↾ [2^{n}, 2^{2n}). Next use the maximum principle to find τ so that p ⊩ τ ∈ ω and p ⊩ for each n ≥ τ, y ↾ [2^{n}, 2^{2n}) ≠ ⋃ Γ ↾ [2^{n}, 2^{2n}). The next step is to note that there is a q < p and an m ∈ ω so that q ⊩ τ = m; indeed, since V [G] ⊧ τ_{G} = m = for some m, there is a q ∈ G as desired by Lemma 7.2. But now, there is an n ≥ m so that the domain of q is contained in n. Let r = q ∪ y ↾ [2^{n}, 2^{2n}) and check that r is an extension of q in Fn(ω, 2) (i.e. r < q). Clearly r forces that y ↾ [2^{n}, 2^{2n}) is equal to ⋃ Γ ↾ [2^{n}, 2^{2n}). This is a contradiction since r being less than q will also forces, as does q, that y ↾ [2^{n}, 2^{2n}) does not equal ⋃ Γ ↾ [2^{n}, 2^{2n}).

Corollary 7.9. V [G] ⊧ V ∩ 2^{ω} has outer measure zero.

Exercise (after reading the next section): If G is Fn(ω_{2}, 2)-generic over V, then V [G] ⊧ every set of reals of size ℵ_{1} has measure zero.

The main application of “everything has a name” is to the preservation of ground model properties. These results usually depend on the combinatorial properties of the forcing notion (poset).

Lemma 7.10. If G is Fn(ω, 2)-generic over V, then ω_{1} is preserved, that is, 1 ⊩ ω̌_{1} is a cardinal.

Lemma 7.11. If P is ccc then every cardinal of V is preserved by forcing with P. That is, for each cardinal κ ∈ V, p ⊩ κ̌ is a cardinal.

See Lemma 7.14 for proofs of the previous two Lemmas. In the case of Fn(ω, 2) we can prove a stronger result.

Lemma 7.12. If G is Fn(ω, 2)-generic over V then V [G] ⊧ for each cofinal I ⊂ ω_{1}^{V} there is an I′ ∈ V such that V ⊧ |I′| = ω_{1} and V [G] ⊧ I′ ⊂ I. Therefore V [G] ⊧ “there is no ω-sequence cofinal in ω_{1}^{V}.

Proof. Let τ ∈ V be a name of a subset of ω_{1} and, in V [G], τ_{G} is cofinal in ω_{1}^{V}. Further suppose that τ_{G} does not contain any uncountable ground model set I′. Fix p ∈ G such that p ⊩ τ is cofinal in ω̌_{1} and that τ does not contain any uncountable ground model set. It is common to consider the following set in V: let τ_{p} denote the set of all α such that there is some q < p such that q ⊩ α ∈ τ. τ_{p} is the smallest set Y in V with the property that τ_{G} is contained in Y for every generic G which contains p. Another way to say this is that τ_{p} is the smallest set in V with the property that p ⊩ τ ⊂ τ_{p}. Clearly then τ_{p} is uncountable. For each α ∈ τ_{p}, fix a p_{α} < p such that p_{α} ⊩ α ∈ τ. Since Fn(ω, 2) is countable, there is a q so that I′ = {α : p_{α} = q} is uncountable (usually the combinatorics on P is more difficult than this). Therefore q ⊩ I′ ⊂ τ, which is a contradiction.

By contrast consider the following “collapsing” poset.

Proposition 7.13. Assume that G is Fn(ω, ω_{1})-generic over V, then V [G] ⊧ ω_{1}^{V} is countable; i.e. 1 ⊩ |ω̌_{1}| = ω (and ω̌_{2} = ω_{1}).

Proof. Again, ⋃ G is a function, this time the domain is ω and the range is a subset of ω_{1}^{V}. We can show that the range is in fact all of ω_{1}^{V} by showing that

D_{α} = {p ∈ Fn(ω, ω_{1}) : α ∈ range p}

is dense for each α < ω_{1}. This is trivial: given any p, choose n ∉ p and extend p by attaching (n, α); this extension is in D_{α}. To prove that

1 ⊩ ω̌_{2} = ω_{1}

it suffices to show that ω_{2}^{V} is a cardinal in V [G]. This follows from the next lemma.

Lemma 7.14. If P satisfies the κ-cc and if τ ∈ V is a P -name of a function with domain I such that p ⊩ τ(i) ∈ V for each i ∈ I, then there is a function F ∈ V such that F (i) is a subset of V of cardinality less than κ, and,

p ⊩ τ(i) ∈ F (i)^{⌣} for each i ∈ I .

Therefore if κ is regular and ȧ is a P -name such that p ⊩ ȧ ∈ [V]^{<κ}, then there is an A ∈ V ∩ [V]^{<κ} such that p ⊩ ȧ ⊂ Ǎ.

Proof. Fix an i; we define F (i) = {a ∈ V : (∃q ∈ P) q < p and q ⊩ τ(ǐ) = ǎ}, since the a associated with a q is unique, F (i) is a set in V by the axiom of replacement. For each a ∈ F (i), let P_{a} = {q ∈ P : q < p and q ⊩ τ(i) = a}. Since p ⊩ τ(i) ∈ V, it follows that ⋃_{a∈F (i)} P_{a} is predense below p (i.e. given any p′ < p, p′ ⊩ τ(i) ∈ V, hence there are q < p′ and a so that q ⊩ τ(i) = a; thus q ∈ P_{a}). Therefore p ⊩ τ(i) ∈ F (i). Now we must show that |F (i)| < κ. For each a ∈ F (i), fix any p_{a} ∈ P_{a}. We show that F (i) has cardinality less than κ by showing that {p_{a} : a ∈ F (i)} is an antichain of P. Fix a ≠ b ∈ F (i) and observe that p_{a} ⊩ τ(ǐ) = ǎ and similarly for p_{b}. Now if q were below both p_{a} and p_{b}, q would simultaneously force that τ(ǐ) was equal to ǎ and to b̌. This contradicts that p (and hence q < p_{a} < p) forces that τ is a function.

A poset P is said to be proper if forcing with P preserves stationary subsets of [θ]^{ω} for all θ. One defines cub subsets of [θ]^{ω} in a natural way: C ⊂ [θ]^{ω} is unbounded if for every b ∈ [θ]^{ω}, there is a c ∈ C such that b ⊂ c, and C is closed if the union of every countable chain from C is again in C. Hence a set is stationary if it meets every cub. However the working definition of proper is usually the following (see [10]):

Definition 7.15. A condition p in a poset P is said to be (M, P)-generic if p forces the generic filter to meet A ∩ M for each A ∈ M such that A is a dense subset of P. This is equivalent to saying that for each dense A ⊂ P (A ∈ M) and each q < p, there is an r ∈ A ∩ M such that r is compatible with q. A poset P is proper if there is a λ such that for every regular θ ≥ λ and every countable M ≺ H(θ) with P ∈ M, there is, for each p ∈ P ∩ M, a q < p which is (M, P)-generic.

Lemma 7.16. (1) A ccc poset is proper.

(2) An ℵ_{1}-closed poset is proper and adds no new countable sets of ordinals.

(3) A proper poset preserves ω_{1}, but not necessarily ω_{2}.

(4) If G is P -generic for a proper poset P and if a ∈ V [G] is a countable subset of V, then there is a countable b ∈ V such that a ⊂ b.

Proof. A ccc poset P is proper because any p ∈ P is (M, P)-generic for any M ≺ H(θ) with P ∈ M. This is simply because every dense set in M contains maximal antichains which are in M. If A is a maximal antichain in M, then, by Lemma 4.4, A is contained in M since it is countable. Since A is predense below p, p forces that G meets A = A ∩ M.

Now suppose that P is ℵ_{1}-closed and that P ∈ M ≺ H(θ) with |M| = ω. Let {D_{n} : n ∈ ω} be an enumeration of the dense subsets of P which are members of M (of course this enumeration is not in M unless P is finite). Fix any p_{0} ∈ P ∩ M and recursively choose p_{n+1} < p_{n} so that p_{n+1} ∈ D_{n} ∩ M. To choose p_{n+1} one must note that p_{n} ∈ M and M ⊧ (∀q ∈ P) (∃r ∈ D_{n}) r < q. In the end, use that P is ℵ_{1}-closed to find a q ∈ P such that q < p_{n} for all n. The condition q is (M, P)-generic since if q is a member of a filter G, then p_{n} ∈ G ∩ (D_{n} ∩ M) for each n. To see that P adds no new countable sets of ordinals, assume that τ ∈ M is the name of a function into the ordinals with domain ω. We can assume that for each p ∈ D_{n}, there is an ordinal α(p, n) such that p ⊩ τ(n) = α(p, n). Therefore q forces that τ(n) = α(p_{n}, n) for each n, i.e. q ⊩ {τ(n) : n ∈ ω} is the ground model set {α(p_{n}, n) : n ∈ ω}. The key is that q decides the values τ(n) for each n, since for any name τ and any condition q, the set {x : q ⊩ x ∈ τ} is a ground model set.

The fact that a proper poset preserves ω_{1} follows from the fourth item. To see that a proper poset need not preserve ω_{2}, note that the poset ^{<ω_{1}}ω_{2} (sometimes called the countable condition collapse of ω_{2}) is countably closed, hence proper. One easily shows that the union of the generic filter is a function from ω_{1} onto ω_{2} (this is nearly identical to Proposition 7.13).

Let τ be a name and p ∈ P be such that p forces that τ_{G} is a function from ω onto a and that each member of a is from V (as in the semantic definition of forcing). Fix a suitably large θ and let M be a countable elementary submodel of H(θ) such that p, P, τ are all in M. Let q < p be (M, P)-generic. If we show that q ⊩ τ(i) ∈ M for each i ∈ ω, then we will have that q forces that a is contained in the countable set M. Define

D_{i} = {r ∈ P : (∃x) r ⊩ τ(i) = x} .

Since all the parameters of D_{i} are in M it follows that D_{i} is in M. We would like to say that D_{i} is dense in P and therefore that q forces that G ∩ (D_{i} ∩ M) is not empty. However all we have said is that p forces that τ(i) is a member of V – hence it follows that D_{i} is predense below p. Since q < p it does follow that G ∩ (D_{i} ∩ M) is not empty. That is, let D̄_{i} = D_{i} ∪ {r ∈ P : r ⊥ p}. Again D̄_{i} is in M and, this time, is dense. Assume that q (hence p) is in G and fix r ∈ G ∩ (D̄_{i} ∩ M). Since p and r are both in G, they must be compatible. Therefore r ∈ D_{i}. Now, r ∈ D_{i} ∩M, so there is an x ∈ M, such that r ⊩ τ(i) = x. This completes the proof.

There are posets which preserve ω_{1} but which do not preserve stationary subsets of ω_{1} – hence being stationary is not preserved by forcings which preserve cardinals (but being a cub is preserved).

Proposition 7.17. Let S be a stationary subset of ω_{1} which does not contain a cub. Then there is a poset P which preserves ω_{1} and introduces a cub which is disjoint from S.

Proof. Let P be the set of closed subsets of ω_{1} which are disjoint from S. Order P by reverse end extension, i.e. b < a if b ∩ (max a) + 1 = a. For each α < ω_{1}, E_{α} = {a ∈ P : a − α ≠ ∅} is easily seen to be dense. Therefore, if G is a generic subset of P, ⋃ G is a cofinal subset of ω_{1} which is disjoint from S. To see that ⋃ G is closed in ω_{1}, assume that β is a limit point. Fix any a ∈ G ∩ E_{α} and check that β is in fact a limit point of a, i.e. ⋃ G ∩ β + 1 = b because the ordering was end extension. The main thing to show is that ω_{1} is preserved. We can actually mimick the proof that ω_{1}-closed posets are proper. Suppose that ḟ is the name a function from ω into ω_{1}. We must show that if a ∈ P is arbitrary, then there is a b < a which forces that the range of ḟ is bounded. Since S does not contain a cub, its complement is stationary, hence there is a countable M ≺ H(θ) such that a, ḟ ∈ M (i.e. H(θ) is large enough) and δ = M ∩ ω_{1} ∉ S (see Lemma 5.5). As above, D_{n} = {r ∈ P : (∃α ∈ ω_{1}) ḟ(n) = α} is dense (we may assume, by the maximum principle that 1 ⊩ ḟ is a function from ω to ω_{1}). The plan is to choose a decreasing sequence a_{n} ∈ D_{n} ∩ M (hence a_{n} forces that ḟ(n) is below δ) so that there is a b ∈ P so that b < a_{n} for each n (and a_{0} < a). In other words we need to ensure that the closure of ∪_{n}a_{n} is disjoint from S. We do so by ensuring that max a_{n} converges to δ. Since δ will be the only new limit point of ∪_{n}a_{n} and δ ∉ S, {δ}∪∪_{n}a_{n} is a member of P which forces that the range of ḟ is bounded. To ensure this, let β_{n} be any sequence which is cofinal in δ. When a_{n} is chosen, be sure that it is a member of D_{n} ∩ E_{β_{n}}.

Another interesting and basic forcing is Prikry forcing. This forcing preserves cardinals but not cofinalities.

Proposition 7.18 (Prikry). Assume that U is a normal ultrafilter on a measurable cardinal κ and define p ∈ P iff there is a finite t_{p} ∈ [κ]^{<ω} and a U_{p} ∈ U such that p = ⟨t_{p}, U_{p}⟩ and U_{p} ∩ max(t_{p}) + 1 = ∅. P is ordered by p < q if t_{p} ⊃ t_{q}, t_{p} − t_{q} ⊂ U_{q}, and U_{p} ⊂ U_{q}. If G is P -generic, then in V [G] the cofinality of κ is ω, but all cardinals are preserved.

Proof. It is easily seen that if G is P -generic filter, then ∪{t_{p} : p ∈ G} is a countable sequence which is cofinal in κ. The key property of this forcing is known as the Prikry property which is used in several other forcings as well. Fix an ordinal α and a P -name τ. For each p ∈ P, there is a condition q < p so that t_{q} = t_{p} and either q ⊩ τ = α or q ⊩ τ ≠ α. That is, one can decide whether a formula in the forcing language is true or false without extending the finite part of the condition. This follows easily from Lemma 6.3. Define a function f : [κ]^{<ω} → 2 as follows: f(s) = 1 if and only if there is a q < p such that t_{q} = t_{p} ∪ s and q ⊩ τ = α. Apply Lemma 6.3 to obtain a U ∈ U such that U ⊂ U_{p} and f(s) depends only on |s| for all s ∈ [U]^{<ω}. The condition we want is (t_{p}, U). If (t_{p}, U) does not decide whether τ is equal to α or not, then there are q_{1} and q_{2} both less than (t_{p}, U) such that q_{1} ⊩ τ = α and q_{2} ⊩ τ ≠ α. We may extend either of them so as to ensure that |t_{q_{1}}| = |t_{q_{2}}|. Clearly, by definition, f(t_{q_{1}} − t_{p}) = 1, hence f(t_{q_{2}} − t_{p}) is also equal to 1. But this leads to a contradiction, for if q < p is such that t_{q} = t_{q_{2}} and q ⊩ τ ≠ α, then q and q_{2} would have to be incompatible. However they are not, since (t_{q_{2}}, U_{q} ∩ U_{q_{2}}) is below both of them.

Note that the fact that two conditions are compatible if they have the same first coordinate implies that P has the κ^{+}-cc, hence all cardinals above κ are preserved. If we show that all cardinals below κ are also preserved then we have that all cardinals are preserved since κ is a limit cardinal. Not only are cardinals below κ preserved but P adds no new subsets of any λ < κ. Indeed assume that ȧ is a name and p ∈ P. We will find a q < p and b ∈ V so that q ⊩ ȧ ∩ λ = b. We will even have that t_{q} = t_{p}. For each α < λ we can find U_{α} ⊂ U_{p} so that either (t_{p}, U_{α}) ⊩ α ∈ ȧ or (t_{p}, U_{α}) ⊩ α ∉ ȧ. Let U = ⋂{U_{α} : α < λ} and b = {α < λ : (t_{p}, U) ⊩ α ∈ ȧ} = ȧ_{(t_{p},U)}. Since U ∈ U, we let q = (t_{p}, U) and we are done.

Lemma 7.19. A standard ccc trick: if A is a subset of a ccc poset P and if |A| has uncountable cofinality, then there is a generic G which meets A in cardinality |A|.

Proof. One can prove this by an indirect method or in a more combinatorial fashion as follows. For each B ⊂ A, let D_{B} be the set of all p ∈ P such that B is predense below p. If B is not empty then D_{B} is not empty and if q ∈ D_{B} and r < q then r ∈ D_{B}. Note that if B ⊂ B′, then D_{B} ⊂ D_{B′}. Let us also note that E_{B} = {p : (∃a ∈ B) p < a} is a dense subset of D_{B}.

Claim: there is an S ⊂ A with |S| < κ such that for all T such that S ⊂ T ⊂ A and |T | < κ, D_{A−T} = D_{A−S}. (One should note that this does not hold for the family of E_{A−S}’s).

Indeed, if not we could choose an increasing sequence, {S_{ξ} : ξ < ω_{1}}, of less than κ-sized subsets of A so that ξ < η < ω_{1} implies that D_{A−S_{η}} is strictly smaller than D_{A−S_{ξ}}. For each ξ < ω_{1}, there is some p_{ξ} ∈ D_{A−S_{ξ}} which is not in D_{A−S_{ξ+1}}. Since p_{ξ} ∉ D_{A−S_{ξ+1}} there is a q_{ξ} < p_{ξ} which is incompatible with each member of A − S_{ξ+1}. It follows that if ξ < η < ω_{1}, then q_{η} is incompatible with q_{ξ}. Indeed, if r were below q_{ξ}, then r would be incompatible with every member of A − S_{η} and so r cannot be below p_{η} since this would make r a member of D_{A−S_{η}}. Since such an uncountable antichain cannot exit in a ccc poset, the Claim is proved.

Fix an S ∈ [A]^{<κ} as in the previous claim. Now let B be any collection of pairwise disjoint countable subsets of A − S such that each B ∈ B is predense below each member of D_{A−S} (equivalently, D_{B} = D_{A−S}) and such that B is maximal. We claim that B has cardinality κ. Indeed, if |B| < κ, then let T = S ∪ ⋃ B and note that D_{A−T} = D_{A−S}. Let C be any maximal antichain of E_{A−T}. Since E_{A−T} is dense in D_{A−T}, C is predense below each member of D_{A−T}. For each c ∈ C fix an a_{c} ∈ A − T such that c ≤ a_{c} (which we may do since c ∈ E_{A−T}). Let B = {a_{c} : c ∈ C}; since P is ccc, C, and thus B, are countable. B is predense below each element of C and so is predense below every element of D_{A−T} = D_{A−S}. This contradicts the maximality of B. To finish the proof of the Proposition, we just note that if p ∈ D_{A−S} is arbitrary and if G is P -generic and contains p, then G ∩ B is not empty for each B ∈ B.

Here is a much more subtle and difficult preservation argument. First we define what is often called Hechler forcing. An element of P_{H} is a pair p = (s, f), where, for some n, s ∈ ^{n}ω and f ∈ ^{ω}ω. The ordering on P_{H} is given by (s, f) < (t, g) if s ⊃ t, f(n) ≥ g(n) for all n, and s(n) > g(n) for all n ∈ dom (s) − dom (t). If G is P_{H}-generic, then ⋃{s : (∃f) (s, f) ∈ G} is a function in ω^{ω} which dominates (mod finite) the family ω^{ω} ∩ V.

Lemma 7.20 (Baumgartner). If {x_{ξ} : ξ ∈ λ} (λ regular) is a tower in [ω]^{ω} (ordered mod finite), and if G is P_{H}-generic, then {x_{ξ} : ξ ∈ λ} remains a tower in V [G].

Proof. Let ẋ be a name of a subset of ω and let ė be the name of the enumerating function for ẋ, i.e.

1 ⊩ {ė(k) : k ∈ ω} enumerates ẋ in increasing order .

Let SEQ denote the set ⋃_{n} ^{n}ω and, for each k ∈ ω, define the following wellfounded ranking on SEQ .

(1) D_{0}^{k} = {s ∈ SEQ : (∃f ∈ ^{ω}ω) (∃j) ⟨s, f⟩ ⊩ ė(k) = j};

(2) D_{α+1}^{k} = {s ∈ SEQ : (∃n ≥ |s|)(∀r ∈ ω)(∃t ∈ D_{α}^{k} ∩ ^{n}ω) t ⊃ s and t(i) ≥

r for i ≥ |s|};

(3) D_{α}^{k} = ⋃_{β<α} D_{β}^{k} when α is a limit ordinal.

It follows that D_{α}^{k} ⊂ D_{β}^{k} for α < β.

Claim 1. For all k, SEQ = ⋃_{α} D_{α}^{k}, i.e. every node in SEQ gets a rank.

Assume otherwise and let s be a member of SEQ which is not a member of D^{k} = ⋃_{α} D_{α}^{k}. Call t ⊃ s a \underline{minimal extension} if t is minimal with respect to being a member of D^{k}. For each n ≥ |s|, there are only finitely many minimal t ∈ ^{n}ω. Indeed, otherwise there would be some maximal j so that {t(j) : t ∈ ^{n}ω is a minimal extension of s} is bounded. Then some t′ ∈ ^{j+1}ω would be contained in infinitely many of these t and it would follow that t′ is in D^{k} – contradicting minimality. So we can define an f ∈ ^{ω}ω so that, for each n ≥ |s|, f(n) > t(n) for each mimimal extension t ∈ ^{n+1}ω. But now, there is ⟨t, g⟩ < ⟨s, f⟩ such that there is a j ∈ ω so that ⟨t, g⟩ ⊩ ė(k) = j. So t is in D_{0}^{k}, hence there must be an n so that t ↾ n + 1 is a minimal extension of s. But this means that f(n) > t(n) contradicting the definition of ⟨t, g⟩ < ⟨s, f⟩.

Now fix a countable M ≺ H(ω_{2}) so that ė ∈ M. Also find ξ < λ so that a − x_{ξ} is infinite for each a ∈ M ∩ [ω]^{ω}. We prove that

⊩ range ė − x_{ξ} is infinite .

Otherwise, fix ⟨s, f⟩ which forces that ė(k) ∈ x_{ξ} for all k greater than some fixed n. Now make the following definition:

Z_{k}(t) = {j : (∀g ∈ ^{ω}ω) ⟨t, g⟩ ⊮ ė(k) ≠ j}, i.e. Z_{k}(t) is the set of j such that, regardless of g, ⟨t, g⟩ has an extension which forces that ė(k) = j.

Surprisingly, for all t ∈ SEQ and k > n, Z_{k}(t) is not empty. This is proven by induction on α, where t ∈ D_{α+1}^{k}. Since t ∈ D_{α+1}^{k}, there is an m such that there are, for each r ∈ ω, t_{r} ∈ D_{α}^{k} ∩^{m}ω extending t so that t_{r}(i) ≥ r for m > i ≥ |t|. Let Z_{r} = ⋃_{r} Z_{k}(t_{r}). First of all, Z_{r} is finite. For otherwise, there is a j ∈ Z_{k}(t_{r}) − x_{ξ}, but notice that ⟨t_{r}, f⟩ forces that ė(k) is in x_{ξ} and so not equal to j, contradicting that j ∈ Z_{k}(t_{r}). Therefore there are j ∈ Z_{r} which are in Z_{k}(t_{r}) for infinitely many r. To see that j ∈ Z_{k}(t), fix any g. Let r be one of these infinitely many r which is larger than g(i) for each i < m and observe that ⟨t_{r}, g⟩ < ⟨t, g⟩. Since ⟨t_{r}, g⟩ has an extension forcing ė(k) to equal j, so does ⟨t, g⟩.

Finally we finish the proof, by observing that since Z_{k}(s) − k is not empty for each k (since ė(k) ≥ k), it follows that there is a j ∈ ⋃_{k} Z_{k}(s)−x_{ξ}. This contradicts that ⟨s, f⟩ ⊩ ė(k) cannot equal j since j ∉ x_{ξ}.

There are two major basic notions remaining. Iterated forcing and the factoring of forcing. These are really two sides of the same coin. One thinks of iterated forcing as the process of extending the model in many stages (finite or infinite). However it turns out that it is really a process of defining new posets and then forcing with these. More fundamental is the process of factoring a forcing, very roughly, if G′ is a subset of G, we can consider V [G′] and then work on how V [G] is obtained from V [G′]. Most of the time G′ is equal G ∩ P′ for some poset P′ ⊂ P (which is completely embedded).

Definition 7.21. A poset P is a complete subposet of Q (denoted P <∘ Q) if <_{P} =<_{Q} ∩P × P, (p ⊥_{P} q) ↔ (p ⊥_{Q} q), and maximal antichains of P are again maximal in Q. We would say that P can be completely embedded in Q if there is an isomorphism j from P into Q such j(P) is a complete subposet of Q.

For example, if P and Q are posets with 1 then both P ×{1_{Q}} and {1_{P} }×Q are complete subposets of P × Q. P × Q is called the product forcing and one usually identifies P × {1_{Q}} with P and {1_{P} } × Q with Q.

If a poset P is densely embedded in Q then P is completely embedded. Two posets are forcing equivalent if there is a single poset in which they can both be densely embedded. In fact, given a poset P, there is a unique complete Boolean algebra B such that P is completely embedded in B − {0}. Therefore two posets are forcing equivalent if these completions are isomorphic. One might guess why they are called forcing equivalent – they give the same generic extensions. If P is dense in Q and if G ⊂ Q is Q-generic, then certainly G ∩ P is P -generic. Similarly, if G ⊂ P is P -generic, then G_{Q} = {q : (∃p ∈ G) p < q} is Q-generic. In addition, e.g. in the latter case, V [G] is equal to V [G_{Q}] (where in the first case you use P -names and the second Q-names).

Exercise: Fn(ω, 2) is forcing equivalent to any countable atomless (separative) poset.

Lemma 7.22. A generic filter for P ×Q has the form G×H where G is V -generic for P and H is V [G]-generic for Q. In addition, given generic G and Q-generic H over V [G], H is certainly V -generic for Q, but also G is V [H]-generic for P.

Proof. Assume that K ⊂ P × Q is a generic filter and let G = {p ∈ P : (∃q ∈ Q) (p, q) ∈ K}. We first show that G is P -generic for V. Indeed, if D ⊂ P is dense, then D′ = D × Q is easily seen to be dense in P × Q. Since K ∩ D′ is not empty it follows that G ∩ D is not empty. Similarly, let H = {q ∈ Q : (∃p ∈ P) (p, q) ∈ K}. We will now show that H is Q-generic for V [G]. Let τ ⊂ P × Q be such that τ_{G} = {q ∈ Q : (∃p ∈ G) (p, q) ∈ τ} is a dense subset of Q. Fix p ∈ G such that p ⊩ τ is a dense subset of Q. We first show, in V, that τ (as a subset P × Q) is predense below (p, q) for each q ∈ Q. Indeed, let (p′, q′) < (p, q) and note that p′ also forces that τ (as a P -name now) is a dense subset of Q. Therefore, by the definition of τ_{G}, there is a p′′ compatible with p′ and a q′′ such that (p′′, q′′) ∈ τ and p′′ ⊩ q′′ ⊥̸ q′. The ordering on Q is the same in V [G] as in V, hence q′′ and q′ are compatible elements of Q. Since p′ < p, p′′ is also compatible with p. Therefore (p′, q′) is compatible with (p′′, q′′).

Now suppose that G is P -generic over V and H is Q-generic over V [G]. We want to show that G × H is P × Q-generic over V (it is easily seen to be a filter). Let D ⊂ P × Q be dense and define D^{∗} = {q : (∃p ∈ G) (p, q) ∈ D}. Clearly D^{∗} is a member of V [G] and if D^{∗} ∩ H is not empty, then D^{∗} ∩ (G × H) is not empty. Therefore we must show that D^{∗} is dense in Q. Fix any q ∈ Q and define, in V, D_{q} = {p ∈ P : (∃q′ ∈ Q) (q′ ≤ q and (p, q′) ∈ D)}. Since D is dense in P × Q, D_{q} is dense in P. Choose any p ∈ G ∩ D; the q′ ∈ Q which witnesses that p ∈ D_{q} is a member of D^{∗} which completes the proof that D^{∗} is dense.

To prove the last statement, we use the standard trick that product forcing can be done in either order. Indeed, suppose that G is P -generic and H is Q-generic over V [G]. Then by the first part of the Lemma, H × G is Q × P -generic over V and therefore G is V [H]-generic for P.

Corollary 7.23. If P and Q are posets then forcing with P × Q is the same as forcing first with P and then, in the resulting extension, forcing with Q. Of course P × Q is also forcing equivalent to Q × P.

Proof. Let G×H be P ×Q-generic over V. We must show that V [G×H] = V [G][H]. However both V [G × H] ⊂ V [G][H] and V [G][H] ⊂ V [G × H] follow from the previous Lemma and the minimality of forcing extensions.

Let us illustrate with some examples.

Proposition 7.24. If G is a generic filter for Fn(ω_{2}, 2), then in V [G] every ultrafilter on ω has character at least ω_{2}.

Proof. By Lemma 7.5, Fn(ω_{2}, 2) is ccc, hence ω_{2}^{V} is equal to ω_{2} in the extension. Assume that {τ_{ξ} : ξ < ω_{1}} is a family of Fn(ω_{2}, 2)-names of subsets of ω. Assume that p ⊩ {τ_{ξ} : ξ < ω_{1}} is an ultrafilter. A standard technique is to introduce equivalent small or canonical names. For each ξ and n, fix an antichain A(ξ, n) ⊂ Fn(ω_{2}, 2) (possibly empty) which is maximal with respect to the property that q ⊩ n ∈ τ_{ξ} for each q ∈ A(ξ, n). Define

σ_{ξ} = {(q, n) : q ∈ A(ξ, n)} .

Claim: p ⊩ σ_{ξ} = τ_{ξ}. If this were not the case, then there would be some q < p and an n such that q ⊩ n ∈ τ_{ξ} and q ⊩ n ∉ σ_{ξ} (or vice versa). Since q ⊩ n ∉ σ_{ξ}, q must be incompatible with each element of A(ξ, n). However, by the maximality condition on A(ξ, n) and the fact that q ⊩ n ∈ τ_{ξ}, there must be some member of A(ξ, n) which is compatible with q. The “vice-versa” case is even easier.

The advantage of the names σ_{ξ} is that they are small, in fact, they are each countable. Therefore there is an ℵ_{1}-sized set I ⊂ ω_{2} such that A(ξ, n) ⊂ Fn(I, 2) for each ξ, n. We may assume, in addition, that p ∈ Fn(I, 2). Now the technique is to note that Fn(ω_{2}, 2) is forcing isomorphic to Fn(I, 2)×Fn(ω_{2} −I, 2) (which is left as an exercise). Let G × H ⊂ Fn(I, 2) × Fn(ω_{2} − I, 2) be generic with p ∈ G. By Proposition 7.23, we know that V [G × H] = (V [G])[H] where H is Fn(ω_{2} − I, 2)- generic over V [G]. Here’s what happens now. Clearly {(σ_{ξ})_{G} : ξ < ω_{1}} is a member of V [G]. We show that no filter on ω in V [G] is still an ultrafilter in V [G][H] and this contradicts the assertion that p forces {(τ_{ξ})_{(G×H)} : ξ < ω_{1}} is an ultrafilter. The key step is getting the small filter into the inner model V [G] and then checking how the further forcing affects it.

We leave as an exercise that Lemma 7.8 finishes the proof.

Exercise: Use the technique of small names to show that if G is Fn(ω_{2}, 2)-generic over V (a model of CH), then 𝔠 = ω_{2} in V [G].

We illustrate the factoring idea further with the following technical result which also begins to introduce the concept of iterated forcing. It is important to realize that Fn(I, J, κ) is intended as a defined notion which is absolute if κ = ω but need not be otherwise. That is, Fn(ω_{1}, 2, ω_{1}) in V [G] need not agree with Fn(ω_{1}, 2, ω_{1})^{V}. In this proof we also introduce a key idea of Silver.

Proposition 7.25. Assume that V is a model of GCH and let G be Fn(ω_{1}, 2)- generic over V. Next, suppose that H is Fn(ω_{3}, 2, ω_{1})-generic over V [G]. Finally let K be Fn(ω_{1}, 2) × Fn(ω_{3}, 2, ω_{1})-generic over V. Then each of V [G][H] and V [K] are models of ω_{1} = ω_{1}^{V}, CH, and 2^{ω_{1}} = ω_{3} = ω_{3}^{V} but they are not the same models.

Proof. Without loss of generality, K traces the same generic filter on Fn(ω_{1}, 2) as that given by G, i.e. G × {1} ⊂ K. However despite our discussion in Lemma 7.23, we cannot assert that K has the form G × H′ where H′ is Fn(ω_{3}, 2, ω_{1})-generic over V [G]. This is because, as mentioned above, this notation refers to a defined notion rather than simply a set (e.g. [0, 1] always refers to the unit interval, whether in V or V [G]). We first have to worry about the values of ω_{3} and ω_{1}, but these are unchanged in this case. Therefore we can say that K has the form G × H′ where H′ is (Fn(ω_{3}, 2, ω_{1}) ∩ V)-generic over V [G]. The two sets Fn(ω_{3}, 2, ω_{1}) and Fn(ω_{3}, 2, ω_{1})∩V are certainly different. If G had been Fn(ω_{4}, 2)-generic they would not even have the same cardinality; if it had even been Fn(ω_{2}, 2)-generic only one would have had the ω_{2}-cc.

Let us first discuss the model V [K] – why, for example, does it preserve ω_{1}? We can consider V [H′][G] or V [G][H′] – this is easy the first way and educational the second.

By Lemma 7.5, Fn(ω_{3}, 2, ω_{1}) satisfies the ℵ_{2}-cc in both the models V and V [G] (in addition, Fn(ω_{3}, 2, ω_{1})∩V is ℵ_{2}-cc in V [G] since it is a subposet of Fn(ω_{3}, 2, ω_{1})). Therefore by Lemma 7.14, it preserves all cardinals greater than ω_{1}. Exactly analogous to the case of Fn(ω_{2}, 2), one can check that it adds ω_{3} new subsets of ω_{1}. By Lemma 7.16, it adds no new countable sets, hence CH is preserved and so is ω_{1}. The passage from V [H′] to V [H′][G] has been discussed so we skip the details.

On the other hand, V [G][H] yields the same extension so, in V [G], Fn(ω_{3}, 2, ω_{1})∩ V preserves cardinals and adds no new countable sets of ordinals etc. and yet it is not ℵ_{1}-closed. It is what is called ℵ_{1}-distributive or ℵ_{1}-Baire, which we shall not get into here. Since the poset Fn(ω_{2}, 2) is ℵ_{1}-cc and Fn(ω_{3}, 2, ω_{1}) is ℵ_{1}-closed (in V), one can show that every maximal antichain of Fn(ω_{3}, 2, ω_{1}) ∩ V of V [G] is refined by a maximal antichain from V. One can then show directly that Fn(ω_{3}, 2, ω_{1}) ∩ V does not add new countable sets of ordinals. This is due to Easton.

Let us now turn to V [G][H]. In this case we cannot turn this around and take V [H][G] since H is not a subset of a poset in V. However the cardinal arithmetic is quite easy to check. We have already covered how to analyze the cardinal arithmetic in V [G] and one can check that it gives us a model of CH. Therefore in passing from V [G] to V [G][H] we are forcing with an ℵ_{1}-closed ℵ_{2}-cc poset – these preserve cardinals and do not add new countable sets of ordinals.

Finally we want to show that the two models are not the same. In V, let T = ^{<ω_{1}}2 be the usual complete binary tree of height ω_{1}. Clearly in V [H′][G], T acquires many new branches (indeed ω_{3} of them). We will show that in the model V [G][H], T gets no new branches. This is a modification of a result of Silver which is due to Mitchell ([9]). They are both very fundamental ideas of set theory. We put these results in their own respective lemmas.

Lemma 7.26 (Silver). Assume that T is a tree whose levels have cardinality less than 𝔠 and that P is an ℵ_{1}-closed poset. Then P adds no new branches to T.

Proof. Let ḃ be the name of a branch of T and choose λ minimal so that there is a p ∈ P such that p ⊩ ḃ ∩ Ť_{λ} is empty. Therefore, for each q < p and α < λ there is an r < q and a t ∈ T_{α} such that r ⊩ ť ∈ ḃ. Assume there is a q < p such that b_{q} = {t ∈ T : (∃r < q) r ⊩ ť ∈ ḃ} forms a chain. Then q ⊩ ḃ = b̌_{q} and ḃ is not a new branch of T. Therefore we may assume that b_{q} is never a chain. Let p_{0} = p and inductively define ordinals α_{n} < λ and conditions {p_{s} : s ∈ ^{n}2} as follows. Let α_{0} be such that there are incomparable t_{0}, t_{1} ∈ b_{p_{0}} ∩ T_{α_{0}} and fix p_{⟨0⟩}, p_{⟨1⟩} in P so that p_{⟨i⟩} ⊩ t_{i} ∈ ḃ. Having defined p_{s} for each s ∈ ^{n−1}2 choose α_{n} large enough so that for each s ∈ ^{n−1}2, there are incomparable t_{s^{⌢}0} and t_{s^{⌢}1} in b_{p_{s}} ∩ T_{α_{n}} (one can easily check that if there are incomparable t, t′ in b_{p_{s}} then there are incomparable members of b_{p_{s}} ∩ T_{β} for all β < λ above the maximum of the levels of t, t′). For each s ∈ ^{n−1}2 and i < 2, fix p_{s^{⌢}i} < p_{s} so that p_{s^{⌢}i} ⊩ t_{s^{⌢}i} ∈ ḃ (where t_{s^{⌢}i} was chosen above). Now let α be the supremum of the α_{n} for n ∈ ω. Using the fact that P is countably closed, choose, for f ∈ 2^{ω}, p_{f} ∈ P so that p_{f} < p_{f↾n} for each n. Note that p_{f} forces that ḃ contains the chain {t_{f↾n} : n ∈ ω}. If α were equal to λ then each p_{f} would have completely determined ḃ, contrary to our assumption on ḃ. Therefore α < λ, and for each f ∈ 2^{ω} we may assume that p_{f} has been extended so that there is t_{f} ∈ T_{α} so that p_{f} ⊩ t_{f} ∈ ḃ. However, if f ≠ g, then t_{f} ≠ t_{g} for if n is minimal such that f ↾ n ≠ g ↾ n, then t_{f↾n} < t_{f} was chosen to be incompatible with t_{g↾n} < t_{g}. This, of course, contradicts that |T_{α}| < 2^{ω}.

Mitchell’s argument is more subtle. It can actually be improved to include the case where |I| = ω but the argument is more complicated.

Lemma 7.27 (Mitchell). Assume that T is a tree in V and that G is Fn(I, 2)- generic over V with |I| > ω. If P is a poset in V [G] which is countably closed and H is P -generic over V [G], then every branch of T which is in V [G][H] is already in V [G].

Proof. Work in V [G] and carry out the exact same construction of the sequence {α_{n} : n ∈ ω} together with the sets {p_{s} : s ∈ 2^{<ω}} and {t_{s} : s ∈ 2^{<ω}} and let α be the supremum of the α_{n}. In addition we can choose the p_{f}’s for f ∈ 2^{ω} as above. However we do not assume that |T_{α}| < 2^{ω} so at this point we take a different tact. We will choose an f ∈ 2^{ω} which is “too” generic for there to be a t_{f} ∈ T_{α} which is below t_{f↾n} for each n. Here’s how we choose f. This argument has taken place in the model V [G], hence we can fix Fn(I, 2)-names for the α_{n} as well as the p_{s} and t_{s} for all s ∈ 2^{<ω}. These are countably many names. We repeat the standard trick which shows that we can assume that the names for the t_{s} are countable. Fix s ∈ 2^{<ω}, and let T (s) denote the set of all t ∈ T such that there is a r_{t} ∈ Fn(I, 2) such that r_{t} ⊩ t = t_{s}. Clearly if t ≠ t′ are both in T (s) then r_{t} is incompatible with r_{t′}. Therefore T (s) is countable. In addition, for each t ∈ T (s) there is an antichain, A(s, t) ⊂ Fn(I, 2), maximal with respect to the property that r ⊩ t = t_{s} for each r ∈ A(s, t). It is easy to check that the name ⋃{(r, t) : r ∈ A(s, t) and t ∈ T (s)} is a name for t_{s}. Now let I′ be a countable subset of I so that A(s, t) ⊂ Fn(I′, 2) for each s ∈ 2^{<ω} and t ∈ T (s). Next, let J = {j_{n} : n ∈ ω} be any infinite subset of I − I′ and let f(n) = (⋃ G)(j_{n}) for each n. We can view G ∩ Fn(J, 2) as being generic over V [G ∩ Fn(I′, 2)] (by Lemma 7.23) and so, by Lemma 7.7, f will not equal y for any y ∈ 2^{ω} ∩ V [G ∩ Fn(I′, 2)]. Well then, working in V [G ∩ Fn(I′, 2)], for each t ∈ T_{α} let y_{t} = ⋃{s ∈ 2^{<ω} : t_{s} < t}. We know that f will be distinct from y_{t} for each t ∈ T_{α} (some may not be in 2^{ω} but f will still not equal them). Return to V [G] and consider p_{f}, which we may assume, for some t ∈ T_{α}, forces that t ∈ ḃ. But then, as before, it follows that t_{f↾n} < t for each n. By the construction of the t_{s}, we also have that t_{s} ≮ t for each s which is incomparable with f. Therefore y_{t} is equal to f – a contradiction.

We finish this section with two new results which are examples of non-preservation results in topology. These results give negative answers to questions posed in [4].

Theorem 7.28. It is possible to lower the density of a space without collapsing cardinals

Proof. Let κ be a measurable cardinal and let U be a normal measure on κ. We will use the product forcing Pr × Fn(κ, 2) where Pr is Prikry forcing using the measure U. Let G × H be Pr × Fn(κ, 2)-generic over V and work in the model V [H]. In this model we define a space X whose density will be κ but which will be separable in V [G × H]. Fix a bijection f : κ × κ → κ and define x_{α}(γ) to be equal H(f(α, γ)) if γ < α and to be 0 for γ ≥ α. It is obvious that the density of X = {x_{α} : α ∈ κ} (as a subspace of 2^{κ}) is no more than the cofinality of κ.

Now we prove that X is separable in V [G × H]. Let {α_{n} : n ∈ ω} denote the Prikry sequence added by Pr. Recall that conditions in Pr are of the form (< α_{0}, …, α_{n} >, U) where U ∈ U and α_{0} < ⋯ < α_{n} < κ. The ordering on Pr is end-extension of the α_{i}’s with the restriction that the new α_{i}’s must come from U and the usual ordering on the members of U. We will show that {x_{α_{n}} : n ∈ ω} is dense in 2^{κ}, hence in X. Let F ⊂ κ be finite and let φ ∈ 2^{F} and let ((< α_{0}, …, α_{n} >, U), p) be an arbitrary member of Pr × Fn(κ, 2). It suffices to find an extension ((< α_{0}, …, α_{n}, α >, U′), p′) which forces that φ ⊂ x_{α}. Choose any U′ ⊂ U (U′ ∈ U) such that dom(p) ∩ U′ is empty. Fix any α ∈ U′ and define p′ ⊃ p so that for each γ ∈ F, p′(f(α, γ)) = φ(γ). It should be clear that p′ forces that x_{α} ⊃ φ.

Theorem 7.29. It is possible to make a regular non-Lindelof space Lindelöf with cardinal preserving forcing. Similarly, the non-Lindelöf property need not be preserved for first countable Hausdorff spaces.

Proof. As in the previous result let G × H be Pr × Fn(κ, 2)-generic, where κ is a measurable cardinal and U is a normal measure on κ. Also fix f : κ × κ → κ as above. For each α < κ, define x_{α} ∈ 2^{κ} by x_{α}(γ) = 0 if γ + ω < α and otherwise, define x_{α}(γ) = H(f(α, γ)). Clearly, in V [H], X = {x_{α} : α < κ} is not Lindelof, but we will show that it is Lindelof in V [G × H].

Any open cover of X can be refined by a cover by basic open sets so fix a sequence of Pr× Fn(κ, 2)-names, {Ḟ_{α} : α < κ} of finite subsets of κ. Letting, for x ∈ 2^{κ}, [x ↾ F] denote the usual basic clopen subset of 2^{κ} consisting of all those y which agree with x on F, we have that 1 ⊩ {[x_{α} ↾ Ḟ_{α}] : α < κ} is a typical cover of X. It suffices to show that 1 ⊩ {[x_{α} ↾ Ḟ_{α}] : α < κ} has a countable subcover (where the forcing relation refers to Pr× Fn(κ, 2) ). For each α, let ṡ_{α} denote the finite partial function x_{α} ↾ Ḟ_{α} and let [ṡ_{α}] denote the corresponding basic clopen set.

Working in V, recursively fix countable elementary submodels M_{F} for F ∈ κ^{<ω} so that s_{α}, M_{F} are both in M_{F^{⌢}α}. We will show that V [G × H] ⊧ S = {[s_{α}] : α ∈ ∪_{n}M_{<α_{0},... ,α_{n}>}} is a cover of X.

Assume that (t, U) ∈ G and p ∈ Fn(κ, 2) are such that ((t, U), p) ⊩ x_{β} ∉ ⋃ S. By extending t ∈ κ^{<ω} we may assume that β < max t. Let λ = min M_{t} − β (of course we assume that β ∉ M_{t}). We will need to apply the Prikry Lemma. First choose k large enough so that f({λ + k} × κ) ∩ dom (p) = ∅ and let J be such that f({β} × J) = dom (p) ∩ f({β} × κ) (i.e. p says nothing about x_{λ+k} and decides x_{β} exactly on J). Extend p to p_{0} so that p_{0} forces that x_{λ+k} and x_{β} agree on J (keeping dom (p_{0}) ∩ f({β} × κ) = {β} × J). Recall that G is Pr-generic and consider ṡ_{λ+k}; we define a Fn(κ, 2)-name ṡ in V [G] such that (ṡ)_{H} = (ṡ_{λ+k})_{G×H}. For each α ∈ κ and e ∈ 2, let A_{α}^{e} ⊂ Fn(κ, 2) be an antichain which is maximal with respect to the property that, for each q ∈ A_{α}, there is (t′, U′) ∈ G such that

( (t′, U′), q) ⊩ ṡ_{λ+k}(α̌) = ě. Define ṡ = {((α, e)^{⌣}, q) : α < κ, e ∈ 2, and q ∈ A_{α}^{e}}. It

is easy to check that ṡ is as desired. Now, still working in V [G], ṡ is a Fn(κ, 2)-name of a finite partial function on κ, therefore, by Lemma 7.19, there is a countable set E ⊂ κ such that A_{α}^{0} ∪ A_{α}^{1} = ∅ for all α ∉ E. Since each A_{α} is at most countable, there is a countable set Y_{0} ⊂ κ such that q ∈ Fn(Y_{0}, 2) for all q ∈ ⋃_{α∈E} A_{α}^{0} ∪ A_{α}^{1}. Hence there is a countable set Y ⊃ E such that Y_{0} ∩ f({α} × κ) = ∅ for all α ∉ Y. Let Ẏ ∈ V be a Pr-name for Y; note that since Ẏ is definable from ṡ_{λ+k}, we may assume that Ẏ is in M_{t}. By the Prikry property, there are Ū and Ȳ in M_{t} such that (t, Ū) ⊩ Ẏ ∩ λ̌ = Ȳ. Since Ȳ ∈ M_{t} and M_{t} ⊧ Ȳ ⊂ λ and λ is the minimal element of M_{t} − β, it follows that Ȳ ⊂ β. By the definition of Ẏ, we ( (t′, U′), p′) < ( (t, Ū), p_{0}) such that there is an s such that ( (t′, U′), p′) ⊩ ṡ = š and dom (p′ − p_{0}) ∩ f({β} × κ) = ∅. Therefore we can extend p′ to some p̄ such that p̄ ⊩ š ⊂ x_{β} (note that dom (s) ∩ λ ⊂ Ȳ, hence 0 = s ↾ λ = s ↾ β ⊂ x_{β} ↾ β).

Now we turn to the first countable example. For each α < κ, let y_{α} = x_{α} ↾ ω, where x_{α} ∈ V [G] is defined as above. A neighbourhood base for y_{α} will be {[y_{α} ↾ n] ∩ {y_{β} : β ≤ α} : n ∈ ω}, where [y ↾ n] = {z ∈ 2^{ω} : y ↾ n ⊂ z}. One easily checks that in V [G], the space Y = {y_{α} : α < κ} with the above topology is Hausdorff and not Lindelöf (using the fact that κ is regular uncountable). In the model V [G][H], κ has countable cofinality of course and we will just use the fact that {y_{α} : α < κ} as a subspace of 2^{ω}, is a Luzin set in V [G]. We leave as exercises this fact together with the fact that, for each α < κ, {y_{β} : α ≤ β < α + ω} is a dense subset of 2^{ω}. Now suppose, in V [G][H], that U is an open cover of Y (in the new topology). For each α let n_{α} < ω be chosen so that U_{α} = [y_{α} ↾ n_{α}] ∩ {y_{β} : β ≤ α} is contained in some U ∈ U. Also let γ_{n} be a cofinal sequence in κ. For each n,

W_{n} = ⋃{[y_{β} ↾ n_{β}] : γ_{n} ≤ β < γ_{n} + ω}

is a dense open subset of 2^{ω} which is a member of V [G] (since Prikry forcing does not add any new small sets). Since Y is a Luzin set in 2^{ω}, Y − W_{n} is countable. Therefore,

{y_{ξ} : ξ < γ_{n}} − ⋃{U_{β} : γ_{n} ≤ β < γ_{n} + ω}

is countable. It follows, then that U has a countable subcover.

8. Iterations – Case Studies

Suppose that α is any ordinal, I ⊂ P(α) is a (not necessarily proper) ideal on α containing [α]^{<ω}. An α-staged iterated forcing sequence with supports in I is an object of the form P_{α} together with a sequence

⟨P_{ξ}, Q̇_{ξ} : ξ < α⟩

which satisfies the following conditions:

(1) elements of P_{ξ} (ξ ≤ α) are sequences of length ξ; (2) each P_{ξ} (ξ ≤ α) is a poset ordered as below;

(3) Q̇_{ξ} is a P_{ξ}-name of a poset;

(4) if ξ < η ≤ α and p ∈ P_{η}, then p ↾ ξ ∈ P_{ξ};

(5) for each ξ ≤ α, p ∈ P_{ξ} and β < ξ, p ↾ β ⊩ p(β) ∈ Q̇_{ξ};

(6) the support of p ∈ P_{ξ}, i.e. the set {β ∈ ξ : p(β) ≠ 1_{β}}, is a member of I;

(7) if p, p′ ∈ P_{ξ+1}, then p ≤ p′ iff p ↾ ξ ≤ p′ ↾ ξ and p ↾ ξ ⊩ p(ξ) ≤ p′(ξ) (in Q̇_{ξ});

(8) if ξ ≤ α is a limit ordinal then p ≤ p′ iff p ↾ η ≤ p′ ↾ η for all η < ξ.

The above definition actually defines a proper class but the easy way out of this is to restrict p(β) to be a P_{β}-name which is an element of H(θ) for some suitably large θ.

Theorem 8.1. If ⟨P_{α}, Q̇_{α} : α < κ⟩ is a finite support iteration such that, for each α < κ, ⊩_{P_{α}} Q̇_{α} is ccc, then P_{κ} is ccc.

The situation for chain conditions in other iterations is not so simple. However the following result is frequently sufficient.

Theorem 8.2 ([10], P96). Suppose that ⟨P_{α}, Q̇_{α} : α < κ⟩ is a countable support iteration such that ⊩_{P_{α}} Q̇_{α} is proper and has cardinality less than κ, and suppose that κ is regular such that μ^{ω} < κ for all μ < κ, then P_{κ} satisfies the κ-cc and ⊩_{P_{α}} 2^{ω} < κ for all α < κ.

8.1. Finite support. Let κ be an uncountable regular cardinal such that λ^{ω} < κ for all λ < κ and, for α ≤ κ, let P_{α} be the finite support iteration where we take Q̇_{β} to be the P_{β}-name of P_{H} as defined in Lemma 7.20. If G is P_{κ}-generic over V, let us see what we get in the model V [G] and what we do not get.

Proposition 8.3. MA(countable) holds, i.e. we add κ Cohen reals.

Proof. Finite support iterations of (non-trivial) posets always add Cohen reals. For each α ∈ κ, fix P_{α}-names {q(α, n) : n ∈ ω} so that ⊩ {q(α, n) : n ∈ ω} is a maximal antichain of Q_{α}. For each s ∈ F n(κ, ω), define p_{s} ∈ P_{κ} so that the support of p_{s} is the same as the domain of s and for each α in the domain of s, let p_{s}(α) = q(α, s(α)). The collection R = {p_{s} : s ∈ F n(κ, ω)} is completely embedded in P_{κ}.

We could also show that P_{H} itself adds a Cohen real. This can be seen as follows. If G ⊂ P_{H} is the generic filter then let g ∈ ^{ω}ω be defined as the union of {t ∈ ^{<ω}ω : (∃f ∈ ^{ω}ω) ⟨t, f⟩ ∈ G}. Let h(n) = 0 if and only if g(n) is even. We claim that h is a Cohen real, i.e. if A is a dense subset of F n(ω, 2) (in V) and is an element of V then there is an a ∈ A such that a ⊂ h. Assume, to the contrary, that there is no such a. By the Forcing Theorem, there is ⟨t, f⟩ ∈ P_{H} which forces there is no such A. However we first decode t so as to find a′ ∈ F n(ω, 2) so that a′(n) = 0 iff t(n) is even and a′(n) = 1 iff t(n) is odd (hence the domain of a′ is the same as the domain of t). Now, since A is dense, there is an a ∈ A so that a′ ⊂ a. Extend t (staying above f) to some t′ so that t′(n) is even iff a(n) = 0 and the domain of t′ is the same as the domain of a. Now if ⟨t′, f⟩ ∈ G, then a ⊂ h and we have finished the proof.

Proposition 8.4. P_{κ} does not fill towers. More generally if P_{κ} is a finite support iteration of posets which do not fill towers, then P_{κ} does not fill towers.

Proof. By Lemma 7.20, P_{H} does not fill any towers. Fix a tower {x_{ξ} : ξ ∈ λ} ∈ V (with λ regular) and proceed by induction on μ ≤ κ to show that P_{μ} does not fill this tower. The successor case follows immediately from Lemma 7.20 so assume that μ is a limit. Suppose that ẋ is a P_{μ}-name so that some p forces that ẋ − x_{ξ} is finite for all ξ < λ. For each ξ, fix p_{ξ} < p and n_{ξ} so that p_{ξ} ⊩ ẋ − x_{ξ} ⊂ n_{ξ}. Since {x_{ξ} : ξ < λ} is a tower, λ will be uncountable. Therefore, there is an n so that n = n_{ξ} for all ξ ∈ L with L cofinal in λ. Now find an I ⊂ L of cardinality λ so that {dom p_{ξ} : ξ ∈ I} forms a Δ-system and let δ < μ be the maximum element of the root. By Lemma 7.19, there is a P_{δ+1}-generic filter G so that I′ = {ξ ∈ I : p_{ξ} ↾ δ + 1 ∈ G} has cardinality λ (note, if this set does not have cardinality λ, then it would suffice to put just one element in G). Now we work in V [G]. Consider X = {m : (∃q ∈ P_{μ}) q ↾ δ + 1 ∈ G and q ⊩ m ∈ ẋ}. This X is clearly an infinite set, so there is a ξ ∈ I′ such that X − x_{ζ} is infinite for all ζ > ξ (recall that {x_{ξ} : ξ ∈ λ} is still a tower in V [G] by the induction hypothesis). Fix an m > n so that m ∈ X − x_{ζ} for infinitely many ζ ∈ I′ (i.e. for each ζ ∈ I′ − ξ there is an m_{ζ} ∈ X − x_{ζ} and one such m will be used λ many times). Since m ∈ X, there is a q such that q ↾ δ + 1 ∈ G and q ⊩ m ∈ ẋ. The support of q is finite so there is a ζ ∈ I′ such that m ∉ x_{ζ} and the intersection of the support of p_{ζ} with the support of q is contained in δ + 1. It follows that p_{ζ} and q are compatible. But this contradicts that p_{ζ} forces that ẋ − x_{ζ} is contained in n.

Corollary 8.5. P (𝔠) fails in V [G], but 𝔟 = 𝔠 holds.

Proposition 8.6. If {x_{ξ} : ξ < λ} is a tower in V [G] ∩ [ω]^{ω}, then λ < κ.

Proof. This is an example of a reflection result. Assume that {x_{ξ} : ξ < λ} is a tower in V [G]. By Lemma 7.3, there is a sequence {τ_{ξ} : ξ < λ} in V so that, for each ξ < λ, (τ_{ξ})_{G} = x_{ξ}, and p ⊩ {τ_{ξ} : ξ < λ} is a tower. Next, fix an elementary submodel M ≺ H(κ^{+}) such that {τ_{ξ} : ξ < λ} and p are elements of M, μ = M ∩ κ ∈ κ, and M^{ω} ⊂ M (see 7.6). If λ < κ then there is nothing to show, so assume otherwise and let δ be the supremum of M ∩ λ. The procedure now is to note that G_{μ} = G ∩ P_{μ} is a P_{μ}-generic filter and, since M^{ω} ⊂ M, V [G_{μ}] ⊧ {x_{ξ} : ξ ∈ δ ∩ M} is a maximal tower of [ω]^{ω}. We also want to note that x_{ξ} = (τ_{ξ})_{G} is the same as (τ_{ξ})_{G_{μ}}.

But now if we treat V [G_{μ}] as the ground model. Then V [G] is obtained by forcing with P_{κ}/G_{μ} = {p ∈ P_{κ} : p ↾ μ ∈ G_{μ}}. It is easy to prove, by induction on α ≤ κ, that P_{α}/G_{μ} is forcing isomorphic to the finite support iteration of length α′ (where μ + α′ = α) in which each iterand is P_{H}, i.e. P_{κ}/G_{μ} is P_{κ} from the point of view of V [G_{μ}]. However since we know that P_{κ} does not fill towers, this contradicts that τ_{δ} is supposed to fill the tower.

Proposition 8.7. If {x_{ξ} : ξ < λ} is a tower in V [G] ∩ [ω]^{ω}, then λ = ω_{1}. Left as an exercise.

Proposition 8.8. If T ∈ V is a Souslin tree, then T is still Souslin in V [G].

Proof. P_{κ} has what is called property K – given any uncountably many members of P_{κ} there are uncountably many that are pairwise compatible. Kunen and Tall have shown that Souslin trees are preserved by property K forcings. Indeed, assume that {ṫ_{α} : α < ω_{1}} are P_{κ} names and that p ⊩ {ṫ_{α} : α < ω_{1}} is an antichain of T. For each α, choose some p_{α} < p and t_{α} ∈ T so that p_{α} ⊩ ṫ_{α} = t_{α}. Because P_{κ} has property K, there is an uncountable I ⊂ ω_{1} such that {p_{α} : α ∈ I} are pairwise compatible. Since T is Souslin, there are α, β in I so that t_{α} ≤ t_{β}. But if q is less than p_{α} and p_{β} then q ≤ p and it forces that ṫ_{α} is compatible with ṫ_{β} contradicting the assumption on p.

Question 8.9. Does the Normal Moore Space Conjecture hold in V [G] if κ is supercompact in V?

8.2. Countable support.

Definition 8.10. Miller forcing or rational perfect set forcing is defined as follows. For a tree p ⊂ ^{<ω}ω (which we always assume is closed downwards, i.e. if s ∈ p, then \{s ↾ j : j ∈ dom s\} ⊂ p), let us say that s is a \underline{splitting} node of s if the set X_{s}^{p} = {m : s ^{⌢} m ∈ p} is infinite. Miller forcing, P_{M}, then is the set of subtrees of ^{<ω}ω with the property that for each t ∈ p, there is a splitting node s ∈ p such that t ⊂ s. Let split(p) denote the set of splitting nodes of p. The poset is ordered by inclusion. The set of p with the property that each s ∈ p is either splitting or has a unique immediate successor is dense so we shall assume that each condition has this property. Therefore split(p) has a minimal element called the root of p. A node s ∈ split(p) is said to be at splitting level n if there are precisely n members of split(p) below it. A final useful bit a notation: if s ∈ p then p_{s} = {t ∈ p : s ⊂ t or t ⊂ s} is a condition of P_{M} such that p_{s} ≤ p and, if s ∈ split(s), s is the root of p_{s}.

Let P_{ω_{2}} denote the countable support iteration of Miller forcing.

The key to proving properties of Miller forcing and many forcing notions like it (beginning with Sacks and Laver forcings) is the idea of a fusion sequence. Beginning with a condition p_{0}, one builds a descending sequence of conditions, {p_{n} : n ∈ ω}, with the idea that the intersection p_{ω} = ⋂_{n} p_{n} will be a condition. The intersection need not, in general, be a condition since it may not have enough splitting nodes. The method requires that at stage n, certain members of split(p_{n−1}) are chosen (e.g. the nodes at level n) and a commitment is made that they will be in p_{m} for all m. In order that these chosen nodes be splitting nodes in p_{ω} one must be sure that, for each of them, for infinitely many m, the nodes committed at stage m will include an increasingly large (finite is sufficient) set of splitting successors of the given node. The idea is given in the following standard proof. Of course one could take p_{m} = p_{0} for all m, but the idea is that there are infinitely many properties that we would like p_{ω} to have – if we are able to find p_{n+1} < p_{n} with the n-th property (while keeping the promise on keeping certain nodes) then p_{ω} (being less than p_{n} for each n) will have all of these properties. Usually it is (p_{n})_{s}, for s among the nodes newly committed at the n-th stage that have the special propery. This is best illustrated with examples.

Proposition 8.11. Miller forcing is proper.

Proof. Let p ∈ P_{M}and fix a countable elementary submodel M of H(ω_{2}) such that p, P_{M} ∈ M. Let {D_{n} : n ∈ ω} enumerate all the dense subsets of P_{M} which are members of M. We build a fusion sequence p_{n} with p_{0} = p so that p_{ω} = ⋂_{n} p_{n} is (M, P_{M})-generic. The proof when P_{M} is countably closed is to ensure that p_{n} ∈ D_{n} ∩ M however this is simply impossible (e.g. q ∈ D_{n} may imply that the root of q has domain at least n). Rather, here is what is done. If q is any extension of p_{ω}, then the root of q will be a splitting node of p_{ω}. The sequence p_{n} can easily be constructed so that the splitting nodes of p_{ω} are precisely the specially saved nodes in the fusion sequence. We must show that, for a fixed n, q is compatible with some member of D_{n} ∩ M. This is where p_{n+1} comes in: the root of q is compatible with one of the nodes, s, on the n-th level of p_{n+1} (the lower levels are for D_{k} k < n). In the construction we ensure that (p_{n+1})_{s} is in D_{n} ∩ M; hence q is compatible with a member of D_{n} ∩ M. It is worth noting that while (p_{n+1})_{s} is in D_{n} ∩ M, hence in M, p_{n+1} itself is not expected to be in M let alone D_{n}. We leave the rest of the proof as an exercise after proving the following lemma (to apply the lemma here, choose each p^{s} to be a member of D_{n} ∩ M).

Lemma 8.12. Suppose p ∈ P_{M} and that S is a set of pairwise incomparable elements of p. For each s ∈ S, let p^{s} be any extension of p_{s} and let

q = (p − ⋃{p_{s} : s ∈ S}) ∪ (⋃{p^{s} : s ∈ S} .)

Then q is a member of P_{M} and q ≤ p. In words, q is obtained from p by replacing each p_{s} by p^{s}.

As an example let us prove that Miller forcing preserves that (ω^{ω})^{V} is unbounded with respect to <^{∗}. We prove something slightly stronger. This is what Shelah calls the property of being almost ω^{ω}-bounding. The stronger property is needed in order to apply the iteration lemmas cited later.

Lemma 8.13. If τ is a P_{M}-name of a function from ω to ω, and if p ∈ P_{M} then there is a g ∈ ω^{ω}, such that for every A ∈ [ω]^{ω}, there is a q < p such that for each s ∈ split(q) and m ∈ X_{s}^{q}, there is an n ∈ A − m so that q_{s^{⌢}m} ⊩ τ(n) < g(n). Therefore, for each A ∈ [ω]^{ω} there is a q < p such that q ⊩ {n ∈ A : τ(n) < g(n)} is infinite.

Proof. We say that q forces a value on τ(n) if there is some m ∈ ω such that q ⊩ τ(n) = m.

Step 1: there is a p′ < p so that for each n and each s at splitting level n of p′, and for each m < n, (p′)_{s} forces a value on τ(m).

Perform the following fusion. Let p_{0} = p. At stage n + 1, let S_{n} be the set of all s ∈ p_{n} which are at splitting level n (note that the members of S_{n} are pairwise incompatible). For each s ∈ S_{n}, choose p^{s} < (p_{n})_{s} so that p^{s} forces a value on τ(n) (by induction, (p_{n})_{s} already forces a value on τ(m) for all m < n). Let p_{n+1} be obtained by replacing each (p_{n})_{s} (s ∈ S_{n}) by p^{s} as in Lemma 8.12. Then p′ is just equal to ⋂_{n} p_{n}. Note that at stage n + 1, the members of S_{n} did not necessarily remain splitting nodes but S_{n} is a subset of p′ and this guarantees that p′ ∈ P.

For ease of notation, suppose that p has the property that we have shown that p′ will have. Now for each branch b ⊂ p, there is a function f ∈ ω^{ω} such that, for each n, there is an s ∈ b such that p_{s} ⊩ f ↾ n = τ ↾ n. For each s ∈ p, fix a branch b_{s} containing s and let f_{s} denote the corresponding function on ω. Let g ∈ ω^{ω} be such that f_{s} <^{∗} g for all s ∈ p. Given A, we perform another fusion to find our q.

By induction we will have that if s is at splitting level n in p_{n} then (p_{n})_{s} = p_{s} (if we work inside a countable elementary submodel M and choose g so that f <^{∗} g for all f ∈ M ∩ ω^{ω} we wouldn’t have to be this careful). Again, let p_{0} = p and suppose we have chosen p_{n} so that for each s at splitting level less than n in p_{n} and each m ∈ X_{s}^{p_{n}}, there is a k ∈ A − m such that (p_{n})_{s^{⌢}m} ⊩ τ(k) < g(k). Let S_{n+1} denote the nodes in p_{n} which are at splitting level n + 1. For each s ∈ S_{n+1} there is a unique m_{s} and s′ such that s′ is at splitting level n, and s′ ^{⌢} m_{s} ⊂ s. It follows that (p_{n})_{s′⌢m_{s}} = (p_{n})_{s}. We must ensure that (p_{n+1})_{s} ⊩ τ(k) < g(k) for some k ∈ A − m_{s} for each s ∈ S_{n+1}. By our inductive assumption, (p_{n})_{s} = p_{s}, hence b_{s} is a subset of p_{n}. Choose a k ∈ A − m_{s} so that f_{s}(k) < g(k) and let s′′ ∈ b be such that p_{s′′} ⊩ τ(k) = f_{s}(k). Without loss of generality s ≤ s′′ and we set p^{s} = (p_{n})_{s′′} for the application of Lemma 8.12. Now if s′ < s is the node at splitting level n, then (p_{n+1})_{s′^{⌢}m_{s}} = p^{s} and is greater than q_{s′^{⌢}m_{s}} (where q = ⋂_{n} p_{n}) hence we will have that there is a k ∈ A − m_{s} such that q_{s′^{⌢}m_{s}} ⊩ τ(k) < g(k) as desired.

Fix any n ∈ ω. To show that q ⊩ (∃k ∈ A − n) τ(k) < g(k), fix an r < q. It suffices to show that each r has an extension r′ which forces τ(k) < g(k) for some k ∈ A − n. The root of r is a splitting node, s, of q. Choose any m > n such that s^{⌢} m ∈ r ⊂ q, and fix k ∈ A − m such that q_{s^{⌢}m} ⊩ τ(k) < g(k). Therefore r_{s^{⌢}m} ⊩ τ(k) < g(k).

Lemma 8.14. Let p ∈ P_{M} and let f : split(p) → 2 be arbitrary, then there is a q < p so that f(s) = f(s′) for all s, s′ ∈ split(q).

Proof. Assume that for each s ∈ split(p) there is an s′ ⊃ s so that f(s′) = 0. Otherwise, there is s ∈ split(p) so that q = p_{s} is such that f(s′) = 1 for all s ∈ split(q). Recursively build a condition q by choosing the members of split(p) which will also be in split(q). Let s_{0} be the root of p and let {(i_{k}, j_{k}) : k ∈ ω} be an enumeration of ω × ω so that i_{k}, j_{k} ≤ k. At stage k, fix any m ∈ X_{s_{i_{k}}}^{p} so that no s_{ℓ} (ℓ < k) extends s_{i_{k}} ^{⌢} m and let s_{k} be any extension of s_{i_{k}} ^{⌢} m so that f(s_{k}) = 0. Then q = ⋃{{s_{k} ↾ j : j ∈ dom s_{k}} : k ∈ ω} is the desired condition. We need to check that split(q) = {s_{k} : k ∈ ω}.

Proposition 8.15 ([8]). Miller forcing preserves P -points of ω^{∗}, i.e. if U is a P -point ultrafilter on ω and if G is P_{M}-generic, then, in V [G], U generates an ultrafilter.

Proof. Let U be a P -point of ω^{∗} and suppose that p ⊩ Ẏ ⊂ ω. We will show that there is an X ∈ U and a q < p so that either q ⊩ X ⊂ Y or q ⊩ X ∩ Y = ∅.

By an argument similar to the first part of the proof of Propostion 8.13, we may assume that if s is a level n splitting node of q, then q_{s} decides Ẏ ∩ n. In a similar fashion, we can assume that if m is in X_{s}^{q} = {k ∈ ω : s^{⌢} k ∈ q}, then q_{s^{⌢}m} decides Y ∩ m. Consider yet one more fusion. We want to show that we may assume that there is a Y_{s} ⊂ ω such that for each n ∈ Y_{s}, the set of m ∈ X_{s}^{q} such that q_{s^{⌢}m} ⊩ n ∉ Y_{s} is finite, and for each n ∉ Y_{s}, the set of m ∈ X_{s}^{q} such that q_{s^{⌢}m} ⊩ n ∈ Y_{s} is also finite. One gets this by performing the following fusion at each splitting node s (by induction on the splitting level). Let us just state one step in the fusion and leave the rest as an exercise. Suppose we have fixed integers m_{0} < ⋯ < m_{n−1} all in X_{s}^{q} and have decided on Y_{s} ∩ n. Consider the integer n: if there are infinitely many m ∈ X_{s}^{q} such that q_{s^{⌢}m} ⊩ n ∈ Ẏ then put n in Y_{s} and let m_{n} > m_{n−1} be the minimal such m and throw away all m > m_{n−1} such that q_{s^{⌢}m} ⊩ n ∉ Ẏ. On the other hand if there are not infinitely many such m, then do not put n in Y_{s} and throw away all m > m_{n−1} such that q_{s^{⌢}m} ⊩ n ∈ Ẏ and let let m_{n} > m_{n−1} be the minimal of those that remain.

By Lemma 8.14, we may assume that either Y_{s} ∈ U for all s ∈ split(q) or that Y_{s} ∉ U for all s ∈ split(q). In the first case fix X ∈ U so that X − Y_{s} is finite for each s ∈ split(q) (in the latter case, X ∩ Y_{s} is finite for each s ∈ split(q)).

Next we perform another fusion building {s_{n} : n ∈ ω} ⊂ split(q) together with an increasing sequence {k_{n} : n ∈ ω} so that ⋃{{s_{n} ↾ k : k ∈ dom s_{n}} : n even} and ⋃{{s_{n} ↾ k : k ∈ dom s_{n}} : n odd} will both be conditions. To begin let s_{0} = s_{1} be the minimal member of split(q) and let k_{0} = 0.

If n is even, fix some even m so that s_{m} needs another splitting successor (i.e. using an enumeration as in the proof of Lemma 8.14). Choose some s_{n} which is a minimal new member of split(q) ∩ q_{s_{m}} and so that Y_{s_{n}} ∩ k_{n−1} = Y_{s_{m}} ∩ k_{n−1}. Why can we do this? Choose ℓ large enough so that q_{s_{m}^{⌢}ℓ′} ⊩ Y_{s_{m}} ∩ k_{n−1} = Ẏ ∩ k_{n−1} for all ℓ′ ∈ X_{s_{m}}^{q} −ℓ. Suppose that s_{n} ⊃ s_{m}^{⌢}ℓ′ for some ℓ′ ≥ ℓ. By the definition of Y_{s_{n}}, there are infinitely many j so that q_{s_{n}^{⌢}j} ⊩ Y_{s_{n}} ∩ k_{n−1} = Ẏ ∩ k_{n−1} – fix such a j. Since q_{s_{n}^{⌢}j} < q_{s_{m}^{⌢}ℓ′}, it follows that q_{s_{n}^{⌢}j} ⊩ Y_{s_{m}} ∩ k_{n−1} = Ẏ ∩ k_{n−1} = Y_{s_{n}} ∩ k_{n−1} – hence Y_{s_{n}} ∩ k_{n−1} = Y_{s_{m}} ∩ k_{n−1}. Next let k_{n} > k_{n−1} be large enough so that X − k_{n} ⊂ Y_{s_{n}}.

For odd n, do the same thing except be sure to choose odd m.

Assume without loss of generality that X_{0} = X ∩ ⋃{[k_{n}, k_{n+1}) : n even} is in U. Let q_{0} = ⋃{{s_{n} ↾ j : j ∈ dom s_{n}} : n even}. We claim that q_{0} ⊩ X_{0} ⊂ Ẏ (wlog X ⊂ Y_{s_{0}}). Suppose that q′ ≤ q_{0} and j ∈ X_{0} are such that q′ ⊩ j ∉ Ẏ. Let s_{n} be the first splitting node of q′. Since q′ ≤ q_{0}, n is even. Fix ℓ large enough so that ℓ′ ∈ X_{s_{n}}^{q} implies that q_{s_{n}^{⌢}ℓ′} ⊩ Y_{s_{n}} ∩ j + 1 = Ẏ ∩ j + 1. Since s_{n} ∈ split(q′), there are ℓ′ ≥ ℓ so that s^{⌢} ℓ′ ∈ q′ and so, q′_{s_{n}^{⌢}ℓ′} ≤ q_{s_{n}^{⌢}ℓ′}. It follows, then, that j ∉ Y_{s_{n}}. Therefore j < k_{n} since X − k_{n} ⊂ Y_{s_{n}}. But now j is actually in X_{0}, hence j < k_{n−1}. Fix m < n so that s_{n} was constructed to extend s_{m}. By the construction Y_{s_{n}} ∩ k_{n−1} = Y_{s_{m}} ∩ k_{n−1}, hence j ∉ Y_{s_{m}}. We can repeat the above steps: j must be less than k_{m} but m is even, hence j < k_{m−1} and we recursively find a descending sequence m = m_{0} > m_{1} > ⋯ so that j ∉ Y_{s_{m_{i}}} and j < k_{m_{i}−1}. This stops when m_{i} gets to 0 and j ∈ X − Y_{s_{0}} is a contradiction.

Having proven that the single stage forcing is proper, almost ω^{ω}-bounding, and preserves P -point ultrafilters we turn to the iteration and to several of Shelah’s preservation results. We treat them as Axioms, however someone who intends to delve deeply into the subject should certainly learn the proofs of Lemmas 8.18 to 8.20. Our proof of Theorem 8.24 illustrates these techniques. Using Lemmas 8.19 and 8.2, we have the following result.

Proposition 8.16. P_{ω_{2}} is proper and satisfies the ω_{2}-cc.

In these iteration results one often need the following result. Let us point out that M[G] is defined as {τ_{G} : τ ∈ M ∩ V^{P} }.

Lemma 8.17. If P is a poset and M ≺ H(θ) with P ∈ M then M[G] ≺ H(θ)[G]. If, in addition, there is an (M, P)-generic condition q in G, then M[G] ∩ H(θ)^{V} = M.

Proof. If τ_{1}, …, τ_{n} are P -names in M and there is a p ∈ G, such that H(θ) ⊧ p ⊩ (∃x) φ(σ, τ_{1}, …, τ_{n}). Now, p, P, τ_{1}, …, τ_{n} are all in M, and H(θ) ⊧ (∃σ) p ⊩ φ(σ, τ_{1}, …, τ_{n}), hence, there is such a σ ∈ M. This verifies that, in V [G], the Tarski-Vaught criteria holds between H(θ)[G] and M[G], hence M[G] ≺ H(θ)[G].

Now suppose that q ∈ G is (M, P)-generic and that h ∈ M[G]. Since h ∈ M[G], there is a P -name τ ∈ M such that τ_{G} = h. Let D_{τ} = {p ∈ P : either (∃x) (p ⊩ τ = x̌) or (∀x)p ⊩ τ ≠ x̌}. Clearly D_{τ} is in M and it is easily seen to be a dense subset of P. Since q ∈ G is (M, P)-generic, there is a p in G ∩ D_{τ} ∩ M. Since p ∈ G and τ_{G} = h, p does not force that τ ≠ ȟ. Therefore, by elementarity, there is an x ∈ M such that p ⊩ τ = x̌. Clearly this x must be h, showing that h ∈ M.

Lemma 8.18. If M ≺ H(θ), p is (M, P)-generic, and p ⊩ q is (M[G], Q)-generic for a P -name of a poset Q (and G is the canonical name of the P -generic filter), then p ∗ q is P ∗ Q-generic.

Lemma 8.19. A countable support iteration of proper posets is proper.

Lemma 8.20. If ⟨P_{β}, Q̇_{β} : β < α⟩ is a countable support iterated forcing system with limit P_{α}, then for all countable M ≺ H(θ), with θ suitably large and ⟨P_{β}, Q̇_{β} : β < α⟩ ∈ M, and for all β < α with β ∈ M and for all p ∈ M ∩P_{α}, and q ∈ P_{β}, if q is (M, P_{β})-generic and q ≤ p ↾ β, there is an r ∈ P_{α} such that r is (M, P_{α})-generic, r ≤ q and r ↾ β = q.

Proposition 8.21 ([11]). For any countable support proper forcing iteration ⟨P_{α}, Q̇_{α} : α < κ⟩, if

⊩_{P_{α}} Q̇_{α} is almost ω^{ω}-bounding

then

⊩_{P_{κ}} ω^{ω} ∩ V is unbounded w.r.t. <^{∗} .

Proposition 8.22 ([1]). For any countable support proper forcing iteration ⟨P_{α}, Q̇_{α} : α < κ⟩ and any P -point U, if, for each α < κ,

⊩_{P_{α}} U generates a P -point

then also

⊩_{P_{κ}} U generates a P -point .

Corollary 8.23. Miller forcing does not add a Cohen real.

One can deduce several other of the cardinal functions from 8.22. For example 𝔲 = ω_{1}, hence 𝔟 = 𝔰 = 𝔱 = ω_{1}. However the proof of Proposition 8.22 is quite difficult, not to mention only applicable to cases where P -points are preserved. There is a quite general preservation scheme available in [11] which applies to things like 𝔟, 𝔰 and 𝔱. These take the form that if certain kinds of families are splitting (see [2]) or form a tower [11], and if each iterand preserve that this for the family, then the countable support iteration does as well.

Proposition 8.24. V [G] ⊧ 𝔰 = 𝔞 = 𝔟 < 𝔡 = ω_{2}.

Proof. We treat the above discussion as having taken care of the cardinals 𝔰 and 𝔟. We first show that 𝔡 = ω_{2}. As mentioned earlier Miller forcing adds a function f ∈ ^{ω}ω which is not bounded by any ground model function. Let {ḟ_{α} : α < ω_{1}} be a set of P_{ω_{2}}-names of functions from ω into ω. For each α < ω_{1} and n ∈ ω, there is a maximal antichain A(α, n) ⊂ P_{ω_{2}} so that for each p ∈ A(α, n) there is an m so that p ⊩ ḟ_{α}(n) = m (i.e. p forces a value on ḟ_{α}(n)). Choose a ξ < ω_{2} so that the support of p is contained in ξ for each p in ⋃{A(α, n) : α < ω_{1} , n ∈ ω}. Let G be P_{ω_{2}}-generic and let G_{ξ} = G ∩ P_{ξ}. Note that, for each α < ω_{1},

(ḟ_{α})_{G_{ξ}} = (ḟ_{α})_{G} .

Therefore {(ḟ_{α})_{G_{ξ}} : α < ω_{1}} is a set of functions in V [G_{ξ}]. Naturally the forcing Q_{ξ} is just Miller forcing and adds a function which is not less than any of the functions in V [G_{ξ}] ∩^{ω}ω.

Now we turn to the much harder task of showing that 𝔞 = ω_{1}. It doesn’t appear that any of the preservation results mentioned above can be used directly but the proof we give (also essentially taken from [11]) gives the flavour of how these results are proven.

We first show that the family A = {a_{α} : α < ω_{1}} constructed in Lemma 2.3 has a special combinatorial property which we can preserve (note that not every mad family is preserved). Let B = { {B_{n}^{β} : n ∈ ω} : α < ω_{1}} enumerate all countable families of finite subsets of ω. Recall that A has the property that for each α < ω_{1} and for each β < α, either there are infinitely many n such that B_{n}^{β} ⊂ a_{α} or there is an I ∈ I_{α} (the ideal generated by {a_{β} : β < α} ∪ [ω]^{<ω}) such that B_{n}^{β} ∩ I ≠ ∅ for all n.

Claim: If M ≺ H(θ) is countable and includes A and B, then for each family {B_{n} : n ∈ ω} ∈ M of finite subsets of ω, either there is an I in I_{δ} with B_{n} ∩ I not empty for all n, or there are infinitely many n with B_{n} ⊂ a_{δ}, where δ = M ∩ ω_{1}. The proof is simply that {B_{n} : n ∈ ω} is equal to {B_{n}^{β} : n ∈ ω} for some β ∈ M.

We finish the proof (but we have a long way to go) by showing that the above claim still holds in V [G_{α}] for α ≤ ω_{2}. Just as we had to construct the family A with special properties we have to strengthen this inductive assumption. Call a model M satisfying both the hypothesis and the conclusion of the claim \underline{good}. Recall that P_{α}/G_{β} (for β < α is equal to {p ∈ P_{α} : p ↾ β ∈ G_{β}}.

ST_{α} is the statement: for each β < α and countable M ≺ H(θ) such that P_{α}, β are both in M and for generic G_{β} ⊂ P_{β}, if M[G_{β}] ∩ ω_{1} = M ∩ ω_{1} and M[G_{β}] is good and if p ∈ M[G_{β}] ∩ P_{α} is such that p ↾ β ∈ G_{β}, then there is a q ∈ P_{α} such that q ↾ β ∈ G_{β}, q ≤ p, q is (M[G_{β}], P_{α}/G_{β})-generic, and, if G_{β} ∪ {q} is contained in a generic G_{α}, then M[G_{α}] is also good.

The successor step involves combinatorics on the iterand, in this case Miller forcing, while the limit stages involve arguments similar to those of 8.19, 8.20, and 8.21.

Assume ST_{α} holds and let us show that ST_{α+1} holds. By 8.20 it suffices to let β = α (and “α” is α + 1) in the statement ST_{α}. We may treat V [G_{α}] as the ground model in which we use M to denote M[G_{α}] (which is assumed to be good) and p = p(α) ∈ M is a member of the Miller poset, Q. We must produce a q < p which is (M, Q)-generic and which forces that M[G] is good. Let δ = M ∩ ω_{1} and let {{τ_{n}^{m} : n ∈ ω} : m ∈ ω} enumerate all the Q-names in M of members of [ [ω]^{<ω} ]^{ω} and let {D_{n} : n ∈ ω} enumerate the dense subsets of Q which are members of M. Set p_{0} = p and we’ll perform a usual fusion so that q = ⋃_{n} p_{n} will be M-generic. Assume that p_{n} has been chosen and that we are “freezing” the nodes in p_{n} which are at splitting level less than or equal n. Let t be a level n splitting node of p_{n}. Recursively, for m ≤ n, refine (p_{n})_{t} so that if it has a root preserving extension in D_{m}, then assume that (p_{n})_{t} is already in D_{m}. Now we turn to the τ_{k}^{m}’s. We repeat the following procedure for each m ≤ n. If (p_{n})_{t} has a root preserving extension which forces that every member of {τ_{n}^{m} : n ∈ ω} meets a fixed I ∈ I_{δ} then assume that (p_{n})_{t} is such a condition. Otherwise for each j such that t^{⌢} j ∈ p_{n}, find an extension q_{j} of (p_{n})_{t^{⌢}j} which forces some B_{ℓ}^{m} ⊂ a_{δ} for some ℓ ≥ n. To see that this is possible, let {B_{k} : k ∈ ω} = {B : (∃q < (p_{n})_{t^{⌢}j} q ⊩ B = τ_{ℓ}^{m} for some ℓ ≥ n}. By assumption, for each I ∈ I_{δ}, there are infinitely many k such that B_{k} is disjoint from I. In addition {B_{k} : k ∈ ω} is a member of M (the indexing is not important), therefore there is a k so that B_{k} ⊂ a_{δ}. Choose q_{j} to be a condition in M associated with this B_{k}. Finally let (p_{n})_{t} be replaced by ∪{q_{j} : t^{⌢} j ∈ (p_{n})_{t}}. We let (p_{n+1})_{t} be the result when we finish m = n and p_{n+1} when we finish each t.

To see that q = ∪_{n}p_{n} is (M, Q)-generic, let r ≤ q be in D_{m} ∩ G for any m. Let t be the root of r and note that t is a branching node of q so we may assume, by extending if necessary, that t is at the n-th branching level of q for some n ≥ m. In the inductive construction we came to the node t at stage n and we see that we obtained a “yes” answer to the question of whether (p_{n})_{t} has a root preserving extension in D_{m} (i.e. r is such an extension). Therefore, by the construction (p_{n+1})_{t} is a member of D_{m}. Since r ≤ p_{n+1} it follows that (p_{n+1})_{t} is a member of D_{m} ∩ G as was to be shown.

Now we check that M[G] is good. Since q is (M, Q)-generic, it follows that M[G] ≺ H(θ)[G]. By definition, if {B_{n} : n ∈ ω} is in M[G] then there is an m, so that {(τ_{n}^{m})_{G} : n ∈ ω} = {B_{n} : n ∈ ω}. Assume that, for each I ∈ I_{δ}, there are infinitely many n so that B_{n} ∩ I is empty and that B_{n} is not contained in a_{δ} for all n > ℓ. Fix r ∈ G which forces the previous statement and let t be the root of r. Again without loss of generality, t is an n-th level splitting node of q for some n > max{ℓ, m}. So when we came to the node t in the fusion, we discovered that (p_{n})_{t} did \underline{not} force that τ_{k}^{m} met I for all k and some fixed I. Therefore, for each appropriate j, q_{j} was chosen. In particular, choose any j so that t^{⌢} j ∈ r and note that (p_{n+1})_{t^{⌢}j} forces that τ_{k}^{m} is contained in a_{δ} for some k > n. This contradicts that r forces the opposite and is compatible with (p_{n+1})_{t^{⌢}j}.

Finally we turn to the limit case. The case where α has uncountable cofinality is essentially vacuous because the iteration is proper and so any new countable subset of [ω]^{<ω} will occur at some countable cofinality stage. This deserves a little more explanation. Let τ be a P_{α}-name (cf(α) > ω) and let p ⊩_{P_{α}} τ ⊂ ω. We produce a q < p and a P_{β}-name σ such that β < α and q ⊩_{P_{α}} σ = τ. Let M be any countable elementary submodel of a suitably large H(θ) such that p, P_{α} and τ are all in M. Let q < p be (M, P_{α})-generic and let σ = τ ∩ M, i.e. τ ⊂ P_{α} × ω and so σ ⊂ (P_{α} ∩ M) × ω. Since q is (M, P_{α})-generic, it follows that, for each n, and each generic G containing q, G∩{p : (p, n) ∈ τ} ≠ ∅ iff G∩{p : (p, n) ∈ (τ ∩M)} ≠ ∅. The only thing remaining to prove is that σ is a P_{β}-name for some β < α. This follows from the fact that M is a countable elementary submodel. Indeed, if p ∈ P ∩ M, then the support of p is a countable subset of α which, by 4.4, is a subset of M. Therefore each p ∈ P ∩ M is a member of P_{β} where β = sup(M ∩ α).

For cf(α) = ω we fix an increasing sequence {β_{n} : n ∈ ω} cofinal in α and work with the iteration ⟨P_{n}, Q̇′_{n} : n ∈ ω⟩ where P_{n} is isomorphic to what was P_{β_{n}} and Q̇′_{n} is the P_{β_{n}}-name of the iteration ⟨P′_{γ}, Q̇_{γ} : γ < β′_{n+1}⟩ where, β_{n} + β′_{n+1} = β_{n+1} and Q̇_{γ} is the P′_{γ}-name of the Miller poset. By induction on γ, P_{β_{n}} ∗ P′_{γ} is forcing isomorphic to P_{β_{n}+γ}. The poset Q̇′_{n} is often denoted by P_{β_{n+1}}/P_{β_{n}} (see [10] 3.3). However let us remark that in some circumstances one has to be careful about the set of P′_{n}-names that p(n) can equal for p ∈ P_{ω}. We refer the interested reader to 8.20 for the details.

Again let {{τ_{n}^{m} : n ∈ ω} : m ∈ ω} enumerate all the P_{ω}-names in M of members of [ [ω]^{<ω} ]^{ω} and let {D_{n} : n ∈ ω} enumerate the dense subsets of P_{ω} which are members of M. Define by induction on k ∈ ω, q_{k}, p_{k}, {ṅ(k, m) : m ≤ k} such that

(1) q_{k} ∈ P_{k} is (M, P_{k})-generic and forces that M[G_{k}] is good,
(2) q_{k} ↾ n = q_{n} for n < k,
(3) p_{k} ∈ P_{ω}
(4) q_{k} ≤ p_{k} ↾ k
(5) p_{k+1} ↾ k = p_{k} ↾ k and p_{k+1} ≤ p_{k}
(6) q_{k} ⊩_{P_{k}} “p_{k} ∈ M ∩ D_{k−1}”

(7) ṅ(k, m) is a P_{k}-name and p_{k+1} ⊩ “τ_{ṅ(k,m)}^{m} ⊂ a_{δ} or (∃I ∈ I_{δ}) τ_{ℓ}^{m} ∩ I is not empty for all ℓ”.

For k + 1, we work in V [G_{k}], G_{k} a generic subset of P_{k} with q_{k} ∈ G_{k}. So p_{k} ∈ M[G_{k}] and p_{k} ↾ k ∈ G_{k}. Similar to Lemma 7.22, we can find p_{k+1} ∈ M[G_{k}] ∩ D_{k} so that p_{k+1} ≤ p_{k} and p_{k+1} ↾ k ∈ G_{k}. Indeed, let D_{k}/G_{k} = {p ∈ D_{k} : p ↾ k ∈ G_{k}}. One more experienced with iterations would say that D_{k}/G_{k} is a member of M[G_{k}] and is a dense subset of P_{ω}/G_{k} = {p ∈ P_{ω} : p ↾ k ∈ G_{k}}. Then, since M[G_{k}] ≺ H(θ)[G_{k}], there is a p_{k+1} < p_{k} in M[G_{k}] ∩ D_{k}/G_{k}. More directly, we argue as follows. Since D_{k} is dense, D_{k}^{∗} = {p ↾ k : p ∈ D_{k} and p < p_{k}} is predense below p_{k} ↾ k in P_{k}. Now D_{k}^{∗} is a member of M and so there is some p′ ∈ G_{k} ∩ (M ∩ D_{k}^{∗}). By elementarity, there is a p_{k+1} ∈ M ∩ D_{k} such that p_{k+1} ↾ k = p′ and p_{k+1} < p_{k}.

In addition, we may use the induction hypothesis that M[G_{k}] is good to justify the assumption that, for each m ≤ k, p_{k+1} forces that there is an n(k, m) ≥ k so that τ_{n(k,m)}^{m} ⊂ a_{δ} or that there is some I ∈ I_{δ} such that τ_{n}^{m} ∩ I is not empty for all n. Indeed, just as in the successor case, let B_{0} = {B : (∃r < p_{n+1}) r ⊩ B = τ_{ℓ}^{0} for some ℓ > k }. If possible, find a B ∈ B_{0} which is contained in a_{δ} and then choose an extension, p_{n+1}^{0} ∈ M[G_{k}] of p_{n+1} which forces that this B to equal τ_{n(k,0)}^{0} for the appropriate value of n(k, 0). Repeat this for m = 1, …, k, and let the new p_{n+1} be equal p_{n+1}^{n}. Since all of this was done in V [G_{k}] (with G_{k} arbitrary generic with q_{k} ∈ G_{k}), there are P_{k} names for the n(k, m) and p_{k+1} such that q_{k} forces them to have the above properties. In actual fact, p_{k+1} is not a member of M but q_{k} forces that there is some p ∈ M such that p = p_{k+1}. Similarly, by the inductive hypothesis ST_{k+1} there is a P_{k}-name q̇ which is forced to be less than p_{k+1}(k) and which, itself, forces that M[G_{k+1}] is good. Define q_{k+1} to be q_{k} ∗ q̇.

In the end, we let q = ∪_{n}q_{n}. This q is (M, P_{ω})-generic since q ⊩ p_{n+1} ∈ D_{n} ∩ M. Let us check that M[G] is good. Fix m ∈ ω and assume that some r ∈ G forces that {n : τ_{n}^{m} ∩ I = ∅} is infinite for each I ∈ I_{δ}. If k > m is arbitrary, then, since w.l.o.g. r < q_{k}, we see that r ⊩ τ_{ṅ(k,m)}^{m} ⊂ a_{δ}.

9. 𝔻-completeness

In this section we introduce (by example only) Shelah’s notion of 𝔻-completeness in forcings. This technique is useful for producing models of CH in which diamond fails. This should be useful for the Moore-Mrowka question in the presence of CH. As a discipline we have spent a lot of time in studying ccc extensions and ultimately PFA whch resulted in many beautiful results concerning the structure of compact sequential spaces (inconsistent with ♢). In this section we reproduce the key new step of Avraham and Todorcevic’s new result that it is consistent with CH that there are no big coherent sequences (they have proven a much more general result). Foolishly, and so as to not alarm the reader, we do not give the definition of a 𝔻-completeness system until we need it (in the proof of Lemma 9.4) and, in fact, we give the definition of a simple 𝔻-completeness system (“simple” here does not mean simpler to understand).

Definition 9.1. Suppose that A = {a_{α} : α < ω_{1}} is a coherent sequence in ω_{1}. Define the poset P_{A}, by p = (a_{p}, α_{p}, S_{p}) where a_{p} ⊂ α_{p} and S_{p} is a countable subset of NS^{+} × α_{p} + 1 such that for each (S, γ) ∈ S_{p} there is an S′ ⊂ S such that (S′, γ) is in S_{p}^{+} where

S_{p}^{+} = {(S, γ) ∈ S_{p} : a_{p} − γ ⊂ a_{β} for all β ∈ S} .

p < q is defined by: a_{p} ∩ α_{q} = a_{q}, α_{p} ≥ α_{q}, and S_{q} ⊂ S_{p}.

Forcing with P_{A} should give us A = ⋃{a_{p} : p ∈ G}, an uncountable subset of ω_{1} such that A ∩ α is almost contained in a_{α} for each α < ω_{1}. The reason for introducing 𝔻-completeness is so that this can be iterated and to not add any new reals, hence preserving CH. For the remainder, assume that A has the property that every uncountable subset of ω_{1} meets some member of A in an infinite set. We will now use P for P_{A}.

Lemma 9.2 (Density). For each p ∈ P and γ ∈ ω_{1}, there is a q ∈ P with q < p and a_{q} − γ ≠ ∅.

Proof. Let {(S_{n}, γ_{n}) : n ∈ ω} enumerate S_{p} and for each ξ ≥ γ, assume there is an n_{ξ} ∈ ω so that {β ∈ S_{n_{ξ}} : ξ ∈ a_{β}} is not stationary. Clearly, there is an uncountable set I ⊂ ω_{1} and an n so that n_{ξ} = n for all ξ ∈ I. Now find any α so that a_{α} ∩ I is infinite. Then there is a stationary S ⊂ S_{n} so that there is some finite b so that a_{α} − a_{β} = b for all β ∈ S. This is a contradiction, since if ξ ∈ (a_{α} − b) ∩ I then ξ ∈ a_{β} for all β ∈ S ⊂ S_{n_{ξ}} – contradicting the definition of n_{ξ}.

Lemma 9.3 (Extension). Let M be a countable elementary submodel of H(μ) such that P ∈ M. Then for each p ∈ M ∩ P and dense open subset of P, there is a q ∈ D ∩ M, such that a_{q} − α_{p} ⊂ a_{δ}, where δ = M ∩ ω_{1}. More generally, given any x ⊂ δ such that a_{β} − x is finite for all β < δ, there is a q ∈ D ∩ M such that q < p and a_{q} − a_{p} ⊂ x.

Proof. Let N = {β : (∃b ∈ [β]^{<ω}) ((q ∈ D and q < p) → a_{q} − a_{p} ⊄ (a_{β} − b))} and observe that N ∈ M. If N ∉ NS, then there is a stationary N′ ⊂ N and (by the pressing down lemma) a finite set b such that (q ∈ D and q < p) implies a_{q} − a_{p} ∉⊂ (a_{β} − b) for each β ∈ N′. By elementary, b and N′ may be chosen in M.

Let p′ = (a_{p}, max(α_{p}, max(b) ), S_{p} ∪ {(N′, α_{p})}) and note that p′ ∈ M ∩ P. Choose q ∈ D ∩ M with q < p′ and fix (N̄, α_{p}) ∈ S_{q}^{+} so that N̄ ⊂ N′. If β ∈ N̄, then a_{q} − α_{p′} ⊂ a_{β} since (N̄, α_{p}) is in S_{q}^{+}. But now, notice that a_{q} ∩ α_{p′} = a_{p′} = a_{p} and so a_{q} − α_{p} ⊂ (a_{β} − b) contradicting the definition of N′. Therefore N ∈ NS ∩ M and so we may choose β ∈ δ − N. Set b = a_{β} − x and, since β ∉ N, there is a q ∈ D such that q < p and a_{q} − a_{p} ⊂ (a_{β} − b) ⊂ x. By elementarity there is such a q ∈ D ∩ M. The statement for a_{δ} now follows since obviously a_{δ} is such an x.

Lemma 9.4. There is an ℵ_{1}-completeness system 𝔻, such that for every coherent sequence A = {a_{α} : α < ω_{1}} there is a 𝔻-complete forcing notion P_{A} which introduces an I ∈ [ω_{1}]^{ω_{1}} such that either I ∩ a_{α} is finite for all α or I ∩ α − a_{α} is finite for all α. Also P_{A} is α-proper for every countable ordinal α.

Proof. A completeness system is called simple if there is a first order formula ψ such that

𝔻(M, P, p) = {A_{x} : x a finitary relation on M}

where

A_{x} = {G ∈ Gen(M, P) : ⟨M ∪ P(M), ∈⟩ ⊧ ψ[G, x, p, P, M]} .

𝔻 is ℵ_{1}-complete if each suitable 𝔻(M, P, p) has the property that any countable intersection is not empty. Finally P is 𝔻-complete if

Gen^{+}(M, P, p) = {G ∈ Gen(M, P) : p ∈ G and there is a lower bound for G inP }

contains some member of 𝔻(M, P, p).

We will define a suitable ψ after we have shown how it would be used. Our primary concern is the completeness. However let us remark that x will code a_{δ} (where δ = M ∩ ω_{1}) and a function from NS^{+} to ω_{1} where x(S) = γ will mean that S contains a stationary set, which we will denote, T (S) such that a_{δ} − a_{β} ⊂ γ for all β ∈ T (S). Note the coherent sequence A = {a_{γ} : γ ∈ M} can be recovered from P. One of the properties of ψ will be to assert that the statement of Lemma 9.3 holds with a_{δ} replaced by x_{0}. If there is an uncountable set I which meets every member of A in a finite set then simply let P_{A} = ^{<ω_{1}}2. Therefore in the remainder assume that there is no such uncountable set and let P denote P_{A}.

Claim. P is 𝔻-complete.

Indeed, Gen^{+}(M, P, p) (for M ≺ H(θ) and P ∈ M) contains A_{x} where x is the code as described above – we use x_{0} to denote the subset of δ coded by x and recall that, for S ∈ NS^{+} ∩ M, x(S) = γ < δ means there is a stationary set T (S) (not in M) contained in S such that a_{δ} − a_{β} ⊂ x(S) for all β ∈ T (S).

Then A_{x} will be all G ∈ Gen(M, P, p) which contain a subsequence {p_{n} : n ∈ ω} which satisfy the following induction.

Assume that for q ∈ P there is a fixed enumeration of S_{q} in order type ω. Also let {(i_{n}, j_{n}) : n ∈ ω} be a fixed enumeration of ω × ω chosen so that (i_{n}, j_{n}) ∈ n + 1 × n + 1. Let {D_{n} : n ∈ ω} enumerate all elements of M which are dense open subsets of P. When p_{n} is chosen, let {(S_{n,m}, γ_{n,m}) : m ∈ ω} be the fixed enumeration of S_{p_{n}}. The sequence p_{n} is chosen so that

(1) p_{0} ≤ p,

(2) p_{n+1} ∈ D_{n},

(3) a_{p_{n+1}} −a_{p_{n}} ⊂ x_{0} −x(S′_{n}) for some (S′_{n}, γ_{i_{n},j_{n}}) ∈ S_{p_{n}}^{+} such that S′_{n} ⊂ S_{i_{n},j_{n}},

(4) α_{p_{n+1}} ≥ x(S′_{n}).

Suppose that p_{n} has been chosen and fix (S′_{n}, γ_{i_{n},j_{n}}) ∈ S_{p_{n}}^{+} so that S′_{n} ⊂ S_{i_{n},j_{n}}. Let γ ≥ max{γ_{i_{n},j_{n}}, x(S′_{n})} and define p′ = (a_{p_{n}}, γ, S_{p_{n}}); clearly p′ < p_{n}. Apply Lemma 9.3 to obtain p_{n+1} ∈ D_{n} with p_{n+1} < p′ and a_{p_{n+1}} − γ ⊂ x_{0}.

Now we claim that there is a suitable x such that {p_{n} : n ∈ ω}, defined above, has a lower bound in P. Of course the point is to show that there is a suitable S ⊃ ⋃_{n} S_{p_{n}} so that (a = ∪a_{p_{n}}, δ, S) is a member of P. Define x_{0} to be a_{δ} and, for each S ∈ NS^{+}, a_{δ} − a_{β} ⊂ x(S) < δ for all β ∈ T (S) ∈ P(S) ∩ NS^{+}. Let S′_{n} be defined as in the inductive statement 3. Define S to be ⋃_{n} S_{p_{n}} together with {(T (S′_{n}), γ_{i_{n},j_{n}}) : n ∈ ω}. Clearly q = (a, δ, S) is below each p_{n} so it suffices to show that q ∈ P and, it should be clear that, it suffices to show that S_{q}^{+} is large enough. For this, it should be clear that it suffices to show that (T (S′_{n}), γ_{i_{n},j_{n}}) ∈ S_{q}^{+} for each n. Fix n and note that since (S′_{n}, γ_{i_{n},j_{n}}) ∈ S_{p_{n}}, it follows that a_{p_{n}} − γ_{i_{n},j_{n}} ⊂ a_{β} for each β ∈ T (S′_{n}). By the definition of T (S′_{n}) and x(S′_{n}) it follows that a_{δ}−a_{β} ⊂ x(S′_{n}) for all β ∈ T (S′_{n}). By construction, a_{p_{n+1}} − a_{p_{n}} ⊂ x_{0} − x(S′_{n}) and for m > n a_{p_{m+1}} − a_{p_{m}} ⊂ x_{0} − α_{p_{m}} ⊂ x_{0} − α_{p_{n+1}} ⊂ x_{0} − x(S′_{n}). Therefore ⋃_{m} a_{p_{m}} − a_{p_{n}} ⊂ a_{β} for all β ∈ T (S′_{n}). This completes the proof that a − γ_{i_{n},j_{n}} ⊂ a_{β} for all β ∈ T (S′_{n}).

Claim. If M ≺ H(μ) for a suitable μ and P ∈ M, then 𝔻(M, P, p) is countably complete for each p ∈ P ∩ M.

Fix any sequence {x^{n} : n ∈ ω} such that wlog a_{γ} − (x^{n})_{0} is finite for all γ ∈ (M ∩ ω_{1}) and n ∈ ω. The plan is to choose a descending sequence p_{n} so that p_{n} ∈ D_{n+1} ∩ M for each n. At stage n, the only thing that needs to be modified from the above construction is to replace x(S′_{n}) by the maximum of {x^{k}(S′_{n}) : k ≤ n}. The sequence which shows that the resulting generic filter G is in A_{x^{n}} is {p_{k} : n ≤ k < ω}.

Now we must establish that P is α-proper where α ∈ ω_{1}. Fix a continuous chain of countable elementary submodels of a suitable H(θ), {M_{γ} : γ ∈ α + 1}, such that P ∈ M_{0}, {M_{γ} : γ ≤ ξ} ∈ M_{ξ+1} for ξ ≤ α, and a condition p ∈ M_{0}; we must find a condition q < p which is (M_{γ}, P)-generic for each γ ≤ α. Inductive assumption: for any continuous chain {M′_{γ} : γ ≤ β} and p ∈ P ∩ M′_{0}, and finite set b ⊂ ω_{1}, there is a q < p such that a_{q} −a_{p} ⊂ (a_{δ′} −b) (where δ′ = M_{β} ∩ω_{1}) and {r ∈ P : r < q}∩M_{γ} is P -generic for M_{γ} for each γ ≤ β. The case where α is a successor is handled by the proof that P is 𝔻-complete, so assume that α is a limit and let {β_{n} : n ∈ ω} be increasing and cofinal in α.

Recursively choose p_{n} ∈ M_{β_{n}+1} together with stationary S_{n} ⊂ S_{i_{n},j_{n}} (use the enumeration as above) such that S_{n} ⊂ S′_{n} for some (S′_{n}, γ_{i_{n},j_{n}}) ∈ S_{p_{n}}^{+} and there is a finite set b_{n} such that a_{δ} − a_{β} = b_{n} for all β ∈ S_{n}. Apply the induction hypothesis to choose p_{n+1} ∈ M_{β_{n+1}} such that p_{n+1} < p_{n}, a_{p_{n+1}} − a_{p_{n}} is contained in a_{δ_{n+1}} −

(b ∪ (⋃_{k≤n} b_{k}) ∪ (a_{δ_{n+1}} − a_{δ})), α_{p_{n+1}} = δ_{n+1}, and {r ∈ P : r < p_{n+1}} ∩ M_{β_{n+1}} is (M_{γ}, P)-generic for all γ ∈ [β_{n} + 1, β_{n+1}).

References

1. A. Blass and S. Shelah. There may be simple P_{ℵ_{1}} and P_{ℵ_{2}}-points and the Rudin-Keisler order may be downward directed. Ann. Pure Appl. Logic, 83:213–243, 1987.

2. A. Dow. Two classes of Fréchet spaces. Proc. Amer. Math. Soc., 108:241–247, 1990.

3. A. Dow, F. Tall, and W. Weiss. A new proof of the Normal Moore space conjecture, I. Top. and its Appl., 337:1–114, 1990.

4. K.P. Hart and J. van Mill. Open problems on βω. In J. van Mill and G.M. Reed, editors, Open problems in Topology, pages 97–125. North-Holland, 1990.

5. K. Kunen. Combinatorics. In Handbook of Logic, pages 371–402. North Holland, 1977.

6. K. Kunen. Set Theory: An Introduction to Independence Proofs. North Holland, 1980.

7. M. Magidor. On the role of supercompact and extendible cardinals in logic. Israel Journal of Math., 10:147–171, 1971.

8. A. Miller. Rational perfect set forcing. In Axiomatic Set Theory, pages 143–159. Contemporary Mathematics, AMS, 1984.

9. W. J. Mitchell. Aronszajn trees and the independence of the transfer property. Annals of Math. Logic, 5:21–46, 1972.

10. S. Shelah. Proper Forcing. Springer Lecture Notes, 1982.

11. S. Shelah. On cardinal invariants of the continuum. In Axiomatic Set Theory. Contemporary Mathematics, AMS, 1984.

Department of Mathematics, York University, 4700 Keele Street, North York, Ontario, Canada M3J 1P3

E-mail: adow@yorku.ca