Well Ordering Principle

The Well Ordering Principle (WOP) is a fundamental axiom of integers. It provides a powerful alternative to Induction, often producing cleaner proofs for existence problems.

---

Definition

Every nonempty set of nonnegative integers has a smallest element.

$S\subseteq \mathbb{N},S\ne \varnothing ⟹\exists m\in S\text{ such that }\forall x\in S,m\le x$

• Nonempty is key: The empty set has no smallest element.
• Integers is key: The set of positive real numbers $(0,1)$ has no smallest element (you can always divide by 2).
• Bounded below: It applies to sets of negative integers only if they have a lower bound (e.g., $\{-5,-4,\dots \}$).

---

Proof Template: The WOP Contradiction

To prove “Property $P(n)$ is true for all $n\in \mathbb{N}$”:

1. Define the Set of Counterexamples: Let $C$ be the set of numbers where $P(n)$ is false. $C=\{n\in \mathbb{N}\mid P(n)\text{ is false}\}$
2. Assume for Contradiction: Assume $C$ is nonempty (i.e., the theorem is false).
3. Apply WOP: Since $C$ is a nonempty set of natural numbers, it must have a smallest element, let’s call it $m$.
   • $m$ is the “minimal counterexample.”
4. Find a Contradiction:
   • Show that $P(m)$ is actually true (contradicting $m\in C$).
   • OR: Find a smaller counterexample $c<m$ (contradicting that $m$ is the smallest).
5. Conclusion: The assumption that $C$ is nonempty must be false. Therefore, $C$ is empty, and $P(n)$ holds for all $n$.

---

Example: The Division Algorithm

Theorem: Given integer $n$ and divisor $d>0$, there exist unique integers $q,r$ such that $n=dq+r$ and $0\le r<d$.

• Proof (Existence): Consider the set of remainders $R=\{n-dq\mid q\in \mathbb{Z}\text{ and }n-dq\ge 0\}$. By WOP, $R$ has a smallest element $r_{min}$. If $r_{min}\ge d$, we could subtract $d$ one more time to get a smaller non-negative remainder, contradicting the minimality of $r_{min}$. Thus, $0\le r_{min}<d$.

---