Well-ordering principle explained

Well-ordering principle should not be confused with Well-ordering theorem.

In mathematics, the well-ordering principle states that every non-empty subset of nonnegative integers contains a least element.^[1] In other words, the set of nonnegative 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 nonnegative integer (other orderings include the ordering 2 , 4 , 6 , ... ; and 1 , 3 , 5 , ... ).\{\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

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 ,\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

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 _{1p} _{2...p} _{k} and b = q _{1q} _{2...q} _{l} , meaning that n = p _{1p} _{2...p} _{k} ⋅ q _{1q} _{2...q} _{l} , a product of primes. This contradicts the assumption that n \in C , so the assumption that C is nonempty must be false.^[2]

Integer summation

Theorem:

1 + 2 + 3 + ... + n = (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 N \mid 1 + 2 + 3 + ... + n ≠ (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, which shows that the equation holds for c , a contradiction. So, the equation must hold for all positive integers.^[2]

Notes and References

1. Book: Apostol, Tom . Introduction to Analytic Number Theory . Tom M. Apostol . 1976 . Springer-Verlag . New York . 0-387-90163-9 . 13 . registration .
2. Book: Lehman . Eric . Meyer . Albert R . Leighton . F Tom . Mathematics for Computer Science . 2 May 2023.