# Show $x^y$ is a primitive recursive function

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?

• What does addition and multiplication look like? – Raphael Jan 16 '13 at 12:45
• 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.? – Pål GD Jan 16 '13 at 12:45
• 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). – Pål GD Jan 16 '13 at 12:49
• You seem to be using $h$ for the new function and also for multiplication. – Carl Mummert Jan 16 '13 at 13:29

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

• 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? – haunted85 Jan 16 '13 at 15:45
• 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.) – Pål GD Jan 16 '13 at 15:49
• 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)$)? – haunted85 Jan 16 '13 at 16:09