This will be a talk for the Set Theory in the UK, STUK 10, held in Oxford 14 June 2023, organized by my students Clara List, Emma Palmer, and Wojciech Wołoszyn.
Abstract. I shall speak on the surprising strength of the second-order reflection principle in the context of set theory with abundant urelements. The theory GBcU with the abundant urelement axiom and second-order reflection is bi-interpretable with a strengthening of KM with a supercompact cardinal. This is joint work with Bokai Yao.
[bibtex key=”HamkinsYao:Reflection-in-second-order-set-theory-with-abundant-urelements”]
Download pdf at arXiv:2204.09766
Abstract. After reviewing various natural bi-interpretations in urelement set theory, including second-order set theories with urelements, we explore the strength of second-order reflection in these contexts. Ultimately, we prove, second-order reflection with the abundant atom axiom is bi-interpretable and hence also equiconsistent with the existence of a supercompact cardinal. The proof relies on a reflection characterization of supercompactness, namely, a cardinal $\kappa$ is supercompact if and only if every $\Pi^1_1$ sentence true in a structure $M$ (of any size) containing $\kappa$ in a language of size less than $\kappa$ is also true in a substructure $m\prec M$ of size less than $\kappa$ with $m\cap\kappa\in\kappa$.
See also my talk at the CUNY Set Theory Seminar: The surprising strength of reflection in second-order set theory with abundant urelements
This was an online talk 15 April 12:15 for the CUNY Set Theory Seminar. Held on Zoom at 876 9680 2366.
Abstract. I shall give a general introduction to urelement set theory and the role of the second-order reflection principle in second-order urelement set theory GBCU and KMU. With the abundant atom axiom, asserting that the class of urelements greatly exceeds the class of pure sets, the second-order reflection principle implies the existence of a supercompact cardinal in an interpreted model of ZFC. The proof uses a reflection characterization of supercompactness: a cardinal $\kappa$ is supercompact if and only if for every second-order sentence $\psi$ true in some structure $M$ (of any size) in a language of size less than $\kappa$ is also true in a first-order elementary substructure $m\prec M$ of size less than $\kappa$. This is joint work with Bokai Yao.
See the article at: Reflection in second-order set theory with abundant urelements bi-interprets a supercompact cardinal
This will be a talk for the Seminaire de Logique Lyon-Paris on 14 April 2021 4pm Paris time (3pm UK). The talk will be held on Zoom at
875 1148 7359.
Abstract. The principle of open determinacy for class games — two-player games of perfect information with plays of length ω, where the moves are chosen from a possibly proper class, such as games on the ordinals — is not provable in Zermelo-Fraenkel set theory ZFC or Gödel-Bernays set theory GBC, if these theories are consistent, because provably in ZFC there is a definable open proper class game with no definable winning strategy. In fact, the principle of open determinacy and even merely clopen determinacy for class games implies Con(ZFC) and iterated instances Con(Con(ZFC)) and more, because it implies that there is a satisfaction class for first-order truth, and indeed a transfinite tower of truth predicates $\text{Tr}_\alpha$ for iterated truth-about-truth, relative to any class parameter. This is perhaps explained, in light of the Tarskian recursive definition of truth, by the more general fact that the principle of clopen determinacy is exactly equivalent over GBC to the principle of elementary transfinite recursion ETR over well-founded class relations. Meanwhile, the principle of open determinacy for class games is strictly stronger, although it is provable in the stronger theory GBC+$\Pi^1_1$-comprehension, a proper fragment of Kelley-Morse set theory KM.
Abstract.
We show that Kelley-Morse (KM) set theory does not prove the class Fodor principle, the assertion that every regressive class function $F:S\to\newcommand\Ord{\text{Ord}}\Ord$ defined on a stationary class $S$ is constant on a stationary subclass. Indeed, it is relatively consistent with KM for any infinite $\lambda$ with $\omega\leq\lambda\leq\Ord$ that there is a class function $F:\Ord\to\lambda$ that is not constant on any stationary class. Strikingly, it is consistent with KM that there is a class $A\subseteq\omega\times\Ord$, such that each section $A_n=\{\alpha\mid (n,\alpha)\in A\}$ contains a class club, but $\bigcap_n A_n$ is empty. Consequently, it is relatively consistent with KM that the class club filter is not $\sigma$-closed.
The class Fodor principle is the assertion that every regressive class function $F:S\to\Ord$ defined on a stationary class $S$ is constant on a stationary subclass of $S$. This statement can be expressed in the usual second-order language of set theory, and the principle can therefore be sensibly considered in the context of any of the various second-order set-theoretic systems, such as Gödel-Bernays (GBC) set theory or Kelley-Morse (KM) set theory. Just as with the classical Fodor’s lemma in first-order set theory, the class Fodor principle is equivalent, over a weak base theory, to the assertion that the class club filter is normal. We shall investigate the strength of the class Fodor principle and try to find its place within the natural hierarchy of second-order set theories. We shall also define and study weaker versions of the class Fodor principle.
If one tries to prove the class Fodor principle by adapting one of the classical proofs of the first-order Fodor’s lemma, then one inevitably finds oneself needing to appeal to a certain second-order class-choice principle, which goes beyond the axiom of choice and the global choice principle, but which is not available in Kelley-Morse set theory. For example, in one standard proof, we would want for a given $\Ord$-indexed sequence of non-stationary classes to be able to choose for each member of it a class club that it misses. This would be an instance of class-choice, since we seek to choose classes here, rather than sets. The class choice principle $\text{CC}(\Pi^0_1)$, it turns out, is sufficient for us to make these choices, for this principle states that if every ordinal $\alpha$ admits a class $A$ witnessing a $\Pi^0_1$-assertion $\varphi(\alpha,A)$, allowing class parameters, then there is a single class $B\subseteq \Ord\times V$, whose slices $B_\alpha$ witness $\varphi(\alpha,B_\alpha)$; and the property of being a class club avoiding a given class is $\Pi^0_1$ expressible.
Thus, the class Fodor principle, and consequently also the normality of the class club filter, is provable in the relatively weak second-order set theory $\text{GBC}+\text{CC}(\Pi^0_1)$. This theory is known to be weaker in consistency strength than the theory $\text{GBC}+\Pi^1_1$-comprehension, which is itself strictly weaker in consistency strength than KM.
But meanwhile, although the class choice principle is weak in consistency strength, it is not actually provable in KM; indeed, even the weak fragment $\text{CC}(\Pi^0_1)$ is not provable in KM. Those results were proved several years ago by the first two authors, but they can now be seen as consequences of the main result of this article (see corollary 15. In light of that result, however, one should perhaps not have expected to be able to prove the class Fodor principle in KM.
Indeed, it follows similarly from arguments of the third author in his dissertation that if $\kappa$ is an inaccessible cardinal, then there is a forcing extension $V[G]$ with a symmetric submodel $M$ such that $V_\kappa^M=V_\kappa$, which implies that $\mathcal M=(V_\kappa,\in, V^M_{\kappa+1})$ is a model of Kelley-Morse, and in $\mathcal M$, the class Fodor principle fails in a very strong sense.
In this article, adapting the ideas of Karagila to the second-order set-theoretic context and using similar methods as in Gitman and Hamkins’s previous work on KM, we shall prove that every model of KM has an extension in which the class Fodor principle fails in that strong sense: there can be a class function $F:\Ord\to\omega$, which is not constant on any stationary class. In particular, in these models, the class club filter is not $\sigma$-closed: there is a class $B\subseteq\omega\times\Ord$, each of whose vertical slices $B_n$ contains a class club, but $\bigcap B_n$ is empty.
Main Theorem. Kelley-Morse set theory KM, if consistent, does not prove the class Fodor principle. Indeed, if there is a model of KM, then there is a model of KM with a class function $F:\Ord\to \omega$, which is not constant on any stationary class; in this model, therefore, the class club filter is not $\sigma$-closed.
We shall also investigate various weak versions of the class Fodor principle.
Definition.
We shall separate these principles as follows.
Theorem. Suppose KM is consistent.
Finally, we show that the class Fodor principle can neither be created nor destroyed by set forcing.
Theorem. The class Fodor principle is invariant by set forcing over models of $\text{GBC}^-$. That is, it holds in an extension if and only if it holds in the ground model.
Let us conclude this brief introduction by mentioning the following easy negative instance of the class Fodor principle for certain GBC models. This argument seems to be a part of set-theoretic folklore. Namely, consider an $\omega$-standard model of GBC set theory $M$ having no $V_\kappa^M$ that is a model of ZFC. A minimal transitive model of ZFC, for example, has this property. Inside $M$, let $F(\kappa)$ be the least $n$ such that $V_\kappa^M$ fails to satisfy $\Sigma_n$-collection. This is a definable class function $F:\Ord^M\to\omega$ in $M$, but it cannot be constant on any stationary class in $M$, because by the reflection theorem there is a class club of cardinals $\kappa$ such that $V_\kappa^M$ satisfies $\Sigma_n$-collection.
Read more by going to the full article: [bibtex key=”GitmanHamkinsKaragila:KM-set-theory-does-not-prove-the-class-Fodor-theorem”]
[bibtex key=”HamkinsWoodin2018:Open-class-determinacy-is-preserved-by-forcing”]
Abstract. The principle of open class determinacy is preserved by pre-tame class forcing, and after such forcing, every new class well-order is isomorphic to a ground-model class well-order. Similarly, the principle of elementary transfinite recursion ETR${}_\Gamma$ for a fixed class well-order $\Gamma$ is preserved by pre-tame class forcing. The full principle ETR itself is preserved by countably strategically closed pre-tame class forcing, and after such forcing, every new class well-order is isomorphic to a ground-model class well-order. Meanwhile, it remains open whether ETR is preserved by all forcing, including the forcing merely to add a Cohen real.
The principle of elementary transfinite recursion ETR — according to which every first-order class recursion along any well-founded class relation has a solution — has emerged as a central organizing concept in the hierarchy of second-order set theories from Gödel-Bernays set theory GBC up to Kelley-Morse set theory KM and beyond. Many of the principles in the hierarchy can be seen as asserting that certain class recursions have solutions.
In addition, many of these principles, including ETR and its variants, are equivalently characterized as determinacy principles for certain kinds of class games. Thus, the hierarchy is also fruitfully unified and organized by determinacy ideas.
This hierarchy of theories is the main focus of study in the reverse mathematics of second-order set theory, an emerging subject aiming to discover the precise axiomatic principles required for various arguments and results in second-order set theory. The principle ETR itself, for example, is equivalent over GBC to the principle of clopen determinacy for class games and also to the existence of iterated elementary truth predicates (see Open determinacy for class games); since every clopen game is also an open game, the principle ETR is naturally strengthened by the principle of open determinacy for class games, and this is a strictly stronger principle (see Hachtman and Sato); the weaker principle ETR${}_\text{Ord}$, meanwhile, asserting solutions to class recursions of length Ord, is equivalent to the class forcing theorem, which asserts that every class forcing notion admits a forcing relation, to the existence of set-complete Boolean completions of any class partial order, to the existence of Ord-iterated elementary truth predicates, to the determinacy of clopen games of rank at most Ord+1, and to other natural set-theoretic principles (see The exact strength of the class forcing theorem).
Since one naturally seeks in any subject to understand how one’s fundamental principles and tools interact, we should like in this article to consider how these second-order set-theoretic principles are affected by forcing. These questions originated in previous work of Victoria Gitman and myself, and question 1 also appears in the dissertation of Kameryn Williams, which was focused on the structure of models of second-order set theories.
It is well-known, of course, that ZFC, GBC, and KM are preserved by set forcing and by tame class forcing, and this is true for other theories in the hierarchy, such as GBC$+\Pi^1_n$-comprehension and higher levels of the second-order comprehension axiom. The corresponding forcing preservation theorem for ETR and for open class determinacy, however, has not been known.
Question 1. Is ETR preserved by forcing?
Question 2. Is open class determinacy preserved by forcing?
We intend to ask in each case about class forcing as well as set forcing. Question 1 is closely connected with the question of whether forcing can create new class well-order order types, longer than any class well-order in the ground model. Specifically, Victoria Gitman and I had observed earlier that ETR${}_\Gamma$ for a specific class well-order $\Gamma$ is preserved by pre-tame class forcing, and this would imply that the full principle ETR would also be preserved, if no fundamentally new class well-orders are created by the forcing. In light of the fact that forcing over models of ZFC adds no new ordinals, that would seem reasonable, but proof is elusive, and the question remains open. Can forcing add new class well-orders, perhaps very tall ones that are not isomorphic to any ground model class well-order? Perhaps there are some very strange models of GBC that gain new class well-order order types in a forcing extension.
Question 3. Assume GBC. After forcing, must every new class well-order be isomorphic to a ground-model class well-order? Does ETR imply this?
The main theorem of this article provides a full affirmative answer to question 2, and partial affirmative answers to questions 2 and 3.
Main Theorem.
We should like specifically to highlight the fact that questions 1 and 3 remain open even in the case of the forcing to add a Cohen real. Is ETR preserved by the forcing to add a Cohen real? After adding a Cohen real, is every new class well-order isomorphic to a ground-model class well-order? One naturally expects affirmative answers, especially in a model of ETR.
For more, click through the arxiv for a pdf of the full article.
[bibtex key=”HamkinsWoodin2018:Open-class-determinacy-is-preserved-by-forcing”]
Kameryn J. Williams successfully defended his dissertation under my supervision at the CUNY Graduate Center on April 6th, 2018, earning his Ph.D. degree in May 2018. He has accepted a position in mathematics at the University of Hawaii, to begin Fall 2018.
What a pleasure it was to work with Kameryn, an extremely talented mathematician with wide interests and huge promise.
Kameryn J Williams | MathOverflow | ar$\chi$iv
Kameryn J. Williams, The Structure of Models of Second-order Set Theories, Ph.D. dissertation for The Graduate Center of the City University of New York, May, 2018. arXiv:1804.09526.
Abstract. This dissertation is a contribution to the project of second-order set theory, which has seen a revival in recent years. The approach is to understand second-order set theory by studying the structure of models of second-order set theories. The main results are the following, organized by chapter. First, I investigate the poset of T-realizations of a fixed countable model of ZFC, where T is a reasonable second-order set theory such as GBC or KM, showing that it has a rich structure. In particular, every countable partial order embeds into this structure. Moreover, we can arrange so that these embedding preserve the existence/nonexistence of upper bounds, at least for finite partial orders. Second I generalize some constructions of Marek and Mostowski from KM to weaker theories. They showed that every model of KM plus the Class Collection schema “unrolls” to a model of ZFC− with a largest cardinal. I calculate the theories of the unrolling for a variety of second-order set theories, going as weak as GBC + ETR. I also show that being T-realizable goes down to submodels for a broad selection of second-order set theories T. Third, I show that there is a hierarchy of transfinite recursion principles ranging in strength from GBC to KM. This hierarchy is ordered first by the complexity of the properties allowed in the recursions and second by the allowed heights of the recurions. Fourth, I investigate the question of which second-order set theories have least models. I show that strong theories—such as KM or $\Pi^1_1$-CA—do not have least transitive models, while weaker theories—from GBC to GBC + ETR${}_{\text{Ord}}$—do have least transitive models.
In addition to his dissertation work and the research currently arising out of it, Kameryn has undertaken a number of collaborations with various international research efforts, including the following:
This will be a talk for the Prague set theory seminar, January 24, 11:00 am to about 2pm (!).
Abstract. The class forcing theorem is the assertion that every class forcing notion admits corresponding forcing relations. This assertion is not provable in Zermelo-Fraenkel ZFC set theory or Gödel-Bernays GBC set theory, if these theories are consistent, but it is provable in stronger second-order set theories, such as Kelley-Morse KM set theory. In this talk, I shall discuss the exact strength of this theorem, which turns out to be equivalent to the principle of elementary transfinite recursion ETRord for class recursions on the ordinals. The principle of clopen determinacy for class games, in contrast, is strictly stronger, equivalent over GBC to the full principle of ETR for class recursions over arbitrary class well-founded relations. These results and others mark the beginnings of the emerging subject I call the reverse mathematics of second-order set theory.
The exact strength of the class forcing theorem | Open determinacy for class games
A few years ago, I had observed after hearing a talk by Benjamin Rin that the principle of first-order transfinite recursion for set well-orders is equivalent to the replacement axiom over Zermelo set theory, and thus we may take transfinite recursion as a fundamental set-theoretic principle, one which yields full ZFC when added to Zermelo’s weaker theory (plus foundation).
In later work, Victoria Gitman and I happened to prove that the principle of elementary transfinite recursion ETR, which allows for first-order class recursions along proper class well-orders (not necessarily set-like) is equivalent to the principle of determinacy for clopen class games [1]. Thus, once again, a strong recursion principle exhibited robustness as a fundamental set-theoretic principle.
The theme continued in recent joint work on the class forcing theorem, in which Victoria Gitman, myself, Peter Holy, Philipp Schlicht and Kameryn Williams [2] proved that the principle $\text{ETR}_{\text{Ord}}$, which allows for first-order class recursions of length $\text{Ord}$, is equivalent to twelve natural set-theoretic principles, including the existence of forcing relations for class forcing notions, the existence of Boolean completions for class partial orders, the existence of various kinds of truth predicates for infinitary logics, the existence of $\text{Ord}$-iterated truth predicates, and to the principle of determinacy for clopen class games of rank at most $\text{Ord}+1$.
A few days ago, a MathOverflow question of Alec Rhea’s — Is there a stronger form of recursion? — led me to notice that one naturally gains additional strength by pushing the recursion principles further into second-order set theory.
So let me introduce the second-order recursion principle STR and make the comparatively simple observation that over Gödel-Bernays GBC set theory this is equivalent to Kelley-Morse set theory KM. Thus, we may take this kind of recursion as a fundamental set-theoretic principle.
Definition. In the context of second-order set theory, the principle of second-order transfinite recursion, denoted STR, asserts of any formula $\varphi$ in the second-order language of set theory, that if $\Gamma=\langle I,\leq_\Gamma\rangle$ is any class well-order and $Z$ is any class parameter, then there is a class $S\subset I\times V$ that is a solution of the recursion, in the sense that
$$S_i=\{\ x\ \mid\ \varphi(x,S\upharpoonright i,Z)\ \}$$
for every $i\in I$, where where $S_i=\{\ x\ \mid\ (i,x)\in S\ \}$ is the section on coordinate $i$ and where $S\upharpoonright i=\{\ (j,x)\in S\ \mid\ j<_\Gamma i\ \}$ is the part of the solution at stages below $i$ with respect to $\Gamma$.
Theorem. The principle of second-order transfinite recursion STR is equivalent over GBC to the second-order comprehension principle. In other words, GBC+STR is equivalent to KM.
Proof. Kelley-Morse set theory proves that every second-order recursion has a solution in the same way that ZFC proves that every set-length well-ordered recursion has a solution. Namely, we simply consider the classes which are partial solutions to the recursion, in that they obey the recursive requirement, but possibly only on an initial segment of the well-order $\Gamma$. We may easily show by induction that any two such partial solutions agree on their common domain (this uses second-order comprehension in order to find the least point of disagreement, if any), and we can show that any given partial solution, if not already a full solution, can be extended to a partial solution on a strictly longer initial segment. Finally, we show that the common values of all partial solutions is therefore a solution of the recursion. This final step uses second-order comprehension in order to define what the common values are for the partial solutions to the recursion.
Conversely, the principle of second-order transfinite recursion clearly implies the second-order comprehension axiom, by considering recursions of length one. For any second-order assertion $\varphi$ and class parameter $Z$, we may deduce that $\{x\mid \varphi(x,Z)\}$ is a class, and so the second-order class comprehension principle holds. $\Box$
It is natural to consider various fragments of STR, such as $\Sigma^1_n\text{-}\text{TR}_\Gamma$, which is the assertion that every $\Sigma^1_n$-formula $\varphi$ admits a solution for recursions of length $\Gamma$. Such principles are provable in proper fragments of KM, since for a given level of complexity, we only need a corresponding fragment of comprehension to undertake the proof that the recursion has a solution. The full STR asserts $\Sigma^1_\omega\text{-}\text{TR}$, allowing any length. The theorem shows that STR is equivalent to recursions of length $1$, since once you get the second-order comprehension principle, then you get solutions for recursions of any length. Thus, with second-order transfinite recursion, a little goes a long way. Perhaps it is more natural to think of transfinite recursion in this context not as axiomatizing KM, since it clearly implies second-order comprehension straight away, but rather as an apparent strengthening of KM that is actually provable in KM. This contrasts with the first-order situation of ETR with respect to GBC, where GBC+ETR does make a proper strengthening of GBC.
Regula Krapf successfully defended her PhD dissertation January 12, 2017 at the University of Bonn, with a dissertation entitled, “Class forcing and second-order arithmetic.” I was a member of the dissertation examining committee. Peter Koepke was the dissertation supervisor.
Regula Krapf, Class forcing and second-order arithmetic, dissertation 2017, University of Bonn. (Slides)
Abstract. We provide a framework in a generalization of Gödel-Bernays set theory for performing class forcing. The forcing theorem states that the forcing relation is a (definable) class in the ground model (definability lemma) and that every statement that holds in a class-generic extension is forced by a condition in the generic filter (truth lemma). We prove both positive and negative results concerning the forcing theorem. On the one hand, we show that the definability lemma for one atomic formula implies the forcing theorem for all formulae in the language of set theory to hold. Furthermore, we introduce several properties which entail the forcing theorem. On the other hand, we give both counterexamples to the definability lemma and the truth lemma. In set forcing, the forcing theorem can be proved for all forcing notions by constructing a unique Boolean completion. We show that in class forcing the existence of a Boolean completion is essentially equivalent to the forcing theorem and, moreover, Boolean completions need not be unique.
The notion of pretameness was introduced to characterize those forcing notions which preserve the axiom scheme of replacement. We present several new characterizations of pretameness in terms of the forcing theorem, the preservation of separation, the existence of nice names for sets of ordinals and several other properties. Moreover, for each of the aforementioned properties we provide a corresponding characterization of the Ord-chain condition.
Finally, we prove two equiconsistency results which compare models of ZFC (with large cardinal properties) and models of second-order arithmetic with topological regularity properties (and determinacy hypotheses). We apply our previous results on class forcing to show that many important arboreal forcing notions preserve the $\Pi^1_1$-perfect set property over models of second-order arithmetic and also give an example of a forcing notion which implies the $\Pi^1_1$-perfect set property to fail in the generic extension.
Regula has now taken up a faculty position at the University of Koblenz.
This will be a talk for the CUNY Logic Workshop on October 2, 2015.
Abstract. The principle of open determinacy for class games — two-player games of perfect information with plays of length $\omega$, where the moves are chosen from a possibly proper class, such as games on the ordinals — is not provable in Zermelo-Fraenkel set theory ZFC or Gödel-Bernays set theory GBC, if these theories are consistent, because provably in ZFC there is a definable open proper class game with no definable winning strategy. In fact, the principle of open determinacy and even merely clopen determinacy for class games implies Con(ZFC) and iterated instances Con(Con(ZFC)) and more, because it implies that there is a satisfaction class for first-order truth, and indeed a transfinite tower of truth predicates $\text{Tr}_\alpha$ for iterated truth-about-truth, relative to any class parameter. This is perhaps explained, in light of the Tarskian recursive definition of truth, by the more general fact that the principle of clopen determinacy is exactly equivalent over GBC to the principle of elementary transfinite recursion ETR over well-founded class relations. Meanwhile, the principle of open determinacy for class games is provable in the stronger theory GBC+$\Pi^1_1$-comprehension, a proper fragment of Kelley-Morse set theory KM.
This is joint work with Victoria Gitman, with the helpful participation of Thomas Johnstone.
Related article and posts:
[bibtex key=GitmanHamkins2016:OpenDeterminacyForClassGames]
Abstract. The principle of open determinacy for class games — two-player games of perfect information with plays of length $\omega$, where the moves are chosen from a possibly proper class, such as games on the ordinals — is not provable in Zermelo-Fraenkel set theory ZFC or Godel-Bernays set theory GBC, if these theories are consistent, because provably in ZFC there is a definable open proper class game with no definable winning strategy. In fact, the principle of open determinacy and even merely clopen determinacy for class games implies Con(ZFC) and iterated instances Con(Con(ZFC)) and more, because it implies that there is a satisfaction class for first-order truth, and indeed a transfinite tower of truth predicates $\text{Tr}_\alpha$ for iterated truth-about-truth, relative to any class parameter. This is perhaps explained, in light of the Tarskian recursive definition of truth, by the more general fact that the principle of clopen determinacy is exactly equivalent over GBC to the principle of transfinite recursion over well-founded class relations. Meanwhile, the principle of open determinacy for class games is provable in the stronger theory GBC$+\Pi^1_1$-comprehension, a proper fragment of Kelley-Morse set theory KM.
See my earlier posts on part of this material:
$\newcommand\Tr{\text{Tr}}$One of the intriguing lessons we have learned in the past half-century of set-theoretic developments is that there is a surprisingly robust connection between infinitary game theory and fundamental set-theoretic principles, including large cardinals. Assertions about the existence of strategies in infinite games often turn out to have an unexpected set-theoretic power. In this post, I should like to give another specific example of this, which Thomas Johnstone and I hit upon yesterday in an enjoyable day of mathematics.
Specifically, I’d like to prove that if we generalize the open-game concept from sets to classes, then assuming consistency, ZFC cannot prove that every definable open class game is determined, and indeed, over Gödel-Bernays set theory GBC the principle of open determinacy (and even just clopen determinacy) implies Con(ZFC) and much more.
To review a little, we are talking about games of perfect information, where two players alternately play elements from an allowed space $X$ of possible moves, and together they build an infinite sequence $\vec x=\langle x_0,x_1,x_2,\ldots\rangle$ in $X^\omega$, which is the resulting play of this particular instance of the game. We have a fixed collection of plays $A\subset X^\omega$ that is used to determine the winner, namely, the first player wins this particular instance of the game if the resulting play $\vec x$ is in $A$, and otherwise the second player wins. A strategy for a player is a function $\sigma:X^{<\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 he or she always wins by following the instructions, no matter how the opponent plays. The game is determined, if one of the players has a winning strategy.
It is a remarkable but elementary fact that if the winning condition $A$ is an open set, then the game is determined. One can prove this by using the theory of ordinal game values, and my article on transfinite game values in infinite chess contains an accessible introduction to the theory of game values. Basically, one defines that a position has game value zero (for player I, say), if the game has already been won at that stage, in the sense that every extension of that position is in the winning payoff set $A$. A position with player I to play has value $\alpha+1$, if player I can move to a position with value $\alpha$, and $\alpha$ is minimal. The value of a position with player II to play is the supremum of the values of all the positions that he or she might reach in one move, provided that those positions have a value. The point now is that if a position has a value, then player I can play so as strictly to decrease the value, and player II cannot play so as to increase it. So if a position has a value, then player I has a winning strategy, which is the value-reducing strategy. Conversely, if a position does not have a value, then player II can maintain that fact, and player I cannot play so as to give it a value; thus, in this case player II has a winning strategy, the value-maintaining strategy. Thus, we have proved the Gale-Stewart theorem: every open game is determined.
That proof relied on the space of moves $X$ being a set, since we took a supremum over the values of the possible moves, and if $X$ were a proper class, we couldn’t be sure to stay within the class of ordinals and the recursive procedure might break down. What I’d like to do is to consider more seriously the case where $X$ is a proper class. Similarly, we allow the payoff collection $A$ to be a proper class, and the strategies $\sigma:X^{<\omega}\to X$ are also proper classes. Can we still prove the Gale-Steward theorem for proper classes? The answer is no, unless we add set-theoretic strength. Indeed, even clopen determinacy has set-theoretic strength.
Theorem. (GBC) Clopen determinacy for proper classes implies Con(ZFC) and much more. Specifically, there is a clopen game, such the existence of a winning strategy is equivalent to the existence of a satisfaction class for first-order truth.
Proof. Let me first describe a certain open game, the truth-telling game, with those features, and I shall later modify it to a clopen game. The truth-telling game will have two players, which I call the challenger and the truth-teller. At any point in the game, the challenger plays by making an inquiry about a particular set-theoretic formula $\varphi(\vec a)$ with parameters. The truth-teller must reply to the inquiry by stating either true or false, and in the case that the formula $\varphi$ is an existential assertion $\exists x\,\psi(x,\vec a)$ declared to be true, then the truth teller must additionally identify a particular witness $b$ and assert that $\psi(b,\vec a)$ is true. So a play of the game consists of a sequence of such inquires and replies.
The truth-teller wins a play of the game, provided that she never violates the recursive Tarskian truth conditions. Thus, faced with an atomic formula, she must state true or false in accordance with the actual truth or falsity of that atomic formula, and similarly,
she must say true to $\varphi\wedge\psi$ just in case she said true to both $\varphi$ and $\psi$ separately (if those formulas had been issued by the challeger), and she must state opposite truth values for $\varphi$ and $\neg\varphi$, if both are issued as challenges.
This is an open game, since the challenger will win, if at all, at a finite stage of play, when the violation of the Tarskian truth conditions is first exhibited.
Lemma 1. The truth-teller has a winning strategy in the truth-telling game if and only if there is a satisfaction class for first-order truth.
Proof. Clearly, if there is a satisfaction class for first-order truth, then the truth-teller has a winning strategy, which is simply to answer all questions about truth by consulting the
satisfaction class. Since that class obeys the Tarskian conditions, she will win the game, no matter which challenges are issued.
Conversely, suppose that the truth-teller has a winning strategy $\tau$ in the game. I claim that we may use $\tau$ to build a satisfaction class for first-order truth. Specifically, let $T$ be the collection of formulas $\varphi(\vec a)$ that are asserted to be true by $\tau$ in any play according to $\tau$. I claim that $T$ is a satisfaction class. We may begin by noting that since $T$ must correctly state the truth of all atomic formulas, it follows that the particular answers that $\tau$ gives on the atomic formulas does not depend on the order of the challenges issued by the challenger. Now, we argue by induction on formulas that the truth values issued by $\tau$ does not depend on the order of the challenges. For example, if all plays in which $\varphi(\vec a)$ is issued as a challenge come out true, then all plays in which $\neg\varphi(\vec a)$ is challenged will result in false, or else we would have a play in which $\tau$ would violate the Tarskian truth conditions. Similarly, if $\varphi$ and $\psi$ always come out the same way, then so does $\varphi\wedge\psi$. We don’t claim that $\tau$ must always issue the same witness $b$ for an existential $\exists x\,\psi(x,\vec a)$, but if it ever says true to this statement, then it will provide some witness $b$, and for that statement $\psi(b,\vec a)$, the truth value stated by $\tau$ is independent of the order of play by the challenger, by induction. Thus, by induction on formulas, the answers provided by the truth-teller strategy $\tau$ gives us a satisfaction predicate for first-order truth. QED
Lemma 2. The challenger has no winning strategy in the truth-telling game.
Proof. Suppose that $F$ is a strategy for the challenger. So $F$ is a proper class function that directs the challenger to issue certain challenges, given the finite sequence of previous challenges and truth-telling answers. By the reflection theorem, there is a closed unbounded proper class of cardinals $\theta$, such that $F”V_\theta\subset V_\theta$. That is, $V_\theta$ is closed under $F$, in the sense that if all previous challenges and responses come from $V_\theta$, then the next challenge will also come from $V_\theta$. Since $\langle V_\theta,\in\rangle$ is a set, we have a satisfaction predicate on it. Consider the play, where the truth-teller replies to all inquires by consulting truth in $V_\theta$, rather than truth in $V$. The point is that if the challenger follows $\tau$, then all the inquiries will involve only parameters $\vec a$ in $V_\theta$, provided that the truth-teller also always gives witnesses in $V_\theta$, which in this particular play will be the case. Since the satisfaction predicate on $V_\theta$ does satisfy the Tarskian truth conditions, it follows that the truth-teller will win this instance of the game, and so $F$ is not a winning strategy for the challenger. QED
Thus, if open determinacy holds for classes, then there is a satisfaction predicate for first-order truth.
This implies Con(ZFC) for reasons I explained on my post KM implies Con(ZFC) and much more, by appealing to the fact that we have the collection axiom relative to the class for the satisfaction predicate itself, and this is enough to verify that the nonstandard instances of collection also must be declared true in the satisfaction predicate.
But so far, we only have an open game, rather than a clopen game, since the truth-teller wins only by playing the game out for infinitely many steps. So let me describe how to modify the game to be clopen. Specifically, consider the version of the truth-telling game, where the challenger must also state on each move a specific ordinal $\alpha_n$, which descend during play $\alpha_0>\alpha_1>\cdots>\alpha_n$. If the challenger gets to $0$, then the truth-teller is declared the winner. For this modified game, the winner is known in finitely many moves, because either the truth-teller violates the Tarskian conditions or the challenger hits zero. So this is a clopen game. Since we made the game harder for the challenger, it follows that the challenger still can have no winning strategy. One can modify the proof of lemma 1 to say that if $\tau$ is a winning strategy for the truth teller, then the truth assertions made by $\tau$ in response to all plays with sufficiently large ordinals for the challenger all agree with one another independently of the order of the formulas issued by the challenger. Thus, there is a truth-telling strategy just in case there is a satisfaction class for first-order truth.
So clopen determinacy for class games implies the existence of a satisfaction class for first-order truth, and this implies Con(ZFC) and much more. QED
One may easily modify the game by allowing a fixed class parameter $B$, so that clopen determinacy implies that there is a satisfaction class relative to truth in $\langle V,\in,B\rangle$.
Furthermore, we may also get iterated truth predicates. Specifically, consider the iterated truth-telling game, which in addition to the usual language of set theory, we have a hierarchy of predicates $\Tr_\alpha$ for any ordinal $\alpha$. We now allow the challenger to ask about formulas in this expanded language, and the truth teller is required to obey not only the usual Tarskian recursive truth conditions, but also the requirements that $\Tr_\alpha(\varphi(\vec a))$ is declared true just in case $\varphi(\vec a)$ uses only truth predicates $\Tr_\beta$ for $\beta<\alpha$ and also $\varphi(\vec a)$ is declared true (if this challenge was issued).
The main arguments as above generalize easily to show that the challenger cannot have a winning strategy in this iterated truth-telling game, and the truth-teller has a strategy just in case there is a satisfaction predicate for truth-about-truth iterated through the ordinals. Thus, the principle of open determinacy for proper class games implies Con(Con(ZFC)) and $\text{Con}^\alpha(\text{ZFC})$ and so on.
Let me finish by mentioning that Kelley-Morse set theory is able to prove open determinacy for proper class games in much the same manner as we proved the Gale-Stewart theorem above, using well-ordered class meta-ordinals, rather than merely set ordinals, as well as in other ways. If there is interest, I can make a further post about that, so just ask in the comments!
I should like to give a brief account of the argument that KM implies Con(ZFC) and much more. This argument is well-known classically, but unfortunately seems not to be covered in several of the common set-theoretic texts.
First, without giving a full formal axiomatization, let us review a little what KM is. (And please see Victoria Gitman’s post on variant axiomatizations of KM.) In contrast to Zermelo-Frankael (ZFC) set theory, which has a purely first-order axiomatization, both Kelley-Morse (KM) set theory and Gödel-Bernays (GBC) set theory are formalized in the second-order language of set theory, where we have two sorts of objects, namely sets and classes, in addition to the usual set membership relation $\in$. A model of KM will have the form $\langle M,{\in^M},S\rangle$, where $M$ is the collection of sets in the model, and $S$ is a collection of classes in the model; each class $A\in S$ is simply the subset of $M$. Both KM and GBC will imply that $\langle M,{\in^M}\rangle$ is a model of ZFC. Both GBC and KM assert the global choice principle, which asserts that there is a class that is a well-ordering of all the sets (or equivalently that there is a class bijection of all the sets with the class of ordinals). Beyond this, both GBC and KM have a class comprehension principle, asserting that for certain formulas $\varphi$, having finitely many set and class parameters, that $\{x \mid \varphi(x)\}$ forms a class. In the case of GBC, we have this axiom only for $\varphi$ having only set quantifiers, but in KM we also allow formulas $\varphi$ that have quantification over classes (which are interpreted in the model by quanfying over $S$). Both theories also assert that the intersection of a class with a set is a set (which amounts to the separation axiom, and this follows from replacement anyway). In addition, both GBC and KM have a replacement axiom, asserting that if $u$ is a set, and for every $a\in u$ there is a unique set $b$ for which $\varphi(a,b)$, where $\varphi$ has finitely many class and set parameters, then $\{ b\mid \exists a\in u\, \varphi(a,b)\}$ is a set. In the case of GBC, we have the replacement axiom only when all the quantifiers of $\varphi$ are first-order quantifiers only, quantifying only over sets, but in KM we allow $\varphi$ to have second-order quantifiers. Thus, both GBC and KM can be thought of as rather direct extensions of ZFC to the second-order class context, but KM goes a bit further by applying the ZFC axioms also in the case of the new second-order properties that become available in that context, while GBC does not.
The theorem I want to discuss is:
Theorem. KM proves Con(ZFC).
Indeed, ultimately we’ll show in KM that there is transitive model of ZFC, and furthermore that the universe $V$ is the union of an elementary chain of elementary rank initial segments $V_\theta\prec V$, each of which, in particular, is a transitive model of ZFC.
We’ll prove it in several steps, which will ultimately reveal stronger results and a general coherent method and idea.
KM has a truth predicate for first-order truth. The first step is to argue in KM that there is a truth predicate Tr for first-order truth, a class of pairs $(\varphi,a)$, where $\varphi$ is a first-order formula in the language of set theory and $a$ is an assignment of the free variabes of $\varphi$ to particular sets, such that the class Tr gets the right answer on the quantifier-free formulas and obeys the recursive Tarskian truth conditions for Boolean combinations and first-order quantification, that is, the conditions explaining how the truth of a formula is determined from the truth of its immediate subformulas.
To construct the truth predicate, begin with the observation that we may easily define, even in ZFC, a truth predicate for quantifier-free truth, and indeed, even first-order $\Sigma_n$ truth is $\Sigma_n$-definable, for any meta-theoretic natural number $n$. In KM, we may consider the set of natural numbers $n$ for which there is a partial truth predicate $T$, one which is defined only for first-order formulas of complexity at most $\Sigma_n$, but which gives the correct answers on the quantifier-free formulas and which obeys the Tarskian conditions up to complexity $\Sigma_n$. The set of such $n$ exists, by the separation axiom of KM, since we can define it by a property in the second-order language (this would not work in GBC, since there is a second-order quantifier asking for the existence of the partial truth predicate). But now we simply observe that the set contains $n=0$, and if it contains $n$, then it contains $n+1$, since from any $\Sigma_n$ partial truth predicate we can define one for $\Sigma_{n+1}$. So by induction, we must have such truth predicates for all natural numbers $n$. This inductive argument really used the power of KM, and cannot in general be carried out in GBC or in ZFC.
A similar argument shows by induction that all these truth predicates must agree with one another, since there can be no least complexity stage where they disagree, as the truth values at that stage are completely determined via the Tarski truth conditions from the earlier stage. So in KM, we have a unique truth predicate defined on all first-order assertions, which has the correct truth values for quantifier-free truth and which obeys the Tarskian truth conditions.
The truth predicate Tr agrees with actual truth on any particular assertion. Since the truth predicate Tr agrees with the actual truth of quantifier-free assertions and obeys the Tarskian truth conditions, it follows by induction in the meta-theory (and so this is a scheme of assertions) that the truth predicate that we have constructed agrees with actual truth for any meta-theoretically finite assertion.
The truth predicate Tr thinks that all the ZFC axioms are all true. Here, we refer not just to the truth of actual ZFC axioms (which Tr asserts as true by the previous paragraph), but to the possibly nonstandard formulas that exist inside our KM universe. We claim nevertheless that all such formulas the correspond to an axiom of ZFC are still decreed true by the predicate Tr. We get all the easy axioms by the previous paragraph, since those axioms are true under KM. It remains only to verify that Tr asserts as true all instances of the replacement axiom. For this, suppose that there is a set $u$, such that Tr thinks every $a\in u$ has a unique $b$ for which Tr thinks $\varphi(a,b)$. But now by KM (actually we need only GB here), we may apply the replacement axiom with Tr a predicate, to find that $\{ b\mid \exists a\in u\, \text{Tr thinks that} \varphi(a,b)\}$ is a set, whether or not $\varphi$ is an actual finite length formula in the metatheory. It follows that Tr will assert this instance of replacement, and so Tr will decree all instances of replacement as being true.
KM produces a closed unbounded tower of transitive models of ZFC. This is the semantic approach, which realizes the universe as the union of an elementary chain of elementary substructures $V_\theta$. Namely, by the reflection theorem, there is a closed unbounded class of ordinals $\theta$ such that $\langle V_\theta,{\in},\text{Tr}\cap V_\theta\rangle\prec_{\Sigma_1}\langle V,{\in},\text{Tr}\rangle$. (We could have used $\Sigma_2$ or $\Sigma_{17}$ here just as well.) It follows that $\text{Tr}\cap V_\theta$ fulfills the Tarskian truth conditions on the structure $\langle V_\theta,\in\rangle$, and therefore agrees with the satisfaction in that structure. It follows that $V_\theta\prec V$ for first-order truth, and since ZFC was part of what is asserted by Tr, we have produced here a transitive model of ZFC. More than this, what we have is a closed unbounded class of ordinals $\theta$, which form an elementary chain $$V_{\theta_0}\prec V_{\theta_1}\prec\cdots\prec V_\lambda\prec\cdots,$$ whose union is the entire universe. Each set in this chain is a transitive model of ZFC and much more.
An alternative syntactic approach. We could alternatively have reasoned directly with the truth predicate as follows. First, the truth predicate is complete, and contains no contradictions, simply because part of the Tarskian truth conditions are that $\neg\varphi$ is true according to Tr if and only if $\varphi$ is not true according to Tr, and this prevents explicit contradictions from ever becoming true in Tr, while also ensuring completeness. Secondly, the truth predicate is closed under deduction, by a simple induction on the length of the proof. One must verify that certain logical validities are decreed true by Tr, and then it follows easily from the truth conditions that Tr is closed under modus ponens. The conclusion is that the theory asserted by Tr contains ZFC and is consistent, so Con(ZFC) holds. Even though Tr is a proper class, the set of sentences it thinks are true is a complete consistent extension of ZFC, and so Con(ZFC) holds. QED
The argument already shows much more than merely Con(ZFC), for we have produced a proper class length elementary tower of transitive models of ZFC. But it generalizes even further, for example, by accommodating class parameters. For any class $A$, we can construct in the same way a truth predicate $\text{Tr}_A$ for truth in the first-order language of set theory augmented with a predicate for the class $A$.
In particular, KM proves that there is a truth predicate for truth-about-truth, that is, for truth-about-Tr, and for truth-about-truth-about-truth, and so on, iterating quite a long way. (Of course, this was also clear directly from the elementary tower of transitive models.)
The elementary tower of transitive elementary rank initial segments $V_\theta\prec V$ surely addresses what is often seen as an irritating limitation of the usual reflection theorem in ZFC, that one gets only $\Sigma_n$-reflection $V_\theta\prec_{\Sigma_n} V$ rather than this kind of full reflection, which is what one really wants in a reflection theorem. The point is that in KM we are able to refer to our first-order truth predicate Tr and overcome that restriction.
Doesn’t the existence of a truth predicate violate Tarski’s theorem on the non-definability of truth? No, not here, since the truth predicate Tr is not definable in the first-order language of set theory. Tarski’s theorem asserts that there can be no definable class (even definable with set parameters) that agrees with actual truth on quantifier-free assertions and which satisfies the recursive Tarskian truth conditions. But nothing prevents having some non-definable class that is such a truth predicate, and that is our situation here in KM.
Although the arguments here show that KM is strictly stronger than ZFC in consistency strength, it is not really very much stronger, since if $\kappa$ is an inaccessible cardinal, then it is not difficult to argue in ZFC that $\langle V_\kappa,\in,V_{\kappa+1}\rangle$ is a model of KM. Indeed, there will be many smaller models of KM, and so the consistency strength of KM lies strictly between that of ZFC, above much of the iterated consistency hierarchy, but below that of ZFC plus an inaccessible cardinal.
_croped.jpg){kind=link}