= Peano arithmetic
{c}
{wiki}
<Peano arithmetic> is the <first-order theory> obtained by adding the full first-order induction schema to <Robinson arithmetic>. For each arithmetic <first-order formula> $\varphi(x,\bar y)$, include the universal closure in its parameter variables $\bar y$ of
$$
\bigl(\varphi(0,\bar y)\wedge\forall x(\varphi(x,\bar y)\to\varphi(Sx,\bar y))\bigr)
\to\forall x\varphi(x,\bar y).
$$
The schema supplies one axiom for every formula; it does not quantify over arbitrary subsets of the universe. The order relation can be added by a defining axiom such as $x<y\leftrightarrow\exists z\,(y=x+Sz)$.
For example, induction on $x$ proves $0+x=x$, complementing the axiom $x+0=x$. Despite its intended interpretation in the <natural numbers>, <Peano arithmetic> also has <non-standard models of arithmetic> by the <compactness theorem>. First-order induction reaches every definable subset satisfying its hypotheses, without making the theory categorical.<Introduction to the Theory of Computation: Computability, Complexity, and the Lambda Calculus by Jean Gallier and Jocelyn Quaintance (2020)>[Chapter6, printed p.156, induction schema]{ref}
Back to article page
