Induction

Almost every courses teach induction

Basic Induction: To prove $\forall n\in \mathbb{N},(P(n))$ use some base case and induction to prove for all.

• $(P(0)\wedge \forall k\in \mathbb{N}.(P(k)⟹P(k+1)))⟹\forall n\in \mathbb{N},(P(n))$
• we have some flexibility on basic case where if we have goal to prove $\forall n\ge 1$ then we will prove $P(1)$

Basic Induction prove template:

Prove by induction.
Base case: [Prove P(0) is true]
Inductive step: Let k be arbitrary natural number, and assume P(k). we will show P(k+1)

Complete Induction: To prove $\forall n\in \mathbb{N},(P(n))$ use some base case and more induction steps to prove for all.

• $(P(0)\wedge \forall k\in \mathbb{N}.(P(0)\wedge P(1)\wedge \dots \wedge P(k)⟹P(k+1)))⟹\forall n\in \mathbb{N},(P(n))$
• similarly, we have flexibility on basic case.

Complete Induction prove template:

Prove by induction.
Base case: [Prove P(0) is true]
Inductive step: Let k be arbitrary natural number, and assume for every natural number i less equal than k, P(i) . we will show P(k+1)

A set generated from $B$ (basic set) by the functions in $F$ (a set of functions $:U^m\to U$ where $U$ stand for universe set of $B$) is the set of elements that can be obtained by applying $f\in F$ to $b\in B$ a finite number of times.

Structural Induction: Let $C$ be a set generated from $B$ by $f\in F$. $(\forall b\in B,P(b))\wedge (\forall f\in F$ on $m$ inputs $\forall a_1,\dots ,a_m\in C,(P(a_1)\wedge P(a_2)\wedge \dots \wedge P(a_m))⟹P(f(a_1,\dots ,a_m)))⟹\forall x\in C.(P(x))$

Define a construction sequence $S$ of length $n$ as $(x_0,\dots ,x_n)$ where $\forall x_i\in S,x_i\in B\vee x_i=f(x_{j_1},\dots ,x_{j_m}),f\in F,j_1,\dots ,j_m<i$.

The length of a construction sequence is represented by some measure of complexity of the object.

WOP

WOP(Well Ordering Principle): $\forall S\subseteq \mathbb{N}(S\ne \varnothing ),S$ has a minimal element.

• let $a\in S,\forall b\in S,a\le b⟹a$ is a minimal element

We can use WOP to prove induction statements of the form $\forall n\in \mathbb{N},(P(n))$:

1. Check $P(b)$ is true, $b$ stand the basic case
2. By contradiction, assume $\exists n\in \mathbb{N}.(\neg P(n))$. So the set $S=\{n\in \mathbb{N}:\neg P(n)\}$ is non-empty
3. By the WOP, $S$ has a minimal element, denote as $m$; commonly, $m$ is the smallest natural number for which $P$ doesn’t hold.
4. Derive the contradiction by showing $P(m)$ or by finding a $m^{\prime }<m$, for which $\neg P(m^{\prime })$