Induction

Based on 21-127 Concepts of Mathematics

Let’s forget everything we know about $\mathbb{N}$. We can define it again using Peano’s axioms. It turns out that everything about $\mathbb{N}$ can be derived from Peano’s axioms.

Peano’s axioms basically says that:

• $\mathbb{N}$ is a set,
• Zero is in this set i.e. $0 \in \mathbb{N}$,
• There is some successor function $s: \mathbb{N} \to \mathbb{N}$ that satisfies:
  • $0 \notin s[\mathbb{N}]$ i.e. $0$ is never an output of $s$,
  • $s$ is injective
  • For all sets $X$, if ($0 \in X$ and for all $n \in \mathbb{N}$, $n \in X$ implies $s(n) \in X$), then $\mathbb{N} \in X$. (viz. if $X$ contains $0$ and all the natural numbers in $X$ “ensures” that the next natural number is in $X$, then $X$ contains $\mathbb{N}$).

(The successor function $s$ is essentially a function that adds one.)

We can then define the natural numbers we know by:

• $1 = s(0)$
• $2 = s(1)$
• $3 = s(2)$
• …

And we can prove things using the property of $s$. For example, $1 \neq 2$. Proof AFSOC assume $1 = 2$. Then $s(0) = s(1)$, so $0 = 1$ since $s$ injective. Then $0 = s(0)$. But 0 is not in the image of $s$. Contradiction $\square$.

(this is an informal statement) Any function $f: \mathbb{N} \to X$ can be completely defined by:

• Stating the value of $f(0) \in X$
• Specify the value of $f(s(n))$ in terms of $n$ and $f(n)$.
  Essentially, say what the function does to the first element, and say what the function does next to the next element based on what it did for the current element.

For example, we can define factorial, viz. $f: \mathbb{N} \to \mathbb{N}$ via $f(n) = n!$ ,by:

• $f(0) = 1$ viz. $0! =1$
• $f(n+1) = (n+1)f(n)$ viz. $(n+1)! = n!(n+1)$

This can also be used to define indexed sum and product recursively.

• Sum:
  • $\displaystyle \sum_{k=1}^0 a_k=0$
  • $\displaystyle \sum_{k=1}^{n+1} a_k=\left(\sum_{k=1}^n a_k\right)+a_{n+1}$
• Product:
  • $\displaystyle \prod_{k=1}^0 a_k=0$
  • $\displaystyle \prod_{k=1}^{n+1} a_k=\left(\prod_{k=1}^n a_k\right) \cdot a_{n+1}$

Say we have a logical formula $p(n)$ with $n \in \mathbb{N}$.

Theorem: if $p(0)$ true and $\forall n \in \mathbb{N}, (p(n) \Rightarrow p(n+1))$, then $\forall n \in \mathbb{N}, p(n)$ is true. (Proof is somewhere)

This is a proof strategy using the weak induction principle.

To prove $p(n)$ true for all $n \in \mathbb{N}$, we can:

• show $p(0)$ is true. This is called the base case.
• show $\forall n \in \mathbb{N}$ (our induction variable), $p(n)$ (induction hypothesis) implies $p(n+1)$ (induction goal). This whole whole thing is the induction step.

Or, if we have a base case that is not zero, say $n_{0}$, we can prove $\forall n\geq n_{0}, p(n)$ using a similar strategy:

• show $p(n_0)$ is true
• let $n \geq n_{0}$, show $p(n)$ implies $p(n+1)$.

Say we have a logical formula $p(n)$ with $n \in \mathbb{N}$.

Theorem:
$$[p(n_0) \wedge \forall n \geq n_{0}, ((\forall k \in [n_{0}, n], p(k)) \Rightarrow p(n+1))] \Rightarrow [\forall n\geq n_{0}, p(n)]$$
This can be proven by weak induction!

To prove $\forall n\geq n_{0}, p(n)$ we can do:

• show $p(n_0)$ is true (base case)
• let $n \geq n_{0}$, assume $p(k)$ for all $n_{0} \leq k \leq n$, derive $p(n+1)$ (induction step)

To prove $\forall n\geq n_{-r}, p(n)$ with some $r \in \mathbb{N}$ we can do:

• prove $p(n_{-r}) \wedge p(n_{-r+1}) \wedge \dots \wedge p(n_{-1}) \wedge p(n_0)$
• let $n \geq n_{0}$, assume $p(k)$ for all $n_{-r} \leq k \leq n$, derive $p(n+1)$

Theorem: every non-empty subset of $\mathbb{N}$ has a least element.

Sketch of the proof by induction

• (BC) Let $X \subseteq \mathbb{N}$. Assume $0 \in X$ then 0 is the least element
• (IS) Let $n \geq 0$. Assume for all $0 \leq k \leq n$, every subset of $\mathbb{N}$ with $k$ as an element has a least element.
  • Let $X \subseteq \mathbb{N}$. Assume $n+1 \in X$. Case on $n+1$ being least or not least. Case 1 is trivial, case 2 means some element $k$ is less than $n+1$ $X$ therefore has least element by IH.