Well-Ordering and Induction

Two Ways to Reason About the Integers

The Principle of Mathematical Induction moves forward: establish a starting case, then show that each case leads to the next. The Well-Ordering Principle works differently: from any nonempty set of positive integers, choose its least member. These principles are closely connected. In the previous tutorial, the Well-Ordering Principle was derived from induction. Here we prove the converse: well-ordering can be used to establish induction.

The connection is useful in both directions. Induction is often convenient when a statement naturally passes from $n$ to $n+1$. Well-ordering is often convenient when a proof can assume that a failure exists and then examine the least failure. The equivalence explains why these approaches can support many of the same arguments.

Theorem (Well-Ordering Implies Mathematical Induction). Suppose $P(n)$ is a statement for every $n\in\mathbb{N}_0$. If $P(0)$ is true and, for every $n\in\mathbb{N}_0$, $P(n)$ implies $P(n+1)$, then $P(n)$ is true for every $n\in\mathbb{N}_0$.

Proof. Assume the hypotheses hold, but suppose that $P(n)$ is false for at least one $n\in\mathbb{N}_0$. The set

F=\{n\in\mathbb{N}_0:P(n)\text{ is false}\}

is then nonempty. As explained in the previous tutorial, the Well-Ordering Principle applies to nonempty subsets of $\mathbb{N}_0$, so $F$ has a least member $m$. Since $P(0)$ is true, $0\notin F$, and therefore $m\geq1$. It follows that $m-1\in\mathbb{N}_0$. The minimality of $m$ means that $m-1\notin F$, so $P(m-1)$ is true. The assumed implication from one case to the next now gives $P(m)$. This contradicts $m\in F$. Thus $F$ must be empty, and $P(n)$ is true for every $n\in\mathbb{N}_0$. $\square$

The converse was proved in the previous tutorial: the Principle of Mathematical Induction implies the Well-Ordering Principle. Together, the two implications establish their equivalence. This does not mean that every proof should be written both ways. It means that the two principles express closely related structure in the nonnegative integers, and each provides a valid route when its proof strategy is useful.

Key takeaway. To use induction through well-ordering, form the set of failures. If it were nonempty, its least member would have a predecessor where the statement is true, so the induction step would make the supposed least failure true as well.

Well-Ordering Gives Division with Remainder

A second application of well-ordering is to select a least nonnegative remainder. This produces the division algorithm, a basic result about integers. We use $\mathbb{N}_0=\{0,1,2,\ldots\}$, and take the divisor to be a positive integer.

Theorem (Division Algorithm for Nonnegative Integers). Let $a\in\mathbb{N}_0$ and let $d$ be a positive integer. There are unique $q,r\in\mathbb{N}_0$ such that $$ a=dq+r \qquad\text{and}\qquad 0\leq r<d. $$

Proof. Consider the set of nonnegative remainders obtainable by subtracting a nonnegative multiple of $d$ from $a$:

R=\{a-dq:q\in\mathbb{N}_0\text{ and }dq\leq a\}.

This set is nonempty: $q=0$ satisfies $dq=0\leq a$, so $a\in R$. Every member of $R$ is in $\mathbb{N}_0$. By the Well-Ordering Principle, $R$ has a least member $r$. By the definition of $R$, there is some $q\in\mathbb{N}_0$ such that $r=a-dq$, which gives $a=dq+r$, and $r\geq0$.

It remains to show $r<d$. If $r\geq d$, then $r-d\geq0$, and

$$ r-d=a-dq-d=a-d(q+1). $$

Since $r-d\geq0$, we have $d(q+1)\leq a$. Thus $r-d\in R$. But $r-d<r$, contradicting that $r$ is the least member of $R$. Hence $0\leq r<d$.

For uniqueness, suppose also that $a=dq'+r'$, where $q'\in\mathbb{N}_0$ and $0\leq r'<d$. Equating the two expressions for $a$ gives

$$ d(q-q')=r'-r. $$

If $q>q'$, then $d(q-q')\geq d$, whereas $r'-r<d$ because $r'\leq d-1$ and $r\geq0$. This is impossible. If $q<q'$, then $d(q-q')\leq-d$, whereas $r'-r>-d$ because $r'\geq0$ and $r\leq d-1$. This is also impossible. Therefore $q=q'$, and the displayed equality then gives $r=r'$. The quotient and remainder are unique. $\square$

The least element in this proof is a remainder, not a quotient. The set $R$ was designed so that every one of its members is nonnegative, while a remainder at least $d$ would allow a smaller member to be constructed. This is a useful pattern: define a nonempty set of nonnegative integer candidates, choose its least member, and show that a candidate violating the desired bound would produce a smaller one.

Worked Examples

Worked Example: Dividing 137 by 12

The Division Algorithm says that there are unique nonnegative integers $q$ and $r$, with $0\leq r<12$, such that $137=12q+r$. To find them, observe that

12\cdot11=132\leq137, \qquad 12\cdot12=144>137.

Subtracting $132$ from $137$ gives $r=5$, so $q=11$. Direct substitution verifies the equation:

137=12\cdot11+5, \qquad 0\leq5<12.

The uniqueness part of the theorem shows that no other quotient and remainder satisfy these conditions. Merely finding an equation of the form $137=12q+r$ would not be enough: the bound $0\leq r<12$ is essential.

Worked Example: Every Positive Integer Has a Binary Representation

We prove that every positive integer is a sum of distinct nonnegative powers of $2$. A sum of distinct powers means that no power occurs more than once; for example, $13=2^3+2^2+2^0$. Suppose, for a contradiction, that some positive integers have no such representation. Let $n$ be the least one. Since $1=2^0$, we have $n>1$.

Apply the Division Algorithm with divisor $2$. There are $q\in\mathbb{N}_0$ and $r\in\{0,1\}$ such that $n=2q+r$. Since $n>1$, in either case $q\geq1$; also $q<n$. By the choice of $n$ as the least failure, $q$ has a representation as a sum of distinct powers of $2$. Write it as

q=\sum_{j\in J}2^j,

where $J$ is a finite set of distinct nonnegative integers. If $r=0$, then

n=2q=\sum_{j\in J}2^{j+1}.

These are distinct powers of $2$, since different indices $j$ give different indices $j+1$. Thus $n$ has the required representation in this case.

If $r=1$, then

n=2q+1=2^0+\sum_{j\in J}2^{j+1}.

Every exponent $j+1$ in the sum is at least $1$, so none of those powers is $2^0$. They remain distinct from one another as well. This is again a representation of $n$ as a sum of distinct powers of $2$. Both possible remainders contradict that $n$ was a failure. Therefore every positive integer has such a representation.

Worked Example: A Binary Representation Is Unique

Suppose a positive integer has two representations as sums of distinct nonnegative powers of $2$. We show that the sets of exponents in the two representations must be the same. If the sets differed, their symmetric difference—the exponents appearing in exactly one set—would be nonempty and finite. Let $k$ be its least member.

All powers with exponents less than $k$ appear on both sides or on neither side, so they cancel when the representations are equated. Divide the remaining equality by $2^k$. On one side there is a contribution $1$, because the exponent $k$ appears there. Every other remaining term on that side has the form $2^{j-k}$ with $j>k$, and is therefore even. That side is odd.

On the other side, exponent $k$ does not appear, and all remaining terms also have the form $2^{j-k}$ with $j>k$. Each is even, so their sum is even (including the possibility of an empty sum, which is $0$). An odd integer cannot equal an even integer, contradicting the assumed equality. Hence the exponent sets cannot differ, and the representation is unique.

This argument uses the least place where the representations differ. Choosing that smallest exponent isolates a single $2^k$ on one side; after the common lower powers are removed, parity rules out equality.

Worked Example: Converting 173 to Base 5

Repeated division by $5$ gives the base-$5$ digits as successive remainders. The divisions are

173=5\cdot34+3, \qquad 34=5\cdot6+4, \qquad 6=5\cdot1+1, \qquad 1=5\cdot0+1.

Read the remainders from last to first to obtain the digits $1,1,4,3$. Checking the result in decimal notation confirms the calculation:

1\cdot5^3+1\cdot5^2+4\cdot5+3 =125+25+20+3 =173.

Each division has a unique remainder between $0$ and $4$, by the Division Algorithm. The remainders therefore give valid base-$5$ digits, and the final quotient is $0$, so there are no further digits to record.

Choosing the Right View

The equivalence of induction and well-ordering gives two complementary proof plans. When the next case follows directly from the current one, induction often keeps the argument organized. When the assumption of a failure naturally leads to a least integer, well-ordering can expose a contradiction. In the binary representation example, the least failure would have a smaller quotient that already has a representation; the division algorithm then turns that representation into one for the supposed failure itself.

A common pitfall is to choose a least object before proving that the candidate set is nonempty and consists of nonnegative or positive integers. The Well-Ordering Principle cannot be applied to an empty set, nor does it promise a least member for an arbitrary set of real numbers. Another pitfall is to omit a bound on the remainder in division: without $0\leq r<d$, quotient and remainder need not be unique.

Key takeaway. The Well-Ordering Principle and the Principle of Mathematical Induction are equivalent. Well-ordering proves induction by ruling out a least failure, and it also proves division with remainder by selecting the least attainable nonnegative remainder.

Check Your Understanding

Use the proofs and examples in this tutorial to answer the following questions.

In the proof that well-ordering implies induction, why can the least false index not be $0$?
In the Division Algorithm proof, what contradiction follows if the least attainable remainder is at least $d$?
Why does the uniqueness proof for division with remainder rule out both $q>q'$ and $q<q'$?
In the binary representation argument, why is $q$ smaller than the least failing integer $n$?
Why do the shifted powers in the odd case of the binary representation proof not duplicate $2^0$?

What You'll Learn