Peano Axioms

Why This Matters

The Peano axioms are the foundation on which all of arithmetic is built. When you write a proof by induction, you are invoking the fifth Peano axiom. When you assume that natural numbers "just work" in any mathematical argument, you are implicitly relying on these five axioms. For ML theory, induction is the primary proof technique for statements about sequences, iterations, and recursive algorithms. Understanding where induction comes from clarifies when it applies and what it assumes.

The Five Axioms

Definition

Peano Axioms

The Peano axioms define a set $\mathbb{N}$ together with a distinguished element $0 \in \mathbb{N}$ and a function $S: \mathbb{N} \to \mathbb{N}$ (the successor function) satisfying:

1. Zero exists: $0 \in \mathbb{N}$
2. Closure under successor: For every $n \in \mathbb{N}$, $S(n) \in \mathbb{N}$
3. Injectivity of successor: If $S(m) = S(n)$, then $m = n$
4. Zero is not a successor: There is no $n \in \mathbb{N}$ such that $S(n) = 0$
5. Induction: If a set $A \subseteq \mathbb{N}$ contains $0$ and is closed under $S$ (meaning $n \in A$ implies $S(n) \in A$), then $A = \mathbb{N}$

What Each Axiom Does

Axiom 1 gives us a starting point. Without it, $\mathbb{N}$ could be empty.

Axiom 2 says we can always count one more. The natural numbers do not stop.

Axiom 3 prevents "merging." Two different numbers cannot have the same successor. Combined with Axiom 4, this ensures the natural numbers form a chain: $0, S(0), S(S(0)), \ldots$ with no repetitions.

Axiom 4 prevents cycles. Without it, the chain could loop back: $S(n) = 0$ for some $n$ would make $\mathbb{N}$ finite and cyclic (like clock arithmetic).

Axiom 5 is the most powerful. It says the natural numbers consist of exactly what you get by starting at $0$ and repeatedly applying $S$. No "rogue" elements exist. This axiom is the foundation of proof by induction.

Main Theorems

Theorem

Principle of Mathematical Induction

Statement

Let $P(n)$ be a property of natural numbers. If:

1. $P(0)$ is true (base case)
2. For all $n \in \mathbb{N}$, $P(n) \implies P(S(n))$ (inductive step)

Then $P(n)$ is true for all $n \in \mathbb{N}$.

Intuition

Let $A = \{n \in \mathbb{N} : P(n) \text{ is true}\}$. The base case says $0 \in A$. The inductive step says $A$ is closed under $S$. By Axiom 5, $A = \mathbb{N}$. Induction is not a separate theorem; it is a direct restatement of Axiom 5 in terms of propositions rather than sets.

Proof Sketch

Define $A = \{n \in \mathbb{N} : P(n)\}$. By hypothesis, $0 \in A$ and $n \in A$ implies $S(n) \in A$. By Peano Axiom 5, $A = \mathbb{N}$. Therefore $P(n)$ holds for all $n \in \mathbb{N}$.

Why It Matters

Induction is the workhorse proof technique in discrete mathematics and theoretical CS. Convergence proofs for iterative algorithms, correctness proofs for recursive programs, and bounds on sequence growth all rely on induction. It is the axiomatic justification for "if it works for step $k$, it works for step $k+1$."

Failure Mode

Induction requires both the base case and the inductive step. A common error is proving the inductive step without verifying the base case. For example, "if all horses in a group of size $n$ are the same color, then all horses in a group of size $n+1$ are the same color" has a valid-looking inductive step but fails at $n = 1 \to 2$ because two groups of size 1 need not overlap. The base case ($n = 2$, not $n = 1$) fails.

Defining Arithmetic from Peano Axioms

Addition is defined recursively using the successor function:

$m + 0 = m$

$m + S(n) = S(m + n)$

Multiplication is defined using addition:

$m \cdot 0 = 0$

$m \cdot S(n) = m \cdot n + m$

From these recursive definitions, all familiar properties (commutativity, associativity, distributivity) can be proved by induction.

Connection to Godel Incompleteness

Peano arithmetic (PA) is the first-order theory obtained from the Peano axioms with the induction axiom replaced by an axiom schema (one instance for each first-order formula). Godel's first incompleteness theorem states that PA, if consistent, is incomplete: there exist true statements about natural numbers that cannot be proved within PA.

This means no finite axiom system can capture all truths about natural numbers. The Peano axioms are the starting point, but they are provably insufficient to decide every arithmetic question.

Strong Induction

Definition

Strong Induction

Strong induction (or complete induction) uses a stronger inductive hypothesis: assume $P(k)$ for all $k < n$, then prove $P(n)$.

Formally: if for all $n$, the statement "for all $k < n$, $P(k)$" implies $P(n)$, then $P(n)$ holds for all $n \in \mathbb{N}$.

Strong induction is equivalent to ordinary induction over the Peano axioms. The proof uses the well-ordering principle: every nonempty subset of $\mathbb{N}$ has a least element.

Common Confusions

Watch Out

Induction is circular reasoning

Induction does not assume what it is trying to prove. The inductive step proves the conditional statement $P(n) \implies P(n+1)$. Combined with the base case $P(0)$, this gives $P(n)$ for all $n$ by Axiom 5. The logical structure is: base case, then modus ponens applied repeatedly.

Watch Out

Induction works for real numbers

Standard induction applies only to natural numbers (or, more generally, to well-ordered sets). You cannot induct over the real numbers because between any two reals there are infinitely many others, and there is no "next" real. For continuous arguments, you need different techniques (e.g., continuity arguments, the least upper bound property).

Canonical Examples

Example

Sum of first n natural numbers

Claim: $\sum_{i=0}^{n} i = n(n+1)/2$.

Base case: $n = 0$. $\sum_{i=0}^{0} i = 0 = 0 \cdot 1 / 2$. True.

Inductive step: assume $\sum_{i=0}^{n} i = n(n+1)/2$. Then $\sum_{i=0}^{n+1} i = n(n+1)/2 + (n+1) = (n+1)(n+2)/2$. This matches the formula for $n+1$.

By induction, the formula holds for all $n \in \mathbb{N}$.

Exercises

ExerciseCore

Problem

Using the recursive definition of addition from the Peano axioms, prove that $S(n) = n + S(0)$ for all $n \in \mathbb{N}$.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Why does the second-order version of the induction axiom (quantifying over all subsets $A \subseteq \mathbb{N}$) pin down $\mathbb{N}$ uniquely up to isomorphism, while the first-order axiom schema does not?

Hint

Reveal Solution

References

Canonical:

• Peano, Arithmetices Principia, Nova Methodo Exposita (1889)
• Enderton, A Mathematical Introduction to Logic (2001), Chapter 3

Current:

• Hodel, An Introduction to Mathematical Logic (2013), Chapter 6

• Kaye, Models of Peano Arithmetic (1991), Chapters 1-2

• Munkres, Topology (2000), Chapter 1 (set theory review)

Next Topics

• Number theory and ML: how number-theoretic ideas connect to machine learning