# Peano Proof Difficulty

New to first order logic and peano arithmetic, how would one prove that $$(x^y)^z = x^{z\times y}$$ without using exponentiation, only multiplication and addition?

Having difficulty figuring finding where to start.

• We can find a representing predicate for the relation $R(w,x,y)$ which holds if $x^y=w$. This will involve only the basic language of Peano arithmetic, so only addition, multiplication, and logical symbols. Then a version of the usual properties can be proved using only the Peano axioms, including instances of the first-order induction axiom scheme. The details, though in principle mechanical, will be decidedly not fun. Commented Nov 14, 2013 at 2:53
• @AndréNicolas Would you mind promoting that to an answer? Commented Nov 25, 2013 at 23:27
• @Lord_Farin: The construction of $R(w,x,y)$ is moderately lengthy, each step is easy but there are quite a few steps. (I have gone through the details repeatedly in teaching the subject.) I would be uncomfortable, in an answer, to just make the bare assertion that it can be done. Commented Nov 26, 2013 at 3:28
• I don't know if my formal development of exponentiation on $N$ can be translated into first-order Peano arithmetic, but you might have a look at "Oh, The Ambiguity!" at my math blog dcproof.wordpress.com I start with a version of Peano's Axioms and addition and multiplication functions. Commented Dec 3, 2013 at 3:43
• @AndréNicolas Since the predicate for $x^y = w$ is just a trick for encoding the recursive definition of exponentiation, is it not the case that any inductive proof based on that recursive definition will mechanically carry over accordingly? Commented Dec 3, 2013 at 9:25

I do not sure about the context what you are working. I try this. If $$n$$ is a natural number, we have the succesor $$n^+$$ of $$n$$. Using

Definition 1 (Exponentiation). Let $$x$$ be a natural number. To raise $$x$$ to the power $$0$$, we define $$x^0 := 1$$. Now suppose recursively that $$x^n$$ has been defined for some natural number $$n$$, then we define $$x^{(n^+)}:= x^n \times x$$

Definition 2 (Multiplication). Let $$x$$ be a natural number. To multiply zero to $$x$$, we define $$x \times 0 := 0$$. Now suppose recursively that we have defined how to multiply $$y$$ to $$x$$. Then we can multiply $$y^+$$ to $$x$$ by defining $$x \times (y^+) := (x \times y) + x$$.

Lemma 3. Let $$x,y,z$$ natural numbers. Then we have $$x^y x^z = x^{y + z}$$.

We want to prove:

Proposition 4. Let $$x,y,z$$ natural numbers. Then we have $$(x^y)^z=x^{y \times z}$$.

Proof. By induct on $$z$$ (with $$y$$ fixed). First we do the base case $$z = 0$$, i.e., we show $$(x^y)^0=x^{y \times 0}$$. By the definition of exponentiation, we have $$(x^y)^z = (x^y)^0 = 1$$, while $$x^{y \times 0} = x^0 = 1$$. Thus the base case is done. Now suppose inductively that $$(x^y)^z=x^{y \times z}$$, now we have to prove that $$(x^y)^{(z^+)}=x^{y \times (z^+)}$$ to close the induction. By the definition of exponentiation, we have $$(x^y)^{(z^+)} = (x^y)^{z} \times x^y$$ and, by inductive hypothesis, we obtain $$(x^y)^{z} \times x^y = x^{y \times z} \times x^y$$. By other hand, by definition of multiplication, we have $$x^{y \times (z^+)} = x^{(y \times z) + y}$$ and, by Lemma 3, $$x^{(y \times z) + y} = x^{y \times z} \times x^y$$. Thus both sides are equal, as desired. This close the induction.

To prove Lemma 3, similarly you can induct on $$z$$, with $$y$$ fixed.