Well-ordering principle

Not to be confused with Well-ordering theorem.

In mathematics, the well-ordering principle states that every non-empty subset of positive integers contains a least element. ^[1] In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which ${\displaystyle x}$ precedes ${\displaystyle y}$ if and only if ${\displaystyle y}$ is either ${\displaystyle x}$ or the sum of ${\displaystyle x}$ and some positive integer (other orderings include the ordering ${\displaystyle 2,4,6,...}$; and ${\displaystyle 1,3,5,...}$).

The phrase "well-ordering principle" is sometimes taken to be synonymous with the "well-ordering theorem". On other occasions it is understood to be the proposition that the set of integers ${\displaystyle \{\ldots ,-2,-1,0,1,2,3,\ldots \}}$ contains a well-ordered subset, called the natural numbers, in which every nonempty subset contains a least element.

Properties

Depending on the framework in which the natural numbers are introduced, this (second-order) property of the set of natural numbers is either an axiom or a provable theorem. For example:

• In Peano arithmetic, second-order arithmetic and related systems, and indeed in most (not necessarily formal) mathematical treatments of the well-ordering principle, the principle is derived from the principle of mathematical induction, which is itself taken as basic.
• Considering the natural numbers as a subset of the real numbers, and assuming that we know already that the real numbers are complete (again, either as an axiom or a theorem about the real number system), i.e., every bounded (from below) set has an infimum, then also every set ${\displaystyle A}$ of natural numbers has an infimum, say ${\displaystyle a^{*}}$. We can now find an integer ${\displaystyle n^{*}}$ such that ${\displaystyle a^{*}}$ lies in the half-open interval ${\displaystyle (n^{*}-1,n^{*}]}$, and can then show that we must have ${\displaystyle a^{*}=n^{*}}$, and ${\displaystyle n^{*}}$ in ${\displaystyle A}$.
• In axiomatic set theory, the natural numbers are defined as the smallest inductive set (i.e., set containing 0 and closed under the successor operation). One can (even without invoking the regularity axiom) show that the set of all natural numbers ${\displaystyle n}$ such that "${\displaystyle \{0,\ldots ,n\}}$ is well-ordered" is inductive, and must therefore contain all natural numbers; from this property one can conclude that the set of all natural numbers is also well-ordered.

In the second sense, this phrase is used when that proposition is relied on for the purpose of justifying proofs that take the following form: to prove that every natural number belongs to a specified set ${\displaystyle S}$, assume the contrary, which implies that the set of counterexamples is non-empty and thus contains a smallest counterexample. Then show that for any counterexample there is a still smaller counterexample, producing a contradiction. This mode of argument is the contrapositive of proof by complete induction. It is known light-heartedly as the "minimal criminal" method^{[ citation needed ]} and is similar in its nature to Fermat's method of "infinite descent".

Garrett Birkhoff and Saunders Mac Lane wrote in A Survey of Modern Algebra that this property, like the least upper bound axiom for real numbers, is non-algebraic; i.e., it cannot be deduced from the algebraic properties of the integers (which form an ordered integral domain).

Example applications

The well-ordering principle can be used in the following proofs.

Prime factorization

Theorem: Every integer greater than one can be factored as a product of primes. This theorem constitutes part of the Prime Factorization Theorem.

Proof (by well-ordering principle). Let ${\displaystyle C}$ be the set of all integers greater than one that cannot be factored as a product of primes. We show that ${\displaystyle C}$ is empty.

Assume for the sake of contradiction that ${\displaystyle C}$ is not empty. Then, by the well-ordering principle, there is a least element ${\displaystyle n\in C}$; ${\displaystyle n}$ cannot be prime since a prime number itself is considered a length-one product of primes. By the definition of non-prime numbers, ${\displaystyle n}$ has factors ${\displaystyle a,b}$, where ${\displaystyle a,b}$ are integers greater than one and less than ${\displaystyle n}$. Since ${\displaystyle a,b<n}$, they are not in ${\displaystyle C}$ as ${\displaystyle n}$ is the smallest element of ${\displaystyle C}$. So, ${\displaystyle a,b}$ can be factored as products of primes, where ${\displaystyle a=p_{1}p_{2}...p_{k}}$ and ${\displaystyle b=q_{1}q_{2}...q_{l}}$, meaning that ${\displaystyle n=p_{1}p_{2}...p_{k}\cdot q_{1}q_{2}...q_{l}}$, a product of primes. This contradicts the assumption that ${\displaystyle n\in C}$, so the assumption that ${\displaystyle C}$ is nonempty must be false. ^[2]

Integer summation

Theorem: ${\displaystyle 1+2+3+...+n={\frac {n(n+1)}{2}}}$ for all positive integers ${\displaystyle n}$.

Proof. Suppose for the sake of contradiction that the above theorem is false. Then, there exists a non-empty set of positive integers ${\displaystyle C=\{n\in \mathbb {N} \mid 1+2+3+...+n\neq {\frac {n(n+1)}{2}}\}}$. By the well-ordering principle, ${\displaystyle C}$ has a minimum element ${\displaystyle c}$ such that when ${\displaystyle n=c}$, the equation is false, but true for all positive integers less than ${\displaystyle c}$. The equation is true for ${\displaystyle n=1}$, so ${\displaystyle c>1}$; ${\displaystyle c-1}$ is a positive integer less than ${\displaystyle c}$, so the equation holds for ${\displaystyle c-1}$ as it is not in ${\displaystyle C}$. Therefore,

$${\displaystyle {\begin{aligned}1+2+3+...+(c-1)&={\frac {(c-1)c}{2}}\\1+2+3+...+(c-1)+c&={\frac {(c-1)c}{2}}+c\\&={\frac {c^{2}-c}{2}}+{\frac {2c}{2}}\\&={\frac {c^{2}+c}{2}}\\&={\frac {c(c+1)}{2}}\end{aligned}}}$$

which shows that the equation holds for ${\displaystyle c}$, a contradiction. So, the equation must hold for all positive integers. ^[2]

References

1. Apostol, Tom (1976). Introduction to Analytic Number Theory . New York: Springer-Verlag. pp.  13. ISBN   0-387-90163-9.
2. Lehman, Eric; Meyer, Albert R; Leighton, F Tom. Mathematics for Computer Science (PDF). Retrieved 2 May 2023.