How to prove that $\mathbb{N}$, the set of natural numbers, is well ordered? I am reading classic set theory by D.C. Goldrei. I am stuck on understanding an argument for proving $\mathbb{N}$ is well ordered (every non-empty subset is of a least element). The author assumed that $B$ is a nonempty subset with no least element. Then the following subset of $\mathbb{N}$ is constructed:
\begin{equation}
A = \left\{\boldsymbol{n} \in \mathbb{N}: \boldsymbol{m} \not\in B\ \textrm{for all}\ \boldsymbol{m} \leq \boldsymbol{n}\right\},
\end{equation}
and the author proved that $A = \mathbb{N}$, so that $B$ is empty, which leads to a contradiction. I am not quite sure about how this argument leads to the fact that $B$ is empty, and what is the relation between the assumption that $B$ is nonempty with no least element and the construction of set $A$. I have no idea why $A$ has to be constructed as such. Could anyone provide hints?
 A: Assume $k \in B$.  Then $k+1 \notin A$ because there is a natural number ($k$) that is less than $k+1$ that is also in $B$.  If $A= \Bbb N$, then $k+1 \notin A$ can't happen, so your initial assumption that $k \in B$ must be false.  But $k$ was an arbitrary natural number, so that means no natural numbers can be elements of $B$; i.e., $B$ is empty.
A: Okay.
Let's do a sort of but not quite proof by contradiction.
The  well-ordered principal says:  Every non-empty subset of $\mathbb N$ has a least element.
Let's assume $B\subset \mathbb N$ without a least element.
If we can prove that $B$ can't be non-empty we are done.  Because if we can prove for $B$ to not have a least element we must have $B=\emptyset$ than that means for any subset that isn't empty, it can't be possible that it doesn't have a least element (because if it doesn't have a least element we have proven it must be empty.).
Okay, let's prove $B$ must be empty.
If we can prove that for any $k \in \mathbb N$ that $k \not \in B$ we will be done.  $B\subset \mathbb N$ but none of the $k \in \mathbb N$ can actually be in $B$ than nothing can be in $B$.  So $B$ would have to be empty.
So let's do that.  Let's prove that if $k \in \mathbb N$, then $k\not \in \mathbb N$.
So your text considers the set $A = \{n\in \mathbb N| $ if $m \le n$ then $m\not \in B\}$.
We can prove $1\in A$.  If $m\le 1$ then $m = 1$.  ANd if $m \in B$ then $m$ is the least element in $B$. But $B$ doesn't have a least element. So $1\not \in B$. so all $m\le 1$ are not in $B$.  So $1 \in A$.
Suppose we have a $k$ so that if $n \le k$ then $n\in A$.  We can prove $k+1\in A$.
If $m \le k+1$ then either $m \le k$ or $m = k+1$.  If $m\le k$ then $k \in A$ by our assumption.  If $m=k+1$ the either $k+1 \in B$ or $k+1\not \in B$.  Because $k\in A$ then all $n< k+1$ then $n \le k$ so $n\not \in B$.  So if $k+1 \in B$ then $k+1$ is the least element of $B$.  But $B$ has no least element. So $k+1 \not \in B$.  So for all $n \le k+1$ we have $n \not \in B$.  So $k+1 \in A$.
Now the natural numbers have the induction principal.  So if $1 \in A$ and if $k\in A \implies k+1 \in A$ we can conclude all $n \in \mathbb N$.
So for all $n \in \mathbb N$ we have $n \in A$.
But that means $B$ is empty.  Why?  Because if $m \in \mathbb N$ then $m \in A$.  And if $m \in A$ then all $n\le m$ are not in $B$.  And $m \le m$ so $m \not \in B$.  So no $m\in \mathbb N$ are in $B$.
So $B$ is empty.
And we have proven everything we needed to prove.
We have proven that if $B$ is any subset of $\mathbb N$ without a least element then $B$ must be empty.  That means for any non-empty set, the set can't not have a least element.  So every non-empty set of natural numbers has a least element.
Note, this will hold for any set that has the induction principal.  Note $\mathbb Z, \mathbb Q, \mathbb R$ etc. don't have the induction principal so $\mathbb Z, \mathbb Q, \mathbb R$ need not be well-ordered.
=====
Actually if it were me I wouldn't bother with the set $A$.
I'd just show

*

*$1 \not \in B$.  (Because otherwise $1$ is the minimal element in $B$)


*If $n \le k$ not in $b$ then $k+1$ is not it $B$ (else $k+1$ would be the least element.)
So by induction there are no $n \in \mathbb N$ that are in $B$.  So $B$ is empty.
