# The Well Ordering Principle

Every nonempty set of nonnegative integers has a smallest element.

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

- Define the set $C$ of counterexamples to $P$ being true. Specifically, define $C::={n∈N∣¬(P(n))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+⋯+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.