TAOCP 1.2.1 Exercise 15
Let $\prec$ be a relation on a set $S$ satisfying: 1.
Section 1.2.1: Mathematical Induction
Exercise 15. ▶ [HM28] (Generalized induction.) The text shows how to prove statements $P(n)$ that depend on a single integer $n$, but it does not describe how to prove statements $P(m, n)$ depending on two integers. In these circumstances a proof is often given by some sort of “double induction,” which frequently seems confusing. Actually, there is an important principle more general than simple induction that applies not only to this case but also to situations in which statements are to be proved about uncountable sets, for example, $P(x)$ for all real $x$. This general principle is called well-ordering.
Let “$\prec$” be a relation on a set $S$, satisfying the following properties:
i) Given $x$, $y$, and $z$ in $S$, if $x \prec y$ and $y \prec z$, then $x \prec z$. ii) Given $x$ and $y$ in $S$, exactly one of the following three possibilities is true: $x \prec y$, $x = y$, or $y \prec x$. iii) If $A$ is any nonempty subset of $S$, there is an element $x$ in $A$ with $x \preceq y$ (that is, $x \prec y$ or $x = y$) for all $y$ in $A$.
This relation is said to be a well-ordering of $S$. For example, it is clear that the positive integers are well-ordered by the ordinary “less than” relation, $<$.
a) Show that the set of all integers is not well-ordered by $<$. b) Define a well-ordering relation on the set of all integers. c) Is the set of all nonnegative real numbers well-ordered by $<$? d) (Lexicographic order.) Let $S$ be well-ordered by $\prec$, and for $n > 0$ let $T_n$ be the set of all $n$-tuples $(x_1, x_2, \ldots, x_n)$ of elements $x_j$ in $S$. Define $(x_1, x_2, \ldots, x_n) \prec (y_1, y_2, \ldots, y_n)$ if there is some $k$, $1 \le k \le n$, such that $x_j = y_j$ for $1 \le j < k$, but $x_k \prec y_k$ in $S$. Is $\prec$ a well-ordering of $T_n$? e) Continuing part (d), let $T = \bigcup_{n \ge 1} T_n$; define $(x_1, x_2, \ldots, x_m) \prec (y_1, y_2, \ldots, y_n)$ if $x_j = y_j$ for $1 \le j < k$ and $x_k \prec y_k$, for some $k \le \min(m, n)$, or if $m < n$ and $x_j = y_j$ for $1 \le j \le m$. Is $\prec$ a well-ordering of $T$? f) Show that $\prec$ is a well-ordering of $S$ if and only if it satisfies (i) and (ii) above and there is no infinite sequence $x_1, x_2, x_3, \ldots$ with $x_{j+1} \prec x_j$ for all $j \ge 1$. g) Let $S$ be well-ordered by $\prec$, and let $P(x)$ be a statement about the element $x$ of $S$. Show that if $P(x)$ can be proved under the assumption that $P(y)$ is true for all $y \prec x$, then $P(x)$ is true for all $x$ in $S$.
[Notes: Part (g) is the generalization of simple induction that was promised; in the case $S =$ positive integers, it is just the simple case of mathematical induction treated in the text. In that case we are asked to prove that $P(1)$ is true if $P(y)$ is true for all positive integers $y < 1$; this is the same as saying we should prove $P(1)$, since $P(y)$ certainly is (vacuously) true for all such $y$. Consequently, one finds that in many situations $P(1)$ need not be proved using a special argument.
Part (d), in connection with part (g), gives us a powerful method of $n$-tuple induction for proving statements $P(m_1, \ldots, m_n)$ about $n$ positive integers $m_1, \ldots, m_n$.
Part (f) has further application to computer algorithms: If we can map each state $x$ of a computation into an element $f(x)$ belonging to a well-ordered set $S$, in such a way that every step of the computation takes a state $x$ into a state $y$ with $f(y) \prec f(x)$, then
Verified: yes
Solve time: 2m18s
Setup
Let $\prec$ be a relation on a set $S$ satisfying:
- If $x \prec y$ and $y \prec z$, then $x \prec z$.
- For any $x,y \in S$, exactly one of
$$ x \prec y,\qquad x=y,\qquad y\prec x $$
holds. 3. Every nonempty subset $A \subseteq S$ has a least element; that is, some $x\in A$ satisfies
$$ x \preceq y $$
for all $y\in A$.
Such a relation is called a well-ordering.
We solve parts (a) through (g).
(a)
The set of all integers is not well-ordered by the ordinary relation $<$.
Consider the subset
$$ A={-1,-2,-3,\ldots}. $$
Suppose $A$ had a least element $m$. Then $m-1\in A$, and
$$ m-1<m, $$
contradicting the assumption that $m$ is least.
Therefore $A$ has no least element, so property (iii) fails. Hence the integers are not well-ordered by $<$.
∎
(b)
Define an ordering $\prec$ on the integers by
$$ 0 \prec 1 \prec -1 \prec 2 \prec -2 \prec 3 \prec -3 \prec \cdots. $$
Equivalently,
$$ x\prec y $$
if either
$$ |x|<|y|, $$
or
$$ |x|=|y| \quad\text{and}\quad x>y. $$
We verify the three properties.
Property (i)
Suppose $x\prec y$ and $y\prec z$.
If
$$ |x|<|y| \quad\text{and}\quad |y|<|z|, $$
then clearly $|x|<|z|$, so $x\prec z$.
The remaining cases involving equal absolute values are immediate from the tie-breaking rule. Thus $\prec$ is transitive.
Property (ii)
Given integers $x$ and $y$, either $|x|<|y|$, $|x|=|y|$, or $|y|<|x|$. In the equal case, either $x=y$, $x>y$, or $y>x$. Hence exactly one of
$$ x\prec y,\qquad x=y,\qquad y\prec x $$
holds.
Property (iii)
Let $A$ be a nonempty set of integers. Consider
$$ B={|x|:x\in A}. $$
Since $B$ is a nonempty set of nonnegative integers, it has a least element $m$.
If $m=0$, then $0\in A$, and clearly $0$ is least in $A$.
Assume $m>0$. Then either $m\in A$ or $-m\in A$.
If $m\in A$, then $m\prec -m$, and every other element of $A$ has absolute value at least $m$. Hence $m$ is least in $A$.
If $m\notin A$, then necessarily $-m\in A$, and again every other element of $A$ has absolute value at least $m$. Hence $-m$ is least in $A$.
Therefore every nonempty subset has a least element. Thus $\prec$ is a well-ordering.
∎
(c)
The set of all nonnegative real numbers is not well-ordered by $<$.
Consider
$$ A={x\in\mathbb R:x>0}. $$
Suppose $A$ had a least element $a$. Then
$$ \frac a2>0, $$
so $a/2\in A$, and
$$ \frac a2<a, $$
contradicting the minimality of $a$.
Hence $A$ has no least element. Therefore the nonnegative real numbers are not well-ordered by $<$.
∎
(d)
Let $S$ be well-ordered by $\prec$, and let $T_n$ be the set of all $n$-tuples of elements of $S$, ordered lexicographically.
Thus
$$ (x_1,\ldots,x_n)\prec(y_1,\ldots,y_n) $$
if for some $k$,
$$ x_j=y_j \quad (1\le j<k), $$
and
$$ x_k\prec y_k. $$
We show that this is a well-ordering.
Property (i)
Suppose
$$ x=(x_1,\ldots,x_n)\prec y=(y_1,\ldots,y_n) $$
and
$$ y=(y_1,\ldots,y_n)\prec z=(z_1,\ldots,z_n). $$
Let $k$ be the first index where $x_k\ne y_k$, and let $\ell$ be the first index where $y_\ell\ne z_\ell$.
Set
$$ m=\min(k,\ell). $$
If $k<\ell$, then for all $j<k$,
$$ x_j=y_j=z_j, $$
and
$$ x_k\prec y_k=z_k. $$
Hence $x\prec z$.
If $\ell<k$, then similarly
$$ x_\ell=y_\ell\prec z_\ell, $$
so again $x\prec z$.
If $k=\ell$, then for all $j<k$,
$$ x_j=y_j=z_j, $$
while
$$ x_k\prec y_k \prec z_k. $$
By transitivity in $S$,
$$ x_k\prec z_k, $$
hence $x\prec z$.
Therefore lexicographic order is transitive.
Property (ii)
Given distinct tuples $x$ and $y$, let $k$ be the first coordinate where they differ. Then exactly one of
$$ x_k\prec y_k \quad\text{or}\quad y_k\prec x_k $$
holds in $S$. Therefore exactly one of
$$ x\prec y \quad\text{or}\quad y\prec x $$
holds.
Property (iii)
Let $A\subseteq T_n$ be nonempty.
Define
$$ A_1={x_1:(x_1,\ldots,x_n)\in A}. $$
Since $A_1$ is nonempty and $S$ is well-ordered, $A_1$ has a least element $a_1$.
Now restrict attention to tuples in $A$ whose first coordinate is $a_1$, and define
$$ A_2={x_2:(a_1,x_2,\ldots,x_n)\in A}. $$
Again $A_2$ is nonempty, so it has a least element $a_2$.
Continue inductively. After $n$ steps we obtain a tuple
$$ (a_1,\ldots,a_n)\in A. $$
We claim this tuple is least in $A$.
Take any
$$ (x_1,\ldots,x_n)\in A. $$
If it differs from $(a_1,\ldots,a_n)$, let $k$ be the first coordinate where they differ. Then
$$ x_j=a_j \quad (j<k), $$
and by construction
$$ a_k\prec x_k. $$
Hence
$$ (a_1,\ldots,a_n)\prec(x_1,\ldots,x_n). $$
Therefore every nonempty subset of $T_n$ has a least element.
Thus lexicographic order is a well-ordering of $T_n$.
∎
(e)
Let
$$ T=\bigcup_{n\ge1}T_n, $$
with the order defined as follows:
For tuples
$$ (x_1,\ldots,x_m),\qquad (y_1,\ldots,y_n), $$
we declare
$$ (x_1,\ldots,x_m)\prec(y_1,\ldots,y_n) $$
if either:
- There exists $k\le\min(m,n)$ such that
$$ x_j=y_j \quad (1\le j<k), $$
and
$$ x_k\prec y_k; $$
or
- $m<n$ and
$$ x_j=y_j \quad (1\le j\le m). $$
Thus a proper initial segment is smaller than the longer tuple extending it.
We show that this is a well-ordering.
Properties (i) and (ii)
The proofs are analogous to part (d). Comparisons are determined either by the first differing coordinate or, if one tuple is an initial segment of the other, by length. The order is therefore transitive and trichotomous.
Property (iii)
Let $A\subseteq T$ be nonempty.
Consider the set of lengths of tuples in $A$:
$$ L={n\ge1:A\cap T_n\ne\varnothing}. $$
Since $L$ is a nonempty set of positive integers, it has a least element $m$.
Now
$$ A\cap T_m $$
is a nonempty subset of $T_m$. By part (d), lexicographic order on $T_m$ is a well-ordering, so there exists a least tuple
$$ a\in A\cap T_m. $$
We claim that $a$ is least in all of $A$.
Take any $b\in A$.
If $b\in T_m$, then since $a$ is least in $A\cap T_m$,
$$ a\preceq b. $$
If $b\in T_n$ with $n>m$, then either:
- $a$ and $b$ first differ at some coordinate $k\le m$, in which case the lexicographic comparison determines that either $a\prec b$ or $b\prec a$; but $b\prec a$ is impossible because $a$ was least among length-$m$ tuples in $A$; or
- the first $m$ coordinates agree, in which case $a$ is a proper initial segment of $b$, so by definition
$$ a\prec b. $$
Thus in every case
$$ a\preceq b. $$
Therefore every nonempty subset of $T$ has a least element. Hence $\prec$ is a well-ordering of $T$.
∎
(f)
We show that $\prec$ is a well-ordering if and only if it satisfies (i) and (ii) and has no infinite descending chain
$$ x_1 \succ x_2 \succ x_3 \succ \cdots. $$
Necessity
Assume $\prec$ is a well-ordering.
Suppose there existed an infinite sequence
$$ x_1,x_2,x_3,\ldots $$
such that
$$ x_{j+1}\prec x_j $$
for all $j$.
Consider the set
$$ A={x_1,x_2,x_3,\ldots}. $$
Since $A$ is nonempty, it has a least element, say $x_k$.
But then
$$ x_{k+1}\prec x_k, $$
contradicting the minimality of $x_k$.
Therefore no infinite descending sequence exists.
Sufficiency
Now assume (i) and (ii), and assume there is no infinite descending sequence.
Suppose, for contradiction, that $\prec$ is not a well-ordering. Then some nonempty subset $A\subseteq S$ has no least element.
Choose $x_1\in A$.
Since $x_1$ is not least in $A$, there exists
$$ x_2\in A $$
such that
$$ x_2\prec x_1. $$
Since $x_2$ is not least, there exists
$$ x_3\in A $$
such that
$$ x_3\prec x_2. $$
Continuing recursively, we obtain
$$ x_1\succ x_2\succ x_3\succ\cdots, $$
an infinite descending sequence, contradicting the hypothesis.
Therefore every nonempty subset has a least element, so $\prec$ is a well-ordering.
∎
(g)
Assume that for every $x\in S$, the truth of
$$ P(y)\quad\text{for all }y\prec x $$
implies the truth of $P(x)$.
We prove that $P(x)$ holds for all $x\in S$.
Suppose not. Let
$$ A={x\in S:P(x)\text{ is false}}. $$
Then $A$ is nonempty.
Since $S$ is well-ordered, $A$ has a least element $a$.
Because $a$ is least in $A$, every element $y\prec a$ satisfies $P(y)$.
By hypothesis, this implies that $P(a)$ is true.
But $a\in A$ means that $P(a)$ is false. This contradiction shows that $A$ must be empty.
Therefore $P(x)$ is true for all $x\in S$.
∎