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?

  • 1
    $\begingroup$ Yep, that's exactly how the standard proof goes. $\endgroup$ – Tim Raczkowski Feb 25 '15 at 3:37
  • $\begingroup$ Didn't know that, my professor proved it in another way. Thanks. $\endgroup$ – Miguelgondu Feb 25 '15 at 3:38
  • $\begingroup$ Perhaps, I shouldn't use the word standard. It's the argument I'm familiar with. $\endgroup$ – Tim Raczkowski Feb 25 '15 at 3:40
  • $\begingroup$ 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$. $\endgroup$ – aes Feb 25 '15 at 4:22

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.