# Every nonempty subset of $\mathbb{N}$ has a smallest element.

Could someone please verify whether my proof is okay?

Every nonempty subset of $\mathbb{N}$ has a smallest element.

Let $S$ be a nonempty subset of $\mathbb{N}$.

Base case: If $1 \in S$, then the proof is done, since $1$ is the smallest natural number.

Inductive hypothesis: If $S$ contains an integer $k$ such that $1 \leq k \leq n$, then it must be that $S$ contains a smallest element.

Inductive step: It remains to be shown that if $S$ contains an integer $k \leq n + 1$, then $S$ has a smallest element.

If there is no such $k \leq n + 1$, then $n + 1$ is the smallest element. If there is such a $k$, since $S$ is nonempty, $S$ must contain an element $k - 1$ that is less than or equal to $n$. That element would then be less than or equal to $n + 1$. By induction, $S$ has a smallest element.

I am not sure whether assuming the element is $k-1$ is correct. The last paragraph is hard for me to understand if I don't assume this...

The last paragraph should be:

Suppose $S$ contains an element $1 \leq k \leq n+1$. If $S$ does not contain an element $1 \leq l \leq n$ then that element $k$ is $n+1$ and it is the smallest element of $S$ because $S$ contains it and nothing less than it.

If $S$ does contain an element $1 \leq l \leq n$ then it meets the criteria of the inductive hypothesis and therefore has a smallest element.

Either way, any set $S$ with an element $1 \leq k \leq n+1$ has a smallest element. This concludes the induction step.

• Thank you for taking the time to help me understand the last paragraph in a simple way. :) – numericalorange Apr 26 '18 at 23:56
• This description makes the use of the Law of the Excluded Middle a bit clearer. That every non-empty set of natural numbers has a least element is actually equivalent to the Law of the Excluded Middle (within an otherwise constructive context). – Derek Elkins Apr 27 '18 at 0:25

Let $S$ be a set of positive integers which contains an element $k\le n+1$

If the only element of $S$ is $k=n+1$, then $n+1$ is the smallest element.

Otherwise $k<n+1$ which implies $k\le n$ , thus by induction hypotheses $S$ has a minimum element.

• And if $k=n+1$ but $S$ is not a singleton set? – Derek Elkins Apr 26 '18 at 23:53
• If other elements are larger than k, then k is still a minimum. and if they are smaller than k, one of them is less than or equal n. – Mohammad Riazi-Kermani Apr 26 '18 at 23:57