Tag Archives: Transfinite recursion

What is the game of recursive chess?

Posted on by
18

Consider this fascinating vision of recursive chess — the etching below was created by Django Pinter, a tutorial student of mine who has just completed his degree in the PPL course here at Oxford, given to me as a parting gift at the conclusion of his studies. Django’s idea was to play chess, but in order for a capture to occur successfully on the board, as here with the black Queen attempting to capture the opposing white knight, the two pieces would themselves sit down for their own game of (recursive) chess. The idea was that the capture would be successful only in the event that the subgame was won. Notice in the image that not only is there a smaller recursive game of chess, but also a still tinier subrecursive game below that (if you inspect closely), while at the same time larger pieces loom in the background, indicating that the main board itself is already several levels deep in the recursion.

The recursive chess idea may seem clear enough initially, and intriguing. But with further reflection, we might wonder how does it work exactly? What precisely is the game of recursive chess? This is my question here.

My goal with this post is to open a discussion about what ultimately should be the precise the rules and operations of recursive chess. I’m not completely sure what the best rule set will be, although I do offer several proposals here. I welcome further proposals, commentary, suggestions, and criticism about how to proceed. Once we settle upon a best or most natural version of the game, then I shall hope perhaps to prove things about it. Will you help me decide what is the game of recursive chess?

Let me describe several natural proposals:

Naïve recursion. Although this seems initially to be a simple, sound proposal, ultimately I find it problematic. The naïve idea is that when one piece wants to capture another in the game at hand, then the two pieces themselves play a game of chess, starting from the usual chess starting position. I would find it natural that the attacking piece should play as white in this game, going first, and if that player wins the subgame, then the capture in the current game is successful. If the subgame is a loss, then the capture is unsuccessful.

There seem, however, to be a variety of ways to handle the losing subgame outcome, and since these will apply with several of the other proposals, let me record them here:

  • Failed-capture. If the subgame is lost, then the capture in the current game simply does not occur. Both pieces remain on their original squares, and the turn of play passes to the opponent. Notice that this will have serious affects in certain chess situations involving zugswang, a position where a player has no good move — because if one of them is a capture, then the player can aim to play badly in the subgame and thereby legally pass the turn of play to the opponent without having made any move. This situation will in effect cause the subgame players to attempt to lose, rather than win, which seems undesirable.
  • Failed-capture-with-penalty. If the subgame is lost, then the capture does not occur, but furthermore, the attacking piece is itself lost, removed from the board, and the turn of play passes to the opponent. In effect, under this rule, every attempt at capture is putting the life of the capturing piece at risk, which makes a certain amount of sense from a military point of view. I think perhaps this is a good rule.
  • Failed-capture-with-retry. If the subgame is lost, then the capture does not occur, but both pieces remain on their original squares, and the attacking player is allowed to proceed with another (different) move. Attempting the same attack from the same board position multiple times is subject to the three-fold repetition rule. This interpretation amounts in effect to the game play searching a large part of the game tree, exploring the possible capturing moves, but with the first successful option fixed as official. It invites manipulation by the opponent, who might play badly against a misguided capture attempt, causing it to be fixed as the official move.
  • Drawn subgame. A further complication arises from the fact that the subgame can itself be drawn, rather than won. Is this sufficient to cause the penalty or the retry? Or does this count as a failed capture?

As I see it, however, the principal problem with the naïve recursion rule is that it seems to be ill-founded. After all, we can have a game with a capture, which leads to a subgame with a capture, which leads to a deeper subgame with a capture, and so on descending forever. How is the outcome determined in this infinitely descending situation? None of the subgames is ever resolved with a definite conclusion until all of them are, and there seems no coherent way to assign resolutions to them. All infinitely many subgames are simply left hanging mid-play, and indeed mid-move. For this reason, the naïve recursion idea seems ultimately incoherent to me as a game rule.

What we would seem to need instead is a well-founded recursion, one which would ultimately bottom-out in a base case. With such a recursion, every outcome of the game would be well-defined. Such a well-founded recursion would be achieved, for example, if on every subgame there were strictly fewer pieces. Eventually, the subgames would reduce to king versus king, a drawn game, and then the drawn subgame rule would be invoked to whatever affect it cause. But the recursion would definitely terminate. And perhaps most recursions would terminate because the stronger player was ultimately mating in all his attacks, without requiring any invocation of the drawn subgame rule.

We can easily describe several natural subgame positions with one fewer piece. For example, when one piece attacks another, we may naturally consider the positions that would result if we performed the capture, or if we removed the attacking piece; and we might further consider swapping the roles of the players in these positions. Such cases would constitute a well-founded recursion, because the subgame position would have fewer pieces than the main position. In this way, we arrive at several natural recursion rules for recursive chess.

Proof-of-sufficiency recursion. The motivating idea of this recursion rule is that in order for an attack to be successful, the attacking player must prove that it will be sufficient for the attack to be successful. So, when piece A attacks piece B in the game, then a subgame is set up from the position that would result if A were successfully to capture B, and the players proceed in the game in which the attack has occurred. This is the same as proceeding in the main game, under the assumption that the attack was successful. If the attacking player can win this subgame, then it shows in a sense the sufficiency of the attack as a means to win, and so on the proof-of-sufficiency idea, we allow this as a reason for the attack to have been successful.

One might object that this recursion seems at first to amount to just playing chess as usual, since the subgame is the same as the original game with the attack having succeeded. But there is a subtle difference. For a misguided attack, the attacked player can play suboptimally in the subgame, intentionally losing that game, and then play differently in the main game. There is, of course, no obligation that the players respond the same at the higher-level games as in the lower games, and this is all part of their strategic calculation.

Proof-of-necessity recursion. The motivating idea of this recursion rule, in contrast, is that in order for an attack to be successful, the attacking player must prove that it is necessary that the attack take place. When piece A attacks piece B in the main game, then a subgame is set up in which the attack has not succeeded, but instead the attacking piece is lost, but the color sides of the players are swapped. If a black Queen attacks a white knight, for example, then in the subgame position, the queen is removed, and the players proceed from that positions, but with the opposite colors. By winning this subgame, the attacking player is in effect demonstrating that if the attack were to fail, then it would be devastating for them. In other words, they are demonstrating the necessity of the success of the attack.

For the both the proof-of-sufficiency and the proof-of-necessity versions of the recursion, it seems to me that any of the three failed-capture rules would be sensible. And so we have quite a few different interpretations here for what is the game of recursive chess.

What is your proposal? Please let me know in the comments. I am interested to hear any comments or criticism.

Second-order transfinite recursion is equivalent to Kelley-Morse set theory over GBC

Posted on by
Reply

1167px-Wooden_spiral_stairs_(Nebotičnik,_Ljubljana)_croped
A few years ago, I had observed after hearing a talk by Benjamin Rin that the principle of first-order transfinite recursion for set well-orders is equivalent to the replacement axiom over Zermelo set theory, and thus we may take transfinite recursion as a fundamental set-theoretic principle, one which yields full ZFC when added to Zermelo’s weaker theory (plus foundation).

In later work, Victoria Gitman and I happened to prove that the principle of elementary transfinite recursion ETR, which allows for first-order class recursions along proper class well-orders (not necessarily set-like) is equivalent to the principle of determinacy for clopen class games [1]. Thus, once again, a strong recursion principle exhibited robustness as a fundamental set-theoretic principle.

The theme continued in recent joint work on the class forcing theorem, in which Victoria Gitman, myself, Peter Holy, Philipp Schlicht and Kameryn Williams [2] proved that the principle $\text{ETR}_{\text{Ord}}$, which allows for first-order class recursions of length $\text{Ord}$, is equivalent to twelve natural set-theoretic principles, including the existence of forcing relations for class forcing notions, the existence of Boolean completions for class partial orders, the existence of various kinds of truth predicates for infinitary logics, the existence of $\text{Ord}$-iterated truth predicates, and to the principle of determinacy for clopen class games of rank at most $\text{Ord}+1$.

A few days ago, a MathOverflow question of Alec Rhea’s — Is there a stronger form of recursion? — led me to notice that one naturally gains additional strength by pushing the recursion principles further into second-order set theory.

So let me introduce the second-order recursion principle STR and make the comparatively simple observation that over Gödel-Bernays GBC set theory this is equivalent to Kelley-Morse set theory KM. Thus, we may take this kind of recursion as a fundamental set-theoretic principle.

Definition. In the context of second-order set theory, the principle of second-order transfinite recursion, denoted STR, asserts of any formula $\varphi$ in the second-order language of set theory, that if $\Gamma=\langle I,\leq_\Gamma\rangle$ is any class well-order and $Z$ is any class parameter, then there is a class $S\subset I\times V$ that is a solution of the recursion, in the sense that
$$S_i=\{\ x\ \mid\  \varphi(x,S\upharpoonright i,Z)\ \}$$
for every $i\in I$, where where $S_i=\{\ x\ \mid\ (i,x)\in S\ \}$ is the section on coordinate $i$ and where $S\upharpoonright i=\{\ (j,x)\in S\ \mid\ j<_\Gamma i\ \}$ is the part of the solution at stages below $i$ with respect to $\Gamma$.

Theorem. The principle of second-order transfinite recursion STR is equivalent over GBC to the second-order comprehension principle. In other words, GBC+STR is equivalent to KM.

Proof. Kelley-Morse set theory proves that every second-order recursion has a solution in the same way that ZFC proves that every set-length well-ordered recursion has a solution. Namely, we simply consider the classes which are partial solutions to the recursion, in that they obey the recursive requirement, but possibly only on an initial segment of the well-order $\Gamma$. We may easily show by induction that any two such partial solutions agree on their common domain (this uses second-order comprehension in order to find the least point of disagreement, if any), and we can show that any given partial solution, if not already a full solution, can be extended to a partial solution on a strictly longer initial segment. Finally, we show that the common values of all partial solutions is therefore a solution of the recursion. This final step uses second-order comprehension in order to define what the common values are for the partial solutions to the recursion.

Conversely, the principle of second-order transfinite recursion clearly implies the second-order comprehension axiom, by considering recursions of length one. For any second-order assertion $\varphi$ and class parameter $Z$, we may deduce that $\{x\mid \varphi(x,Z)\}$ is a class, and so the second-order class comprehension principle holds. $\Box$

It is natural to consider various fragments of STR, such as $\Sigma^1_n\text{-}\text{TR}_\Gamma$, which is the assertion that every $\Sigma^1_n$-formula $\varphi$ admits a solution for recursions of length $\Gamma$.  Such principles are provable in proper fragments of KM, since for a given level of complexity, we only need a corresponding fragment of comprehension to undertake the proof that the recursion has a solution. The full STR asserts $\Sigma^1_\omega\text{-}\text{TR}$, allowing any length. The theorem shows that STR is equivalent to recursions of length $1$, since once you get the second-order comprehension principle, then you get solutions for recursions of any length. Thus, with second-order transfinite recursion, a little goes a long way. Perhaps it is more natural to think of transfinite recursion in this context not as axiomatizing KM, since it clearly implies second-order comprehension straight away, but rather as an apparent strengthening of KM that is actually provable in KM. This contrasts with the first-order situation of ETR with respect to GBC, where GBC+ETR does make a proper strengthening of GBC.

  1. [bibtex key=”GitmanHamkins2016:OpenDeterminacyForClassGames”]
  2. [bibtex key=”GitmanHamkinsHolySchlichtWilliams:The-exact-strength-of-the-class-forcing-theorem”]
Photo by Petar Milošević (Own work) [CC BY-SA 4.0], via Wikimedia Commons

Diamond on the ordinals

Posted on by
5

I was recently surprised to discover that if there is a definable well-ordering of the universe, then the diamond principle on the ordinals holds for definable classes, automatically. In fact, the diamond principle for definable classes is simply equivalent in ZFC to the existence of a definable well-ordering of the universe. It follows as a consequence that the diamond principle for definable classes, although seeming to be fundamentally scheme-theoretic, is actually expressible in the first-order language of set theory.

In set theory, the diamond principle asserts the existence of a sequence of objects $A_\alpha$, of growing size, such that any large object at the end is very often anticipated by these approximations.  In the case of diamond on the ordinals, what we will have is a definable sequence of $A_\alpha\subseteq\alpha$, such that for any definable class of ordinals $A$ and any definable class club set $C$, there are ordinals $\theta\in C$ with $A\cap\theta=A_\theta$.  This kind of principle typically allows one to undertake long constructions that will diagonalize against all the large objects, by considering and reacting to their approximations $A_\alpha$. Since every large object $A$ is often correctly approximated that way, this enables many such constructions to succeed.

Let me dive right in to the main part of the argument.$\newcommand\restrict\upharpoonright
\newcommand\of\subseteq
\newcommand\Ord{\text{Ord}}
\newcommand\HOD{\text{HOD}}\newcommand\ZFC{\text{ZFC}}$

Theorem. In $\ZFC$, if there is a definable well-ordering of the universe, then $\Diamond_{\Ord}$ holds for definable classes. That is, there is a $p$-definable sequence $\langle A_\alpha\mid\alpha<\Ord\rangle$, such that for any definable class $A\of\Ord$ and any definable closed unbounded class of ordinals $C\of\Ord$ (allowing parameters), there is some $\theta\in C$ with $A\cap\theta=A_\theta$.

Proof. The theorem is proved as a theorem scheme; namely, I shall provide a specific definition for the sequence $\vec A=\langle A_\alpha\mid\alpha<\Ord\rangle$, using the same parameter $p$ as the definition of the global well-order and with a definition of closely related syntactic complexity, and then prove as a scheme, a separate statement for each definable class $A\of\Ord$ and class club $C\of\Ord$, that there is some $\alpha\in C$ with $A\cap\alpha=A_\alpha$. The definitions of the classes $A$ and $C$ may involve parameters and have arbitrary complexity.

Let $\lhd$ be the definable well-ordering of the universe, definable by a specific formula using some parameter $p$. I define the $\Diamond_{\Ord}$-sequence $\vec A=\langle A_\alpha\mid\alpha<\Ord\rangle$ by transfinite recursion. Suppose that $\vec A\restrict\theta$ has been defined. I shall let $A_\theta=\emptyset$ unless $\theta$ is a $\beth$-fixed point above the rank of $p$ and there is a set $A\of\theta$ and a closed unbounded set $C\of\theta$, with both $A$ and $C$ definable in the structure $\langle V_\theta,\in\rangle$ (allowing parameters), such that $A\cap\alpha\neq A_\alpha$ for every $\alpha\in C$. In this case, I choose the least such pair $(A,C)$, minimizing first on the maximum of the logical complexities of the definitions of $A$ and of $C$, and then minimizing on the total length of the defining formulas of $A$ and $C$, and then minimizing on the Gödel codes of those formulas, and finally on the parameters used in the definitions, using the well-order $\lhd\restrict V_\theta$. For this minimal pair, let $A_\theta=A$. This completes the definition of the sequence $\vec A=\langle A_\alpha\mid\alpha\in\Ord\rangle$.

Let me remark on a subtle point, since the meta-mathematical issues loom large here. The definition of $\vec A$ is internal to the model, and at stage $\theta$ we ask about subsets of $\theta$ definable in $\langle V_\theta,\in\rangle$, using the truth predicate for this structure. If we were to run this definition inside an $\omega$-nonstandard model, it could happen that the minimal formula we get is nonstandard, and in this case, the set $A$ would not actually be definable by a standard formula. Also, even when $A$ is definable by a standard formula, it might be paired (with some constants), with a club set $C$ that is defined only by a nonstandard formula (and this is why we minimize on the maximum of the complexities of the definitions of $A$ and $C$ together). So one must give care in the main argument keeping straight the distinction between the meta-theoretic natural numbers and the internal natural numbers of the object theory $\ZFC$.

Let me now prove that the sequence $\vec A$ is indeed a $\Diamond_{\Ord}$-sequence for definable classes. The argument follows in spirit the classical proof of $\Diamond$ in $L$, subject to the mathematical issues I mentioned. If the sequence $\vec A$ is not a diamond sequence, then there is some definable class $A\of\Ord$, defined in $\langle V,\in\rangle$ by a specific formula $\varphi$ and parameter $z$, and definable club $C\of\Ord$, defined by some $\psi$ and parameter $y$, with $A\cap\alpha\neq A_\alpha$ for every $\alpha\in C$. We may assume without loss that these formulas are chosen so as to be minimal in the sense of the construction, so that the maximum of the complexities of $\varphi$ and $\psi$ are as small as possible, and the lengths of the formulas, and the Gödel codes and finally the parameters $z,y$ are $\lhd$-minimal, respectively, successively. Let $m$ be a sufficiently large natural number, larger than the complexity of the definitions of $\lhd$, $A$, $C$, and large enough so that the minimality condition we just discussed is expressible by a $\Sigma_m$ formula. Let $\theta$ be any $\Sigma_m$-correct ordinal above the ranks of the parameters used in the definitions. It follows that the restrictions $\lhd\restrict V_\theta$ and also $A\cap\theta$ and $C\cap\theta$ and $\vec A\restrict\theta$ are definable in $\langle V_\theta,\in\rangle$ by the same definitions and parameters as their counterparts in $V$, that $C\cap\theta$ is club in $\theta$, and that $A\cap\theta$ and $C\cap\theta$ form a minimal pair using those definitions with $A\cap\alpha\neq A_\alpha$ for any $\alpha\in C\cap\theta$. Thus, by the definition of $\vec A$, it follows that $A_\theta=A\cap\theta$. Since $C\cap\theta$ is unbounded in $\theta$ and $C$ is closed, it follows that $\theta\in C$, and so $A_\theta=A\cap\theta$ contradicts our assumption about $A$ and $C$. So there are no such counterexample classes, and thus $\vec A$ is a $\Diamond_{\Ord}$-sequence with respect to definable classes, as claimed.
QED

Theorem. The following are equivalent over $\ZFC$.

  1. There is a definable well-ordering of the universe, using some set parameter $p$.
  2. $V=\HOD_{\{p\}}$, for some set $p$.
  3. $\Diamond_{\Ord}$ holds for definable classes. That is, there is a set parameter $p$ and a definable sequence $\vec A=\langle A_\alpha\mid\alpha<\Ord\rangle$, such that for any definable class $A\of\Ord$ and definable class club $C\of\Ord$, there is some $\alpha\in C$ with $A\cap\alpha=A_\alpha$.

Proof. Let me first give the argument, and then afterward discuss some issues about the formalization, which involves some subtle issues.

($1\to 2$) $\newcommand\rank{\text{rank}}$Suppose that $\lhd$ is a $p$-definable well-ordering of $V$, which means that every set has a $\lhd$-minimal element. Let us refine this order by defining $x\lhd’ y$, just in case $\rank(x)<\rank(y)$ or $\rank(x)=\rank(y)$ and $x\lhd y$. The new order is also a well-order, which now respects rank. In particular, the order $\lhd’$ is set-like, and so every object $x$ is the $\alpha^{th}$ element with respect to the $\lhd’$-order, for some ordinal $\alpha$. Thus, every object is definable from $p$ and an ordinal, and so $V=\HOD_{\{p\}}$, as desired.

($2\to 1$) If $V=\HOD_{\{p\}}$, then we have the canonical well-order of $\HOD$ using parameter $p$, similar to how one shows that the axiom of choice holds in $\HOD$. Namely, define $x\lhd y$ if and only if $\rank(x)<\rank(y)$, or the ranks are the same, but $x$ is definable from $p$ and ordinal parameters in some $V_\theta$ with a smaller $\theta$ than $y$ is, or the ranks are the same and the $\theta$ is the same, but $x$ is definable in that $V_\theta$ by a formula with a smaller Gödel code, or with the same formula but smaller ordinal parameters. It is easy to see that this is a $p$-definable well-ordering of the universe.

($1\to 3$) This is the content of the theorem above.

($3\to 1$) If $\vec A$ is a $p$-definable $\Diamond_{\Ord}$-sequence for definable classes, then it is easy to see that if $A$ is a set of ordinals, then $A$ must arise as $A_\alpha$ for unboundedly many $\alpha$. In $\ZFC$, using the axiom of choice, it is a standard fact that every set is coded by a set of ordinals. So let us define that $x\lhd y$, just in case $x$ is coded by a set of ordinals that appears earlier on $\vec A$ than any set of ordinals coding $y$. This is clearly a well-ordering, since the map sending $x$ to the ordinal $\alpha$ for which $A_\alpha$ codes $x$ is an $\Ord$-ranking of $\lhd$. So there is a $p$-definable well-ordering of the universe.
QED

An observant reader will notice some meta-mathematical issues concerning the previous theorem. The issue is that statements 1 and 2 are known to be expressible by statements in the first-order language of set theory, as single statements, but for statement 3 we have previously expressed it only as a scheme of first-order statements. So how can they be equivalent? The answer is that the full scheme-theoretic content of statement 3 follows already from instances in which the complexity of the definitions of $A$ and $C$ are bounded. Basically, once one gets the global well-order, then one can construct a $\Diamond_{\Ord}$-sequence that works for all definable classes. In this sense, we may regard the diamond principle $\Diamond_{\Ord}$ for definable classes as not really a scheme of statements, but rather equivalent to a single first-order assertion.

Lastly, let me consider the content of the theorems in Gödel-Bernays set theory or Kelley-Morse set theory. Of course, we know that there can be models of these theories that do not have $\Diamond_{\Ord}$ in the full second-order sense. For example, it is relatively consistent with ZFC that an inaccessible cardinal $\kappa$ does not have $\Diamond_\kappa$, and in this case, the structure $\langle V_\kappa,\in,V_{\kappa+1}\rangle$ will satisfy GBC and even KM, but it won’t have $\Diamond_{\Ord}$ with respect to all classes, even though it has a definable well-ordering of the universe (since there is such a well-ordering in $V_{\kappa+1}$). But meanwhile, there will be a $\Diamond_{\Ord}$-sequence that works with respect to classes that are definable from that well-ordering and parameters, simply by following the construction given in the theorem.

This leads to several extremely interesting questions, about which I am currently thinking, concerning instances where we can have $\Diamond_\kappa$ for definable classes in $V_\kappa$, even when the full $\Diamond_\kappa$ fails. Stay tuned!

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.

Transfinite Nim

Posted on by
7

Wooden blocksShall we have a game of transfinite Nim? One of us sets up finitely many piles of wooden blocks, each pile having some ordinal height, possibly transfinite, and the other of us decides who shall make the first move. Taking turns, we each successively remove a top part of any one pile of our choosing, making it strictly shorter. Whoever takes the very last block wins. (It is fine to remove an entire pile on a turn or to remove blocks from a different pile on a later turn.)

In my challenge problem last week, for example, I set up six piles with heights:
$$1\qquad \omega+3\qquad \omega^\omega+5 \qquad \omega^{\omega+3}+\omega^\omega\cdot3+\omega\cdot 5+7\qquad \epsilon_0\qquad \omega_1$$Would you want to go first or second? What is the best move? In general, we can start with any finite number of piles of arbitrary ordinal heights — what is the general winning strategy?

Before proceeding with the transfinite case, however, let’s review the winning strategy in ordinary finite Nim, which I explained in my post last week concerning my visit to the 7th/8th grade Math Team at my son’s school. To say it quickly again, a finite Nim position is balanced, if when you consider the binary representations of the pile heights, there are an even number of ones in each binary place position. Another way to say this, and this is how I explained it to the school kids, is that if you think of each pile height as a sum of distinct powers of two, then any power of two that arises in any pile does so an even number of times overall for all the piles. The mathematical facts to establish are that (1) any move on a balanced position will unbalance it; and (2) any unbalanced position admits a balancing move. Since the winning move of taking the very last block is a balancing move, it follows that the winning strategy is to balance whatever position with which you are faced. At the start, if the position is unbalanced, then you should go first and balance it; if it is already balanced, then you should go second and adopt the balancing strategy. It may be interesting to note that this winning strategy is unique in the sense that any move that does not balance the position is a losing move, since the opposing player can adopt the balancing strategy from that point on. But of course there is often a choice of balancing moves.

Does this balancing strategy idea continue to apply to transfinite Nim? Yes! All we need to do is to develop a little of the theory of transfinite binary representation. Let me assume that you are all familiar with the usual ordinal arithmetic, for which $\alpha+\beta$ is the ordinal whose order type is isomorphic to a copy of $\alpha$ followed by a copy of $\beta$, and $\alpha\cdot\beta$ is the ordinal whose order type is isomorphic to $\beta$ many copies of $\alpha$. Consider now ordinal exponentiation, which can be defined recursively as follows:
$$\alpha^0=1$$ $$\alpha^{\beta+1}=\alpha^\beta\cdot\alpha$$ $$\alpha^\lambda=\sup_{\beta<\lambda} \alpha^\beta\qquad\lambda\text{ limit}$$ It turns out that $\alpha^\beta$ is the order-type of the finite-support functions from $\beta$ to $\alpha$, under the suitable lexical order. Ordinal exponentiation should not be confused with cardinal exponentiation, since they are very different. For example, with ordinal exponentiation, one has $$2^\omega=\sup_{n<\omega}2^n=\omega,$$which of course is not the case with cardinal exponentiation. In this post, I use only ordinal exponentiation.

Theorem. Every ordinal $\beta$ has a unique representation as a decreasing finite sum of ordinal powers of two. $$\beta=2^{\beta_n}+\cdots+2^{\beta_0}, \qquad \beta_n>\cdots>\beta_0$$

The proof is easy! We simply prove it by transfinite induction on $\beta$. If the theorem holds below an ordinal $\beta$, first let $2^\alpha$ be the largest power of two that is at most $\beta$, so that $\beta=2^\alpha+\gamma$ for some ordinal $\gamma$. It follows that $\gamma<2^\alpha$, for otherwise we could have made $2^{\alpha+1}\leq\beta$. Thus, by induction, $\gamma$ has a representation with powers of two, and so we may simply add $2^\alpha$ at the front to represent $\beta$. To see that the representations are unique, first establish that any power of two is equal to or more than the supremum of the finite decreasing sums of any strictly smaller powers of two. From this, it follows that any representation of $\beta$ as above must have used $2^\alpha$ just as we did for the first term, because otherwise it couldn’t be large enough, and then the representation of the remaining part $\gamma$ is unique by induction, and so we get uniqueness for the representation of $\beta$. QED

Thus, the theorem shows that every ordinal has a unique binary representation in the ordinals, with finitely many nonzero bits. Suppose that we are given a position in transfinite Nim with piles of ordinal heights $\eta_0,\ldots,\eta_n$. We define that such a position is balanced, if every power of two appearing in the representation of any of the piles appears an even number of times overall for all the piles.

The mathematical facts to establish are (1) any move on a balanced position will unbalance it; and (2) every unbalanced position has a balancing move. These facts can be proved in the transfinite case in essentially the same manner as the finite case. Namely, if a position is balanced, then any move affects only one pile, changing the ordinal powers of two that appear in it, and thereby destroy the balanced parity of whichever powers of two are affected. And if a position is unbalanced, then look at the largest unbalanced ordinal power of two appearing, and make a move on any pile having such a power of two in its representation, reducing it so as exactly to balance all the smaller powers of two appearing in the position.

Finally, those two facts again imply that the balancing strategy is a winning strategy, since the winning move of taking the last block or blocks is a balancing move, down to the all-zero position, which is balanced.

In the case of my challenge problem above, we may represent the ordinals in binary. We know how to do that in the case of 1, 3, 5 and 7, and actually those numbers are balanced. Here are some other useful binary representations:

$\omega+3=2^\omega+2+1$

$\omega^\omega+5 = (2^\omega)^\omega+5=2^{\omega^2}+4+1$

$\omega^{\omega+3}=(2^\omega)^{\omega+3}=2^{\omega^2+\omega\cdot 3}$

$\omega^\omega\cdot3=(2^\omega)^\omega\cdot 3=2^{\omega^2}\cdot 2+2^{\omega^2}=2^{\omega^2+1}+2^{\omega^2}$

$\omega\cdot 5+7 =2^{\omega}\cdot 2^2+2^\omega+7=2^{\omega+2}+2^\omega+4+2+1$

$\epsilon_0 = 2^{\epsilon_0}$

$\omega_1=2^{\omega_1}$

I emphasize again that this is ordinal exponentiation. The Nim position of the challenge problem above is easily seen to be unbalanced in several ways. For example, the $\omega_1$ term among others appears only once. Thus, we definitely want to go first in this position. And since $\omega_1$ is the largest unbalanced power of two and it appears only once, we know that we must play on the $\omega_1$ pile. Once one represents all the ordinals in terms of their powers of two representation, one sees that the unique winning move is to reduce the $\omega_1$ pile to have ordinal height
$$\epsilon_0+\omega^{\omega+3}+\omega^\omega\cdot 2+\omega\cdot 4.$$This will exactly balance all the smaller powers of two in the other piles and therefore leaves a balanced position overall. In general, the winning strategy in transfinite Nim, just as for finite Nim, is always to leave a balanced position.

Special honors to Pedro Sánchez Terraf for being the only one to post the winning move in the comments on the other post!

Now I know!

Posted on by
18

Inspired by Timothy Gowers’s example, here is my transfinite epistemic logic problem.

First, let’s begin with a simple finite example.

Cheryl   Hello Albert and Bernard! I have given you each a different natural number ($0, 1, 2, \ldots$). Who of you has the larger number?

Albert   I don’t know.

Bernard   I don’t know either.

Albert    Even though you say that, I still don’t know.

Bernard    And still neither do I.

Albert    Alas, I continue not to know.

Bernard   And also I do not know.

Albert     Yet, I still do not know.

Bernard     Aha! Now I know which of us has the larger number.

Albert      In that case, I know both our numbers.

Bernard.  And now I also know both numbers.

Question: What numbers do Albert and Bernard have?

Click for the solution.

infinity

 

Now, let us consider a transfinite instance. Consider the following conversation.

Cheryl     I have given you each a different ordinal number, possibly transfinite, but possibly finite. Who of you has the larger ordinal?

Albert     I don’t know.

Bernard     I don’t know, either.

Albert     Even though you say that, I still don’t know.

Bernard     And still neither do I.

Albert     Alas, I still don’t know.

Bernard     And yet, neither do I.

Cheryl     Well, this is becoming boring. Let me tell you that no matter how much longer you continue that back-and-forth, you still will not know the answer.

Albert      Well, thank you, Cheryl, for that new information. However, I still do not know who has the larger ordinal.

Bernard     And yet still neither do I.

Albert     Alas, even now I do not know!

Bernard      And neither do I!

Cheryl     Excuse me; you two can go back and forth like this again, but let me tell you that no matter how much longer you continue in that pattern, you will not know.

Albert      Well, ’tis a pity, since even with this further information, I still do not know.

Bernard     Aha! Now at last I know who of us has the larger ordinal.

Albert     In that case, I know both our ordinals.

Bernard. And now I also know both ordinals.

Question:   What ordinals do they have?

Click for a solution.

 

See my next transfinite epistemic logic puzzle challenge!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Solutions.

  1. For the first problem, with natural numbers, let us call the numbers $a$ and $b$, respectively, for Albert and Bernard. Since Albert doesn’t know at the first step, it means that $a\neq 0$, and so $a$ is at least $1$. And since Bernard can make this conclusion, when he announces that he doesn’t know, it must mean that $b$ is not $0$ or $1$, for otherwise he would know, and so $b\geq 2$. On the next round, since Albert still doesn’t know, it follows that $a$ must be at least $3$, for otherwise he would know; and then, because Bernard still doesn’t know, it follows that $b$ is at least $4$. The next round similarly yields that $a$ is at least $5$ and then that $b$ is at least $6$. Because Albert can undertake all this reasoning, it follows that $a$ is at least $7$ on account of Albert’s penultimate remark. Since Bernard announces at this point that he knows who has the larger number, it must be that Bernard has $6$ or $7$ and that Albert has the larger number. And since Albert now announces that he knows the numbers, it must be because Albert has $7$ and Bernard has $6$.
  2. For the transfinite problem, let us call the ordinal numbers $\alpha$ and $\beta$, respectively, for Albert and Bernard. Since Albert doesn’t know at the first step, it means that $\alpha\neq 0$ and so $\alpha\geq 1$. Similarly, $\beta\geq 2$ after Bernard’s remark, and then $\alpha\geq 3$ and $\beta\geq 4$ and this would continue for some time. Because Cheryl says that no matter how long they continue, they will not know, it follows that both $\alpha$ and $\beta$ are infinite ordinals, at least $\omega$. But since Albert does not know at this stage, it means $\alpha\geq\omega+1$, and then $\beta\geq \omega+2$. Since Cheryl says again that no matter how long they continue that, they will not know, it means that $\alpha$ and $\beta$ must both exceed $\omega+k$ for every finite $k$, and so $\alpha$ and $\beta$ are both at least $\omega\cdot 2$. Since Albert still doesn’t know after that remark, it means $\alpha\geq\omega\cdot 2+1$. But now, since Bernard knows at this point, it must be that $\beta=\omega\cdot 2$ or $\omega\cdot 2+1$, since otherwise he couldn’t know. So Albert’s ordinal is larger. Since at this point Albert knows both the ordinals, it must be because Albert has $\omega\cdot 2+1$ and Bernard has $\omega\cdot 2$.

It is clear that one may continue in this way through larger transfinite ordinals. When the ordinals become appreciable in size, then it will get harder to turn it into a totally finite conversation, by means of Cheryl’s remarks, but one may succeed at this for quite some way with suitably obscure pronouncements by Cheryl describing various limiting processes of the ordinals. To handle any given (possibly uncountable) ordinal, it seems best that we should consider conversations of transfinite length.

Transfinite recursion as a fundamental principle in set theory

Posted on by
23

$\newcommand\dom{\text{dom}}
\newcommand\ran{\text{ran}}
\newcommand\restrict{\upharpoonright}$
InfinityAt the Midwest PhilMath Workshop this past weekend, I heard Benjamin Rin (UC Irvine) speak on transfinite recursion, with an interesting new perspective.  His idea was to consider transfinite recursion as a basic principle in set theory, along with its close relatives, and see how they relate to the other axioms of set theory, such as the replacement axiom. In particular, he had the idea of using our intuitions about the legitimacy of transfinite computational processes as providing a philosophical foundation for the replacement axiom.

This post is based on what I learned about Rin’s work from his talk at the workshop and in our subsequent conversations there about it.  Meanwhile, his paper is now available online:

Benjamin Rin, Transfinite recursion and the iterative conception of set, Synthese, October, 2014, p. 1-26. (preprint).

Since I have a little different perspective on the proposal than Rin did, I thought I would like to explain here how I look upon it.  Everything I say here is inspired by Rin’s work.

To begin, I propose that we consider the following axiom, asserting that we may undertake a transfinite recursive procedure along any given well-ordering.

The Principle of Transfinite Recursion. If $A$ is any set with well-ordering $<$ and $F:V\to V$ is any class function, then there is a function $s:A\to V$ such that $s(b)=F(s\upharpoonright b)$ for all $b\in A$, where $s\upharpoonright b$ denotes the function $\langle s(a)\mid a<b\rangle$.

We may understand this principle as an infinite scheme of statements in the first-order language of set theory, where we make separate assertions for each possible first-order formula defining the class function $F$, allowing parameters. It seems natural to consider the principle in the background theory of first-order Zermelo set theory Z, or the Zermelo theory ZC, which includes the axiom of choice, and in each case let me also include the axiom of foundation, which apparently is not usually included in Z.   (Alternatively, it is also natural to consider the principle as a single second-order statement, if one wants to work in second-order set theory.)

Theorem. (ZC) The principle of transfinite recursion is equivalent to the axiom of replacement. In other words,

ZC + transfinite recursion  =  ZFC.

Proof. Work in the Zermelo set theory ZC. The converse implication amounts to the well-known observation in ZF that transfinite recursion is legitimate. Let us quickly sketch the argument. Suppose we are given an instance of transfinite recursion, namely, a well-ordering $\langle A,<\rangle$ and a class function $F:V\to
V$. I claim that for every $b\in A$, there is a unique function $s:\{a\in A\mid a\leq b\}\to V$ obeying the recursive rule $s(d)=F(s\upharpoonright d)$ for all $d\leq b$. The reason is that there can be no least $b$ without such a unique function. If all $a<b$ have such a unique function, then by uniqueness they must cohere with one another, since any difference would show up at a least stage and thereby violate the recursion rule, and so by the replacement axiom of ZFC we may assemble these smaller functions into a single function $t$ defined on all $a<b$, and satisfying the recursion rule for those values. We may then extend this function $t$ to be defined on $b$ itself, simply by defining $u(b)=F(t)$ and $u\upharpoonright b=t$, which thereby satisfies the recursion at $b$. Uniqueness again follows from the fact that there can be no least place of disagreement. Finally, using replacement again, let $s(b)$ be the unique value that arises at $b$ during the recursions that work up to and including $b$, and this function $s:A\to V$ satisfies the recursive definition.

Conversely, assume the Zermelo theory ZC plus the principle of transfinite recursion, and suppose that we are faced with an instance of the replacement axiom. That is, we have a set $A$ and a formula $\varphi$, where every $b\in A$ has a unique $y$ such that $\varphi(b,y)$. By the axiom of choice, there is a well-ordering $<$ of the set $A$. We shall now define the function $F:V\to V$. Given a function $s$, where $\dom(s)=\{a\in A\mid a<b\}$ for some $b\in A$, let $F(s)=y$ be the unique $y$ such that $\varphi(b,y)$; and otherwise let $F(s)$ be anything you like. By the principle of transfinite recursion, there is a function $s:A\to V$ such that $s(b)=F(s\upharpoonright b)$ for every $b\in A$. In this case, it follows that $s(b)$ is the unique $y$ such that $\varphi(a,b)$. Thus, since $s$ is a set, it follows in ZC that $\ran(s)$ is a set, and so we’ve got the image of $A$ under $\varphi$ as a set, which verifies replacement. QED

In particular, it follows that the principle of transfinite recursion implies that every well-ordering is isomorphic to a von Neumann ordinal, a principle Rin refers to as ordinal abstraction. One can see this as a consequence of the previous theorem, since ordinal abstraction holds in ZF by Mostowski’s theorem, which for any well-order $\langle A,<\rangle$ assigns an ordinal to each node $a\mapsto \alpha_a$ according to the recursive rule $\alpha_a=\{\alpha_b\mid b<a\}$. But one can also argue directly as follows, without using the axiom of choice. Assume Z and the principle of transfinite recursion. Suppose that $\langle A,<\rangle$ is a well-ordering. Define the class function $F:V\to V$ so that $F(s)=\ran(s)$, whenever $s$ is a function. By the principle of transfinite recursion, there is a function $s:A\to V$ such that $s(b)=F(s\restrict b)=\ran(s\restrict b)$. One can now simply prove by induction that $s(b)$ is an ordinal and $s$ is an isomorphism of $\langle A,<\rangle$ with $\ran(s)$, which is an ordinal.

Let me remark that the principle of transfinite recursion allows us also to perform proper-class length recursions.

Observation. Assume Zermelo set theory Z plus the principle of transfinite recursion. If $A$ is any particular class with $<$ a set-like well-ordering of $A$ and $F:V\to V$ is any class function, then there is a class function $S:A\to V$ such that $S(b)=F(S\upharpoonright b)$ for every $b\in A$.

Proof. Since $\langle A,<\rangle$ is set-like, the initial segment $A\upharpoonright d=\{a\in A\mid a<d\}$, for any particular $d\in A$, is a set. It follows that the principle of transfinite recursion shows that there is a function $s_d:(A\upharpoonright d)\to V$ such that $s_d(b)=F(s_d\upharpoonright b)$ for every $b<d$. It is now easy to prove by induction that these $s_d$ must all cohere with one another, and so we may define the class $S(b)=s_d(b)$ for any $d$ above $b$ in $A$. (We may assume without loss that $A$ has no largest element, for otherwise it would be a set.) This provides a class function $S:A\to V$ satisfying the recursive definition as desired. QED

Although it appears explicitly as a second-order statement “there is a class function $S$…”, we may actually take this observation as a first-order theorem scheme, if we simply strengthen the conclusion to provide the explicit definition of $S$ that the proof provides. That is, the proof shows exactly how to define $S$, and if we make the observation state that that particular definition works, then what we have is a first-order theorem scheme. So any first-order definition of $A$ and $F$ from parameters leads uniformly to a first-order definition of $S$ using the same parameters.

Thus, using the principle of transfinite recursion, we may also take proper class length transfinite recursions, using any set-like well-ordered class that we happen to have available.

Let us now consider a weakening of the principle of transfinite recursion, where we do not use arbitrary well-orderings, but only the von Neumann ordinals themselves.

Principle of transfinite recursion on ordinals. If $F:V\to V$ is any class function, then for any ordinal $\gamma$ there is a function $s:\gamma\to V$ such that $s(\beta)=F(s\upharpoonright\beta)$ for all $\beta<\gamma$.

This is a weakening of the principle of transfinite recursion, since every ordinal is well-ordered, but in Zermelo set theory, not every well-ordering is necessarily isomorphic to an ordinal. Nevertheless, in the presence of ordinal abstraction, then this ordinal version of transfinite recursion is clearly equivalent to the full principle of transfinite recursion.

Observation. Work in Z. If every well-ordering is isomorphic to an ordinal, then the principle of transfinite recursion is equivalent to its restriction to ordinals.

Meanwhile, let me observe that in general, one may not recover the full principle of transfinite recursion from the weaker principle, where one uses it only on ordinals.

Theorem. (ZFC) The structure $\langle V_{\omega_1},\in\rangle$ satisfies Zermelo set theory ZC with the axiom of choice, but does not satisfy the principle of transfinite recursion. Nevertheless, it does satisfy the principle of transfinite recursion on ordinals.

Proof. It is easy to verify all the Zermelo axioms in $V_{\omega_1}$, as well as the axiom of choice, provided choice holds in $V$. Notice that there are comparatively few ordinals in $V_{\omega_1}$—only the countable ordinals exist there—but $V_{\omega_1}$ has much larger well-orderings. For example, one may find a well-ordering of the reals already in $V_{\omega+k}$ for small finite $k$, and well-orderings of much larger sets in $V_{\omega^2+17}$ and so on as one ascends toward $V_{\omega_1}$. So $V_{\omega_1}$ does not satisfy the ordinal abstraction principle and so cannot satisfy replacement or the principle of transfinite recursion. But I claim nevertheless that it does satisfy the weaker principle of transfinite recursion on ordinals, because if $F:V_{\omega_1}\to V_{\omega_1}$ is any class in this structure, and $\gamma$ is any ordinal, then we may define by recursion in $V$ the function $s(\beta)=F(s\restrict\beta)$, which gives a class $s:\omega_1\to V_{\omega_1}$ that is amenable in $V_{\omega_1}$. In particular, $s\restrict\gamma\in V_{\omega_1}$ for any $\gamma<\omega_1$, simply because $\gamma$ is countable and $\omega_1$ is regular. QED

My view is that this example shows that one doesn’t really want to consider the weakened principle of transfinite recursion on ordinals, if one is working in the Zermelo background ZC, simply because there could be comparatively few ordinals, and this imposes an essentially arbitrary limitation on the principle.

Let me point out, however, that there was a reason we had to go to $V_{\omega_1}$, rather than considering $V_{\omega+\omega}$, which is a more-often mentioned model of the Zermelo axioms. It is not difficult to see that $V_{\omega+\omega}$ does not satisfy the principle of transfinite recursion on the ordinals, because one can define the function $s(n)=\omega+n$ by recursion, setting $s(0)=\omega$ and $s(n+1)=s(n)+1$, but this function does not exist in $V_{\omega+\omega}$. This feature can be generalized as follows:

Theorem. Work in the Zermelo set theory Z. The principle of transfinite recursion on ordinals implies that if $\langle A,<\rangle$ is a well-ordered set, and $A$ is bijective with some ordinal, then $\langle A,<\rangle$ is order-isomorphic with an ordinal.

In other words, we get ordinal abstraction for well-orderings whose underlying set is bijective with an ordinal.

First, the proof of the first theorem above actually shows the following local version:

Lemma. (Z) If one has the principle of transfinite recursion with respect to a well-ordering $\langle A,<\rangle$, then $A$-replacement holds, meaning that if $F:V\to V$ is any class function, then the image $F”A$ is a set.

Proof of theorem. Suppose that $\langle A,<\rangle$ is a well-ordering, and that $A$ is bijective with some ordinal $\kappa$, and that $F:V\to V$ is a class function. Assume the principle of transfinite recursion for $\kappa$. We prove by induction on $d\in A$ that there is a unique function $s_d$ with $\dom(s)=\{a\in A\mid a\leq d\}$ and satisfying the recursive rule $s(b)=F(s\upharpoonright b)$. If this statement is true for all $d<d’$, then because the size of the predecessors of $d’$ in $\langle A,<\rangle$ is at most $\kappa$, we may by the lemma form the set $\{s_d\mid d<d’\}$, which is a set by $\kappa$-replacement. These functions cohere, and the union of these functions gives a function $t:(A\upharpoonright d’)\to V$ satisfying the recursion rule for $F$. Now extend this function one more step by defining $s(d’)=F(t)$ and $s\upharpoonright d’=t$, thereby handling the existence claim at $d’$. As in the main theorem, all these functions cohere with one another, and by $\kappa$-replacement we may form the set $\{s_d\mid d\in A\}$, whose union is the desired function $s:A\to V$ satisfying the recursion rule given by $F$, as desired. QED

For example, if you have the principle of transfinite recursion for ordinals, and $\omega$ exists, then every countable well-ordering is isomorphic to an ordinal. This explains why we had to go to $\omega_1$ to find a model satisfying transfinite recursion on ordinals. One can understand the previous theorem as showing that although the principle of transfinite recursion on ordinals does not prove ordinal abstraction, it does prove many instances of it: for every ordinal $\kappa$, every well-ordering of cardinality at most $\kappa$ is isomorphic to an ordinal.

It is natural also to consider the principle of transfinite recursion along a well-founded relation, rather than merely a well-ordered relation.

The principle of well-founded recursion. If $\langle A,\lhd\rangle$ is a well-founded relation and $F:V\to V$ is any class function, then there is a function $s:A\to V$ such that $s(b)=F(s\restrict b)$ for all $b\in A$, where $s\restrict b$ means the function $s$ restricted to the domain of elements $a\in A$ that are hereditarily below $b$ with respect to $\lhd$.

Although this principle may seem more powerful, in fact it is equivalent to transfinite recursion.

Theorem. (ZC) The principle of transfinite recursion is equivalent to the principle of well-founded recursion.

Proof. The backward direction is immediate, since well-orders are well-founded. For the forward implication, assume that transfinite recursion is legitimate. It follows by the main theorem above that ZFC holds. In this case, well-founded recursion is legitimate by the familiar arguments. For example, one may prove in ZFC that for every node in the field of the relation, there is a unique solution of the recursion defined up to and including that node, simply because there can be no minimal node without this property.  Then, by replacement, one may assemble all these functions together into a global solution. Alternatively, arguing directly from transfinite recursion, one may put an ordinal ranking function for any given well-founded relation $\langle A,\lhd\rangle$, and then prove by induction on this rank that one may construct functions defined up to and including any given rank, that accord with the recursive rule. In this way, one gets the full function $s:A\to V$ satisfying the recursive rule. QED

Finally, let me conclude this post by pointing out how my perspective on this topic differs from the treatment given by Benjamin Rin. I am grateful to him for his idea, which I find extremely interesting, and as I said, everything here is inspired by his work.

One difference is that Rin mainly considered transfinite recursion only on ordinals, rather than with respect to an arbitrary well-ordered relation (but see footnote 17 in his paper). For this reason, he had a greater need to consider whether or not he had sufficient ordinal abstraction in his applications. My perspective is that transfinite recursion, taken as a basic principle, has nothing fundamentally to do with the von Neumann ordinals, but rather has to do with a general process undertaken along any well-order. And the theory seems to work better when one undertakes it that way.

Another difference is that Rin stated his recursion principle as a principle about iterating through all the ordinals, rather than only up to any given ordinal. This made the resulting functions $S:\text{Ord}\to V$ into class-sized objects for him, and moved the whole analysis into the realm of second-order set theory. This is why he was led to prove his main equivalence with replacement in second-order Zermelo set theory. My treatment shows that one may undertake the whole theory in first-order set theory, without losing the class-length iterations, since as I explained above the class-length iterations form classes, definable from the original class functions and well-orders. And given that a completely first-order account is possible, it seems preferable to undertake it that way.

Update. (August 17, 2018) I’ve now realized how to eliminate the need for the axiom of choice in the arguments above. Namely, the main argument above shows that the principle of transfinite recursion implies the principle of well-ordered replacement, meaning the axiom of replacement for instances where the domain set is well-orderable.  The point now is that in recent work with Alfredo Roque Freire, I have realized that The principle of well-ordered replacement is equivalent to full replacement over Zermelo set theory with foundation. We may therefore deduce:

Corollary. The principle of transfinite recursion is equivalent to the replacement axiom over Zermelo set theory with foundation.

We do not need the axiom of choice for this.