The canonical function game

Paul B. Larson^{∗}

June 20, 2004

Department of Mathematics, Miami University Oxford, Ohio 45056, United States email: larsonpb@@muohio.edu

Abstract

The canonical function game is a game of length ω_{1} introduced by W. Hugh Woodin which falls inside a class of games known as Neeman games. Using large cardinals, we show that it is possible to force that the game is not determined. We also discuss the relationship between this result and Σ_{2}^{2} absoluteness, cardinality spectra and Π_{2} maximality for H(ω_{2}) relative to the Continuum Hypothesis.

MSC2000: 03E60; 03E50, 03D60

The canonical function game, introduced by W.H. Woodin, is a game of perfect information of length ω_{1} between two players, whom we call Dominating and Undominated. In each round α, Undominated plays a countable ordinal u(α), and then Dominating plays σ_{α}, a wellordering of α of ordertype greater than u(α) (if α ≥ ω; when α is finite we require only that σ_{α} is a wellordering of α; the first ω moves are irrelevant to the outcome of the game). After all ω_{1} rounds have been played, Dominating wins the run of the game if and only if there exists a club C ⊂ ω_{1} such that σ_{α} = σ_{β} ∩ (α × α) for all α < β in C.

Given an ordinal γ ∈ [ω_{1}, ω_{2}), a canonical function for γ is a function f: ω_{1} → ω_{1} for which there exists a bijection π: ω_{1} → γ such that the set {α < ω_{1} | f(α) = o.t.(π[α])} contains a club subset of ω_{1}. Any two canonical functions for the same ordinal agree on a club. Futhermore, if γ < γ′ are ordinals in [ω_{1}, ω_{2}), f is a canonical function for γ and f′ is a canonical function for γ′, then f′ > f on a club. If ⟨(u(α), σ_{α}) : α < ω_{1}⟩ is a run of the canonical function game and C ⊂ ω_{1} is a club witnessing that Dominating wins this run of the game, then Σ = ∪{σ_{α} : α ∈ C} is a wellordering of ω_{1}, and the function f: ω_{1} → ω_{1} defined by letting f(α) be the ordertype of σ_{α} is a canonical function for the ordertype of Σ.

∗The research in this paper was conducted while the author was a guest of the Fields Institute, and the writing was completed with the support of a FAPESP fellowship (Grant # 02/11551-3) at the University of São Paulo.

We let Bounding denote the statement that every function from ω_{1} to ω_{1} is dominated by a canonical function on a club. If Bounding fails, then Undominated has a simple winning strategy in the canonical function game: he plays so that u: ω_{1} → ω_{1} is any function which is not dominated by a canonical function on a a club. Deiser and Donder [1] have shown Bounding to be equiconsistent with a strongly inaccessible limit of measurable cardinals.

In this paper we will show that the canonical function game is consistently undetermined, assuming the consistency of a strongly inaccessible limit of measurable cardinals. Part of the significance of this result is its relation to a class of games known as Neeman games. There are only countably many Neeman games, one for each n-ary formula ϕ (for some integer n) in the expanded language with one unary predicate. Given such a pair n, ϕ, the Neeman game G_{ϕ} is a game of length ω_{1} where players I and II collaborate to build a function a: ω_{1} → {0, 1}, with I picking a(0), II picking a(1) and so on, with I picking a(γ) for each limit ordinal γ. After a has been constructed, I wins if and only if there exists a club C ⊂ ω_{1} such that for all α_{1} < ⋯ < α_{n} in C, ⟨H(ω_{1}), a, ∈⟩ ⊧ ϕ(α_{1}, …, α_{n}). For a given integer n, an n-ary Neeman game is the Neeman game corresponding to some n-ary formula. The canonical function game can easily be recast as a binary Neeman game, with Dominating as I and Undominated as II (the fact that the players play in the opposite order in the two games is not important). In contrast to the main result of this paper, Neeman has shown that the existence of an iterable model with indiscernible Woodin cardinals implies that all unary Neeman games are determined [6].

If B is a set of reals, we define the B-Neeman game G_{B,ϕ}, where ϕ is an n-ary formula in the expanded language with two unary predicates, by saying that I wins if and only if there exists a club C ⊂ ω_{1} such that for all α_{1} < ⋯ < α_{n} in C, ⟨H(ω_{1}), a, B, ∈⟩ ⊧ ϕ(α_{1}, …, α_{n}). Woodin has connected the determinacy of Neeman games to the question of Σ_{2}^{2}-absoluteness with the following result.

Theorem 0.1. (Woodin) Suppose that these exists a proper class of supercompact cardinals. Let Γ denote the set of all universally Baire sets of reals. The following are equivalent.

• For each B ∈ Γ, ZFC + ◇_{G} implies in Ω-logic that all B-Neeman games are determined.

• For each B ∈ Γ and for every unary Σ_{2}^{2} formula ϕ, ZFC + ◇_{G} implies exactly one of ϕ(B) and ¬ϕ(B) in Ω-logic.

Here ◇_{G} (called generic Diamond) is the statement that for each Σ_{2} sentence ϕ for H(ω_{2}), ϕ holds if and only if Coll(ω_{1}, ℝ) forces ϕ; this is a strong form of ◇. We refer the reader to [9] for the definitions of Ω-logic and universally Baire sets of reals, which are not used in this paper (though we note that if T implies ϕ in Ω-logic, then T + ¬ϕ cannot be forced to hold in a rank initial segment of the universe). Again, the main results in this paper imply that some hypothesis beyond ZFC is required to imply the determinacy of all Neeman games in Ω-logic. Since ◇ implies that Bounding fails, the canonical function game is not a counterexample to ◇_{G} implying the determinacy of all Neeman games in Ω-logic, however.

The canonical function game and Theorem 0.1 were presented by Woodin in his talk Beyond Σ_{1}^{2} absoluteness, given June 2, 2002 at the Association for Symbolic Logic Annual Meeting at the University of Nevada, Las Vegas (see also [10]). Theorem 1.1 and Corollary 1.4 of this paper answer two questions asked in that talk.

1 Indeterminacy of the canonical function game

Theorem 1.1. Dominating does not have a winning strategy in the canonical function game.

Proof. Fix a strategy τ for Dominating. We will construct two plays of the canonical function game such that each is a play by τ and yet Dominating loses at least one of the two plays.

Our two runs of the game will be conducted on boards labelled a and b, and we will use Dominating(a), Undominated(a), u_{a} and σ_{α}^{a} to describe one run, and Dominating(b), Undominated(b), u_{b} and σ_{α}^{b} to describe the other.

Let A be a stationary, co-stationary subset of ω_{1}. For each round α, having built both plays up to round α, if α is in A then we let u_{a}(α) = 0 and let σ_{α}^{a} be the move given by τ for the partial play defined so far on board a. Then we let u_{b}(α) = o.t.(σ_{α}^{a}) + 1, and let σ_{α}^{b} be the move given by τ to the partial play given so far on board b. If α is not in A, then we reverse the roles of a and b. That is, we let u_{b}(α) = 0 and let σ_{α}^{b} be the move given by τ for the partial play defined so far on board b, then we let u_{a}(α) = o.t.(σ_{α}^{b}) + 1 and we let σ_{α}^{a} be the move given by τ to the partial play given so far on board a.

The essential point is that, having completely constructed both plays in this manner,

{α < ω_{1} | o.t.(σ_{α}^{a}) > o.t.(σ_{α}^{b})}

and

{α < ω_{1} | o.t.(σ_{α}^{a}) < o.t.(σ_{α}^{b})}

are both stationary subsets of ω_{1}. Now, if C and D are club subsets of ω_{1} such that

∀α, β ∈ C α < β ⇒ σ_{α}^{a} = σ_{β}^{a}↾α

and

∀α, β ∈ D α < β ⇒ σ_{α}^{b} = σ_{β}^{b}↾α,

then by taking the intersection of C and D we may assume that C = D. Further,

Σ_{a} = ⋃{σ_{α}^{a} | α ∈ C}

and

Σ_{b} = ⋃{σ_{α}^{b} | α ∈ C}

both define wellorderings of ω_{1}. Now, if o.t.(Σ_{a}) < o.t.(Σ_{b}), then for club many α ∈ C, o.t.(Σ_{a}↾α) < o.t.(Σ_{b}↾α). However, this is false, since for each α ∈ C, Σ_{a}↾α = σ_{α}^{a}, and Σ_{b}↾α = σ_{α}^{b}. The relations o.t.(Σ_{a}) > o.t.(Σ_{b}) and o.t.(Σ_{a}) = o.t.(Σ_{b}) are similarly contradictory.

Next we will see that is it consistent that Undominated fails to have a winning strategy. First we will show that if there exists a measurable cardinal, then for any strategy τ for Undominated there is a semi-proper forcing adding a run of the canonical function game where Dominating wins and Undominated plays by τ. This implies in particular that Martin’s Maximum [3] plus the existence of a measurable cardinal implies that the canonical function game is undetermined. Furthermore, we will see that the indeterminacy of the canonical function game can be forced from a strongly inaccessible limit of measurable cardinals.

Given a strategy τ for Undominated in the canonical function game, let P_{τ} be the forcing which adds a run of the game where Undominated plays by τ. The conditions in P_{τ} are countable partial runs of the game where Undominated plays by τ and Dominating was the last to play. The order is extension. Note that P_{τ} is countably closed. If p is a condition in P_{τ}, we let l(p) denote the length of p, and we let τ(p) be the response to p given by τ.

Given a cardinal κ, let Q_{κ} be the set of pairs (c, h) such that

• c is a closed, bounded subset of ω_{1},

• h is an injective function from max(c) to κ.

Still fixing τ and κ, let P Q_{κ}^{τ} be the partial order consiting of triples (p,c,h) such that

• p = ⟨(u(α), σ_{α}) : α < l(p)⟩ ∈ P_{τ},

• (c, h) ∈ Q_{κ},

• l(p) > max(c),

• for all α, β ∈ c, α < β implies that σ_{α} = σ_{β}↾α,

• for all α, β ∈ max(c), if α ≠ β then (α, β) ∈ σ_{max(c)} ⇔ h(α) < h(β).

We say that (p, c, h) ≥ (p′, c′, h′) if p′ extends p, c′ end-extends c and h ⊂ h′.

Suppose that κ is a cardinal and τ is a strategy for Undominated. Given that P Q_{κ}^{τ} preserves ω_{1}, which we will show in the case when κ is measurable, it follows by genericity that P Q_{κ}^{τ} adds a run of the canonical function game where Undominated plays by τ and Dominating wins.

Let μ be a normal measure on κ. Fix a regular cardinal θ > 2^{κ} and let X ≺ H(θ) be countable with μ, τ ∈ X. A condition p^{∗} ∈ P_{τ} is X-generic if for all α ∈ X ∩ ω_{1}, p^{∗}↾α is in X, and each dense subset of P_{τ} in X has some p^{∗}↾α (α ∈ X ∩ω_{1}) as a member. Likewise, a triple (p^{∗}, c^{∗}, h^{∗}) ∈ P_{τ} ×Q_{κ} is X-generic if for each α ∈ X ∩ ω_{1},

(p^{∗}↾(α + 1), c^{∗} ∩ (α + 1), h^{∗}↾α) ∈ P Q_{κ}^{τ} ∩ X,

and each dense open subset of P Q_{κ}^{τ} in X contains (p^{∗}↾(α+1), c^{∗} ∩(α+1), h^{∗}↾α) for some α ∈ X ∩ ω_{1}. Note that we do not require that (p^{∗}, c^{∗}, h^{∗}) ∈ P Q_{κ}^{τ} (i.e., we define genericity even for triples which are not conditions in P Q_{κ}^{τ}).

Still fixing X and μ, let A_{μ}^{X} = ⋂(X ∩ μ). It is a standard fact that if E ⊂ A_{μ}^{X}, then

X_{E} = {f(a) | f: [κ]^{<ω} → H(θ) ∧ f ∈ X ∧ a ∈ [E]^{<ω}}

is an elementary submodel of H(θ) containing X and end-extending X below κ (see, for instance, [4]). Whenever E is countable, we will call any such model X_{E} a μ-extension of X.

Lemma 1.2. Let μ be a normal measure on a cardinal κ and let τ be a strategy for Undominated in the canonical function game. Fix a regular cardinal θ > 2^{κ} and let X ≺ H(θ) be countable with μ, τ ∈ X. Let δ = X ∩ ω_{1}. Let p^{∗} be an X-generic condition in P_{τ}. Then for every μ-extension Y of X and for every pair (c, h) ∈ Y ∩ Q_{κ} such that

(p^{∗}↾(max(c) + 1), c, h) ∈ P Q_{κ}^{τ}

there exists a pair (c^{∗}, h^{∗}) ∈ Q_{κ} such that (p^{∗}, c^{∗}, h^{∗}) is Y -generic.

Furthermore, if o.t.(Y ∩ κ) > τ(p^{∗}), then

((p^{∗})^{⌢}(τ(p^{∗}), ⋃{σ_{α} : α ∈ c^{∗}}), c^{∗} ∪ {δ}, h^{∗}) ∈ P Q_{κ}^{τ}.

Proof. Fix μ, κ, τ, θ, X, δ and p^{∗} as given. Let E ⊂ A_{μ}^{X} be countable and let Y = X_{E}. Fix (c, h) as in the statement of the lemma. We will build c^{∗} and h^{∗} by approximations c_{k}, h_{k} in Y. Let c_{0} = c and h_{0} = h. Let D_{k} (k < ω) enumerate the dense subsets of P Q_{κ}^{τ} in Y. Given c_{k} and h_{k}, we will find c_{k+1} and h_{k+1} in Y extending c_{k} and h_{k} such that

(p^{∗}↾(max(c_{k+1}) + 1), c_{k+1}, h_{k+1}) ∈ D_{k}.

The key point is that since Y end-extends X below κ, p^{∗} is Y -generic for P_{τ}. The set of conditions p in P_{τ} for which there is some pair (c′, h′) ∈ Q_{κ} extending (c_{k}, h_{k}) such that (p, c′, h′) ∈ D_{k} (and such that the length of p is equal to max(c′) + 1) is dense below p^{∗}↾(max(c_{k}) + 1) and is a member of Y, so some initial segment of p^{∗} in Y satisfies this condition, enabling the choice of the desired pair (c_{k+1}, h_{k+1}).

The last part of the conclusion of the lemma follows from the fact that for each γ ∈ κ, the set of (p′, c′, h′) ∈ P Q_{κ}^{τ} with γ ∈ range(h′) is dense, which in turn implies that h^{∗}[δ] = Y ∩ κ. To see that this set is dense, fix (p̄, c̄, h̄) ∈ P Q_{κ}^{τ} and γ < κ such that γ ∉ range(h̄). Let β = l(p̄) + ω and extend p̄ to a partial play p′ = ⟨u(α), σ_{α} : α ≤ β⟩ according to τ such that the following hold.

• σ_{β}↾max(c̄) = σ_{max(c̄)}.

• for all α < max(c̄), (α, max(c̄)) ∈ σ_{β} ⇔ h′(α) < γ.

• (max(c̄) + 1) × (β \ (max(c̄) + 1)) ⊂ σ_{β}.

Then if c′ = c̄ ∪ {β} and h′ is any suitable extension of h̄ ∪ {(max(c̄), γ)} (for example, for each α ∈ β \(max(c̄)+1) we could let h′(α) be sup(range(h̄))+ζ_{α}, where ζ_{α} is the rank of α in the wellordering σ_{β}), then (p′, c′, h′) ≤ (p̄, c̄, h̄) in P Q_{κ}^{τ} and γ ∈ range(h′).

Theorem 1.3. If κ is a measurable cardinal, and τ is a strategy for Undominated, then there is a semi-proper forcing adding a run of the game for which Undominated plays by τ and Dominating wins.

Proof. The forcing is P Q_{κ}^{τ}. We need to see only that this forcing is semi-proper. Let (p, c, h) be a condition in P Q_{κ}^{τ}, let θ be a regular cardinal greater than 2^{κ} and let X be a countable elementary submodel of H(θ) with τ, κ and (p, c, h) in X. Let p^{∗} be an X-generic condition in P_{τ}. Let μ be a normal measure on κ in X and let Y be a μ-extension of X such that o.t.(Y ∩ κ) > τ(p^{∗}). Then by Lemma 1.2 there is a pair c^{∗}, h^{∗} such that (p^{∗}, c^{∗}, h^{∗}) is a Y -generic condition in P Q_{κ}^{τ}.

Corollary 1.4. Martin’s Maximum plus the existence of a measurable cardinal implies that Undominated does not have a winning strategy in the canonical function game.

Given a cardinal κ, let R_{κ} denote the countable support product of all the partial orders P Q_{κ}^{τ} where τ is a strategy for Undominated. The proof of Lemma 1.2 shows that if κ is a measurable cardinal then R_{κ} is semi-proper (first take an X-generic for the countable support product of all the P_{τ} ’s, then end-extend to a Y such that o.t.(Y ∩κ) is greater than all the τ(p)’s, and choose the rest of the generic filter as before; there are several suitable alternate definitions of R_{κ}). Now suppose that λ is a strongly inaccessible limit of measurable cardinals, and let ℙ = ⟨ℙ_{α}, ℚ_{∼}_{α} : α < λ⟩ be an RCS iteration (see [2]) such that each ℚ_{α} is forced to be R_{κ} for κ the least measurable cardinal in the extension by ℙ_{α}. If ρ is a ℙ-name for a strategy for Undominated in the canonical function game, then in the ℙ-extension (in which λ = ω_{2}) there is a γ < λ such that G ∩ ℙ_{γ} (where G ⊂ ℙ is the generic filter) decides ρ on all positions in V [G ∩ ℙ_{γ}]. Then ℚ_{γ} added a complete run of the game where Undominated played by ρ and lost. Putting all of this together, we have the following.

Theorem 1.5. If there exists a strongly inaccessible limit of measurable cardinals then there is a semi-proper forcing making the canonical function game undetermined.

2 … and the Continuum Hypothesis

Although the forcing P Q_{κ}^{τ} is (ω, ∞)-distributive, we do not know whether the indeterminacy of the canonical function game is consistent with CH. Thi questions raises some interesting issues. The principle below has been known for some time; the name we give for it is new.

2.1 Definition. ♣_{c} (Club for clubs) is the statement that there exist a_{α} (α a countable limit ordinal) such that each a_{α} is a cofinal subset of α of ordertype ω and such that for every club subset C of ω_{1} there is an α < ω_{1} such that a_{α} ⊂ C.

Call a pair X, Y of countable elementary submodels of H(ω_{2}) good if either X ∩ ω_{1} ≠ Y ∩ ω_{1} or for all club subsets of ω_{1} C ∈ X and D ∈ Y,

C ∩ D ∩ X ∩ ω_{1} ≠ ∅.

We let (+) denote the statement that there exists a stationary set S of countable elementary submodels of H(ω_{2}) such that every pair from S is good.

Theorem 2.2. ♣_{c} ⇒ (+).

Proof. Let ⟨a_{α} : α < ω_{1} limit⟩ witness ♣_{c}, and let S be the set of countable X ≺ H(ω_{2}) such that for every club D ⊂ ω_{1} in X, a_{(X∩ω_{1})} \ D is bounded in X ∩ ω_{1}. Any pair of members of S is good. If S is not stationary, then there exists a continuous, increasing chain ⟨X_{α} : α < ω_{1}⟩ of countable elementary submodels of H(ω_{2}) not in S. Let ⟨D_{α} : α < ω_{1}⟩ enumerate the club subsets of ω_{1} in ∪{X_{α} : α < ω_{1}}, and let D = △{D_{α} : α < ω_{1}⟩. Let E ⊂ ω be the club consisting of all β < ω_{1} such that {D_{α} : α < β} lists the club subsets of ω_{1} in X_{β}. Now let β be such that a_{β} ⊂ D ∩ E. Then for each α < β, a_{(X∩ω_{1})} \ D_{α} is bounded in X ∩ ω_{1}, so X_{β} ∈ S, giving a contradiction.

Theorem 2.3. The statement (+) implies that Undominated has a winning strategy in the canonical function game.

Proof. Let S witness (+). The strategy for Undominated is, in round β, if

p = ⟨(u(α), σ_{α}) : α < β⟩

is the play so far and there exist an X ∈ S and a complete run of the game p^{∗} = ⟨(u′(α), σ′_{α}) : α < ω_{1}⟩ in X such that

• X ∩ ω_{1} = β,

• p = p^{∗}↾β,

• Dominating wins the run p^{∗}, then choose such a pair X, p^{∗} and let u(β) = o.t.(σ′_{β}) + 1. If there is no such pair X, p^{∗}, then let u(β) = 0. Now suppose that

p̄ = ⟨(u(α), σ_{α}) : α < ω_{1}⟩

is a complete run of the game where Undominated has played by this strategy and Dominating has won. Then there is a Y ∈ S with p̄ ∈ Y. Let β = Y ∩ ω_{1}. By the rules of the strategy for Undominated and the properties of the pair Y, p̄, there exist an X ∈ S and a complete run of the game p^{∗} = ⟨(u′(α), σ′_{α}) : α < ω_{1}⟩ in X such that

• X ∩ ω_{1} = β

• p^{∗}↾β = p̄↾β

• Dominating wins the run p^{∗},

• u(β) = o.t.(σ′_{β}) + 1.

Let C ∈ Y and D ∈ X be club subsets of ω_{1} witnessing respectively that p̄ and p^{∗} are winning plays for Dominating. Since X and Y are both in S, C ∩ D ∩ β must be cofinal in β. Then

σ_{β} = ∪{σ_{α} : α ∈ C ∩ D ∩ β} = σ′_{β},

contradicting the fact that o.t.(σ_{β}) > u(β) > o.t.(σ′_{β}).

So ♣_{c} implies that the canonical function game is determined. In [5], it was shown that Bounding is consistent with the Continuum Hypothesis. An important point of the proof of this fact is that the standard forcing to make Bounding hold is α-semi-proper, for each countable ordinal α, as defined below. Recall that if P is a partial order, θ is a regular cardinal greater than 2^{|P |} and X is a countable elementary submodel of H(θ) with P ∈ X, then a condition p ∈ P is (X, P)-semi-generic if p⊩τ ∈ (X̌ ∩ ω_{1}) for each P -name τ in X for a countable ordinal.

2.4 Definition. Given a countable ordinal α, a partial order P is α-semi-proper if, whenever p ∈ P, θ is a regular cardinal greater than 2^{|P |}, ≤_{θ} is a wellordering of H(θ) and X_{β} (β < α) are countable elementary submodels of ⟨H(θ), ≤_{θ}, ∈⟩ with each ⟨X_{γ} : γ < β⟩ ∈ X_{β} and p, P ∈ X_{0}, there exists a p′ ≤ p in P which is (X_{β}, P)-semi-generic for each β < α.

Theorem 2.5 below is a generalization of a standard fact. Along with the observation that the one-step forcing in the iteration to make Bounding hold makes ♣_{c} hold, it shows that ♣_{c} holds in all currently known models of Bounding + CH.

Theorem 2.5. The principle ♣_{c} is preserved by ω-semi-proper forcing.

Proof. Let P be an ω-semi-proper partial order and let ⟨a_{α} : α < ω_{1} limit⟩ witness ♣_{c}. Let p be a condition in P and let τ be a P -name for a club subset of ω_{1}. We will find a p′ ≤ p and a limit ordinal α < ω_{1} such that p′ forces that a_{α} ⊂ τ. Let θ be a regular cardinal greater than 2^{|P |}, let ≤_{θ} be a wellordering of H(θ) and let ⟨X_{α} : α < ω_{1}⟩ be a continuous, increasing chain of countable elementary submodels of ⟨H(θ), ≤_{θ}, ∈⟩ such that p, P ∈ X_{0} and each X_{β} ∈ X_{α} for all β < α < ω_{1}. Let D = {X_{α} ∩ ω_{1} : α < ω_{1} limit}. Then D is a club subset of ω_{1}. Let α < ω_{1} be such that a_{α} ⊂ D. Let ⟨β_{i} : i < ω⟩ be an increasing enumeration of a_{α}, and let ⟨γ_{i} : i < ω⟩ be such that each β_{i} = X_{γ_{i}} ∩ ω_{1}. Then p, P ∈ X_{γ_{0}} and each ⟨X_{γ_{j}} : j < i⟩ ∈ X_{γ_{i}}. Therefore, there is a condition p′ ≤ p in P which is (X_{γ_{i}}, P)-semi-generic for each i < ω. This p′ then forces that {β_{i} : i < ω} ⊂ τ.

This raises two questions.

2.6 Question. Does CH imply that Undominated has a winning strategy in the canonical function game?

2.7 Question. Does Bounding + CH imply ♣_{c}?

A negative answer to Question 2.6 would imply a negative answer to Question 2.7, which in turn would require a new proof of the consistency of Bounding + CH. On the other hand, a positive answer to Question 2.7 would give a positive answer to the following question of Woodin.

2.8 Question. ([9]) Do there exist Π_{2} sentences for H(ω_{2}) ϕ and ψ such that CH + ϕ and CH + ψ are both Ω-consistent but CH + ϕ + ψ is not?

By contrast, Woodin has shown that all Ω-consistent Π_{2} sentences for H(ω_{2}) hold in the ℙ_{max} extension of L(ℝ), assuming certain large cardinals [9]. Shelah has shown that CH is consistent with the failure of ♣_{c} ([8], Chapter XVIII).

3 Elementary submodels and absoluteness

Shelah ([8], Chapter XVI) has shown that if there exists a Woodin cardinal, then there is a semi-proper forcing making the nonstationary ideal on ω_{1} (NS_{ω_{1}}) saturated. His argument makes use of the following definitions, the first of which is implicit in [3].

3.1 Definition. A set A ⊂ P(ω_{1})\NS_{ω_{1}} is semi-proper if for any transitive set M closed under sequences of length 2^{ω_{2}}, if X ≺ M is countable with A ∈ X, then there exists a countable Y ≺ M such that

• X ⊂ Y,

• X ∩ ω_{1} = Y ∩ ω_{1},

• Y ∩ ω_{1} ∈ S for some S ∈ Y ∩ A.

3.2 Definition. Given a set A ⊂ P(ω_{1}) \ NS_{ω_{1}}, the sealing forcing for A is the partial order consisting of pairs (f, c) such that f is a function into A with domain some countable ordinal and c is a closed subset of dom(f) + 1 such that for each α ∈ c there exists a β < α with α ∈ f(β), ordered by extension.

If A ⊂ P(ω_{1}) \ NS_{ω_{1}} is semi-proper in the sense of Definition 3.1, then the sealing forcing for A is semi-proper in the usual sense. Shelah’s forcing for making NS_{ω_{1}} saturated consists of an iteration of length some Woodin cardinal where at limit stages one forces with the countable support product of all semiproper sealing forcings as above, and at successor stages with Coll(ω_{1}, 2^{ω_{2}}).

The following definition, taken from [9], is implicit in Shelah’s argument.

3.3 Definition. Suppose that A ⊂ P(ω_{1})\NS_{ω_{1}}. Let T_{A} be the set of countable X ≺ P(H(ω_{2})) such that for no countable Y ≺ P(H(ω_{2})) does it hold that

• X ⊂ Y,

• X ∩ ω_{1} = Y ∩ ω_{1},

• Y ∩ ω_{1} ∈ S for some S ∈ Y ∩ A.

So if, A ⊂ P(ω_{1}) \ NS_{ω_{1}} is not semi-proper, then T_{A} is a stationary subset of P_{ω_{1}}(P(H(ω_{2}))). Following [9], if N ⊂ M are transitive models of ZFC with the same ω_{1}, say that M is a good extension of N if (T_{A})^{N} is a stationary set in M for each A ⊂ (P(ω_{1}) \ NS_{ω_{1}})^{N} which is predense and not semi-proper in N.

Now, suppose that δ is a Woodin cardinal. Let ℙ be any semi-proper iteration of length δ where at limit stages we take the countable support product of all semi-proper sealing forcings as above, and at successors to limit stages we pass to a good extension while collapsing 2^{ω_{2}}. Then it follows immediately from Claim XVI 2.8 of [8] or Theorem 2.62 of [9] that ℙ makes NS_{ω_{1}} saturated. (Using this fact, Theorem 2.5 and the fact (shown in [5]) that ω-semi-properness is preserved by Revised Countable Support iterations, it is straightforward to show that the saturation of NS_{ω_{1}} is consistent with ♣_{c}.) The key point here is that if N ⊂ M are transitive models of ZFC such that M is a good extension of N and (2^{ω_{2}})^{N} has cardinality ℵ_{1} in M, then any semi-proper extension of M is a good extension of N. So if our iteration uses Coll(ω_{1}, 2^{ω_{2}}) at successors to limit stages and the forcing R_{κ} (for κ the least measurable cardinal) defined at the end of Section 1 at all other successor stages, ℙ forces that NS_{ω_{1}} is saturated and the canonical function game is undetermined (since the countable support product of all semi-proper sealing forcings followed by Coll(ω_{1}, 2^{ω_{2}}) doesn’t add reals, every strategy for Undominated existing after a limit stage of the iteration is still defined on every position two steps later). In fact, the proof of Lemma 1.2 shows that we can use R_{κ} at all successor stages to achieve the same effect (i.e., the R_{κ}-extension is also good - the proof of this, relative to the version of Lemma 1.2 for R_{κ}, is the same as the proof of Lemma 2.63 in [9]).

For a given real number x, let I_{x} denote the class of indiscernibles for x, assuming that x^{#} exists. We let C_{x} denote the class of uncountable cardinals of the inner model L[x]. If ω_{1} is inaccessible to reals then for each real x, C_{x} ∩ ω_{1} is a club subset of ω_{1}. Also, standard arguments show that for each real x and each γ ∈ C_{x^{#}}, I_{x} ∩ γ is definable over L_{γ}[x^{#}] and has ordertype γ, so in particular C_{x^{#}} ⊂ I_{x}.

Woodin [9] has shown that if NS_{ω_{1}} is saturated and there exists a measurable cardinal, then every club subset of ω_{1} contains I_{x} ∩ ω_{1} (and thus C_{x^{#}} ∩ ω_{1}) for some real number x. It is not hard to see that if

• ω_{1} is inaccessible to reals,

• every club subset of ω_{1} contains C_{x} ∩ ω_{1} for some real x,

• there is a function f: ℝ → ℝ such that for all x, y ∈ ℝ,

min(C_{x} ∩ C_{y}) < min(C_{f(x)} ∩ C_{f(y)}),

then (+) holds, and in fact there is a club set C of countable elementary submodels of H(ω_{2}) (those closed under f) such that each pair from C is good. While the existence of such a club C is consistent (there is one in L, for instance), the hypotheses of the previous sentence may be contradictory, as far we know. In any case, we have the following theorem.

Theorem 3.4. Suppose that there exists a Woodin cardinal δ below a measurable cardinal. Then for every function f: ℝ → ℝ existing in an inner model whose theory cannot be changed by forcing with a partial order in V_{δ+1}, there exist x, y ∈ ℝ, such that

min(C_{x} ∩ C_{y}) = min(C_{f(x)} ∩ C_{f(y)}).

Woodin has shown that whenever δ is a limit of Woodin cardinals below a measurable cardinal no forcing construction in V_{δ} can change the theory of L(ℝ) (see [4]). Even for the special case of the function f(x) = x^{#}, we know of no direct proof of Theorem 3.4. Paris [7] has shown that if a and b are reals such that a ∈ L[b] and a^{#} ∉ L[b], then there are countable ordinals α and β such that every α-th a-indiscernible above β is a b-indiscernible. It follows then that if x, y are reals such that min(C_{x} ∩ C_{y}) = min(C_{x^{#}} ∩ C_{y^{#}}), then the set of reals in L[x] ∩ L[y] is closed under sharps.

Theorem 3.4 can be easily generalized in a number of ways, none of which we have application for at this time.

References

[1] O. Deiser, H.-D. Donder, Canonical functions, non-regular ultrafilters and Ulam’s problem on ω_{1}, J. Symbolic Logic, 68 (2003), no. 3, 713–739

[2] H.-D. Donder, U. Fuchs, Revised Countable Support Iterations, Handbook of Set Theory, to appear [3] M. Foreman, M. Magidor, S. Shelah, Martin’s Maximum. saturated ideals,

and non-regular ultrafilters. Part I, Annals of Mathematics, 127 (1988), 1-47

[4] P. Larson, Notes on the stationary tower, American Mathematical Society University Lecture Series, to appear

[5] P. Larson, S. Shelah, Bounding by canonical funtions, with CH, J. Math. Logic 3 (2003), No. 2, 193-215

[6] I. Neeman, Games of length ω_{1}, in preparation

[7] Paris, J.B., Patterns of indiscernibles, Bull. London Math. Soc. 6 (1974) 183-188

[8] S. Shelah, Proper and improper forcing, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1998

[9] W.H. Woodin, The axiom of determinacy, forcing axioms, and the nonstationary ideal, DeGruyter Series in Logic and Its Applications, vol. 1, 1999

[10] W.H. Woodin, Beyond Σ ∼_{1}^{2} absoluteness, Proceedings of the International Congress of Mathematicians, Vol. I (Beijing, 2002), 515–524