# Is this a valid way of proving the well ordering principle?

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?

• Yep, that's exactly how the standard proof goes. – Tim Raczkowski Feb 25 '15 at 3:37
• Didn't know that, my professor proved it in another way. Thanks. – Miguelgondu Feb 25 '15 at 3:38
• Perhaps, I shouldn't use the word standard. It's the argument I'm familiar with. – Tim Raczkowski Feb 25 '15 at 3:40
• Yes, that's a nice proof. Note that the introduction of $R = \mathbb{N}-S$ is not necessary. You can simply prove $\forall n \in \mathbb{N}, n \not\in S$ by strong induction. That is, the same work you do here, but use $n \not\in S$ everywhere in place of $n \in R$. – aes Feb 25 '15 at 4:22

## 1 Answer

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.