Well Ordering Principle
The Well Ordering Principle states that every nonempty subset of the positive integers contains a smallest element. While this theorem is mostly brushed off as common sense, there is a bit of formalism required to actually prove it sufficiently. We will do this here.
Definition: A subset of the real numbers is said to be inductive if it contains the number
, and if for every
, the number
as well. Let
be the collection of all the inductive subsets of
. Then the positive integers denoted
are defined by the equation

Using this definition, we can rephrase the principle of mathematical induction as follows: if is an inductive set of the positive integers, then
. We can now proceed with the proof.
Proof: We first show that for any , every nonempty subset of
has a smallest element. Let
be the set of all positive integers
where this statement holds. We see
contains
, since if
then the only subset of
is
itself. Then, supposing
contains
we show that it must contain
. Let
be a nonempty subset of
. If
then
is its smallest element. Otherwise, consider
, which is nonempty. Because
, this set has a smallest element, which will be the smallest element of
also. This means that
is inductive and
, so the statement is true for all
.
Now suppose
is nonempty. By choosing some
, the set
is also nonempty which means that
has a smallest element
. This means that
is the smallest element of
too, which completes the proof