$\newcommand\dom{\text{dom}}
\newcommand\ran{\text{ran}}
\newcommand\restrict{\upharpoonright}$
At 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.