Induction (Simple & Structural)

Induction is the workhorse proof technique for $\forall n \in \mathbb{N}. P(n)$.

Simple induction:
1. Base case: prove $P(0)$.
2. Inductive step: prove $\forall n. P(n) \Rightarrow P(s(n))$.

Strong (complete) induction: instead of assuming $P(n)$, assume $P(k)$ for
all $k < n$ (or $k \leq n$).

Structural induction: for inductively defined sets (lists, trees), induct
on the structure:
1. Base: prove $P$ for the constructors (e.g. empty list).
2. Step: assuming $P$ for the components, prove $P$ for the constructed value.

All three are reducible to P5 (Peano's induction axiom).

For all unary naturals $a, b, c$, $(a \oplus b) \oplus c = a \oplus (b \oplus c)$.

Proof sketch. By induction on $c$. Base $c = o$: $(a \oplus b) \oplus o = a \oplus b$ (by first eq.) $= a \oplus (b \oplus o)$ (same eq.). Step: assume $(a \oplus b) \oplus c = a \oplus (b \oplus c)$. Then $(a \oplus b) \oplus s(c) = s((a \oplus b) \oplus c) = s(a \oplus (b \oplus c)) = a \oplus s(b \oplus c) = a \oplus (b \oplus s(c))$. $\square$

Definition 3.5 (Summation). $\sum_{i=m}^{n} f(i) := \begin{cases} 0 & n < m \\ f(m) + \sum_{i=m+1}^{n} f(i) & \text{otherwise} \end{cases}$

Definition 3.6 (Product). $\prod_{i=m}^{n} f(i) := \begin{cases} 1 & n < m \\ f(m) \cdot \prod_{i=m+1}^{n} f(i) & \text{otherwise} \end{cases}$

These are 'higher-order' operations: they take a function $f$ and a range, and reduce. Note the empty cases: an empty sum is 0 (the additive identity) and an empty product is 1 (the multiplicative identity). This is essential for induction.

Some theorems require induction over two variables. The technique:

Theorem. $\forall a, b \in \mathbb{N}.\, a + b = b + a$ (addition is commutative).

Proof by nested induction. We prove it by induction on $a$, then within each step, by induction on $b$.

Outer induction on $a$:
- Base $a = o$: We need $\forall b.\, o + b = b + o$. Inner induction on $b$:
- Base $b = o$: $o + o = o$ (first axiom) $= o + o$ (trivially). ✓
- Step $b = s(b')$: $o + s(b') = s(o + b') = s(b')$ (second axiom). And $s(b') + o = s(b' + o) = s(b')$ (first axiom on the right). ✓
- Step $a = s(a')$: Assume $\forall b.\, a' + b = b + a'$ (outer IH). We need $\forall b.\, s(a') + b = b + s(a')$. Inner induction on $b$:
- Base $b = o$: $s(a') + o = s(a')$ (first axiom). And $o + s(a') = s(o + a') = s(a' + o)$ (second axiom) $= s(a')$ (outer IH with $b = o$). ✓
- Step $b = s(b')$: $s(a') + s(b') = s(s(a') + b') = s(s(b' + a'))$ (outer IH) $= s(s(b') + a')$ (outer IH again) $= s(b') + s(a')$ (second axiom). ✓

So $a + b = b + a$ for all $a, b$. $\square$

Reading. Note that the inner induction re-uses the outer IH each time. The two levels of induction can swap roles (do inner on outer and vice versa) depending on the theorem.