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

Question

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

Answer 1

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.

Answer 2

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.