Well-ordering principle
Template:Short description Template:DistinguishIn mathematics, the well-ordering principle, also called the well-ordering property<ref name=":0" /> or least natural number principle,<ref>Template:Cite book</ref><ref>Template:Cite book</ref> states that every non-empty subset of the nonnegative integers<ref name="Tuset" /> contains a least element,<ref>Template:Cite book</ref> also called a smallest element.<ref>Template:Cite book</ref> In other words, if <math>A</math> is a nonempty subset of the nonnegative integers, then there exists an element of <math>A</math> which is less than, or equal to, any other element of <math>A</math>.<ref name=":0">Template:Cite book</ref> Formally, <math>\forall A \left[ \left( A \subseteq \mathbb{Z}_{\geq 0} \land A \neq \varnothing \right) \rightarrow \left( \exists m \in A \, \forall a \in A \, (m \leq a) \right) \right]</math>.<ref>Template:Cite web</ref> Most sources state this as an axiom or theorem about the natural numbers, but the phrase "natural number" was avoided here due to ambiguity over the inclusion of zero. The statement is true about the set of natural numbers <math>\mathbb{N}</math> regardless whether it is defined as <math>\mathbb{Z}_{\geq 0}</math> (nonnegative integers) or as <math>\mathbb{Z}^+</math> (positive integers), since one of Peano's axioms for <math>\mathbb{N}</math>, the induction axiom (or principle of mathematical induction), is logically equivalent to the well-ordering principle.<ref name=":3" /> Since <math>\mathbb{Z}^+ \subseteq \mathbb{Z}_{\geq 0}</math> and the subset relation <math>\subseteq</math> is transitive, the statement about <math>\mathbb{Z}^+</math> is implied by the statement about <math>\mathbb{Z}_{\geq 0}</math>. Template:Quote box
The standard order on <math>\mathbb{N}</math> is well-ordered by the well-ordering principle, since it begins with a least element, regardless whether it is 1 or 0. By contrast, the standard order on <math>\mathbb{R}</math> (or on <math>\mathbb{Z}</math>) is not well-ordered by this principle, since there is no smallest negative number.<ref name=":5">Template:Cite book</ref> According to Deaconu and Pfaff,<ref>Template:Cite book</ref> the phrase "well-ordering principle" is used by some (unnamed) authors as a name for Zermelo's "well-ordering theorem" in set theory, according to which every set can be well-ordered. This theorem, which is not the subject of this article, implies that "in principle there is some other order on <math>\mathbb{R}</math> which is well-ordered, though there does not appear to be a concrete description of such an order."<ref name=":5" />
Equivalent to induction
The well-ordering principle is logically equivalent to the principle of mathematical induction, according to which <math>\forall n \in \mathbb{Z}_{\geq 0} \left[ \left( P(0) \land \left( \forall k \in \mathbb{Z}_{\geq 1} [ P(k) \rightarrow P(k+1) ] \right) \right] \rightarrow P(n) \right]</math>.<ref name=":1">Template:Cite book</ref><ref name=":2">Template:Cite book</ref><ref>Template:Cite book</ref> In other words, if one takes the principle of mathematical induction as an axiom, one can prove the well-ordering principle as a theorem (as done in <ref>Template:Cite book</ref><ref>Template:Cite book</ref>), and conversely, if one takes the well-ordering principle as an axiom, one can prove the principle of mathematical induction as a theorem (as done in <ref>Template:Cite book</ref><ref name=":4">Template:Cite book</ref><ref>Template:Cite book</ref>).<ref name=":1" /><ref name=":2" /> The former is more common due to tradition, since the principle of mathematical induction was one of Peano's axioms for the natural numbers, and Peano was an influential mathematician.
The principle of mathematical induction and the well-ordering principle are each also equivalent to the principle of strong induction (also called the principle of complete induction), according to which <math>\left[ \left( P(0) \land \forall k \left( \left( \forall j \, (0 \leq j \leq k) \rightarrow P(j) \right) \rightarrow P(k+1) \right) \right) \right] \rightarrow \forall n \in \mathbb{Z}_{\geq 0}, \, P(n)</math>.<ref>Template:Cite book</ref> Accordingly, one can also use the principle of strong induction as an axiom to prove the well-ordering principle as a theorem (as done in <ref>Template:Cite book</ref><ref>Template:Cite book</ref><ref>Template:Cite book</ref><ref>Template:Cite book</ref>), or take the well-ordering principle as an axiom to prove the principle of strong induction as a theorem (as in <ref>Template:Cite book</ref>Template:Refn).
This also means that, in axiomatic set theory, the definition of the natural numbers as the smallest inductive set, <math>\mathbb{N} = \{ x \in S \mid 0 \in S \land \forall n \in S,\; n+1 \in S \}</math>, is equivalent to the statement that the well-ordering principle is true for it.<ref name=":3">Template:Cite book</ref>
Implied by completeness of the reals
If one knows, as an axiom or theorem, that the real numbers are complete, then one can use this to prove the well-ordering principle for nonnegative integers.<ref>Template:Cite book</ref> This is because the completeness property implies that every bounded-from-below subset of <math>\mathbb{R}</math> has an infimum, which means that, since <math>\mathbb{Z}_{\geq 0}</math> is a bounded-from-below subset of <math>\mathbb{R}</math> (and the subset relation <math>\subseteq</math> is transitive), then also every set <math>A \subseteq \mathbb{Z}_{\geq 0}</math> has an infimum <math>a</math>, which implies that there exists an integer <math>n</math> such that <math>a</math> lies in the half-open interval <math>(n-1,n]</math>, which implies that <math>a = n</math> and <math>n \in A</math>.<ref>Template:Cite book</ref>
Nonalgebraic
The well-ordering principle, like the least upper bound axiom for real numbers,<ref>Template:Cite book</ref><ref>Template:Cite book</ref> is non-algebraic, i.e., it cannot be deduced from the algebraic properties of the integers (which form an ordered integral domain).<ref>Template:Cite book</ref><ref>Template:Cite book</ref>
Used in proofs by minimal counterexample
The well-ordering principle is used in proofs by minimal counterexample, also known light-heartedly as the "minimal criminal" method of proof,<ref>Template:Cite book</ref> in which to prove that every natural number belongs to a specified set <math>S</math>, one assumes the contrary, which implies that the set of counterexamples is non-empty and thus (given the well-ordering principle) contains a smallest counterexample. One then shows 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, and is similar in its nature to Fermat's method of "infinite descent". The following are examples of this that have been found in the literature.
Example: no integer between 0 and 1
Theorem: There is no integer between 0 and 1, so that 1 is the smallest positive integer.
Proof.<ref>Template:Cite book</ref><ref>Template:Cite book</ref> Assume, for contradiction, that there exists an integer <math>n</math> such that <math>0 < n < 1</math>. By the well-ordering principle, the set of positive integers less than 1 has a least element, say <math>n</math>. Since <math>0 < n < 1</math>, multiplying all parts of the inequality by <math>n</math> gives <math>0 < n^2 < n</math>. But if <math>n</math> is an integer, then <math>n^2</math> would also be an integer, which contradicts the initial assumption that <math>n</math> was the least positive integer between 0 and 1. Therefore, this assumption is false, and there is no integer between 0 and 1.
Example: all decreasing nonnegative integer sequences finite
Theorem: Every decreasing sequence of nonnegative integers is finite.
Proof.<ref>Template:Cite book</ref><ref>Template:Cite book</ref> Suppose that there exists a strictly decreasing sequence <math>S</math> of nonnegative integers <math>a_1 > a_2 > a_3 > \cdots</math>; then by the well-ordering principle, <math>S</math> has a least element <math>a_k</math> for some <math>k</math>. But <math>a_k</math> must be the last in the sequence, otherwise <math>a_{k+1} < a_k</math>, which contradicts the assumption that <math>a_k</math> is the smallest member.
Example: prime factorization
Theorem: Every integer greater than one is a product of finitely many primes. This theorem constitutes part of the Fundamental Theorem of Arithmetic.
Proof.<ref>Template:Cite book</ref><ref>Template:Cite book</ref><ref>Template:Cite book</ref> Let <math>C</math> be the set of all integers greater than one that cannot be factored as a product of primes. We show that <math>C</math> is empty: assume for the sake of contradiction that <math>C</math> is not empty. Then, by the well-ordering principle, there is a least element <math>n \in C</math>; <math>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>n</math> has factors <math>a, b</math>, where <math>a, b</math> are integers greater than one and less than <math>n</math>. Since <math>a, b < n</math>, they are not in <math>C</math> as <math>n</math> is the smallest element of <math>C</math>. So, <math>a, b</math> can be factored as products of primes, where <math>a = p_1p_2...p_k</math> and <math>b = q_1q_2...q_l</math>, meaning that <math>n = p_1p_2...p_k \cdot q_1q_2...q_l</math>, a product of primes. This contradicts the assumption that <math>n \in C</math>, so the assumption that <math>C</math> is nonempty must be false.
External links
- Proof of equivalence between the well-ordering principle and the principle of mathematical induction