Well-Founded Induction

The Principle of Well-Founded Induction

Statement

Let $\prec$ be a well-founded relation on $A$. Let $P$ be a property. If:

$\forall x \in A. (\forall y \prec x. P(y)) \Rightarrow P(x)$

then $\forall x \in A. P(x)$ holds.

Intuition

To prove $P(x)$ for all $x$, we may assume $P(y)$ holds for all $y \prec x$ when proving $P(x)$.

This generalises strong induction from $\mathbb{N}$ to any well-founded structure.

Examinable Proof

Theorem: Well-founded induction is valid.

Proof:

Suppose $\forall x \in A. (\forall y \prec x. P(y)) \Rightarrow P(x)$ holds.

Assume for contradiction that $S = \{x \in A : \neg P(x)\}$ is non-empty.

Since $\prec$ is well-founded, $S$ has a minimal element $m$.

Key observation: $m \in S$ implies $\neg P(m)$, but $\forall y \prec m. P(y)$ holds (since $m$ is minimal in $S$).

By assumption, $(\forall y \prec m. P(y)) \Rightarrow P(m)$.

This gives $P(m)$, contradicting $m \in S$.

Therefore $S = \emptyset$, i.e., $\forall x. P(x)$.

Connection to Strong Induction

On $\mathbb{N}$

Strong induction on $\mathbb{N}$ is exactly well-founded induction for $\prec \; = \; <$ on $\mathbb{N}$.

The premise becomes: $\forall n. (\forall m < n. P(m)) \Rightarrow P(n)$.

Base Case

For $n = 0$: the hypothesis $\forall m < 0. P(m)$ is vacuously true, so we must prove $P(0)$ directly.

This recovers the base case of strong induction.

Using Well-Founded Induction

Recipe

1. Identify the well-founded relation $\prec$
2. State the induction hypothesis: $\forall y \prec x. P(y)$
3. Prove $P(x)$ assuming the hypothesis

Example: Termination of Euclid’s Algorithm

Claim: $\gcd(a, b)$ terminates for all $a, b \in \mathbb{N}$ (not both zero).

Well-founded relation: Lexicographic ordering on pairs $(a, b)$.

Proof: At each step, $(a, b) \mapsto (b, a \bmod b)$.

Since $a \bmod b < b$, the second component decreases (or stays zero while the first decreases).

By well-foundedness of the lexicographic order, the process terminates.

Lexicographic Ordering

Definition

For well-founded relations $\prec_A$ on $A$ and $\prec_B$ on $B$, define the lexicographic order on $A \times B$:

$(a_1, b_1) \prec (a_2, b_2) \iff a_1 \prec_A a_2 \lor (a_1 = a_2 \land b_1 \prec_B b_2)$

Well-Foundedness

If $\prec_A$ and $\prec_B$ are well-founded, then $\prec$ (lexicographic) is well-founded.

Application

This justifies nested induction or induction on pairs.

Induction on Recursive Structures

Trees

For finite trees with subtree relation “is proper subtree of”:

This is well-founded (trees have finite depth).

Lists

For lists with “tail” operation:

“Is a proper suffix of” is well-founded.

---

Summary

• Well-founded induction: if $(\forall y \prec x. P(y)) \Rightarrow P(x)$ for all $x$, then $\forall x. P(x)$
• Proof: minimal element of counterexample set leads to contradiction
• Specialises to strong induction on $\mathbb{N}$
• Lexicographic order preserves well-foundedness