Induction

## Equivalence of WOP and Induction

Here is how an inductive proof can be stated using WOP:

The inductive proof follows this format:

• One shows the base case is true, e.g. $P(1)$ is true (this step depends on the problem).
• Next one shows that for any $n$, we have $P(n) \implies P(n+1)$ (this step also depends on the specific problem).
• Now by induction we conclude that for all $n$, $P(n)$ is true.

The same proof can be stated using WOP. Here is how:

• Let the set $S$ be the set of all numbers $n$ such that $P(n)$ is false.
• If $S$ is empty we have already proved our claim. Otherwise by WOP this set has a smallest element. Let's call it $k$.
• If $k=1$, one can show that $P(k)$ which is $P(1)$ is true (the same way we prove our induction base case). But this is a contradiction, since we assumed that $k\in S$ which means that $P(k)$ is false.
• If $k>1$, then $k-1$ is a smaller natural number. But since $k$ was the smallest number in $S$, $k-1$ cannot be in $S$, which means that $P(k-1)$ is true. Now we again provide the proof of the inductive step, from which we conclude that $P(k-1) \implies P(k)$. But since $P(k-1)$ is true, this means that $P(k)$ is true. But this is again a contradiction, since we assumed $P(k)$ is false.
• Since we get a contradiction either way, our assumption that $S$ was not empty must be false.