340 CONSTRUCTION OF NUMBER SYSTEMS Chapter 10
Partial proof We prove (b), with the others for you to verify in Exercise
5(b). To prove that (c - b) + a = c - (b - a), we need only show that
(c - b) + a added to b - a yields c. Note that [(c - b) + a] + (b - a)
= (C - b) + [a + (b - a)] = (c - b) + b = b + (c - b) = c, as desired.
0
We conclude our discussion of the "less than" relation on N by proving
the important trichotomy property.
THEOREM 10
Given a, b E N, exactly one of the three statements a < b, a = b, and a > b is true.Proof Given EN, let Sa= {b~Nleither a<b or a=b or a>bJ. We
first show that S, = N by induction; then we show that at most one of the
three relationships holds for any pair of positive integers. For the induc-
tion proof, note first that 1 E S, since if a # 1, then a = a(x) = 1 + x
for some x E N, so that 1 < a. Second, assume b E S, so that either a < b
or a = b or a > b. We must prove that a(b) E S,; that is, either a < o(b),
a = ~(b), or a > a(b). Now if a < b, then since b < a(b), we have (by the
transitivity of <) that a < a(b). If a = b, then since b < ~(b), we have
a < a(b). If a > b, then either a = o(b) or a # ~(b). In the first case the
desired result follows immediately. If a # a(b), then a = b + x for some
x E N, x # 1. Since x # 1, then x = a(y) for some y E N. Hence a =
b + x = b + a(y) = a(b + y) = a(b) + y so that a(b) < a. Thus S, = N
and we may be certain that at least one of the three relationships must
be true for any a, b E N. We next show that at most one of the relation-
ships may hold between a given a and b. Note first that if either a < b
or b < a, then a # b, by Theorem 8(d). Thus we have only the possibility
"a < b and b < a" to eliminate. If both relationships hold, then there
exist x, y E N such that a = b + x and b = a + y. Hence a = b + x =
(a + y) + x = a + (y + x) = a + z, where z = x + y E N, by closure.
This contradicts (c) of Theorem 5. 0WELL-ORDERING OF N
In (e) of Theorem 8 we observed informally that 1 is the smallest element
of N [see Exercise 7(g)]. 1n fact, N satisfies a stronger property involving
the idea of a smallest element, the well-ordering principle. Note first that
if S c N, an element a E N is said to be a smallest (or least) element of S
if and only if a E S and, for all x E N, x E S implies either a = x or a < x.
The well-ordering principle (WOP) for N states that every nonempty subset
of N has a least element. This property is an extremely useful theoretical
tool for proving existence; you may recall, for instance, Example 10, Article
6.3. It turns out that WOP is equivalent to the induction postulate. We