354
Relations, Functions, and Matrices
50. Let p be a prime number. Prove that x
2
≡ y
2
(mod p) if and only if x ≡ y (mod p) or x ≡ −y (mod p).
51. a. Given the partition 51, 26 and 53, 46 of the set S = 51, 2, 3, 46, list the ordered pairs in the corresponding equivalence relation.
b. Given the partition 5a, b, c6 and 5d, e6 of the set S = 5a, b, c, d, e6, list the ordered pairs in the corresponding equivalence relation.
52. Let S be the set of all books in the library. Let r be a binary relation on S defined by x r y 4 “the color of
x’s cover is the same as the color of y’s cover.” Show that r is an equivalence relation on S and describe
the resulting equivalence classes.
53. Let S = N and let r be a binary relation on S defined by x r y 4 x
2
− y
2
is even. Show that r is an equivalence relation on S and describe the resulting equivalence classes.
54. Let S = R and let r be a binary relation on S defined by x r y 4 x − y is an integer.
a. Show that r is an equivalence relation on S.
b. List 5 values that belong to [1.5].
55. Let S = N × N and let r be a binary relation on S defined by (x, y) r (z, w) 4 y = w. Show that r is an
equivalence relation on S and describe the resulting equivalence classes.
56. Let S = N × N and let r be a binary relation on S defined by (x, y) r (z, w) 4 x + y = z + w. Show that
r is an equivalence relation on S and describe the resulting equivalence classes.
57. Let S be the set of all binary strings of length 8 and let r be a binary relation on S defined by x r y 4
y starts with the same bit value (0 or 1) as x and y ends with the same bit value (0 or 1) as x.
a. Show that r is an equivalence relation on S.
b. How many strings are in the set S?
c. Into how many equivalence classes does r partition S? Explain your answer.
d. How many strings are in each equivalence class?
58. The documentation for the Java programming language recommends that when a boolean “equals method”
is defined for an object, it should be an equivalence relation. That is, if r is defined by x r y 4 x.equals(y)
for all objects in the class, then r should be an equivalence relation. In 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 two points in the plane, then
p.equals(q) 4 the distance from p to q is ≤ 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.
59. Let S be the set of all propositional wffs with n statement letters. Let r be a binary relation on S defined
by P r Q 4 “P 4 Q is a tautology.” Show that r is an equivalence relation on S and describe the resulting
equivalence classes. (We have used the notation P 3 Q for P r Q.)
60. Given two partitions p 1 and p 2 of a set S, p 1 is a refinement of p 2 if each block of p 1 is a subset of a block
of p 2 . Show that refinement is a partial ordering on the set of all partitions of S.
Exercises 61–72 all deal with partitions on a set.
61. Let P n denote the total number of partitions of an n-element set, n ≥ 1. The numbers P n are called Bell
numbers. Compute the following Bell numbers.
a. P 1
b. P 2
c. P 3
d. P 4
Relations, Functions, and Matrices
50. Let p be a prime number. Prove that x
2
≡ y
2
(mod p) if and only if x ≡ y (mod p) or x ≡ −y (mod p).
51. a. Given the partition 51, 26 and 53, 46 of the set S = 51, 2, 3, 46, list the ordered pairs in the corresponding equivalence relation.
b. Given the partition 5a, b, c6 and 5d, e6 of the set S = 5a, b, c, d, e6, list the ordered pairs in the corresponding equivalence relation.
52. Let S be the set of all books in the library. Let r be a binary relation on S defined by x r y 4 “the color of
x’s cover is the same as the color of y’s cover.” Show that r is an equivalence relation on S and describe
the resulting equivalence classes.
53. Let S = N and let r be a binary relation on S defined by x r y 4 x
2
− y
2
is even. Show that r is an equivalence relation on S and describe the resulting equivalence classes.
54. Let S = R and let r be a binary relation on S defined by x r y 4 x − y is an integer.
a. Show that r is an equivalence relation on S.
b. List 5 values that belong to [1.5].
55. Let S = N × N and let r be a binary relation on S defined by (x, y) r (z, w) 4 y = w. Show that r is an
equivalence relation on S and describe the resulting equivalence classes.
56. Let S = N × N and let r be a binary relation on S defined by (x, y) r (z, w) 4 x + y = z + w. Show that
r is an equivalence relation on S and describe the resulting equivalence classes.
57. Let S be the set of all binary strings of length 8 and let r be a binary relation on S defined by x r y 4
y starts with the same bit value (0 or 1) as x and y ends with the same bit value (0 or 1) as x.
a. Show that r is an equivalence relation on S.
b. How many strings are in the set S?
c. Into how many equivalence classes does r partition S? Explain your answer.
d. How many strings are in each equivalence class?
58. The documentation for the Java programming language recommends that when a boolean “equals method”
is defined for an object, it should be an equivalence relation. That is, if r is defined by x r y 4 x.equals(y)
for all objects in the class, then r should be an equivalence relation. In 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 two points in the plane, then
p.equals(q) 4 the distance from p to q is ≤ 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.
59. Let S be the set of all propositional wffs with n statement letters. Let r be a binary relation on S defined
by P r Q 4 “P 4 Q is a tautology.” Show that r is an equivalence relation on S and describe the resulting
equivalence classes. (We have used the notation P 3 Q for P r Q.)
60. Given two partitions p 1 and p 2 of a set S, p 1 is a refinement of p 2 if each block of p 1 is a subset of a block
of p 2 . Show that refinement is a partial ordering on the set of all partitions of S.
Exercises 61–72 all deal with partitions on a set.
61. Let P n denote the total number of partitions of an n-element set, n ≥ 1. The numbers P n are called Bell
numbers. Compute the following Bell numbers.
a. P 1
b. P 2
c. P 3
d. P 4