To prove non-trivial functions are primitive recursive...

Question

Im having struggle with these little things. I have got that the main idea is to prove it by mere induction but I haven't figured how to apply it in more complicated cases. The prove that the function given by $f$ where $f(0)=1$ and $f(n+1)=2^{f(0)} 3^{f(1)} \cdots p_n^{f(n)}$ where $p_n$ is the $n$-th prime number is primitive recursive. And the function given by $f$ where $f(m,n)= m-n$ iff $m \geq n$ and $f(m,n)=0$ otherwise is primitive recursive. Thank you for your time and your answer will be appreciated.

Answer 1

In most cases "brute force" (directly expressing our function using base operations) is the simplest way to go.

Your second function is known as "limited subtraction" and denoted as $m \dot - n$. It is primitive recursive, as it can be defined as $m \dot - 0 = m$, $m \dot - S(n) = P(m \dot - n)$, where $P(0) = 0$, $P(S(n)) = n$ (also primitive recursive function).

The first function is more interesting. We need to show that $a \cdot b$, $a^b$ and $p_n$ ($n$-th prime) are primitive recursive, then we can write $f(S(n)) = g(n, f(n))$ where $g(x, y) = p_x^y \cdot y$.

First, $a + b$ is primitive recursive: $a + 0 = a$ and $a + S(b) = S(a + b)$.

$a \cdot b$ is similarly primitive recursive: $a\cdot 0 = 0$ and $a \cdot S(b) = a\cdot b + b$.

Repeating once more, we get $a^b$: $a^0 = 1$, $a^{S(b)} = a^b \cdot a$.

Proving that $p_n$ is primitive recursive is significantly harder, check, for example, proof wiki.