2
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Nov 14, 2013 at 2:53
  • $\begingroup$ @AndréNicolas Would you mind promoting that to an answer? $\endgroup$
    – Lord_Farin
    Commented Nov 25, 2013 at 23:27
  • $\begingroup$ @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. $\endgroup$ Commented Nov 26, 2013 at 3:28
  • $\begingroup$ 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. $\endgroup$ Commented Dec 3, 2013 at 3:43
  • $\begingroup$ @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? $\endgroup$ Commented Dec 3, 2013 at 9:25

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .