The well ordering principle states that every non-empty subset of $\mathbb{N}$ must have a first element (i.e. a minimum).
For my proof, I suppose there exists a set $\varnothing \neq S \subseteq \mathbb{N}$ that doesn't have a minimum. I, then, consider the set $R = \mathbb{N} - S = \{x\in \mathbb{N} \; \vert \; x\notin S\}$. The proof follows with proving $R = \mathbb{N}$ via induction:
- $0\in R$, because, otherwise, $S$ would have a minimum (because $0\leq n \; \forall n \in \mathbb{N}$).
- I suppose that every $k<n$ is in $R$ (i.e. every $k<n$ isn't in $S$). If $n$ was to be in $S$, $S$ would have a minimal element. Therefore, $n \in R$.
This proves that $R= \mathbb{N}$, it follows that $S = \varnothing$. Absurd.
Is this a valid proof?
I've always found that proof slightly indirect, not sure why. An essentially equivalent proof, that nonetheless seems a bit more intuitive to me, is:
Consider the formula $\varphi(n)$="Any set $X \subseteq\mathbb{N}$ which contains $n$, has a least element."
By induction, we have $\forall n\varphi(n)$: the initial case $n=0$ is obvious, and for the inductive case, either $X$ contains some $m<n+1$ (in which case by the inductive hypothesis we're done), or it doesn't (in which case $n+1$ is the minimal element).
So we're done.