1

I am given three primitive recursive functions $f$,$g$ and $r$ and I am asked to show that the following functions are primitive recursive:

\begin{equation} h(x) = \begin{cases} f(x) & \text{ if r(x) = 0} \\ g(x) & \text{if r(x)} \neq 0 \end{cases} \end{equation}

\begin{equation} t(x) = \# \{ y \leq x : f(y) < y \} \end{equation}

I don't really understand how to prove that a function is primitive recursive when these are not basic functions or when they are not composition of basic functions so I don't really know how to proceed.

McNuggets666
  • 1,583
  • Hint: you've forgotten recursion. $h$ can be defined from $f$ and $g$ by recursion. You can then use recursion again and something like $h$ with a suitable choice of $f$, $g$ and $r$ to define $t$. – Rob Arthan Nov 19 '17 at 20:31

0 Answers0