344 CONSTRUCTION OF NUMBER SYSTEMS Chapter 10
N x N of all ordered pairs of positive integers. Define a relation - on this
set by the rule (m, n) - (p, q) if and only if m + q = n + p. On an intuitive
basis we are identifying any two ordered pairs in which the corresponding
quantities "first component minus second component" are equal, but our
definition is such that only arithmetic in N is involved. Our first task is
to prove Theorem 1.
THEOREM 1- is an equivalence relation on N x N.
Proof (Reflexive) Given m, n E N. Then (m, n) - (m, n) since m + n = n + m.
(Symmetric) Assume (m, n) - (p, q) so that m + q = n + p. The state-
ment (p, q) - (m, n) means p + n = q + m, obviously equivalent to the
assumed property.
(Transitive) Assume (m, n) - (p, q) and (p, q) - (r, s). Then m + q =
n + p and p + s = q + r. To prove (m, n) - (r, s), we must verify m + s
= n + r. Adding the two assumed equations yields (m + q) + (p + s) =
(n + p) + (q + r), which may be rewritten in the form (m + s) + (p + q)
= (n + r) + (p + q). Using additive cancellation in N [recall Theorem
5(d), Article 10.11, we conclude m + s = n + r, as desired.
Denote by Z the set of all equivalence classes induced on N x N by the
equivalence relation -. Note that the elements of Z are of the form [(a, b)],
where (c, d) E [(a, b)] if and only if a + d = b + c. For the sake of your
intuition, we note that [(7,4)] will correspond to the integer 3, [(5,5)] to
0, and [(3,4)] to - 1. We propose now to introduce algebraic structure
on Z by defining operations of addition and multiplication.
DEFINITION 1
Given elements [(m, n)] and [(p, q)] of 2, we define:Several examples should be checked to convince you that the preceding
definitions are reasonable. For instance, the product of [(7,4)] with [(5, 3)]
equals [(35 + 12,20 + 21)] = [(47,41)], corresponding to the fact that the
product of 3 and 2 is 6. Having formulated these definitions of addition
and multiplication of equivalence classes of ordered pairs, we now come
face to face with an issue that will be quite familiar to you by the end of
the chapter, namely, well-dejnedness of an algebraic operation. Suppose
we wish to use Definition l(a) to add two elements of Z, that is, to add two
equivalence classes of ordered pairs of positive integers. According to the
definition of addition, we should choose an arbitrary ordered pair (often
referred to in this context as a representative) from each of the two classes,
add those two ordered pairs by (a) of Definition 1, and then locate the
equivalence class containing the resulting ordered pair. The problem now
is this. Suppose I carry out the procedure just described and arrive at an