Page 636 - Discrete Mathematics and Its Applications

9.5 Equivalence Relations 615

Exercises

1. Which of these relations on {0, 1, 2, 3} are equivalence 11. Show that the relation R consisting of all pairs (x, y) such
relations? Determine the properties of an equivalence re- that x and y are bit strings of length three or more that
lation that the others lack. agree in their first three bits is an equivalence relation on
the set of all bit strings of length three or more.
a) {(0, 0), (1, 1), (2, 2), (3, 3)}
b) {(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}
12. Show that the relation R consisting of all pairs (x, y) such
c) {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)} that x and y are bit strings of length three or more that
d) {(0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2), agree except perhaps in their first three bits is an equiva-
(3, 3)} lence relation on the set of all bit strings of length three
e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), or more.
(2, 2), (3, 3)}
13. Show that the relation R consisting of all pairs (x, y) such
2. Which of these relations on the set of all people are equiv-
that x and y are bit strings that agree in their first and third
alence relations? Determine the properties of an equiva-
bits is an equivalence relation on the set of all bit strings
lence relation that the others lack.
of length three or more.
a) {(a, b) | a and b are the same age}
14. Let R be the relation consisting of all pairs (x, y) such
b) {(a, b) | a and b have the same parents}
that x and y are strings of uppercase and lowercase En-
c) {(a, b) | a and b share a common parent}
glish letters with the property that for every positive in-
d) {(a, b) | a and b have met}
teger n, the nth characters in x and y are the same letter,
e) {(a, b) | a and b speak a common language}
either uppercase or lowercase. Show that R is an equiva-
3. Which of these relations on the set of all functions from Z lence relation.
to Z are equivalence relations? Determine the properties
of an equivalence relation that the others lack. 15. Let R be the relation on the set of ordered pairs of posi-
a) {(f, g) | f(1) = g(1)} tive integers such that ((a, b), (c, d)) ∈ R if and only if
a + d = b + c. Show that R is an equivalence relation.
b) {(f, g) | f(0) = g(0) or f(1) = g(1)}
c) {(f, g) | f(x) − g(x) = 1 for all x ∈ Z}
16. Let R be the relation on the set of ordered pairs of posi-
d) {(f, g) | for some C ∈ Z, for all x ∈ Z, f (x) − tive integers such that ((a, b), (c, d)) ∈ R if and only if
g(x) = C} ad = bc. Show that R is an equivalence relation.
e) {(f, g) | f(0) = g(1) and f(1) = g(0)}
17. (Requires calculus)
4. Define three equivalence relations on the set of students
in your discrete mathematics class different from the re- a) Show that the relation R on the set of all differentiable
lations discussed in the text. Determine the equivalence functions from R to R consisting of all pairs (f, g)

classes for each of these equivalence relations. such that f (x) = g (x) for all real numbers x is an
equivalence relation.
5. Define three equivalence relations on the set of buildings
on a college campus. Determine the equivalence classes b) Which functions are in the same equivalence class as
2
for each of these equivalence relations. the function f(x) = x ?
6. Define three equivalence relations on the set of classes of- 18. (Requires calculus)
fered at your school. Determine the equivalence classes a) Let n be a positive integer. Show that the relation
for each of these equivalence relations. R on the set of all polynomials with real-valued
7. Show that the relation of logical equivalence on the set coefficients consisting of all pairs (f, g) such that
(n)
(n)
of all compound propositions is an equivalence relation. f (n) (x) = g (x) is an equivalence relation. [Here
What are the equivalence classes of F and of T? f (x) is the nth derivative of f(x).]
8. Let R be the relation on the set of all sets of real numbers b) Which functions are in the same equivalence class as
4
such that SR T if and only if S and T have the same the function f(x) = x , where n = 3?
cardinality. Show that R is an equivalence relation. What 19. Let R be the relation on the set of all URLs (or Web ad-
are the equivalence classes of the sets {0, 1, 2} and Z? dresses) such that xR y if and only if the Web page at
9. Suppose that A is a nonempty set, and f is a function that x is the same as the Web page at y. Show that R is an
has A as its domain. Let R be the relation on A consisting equivalence relation.
of all ordered pairs (x, y) such that f(x) = f(y).
20. Let R be the relation on the set of all people who have
a) Show that R is an equivalence relation on A. visited a particular Web page such that xR y if and only
b) What are the equivalence classes of R? if person x and person y have followed the same set of
10. Suppose that A is a nonempty set and R is an equivalence links starting at this Web page (going from Web page to
relation on A. Show that there is a function f with A as its Web page until they stop using the Web). Show that R is
domain such that (x, y) ∈ R if and only if f(x) = f(y). an equivalence relation.