Page 638 - Discrete Mathematics and Its Applications

9.5 Equivalence Relations 617

c) the set of integers divisible by 3, the set of integers b) {a}, {b}, {c, d}, {e, f }, {g}
leaving a remainder of 1 when divided by 3, and the
c) {a, b, c, d}, {e, f, g}
set of integers leaving a remainder of 2 when divided
by 3 d) {a, c, e, g}, {b, d}, {f }
A partition P 1 is called a refinement of the partition P 2 if
d) the set of integers less than −100, the set of integers
every set in P 1 is a subset of one of the sets in P 2 .
with absolute value not exceeding 100, and the set of
integers greater than 100 49. Show that the partition formed from congruence classes
e) the set of integers not divisible by 3, the set of even modulo 6 is a refinement of the partition formed from
integers, and the set of integers that leave a remainder congruence classes modulo 3.
of 3 when divided by 6
50. Show that the partition of the set of people living in the
45. Which of these are partitions of the set Z × Z of ordered United States consisting of subsets of people living in the
pairs of integers? same county (or parish) and same state is a refinement of
a) the set of pairs (x, y), where x or y is odd; the set the partition consisting of subsets of people living in the
of pairs (x, y), where x is even; and the set of pairs same state.
(x, y), where y is even
51. Show that the partition of the set of bit strings of length 16
b) the set of pairs (x, y), where both x and y are odd; formed by equivalence classes of bit strings that agree on
the set of pairs (x, y), where exactly one of x and y the last eight bits is a refinement of the partition formed
is odd; and the set of pairs (x, y), where both x and y from the equivalence classes of bit strings that agree on
are even the last four bits.
c) the set of pairs (x, y), where x is positive; the set of In Exercises 52 and 53, R n refers to the family of equivalence
pairs (x, y), where y is positive; and the set of pairs relations defined in Example 5. Recall that sR n t, where s
(x, y), where both x and y are negative and t are two strings if s = t or s and t are strings with at least
d) the set of pairs (x, y), where 3 | x and 3 | y; the set n characters that agree in their first n characters.
of pairs (x, y), where 3 | x and 3 | y; the set of pairs
52. Show that the partition of the set of all bit strings formed
(x, y), where 3 | x and 3 | y; and the set of pairs
by equivalence classes of bit strings with respect to the
(x, y), where 3 | x and 3 | y
equivalence relation R 4 is a refinement of the partition
e) the set of pairs (x, y), where x> 0 and y> 0; the formed by equivalence classes of bit strings with respect
set of pairs (x, y), where x> 0 and y ≤ 0; the set of to the equivalence relation R 3 .
pairs (x, y), where x ≤ 0 and y> 0; and the set of
pairs (x, y), where x ≤ 0 and y ≤ 0 53. Show that the partition of the set of all identifiers in C
formed by the equivalence classes of identifiers with re-
f) the set of pairs (x, y), where x = 0 and y = 0; the set spect to the equivalence relation R 31 is a refinement of
of pairs (x, y), where x = 0 and y = 0; and the set of the partition formed by equivalence classes of identifiers
pairs (x, y), where x = 0 and y = 0
with respect to the equivalence relation R 8 . (Compilers
46. Which of these are partitions of the set of real numbers? for“old”Cconsideridentifiersthesamewhentheirnames
a) the negative real numbers, {0}, the positive real agree in their first eight characters, while compilers in
numbers standard C consider identifiers the same when their names
b) the set of irrational numbers, the set of rational agree in their first 31 characters.)
numbers
54. Suppose that R 1 and R 2 are equivalence relations on a
c) the set of intervals [k, k + 1], k = ..., −2, −1, 0, set A. Let P 1 and P 2 be the partitions that correspond to
1, 2,... R 1 and R 2 , respectively. Show that R 1 ⊆ R 2 if and only
d) the set of intervals (k, k + 1), k = ..., −2, −1, 0, if P 1 is a refinement of P 2 .
1, 2,...
55. Find the smallest equivalence relation on the set
e) the set of intervals (k, k + 1], k = ..., −2, −1, 0, {a, b, c, d, e} containing the relation {(a, b), (a, c),
1, 2,... (d, e)}.
f) the sets {x + n | n ∈ Z} for all x ∈[0, 1)
56. Suppose that R 1 and R 2 are equivalence relations on the
47. List the ordered pairs in the equivalence relations pro- set S. Determine whether each of these combinations
duced by these partitions of {0, 1, 2, 3, 4, 5}. of R 1 and R 2 must be an equivalence relation.
a) {0}, {1, 2}, {3, 4, 5} a) R 1 ∪ R 2 b) R 1 ∩ R 2 c) R 1 ⊕ R 2
b) {0, 1}, {2, 3}, {4, 5} 57. Consider the equivalence relation from Example 2,
c) {0, 1, 2}, {3, 4, 5} namely, R ={(x, y) | x − y is an integer}.
d) {0}, {1}, {2}, {3}, {4}, {5} a) What is the equivalence class of 1 for this equivalence
48. List the ordered pairs in the equivalence relations pro- relation?
duced by these partitions of {a, b, c, d, e, f, g}. b) What is the equivalence class of 1/2 for this equiva-
lence relation?
a) {a, b}, {c, d}, {e, f, g}