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?

  • 5
    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.2011-07-05
  • 0
    @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_ )...2011-07-05
  • 1
    @Steven, I'm proving by induction on $n$ that if $S$ contains $n$ then it has a smallest element.2011-07-05
  • 0
    @Gerry Myerson: Excellent observation. Now I wonder why the set theory books don't use your proof!2011-07-06
  • 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