Define a function %$h'$% as follows: %\[ h'(s,a,b)=\begin{cases} g(b),& \text{if $a=0$,}\h((s)_{a-1},a-1,b),& \text{if $a>0$.} \end{cases}\]% The function %$h'$% is representable, since %\[h'(s,a,b)=v\text{ if and only if }(v=g(b)\land a=0)\lor\exists c<a(a=Sc\land v=h((s)_{c},c,b)).\]%

By Theorem 33P, the function %$f(a,b)$% defined by %$f(a,b)=h'(\overline{f}(a,b),a,b)$% is representable.

The function %$f(a,b)$% is as desired: %\[\begin{align*} f(0,b)&=h'(\overline{f}(0,b),0,b)&=g(b),\f(a+1,b)&=h'(\overline{f}(a+1,b),a+1,b)=h((\overline{f}(a+1,b))_{a},a,b)&=h((f(a,b),a,b). \end{align*}\]%

9. Show that there is a representable function %$f$% such that for every %$n$%, %$a_0, \ldots , a_n,$%

%\[f(\langle a_0 , \ldots , a_n \rangle) = a_n.\]%

(For example, %$f(72)=1$% and %$f(750)=2$%.)

This falls out of catalog items 9 and 11—we just use the length of %$\langle a_0 , \ldots , a_n \rangle$%, when that length is at least 1. Let %$f(\langle a_0 , \dotsc , a_n \rangle) = (\langle a_0 , \ldots , a_n \rangle )_{\mathrm{lh }\langle a_0 , \ldots , a_n \rangle - 1}$%. That is what we want.

10. Assume that %$R$% is a representable relation and that %$g$% and %$h$% are representable functions. Show that %$f$% is representable, where %\[ f(\overline{a})=\begin{cases} g(\overline{a}),& \text{ if $\overline{a} \in R$,}\h(\overline{a}),& \text{ if $\overline{a} \not\in R$.} \end{cases}\]%

%\[f(\overline{a}) = y\text{ if and only if }(K_R(\overline{a}) = 1 \land g(\overline{a}) = y) \lor (K_R(\overline{a}) = 0 \land h(\overline{a}) = y).\]% Thus, %$f$% is representable since %$K_R$%, %$g$%, and %$h$% are.

-- IanEvans

-- ShaughanLavine - 04 May 2008