Transfinite Recursion Theorem:

Let $G:V\to V$ be a class function. Then there is a unique function $F:\operatorname{Ord}\to V$ such that $$\forall \alpha\in \operatorname{Ord}:F(\alpha)=G(F\restriction\alpha)$$

I found that the proof of this theorem often follows:

  1. First, it proves that

For all $\alpha\in\operatorname{Ord}$, there exists a unique function $f_{\alpha}$ that satisfies

(1) $\operatorname{dom}f_{\alpha} = \alpha+1$

(2) $\forall \beta\le\alpha:f_{\alpha}(\beta) = G(f_{\alpha}\restriction\beta)$

  1. Second, it defines $F$

For all $\alpha\in\operatorname{Ord}$, $F(\alpha):=f_{\alpha}(\alpha)$.

  1. It proves that $F\restriction\alpha$ is a set with the following reasoning

We have $F\restriction\alpha=\{\langle \beta,F(\beta)\rangle\mid \beta<\alpha\}$, so by Axiom of Schema Replacement, $F\restriction\alpha$ is a set.

My questions:

  1. Of my understanding, After define $F$ by $\forall\alpha\in\operatorname{Ord}:F(\alpha):=f_{\alpha}(\alpha)$. I think I've finished our task, which is to define $F$.

I'm unable to understand why the proof goes on to prove that $F\restriction\alpha$ is a set for all $\alpha\in\operatorname{Ord}$.

  1. Of my understanding, $F$ is a function and $F\restriction\alpha$ is a restriction on $F$ and thus is a set.

I'm unable to understand what is the role of Axiom of Schema Replacement here.

Thank you so much for your response!


How can you prove that $F\restriction\alpha$ is a set otherwise? This is literally a way to formulate the Replacement axiom schema: a class function restricted to a set is a set.

The point is that if you want to argue that $F(\alpha)=G(F\restriction\alpha)$, then you need to prove that $F\restriction\alpha$ is in the domain of $G$, or in other words, a set. Arguably, you could prove that $F\restriction\alpha+1=f_\alpha$, but this too will require you to appeal to Replacement (or its formulation via transfinite induction).

One good way to see this is to try and recreate the proof in a setting where we know it is bound to fail. Work in $V_{\omega+\omega}$ and consider $G(x)=\omega+n$ if $x\in V_{\omega+n+1}\setminus V_{\omega+n}$, or if $x\in V_{n+1}\setminus V_n$, and otherwise $G(x)=0$.

Now define by recursion this $F$. Then $F(0)=G(\varnothing)=0$, then $F(1)=G(F\restriction 1)=\omega+k$ for some appropriate $k$ (depending on your coding of ordered pairs and functions, of course). As you continue on, you realize that $F\restriction\omega$ is no longer a set. So how could you define $F(\omega)$?

  • $\begingroup$ Although I'm unable to understand your example (since I've just learned about Transfinite Induction/Recursion), I seem to understand your first reasoning. For the formula $F(\alpha)=G(F\restriction\alpha)$ to work, $G(F\restriction\alpha)$ must be well-defined and thus $F\restriction\alpha$ must be in the domain of $G$. Moreover, $G$ is a function that only takes set as input. So we must prove $F\restriction\alpha$ must be a set.[...] $\endgroup$ – Akira Oct 17 '18 at 15:18
  • $\begingroup$ [...]In my proof, I've already proved that $f_{\alpha}$ is a set for all $\alpha\in\operatorname{Ord}$ (by Axiom of Schema Replacement). Is it correct when I use this transformation to prove that $F\restriction\alpha$ is a set: $F\restriction\alpha=\{\langle \beta,F(\beta)\rangle\mid \beta<\alpha\}=\{\langle \beta,f_{\beta}(\beta)\rangle\mid \beta<\alpha\}=\{\langle \beta,f_{\alpha}(\beta)\rangle\mid \beta<\alpha\}=f_{\alpha}\restriction\alpha$. Since we've already know that $f_{\alpha}$ is a set. Then $f_{\alpha}\restriction\alpha$ is a set and thus $F\restriction\alpha$ is a set too. $\endgroup$ – Akira Oct 17 '18 at 15:19
  • $\begingroup$ How did you define $f_\alpha$ when $\alpha$ is a limit ordinal? $\endgroup$ – Asaf Karagila Oct 17 '18 at 15:20
  • $\begingroup$ Hi @Asaf! I did it as follows: Assume that for all $\beta<\alpha$, there exists a unique function $f_{\beta}$ that satisfies the conditions. Let $f=\bigcup_{\beta<\alpha}f_{\beta}$. The Axiom of Schema of Replacement asserts that $f$ is a set. Let $f_{\alpha}=f\cup\{\langle\alpha,G(f)\rangle\}$ Next we prove that $f_{\alpha}$ satisfies the conditions. $\endgroup$ – Akira Oct 17 '18 at 15:22
  • $\begingroup$ So, how do you know that $\bigcup_{\beta<\alpha}f_\beta$ is a set? $\endgroup$ – Asaf Karagila Oct 17 '18 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.