# 4.1: Well-orderings

- Page ID
- 99069

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.