# 4.1: Well-orderings

• Bob Dumas and John E. McCarthy
• University of Washington and Washington University in St. Louis

In this chapter we discuss the principle of mathematical induction. Be aware that the word induction has a different meaning in mathematics than in the rest of science. The principle of mathematical induction depends on the order structure of the natural numbers, and gives us a powerful technique for proving universal mathematical claims.

DEFINITION. Well-ordering Let $$X$$ be a set, and $$\preceq$$ a linear ordering on $$X$$. We say that $$X$$ is well-ordered with respect to $$\preceq$$ (or $$\preceq$$ is a wellordering of $$X$$ ) if every non-empty subset of $$X$$ has a least element with respect to $$\preceq$$. That is, for any non-empty subset $$Y$$ of $$X$$ $(\exists a \in Y)(\forall y \in Y) a \preceq y .$ In general, linear orderings need not be well-orderings. Well-ordering is a universal property — a set $$X$$ with an ordering $$\preceq$$ is well-ordered if every non-empty subset of $$X$$ has a least element with respect to $$\preceq$$. If there is any non-empty subset which does not have a least element, then $$\preceq$$ does not well-order $$X$$.

EXAMPLE 4.1. $$\mathbb{Z}$$ is not well-ordered by $$\leq$$. The integers do not have a least element, which suffices to demonstrate that $$\mathbb{Z}$$ is not well-ordered by $$\leq$$.

EXAMPLE 4.2. Let $$X=\{x \in \mathbb{R} \mid x \geq 2\}$$. Let $$\leq$$ be the usual ordering on $$\mathbb{R} . X$$ is linearly ordered by $$\leq$$, but $$X$$ is not well-ordered by $$\leq$$. In this example, $$X$$ has a least element, but any open interval contained in $$X$$ will fail to have a least element. The key order properties of $$\mathbb{N}$$ are that it is well-ordered and every element of $$\mathbb{N}$$, except 0 , is the successor of a natural number:

WELL-ORDERING PRINCIPLE FOR THE NATURAL NUMBERS: The set $$\mathbb{N}$$ is well-ordered by $$\leq$$.

SUCCESSOR PROPERTY FOR THE NATURAL NUMBERS: If $$n \in \mathbb{N}$$ and $$n \neq 0$$, then there is $$m \in \mathbb{N}$$ such that $$n=m+1$$.

If one accepts an intuitive understanding of the natural numbers, these principles are more or less obvious. Indeed, let $$Y$$ be any nonempty subset of $$\mathbb{N}$$. Since it is non-empty, there is some $$m$$ in $$Y$$. Now, consider each of the finitely many numbers $$0,1,2, \ldots, m$$ in turn. If $$0 \in Y$$, then 0 is the least element. If 0 is not in $$Y$$, proceed to 1 . If this is in $$Y$$, it must be the least element; otherwise proceed to 2 . Continue in this way, and you will find some number less than or equal to $$m$$ that is the least element of $$Y$$.

This argument, though convincing, does rely on the fact that we have an idea of what $$\mathbb{N}$$ "is". If we wish to define $$\mathbb{N}$$ in terms of set operations, as we do in Chapter 8, we essentially have to include the well-ordering principle for the natural numbers as an axiom.

This page titled 4.1: Well-orderings is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Bob Dumas and John E. McCarthy via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.