Exercise 0.2.6(Well Ordering of $\mathbb{Z}^+$)

Proof. Let $A$ be any nonempty subset of ${\mathbb{Z}}^{+}$. Assume for the sake of contradiction that there is no element $m$ in $A$ such that $m\le a$, for all $a\in A$ (i.e., $A$ has no minimal element).

Let $𝒫(n)$ the proposition defined for every $n\in {\mathbb{Z}}^{+}$ by

(that is, $A$ contains no element $k\le n$).

• If $1\in A$, where $A\subseteq {\mathbb{Z}}^{+}$, then $1\le a$ for all $a\in A$. This is impossible, since $A$ has no minimal element. Therefore $1\notin A$, so $𝒫(1)$ is true.
• Suppose that $𝒫(n)$ is true, so that $k\notin A$ for every $k\le n$. If $n+1\in A$, then for every $a\in A$, $a\le n$ is false, thus $n<a$, or equivalently $n+1\le a$, so $n+1$ would be a minimal element of $A$. This contradicts our hypothesis, so $n+1\notin A$. This shows that $𝒫(n+1)$ is true.
• The induction is done, which proves that for all $n\in {\mathbb{Z}}^{+}$, $n\notin A$.

Since $A\subseteq {\mathbb{Z}}^{+}$, $A=\varnothing$. This contradicts the hypothesis $A\ne \varnothing$. This contradiction shows that $A$ has a minimal element, so the Well Ordering of ${\mathbb{Z}}^{+}$ is proven.

Moreover, if $a$ and $b$ are both minimal elements of $A$, then $a\in A$ and $b\in A$, so $a\le b$ and $b\le a$, thus $a=b$. The minimal element is unique. □