Upward closure and amalgamation in the generic multiverse of a countable model of set theory

Posted on by
7

[bibtex key=Hamkins2016:UpwardClosureAndAmalgamationInTheGenericMultiverse]

Abstract. I prove several theorems concerning upward closure and amalgamation in the generic multiverse of a countable transitive model of set theory. Every such model $W$ has forcing extensions $W[c]$ and $W[d]$ by adding a Cohen real, which cannot be amalgamated in any further extension, but some nontrivial forcing notions have all their extensions amalgamable. An increasing chain $W[G_0]\subseteq W[G_1]\subseteq\cdots$ has an upper bound $W[H]$ if and only if the forcing had uniformly bounded essential size in $W$. Every chain $W\subseteq W[c_0]\subseteq W[c_1]\subseteq \cdots$ of extensions adding Cohen reals is bounded above by $W[d]$ for some $W$-generic Cohen real $d$.

This article is based upon I talk I gave at the conference on Recent Developments in Axiomatic Set Theory at the Research Institute for Mathematical Sciences (RIMS) at Kyoto University, Japan in September, 2015, and I am extremely grateful to my Japanese hosts, especially Toshimichi Usuba, for supporting my research visit there and also at the CTFM conference at Tokyo Institute of Technology just preceding it. This article includes material adapted from section section 2 of Set-theoretic geology, joint with G. Fuchs, myself and J. Reitz, and also includes a theorem that was proved in a series of conversations I had with Giorgio Venturi at the Young Set Theory Workshop 2011 in Bonn and continuing at the London 2011 summer school on set theory at Birkbeck University London.

The rearrangement number: how many rearrangements of a series suffice to verify absolute convergence? Vassar Math Colloquium, November 2015

Posted on by
3

This will be a talk for the Mathematics Colloquium at Vassar College, November 10, 2015, tea at 4:00 pm, talk at 4:15 pm, Rockefeller Hall 310

Abstract. The Riemann rearrangement theorem asserts that a series $\sum_n a_n$ is absolutely convergent if and only if every rearrangement $\sum_n a_{p(n)}$ of it is convergent, and furthermore, any conditionally convergent series can be rearranged so as to converge to any desired extended real value. How many rearrangements $p$ suffice to test for absolute convergence in this way? The rearrangement number, a new cardinal characteristic of the continuum introduced just recently, is the smallest size of a family of permutations, such that whenever the convergence and value of a convergent series is invariant by all these permutations, then it is absolutely convergent. The exact value of the rearrangement number turns out to be independent of the axioms of set theory. In this talk, I shall place the rearrangement number into a discussion of cardinal characteristics of the continuum, including an elementary introduction to the continuum hypothesis and an account of Freiling’s axiom of symmetry.

This talk is based in part on current joint work with Andreas Blass, Will Brian, myself, Michael Hardy and Paul Larson.

My Lecture Notes are available. 

A position in infinite chess with game value $\omega^4$

Posted on by
17

[bibtex key=EvansHamkinsPerlmutter2017:APositionInInfiniteChessWithGameValueOmega^4]

Abstract.  We present a position in infinite chess exhibiting an ordinal game value of $\omega^4$, thereby improving on the previously largest-known values of $\omega^3$ and $\omega^3\cdot 4$.

This is a joint work with Cory Evans and Norman Perlmutter, continuing the research program of my previous article with Evans, Transfinite game values in infinite chess, namely, the research program of finding positions in infinite chess with large transfinite ordinal game values. In the previous article, Cory and I presented a position with game value $\omega^3$. In the current paper, with Norman Perlmutter now having joined us accompanied by some outstanding ideas, we present a new position having game value $\omega^4$, breaking the previous record.

Full position value omega^4

A position in infinite chess with value $\omega^4$

In the new position, above, the kings sit facing each other in the throne room, an uneasy détente, while white makes steady progress in the rook towers. Meanwhile, at every step black, doomed, mounts increasingly desperate bouts of long forced play using the bishop cannon battery, with bishops flying with force out of the cannons, and then each making a long series of forced-reply moves in the terminal gateways. Ultimately, white wins with value omega^4, which exceeds the previously largest known values of omega^3.

In the throne room, if either black or white places a bishop on the corresponding diagonal entryway, then checkmate is very close. A key feature is that for white to place a white-square white bishop on the diagonal marked in red, it is immediate checkmate, whereas if black places a black-square black bishop on the blue diagonal, then checkmate comes three moves later.  The bishop cannon battery arrangement works because black threatens to release a bishop into the free region, and if white does not reply to those threats, then black will be three steps ahead, but otherwise, only two.

           The throne room

The rook towers are similar to the corresponding part of the previous $\omega^3$ position, and this is where white undertakes most of his main line progress towards checkmate.  Black will move the key bishop out as far as he likes on the first move, past $n$ rook towers, and the resulting position will have value $\omega^3\cdot n$.  These towers are each activated in turn, leading to a long series of play for white, interrupted at every opportunity by black causing a dramatic spectacle of forced-reply moves down in the bishop cannon battery.

Rook towers

            The rook towers

At every opportunity, black mounts a long distraction down in the bishop cannon battery.  Shown here is one bishop cannon. The cannonballs fire out of the cannon with force, in the sense that when each green bishop fires out, then white must reply by moving the guard pawns into place.

Bishop cannon

Bishop cannon

Upon firing, each bishop will position itself so as to attack the entrance diagonal of a long bishop gateway terminal wing.  This wing is arranged so that black can make a series of forced-reply threats successively, by moving to the attack squares (marked with the blue squares). Black is threatening to exit through the gateway doorway (in brown), but white can answer the threat by moving the white bishop guards (red) into position. Thus, each bishop coming out of a cannon (with force) can position itself at a gateway terminal of length $g$, making $g$ forced-reply moves in succession.  Since black can initiate firing with an arbitrarily large cannon, this means that at any moment, black can cause a forced-reply delay with game value $\omega^2$. Since the rook tower also has value $\omega^2$ by itself, the overall position has value $\omega^4=\omega^2\cdot\omega^2$.

Bishop gateway terminal wing

With future developments in mind, we found that one can make a more compact arrangement of the bishop cannon battery, freeing up a quarter board for perhaps another arrangement that might lead to a higher ordinal values.

Alternative compact version of bishop cannon battery

Read more about it in the article, which is available at the arxiv (pdf).

See also:

The rearrangement number, CUNY set theory seminar, November 2015

Posted on by
3

This will be a talk for the CUNY Set Theory Seminar on November 6, 2015.

The Riemann rearrangement theorem states that a convergent real series $\sum_n a_n$ is absolutely convergent if and only if the value of the sum is invariant under all rearrangements $\sum_n a_{p(n)}$ by any permutation $p$ on the natural numbers; furthermore, if the series is merely conditionally convergent, then one may find rearrangements for which the new sum $\sum_n a_{p(n)}$ has any desired (extended) real value or which becomes non-convergent.  In recent joint work with Andreas Blass, Will Brian, myself, Michael Hardy and Paul Larson, based on an exchange in reply to a Hardy’s MathOverflow question on the topic, we investigate the minimal size of a family of permutations that can be used in this manner to test an arbitrary convergent series for absolute convergence.

Specifically, we define the rearrangement number $\newcommand\rr{\mathfrak{rr}}\rr$ (“double-r”), a new cardinal characteristic of the continuum, to be the smallest cardinality of a set $P$ of permutations of the natural numbers, such that if a convergent real series $\sum_n a_n$ remains convergent and with the same sum after all rearrangements $\sum_n a_{p(n)}$ by a permutation $p\in P$, then it is absolutely convergent. The corresponding rearrangement number for sums, denoted $\newcommand\rrsum{\rr_{\scriptscriptstyle\Sigma}}
\rrsum$, is the smallest cardinality of a family $P$ of permutations, such that if a series $\sum_n a_n$ is conditionally convergent, then there is a rearrangement $\sum_n a_{p(n)}$, by some permutation $p \in P$, which converges to a different sum. We investigate the basic properties of these numbers, and explore their relations with other cardinal characteristics of the continuum. Our main results are that $\mathfrak{b}\leq\rr\leq\mathop{\bf non}(\mathcal{M})$, that $\mathfrak{d}\leq \rrsum$, and that $\mathfrak{b}<\rr$ is relatively consistent.

MathOverflow question | CUNY Set Theory Seminar

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:

 

 

Being HOD-of-a-set is invariant throughout the generic multiverse

Posted on by
2

Iowa State Capitol - Law Library _ Flickr - Photo Sharing!$\newcommand\HOD{\text{HOD}}$The axiom $V=\HOD$, introduced by Gödel, asserts that every set is ordinal definable. This axiom has a subtler foundational aspect than might at first be expected. The reason is that the general concept of “object $x$ is definable using parameter $p$” is not in general first-order expressible in set theory; it is of course a second-order property, which makes sense only relative to a truth predicate, and by Tarski’s theorem, we can have no first-order definable truth predicate. Thus, the phrase “definable using ordinal parameters” is not directly meaningful in the first-order language of set theory without further qualification or explanation. Fortunately, however, it is a remarkable fact that when we allow definitions to use arbitrary ordinal parameters, as we do with $\HOD$, then we can in fact make such qualifications in such a way that the axiom becomes first-order expressible in set theory. Specifically, we say officially that $V=\HOD$ holds, if for every set $x$, there is an ordinal $\theta$ with $x\in V_\theta$, for which which $x$ is definable by some formula $\psi(x)$ in the structure $\langle V_\theta,{\in}\rangle$ using ordinal parameters. Since $V_\theta$ is a set, we may freely make reference to first-order truth in $V_\theta$ without requiring any truth predicate in $V$. Certainly any such $x$ as this is also ordinal-definable in $V$, since we may use $\theta$ and the Gödel-code of $\psi$ also as parameters, and note that $x$ is the unique object such that it is in $V_\theta$ and satisfies $\psi$ in $V_\theta$. (Note that inside an $\omega$-nonstandard model of set theory, we may really need to use $\psi$ as a parameter, since it may be nonstandard, and $x$ may not be definable in $V_\theta$ using a meta-theoretically standard natural number; but fortunately, the Gödel code of a formula is an integer, which is still an ordinal, and this issue is the key to the issue.) Conversely, if $x$ is definable in $V$ using formula $\varphi(x,\vec\alpha)$ with ordinal parameters $\vec\alpha$, then it follows by the reflection theorem that $x$ is defined by $\varphi(x,\vec\alpha)$ inside some $V_\theta$. So this formulation of $V=HOD$ is expressible and exactly captures the desired second-order property that every set is ordinal-definable.

Consider next the axiom $V=\HOD(b)$, asserting that every set is definable from ordinal parameters and parameter $b$. Officially, as before, $V=\HOD(b)$ asserts that for every $x$, there is an ordinal $\theta$, formula $\psi$ and ordinals $\vec \alpha<\theta$, such that $x$ is the unique object in $V_\theta$ for which $\langle V_\theta,{\in}\rangle\models\psi(x,\vec\alpha,b)$, and the reflection argument shows again that this way of defining the axiom exactly captures the intended idea.

The axiom I actually want to focus on is $\exists b\,\left( V=\HOD(b)\right)$, asserting that the universe is $\HOD$ of a set. (I assume ZFC in the background theory.) It turns out that this axiom is constant throughout the generic multiverse.

Theorem. The assertion $\exists b\, (V=\HOD(b))$ is forcing invariant.

  • If it holds in $V$, then it continues to hold in every set forcing extension of $V$.
  • If it holds in $V$, then it holds in every ground of $V$.

Thus, the truth of this axiom is invariant throughout the generic multiverse.

Proof. Suppose that $\text{ZFC}+V=\HOD(b)$, and $V[G]$ is a forcing extension of $V$ by generic filter $G\subset\mathbb{P}\in V$. By the ground-model definability theorem, it follows that $V$ is definable in $V[G]$ from parameter $P(\mathbb{P})^V$. Thus, using this parameter, as well as $b$ and additional ordinal parameters, we can define in $V[G]$ any particular object in $V$. Since this includes all the $\mathbb{P}$-names used to form $V[G]$, it follows that $V[G]=\HOD(b,P(\mathbb{P})^V,G)$, and so $V[G]$ is $\HOD$ of a set, as desired.

Conversely, suppose that $W$ is a ground of $V$, so that $V=W[G]$ for some $W$-generic filter $G\subset\mathbb{P}\in W$, and $V=\HOD(b)$ for some set $b$. Let $\dot b$ be a name for which $\dot b_G=b$. Every object $x\in W$ is definable in $W[G]$ from $b$ and ordinal parameters $\vec\alpha$, so there is some formula $\psi$ for which $x$ is unique such that $\psi(x,b,\vec\alpha)$. Thus, there is some condition $p\in\mathbb{P}$ such that $x$ is unique such that $p\Vdash\psi(\check x,\dot b,\check{\vec\alpha})$. If $\langle p_\beta\mid\beta<|\mathbb{P}|\rangle$ is a fixed enumeration of $\mathbb{P}$ in $W$, then $p=p_\beta$ for some ordinal $\beta$, and we may therefore define $x$ in $W$ using ordinal parameters, along with $\dot b$ and the fixed enumeration of $\mathbb{P}$. So $W$ thinks the universe is $\HOD$ of a set, as desired.

Since the generic multiverse is obtained by iteratively moving to forcing extensions to grounds, and each such movement preserves the axiom, it follows that $\exists b\, (V=\HOD(b))$ is constant throughout the generic multiverse. QED

Theorem. If $V=\HOD(b)$, then there is a forcing extension $V[G]$ in which $V=\HOD$ holds.

Proof. We are working in ZFC. Suppose that $V=\HOD(b)$. We may assume $b$ is a set of ordinals, since such sets can code any given set. Consider the following forcing iteration: first add a Cohen real $c$, and then perform forcing $G$ that codes $c$, $P(\omega)^V$ and $b$ into the GCH pattern at uncountable cardinals, and then perform self-encoding forcing $H$ above that coding, coding also $G$ (see my paper on Set-theoretic geology for further details on self-encoding forcing). In the final model $V[c][G][H]$, therefore, the objects $c$, $b$, $P(\omega)^V$, $G$ and $H$ are all definable without parameters. Since $V\subset V[c][G][H]$ has a closure point at $\omega$, it satisfies the $\omega_1$-approximation and cover properties, and therefore the class $V$ is definable in $V[c][G][H]$ using $P(\omega)^V$ as a parameter. Since this parameter is itself definable without parameters, it follows that $V$ is parameter-free definable in $V[c][G][H]$. Since $b$ is also definable there, it follows that every element of $\HOD(b)^V=V$ is ordinal-definable in $V[c][G][H]$. And since $c$, $G$ and $H$ are also definable without parameters, we have $V[c][G][H]\models V=\HOD$, as desired. QED

Corollary. The following are equivalent.

  1. The universe is $\HOD$ of a set: $\exists b\, (V=\HOD(b))$.
  2. Somewhere in the generic multiverse, the universe is $\HOD$ of a set.
  3. Somewhere in the generic multiverse, the axiom $V=\HOD$ holds.
  4. The axiom $V=\HOD$ is forceable.

Proof. This is an immediate consequence of the previous theorems. $1\to 4\to 3\to 2\to 1$. QED

Corollary. The axiom $V=\HOD$, if true, even if true anywhere in the generic multiverse, is a switch.

Proof. A switch is a statement such that both it and its negation are necessarily possible by forcing; that is, in every set forcing extension, one can force the statement to be true and also force it to be false. We can always force $V=\HOD$ to fail, simply by adding a Cohen real. If $V=\HOD$ is true, then by the first theorem, every forcing extension has $V=\HOD(b)$ for some $b$, in which case $V=\HOD$ remains forceable, by the second theorem. QED

Quoted in New York magazine: The Chalk for Math Professors

Posted on by
8

The Chalk for Math Professors: Hagoromo Fulltouch, by Alex Ronan for the current issue of New York magazine, part of the Status Survey on various items for professionals.

The smooth texture flows so easily across the chalkboard like a fountain pen … One puts up mathematics on the chalkboard as if tracing out an idea in the air.

Meanwhile, I happened to be at a conference at the Research Institute for Mathematical Sciences in Kyoto last week, and I gave my talk using the chalkboard and the plentiful supply of Hagoromo chalk provided there.

Chalk1 chalk2

 

 

 

 

 

 

 

 

Related MathOverflow post.

Different models of set theory with the same subset relation

Posted on by
11

OkonomiyakiRecently Makoto Kikuchi (Kobe University) asked me the following interesting question, which arises very naturally if one should adopt a mereological perspective in the foundations of mathematics, placing a focus on the parthood relation rather than the element-of relation. In set theory, this perspective would lead one to view the subset or inclusion relation $\subseteq$ as the primary fundamental relation, rather than the membership $\in$ relation.

Question. Can there be two different models of set theory, with the same inclusion relation?

We spent an evening discussing it, over delicious (Rokko-michi-style) okonomiyaki and bi-ru, just like old times, except that we are in Tokyo at the CTFM 2015, and I’d like to explain the answer, which is yes, this always happens in every model of set theory.

Theorem. In any universe of set theory $\langle V,\in\rangle$, there is a definable relation $\in^*$, different from $\in$, such that $\langle V,\in^*\rangle$ is a model of set theory, in fact isomorphic to the original universe $\langle V,\in\rangle$, for which the corresponding inclusion relation $$u\subseteq^* v\iff \forall a\, (a\in^* u\to a\in^* v)$$ is identical to the usual inclusion relation $u\subseteq v$.

Proof. Let $\theta:V\to V$ be any definable non-identity permutation of the universe, and let $\tau:u\mapsto \theta[u]=\{\ \theta(a)\mid a\in u\ \}$ be the function determined by pointwise image under $\theta$. Since $\theta$ is bijective, it follows that $\tau$ is also a bijection of $V$ to $V$, since every set is the $\theta$-image of a unique set. Furthermore, $\tau$ is an automorphism of $\langle V,\subseteq\rangle$, since $$u\subseteq v\iff\theta[u]\subseteq\theta[v]\iff\tau(u) \subseteq\tau(v).$$ I had used this idea a few years ago in my answer to the MathOverflow question, Is the inclusion version of Kunen inconsistency theorem true?, which shows that there are nontrivial $\subseteq$ automorphisms of the universe. Note that since $\tau(\{a\})=\{\theta(a)\}$, it follows that any instance of nontriviality $\theta(a)\neq a$ in $\theta$ leads immediately to an instance of nontriviality in $\tau$.

Using the map $\tau$, define $a\in^* b\iff\tau(a)\in\tau(b)$. By definition, therefore, $\tau$ is an isomorphism of $\langle V,\in^*\rangle\cong\langle V,\in\rangle$. Let us show that $\in^*\neq \in$. Since $\theta$ is nontrivial, there is an $\in$-minimal set $a$ with $\theta(a)\neq a$. By minimality, $\theta[a]=a$ and so $\tau(a)=a$. But as mentioned, $\tau(\{a\})=\{\theta(a)\}\neq\{a\}$. So we have $a\in\{a\}$, but $\tau(a)=a\notin\{\theta(a)\}=\tau(\{a\})$ and hence $a\notin^*\{a\}$. So the two relations are different.

Meanwhile, consider the corresponding subset relation. Specifically, $u\subseteq^* v$ is defined to mean $\forall a\,(a\in^* u\to a\in^* v)$, which holds if and only if $\forall a\, (\tau(a)\in\tau(u)\to \tau(a)\in\tau(v))$; but since $\tau$ is surjective, this holds if and only if $\tau(u)\subseteq \tau(v)$, which as we observed at the beginning of the proof, holds if and only if $u\subseteq v$. So the corresponding subset relations $\subseteq^*$ and $\subseteq$ are identical, as desired.

Another way to express what is going on is that $\tau$ is an isomorphism of the structure $\langle V,{\in^*},{\subseteq}\rangle$ with $\langle V,{\in},{\subseteq}\rangle$, and so $\subseteq$ is in fact that same as the corresponding inclusion relation $\subseteq^*$ that one would define from $\in^*$. QED

Corollary. One cannot define $\in$ from $\subseteq$ in a model of set theory.

Proof. The map $\tau$ is a $\subseteq$-automorphism, and so it preserves every relation definable from $\subseteq$, but it does not preserve $\in$. QED

Nevertheless, I claim that the isomorphism type of $\langle V,\in\rangle$ is implicit in the inclusion relation $\subseteq$, in the sense that any other class relation $\in^*$ having that same inclusion relation is isomorphic to the $\in$ relation.

Theorem. Assume ZFC in the universe $\langle V,\in\rangle$. Suppose that $\in^*$ is a class relation for which $\langle V,\in^*\rangle$ is a model of set theory (a weak set theory suffices), such that the corresponding inclusion relation $$u\subseteq^* v\iff\forall a\,(a\in^* u\to a\in^* v)$$is the same as the usual inclusion relation $u\subseteq v$. Then the two membership relations are isomorphic $$\langle V,\in\rangle\cong\langle V,\in^*\rangle.$$

Proof. Since the singleton set $\{a\}$ has exactly two subsets with respect to the usual $\subseteq$ relation — the empty set and itself — this must also be true with respect to the inclusion relation $\subseteq^*$ defined via $\in^*$, since we have assumed $\subseteq^*=\subseteq$. Thus, the object $\{a\}$ is also a singleton with respect to $\in^*$, and so there is a unique object $\eta(a)$ such that $x\in^* a\iff x=\eta(a)$. By extensionality and since every object has its singleton, it follows that $\eta:V\to V$ is both one-to-one and onto. Let $\theta=\eta^{-1}$ be the inverse permutation.

Observe that $a\in u\iff \{a\}\subseteq u\iff \{a\}\subseteq^* u\iff\eta(a)\in^* u$. Thus, $$b\in^* u\iff \theta(b)\in u.$$

Using $\in$-recursion, define $b^*=\{\ \theta(a^*)\mid a\in b\ \}$. The map $b\mapsto b^*$ is one-to-one by $\in$-recursion, since if there is no violation of this for the elements of $b$, then we may recover $b$ from $b^*$ by applying $\theta^{-1}$ to the elements of $b^*$ and then using the induction assumption to find the unique $a$ from $a^*$ for each $\theta(a^*)\in b^*$, thereby recovering $b$. So $b\mapsto b^*$ is injective.

I claim that this map is also surjective. If $y_0\neq b^*$ for any $b$, then there must be an element of $y_0$ that is not of the form $\theta(b^*)$ for any $b$. Since $\theta$ is surjective, this means there is $\theta(y_1)\in y_0$ with $y_1\neq b^*$ for any $b$. Continuing, there is $y_{n+1}$ with $\theta(y_{n+1})\in y_n$ and $y_{n+1}\neq b^*$ for any $b$. Let $z=\{\ \theta(y_n)\mid n\in\omega\ \}$. Since $x\in^* u\iff \theta(x)\in u$, it follows that the $\in^*$-elements of $z$ are precisely the $y_n$’s. But $\theta(y_{n+1})\in y_n$, and so $y_{n+1}\in^* y_n$. So $z$ has no $\in^*$-minimal element, violating the axiom of foundation for $\in^*$, a contradiction. So the map $b\mapsto b^*$ is a bijection of $V$ with $V$.

Finally, we observe that because $$a\in b\iff\theta(a^*)\in b^*\iff a^*\in^* b^*,$$ it follows that the map $b\mapsto b^*$ is an isomorphism of $\langle V,\in\rangle$ with $\langle V,\in^*\rangle$, as desired. QED

The conclusion is that although $\in$ is not definable from $\subseteq$, nevertheless, the isomorphism type of $\in$ is implicit in $\subseteq$, in the sense that any other class relation $\in^*$ giving rise to the same inclusion relation $\subseteq^*=\subseteq$ is isomorphic to $\in$.

Meanwhile, I do not yet know what the situation is when one drops the assumption that $\in^*$ is a class with respect to the $\langle V,\in\rangle$ universe.

Question. Can there be two models of set theory $\langle M,\in\rangle$ and $\langle M,\in^*\rangle$, not necessarily classes with respect to each other, which have the same inclusion relation $\subseteq=\subseteq^*$, but which are not isomorphic?

(This question is now answered! See my joint paper with Kikuchi at Set-theoretic mereology.)

Upward countable closure in the generic multiverse of forcing to add a Cohen real

Posted on by
4

I’d like to discuss my theorem that the collection of models $M[c]$ obtained by adding an $M$-generic Cohen real $c$ over a fixed countable transitive model of set theory $M$ is upwardly countably closed, in the sense that every increasing countable chain has an upper bound.

I proved this theorem back in 2011, while at the Young Set Theory Workshop in Bonn and continuing at the London summer school on set theory, in a series of conversations with Giorgio Venturi. The argument has recently come up again in various discussions, and so let me give an account of it.

We consider the collection of all forcing extensions of a fixed countable transitive model $M$ of ZFC by the forcing to add a Cohen real, models of the form $M[c]$, and consider the question of whether every countable increasing chain of these models has an upper bound. The answer is yes!  (Actually, Giorgio wants to undertake forcing constructions by forcing over this collection of models to add a generic upward directed system of models; it follows from this theorem that this forcing is countably closed.) This theorem fits into the theme of my earlier post, Upward closure in the toy multiverse of all countable models of set theory, where similar theorems are proved, but not this one exactly.

Theorem. For any countable transitive model $M\models\text{ZFC}$, the collection of all forcing extensions $M[c]$ by adding an $M$-generic Cohen real is upward-countably closed. That is, for any countable tower of such forcing extensions
$$M[c_0]\subset M[c_1]\subset\cdots\subset M[c_n]\subset\cdots,$$
we may find an $M$-generic Cohen real $d$ such that $M[c_n]\subset M[d]$ for every natural number $n$.

Proof. $\newcommand\Add{\text{Add}}$Suppose that we have such a tower of forcing extensions $M[c_0]\subset M[c_1]\subset\cdots$, and so on. Note that if $M[b]\subset M[c]$ for $M$-generic Cohen reals $b$ and $c$, then $M[c]$ is a forcing extension of $M[b]$ by a quotient of the Cohen-real forcing. But since the Cohen forcing itself has a countable dense set, it follows that all such quotients also have a countable dense set, and so $M[c]$ is actually $M[b][b_1]$ for some $M[b]$-generic Cohen real $b_1$. Thus, we may view the tower as having the form:
$$M[b_0]\subset M[b_0\times b_1]\subset\cdots\subset M[b_0\times b_1\times\cdots\times b_n]\subset\cdots,$$
where now it follows that any finite collection of the reals $b_i$ are mutually $M$-generic.

Of course, we cannot expect in general that the real $\langle b_n\mid n<\omega\rangle$ is $M$-generic for $\Add(\omega,\omega)$, since this real may be very badly behaved. For example, the sequence of first-bits of the $b_n$’s may code a very naughty real $z$, which cannot be added by forcing over $M$ at all. So in general, we cannot allow that this sequence is added to the limit model $M[d]$. (See further discussion in my post Upward closure in the toy multiverse of all countable models of set theory.)

We shall instead undertake a construction by making finitely many changes to each real $b_n$, resulting in a real $d_n$, in such a way that the resulting combined real $d=\oplus_n d_n$ is $M$-generic for the forcing to add $\omega$-many Cohen reals, which is of course isomorphic to adding just one. To do this, let’s get a little more clear with our notation. We regard each $b_n$ as an element of Cantor space $2^\omega$, that is, an infinite binary sequence, and the corresponding filter associated with this real is the collection of finite initial segments of $b_n$, which will be an $M$-generic filter through the partial order of finite binary sequences $2^{<\omega}$, which is one of the standard isomorphic copies of Cohen forcing. We will think of $d$ as a binary function on the plane $d:\omega\times\omega\to 2$, where the $n^{th}$ slice $d_n$ is the corresponding function $\omega\to 2$ obtained by fixing the first coordinate to be $n$.

Now, we enumerate the countably many open dense subsets for the forcing to add a Cohen real $\omega\times\omega\to 2$ as $D_0$, $D_1$, and so on. There are only countably many such dense sets, because $M$ is countable. Now, we construct $d$ in stages. Before stage $n$, we will have completely specified $d_k$ for $k<n$, and we also may be committed to a finite condition $p_{n-1}$ in the forcing to add $\omega$ many Cohen reals. We consider the dense set $D_n$. We may factor $\Add(\omega,\omega)$ as $\Add(\omega,n)\times\Add(\omega,[n,\omega))$. Since $d_0\times\cdots\times d_{n-1}$ is actually $M$-generic (since these are finite modifications of the corresponding $b_k$’s, which are mutually $M$-generic, it follows that there is some finite extension of our condition $p_{n-1}$ to a condition $p_n\in D_n$, which is compatible with $d_0\times\cdots\times d_{n-1}$. Let $d_n$ be the same as $b_n$, except finitely modified to be compatible with $p_n$. In this way, our final real $\oplus_n d_n$ will contain all the conditions $p_n$, and therefore be $M$-generic for $\Add(\omega,\omega)$, yet every $b_n$ will differ only finitely from $d_n$ and hence be an element of $M[d]$. So we have $M[b_0]\cdots[b_n]\subset M[d]$, and we have found our upper bound. QED

Notice that the real $d$ we construct is not only $M$-generic, but also $M[c_n]$-generic for every $n$.

My related post, Upward closure in the toy multiverse of all countable models of set theory, which is based on material in my paper Set-theoretic geology, discusses some similar results.

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:

 

Upward closure in the generic multiverse of a countable model of set theory, RIMS 2015, Kyoto, Japan

Posted on by
Reply
Philosophers Walk Kyoto Japan (summer)This will be a talk for the conference Recent Developments in Axiomatic Set Theory at the Research Institute for Mathematical Sciences (RIMS) in Kyoto, Japan, September 16-18, 2015.

Abstract. Consider a countable model of set theory amongst its forcing extensions, the ground models of those extensions, the extensions of those models and so on, closing under the operations of forcing extension and ground model.  This collection is known as the generic multiverse of the original model.  I shall present a number of upward-oriented closure results in this context. For example, for a long-known negative result, it is a fun exercise to construct forcing extensions $M[c]$ and $M[d]$ of a given countable model of set theory $M$, each by adding an $M$-generic Cohen real, which cannot be amalgamated, in the sense that there is no common extension model $N$ that contains both $M[c]$ and $M[d]$ and has the same ordinals as $M$. On the positive side, however, any increasing sequence of extensions $M[G_0]\subset M[G_1]\subset M[G_2]\subset\cdots$, by forcing of uniformly bounded size in $M$, has an upper bound in a single forcing extension $M[G]$. (Note that one cannot generally have the sequence $\langle G_n\mid n<\omega\rangle$ in $M[G]$, so a naive approach to this will fail.)  I shall discuss these and related results, many of which appear in the “brief upward glance” section of my recent paper:  G. Fuchs, J. D. Hamkins and J. Reitz, Set-theoretic geology.


Universality and embeddability amongst the models of set theory, CTFM 2015, Tokyo, Japan

Posted on by
2

Tokyo Institute of TechnologyThis will be a talk for the Computability Theory and Foundations of Mathematics conference at the Tokyo Institute of Technology, September 7-11, 2015.  The conference is held in celebration of Professor Kazuyuki Tanaka’s 60th birthday.

Abstract. Recent results on the embeddability phenomenon and universality amongst the models of set theory are an appealing blend of ideas from set theory, model theory and computability theory. Central questions remain open.

A surprisingly vigorous embeddability phenomenon has recently been uncovered amongst the countable models of set theory. It turns out, for instance, that among these models embeddability is linear: for any two countable models of set theory, one of them embeds into the other. Indeed, one countable model of set theory $M$ embeds into another $N$ just in case the ordinals of $M$ order-embed into the ordinals of $N$. This leads to many surprising instances of embeddability: every forcing extension of a countable model of set theory, for example, embeds into its ground model, and every countable model of set theory, including every well-founded model, embeds into its own constructible universe.

V to LAlthough the embedding concept here is the usual model-theoretic embedding concept for relational structures, namely, a map $j:M\to N$ for which $x\in^M y$ if and only if $j(x)\in^N j(y)$, it is a weaker embedding concept than is usually considered in set theory, where embeddings are often elementary and typically at least $\Delta_0$-elementary. Indeed, the embeddability result is surprising precisely because we can easily prove that in many of these instances, there can be no $\Delta_0$-elementary embedding.

The proof of the embedding theorem makes use of universality ideas in digraph combinatorics, including an acyclic version of the countable random digraph, the countable random $\mathbb{Q}$-graded digraph, and higher analogues arising as uncountable Fraïssé limits, leading to the hypnagogic digraph, a universal homogeneous graded acyclic class digraph, closely connected with the surreal numbers. Thus, the methods are a blend of ideas from set theory, model theory and computability theory.

Results from Incomparable $\omega_1$-like models of set theory show that the embedding phenomenon does not generally extend to uncountable models. Current joint work of myself, Aspero, Hayut, Magidor and Woodin is concerned with questions on the extent to which the embeddings arising in the embedding theorem can exist as classes inside the models in question. Since the embeddings of the theorem are constructed externally to the model, by means of a back-and-forth-style construction, there is little reason to expect, for example, that the resulting embedding $j:M\to L^M$ should be a class in $M$. Yet, it has not yet known how to refute in ZFC the existence of a class embedding $j:V\to L$ when $V\neq L$. However, many partial results are known. For example, if the GCH fails at an uncountable cardinal, if $0^\sharp$ exists, or if the universe is a nontrivial forcing extension of some ground model, then there is no embedding $j:V\to L$. Meanwhile, it is consistent that there are non-constructible reals, yet $\langle P(\omega),\in\rangle$ embeds into $\langle P(\omega)^L,\in\rangle$.

CFTM 2015 extended abstract | Article | CFTM | Slides

Every ordinal has only finitely many order-types for its final segments

Posted on by
8

droste_effect_clock_by_kiluncle-d4ya2gnI was recently asked an interesting elementary question about the number of possible order types of the final segments of an ordinal, and in particular, whether there could be an ordinal realizing infinitely many different such order types as final segments.  Since I found it interesting, let me write here how I replied.

The person asking me had noted that every nonempty final segment of the first infinite ordinal $\omega$ is isomorphic to $\omega$ again, since if you start counting from $5$ or from a million, you have just as far to go in the natural numbers. Thus, if one includes the empty final segment, there are precisely two order-types that arise as final segments of $\omega$, namely, $0$ and $\omega$ itself. A finite ordinal $n$, in contrast, has precisely $n+1$ many final segments, corresponding to each of the possible cuts between any of the elements or before all of them or after all of them, and these final segments, considered as orders themselves, all have different sizes and hence are not isomorphic.

He wanted to know whether an ordinal could have infinitely many different order-types for its tails.

Question. Is there an ordinal having infinitely many different isomorphism types for its final segments?

The answer is no, and I’d like to explain why. I’ll discuss two different arguments, the first being an easy direct argument aimed only at this answer, and the second being a more careful analysis aimed at understanding exactly how many and which order-types arise as the order type of a final segment of an ordinal $\alpha$.

Theorem. Every ordinal has only finitely many order types of its final segments.

Proof: Suppose that $\alpha$ is an ordinal, and consider the order types of the final segments $[\eta,\alpha)$, for $\eta\leq\alpha$. Note that as $\eta$ increases, the final segment $[\eta,\alpha)$ becomes smaller as a suborder, and so it’s order type does not go up. And since these are well-orders, it can go down only finitely many times. So only finitely many order types arise, and the theorem is proved. QED

But let’s figure out exactly how many and which order types arise.

Theorem. The number of order types of final segments of an ordinal $\alpha$ is precisely $n+1$, where $n$ is the number of terms in the Cantor normal form of $\alpha$, and one can describe those order types in terms of the normal form of $\alpha$.

Cantor proved that every ordinal $\alpha$ can be uniquely expressed as a finite sum $$\alpha=\omega^{\beta_n}+\cdots+\omega^{\beta_0},$$ where $\beta_n\geq\cdots\geq\beta_0$, and this is called the Cantor normal form of the ordinal. There are alternative forms, where one allows terms like $\omega^\beta\cdot n$ for finite $n$, but in my favored formulation, one simply expands this into $n$ terms with $\omega^\beta+\cdots+\omega^\beta$. In particular, the ordinal $\omega=\omega^1$ has exactly one term in its Cantor normal form, and a finite number $n=\omega^0+\cdots+\omega^0$ has exactly $n$ terms in its Cantor normal form. So the statement of the theorem agrees with the calculations that we had made at the very beginning.

Proof: First, let’s observe that every nonempty final segment of an ordinal of the form $\omega^\beta$ is isomorphic to $\omega^\beta$ again. This amounts to the fact that ordinals of the form $\omega^\beta$ are additively indecomposable, or in other words, closed under ordinal addition, since the final segments of an ordinal $\alpha$ are precisely the ordinals $\zeta$ such that $\alpha=\xi+\zeta$ for some $\xi$. If $\alpha$ is additively indecomposable, then it cannot be that $\zeta<\alpha$, and so all final segments would be isomorphic to $\alpha$. So let’s prove that $\omega^\beta$ is additively indecomposable. This is clear if $\beta=0$, since the only ordinal less than $\omega^0=1$ is $0$ and $0+0<1$. If $\beta$ is a limit ordinal, then the ordinals $\omega^\eta$ for $\eta<\beta$ are unbounded in $\omega^\beta$, and adding them stays below because $\omega^\eta+\omega^\eta=\omega^\eta\cdot 2\leq\omega^\eta\cdot\omega=\omega^{\eta+1}<\omega^\beta$. If $\beta=\delta+1$ is a successor ordinal, then $\omega^\beta=\omega^{\delta+1}=\omega^\delta\cdot\omega=\sup_{n<\omega}\omega^\delta\cdot n$, but again adding them stays below because $\omega^\delta\cdot n+\omega^\delta\cdot m=\omega^\delta\cdot(n+m) < \omega^\delta\cdot\omega=\omega^\beta$.

To prove the theorem, consider any ordinal $\alpha$ with Cantor normal form $\alpha=\omega^{\beta_n}+\cdots+\omega^{\beta_0}$, where $\beta_n\geq\cdots\geq\beta_0$. So as an order type, $\alpha$ consists of finitely many pieces, the first of type $\omega^{\beta_n}$, the next of type $\omega^{\beta_{n-1}}$ and so on up to $\omega^{\beta_0}$. Any final segment of $\alpha$ therefore consists of a final segment of one of these segments, together with all the segments after that segment (and omitting any segments prior to it, if any). But since these segments all have the form $\omega^{\beta_i}$, they are additively indecomposable and therefore are isomorphic to all their nonempty final segments. So any final segment of $\alpha$ is order-isomorphic to an ordinal whose Cantor normal form simply omits some (or none) of the terms from the front of the Cantor normal form of $\alpha$. Since we may start with any of the $n$ terms (or none), this gives precisely $n+1$ many order types of the final segments of $\alpha$, as claimed.

The argument shows, furthermore, that the possible order types of the final segments of $\alpha$, where $\alpha=\omega^{\beta_n}+\cdots+\omega^{\beta_0}$, are precisely the ordinals of the form $\omega^{\beta_k}+\cdots+\omega^{\beta_0}$, omitting terms only from the front, where $k\leq n$. QED

The axiom of determinacy for small sets

Posted on by
4

Lewis ChessmenI should like to argue that the axiom of determinacy is true for all games having a small payoff set. In particular, the size of the smallest non-determined set, in the sense of the axiom of determinacy, is the continuum; every set of size less than the continuum is determined, even when the continuum is enormous.

We consider two-player games of perfect information. Two players, taking turns, play moves from a fixed space $X$ of possible moves, and thereby together build a particular play or instance of the game $\vec a=\langle a_0,a_1,\ldots\rangle\in X^\omega$. The winner of this instance of the game is determined according to whether the play $\vec a$ is a member of some fixed payoff set $U\subset X^\omega$ specifying the winning condition for this game. Namely, the first player wins in the case $\vec a\in U$.

A strategy in such a game is a function $\sigma:X^{<\omega}\to X$ that instructs a particular player how to move next, given the sequence of partial play, and such a strategy is a winning strategy for that player, if all plays made against it are winning for that player. (The first player applies the strategy $\sigma$ only on even-length input, and the second player only to the odd-length inputs.) The game is determined, if one of the players has a winning strategy.

It is not difficult to see that if $U$ is countable, then the game is determined. To see this, note first that if the space of moves $X$ has at most one element, then the game is trivial and hence determined; and so we may assume that $X$ has at least two elements. If the payoff set $U$ is countable, then we may enumerate it as $U=\{s_0,s_1,\ldots\}$. Let the opposing player now adopt the strategy of ensuring on the $n^{th}$ move that the resulting play is different from $s_n$. In this way, the opposing player will ensure that the play is not in $U$, and therefore win. So every game with a countable payoff set is determined.

Meanwhile, using the axiom of choice, we may construct a non-determined set even for the case $X=\{0,1\}$, as follows. Since a strategy is function from finite binary sequences to $\{0,1\}$, there are only continuum many strategies. By the axiom of choice, we may well-order the strategies in order type continuum. Let us define a payoff set $U$ by a transfinite recursive procedure: at each stage, we will have made fewer than continuum many promises about membership and non-membership in $U$; we consider the next strategy on the list; since there are continuum many plays that accord with that strategy for each particular player, we may make two additional promises about $U$ by placing one of these plays into $U$ and one out of $U$ in such a way that this strategy is defeated as a winning strategy for either player. The result of the recursion is a non-determined set of size continuum.

So what is the size of the smallest non-determined set? For a lower bound, we argued above that every countable payoff set is determined, and so the smallest non-determined set must be uncountable, of size at least $\aleph_1$. For an upper bound, we constructed a non-determined set of size continuum. Thus, if the continuum hypothesis holds, then the smallest non-determined set has size exactly continuum, which is $\aleph_1$ in this case. But what if the continuum hypothesis fails? I claim, nevertheless, that the smallest non-determined set still has size continuum.

Theorem. Every game whose winning condition is a set of size less than the continuum is determined.

Proof. Suppose that $U\subset X^\omega$ is the payoff set of the game under consideration, so that $U$ has size less than continuum. If $X$ has at most one element, then the game is trivial and hence determined. So we may assume that $X$ has at least two elements. Let us partition the elements of $X^\omega$ according to whether they have exactly the same plays for the second player. So there are at least continuum many classes in this partition. If $U$ has size less than continuum, therefore, it must be disjoint from at least one (and in fact from most) of the classes of this partition (since otherwise we would have an injection from the continuum into $U$). So there is a fixed sequence of moves for the second player, such that any instance of the game in which the second player makes those moves, the result is not in $U$ and hence is a win for the second player. This is a winning strategy for the second player, and so the game is determined. QED

This proof generalizes the conclusion of the diagonalization argument against a countable payoff set, by showing that for any winning condition set of size less than continuum, there is a fixed play for the opponent (not depending on the play of the first player) that defeats it.

The proof of the theorem uses the axiom of choice in the step where we deduce that $U$ must be disjoint from a piece of the partition, since there are continuum many such pieces and $U$ had size less than the continuum. Without the axiom of choice, this conclusion does not follow. Nevertheless, what the proof does show without AC is that every set that does not surject onto $\mathbb{R}$ is determined, since if $U$ contained an element from every piece of the partition it would surject onto $\mathbb{R}$. Without AC, the assumption that $U$ does not surject onto $\mathbb{R}$ is stronger than the assumption merely that it has size less the continuum, although these properties are equivalent in ZFC.  Meanwhile, these issues are relevant in light of the model suggested by Asaf Karagila in the comments below, which shows that it is consistent with ZF without the axiom of choice that there are small non-determined sets. Namely, the result of Monro shows that it is consistent with ZF that $\mathbb{R}=A\sqcup B$, where both $A$ and $B$ have cardinality less than the continuum. In particular, in this model the continuum injects into neither $A$ nor $B$, and consequently neither player can have a strategy to force the play into their side of this partition. Thus, both $A$ and $B$ are non-determined, even though they have size less than the continuum.

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.