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 > 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 > a_1$ and $a_n > a_{n+1}$.
Proposition: $$s - a_n \ge n$$
Proof with mathematical induction:
The base case holds since $s > a_1 \implies s-a_1 \ge 1$.
Also: $a_n > 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 < 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
 A: The sequence you introduce is not necessary and, moreover, building it requires recursion.
Suppose $A$ has no least element. Consider the set
$$
A^*=\{n\in\mathbb{N}:n<a,\text{for all $a\in A$}\}
$$
Note that $A\cap A^*=\emptyset$, because if $a\in A\cap A^*$ we would have $a<a$, a contradiction.
We prove by induction that $n\in A^*$, for all $n\in\mathbb{N}$.


*

*$0\in A^*$; indeed, if $0\notin A^*$, there exists $a\in A$ with $a\le0$; thus $0\in A$ and $A$ has a least element.

*Suppose $n\in A^*$. If $n+1\notin A^*$, there exists $a\in A$ with $a\le n+1$. Since $n\in A^*$ we have $n<a$ and therefore $a=n+1$. Then $a=n+1$ is the least element of $A$.
Therefore $A^*=\mathbb{N}$ and so $A$ is empty.
If your natural numbers start at $1$, the proof is exactly the same.
The proof relies on the fact that “$n<a\le n+1$ implies $a=n+1$”, that in turn is the same as “$0<a\le 1$ implies $a=1$. Indeed, since $a\ne0$, we have $a=b+1$, for some $b$; thus $b+1\le 1$ and therefore $b\le0$, which implies $b=0$ and so $a=1$.
A: 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$.
A: 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 < y < \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 < 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.
