Games with creatures

Saharon Shelah and Jindřich Zapletal ^{∗}

March 17, 2002

Abstract

Many forcing notions obtained using the creature technology are naturally connected with certain integer games.

1 Introduction

The paper [7] revealed an intimate connection between the proper forcing technology and determinacy of infinite games. Many definable proper forcings P adding a real turn out to have an integer game attached to them. This means that there are Borel sets C, D ⊂ ω^{ω} and a Borel function f : C → ℝ such that

1. the set I = {A ⊂ ℝ : the second player has a winning strategy in the integer game with payoff set D ∪ f^{−1}A} is a σ-ideal

2. every analytic I-positive set has a Borel I-positive subset

3. the poset P is forcing equivalent to the poset of all Borel I-positive sets modulo the ideal I.

This is in fact a very natural concept, but it must be illustrated on examples.

Example 1.1. The game attached to Sacks forcing is just the perfect set game [1]. Just let C = ω^{ω}, D = 0 and use a reasonable coding of the perfect set game into an integer game to let f : ω^{ω} → ℝ be given by f(x) =the real resulting from the run of the perfect set game coded by x.

Example 1.2. The game attached to Miller forcing is the unboundedness game of [2]

Example 1.3. The game attached to Cohen forcing is the Baire category game [1].

∗The first author is supported by The Israel Science Foundation founded by the Israel Academy of Sciences and Humanities. Publication 791. The second author is partially supported by grants GA ČR 201-00-1466, NSF DMS-0071437 and a CLAS UF research award.

Example 1.4. Mathias forcing does not have an integer game attached to it. This follows from the fact that Mathias forcing can be written as a two step σ-closed*c.c.c. iteration, see the next paragraph.

In this paper we show that there is a pattern extending to many partial orders obtained by the creature technology of [4], and in fact the proofs of properness of such posets naturally generate the related games. Why are we interested in the connection? First of all, the concepts of both properness and determinacy have been around for several decades and it is a priori interesting to see if they have anything in common. But there are practical reasons as well. Under suitable determinacy assumptions every forcing P with a game ideal I attached to it satisfies a dichotomy: every projective set of reals has either a Borel Ipositive subset or a coanalytic I-small superset–Lemma 4.1. Such a dichotomy simplifies the treatment of the countable support iteration of the poset P and the statement of the absoluteness theorems in [7]. Such a dichotomy also means that all intermediate forcing extensions within the P -extension are c.c.c. [8]

Let us now describe the results of the paper. The creature technology is quite complex and it is difficult–indeed self-defeating–to treat it in its full generality. In the language of [4] we will deal with partial orders given by suitably definable tree-creating pairs of countable character whose subcomposition operation is trivial, with no glueing. The information carried by such pairs can be coded into a simple norm, a Borel function whose domain is the set of all creatures of the form ⟨t, X⟩ where t ∈ ω^{<ω} is a sequence and X is a set of its one-step extensions. The values of the function are nonnegative real numbers. A simple norm gives rise to several forcing notions, among them

ℚ_{0} This is the partial order of all trees T ⊂ ω^{<ω} such that for every natural number n and a node s ∈ T there is a longer node t ∈ T such that norm(t, succ_{T} (t)) > n. The ordering is by inclusion.

ℚ_{1} This is the partial order of all trees T ⊂ ω^{<ω} such that for every path x ∈ [T] the limes inferior of the numbers norm(x ↾ n, succ_{T} (x ↾ n)) : n ∈ ω is infinity. The ordering is again by inclusion.

Of course these forcings depend on the choice of the norm, but in this paper all theorems are stated for the general case of an arbitrary simple norm, and we will not mention the dependence. There are many standard notions of forcing that can be obtained in this way: Sacks, Miller and Laver forcing, P T_{fg} of [6] 7.3.3, the LT forcings of [5] and others.

Example 1.5. Let norm(t, X) be the length of the sequence t if X is infinite and norm(t, X) = 0 otherwise. Then ℚ_{0} is the Miller forcing and ℚ_{1} is the Laver forcing.

The exact syntactical complexity of the norm is not critical as long as it is a projective function. For norms more complex than Borel we would have to change the wording of our theorems a bit. However, the norms occurring in practice are very simple. Note that in the case of finitely branching trees the norm is actually a hereditarily countable object.

It turns out that under our assumptions the forcings ℚ_{0} are always proper and they carry a particularly simple game. This case is treated in Section 2. The forcings ℚ_{1} do not have to be proper, however the most common way of guaranteeing the properness automatically provides an integer game for them. This is shown in Section 3. In Section 4 we investigate the resulting dichotomies.

The notation of this paper follows the set theoretic standard of [1]. For a tree T ⊂ ω^{<ω} and a node t ∈ T the symbol succ_{T} (t) denotes the set of immediate successors of the node t in the tree T. In forcing, we follow the western convention of writing q ≤ p when q is a condition more informative than p. For forcings ℚ_{0} and ℚ_{1} the symbol ṙ_{gen} stands for the name for the generic function in ω^{ω}, in both cases equal to the intersection of all the trees in the generic filter. The abbreviation LC denotes a use of a suitable large cardinal hypothesis.

2 The ℚ_{0} forcing

For the ℚ_{0} forcing arising from some simple norm, it is natural to consider the collection

Definition 2.1. I_{0} is the collection of all sets A ⊂ ω^{ω} which have an F_{σ}-superset B such that for no tree T ∈ ℚ_{1} we have [T] ⊂ B.

This collection can be restated in terms of an infinite game:

Definition 2.2. Let A ⊂ ω^{ω} be a set. The infinite game G_{0}(A) is played between Adam and Eve. First, Adam plays a sequence t_{0} ∈ ω^{<ω}. After that, stage n of the game proceeds as follows: a sequence t_{n} ∈ ω^{<ω} is given and Adam plays one by one some of its one step extensions (beginning a construction of a creature of norm ≥ n). The stage n ends when (and if) Eve accepts one of these extensions, after which Adam extends it further in an arbitrary way to a sequence t_{n+1} ∈ ω^{<ω}. Adam wins if either at some stage n Eve did not accept any of his extensions of the sequence t_{n} and the creature he constructed has norm ≥ n, or else ⋃_{n} t_{n} ∈ A.

And the following is the key fact:

Lemma 2.3. 1. Adam has a winning strategy in the game G_{0}(A) if and only if for some tree T ∈ ℚ_{0} it is the case that [T] ⊂ A.

2. I_{0} is the collection of those sets A ⊂ ω^{ω} for which Eve has a winning strategy in the game G_{0}(A).

3. I_{0} is a σ-ideal and ℚ_{0} is forcing equivalent to the algebra of Borel I_{0}- positive sets ordered by inclusion.

Proof. The first item is almost trivial. Suppose that Adam has a winning strategy in the game G_{0}(A). Then the initial segment closure of the set of all sequences that can possibly come up in a play following the strategy, is some tree T, and it is not difficult to see that T ∈ ℚ_{0} and [T] ⊂ A. On the other hand, if for some tree T ∈ ℚ_{0} we have [T] ⊂ A, then Adam can win the game G(A) by playing only the nodes that occur on the tree T. The reader can easily complete the standard argument.

For the second item, it is now clear from (1) and Borel determinacy that if A ∈ I_{0} then Eve has a winning strategy in the game G_{0}(A). For the converse, suppose that Eve has a winning strategy σ in the game G_{0}(A) and fix some notation: given a partial run v of the game which ends with Eve accepting some sequence t_{v} at a stage n_{v}, let T_{v} = {t ∈ ω^{<ω} : no intermediate node t_{v} ⊂ s ⊆ t can be accepted by Eve in some run of the game G_{0} extending v and respecting the strategy σ}. It is not difficult to see that except for the initial segments of the sequence t_{v}, the collection T_{v} is closed under initial segment, and no node in it can branch into more than norm = n_{v} + 1 many immediate successors. We will show that A ⊂ ⋃_{v}[T_{v}] and that no tree T ∈ ℚ_{1} has [T] ⊂ ⋃_{v}[T_{v}], concluding the proof of the second item. For the first statement, if r ∉ ⋃_{v}[T_{v}] then it is possible to construct runs 0 = v_{0} ⊂ v_{1} ⊂ … respecting the strategy σ in such a way that t_{v} ⊂ r using the fact that at each stage m of the construction, the real r ∈ ω^{ω} must steer out of the tree T_{v_{m}}. Then ⋃_{m} v_{m} is a run of the game G_{0} according to the winning strategy σ resulting in the real r, meaning that r ∉ A. For the second statement, choose a tree T ∈ ℚ_{0}. Enumerate all partial runs respecting the strategy σ by v_{m} : m ∈ ω and construct nodes 0 = t_{0} ⊂ t_{1} ⊂ so that the node t_{m+1} branches into more than norm = n_{v_{m}} + 1 many immediate successors and the node t_{m+2} falls out of the tree T_{v_{m}}. Then ⋃_{m} t_{m} is a branch through the tree T which is not in the set ⋃_{v}[T_{v}].

There are now two dual ways to show that the collection I_{0} is a σ-ideal; one uses a fusion argument with the poset ℚ_{0} and the other will combine countably many Eve’s strategies into one. Both of the arguments are rather standard, and one point in this paper is that they are really the same thing. Let us perform the fusion argument. Suppose that A_{n} : n ∈ ω are F_{σ} sets, each of them without a subset of the form [T] where T ∈ ℚ_{0}. Clearly ⋃_{n} A_{n} is a F_{σ} set and it is enough to prove that it does not contain all branches of some ℚ_{0} tree T. Suppose for contradiction it does; then T ⊩ ṙ_{gen} ∈ ⋃_{n} Ȧ_{n} and by thinning out the tree T if necessary we may find a particular number n such that T ⊩ ṙ_{gen} ∈ Ȧ_{n}. Certainly A_{n} is an analytic set and there is a tree U ⊂ (ω ×ω)^{<ω} which projects into A_{n} in all generic extensions, in particular in the ℚ_{0} extension. So there is a name τ for a function in ω^{ω} such that T ⊩ ⟨ṙ_{gen}, τ⟩ is a branch through the tree Ǔ. A standard fusion argument will now yield a condition S ⊂ T in the poset ℚ_{0} such that for every number m the tree S_{m} = {s ∈ S : S ↾ s does not decide the value of τ(m̌)} is wellfounded. This means that for every branch x through the tree S the expression τ/x makes sense, it is a function in ω^{ω} and ⟨x, τ/x⟩ is a branch through the tree U. This is to say that [S] ⊂ A_{n}, contradicting the properties of the set A.

It is now clear that the poset ℚ_{0} is isomorphic to the algebra of I_{0}-positive Borel sets ordered by inclusion: the function π(T) = [T] is an order isomorphism between the poset ℚ_{0} and a dense subset of the algebra.

Thus the poset ℚ_{0} has a game attached to it, namely the game G_{0}, and the corresponding ideal has a basis consisting of F_{σ} sets. This has numerous consequences for the forcing properties of the poset, see for example [8].

Whenever I is a σ-ideal with a basis consisting of F_{σ} sets, then the algebra of I-positive Borel sets is a proper notion of forcing [8]. There are very many such algebras and by far not all of them are forcing equivalent to a poset of the form ℚ_{0}, if only for the reason that closed sets are not dense in them. A simple example is the ideal of meager sets: while the equivalence classes of clopen sets are dense in the factor algebra of Borel sets modulo the meager sets, the closed sets themselves are not dense in the original unfactored algebra of nonmeager Borel sets ordered by inclusion. A somewhat more sophisticated example is provided by the ideal σ-generated by closed measure zero sets. Clearly, no positive Borel measure zero set can have a closed positive subset, and the situation carries over to the factor algebra as well.

3 The ℚ_{1} forcing

Now let us look at the forcing ℚ_{1} arising from some simple norm. It is natural to consider the following object:

Definition 3.1. I_{1} is the collection of all sets A ⊂ ω^{ω} which have a coanalytic superset B ⊂ ω^{ω} such that for no tree T ∈ ℚ_{1} it is the case that [T] ⊂ B.

It is not difficult to express the collection I_{1} in terms of an infinite game:

Definition 3.2. Let A ⊂ ω^{ω} be a set. The infinite game G_{1}(A) between players Adam and Eve is played as follows. First Adam indicates a sequence t_{0} ∈ ω^{<ω}. Then, at stage n of the game a sequence t_{n} will be known, Adam will play a natural number m_{n} and then one-by-one a set of one-step extensions of the sequence t_{n} (beginning a construction of a creature of norm > m_{n} based on t_{n}). The stage n will be finished when (and if) Eve accepts one of these extensions to become t_{n+1}. Adam wins if either at some stage n Eve has not played for infinitely many rounds and the creature Adam constructed at that stage has norm > m_{n}, or else the numbers {m_{n} : n ∈ ω} diverge to infinity and the real ⋃_{n} t_{n} belongs to the set A.

We will use the occassion to fix some notation relevant to the game G_{1}. The real ⋃_{n} t_{n} will be referred to as the outcome of the play. The numbers m_{n} that Adam plays will be called norms. If u ⊂ v are two runs of the game G_{1} then we will say that the run v n-extends the run u if all the norms played on v \ u are greater or equal to n. A good strategy for Eve is one that cannot be defeated by reason of not accepting any node at some stage while Adam constructs a creature of a suitable norm at that stage. Clearly, the set of all good strategies for Eve is a coanalytic set. A play of the game is correct if Eve accepts a node at all the infinitely many stages, and the norms played diverge to infinity.

It is not difficult to verify

Lemma 3.3. 1. Adam has a winning strategy in the game G_{1}(A) if and only if there is a tree T ∈ ℚ_{1} such that [T] ⊂ A.

2. (LC) I_{1} = {A ⊂ ω^{ω} : Eve has a winning strategy in the game G_{1}(A)}.

Proof. The first item is next to trivial. If, on one hand, there is a tree T ∈ ℚ_{1} such that [T] ⊂ A then Adam can win the game G_{1}(A) by simply making sure that t_{n} ∈ T, playing m_{n} = norm(t_{n}, succ_{T} (t_{n})), and on the n-th stage simply enumerating all the immediate successors of the node t_{n} in the tree T. On the other hand, Adam has a winning strategy σ in the game G_{1}(A) then the tree T of all nodes that can occur as some t_{n} in some run of the game observing the strategy σ, is an element of the poset ℚ_{1} such that [T] ⊂ A, as the reader can easily verify.

For the second item, first prove the right-to-left inclusion. Suppose σ is Eve’s winning strategy in the game G_{1}(A). Then the set A is included in the coanalytic set B = ω^{ω}\the set of all outcomes of the correct plays which observe the strategy σ. The strategy σ is still winning for Eve in the game G_{1}(B), and by the first item the set B does not have a subset of the form [T] for a tree T ∈ ℚ_{1}. Thus A ∈ I_{1}. For the other inclusion, suppose that A ∈ I_{1} is a set. This means that A is a subset of a coanalytic set B without a ℚ_{1}-tree in it. By the analytic determinacy and the first item, Eve has a winning strategy in the game G_{1}(B), which is of course winning even in the game G_{1}(A).

Comparing the situation with the parallel development in the previous section, now it would be natural to prove that I_{1} is a σ-ideal; then, as in Lemma 2.3(3), the poset ℚ_{1} will be forcing equivalent to the algebra of I_{1}-positive Borel sets ordered by inclusion and G_{1} will be the game attached to the forcing P_{1}. However, here the situation is complicated by the fact that the collection I_{1} is not necessarily a σ-ideal, a problem that is connected with the possibility that the poset ℚ_{1} is not proper.

We will prove two implications: “ℚ_{1} has continuous reading of names” implies that “I_{1} is a σ-ideal”, which in turn implies that “ℚ_{1} is proper”. Here, the continuous reading of names is the most common tool to ensure the properness of the forcing ℚ_{1}. Thus we can be satisfied to conclude that for the forcings of the form ℚ_{1} the existence of an attached integer game is tightly connected with properness.

It should be remarked that it is in general impossible to find a basis for the ideal I_{1} consisting of F_{σ} sets. The reason is that for a suitable norm the forcing ℚ_{1} can add a dominating real, and such a real cannot be added by an algebra of Borel I-positive sets ordered by inclusion, where I is an ideal with basis consisting of F_{σ} sets.

Definition 3.4. The forcing ℚ_{1} has continuous reading of names if for every collection {O_{n} : n ∈ ω} of open dense subsets of it and every tree T ∈ ℚ_{1} there is a subtree S ⊂ T in the poset ℚ_{1} such that for every number n the set S_{n} = {t ∈ S : S ↾ t ∉ O_{n}} is wellfounded.

While this notion has not been explicitely defined in print, it has very often been used. Cf. Lemma 2.3.6(2) in [4]. It is not difficult to see that if the poset ℚ_{1} has continuous reading of names then it preserves ℵ_{1} and every real in the extension is an image of the generic real under a continuous function in the ground model–hence the name.

Lemma 3.5. (LC) Suppose that the forcing ℚ_{1} has continuous reading of names. Then I_{1} is a σ-ideal.

Proof. Suppose I_{1} is not a σ-ideal; then there must be I_{1}-small sets A_{n} : n ∈ ω such that ⋃_{n} A_{n} ∉ I. Let B_{n} be coanalytic sets such that A_{n} ⊂ B_{n} and for no tree T ∈ ℚ_{1} and no natural number n, [T] ⊂ B_{n}. Now ⋃_{n} A_{n} ⊂ ⋃_{n} B_{n} and ⋃_{n} B_{n} ∉ I_{1} is a coanalytic set. By the analytic determinacy and the previous lemma, there is a tree T ∈ ℚ_{1} such that [T] ⊂ ⋃_{n} B_{n}. Clearly, T ⊩ ṙ_{gen} ∈ ⋃_{n} Ḃ_{n} and strengthening the tree T if necessary we may assume that there is a specific number n such that T ⊩ ṙ_{gen} ∈ Ḃ_{n}. Let U ⊂ (ω × ω_{1})^{<ω} be a tree whose projection in all ω_{1}-preserving extensions is the set B_{n}. Thus T ⊩ ṙ_{gen} ∈ p[Ǔ] and there must be a ℚ_{1}-name τ for a function from ω to ω_{1} such that T ⊩ ⟨ṙ_{gen}, τ⟩ is a branch through the tree Ǔ. By the continuous reading of names, there is a subtree S ⊂ T in the poset ℚ_{1} such that for every natural number m the subtree S_{m} = {t ∈ S : S ↾ t does not decide the value of τ(m̌)} is wellfounded. This means that for every path x ∈ p[S] the formula τ/x = {⟨m, α⟩ : for some initial segment t ⊂ x with S ↾ t ⊩ τ(m̌) = α̌} defines a total function from ω to ω_{1} and the pair ⟨x, τ/x⟩ constitutes a path through the tree U. This is to say that [S] ⊂ B_{n} contradicting the choice of the set B_{n}.

Note that we have not used anything concerning the definability of the ordering ℚ_{1} in the above proof.

Lemma 3.6. (LC) If I_{1} is a σ-ideal then the forcing ℚ_{1} is proper.

Proof. Suppose that I_{1} is a σ-ideal. Then the poset ℚ_{1} is forcing equivalent to the algebra of Borel I_{1}-positive sets ordered by inclusion, and it is enough to argue for the properness of the algebra. We will prove the following lemma of independent interest:

Claim 3.7. (LC) Let P be a poset adding a real ṙ which is forced to fall out of all ground model coded I_{1}-small sets. Let M be a countable elementary submodel of a large enough structure. For every condition p ∈ P ∩M the set {ṙ/g : g ⊂ P ∩M is an M-generic filter} is I_{1}-positive.

The lemma follows immediately from the claim applied to the special case of the algebra of Borel I_{1} positive sets via Lemma 2.2. of [7]. To prove the claim, fix the poset P and the name ṙ. Choose a measurable cardinal κ > |P | and fix the usual tree U ⊂ (ω ×κ)^{<ω} projecting into the coanalytic set of all good Eve’s strategies for the game G_{1}. Consider another infinite game H with the following rules: player I first indicates a condition p_{0} ∈ P and then produces one-by-one open dense sets O_{n} : n ∈ ω of the poset P and nodes u_{0} ⊂ u_{1} ⊂ … in the tree U. Thus ⋃_{n} u_{n} is a branch through the tree U and its first coordinates constitute a good Eve’s strategy that we will denote by σ. Meanwhile, player II is allowed to tread water–to wait for an arbitrary finite number of rounds before his next move. He produces one-by-one conditions p_{0} ≥ p_{1} ≥ … and partial runs 0 = v_{0} ⊂ v_{1} ⊂ v_{2} ⊂ … of the game G_{1}. Player II wins if the filter g generated by the conditions {p_{n} : n ∈ ω} meets all the sets {O_{n} : n ∈ ω}, the run ⋃_{n} v_{n} is correct, it respects the strategy σ, and it results in the real ṙ/g.

Claim 3.8. Player II has a winning strategy in the game H.

Claim 3.7 follows. Fix Player II’s winning strategy τ, let M be a countable elementary submodel of a large enough structure with τ ∈ M, let p ∈ P ∩ M and consider the set A = {ṙ/g : p ∈ g, g ⊂ P ∩ M is an M-generic filter}. Suppose for contradiction that A ∈ I_{1}; then there must be Eve’s good winning strategy σ in the game G_{1}(A). Let N be an elementary submodel such that M ∩ P(P) = N ∩ P(P) and the ordertype of the set N ∩ κ is ω_{1}; there is such a model due to the measurability of the cardinal κ. The tree U ∩ N still projects into the set of all Eve’s good strategies, in particular, there is a branch through the tree U ∩ N which gives the strategy σ. Now simulate a run of the game H in which player II follows his strategy τ and player I puts p = p_{0} and then enumerates the incriminated branch of the tree U ∩ N and all the open dense subsets of the poset P in the model M. Since Player II’s moves come from the model N and τ ∈ N, player I’s responses come from the model N too (or M, which is the same thing due to the choice of the model N). Let g ⊂ P ∩ M be the filter and let v be the run of the game G_{1} generated by player II’s responses. Clearly, ṙ/g ∈ A and v is a run of the game G_{1}(A) which respects the strategy σ which results in this real–that is, Adam has won. Thus the strategy σ was not winning for Eve, contradiction.

The observation critical for the proof of the claim is that the payoff set of the game H is Borel in the space of all possible runs of the game, therefore the game is determined by [3]. So it is enough to derive a contradiction from the assumption that player I has a winning strategy τ. Player II will construct a counterplay consisting of conditions p_{n} and partial runs v_{n} using the following induction hypothesis:

1. the condition p_{n} and the run v_{n} are played at the same time, p_{n+1} ∈ O_{n}

2. the partial run v_{n} obeys the part of the strategy σ that is known by the time the run v_{n} is played. The run v_{n} ends with Eve accepting some sequence t_{n} and p_{n} ⊩ ť_{n−1} ⊂ ṙ. The run v_{n+1} n-extends the run v_{n}.

3. The condition p_{n} is v_{n}, n-good, meaning that for every good Eve’s strategy σ which can output the run v_{n} there exists a condition q ≤ p_{n} such that q ⊩ there is a complete run of the game G_{1} which n-extends the run v_{n+1}, it is correct, it respects the strategy σ and results in the real ṙ.

The first two items say that if player II can perform the construction, the result will be a run of the game H against the strategy τ in which he wins, contradicting the assumption on the strategy τ. The third item is just an extra induction hypothesis designed so as to make the inductive step possible.

In the beginning, the condition p_{0} is given, and let v_{0} = 0. The induction hypothesis is satisfied. Note that the third item in this case is implied by the assumption that the real ṙ is forced to fall out of all ground model coded I_{1}- small sets. Suppose p_{n}, v_{n} are known. To construct the condition p_{n+1} and the run v_{n+1}, first look at what happens if player II treads water from this point on. Of course, in this way he loses, but the main point is that the strategy τ will have to continue playing, creating Eve’s strategy σ and also, somewhere on the way, the open dense set O_{n} ⊂ P. Since the condition p_{n} ∈ P is v_{n}, n-good, there is a condition q ≤ p_{n} with the properties described in the third item above. Strengthening the condition q if necessary, we may assume that q ∈ O_{n}.

Claim 3.9. There is a partial run w of the game G_{1} which n-extends the run v_{n}, in which Eve uses the strategy σ, at the last move in it she accepts some sequence, and such that the condition q is w, n + 1-good.

This will conclude the inductive step, since player II will be able to play p_{n+1} = q, v_{n+1} = w as soon as the strategy τ reveals the open dense set O_{n} and enough of the strategy σ to see that w is a run in which Eve uses that strategy, and the inductive hypothesis will continue to hold.

Well, suppose that the claim fails. Then for each run w satisfying the assumptions of the claim we can find a strategy σ_{w} for Eve in the game G_{1} showing that the condition q is not w, n + 1-good. This means that q ⊩ ṙ ∈ Ẋ where X = {s ∈ ω^{ω} : there is a complete run n-extending the run v_{n}, respecting the strategy σ, and resulting in the real s; however, for no partial run w satisfying the assumptions of the claim there is a correct complete run n+1-extending the run w which follows the strategy σ_{w} and results in the real s}. The definition of the set X is a mouthful, but it is really a boolean combination of analytic sets. By our large cardinal assumptions, the game G_{1}(X) is determined and either X ∈ I_{1} or [T] ⊂ X for some tree T ∈ ℚ_{1}. The first case is impossible, since q ⊩ ṙ ∈ Ẋ and the real ṙ is forced to fall out of all ground model coded I_{1}-small sets. So we are stuck in the second case. There must be a node in the tree T such that all the norms above that node are ≥ n + 1. There must be a partial run w n-extending the run v_{n+1}, in which Eve follows the strategy σ and in her last move accepts exactly the sequence t. Now clearly Adam can n + 1-extend the run w into a correct complete run against the strategy σ_{w} by playing only nodes of the tree T below t. The result of that run should be a real which is not in the set X by its definition. At the same time, it will be a branch through the tree T and as such it does belong to the set X. Contradiction.

4 The dichotomies

The natural conclusion of the previous sections are the following dichotomies. Consult [7] for the definition of I-perfect sets and iterated Fubini power I^{α} for σ-ideals I on the reals.

Lemma 4.1. (LC) Suppose that P is a proper forcing with an integer game attached to it, as witnessed by Borel sets C, D ⊂ ω^{ω}, a Borel function f : C → ℝ and the σ-ideal I. For every universally Baire set A ⊂ ω^{ω},

1. either A has a Borel I-positive subset

2. or A has a coanalytic I-small superset.

For every countable ordinal α and every universally Baire set A ⊂ (ω^{ω})^{α},

1. either A has a Borel I-perfect subset

2. or A is I^{α}-small.

Proof. Suppose that A ⊂ ω^{ω} is universally Baire set. Suitable large cardinal assumptions imply that the integer game with the payoff set D ∪ f^{−1}A is determined. If player I has a winning strategy σ, then the set f′′σ′′ω^{ω} ⊂ A is analytic, it is I-positive since σ remains a winning strategy for player I in the associated game, therefore it has a Borel I-positive subset and we are in the first case of the dichotomy. If on the other hand player II has a winning strategy σ then the set ℝ \ f′′σ′′ω^{ω} ⊃ A is coanalytic and it is in the ideal I since the strategy σ remains a winning strategy for player II in the associated game.

The second dichotomy is proved using the first dichotomy and the results of [7].

Lemma 4.2. (LC) The above dichotomies hold for the forcing ℚ_{0}. Suppose that the forcing ℚ_{1} has continuous reading of names. Then the above dichotomies hold for ℚ_{1} as well.

All similar dichotomies beg a question: what happens in the classical choiceless Solovay model?

Lemma 4.3. (LC) Suppose that the forcing ℚ_{1} has continuous reading of names and κ is an inaccessible cardinal. The above dichotomies hold in the model V (ℝ) ⊂ V [G] for all subsets of ω^{ω} and (ω^{ω})^{α} respectively, whenever G ⊂ Coll(ω, < κ) is a generic filter. The same holds about the forcing ℚ_{0}.

Proof. We will treat the case of the ℚ_{1} forcing, the ℚ_{0} case being much simpler.

Start with the first dichotomy. Suppose that A ∈ V (ℝ) is a subset of ω^{ω}. By a standard argument we may assume that the set A is definable in V (ℝ) from a parameter t in the ground model as A = {r ∈ ω^{ω} : ϕ(r, t)}. Assume that the set A is forced to be I_{1}-positive. Then there must be in V a forcing P of size < κ and a P -name ṙ such that P ⊩“the real ṙ falls out of all the I_{1}-small sets coded in the ground model and Coll(ω, < κ) ⊩ V (ℝ) ⊧ ϕ(ṙ, checkt)”. By essentially Claim 3.7 applied in the model V [G] to the model V instead of the arbitrary countable M, the set B = {r/g : g ⊂ P is V -generic} is I_{1}-positive. It is also a Borel set, and by the choice of the name ṙ and the homogeneity properties of the forcing Coll(ω, < κ), it is also the case that B ⊂ A.

For the second dichotomy assume that α ∈ κ is an ordinal and A ⊂ (ω^{ω})^{α} is a set in V (ℝ). Working in the model V (ℝ), we will show that if the set A is not I_{1}^{α}-small, then it contains an I_{1}-perfect Borel subset. By a standard argument we may assume that α ∈ ω_{1}^{V} and the set A is definable from a parameter t in the ground model V as A = {r⃗ ∈ (ω^{ω})^{α} : ϕ(r⃗, t)}. Consider the strategy σ for Adam in the transfinite game of length α defining the ideal I_{1}^{α}: the strategy σ applied to a string s⃗ of Eve’s answers gives the set ⋃{X : X ∈ I_{1} coded in the model V [s⃗]. If the set A is not I_{1}^{α}-small, there must be a sequence r⃗ ∈ A which is a legal counterplay against this strategy. This means that back in V there is a poset P of size < κ and a P -name r⃗ for an α-sequence of reals such that P ⊩“for every β ∈ α̌, r⃗(β) ∉ ⋃{X : X ∈ I_{1} coded in the model V [r⃗ ↾ β]}; moreover Coll(ω, < κ) ⊩ ϕ(r⃗, ť)”.

Back to the model V (ℝ). Call a sequence s⃗ ∈ (ω^{ω})^{≤α} P -generic if there is a V -generic filter g ⊂ P such that s⃗ ⊂ r⃗/g. For such a sequence s⃗ and a condition p ∈ P we will say that p is s⃗-good if there is a V -generic filter g ⊂ P containing the condition p such that s⃗ = r⃗/g. The following claim is reminiscent of the classical preservation theorems for countable support iterations. Note that P is a countable set in the model V (ℝ).

Claim 4.4. For every ordinal β ≤ α, for every ordinal γ ∈ β, every Borel I_{1}-perfect set C ⊂ (ω^{ω})^{γ} consisting of P -generic sequences, and every Borel function f : C → P such that for every sequence s⃗ ∈ B the condition f(s⃗) is s⃗- good, there is a Borel I_{1}-perfect set B ⊂ (ω^{ω})^{β} consisting of P -generic sequences such that C = B ↾ γ and for every sequence s⃗ ∈ B the condition f(s⃗ ↾ γ) is s⃗-good.

Once the claim has been proved, we will apply it with β = α and γ = 0 to get a Borel I_{1}-perfect set B ⊂ (ω^{ω})^{α} consisting of P -generic sequences. By a standard argument using the homogeneity of the poset Coll(ω, < κ) we can conclude that B ⊂ A and the second dichotomy follows.

The claim is proved by induction on the ordinal β. First the successor step. Suppose the induction hypothesis holds at β and we want to verify it at β + 1 for some ordinal γ ≤ β, a Borel I_{1}-perfect set C ⊂ (ω^{ω})^{γ} and a Borel function f : C → P. Use the induction hypothesis to get a Borel I_{1}-perfect set D ⊂ (ω^{ω})^{β} consisting of P -generic sequences such that C = D ↾ γ and for every sequence s⃗ ∈ D the condition f(s⃗ ↾ γ) is s⃗-good. Now consider the set B = {s⃗ ∈ (ω^{ω})^{β+1} : s⃗ ↾ β ∈ D and s⃗ is a P -generic sequence such that the condition f(s⃗ ↾ γ) is s⃗-good}. The set B is as required; the only thing to verify is that for every sequence s⃗ ∈ D the set {r ∈ ω^{ω} : s^{⌢}r ∈ B} is not in the ideal I_{1}. But this follows essentially from Claim 3.7 applied to the forcing P/s⃗ below the condition f(s⃗ ↾ γ), the name r⃗(β) and the model V [s⃗] in place of the model M. Note that the real r⃗(β) is forced to fall out of all I_{1}-small sets in the model V [r⃗ ↾ β].

For the limit step, suppose that β is a limit of an increasing sequence of ordinals ⟨β_{n} : n ∈ ω⟩, γ ∈ β_{0} is an ordinal and C ⊂ (ω^{ω})^{γ} and f : C → P are objects as in the assumption of the claim. Let ⟨O_{n} : n ∈ ω⟩ be an enumeration of open dense subsets of the poset P in the ground model V, and by use the inductive hypothesis on the ordinals β_{n} repeatedly to construct a sequence ⟨B_{n}, f_{n} : n ∈ ω⟩ such that B_{n} ⊂ (ω^{ω})^{β_{n}} are Borel I_{1}-perfect sets and f_{n} : B_{n} → P are Borel functions such that B_{n−1} = B_{n} ↾ β_{n_{1}} and for every sequence s⃗ ∈ B_{n} the condition f_{n}(s⃗) is s⃗-good, it belongs to the open dense set O_{n} and it is smaller than f_{n−1}(s⃗ ↾ β_{n−1}). Here it is understood that C = B_{−1} and f = f_{−1}. The construction is very easy to perform: at each number n ∈ ω first apply the induction hypothesis at β_{n} to get a set B_{n} as asserted in the Claim, and then for every sequence s⃗ ∈ B_{n} let f_{n}(r⃗) be some condition in the open dense set O_{n} smaller than f_{n−1}(s⃗ ↾ β_{n−1}) which is s⃗-good, say a condition with this property in some fixed enumeration of the poset P. In the end, let B = {s⃗ ∈ (ω^{ω})^{β} : ∀n ∈ ω s⃗ ↾ β_{n} ∈ B_{n}}. It is clear that the set B is Borel I_{1}-perfect. Moreover, every sequence s⃗ ∈ B is P -generic and the condition f(s⃗ ↾ γ) is s⃗-good, as witnessed by the V -generic filter g ⊂ P obtained from the descending sequence ⟨f_{n}(s⃗ ↾ β_{n}) : n ∈ ω⟩ of conditions in the poset P.

References

[1] Thomas Jech. Set Theory. Academic Press, San Diego, 1978.

[2] Alexander Kechris. On a notion of smallness for subsets of the baire space. Transactions of American Mathematical Society, 229:191–207, 1977.

[3] D. Anthony Martin. A purely inductive proof of Borel determinacy, pages 303–308. Number 42 in Proccedings of Symposia in Pure Mathematics. American Mathematical Society, Providence, 1985.

[4] Andrzej Roslanowski and Saharon Shelah. Norms on possibilities i: forcing with trees and creatures. Memoirs of the American Mathematical Society, 141, 1999.

[5] Saharon Shelah. Viva la difference i: Nonisomorphism of ultrapowers of countable models. In Set Theory of the Continuum, volume 26 of Mathematical Sciences Research Institute Publications, pages 357–405. Springer Verlag, 1992.

[6] Tomek Bartoszynski and Haim Judah. Set Theory. On the structure of the real line. A K Peters, Wellesley, MA, 1995.

[7] Jindřich Zapletal. Determinacy and cardinal invariants. 2002.

[8] Jindřich Zapletal. Forcing with ideals of closed sets. Commentationes Mathematicae Universitatis Carolinae, 2002.