Addition

$$ \begin{aligned} &\forall x \\;f(x, 0 ) =x \newline &\forall x \forall y \\;f(x, S(y)) = S(f(x, y)) \end{aligned} $$

Multiplication

$$ \begin{aligned} &h(x,0)\\;:=\\;0\newline &h\bigl(x,S(y)\bigr) \\;:=\\;f\bigl(h(x,y),\\,x\bigr) \end{aligned} $$

Generated by AI.

Statements

1. Zero is neutral for addition

   $$ \forall x\;\bigl(x + 0 = x\bigr). $$

   Every number plus zero is itself.

2. Successor distributes over addition

   $$ \forall x\,\forall y\;\bigl(x + S(y) = S(x + y)\bigr). $$

   Adding the successor of $y$ to $x$ is the successor of $(x+y)$.

3. Zero annihilates multiplication

   $$ \forall x\;\bigl(x \cdot 0 = 0\bigr). $$

   Any number times zero is zero.

4. Successor distributes over multiplication

   $$ \forall x\,\forall y\;\bigl(x \cdot S(y) = x\cdot y + x\bigr). $$

   Multiplying by the successor is like multiplying and then adding once more.

5. Addition is commutative

   $$ \forall x\,\forall y\;\bigl(x + y = y + x\bigr). $$

   Order doesn’t matter in addition.

6. Addition is associative

   $$ \forall x\,\forall y\,\forall z\;\bigl((x + y) + z = x + (y + z)\bigr). $$

   You can reassociate sums freely.

7. Multiplication is commutative

   $$ \forall x\,\forall y\;\bigl(x \cdot y = y \cdot x\bigr). $$

   Order doesn’t matter in multiplication either.

8. Distributive law

   $$ \forall x\,\forall y\,\forall z\;\bigl(x \cdot (y + z) = x\cdot y + x\cdot z\bigr). $$

   Multiplication distributes over addition.

9. Cancellation law for addition

   $$ \forall x\,\forall y\,\forall z\;\bigl(x + z = y + z \;\rightarrow\; x = y\bigr). $$

   If adding the same $z$ to two numbers yields equal sums, the numbers were equal.

10. Strictness of successor

    $$ \forall x\;\bigl(S(x) \neq 0\bigr). $$

    No successor ever equals zero.

11. Injectivity of successor

    $$ \forall x\,\forall y\;\bigl(S(x) = S(y) \;\leftrightarrow\; x = y\bigr). $$

    Different numbers have different successors.

12. The Induction Schema For any formula $\varphi(x)$ in the language of PA one has the axiom‐schema instance

    $$ \bigl[\;\varphi(0)\;\wedge\;\forall x\,( \varphi(x)\rightarrow \varphi(S(x)))\bigr]\;\rightarrow\;\forall x\,\varphi(x). $$

    If a property holds of 0 and is preserved by successor, then it holds of all naturals.

Proofs

Below are sketch‐proofs—using only the Peano axioms plus the usual defining equations for “+” and “·” and the induction schema—of

1. Associativity of addition
2. Commutativity of addition
3. Associativity of multiplication
4. Commutativity of multiplication

For reference, the defining axioms are:

$$ \begin{aligned} &x+0 = x,\\ &x + S(y) = S(x+y),\\ &x\cdot 0 = 0,\\ &x\cdot S(y) = x\cdot y + x, \end{aligned} $$

and induction is:

$$ \bigl[\varphi(0)\wedge\forall n\,(\varphi(n)\to\varphi(S(n)))\bigr]\;\to\;\forall n\,\varphi(n). $$

---

1. Associativity of addition

Theorem.

$$ \forall x\,\forall y\,\forall z\;\bigl(x + (y + z) = (x + y) + z\bigr). $$

Proof (by induction on $z$).

• Base $z=0$:

  $$ x + (y+0) = x + y \quad\text{and}\quad (x+y)+0 = x+y $$

  by the defining clause $y+0=y$ and then $w+0=w$.

• Inductive step: assume

  $$ x + (y + z) = (x + y) + z \quad\text{for some }z, $$

  and prove for $S(z)$:

  $$ \begin{aligned} x + \bigl(y + S(z)\bigr) &= x + S\bigl(y+z\bigr)\quad(\text{by def.})\\ &= S\bigl(x + (y+z)\bigr)\quad(\text{by def.})\\ &= S\bigl((x+y) + z\bigr)\quad(\text{IH})\\ &= (x+y) + S(z)\quad(\text{by def.}), \end{aligned} $$

  completing the induction. ∎

---

2. Commutativity of addition

Theorem.

$$ \forall x\,\forall y\;\bigl(x + y = y + x\bigr). $$

We first prove two helper lemmas.

Lemma 2.1. $\forall x;(0 + x = x).$

• By induction on $x$.

  • Base $x=0$: $0+0=0$.
  • Step: $0+S(k)=S(0+k)=S(k)$ by def. and IH.

Lemma 2.2. $\forall x,\forall y;(S(x) + y = S(x+y)).$

• By induction on $y$.

  • Base $y=0$: $S(x)+0 = S(x)$ and $S(x+0)=S(x)$.

  • Step:

    $$ \begin{aligned} S(x) + S(k) &= S\bigl(S(x)+k\bigr)\quad(\text{def.})\\ &= S\bigl(S(x+k)\bigr)\quad(\text{IH})\\ &= S\bigl(x + S(k)\bigr)\quad(\text{def.}), \end{aligned} $$

    so both sides agree.

Now the main proof by induction on $y$:

• Base $y=0$:

  $$ x + 0 = x \quad\text{and}\quad 0 + x = x $$

  by the defining equations and Lemma 2.1.

• Step assume $x + k = k + x$. Then

  $$ \begin{aligned} x + S(k) &= S\bigl(x + k\bigr)\quad(\text{def.})\\ &= S\bigl(k + x\bigr)\quad(\text{IH})\\ &= S(k) + x\quad(\text{Lemma 2.2 with }x\mapsto k,\;y\mapsto x). \end{aligned} $$

  Hence $x + S(k) = S(k) + x$. ∎

---

3. Associativity of multiplication

Theorem.

$$ \forall x\,\forall y\,\forall z\;\bigl(x\cdot(y\cdot z) = (x\cdot y)\cdot z\bigr). $$

Proof (by induction on $z$).

• Base $z=0$:

  $$ x\cdot (y\cdot 0) = x\cdot 0 = 0 \quad\text{and}\quad (x\cdot y)\cdot 0 = 0. $$

• Step assume $x\cdot(y\cdot k) = (x\cdot y)\cdot k$. Then

  $$ \begin{aligned} x\cdot\bigl(y\cdot S(k)\bigr) &= x\cdot\bigl(y\cdot k + y\bigr)\quad(\text{def. on mult.})\\ &= x\cdot(y\cdot k) + x\cdot y\quad(\text{distributivity})\\ &= (x\cdot y)\cdot k + x\cdot y\quad(\text{IH})\\ &= (x\cdot y)\cdot S(k)\quad(\text{def. on mult.}), \end{aligned} $$

  completing the induction. ∎

---

4. Commutativity of multiplication

Theorem.

$$ \forall x\,\forall y\;\bigl(x\cdot y = y\cdot x\bigr). $$

We first note the lemma $\forall x,(0\cdot x = 0)$, which is proved by induction on $x$ exactly like Lemma 2.1 above.

Then induct on $y$:

• Base $y=0$:

  $$ x\cdot 0 = 0 \quad\text{and}\quad 0\cdot x = 0. $$

• Step assume $x\cdot k = k\cdot x$. Then

  $$ \begin{aligned} x\cdot S(k) &= x\cdot k + x\quad(\text{def.})\\ &= k\cdot x + x\quad(\text{IH})\\ &= x + k\cdot x\quad(\text{commutativity of + from §2})\\ &= S(k)\cdot x\quad(\text{def. on mult.}). \end{aligned} $$

  Hence $x\cdot S(k) = S(k)\cdot x$. ∎

Predicates

1. Zero

   $$ \mathrm{Zero}(x)\\;\equiv\\;x=0. $$

2. Successor

   $$ \mathrm{Succ}(x,y)\\;\equiv\\;y=S(x). $$

3. One

   $$ \mathrm{One}(x)\\;\equiv\\;x=S(0)\\;=\\;\overline{1}. $$

4. Addition

   $$ \mathrm{Add}(x,y,z)\\;\equiv\\;x + y = z. $$

5. Multiplication

   $$ \mathrm{Mul}(x,y,z)\\;\equiv\\;x \times y = z. $$

6. Less-than

   $$ x < y \\;\equiv\\;\exists z\bigl(z \neq0\\;\wedge\\; x + z = y\bigr). $$

7. Less-or-equal

   $$ x \le y \\;\equiv\\;\exists z\\,(x + z = y). $$

8. Divisibility

   $$ x\mid y \\;\equiv\\;\exists z\\,(x \times z = y). $$

9. Evenness

   $$ \mathrm{Even}(x)\\;\equiv\\;\exists y\\,(x = y + y). $$

10. Oddness

    $$ \mathrm{Odd}(x)\\;\equiv\\;\exists y\bigl(x = (y + y) + S(0)\bigr). $$

11. Square-number

    $$ \mathrm{Square}(x)\\;\equiv\\;\exists y\\,(y \times y = x). $$

12. Prime

    $$ \mathrm{Prime}(x)\\;\equiv\\;x \neq0\\;\wedge\\;x \neq S(0)\\;\wedge\\;\forall y\forall z\Bigl(x = y\times z \\;\rightarrow\\;(y = S(0)\\;\lor\\;z = S(0))\Bigr). $$

13. Factorial

    $$ \mathrm{Fact}(n,m)\\;\equiv\\;\bigl[n=0\wedge m=S(0)\bigr]\\;\lor\\;\exists u\exists v\bigl[n=S(u)\wedge \mathrm{Fact}(u,v)\wedge m = S(u)\times v\bigr]. $$

14. Power of 2

    $$ \mathrm{Pow2}(x)\\;\equiv\\;\bigl[x = S(0)\bigr]\\;\lor\\;\exists y\bigl(\mathrm{Pow2}(y)\\;\wedge\\;x = y + y\bigr). $$

15. Exponentiation (as a ternary relation)

    $$ \mathrm{Exp}(a,b,c)\\;\equiv\\;\bigl[b=0\wedge c=S(0)\bigr]\\;\lor\\;\exists u\exists v\bigl[b=S(u)\wedge \mathrm{Exp}(a,u,v)\wedge c = a \times v\bigr]. $$

Proofs

---

1. $ \displaystyle PA\;\vdash\;\forall x\,(x + 0 = x)$

We prove by induction on $x$.

$$ \begin{aligned} \text{(Axiom)}\quad& x + 0 = x &&\text{is one of the defining axioms of \(+\).}\newline \text{Base case:}&\quad 0 + 0 = 0 &&\text{instantiate the axiom at \(x:=0\).}\newline \text{Inductive step:}&\quad\text{Assume }u + 0 = u.\newline &\quad S(u) + 0 = S\bigl(u + 0\bigr) &&\text{by the axiom }x + 0 = x\text{ with }x:=S(u).\newline &\quad\\;\\;=\\;S(u) &&\text{by the inductive hypothesis.}\newline &\quad\text{Hence }(S(u)+0 = S(u)).\newline \text{By Induction:}&\quad PA\vdash\forall x\\,(x+0=x). \end{aligned} $$

---

2. $ \displaystyle PA\;\vdash\;\forall x\,(x \le x)$

Recall $x\le y$ is defined as $\exists z\,(x+z = y)$.

$$ \begin{aligned} &\text{Fix an arbitrary \(x\).}\newline &\text{We exhibit the witness \(z:=0\).}\newline &\quad x + 0 = x &&\text{by the axiom just proved above.}\newline &\therefore\\;\exists z\\,(x+z = x).\newline &\text{Since \(x\) was arbitrary, }PA\vdash\forall x\\,(x\le x). \end{aligned} $$

No induction needed beyond our previous theorem.

---

3. $ \displaystyle PA;\vdash;\forall x\,\forall y\,\forall z;\bigl(x<y \wedge y<z ;\to; x<z\bigr)$

Here $x<y$ is shorthand for $\exists u\,[u\neq0\wedge x+u = y]$.

$$ \begin{aligned} &\text{Fix \(x,y,z\), and assume }x