Long Games and $\sigma$ -Projective Sets

Juan P. Aguilera Juan P. Aguilera, Department of Mathematics, Ghent University. Krijgslaan 281-S8, 9000 Ghent, Belgium. Institut für diskrete Mathematik und Geometrie, Technische Universität Wien. Wiedner Hauptstrasse 8-10, 1040 Wien, Austria. [email protected] , Sandra Müller Sandra Müller, Institut für Mathematik, Universität Wien. Kolingasse 14-16, 1090 Wien, Austria. [email protected] and Philipp Schlicht Philipp Schlicht, Institut für Mathematik, Universität Wien. Kolingasse 14-16, 1090 Wien, Austria School of Mathematics, University of Bristol, Fry Building, Woodland Road, Bristol, BS8 1UG, UK [email protected]

Abstract.

We prove a number of results on the determinacy of $\sigma$ -projective sets of reals, i.e., those belonging to the smallest pointclass containing the open sets and closed under complements, countable unions, and projections. We first prove the equivalence between $\sigma$ -projective determinacy and the determinacy of certain classes of games of variable length ${<}\omega^{2}$ (Theorem 2.4). We then give an elementary proof of the determinacy of $\sigma$ -projective sets from optimal large-cardinal hypotheses (Theorem 4.4). Finally, we show how to generalize the proof to obtain proofs of the determinacy of $\sigma$ -projective games of a given countable length and of games with payoff in the smallest $\sigma$ -algebra containing the projective sets, from corresponding assumptions (Theorems 5.1 and 5.4).

Key words and phrases:

Infinite Game, Determinacy, Inner Model Theory, Large Cardinal, Long Game, Mouse

2010 Mathematics Subject Classification:

03E60, 03E45, 03E15, 03E30, 03E55

1. Introduction

Let $\omega^{\omega}$ denote the space of infinite sequences of natural numbers with the product topology, i.e., the topology generated by basic (cl)open sets of the form

O(s)=\{x\in\omega^{\omega}:\text{ $x$ extends $s$}\},

where $s\in\omega^{<\omega}$ . As usual, we will refer to the elements of $\omega^{\omega}$ as reals. Given a subset $A$ of $\omega^{\omega}$ , the payoff set, we consider the Gale-Stewart game $G$ of length $\omega$ as follows:

$\mathrm{I}$	$x_{0}$		$x_{2}$		$\dots$
$\mathrm{II}$		$x_{1}$		$x_{3}$		$\dots$

for $x_{0},x_{1},\ldots\in\omega$ .

Two players, I and II, alternate turns playing $x_{0},x_{1},\ldots\in\omega$ to produce an element $x=(x_{0},x_{1},\dots)$ of $\omega^{\omega}$ . Player I wins if and only if $x\in A$ ; otherwise, Player II wins. One can likewise define longer games by considering subsets of $\omega^{\alpha}$ , where $\alpha$ is a countable ordinal. If so, we will again regard $\omega^{\alpha}$ as a product of discrete spaces. A game is determined if one of players I and II has a winning strategy. A set $A\subset\omega^{\omega}$ is said to be determined if the corresponding game is.

These games have been studied extensively; under suitable set-theoretic assumptions, one can prove various classes of them to be determined. One often studies the determinacy of pointclasses given in terms of definability (a general reference is Moschovakis [Mos09]). A pointclass central to this article is the following:

Definition 1.1.

The pointclass of $\sigma$ -projective sets is the smallest pointclass closed under complements, countable unions,¹¹1Of course, one only considers unions of sets in the same space, as is usual. and projections.

In this article, we consider the following classes of games, and their interplay:

(1)

games of fixed countable length $\alpha$ whose payoff is $\sigma$ -projective;
(2)

games of variable length ${<}\alpha+\omega^{2}$ whose payoff is a pointclass containing the clopen sets and contained in the $\sigma$ -projective sets;
(3)

games of countable length $\alpha$ with payoff in other $\sigma$ -algebras.

Neeman extensively studied long games and their connection to large cardinals in [Nee04]. These results are based on his earlier work in [Nee95] and [Nee02] on games of length $\omega$ , where he started connecting moves in long games with moves in iteration games. He showed in [Nee04] for example that the determinacy of games with fixed countable length and analytic payoff set follows from the existence of Woodin cardinals. Moreover, he also analyzed games of continuously coded length (see also [Nee05]) and games of length up to a locally uncountable ordinal. In [Nee07] he even showed determinacy for open games of length $\omega_{1}$ , indeed for a larger class of games of length $\omega_{1}$ , from large cardinals. That the determinacy of arbitrary games of length $\omega_{1}$ is inconsistent is due to Mycielski and has been known for a long time (see [Myc64]).

As for the converse, the determinacy of infinite games implies the existence of inner models with large cardinals (cf. e.g., [Har78, KW10, Tra13, Uhl16, MSW20] and others).

Summary of results

We begin in Section 2 by introducing a class of games of variable length below $\omega^{2}$ . We call these games $\Gamma$ -simple, where $\Gamma$ is a pointclass. We show that $\sigma$ -projective determinacy implies the determinacy of $\Gamma$ -simple games of length $\omega^{2}$ where $\Gamma$ is the pointclass of all $\sigma$ -projective sets. In Section 3 we introduce a class of games we call decoding games. These are used to show that $\sigma$ -projective determinacy follows from simple clopen determinacy of length $\omega^{2}$ . The proof also shows directly that simple $\sigma$ -projective determinacy of length $\omega^{2}$ follows from simple clopen determinacy of length $\omega^{2}$

In Section 4, we prove simple clopen determinacy of length $\omega^{2}$ (and thus $\sigma$ -projective determinacy of length $\omega$ ) from optimal large cardinal assumptions. The proof is level-by-level. An alternative, purely inner-model-theoretic proof of $\sigma$ -projective determinacy can be found [Agu]; our proof, however, requires little inner model theory beyond the definition of the large-cardinal assumption. Roughly, it consists in repeatedly applying a theorem of Neeman [Nee04] to reduce a simple clopen game of length $\omega^{2}$ to an iteration game on an extender model with many partial extenders. The difference here is that players are allowed to drop gratuitously in the iteration game finitely many times to take advantage of the partial extenders in the model.

Finally, in Section 5, we exhibit some additional applications of the proof in Section 4. Specifically we prove from (likely optimal) large cardinal assumptions that $\sigma$ -projective games of length $\omega\cdot\theta$ are determined, where $\theta$ is a countable ordinal. We also prove, from a hypothesis slightly beyond projective determinacy, that games in the smallest $\sigma$ -algebra containing the projective sets are determined.

2. Simple games of length $\omega^{2}$

We begin by noting a result on the determinacy of games of length²²2Here and below, we identify the spaces $\omega^{\omega^{2}}$ , $(\omega^{\omega})^{\omega}$ and $\omega^{\omega\times\omega}$ , as well as $\omega^{\omega\cdot n}$ and $(\omega^{\omega})^{n}$ . ${<}\omega^{2}$ :

Theorem 2.1 (folklore).

The following are equivalent:

(1)

All projective games of length $\omega$ are determined.
(2)

All projective games of length $\omega\cdot n$ are determined, for all $n<\omega$ .
(3)

All clopen³³3In the product topology on $\omega^{\omega\cdot n}$ . games of length $\omega\cdot n$ are determined, for all $n<\omega$ .

Instead of providing a proof of Theorem 2.1, we refer the reader to the proof of Theorem 2.4 below, an easy adaptation of which suffices (cf. Remark 2.5).

Our first result is the analog of Theorem 2.1 for $\sigma$ -projective games. Although the equivalence between the first two items remains true if one replaces “projective” with “ $\sigma$ -projective,” the one between the last two does not. Instead, one needs to consider a larger class of games that are still decided in less than $\omega^{2}$ rounds, in the sense that for any $x\in\omega^{\omega^{2}}$ there is $n\in\omega$ such that for all $y\in\omega^{\omega^{2}}$ , if $y\upharpoonright\omega\cdot n=x\upharpoonright\omega\cdot n$ , then

x\text{ is a winning run for Player I if and only if $y$ is.}

Note that every game of length $\omega\cdot n$ can be seen as a game of this form, for any $n\in\omega$ . For the definition below, we adapt the convention that if $n\in\omega$ , then a subset $A$ of $\omega^{\omega\cdot n}$ can be identified with

\{x\in\omega^{\omega^{2}}:x\upharpoonright\omega\cdot n\in A\}.

Definition 2.2.

Let $\Gamma$ be a collection of subsets of $\omega^{\omega^{2}}$ (each $A\in\Gamma$ identified with a subset of $\omega^{\omega\cdot n}$ for some $n\in\omega$ as above). A game of length $\omega^{2}$ is $\Gamma$ -simple if it is obtained as follows:

(1)

For every $n\in\omega$ , games that are decided after $\omega\cdot n$ moves such that their payoff restricted to sequences of length $\omega\cdot n$ is in $\Gamma$ are $\Gamma$ -simple.
(2)

Let $n\in\omega$ and for each $i\in\omega$ let $G_{i}$ be a $\Gamma$ -simple game. Then the game $G$ obtained as follows is $\Gamma$ -simple: Players I and II take turns playing natural numbers for $\omega\cdot n$ moves, i.e., $n$ rounds in games of length $\omega$ . Afterwards, Player I plays some $i\in\omega$ . Players I and II continue playing according to the rules of $G_{i}$ (keeping the first $\omega\cdot n$ natural numbers they have already played, but not $i$ ).
(3)

Let $n\in\omega$ and for each $i\in\omega$ let $G_{i}$ be a $\Gamma$ -simple game. Then the game $G$ obtained as follows is $\Gamma$ -simple: Players I and II take turns playing natural numbers for $\omega\cdot n$ moves, i.e., $n$ rounds in games of length $\omega$ . Afterwards, Player II plays some $i\in\omega$ . Players I and II continue playing according to the rules of $G_{i}$ (keeping the first $\omega\cdot n$ natural numbers they have already played, but not $i$ ).

We are mainly interested in games of length $\omega^{2}$ which are simple clopen, i.e., which are $\Gamma$ -simple for $\Gamma=\boldsymbol{\Delta}^{0}_{1}$ the collection of clopen sets. Let us start by noting that every simple clopen game has in fact a payoff set which is clopen in $\omega^{\omega\times\omega}$ (this fact will not be needed, but it justifies our terminology).

Lemma 2.3.

Let $G$ be a simple clopen game of length $\omega^{2}$ with payoff set $B$ . Then $B$ is clopen in $\omega^{\omega\times\omega}$ .

Proof.

We prove this by induction on the definition of simple clopen games. In the case that $G$ is a clopen game of fixed length $\omega\cdot n$ it is clear that $B$ is clopen. So suppose that we are given simple clopen games $G_{i}$ , $i<\omega$ with payoff sets $B_{i}$ . Moreover, suppose for notational simplicity that $n=1$ , i.e., the players play one round of length $\omega$ before Player I plays $i\in\omega$ to decide which rules to follow. Inductively, we can assume that every $B_{i}$ is clopen in $\omega^{\omega\times\omega}$ . Let $G$ be the game obtained by applying (2) in Definition 2.2. For $x\in\omega^{\omega\times\omega}$ , write $x^{*}$ for

x\upharpoonright\omega^{\frown}x\upharpoonright[\omega+1,\omega^{2}).

Then $x$ is a winning run for Player I in $G$ iff

\displaystyle x\in\bigcup_{i\in\omega}\left\{y\in\omega^{\omega\times\omega}:y(\omega)=i\wedge y^{*}\in B_{i}\right\}.

Each $B_{i}$ is open, so the payoff set $B$ of $G$ is open. Additionally, $x\in B$ if, and only if,

\displaystyle x\in\bigcap_{i\in\omega}\left\{y\in\omega^{\omega\times\omega}:y(\omega)\neq i\vee y^{*}\in B_{i}\right\}.

Each $B_{i}$ is closed, so $B$ is closed. Therefore, $B$ is clopen.

The argument for applying (3) in Definition 2.2 is analogous. ∎

The main fact about simple clopen games is that their determinacy is already equivalent to determinacy of $\Gamma$ -simple games where $\Gamma$ is the pointclass of all $\sigma$ -projective sets:

Theorem 2.4.

The following are equivalent:

(1)

All $\sigma$ -projective games of length $\omega$ are determined.
(2)

All simple $\sigma$ -projective games of length $\omega^{2}$ are determined.
(3)

All simple clopen games of length $\omega^{2}$ are determined.

The proof of $\sigma$ -projective determinacy of length $\omega$ from simple clopen determinacy, i.e., $(3)\Rightarrow(1)$ , will take place in the next section (Proposition 3.1). For now, we content ourselves with showing that $\sigma$ -projective determinacy of length $\omega$ implies simple clopen determinacy of length $\omega^{2}$ , i.e., $(1)\Rightarrow(3)$ (see Proposition 2.7), although the proof we give easily adapts to show simple $\sigma$ -projective determinacy of length $\omega^{2}$ from the same hypothesis, i.e., $(1)\Rightarrow(2)$ (see Proposition 3.7). Note that $(2)\Rightarrow(3)$ is obvious. It will be convenient for the future to introduce the definition of the game rank of a simple clopen game.

To each simple clopen game $G$ of length $\omega^{2}$ we associate a countable ordinal $\mathrm{gr}(G)$ , the game rank of $G$ , by induction on the definition of simple clopen games. If $G$ is a game of fixed length $\omega\cdot n$ , then $\mathrm{gr}(G)=n$ . If $G$ is obtained from games $G_{0},G_{1},\ldots$ , and from an ordinal $\omega\cdot n$ as in Definition 2.2, we let

\mathrm{gr}(G)=\sup\{\mathrm{gr}(G_{i})+\omega:i\in\omega\}+n.

Remark 2.5.

The proof of Theorem 2.4 is local. We leave the computation of the precise complexity bounds to the curious reader, but we mention that e.g., the proof shows the equivalence among

(1)

the determinacy of games of length $\omega$ which are $\boldsymbol{\Pi}^{1}_{n}$ for some $n\in\omega$ ;
(2)

the determinacy of simple clopen games of length $\omega^{2}$ of rank ${<}\omega$
(3)

the determinacy of simple games of rank ${<}\omega$ which are $\boldsymbol{\Pi}^{1}_{n}$ for some $n\in\omega$ .

Thus, Theorem 2.4 generalizes Theorem 2.1.

The reason why we have chosen to define the game rank this way is that it will make some arguments by induction easier later on. Let us consider some examples: if $\mathrm{gr}(G)=\omega$ , then $G$ is essentially a game in which an infinite collection of games, each of bounded length, are given, and one of the players begins by deciding which one of them they will play. If $\mathrm{gr}(G)=\omega+1$ , then the game is similar, except that the player does not decide which game they will play until the first $\omega$ moves have been played. More generally, a game has limit rank if and only if it begins with one player choosing one among a countably infinite collection of games that can be played.

Remark 2.6.

Let $G$ be a simple clopen game of rank $\alpha$ and $p$ be a partial play of $G$ . Denote by $G_{p}$ the game that results from $G$ after $p$ has been played. Then $G_{p}$ is a simple clopen game of rank $\leq\alpha$ .

Clearly, every simple clopen game has a countable rank. Now we turn to the proof of $(1)\Rightarrow(3)$ in Theorem 2.4.

Proposition 2.7.

Suppose that all $\sigma$ -projective games of length $\omega$ are determined. Then all simple clopen games of length $\omega^{2}$ are determined.

Proof.

Let us say that two games $G$ and $H$ are equivalent if the following hold:

(1)

Player I has a winning strategy in $G$ if and only if she has one in $H$ ; and
(2)

Player II has a winning strategy in $G$ if and only if she has one in $H$ .

We prove the proposition by induction on the game rank of a simple clopen game $G$ . In the case that the game rank is a successor ordinal, we additionally show that the game is equivalent to a $\sigma$ -projective game of length $\omega$ (this is clear in the limit case). Suppose that $\alpha$ is a limit ordinal and this has been shown for games of rank ${<}\alpha$ . Let $\alpha+n$ be the rank of $G$ , where $n\in\omega$ . If $n=0$ , then the result follows easily: by the definition of game rank, the rules of $G$ dictate that one player must begin by choosing one amongst an infinite sequence of games $G^{i}$ . If that player has a winning strategy in any one of them, then choosing that game will guarantee a win in $G$ ; otherwise, the induction hypothesis yields a winning strategy for the other player in each game $G^{i}$ and thus in $G$ .

If $0<n$ , say, $n=k+1$ , then one argues as follows. Given a partial play $p$ of $G$ , we denote by $G_{p}$ the game $G$ after $p$ has been played. Consider the following game, $H$ :

(1)

Players I and II alternate $\omega$ many turns to produce a real number $x$ .

(2)

Afterwards, the game ends. Player I wins if and only if

\exists x_{1}\in\omega^{\omega}\,\forall y_{1}\in\omega^{\omega}\,\exists x_{2}\in\omega^{\omega}\,\ldots\,\forall y_{k}\in\omega^{\omega}

Player I has a winning strategy in

G_{p}

where $p=\langle x,x_{1}*y_{1},\ldots,x_{k}*y_{k}\rangle$ .⁴⁴4Here, $x*y$ denotes the result of facing off the strategies coded by the reals $x$ and $y$ .

Claim 1.

$H$ is equivalent to $G$ .

Granted the claim, it is easy to prove the proposition, for, letting $p$ be as above, the rules of $G_{p}$ dictate that one of the players must choose one amongst an infinite sequence of games $G^{i}$ . Assume without loss of generality that this is Player I. By induction hypothesis, the set of $p$ such that there exists $i$ so that Player I has a winning strategy in $G^{i}$ is $\sigma$ -projective. Hence, the payoff set of $H$ is $\sigma$ -projective, as was to be shown.

It remains to prove the claim. Thus, let $0\leq m\leq k$ and consider the following game $H_{m}$ :

(1)

Players I and II alternate $\omega\cdot(m+1)$ many turns to produce real numbers $z_{0},\ldots,z_{m}$ .
(2)

Afterwards, the game ends. Player I wins if and only if

$\exists x_{m+1}\,\forall y_{m+1}\,\exists x_{m+2}\,\ldots\,\forall y_{k}$ Player I has a winning strategy in the game $G_{p}$ ,

where $p=\langle z_{0},\ldots,z_{m},x_{m+1}*y_{m+1},\ldots,x_{k}*y_{k}\rangle$ .

Thus, $H=H_{0}$ . By induction on $q=k-m$ (i.e., by downward induction on $m$ ), we show that $H_{m}$ is equivalent to $G$ . A simple modification of the argument shows that $(H_{m})_{p}$ is equivalent to $G_{p}$ , for each $p\in(\omega^{\omega})^{l}$ and each $l\leq m+1$ ; this is possible because $G_{p}$ is a simple clopen game of rank $\leq\alpha+n$ . We will use the equivalence between $(H_{m})_{p}$ and $G_{p}$ as part of the induction hypothesis.

We have shown (by the induction hypothesis for the proposition) that $G$ is equivalent to $H_{k}$ . The same argument applied to $G_{p}$ shows that $G_{p}$ is equivalent to $(H_{k})_{p}$ for every $p\in(\omega^{\omega})^{k+1}$ and thus that $G_{p}$ is determined. Moreover, Player I wins a run $p\in(\omega^{\omega})^{m+1}$ of $H_{m}$ if and only if she has a winning strategy in $(H_{m+1})_{p}$ and Player II wins a run $p\in(\omega^{\omega})^{m+1}$ of $H_{m}$ if and only if Player I does not have a winning strategy in $(H_{m+1})_{p}$ ; however, $(H_{m+1})_{p}$ is determined for every $p\in(\omega^{\omega})^{m+1}$ , as it is a $\sigma$ -projective game of length $\omega$ (this follows from an argument as right after the statement of Claim 1). Moreover, the induction hypothesis (for the claim) shows that a player has a winning strategy in $(H_{m+1})_{p}$ if and only if she has one in $G_{p}$ . This shows that a player has a winning strategy in $H_{m}$ if and only if she has one in $G$ , as was to be shown. ∎

3. Decoding games

Our first goal in this section is to prove the following proposition, i.e., $(3)\Rightarrow(1)$ in Theorem 2.4.

Proposition 3.1.

Suppose simple clopen games of length $\omega^{2}$ are determined. Then $\sigma$ -projective games of length $\omega$ are determined.

In order to prove Proposition 3.1, we introduce a representation of $\sigma$ -projective sets.

Definition 3.2.

Fix an enumeration

\{A_{n+1}:n\in\omega\}

of all basic open and basic closed sets in each $(\omega^{\omega})^{k}$ , for $1\leq k<\omega$ . Suppose $A\subset(\omega^{\omega})^{k}$ is $\sigma$ -projective. A $\sigma$ -projective code $[A]$ of $A$ is defined inductively as follows:

(1)

If $A$ is basic open, then $[A]=\langle n\rangle$ , where $A=A_{n}$ .
(2)

If $A$ is basic closed, then $[A]=\langle n\rangle$ , where $A=A_{n}$ .
(3)

If $A=\bigcup_{i}A_{i}$ , then $[A]=\langle[A_{0}],[A_{1}],\ldots\rangle$ .
(4)

If $A=\bigcap_{i}A_{i}$ , then $[A]=\langle 0,[A_{0}],[A_{1}],\ldots\rangle$ .
(5)

If $A=(\omega^{\omega})^{k}\setminus B$ for some $k\in\omega$ , then $[A]=\langle 1,[B]\rangle$ .
(6)

If $A=p[B]$ , then $[A]=\langle 2,[B]\rangle$ .
(7)

If $A=u[B]$ , then $[A]=\langle 3,[B]\rangle$ .

Here, $u[B]$ denotes the dual of the projection,

u[B]=\{x\in\omega^{\omega}:\forall y\,(x,y)\in B\}.

A $\sigma$ -projective code of a given set is not unique. In fact,

Lemma 3.3.

Let $A$ be $\sigma$ -projective.

(1)

$A$ has a $\sigma$ -projective code in which no complements and no basic open sets appear.
(2)

$A$ has a $\sigma$ -projective code in which no complements and no basic closed sets appear.

Proof.

Given a $\sigma$ -projective code for $A$ , one obtains, by a simple application of de Morgan’s laws, a $\sigma$ -projective code in which complements are only applied to basic open sets or to basic closed sets. Since every basic open set is clopen, basic open sets can be replaced by a countable intersection of basic closed sets in the projective code; similarly, basic closed sets can be replaced by a countable union of basic open sets. ∎

Definition 3.4.

Suppose $A\subset(\omega^{\omega})^{n}$ for some $1\leq n<\omega$ is $\sigma$ -projective and fix a code $[A]$ for $A$ . The decoding game for $A$ (with respect to $[A]$ ) is a game of length $\omega^{2}$ according to the following rules: In the first $n$ rounds, which we will call the preparation, Players I and II start by alternating turns playing $\omega\cdot n$ natural numbers to obtain reals $x_{1},x_{2},\ldots,x_{n}\in\omega^{\omega}$ . Afterwards, they proceed according to the $\sigma$ -projective code $[A]$ of $A$ via the following recursive definition:

(1)

If $A$ is basic open, say $A=A_{k}$ , then the game is over, i.e., further moves are not relevant. Player I wins if and only if $(x_{1},x_{2},\ldots,x_{n})\in A_{k}$ .
(2)

If $A$ is basic closed, say $A=A_{k}$ , then the game is over, i.e., further moves are not relevant. Player I wins if and only if $(x_{1},x_{2},\ldots,x_{n})\in A_{k}$ .
(3)

If $A=\bigcup_{i}A_{i}$ , so that $[A]=\langle[A_{0}],[A_{1}],\ldots\rangle$ , then Player I plays some $k\in\omega$ . The game continues from the current play (without the last move, $k$ ) with the rules of the decoding game with respect to $[A_{k}]$ .
(4)

If $A=\bigcap_{i}A_{i}$ , so that $[A]=\langle 0,[A_{0}],[A_{1}],\ldots\rangle$ , then Player II plays some $k\in\omega$ . The game continues from the current play (without the last move, $k$ ) with the rules of the decoding game with respect to $[A_{k}]$ .
(5)

If $A=(\omega^{\omega})^{k}\setminus B$ for some $k\in\omega$ , so that $[A]=\langle 1,[B]\rangle$ , then the game continues from the current play with the rules of the decoding game with respect to $[B]$ , except that the roles of Players I and II are reversed.
(6)

If $A=p[B]$ , so that $[A]=\langle 2,[B]\rangle$ , then Player I plays some $y\in\omega^{\omega}$ in $\omega$ moves of the game, where the moves of Player II are not relevant. The game continues from the current play, together with $y$ , using the rules of the decoding game with respect to $[B]$ .
(7)

If $A=u[B]$ , so that $[A]=\langle 3,[B]\rangle$ , then Player II plays some $y\in\omega^{\omega}$ in $\omega$ moves if the game, where the moves of Player I are not relevant. The game continues from the current play, together with $y$ , using the rules of the decoding game with respect to $[B]$ .

Clause (5) of the preceding definition will not be used below, but we have defined it in the natural way nonetheless.

Lemma 3.5.

Let $A\subset(\omega^{\omega})^{n}$ for some $1\leq n<\omega$ be $\sigma$ -projective and fix a code $[A]$ for $A$ . A player has a winning strategy in the game with payoff set $A$ if and only if the player has a winning strategy in the decoding game for $A$ with respect to $[A]$ .

Proof.

Assume first that Player I has a winning strategy $\sigma$ in the game $G_{A}$ with winning set $A$ . Then the following describes a winning strategy for Player I in the decoding game for $A$ with respect to $[A]$ . In the first $n$ rounds of the game, Player I follows the strategy $\sigma$ . Since $\sigma$ is a winning strategy in $G_{A}$ , the players produce a sequence of reals $(x_{1},\dots,x_{n})\in A$ . In the following rounds, Player I follows the rules of the decoding game according to $[A]$ , playing witnesses to the fact that $(x_{1},\dots,x_{n})\in A$ . This means that, e.g., if $[A]=\langle[A_{0}],[A_{1}],\ldots\rangle$ , i.e., $A=\bigcup_{i}A_{i}$ , then Player I plays $k\in\omega$ such that $(x_{1},\dots,x_{n})\in A_{k}$ . The strategy for the other cases is defined similarly. This yields a winning strategy for Player I in the decoding game for $A$ with respect to $[A]$ .

Now assume that Player I has a payoff strategy $\sigma$ in the decoding game for $A$ with respect to $[A]$ . Then the restriction of $\sigma$ to the first $n$ rounds of the game is a winning strategy for Player I in the game $G_{A}$ . Similarly for Player II. ∎

Lemma 3.6.

Let $A\subset(\omega^{\omega})^{k}$ be $\sigma$ -projective, for some $1\leq k<\omega$ . Then, for every $\sigma$ -projective code $[A]$ for $A$ in which no complements appear, the decoding game given by $[A]$ is simple clopen.

Proof.

Choose a code $[A]$ for $A$ in which no complements appear. We will show by induction on the definition of simple clopen games, that the game obtained as in (6) or (7) in Definition 3.4 is simple clopen again. This will finish the proof as games obtained by clauses (1)-(4) in Definition 3.4 are clearly simple clopen, by the definition of simple clopen games.

Let us introduce some notation for this proof. If $x\in\omega^{\omega}$ , we write $x^{I}$ for the sequence of digits of $x$ in even positions, and $x^{II}$ for the sequence of digits of $x$ in odd positions. Thus, if $x$ results from a run of a Gale-Stewart game, then $x^{I}$ is the sequence of moves of Player I and $x^{II}$ that of Player II.

So let $G$ be a simple clopen game with payoff set $B\subseteq(\omega^{\omega})^{\omega}$ and consider the game $G^{P,k}$ which is defined as follows. Players I and II start by alternating turns playing $\omega\cdot k$ natural numbers to define reals $x_{1},\dots,x_{k}\in\omega^{\omega}$ . Then players I and II alternate moves to play some real $x_{k+1}$ . Finally, Players I and II alternate again to produce reals $z_{1},z_{2},\dots$ so that $(x_{1},\dots,x_{k},x_{k+1}^{I},z_{1},z_{2},\dots)\in(\omega^{\omega})^{\omega}$ and we say that $(x_{1},\dots,x_{k},x_{k+1},z_{1},z_{2},\dots)$ is a winning run for Player I in $G^{P,k}$ iff $(x_{1},\dots,x_{k},x_{k+1}^{\mathrm{I}},z_{1},z_{2},\dots)\in B$ . That means if $B^{*}$ denotes the payoff set of $G^{P,k}$ , we have $(x_{1},\dots,x_{k},x_{k+1},z_{1},z_{2},\dots)\in B^{*}$ iff $(x_{1},\dots,x_{k},x_{k+1}^{\mathrm{I}},z_{1},z_{2},\dots)\in B$ . We aim to show that $G^{P,k}$ is simple clopen again.

Suppose first that $G$ is a clopen game of some fixed length $\omega\cdot n$ , i.e., we consider $G$ as a game of length $\omega^{2}$ but only the first $\omega\cdot n$ moves are relevant for the payoff set. Fix some $k\in\omega$ . In particular, $B$ is a clopen set in $\omega^{\omega\times\omega}$ . We can naturally write $B=B_{0}\times B_{1}\times B_{2}$ for clopen sets $B_{0}\subseteq(\omega^{\omega})^{k}$ , $B_{1}\subseteq\omega^{\omega}$ and $B_{2}\subseteq(\omega^{\omega})^{\omega}$ . By definition, the payoff set for the game $G^{P,k}$ is $B_{0}\times(B_{1})_{\mathrm{I}}\times B_{2}$ , where

(B_{1})_{\mathrm{I}}=\{x\in\omega^{\omega}:x^{\mathrm{I}}\in B_{1}\},

which is clopen. Moreover, in $G^{P,k}$ again only the first $\omega\cdot n$ moves are relevant, so $G^{P,k}$ is a clopen game of fixed length $\omega\cdot n$ and in particular simple clopen.

Now suppose that $G$ is a simple clopen game obtained by condition (2) in Definition 2.2, i.e., we are given simple clopen games $G_{i}$ , $i<\omega$ , and after Player I and II take turns producing $x_{1},\dots,x_{k},x_{k+1}$ , Player I plays some natural number $i$ and the players continue according to the rules of $G_{i}$ (keeping the moves which produced $x_{1},\dots,x_{k},x_{k+1}$ ). That means for every $i<\omega$ , some sequence $(x_{1},\dots,x_{k},x_{k+1},i,z_{1},z_{2},\dots)$ is a winning run for Player I in $G$ iff $(x_{1},\dots,x_{k},x_{k+1},z_{1},z_{2},\dots)$ is a winning run for Player I in $G_{i}$ . We can assume inductively that the games $G^{P,k}_{i}$ for $i<\omega$ (obtained as above) are simple clopen and we aim to show that $G^{P,k}_{i}$ is simple clopen. Consider the simple clopen game $G^{*}$ which is obtained by applying (2) in Definition 2.2 to the games $G^{P,k}_{i}$ and the natural number $k+1$ . Suppose Players I and II produce $(x_{1},\dots,x_{k},x_{k+1},i,z_{1},z_{2},\dots)$ in a run of $G^{*}$ . Then

	$\displaystyle(x_{1},\dots,x_{k},$	$\displaystyle x_{k+1},i,z_{1},z_{2},\dots)\text{ is a winning run for Player I in }G^{*}$
	$\displaystyle\text{ iff }(x_{1},\dots,x_{k},$	$\displaystyle x_{k+1},z_{1},z_{2},\dots)\text{ is a winning run for Player I in }G_{i}^{P,k}$
	$\displaystyle\text{ iff }(x_{1},\dots,x_{k},$	$\displaystyle x_{k+1}^{\mathrm{I}},z_{1},z_{2},\dots)\text{ is a winning run for Player I in }G_{i}$
	$\displaystyle\text{ iff }(x_{1},\dots,x_{k},$	$\displaystyle x_{k+1}^{\mathrm{I}},i,z_{1},z_{2},\dots)\text{ is a winning run for Player I in }G$
	$\displaystyle\text{ iff }(x_{1},\dots,x_{k},$	$\displaystyle x_{k+1},i,z_{1},z_{2},\dots)\text{ is a winning run for Player I in }G^{P,k},$

where the first equivalence holds by definition of $G^{*}$ , the second equivalence holds by inductive hypothesis, the third equivalence by choice of $G$ , and the fourth equivalence by definition of $G^{P,k}$ . Hence $G^{P,k}$ and $G^{*}$ are equal and $G^{P,k}$ is a simple clopen game, as desired.

The argument for simple clopen games obtained by condition (3) in Definition 2.2 is analogous. ∎

With Lemmata 3.5 and 3.6, Proposition 3.1 is proved. To finish the proof of Theorem 2.4 one needs to show the following proposition. This is $(3)\Rightarrow(2)$ and $(1)\Rightarrow(2)$ in Theorem 2.4.

Proposition 3.7.

Suppose either that simple clopen games of length $\omega^{2}$ are determined or that $\sigma$ -projective games of length $\omega$ are determined. Then simple $\sigma$ -projective games of length $\omega^{2}$ are determined.

Proposition 3.7 can be proved directly either by the method of the proof of Proposition 3.1, or by that of Proposition 2.7. In the second case, one need only carry out a straightforward adaptation. In the first case, a simple $\sigma$ -projective game $G$ is reduced to the simple clopen game in which two players play the game $G$ , producing a sequence $x\in(\omega^{\omega})^{n}$ for some $n\in\omega$ such that there is a $\sigma$ -projective set $A\subset(\omega^{\omega})^{n}$ with the property that Player I wins $G$ iff $x\in A$ , no matter how the players continue playing the rest of $G$ . After this, the players play the decoding game for $A$ to determine who the winner is in a clopen way.

We close this section with a useful characterization of the $\sigma$ -projective sets, although it will not be used.

Proposition 3.8 (Folklore).

A set $A\subset\mathbb{R}$ is $\sigma$ -projective if and only if it belongs to $L_{\omega_{1}}(\mathbb{R})$ .

Proof.

Clearly, $L_{\omega_{1}}(\mathbb{R})$ is closed under countable sequences and $\mathcal{P}(\mathbb{R})\cap L_{\omega_{1}}(\mathbb{R})$ is closed under projections.

Conversely, by induction on $\alpha<\omega_{1}$ , one sees that $L_{\alpha}(\mathbb{R})$ and the satisfaction relation for $L_{\alpha}(\mathbb{R})$ are coded by $\sigma$ -projective sets of reals:

(1)

$L_{0}(\mathbb{R})=\mathbb{R}=V_{\omega+1}$ is coded by itself. The satisfaction relation $S_{0}$ for $V_{\omega+1}$ is given by

$S_{0}(\phi,\vec{a})\leftrightarrow V_{\omega+1}\models\phi(\vec{a}),$

for $\phi$ a formula in the language of set theory and $\vec{a}$ a finite sequence of reals. Since every formula in the language of set theory is in the class $\Sigma_{n}$ for some $n$ , $S_{0}$ belongs to the pointclass $\bigcup_{n<\omega}\Sigma^{1}_{n}$ (i.e., the pointclass of countable unions of projective sets) and is thus $\sigma$ -projective.

(2)

Suppose that a $\sigma$ -projective code $C_{\alpha}$ for $L_{\alpha}(\mathbb{R})$ has been defined and that a $\sigma$ -projective satisfaction predicate $S_{\alpha}$ for $L_{\alpha}(\mathbb{R})$ relative to $C_{\alpha}$ has been defined. Suppose that $\vec{a}\in(C_{\alpha})^{n}$ and

\phi=\exists y_{1}\,\forall y_{2},\ldots Qy_{m}\,\phi_{0}(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})

(where $Q$ is a quantifier and $\phi_{0}$ is $\Delta_{0}$ ) is a $\Sigma_{m}$ -formula with $n$ free variables. Then, letting

C^{\phi,\vec{a}}_{\alpha}=\big{\{}x\in\mathbb{R}:\exists y_{1}\in C_{\alpha}\,\forall y_{2}\in C_{\alpha}\,\ldots\,Qy_{m}\in C_{\alpha}\,S_{\alpha}(\phi_{0},\vec{a},y_{1},\ldots,y_{m})\big{\}},

a $\sigma$ -projective code $C_{\alpha+1}$ for $L_{\alpha+1}(\mathbb{R})$ can be defined by the disjointed union

C_{\alpha+1}=C_{\alpha}\,\dot{\cup}\,\{\hat{C}^{\phi,\vec{a}}_{\alpha}:\phi\text{ is a formula and }\vec{a}\in(C_{\alpha})^{n}\},

where $\hat{C}^{\phi,\vec{a}}_{\alpha}$ is a real number coding⁵⁵5E.g., it could be the tuple $(\phi,\vec{a},\alpha)$ . the set $C^{\phi,\vec{a}}_{\alpha}$ . A satisfaction relation $S_{\alpha+1}$ can be defined from this: for atomic formulae, we set

	$\displaystyle S_{\alpha+1}(\cdot\in\cdot,x,y)\leftrightarrow$	$\displaystyle\big{(}x,y\in C_{\alpha}\wedge S_{\alpha}(\cdot\in\cdot,x,y)\big{)}\vee$
		$\displaystyle\big{(}x\in C_{\alpha}\wedge\exists\phi\,\exists\vec{a}\subset(C_{\alpha})^{\text{lth}(a)}\,y=\hat{C}^{\phi,\vec{a}}_{\alpha}\wedge S_{\alpha}(\phi,\vec{a},x)\big{)}.$

For other formulae, this is done as above, so the satisfaction relation $S_{\alpha+1}$ is seen to belong to the pointclass $\bigcup_{n<\omega}\Sigma^{1}_{n}(C_{\alpha+1},S_{\alpha})$ and is thus by using the inductive hypothesis $\sigma$ -projective.

(3)

Suppose that a $\sigma$ -projective code $C_{\alpha}$ for $L_{\alpha}(\mathbb{R})$ has been defined and that a $\sigma$ -projective satisfaction predicate $S_{\alpha}$ for $L_{\alpha}(\mathbb{R})$ has been defined for every $\alpha<\lambda$ , where $\lambda$ is a countable limit ordinal. Then $C_{\lambda}$ can be defined as the disjoint (countable) union of $C_{\alpha+1}\setminus C_{\alpha}$ , for $\alpha<\lambda$ . Thus $C_{\lambda}$ is $\sigma$ -projective. The satisfaction relation $S_{\lambda}$ can be defined as above.

This completes the proof. ∎

4. Determinacy from large cardinals

In this section, we prove level-by-level that the existence of certain iterable inner models with Woodin cardinals implies simple clopen determinacy of length $\omega^{2}$ , which in turn implies $\sigma$ -projective determinacy of length $\omega$ . A different proof of this latter result can be found in [Agu], but the proof we give here has the advantage that it requires almost no inner-model-theoretic background. Another advantage is that it easily generalizes to yield further results (cf. the next section).

The idea of this proof is to enhance a simple clopen game of length $\omega^{2}$ by presenting each player with a fine-structural model that can be manipulated to obtain information about the game. This method of proof is due to Neeman [Nee04]; the difference in our context is that the models considered will contain many partial measures and, in addition to taking iterated ultrapowers, we will allow the players to remove end-segments of their models during the game so as to make the measures total and obtain new information. Although this determinacy proof could have been framed directly in terms of (the decoding game for) $\sigma$ -projective sets, it seems somewhat more natural to consider simple clopen games of length $\omega^{2}$ instead and proceed by induction on the game rank.

Before we start with the proof, let us recall the relevant inner model theoretic notions we will need. In what follows, we will work with premice and formulae in the language of relativized premice $\mathcal{L}_{\mathrm{pm}}=\{\dot{\in},\dot{E},\dot{F},\dot{x}\}$ , where $\dot{E}$ is a predicate for a sequence of extenders, $\dot{F}$ is a predicate for an extender, and $\dot{x}$ is a predicate for a real number over which we construct the premouse.

For some real $x$ , a potential $x$ -premouse is a model $M=(J_{\eta}^{\vec{E}},\in,\vec{E}\upharpoonright\eta,E_{\eta},x),$ where $\vec{E}$ is a fine extender sequence⁶⁶6See Definition $2.4$ in [Ste10], which goes back to Section $1$ in [MS94] and [SSZ02]. and $\eta$ an ordinal or $\eta={\mathrm{Ord}}$ (see Section $2$ in [Ste10] for details). We say that such a potential $x$ -premouse $M$ is active iff $E_{\eta}\neq\emptyset$ . If $\nu\leq\eta$ , we write $M|\nu=(J_{\nu}^{\vec{E}},\in,\vec{E}\upharpoonright\nu,E_{\nu},x)$ for the corresponding initial segment of $M$ . A potential $x$ -premouse $M$ is called an $x$ -premouse if every proper initial segment of $M$ is $\omega$ -sound. If it does not lead to confusion, we will sometimes drop the $x$ and just call $M$ a premouse. Informally, an $x$ -mouse is an iterable $x$ -premouse. We will avoid this term as the notion of iterability is ambiguous, but $\omega_{1}$ -iterability suffices for all our arguments.⁷⁷7We will only need weak iterability, in the sense of [Nee04]. Here we say that an $x$ -premouse $M$ is $\omega_{1}$ -iterable if it is iterable for countable stacks of normal trees of length $<\omega_{1}$ (see Section $4.1$ of [Ste10] for a formal definition).

We consider premice belonging to various smallness classes:

Definition 4.1.

Let $M$ be an $\omega_{1}$ -iterable premouse and $\delta\in M\cap{\mathrm{Ord}}$ .

(1)

We say $M$ is of class $S_{0}$ above $\delta$ if $M$ is a proper class or active.
(2)

We say $M$ is of class $S_{\alpha+1}$ above $\delta$ if there is some ordinal $\delta_{0}>\delta$ and some $N\trianglelefteq M$ with $\delta_{0}<N\cap{\mathrm{Ord}}$ such that $N$ is of class $S_{\alpha}$ above $\delta_{0}$ and $\delta_{0}$ is Woodin in $N$ .
(3)

Let $\lambda$ be a countable limit ordinal. We say $M$ is of class $S_{\lambda}$ above $\delta$ if $\lambda<\omega_{1}^{M}$ and $M$ is of class $S_{\alpha}$ above $\delta$ for all $\alpha<\lambda$ .

Moreover, we say $M$ is of class $S_{\alpha}$ if it is of class $S_{\alpha}$ above $0$ .

Example 4.2.

Let $n\geq 1$ and recall that a premouse $M$ is called $n$ -small if for every $\kappa$ which is a critical point of an extender on the sequence of extenders of $M$ , $M|\kappa\nvDash\text{``there are }n\text{ Woodin cardinals''}$ . Moreover, we say $M$ is $0$ -small if $M$ is an initial segment of $L$ . Let $M_{n}^{\sharp}$ denote the unique countable, sound, $\omega_{1}$ -iterable premouse which is not $n$ -small, but all of whose proper initial segments are $n$ -small, if it exists and is unique. If $M_{n}^{\sharp}$ exists and is unique for all $n\in\omega$ , then – in particular – every $x\in\omega^{\omega}$ has a sharp. Let $N_{\omega}^{\sharp}$ denote the smallest active premouse extending

\bigcup_{n\in\omega}M_{n}^{\sharp}.

Then $N_{\omega}^{\sharp}$ is of class $S_{\omega}$ . If there is a premouse of class $S_{\omega+1}$ , then it contains $N_{\omega}^{\sharp}$ and in fact $N_{\omega}^{\sharp}$ is countable in it.

Note that if $M$ is a premouse of class $S_{\alpha}$ , then $M$ is aware of this, since $\alpha$ is countable in $M$ . If $M$ is of class $S_{\alpha}$ and not a proper class, then $M$ is active and we can obtain a proper class model by iterating the active extender of $M$ and its images out of the universe. By convention, we shall say that this proper class model is also of class $S_{\alpha}$ .

We recall the definition of the game rank of a simple clopen game. If $G$ is a game of fixed length $\omega\cdot n$ , then $\mathrm{gr}(G)=n$ . If $G$ is obtained from games $G_{0},G_{1},\ldots$ , and from an ordinal $\omega\cdot n$ as in Definition 2.2, we let

\mathrm{gr}(G)=\sup\{\mathrm{gr}(G_{i})+\omega:i\in\omega\}+n.

Remark 4.3.

For every simple game $G$ and initial play $p$ of $G$ , let $G_{p}$ denote the rest of the game $G$ after $p$ has been played. Let $p_{0},p_{1},\dots$ be a sequence of initial plays of $G$ starting with the empty sequence $p_{0}=\emptyset$ such that $p_{i+1}$ end-extends $p_{i}$ , and either $\mathrm{gr}(G_{p_{i}})$ is a successor ordinal with $\mathrm{gr}(G_{p_{i}})=\mathrm{gr}(G_{p_{i+1}})+1$ or $\mathrm{gr}(G_{p_{i}})$ is a limit ordinal. Then this sequence has to be of finite length $k+1$ and we can choose $k$ large enough such that $\mathrm{gr}(G_{p_{k}})=1$ .

Theorem 4.4.

Suppose that $\gamma<\omega_{1}$ and for every $y\in\omega^{\omega}$ there is an $x\geq_{T}y$ such that there is a proper class $x$ -premouse of class $S_{\gamma}$ which is a model of ${\sf ZFC}$ . Then every simple clopen game $G$ such that $\mathrm{gr}(G)\leq\gamma$ is determined.

In the proof, we are going to use premice of class $S_{\gamma}$ to apply the following theorem of Neeman multiple times.

Theorem 4.5 (Neeman, Theorem 2A.2 in [Nee04]).

There are binary formulae $\phi_{\mathrm{I}}$ and $\phi_{\mathrm{II}}$ in the language of set theory such that the following hold for any transitive, weakly iterable⁸⁸8As defined in Appendix A, Iterability in [Nee04]. Note that $\omega_{1}$ -iterability implies weak iterability. premouse $M$ which is a model of ${\sf ZFC}$ :

Let $\delta<\omega_{1}$ be a Woodin cardinal in $M$ and let $\dot{A}\in M$ and $\dot{B}\in M$ be $\operatorname{Col}(\omega,\delta)$ -names for a subset of $\omega^{\omega}$ . Then,

(1)

If $M\models\phi_{\mathrm{I}}[\delta,\dot{A}]$ , there is a strategy $\sigma$ for Player I in a game of length $\omega$ such that whenever $x$ is a play by $\sigma$ , there is a non-dropping iterate $N$ of $M$ with embedding $j$ and an $N$ -generic $g\subset\operatorname{Col}(\omega,j(\delta))$ such that $x\in N[g]$ and $x\in j(\dot{A})[g]$ .
(2)

If $M\models\phi_{\mathrm{II}}[\delta,\dot{B}]$ , there is a strategy $\tau$ for Player II in a game of length $\omega$ such that whenever $x$ is a play by $\tau$ , there is a non-dropping iterate $N$ of $M$ with embedding $j$ and an $N$ -generic $g\subset\operatorname{Col}(\omega,j(\delta))$ such that $x\in N[g]$ and $x\in j(\dot{B})[g]$ .
(3)

Otherwise, there is an $M$ -generic $g\subset\operatorname{Col}(\omega,\delta)$ and an $x\in M[g]$ such that $x\not\in\dot{A}[g]$ and $x\not\in\dot{B}[g]$ .

We now proceed to:

Proof of Theorem 4.4.

We may as well assume that $\gamma$ is infinite, since otherwise $G$ has fixed length ${<}\omega^{2}$ , so it is determined by the results of [Nee95] and [Nee02] (see also the introduction of [Nee04]).

Let $G$ be a simple clopen game with $\mathrm{gr}(G)\leq\gamma$ , say $\mathrm{gr}(G)=\alpha$ . We assume that $\alpha$ is a successor ordinal, since the limit case is similar. Let $r\in\omega^{\omega}$ code all parameters used in the definition of $G$ . We may as well assume that $r$ belongs to the Turing cone given by the hypothesis of the theorem.

To each non-terminal play $p$ of $G$ corresponds a game

G_{p}:=\text{ the game $G$ after $p$ has been played.}

Clearly, $G_{p}$ is a simple game and $\mathrm{gr}(G_{p})\leq\alpha$ . Given $y\geq_{T}r$ , a $y$ -premouse $M$ , we select $\delta\in{\mathrm{Ord}}^{M}$ and define formulae $\phi^{p}_{\mathrm{I}}$ and $\phi^{p}_{\mathrm{II}}$ , and two sets $\dot{W}^{p}_{\mathrm{I}}$ and $\dot{W}^{p}_{\mathrm{II}}$ , each of which is either a $\operatorname{Col}(\omega,\delta)$ -name for a set of real numbers or a set of natural numbers. The definition is by induction on $\mathrm{gr}(G_{p})$ (not on $p$ !). Formally, these names and sets of course depend on the model $M$ in which they are defined, so we sometimes write $\dot{W}^{p}_{\mathrm{I}}(M)$ and $\dot{W}^{p}_{\mathrm{II}}(M)$ to make this explicit. But for simplicity and readability we will omit this whenever it does not lead to confusion.

At the same time, we show that there are names, names for names, etc., for these sets such that their interpretation with respect to generics $g_{0},\dots,g_{n}$ for some $n\in\omega$ for collapsing Woodin cardinals of $M$ is a set of the same form with respect to the model $M[g_{0}]\dots[g_{n}]$ instead of $M$ . More precisely, if $M$ is a model as above and $M$ has (at least) $n+1$ Woodin cardinals, then let $\mathbb{P}_{n}=\mathbb{P}(\delta_{0},\dots,\delta_{n})$ be the forcing iteration of length $n+1$ collapsing the ordinals $\delta_{0},\delta_{1},\dots,\delta_{n}$ to $\omega$ one after the other, where $\delta_{0}$ is the least Woodin cardinal in $M$ and $\delta_{i+1}$ is the least Woodin cardinal in $M$ above $\delta_{i}$ for all $0\leq i<n$ , i.e., $\mathbb{P}_{0}=\operatorname{Col}(\omega,\delta_{0})$ and for all $0\leq i<n$ ,

\mathbb{P}_{i+1}=\mathbb{P}_{i}*\operatorname{Col}(\omega,\delta_{i+1})^{\check{}},

where $\operatorname{Col}(\omega,\delta_{i+1})^{\check{}}\in M$ is the canonical $\mathbb{P}_{i}$ -name for $\operatorname{Col}(\omega,\delta_{i+1})$ . This is of course equivalent to the product and to the $\operatorname{Col}(\omega,\delta_{n})$ , but we are interested in the step-by-step collapse.

We consider nice $\mathbb{P}_{n}$ -names $\dot{p}$ for finite sequences of reals with the property that the game rank of $G_{\dot{p}}$ is decided by the empty condition.⁹⁹9Note that the game rank of $G_{p}$ depends only on $G$ and finitely many digits of $p$ . By induction on the game rank of $G_{\dot{p}}$ , we will specify for every $n<\omega$ such that $M$ has at least $n+1$ Woodin cardinals and every such $\mathbb{P}_{n}$ -name $\dot{p}$ , a $\mathbb{P}_{n}$ -name $\dot{B}^{\dot{p},I}_{n}$ in $M$ such that whenever $G$ is $\mathbb{P}_{n}$ -generic over $M$ ,

\dot{B}^{\dot{p},I}_{n}[G]=\dot{W}^{p}_{\mathrm{I}}(M[G]),

where $p=\dot{p}[G]$ . We will call this name $\dot{B}^{\dot{p},I}_{n}$ the good $\mathbb{P}_{n}$ -name for $\dot{W}^{p}_{\mathrm{I}}$ . We will also define analogous names $\dot{B}^{\dot{p},II}$ for $\dot{W}^{p}_{\mathrm{II}}$ . We now proceed to the recursive definition of $\phi^{p}_{\mathrm{I}}$ , $\phi^{p}_{\mathrm{II}}$ , $\dot{W}^{p}_{\mathrm{I}}$ , $\dot{W}^{P}_{\mathrm{II}}$ , $\dot{B}_{n}^{p,I}$ , and $\dot{B}_{n}^{p,II}$ .¹⁰¹⁰10For every $p$ , $\phi^{p}_{\mathrm{I}}$ will be one of three formulae (there is one possibility for the successor case and two for the limit case). We will however use the notation $\phi^{p}_{\mathrm{I}}$ to make the presentation uniform. Similarly for $\phi^{p}_{\mathrm{II}}$ .

Case 1.

$\mathrm{gr}(G_{p})=2$ (this is the base case).

Let $y\geq_{T}r$ and let $M$ be any $y$ -premouse which is a model of ${\sf ZFC}$ and of class $S_{1}$ . Assume without loss of generality that $M$ is minimal, in the sense that no proper initial segment of $M$ is a model of ${\sf ZFC}$ of class $S_{1}$ . Let $\delta$ be the least Woodin cardinal in $M$ , so that $M$ is of class $S_{0}$ above $\delta$ , and let $p\in M$ . We define the $\operatorname{Col}(\omega,\delta)$ -names for sets of reals $\dot{W}^{p}_{\mathrm{I}}$ and $\dot{W}^{p}_{\mathrm{II}}$ by¹¹¹¹11Here and below, all names for real are assumed to be nice.

\dot{W}^{p}_{\mathrm{I}}=\dot{W}^{p}_{\mathrm{I}}(M)=\{(\dot{y},q)\,|\,q\Vdash^{M}_{\operatorname{Col}(\omega,\delta)}\text{ Player I has a winning strategy in }G_{\check{p}^{\frown}\dot{y}}\}

and

\dot{W}^{p}_{\mathrm{II}}=\dot{W}^{p}_{\mathrm{II}}(M)=\{(\dot{y},q)\,|\,q\Vdash^{M}_{\operatorname{Col}(\omega,\delta)}\text{ Player II has a winning strategy in }G_{\check{p}^{\frown}\dot{y}}\}.

Let $\phi^{p}_{\mathrm{I}}$ and $\phi^{p}_{\mathrm{II}}$ be the formulae given by Neeman’s theorem (Theorem 4.5) such that the following hold:

(1)

If $M\models\phi^{p}_{\mathrm{I}}[\dot{W}^{p}_{\mathrm{I}}]$ , there is a strategy $\sigma$ for Player I in a game of length $\omega$ such that whenever $x$ is a play by $\sigma$ , there is an iterate $N$ of $M$ , an elementary embedding $j\colon M\rightarrow N$ and an $N$ -generic $h\subset\operatorname{Col}(\omega,j(\delta))$ such that $x\in N[h]$ and $x\in j(\dot{W}^{p}_{\mathrm{I}})[h]$ .
(2)

If $M\models\phi^{p}_{\mathrm{II}}[\dot{W}^{p}_{\mathrm{II}}]$ , there is a strategy $\tau$ for Player II in a game of length $\omega$ such that whenever $x$ is a play by $\tau$ , there is an iterate $N$ of $M$ , an elementary embedding $j\colon M\rightarrow N$ and an $N$ -generic $h\subset\operatorname{Col}(\omega,j(\delta))$ such that $x\in N[h]$ and $x\in j(\dot{W}^{p}_{\mathrm{II}})[h]$ .
(3)

Otherwise, there is an $M$ -generic $g\subset\operatorname{Col}(\omega,\delta)$ and an $x\in M[g]$ such that $x\not\in\dot{W}^{p}_{\mathrm{I}}[g]$ and $x\not\in\dot{W}^{p}_{\mathrm{II}}[g]$ .

Now, we specify the good $\mathbb{P}_{n}$ -names $\dot{B}^{\dot{p},I}_{n}$ as claimed above, for models with enough Woodin cardinals below $\delta$ so that $\mathbb{P}_{n}$ is defined. For $n=0$ , suppose that $M$ is a premouse with Woodin cardinals $\delta_{0}<\delta$ and is of class $S_{0}$ above $\delta$ and minimal above $\delta$ .¹²¹²12A case of interest will be that of such $M$ which are initial segments of a model $N$ of some class $S_{\beta}$ which is minimal above $\delta_{0}$ . In such an $N$ , $\delta$ need not be a cardinal. Let $\dot{p}$ be a nice $\operatorname{Col}(\omega,\delta_{0})$ -name for a finite sequence of reals and set

\dot{B}^{\dot{p},I}_{0}=\{((\dot{\dot{y}},\dot{q}),q_{0})\,|\,q_{0}\Vdash_{\operatorname{Col}(\omega,\delta_{0})}\dot{q}\Vdash_{\operatorname{Col}(\omega,\delta)^{\check{}}}\text{ Player I has a winning strategy in }G_{\check{\dot{p}}^{\frown}\dot{\dot{y}}}\}.

The good $\mathbb{P}_{n}$ -names $\dot{B}^{\dot{p},I}_{n}$ for $n>0$ and similar names $\dot{B}^{\dot{p},II}_{n}$ for $\dot{W}^{p}_{\mathrm{II}}$ are defined analogously.

Case 2.

$\mathrm{gr}(G_{p})=\gamma+1$ for some $\gamma\geq 2$ .

Let $y\geq_{T}r$ and let $M$ be any $y$ -premouse which is a model of ${\sf ZFC}$ of class $S_{\gamma+1}$ . Assume without loss of generality that $M$ is minimal, in the sense that no proper initial segment of $M$ is a model of ${\sf ZFC}$ of class $S_{\gamma+1}$ . Let $\delta$ be the least Woodin cardinal in $M$ , so that $M$ is of class $S_{\gamma}$ above $\delta$ , and let $p\in M$ . Then let

\dot{W}^{p}_{\mathrm{I}}=\dot{W}^{p}_{\mathrm{I}}(M)=\{(\dot{y},q)\,|\,q\Vdash^{M}_{\operatorname{Col}(\omega)}\phi^{\check{p}^{\frown}\dot{y}}_{\mathrm{I}}[\dot{B}]\},

where $\dot{B}\in M$ is the good $\operatorname{Col}(\omega,\delta)$ -name with respect to $\check{p}^{\frown}\dot{y}$ , so that whenever $G$ is $\operatorname{Col}(\omega,\delta)$ -generic over $M$ , $\dot{B}[G]=\dot{W}^{p^{\frown}y}_{\mathrm{I}}(M[G])$ , where $p^{\frown}y=(\check{p}^{\frown}\dot{y})[G]$ . We also let

\dot{W}^{p}_{\mathrm{II}}=\dot{W}^{p}_{\mathrm{II}}(M)=\{(\dot{y},q)\,|\,q\Vdash^{M}_{\operatorname{Col}(\omega,\delta)}\phi^{\check{p}^{\frown}\dot{y}}_{\mathrm{II}}[\dot{B}]\},

for $\dot{B}$ analogous as above. Note that $\dot{B}$ is a good name for $\dot{W}^{p^{\frown}y}_{\mathrm{I}}$ or $\dot{W}^{p^{\frown}y}_{\mathrm{II}}$ respectively and hence already defined since for every real $y$ , $\mathrm{gr}(G_{p^{\frown}y})=\gamma$ . Let $\phi^{p}_{\mathrm{I}}$ and $\phi^{p}_{\mathrm{II}}$ be the formulae given by Neeman’s theorem (Theorem 4.5) such that the following hold:

(1)

If $M\models\phi^{p}_{\mathrm{I}}[\dot{W}^{p}_{\mathrm{I}}]$ , there is a strategy $\sigma$ for Player I in a game of length $\omega$ such that whenever $x$ is a play by $\sigma$ , there is an iterate $N$ of $M$ , an elementary embedding $j\colon M\rightarrow N$ and an $N$ -generic $h\subset\operatorname{Col}(\omega,j(\delta))$ such that $x\in N[h]$ and $x\in j(\dot{W}^{p}_{\mathrm{I}})[h]$ .
(2)

If $M\models\phi^{p}_{\mathrm{II}}[\dot{W}^{p}_{\mathrm{II}}]$ , there is a strategy $\tau$ for Player II in a game of length $\omega$ such that whenever $x$ is a play by $\tau$ , there is an iterate $N$ of $M$ , an elementary embedding $j\colon M\rightarrow N$ and an $N$ -generic $h\subset\operatorname{Col}(\omega,j(\delta))$ such that $x\in N[h]$ and $x\in j(\dot{W}^{p}_{\mathrm{II}})[h]$ .
(3)

Otherwise, there is an $M$ -generic $g\subset\operatorname{Col}(\omega,\delta)$ and an $x\in M[g]$ such that $x\not\in\dot{W}^{p}_{\mathrm{I}}[g]$ and $x\not\in\dot{W}^{p}_{\mathrm{II}}[g]$ .

Now, we specify the good $\mathbb{P}_{n}$ -names $\dot{B}^{\dot{p},I}_{n}$ . For $n=0$ , suppose $M$ is a premouse with Woodin cardinals $\delta_{0}<\delta$ and that $M$ is of class $S_{\gamma}$ above $\delta$ and minimal above $\delta$ . Let $\dot{p}\in M$ be a nice $\operatorname{Col}(\omega,\delta_{0})$ -name for a finite sequence of reals. Set

\dot{B}^{\dot{p},I}_{0}=\{((\dot{\dot{y}},\dot{q}),q_{0})\,|\,q_{0}\Vdash_{\operatorname{Col}(\omega,\delta_{0})}\dot{q}\Vdash_{\operatorname{Col}(\omega,\delta)^{\check{}}}\phi^{\check{\dot{p}}^{\frown}\dot{\dot{y}}}_{\mathrm{I}}[\dot{B}]\},

where $\dot{B}$ is a good $\mathbb{P}(\delta_{0},\delta)$ -name for $\dot{W}_{\mathrm{I}}^{p}$ . That means $\dot{B}$ is such that whenever $G$ is $\mathbb{P}(\delta_{0},\delta)$ -generic over $M$ , $\dot{B}[G]=\dot{W}^{p^{\frown}y}_{\mathrm{I}}(M[G])$ , where $p^{\frown}y=(\check{\dot{p}}^{\frown}\dot{\dot{y}})[G]$ . The $\mathbb{P}_{n}$ -names $\dot{B}^{\dot{p},I}_{n}$ for $n>0$ and similar names $\dot{B}^{\dot{p},II}_{n}$ for $\dot{W}^{p}_{\mathrm{II}}$ are defined analogously.

Case 3.

$\mathrm{gr}(G_{p})=\lambda$ is a limit ordinal and the rules of $G$ dictate that, after $p$ , it is Player I’s turn.

Let $y\geq_{T}r$ and let $M$ be any $y$ -premouse which is a model of ${\sf ZFC}$ and of class $S_{\lambda}$ . Let $p\in M$ . Then let $\dot{W}^{p}_{\mathrm{I}}=\dot{W}^{p}_{\mathrm{I}}(M)$ be the set of all $k\in\omega$ such that there is an $\eta<M\cap{\mathrm{Ord}}$ such that $M|\eta$ is an active $y$ -premouse of class $S_{\mathrm{gr}(G_{p^{\frown}k})}$ which is minimal, in the sense that no proper initial segment thereof is of class $S_{\mathrm{gr}(G_{p^{\frown}k})}$ , and, if we let $M^{*}$ be the result of iterating the active extender of $M|\eta$ out of the universe, then

M^{*}\models\phi^{p^{\frown}k}_{\mathrm{I}}[\delta^{*},\dot{W}_{\mathrm{I}}^{p^{\frown}k}(M^{*})].

This makes sense because for all $k\in\omega$ , $\mathrm{gr}(G_{p^{\frown}k})<\mathrm{gr}(G_{p})$ , so the set $\dot{W}_{\mathrm{I}}^{p^{\frown}k}(M^{*})$ has been defined for all $M^{*}$ as above. Moreover, $\dot{W}^{p}_{\mathrm{I}}$ belongs to $M$ , since the formulae $\phi^{p^{\frown}k}_{I}(\dot{W}_{\mathrm{I}}^{p^{\frown}k}[M^{*}])$ , together with their parameters $\dot{W}_{\mathrm{I}}^{p^{\frown}k}(M^{*})$ , are definable¹³¹³13Recall that the structure $M$ includes a predicate for its extender sequence. uniformly in $p$ , $\mathrm{gr}(G_{p})$ , and $\eta$ , as can be shown inductively by following this construction and the proof of Theorem 4.5 (cf. the proof of [Nee04, Theorem 1E.1]).

We let $\phi^{p}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{p}(M)]$ be the formula asserting that $\dot{W}^{p}_{\mathrm{I}}$ is non-empty. Similarly, let $\dot{W}^{p}_{\mathrm{II}}=\dot{W}^{p}_{\mathrm{II}}(M)$ be the set of all $k\in\omega$ such that whenever $\eta<M\cap{\mathrm{Ord}}$ is such that $M|\eta$ is an active $y$ -premouse of class $S_{\mathrm{gr}(G_{p^{\frown}k})}$ which is minimal, then

M^{*}\models\phi^{p^{\frown}k}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{p^{\frown}k}(M^{*})],

for $M^{*}$ defined as above. We let $\phi^{p}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{p}(M)]$ be the formula asserting that $\dot{W}^{p}_{\mathrm{II}}$ is equal to $\omega$ . As before, the set $\dot{W}^{p}_{\mathrm{II}}$ belongs to $M$ .

The good $\mathbb{P}_{n}$ -names $\dot{B}^{\dot{p},I}_{n}$ and $\dot{B}^{\dot{p},II}_{n}$ are defined as before, for premice $M$ which are of class $S_{\lambda}$ above finitely many Woodin cardinals.

Case 4.

$\mathrm{gr}(G_{p})=\lambda$ is a limit ordinal and the rules of $G$ dictate that, after $p$ , it is Player II’s turn.

Let $y\geq_{T}r$ and let $M$ be any $y$ -premouse which is a model of ${\sf ZFC}$ and of class $S_{\lambda}$ . Let $p\in M$ . Then let $\dot{W}^{p}_{\mathrm{I}}(M)$ be the set of all $k\in\omega$ such that there is an $\eta<M\cap{\mathrm{Ord}}$ such that $M|\eta$ is an active $y$ -premouse of class $S_{\mathrm{gr}(G_{p^{\frown}k})}$ which is minimal, in the sense that no proper initial segment of $M|\eta$ is of class $S_{\mathrm{gr}(G_{p^{\frown}k})}$ , and, if we again let $M^{*}$ be the result of iterating the active extender of $M|\eta$ out of the universe, then

M^{*}\models\phi^{p^{\frown}k}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{p^{\frown}k}(M^{*})].

Again, $\dot{W}_{\mathrm{I}}^{p}$ is in $M$ . We let $\phi^{p}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{p}(M)]$ be the formula asserting that $\dot{W}^{p}_{\mathrm{I}}$ is equal to $\omega$ . Similarly, let $\dot{W}^{p}_{\mathrm{II}}=\dot{W}^{p}_{\mathrm{II}}(M)$ be the set of all $k\in\omega$ such that whenever $\eta<M\cap{\mathrm{Ord}}$ is such that $M|\eta$ is an active $y$ -premouse of class $S_{\mathrm{gr}(G_{p^{\frown}k})}$ which is minimal, then

M^{*}\models\phi^{p^{\frown}k}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{p^{\frown}k}(M^{*})],

for $M^{*}$ defined as above. We let $\phi^{p}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{p}(M)]$ be the formula asserting that $\dot{W}^{p}_{\mathrm{II}}$ is non-empty.

The good $\mathbb{P}_{n}$ -names $\dot{B}^{\dot{p},I}_{n}$ and $\dot{B}^{\dot{p},II}_{n}$ are defined as before, for premice $M$ which are of class $S_{\lambda}$ above finitely many Woodin cardinals.

This completes the definition of the names $\dot{W}^{p}_{\mathrm{I}}$ , $\dot{W}^{p}_{\mathrm{II}}$ , $\dot{B}^{\dot{p},I}_{n}$ , $\dot{B}^{\dot{p},II}_{n}$ , and the formulae $\phi^{p}_{\mathrm{I}}$ and $\phi^{p}_{\mathrm{II}}$ . Continuing with the proof of Theorem 4.4, we prove a technical claim which shows that these names behave well under elementary embeddings.

Claim 1.

Suppose $\mathrm{gr}(G)$ is a successor ordinal, let $M$ be a proper class premouse which is a model of ${\sf ZFC}$ of class $S_{\mathrm{gr}(G)}$ and minimal, in the sense that no proper initial segment of $M$ is a model of ${\sf ZFC}$ of class $S_{\mathrm{gr}(G)}$ .¹⁴¹⁴14Since $\mathrm{gr}(G)$ is a successor ordinal and $M$ is minimal, $M$ has a Woodin cardinal. Let $j\colon M\rightarrow N$ be an elementary embedding. Let $p\in M$ be a finite sequence of reals in $M$ . Then

j(\dot{W}_{\mathrm{I}}^{p}(M))=\dot{W}_{\mathrm{I}}^{p}(N)

and, analogously,

j(\dot{W}_{\mathrm{II}}^{p}(M))=\dot{W}_{\mathrm{II}}^{p}(N).

Proof.

Let $\delta$ denote the least Woodin cardinal of $M$ . We will in fact show that whenever $\dot{p}\in M$ is a $\mathbb{P}_{n}$ -name for a finite sequence of reals such that $\mathrm{gr}(G_{\dot{p}})$ is decided by the empty condition, we have

j(\dot{B}^{\dot{p},I}_{n})=(\dot{B}^{j(\dot{p}),I}_{n})^{N},

and

j(\dot{B}^{\dot{p},II}_{n})=(\dot{B}^{j(\dot{p}),II}_{n})^{N},

i.e., if $\dot{B}\in M$ is a good $\mathbb{P}_{n}$ -name such that whenever $G$ is $\mathbb{P}_{n}$ -generic over $M$ ,

\dot{B}[G]=\dot{W}_{\mathrm{I}}^{\dot{p}[G]}(M[G]),

then $j(\dot{B})\in N$ is a good $j(\mathbb{P}_{n})$ -name such that whenever $H$ is $j(\mathbb{P}_{n})$ -generic over $N$ ,

j(\dot{B})[H]=\dot{W}_{\mathrm{I}}^{j(\dot{p})[H]}(N[H])

and similarly for $\dot{B}^{\dot{p},II}_{n}$ .

This will yield the claim if applied to $n=0$ , as, by definition,

\dot{W}_{\mathrm{I}}^{p}(M)=\{(\dot{y},q):q\Vdash^{M}_{\operatorname{Col}(\omega,\delta)}\phi^{\check{p}^{\frown}\dot{y}}_{\mathrm{I}}[\dot{B}^{\check{p}^{\frown}\dot{y},I}_{0}]\}.

Hence,

	$\displaystyle j(\dot{W}_{\mathrm{I}}^{p}(M))$	$\displaystyle=\{(\dot{y},q):q\Vdash^{N}_{\operatorname{Col}(\omega,j(\delta))}\phi^{\check{p}^{\frown}\dot{y}}_{\mathrm{I}}[j(\dot{B}^{\check{p}^{\frown}\dot{y},I}_{0})]\}$
		$\displaystyle=\{(\dot{y},q):q\Vdash^{N}_{\operatorname{Col}(\omega,j(\delta))}\phi^{\check{p}^{\frown}\dot{y}}_{\mathrm{I}}[(\dot{B}_{0}^{j(\check{p}^{\frown}\dot{y}),I})^{N}]\}$
		$\displaystyle=\dot{W}_{\mathrm{I}}^{p}(N),$

and similarly for $\dot{B}^{\dot{p},II}_{n}$ .

By the definition of simple games, $\mathrm{gr}(G_{p})$ depends only on $G$ , the length of $p$ , and finitely many values of $p$ (those in which the players determine the subgames played). Thus, if $\dot{p}$ is a $\mathbb{P}_{n}$ -name in $M$ for a finite sequence of reals such that $\Vdash^{M}_{\mathbb{P}_{n}}\mathrm{gr}(G_{\dot{p}})=\gamma+1$ for some countable ordinal $\gamma$ and if $\dot{y}$ is a $\mathbb{P}(\delta_{0},\dots,\delta_{n},\delta)$ -name for a real, then

\Vdash^{M}_{\mathbb{P}(\delta_{0},\dots,\delta_{n},\delta)}\mathrm{gr}(G_{\check{\dot{p}}^{\frown}\dot{y}})=\gamma.

The claim is proved simultaneously for all premice $M$ and all $\dot{p}\in M$ , by induction on the game rank of $\mathrm{gr}(G_{p})$ . We prove it for the names $\dot{B}^{\dot{p},I}_{n}$ for Player I; the other part is similar. We proceed by cases:

First suppose that $\gamma=2$ and let $n<\omega$ and $\dot{p}\in M$ be a $\mathbb{P}_{n}$ -name for a finite sequence of reals such that $\Vdash^{M}_{\mathbb{P}_{n}}\mathrm{gr}(G_{\dot{p}})=2$ . Let $\dot{B}=\dot{B}^{\dot{p},I}_{n}\in M$ , so that whenever $G$ is $\mathbb{P}_{n}$ -generic over $M$ ,

\dot{B}[G]=\dot{W}_{\mathrm{I}}^{\dot{p}[G]}(M[G]).

By definition,

\Vdash^{M}\dots\Vdash\dot{B}=\{(\dot{y},q)\,|\,q\Vdash_{\operatorname{Col}(\omega,\delta)}\text{ Player I has a winning strategy in }G_{\check{\dot{p}}^{\frown}\dot{y}}\}.

By elementarity,

\Vdash^{N}\dots\Vdash j(\dot{B})=\{(\dot{y},q)\,|\,q\Vdash_{\operatorname{Col}(\omega,j(\delta))}\text{ Player I has a winning strategy in }G_{j(\check{\dot{p}})^{\frown}\dot{y}}\}.

But this implies that $j(\dot{B})$ is a good $j(\mathbb{P}_{n})$ -name such that whenever $H$ is $j(\mathbb{P}_{n})$ -generic over $N$ ,

j(\dot{B})[H]=\dot{W}_{\mathrm{I}}^{j(\dot{p})[H]}(N[H]).

This finishes the case $\gamma=2$ .

If $\gamma=\beta+1$ , where $\beta>1$ , let again $n<\omega$ , $\dot{p}\in M$ be a $\mathbb{P}_{n}$ -name for a finite sequence of reals such that $\Vdash^{M}_{\mathbb{P}_{n}}\mathrm{gr}(G_{\dot{p}})=\beta+1$ and let $\dot{B}=\dot{B}^{\dot{p},I}_{n}\in M$ , so that whenever $G$ is $\mathbb{P}_{n}$ -generic over $M$ ,

\dot{B}[G]=\dot{W}_{\mathrm{I}}^{\dot{p}[G]}(M[G]).

This means that

\Vdash^{M}\dots\Vdash\dot{B}=\{(\dot{y},q)\,|\,q\Vdash_{\operatorname{Col}(\omega,\delta)}\phi^{\check{\dot{p}}^{\frown}\dot{y}}_{\mathrm{I}}[\dot{C}]\},

where $\dot{C}\in M$ is a good $\mathbb{P}(\delta_{0},\dots,\delta_{n},\delta)$ -name such that whenever $g$ is $\mathbb{P}(\delta_{0},\dots,\delta_{n},\delta)$ -generic over $M$ ,

\dot{C}[g]=\dot{W}_{\mathrm{I}}^{(\check{\dot{p}}^{\frown}\dot{y})[g]}(M[g]).

By inductive hypothesis, and using that $\Vdash^{M}_{\mathbb{P}(\delta_{0},\dots,\delta_{n},\delta)}\mathrm{gr}(G_{\check{\dot{p}}^{\frown}\dot{y}})=\beta<\mathrm{gr}(G_{\check{\dot{p}}})$ , we have that $j(\dot{C})\in N$ is a good $\mathbb{P}(j(\delta_{0}),\dots,j(\delta_{n}),j(\delta))$ -name such that whenever $h$ is $\mathbb{P}(j(\delta_{0}),\dots,j(\delta_{n}),j(\delta))$ -generic over $N$ ,

j(\dot{C})[h]=\dot{W}_{\mathrm{I}}^{j(\check{\dot{p}}\frown\dot{y})[h]}(N[h]).

Since, by elementarity,

\Vdash^{N}\dots\Vdash j(\dot{B})=\{(\dot{y},q)\,|\,q\Vdash_{\operatorname{Col}(\omega,j(\delta))}\phi^{j(\check{\dot{p}}^{\frown}\dot{y})}_{\mathrm{I}}[j(\dot{C})]\},

it follows that $j(\dot{B})$ is a good $j(\mathbb{P}_{n})$ -name such that for every $j(\mathbb{P}_{n})$ -generic $H$ over $N$ ,

j(\dot{B})[H]=\dot{W}_{\mathrm{I}}^{j(\dot{p})[H]}(N[H]),

as desired.

If $\gamma$ is a limit ordinal, let again $n<\omega$ , $\dot{p}\in M$ be a $\mathbb{P}_{n}$ -name for a finite sequence of reals such that $\Vdash^{M}_{\mathbb{P}_{n}}\mathrm{gr}(G_{\dot{p}})=\gamma$ . Let $\dot{B}=\dot{B}^{\dot{p},I}_{n}\in M$ , so that whenever $G$ is $\mathbb{P}_{n}$ -generic over $M$ ,

\dot{B}[G]=\dot{W}_{\mathrm{I}}^{\dot{p}[G]}(M[G]).

This means that

	$\displaystyle\Vdash^{M}\dots$	$\displaystyle\Vdash\dot{B}=\{k\in\omega\,\|\,\text{there is an initial segment }M^{*}\text{ minimal of class }$
		$\displaystyle S_{\mathrm{gr}(G_{\dot{p}^{\frown}k})}\text{ which satisfies }\phi^{\dot{p}^{\frown}k}_{\mathrm{I}}[\dot{C}]\},$

where $\dot{C}\in M^{*}$ is a good $\mathbb{P}_{n}$ -name such that whenever $g$ is $\mathbb{P}_{n}$ -generic over $M^{*}$ ,

\dot{C}[g]=\dot{W}_{\mathrm{I}}^{(\dot{p}^{\frown}k)[g]}(M^{*}[g]).

By inductive hypothesis, $j(\dot{C})\in N|(j(M^{*})\cap{\mathrm{Ord}})$ is a good $j(\mathbb{P}_{n})$ -name such that whenever $h$ is $j(\mathbb{P}_{n})$ -generic over $N|(j(M^{*})\cap{\mathrm{Ord}})$ ,

j(\dot{C})[h]=\dot{W}_{\mathrm{I}}^{j(\dot{p}^{\frown}k)[h]}(N|(j(M^{*})\cap{\mathrm{Ord}})[h]).

Since, by elementarity,

	$\displaystyle\Vdash^{N}\dots$	$\displaystyle\Vdash j(\dot{B})=\{k\in\omega\,\|\,\text{there is an initial segment }N^{*}\text{ minimal of class }$
		$\displaystyle S_{\mathrm{gr}(G_{\dot{p}^{\frown}k})}\text{ which satisfies }\phi^{j(\dot{p}^{\frown}k)}_{\mathrm{I}}[j(\dot{C})]\},$

it follows that $j(\dot{B})$ is a good $j(\mathbb{P}_{n})$ -name such that for every $j(\mathbb{P}_{n})$ -generic $H$ over $N$ ,

j(\dot{B})[H]=\dot{W}_{\mathrm{I}}^{j(\dot{p})[H]}(N[H]),

as desired.

The argument for $\dot{W}_{\mathrm{II}}^{p}(M)$ is analogous. This completes the proof of the claim. ∎

Now we turn to the proof of the following claim, from which the theorem follows. Recall that $\alpha=\mathrm{gr}(G)$ .

Claim 2.

Let $M$ be an $r$ -premouse which of ${\sf ZFC}$ of class $S_{\alpha}$ but has no proper initial segment of class $S_{\alpha}$ . Let $\delta$ denote the least Woodin cardinal in $M$ . Then

(1)

If $M\models\phi^{\emptyset}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{\emptyset}]$ , then Player I has a winning strategy in $G$ .
(2)

If $M\models\phi^{\emptyset}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{\emptyset}]$ , then Player II has a winning strategy in $G$ .
(3)

$M\models\phi^{\emptyset}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{\emptyset}]\vee\phi^{\emptyset}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{\emptyset}]$ .

Proof.

If $M$ is active, then we may identify it with the proper class sized iterated ultrapower by its top extender and its images, so we may assume that $M$ is a model of ${\sf ZFC}$ . Note that $M$ always has a Woodin cardinal, as $\alpha$ is a successor ordinal. We first prove (3). Suppose that $M\not\models\phi^{\emptyset}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{\emptyset}]$ and $M\not\models\phi^{\emptyset}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{\emptyset}]$ . We inductively construct a run of the game $G$ by its initial segments $p_{m}$ together with reals $y_{m}$ , $y_{m}$ -premice $M^{p_{m}}$ which are proper class models of ${\sf ZFC}$ and ordinals $\delta_{p_{m}}$ . Let $p_{0}$ be the empty play, $y_{0}=r$ , and $M_{0}=M$ . Inductively, suppose that $p_{m}$ , $y_{m}$ , and $M^{p_{m}}$ have been defined and that

M^{p_{m}}\not\models\phi^{p_{m}}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{p_{m}}]\text{ and }M^{p_{m}}\not\models\phi^{p_{m}}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{p_{m}}],

and let $\delta_{p_{m}}$ be the least Woodin cardinal of $M^{p_{m}}$ , if it exists.

If $\mathrm{gr}(G_{p_{m}})=\gamma+1$ is a successor ordinal for some $\gamma\geq 2$ , then, by Neeman’s theorem (Theorem 4.5), there is an $M^{p_{m}}$ -generic $g_{m}\subset\operatorname{Col}(\omega,\delta_{p_{m}})$ and a $y\in M^{p_{m}}[g_{m}]$ such that $y\notin\dot{W}_{\mathrm{I}}^{p_{m}}[g_{m}]$ and $y\notin\dot{W}_{\mathrm{II}}^{p_{m}}[g_{m}]$ . This means that

M^{p_{m}}[g_{m}]\not\models\phi_{\mathrm{I}}^{p_{m}^{\frown}y}[\dot{W}_{\mathrm{I}}^{p_{m}^{\frown}y}]\text{ and }M^{p_{m}}[g_{m}]\not\models\phi_{\mathrm{II}}^{p_{m}^{\frown}y}[\dot{W}_{\mathrm{II}}^{p_{m}^{\frown}y}].

Let $p_{m+1}=p_{m}^{\frown}y$ , $M^{p_{m+1}}=M^{p_{m}}[g_{m}]$ . Here $M^{p_{m}}[g_{m}]$ can be rearranged as a $y_{m+1}$ -premouse for some real $y_{m+1}$ coding $y_{m}$ and $g_{m}$ as $g_{m}$ collapses a cutpoint of the $y_{m}$ -premouse $M^{p_{m}}$ . We will always consider $M^{p_{m+1}}$ as such a $y_{m+1}$ -premouse.

Suppose that $\mathrm{gr}(G_{p_{m}})$ is a limit ordinal and the rules of $G$ dictate that after $p_{m}$ , it is Player I’s turn. By inductive hypothesis we have $M^{p_{m}}\not\models\phi^{p_{m}}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{p_{m}}]$ , so there is no active initial segment $M^{p_{m}}|\nu$ , $\nu\in{\mathrm{Ord}}$ , of $M^{p_{m}}$ of class $S_{\mathrm{gr}(G_{p_{m}^{\frown}k})}$ which is minimal and satisfies $\phi^{p_{m}^{\frown}k}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{p_{m}^{\frown}k}]$ , for any $k\in\omega$ . Moreover, $M^{p_{m}}\not\models\phi^{p_{m}}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{p_{m}}]$ . Hence, there is some $k\in\omega$ and an active initial segment of $M^{p_{m}}$ of class $S_{\mathrm{gr}(G_{p_{m}^{\frown}k})}$ which is minimal and does not satisfy $\phi^{p_{m}^{\frown}k}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{p_{m}^{\frown}k}]$ , where $\delta^{*}$ is defined analogous as above. Fix such a $k$ and such an active initial segment $M^{p_{m}}|\eta$ of $M^{p_{m}}$ and let $M^{p_{m+1}}$ be the proper class model resulting from iterating the active extender of $M^{p_{m}}|\eta$ out of the universe. Set $p_{m+1}=p_{m}^{\frown}k$ and $y_{m+1}=y_{m}$ . Then,

M^{p_{m+1}}\not\models\phi^{p_{m+1}}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{p_{m+1}}]\text{ and }M^{p_{m+1}}\not\models\phi^{p_{m+1}}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{p_{m+1}}].

The case that $\mathrm{gr}(G_{p_{m}})$ is a limit ordinal and the rules of $G$ dictate that it is Player II’s turn after $p_{m}$ is similar.

Finally, suppose that $\mathrm{gr}(G_{p_{m}})=2$ . By Neeman’s theorem (Theorem 4.5), there is some $M^{p_{m}}$ -generic $g_{m}\subset\operatorname{Col}(\omega,\delta_{p_{m}})$ and some $y\in M_{m}[g_{m}]$ such that $y\notin\dot{W}^{p_{m}}_{\mathrm{I}}[g_{m}]$ and $y\notin\dot{W}^{p_{m}}_{\mathrm{II}}[g_{m}]$ . This means that

(1)

$M^{p_{m}}[g_{m}]\models$ “Player I does not have a winning strategy in $G_{p_{m}^{\frown}y}$ ”, and
(2)

$M^{p_{m}}[g_{m}]\models$ “Player II does not have a winning strategy in $G_{p_{m}^{\frown}y}$ ”.

However, $\mathrm{gr}(G_{p_{m}^{\frown}y})=1$ , so $G_{p_{m}^{\frown}y}$ is a clopen game of length $\omega$ . This is a contradiction, as $M^{p_{m}}[g_{m}]$ is a model of ${\sf ZFC}$ , so it certainly satisfies clopen determinacy. This proves (3).

We now prove (1); the proof of (2) is similar.

Let $M$ be as in the statement of the claim and suppose $M\models\phi_{\mathrm{I}}^{\emptyset}[\dot{W}_{\mathrm{I}}^{\emptyset}]$ . We will describe a winning strategy $\sigma$ for Player I in $G$ (in $V$ ) as a concatenation of strategies $\sigma_{m}$ for different rounds of $G$ . Playing against arbitrary moves of Player II, we will for $m\geq 1$ inductively construct plays $p_{m}$ for initial segments of $G$ according to $\sigma$ together with

•

reals $y_{m}$ such that $y_{m+1}\geq_{T}y_{m}$ and $y_{0}=r$ ,
•

$y_{m}$ -premice $M^{p_{m}}$ which are proper class models of ${\sf ZFC}$ of class $S_{\mathrm{gr}(G_{p_{m}})}$ , none of whose initial segments are of class $S_{\mathrm{gr}(G_{p_{m}})}$ , and such that $p_{m}\in M^{p_{m}}$ ,
•

premice $N^{p_{m}}$ together with iteration embeddings $j_{m}\colon M^{p_{m}}\rightarrow N^{p_{m}}$ ,
•

if $M^{p_{m}}$ has a Woodin cardinal and $\delta_{p_{m}}$ is the least Woodin cardinal in $M^{p_{m}}$ , $\operatorname{Col}(\omega,j(\delta_{p_{m}}))$ -generics $g_{p_{m}}$ over $N^{p_{m}}$ .

In case $M^{p_{m}}$ does not have a Woodin cardinal, we will let $g_{p_{m}}$ be undefined and let $M^{p_{m+1}}=N^{p_{m}}$ . In the other case, we let $M^{p_{m+1}}=N^{p_{m}}[g_{p_{m}}]$ . Finally, we will stop the construction after finitely many steps when $\mathrm{gr}(G_{p_{m}})=1$ .

Let $p_{0}$ be the empty play and $M^{p_{0}}=M$ . We will inductively argue that

M^{p_{m}}\models\phi_{\mathrm{I}}^{p_{m}}[\dot{W}_{\mathrm{I}}^{p_{m}}(M^{p_{m}})],

where $\dot{W}_{\mathrm{I}}^{p_{m}}(M^{p_{m}})$ is the $\operatorname{Col}(\omega,\delta_{p_{m}})$ -name or set of natural numbers in $M^{p_{m}}$ defined above.

Assume inductively that $p_{n}$ and $M^{p_{n}}$ with $M^{p_{n}}\models\phi_{\mathrm{I}}^{p_{n}}[\dot{W}_{\mathrm{I}}^{p_{n}}(M^{p_{n}})]$ are already constructed for all $n\leq m$ and that $\mathrm{gr}(G_{p_{m}})\geq 2$ . To construct $p_{m+1}$ and $M^{p_{m+1}}$ we distinguish the following cases.

Assume first that $\mathrm{gr}(G_{p_{m}})=\gamma+1$ for some $\gamma\geq 2$ . Since

M^{p_{m}}\models\phi_{\mathrm{I}}^{p_{m}}[\dot{W}_{\mathrm{I}}^{p_{m}}(M^{p_{m}})],

it follows from Neeman’s theorem (Theorem 4.5) that there is a strategy $\sigma_{m}$ for Player I in a game of length $\omega$ such that whenever $x$ is a play by $\sigma_{m}$ , there is an iterate $N^{p_{m}}$ of $M^{p_{m}}$ , an elementary embedding $j\colon M^{p_{m}}\rightarrow N^{p_{m}}$ and an $N^{p_{m}}$ -generic $h\subset\operatorname{Col}(\omega,j(\delta_{p_{m}}))$ such that $x\in N^{p_{m}}[h]$ and $x\in j(\dot{W}^{p_{m}}_{\mathrm{I}}(M^{p_{m}})[h]$ . Hence, by Claim 1, $x\in\dot{W}^{p_{m}}_{\mathrm{I}}(N^{p_{m}})[h]$ . By definition,

N^{p_{m}}[h]\models\phi_{\mathrm{I}}^{p_{m}^{\frown}x}[\dot{W}^{p_{m}^{\frown}x}_{\mathrm{I}}(N^{p_{m}}[h])].

Let $p_{m+1}=p_{m}^{\frown}x$ , $M^{p_{m+1}}=N^{p_{m}}[h]$ , and $g_{p_{m}}=h$ . Note that $p_{m+1}\in M^{p_{m+1}}$ and as before $N^{p_{m}}[h]$ can be rearranged as a $y_{m+1}$ -premouse for some real $y_{m+1}$ coding $y_{m}$ and $h$ . Again, we will always consider $M^{p_{m+1}}$ as such a $y_{m+1}$ -premouse.

Now suppose that $\mathrm{gr}(G_{p_{m}})=\lambda$ is a limit ordinal and the rules of $G$ dictate that, after $p_{m}$ , it is Player I’s turn. By assumption, $M^{p_{m}}\models\phi_{\mathrm{I}}^{p_{m}}[\dot{W}_{\mathrm{I}}^{p_{m}}(M^{p_{m}})]$ . So

M^{p_{m}}\models\dot{W}_{\mathrm{I}}^{p_{m}}(M^{p_{m}})\neq\emptyset.

Hence, there is a natural number $k$ and an ordinal $\eta$ such that $M^{p_{m}}|\eta$ is an active initial segment of $M^{p_{m}}$ of class $S_{\mathrm{gr}(G_{p_{m}^{\frown}k})}$ and is minimal, and, if we let $N^{p_{m}}$ be the result of iterating the active extender of $M^{p_{m}}|\eta$ out of the universe, then $N^{p_{m}}\models\phi_{\mathrm{I}}^{p_{m}^{\frown}k}[\dot{W}_{\mathrm{I}}^{p_{m}^{\frown}k}(N^{p_{m}})].$ Let $p_{m+1}=p_{m}^{\frown}k$ , $y_{m+1}=y_{m}$ , and $M^{p_{m+1}}=N^{p_{m}}$ . Moreover, let $\sigma_{m}$ be the strategy which tells Player I to play $k$ .

For the other limit case suppose that $\mathrm{gr}(G_{p_{m}})=\lambda$ is a limit ordinal and the rules of $G$ dictate that, after $p_{m}$ , it is Player II’s turn. In this case we can let $\sigma_{m}=\emptyset$ as Player I is not playing, i.e., we only have to react to what Player II is playing in the next round. Suppose that Player II plays some natural number $k$ and let $p_{m+1}=p_{m}^{\frown}k$ . Since $M^{p_{m}}\models\phi_{\mathrm{I}}^{p_{m}}[\dot{W}_{\mathrm{I}}^{p_{m}}(M^{p_{m}})]$ , we have

M^{p_{m}}\models\dot{W}_{\mathrm{I}}^{p_{m}}(M^{p_{m}})=\omega.

In particular, $k\in\dot{W}_{\mathrm{I}}^{p_{m}}(M^{p_{m}})$ . Thus there is an ordinal $\eta$ such that $M^{p_{m}}|\eta$ is an active initial segment of $M^{p_{m}}$ , minimal of class $S_{\mathrm{gr}(G_{p_{m}^{\frown}k})}$ , and if we let $N^{p_{m}}$ denote the result of iterating the active extender of $M^{p_{m}}|\eta$ out of the universe, then $N^{p_{m}}\models\phi_{\mathrm{I}}^{p_{m}^{\frown}k}[\dot{W}_{\mathrm{I}}^{p_{m}^{\frown}k}(N^{p_{m}})].$ Let $M^{p_{m+1}}=N^{p_{m}}$ , and $y_{m+1}=y_{m}$ .

Finally, assume that $\mathrm{gr}(G_{p_{m}})=2$ . Since $M^{p_{m}}\models\phi^{p_{m}}_{\mathrm{I}}[\dot{W}^{p_{m}}_{\mathrm{I}}(M^{p_{m}})]$ , by Neeman’s theorem (Theorem 4.5), there is a strategy $\sigma_{m}$ for Player I in a game of length $\omega$ such that whenever $x$ is a play by $\sigma_{m}$ , there is an iterate $N^{p_{m}}$ of $M^{p_{m}}$ , an elementary embedding $j\colon M^{p_{m}}\rightarrow N^{p_{m}}$ and an $N^{p_{m}}$ -generic $h\subset\operatorname{Col}(\omega,j(\delta_{p_{m}}))$ such that $x\in N[h]$ and $x\in j(\dot{W}^{p_{m}}_{\mathrm{I}}(M^{p_{m}}))[h]$ . Then, by Claim 1, $x\in\dot{W}^{p_{m}}_{\mathrm{I}}(N^{p_{m}}))[h]$ . Therefore,

N^{p_{m}}[h]\models\text{ Player I has a winning strategy in }G_{p_{m}^{\frown}x}.

We let $p_{m+1}=p_{m}^{\frown}x$ and stop the construction. Since $\mathrm{gr}(G_{p_{m}^{\frown}x})=1$ , $G_{p_{m}^{\frown}x}$ is a clopen game of length $\omega$ . As $N^{p_{m}}[h]$ is a proper class model of ${\sf ZFC}$ , we can use absoluteness of winning strategies for clopen games of length $\omega$ to obtain that Player I has a winning strategy in $G_{p_{m}^{\frown}x}$ in $V$ . Let $\sigma_{m+1}$ be a strategy for Player I witnessing this.

This process describes a winning strategy $\sigma$ for Player I in $G$ by concatenating the strategies $\sigma_{i}$ for $1\leq i\leq m+1$ , as desired. ∎

This finishes the proof of Theorem 4.4. ∎

5. Further applications

In this section, we present some additional applications of the proof of Theorem 4.4. Since the proofs are similar, we simply sketch the differences.

5.1. Longer games

We begin by noting that the results presented so far generalize to longer games. In particular:

Theorem 5.1.

Let $\theta$ be a countable ordinal. Suppose that for each $\alpha<\omega_{1}$ and each $y\in\mathbb{R}$ there is some $x\geq_{T}y$ and an $x$ -premouse $M$ of class $S_{\alpha}$ above some $\lambda$ below which there are $\theta$ Woodin cardinals in $M$ . Then $\sigma$ -projective games of length $\omega\cdot\theta$ are determined.

The theorem is a consequence of a more general result akin to Theorem 4.4, namely, the determinacy of simple $\sigma$ -projective games of length $\omega\cdot(\theta+\omega)$ , in the following sense:

Definition 5.2.

Let $\Gamma$ be a collection of subsets of $\omega^{\omega\cdot\theta+\omega^{2}}$ (with each $A\in\Gamma$ identified with a subset of $\omega^{\omega\cdot\theta+\omega\cdot n}$ for some $n\in\omega$ as in Definition 2.2). A game of length $\omega\cdot\theta+\omega^{2}$ is $\Gamma$ -simple if it is obtained as follows:

(1)

For every $n\in\omega$ , games in $\Gamma$ of fixed length $\omega\cdot\theta+\omega\cdot n$ are $\Gamma$ -simple.
(2)

Let $n\in\omega$ and for each $i\in\omega$ let $G_{i}$ be a $\Gamma$ -simple game. Then the game $G$ obtained as follows is $\Gamma$ -simple: Players I and II take turns playing natural numbers for $\omega\cdot\theta+\omega\cdot n$ moves, i.e., $\theta+n$ rounds in games of length $\omega$ . Afterwards, Player I plays some $i\in\omega$ . Players I and II continue playing according to the rules of $G_{i}$ (keeping the first $\omega\cdot\theta+\omega\cdot n$ natural numbers they have already played).
(3)

Let $n\in\omega$ and for each $i\in\omega$ let $G_{i}$ be a $\Gamma$ -simple game. Then the game $G$ obtained as follows is $\Gamma$ -simple: Players I and II take turns playing natural numbers for $\omega\cdot\theta+\omega\cdot n$ moves, i.e., $\theta+n$ rounds in games of length $\omega$ . Afterwards, Player II plays some $i\in\omega$ . Players I and II continue playing according to the rules of $G_{i}$ (keeping the first $\omega\cdot\theta+\omega\cdot n$ natural numbers they have already played).

The notion of game rank in this context is defined as before: if $G$ is a game of fixed length $\omega\cdot\theta+\omega\cdot n$ , then $\mathrm{gr}(G)=n$ . If $G$ is obtained from games $G_{0},G_{1},\ldots$ , and from an ordinal $\omega\cdot\theta+\omega\cdot n$ as in Definition 5.2, we let

\mathrm{gr}(G)=\sup\{\mathrm{gr}(G_{i})+\omega:i\in\omega\}+n.

Theorem 5.3.

Let $\theta$ be a countable ordinal. Suppose that for each $\alpha<\omega_{1}$ and each $y\in\mathbb{R}$ there is some $x\geq_{T}y$ and an $x$ -premouse $M$ of class $S_{\alpha}$ above some $\lambda$ below which there are $\theta$ Woodin cardinals in $M$ . Then, simple $\sigma$ -projective games of length $\omega\cdot(\theta+\omega)$ are determined.

Proof Sketch.

The theorem is proved like Theorem 4.4: first, by arguing as in Proposition 3.7, one sees that is suffices to prove determinacy for simple clopen games of length $\omega\cdot(\theta+\omega)$ . Let $G$ be a game of successor rank $\alpha$ definable from a parameter $x$ . Given $y\geq_{T}x$ and an active $y$ -premouse $M$ of class $S_{\alpha}$ , one defines sets $\dot{W}_{\mathrm{I}}^{p}(M)$ and $\dot{W}_{\mathrm{II}}^{p}(M)$ and formulae $\phi^{p}_{\mathrm{I}}$ and $\phi^{p}_{\mathrm{II}}$ by induction on $\mathrm{gr}(G_{p})$ as in the proof of Theorem 4.4, provided $\mathrm{gr}(G_{p})<\mathrm{gr}(G)$ .

The difference is as follows: in the proof of Theorem 4.4, $\mathrm{gr}(G)=\mathrm{gr}(G_{p})$ occurs when $p=\emptyset$ ; here, it happens when $p$ is a $\theta$ -sequence of reals. Instead of defining $\dot{W}^{p}_{\mathrm{I}}$ in this case, we define only $\dot{W}^{\emptyset}_{\mathrm{I}}$ and $\dot{W}^{\emptyset}_{\mathrm{II}}$ . These are names for sets of $\theta+1$ -sequences of reals and are defined as in Case 2 in the proof of Theorem 4.4; namely,

\dot{W}^{\emptyset}_{\mathrm{I}}=\big{\{}(\dot{p},q)|q\Vdash^{M}_{\operatorname{Col}(\omega,\delta)}\phi^{\dot{p}}_{\mathrm{I}}[\dot{W}^{\dot{p}}_{\mathrm{I}}]\big{\}},

where $\dot{p}$ is a name for a $\theta+1$ -sequence of reals, $\delta$ is the least Woodin cardinal of $M$ above $\lambda$ , and $\delta^{*}$ is the second Woodin cardinal of $M$ above $\lambda$ , if it exists, and $\omega$ , otherwise. (Note that $\delta$ exists since, by assumption, $\alpha$ is a successor ordinal). $\dot{W}^{\emptyset}_{\mathrm{II}}$ is defined similarly. Once these names have been defined, one applies Theorem 2A.2 of [Nee04] (the general version of Theorem 4.5) so that (using the fact that $M$ has $\theta$ Woodin cardinals below $\lambda$ ) one obtains formulae $\phi_{\mathrm{I}}$ and $\phi_{\mathrm{II}}$ with parameters $\dot{W}^{\emptyset}_{\mathrm{I}}$ and $\dot{W}^{\emptyset}_{\mathrm{II}}$ , such that one of the following holds:

(1)

If $M\models\phi_{\mathrm{I}}[\dot{W}^{\emptyset}_{\mathrm{I}}]$ , there is a strategy $\sigma$ for Player I in a game of length $\omega\cdot\theta+\omega$ such that whenever $\vec{x}$ is a play by $\sigma$ , there is a non-dropping iterate $N$ of $M$ with an embedding $j$ and an $N$ -generic $g\subset\operatorname{Col}(\omega,j(\delta))$ such that $\vec{x}\in N[g]$ and $\vec{x}\in j(\dot{W}^{\emptyset}_{\mathrm{I}})[g]$ .
(2)

If $M\models\phi_{\mathrm{II}}[\dot{W}^{\emptyset}_{\mathrm{II}}]$ , there is a strategy $\tau$ for Player II in a game of length $\theta\cdot\omega+\omega$ such that whenever $\vec{x}$ is a play by $\tau$ , there is a non-dropping iterate $N$ of $M$ with an embedding $j$ and an $N$ -generic $g\subset\operatorname{Col}(\omega,j(\delta))$ such that $\vec{x}\in N[g]$ and $\vec{x}\in j(\dot{W}^{\emptyset}_{\mathrm{II}})[g]$ .
(3)

Otherwise, there is an $M$ -generic $g\subset\operatorname{Col}(\omega,\delta)$ and an $\vec{x}\in M[g]$ such that $\vec{x}\not\in\dot{W}^{\emptyset}_{\mathrm{I}}[g]$ and $\vec{x}\not\in\dot{W}^{\emptyset}_{\mathrm{II}}[g]$ .

An argument as in the proof of Theorem 4.4 yields the following claim:

Claim 1.

Let $M$ be an $x$ -premouse and $\lambda\in M$ be an ordinal such that $M$ has $\theta$ Woodin cardinals below $\lambda$ . Suppose that $M$ is of class $S_{\alpha}$ above $\lambda$ and no proper initial segment of $M$ is of class $S_{\alpha}$ above $\lambda$ , where $\alpha$ is a successor ordinal. Let $\delta$ denote the least Woodin cardinal of $M$ above $\lambda$ . Then

(1)

If $M\models\phi^{\emptyset}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{\emptyset}]$ , then Player I has a winning strategy in $G$ .
(2)

If $M\models\phi^{\emptyset}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{\emptyset}]$ , then Player II has a winning strategy in $G$ .
(3)

$M\models\phi^{\emptyset}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{\emptyset}]\vee\phi^{\emptyset}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{\emptyset}]$ .

The theorem is now immediate from the claim. ∎

It seems very likely that the hypotheses of Theorem 5.1 are optimal. However, the proof in [Agu] does not seem to adapt easily to show this.

5.2. $\sigma$ -algebras

The proof of Theorem 4.4 adapts to prove the determinacy of various $\sigma$ -algebras. As an example, we consider the smallest $\sigma$ -algebra containing all projective sets. We show that a sufficient condition for its determinacy is the existence of $x$ -premice of class $S_{\omega+1}$ for every $x\in\mathbb{R}$ .

Theorem 5.4.

Suppose that for each $x\in\omega^{\omega}$ there is an $x$ -premouse of class $S_{\omega+1}$ . Then, every set in the smallest $\sigma$ -algebra on $\omega^{\omega}$ containing the projective sets is determined.

Proof Sketch.

Let $A$ belong to the $\sigma$ -algebra in the statement. Let

\{\boldsymbol{\Sigma}^{0}_{\alpha}(\boldsymbol{\Pi}^{1}_{\omega}):\alpha<\omega_{1}\}

denote the Borel hierarchy built starting from sets which are countable intersections of projective sets, i.e., $\boldsymbol{\Sigma}^{0}_{0}(\boldsymbol{\Pi}^{1}_{\omega})=\boldsymbol{\Pi}^{1}_{\omega}$ consists of all countable intersections of projective sets and $\boldsymbol{\Sigma}^{0}_{\alpha}(\boldsymbol{\Pi}^{1}_{\omega})$ consists of all countable unions of sets each of which is the complement of a set in $\boldsymbol{\Sigma}^{0}_{\beta}(\boldsymbol{\Pi}^{1}_{\omega})$ for some $\beta<\alpha$ . Standard arguments show that these pointclasses constitute a hierarchy of sets in the smallest $\sigma$ -algebra containing the projective sets. It follows that there is $\alpha<\omega_{1}$ and $x\in\omega^{\omega}$ such that $A\in\Sigma^{0}_{\alpha}(\Pi^{1}_{\omega})(x)$ , i.e., such that $A$ belongs to $\boldsymbol{\Sigma}^{0}_{\alpha}(\boldsymbol{\Pi}^{1}_{\omega})$ and that $A$ has a $\sigma$ -projective code (in the sense of Section 3) which is recursive in $x$ .

Let $[A]$ be a $\sigma$ -projective code for $A$ which is recursive in $x$ and in which no complements appear. To show that $A$ is determined, it suffices to show that the decoding game for $[A]$ is determined. Let us denote this game by $G$ . It is a simple clopen game; it is not quite of rank $\omega+1$ , so determinacy does not follow immediately from Theorem 4.4, but it follows from the proof:

Given a partial play $p$ of the game and a model $N$ , we define sets $\dot{W}_{\mathrm{I}}^{p}(N)$ and $\dot{W}_{\mathrm{II}}^{p}(N)$ , formulae $\phi_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{p}(N)]$ and $\phi_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{p}(N)]$ , and names $\dot{B}^{\dot{p},I}_{n}$ and $\dot{B}^{\dot{p},II}_{n}$ as in the proof of Theorem 4.4. The cases where $\mathrm{gr}(G_{p})\leq\omega$ are exactly as in the proof of Theorem 4.4. The remaining cases are very slightly different—for this, let us define the notion of subrank. Recall that $G$ has the following rules:

(1)

Players I and II begin by alternating $\omega$ many rounds to play a real number $y\in\omega^{\omega}$ .
(2)

Afterwards, they alternate a finite amount of turns as follows: letting $[A_{0}]=[A]$ and supposing $[A_{n}]$ has been defined, $[A_{n}]$ is a $\sigma$ -projective code for a union or an intersection of sets, say $\{B_{i}:i\in\omega\}$ , with each $B_{i}$ of smaller (Borel) rank. By the rules of the decoding game, one of the players needs to play a natural number $i$ , thus selecting a $\sigma$ -projective code $[B_{i}]$ for $B_{i}$ ; we let $[A_{n+1}]=[B_{i}]$ .
(3)

Eventually, a stage $n^{*}$ is reached in which $[A_{n^{*}}]$ is a code for a projective set; at this point the players continue with the rules of the decoding game for $[A_{n^{*}}]$ .

Given a play $p$ of $G$ in which a player needs to play a natural number $i$ and $[A_{n}]$ has been defined as above, we say that the game subrank of $G_{p}$ is the least $\gamma$ such that $A_{n}\in\Sigma^{0}_{\gamma}(\Pi^{1}_{\omega})(x)$ or $A_{n}\in\Pi^{0}_{\gamma}(\Sigma^{1}_{\omega})(x)$ .

We now continue the definition of the sets $\dot{W}_{\mathrm{I}}^{p}(N)$ and $\dot{W}_{\mathrm{II}}^{p}(N)$ , formulae $\phi_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{p}(N)]$ and $\phi_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{p}(N)]$ , and names $\dot{B}^{\dot{p},I}_{n}$ and $\dot{B}^{\dot{p},II}_{n}$ . Assume $p$ is such that $\omega<\mathrm{gr}(G_{p})$ , so that the sets have not been defined already; we proceed by induction on the subrank of $G_{p}$ :

Case 5.

The subrank of $G_{p}$ is defined and nonzero and the rules of $G$ dictate that, after $p$ , it is Player I’s turn.

Let $y\geq_{T}x$ and let $M$ be any $y$ -premouse which is a model of ${\sf ZFC}$ and of class $S_{\omega}$ . Let $p\in M$ . Then let $\dot{W}^{p}_{\mathrm{I}}=\dot{W}^{p}_{\mathrm{I}}(M)$ be the set of all $k\in\omega$ such that

M\models\phi^{p^{\frown}k}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{p^{\frown}k}(M)].

This makes sense because for all $k\in\omega$ , the subrank of $G_{p^{\frown}k}$ is smaller than the subrank of $G_{p}$ , so the set $\dot{W}_{\mathrm{I}}^{p^{\frown}k}(M)$ has been defined. Moreover, $\dot{W}^{p}_{\mathrm{I}}$ belongs to $M$ , since $[A]$ is recursive in $x$ and the formulae $\phi^{p^{\frown}k}_{I}(\dot{W}_{\mathrm{I}}^{p^{\frown}k}[M])$ , as well as the sets $\dot{W}_{\mathrm{I}}^{p^{\frown}k}(M)$ , are definable uniformly in $p$ , as can be shown inductively by following this construction and the proof of Theorem 4.5 (cf. the proof of [Nee04, Theorem 1E.1]).

M\models\phi^{p^{\frown}k}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{p^{\frown}k}(M)].

We let $\phi^{p}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{p}(M)]$ be the formula asserting that $\dot{W}^{p}_{\mathrm{II}}$ is equal to $\omega$ . As before, the set $\dot{W}^{p}_{\mathrm{II}}$ belongs to $M$ .

The good $\mathbb{P}_{n}$ -names $\dot{B}^{\dot{p},I}_{n}$ and $\dot{B}^{\dot{p},II}_{n}$ are defined as in the other cases.

Case 6.

The subrank of $G_{p}$ is defined and nonzero and the rules of $G$ dictate that, after $p$ , it is Player II’s turn.

This case is similar to the preceding one.

Case 7.

$p$ is the empty play.

Let $M$ be any $x$ -premouse which is a model of ${\sf ZFC}$ and of class $S_{\omega+1}$ and let $\delta$ be the smallest Woodin cardinal of $M$ . In this case, $\dot{W}^{\emptyset}_{\mathrm{I}}$ is the canonical $\operatorname{Col}(\omega,\delta)$ -name for all reals $p$ such that $\phi^{p}_{I}(\dot{W}_{\mathrm{I}}^{p}[\dot{B}])$ holds, where $\dot{B}\in M$ is a good $\operatorname{Col}(\omega,\delta)$ -name with respect to $\dot{p}$ , so that whenever $G$ is $\operatorname{Col}(\omega,\delta)$ -generic over $M$ , $\dot{B}[G]=\dot{W}^{p}_{\mathrm{I}}(M[G])$ , where $p=\dot{p}[G]$ .

The name $\dot{W}^{\emptyset}_{\mathrm{II}}$ is defined analogously. The formulae $\phi^{\emptyset}_{\mathrm{I}}(\dot{W}^{\emptyset}_{\mathrm{I}})$ and $\phi^{\emptyset}_{\mathrm{II}}(\dot{W}^{\emptyset}_{\mathrm{II}})$ are obtained by applying Neeman’s theorem to $\dot{W}^{\emptyset}_{\mathrm{I}}$ and $\dot{W}^{\emptyset}_{\mathrm{II}}$ .

This completes the definition of the names and formulae. After this, an argument as in the proof of Theorem 4.4 yields the following claim:

Claim 1.

Let $M$ be an $x$ -premouse which is of class $S_{\omega+1}$ but has no proper initial segment of class $S_{\omega+1}$ . Let $\delta$ denote the least Woodin cardinal in $M$ . Then

(1)

If $M\models\phi^{\emptyset}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{\emptyset}]$ , then Player I has a winning strategy in $G$ .
(2)

If $M\models\phi^{\emptyset}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{\emptyset}]$ , then Player II has a winning strategy in $G$ .
(3)

$M\models\phi^{\emptyset}_{\mathrm{I}}[\dot{W}_{\mathrm{I}}^{\emptyset}]\vee\phi^{\emptyset}_{\mathrm{II}}[\dot{W}_{\mathrm{II}}^{\emptyset}]$ .

The theorem is now immediate from the claim. ∎

The following remains an interesting open problem:

Question 5.5.

What is the consistency strength of determinacy for sets in the smallest $\sigma$ -algebra containing the projective sets?

Acknowledgements

The first-listed author was partially suported by FWO grant number 3E017319 and by FWF grant numbers I4427 and I4513-N. The second-listed author, formerly known as Sandra Uhlenbrock, was partially supported by FWF grant number P 28157 and in addition gratefully acknowledges funding from L’ORÉAL Austria, in collaboration with the Austrian UNESCO Commission and in cooperation with the Austrian Academy of Sciences - Fellowship Determinacy and Large Cardinals. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 794020 of the third-listed author (Project IMIC: Inner models and infinite computations). The third-listed author was partially supported by FWF grant number I4039.

References

[Agu] J. P. Aguilera. $\sigma$ -Projective Determinacy. Submitted. Available at https://www.dropbox.com/s/g853hj5ern1kkyb/SPReversal.pdf?dl=0.
[Har78] L. Harrington. Analytic Determinacy and $0^{\#}$ . Journal of Symbolic Logic, 43:685–693, 1978.
[KW10] P. Koellner and W. H. Woodin. Large Cardinals from Determinacy. In M. Foreman and A. Kanamori, editors, Handbook of Set Theory. Springer, 2010.
[Mos09] Y. N. Moschovakis. Descriptive set theory, second edition, volume 155 of Mathematical Surveys and Monographs. AMS, 2009.
[MS94] W. J. Mitchell and J. R. Steel. Fine structure and iteration trees. Lecture notes in logic. Springer-Verlag, Berlin, New York, 1994.
[MSW20] S. Müller, R. Schindler, and W.H. Woodin. Mice with finitely many woodin cardinals from optimal determinacy hypotheses. Journal of Mathematical Logic, 20, 2020.
[Myc64] Jan Mycielski. On the axiom of determinateness. Fundamenta Mathematicae, 53(2):205–224, 1964.
[Nee95] I. Neeman. Optimal Proofs of Determinacy. Bulletin of Symbolic Logic, 1(3):327–339, 09 1995.
[Nee02] I. Neeman. Optimal Proofs of Determinacy II. Journal of Mathematical Logic, 2(2):227–258, 11 2002.
[Nee04] I. Neeman. The Determinacy of Long Games. De Gruyter series in logic and its applications. Walter de Gruyter, 2004.
[Nee05] Itay Neeman. An introduction to proofs of determinacy of long games, pages 43––86. Lecture Notes in Logic. Cambridge University Press, 2005.
[Nee07] Itay Neeman. Games of length $\omega_{1}$ . Journal of Mathematical Logic, 07(01):83–124, 2007.
[SSZ02] R. Schindler, J. R. Steel, and M. Zeman. Deconstructing inner model theory. Journal of Symbolic Logic, 67:721–736, 2002.
[Ste10] J. R. Steel. An Outline of Inner Model Theory. In M. Foreman and A. Kanamori, editors, Handbook of Set Theory. Springer, 2010.
[Tra13] N. D. Trang. Generalized Solovay Measures, the HOD analysis, and the Core Model Induction. 2013. PhD Thesis. UC Berkeley.
[Uhl16] Sandra Uhlenbrock, now Müller. Pure and Hybrid Mice with Finitely Many Woodin Cardinals from Levels of Determinacy. PhD thesis, WWU Münster, 2016.

Long Games and σ\sigma-Projective Sets

Abstract.

Key words and phrases:

2010 Mathematics Subject Classification:

1. Introduction

Definition 1.1.

Summary of results

2. Simple games of length ω2\omega^{2}

Theorem 2.1 (folklore).

Definition 2.2.

Lemma 2.3.

Proof.

Theorem 2.4.

Remark 2.5.

Remark 2.6.

Proposition 2.7.

Proof.

Claim 1.

3. Decoding games

Proposition 3.1.

Definition 3.2.

Lemma 3.3.

Proof.

Definition 3.4.

Lemma 3.5.

Proof.

Lemma 3.6.

Proof.

Proposition 3.7.

Proposition 3.8 (Folklore).

Proof.

4. Determinacy from large cardinals

Definition 4.1.

Example 4.2.

Remark 4.3.

Theorem 4.4.

Theorem 4.5 (Neeman, Theorem 2A.2 in [Nee04]).

Proof of Theorem 4.4.

Case 1.

Case 2.

Case 3.

Case 4.

Claim 1.

Proof.

Claim 2.

Proof.

5. Further applications

5.1. Longer games

Theorem 5.1.

Definition 5.2.

Theorem 5.3.

Proof Sketch.

Claim 1.

5.2. σ\sigma-algebras

Theorem 5.4.

Proof Sketch.

Case 5.

Case 6.

Case 7.

Claim 1.

Question 5.5.

Acknowledgements

References

Long Games and $\sigma$ -Projective Sets

2. Simple games of length $\omega^{2}$

5.2. $\sigma$ -algebras