Every nonempty subset of the natural numbers has a least number Proposition: Every nonempty subset $A$ of $\mathbb{N}$ has a least element.


We assume the opposite: $$\exists \left( A \subseteq \mathbb{N} \wedge A \neq \varnothing \right): \forall s \in A: \exists a \in A: s &gt; a$$

Be $A \subseteq \mathbb{N}$ and $A \neq \varnothing$.
Be $s \in A$ and $a_n \in A$ for every $n \in \mathbb{N}_{\ge 1}$ and be $s &gt; a_1$ and $a_n &gt; a_{n+1}$.

Proposition: $$s - a_n \ge n$$

Proof with mathematical induction:

The base case holds since $s &gt; a_1 \implies s-a_1 \ge 1$.

Also: $a_n &gt; a_{n+1} \implies a_n - a_{n+1} \ge 1$ and with this $s - a_n \ge n$ implies $s - a_{n+1} \ge n+1 \quad \square$

Since $s - a_n \ge n$ and $a_n \ge 0$ holds we get: $$s \ge n \quad \forall n \in \mathbb{N}_{\ge 1}$$
But it is $s &lt; s+1 \in \mathbb{N}_{\ge 1} \text{ Contradiction!} \quad \square$


  First question: Is this proof valid?
  
  Second question: Do you know different proofs for this proposition?


Cheers
One standard argument is as follows:

Suppose $A\subseteq\Bbb N$ has no least element. If $0\in A$ then $A$ would have a least element.  So $0\notin A$.  Now suppose $0\notin A,1\notin A,\ldots, n-1\notin A$.  If $n\in A$ under these assumptions, then $A$ would have a least element.  So, by induction, $n\notin A$ for every $n\in\Bbb N$.  Therefore $A=\emptyset$.
Well, it might not be kosher to bring a baseball bat to a cricket game but:

$\mathbb N \subset \mathbb R$ and the reals have the least upper bound property.  A is bounded below by 0. so $x =\inf A$ exists.

It's easy to show x is an integer.  (Else there exists a $y$ such that $x &lt; y &lt; \lceil x\rceil$ so y is also a lower bound so $x$ is not inf.) And it's easy to show $x \in A$.  (Else $x + 1/10$ is also a lower bound and x is not inf.)

So $x = \inf A$ and $x \in A$ imply $x$ is the least element in A.

====

A bit more cricket:

Assume non-empty A has no minimum element.

We can do a downward induction to prove the following statement:  For any integer m, there is an element of A that is less than m.

Sub-base case:  Let a be in A.  then for all m > a the statement is true because a &lt; m.

Base case: as A does not have a minimum element, a is not the minimum element.  So there is an element of A that is less than a.

Induction step: Assume the statement is true for m.  The element of A less than m must be less than or equal to m - 1.  If it isn't equal to m, than the there is an element of A less than m -1.  If it is equal to m, then m is an element of A but it isn't the minimum element as there is no minimum element.  So there is an element of A less than m - 1.

Hence this statement is true for all integers.

But it's not true for 0 or any negative integer.

So our assumption was wrong, and non-empty A has a minimum element.