Exercise 6.4.1

Proof. Since in these Recursion Theorems the arguments of interest of the given operation $𝐆$ are typically functions, we assume that $𝐆$ still takes a single variable despite what the text says. Hence for each $x$ there is a unique $y$ such that $y=𝐆(x)$. It just happens that in this case the variables of interest are functions of two variables.

For ordinals $\alpha$ and $\beta$ we let $f_{\alpha ,\beta }$ be the isomorphism from the ordinal $(\beta +1)\cdot (\alpha +1)$ to the lexicographic ordering of $(\alpha +1)\times (\beta +1)$, which exists by Theorem 6.5.8. We also note that according to Exercise 6.5.2 we have

so that $(\beta +1)\cdot (\alpha +1)$ is a successor ordinal. Then for $\gamma <(\beta +1)\cdot (\alpha +1)$ define

Then for $\gamma <(\beta +1)\cdot (\alpha +1)$ we say that $t$ is a computation of length $\gamma$ if $t$ is a transfinite sequence whose domain is $\gamma +1$ and such that $t(\delta )=𝐆(t\circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta }))$ for all $\delta \le \gamma$. We note that since $(\beta +1)\cdot (\alpha +1)$ is a successor that $\gamma +1\le (\beta +1)\cdot (\alpha +1)$.

Now we define the property $𝐏(x,y,z)$ such that $𝐏(x,y,z)$ holds if and only if

1.

$x$ and $y$ are ordinal numbers and $z=t(f_{x,y}^{-1}(x,y))$ for some computation $t$ of length $(y+1)\cdot x+y$ (with respect to $𝐆$), or

2.

$x$ or $y$ is not an ordinal and $z=\varnothing$.

We prove that $𝐏$ defines an operation. Hence we have to show that for any $x$ and $y$ there is a unique $z$ such that $𝐏(x,y,z)$ holds. So consider any sets $\alpha$ and $\beta$. If $\alpha$ or $\beta$ is not an ordinal than clearly $𝐏(\alpha ,\beta ,\varnothing )$ holds and $\text{∅}$ is unique. So suppose that both $\alpha$ and $\beta$ are ordinals. Then it suffices to show that there is a unique computation of length $(y+1)\cdot x+y$ (with respect to $𝐆$) since this will make $z=t(f_{\alpha ,\beta }^{-1}(\alpha ,\beta ))$ unique. We show this via transfinite induction.

So consider any ordinal $\gamma <(\beta +1)\cdot (\alpha +1)$ so that $\gamma \le (y+1)\cdot x+y$ and assume that for all $\delta <\gamma$ that there is a unique computation of length $\delta$ and we show that there exists a unique computation of length $\gamma$, which completes the proof that $𝐏$ defines an operation.

Existence. First define a property $𝐑(x,y)$ such that $𝐑(x,y)$ holds if and only if

1.

$x$ is an ordinal where $x<\gamma$ and $y$ is a computation of length $x$ (with respect to $𝐆$), or

2.

$x$ is is an ordinal and $x\ge \gamma$ and $y=\varnothing$, or

3.

$x$ is not an ordinal and $y=\varnothing$.

Clearly by the induction hypothesis this property has a unique $y$ for every $x$. Hence we can apply the Axiom Schema of Replacement, according to which there is a set $T$ such that for every $\delta \in \gamma$ (so that $\delta <\gamma$) there is a $t$ in $T$ such that $𝐑(\delta ,t)$ holds. That is

Now, $T$ is a system of transfinite sequences (which are functions) so define $\bar{t}=\bigcup <!--\; FUNCTION\; APPLICATION\; -->T$ and let $\tau =\bar{t}\cup \left\{(\gamma ,𝐆(\bar{t}\circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\gamma }))\right\}$.

Claim 1: $\mathrm{dom}(\tau )=\gamma +1$. So consider any $𝜀\in \mathrm{dom}(\tau )$. Clearly if $𝜀=\gamma$ then $𝜀\in \gamma +1$. On the other hand if $𝜀\in \mathrm{dom}(\bar{t})$ then there is a $t\in T$ such that $𝜀\in \mathrm{dom}(t)$. But since $t$ is a computation of length $\delta$ and $\delta <\gamma$ it follows that $𝜀\le \delta <\gamma <\gamma +1$ so that $𝜀\in \gamma +1$. Hence since $𝜀$ was arbitrary $\mathrm{dom}(\tau )\subseteq \gamma +1$.

Now consider any $𝜀\in \gamma +1$ so that $𝜀\le \gamma$. If $𝜀=\gamma$ then clearly by definition $𝜀\in \mathrm{dom}(\tau )$. On the other hand if $𝜀\ne \gamma$ then $𝜀<\gamma$. So consider the $t\in T$ where $t$ is the unique computation of length $𝜀$ (which exists since $𝜀<\gamma$). Then clearly $𝜀\in \mathrm{dom}(t)$ so that $𝜀\in \mathrm{dom}(\bar{t})$. From this it follows that clearly $𝜀\in \mathrm{dom}(\tau )$ so that $\gamma +1\subseteq \mathrm{dom}(\tau )$ since $𝜀$ was arbitrary. This proves the claim.

Claim 2: $\tau$ is a function. Consider any $𝜀\in \mathrm{dom}(\tau )=\gamma +1$ so that again $𝜀\le \gamma$. If $𝜀=\gamma$ then clearly $\tau (𝜀)=\tau (\gamma )=𝐆(\bar{t}\circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\gamma }))$ is unique since $𝐆$ is an operation. On the other hand if $𝜀<\gamma$ then $\tau$ is a function so long as $\bar{t}$ is, and this is the case so long as $T$ is a compatible system of functions since $\bar{t}=\bigcup <!--\; FUNCTION\; APPLICATION\; -->T$. We show this presently.

So consider any arbitrary $t_1,t_2\in T$ where $t_1$ is the computation of length ${𝜀}_1$ and $t_2$ is the computation of length ${𝜀}_2$. Without loss of generality we can assume that ${𝜀}_1\le {𝜀}_2$. We must show that $t_1(\delta )=t_2(\delta )$ for all $\delta \le {𝜀}_1$. This we show by transfinite induction. So suppose that $t_1(\kappa )=t_2(\kappa )$ for all $\kappa <\delta \le {𝜀}_1$. Then clearly $t_1\upharpoonright \delta =t_2\upharpoonright \delta$, from which it follows that $t_1\circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta })=t_2\circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta })$ and since $𝐆$ is an operation we have $t_1(\delta )=𝐆(t_1\circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta }))=𝐆(t_2\circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta }))=t_2(\delta )$. This completes the proof of the claim.

Claim 3: $\tau (\delta )=𝐆(\tau \circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta }))$ for all $\delta \le \gamma$. So consider any such $\delta$. If $\delta =\gamma$ then since $\tau \upharpoonright \gamma =\bar{t}$ we clearly have $\tau (\delta )=\tau (\gamma )=𝐆(\bar{t}\circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\gamma }))=𝐆(\tau \circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\gamma }))=𝐆(\tau \circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta }))$. On the other hand if $\delta <\gamma$ then let $t\in T$ be the computation of length $\delta$ (which exists since $\delta <\gamma$). Then $\tau (\delta )=t(\delta )=𝐆(t\circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta }))=𝐆(\tau \circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta }))$ since $t$ is a computation (with respect to $𝐆$) and clearly $t\subseteq \tau$.

Claims 1 through 3 show that $\tau$ is a computation of length $\gamma$ and hence that such a computation exists.

Uniqueness. Now let $\sigma$ be another computation of length $\gamma$. We show that $\sigma =\tau$, which proves uniqueness. Since both $\sigma$ and $\tau$ are functions with $\mathrm{dom}(\sigma )=\gamma +1=\mathrm{dom}(\tau )$ it suffices to show that $\sigma (\delta )=\tau (\delta )$ for all $\delta \le \gamma$. We show this once again by using transfinite induction. So suppose that $\sigma (𝜀)=\tau (𝜀)$ for all $𝜀<\delta \le \gamma$. It then follows that $\sigma \upharpoonright \delta =\tau \upharpoonright \delta$ so that $\sigma \circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta })=\tau \circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta })$. Then since $\sigma$ and $\tau$ are computations we have that $\sigma (\delta )=𝐆(\sigma \circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta }))=𝐆(\tau \circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,\delta }))=\tau (\delta )$, thereby completing the uniqueness proof.

This completes the proof that $𝐏$ defines an operation.

So let $𝐅$ be the operation defined by $𝐏$. The last thing we need to show to complete the proof of the entire theorem is that $𝐅(\alpha ,\beta )=𝐆(𝐅\upharpoonright (\alpha \times \beta ))$ for all ordinals $\alpha$ and $\beta$, noting that we are treating $𝐅$ as a function even though it is an operation. Thus, for any set $X$, $𝐅\upharpoonright X$ denotes the set $\left\{(x,𝐅(x))\mid x\in X\right\}$, which forms a function with domain $X$. The range of this function is a set whose existence is guaranteed by the Axiom Schema of Replacement since $𝐅$ is an operation.

So consider any ordinals $\alpha$ and $\beta$ and the unique computation $t$ of length $(\beta +1)\cdot \alpha +\beta$. Then clearly for any $\gamma \le (\beta +1)\cdot \alpha +\beta$ we have that $t_{\gamma }=t\upharpoonright (\gamma +1)$ is a computation of length $\gamma$. Since this computation is the unique computation of length $\gamma$, by the definition of $𝐅$ as it relates to $𝐏$ we have $𝐅(f(\gamma ))=t_{\gamma }(\gamma )=t(\gamma )$. Since $\gamma$ was arbitrary this shows that $𝐅\upharpoonright (\alpha \times \beta )=t\upharpoonright (\beta +1)\cdot \alpha +\beta$. Then clearly we have $𝐅(\alpha ,\beta )=t((\beta +1)\cdot \alpha +\beta )=𝐆(t\circ (f_{\alpha ,\beta }^{-1}\upharpoonright X_{\alpha ,\beta ,(\beta +1)\cdot \alpha +\beta }))=𝐆(t\upharpoonright (\beta +1)\cdot \alpha +\beta )=𝐆(𝐅\upharpoonright (\alpha \times \beta ))$ by what was just shown above. □