Mathematical Induction

$$\left(P(1)\wedge \forall \left(P(k)\to P(k+1)\right)\right)\to \forall nP(n)$$

Strong Induction

$$\left(P(1)\wedge \forall \left(P(1)\wedge P(2)\wedge \cdots \wedge P(k)\to P(k+1)\right)\right)\to \forall nP(n)$$

The Well-Ordering Property

Every non-empty set of non-negative integers has a least element

This principle underpin the principle of mathematical induction

Structural Induction

• Base Case: Prove that the property holds for all base case elements of the recursive definition
• Induction Step: Prove that if the property holds for the immediate substructures of a certain structure S, then it must also hold for S itself

Extended Induction

Extend mathematical induction from $\mathbb{N}$ to any Partially Ordered Set with the well-ordering property.