Bridge to Abstract Mathematics: Mathematical Proof and Structures

10.1 AN AXlOMATlZATlON FOR THE SYSTEM OF POSITIVE INTEGERS 337

Partial proof (a) Given n, p E N, denote by S,, the set (q E Nl(n + p) +
q = n + (p + q)]. It is left to you [Exercise 2(a)] to verify conditions (I)
and (11) of the induction postulate and conclude thereby that S,, = N.
(b) This proof is more difficult than the proof of associativity. Recall
that o(m) = m + 1 for all m E N, by (1). We need as a lemma the fact the
a(m) = 1 + m for any m E N; note that this is a special case of the desired
result. Assuming that you have supplied the straightforward induction
verification [Exercise 2(b)], we approach the desired result by using
another induction. For n E N, let Sn = (p E Nl n + p = p + n). Using
this lemma, we observe that 1 E S,, since n + 1 = a(n) = 1 + n. For (11),
assume p E S,, SO that n + p = p + n. We must prove o(p) = p + 1 E S,;
that is, n + (p + 1) = (p + 1) + n. Now

n + (p + 1) = (n + p) + 1 [by (211

= (p + n) + 1 (by induction hypothesis and well-

definedness (wd) of " + ")

= P + (n + 1) [by (211

= p + (1 + n) (by the lemma)

= (P + 1) + n [by (211

(c) Given p E N, let S, = (n E ~ln + p # n). Note first that^1 E S,,

since 1 + p = o(p) # 1, since 1 # im (a). Next, assume n E S,, so that

n + p # n. To show a(n) = n + 1 E S,, we must prove that (n + 1) +

p # n + 1; that is, o(n) + p # ~(n). Now if o(n) + p = o(n), then we

would have o(n) = o(n) + p = o(n + p) and, by the one-to-one property

of o, n = n + p, a contradiction.

(d) Given n,p~N, let Sn! = (q~Nln + q =P + q implies n =p}.

Note first that 1 E Snp since if n + 1 = p + 1, then o(n) = o(p) so that

n = p, by the one-to-oneness of cr. Now suppose q E S,,, so that n = p

whenever n + q = p + q. To show o(q) = q + 1 E S,,, assume that

n + (q + 1) = p + (q + 1). We must show that n = p. In that case

we have (n + q) + 1 = n + (q + 1) = p d- (q + 1) = (p + q) + 1, so that

o(n + q) = a(p + q). By the one-to-one property oflo, we have n + q =

p + q. By the induction hypothesis, we conclude n = p, as desired. 0

Property (d) of Theorem 5 might be called "right-additive" cancellation.

Note that combining (d) with (b), the commutative pr~perty of addition,

yields easily a corresponding "left-additive" cancellation property [see Ex-

ercise 2(c)],

Our next goal is to begin to consider algebraic properties involving

multiplication. We begin by giving a proof of the only field property that

involves addition and multiplication together.

THEOREM 6

Let n, p, q E N. Then n(p + q) = np + nq. (distributivity)