Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
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
1  
@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
add comment

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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