well-ordering principle

Due to the fact that mathematicians still can't decide whether zero is a natural number, some sources will exclude zero from the definition. Regardless, the principle satisfies natural numbers with or without zero.

Let some set \[S\] be a non-empty subset of natural numbers, i.e. \[S\subseteq \mathbb{N}\] and \[S\ne\emptyset\]. Since natural numbers itself is a subset of real numbers, \[S\subseteq \mathbb{R}\]. Additionally, for all \[n\in \mathbb{N}\], by definition of natural numbers \[n\ge0\], consequently, for all \[n\in S\], \[n\ge 0\]. Thus, 0 is a lower bound of \[S\].

By the corollary of the completeness axiom, \[S\] has an infimum as it has a lower bound. Hence, let \[b=\inf S\]. By definition, since \[b\] is the greatest lower bound for \[S\], it follows that \[b+1\] can't be a lower bound of \[S\]. So, for some \[n\in S\], \[n<b+1\]. We'll use proof by contradiction to show that \[n\] is the smallest element of \[S\].

Assume \[n\] is not the smallest element of \[S\], then there must exist some \[m\in S\] such that \[b\le m<n<b+1\]. It is obvious that there exist no combination of natural numbers that satisfies the inequality. Mathematically, by rearranging the inequality, \[m<n\implies0<n-m\] (centre inequality); \[b+1\le m+1\implies n<b+1\le m+1\] (left inequality), which follows that \[n<m+1\implies n-m<1\]. We find that \[0<n-m<1\]. However, there exist no natural number between zero and 1, therefore, \[n=b\] must be the smallest element of \[S\].

To make sense of this proof, write down a simple set of natural numbers, e.g. \[S=\left\{ 2,2,3,4 \right\}\], then substitute the numbers while following the proof above.

The following is a proof by contradiction.

Let \[S\] be a non-empty subset of \[\mathbb{N}\] with no least element. Note that \[0\notin S\] since 0 is the smallest number, and choosing 0 as the smallest number is just purely convention. Though, the following proof still works regardless of choosing 0 or 1 as the smallest number (for those arguing that 0 is not a natural number).

Let \[J\] be the set of all natural numbers that are not in \[S\]. Since 0 is the lower bound of \[\mathbb{N}\] (as it is the smallest natural number) and \[S\] can not have a least element, \[0\notin S\implies 0\in J\]. We will now prove by induction \[0,1,2,\dots,n\in J\] implies that \[n+1\in J\]. Suppose \[0,1,2,\dots,n\in J\]. Then, \[n+1\] can not be in \[S\], as \[n+1\] would be the lowest bound of \[S\] because \[0,1,2,\dots,n\notin S\], which would make \[n+1\] the least element of \[S\]. Thus, since our premise is that \[S\] can not have a least element, \[n+1\in J\].

By induction, we conclude that \[J=\mathbb{N}\], which implies that \[S\] must be an empty set, which contradictions our initial assumption. Therefore, \[S\] must have a least element.