1
$\begingroup$

Let $V$ be the class of all sets, $\operatorname{Ord}$ be the class of all ordinals, and $G:V\to V$ be a class function.

Transfinite Recursion Theorem:

There exists a class function $F:\operatorname{Ord}\to V$ such that $F(\alpha)=G(F\restriction \alpha)$ for all $\alpha\in\operatorname{Ord}$.


While I'm able to prove that Transfinite Recursion Theorem implies the below theorem, I have tried but to no avail in proving that the theorem implies Transfinite Recursion Theorem.

I would like to ask if it is possible to prove that this theorem implies Transfinite Recursion Theorem.

Thank you for your help!


Theorem:

Let $G_1,G_2,G_3$ be class functions from $V$ to $V$. There exists a class function $F:\operatorname{Ord}\to V$ such that

(1) $F(0)=G_1(\emptyset)$

(2) $F(\alpha+1)=G_2(F(\alpha))$ for all $\alpha\in\operatorname{Ord}$

(3) $F(\alpha)=G_3(F\restriction\alpha)$ for all limit $\alpha\neq 0$

$\endgroup$
2
  • $\begingroup$ Do you know how to prove strong induction (on $\mathbb{N}$) from weak induction? It's the same idea. $\endgroup$ – Eric Wofsey Oct 25 '18 at 2:46
  • $\begingroup$ Hi @EricWofsey! Yes, I do. I will try your suggestion. $\endgroup$ – LE Anh Dung Oct 25 '18 at 2:54
1
$\begingroup$

The trick is to not construct $F$ itself, but to construct the function $H$ which sends $\alpha$ to $F\restriction \alpha$. That way, at successor steps you have access to the entire history of the recursion so far and not just the last step.

In detail, given $G:V\to V$, we define $G_1$, $G_2$, and $G_3$ as follows: $$G_1(x)=\emptyset$$ $$G_2(x)=x\cup\{(\operatorname{dom}(x),G(x))\}$$ $$G_3(x)=\bigcup\operatorname{ran}(x)$$ By the theorem, we then get a function $H:Ord\to V$ such that $H(0)=G_1(\emptyset)$, $H(\alpha+1)=G_2(H(\alpha))$, and $H(\alpha)=G_3(H\restriction\alpha)$ for $\alpha\neq 0$ limit. It is then easy to prove by induction that $H(\alpha)$ is a function with domain $\alpha$ for each $\alpha$, with $H(\alpha)\restriction \beta=H(\beta)$ for all $\beta<\alpha$. So, defining $F=\bigcup\operatorname{ran}(H)$, $F$ is a function on $Ord$ with $F\restriction\alpha=H(\alpha)$ for each $\alpha$. For each $\alpha$, we then have $$F(\alpha)=H(\alpha+1)(\alpha)=G_2(H(\alpha))(\alpha)=G_2(F\restriction\alpha)(\alpha).$$ Since $\operatorname{dom}(F\restriction\alpha)=\alpha$, our definition of $G_2$ tells us that $$F(\alpha)=G_2(F\restriction\alpha)(\alpha)=G(F\restriction\alpha),$$ as desired.

$\endgroup$
5
  • $\begingroup$ I'm feeling confused. You have shown how to derive the Q's 2nd theorem from its first. But the proposer seems to want to see the 1st derived from the second, although it is obvious that if the second one holds, then, for a given $G$, we can simply let $G_1=G_2=G_3=G$. So I'm thinking that the proposer stated the Q backwards. $\endgroup$ – DanielWainfleet Oct 25 '18 at 3:49
  • $\begingroup$ @DanielWainfleet: I am deriving the first theorem from the second. I start with a function $G$ as in the first theorem, then use the second theorem to get a function $H$ and then define $F$ from $H$ which verifies the conclusion of the first theorem. It does not work to simply define $G_1=G_2=G_3=G$ since $G_2$ takes as its input just $F(\alpha)$, not $F\restriction\alpha$. $\endgroup$ – Eric Wofsey Oct 25 '18 at 4:04
  • $\begingroup$ Thank you so much! You make my day :) $\endgroup$ – LE Anh Dung Oct 25 '18 at 8:14
  • $\begingroup$ Thank you for clearing up my confusion. $\endgroup$ – DanielWainfleet Oct 25 '18 at 21:26
  • $\begingroup$ Hi! I'm now struggling with a seemingly similar problem like this one. I have tried to replicate your proof but failed at the end. If you don't mind, please have a look at math.stackexchange.com/questions/2970783/…. Thank you for your help! $\endgroup$ – LE Anh Dung Oct 27 '18 at 14:16
0
$\begingroup$

I fill in @Eric Wofsey's proof with detail and post it here. All credits are given to @Eric Wofsey.


Given $G:V\to V$, we define $G_1$, $G_2$, and $G_3$ as follows: $$\begin{align}&G_1(x)=\emptyset\text{ for all }x\\&G_2(x)=\begin{cases} x\cup\{(\operatorname{dom}(x),G(x))\}&\text{if }x\text{ is a function}\\\emptyset&\text{otherwise}\end{cases}\\&G_3(x)=\begin{cases} \bigcup\operatorname{ran}(x)&\text{if }x\text{ is a function}\\\emptyset&\text{otherwise}\end{cases}\end{align}$$

By The theorem, there is a class function $H:\operatorname{Ord}\to V$ such that $H(0)=G_1(\emptyset)$, $H(\alpha+1)=G_2(H(\alpha))$, and $H(\alpha)=G_3(H\restriction\alpha)$ for $\alpha\neq 0$ limit.

First, we prove by induction that $H(\alpha)$ is a function with domain $\alpha$ for all $\alpha\in\operatorname{Ord}$ and with $H(\alpha)\restriction \beta=H(\beta)$ for all $\beta<\alpha$.

  • $H(0)=G_1(0)=\emptyset$. Then the statement is trivially true for $\alpha=0$.

  • Assume that the statement is true for $\alpha$. Then $H(\alpha+1)=G_2(H(\alpha))=$ $H(\alpha)\cup\{(\operatorname{dom}(H(\alpha)),G(H(\alpha)))\}=H(\alpha)\cup\{(\alpha,G(H(\alpha)))\}$. It follows that $\operatorname{dom}(H(\alpha+1))=\operatorname{dom}(H(\alpha))\cup \{\alpha\}=\alpha\cup \{\alpha\}=\alpha+1$. For $\beta=\alpha$, $H(\alpha+1)\restriction \beta=H(\alpha+1)\restriction \alpha=H(\alpha)=H(\beta)$. For $\beta<\alpha$, $H(\alpha+1)\restriction \beta=$ $H(\alpha)\restriction \beta=H(\beta)$. Thus $H(\alpha+1)\restriction \beta=H(\beta)$ for all $\beta<\alpha+1$.

  • Assume that the statement is true for all $\beta<\alpha$ where $\alpha\neq\emptyset$ is limit ordinal. Then $H(\alpha)=G_3(H(\alpha))=\bigcup\operatorname{ran}(H(\alpha))=\bigcup\{H(\beta)\mid \beta<\alpha\}$. For any $\beta_1\le\beta_2<\alpha$: $H(\beta_2)\restriction\beta_1=H(\beta_1)$and thus $H(\beta_1)\subseteq H(\beta_2)$. Then $H(\alpha)=\bigcup\{H(\beta)\mid \beta<\alpha\}$ is actually a function. It follows that $\operatorname{dom}(H(\alpha))=\bigcup_{\beta<\alpha}\operatorname{dom}(H(\beta))=\bigcup_{\beta<\alpha}\beta=\alpha$ since $\alpha$ is limit ordinal. Moreover, $H(\alpha)\restriction \beta=\{(\gamma,H(\alpha)(\gamma))\mid \gamma<\beta\}=\{(\gamma,H(\gamma+1)(\gamma))\mid \gamma<\beta\}=$ $\{(\gamma,H(\beta)(\gamma))\mid \gamma<\beta\}=H(\beta)$.

As a result, $\forall\beta<\alpha:H(\alpha)\restriction \beta=H(\beta)$ and thus $\forall\beta<\alpha:H(\beta)\subsetneq H(\alpha)$.

Next we define $F=\bigcup\operatorname{ran}(H)$. Then $F=\bigcup\{H(\alpha)\mid \alpha\in\operatorname{Ord}\}$ is a function with domain $\operatorname{Ord}$ and with $F\restriction\alpha=\{F(\beta)\mid\beta<\alpha\}=\{H(\beta+1)(\beta)\mid\beta<\alpha\}=\{H(\alpha)(\beta)\mid\beta<\alpha\}=H(\alpha)$ for all $\alpha\in\operatorname{Ord}$.

Since $F\restriction\alpha=H(\alpha)$ and $\operatorname{dom}(H(\alpha))=\alpha$, $\operatorname{dom}(F\restriction\alpha)=\alpha$. Then $G_2(F\restriction\alpha)=(F\restriction\alpha)\cup \{(\alpha,G(F\restriction\alpha))\}$ and thus $G_2(F\restriction\alpha)(\alpha)=G(F\restriction\alpha)$.

For each $\alpha\in\operatorname{Ord}$, we have $F(\alpha)=H(\alpha+1)(\alpha)=G_2(H(\alpha))(\alpha)=G_2(F\restriction\alpha)(\alpha)=G(F\restriction\alpha)$.


Update: I have found another way to define $F$

We define $F$ as follows $F(\alpha):=H(\alpha+1)(\alpha)$

Then $F(\alpha)=H(\alpha+1)(\alpha)=G_2(H(\alpha))(\alpha)=(H(\alpha)\cup\{(\operatorname{dom}(H(\alpha)),G(H(\alpha)))\})(\alpha)=(H(\alpha)\cup\{(\alpha,G(H(\alpha)))\})(\alpha)=G(H(\alpha))$.

Moreover, $H(\alpha)=\{(\beta,H(\alpha)(\beta))\mid\beta<\alpha\}=\{(\beta,H(\beta+1)(\beta))\mid\beta<\alpha\}=\{(\beta,F(\beta))\mid\beta<\alpha\}=F\restriction\alpha$.

Thus $F(\alpha)=G(H(\alpha))=G(F\restriction\alpha)$.

$\endgroup$

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.