Let A be the set of points in the rectangle with x and y

Problem 47E Refer to the quote at the beginning of this section to answer the following questions. a. What is the name of the Knight’s song called? ________________ b. What is the name of the Knight’s song? ________________ c. What is the Knight’s song called? ________________ d. What is the Knight’s song? ________________ e. What is your (full, legal) name? ________________ f. What are you called? ________________ g. What are you? (Do not answer this on paper; just think about it.)

Problem 2E Each of the following partitions of {0, 1, 2, 3, 4} induces a relation R on {0, 1, 2, 3, 4}. In each case, find the ordered pairs in R. a. {0, 2}, {1}, {3, 4} ________________ b. {0}, {1,3, 4}, {2} ________________ c. {0}, {1, 2, 3, 4}

Problem 3E The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. Exercise A = {0, 1, 2, 3, 4} R = {(0, 0), (0, 4), (1, 1), (1, 3), (2, 2), (3, 1), (3, 3),(4, 0), (4, 4)}

Problem 4E The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. Exercise A = {a, b, c, d} R = {(a, a), (b, b), (b, d), (c, c), (d, b), (d, d)}

Problem 5E The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. Exercise A = {1, 2, 3, 4, ..., 20}. R is defined on A as follows: For all x, y ? A, x R y? 4 | (x – y).

Problem 1E Suppose that S = {a, b, c, d, e} and R is a relation on S such that a R b, b R c, and d R e. List all of the following that must be true if R is (a) reflexive (but not symmetric or transitive), (b) symmetric (but not reflexive or transitive), (c) transitive (but not reflexive or symmetric), and (d) an equivalence relation. cRb cRc aRc bRa aRd eRa eRd cRa

Problem 6E The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. Exercise A = {–4, –3, –2, –1, 0, 1, 2, 3, 4, 5}. R is defined on A as follows: For all x, y e A, x R y ? 3 | (x – y).

Problem 7E The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. Exercise A = {(1,3), (2, 4), (–4, –8), (3, 9), (1, 5), (3, 6)}. R is defined on A as follows: For all (a, b), (c, d) ? A, (a, b) R (c, d) ? ad = bc.

Problem 9E The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. Exercise X = { – 1, 0, 1} and A = R is defined on as follows: For all sets s and t in s R t ? the sum of the elements in s equals the sum of the elements in t.

Problem 8E The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. Exercise X = {a, b, c} and A = R is defined on A as follows: For all sets u and v in P(X), u R v ? N (u) = N (v). (That is, the number of elements in u equals the number of elements in v.)

Problem 10E The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. Exercise A = {–5, –4, –3, –2, –1,0, 1, 2, 3, 4, 5}. R is defined on A as follows: For all m, n ? Z, m R n ? 3 | (m2 –n2).

Problem 12E The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. Exercise A = {–4, –3, –2, –1, 0, 1, 2, 3, 4}. R is defined on A as follows: For all (m, n) ? A, m R n ? 5 | (m2 – n2).

Problem 13E In each of 3–14, the relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. A is the set of all strings of length 4 in a’s and b’s. R is defined on A as follows: For all strings s and t in A, s R t ? s has the same first two characters as t.

Problem 11E The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. Exercise A = {–4, –3, –2, –1, 0, 1, 2, 3, 4}. R is defined on A as follows: For all (m, n) ? A, m R n ? 4 | (m2 – n2).

Problem 14E In each of 3–14, the relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. A is the set of all strings of length 2 in 0’s, 1’s, and 2’s. R is defined on A as follows: For all strings s and t in A, s R t ? the sum of the characters in s equals the sum of the characters in t.

Problem 15E Determine which of the following congruence relations are true and which are false. a. 17 = 2 (mod 5) ________________ b. 4 = –5 (mod 7) ________________ c. –2 = –8 (mod 3) ________________ d. –6 = 22 (mod 2)

Problem 16E a. Let R be the relation of congruence modulo 3. Which of the following equivalence classes are equal? [7], [–4], [–6], [17], [4], [27], [19] ________________ b. Let R be the relation of congruence modulo 7. Which of the following equivalence classes are equal? [35], [3], [–7], [12], [0], [–2], [17]

Problem 17E a. Prove that for all integers m and n, m = n (mod 3) if, and only if, m mod 3 = n mod 3. b. Prove that for all integers m and n and any positive integer d, m = n (mod d) if, and only if, m mod d = nmodd.

Problem 18E a. Give an example of two sets that are distinct but not disjoint. b. Find sets A1 and A2 and elements x, y and z such that x and y are in A1 and y and z are in A2 but x and z are not both in either of the sets A1 or A2.

Problem 20E (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Exercise E is the relation defined on Z as follows: For all m, n ? Z, mEn ^ 2 | (m -n).

Problem 19E (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Exercise A is the set of all students at your college. a. R is the relation defined on A as follows: For all x and y in A , x R y ? x has the same major (or double major) as y. (Assume “undeclared” is a major.) ________________ b. S is the relation defined on A as follows: For all x, y ? A, x S y ? x is the same age as y.

Problem 21E (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Exercise F is the relation defined on Z as follows: For all m, n ? Z, mFn ? 4 | (m –n).

Problem 23E In 19?31, (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Let P be a set of parts shipped to a company from various suppliers. S is the relation defined on P as follows: For all x, y ? P, x S y ? x has the same part number and is shipped from the same supplier as y.

Problem 22E (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Exercise Let A be the set of all statement forms in three variables p, q, and r. R is the relation defined on A as follows: For all p and q in A, p R q ? p and q have the same truth table.

Problem 24E In 19–31, (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Let A be the set of identifiers in a computer program. It is common for identifiers to be used for only a short part of the execution time of a program and not to be used again to execute other parts of the program. In such cases, arranging for identifiers to share memory locations makes efficient use of a computer’s memory capacity. Define a relation R on A as follows: For all identifiers x and y, x R y ? the values of x and y are stored in the same memory location during execution of the program.

Problem 25E (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Exercise A is the “absolute value” relation defined on R as follows: For all x, y ? R, x Ay ? |x | = |y|.

Problem 27E (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Exercise R is the relation defined on Z as follows: For all (m, n) ? Z, m R n ? 4| (m2 –n2).

Problem 26E (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Exercise D is the relation defined on Z as follows: For all m, n ? Z, m D n ? 3 | (m2 –n2).

Problem 28E (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Exercise I is the relation defined on R as follows: For all x, y ? R, x I y ? x –y is an integer.

Problem 31E (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Exercise Let P be the set of all points in the Cartesian plane except the origin. R is the relation defined on P as follows: For all p1 and p2 in P, p1 R p2 ? p1 and p2 lie on the same half-line emanating from the origin.

Problem 30E (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Exercise Define Q on the set R × R as follows: For all (w, x), (y, z) ? R × R, (w, x) Q (y, z) ? x = z.

Problem 29E (1) prove that the relation is an equivalence relation, and (2) describe the distinct equivalence classes of each relation. Exercise Define P on the set R × R of ordered pairs of real numbers as follows: For all (w, x), (y, z) ? R × R, (w, x) P (y, z) ? w = y.

Problem 32E Let A be the set of all straight lines in the Cartesian plane. Define a relation || on A as follows: For all l1 and l2 in A, l1 || l2 ? l1 is parallel to l2. Then || is an equivalence relation on A. Describe the equivalence classes of this relation.

Problem 33E Let A be the set of points in the rectangle with x and y coordinates between 0 and 1. That is, A = {(x, y) ? R ×R | 0 ? x ?1 and 0? y ? 1}. Define a relation R on A as follows: For all (x1, y1) and (x2, y2) in A, (x1, y1) R (x2, y2) ? (x1, y1) = (x2, y2); or x1 = 0 and x2 = 1 and y1 = y2; or x1 = 1 and x2 = 0 and y1 = y2; or y1 = 0 and y2 = 1 and x1 = x2; or y1 = 1 and y2 = 0 and x1 = x2. In other words, all points along the top edge of the rectangle are related to the points along the bottom edge directly beneath them, and all points directly opposite each other along the left and right edges are related to each other. The points in the interior of the rectangle are not related to anything other than themselves. Then R is an equivalence relation on A. Imagine gluing together all the points that are in the same equivalence class. Describe the resulting figure.

Problem 34E The documentation for the computer language Java recommends that when an “equals method” is defined for an object, it be an equivalence relation. That is, if R is defined as follows: x R y ? x.equals(y) for all objects in the class, then R should be an equivalence relation. Suppose that in trying to optimize some of the mathematics of a graphics application, a programmer creates an object called a point, consisting of two coordinates in the plane. The programmer defines an equals method as follows: If p and q are any points, then p . equals ( q ) ? the distance from p to q is less than or equal to c where c is a small positive number that depends on the resolution of the computer display. Is the programmer’s equals method an equivalence relation? Justify your answer.

Problem 35E Find an additional representative circuit for the input/output table of Example 8.3.9. Input Output P Q R 1 1 0 1 0 0 0 1 0 0 0 1

Problem 38E Let R be an equivalence relation on a set A. Prove each of the statements.directly from the definitions of equivalence relation and equivalence class without using the results of Lemma 8.3.2, Lemma 8.3.3, or Theorem. Theorem Suppose A is a set and R is an equivalence relation on A. For notational simplicity, we assume that R has only a finite number of distinct equivalence classes, which we denote A1, A2,…An, where n is a positive integer. (When the number of classes is infinite, the proof is identical except for notation.) Proof that A = A1 ? A2? …? An: [We must show that A ? A1 ? A2 ? ? ? ? ? An and that A1 ? A2 ?… ? An ? A.] To show that A ? A1 ? A2 ?… ? An, suppose x is any element of A. [We must show that x ? A1 ? A2 ?…? An.] By reflexivity of R,x R x. But this implies that x ? [x] by definition of class. Since x is in some equivalence class, it must be in one of the distinct equivalence classes A1, A2, …or An. Thus x ? Ai for some index i , and hence x ? A1 ? A2 ?…? An by definition of union [as was to be shown]. To show that A1 ? A2 ?…? An ? A, suppose x ? A1 ? A2 ?…? An. [We must show that x ? A.] Then x ? Ai for some i = 1, 2…n, by definition of union. But each Ai is an equivalence class of R. And equivalence classes are subsets of A. Hence Ai ? A and so x ? A [as was to be shown]. Since A ? A1 ? A2 ?… ? An and A1 ? A2 ?…? An ? A, then by definition of set equality, A = A1 ? A2 ?…? An. Proof that the distinct classes of R are mutually disjoint: Suppose that Ai and Aj are any two distinct equivalence classes of R. [We must show that Ai and Aj are disjoint.] Since Ai and Aj are distinct, then Ai ? Aj . And since Ai and Aj are equivalence classes of R, there must exist elements a and b in A such that Ai = [a] and Aj= [b]. By Lemma 8.3.3, either But [a] ?[b] because Ai ?Aj . Hence [a] ? [b] = . Thus Ai ? Aj = ,and so Ai and Aj are disjoint [as was to be shown]. Exercise For all a, b and c in A, if b R c and c ? [a] then b ? [a].

Problem 39E Let R be an equivalence relation on a set A. Prove each of the statements.directly from the definitions of equivalence relation and equivalence class without using the results of Lemma 8.3.2, Lemma 8.3.3, or Theorem. Theorem Suppose A is a set and R is an equivalence relation on A. For notational simplicity, we assume that R has only a finite number of distinct equivalence classes, which we denote A1, A2,…An, where n is a positive integer. (When the number of classes is infinite, the proof is identical except for notation.) Proof that A = A1 ? A2? …? An: [We must show that A ? A1 ? A2 ? ? ? ? ? An and that A1 ? A2 ?… ? An ? A.] To show that A ? A1 ? A2 ?… ? An, suppose x is any element of A. [We must show that x ? A1 ? A2 ?…? An.] By reflexivity of R,x R x. But this implies that x ? [x] by definition of class. Since x is in some equivalence class, it must be in one of the distinct equivalence classes A1, A2, …or An. Thus x ? Ai for some index i , and hence x ? A1 ? A2 ?…? An by definition of union [as was to be shown]. To show that A1 ? A2 ?…? An ? A, suppose x ? A1 ? A2 ?…? An. [We must show that x ? A.] Then x ? Ai for some i = 1, 2…n, by definition of union. But each Ai is an equivalence class of R. And equivalence classes are subsets of A. Hence Ai ? A and so x ? A [as was to be shown]. Since A ? A1 ? A2 ?… ? An and A1 ? A2 ?…? An ? A, then by definition of set equality, A = A1 ? A2 ?…? An. Proof that the distinct classes of R are mutually disjoint: Suppose that Ai and Aj are any two distinct equivalence classes of R. [We must show that Ai and Aj are disjoint.] Since Ai and Aj are distinct, then Ai ? Aj . And since Ai and Aj are equivalence classes of R, there must exist elements a and b in A such that Ai = [a] and Aj= [b]. By Lemma 8.3.3, either But [a] ?[b] because Ai ?Aj . Hence [a] ? [b] = . Thus Ai ? Aj = ,and so Ai and Aj are disjoint [as was to be shown]. Exercise For all a and b in A, if [a] = [b] then a R b.

Problem 36E Let R be an equivalence relation on a set A. Prove each of the statements.directly from the definitions of equivalence relation and equivalence class without using the results of Lemma 8.3.2, Lemma 8.3.3, or Theorem. Theorem Suppose A is a set and R is an equivalence relation on A. For notational simplicity, we assume that R has only a finite number of distinct equivalence classes, which we denote A1, A2,…An, where n is a positive integer. (When the number of classes is infinite, the proof is identical except for notation.) Proof that A = A1 ? A2? …? An: [We must show that A ? A1 ? A2 ? ? ? ? ? An and that A1 ? A2 ?… ? An ? A.] To show that A ? A1 ? A2 ?… ? An, suppose x is any element of A. [We must show that x ? A1 ? A2 ?…? An.] By reflexivity of R,x R x. But this implies that x ? [x] by definition of class. Since x is in some equivalence class, it must be in one of the distinct equivalence classes A1, A2, …or An. Thus x ? Ai for some index i , and hence x ? A1 ? A2 ?…? An by definition of union [as was to be shown]. To show that A1 ? A2 ?…? An ? A, suppose x ? A1 ? A2 ?…? An. [We must show that x ? A.] Then x ? Ai for some i = 1, 2…n, by definition of union. But each Ai is an equivalence class of R. And equivalence classes are subsets of A. Hence Ai ? A and so x ? A [as was to be shown]. Since A ? A1 ? A2 ?… ? An and A1 ? A2 ?…? An ? A, then by definition of set equality, A = A1 ? A2 ?…? An. Proof that the distinct classes of R are mutually disjoint: Suppose that Ai and Aj are any two distinct equivalence classes of R. [We must show that Ai and Aj are disjoint.] Since Ai and Aj are distinct, then Ai ? Aj . And since Ai and Aj are equivalence classes of R, there must exist elements a and b in A such that Ai = [a] and Aj= [b]. By Lemma 8.3.3, either But [a] ?[b] because Ai ?Aj . Hence [a] ? [b] = . Thus Ai ? Aj = ,and so Ai and Aj are disjoint [as was to be shown]. Exercise For all a in A, a ? [a].

Problem 37E Let R be an equivalence relation on a set A. Prove each of the statements.directly from the definitions of equivalence relation and equivalence class without using the results of Lemma 8.3.2, Lemma 8.3.3, or Theorem. Theorem Suppose A is a set and R is an equivalence relation on A. For notational simplicity, we assume that R has only a finite number of distinct equivalence classes, which we denote A1, A2,…An, where n is a positive integer. (When the number of classes is infinite, the proof is identical except for notation.) Proof that A = A1 ? A2? …? An: [We must show that A ? A1 ? A2 ? ? ? ? ? An and that A1 ? A2 ?… ? An ? A.] To show that A ? A1 ? A2 ?… ? An, suppose x is any element of A. [We must show that x ? A1 ? A2 ?…? An.] By reflexivity of R,x R x. But this implies that x ? [x] by definition of class. Since x is in some equivalence class, it must be in one of the distinct equivalence classes A1, A2, …or An. Thus x ? Ai for some index i , and hence x ? A1 ? A2 ?…? An by definition of union [as was to be shown]. To show that A1 ? A2 ?…? An ? A, suppose x ? A1 ? A2 ?…? An. [We must show that x ? A.] Then x ? Ai for some i = 1, 2…n, by definition of union. But each Ai is an equivalence class of R. And equivalence classes are subsets of A. Hence Ai ? A and so x ? A [as was to be shown]. Since A ? A1 ? A2 ?… ? An and A1 ? A2 ?…? An ? A, then by definition of set equality, A = A1 ? A2 ?…? An. Proof that the distinct classes of R are mutually disjoint: Suppose that Ai and Aj are any two distinct equivalence classes of R. [We must show that Ai and Aj are disjoint.] Since Ai and Aj are distinct, then Ai ? Aj . And since Ai and Aj are equivalence classes of R, there must exist elements a and b in A such that Ai = [a] and Aj= [b]. By Lemma 8.3.3, either But [a] ?[b] because Ai ?Aj . Hence [a] ? [b] = . Thus Ai ? Aj = ,and so Ai and Aj are disjoint [as was to be shown]. Exercise For all a and b in A, if b ? [a] then a R b.

Problem 41E Let R be an equivalence relation on a set A. Prove each of the statements.directly from the definitions of equivalence relation and equivalence class without using the results of Lemma 8.3.2, Lemma 8.3.3, or Theorem. Theorem Suppose A is a set and R is an equivalence relation on A. For notational simplicity, we assume that R has only a finite number of distinct equivalence classes, which we denote A1, A2,…An, where n is a positive integer. (When the number of classes is infinite, the proof is identical except for notation.) Proof that A = A1 ? A2? …? An: [We must show that A ? A1 ? A2 ? ? ? ? ? An and that A1 ? A2 ?… ? An ? A.] To show that A ? A1 ? A2 ?… ? An, suppose x is any element of A. [We must show that x ? A1 ? A2 ?…? An.] By reflexivity of R,x R x. But this implies that x ? [x] by definition of class. Since x is in some equivalence class, it must be in one of the distinct equivalence classes A1, A2, …or An. Thus x ? Ai for some index i , and hence x ? A1 ? A2 ?…? An by definition of union [as was to be shown]. To show that A1 ? A2 ?…? An ? A, suppose x ? A1 ? A2 ?…? An. [We must show that x ? A.] Then x ? Ai for some i = 1, 2…n, by definition of union. But each Ai is an equivalence class of R. And equivalence classes are subsets of A. Hence Ai ? A and so x ? A [as was to be shown]. Since A ? A1 ? A2 ?… ? An and A1 ? A2 ?…? An ? A, then by definition of set equality, A = A1 ? A2 ?…? An. Proof that the distinct classes of R are mutually disjoint: Suppose that Ai and Aj are any two distinct equivalence classes of R. [We must show that Ai and Aj are disjoint.] Since Ai and Aj are distinct, then Ai ? Aj . And since Ai and Aj are equivalence classes of R, there must exist elements a and b in A such that Ai = [a] and Aj= [b]. By Lemma 8.3.3, either But [a] ?[b] because Ai ?Aj . Hence [a] ? [b] = . Thus Ai ? Aj = ,and so Ai and Aj are disjoint [as was to be shown]. Exercise For all a and b in A, if a ? [b] then [a] = [b].

Problem 40E Let R be an equivalence relation on a set A. Prove each of the statements.directly from the definitions of equivalence relation and equivalence class without using the results of Lemma 8.3.2, Lemma 8.3.3, or Theorem. Theorem Suppose A is a set and R is an equivalence relation on A. For notational simplicity, we assume that R has only a finite number of distinct equivalence classes, which we denote A1, A2,…An, where n is a positive integer. (When the number of classes is infinite, the proof is identical except for notation.) Proof that A = A1 ? A2? …? An: [We must show that A ? A1 ? A2 ? ? ? ? ? An and that A1 ? A2 ?… ? An ? A.] To show that A ? A1 ? A2 ?… ? An, suppose x is any element of A. [We must show that x ? A1 ? A2 ?…? An.] By reflexivity of R,x R x. But this implies that x ? [x] by definition of class. Since x is in some equivalence class, it must be in one of the distinct equivalence classes A1, A2, …or An. Thus x ? Ai for some index i , and hence x ? A1 ? A2 ?…? An by definition of union [as was to be shown]. To show that A1 ? A2 ?…? An ? A, suppose x ? A1 ? A2 ?…? An. [We must show that x ? A.] Then x ? Ai for some i = 1, 2…n, by definition of union. But each Ai is an equivalence class of R. And equivalence classes are subsets of A. Hence Ai ? A and so x ? A [as was to be shown]. Since A ? A1 ? A2 ?… ? An and A1 ? A2 ?…? An ? A, then by definition of set equality, A = A1 ? A2 ?…? An. Proof that the distinct classes of R are mutually disjoint: Suppose that Ai and Aj are any two distinct equivalence classes of R. [We must show that Ai and Aj are disjoint.] Since Ai and Aj are distinct, then Ai ? Aj . And since Ai and Aj are equivalence classes of R, there must exist elements a and b in A such that Ai = [a] and Aj= [b]. By Lemma 8.3.3, either But [a] ?[b] because Ai ?Aj . Hence [a] ? [b] = . Thus Ai ? Aj = ,and so Ai and Aj are disjoint [as was to be shown]. Exercise For all a, b, and x in A, if a R b and x ?[a] then x ?[b].

Problem 42E Let R be the relation defined in Example. a. Prove that R is reflexive. ________________ b. Prove that R is symmetric. ________________ c. List four distinct elements in [(1, 3)]. ________________ d. List four distinct elements in [(2, 5)]. Example Rational Numbers Are Really Equivalence Classes For a moment, forget what you know about fractional arithmetic and look at the numbers as symbols. Considered as symbolic expressions, these appear quite different. In fact, if they were written as ordered pairs (1, 3) and (2, 6) they would be different. The fact that we regard them as “the same” is a specific instance of our general agreement to regard any two numbers as equal provided the cross products are equal: ad = bc. This can be formalized as follows, using the language of equivalence relations. Let A be the set of all ordered pairs of integers for which the second element of the pair is nonzero. Symbolically, A = Z × (Z –{0}). Define a relation R on A as follows: For all (a, b), (c, d) ? A, (a, b) R (c, d) ? ad = bc. The fact is that R is an equivalence relation. a. Prove that R is transitive. (Proofs that R is reflexive and symmetric are left to the exercises.) b. Describe the distinct equivalence classes of R. Solution a. [We must show that for all (a, b), (c, d), (e, f ) ? A, if (a, b) R (c, d) and (c, d)R (e, f ), then (a, b) R (e, f ).] Suppose (a, b), (c, d), and (e, f ) are particular but arbitrarily chosen elements of A such that (a, b) R (c, d) and (c, d) R (e, f ). [We must show that (a, b) R (e, f ).] By definition of R, (1) ad = bc and (2) cf = de. Since the second elements of all ordered pairs in A are nonzero, b ? 0, d ?0, and f ? 0. Multiply both sides of equation (1) by f and both sides of equation (2) by b to obtain (1?) ad f = bcf and (2?) bcf = bde. Thus ad f = bde and, since d ? 0, it follows from the cancellation law for multiplication (T7 in Appendix A) that a f = be. It follows, by definition of R, that (a, b) R (e, f ) [as was to be shown]. ________________ b. There is one equivalence class for each distinct rational number. Each equivalence class consists of all ordered pairs (a, b) that, if written as fractions a/b, would equal each other. The reason for this is that the condition for two rational numbers to be equal is the same as the condition for two ordered pairs to be related. For instance, the class of (1, 2) is [(1, 2)] = {(1, 2), (–1,–2), (2, 4), (–2,–4), (3, 6), (–3,–6),…} Since and so forth.

Problem 46E Let R be a relation on a set A and suppose R is symmetric and transitive. Prove the following: If for every x in A there is a y in A such that x R y, then R is an equivalence relation.

Problem 43E In Example, define operations of addition (+) and multiplication (•) as follows: For all (a, b), (c, d) ?A, [(a, b)] + [(c, d)] = [(ad+(bc, bd)] [(a, b)]•[(c, d)]= [(ac, bd)]. a. Prove that this addition is well defined. That is, show that if [(a, b)] = [(a', b')] and [(c, d)] = [(c', d')], then [(ad + bc, bd)] = [(a'd' + b'c', b'd')]. ________________ b. Prove that this multiplication is well defined. That is, show that if [(a, b)\ = [(a', b')] and [(c, d)] = [(c', d')], then [(ac, bd)] = [(a'c', b'd')]. ________________ c. Show that [(0, 1)] is an identity element for addition. That is, show that for any (a, b) ? A, [(a, b)] + [(0, 1)] = [(0, 1)] + [(a, b)] = [(a, b)] ________________ d. Find an identity element for multiplication. That is, find (i, j) in A so that for all (a, b) in A. [(a, b)] • [(i, j)]= [(i, j)] •[(a, b)] = [(a, b)]. ________________ e. For any (a, b) ?A, show that [(-a, b)\ is an inverse for [(a, b)] for addition. That is, show that [(-a, b)] + [(a, b)] = [(a, b)] + [(-a, b)] = [(0, 1)]. ________________ f. Given any (a, b) ? A with a = 0, find an inverse for [(a, b)] for multiplication. That is, find (c, d) in A so that [(a, b)]•[(c, d)] = [(c, d)]•[(a, b)] = [(i, j)], where [(i, j)] is the identity element you found in part (d). Example Rational Numbers Are Really Equivalence Classes For a moment, forget what you know about fractional arithmetic and look at the numbers as symbols. Considered as symbolic expressions, these appear quite different. In fact, if they were written as ordered pairs (1, 3) and (2, 6) they would be different. The fact that we regard them as “the same” is a specific instance of our general agreement to regard any two numbers as equal provided the cross products are equal: ad = bc. This can be formalized as follows, using the language of equivalence relations. Let A be the set of all ordered pairs of integers for which the second element of the pair is nonzero. Symbolically, A = Z × (Z –{0}). Define a relation R on A as follows: For all (a, b), (c, d) ? A, (a, b) R (c, d) ? ad = bc. The fact is that R is an equivalence relation. a. Prove that R is transitive. (Proofs that R is reflexive and symmetric are left to the exercises.) b. Describe the distinct equivalence classes of R. Solution a. [We must show that for all (a, b), (c, d), (e, f ) ? A, if (a, b) R (c, d) and (c, d)R (e, f ), then (a, b) R (e, f ).] Suppose (a, b), (c, d), and (e, f ) are particular but arbitrarily chosen elements of A such that (a, b) R (c, d) and (c, d) R (e, f ). [We must show that (a, b) R (e, f ).] By definition of R, (1) ad = bc and (2) cf = de. Since the second elements of all ordered pairs in A are nonzero, b ? 0, d ?0, and f ? 0. Multiply both sides of equation (1) by f and both sides of equation (2) by b to obtain (1?) ad f = bcf and (2?) bcf = bde. Thus ad f = bde and, since d ? 0, it follows from the cancellation law for multiplication (T7 in Appendix A) that a f = be. It follows, by definition of R, that (a, b) R (e, f ) [as was to be shown]. ________________ b. There is one equivalence class for each distinct rational number. Each equivalence class consists of all ordered pairs (a, b) that, if written as fractions a/b, would equal each other. The reason for this is that the condition for two rational numbers to be equal is the same as the condition for two ordered pairs to be related. For instance, the class of (1, 2) is [(1, 2)] = {(1, 2), (–1,–2), (2, 4), (–2,–4), (3, 6), (–3,–6),…} Since and so forth.

Problem 45E The following argument claims to prove that the requirement that an equivalence relation be reflexive is redundant. In other words, it claims to show that if a relation is symmetric and transitive, then it is reflexive. Find the mistake in the argument. “Proof: Let R be a relation on a set A and suppose R is symmetric and transitive. For any two elements x and yin A, if x R y then y R x since R is symmetric. But then it follows by transitivity that x R x. Hence R is reflexive.”

Problem 44E Let A = Z+× Z+. Define a relation R on A as follows: For all (a, b) and (c, d) in A, (a, b) R (c, d) ? a + d = c + b. a. Prove that R is reflexive. ________________ b. Prove that R is symmetric. ________________ c. Prove that R is transitive. ________________ d. List five elements in [(1, 1)]. ________________ e. List five elements in [(3, 1)]. ________________ f. List five elements in [(1, 2)]. ________________ g. Describe the distinct equivalence classes of R.