Choosing the Least Integer
The Principle of Mathematical Induction lets us establish a statement at a starting integer and then carry it forward one step at a time. The Well-Ordering Principle gives a different way to reason about positive integers: if a collection of them is nonempty, one of its members must be the smallest. This is useful when a proof can be organized around the smallest possible failure, or the smallest object with a specified property.
The condition that the set be nonempty matters: the empty set has no element that could be least. The domain matters too. The principle applies to subsets of the positive integers, not to every nonempty subset of the real numbers. For example, the real interval \((0,1)\) has no least element, since for every \(x\in(0,1)\), the smaller number \(x/2\) is also in \((0,1)\).
The principle also applies to nonempty subsets of \(\mathbb{N}_0=\{0,1,2,\ldots\}\). If such a set contains \(0\), then \(0\) is its least element. If it does not contain \(0\), it is a nonempty subset of the positive integers, so the Well-Ordering Principle applies.
Deriving the Principle from Induction
In this course, the Well-Ordering Principle can be obtained from the Principle of Mathematical Induction. The argument uses the contrapositive idea that a set with no least element cannot contain any positive integer.
Proof. Suppose, to the contrary, that a nonempty set \(A\) of positive integers has no least element. For each positive integer \(n\), let \(P(n)\) be the statement that \(A\) contains no element less than or equal to \(n\).
First, \(P(1)\) holds. If \(1\in A\), then \(1\) would be the least element of \(A\), contrary to the assumption. Thus \(1\notin A\), which is exactly \(P(1)\).
Now suppose \(P(n)\) holds for some positive integer \(n\). If \(n+1\in A\), then \(A\) has no element at most \(n\), by \(P(n)\). Every positive integer less than \(n+1\) is at most \(n\), so \(n+1\) would be the least element of \(A\). This again contradicts the assumption that \(A\) has no least element. Therefore \(n+1\notin A\), and \(P(n+1)\) holds. By the Principle of Mathematical Induction, \(P(n)\) holds for every positive integer \(n\).
Since \(A\) is nonempty, choose \(a\in A\). The statement \(P(a)\) says that \(A\) contains no element less than or equal to \(a\), but \(a\) itself belongs to \(A\). This is a contradiction. Hence every nonempty set of positive integers has a least element. \(\square\)
The proof highlights the connection with induction: assuming there is no least element lets us show that every positive integer is absent from \(A\), one integer at a time. But the principle is useful in its own right, because it allows us to start with a nonempty set of integers and select its smallest member directly.
Worked Examples
Worked Example: The Least Positive Integer Whose Square Exceeds Fifty
Consider the set
This set is nonempty because \(8^2=64>50\), so the Well-Ordering Principle guarantees that \(A\) has a least element. We can identify it: \(7^2=49\leq50\), while \(8^2=64>50\). If \(n\) is a positive integer with \(n<8\), then \(n\leq7\), so \(n^2\leq49\). Thus no positive integer less than \(8\) belongs to \(A\), and \(8\) does belong to \(A\). Its least element is \(8\).
The principle guarantees a least element as soon as nonemptiness is established. To identify that element explicitly, we still need to check that it belongs to the set and that no smaller positive integer does.
Worked Example: A Strictly Decreasing Sequence of Positive Integers Cannot Continue Forever
Suppose, for a contradiction, that positive integers \(a_1,a_2,\ldots\) satisfy \(a_{k+1}<a_k\) for every positive integer \(k\). The set \(S=\{a_k:k\geq1\}\) is a nonempty set of positive integers. By the Well-Ordering Principle, it has a least element \(a_j\) for some index \(j\).
But \(a_{j+1}\) also belongs to \(S\), and the assumed decrease gives \(a_{j+1}<a_j\). This contradicts the fact that \(a_j\) is the least element of \(S\). Therefore no infinite sequence of positive integers can be strictly decreasing at every step.
The contradiction depends on both parts of the setup: the values are positive integers, and each next value is strictly smaller. A nonincreasing sequence may repeat values, and a decreasing sequence of real numbers need not be impossible; for example, \(1,1/2,1/3,\ldots\) is strictly decreasing and consists of positive real numbers.
Worked Example: Every Integer Greater Than One Has a Prime Divisor
Let \(n\geq2\) be an integer, and define \(D=\{d\in\{1,2,3,\ldots\}:d\mid n\text{ and }d\geq2\}\). This set is nonempty because \(n\mid n\) and \(n\geq2\). By the Well-Ordering Principle, \(D\) has a least element \(d\).
We claim that \(d\) is prime. It is an integer greater than \(1\). If it were not prime, it would have a positive divisor \(u\) with \(1<u<d\). Since \(u\mid d\) and \(d\mid n\), divisibility is transitive, so \(u\mid n\). Hence \(u\in D\), contradicting the minimality of \(d\), because \(u<d\). Thus \(d\) is prime. Since \(d\mid n\), this proves that \(n\) has a prime divisor.
The choice of set is the key step: we collect the divisors of \(n\) that are at least \(2\), then take the smallest one. If that smallest divisor could be factored into smaller positive integers greater than \(1\), one of those factors would be a smaller member of the same set.
Worked Example: Every Integer Greater Than One Is a Product of Primes
Call an integer \(n\geq2\) a failure if it cannot be written as a product of finitely many primes. Suppose there is at least one failure. The set of failures is a nonempty subset of the positive integers, so it has a least member \(n\).
If \(n\) is prime, then it is already a product of primes with just one factor, contradicting that \(n\) is a failure. If \(n\) is not prime, then, since \(n\geq2\), it has a factorization \(n=ab\) with integers \(1<a<n\) and \(1<b<n\). Neither \(a\) nor \(b\) is a failure: each is an integer at least \(2\) and smaller than the least failure \(n\). Thus each is a product of finitely many primes. Joining those two products gives a product of primes equal to \(ab=n\), again contradicting that \(n\) is a failure.
Both possibilities lead to a contradiction, so there are no failures. Every integer greater than one is a product of finitely many primes. This argument establishes existence of a prime factorization; it does not establish that the factorization is unique.
The Least-Counterexample Technique
The last example illustrates a general way to organize a proof. Instead of trying to prove a claim for all positive integers at once, suppose that some integers violate it and choose the least one that does. If the least failure can be shown not to be a failure, the assumption that any failure exists is impossible.
Specify precisely which positive integers would contradict the claim, and assume this set is nonempty.
Apply the Well-Ordering Principle to the nonempty set of positive integers that fail the claim.
Show that the least failure either satisfies the claim after all or would force a smaller failure.
Either outcome conflicts with the choice of the least failure, so no failure exists.
A common pitfall is to choose a least element without first establishing that the set in question is nonempty and consists of positive integers. The Well-Ordering Principle applies only after both conditions have been checked. Also, the principle guarantees a least element, not a greatest one: the positive integers themselves have a least element, \(1\), but no greatest element.
Check Your Understanding
Use the Well-Ordering Principle and the examples above to answer the following questions.
- Why must a set be nonempty before the Well-Ordering Principle can be applied?
- What are the two facts about a set that made the decreasing-sequence contradiction possible?
- In the prime-divisor argument, why would a nonprime least divisor produce a smaller member of the divisor set?
- What must be shown about the set of failures before choosing its least member?
- Why does the Well-Ordering Principle not imply that every nonempty subset of the real numbers has a least element?