The order isomorphism theorem without Replacement In $\sf ZF$, there is the following theorem:

Theorem: For any well-ordered set $\langle A,\prec\rangle$, there is a (unique) order isomorphism $F$ from $\langle\alpha,\in\rangle$ to $\langle A,\prec\rangle$ for some ordinal $\alpha$.
Proof: Define $F$ by transfinite recursion such that $F(\alpha)$ is the $\prec$-smallest element larger than $F[\alpha]$ (the $F$-image of $\alpha$ - note that $\alpha$ is a von Neumann ordinal and hence is equal to the set of all ordinals less than it), terminating when there are no such elements. If the recursion never terminates, this defines a function from $\rm On$ to $A$, a contradiction because $A$ is a set. Thus $F$ has domain some ordinal and the definition of $F$ ensures that $F$ is an order isomorphism.

What is the best equivalent to this theorem if we drop the axiom of replacement here (to get $\sf Z$, Zermelo set theory)? There are two important applications of replacement in the above proof: once in the transfinite recursion theorem and again to ensure that the recursion terminates at an ordinal. It would seem more natural to express the proper class version of this theorem in $\sf Z$, since it is possible to have sets map to proper classes in $\sf Z$:

Claim: For any well-ordered class $\langle A,\prec\rangle$, there is a (unique) $F$ such that either $F$ is an order isomorphism from $\langle\alpha,\in\rangle$ to $\langle A,\prec\rangle$ for some (set) ordinal $\alpha$, or $F$ is an order isomorphism from $\rm On$ to some initial segment $B$ of $A$.

Is this provable? Is there a stronger theorem that can be stated in this vein? I often see "set-like" being used in statements like these, but I think it wouldn't help here. My prototypical counterexample is to set $A=\omega$ with a well order of order-type $\omega2$ or $\omega3$ within the model $V_{\omega2}$ of $\sf Z$; in this case $F$ will only go as far as the $\omega2$-initial segment of $A$, even though $A$ is set-like (because $A$ is a set).
 A: We prove the following version of the Claim:

Theorem: For any set-like well-ordered class $\langle A,\prec\rangle$, there is a (unique) $F$ such that $F$ is an order isomorphism from $\langle\alpha,\in\rangle$ to $\langle B,\prec\rangle$ for some (class) ordinal $\alpha$ and some initial segment $B$ of $A$, and one of these three holds:

*

*$B=A$

*$\alpha=\rm On$

*$B$ is a proper class

In any of these cases it is clear that $F$ cannot be extended any farther.

We start with the following lemma:

Lemma: If $B\subseteq A$ is a nonempty subclass of $\langle A,\prec\rangle$, then there is a (unique) $x\in B$ such that $\forall y\in B,x\preceq y$.

Uniqueness follows because $\prec$ is a total order. To show existence, pick some $a\in B$. Since $\prec$ is set-like, $C=\{x\in B:x\prec a\}$ is a set. If it is empty, then $a$ is the desired element; otherwise, by the definition of a well-order there is a minimal element $x$ in $C$. Then for any $y\in B$ if $y\prec x$ then $y\in C$ so $x\preceq y$ since $x$ is minimal in $C$, a contradiction; thus $x\preceq y$.
For the main theorem, we can follow the $\sf ZF$ proof. The problem is that the transfinite recursion theorem (which constructs a function $F$ on $\rm On$ satisfying $F(\alpha)=G(F\restriction \alpha)$) uses Replacement. Nevertheless, one can still establish the following weaker version of the transfinite recursion theorem:

Given a function $G$, there is a function $F$ such that:

*

*$F$ is a proper class

*$F$ is defined on a (class) limit ordinal $\delta$

*$F\restriction \alpha$ is a set and $F(\alpha)=G(F\restriction \alpha)$ for all $\alpha<\delta$.


In $\sf ZF$ we can use the fact that $F$ is a proper class to prove that its domain is $\rm On$, but in $\sf Z$ this is as strong as we can get. It is still good enough for many purposes: for example if $G:X\to Y$ for some set $Y$, then if $F$ is defined on a set ordinal $\delta$, then $F$ is contained in $\delta\times Y$ which is a set, so we conclude that $F$ is defined on $\rm On$.
In the proof we want to take $F(\alpha)$ to be the minimal element of $\{x\in A:\forall \beta<\alpha,F(\beta)\prec y\}$, and the Lemma ensures that such an element exists. There are two reasons why the recursion will stop: (1) The set is empty for some $\alpha<\delta$, or (2) we have run out of ordinals, i.e. we reach $\delta$ without terminating. In the first case, we have constructed an order isomorphism onto $A$, and in the second case we have constructed an order isomorphism onto some initial segment $B\subseteq A$. Since $F:\delta\to B$, either $\delta$ or $B$ must be a proper class because $F$ is a proper class, and this gives us the three cases at the beginning.
