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
and some nonnegative integer (other orderings include the ordering
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.
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 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).
The well-ordering principle can be used in the following proofs.
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).
be the set of all integers greater than one that cannot be factored as a product of primes.
Assume for the sake of contradiction that
Then, by the well-ordering principle, there is a least element
By the definition of non-prime numbers,
is the smallest element of
can be factored as products of primes, where
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
, the equation is false, but true for all positive integers less than
which shows that the equation holds for
So, the equation must hold for all positive integers.