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 the theorem 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.

Page

Toolbox

Search

Well Ordering Principle