# Proving that the set of natural numbers is well-ordered

Consider the following theorem:

"Every non-empty set of positive integers has a minimum element".

The proof I usually see is one that uses contradiction, and does not seem like the easiest possible proof. I think there is an easier proof, and I wonder why I never see it. Does it contain an invalid assumption? The proof goes as follows:

First, prove by induction that the theorem is true for finite sets. Base case: It's true for a set of size 1, trivially. Induction step: Consider a finite set $S$ of size $n+1$. Let $s$ be a member of $S$. By I.H., $|S-s|$ has a minimum $s'$. If $s\lt s'$, then $s$ is the minimum of $S$. Otherwise, it is $s'$.

Second, let $T$ be a any non-empty set of positive integers ($T$ could be infinite). Let $t$ be an element of $T$. Consider the set $T\cap [0,t]$. The set is clearly finite, so it has a minimum element $min$. Next, we show that $min$ is also a minimum element of $T$. Let $x$ be an element of $T$. If $t\lt x$, then $min\leq x$. Otherwise $x\in T\cap [0,t]$, so $min\leq x$.

Is there a problem with this proof? I think when people prove that N is well-ordered, they do it in set theory books at a point where very little has been proven, so they can't assume much. Am I assuming too much in this proof? If not, why don't people ever use this very simple proof?

-
I don't see any need to treat finite and infnite sets separately. Since $S$ is non-empty, it contains some integer $n$. If $n=1$, we're done. Otherwise, either $n$ is the smallest element of $S$, in which case we're done, or $S$ contains a smaller element than $n$, in which case we're done by induction. – Gerry Myerson Jul 5 '11 at 6:56
@Gerry Myerson: It's not clear what your induction step there is, exactly (at least it's not clear to me); on the other hand, your argument would seem to convert into a relatively nice proof using the lack of infinite descent in the naturals (that is, that the naturals are well-founded )... – Steven Stadnicki Jul 5 '11 at 7:16
@Steven, I'm proving by induction on $n$ that if $S$ contains $n$ then it has a smallest element. – Gerry Myerson Jul 5 '11 at 7:28
@Gerry Myerson: Excellent observation. Now I wonder why the set theory books don't use your proof! – Ernest Jul 6 '11 at 0:26
¿Isn't Second part enought to prove that every finite or infinite subset of $\mathbb{N}$ has a least element? – Fonseca Jan 31 at 17:17

To expand a little on Levon's answer, in a serious set-theoretic introduction the positive integers are likely to be defined in a way that ensures that they're well-ordered, in which case it's automatic that every non-empty set of them has a least element. In that approach what you have to prove is that proof by induction is valid on well-ordered sets (and hence on the positive integers). If it's a rigorous course, you'll also prove that definitions by recursion are legitimate.

There are other ways to develop the theory of the positive integers, and some of them take some form of induction as axiomatic, making the well-ordering a derived property, but in my experience these approaches are less common, especially in set theory courses.

Informal courses are another matter altogether. In them the basic properties of the integers are generally taken as given, including well-ordering and as a pair. Typically the authors simply prove that the two are logically equivalent, so that it doesn't matter which one a given reader finds intuitively obvious. (I suspect that the authors are hoping that most readers will find at least one of the two properties intuitively obvious.) It's actually in these courses that I most often see a proof by contradiction, but it's the proof that well-ordering implies induction, not the reverse.

-

First of all let me state that I have seen inductive proofs of well-ordering of naturals in non set theory books.

The reason that you don't see such proof in set theory books, I think, is that induction and well-ordering are tightly connected to each other in set theory. You can do induction on a linearly ordered set if and only if it is well-ordered. So in a sense you should prove that naturals are well-ordered and then do induction on it.

-
This is only true if you mean something unusual by "induction". The usual form of induction (any subset containing the first element and closed under successor is the whole set) fails for wellorderings of length greater than $\omega$. – Chris Eagle Jul 6 '11 at 10:39
@Chris: In set theory the induction is usually formulated as follows: if $(\forall x < y P(x)) \to P(y)$ holds for all $y$, then $\forall y P(y)$ (of course everything relativised to some well-ordered set). This holds for all well-ordered sets. – Levon Haykazyan Jul 6 '11 at 12:54
@Levon: Or even relativized to some well-founded relation. @Chris: From a set theorist's point of view Peano induction is a very limited special case, not the usual notion. It's too limited even for many sophomore-level discrete math texts, which often need structural induction. – Brian M. Scott Jul 6 '11 at 18:05