As this thread title gives away I need to prove $x^y$ to be a primitive recursive function.

So mathematically speaking, I think the following are the recursion equations, well aware that I am assigning to $0^0$ the value $1$, which shouldn't be, since it is an "indeterminate" form.

\begin{cases} x^0=1 \\ x^{n+1} = x^n\cdot x \end{cases}

More formally I would write: \begin{cases} h(0) = 1 \\ h(x,y+1) = g(y,h(x,x),x) \end{cases}

as $g(x_1, x_2, x_3) = h\left(u^3_2(x_1, x_2, x_3),u^3_3(x_1, x_2, x_3)\right)$ and provided $h(x,y) = x \cdot y$ is primitive recursive.

Is my proof acceptable? Am I correct, am I missing something or am I doing anything wrong?

  • $\begingroup$ What does addition and multiplication look like? $\endgroup$
    – Raphael
    Commented Jan 16, 2013 at 12:45
  • $\begingroup$ Well, first of all, you have given what seems to be a recursion scheme, but you haven't proven anything. You also need to prove that the function you give is actually $x^y$, and this you do on double induction. Moreover, have you proved that $x \cdot y$ is p.r.? $\endgroup$ Commented Jan 16, 2013 at 12:45
  • $\begingroup$ To give a hint, try defining $f(y,x) = x^y$ (note the reversed order). This allows you to recurse on the first argument (which is the usual way of doing it). $\endgroup$ Commented Jan 16, 2013 at 12:49
  • $\begingroup$ You seem to be using $h$ for the new function and also for multiplication. $\endgroup$ Commented Jan 16, 2013 at 13:29

2 Answers 2


Supposing that $\times~(mult)$ is primitive recursive function. Then you could write:

$exp(x,y)={ x }^{ y }$

1) $exp(x,0)=x^0=1$

2) $exp(x,y+1)=x^{y+1}=(x^y)\times x=mult(exp(x,y),x)$

for $mult$ you could show that:

$mult(x,y)=x\times y$

1)$mult(x,0)=x \times 0=0$

2)$\operatorname{mult} \left({x, y + 1}\right) = x \times \left({y + 1}\right) = \left({x \times y}\right) + x = \operatorname{add} \left({\operatorname{mult} \left({x, y}\right), x}\right)$

and for addition $add$ the proof is straightforward.

Hope these are useful!


As I wrote in the comments, you haven't actually proved anything. If you want to prove that $x^y$ is p.r., you need to write it in the scheme form, and then you need to prove that indeed $x^y = f(y,x)$ for your defined $f$ for all $x$ and $y$ (by double induction).

Consider the following definition of $f(y,x) = x^y$:

$f(0,x) = s(z(x))$ (i.e., the successor of the constant zero function).

$f(y+1, x) = u^3_1(u^3_1(x^y, x, y) \cdot x, x, y)$.

I assume now that multiplication, $x \cdot y$ and wrote it infix, and obviously $x^y = f(y,x)$. The function $u^a_b$ is the $a$-ary projection of $b$.

(Ps. if this doesn't work for you, please post your scheme you want to use, otherwise we cannot do else then guess.)

  • $\begingroup$ Thank you for your answer. I don't know if my lecture notes jump to conclusions when showing that a function is primitive recursive, because they basically stick to what you call the recursion scheme, so I thought that was enough. Regardless I'd love to learn more. But, again, I don't know what you mean by scheme. I've been under the (mistaken) impression that it is some kind of fixed pattern to adapt to the case, but now I feel kind of lost. What am I looking for exactly? $\endgroup$
    – haunted85
    Commented Jan 16, 2013 at 15:45
  • $\begingroup$ Yes, it is the pattern you must follow (that's what we call the p.r. scheme). But indeed, if I give you a scheme, say $f(x,y)$ and say that it defines the Ackermann function, you wouldn't believe me without a proof that it actually is the Ackermann function, right? That's what I mean when I say you need to prove that your function actually is exponentiation. (btw. Ackermann is not p.r.) $\endgroup$ Commented Jan 16, 2013 at 15:49
  • $\begingroup$ Ok, bear with me on this, I apologize in advance if you find anything I write really really dumb. Let me start over. Look at the recursion scheme I've posted. I say $h(x,y+1)$ is built using a $g$ function such that it has three parameters so $g(x_1, x_2, x_3)$ where $x_2 = h(x,x)$ and $x_3 = x$. As I know that $h(x,y) = x \cdot y$ is p.r., am I allowed to state that $h\left(u^3_2(x_1, x_2, x_3),u^3_3(x_1, x_2, x_3)\right) = h(h(x,x),x)$ is in fact the exp function and it is p.r. because I am making use of the $h(x,x)$ which is p.r. (other than $s(x)$ and $z(x)$)? $\endgroup$
    – haunted85
    Commented Jan 16, 2013 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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