Recursive relation using successor function

Question

What is the recursive relation for $$H(m)=2^{(m^2)}$$ using successor function recursive relation for multiplication: $$mult(x,0)=0; mult(x,S(y))=add(x,mult(x,y))$$ recursive relation for addition: $$add(x,0)=x; add(x,S(y))=S(add(x,y))$$ Where H function is a composite function. I need to come up with recursive relation for that function. What steps do you suggest I take? Thanks so much in advance!!!

Answer 1

We note that all primitive recursive functions $p(x,y)$ defined by primitive recursion are of the form, $$p(x,y) = \begin{cases} p(x,0)= g(x) \\ p(x,Sy)= h(x,y,p(x,y)) \\ \end{cases}$$ Firstly, we define sum$(x,y)$ by primitive recursion as follows, $$\text{sum}(x,y) = \begin{cases} \text{sum}(x,0) = I_{1}^{1}(x) \\ \text{sum}(x,Sy) = S(I_{3}^{3}(x,y,\text{sum}(x,y))) \end{cases}$$ This defines that $x + 0 = x$ and that $x + Sy = S(x+y)$, which are both axioms of $PA$. Thus, sum$(x,y)$ is defined by primitive recursion and composition from initial functions $S$ and $I_{i}^{k}$, so we may conclude that sum$(x,y)$ is a primitive recursive function. Secondly, we define prod$(x,y)$ by primitive recursion as follows, $$\text{prod}(x,y) = \begin{cases} \text{prod}(x,0) = \mathcal{Z}(x) \\ \text{prod}(x,Sy)= \text{sum}(I_{3}^{3}(x,y,\text{prod}(x,y)),I_{1}^{3}(x,y,\text{prod}(x,y))) \end{cases}$$ This defines that $x \times 0 = 0$ and that $x \times Sy = (x \times y) + x$, as desired. Thus, prod$(x,y)$ is defined by primitive recursion and composition from the initial functions $S$, $I_{i}^{k}$, and $\mathcal{Z}$, so we may conclude that prod$(x,y)$ is a primitive recursive function. Thirdly, we define exp$(x,y)$ by primitive recursion as follows, $$\text{exp}(x,y) = \begin{cases} \text{exp}(x,0) = S(\mathcal{Z}(x)) \\ \text{exp}(x,Sy) = \text{prod}(I_{3}^{3}(x,y,\text{exp}(x,y)),I_{1}^{3}(x,y,\text{exp}(x,y))) \\ \end{cases}$$ This defines that $x^0 = 1$ and that $x^{Sy} = x^y \times x$. Thus, exp$(x,y)$ is defined by primitive recursion and composition from the initial functions $S$, $I_{i}^{k}$, and $\mathcal{Z}$, so we may conclude that exp$(x,y)$ is a primitive recursive function.

Answer 2

Define the exponential $\mathit{exp}(m, n)$ in the absolutely standard way:

$\mathit{exp}(m, 0) = 1$,

$\mathit{exp}(m, Sn) = \mathit{mult}(\mathit{exp}(m, n), m)$.

That shows $\mathit{exp}$ is p.r. And now put

$H(m) = \mathit{exp}(2, \mathit{mult}(m, m))$.

Then $H$ is p.r. since it is a composition of p.r. functions.

Or of course you could alternatively, more simply, define the function $\mathit{exp_2}(n) = 2^n$ by

$\mathit{exp_2}(0) = 1$,

$\mathit{exp_2}(Sn) = \mathit{mult}(\mathit{exp_2}(n), 2)$.

and then put

$H(m) = \mathit{exp_2}(\mathit{mult}(m, m))$.