Open determinacy for class games

  • V. Gitman and J. D. Hamkins, “Open determinacy for class games,” in Foundations of mathematics, logic at harvard, essays in honor of hugh woodin’s 60th birthday, A. E. Caicedo, J. Cummings, P. Koellner, and P. Larson, Eds., American Mathematical Society, (expected) 2016. (Newton Institute preprint ni15064)  
    @INCOLLECTION{GitmanHamkins:OpenDeterminacyForClassGames,
    author = {Victoria Gitman and Joel David Hamkins},
    title = {Open determinacy for class games},
    booktitle = {Foundations of Mathematics, Logic at Harvard, Essays in Honor of Hugh Woodin's 60th Birthday},
    publisher = {American Mathematical Society},
    year = {(expected) 2016},
    editor = {Andr\'es E. Caicedo and James Cummings and Peter Koellner and Paul Larson},
    volume = {},
    number = {},
    series = {Contemporary Mathematics},
    type = {},
    chapter = {},
    pages = {},
    address = {},
    edition = {},
    month = {},
    note = {Newton Institute preprint ni15064},
    url = {http://jdh.hamkins.org/open-determinacy-for-class-games},
    eprint = {1509.01099},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    abstract = {},
    keywords = {},
    pdf= {http://boolesrings.org/victoriagitman/files/2016/09/Proper-class-games.pdf},
    }

One of the intriguing lessons of the past half-century of set theory is that there is a robust connection between infinitary game theory and fundamental set-theoretic principles, including the existence of certain large cardinals, and the existence of strategies in infinite games has often turned out to have an unexpected set-theoretic power. In this article, we should like to exhibit another such connection in the case of games of proper class size, by proving that the principle of clopen determinacy for class games is exactly equivalent to the principle of transfinite recursion along well-founded class relations. Since this principle implies ${\rm Con}({\rm ZFC})$ and iterated instances of ${\rm Con}^\alpha({\rm ZFC})$ and more, the principles of open determinacy and clopen determinacy both transcend ${\rm ZFC}$ in consistency strength.

We consider two-player games of perfect information, where two players alternately play elements from an allowed space $X$ of possible moves, which in our case may be a proper class such as the class of all ordinals $X={\rm Ord}$. Together, the players build an infinite sequence $\vec\alpha=\langle \alpha_0,\alpha_1,\alpha_2,\ldots\rangle$ in $X^\omega$, which is the play resulting from this particular instance of the game. The winner of this play is determined by consulting a fixed class of plays $A\subseteq X^\omega$, possibly a proper class: if $\vec\alpha\in A$, then the first player has won this particular instance of the game, and otherwise the second player has won. A strategy for a player is a (class) function $\sigma:X^{\lt\omega}\to X$, which tells a player how to move next, given a finite position in the game. Such a strategy is winning for that player, if following the instructions of the strategy leads to a winning play of the game, regardless of how the other player has moved. The game is determined, if one of the players has a winning strategy. We may formalize all talk of classes here in Gödel-Bernays ${\rm GBC}$ set theory, or in ${\rm ZFC}$ if one prefers to regard classes as definable from parameters.

The case of open games, generalizing the finite games, is an attractive special case, which for set-sized games has been useful in many arguments. Specifically, a game is open for a particular player, if for every winning play of the game for that player, there occurred during the course of play a finite position where the winning outcome was already ensured, in the sense that all plays extending that position are winning for that player. This is equivalent to saying that the winning condition set for that player is open in the product topology on $X^\omega$, where we put the discrete topology on $X$. Similarly, a game is clopen, if it is open for each player; these are the games for which every play of the game has a finite stage where the outcome is already known.

It is a remarkable elementary fact, the Gale-Stewart theorem [1], that in the context of set-sized games, every open game is determined. An elegant proof of open determinacy can be undertaken using the theory of ordinal game values. (For an accessible discussion of ordinal game values, using infinite chess amongst other games as illustration, please see the second author’s article [2].) Suppose that we have a game that is open for player I, with open winning condition $A\subseteq X^\omega$, where $X$ is the set of possible moves. Consider the collection of positions that arise in this game at a finite stage of the game. Such a position $p$ is said to have value $0$, if player I has essentially already won by achieving that position, in the sense that every play extending $p$ is in $A$; in other words, the entire basic open neighborhood of $p$ is contained in the open set $A$. A position $q$ with player I to play has value $1$, if it isn’t yet winning in that sense, but player I can make a move to $q^\smallfrown x$ so as to have value $0$. These game values measure the distance, in a sense, to a win for player I. Continuing recursively, define that a position $p$ with player I to play has value $\alpha+1$, if $\alpha$ is minimal such that player I can play to a position $p^\smallfrown x$ with value $\alpha$. Finally, the value of a position $p$ with player II to play is defined only when every position $p^\smallfrown y$ that player II can reach already has a value, and in this case the value of $p$ is the supremum of those values. There are two key observations to make. First, if a position has a value, then on his turns player I can play so as to decrease this value and player II cannot play so as to increase it or make it become undefined; thus, by means of this value-reducing strategy, the first player can ensure that eventually the value will become zero, since there is no infinite descending sequence of ordinals, and so this strategy is winning for player I. Second, if a position does not have a defined value, then player I cannot play so as to give it a value and player II can play so as to maintain the fact that it is unvalued; thus, by means of this maintaining strategy, the second player can ensure that a position with value zero is never reached, and so this strategy is winning for player II. Thus, we have proved the Gale-Stewart theorem: every open game is determined.

The reader should observe that this proof of open determinacy relied on the space $X$ of possible moves being a set, because when defining the value function of a position where it was player II’s turn, we took a supremum over the ordinal values of the positions arising from the possible moves, and if $X$ were a proper class, we couldn’t necessarily be sure to stay within the class of ordinals with this supremum. With a proper class $X$, the recursive procedure might break down, and it would seem that we could be pushed to consider class well-orderings having an order-type taller than ${\rm Ord}$. What we should like to do in this article, therefore, is consider more seriously the case where $X$ is a proper class. In this case, the strategies $\sigma:X^{\lt\omega}\to X$ will also be proper classes, and the winning condition $A\subseteq X^\omega$ may also be a proper class.

Question: Can we prove open determinacy for class games?

For example, does every definable open class game in ${\rm ZFC}$ admit a definable winning strategy for one of the players? In ${\rm GBC}$, must every open class game have a winning strategy?

We shall prove that the answers to both of these questions is no. The basic reason, established by Theorem 1, is that open determinacy implies ${\rm Con}({\rm ZFC})$ and much more. Thus, the principle of open determinacy and even of clopen determinacy goes strictly beyond the strength of ${\rm ZFC}$ and ${\rm GBC}$, if these are consistent. This result is generalized and clarified by Theorem 2, which shows that the principle of clopen determinacy is exactly equivalent over ${\rm GBC}$ to the principle of transfinite recursion over well-founded class relations. After this, we shall prove in Theorem 3 that open determinacy is provable in Kelley-Morse set theory ${\rm KM}$, and even in the theory ${\rm GBC}+\Pi^1_1$-comprehension, which is a proper fragment of ${\rm KM}$.

Theorem 1: The principle of clopen determinacy for class games implies ${\rm Con}({\rm ZFC})$, as well as iterated consistency assertions ${\rm Con}^\alpha({\rm ZFC})$ and more. Specifically, there is a definable clopen game, whose determinacy is equivalent over ${\rm GBC}$ to the existence of a satisfaction class for first-order truth.

Theorem 2: In Gödel-Bernays set theory ${\rm GBC}$, the following are equivalent.

  1. Clopen determinacy for class games.
  2. The principle of first-order transfinite recursion over well-founded class relations: every such recursion has a solution.

Theorem 3: Kelley-Morse set theory ${\rm KM}$ proves the principle of open determinacy for class games. Indeed, this conclusion is provable in the subtheory consisting of ${\rm GBC}$ plus $\Pi^1_1$-comprehension.

[1] D. Gale and F. M. Stewart, “Infinite games with perfect information,” in Contributions to the theory of games, vol. 2, Princeton University Press, Princeton, N. J., 1953, pp. 245-266.
[Bibtex]
@incollection {GaleStewart1953:InfiniteGamesWithPerfectInformation,
AUTHOR = {Gale, David and Stewart, F. M.},
TITLE = {Infinite games with perfect information},
BOOKTITLE = {Contributions to the theory of games, vol. 2},
SERIES = {Annals of Mathematics Studies, no. 28},
PAGES = {245--266},
PUBLISHER = {Princeton University Press, Princeton, N. J.},
YEAR = {1953},
MRCLASS = {90.0X},
MRNUMBER = {0054922 (14,999b)},
MRREVIEWER = {S. Sherman},
}
[2] C. D. A. Evans and J. D. Hamkins, “Transfinite game values in infinite chess,” Integers, vol. 14, p. Paper No. G2, 36, 2014.
[Bibtex]
@ARTICLE{EvansHamkins2014:TransfiniteGameValuesInInfiniteChess,
AUTHOR = {C.D.A. Evans and Joel David Hamkins},
TITLE = {Transfinite game values in infinite chess},
JOURNAL = {Integers},
FJOURNAL = {Integers Electronic Journal of Combinatorial Number Theory},
YEAR = {2014},
volume = {14},
number = {},
pages = {Paper No. G2, 36},
month = {},
note = {},
eprint = {1302.4377},
url = {http://jdh.hamkins.org/game-values-in-infinite-chess},
ISSN = {1553-1732},
MRCLASS = {03Exx (91A46)},
MRNUMBER = {3225916},
abstract = {},
keywords = {},
source = {},
}
This entry was posted in publications and tagged , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *