14 Exercises for Unit I V (Relations and functions) IV.1 : Binary relations (Halmos, § 6; Lipschutz, §§ 3.3 – 3.9, 3.11, 7.1 – 7.6, 7.8) Problems for study. Lipschutz : 3.6(a), 3.7(b), 3.11, 3.12(b), 3.13 – 3.14, 3.16 – 3.18, 3.23 – 3.25, 3.29 – 3.30, 3.32 – 3.33, 3.41(ab), 3.45 – 3.50, 3.55, 3.57. Exercises to work. 1. (Rosen, Exercise 3, p. 480) Determine whether each of the following relations on the set {1, 2, 3, 4} is reflexive, symmetric, antisymmetric or transitive. (a) { (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4) } (b) { (1, 1), (2, 2), (2, 1), (1, 2), (3, 3), (4, 4) } (c) { (2, 4), (4, 2) } (d) { (1, 2), (2, 3), (3, 4) } (e) { (1, 1), (2, 2), (3, 3), (3, 4) } ( f ) { (1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4) } 2. (Taken from Rosen, Exercise 6, p. 480) Determine whether the relations described by the conditions below are reflexive, symmetric, antisymmetric or transitive. (c) All ordered pairs of real numbers (x, y) such that x – y is rational. (d) All ordered pairs of real numbers (x, y) such that x = 2y. (e) All ordered pairs of real numbers (x, y) such that x y ≥≥≥≥ 0. (f) All ordered pairs of real numbers (x, y) such that x y = 0. 3. (Taken from Rosen, Exercise 7, p. 480) Determine whether the relations described by the conditions below are reflexive, symmetric, antisymmetric or transitive. (a) All ordered pairs of real numbers (x, y) such that x ≠≠≠≠ y. (b) All ordered pairs of real numbers (x, y) such that x y ≥≥≥≥ 1. (c) All ordered pairs of real numbers (x, y) such that x = y ±±±± 1. (g) All ordered pairs of real numbers (x, y) such that x = y2. (h) All ordered pairs of real numbers (x, y) such that x ≥≥≥≥ y2. 4. (Taken from Rosen, Exercise 7, p. 533) Suppose that R1 and R2 are reflexive relations on a set A. Are their union and intersection reflexive? Give reasons for your answer.15 5. (Taken from Rosen, Exercise 1, p. 513) Which of the relations described below on the set {0, 1, 2, 3} are equivalence relations? Determine the properties of an equivalence relation that the others lack. (a) { (0, 0), (1, 1), (2, 2), (3, 3) } (b) { (0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3) } (c) { (0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3) } (d) { (0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) } (e) { (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 2), (3, 3) } 6. (Taken from Rosen, Exercise 2, p. 513) Which of the relations described below on the set of all people are equivalence relations? Determine the properties of an equivalence relation that the others lack. (a) All a and b such that a and b have the same age. (b) All a and b such that a and b have the same parents. (c) All a and b such that a and b have a common parent. (d) All a and b such that a and b have met. (e) All a and b such that a and b speak a common language. 7. Let R be a binary relation that is reflexive and transitive, and define a new binary relation S such that x S y if and only if x R y and y R x. Prove that S is an equivalence relation. 8. (Taken from Rosen, Exercise 10, p. 533) A relation R is said to be circular if it satisfies a R b and b R c imply c R a. Show that R is an equivalence relation if and only if it is reflexive and circular. 9. Let R denote the real numbers, and let P be the binary relation on R ×××× ( R – {0} ) such that (x, y) P (z, w) if and only if x w = y z. Prove that P is an equivalence relation, and show that every equivalence class contains a unique element (or representative) of the form (r, 1). 10. Let N + be the set of all positive integers, and define a binary relation Q on the set N + ×××× N + such that (x, y) Q (z, w) if and only if x w = z y . Determine whether Q is an equivalence relation. 11. Let R be the binary relation in Algebraic Example 3 (the set is a chessboard, and the relation is that two squares are related if there is a knight’s move from one to the other). (i) Let E be the equivalence relation generated by R. Show that E contains exactly one equivalence class; in other words, starting from the standard position of (1, 2) the knight can reach every point on the chessboard. (ii) Suppose that we replace our 8 ×××× 8 chessboard with an infinite board whose elements are ordered pairs of integers. Prove that in this case the16 equivalence relation E generated by R also has one point. [ Hint : Start at the origin, and show that every adjacent square is E – related to it. ] 12. (Taken from Rosen, Exercise 38, p. 481) Let R1 be the relation “a divides b” on the positive integers, and let R2 be the relation “a is a multiple of b” on positive integers. Describe the relations R1 ∪∪∪∪ R2 and R1 ∩∩∩∩ R2 . 13. Given two binary relations S and T on a set A, their composite S T is defined to be all (x, z) ∈∈∈∈ A ×××× A such that there is some y ∈∈∈∈ A for which x S y and y T z. If A is the real line and S and T are the relations u S v if and only if |u| = |v| u T v if and only if |u + 1| = |v – 2| then find all real numbers z such that 1 S T z and all real number z such that 2 S T z. [ Hint: the first relation amounts to saying that v = a u where a = ±±±± 1, and the second amounts to saying that v – 2 = b(u – 1) where once again b = ±±±± 1. Why does this imply that there are at most four choices for z in each case? ] 14. Let S, T1 and T2 be binary relations on a set A. Prove that we have S (T1 ∪∪∪∪T2) = (S T1) ∪∪∪∪ (S T2) and S(T1 ∩∩∩∩ T2) ⊂⊂⊂⊂ (S T1) ∩∩∩∩ (S T2). Find an example where the inclusion in the second statement is proper. [ Hint: There is an example for which A has four elements. ] IV.2 : Partial and linear orderings (Halmos, § 14; Lipschutz, §§ 3.10, 7.1 – …