Well-ordering principle

Short description: Statement that all sets of positive numbers contains a least element

In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which $x$ precedes $y$ if and only if $y$ is either $x$ or the sum of $x$ and some positive integer (other orderings include the ordering $2,4,6,...$; and $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 $\{\dots ,-2,-1,0,1,2,3,\dots \}$ 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 $A$ of natural numbers has an infimum, say $a^{*}$. We can now find an integer $n^{*}$ such that $a^{*}$ lies in the half-open interval $(n^{*}-1,n^{*}]$, and can then show that we must have $a^{*}=n^{*}$, and $n^{*}$ in $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 $n$ such that "$\{0,\dots ,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 $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 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 $C$ be the set of all integers greater than one that cannot be factored as a product of primes. We show that $C$ is empty.

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

Integer summation

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

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

References

cs:Princip dobrého uspořádání