378 ANSWERS AND SOLUTIONS TO SELECTED EXERCISES
Article 10.1
- (b) x1 =x; xn= x(9-') ifn > 1.
- (b) Proof Let S = {m~Nlo(m) = 1 + m). Clearly 1 ES, since when m = 1,
then dm) = m + 1 = 1 + 1 = 1 + m. Next, assume p E S SO that 4p) = 1 + p.
We must prove that 4p) = p + 1 E S; that is, (p + 1) + 1 = 1 + (p + 1). But
(p + 1) + 1 = (1 + p) + 1 (by induction hypothesis and well-definedness of
addition) = 1 + (p + 1) (by associativity). - (a) Proof Given a, b, c E N with a + c < b + c. Suppose that a < b is false.
Then, by Theorem 10, we must have b < a or b = a. If b < a, then b + c < a + c,
by Theorem 8(g), whereas if b = a, then b + c = a + c, by the well-definedness
of addition. The conclusion in either of these cases contradicts the hypothesis
a+c<b+c. 0 - (a) Proof Let S be a subset of N satisfying (i) 1 E S and (ii) for all m E N,
if m E S, then m + 1 E S; we claim S = N. For if not, then N - S # 0, and
so, by the well-ordering principle, N - S contains a least element, call it m,.
Now clearly m, > 1, since 1 E S (by (i)) and m, E N - S, so that m, - 1 E N.
Since m, - 1 < m, and m, is the least element of N - S, then m, - 1 E S.
Hence, by (ii), m, = (m, - 1) + 1 E S, contradicting the fact that
EN-S.
Article 10.2
- Proof Assume (a, b) - (a', b') and (c, d) - (c', d'), where all symbols represent
elements of N. To show (ac + bd, ad + bc) - (a'c' + b'd', a'd' + b'c'), we must
prove that ac + bd + a'd' + b'c' = ad + bc + arc' + b'd'. We use the following
two lemmas, whose simple proofs are left to you. Lemma I: If (a, b) - (a', b'),
then a < a' o b < b'. Lemma 2: If (a, b) - (a', b'), and a < a', then
a' - a = b' - b. Assume without loss of generality that c < c', so that d < d'
by Lemma 1. Then ac + bd + a'd' + b'c' = ac + b'c' + a'd' + bd = (a + b')c +
(a' + b)d + b'(cl - c) + al(d' - d) = (a' + b)c + (a + b')d + b'(d' - d) +
al(c' - c) = bc + ad + b'd' + a'c' = ad + bc + arc' + b'd', as desired. The second
equality in the preceding string follows by adding b'c + a'd to both sides and
using additive cancellation [Theorem 5(d), Article 10.11. - (d) Proof Let [(p, q)] and [(r, s)] be elements of Z+, so that p > q and r > s.
We claim that [(p, q)] + [(r, s)] E Z+ and [(p, q)] - [(r, s)] E Z+; that is,
p + r > q + s and pr + qs > ps + qr, respectively. The former is true, by
Exercise 6, Article 10.1. For the latter, we note that pr + qs = ps + qr +
(p - q)(r - s), where (p - q)(r - s) E N, by (b) of the corollary to Theorem 3,
Article 10.1, since p - q E N and r - s E N (because p > q and r > s). Hence,
by Definition 2, Article 10.1, we conclude pr + qs > ps + qr, as desired.
(c) Proof Let x = [(p, q)], y = [(r, s)], and z = [(t, u)]. Then x(y + z) =
[(P, q)] [(r + t, s + 41 = [(Ar + t) + q(s + 4, As + u) + q(r + t))] =
[(pr + 4s) + (pt + qu), (PS + qr) + (PU + qt)] = [(pr + qs, PS + qr)] +
[(pt + qu, pu + qt)] = xy + xz, as desired.
(b) (ii) Proof Given x = [(a, b)], assume x > 0; that is, [(I, I)] < [(a, b)] so
that, by Definition 2, we have 1 + b < 1 + a. By Exercise qa), Article 10.1, we