Tag Archives: GBC

Open determinacy for games on the ordinals is stronger than ZFC, CUNY Logic Workshop, October 2015

Posted on by
1

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:

 

 

Open determinacy for class games

Posted on by
7

[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:

 

Determinacy for proper-class clopen games is equivalent to transfinite recursion along proper-class well-founded relations

Posted on by
5

The Infinite Combat - Philipp Klinger

I’d like to continue a bit further my exploration of some principles of determinacy for proper-class games; it turns out that these principles have a surprising set-theoretic strength.  A few weeks ago, I explained that the determinacy of proper-class open games and even clopen games implies Con(ZFC) and much more.  Today, I’d like to prove that clopen determinacy is exactly equivalent over GBC to the principle of transfinite recursion along proper-class well-founded relations.  Thus, GBC plus either of these principles is a strictly intermediate set theory between GBC and KM.

The principle of clopen determinacy for class games is the assertion that in any two-player infinite game of perfect information whose winning condition is a clopen class, there is a winning strategy for one of the players. Players alternately play moves in a playing space $X$, thereby creating a particular play $\vec a\in X^\omega$, and the winner is determined according to whether $\vec a$ is in a certain fixed payoff class $U\subset X^\omega$ or not. One has an open game when this winning condition class $U$ is open in the product topology (using the discrete topology on $X$). A game is open for a player if and only if every winning play for that player has an initial segment, all of whose extensions are also winning for that player. So the game is won for an open player at a finite stage of play. A clopen game, in contrast, has a payoff set that is open for both players. Clopen games can be equivalently cast in terms of the game tree, consisting of positions in the game where the winner is not yet determined, and where play terminates when the winner is known. Namely, a game is clopen exactly when this game tree is well-founded, so that in every play, the outcome is known already at a finite stage.

A strategy is a class function $\sigma:X^{<\omega}\to X$ that instructs the player what to play next, given a position of partial play, and the strategy is winning for a player if all plays that accord with it satisfy the winning condition for that player.

The principle of transfinite recursion along well-founded class relations is the assertion that we may undertake recursive definitions along any class well-founded partial order relation. That is, suppose that $\lhd$ is a class well-founded partial order relation on a class $A$, and suppose that $\varphi(F,a,y)$ is a formula, using only first-order quantifiers but having a class variable $F$, which is functional in the sense that for any class $F$ and any set $a\in A$ there is a unique $y$ such that $\varphi(F,a,y)$. The idea is that $\varphi(F,a,y)$ expresses the recursive rule to be iterated, and a solution of the recursion is a class function $F$ such that $\varphi(F\upharpoonright a,a,F(a))$ holds for every $a\in A$, where $F\upharpoonright a$ means the restriction of $F$ to the class $\{ b\in A\mid b\lhd a\}$. Thus, the value $F(a)$ is determined by the class of previous values $F(b)$ for $b\lhd a$. The principle of transfinite recursion along class well-founded relations is the assertion scheme that for every such well-founded partial order class $\langle A,\lhd\rangle$ and any recursive rule $\varphi$ as above, there is a solution.

In the case that the relation $\lhd$ is set-like, which means that the predecessors $\{b\mid b\lhd a\}$ of any point $a$ form a set (rather than a proper class), then GBC easily proves that there is a unique solution class, which furthermore is definable from $\lhd$. Namely, one can show that every $a\in A$ has a partial solution that obeys the recursive rule at least up to $a$, and furthermore all such partial solutions agree below $a$, because there can be no $\lhd$-minimal violation of this. It follows that the class function $F$ unifying these partial solutions is a total solution to the recursion. Similarly, GBC can prove that there are solutions to other transfinite recursion instances where the well-founded relation is not necessarily set-like, such as a recursion of length $\text{Ord}+\text{Ord}$ or even much longer.

Meanwhile, if GBC is consistent, then it cannot in general prove that transfinite recursions along non-set-like well-founded relations always succeed, since this principle would imply that there is a truth-predicate for first-order truth, as the Tarskian conditions are precisely such a recursion on a well-founded relation based on the complexity of formulas. (That relation is not set-like, since when considering the truth of $\exists x\,\psi(x,\vec a)$, we want to consider the truth of $\psi(b,\vec a)$ for any parameter $b$, and there are a proper class of such $b$.) Thus, GBC plus transfinite recursion (or plus clopen determinacy) is strictly stronger than GBC, although it is provable in Kelley-Morse set theory KM essentially the same as GBC proves the set-like special case.

Theorem. Assume GBC. Then the following are equivalent.

  1. Clopen determinacy for class games. That is, for any two-player game of perfect information whose payoff class is both open and closed, there is a winning strategy for one of the players.
  2. Transfinite recursion for proper class well-founded relations (not necessarily set-like).

Proof. ($2\to 1$) Assume the principle of transfinite recursion for proper class well-founded relations, and suppose we are faced with a clopen game. Consider the game tree $T$, consisting of positions arising during play, up to the moment that a winner is known. This tree is well-founded because the game is clopen. Let us label the terminal nodes of the tree with I or II according to who has won the game in that position, and more generally, let us label all the nodes of the tree with I or II according to the following transfinite recursion: if a node has I to play, then it will have label I if there is a move to a node labeled I, and otherwise II; and similarly when it is II to play. By the principle of transfinite recursion, there is a labeling of the entire tree that accords with this recursive rule. It is now easy to see that if the initial node is labeled with I, then player I has a winning strategy, which is simply to stay on the nodes labeled I. Note that player II cannot play in one move from a node labeled I to one labeled II. Similarly, if the initial node is labeled II, then player II has a winning strategy; and so the game is determined, as desired.

($1\to 2$) Conversely, let us assume the principle of clopen determinacy for class games. Suppose we are faced with a recursion along a class relation $\lhd$ on a class $A$, using a recursion rule $\varphi(F,a,y)$. We shall define a certain clopen game, and prove that any winning strategy for this game will produce a solution for the recursion.

It will be convenient to assume that $\varphi(F,a,y)$ is strongly functional, meaning that not only does it define a function as we have mentioned in $V$, but also that $\varphi(F,a,y)$ defines a function $(F,a)\mapsto y$ when used over any model $\langle V_\theta,\in,F\rangle$ for any class $F\subset V_\theta$. The strongly functional property can be achieved simply by replacing the formula with the assertion that $\varphi(F,a,y)$, if $y$ is unique such that this holds, and otherwise $y=\emptyset$.

At first, let us consider a slightly easier game, which will be open rather than clopen; a bit later, we shall revise this game to a clopen game. The game is the recursion game, which will be very much like the truth-telling game of my previous post, Open determinacy for proper class games implies Con(ZFC) and much more. Namely, we have two players, the challenger and the truth-teller. The challenger will issues challenges about truth in a structure $\langle V,\in,\lhd,F\rangle$, where $\lhd$ is the well-founded class relation and $F$ is a class function, not yet specified. Specifically, the challenger is allowed to ask about the truth of any formula $\varphi(\vec a)$ in this structure, and to inquire as to the value of $F(a)$ for any particular $a$. The truth-teller, as before, will answer the challenges by saying either that $\varphi(\vec a)$ is true or false, and in the case $\varphi(\vec a)=\exists x\,\psi(x,\vec a)$ and the formula was declared true, by also giving a witness $b$ and declaring $\psi(b,\vec a)$ is true; and the truth-teller must specify a specific value for $F(a)$ for any particular $a$. The truth-teller loses immediately, if she should ever violate Tarski’s recursive definition of truth; and she also loses unless she declares the recursive rules $\varphi(F\upharpoonright a,a,F(a))$ to be true. Since these violations occur at a finite stage of play if they do at all, the game is open for the challenger.

Lemma. The challenger has no winning strategy in the recursion game.

Proof. Suppose that $\sigma$ is a strategy for the challenger. So $\sigma$ is a class function that instructs the challenger how to play next, given a position of partial play. By the reflection theorem, there is an ordinal $\theta$ such that $V_\theta$ is closed under $\sigma$, and using the satisfaction class that comes from clopen determinacy, we may actually also arrange that $\langle V_\theta,\in,\lhd\cap V_\theta,\sigma\cap V_\theta\rangle\prec\langle V,\in,\lhd,\sigma\rangle$. Consider the relation $\lhd\cap V_\theta$, which is a well-founded relation on $A\cap V_\theta$. The important point is that this relation is now a set, and in GBC we may certainly undertake transfinite recursions along well-founded set relations. Thus, there is a function $f:A\cap V_\theta\to V_\theta$ such that $\langle V_\theta,\in,f\rangle$ satisfies $\varphi(f\upharpoonright a,a,f(a))$ for all $a\in V_\theta$, where $f\upharpoonright a$ means restricting $f$ to the predecessors of $a$ in $V_\theta$, and this may not be all the predecessors of $a$ with respect to $\lhd$, which may not be set-like. Note that this is the place where we use our assumption that $\varphi$ was strongly functional, since we want to ensure that it can still be used to define a valid recursion over $\lhd\cap V_\theta$. (We are not claiming that $\langle V_\theta,\in,\lhd\cap V_\theta,f\rangle$ models $\text{ZFC}(\lhd,f)$.)

Consider now the play of the recursion game in $V$, where the challenger uses the strategy $\sigma$ and the truth-teller plays in accordance with $\langle V_\theta,\in,\lhd\cap V_\theta,f\rangle$. Since $V_\theta$ was closed under $\sigma$, the challenger will never issue challenges outside of $V_\theta$. And since the function $f$ fulfills the recursion $\varphi(f\upharpoonright a,a,f(a))$ in this structure, the truth-teller will not be trapped in any violation of the Tarski conditions or the recursion condition. Thus, the truth-teller will win this instance of the game, and so $\sigma$ was not a winning strategy for the challenger, as desired. QED

Lemma. The truth-teller has a winning strategy in the recursion game if and only if there is a solution of the recursion.

Proof. If there is a solution $F$ of the recursion, then by clopen determinacy, we also get a satisfaction class for the structure $\langle V,\in,\lhd,F\rangle$, and the truth-teller can answer all queries of the challenger by referring to what is actually true in this structure. This will be winning for the truth-teller, since the actual truth obeys the Tarskian conditions and the recursive rule.

Conversely, suppose that $\tau$ is a winning strategy for the truth-teller in the recursion game. We claim that the truth assertions made by $\tau$ do not depend on the order in which challenges are made by the challenger; they all cohere with one another. This is easy to see for formulas not involving $F$ by induction on formulas, for if the truth of a formula $\psi(\vec a)$ is independent of play, then also the truth of $\neg\psi(\vec a)$ is as well, and similarly if $\exists x\psi(x,\vec a)$ is declared true with witness $\psi(b,\vec a)$, then by induction $\psi(b,\vec a)$ is independent of the play, in which case $\exists x\psi(x,\vec a)$ must always be declared true by $\tau$ independently of the order of play by the challenger (although the particular witness $b$ provided by $\tau$ may depend on the play). Now, let us also argue that the values of $F(a)$ declared by $\tau$ are also independent of the order of play. If not, there is some $\lhd$-least $a$ where this fails. (Note that such an $a$ exists, since $\tau$ is a class, and we can define from $\tau$ the class of $a$ for which the value of $F(a)$ declared by $\tau$ depends on the order of play; without $\tau$, one might have expected to need $\Pi^1_1$-comprehension to find a minimal $a$ where the recursion fails.) As in the truth-telling game, the truth assertions made by $\tau$ about $\langle V,\in,\lhd,F\upharpoonright a\rangle$, where $F\upharpoonright a$ is the class function of values that are determined by $\tau$ on $b\lhd a$, must not depend on the order of play. Since the recursion rule $\varphi(F\upharpoonright a,a,y)$ is functional, there is only one value $y=F(a)$ for which this formula can be truthfully held, and so if some play causes $\tau$ to play a different value for $F(a)$, the challenger can in finitely many additional moves (bounded by the syntactic complexity of $\varphi$) trap the truth-teller in a violation of the Tarskian conditions or the recursion condition. Thus, the values of $F(a)$ declared by $\tau$ must in fact all cohere independently of the order of play, and so $\tau$ is describing a class function $F:A\to V$ such that $\varphi(F\upharpoonright a,a,F(a))$ is true for every $a\in A$. So the recursion has a solution, as desired. QED

So far, we have established that the principle of open determinacy implies the principle of transfinite recursion along well-founded class relations. In order to improve this implication to use only clopen determinacy rather than open determinacy, we modify the game to become a clopen game rather than an open game.

Consider the clopen form of the recursion game, where we insist also that the challenger announce on the first move a natural number $n$, such that the challenger loses if the truth-teller survives for at least $n$ moves. This is now a clopen game, since the winner will be known by that time, either because the truth-teller will violate the Tarski conditions or the recursion condition, or else the challenger’s limit on play will expire.

Since the modified version of the game is even harder for the challenger, there can still be no winning strategy for the challenger. So by the principle of clopen determinacy, there is a winning strategy $\tau$ for the truth-teller. This strategy is allowed to make decisions based on the number $n$ announced by the challenger on the first move, and it will no longer necessarily be the case that the theory declared true by $\tau$ will be independent of the order of play. Nevertheless, it will be the case, we claim, that the theory declared true by $\tau$ for all plays with sufficiently large $n$ (and with sufficiently many remaining moves) will be independent of the order of play. One can see this by observing that if an assertion $\psi(\vec a)$ is independent in this sense, then also $\neg\psi(\vec a)$ will be independent in this sense, for otherwise there would be plays with large $n$ giving different answers for $\neg\psi(\vec a)$ and we could then challenge with $\psi(\vec a)$, which would have to give different answers or else $\tau$ would not win. Similarly, since $\tau$ is winning, one can see that allowing the challenger to specify a bound on the total length of play does not prevent the arguments above showing that $\tau$ describes a coherent solution function $F:A\to V$ satisfying the recursion $\varphi(F\upharpoonright a,a,F(a))$, provided that one looks only at plays in which there are sufficiently many moves remaining. There cannot be a $\lhd$-least $a$ where the value of $F(a)$ is not determined in this sense, and so on as before.

Thus, we have proved that the principle of clopen determinacy for class games is equivalent to the principle of transfinite recursion along well-founded class relations. QED

The material in this post will become part of a joint project with Victoria Gitman and Thomas Johnstone. We are currently investigating several further related issues.

Open determinacy for proper class games implies Con(ZFC) and much more

Posted on by
5

1000px-Apollonian_gasket.svg

$\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!

Kelley-Morse set theory implies Con(ZFC) and much more

Posted on by
23

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.