Well-ordering principle
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 precedes if and only if is either or the sum of and some nonnegative integer (other orderings include the ordering ; and ).
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 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 of natural numbers has an infimum, say . We can now find an integer such that lies in the half-open interval , and can then show that we must have , and in .
- 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 such that " 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 , 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 be the set of all integers greater than one that cannot be factored as a product of primes. We show that is empty.
Assume for the sake of contradiction that is not empty. Then, by the well-ordering principle, there is a least element ; cannot be prime since a prime number itself is considered a length-one product of primes. By the definition of non-prime numbers, has factors , where are integers greater than one and less than . Since , they are not in as is the smallest element of . So, can be factored as products of primes, where and , meaning that , a product of primes. This contradicts the assumption that , so the assumption that is nonempty must be false.[2]
Integer summation
Theorem: for all positive integers .
Proof. Suppose for the sake of contradiction that the above theorem is false. Then, there exists a non-empty set of positive integers . By the well-ordering principle, has a minimum element such that when , the equation is false, but true for all positive integers less than . The equation is true for , so ; is a positive integer less than , so the equation holds for as it is not in . Therefore, which shows that the equation holds for , a contradiction. So, the equation must hold for all positive integers.[2]
References
- ^ Apostol, Tom (1976). Introduction to Analytic Number Theory. New York: Springer-Verlag. pp. 13. ISBN 0-387-90163-9.
- ^ a b Lehman, Eric; Meyer, Albert R; Leighton, F Tom. Mathematics for Computer Science (PDF). Retrieved 2 May 2023.