Well Ordering Principle

The Well Ordering Principle states that every nonempty subset of the positive integers $\mathbb{Z}^{+}$ 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 $A$ of the real numbers is said to be inductive if it contains the number $1$, and if for every $x\in A$, the number $x+1\in A$ as well. Let $\mathcal{A}$ be the collection of all the inductive subsets of $\mathbb{R}$. Then the positive integers denoted $\mathbb{Z}^{+}$ are defined by the equation

$\mathbb{Z}^{+}=\bigcap_{A\in \mathcal{A}}A$.

Using this definition, we can rephrase the principle of mathematical induction as follows: if $A$ is an inductive set of the positive integers, then $A=\mathbb{Z}^{+}$. We can now proceed with the proof.


Proof: We first show that for any $n\in\mathbb{Z}^{+}$, every nonempty subset of $\{1,2,\ldots, n\}$ has a smallest element. Let $A$ be the set of all positive integers $n$ where this statement holds. We see $A$ contains $1$, since if $n=1$ then the only subset of $\{1,2,\ldots, n\}$ is $\{1\}$ itself. Then, supposing $A$ contains $n$ we show that it must contain $n+1$. Let $C$ be a nonempty subset of $\{1,2,\ldots, n+1\}$. If $C=\{n+1\}$ then $n+1$ is its smallest element. Otherwise, consider $C\cap \{1,2,\ldots,n\}$, which is nonempty. Because $n\in A$, this set has a smallest element, which will be the smallest element of $C$ also. This means that $A$ is inductive and $A=\mathbb{Z}^{+}$, so the statement is true for all $n\in\mathbb{Z}^{+}$. Now suppose $D\in \mathbb{Z}^{+}$ is nonempty. By choosing some $n\in D$, the set $A\cap\{1,2\ldots, n\}$ is also nonempty which means that $A$ has a smallest element $k$. This means that $k$ is the smallest element of $D$ too, which completes the proof $\square$

Invalid username
Login to AoPS