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