7
$\begingroup$

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?

  • 0
    ¿Isn't Second part enought to prove that every finite or infinite subset of $\mathbb{N}$ has a least element?2016-01-31

2 Answers 2

5

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 induction. 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.

0

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.

  • 0
    @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.2011-07-06