Peano Arithmetic

Abstract

Second-order theory of natural numbers characterizing the naturals, $\mathbb{N}$, via successor, addition, and multiplication, governed by the Peano axioms and the induction schema.

Definition

Peano Arithmetic ($PA$) is a first-order theory over the signature $\{0,S,+,\cdot \}$. The axioms are:

1. $\forall n.S(n)\ne 0$
2. $\forall n,m.S(n)=S(m)\to n=m$
3. Addition: $$\begin{array}{rl}\forall n.n+0& =n\\ \forall n,m.n+S(m)& =S(n+m)\end{array}$$
4. Multiplication: $$\begin{array}{rl}\forall n.n\cdot 0& =0\\ \forall n,m.n\cdot S(m)& =n\cdot m+n\end{array}$$
5. Induction Schema: For any formula $\varphi (x)$ with free variable $x$: $$(\varphi (0)\wedge \forall n.(\varphi (n)\to \varphi (S(n))))\to \forall n.\varphi (n)$$

Properties

• $PA$ is essentially incomplete; there exist sentences expressible in the language of $PA$ that are neither provable nor disprovable (Gödel’s First Incompleteness Theorem).
• The consistency of $PA$ is not provable within $PA$ (Gödel’s Second Incompleteness Theorem).
• Gentzen proved consistency of $PA$ using transfinite induction up to the ordinal ${ϵ}_0$.
• Isomorphic to the standard model $\mathbb{N}$ in second-order logic, but admits non-standard models in first-order logic.

See Also

• Heyting Arithmetic
• Gödel’s Incompleteness Theorems
• Natural Numbers Object
• Robinson Arithmetic