348
Relations, Functions, and Matrices
15. Which of the binary relations of Exercise 13 are equivalence relations? For each equivalence relation,
describe the associated equivalence classes.
16. Which of the binary relations of Exercise 14 are equivalence relations? For each equivalence relation,
describe the associated equivalence classes.
17. Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry, and
transitivity.
a. S = Z
x r y 4 x + y is a multiple of 5
b. S = Z
x r y 4 x < y
c. S = set of all finite-length binary strings
x r y 4 x is a prefix of y
d. S = set of all finite-length binary strings
x r y 4 x has the same number of 1s as y
18. Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry, and
transitivity.
a. S = Z
x r y 4 x = ky for some integer k
b. S = Z
x r y 4 there is a prime number p such that p 0 x and p 0 y
c. S = `(51, 2, 3, 4, 5, 6, 7, 8, 96)
A r B 4 A d B = [
d. S = `(51, 2, 3, 4, 5, 6, 7, 8, 96)
A r B 4 A = B′
19. Let S be the set of people in the United States. Test the following binary relations on S for reflexivity, symmetry, antisymmetry, and transitivity.
a. x r y 4 x is at least as tall as y.
b. x r y 4 x is taller than y.
c. x r y 4 x is the same height as y.
d. x r y 4 x is a child of y.
20. Let S be the set of people in the United States. Test the following binary relations on S for reflexivity,
symmetry, antisymmetry, and transitivity.
a. x r y 4 x is the husband of y.
b. x r y 4 x is the spouse of y.
c. x r y 4 x has the same parents as y.
d. x r y 4 x is the brother of y.
21. For each case, think of a set S and a binary relation r on S (different from any in the examples or problems) satisfying the given conditions.
a. r is reflexive and symmetric but not transitive.
b. r is reflexive and transitive but not symmetric.
c. r is not reflexive or symmetric but is transitive.
d r is reflexive but neither symmetric nor transitive.
Relations, Functions, and Matrices
15. Which of the binary relations of Exercise 13 are equivalence relations? For each equivalence relation,
describe the associated equivalence classes.
16. Which of the binary relations of Exercise 14 are equivalence relations? For each equivalence relation,
describe the associated equivalence classes.
17. Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry, and
transitivity.
a. S = Z
x r y 4 x + y is a multiple of 5
b. S = Z
x r y 4 x < y
c. S = set of all finite-length binary strings
x r y 4 x is a prefix of y
d. S = set of all finite-length binary strings
x r y 4 x has the same number of 1s as y
18. Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry, and
transitivity.
a. S = Z
x r y 4 x = ky for some integer k
b. S = Z
x r y 4 there is a prime number p such that p 0 x and p 0 y
c. S = `(51, 2, 3, 4, 5, 6, 7, 8, 96)
A r B 4 A d B = [
d. S = `(51, 2, 3, 4, 5, 6, 7, 8, 96)
A r B 4 A = B′
19. Let S be the set of people in the United States. Test the following binary relations on S for reflexivity, symmetry, antisymmetry, and transitivity.
a. x r y 4 x is at least as tall as y.
b. x r y 4 x is taller than y.
c. x r y 4 x is the same height as y.
d. x r y 4 x is a child of y.
20. Let S be the set of people in the United States. Test the following binary relations on S for reflexivity,
symmetry, antisymmetry, and transitivity.
a. x r y 4 x is the husband of y.
b. x r y 4 x is the spouse of y.
c. x r y 4 x has the same parents as y.
d. x r y 4 x is the brother of y.
21. For each case, think of a set S and a binary relation r on S (different from any in the examples or problems) satisfying the given conditions.
a. r is reflexive and symmetric but not transitive.
b. r is reflexive and transitive but not symmetric.
c. r is not reflexive or symmetric but is transitive.
d r is reflexive but neither symmetric nor transitive.