# How can I prove that a set of natural numbers always have a minimum?

Let's say I have a finite not-empty set named A, which is a set of natural numbers. How do I prove it has a minimum? (In Calculus)

• how can natural numbers form a group? Do you mean a set? – Lost1 Aug 17 '13 at 15:24
• Are you sure this question is related to Calculus? Are you wondering about the minimum of a function that takes only integer values? If that's the case, such a function is not going to have a derivative and allow itself the usual minimization/maximization techniques. – Patrick Aug 17 '13 at 15:24
• en.wikipedia.org/wiki/Well-ordering_principle – Alex Wertheim Aug 17 '13 at 15:25

## 3 Answers

Suppose not. Then, for every $x\in A$ you can find a smaller $y\in A$. Now consider the set of all numbers that are strictly less than every number in $A$. Clearly, $0$ is there (it is $\le y<x$ and if $t$ is there, then $S(t)$ is there ($t<y$ implies $S(t)<S(y)\le x$). Thus, all $\mathbb N$ is there which is absurd. Note that the last step is nothing but the minimalistic version of the "induction" axiom and that I assumed that the ordering is already defined and all relevant fact I used are proven. The axiomatic games are never fun...

You are trying to prove that the natural numbers are well-ordered. Calculus isn't going to help you here.

Instead, try using induction. There is an obvious proof by induction on the cardinality of the set, for finite sets. Proving that even infinite sets have a least element requires being a little more clever: let $P(n)$ be "all sets containing $n$ as an element have a least element," then prove $P(n)$ holds for all $n$ using (strong) induction.

• The problem is I can't use Induction. – HaloKiller Aug 17 '13 at 16:21
• @Yonatan Why not? Please edit your question with more details of the problem (including its exact wording). – user7530 Aug 17 '13 at 16:45

You can't. Unless you add the condition that $A\ne \emptyset$.

Assume $A\subseteq \mathbb N$ has no monimal element. Then prove by induction that $$\{1,\ldots,n\}\cap A=\emptyset$$ holds for all $n\in \mathbb N$. The induction stecp $n\to n+1$ goes as follows: $\{1,\ldots,n\}\cap A$. If $n+1\in A$, this would imply that $n+1$ is a minimal element of $A$, contrary to the assumption. Therefore $n+1\notin A$ and hence $\{1,\ldots,n+1\}\cap A=\emptyset$.

Then note that $\{1,\ldots,n\}\cap A$ for all $n$ implies $A=\emptyset$ (as $n\in A$ implies $n\in \{1,\ldots,n\}\cap A$).

• What about $A = \{0\}$ ? – Pece Aug 17 '13 at 15:30
• The problem is I can't use Induction. – HaloKiller Aug 17 '13 at 16:22