Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!!!

share|improve this question
1  
Please do not deface the question. It orphans the answers that people have given. –  robjohn Feb 11 '13 at 18:34

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer

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))$.

share|improve this answer
    
Thanks much!!!! –  user60465 Feb 3 '13 at 16:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.