The Well Ordering Principle

Every nonempty set of nonnegative integers has a smallest element.

To prove that “$P(n)$ is true for all $n\in N$” using the Well Ordering Principle:

• Define the set $C$ of counterexamples to $P$ being true. Specifically, define $C::=\{n\in \mathbb{N}\mid \neg (P(n))\text{ is true}\}$
• Assume for proof by contradiction that C is nonempty.
• By the Well Ordering Principle, there will be a smallest element, n, in C.
• Reach a contradiction somehow—often by showing that $P(n)$ is actually true or by showing that there is another member of C that is smaller than $n$. This is the open-ended part of the proof task.
• Conclude that C must be empty, that is, no counterexamples exist.

Use Cases

• Proving that $1+2+\cdots +n=n(n+1)/2$ → see https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf
• This is useful in CS to show that a state machine will eventually terminate.