Parametrized ♢ principles

Justin Tatch Moore, Michael Hrušák, Mirna Džamonja ^{∗}^{†}

September 2, 2003

Abstract

We will present a collection of guessing principles which have a similar relationship to ♢ as cardinal invariants of the continuum have to CH. The purpose is to provide a means for systematically analyzing ♢ and its consequences. It also provides for a unified approach for understanding the status of a number of consequences of CH and ♢ in models such as those of Laver, Miller, and Sacks.

1 Introduction

Very early on in the course of modern set theory, Jensen isolated the following combinatorial principle known as ♢:

♢ There is a sequence A_{α} (α < ω_{1}) such that for all α < ω_{1}, A_{α} ⊆ α and if X is a subset of ω_{1} then set

{α < ω_{1} : X ∩ α = A_{α}}

is stationary.

∗The first and third authors received support from EPSRC grant GR/M71121 for the research of this paper. The research of the second author was supported in part by the Netherlands Organization for Scientific Research (NWO) – Grant 613.007.039, and in part by the Grant Agency of the Czech Republic – Grant GAČR 201/00/1466.

†2000 Mathematics Subject Classification. Primary 03E17, 03E65. Key words: Diamond, weak diamond, cardinal invariant, guessing principle.

Jensen used this principle to construct a Suslin tree [17] and later many other constructions were carried out using ♢ as an assumption — see [9].

The purpose of this paper is to provide a broad framework for analyzing the consequences of Jensen’s ♢ principle. Our intent is to present an array of ♢-principles which have the same relation to ♢ as the cardinal invariants of the continuum (see e.g. [2] or [8]) have to the Continuum Hypothesis. We will approach an analysis of ♢ in much the same way as Blass approaches cardinal invariant inequalities in [4].

Our immediate motivation in this consideration stems from the isolation of the principle ♢_{𝔡} in [15] (see also [16]).

♢_{𝔡} There is a sequence g_{α} : α → ω indexed by ω_{1} such that for every f : ω_{1} → ω there is an α ≥ ω with f ↾ α <^{∗} g_{α}.

This principle implies 𝔡 = ω_{1} (for much the same reason as ♢ implies 𝔠 = ω_{1}), follows from 𝔡 = ω_{1}+♣, and holds in most of the standard generic extensions in which 𝔡 = ω_{1} holds [16].^{1} The main interest in it comes from the following fact relating to the question of whether 𝔡 = ω_{1} implies 𝔞 = ω_{1}.

Theorem 1.1. [16] ♢_{𝔡} implies 𝔞 = ω_{1}.

It was initially unclear whether other cardinal invariants of the continuum, such as 𝔟 and 𝔰, have similar ♢-like principles corresponding to them. The cardinal 𝔰 was of particular interest in this context, since it seemed that the construction of the Ostaszewski space from ω_{1} random reals in [23] should be a consequence of a principle similar to ♢_{𝔰} (whatever that might be).

It turned out that the correct language to use for formulating ♢-principles like those mentioned above was developed by Devlin and Shelah in [7]. They considered the following statement

Φ For every F : 2^{<ω_{1}} → 2 there is a g : ω_{1} → 2 such that for every f : ω_{1} → 2 the set {α ∈ ω_{1} : F (f ↾ α) = g(α)} is stationary.

which they showed to be equivalent to 2^{ℵ_{0}} < 2^{ℵ_{1}}. The framework of the weak diamond principle Φ of [7] allows for the definition of two classes of ♢-principles, Φ(A, B, E) and ♢(A, B, E), each taking a cardinal invariant (A, B, E) as a parameter.

1Another ♢-like principle in this spirit is the statement ♢(ω_{1}^{<ω}) presented in Section 6.2 of [36] (Definition 6.37). To draw an analogy, this principle might also be called ♢_{non(M)} in the language of [16] (see Theorem 6.49 of [36]). Also, Shelah has considered some specific cases of Φ(A, B, E) defined below in the appendix of [27].

Like ♢_{𝔡}, these principles all imply that the corresponding cardinal invariant is ω_{1}. They all follow from ♢, with ♢(𝔠) and Φ(𝔠) both being equivalent to ♢. They also each have a “guessing” component which allows them to carry out constructions for which one historically has used ♢. Moreover, many of the classical ♢ constructions seem to fit very naturally into this scheme. For instance the standard construction of a Suslin tree from ♢ really requires only ♢(non(M)). Also like ♢_{𝔡}, the principles ♢(A, B, E) hold in many of the natural models in which their corresponding cardinal invariant ⟨A, B, E⟩ is ω_{1}. For instance ♢(𝔟) holds in Miller’s model and ♢(cof(N)) holds in both the iterated and the “side-by-side” Sacks models.

The paper is organized as follows. Section 2 introduces an abstract form of a cardinal invariant of the continuum and formulates the principles Φ(A, B, E) which serve as a first approximation to ♢(A, B, E). Section 3 presents the Suslin tree construction from ♢ in the language of Φ(non(M)). Section 4 introduces a refinement of Φ(A, B, E) called ♢(A, B, E) and gives some explanation for our choice of it over Φ(A, B, E). Section 5 presents some more constructions which use ♢(A, B, E). Section 6 shows that ♢(A, B, E) holds in many of the models of ⟨A, B, E⟩ = ω_{1}. Section 7 studies the role of ♢(A, B, E) in analyzing cardinal invariants other than those fitting into our framework. Section 8 presents a proof that ♢(A, B, E) is not a consequence of CH for any of the classical invariants (A, B, E).

Our notation is, for the most part, standard (see [19]). We will use A^{B} to denote the collection of all functions from B to A. 2^{<ω_{1}} will be used to denote the tree of all functions from a countable ordinal into 2 ordered by extension. If t is a function defined on an ordinal, then we will use |t| to denote the domain of t. Otherwise |A| will be used to denote the cardinality of a set A. The meaning of | · | should always be clear from the context. If B is a Borel subset of a Polish space, we will often identify it with its code and use this code to define B in forcing extensions. We will use B̌ to represent the name for this set in the forcing extension.

Many of the constructions in this paper will require choosing a sequence e_{δ} : ω ↔ δ of bijections for each δ ∈ ω_{1} or an increasing sequence δ_{n} (n ∈ ω) which is cofinal in δ for limit δ. To avoid repetition, we will fix a sequence of bijections e_{δ} (δ ∈ ω_{1}) and cofinal sequences δ_{n} (n ∈ ω) for limit δ once and for all. If there is a need to refer to, e.g., a special cofinal sequence in δ we will use δ̄_{n} (n ∈ ω) for the sequence instead.

2 Abstract cardinal invariants and Φ

The following structure allows for a compact definition of many of common cardinal invariants of the continuum.

Definition 2.1. [34] An invariant is a triple (A, B, E) such that

1. A and B are sets of cardinality at most |ℝ|,

2. E ⊆ A × B,

3. for every a ∈ A there is a b ∈ B such that (a, b) ∈ E,

4. for every b ∈ B there is an a ∈ A such that (a, b) ∉ E.

Usually we will write aEb instead of (a, b) ∈ E.

Definition 2.2. If (A, B, E) is an invariant, then its evaluation ⟨A, B, E⟩ is given by

⟨A, B, E⟩ = min{|X| : X ⊆ B and (∀a ∈ A)(∃b ∈ X)(aEb)}

If A = B then we will write (A, E) and ⟨A, E⟩ instead of (A, B, E) and ⟨A, B, E⟩ respectively. Two typical examples of invariants are (N , ⊆) and (M, ℝ, ∌). The evaluations ⟨N , ⊆⟩ and ⟨M, ℝ, ∌⟩ are clearly just cof(N) and non(M). Even though, strictly speaking, M and N are ideals of cardinality 2^{𝔠} they both have a basis consisting of Borel sets, hence of cardinality 𝔠. If an invariant (A, B, E) already has a common representation, we will use such a representation instead of (A, B, E). Moreover, we will abuse notation and use these representations to abbreviate both the invariant and its evaluation. What we mean should always be clear from the context.

Definition 2.3. Let (A, B, E) be an invariant. Φ(A, B, E) is the following statement:

Φ(A, B, E) For every F : 2^{<ω_{1}} → A there is a g : ω_{1} → B such that for every f : ω_{1} → 2 the set {α ∈ ω_{1} : F (f ↾ α)E g(α)} is stationary.

The witness g for a given F in this statement will be called a ♢(A, B, E)- sequence for F. If F (f ↾ δ)Eg(δ) then we will say that g guesses f (via F) at δ.

Proposition 2.4. ♢ implies Φ(A, B, E) for any invariant (A, B, E).

Proof. Let A_{α} (α ∈ ω_{1}) be a diamond sequence which guesses elements of 2^{ω_{1}} (A_{α} is in 2^{α}). Set g(α) to be any b ∈ B such that F (A_{α})Eb. Then g is a ♢(A, B, E)-sequence for F since for all f : ω_{1} → 2

{δ ∈ ω_{1} : f ↾ δ = A_{δ}} ⊆ {δ ∈ ω_{1} : F (f ↾ δ)Eg(δ)}.

Proposition 2.5. Φ(A, B, E) implies ⟨A, B, E⟩ is at most ω_{1}.

Proof. Let F : 2^{ω} → A be a surjection and extend F to 2^{<ω_{1}} by setting F (t) = F (t ↾ ω) if t has an infinite domain and defining F (t) arbitrarily otherwise. Let g be a ♢(A, B, E)-sequence for F. It is easy to see that the range of g witnesses ⟨A, B, E⟩ ≤ ω_{1}.

Notice the resemblance of this proof to the standard proof that ♢ implies CH. In fact, if we view 𝔠 as the invariant (ℝ, =) then we have the following fact.

Proposition 2.6. Φ(𝔠) is equivalent to ♢.

Proof. By Proposition 2.4 we need only to show that Φ(𝔠) implies ♢. For each infinite α ∈ ω_{1}, fix a bijection H_{α} : 2^{α} → ℝ. Set F (t) = H_{α}(t) where α = |t|. Let g be the ♢(𝔠)-sequence for this F. Set A_{α} = H_{α}^{−1}(g(α)). It is easy to see that A_{α} (α ∈ ω_{1}) is a ♢-sequence.

Proposition 2.7. Φ(ℝ^{ω}, ⊑) is equivalent to ♢. Here f ⊑ g iff the range of f is contained in the range of g.

Proof. Combine the previous proof with the Kunen’s result stating that ♢ is equivalent to ♢^{−} (see [19]).

A natural question which arises is: “When do relations between invariants translate into implications between the corresponding ♢-principles?” This is largely answered by the next proposition.

Notation. (Tukey ordering [34]) If (A_{1}, B_{1}, E_{1}) and (A_{2}, B_{2}, E_{2}) are invariants then

(A_{1}, B_{1}, E_{1}) ≤_{T} (A_{2}, B_{2}, E_{2})

when there are maps ϕ : A_{1} → A_{2} and ψ : B_{2} → B_{1} such that (ϕ(a), b) ∈ E_{2} implies (a, ψ(b)) ∈ E_{1}.

As one would expect, the Tukey ordering on invariants gives the corresponding implications for Φ principles.

Proposition 2.8. If (A_{1}, B_{1}, E_{1}) ≤_{T} (A_{2}, B_{2}, E_{2}) then Φ(A_{1}, B_{1}, E_{1}) is a consequence of Φ(A_{2}, B_{2}, E_{2}).

One should exercise caution, however, when trying to turn inequalities between evaluations of cardinal invariants into implications between ♢- principles. For instance, (ω^{ω}, <^{∗}) are (ω^{ω}, ≤) have the same evaluation but seem to give rise to different ♢-principles. We will use 𝔡 to denote (ω^{ω}, <^{∗}).

The smallest invariant in the Tukey order is (ℝ, ≠). It is known that Φ(2, ≠) is equivalent to Φ(ℝ, ≠) — this was noted by Abraham and can be extracted from [7]. The proof is given for completeness.

Theorem 2.9. Φ(2, ≠) is equivalent to Φ(ℝ, ≠).

Proof. Since (ℝ, ≠) is below (2, ≠) in the Tukey order, it suffices to show that Φ(ℝ, ≠) implies Φ(2, ≠). To this end, suppose that F : 2^{<ω_{1}} → 2 witnesses that Φ(2, ≠) fails. Define a function F^{∗} whose ranges is contained in 2^{ω} and whose domain consists of functions of the form t : δ × ω → 2 so that F^{∗}(t)(i) = F (t(·, i)). Now let g : ω_{1} → 2^{ω} be given. To see that g is not a ♢(ℝ, ≠)-sequence for F^{∗}, pick closed unbounded sets C_{n} ⊆ ω_{1} and functions f_{n} : ω_{1} → 2 such that F (f_{n} ↾ δ) = g(δ)(n) for every n and δ in C_{n}. Now define f : ω_{1} ×ω → 2^{ω} by putting f(δ, n) = f_{n}(δ). Then F^{∗}(f ↾ δ ×ω) = g(δ) whenever δ is in ⋂_{n∈ω} C_{n}.

3 The Suslin tree construction

In order to get a feel for how the statements Φ(A, B, E) are used, we will begin by revisiting an old construction and translating it into the language which we have developed.

Theorem 3.1. Φ(non(M)) implies that there is a Suslin tree.

Proof. By some suitable coding, F will take triples (α, ≺, A) as its argument where α ∈ ω_{1}, ≺⊆ α^{2}, and A ⊆ α. F will be defined to be the empty set unless

1. α is a limit of limit ordinals, 2. ≺ is a tree order on α ∈ ω_{1} of limit height,

3. if γ < α then for every δ less than the height of (α, ≺) there is a γ̄ < α with γ ≺ γ̄ and the height of γ̄ greater than δ,

4. every element of α has exactly ω immediate successors in ≺,

5. if ξ < α, then [ξ · ω, ξ · ω + ω) is exactly the collection of elements of (α, ≺) of height ξ, and

6. A is a maximal antichain in (α, ≺).

For such a triple (α, ≺, A) let α_{n} (n ∈ ω) be an increasing sequence cofinal in α and such that each α_{n} is a limit ordinal. Let [α, ≺] denote the collection of all cofinal branches through (α, ≺). Define

ϕ_{≺} : [α, ≺] → ω^{ω}

by setting ϕ_{≺}(b)(n) to be the unique k such that α_{n} + k is in b. Notice that if A ⊆ α is a maximal antichain then

N(α, ≺, A) = {ϕ_{≺}(b) : b ∈ [α, ≺] and A ∩ b = ∅}

is closed and nowhere dense in ω^{ω}. Also, observe that ϕ_{≺} is a surjection. Let F (α, ≺, A) be the collection of all finite changes of elements of N(α, ≺, A).

Now suppose that g : ω_{1} → ω^{ω} is a ♢(non(M))-sequence for F. Construct a tree order ≺ on ω_{1} by recursion. Define (ω^{2}, ≺) so that it is isomorphic to ω^{<ω} ordered by end extension. Now suppose that (α, ≺) is defined and has limit height. Extend the order to (α + ω, ≺) in such a way that a cofinal branch b in [α, ≺] has an upper bound in (α + ω, ≺) iff ϕ_{≺}(b) is eventually equal to g(α). Now extend ≺ to α + ω^{2} in such a way that conditions 1-5 above are satisfied.

To see that (ω_{1}, ≺) is a Suslin tree, suppose that A ⊆ ω_{1} is a maximal antichain in (ω_{1}, ≺). By the same crucial lemma as in the standard ♢ construction (see Lemma 7.6 in Chapter II of [19]) the set of α < ω_{1} such that A ∩ α is a maximal antichain in (α, ≺) contains a closed unbounded set C. If g guesses (ω_{1}, ≺, A) at α ∈ C and F (α, ≺↾ α, A ∩ α) is nonempty, then A ∩ α is a maximal antichain in (α + ω, ≺). It is now easily verified using properties 1–4 above that, since A ⊆ α is a maximal antichain in (α + ω, ≺), it is maximal in (ω_{1}, ≺) as well.

A reader familiar with the classical construction of a Suslin tree from ♢ (see, e.g., Section II.7 of [19]) should have no trouble in seeing that this is indeed the same construction with the assumption reduced to the minimum required to carry out the argument. In Section 4 we shall comment that the principle ♢(non(M)) implied by Φ(non(M)) suffices for this construction and in Section 6 we will see that ♢(non(M)) is in fact much weaker than ♢.

4 ♢(A, B, E) — a definable form of Φ(A, B, E)

The purpose of this section is to demonstrate that Φ(A, B, E) is, in general, too strong to hold in typical generic extensions in which ⟨A, B, E⟩ = ω_{1}. We will, however, recover from it a principle ♢(A, B, E) which is still strong enough for most of the combinatorial applications of Φ(A, B, E) and which is of a more appropriate strength.

Proposition 4.1. Φ(A, B, E) implies 2^{ω} < 2^{ω_{1}}.

Proof. Suppose that 2^{ω} = 2^{ω_{1}}. Let H : 2^{ω} → B^{ω_{1}} be a surjection. Define F (t) to be any a in A such that (a, H(t ↾ ω)(|t|)) is not in E. Now if g : ω_{1} → B is given, pick an f : ω_{1} → 2 such that H(f ↾ ω) = g. It is easily checked that g does not guess f at any δ ≥ ω.

A closer look at the uses of Φ(A, B, E) presented in Sections 2 and 3 reveals that in all cases the maps F which were used in the proofs could be chosen to be nicely definable. This, generally speaking, is atypical of the map F in the proof of Proposition 4.1. Before we discuss the principles ♢(A, B, E), we first need to define the notion of a Borel invariant.

Definition 4.2. [4] An invariant (A, B, E) is Borel if A, B and E are Borel subsets of some Polish space.

With slight technical changes, all of the “standard” invariants (A, B, E) can be represented as Borel invariants. The invariants for which this is non trivial are those in Cichoń’s diagram. First note that the G_{δ} null and F_{σ} meager sets generate N and M respectively. Furthermore, ⊆ is a Borel relation on a cofinal subset of the G_{δ} null and F_{σ} meager sets. The details for the category invariants are handled in Section 3 of [4]. For null sets, one can use the fact that any null set is contained in the union of two small sets and that the containment relation on such unions is Borel (see Section 2.5 of [2] for a discussion of small set and their relation to null sets).

Definition 4.3. Suppose that A is a Borel subset of some Polish space. A map F : 2^{<ω_{1}} → A is Borel if for every δ the restriction of F to 2^{δ} is a Borel map.

As we will see throughout this paper, the maps F which we are actually interested in considering in the context of Φ(A, B, E) all can be made to satisfy this requirement. This motivates the following definition.

Definition 4.4. Let (A, B, E) be a Borel invariant. ♢(A, B, E) is the following statement:

♢(A, B, E) For every Borel map F : 2^{<ω_{1}} → A there is a g : ω_{1} → B such that for every f : ω_{1} → 2 the set {α ∈ ω_{1} : F (f ↾ α)Eg(α)} is stationary.

Aside from the fact that ♢(A, B, E) often suffices for applications of Φ(A, B, E), it is also the case that, unlike Φ(A, B, E), ♢(A, B, E) is often forced in the standard models where ⟨A, B, E⟩ = ω_{1} is forced. This is the content of Section 6. The key property of Borel maps which we will need in Section 6 is that if M is a model of ZFC (usually an intermediate forcing extension) which contains the codes for A and F ↾ 2^{δ} and t ∈ 2^{δ} then F (t) can be computed in M. Often it will be convenient to define a map F only on a Borel subset of 2^{δ} for each δ. In such a case F will assume a fixed constant value elsewhere.

The reader is now encouraged to re-read Section 2 and convince themselves that ♢(A, B, E) suffices in each case in which Φ(A, B, E) was used as an assumption for a particular Borel invariant (A, B, E). For instance we have the following theorems.

Proposition 4.5. ♢(𝔠) is equivalent to ♢.

Proposition 4.6. ♢(ℝ, ≠) is equivalent to ♢(2, ≠).

Theorem 4.7. ♢(non(M)) implies the existence of a Suslin tree.

Another problematic aspect of the statements Φ(A, B, E) is that under CH, the Tukey types of many of the standard invariants are reduced to (ω_{1}, <). For instance, under 𝔡 = ω_{1} the Tukey type of (ω^{ω}, <^{∗}) reduces to (ω_{1}, <) and hence Φ(𝔡) is equivalent to Φ(ω_{1}, <) (see [37]). The Tukey maps in such situations, however, are generally far from being definable. The analog of Proposition 2.8 for ♢(A, B, E) avoids this.

Definition 4.8. (Borel Tukey ordering [4]) Given a pair of Borel invariants (A_{1}, B_{1}, E_{1}) and (A_{2}, B_{2}, E_{2}) We will say that (A_{1}, B_{1}, E_{1}) ≤_{T}^{B} (A_{2}, B_{2}, E_{2}) if (A_{1}, B_{1}, E_{1}) ≤_{T} (A_{2}, B_{2}, E_{2}) and the connecting maps are both Borel.

Proposition 4.9. If (A_{1}, B_{1}, E_{1}) ≤_{T}^{B} (A_{2}, B_{2}, E_{2}) then ♢(A_{2}, B_{2}, E_{2}) implies ♢(A_{1}, B_{1}, E_{1}).

It turns out that the Tukey connections between all the invariants we will consider satisfy the above requirement (see [4]) and hence implications such as ♢(add(M)) implies ♢(add(N)) hold.

5 Some more constructions

The purpose of this section is to present some more topological and combinatorial constructions. The first construction is that of the Ostaszewski space of [24]. Recall that an Ostaszewski space is a countably compact noncompact perfectly normal space. Usually this space is considered to have the additional property that its closed sets are either countable or co-countable. Originally this space was constructed using ♣ + CH, an equivalent of ♢ [24].

Unlike the example of the Suslin tree, which does not seem to yield any new models in which there are Suslin trees, the hypothesis we use in the construction makes it rather transparent that there are Ostaszewski spaces after adding ω_{1} random reals. The construction of an Ostaszewski space from a sequence of random reals (see [23] or [22]) and a careful analysis of the combinatorics involved was one of the main motivations and inspirations for the formulation of ♢(𝔰) and consequently ♢(A, B, E) for arbitrary invariants (A, B, E).

Notation. Let (ω)_{ω}^{ω} denote the collection of all partitions of ω into infinitely many infinite pieces.

Recall that if A, B ⊆ ω then A is split by B if both A ∩ B and A \ B are infinite. The invariant which seems to be at the heart of Ostaszewski’s construction is

𝔰^{ω} = ([ω]^{ω}, (ω)_{ω}^{ω}, is split by all pieces of),

a close relative of

𝔰 = ([ω]^{ω}, is split by).

The invariant 𝔰^{ω} is connected to non(M) and non(N) by the following proposition.

Proposition 5.1. 𝔰^{ω} is below both non(M) and non(N) in the Borel Tukey order.

Proof. Let μ be the product measure on ω^{ω} obtained by setting μ({n}) = 2^{−n−1}. Let S be the collection of all f in ω^{ω} which take the value n infinitely often for each n. It is easily verified that S is both comeager and measure 1 and hence we can view non(M) = (M, S, ∌) and non(N) = (N , S, ∌). Define ϕ : [ω]^{ω} → M ∩ N by letting ϕ(A) be the collection of all f in S which take all values infinitely often on A. Define ψ : S → (ω)_{ω}^{ω} by ψ(f) = {f^{−1}(n) : n ∈ ω}. It is easily verified that this pair of maps gives the desired Borel Tukey connections.

Theorem 5.2. ♢(𝔰^{ω}) implies the existence of a perfectly normal countably compact non-compact space (i.e. an Ostaszewski space).

Proof. Again by suitable coding, we will take the domain of F to be the set of all triples (α, B, D) such that α ∈ ω_{1}, B = ⟨U_{γ} : γ < α⟩ where U_{γ} ⊆ γ + 1, γ ∈ U_{γ}, and D ⊆ α. Given a pair (α, B) as above, let τ_{B} be the topology on α generated by taking B as a clopen subbase. F (α, B, D) is defined to be ω unless

1. α is a limit ordinal,

2. U_{γ} is compact in τ_{B} for all γ < α,

3. for every γ < α, the closure of [γ, γ + ω) in (α, τ_{B}) is [γ, α), and

4. D does not have compact closure in (α, τ_{B}).

Define V_{α,n} for n in ω by setting V_{α,0} = U_{e_{α}(0)} and

V_{α,n} = U_{e_{α}(k)} \ ⋃_{i<n} V_{α,i}

where k is minimal such that this set is nonempty and such that e_{α}(n) is covered by V_{α,i} for some i ≤ n. Thus {V_{α,n} : n ∈ ω} is a partition of (α, τ_{B}) into compact open sets. Set F (α, B, D) to be the collection of all n such that D ∩ V_{α,n} is nonempty. Notice that since V_{α,n} is compact for all n and D does not have compact closure, F (α, B, D) is infinite.

Now let g : ω_{1} → (ω)_{ω}^{ω} be a ♢(𝔰^{ω})-sequence for F. Define a locally compact topology (ω_{1}, τ_{B}) by recursion. Suppose that B ↾ α have been defined so far, satisfying 1-3. Notice that if A ⊆ ω and σ, σ′ ∈ (ω)_{ω}^{ω} are such that A is split by all pieces of σ and every element of σ′ contains some element of σ then A is split by every element of σ′. Thus by altering g(α), if necessary, we may assume that for each k, the collection {V_{α,n} : n ∈ g(α)(k)} has a union which is cofinal in α. Let

U_{α+k} = ⋃_{n∈g(α)(k)} V_{α,n}.

Since U_{α+k} is cofinal in α for all k, the closure of a co-bounded subset of α is co-bounded in α + ω.

Clearly (ω_{1}, τ_{ω_{1}}) is not compact since all initial segments are open in τ_{ω_{1}}. To finish the proof, it suffices to show that closed sets are either compact or co-countable. Now suppose that D ⊆ ω_{1} does not have compact closure. Let δ ∈ ω_{1} be such that F (δ, B ↾ δ, D ∩ δ) is defined and is split by every element of g(δ). Then D ∩ δ must accumulate at δ + n for all n. It follows from 3 that the closure of D in ω_{1} is co-bounded.

As mentioned above, the construction can be carried out using ♢(non(N)) which holds after adding ω_{1} random reals. Eisworth and Roitman have shown that the construction of an Ostaszewski space can not be carried out under CH alone and hence some form of a guessing principle is required [11]. While the space above is hereditarily separable, the following question is open:

Question 5.3. Does ♢(non(N)) imply the existence of a non-metric compact space X such that X^{2} is hereditarily separable?

We will now pass to a purely combinatorial construction. Recall that a sequence A_{α} : α → 2 indexed by ω_{1} is coherent if for every α < β A_{α} =^{∗} A_{β} ↾ α. Such a sequence is trivial if there is a B : ω_{1} → 2 such that A_{α} =^{∗} B ↾ α for all α. Non-trivial coherent sequences can be constructed without additional set theoretic assumptions [35]. The conclusion of the following theorem is deduced from ♢ in [9], though unlike Theorems 3.1 and 5.2, the argument presented here does not mirror an existing argument.

Theorem 5.4. ♢(𝔟) implies that there is a coherent sequence A_{α} (α ∈ ω_{1}) of binary maps such that for every uncountable set X, there is an α ∈ ω_{1} with A_{α} taking both its values infinitely often on X ∩ α.

First we will need the following fact which seems to be of independent interest. Recall that a ladder system is a sequence ⟨C_{δ} : δ ∈ lim(ω_{1})⟩ such that C_{δ} is a cofinal subset of δ of order type ω for each limit ordinal δ ∈ ω_{1}.

Theorem 5.5. ♢(𝔟) implies that there is a ladder system C_{δ} such that for every sequence of uncountable sets X_{γ} ⊆ ω_{1} (γ ∈ ω_{1}) there are stationarily many δ such that X_{γ} ∩ C_{δ} is infinite for all γ < δ.

Proof. (of Theorem 5.5) Let X⃗ = ⟨X_{γ} : γ < δ⟩ be a given sequence of subsets of δ and set F (X⃗) to be the identity function unless δ is a limit ordinal and X_{γ} is unbounded in δ for all γ < δ. Set

F (X⃗)(n) = max_{i≤n} {min{e_{δ}^{−1}(γ) : γ ∈ X_{e_{δ}(i)} \ δ_{n}}} .

Now suppose that g : ω_{1} → ω^{ω} is a ♢(𝔟)-sequence for F. By making g(δ) larger if necessary, we may assume that

g(δ)(n) > e_{δ}^{−1}(δ_{n}).

Set

C_{δ} = ⋃_{n=0}^{∞}{γ < δ : (e_{δ}^{−1}(γ) ≤ g(δ)(n)) and (γ ≥ δ_{n})}.

Clearly C_{δ} is an ω-sequence which is cofinal in δ and it is routine to check that it satisfies the conclusion of the theorem.

Definition 5.6. A binary coherent sequence A⃗ almost contains a ladder system C⃗ if A_{α} is eventually 1 on C_{δ} whenever δ < α.

Notice that if C⃗ satisfies the conclusion of Theorem 5.5 then for any binary sequence A_{α} which almost contains C⃗ and any uncountable set X, there is an α such that A_{α} takes the value 1 infinitely often on X ∩ α. Since coherence implies that this occurs for all β ≥ α as well, it suffices to prove the following lemma.

Lemma 5.7. ♢(𝔟) implies that for every ladder system C⃗ there is a coherent sequence A⃗ which almost contains C⃗ such that for every uncountable set X ⊆ ω_{1} there is an α such that A_{α} takes the value 0 infinitely often on X ∩ α.

Proof. First recall the following notion of a minimal walk (see [30] or [31]). If α < β then β(α) = min(C_{β} \ α). Here C_{α+1} = {α}. Define β^{i}(α) recursively by setting β^{0}(α) = β and β^{i+1}(α) = β^{i}(α)(α). Let

a_{β}(α) = |C_{β^{k−1}(α)} ∩ α|

where k is the minimal such that β^{k}(α) = α. That is, a_{β}(α) is the weight of the last step in the walk from β to α.

Now let X ⊆ δ be given. Define F (X, δ) to be the identity function unless X is cofinal in δ in which case set

F (X, δ)(n) = min{a_{δ}(γ) : γ ∈ δ ∩ X \ δ̄_{n}},

where δ̄_{n} (n ∈ ω) is an increasing enumeration of C_{δ}.

Let g : ω_{1} → ω^{ω} be a ♢(𝔟)-sequence for F. By making functions in g larger if necessary we may assume that g(α) is monotonic for all α. Set

b_{β}(α) = max_{i<k−1} g(β^{i}(α))(|C_{β^{i}(α)} ∩ α|)

if the maximum is over a nonempty set and 0 otherwise (where, again, k is minimal such that β^{k}(α) = α). Define A_{β}(α) to be 0 if a_{β}(α) < b_{β}(α) and 1 otherwise.

It is routine to show that a⃗ and b⃗ are both coherent and hence that A⃗ is coherent (see section 1 of [30] or [31]). It is equally routine to show that b_{β} is eventually constant on any ladder while a_{β} is eventually 1-1 on each ladder and hence A⃗ almost contains C⃗. To see that A⃗ satisfies the conclusion of the theorem, let X be an uncountable set. Fix a δ such that X ∩ δ is cofinal in δ and g(δ) is not dominated by F (X ∩δ, δ). Let γ < δ be arbitrary. It suffices to find an α in X ∩ δ \ γ such that A_{δ}(α) = 0. Let n be such that δ̄_{n} > γ and F (X ∩ δ, δ)(n) < g(δ)(n). Let α ∈ X ∩ δ \ δ̄_{n} be such that a_{δ}(α) = F (X ∩ δ, δ)(n). Now

b_{δ}(α) ≥ g(δ)(|C_{δ} ∩ α|) ≥ g(δ)(n) > a_{δ}(α)

which finishes the proof.

Question 5.8. For which Borel invariants (A, B, E) does ♢(A, B, E) imply the existence of a c.c.c. destructible (ω_{1}, ω_{1}^{∗})-gap in [ω]^{ω}?

6 Canonical models for ♢(A, B, E)

The purpose of this section is to show that, for the classical invariants (A, B, E), ♢(A, B, E) holds in many of the standard models for ⟨A, B, E⟩ = ω_{1}.

Theorem 6.1. Let C_{ω_{1}} and R_{ω_{1}} be the Cohen and measure algebras corresponding to the product space 2^{ω_{1}} with its usual topological and measure theoretic structures. The orders C_{ω_{1}} and R_{ω_{1}} force ♢(non(M)) and ♢(non(N)) respectively.

Proof. The arguments for each are almost identical so we will only present the case of R_{ω_{1}}. Let Ġ be an R_{ω_{1}}-name for the element of 2^{ω_{1}} corresponding to the generic filter. Fix an R_{ω_{1}}-name Ḟ for a Borel map from 2^{<ω_{1}} to N and let ṙ_{δ} be an R_{ω_{1}}-name for a real such that Ḟ ↾ 2^{δ} is definable from ṙ_{δ}. Pick a strictly increasing function f : ω_{1} → ω_{1} such that ṙ_{δ} is forced to be in V[Ġ ↾ f(δ)]. Let ġ(δ) be defined to be Ġ ↾ [f(δ), f(δ) + ω) (interpreted canonically as a real).

To see that ġ works, let ḟ : ω_{1} → 2 be an R_{ω_{1}}-name. Let C be the collection of all δ for which it is forced that ḟ ↾ δ ∈ V[Ġ ↾ δ]. Because R_{ω_{1}} is c.c.c., C is closed and unbounded. Since Ġ is generic, ġ(δ) avoids every null set coded in V[Ġ ↾ f(δ)], including Ḟ (ḟ ↾ δ).

The above proof actually shows that ♢^{∗}(non(M)) and ♢^{∗}(non(N)) hold in the corresponding models where ♢^{∗}(A, B, E) is obtained from ♢(A, B, E) by replacing “stationary” by “club.” One could, of course, produce a myriad of results of a similar flavor: e.g. ♢^{∗}(cof(M)) holds after adding ω_{1} Hechler reals or ♢^{∗}(𝔰) holds after generically adding a sequence of ω_{1} independent reals.

It should be noted that the results of [13], [22], and [33] place considerable limitations on the strength of ♢^{∗}(non(N)) — and hence ♢(non(N)) — as they show that there are a number of consequences of MA_{ℵ_{1}} which are consistent with ♢^{∗}(non(N)). For instance Theorem 6.1 gives the following corollary which contrasts the remarks preceding Definition 4.8.

Theorem 6.2. It is relatively consistent with CH that ♢(non(N)) holds but ♢(non(M)) fails.

Proof. By a result of Hirschorn [13], it is consistent with CH that after forcing with any measure algebra there are no Suslin trees. After forcing with R_{ω_{1}} over this model we obtain a model in which ♢(non(M)) fails but ♢(non(N)) holds.

So in particular, ♢(non(N)) is not sufficient to carry out the construction of a Suslin tree.

Question 6.3. Does ♢(𝔟) imply the existence of a Suslin tree?

This also suggests the following meta-question:

Question 6.4. If (A_{1}, B_{1}, E_{1}) and (A_{2}, B_{2}, E_{2}) are two Borel invariants such that the inequality ⟨A_{1}, B_{1}, E_{1}⟩ < ⟨A_{2}, B_{2}, E_{2}⟩ is consistent, is it consistent that ♢(A_{1}, B_{1}, E_{1}) holds and ♢(A_{2}, B_{2}, E_{2}) fails in the presence of CH?

We will now move on to study countable support iterations.

Definition 6.5. A Borel forcing notion is a partial order (X, ≤) with a maximal element^{2} such that X and ≤ are Borel sets.

Given a Borel forcing notion, we will always interpret it in forcing extensions using its code rather than taking the ground model forcing notion. Observe that many Borel forcing notions Q designed for adding a single real (e.g. those for adding Laver, Miller, Sacks, etc. reals) are equivalent to the forcing P(2)^{+} × Q where P(2) is considered as the Boolean algebra with two atoms. The atom of P(2) which the generic selects can be thought of as the first coordinate of the generic real which is added.

The following theorem will now become our focus:

Theorem 6.6. Suppose that ⟨Q_{α} : α < ω_{2}⟩ is a sequence of Borel partial orders such that for each α < ω_{2} Q_{α} is equivalent to P(2)^{+} × Q_{α} as a forcing notion and let P_{ω_{2}} be the countable support iteration of this sequence. If P_{ω_{2}} is proper and (A, B, E) is a Borel invariant then P_{ω_{2}} forces ⟨A, B, E⟩ ≤ ω_{1} iff P_{ω_{2}} forces ♢(A, B, E).

Remark 6.7. This is actually a rather weak formulation what can be proved. All of “Borel” that is used is that the forcing notions remain forcing notions in generic extensions and they can be computed from a real. Also, it is not entirely necessary that the forcing notions be in V; we will need only that the choice of the sequence of forcing notions does not depend on the “first coordinates” of the first ω_{1} generic reals added by the iteration. We chose the phrasing that we did both because of its simplicity and the fact that it covers most countable support iterations of definable forcings.

2In this paper we adopt the convention that if p is stronger than q then we write p ≤ q.

We will prove this theorem as a series of lemmas.

Lemma 6.8. Suppose that ⟨P_{α}, (P(2)^{+}×Q̇_{α}) : α < ω_{1}⟩ is a countable support iteration such that for all α < ω_{1} P_{α} forces Q̇_{α} is a proper partial order. For all α ≤ ω_{1}, the suborder P_{α}^{0} ⊆ P_{α} of all conditions whose first coordinate is trivial is completely embedded in P_{α}.

Proof. By induction on α we prove that the identity map ι_{α} : P_{α}^{0} → P_{α} is a complete embedding. Note that for γ < α, P_{γ}^{0} = {p ↾ γ : p ∈ P_{α}^{0}}. Also observe that P_{α}^{0} the direct limit of P_{γ}^{0} (γ < α) under the usual system of embeddings.

If α = 0 this is trivial. By the above observation, for a limit ordinal α > 0 we have (checking conditions (1) – (3) of Definition 7.1 of Ch VII in [19]):

1. Since ι_{α} is the inclusion map, it automatically preserves order.

2. If p, p′ are incompatible in P_{α}^{0}, there must be a γ < α such that p ↾ γ is incompatible with p ↾ γ′ in P_{γ}^{0} (this is a standard fact about direct limits — see 5.11 of Ch VIII in [19]). By the induction hypothesis, p ↾ γ and p′ ↾ γ are incompatible in P_{γ} and hence p and p′ are incompatible in P_{α}.

3. Given q in P_{α} let (ϵ̇_{γ}, q̇_{γ}) denote q(γ). It is easy to check by induction on γ < α that there is a unique condition q̄ in P_{α}^{0} such that q̄(γ) = (1, q̇_{γ}) for all γ < α. We now claim that if r ∈ P_{α}^{0} extends q̄ then r is compatible with q. Indeed, the γ^{th} coordinate of the common extension is (ϵ_{γ}, ṙ_{γ}) where r(γ) = (1, ṙ_{γ}).

This finishes the limit case of the inductive proof; the successor case is similar.

Lemma 6.9. Suppose T is a forcing notion which does not add any countable sequences of ordinals and that P = ⟨P_{α}, Q̇_{α} : α < δ⟩ is a proper countable support iteration of Borel forcing notions. The forcings T ∗ Ṗ and P × T are equivalent provided that they do not collapse ω_{1}.

Proof. The T -name Ṗ will be used to refer to the iteration computed after forcing with T . It now suffices to show that Ṗ is equal to P̌. This will be proved by induction on δ.

If δ is a limit of uncountable cofinality then, by the inductive hypothesis, P̌ and Ṗ are both inverse limits of equal orders (computed before and after forcing with T respectively). Since T adds no new countable sequences of ordinals, it forces that cf(δ) > ω. Therefore the inverse limit construction is absolute and we have that Ṗ equals P̌.

If δ is a limit of countable cofinality, the same argument applies with the observation that direct limits of systems with countable cofinality are absolute between models with the same countable sequences of ordinals.

Finally, if δ = α + 1 then P = P_{α} ∗ Q̇_{α}. First we will prove that T does not add any new P_{α}-names for reals. To this end, suppose that t is in T , ṙ is forced by t to be a T -name for a P_{α}-name for an element of 2^{ω}. Let Ȧ_{n} (n < ω) be a countable sequence such that t forces that Ȧ_{n} is a maximal antichain in P_{α} whose elements decide the value of ṙ(n). Since T ∗ P_{α} does not collapse ω_{1}, there is a t̄ extending t, a p in P_{α} and T -names Ċ_{n} such that t̄ forces that Ċ_{n} is a countable subset of Ȧ_{n} and is maximal below p. Since T does not add countable sequences, there is an extension of t̄ which decides Ċ_{n} for all n. Hence T does not add any P_{α}-names for reals and therefore Q_{α} is the same computed after forcing with T ∗ P_{α} as it is after forcing with P_{α}. Combining this with the inductive hypothesis we have

P̌ = P̌_{α} ∗ Q̌_{α} = Ṗ_{α} ∗ Q̇_{α} = Ṗ,

thus finishing the proof.

Definition 6.10. A forcing notion (P, ≤) is nowhere c.c.c. if for every p in P there is an uncountable antichain of elements which extend p.

Lemma 6.11. If P_{ω_{2}} is as in the statement of Theorem 6.6 and P_{ω_{1}} is the c.s. iteration of ⟨P_{α}, Q_{α} : α < ω_{1}⟩ then there is a P_{ω_{1}}-name Ṫ for a tree of height ω_{1} which is nowhere c.c.c. and does not add reals such that P_{ω_{2}} is equivalent to P_{ω_{2}} ∗ Ṫ.

Proof. By passing to an equivalent iteration, we replace P_{ω_{1}} by the c.s. iteration of the orders P(2)^{+} × Q_{α}. Let Ṫ be the P_{ω_{1}}^{0}-name for the quotient of P_{ω_{1}} by the P_{ω_{1}}^{0}-generic filter. Observe that if G ⊆ P_{ω_{1}}^{0} is generic, T is the collection of all t : α → 2 in V [G] such that for every γ ≤ α, t ↾ γ is in V [G ∩ P_{γ}^{0}]. From this it is clear that T is nowhere c.c.c.. Since Ṫ is P_{ω_{1}}^{0}-name for a tree of size ω_{1} which is everywhere of uncountable height and which embeds into a proper partial order, P_{ω_{1}}^{0} forces that Ṫ does not add any new countable sequences of ordinals.

Let Ṗ′ be the P_{ω_{1}}-name for the remaining part of the iteration P_{ω_{2}}. Now P_{ω_{2}} is equivalent to (P_{ω_{1}}^{0} ∗Ṫ)∗Ṗ′ which is in turn equivalent to P_{ω_{1}} ∗(Ṫ ∗P′) which is equivalent to (P_{ω_{1}} ∗ Ṗ′) ∗ Ṫ = P_{ω_{2}} ∗ Ṫ.

The following lemma now completes the proof of Theorem 6.6.

Lemma 6.12. Let (A, B, E) be a Borel invariant such that ⟨A, B, E⟩ ≤ ω_{1}. If T is a tree of height ω_{1} which is nowhere c.c.c. and does not add reals then T forces ♢(A, B, E).

Proof. Let b_{ξ} (ξ < ω_{1}) be a sequence of elements of B which witnesses ⟨A, B, E⟩ ≤ ω_{1} and let Ḟ : 2^{<ω_{1}} → A be a T -name for a Borel function. For each δ < ω_{1} pick a T -name ṙ_{δ} for a real which codes Ḟ ↾ δ. For each t in T of height δ pick a real s_{t} and a map h_{t} : ω_{1} → T such that

1. the collection {h_{t}(ξ) : ξ < ω_{1}} is an antichain and

2. h_{t}(ξ) extends t and forces ṙ_{δ} to be s_{t}.

Define a T -name ġ for a function from ω_{1} into B by making h_{t}(ξ) force that ġ(δ) = b_{ξ}, where δ is the height of t (if ġ is undefined somewhere define it arbitrarily).

Now let ḟ be a T -name for a function from ω_{1} to 2 and Ċ be a T -name for a closed unbounded subset of ω_{1}. Let A_{n} be a sequence of maximal antichains in T such that if u is in A_{n} and has height δ and ū is in A_{n+1} and extends u then ū decides ḟ ↾ δ and forces that there is an element of Ċ between δ and the height of ū. Since T does not add reals, there is a minimal t such that for every n there is a u_{n} in A_{n} which is below t. Hence if δ is the height of t, t decides ḟ ↾ δ and forces δ to be in Ċ. Now there is an a in A such that t forces that if Ḟ (ḟ ↾ δ) is computed using the code s_{t} then its value is a. Find a ξ such that (a, b_{ξ}) is in E. The condition h_{t}(ξ) forces that δ is in Ċ and that (Ḟ (ḟ ↾ δ), ġ(δ)) is in E, finishing the proof.

The following is a typical corollary of the previous two theorems. We will see in Section 7 that this in turn implies that 𝔞 = 𝔲 = ω_{1} in the iterated Sacks model.

Corollary 6.13. Both ♢(𝔯) and ♢(𝔡) hold in the iterated Sacks model.

The following result gives another way of seeing the relative consistency of ♣ + ¬CH.^{3} Unlike the standard proofs (see Chapter I Section 7 of [27]) where one deliberately arranges that ♣ holds in the forcing extension, the Sacks model was considered for entirely different reasons.

3Baumgartner has demonstrated in an unpublished note that ♣ holds in the Sacks model. This result was obtained shortly after Shelah’s proof of the consistency of ♣+¬CH [3].

Corollary 6.14. ♣ holds in the iterated Sacks model.

Proof. Without loss of generality we may assume that our ground model satisfies CH. It suffices to show that 𝕊_{ω_{2}} ∗ Ṫ forces ♣ where T is the forcing notion from Lemma 6.11. In [14] it has been (essentially) shown that for every 𝕊_{ω_{2}}-name Ẋ for an uncountable subset of ω_{1} there is a 𝕊_{ω_{2}}-name Ċ for a closed and unbounded subset of ω_{1} such that if p forces that δ is in Ċ then there is a q extending p and a ground model A ⊆ δ which is cofinal such that q forces that A is contained in Ẋ.

We will now work in the forcing extension given by 𝕊_{ω_{2}}. For each t in T , let h_{t} : ω_{1} → Ṫ be a 1-1 function such that the range of h_{t} is an antichain above t. For limit δ define a T -name Ċ_{δ} by letting h_{t}(ξ) force Ċ_{δ} = A_{ξ} where {A_{ξ} : ξ < ω_{1}} enumerates the cofinal subsets of δ before forcing with 𝕊_{ω_{2}}. The method of proof of Lemma 6.12 now shows that Ċ_{δ} (δ ∈ lim(ω_{1})) is forced to be a ♣-sequence.

One “rule of thumb” which one learns when working with the classical invariants of the form (A, B, E) is that, if ⟨A, B, E⟩ < ⟨C, D, F ⟩ is consistent then this can typically accomplished by a countable support iteration of length ω_{2} of proper Borel forcing notions in V (typically the sequence Q_{α} (α < ω_{2}) is a constant sequence).^{4} In such a case, Theorem 6.6 tells us that ♢(A, B, E) does not imply ⟨C, D, F ⟩ is ω_{1}. The reader is referred to [2] for an introduction to some of the common Borel forcing notions and [25] for some of the more advanced techniques for building Borel forcing notions.

The above results imply that ♢(ℝ, ≠) holds in many of the models obtained by adding a specific type of real. The following theorem, however, gives a much more natural setting for studying ♢(ℝ, ≠) and its consequences.

Theorem 6.15. After forcing with a Suslin tree ♢(ℝ, ≠) holds.

Proof. Similar to the proof of Theorem 6.6 (in fact it is most natural to show that ♢(ω, =) holds after forcing with a Suslin tree).

Many of the combinatorial consequences of 2^{ω} < 2^{ω_{1}} are in fact consequences of ♢(ℝ, ≠). It should be noted that Farah, Larson, Todorčević and others have noticed that these consequences hold after forcing with a Suslin tree.

4In general this is a phenomenon which is not well understood and is currently being analyzed by a number of people. There are Borel invariants such as cov(N) and (ℝ^{ω}, N , ⊑)

which can only be separated if the continuum is larger than ℵ_{ω} (f ⊑ E if the range of f is contained in E). This is because cov(N) can have countable cofinality [26] while (ℝ^{ω}, N , ⊑) cannot and yet cov(N) ≤ ⟨ℝ^{ω}, N , ⊑⟩ ≤ cf([cov(N)]^{ω}, ⊆).

Theorem 6.16. ♢(ℝ, ≠) implies:

1. 𝔱 = ω_{1}.

2. There are no Q-sets.

3. Every ladder system has a non-uniformizable coloring.

4. There is an uncountable subset of a c.c.c. partial order with no uncountable 3-linked subcollection.

Proof. Item 1 is deferred to Theorem 7.1 of the next section. The proof that ♢(ℝ, ≠) implies items 2 and 3 is the same as the proof that Φ(2, ≠) implies these statements (see [7]). Item 4 can be extracted from the proof of Theorem 7.7 of [32] and Theorem 7.1 below.

On the other hand, Larson and Todorčević have had a great deal of success in proving that certain consequences of MA_{ℵ_{1}} and other forcing axioms can hold after forcing with a Suslin tree (see [20], [21]). A variant on a major open question in this line of research is:

Question 6.17. Is ♢(ℝ, ≠) consistent with the assertion that every c.c.c. forcing notion has Property K?

7 ♢-principles and cardinal invariants

There are a number of well studied cardinal invariants of the continuum which do not satisfy our definition of “invariant.” Generally this is because the invariants in question make reference to some additional structure. For instance, 𝔲 can be considered to be the smallest size of a reaping family which is also a filter base. A natural question to ask is how these cardinals are influenced by the ♢-principles we have considered thus far. It turns out that these ♢-principles do have a strong impact on cardinals such as 𝔱, 𝔞, 𝔲, and 𝔦 and moreover provide a uniform approach for computing the values of these invariants in many standard models.

The first instance of this influence was Hrušák’s proof that ♢_{𝔡} implies 𝔞 = ω_{1}. In addition to allowing for easier computations, the results below explain why the proofs of statements such as CON(𝔟 < 𝔞) and CON(𝔯 < 𝔲) require more sophisticated arguments than, e.g., CON(𝔟 < 𝔡). It also suggests that there are no natural formulations of statements such as ♢(𝔱) and ♢(𝔞).

The first theorem is essentially a recasting of the well known fact that 2^{ω} < 2^{ω_{1}} implies 𝔱 = ω_{1}.

Theorem 7.1. ♢(ℝ, ≠) implies 𝔱 = ω_{1}.

Proof. ♢(ℝ, ≠) is equivalent to ♢(2, ≠) so we will use this assumption instead. Let X be the subset of ([ω]^{ω})^{ω} consisting of all strictly ⊆^{∗} decreasing sequences of sets. Let D : X → [ω]^{ω} be defined by setting the n^{th} element of D(A⃗) to be the least element of ⋂_{i≤n} A_{i} which is greater than n. Notice that D(A⃗) is almost contained in A_{n} for all n < ω and D is continuous.

Our map F will be defined on pairs A⃗, C where A⃗ = ⟨A_{ξ} : ξ < δ⟩ is a strictly ⊆^{∗}-decreasing sequence, δ is a limit and C is an infinite subset of ω which is almost contained in A_{ξ} for all ξ < δ. Let B(A⃗) be the collection of all even indexed elements of D(⟨A_{δ_{n}} : n ∈ ω⟩) in its increasing enumeration. Set F (A⃗, C) to be 0 if C is almost contained in B(A⃗) and 1 otherwise.

Let g : ω_{1} → 2 be a ♢(ℝ, ≠)-sequence for F. Construct ⟨A_{ξ} : ξ ∈ ω_{1}⟩ by recursion. Let A_{n} (n ∈ ω) be any strictly decreasing ω-sequence in [ω]^{ω}. Now suppose that ⟨A_{ξ} : ξ < δ⟩ is given. Define A_{δ} to be B(A⃗) if g(δ) = 0 and D(⟨A_{δ_{n}} : n ∈ ω⟩) \ B(A⃗) otherwise. It is easily checked that if F (⟨A_{ξ} : ξ < δ⟩, C) is defined and not equal to g(δ) then A_{δ} does not almost contain C.

The next result can be considered as an optimization of Theorem 1.1. It is an old result of Solomon that 𝔟 ≤ 𝔞 is provable in ZFC [8].

Theorem 7.2. ♢(𝔟) implies 𝔞 = ω_{1}.

Remark 7.3. Shelah has shown that 𝔟 < 𝔞 is consistent [28] (see also [6]).

Proof. We will first define a Borel function F into the set ω^{ω} as follows. The domain of F is the set of all pairs (⟨A_{ξ} : ξ < δ⟩, B) such that:

1. δ is an infinite countable ordinal.

2. {A_{ξ} : ξ < δ} ∪ {B} is an almost disjoint family of infinite subsets of ω.

3. For infinitely many n the set B ∩ A_{e_{δ}(n)} \ ⋃_{i<n} A_{e_{δ}(i)} is non-empty.

We will denote the set of n from condition 3 by I(A⃗, B). Define

F (⟨A_{ξ} : ξ < δ⟩, B)(k) = min (B ∩ A_{e_{δ}(n)} \ ⋃_{i<n} A_{e_{δ}(i)})

where n is the k^{th} least element of I(A⃗, B).

Now suppose that g : ω_{1} → ω^{ω} is a ♢(𝔟)-sequence for F. By making the entries in g larger if necessary, we may assume that they form a <^{∗}-strictly increasing sequence of increasing functions.

We will now construct a maximal almost disjoint family by recursion. Let ⟨A_{n} : n < ω⟩ be any almost disjoint family of infinite subsets of ω. If ⟨A_{ξ} : ξ < δ⟩ has been defined, set

A_{δ} = ω \ ⋃_{n<ω} [A_{e_{δ}(n)} \ (g(δ)(n) ∪ ⋃_{i<n} A_{e_{δ}(i)})] .

Since for each n the set g(δ)(n)∪⋃_{i<n} A_{e_{δ}(i)} has finite intersection with A_{e_{δ}(n)}, A_{ξ} has finite intersection with A_{δ} for each ξ < δ.

To see that {A_{ξ} : ξ < ω_{1}} is maximal, suppose that B is an infinite subset of ω. First notice that if δ is at least ω and (⟨A_{ξ} : ξ < δ⟩, B) satisfies condition (2) but not condition (3), then B has infinite intersection with (in fact is almost contained in) A_{δ}. Therefore we will be finished if we can show that if (⟨A_{ξ} : ξ < δ⟩, B) satisfies conditions (1)-(3) and g guesses (⟨A_{ξ} : ξ < ω_{1}⟩, B) at δ then B ∩ A_{δ} is infinite.

To this end, suppose

F (⟨A_{ξ} : ξ < δ⟩, B) ≯^{∗} g(δ)

and let N be a given natural number. For ease of reading we will let A⃗ abbreviate ⟨A_{ξ} : ξ < δ⟩. Find a number k such that the k^{th} least element n of I(A⃗, B) has the following properties:

1. g(δ)(k) is greater than F (A⃗, B)(k)

2. the minimum l of B ∩ A_{e_{δ}(n)} \ ⋃_{i<n} A_{e_{δ}(i)} is greater then N.

The last choice is possible since

{A_{e_{δ}(j)} \ ⋃_{i<j} A_{e_{δ}(i)} : j < ω}

forms a disjoint family of sets. It is now sufficient to show that l is in A_{δ}. Observe that the only possibility for removing l from A_{δ} is with the index n since l is in every set of the form ⋃_{i<m} A_{e_{δ}(i)} for m > n and not in any A_{e_{δ}(i)} for i < n. Since k ≤ n and g(δ) is monotonic, l = F (A⃗, B)(k) < g(δ)(k) ≤ g(δ)(n). Thus l is not in

A_{e_{δ}(n)} \ (g(δ)(n) ∪ ⋃_{i<n} A_{e_{δ}(i)})

and therefore is in A_{δ} as desired.

Notation. If two functions f, g in ω^{ω} are equal infinitely often, then we will write f =^{∞} g.

It is known that the cardinal non(M) is equal to ⟨ω^{ω}, =^{∞}⟩ [2].

Definition 7.4. [38] The cardinal 𝔞_{e} is the smallest size of a maximal collection A ⊆ ω^{ω} of eventually different functions.

It follows from the above remark that 𝔞_{e} ≥ non(M) and it has been shown by Brendle that strict inequality is consistent [5].

Theorem 7.5. ♢(ω^{ω}, =^{∞}) implies 𝔞_{e} = ω_{1}.

Proof. Let A_{n} (n ∈ ω) be a fixed partition of ω into infinite pieces. The domain of F will be all countable sequences ⟨f_{ξ} : ξ < δ⟩ of eventually different functions and an h ∈ ω^{ω} which is eventually different from every f_{ξ} (ξ < δ). For convenience our F will take values in (ω^{2})^{ω}. Set F (⟨f_{ξ} : ξ < δ⟩, h)(n) to be (k, h(k)) where k is the least integer in A_{n} such that h(l) ≠ f_{e_{δ}(i)}(l) for all i ≤ n and l ≥ k.

Let g : ω_{1} → (ω^{2})^{ω} be a ♢(ω^{ω}, =^{∞})-sequence for F. Construct a sequence of eventually different functions f_{ξ} (ξ ∈ ω_{1}) by recursion. Let f_{ξ} for ξ < δ be a given sequence of eventually different functions. Let Γ be the collection of all (k, v) such that k is in A_{n}, g(δ)(n) = (k, v), and if ξ < δ with e_{δ}^{−1}(ξ) ≤ n then f_{ξ}(k) ≠ v. Notice that for a given k there is at most one v such that (k, v) is in Γ, and that Γ is almost disjoint from f_{ξ} for all ξ < δ. Define f_{δ}(k) to be v if (k, v) is in Γ for some v and f_{δ}(k) to be the least integer greater than f_{ξ}(k) for all ξ with e_{δ}^{−1}(ξ) ≤ k. Notice that f_{δ} is eventually different from f_{ξ} for all ξ < δ. To see that {f_{ξ} : ξ ∈ ω_{1}} is maximal, let h ∈ ω^{ω} and notice that if F (⟨f_{ξ} : ξ < δ⟩, h) is defined and infinitely often equal to g(δ) then f_{δ} agrees with h on an infinite set — namely those k’s for which Γ was used in the definition of f_{δ}(k).

Recall that ♢_{𝔡} is the following statement from [16]:

♢_{𝔡} There is a sequence g_{δ} : δ → ω indexed by ω_{1} such that if f : ω_{1} → ω then there is a δ ≥ ω such that f ↾ δ <^{∗} g_{δ}.

It is straightforward to check that ♢_{𝔡} is a consequence of ♢(𝔡). The following theorem answers a question asked in [16].

Theorem 7.6. ♢_{𝔡} implies that ω^{ω} can be partitioned into ω_{1} compact sets.

Remark 7.7. Spinas has shown that it is consistent that 𝔡 = ω_{1} and yet ω^{ω} cannot be partitioned into ω_{1} disjoint compact sets [29].

Proof. Notice first that any σ-compact subset of ω^{ω} can be partitioned into countably many compact sets. This follows from the fact that ω^{ω} is 0dimensional. If f ∈ ω^{ω}, let K_{f} be the collection of all g in ω^{ω} such that g ≤ f. If C ⊆ ω^{ω} is compact and f ∈ ω^{ω} \ C, let Δ(f, C) be the maximum of Δ(f, y) where y ranges over C (if C is empty then let Δ(f, C) = 0). Since C is compact and f is not in C, this is always a finite number.

Let g_{δ} (δ ∈ ω_{1}) be a ♢_{𝔡}-sequence. Given C_{ξ} (ξ < δ), a disjoint sequence of compact sets for limit δ, define

F_{δ} = ⋃_{g=^{∗}g_{δ}}[K_{g↾ω} \ ⋃_{ξ<δ}{x ∈ ω^{ω} : Δ(x, C_{ξ}) > g(ξ)}].

Notice that ⋃_{ξ<δ}{x ∈ ω^{ω} : Δ(x, C_{ξ}) > g(ξ)} is open and hence F_{δ} is σcompact. Let {C_{δ+n} : n ∈ ω} be a partition of F_{δ} into disjoint compact sets. Clearly the sequence C_{ξ} (ξ ∈ ω_{1}) is pairwise disjoint. Let x be in ω^{ω} and suppose that x is not contained in C_{ξ} for any ξ ∈ ω_{1}. Define f : ω_{1} → ω by setting f ↾ ω = x and f(ξ) = Δ(x, C_{ξ}) if ξ ≥ ω. Now pick an δ > ω such that f ↾ δ <^{∗} g_{δ}. It follows that x is in F_{δ} and therefore in C_{δ+n} for some n, a contradiction.

Recall that a free ultrafilter U on ω is a P-point if whenever F_{n} (n ∈ ω) is a sequence of elements of U, there is a U in U such that U \ U_{n} is finite for each n ∈ ω.

Theorem 7.8. ♢(𝔯) implies that there is a P-point of character ω_{1}. In particular ♢(𝔯) implies 𝔲 = ω_{1}.

Remark 7.9. Shelah and Goldstern have shown that ω_{1} = 𝔯 < 𝔲 is consistent [12].

Proof. The domain of the function F we will consider will consist of pairs (U⃗, C) such that U⃗ = ⟨U_{ξ} : ξ < δ⟩ is a countable ⊆^{∗}-decreasing sequence of infinite subsets of ω and C is a subset of ω.

Given U⃗ as above, let B(U⃗) be the set {k_{i} : i ∈ ω} where

k_{i} = min(⋂_{j≤i} U_{e_{δ}^{−1}(j)} \ (k_{i−1} + 1)).

Note that B(U⃗) is infinite and almost contained in U_{ξ} for every ξ < δ. Let

F (U⃗, C) = {i : k_{i} ∈ C ∩ B(U⃗)}

if {i : k_{i} ∈ C ∩ B(U⃗)} is infinite and let

F (U⃗, C) = {i : k_{i} ∉ C ∩ B(U⃗)}

otherwise. Now suppose that g : ω_{1} → [ω]^{ω} is a ♢(𝔯)-sequence for F. Construct a ⊆^{∗}-decreasing sequence ⟨U_{ξ} : ξ ∈ ω_{1}⟩ of infinite sets by recursion. Let U_{n} = ω \ n. Having defined U⃗ = ⟨U_{ξ} : ξ < δ⟩ let U_{δ} = {k_{i} : i ∈ g(δ)} where B(U⃗) = {k_{i} : i ∈ ω}.

The family ⟨U_{ξ} : ξ ∈ ω_{1}⟩ obviously generates a P-filter. To see that it is an ultrafilter, note that if a C ⊆ ω is given and g guesses U⃗, C at δ then U_{δ} is either almost contained in or almost disjoint from C.

By combining the above proof with the argument that shows that 𝔡 = ω_{1} implies the existence of a Q-point one can without much difficulty prove the following.

Corollary 7.10. ♢(𝔯) + 𝔡 = ω_{1} implies that there is a selective ultrafilter of character ω_{1}.

Recall that 𝔦 is the smallest cardinality of a maximal independent family. In [1] the rational reaping number

𝔯_{ℚ} = (P(ℚ) \ NWD, “does not reap”)

is considered and it is proved that 𝔯, 𝔡 ≤ 𝔯_{ℚ} ≤ 𝔦. As with the earlier theorems we show that the last inequality is, in a sense, sharp.

Theorem 7.11. ♢(𝔯_{ℚ}) implies 𝔦 = ω_{1}.

Proof. For this proof we will view ℚ ⊆ 2^{ω} as the collection of all binary sequences with finite support. We will now define a Borel function F on pairs (⟨I_{ξ} : ξ < δ⟩, A) where δ is an ordinal less than ω_{1} and A and I_{ξ} are subsets of ω for all ξ < δ. The range of F will be contained in P(ℚ).

If δ is finite or I⃗ = ⟨I_{ξ} : ξ < δ⟩ is not independent then return ℚ as the value of F (I⃗, A). Otherwise, let x_{n}(I⃗) be the element of 2^{ω} defined by x_{n}(I⃗)(k) = 1 iff n is in I_{e_{δ}(k)}. Observe that X(I⃗) = {x_{n}(I⃗)}_{n=0}^{∞} is dense in 2^{ω} since I⃗ is independent. Fix a recursive homeomorphism h from X(I⃗) to ℚ. Now put F (I⃗, A) to be the image of {x_{n}(I⃗) : n ∈ A} under the map h.

Now suppose that g is a ♢(𝔯_{ℚ})-sequence for F. We will now build an independent family {I_{ξ} : ξ < ω_{1}} by recursion. Let {I_{n} : n < ω} be any countable independent family. Now given I⃗ = ⟨I_{ξ} : ξ < δ⟩, let t in 2^{<ω} be such that g(δ) is dense in [t] = {x ∈ 2^{ω} : t ⊆ x}. By altering g(δ) if necessary, we may assume that h^{−1}(g(δ)) is contained in [t] and that [t] \ h^{−1}(g(δ)) is also dense in [t]. Let C = {n ∈ ω : h(x_{n}) ∈ g(δ)}. First we will see that C has a nonempty intersection with ⋂_{i<|u|} I_{e_{δ}(i)}^{u(i)} iff u extends t where I^{1} = I and I^{0} = ω \ I. If n is in such an intersection then x_{n}(I⃗) must be in [u] by definition. Now, if u extends t, pick an n such that x_{n} is in h^{−1}(g(δ)) ∩ [u]. Then n is in C and in ⋂_{i<|u|} I_{e_{δ}(i)}^{u(i)}. Similarly one shows that

ω \ C intersects every set of the form ⋂_{i<|u|} I_{e_{δ}(i)}^{u(i)} for every u in 2^{<ω}. Form I_{δ}

so that ⟨I_{ξ} : ξ ≤ δ⟩ is independent and I_{δ} ∩ ⋂_{i<|t|} I_{e_{δ}(i)}^{t(i)} = C.

We are now finished once we show that {I_{ξ} : ξ < ω_{1}} is a maximal independent family. It is now sufficient to show that if g guesses (⟨I_{ξ} : ξ < ω_{1}⟩, A) at δ then {I_{ξ} : ξ ≤ δ} ∪ {A} is not independent. In fact, if t is the element of 2^{<ω} used in the definition of C then

I_{δ} ∩ ⋂_{i<|t|} I_{e_{δ}(i)}^{t(i)}

is either contained in or disjoint from A.

A natural question to ask is whether ♢(non(M)) implies the existence of a Luzin set. The answer is negative as the following theorem shows.

Theorem 7.12. It is consistent that both ♢(non(M)) and ♢(non(N)) hold and there are no Luzin or Sierpiński sets.

Proof. In the Miller model the cardinals non(M) and non(N) are both ω_{1} and hence by Theorem 6.6 the corresponding ♢-principles hold. On the other hand, Judah and Shelah [18] have shown there are no Luzin or Sierpiński sets in this model.

One should note that results of this section combined with those of the previous section provide unified approach to determining values of cardinal invariants with structure in many models in which this was traditionally done by arguments specific to the forcing construction at hand (see e.g. [9]).

8 ♢(A, B, E) and the Continuum Hypothesis

One of the most remarkable facts about the principle Φ of Devlin and Shelah is that, while it resembles a guessing principle in its statement, it is in fact equivalent to the inequality 2^{ω} < 2^{ω_{1}} [7]. The purpose of this section is to show that this phenomenon is rather unique to the invariants between (ℝ, ≠) and (2, ≠) which characterize Φ. In particular we will show that ♢(ℝ^{ω}, ⋣) is not a consequence of CH. To emphasize the relevance of this to the invariants considered in literature, we introduce the following definition.

Definition 8.1. A Borel invariant (A, B, E) is a σ-invariant if it satisfies the following strengthenings

3^{+}. There is a Borel map Δ : A^{ω} → B such that for all {a_{n}} in A^{ω} the relation a_{n}EΔ({a_{n}}) holds for all n.

4^{+}. There is a Borel map Δ^{∗} : B^{ω} → A such that for all {b_{n}} in B^{ω} the relation Δ^{∗}({b_{n}})Eb_{n} does not hold for any n.

Notice that if (A, B, E) is a Borel σ-invariant then ⟨A, B, E⟩ ≥ ω_{1}. Moreover the cardinal invariants (A, B, E) which appear in the literature typically satisfy these conditions. The connection to (ℝ^{ω}, ⋣) is the following.

Proposition 8.2. If (A, B, E) is a Borel σ-invariant then (A, B, E) is above (ℝ^{ω}, ⋣) and below (ℝ^{ω}, ⊑) in the Borel Tukey order.

Proof. We will only present the proof for (ℝ^{ω}, ⋣) as the proof dualizes to the other case. Since B must be an uncountable Borel set for (A, B, E) to be a σ-invariant, we can find a Borel isomorphism between B and ℝ. Thus it suffices to show that (B^{ω}, ⋣) is below (A, B, E) in the Borel Tukey order.

The map f : B^{ω} → A is the map Δ^{∗} and the map g : B → B^{ω} sends b to the constant sequence b̄. If b⃗ is in B^{ω} and b is in B with Δ^{∗}(b⃗)Eb then b could not be in the range of b⃗. Hence b⃗ ⋣ b̄.

Theorem 8.3. CH does not imply ♢(ℝ^{ω}, ⋣).

In order to prove this theorem, we will prove a more technical result which may be of independent interest.

Theorem 8.4. It is relatively consistent with CH that whenever C⃗ is a ladder system and r⃗ is a sequence of distinct elements of 2^{ω} indexed by lim(ω_{1}), there is a countable decomposition lim(ω_{1}) = ⋃_{n=0}^{∞} X_{n} such that if γ < δ are in X_{n} then

|C_{γ} ∩ C_{δ}| ≤ Δ(r_{γ}, r_{δ})

where Δ(r_{γ}, r_{δ}) is the size of the largest common initial segment of r_{γ} and r_{δ}.

We shall now prove several lemmas that will at the end allow us to prove Theorem 8.4. For the purposes of this proof let θ be a large enough regular cardinal.

Given a pair C⃗, r⃗ as in the theorem we will denote by Q_{C⃗,r⃗} the partial order consisting of functions q : lim(δ + 1) → 2^{<ω} for δ < ω_{1} and such that

1. q(β) is an initial segment of r_{β} for every β ∈ dom(q),

2. if β and γ are distinct and q(β) = q(γ) then |C_{γ} ∩ C_{β}| ≤ Δ(r_{γ}, r_{β}).

ordered by extension (reverse inclusion).

If q is in Q_{C⃗,r⃗}, C ⊆ ω_{1} has order type ω, r is in 2^{ω}, and σ is in 2^{<ω}, then we will say that q is consistent with (C, r) ↦ σ if σ is an initial segment of r and |C ∩ C_{δ}| ≤ Δ(r, r_{δ}) for every δ ∈ dom(q) with q(δ) = σ.

Lemma 8.5. Let q ∈ Q_{C⃗,r⃗}.

1. If C ⊆ ω_{1} has order type ω, |C ∩ dom(q)| is finite, and r is in 2^{ω}, then there is an n ∈ ω such that for all m ≥ n q is consistent with (C, r) ↦ r ↾ m.

2. If q is consistent with (C_{α}, r_{α}) ↦ σ then there is a q̄ ≤ q such that α is in the domain of q̄ and q̄(α) = σ.

3. Let M be a countable elementary submodel of H(θ) such that r⃗ ∈ M. If δ = M ∩ ω_{1} then for every β ∈ M ∩ ω_{1} and n ∈ ω there is a γ > β in M such that r_{γ} ↾ n = r_{δ} ↾ n.

Proof. For (1) n = |C ∩ dom(q)| obviously works. For (2) enumerate lim(α + 1) \ dom(q) as {α_{i} : i ∈ I}, where I is either an integer or ω, so that α = α_{0}. Recursively pick a sequence σ_{n} (n ∈ I) so that σ_{0} = σ, q is consistent with (C_{α_{n}}, r_{α_{n}}) ↦ σ_{n}, and |σ_{n}| < |σ_{n+1}|. Then set

q̄(β) = \begin{cases}q(β) & if β ∈ dom(q) \\ σ_{n} & if β = α_{n} for some n ∈ I. \end{cases}

To prove (3), let σ = r_{δ} ↾ n. As it is finite, σ ∈ M, and δ witnesses that

H(θ) ⊧ (∃γ > β)r_{γ} ↾ n = σ.

Hence M satisfies the same by elementarity.

Notice first that if G is a Q_{C⃗,r⃗}-generic filter then {X_{σ} : σ ∈ 2^{<ω}} is the required decomposition, where X_{σ} = {α : ∃q ∈ G(q(α) = σ)}.

Next we will show that the forcing Q_{C⃗,r⃗} is proper and does not add new reals, and that moreover these forcings can be iterated with countable support without adding reals. Recall that a forcing notion Q is totally proper if for every countable elementary submodel M of H(θ) such that Q ∈ M and for every q ∈ M ∩Q there is a q̄ ≤ q which is a lower bound for a filter containing q which is Q-generic over M. Every such q̄ is called totally (M, P)-generic. Q is α-proper (α < ω_{1}) if for every q in Q and every increasing ∈-chain {M_{β} : β ≤ α} of elementary submodels of H(θ) such that q, Q ∈ M_{0}, there is a q̄ ≤ q which is (M_{γ}, Q)-generic for every γ ≤ α. If Q is α-proper for every α < ω_{1} we will say that Q is < ω_{1}-proper.

It is not difficult to see that a forcing notion Q is totally proper if and only if it is proper and does not add reals (see [11]).

Lemma 8.6. The forcing notion Q_{C⃗,r⃗} is totally proper.

Proof. Let M be an elementary submodel of H(θ) such that C⃗, r⃗ ∈ M. Fix a q ∈ Q_{C⃗,r⃗} ∩ M and select an enumeration {D_{n} : n ∈ ω} of all dense open subsets of Q_{C⃗,r⃗} which are elements of M. Without loss of generality M is an increasing union of an ∈-chain of elementary submodels M_{n} (n ∈ ω) such that q and Q_{C⃗,r⃗} are in M_{0} and D_{n} is in M_{n}. Set δ = M ∩ ω_{1} and σ = r_{δ} ↾ |C_{δ} ∩ dom(q)|. Construct a sequence q_{n} (n ∈ ω) of conditions together with a sequence β_{n} (n ∈ ω) of ordinals so that

1. q ≥ q_{0} ≥ q_{1} ≥ ⋯ ≥ q_{n} ≥ q_{n+1} ≥ …,

2. C_{δ} ∩ M_{n} ⊆ β_{n} ∈ M_{n},

3. Δ(r_{β_{n}}, r_{δ}) ≥ |C_{δ} ∩ M_{n}|,

4. q_{n} ∈ M_{n} ∩ D_{n}, dom(q_{n}) = β_{n} + 1, and q_{n}(β_{n}) = σ.

Constructing these sequences is straightforward using Lemma 8.5. Having done this let

q̄ = ⋃_{n∈ω} q_{n} ∪ {(δ, σ)}.

Notice that as q_{n} is consistent with (C_{δ}, r_{δ}) ↦ σ for every n ∈ ω, q̄ is a condition in Q_{C⃗,r⃗}. q̄ is obviously totally (M, Q_{C⃗,r⃗})-generic since for every n, q̄ is below q_{n} which is in D_{n}.

Lemma 8.7. Q_{C⃗,r⃗} is α-proper for every α < ω_{1}.

Proof. We will prove the lemma by induction on α. Assume that the lemma holds for every β < α. Let {M_{β} : β ≤ α} and q ∈ Q_{C⃗,r⃗} ∩ M_{0} be given. Set δ_{β} = M_{β} ∩ ω_{1} for each β ≥ α and let σ = r_{δ_{α}} ↾ |C_{δ_{α}} ∩ dom(q)|.

If α = β + 1 for some β let q′ ∈ M_{α}, q′ ≤ q, be generic over all M_{γ} with γ ≤ β. As in Lemma 8.6 extend q′ to q̄ which is (totally) generic over M_{α}.

If α is a limit ordinal, we will mimic the proof of Lemma 8.6. Fix a sequence of ordinals α_{n} (n ∈ ω) increasing to α. Let {D_{n} : n ∈ ω} be an enumeration of all dense open subsets of Q_{C⃗,r⃗} in M_{α} such that D_{n} ∈ M_{α_{n}}. Construct a sequence q_{n} (n ∈ ω) of conditions together with a sequence β_{n} (n ∈ ω) of ordinals so that

1. q ≥ q_{0} ≥ q_{1} ≥ ⋯ ≥ q_{n} ≥ q_{n+1} ≥ …,

2. C_{δ_{α}} ∩ M_{α_{n}} ⊆ β_{n} ∈ M_{α_{n}},

3. Δ(r_{α_{n}}, r_{δ_{α}}) ≥ |C_{δ_{α}} ∩ M_{α_{n}}|,

4. q_{n} ∈ M_{n} ∩ D_{n}, dom(q_{n}) = β_{n} + 1, and q_{n}(β_{n}) = σ, and

5. q_{n+1} is M_{γ}-generic for every γ ≤ α_{n}.

Let q̄ = ⋃_{n∈ω} q_{n} ∪ {(δ_{α}, σ)}. The verification that this works is as in Lemma 8.6.

Recall the following definition and theorem from [11].

Definition 8.8. [11] Let P be totally proper and Q̇ a P-name for a forcing notion and let θ be a large enough regular cardinal. We shall say that Q̇ is 2-complete for P if WHENEVER

1. N_{0} ∈ N_{1} ∈ N_{2} are countable elementary submodels of H(θ),

2. P, Q̇ ∈ N_{0},

3. G ∈ N_{1} is P-generic over N_{0} and has a lower bound, and

4. q̇ ∈ N_{0} is a P-name for a condition in Q̇,

IT FOLLOWS THAT there is a G′ ∈ V which is Q̇-generic over N_{0}[G] such that q̇[G] ∈ G′ and if t ∈ P is a lower bound for G and t is P-generic for N_{1} and N_{2} then t forces that G′ has a lower bound in Q̇.

Theorem 8.9. [11] Let P_{κ} = ⟨P_{α}, Q̇_{α} : α < κ⟩ be a countable support iteration such that ⊩_{α} “Q̇_{α} is < ω_{1}-proper and Q̇_{α} is 2-complete for P_{α}”. Then P_{κ} is totally proper.

Lemma 8.10. Let P be a totally proper < ω_{1}-proper poset and let Q̇ be a P-name for Q_{C⃗,r⃗} for some pair C⃗, r⃗. Then Q̇ is 2-complete for P.

Proof. Let N_{0} ∈ N_{1} ∈ N_{2} be countable elementary submodels of H(θ) and let P, Q̇ ∈ N_{0}. Assume that G ∈ N_{1} is an (N_{0}, P)-generic filter having a lower bound and let q̇ ∈ N_{0} be a P-name for a condition in Q̇. We have to find a G′ which is a Q̇[G]-generic filter over N_{0}[G] such that whenever t ∈ P is a lower bound for G which is also P-generic over N_{1} and N_{2} then there is a P-name ṡ such that t ⊩ “ṡ is a lower bound for G′.”

Let δ = ω_{1} ∩ N_{0} and set

D = {D ∈ N_{0}[G] : N_{0}[G] ⊧ “D is dense open in Q̇[G]”}.

Since N_{0}, Q̇, D and G are all elements of N_{1} and N_{1} ⊧ “D is countable”, we can find an enumeration D = {D_{n} : n ∈ ω} which is in N_{1}.

Let E be the collection of all (C, r) such that C is a cofinal subset of δ of order type ω and r is in 2^{ω}. Clearly E is in N_{1}. Find an enumeration {(C^{n}, r^{n}) : n ∈ ω} =

{(C, r) ∈ E ∩ N_{1} : (∀β < δ)(∀n ∈ ω)(∃γ ∈ [β, δ))(r_{γ} ↾ n = r ↾ n)}

which is in N_{2}. If we knew what Ċ_{δ} and ṙ_{δ} evaluated to, we could proceed as in the proof of Lemma 8.6 to produce G′. This is typically not the case. What we do know, however, is that any t which is a lower bound for G and is P-generic over N_{1} and N_{2} forces that (Ċ_{δ}, ṙ_{δ}) appears in the enumeration {(C^{n}, r^{n}) : n ∈ ω}, since P does not add any new reals. This allows us to simulate the proof of Lemma 8.6 by diagonalizing over all possible choices of (Ċ_{δ}, ṙ_{δ}).

Again we may and will assume that N_{0} is the union of an ∈-chain of elementary submodels M_{n} (n ∈ ω) such that {M_{n} : n ∈ ω} is in N_{1}, q̇[G] is in M_{0} and D_{n} is in M_{n}[G]. Construct a sequence q_{n} (n ∈ ω) of conditions together with a sequence F_{n} (n ∈ ω) of finite sets of ordinals and σ_{n} (n ∈ ω) of elements of 2^{<ω} by recursion on n so that for every i ≤ n

1. q̇[G] ≥ q_{i} ≥ q_{n},

2. C^{i} ∩ M_{n}[G] ⊆ min F_{n} ∈ M_{n}[G],

3. q_{n} is consistent with (C^{i}, r^{i}) ↦ σ_{i}

4. there is a γ in F_{n} such that Δ(r_{γ}, r^{i}) ≥ |C^{i} ∩ M_{n}|, γ is in the domain of q_{n}, and q_{n}(γ) = σ_{i},

5. q_{n} ∈ M_{n}[G] ∩ D_{n}.

It is not difficult to construct these sequences. It follows directly from Clause 5 that if we set

G′ = {s ∈ N_{0}[G] : (∃n ∈ ω)q_{n} ≤ s}

then q̇[G] ∈ G′ and G′ is Q̇-generic over N_{0}[G]. Notice that, for every i, n ∈ ω, q_{n} is consistent with (C^{i}, r^{i}) ↦ σ_{i}. Define a name s̄ by

t ⊩ “s̄(β) = \begin{cases}q_{n}(β) & if β ∈ dom(q_{n}), \\ σ_{i} & if β = δ and t ⊩ “Ċ_{δ} = C^{i} and ṙ_{δ} = r^{i}”. \end{cases}

It is easy to see that if t is a lower bound for G and is P-generic over N_{1} and N_{2} then t ⊩ “ṡ ∈ Q̇” and obviously ṡ will be lower bound for G′.

Proof. (of Theorem 8.4) Let V be a model of GCH. Construct a countable support iteration P_{ω_{2}} = ⟨P_{α}, Q̇_{α} : α < ω_{2}⟩ such that for every α < ω_{2} we have ⊩_{α} “Q̇_{α} = Q_{C⃗,r⃗} for some pair C⃗, r⃗”. Since CH holds in V and ⊩_{α} “|Q_{α}| = ℵ_{1}” it follows that P_{ω_{2}} satisfies the ω_{2}-c.c.. A standard bookkeeping argument ensures that in V^{P_{ω_{2}}} every pair C⃗, r⃗ admits a decomposition of ω_{1} = ⋃_{n∈ω} X_{n} such that

|C_{γ} ∩ C_{δ}| ≤ Δ(r_{γ}, r_{δ})

whenever γ < δ are in the same X_{n}. By Theorem 8.9 and Lemmas 8.7 and 8.10, CH also holds in V^{P_{ω_{2}}} so the proof of Theorem 8.4 is complete.

We will now finish the proof of Theorem 8.3. Start with the model of the Theorem 8.4. First we will need the following lemma.

Lemma 8.11. There is a ladder system C_{δ} indexed by the positive countable limit ordinals such that C_{γ} ∩ C_{δ} is an initial segment of both C_{δ} and C_{γ} whenever γ < δ are limits.

Proof. Let h : ω^{<ω} ↔ ω be a bijection which satisfies h(s) < h(t) whenever s is an initial part of t. For a fixed limit δ > 0, we shall build an increasing ω-sequence δ̄_{n} (n ∈ ω) cofinal in δ such that for every n the ordinal δ̄_{n} has the form

δ̄_{n} = ξ + h(⟨e_{ξ+ω}^{−1}(δ̄_{i}) : i < n⟩)

for some limit ordinal ξ (note that ξ depends on n, is possibly equal to 0, and that this decomposition of δ̄_{n} is unique for any given n).

To see that this can be done, first note that if δ = ξ + ω for some limit ordinal ξ then

δ̄_{n} = ξ + h(⟨e_{ξ+ω}^{−1}(δ̄_{i}) : i < n⟩)

recursively defines the sequence of δ̄_{n}’s. If δ is a limit of limits, then first choose an increasing sequence of limits ξ_{n} (n < ω) which is cofinal in δ. Again

δ̄_{n} = ξ_{n} + h(⟨e_{ξ_{n}+ω}^{−1}(δ̄_{i}) : i < n⟩)

recursively defines the sequence of δ̄_{n}’s.

Now suppose that for some positive limit ordinals δ, ϵ < ω_{1} and some m, n < ω δ̄_{m} = ϵ̄_{n}. We need to show that m = n and that if i < m then δ̄_{i} = ϵ̄_{i}. Find a unique limit ordinal ξ and a unique element t in ω^{<ω} such that

δ̄_{m} = ξ + h(t) = ϵ̄_{n}.

Now notice that m = |t| = n and

δ̄_{i} = e_{ξ+ω}(t(i)) = e_{ξ+ω}(t(i)) = ϵ̄_{i}

for any i < n.

Fix C_{δ} = {δ̄_{n} : n ∈ ω} as in Lemma 8.11. For simplicity, identify ℝ with 2^{ω}. The domain of F will consist of a countable sequence t⃗ = ⟨t_{n} : n ∈ ω⟩ of functions from δ to 2 for some δ ∈ ω_{1}. Let the n^{th} element of the sequence F (t⃗) be given by

k ↦ t_{n}(δ̄_{k})

where δ = |t_{n}|. Now suppose that g : ω_{1} → ℝ^{ω} is given. For each i, let lim(ω_{1}) = ⋃_{j=0}^{∞} X_{i,j} such that for all γ < δ in X_{i,j}

|C_{γ} ∩ C_{δ}| ≤ Δ(g(γ)(i), g(δ)(i)).

Now it is possible to choose f_{n} : ω_{1} → 2 in such a way that if δ is in X_{i,j} then g(δ)(i) is the mapping

k ↦ f_{2^{i}3^{j}}(δ̄_{k}).

Thus for all limit δ the range of g(δ) is contained in the range of F (f⃗ ↾ δ). Remark 8.12. Shelah has shown that ♢(3, =) is not a consequence of CH (Section VIII.4 of [27]) and Eisworth has shown that ♢([ω]^{2}, ω, ∌) is not a consequence of CH [10].

References

[1] B. Balcar and M. Hrušák. Combinatorics of dense subsets of the rationals. Preprint, 2003.

[2] T. Bartoszyński and H. Judah. Set theory. On the structure of the real line. A K Peters, Ltd., 1995.

[3] T. Baumgartner. Personal communication, January 2003.

[4] A. Blass. Reductions between cardinal characteristics of the continuum. In Set Theory (Boise, ID, 1992–1994), 31–49. Contemp. Math., 192, AMS 1996.

[5] Jörg Brendle. Mad families and iteration theory. In Y. Zhang, editor, Logic and Algebra, 1–31. Contemp. Math., 302, AMS 2002.

[6] Jörg Brendle. Mob families and mad families. Arch. Math. Logic, 37(3):183–197, 1997.

[7] K. Devlin and S. Shelah. A weak version of ♢ which follows from 2^{ℵ_{0}} < 2^{ℵ_{1}}. Israel Journal of Math, 29(2–3):239–247, 1978.

[8] E. K. van Douwen. The integers and topology. In K. Kunen and J. Vaughan, editors, Handbook of Set-Theoretic Topology, pages 111– 167. North-Holland, 1984.

[9] A. Dow. More set-theory for topologists. Topology Appl., 64(3):243–300, 1995.

[10] T. Eisworth. All ladder systems can be anti-Dowker. Preprint.

[11] T. Eisworth and J. Roitman. CH with no Ostaszewski spaces. Trans. Amer. Math. Soc., 351(7):2675–2693, 1999.

[12] M. Goldstern and S. Shelah. Ramsey ultrafilters and the reaping number—con(𝔯 < 𝔲). Ann. Pure Appl. Logic, 49(2):121–142, 1990.

[13] J. Hirschorn. Cohen and random reals. PhD thesis, University of Toronto, 2000.

[14] M. Hrušák. Life in the Sacks model. Acta Univ. Carolin. Math. Phys., 42(2):43–58, 2001.

[15] M. Hrušák. Rendezvous with madness. PhD thesis, York University, 1999.

[16] M. Hrušák. Another ♢-like principle. Fund. Math., 167(3):277–289, 2001.

[17] R. B. Jensen. Souslin’s Hypothesis is incompatible with V = L. Notices Amer. Math. Soc., 15:935, 1968.

[18] Judah-Shelah. Killing Luzin and Sierpinski sets. Proc. Amer. Math. Soc., 120(3):917–920, 1994.

[19] K. Kunen. An introduction to independence proofs, volume 102 of Studies in Logic and the Foundations of Mathematics. North-Holland, 1983.

[20] P. Larson and S. Todorčević. Katětov’s problem. Trans. Amer. Math. Soc., 354:1783–1792, 2002.

[21] P. Larson and S. Todorčević. Chain conditions in maximal models. Fund. Math., 168(1):77–104, 2001.

[22] J. T. Moore. Random forcing and (S) and (L). Submitted to Top. Appl.

[23] J. T. Moore. Ramsey theory on sets of real numbers. PhD thesis, University of Toronto, 2000.

[24] A. Ostaszewski. On countably compact, perfectly normal spaces. J. London Math. Soc., 14(3):505–516, 1976.

[25] A. Rosłanowski and S. Shelah. Norms on possibilities I. Forcing with trees and creatures. Mem. Amer. Math. Soc., 141(671), 1999.

[26] Saharon Shelah. Covering of the null ideal may have countable cofinality. Fund. Math., 166(1-2):109–136, 2000. Saharon Shelah’s anniversary issue.

[27] S. Shelah. Proper and improper forcing. Springer-Verlag, Berlin, second edition, 1998.

[28] Saharon Shelah. On cardinal invariants of the continuum. In Axiomatic set theory (Boulder, Colo., 1983), pages 183–207. Amer. Math. Soc., Providence, RI, 1984.

[29] Otmar Spinas. Partition numbers. Ann. Pure Appl. Logic, 90(1-3):243– 262, 1997.

[30] S. Todorčević. Coherent sequences (preprint 2002). In Handbook of Set Theory. North-Holland.

[31] S. Todorčević. Partitioning pairs of countable ordinals. Acta Math., 159(3–4):261–294, 1987.

[32] S. Todorčević. Partition Problems In Topology. Amer. Math. Soc., 1989.

[33] S. Todorčević. Random set mappings and separability of compacta. Topology and its Applications, 74:265–274, 1996.

[34] Peter Vojtáš. Generalized Galois-Tukey-connections between explicit relations on classical objects of real analysis. In Set theory of the reals (Ramat Gan, 1991), pages 619–643. Bar-Ilan Univ., Ramat Gan, 1993.

[35] Nancy M. Warren. Properties of Stone-Čech compactifications of discrete spaces. Proc. Amer. Math. Soc., 33:599–606, 1972.

[36] W. H. Woodin. The Axiom of Determinacy, Forcing Axioms, and the Nonstationary Ideal. Logic and its Applications. de Gruyter, 1999.

[37] O. Yiparaki. On Some Partition Trees. PhD thesis, University of Michigan, 1994.

[38] Y. Zhang. On a class of mad families. J. Symbolic Logic, 64:737–746, 1999.