ANSWERS AND SOLUTIONS TO SELECTED EXERCISES 373R = R-l. To prove R is symmetric, let (x, y) E R. Then (y, x) E R-' = R, so
(y, x) E R, as desired. 0- (c) [I] = {1,3), [2] = (2,3), [3] = (1,Z 31, [4] = (51, [5] = (4).
Article 7.2
- (b) S, is an equivalence relation. It is reflexive since everyone has the same
biological parents as himself or herself. It is symmetric: If x and y have the
same biological parents, so do y and x. It is transitive, for if x and y have the
same biological parents and y and z have the same biological parents, then
x and z have the same biological parents.
4.(a)(i)q=4,r=l (iu)q=-4,r=3 (c)Form1=13andd=5,we
have q, = 2 and r, = 3. For m, = - 17, d = 5, we have q2 = -4 and r2 = 3.
Note that r, = 3 = r,, not unexpected since m, and m, are congruent modulo
5 in this case. For m, = 8 and d = 5, we have 4, = 1 and r, = 3. For
m2 = -3, d = 5, we have 4, = - 1 and r, = 2. Note that r, = 3, r, = 2, so
r, # r,, as we expect in this case, since this m, and m, are not congruent
modulo 5. - Proof (Reflexive) Let m, n E Q, with n # 0. Clearly (m, n) - (m, n), since
mn = nm. (Symmetric) Let m, n, p, q E Q, with n # 0 and q # 0, and assume
(m, n) - (p, q), SO that mq = np. To prove (p, q) - (111) n), we need only show
pn = qm, clearly true since pn = np = mq = qm, using commutativity.
(Transitive) Assume m, n, p, q, r, s E Q, with n # 0, q # 0, s # 0, with
(m, n) - (p, q) and (p, q) - (r, s). To prove (m, n) - (r, s), we must prove
ms = nr. By our assumptions, we have mq = np and ps = qr. Multiplying
the first equation by s and the second by n, we get mqs = nps = nqr, so that
msq = nrq. Since q # 0, we may cancel it to get ms = nr, as required. - (d) Ordered pair example for (R, NS, NT): Let S = (1,2,3), R, =
{(1,1), (2921, (3,3), (1, a, (2,3), (3,219 (1931, (391)). Rl is clearly (R, NS) and is
also (NT) since (2, 3) E R, and (3, 1) E R,, but (2, 1) & R,. Rule example for
(R, NS, N T): Let S = R - (0) and R, = ((x, y) ( y # 2x1. Now R, is reflexive
since x E S implies x # 0 so that x # 2x. R, is not symmetric since (6,3) E R,,
but (3,6) 4 R,. Finally, R, is not transitive, because (6,3) E R, and (3, 12) E R,,
but (6, 12) & R,. - (a) (0) NR, S, NT
Article 7.3
- <c) A/& = ({a, b), (G e), (d,f))
- (b) Al92 = {(a, 4 (b, b), (c, c), (4 4, (e, 4, (f, f ), (c, 4, (4 4, (c, f 1, (f 4,
(d, f ), (f 9 4)- - (b) S = ((odd integers), {even integers)), a two-celled partition of Z.
(j) The partition has infinitely many cells. The cell containing a function
y = f(x) contains precisely those functions whose functional values differ from
those off at only a finite number of points.