> [!NOTE] Proposition (Induction Principle) > Suppose that $(P(n))_{n\geq n_{0}}$ is a sequences of properties, one for each natural number, such that > 1. $P(n_{0})$ is true and > 2. for all $k\geq n_{0},$ if $P(k)$ is true then $P(k+1)$ is true. > >then $P(n)$ is true for all $n\geq n_{0}.$ # Proofs Taken as one of Peano's axiom. IP <-> IPS WO: [[Well-Ordering Principle|IP -> WO]]. WO -> IP? # Applications See [[Strong Form of Induction Principle]]. **Recursive functions**: The [[Recursive Function|recursion theorem]] guarantees that recursively defined functions exist. Prime factorisation: [[Fundamental theorem of arithmetic]].