8 SETS AND RELATIONS [CHAP.

No other ordered pairs belong to V 0 U, that is,

Vo U =-- { (1,5), (1, 6), (3, 7), (4, 7) }

Observe that V 0 U consists precisely of those pairs (x, y) for which there exists, in
the above diagram, a "path" from x E A to y E C composed of two arrows, one fol-
lowing the other.

Example 9.2: Let U and V be the relations in R defined by

U = { (x, y) : x2 + y2 = 1} and V = {(y, z) : 2y 3z = 4}
Then the relation V 0 U, the composition of U and V, can be found by eliminating
y from the two equations x2 + y2 = 1 and 2y + 3z = 4. In other words,
Vo U = f(x, z) : 4x2 9z2 — 24z + 12 = 01

Example 9.3: Let N denote the set of positive integers, and let R denote the relation < in N, i.e.
(a, b) E R if a < b. Hence (a, b) E R -1 iff a> b. Then

R 0 R -1 = { (x, y) : x,y E N; 3 b E N s.t. (x, b) E R -1 , (b, y) E R

= {(x, y) : x,y E N; 3b E N s.t. b < x, b < y }
(N\{1}) X (N\{1}) = {(x,y): x,y E N; x,y 1)
and
R -1 OR = { (x, y) x,y E N; 3b E N s.t. (x, E R, (b,y) E R -1 }
{ (x, y) : x,y E N; 3b E N s.t. b > x, b> y}
NXN

Note that R 0 R -1 R -1 o R.

Solved Problems
SETS, ELEMENTS, SUBSETS
1. Let A = {x: 3x = 61. Does A= 2?
Solution:
A is the set which consists of the single element 2, i.e. A = {2}. The number 2 belongs to A; it
does not equal A. There is a basic difference between an element p and the singleton set { p).

2. Determine which of the following sets are equal: 0, {01, {Q}.

Solution:
Each is different from the other. The set {0} contains one element, the number zero. The set 0
contains no elements; it is the null set. The set {0} also contains one element, the null set.

3. Determine whether or not each of the following sets is the null set:
(i) X = {x: x 2 =9, 2x= 41, (ii) Y = fx : xx1, (iii) Z= {x: x +8 = 81.
Solution:
(1) There is no number which satisfies both x2 = 9 and 2x = 4; hence X = Q.
(11) We assume that any object is itself, so Y is empty. In fact, some texts define the null set by
—= {x : x x } .
(iii) The number zero satisfies x -I- 8 = 8; hence Z = {0}. Accordingly, Z Q.

4. Prove that A {2,3,4,5 } is not a subset of B fx:x is even).

Solution:
It is necessary to show that at least one member of A does not belong to B. Since 3 E A and
3 B, A is not a subset of B.
CHAP. 1] SETS AND RELATIONS 9

5. Prove Theorem 1.1 (iii): If AcB and BcC then ACC.

Solution:
We must show that each element in A also belongs to C. Let x E A. Now A cB implies x E B.
But BcC, so x E C. We have therefore shown that x E A implies x E C, or ACC.

6. Prove: If A is a subset of the null set Q, then A= Q.

Solution:
The null set 0 is a subset of every set: in particular, (/) cA. But, by hypothesis, A 46; hence,
by Definition 1.1, A=0.

7. Find the power set P(S) of the set S {1,2,31.

Solution:
Recall that the power set 41)(S) of S is the class of all subsets of S. The subsets of S are
{1, 2, 3 } , {1, 2), {1, 3 } , {2, 3), 111, {2 } , {3} and the empty set V). Hence
P(S) = IS, {1,31, {2, 3), {1, 2), {1}, {2 } , {3},

Note that there are 23 =--- 8 subsets of S.

8. Find the power set P(S) of S = (3, (1,41).

Solution:
Note first that S contains two elements, 3 and the set (1, 4). Therefore `1)(S) contains 22 = 4
elements: S itself, the empty set (6, the singleton set {3} containing 3 and the singleton set {{1, 4))
containing the set {1, 4 } . In other words,
'KS) = KS, 01, (0,411, 0)

SET OPERATIONS
9. Let U = {1, 2, . ., 8, 91, A = {1, 2, 3, 4 } , B = {2, 4, 6, 8 } and C = {3, 4, 5, 6 } .
Find: (i) Ac, (ii) (A n C )c , (iii) B \C , (iv) (Au By .
Solution:
(I) Ac consists of the elements in U that are not in A; hence Ac = {5, 6, 7, 8, 9).

(ii) A nC consists of the elements in both A and C; hence

A nc = {3,4} and (A n c)c = {1, 2, 5, 6, 7, 8, 9 }
(iii) B\C consists of the elements in B which are not in C; hence B\C = {2, 8).
(iv) A UB consists of the elements in A or B (or both); hence
AUB = {1, 2, 3, 4, 6, 8 } and (AuB) = 9}

10. Prove-. (A \B) n B =

Solution: (A \B)nB {x: x E B, x E A\B}
{x: x E B, x E A, x B}
since there is no element x satisfying x E B and x B.

11. Prove De Morgan's Law: (A u B)c = Ac n Bc.

Solution: (AuB)c {x e Au B}
= {x : x A, x B}
= {x: x E Ac, x E Bc} AenBc

12. Prove: B \ A = B n Ac.

Solution: B \A {x x E B, x A} = {x x E B, x E Ac) = BnAc
10 SETS AND RELATIONS [CHAP. 1

13. Prove the Distributive Law: A n (B UC) = (An B) U (A n C).

Solution: An(BuC) : x E A; xEBuC}
x E A; x E B or x E C}
{x x E A, xE B; or x E A, x E C}
{x xEAnB or xEAnC}
(A nB) u (AnC)
Observe that in the third step above we used the analogous logical law
p A (q v r) = (p q)v (p A r)
where A reads "and" and y reads "or".

14. Prove: For any sets A and B, A nBcA cA uB.

Solution:
Let x E AnB; then xEA and xEB. In particular, xEA. Accordingly, AnBcA. If xEA,
then x E A or x E B, i.e. x E AuB. Hence A cA u B. In other words, AnBcA c A u B.

15. Prove Theorem 1.3 (i): A cB if and only if A nB = A.

Solution:
Suppose A cB. Let x E A; then by hypothesis, x E B. Hence x E A and x E B, i.e. x E A nB.
Accordingly, A cA nB. But by the previous problem, A nB cA. Hence AnB = A.
On the other hand, suppose A nB = A. Then in particular, A cA n B. But, by the previous
problem, A nB cB. Hence, by Theorem 1.1, A c B.

PRODUCT SETS, RELATIONS, COMPOSITION OF RELATIONS

16. Let A= {a, b}, B= (2,31 and C = {3,4 }. Find: (1) A x (B U C), (ii) (A x B)U (A x C).
Solution:
(i) First compute BUG = {2, 3, 4 } . Then
A x (B u C) = (a, 2), (a, 3), (a, 4), (b, 2), (b, 3), (b, 4)1

(ii) First find A x B and A x C:

A x B = { (a, 2), (a, 3), (b, 2), (b, 3) 1, A X C = { (a, 3), (a, 4), (b, 3), (b, 4) 1
Then compute the union of the two sets:
(A X B)u (A X C) { (a, 2), (a, 3), (b, 2), (b, 3), (a, 4), (b, 4) 1
Observe, from (i) and (ii), that A x (B u C) = (A X B) u (A X C).

17. Prove: A x (B nC) = (A X B) n (A x C).

Solution: A x (B n C) = {(x,y): x EA, yEBnC}
• {(x, y) : xEA,yEB,yEC1
• { (x, : (x, y) E Ax B, (x, y) EA xC}
• (A x B) n (A x C)

18. Let R be the relation < from A = {1,2,3,4} to 5 • • • •

B = {1, 3, 5}, i.e., (a, e R iff a < b.
(i) Write R as a set of ordered pairs. 3 • •
(ii) Plot R on a coordinate diagram of A x B.
(iii) Find domain of R, range of R and R -1 . A
(iv) Find R 0R -1 . 2 4
CHAP. 1] SETS AND RELATIONS 11

Solution:
R consists of those ordered pairs (a, b) E A XB such that a < b; hence
R (1,5), (2, 3), (2, 5), (3, 5), (4, 5) 1
(ii) R is displayed on the coordinate diagram of A x B as shown above.
(iii) The domain of R is the set of first coordinates of the pairs in R; hence domain of R = {1, 2, 3, 41.
The range of R is the set of second coordinates of the pairs in R; hence range of R = 0,51.
R ' can be obtained from R by reversing the pairs in R; hence
R -1 = { (3, 1), (5, 1), (3, 2), (5, 2), (5, 3), (5,4) }
(iv) To find R0R -1 , construct diagrams of R -1 and R as shown below. Observe that R -1 , the
second factor in the product R 0R 1 , is constructed first. Then

R R -1 = { (3, 3), ( 3, 5 ), (5 , 3), (5, 5 ) }

19. Let T be the relation in the set of real numbers R defined by

xT y if both x rn,n +11 and y G [n, n +11 for some integer n
Graph the relation T.
Solution:
T consists of the shaded squares below.
3 -

2-

- 3 -2 -

20. Let T be the relation in the set of real numbers R defined by xTy if 0 x-y 1.
(i) Express T and T -1 as subsets of R x R and graph.'
(ii) Show that T 0T -1 = {(x, z) -
Solution:
(i) T = {(x,y): x,y E R, 0 x - y 1}
T-1 = ( (x, y) : (y, E T } = ((x, y) : x,y E R, 0 y - x 1}
The relations T and T -1 are graphed below,
-2 4,4.

I I
1 2

--2

Graph of T Graph of T - 1
12 SETS AND' RELATIONS [CHAP. 1

(ii) By definition of composition of relations,

T T -1 = { (x, z) : 3y E R s.t. (x, y) E T -1 , ( y, z) E T
(x, z) : 3y E R s.t. (y, x), (y, z) E
{(x,z): 3yER s.t. 0=y - x=1, 0=y-z=1}
Let S = { (x, z) : lx - = 1). We want to show that T T -1 = S.
Let (x, z) belong to T o T -1 . Then 3y s.t. 0 y- x, y - z 1. But
0 =yœx, y-z=1 y-z=1
• y-z
• x- z=1

Also, 0 y - x, y - z = 1 y-x=1
• y-x=1-1-y- z
• -1 -= x - z
In other words, 0 = y - x, y - z = 1 -1 = x - z = 1 if x - zi -‹ 1
Accordingly, (x, z) E S, i.e. To T -1 C S.

Now let (x, z) belong to S; then Ix - zi -= 1.

Let y = max (x, z); then 0=y-x ,<1 and 0 y - z 1.
Thus (x, z) also belongs to To T -1 , i.e. Sc To T -1 . Hence TOT - ' =- S.

21. Prove: For any two relations R cXx Y and ScYx Z, (S R) --1 = R -1 0S -- '.
Solution: (SoR) -1 = {(z,x): (x,z)E SoR)
= (z, x): 3y E Y s.t. (x, y) E R, (y, z) E S)
(z, : 3y E Y s.t. (z, y) E S -1 , (y, x) E R -1 }
= R-1 0 S -1

22. Prove: For any three relations RcWxX, ScXxY and Tc YxZ, (ToS)0.1? =
To (S o R).
Solution: (T 0 S) OR { (w, : 3x E X s.t. (w, x) E R, (x, z)E TOS}
• { (tv, 3x E X, 3y E Y s.t. x) E R, (x, y) E S, (y, z) E T }
• (w, : ay E Y s.t. (w, y) E S o R, (y, E T1
To(SoR)

REFLEXIVE, SYMMETRIC, TRANSITIVE AND EQUIVALENCE RELATIONS

23. Prove: Let R be a relation in A, i.e. RcAx A. Then:
(i) R is reflexive if AA C R;
(ii) R is symmetric if R -= R -1 ;
(iii)R is transitive iff R oR c R;
(iv) R reflexive implies R oR D R and R 0 R is reflexive;
(v.) R symmetric implies R 0 R -1 = R -1 R;
(vi) R transitive implies R 0 R is transitive.
Solution:
(i) Recall that the diagonal AA = {(a, : a E A}. Now R is reflexive if, for every a E A,
(a, a) E R if AA C R.
(ii) Follows directly from the definition of R -1 and symmetric.
(iii) Let (a, e) E R 0 R; then 3 b E A such that (a, b) E R and (b, e) E R. But, by transitivity,
(a, b), (b, E R implies (a, OE R. Consequently, RoR c R.
On the other hand, suppose RoRcR. If (a, b),(b,c)ER, then (a, e) ER0R c R. In
other words, R is transitive.
CHAP. 11 SETS AND RELATIONS 13

(iv) Let (a, b) E R. Now, R 0R = { (a, c) : 3b E A s.t. (a, b) E R, (b, e) E R).

But (a, b)ER and, since R is reflexive, (b,b)ER. Thus (a, b)ER0R, i.e. R cRoR.
Furthermore, A A CR c R oR implies R o R is also reflexive.

(y) R R -1 { (a, c) : 3b E A s.t. (a, b) E R -1 , (b, E R)

{ (a, : 3b E A s.t. (a, b) E R, (b, e) E R -1 }
= R -1 0 R

(vi) Let (a,b), (b,c) E R 0 R. By (iii), R oR c R; hence (a,b), (b,c) E R. So (a, c) E R 0 R, i.e. R 0 R is
transitive.

24. Consider the relation R = (1,1), (2,3), (3,2)} in X = {1,2,31. Determine whether
or not R is (1) reflexive, (ii) symmetric, (iii) transitive.
Solution:
(i) R is not reflexive since 2 E X but (2, 2) E R.
(ii) R is symmetric since R -1 = R.
(iii) R is not transitive since (3, 2) E R and (2, 3) E R but (3, 3) E R.

25. Consider the set N x N, i.e. the set of ordered pairs of positive integers. Let R be the
relation = in N x N which is defined by
(a, b) (c, d) if ad = be
Prove that R is an equivalence relation.
Solution:
Note that, for every (a, b) E N X N, (a, b) (a, b) since ab = ba; hence R is reflexive.
Suppose (a, h) (c, d). Then ad be, which implies cb da. Hence (c, d) (a, b) and, therefore
R is symmetric.
Now suppose (a, h) (c, d) and (c, d)_^,z (e, f). Then ad = be and cf--=--- de. Thus
(ad)(cf) = (bc)(de)
and, by cancelling from both sides, af =- be. Accordingly, (a, h) (e, f) and R is transitive.
Since R is reflexive, symmetric and transitive, R is an equivalence relation.
a
Observe that if the ordered pair (a, b) is written as a fraction then the above relation R is,
a c
usual definition of the equality of two fractions, i.e. -b- = infact,he ad = be.
if

26. Prove Theorem 1.4: Let R be an equivalence relation in A and let [a] be the equivalence
class of a e A. Then:
(1) For every a E A, a E raj.
(ii) [a] = [b] if and only if (a, b) E R. ,

(iii) If [a] [b], then [a] and [b] are disjoint.

Solution:
Proof of (i). Since R is reflexive, (a, a) E R for every a E A and therefore a E [a].
Proof of (ii). Suppose (a, b) E R. We want to show that [a] [b]. Let x E [b]; then
(b, x) E R. But by hypothesis, (a, b) E R; hence by transitivity, (a, x) E R. Accordingly, x E [a],
i.e. [b] c [a]. To prove that [a] c [b], we observe that (a, b) E R implies, by symmetry, that
(b, a) E R. Then by a similar argument, we get [a] c [b]. So [a] = [b].
On the other hand, if [a] [b], then by reflexivity, b E [h] = [a], i.e. (a, b) E R.
Proof of (iii). We prove the equivalent contrapositive statement, i.e. if [a] n [b] 0, then
[a] = [b]. If Fain [b] 0, there exists an element x E A with x E [a] n [b]. Hence (a, x) E
and (b, x) E R. By symmetry, (x, b) E R and, by transitivity, (a, h) E R. Consequently by (ii),
[a] = [b].
14 SETS AND RELATIONS [CHAP. 1

Supplementary Problems
SETS, ELEMENTS, SUBSETS
27. Determine which of the following sets is the empty set:
(i) {x:1<x< 2, xER} (iii) {x : x E
(ii) { x : 1 < x < 2, x E N } (iv) {x : x 2 < x, x E

28. Let A = {1, 2, ..., 8, 9 } , B = {2, 4, 6, 81, C = {1, 3, 5, 7, 9 } , D = {3, 4, 5} and E = {3, 5 } . Which
of these sets can equal X if we are given the following information?
(i) X and B are disjoint, (ii) XcD and X03, (iii) XcA and X4C, (iv) X c C and 2CA.

29. State whether each of the following statements is true or false.

(i) Every subset of a finite set is finite. (ii) Every subset of an infinite set is infinite.

30. Discuss all inclusions and membership relations among the following three sets: (6, {0}, {0, {0}}.

31. Prove that the closed interval [a, b] is not a subset of the open interval (a, b).

32. Find the power set "P(U) of U =--- 21 and the power set P(V) of V = {0, { 1 , 2 } 1-

33. State whether each of the following is true or false. Here S is any non-empty set and 2s is the
power set of S.
(i) S E 2s (ii) S c 2s (iii) {S} E 2s (iv) {S} c 2s

SET OPERATIONS
34. Let A = {1, 2, 3, {1, 2, 3 } ), B = {1,2, {1, 2 } ). Find: A uB, A nB, A \ B, B \A.

35. In each of the Venn diagrams below shade: (i) A n (B u C), (ii) C\ (A nB).

(a) (b)

36. Prove and show by Venn diagrams: /lc \Be = B A.

37. (i) Prove A n (B\C) = (A n B)\ (A n C).

(ii) Give an example to show that A u (B \C) (A u B)\ (A u C).

38. prove: 24c 213 2A n B ; 2A U2B C2AUB. Give an example to show that 2A u 2B 2A UB.

39. Prove Theorem 1.3: Each of the following conditions is equivalent to A cB:
(i) A nB = A, (ii) Au B = B, (iii) Be cile, (iv) A nBe =Ø, (y) B uAc U
(Note. A nB = A was already proven equivalent to A cB in Problem 15.)

40. Prove that A cB iff (B n C)u A = B n (Cu A) for any C.

PRODUCT SETS, RELATIONS, COMPOSITION OF RELATIONS

41. Prove: A x (BuC) = (A x B)u (A X C).

42. Using the definition of ordered pair, i.e. (a, b) = {{a}, {a, b1), prove that (a, b) = (e, d) if
a= e and b= d.

43. Determine the number of distinct relations from a set with m elements to a set with n elements,
where m and n are positive integers.
CHAP. 11 SETS AND RELATIONS 15

44. Let R be the relation in the positive integers N defined by

R = { (x, : x,y E N, x 2y = 12 }
(i) Write R as a set of ordered pairs. (ii) Find domain of R, range of R and R -1 . (iii) Find RoR.
(iv) Find 1? -1 0 R.

45. Consider the relation R 1 (4, 5), (1, 4), (4, 6), (7, 6), (3, 7) in N.
(i) Find domain of R, range of R and R -1 . (ii) Find R 0 R. (iii) Find R -1 0R.

46. Let U and V be the relations in R defined by U = {(x, y) : x 2 + 2y = 5) and V = {(x, y) : 2x — y = 3).
(i) Find Vo U. (ii) Find U o V.

47. Consider the relations < and in R. Show that < u A = where A is the diagonal.

EQUIVALENCE RELATIONS
48. State whether each of the following statements is true or false. Assume R and S are (non-empty)
relations in a set A.
(1) If R is symmetric, then R -1 is symmetric.
(2) If R is reflexive, then RnR -1 Ç.
(3) If R is symmetric, then RnR -1
(4) If R and S are transitive, then RuS is transitive.
(5) If R and S are transitive, then RnS is transitive.
(6) If R and S are symmetric, then RuS is symmetric.
(7) If R and S are symmetric, then RnS is symmetric.
(8) If R and S are reflexive, then R nS is reflexive.

49. Consider N X N, the set of ordered pairs of positive integers. Let be the relation in N X N defined by
(a, b) (c,d) if a + d = b c
(i) Prove = is an equivalence relation. (ii) Find the equivalence class of (2, 5), i.e. [(2,

50. Let — be the relation in R defined by x — y if x — y is an integer. Prove that — is an equivalence

relation.

51. Let — be the relation in the Cartesian plane R2 defined by (x, y (w, z) if x = W.
Prove that — is an equivalence relation and graph several equivalence classes.

52. Let a and b be arbitrary real numbers. Furthermore, let — be the relation in R2 defined by
(x, — (w z) if 3k E Z s.t. x — w = ka, y — z = kb
,

Prove that — is an equivalence relation and graph several equivalence classes.

Answers to Supplementary Problems

27. The sets in (ii) and (iii) are empty.

31. a G [a, b] but a 4 (a, b).

32. 'P(V) = (V, (0), {(1, 2)), 01

33. (i) T, (ii) F, (iii) F, (iv) T

34. AuB = (1, 2, 3, {1, 2 } , { 1, 2, 3 } 1, AnB = { 1, 2 } , A\B = (3, {1, 2, 33, B\A = ((1, 2 ) ).
16 SETS AND RELATIONS [CHAP. 1

35.

(i )

37. (ii) C = 0, A= B

38. Example: A = {1 } , B = ( 2)

43. 2inn

(i) R { ( 1 0, 1), (8, 2), (6, 3), (4, 4), (2,5) }

(ii) domain of R = {10, 8, 6, 4, 21, range of R = {1, 2, 3, 4, 5 } ,
R -' { (1, 10), (2, 8), (3, 6), (4, 4), (5, 2)
(iii) R oR { (8, 5), (4,4) }
(iv) R -1 0 R = (10, 10), (8, 8), (6„6), (4, 4), (2, 2) )

45. (i) domain of R = {4, 1, 7, 3}, range of R = {5, 4, 6, 7}, R -1 = { (5, 4), (4, 1), (6, 4), (6, 7), (7, 3) )
(ii) R 0 R = { (1, 5), (1, 6), (3, 6) 1
(iii) R -1 OR = { (4, 4), (1, 1), (4, 7), (7, 4), (7, 7), (3, 3) }
46. V 0 U = (x, y) : x2 + y = 2 1, U o V = (x, y) : 4x 2 - 12x + 2y + 4 = 0 1

48. (1) T, (2) T, (3) T, (4) F, (5) T, (6) T, (7) T, (8) T

49. (ii) [(2, 5)] = (1, 4), (2, 5), (3, 6), (4, 7), (n, n 3), .}

51.

The equivalence classes are the vertical lines.

52.
• •
• •
•
• • •
a

•
• •
The above gives a typical equivalence class. The distance between adjacent horizontal points is a and
the distance between adjacent vertical points is b.