# Principle of Mathematical Induction/Peano Structure

## Theorem

Let $\struct {P, s, 0}$ be a Peano structure.

Let $\map Q n$ be a propositional function depending on $n \in P$.

Suppose that:

$(1): \quad \map Q 0$ is true
$(2): \quad \forall n \in P: \map Q n \implies \map Q {\map s n}$

Then:

$\forall n \in P: \map Q n$

### Principle of Finite Induction

Let $\struct {P, s, 0}$ be a Peano structure.

Let $S \subseteq P$.

Suppose that:

$(1): \quad 0 \in S$
$(2): \quad \forall n: n \in S \implies \map s n \in S$

Then:

$S = P$

## Proof

Let $A \subseteq P$ be defined by:

$A := \set {n \in P: \map Q n}$

From $(1)$, $0 \in A$.

From $(2)$:

$\forall n \in P: n \in A \implies \map s n \in A$

As this holds for all $n \in P$, it holds a fortiori for all $n \in A$.

Thus the condition:

$n \in A \implies \map s n \in A$

is satisfied.

$A = P$

That is:

$\forall n \in P: \map Q n$

$\blacksquare$

## Also defined as

Some treatments of Peano's axioms define the non-successor element (or primal element) to be $1$ and not $0$.

The treatments are similar, but the $1$-based system results in an algebraic structure which has no identity element for addition, and so no zero for multiplication.

## Sources

WARNING: This link is broken. Amend the page to use {{KhanAcademySecure}} and check that it links to the appropriate page.