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 [math]\displaystyle{ x }[/math] precedes [math]\displaystyle{ y }[/math] if and only if [math]\displaystyle{ y }[/math] is either [math]\displaystyle{ x }[/math] or the sum of [math]\displaystyle{ x }[/math] and some positive integer (other orderings include the ordering [math]\displaystyle{ 2, 4, 6, ... }[/math]; and [math]\displaystyle{ 1, 3, 5, ... }[/math]).

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 [math]\displaystyle{ \{\ldots, -2, -1, 0, 1, 2, 3, \ldots \} }[/math] 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 [math]\displaystyle{ A }[/math] of natural numbers has an infimum, say [math]\displaystyle{ a^* }[/math]. We can now find an integer [math]\displaystyle{ n^* }[/math] such that [math]\displaystyle{ a^* }[/math] lies in the half-open interval [math]\displaystyle{ (n^*-1,n^*] }[/math], and can then show that we must have [math]\displaystyle{ a^* = n^* }[/math], and [math]\displaystyle{ n^* }[/math] in [math]\displaystyle{ A }[/math].
• 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 [math]\displaystyle{ n }[/math] such that "[math]\displaystyle{ \{0,\ldots,n\} }[/math] 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 [math]\displaystyle{ S }[/math], 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 [math]\displaystyle{ C }[/math] be the set of all integers greater than one that cannot be factored as a product of primes. We show that [math]\displaystyle{ C }[/math] is empty.

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

Integer summation

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

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

References

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