On Shoenfield's Mathematical Logic, Chapter 6 Q2

Question

I need help with Chapter 6, Exercise 2 of Shoenfield's Mathematical Logic:

Let $H$ and $K$ be recursive functions, and let $F$ and $G$ be defined inductively by: $$ F(a,\mathfrak{a}) = H(\bar{F}(a,\mathfrak{a}), \bar{G}(a,\mathfrak{a}), a, \mathfrak{a}) \\ G(a,\mathfrak{a}) = K(\bar{F}(a + 1,\mathfrak{a}), \bar{G}(a,\mathfrak{a}), a, \mathfrak{a}) $$ Show that $F$ and $G$ are recurseive. [Hint: Let $L(a,\mathfrak{a}) := \langle{F(a,\mathfrak{a}),G(a,\mathfrak{a})}\rangle$, and use R14 to show that $L$ is recursive.]

---

My main issue lies with showing that $L$ is recursive. Suppose that is done, we can then conclude that: $$ F(a,\mathfrak{a}) = \beta(L(a,\mathfrak{a}),1) \\ G(a,\mathfrak{a}) = \beta(L(a,\mathfrak{a}),2) $$ where $\beta$ is the Godel beta function, which is recursive, so both $F$ and $G$ are recursive. However, I tried various methods to show that $L$ is recursive, such as expanding the definition of $F$ and $G$ in $L$, but to no avail.

Any help is appreciated.

Answer 1

$ \renewcommand{\c}[1]{\langle #1 \rangle} \renewcommand{\bb}[1]{\left( #1 \right)} \renewcommand{\In}{\mathrm{In}} $ This proof is motivated by @M477's answer, and serves to fill in the details. Let $F,G_1,\dots,G_k$ be functions. We say that $F$ is a recursive function of $G_1,\dots,G_k$ if there exists a recursive function $H$ such that:\begin{align*} F(a,\mathfrak{a}) = H(G_1(a,\mathfrak{a}),\dots,G_k(a,\mathfrak{a}),a,\mathfrak{a})\end{align*}

Note that:

1. If $G_1,\dots,G_k$ are all recursive and $F$ is a recursive function of $G_1,\dots,G_k$, then $F$ is recursive by R2.

2. If $F$ is a recursive function of $G_1,\dots,G_k$ and each $G_i$ is a recursive function of $H_1,\dots,H_\ell$, then $F$ is a recursive function of $H_1,\dots,H_\ell$ by R2.

3. If $F$ is a recursive function of $\bar{F}$, then $F$ is recursive by R14.

---

Following the hint, given $a,\mathfrak{a}$, define $L(a,\mathfrak{a}) := \c{F(a,\mathfrak{a}),G(a,\mathfrak{a})}$. To show that $L$ is recursive, we proceed in a few steps. The proof will proceed in several steps.

Step 1 - Show that $\bar{F}$,$\bar{G}$ are both recursive functions of $\bar{L}$. For $\bar{F}$, we have: \begin{align*} \bar{F}(a,\mathfrak{a}) &= \mu x\bb{lh(x) = a \wedge \forall i_{i < a}\bb{(x)_i = F(i,a)}} \\ &= \mu x\bb{lh(x) = a \wedge \forall i_{i < a}\bb{(x)_i = ((\bar{L}(a,\mathfrak{a}))_i)_0}} \end{align*} and similarly for $\bar{G}$ as well.

Step 2 - Show that $F$ is a recursive function of $\bar{L}$. By definition, we see that $F$ is a recursive function of $\bar{F},\bar{G}$, and is hence a recursive function of $\bar{L}$ by (2) above.

Step 3 - Show that $(a,\mathfrak{a}) \mapsto \bar{F}(a+1,\mathfrak{a})$ is a recursive function of $\bar{L}$. Observe that: \begin{align*} \bar{F}(a+1,\mathfrak{a}) &= \c{F(0,a),\dots,F(a,\mathfrak{a})} \\ &= \mu x\bb{lh(x) = a + 1 \wedge \In(x,a) = \bar{F}(a,\bar{a}) \wedge (x)_a = F(a,\mathfrak{a})} \end{align*} Thus, $(a,\mathfrak{a}) \mapsto F(a+1,\mathfrak{a})$ is a recursive function of $F,\bar{F}$, and is thus a recursive function of $\bar{L}$ by (2).

Step 4 - Show that $G$ is a recursive function of $\bar{L}$. Similarly, by definition we see that $G$ is a recursive function of $(a,\mathfrak{a}) \mapsto \bar{F}(a+1,\mathfrak{a}),\bar{G}$, and is hence a recursive function of $\bar{L}$ by the previous steps and (2) above.

Step 5 - Show that $L$ is recursive. Finally, since $L(a,\mathfrak{a}) = \c{F(a,\mathfrak{a}),G(a,\mathfrak{a})}$ and both $F$ and $G$ are recursive functions of $\bar{L}$, we have that $L$ is a recursive function of $\bar{L}$, and is hence recursive.

Answer 2

I have come up with a solution and it seems to be correct.

If you hope to apply the R14, then you will need to introduce $\overline{L}(a,\textbf{a})$ which is, by usual definition, $\langle \langle F(0,\textbf{a}),G(0,\textbf{a})\rangle,...,\langle F(a-1,\textbf{a}),G(a-1,\textbf{a})\rangle \rangle$. Then $F(0,\textbf{a}), ..., F(a-1, \textbf{a}), G(0,\textbf{a}), ..., G(a-1, \textbf{a})$ are all just recursive functions of $\overline{L}(a,\textbf{a})$ since $((\overline{L}(a,\textbf{a}))_{i})_{0}$ are just recursive functions of $\overline{L}(a,\textbf{a})$ for $0\leq i\leq a-1$.Then $\overline{F}(a,\textbf{a})$ and $\overline{G}(a,\textbf{a})$ are just recursive functions of $\overline{L}(a,\textbf{a})$. Now it is quite clear and you will easily get that $L(a,\textbf{a}) = G(\overline{L}(a,\textbf{a}),a, \textbf{a})$ and apply R14, you get that F,G are both recursive.

(This is the first time I answer a Q here. So if there is anything wrong or unclear, please let me know :)