Section 5.1 Relations
347
10. Both r and s are binary relations from P to C where P = 5people in theUnited States6, C = 5cities in the
United States6, x r y 4 x lives in y, and x s y 4 x works in y. Describe each of the following relations.
a. r d s
c. r d s′
b. r c s
d. r′ d s
11. Let S = 51, 2, 36. Test the following binary relations on S for reflexivity, symmetry, antisymmetry, and
transitivity.
a. r = 5(1, 3), (3, 3), (3, 1), (2, 2), (2, 3), (1, 1), (1, 2)6
b. r = 5(1, 1), (3, 3), (2, 2)6
c. r = 5(1, 1), (1, 2), (2, 3), (3, 1), (1, 3)6
d. r = 5(1, 1), (1, 2), (2, 3), (1, 3)6
12. Let S = 50, 1, 2, 4, 66. Test the following binary relations on S for reflexivity, symmetry, antisymmetry,
and transitivity.
a. r = 5(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (0, 1), (1, 2), (2, 4), (4, 6)6
b. r = 5(0, 1), (1, 0), (2, 4), (4, 2), (4, 6), (6, 4)6
c. r = 5(0, 1), (1, 2), (0, 2), (2, 0), (2, 1), (1, 0), (0, 0), (1, 1), (2, 2)6
d. r = 5(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (4, 6), (6, 4)6
e. r = [
13. Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry, and transitivity.
a. S = Q
x r y 4 0 x 0 ≤ 0 y 0
b. S = Z
x r y 4 x − y is an integral multiple of 3
c. S = N
x r y 4 x # y is even
d. S = N
x r y 4 x is odd
e. S = set of all squares in the plane
S 1 r S 2 4 length of side of S 1 = length of side of S 2
14. Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry, and
transitivity.
a. S = set of all finite-length strings of characters
x r y 4 number of characters in x = number of characters in y
b. S = 50, 1, 2, 3, 4, 56
x r y 4 x + y = 5
c. S = `(51, 2, 3, 4, 5, 6, 7, 8, 96)
A r B 4 0 A0 = 0 B0
d. S = `(51, 2, 3, 4, 5, 6, 7, 8, 96)
A r B 4 0 A0 ∙ 0 B0
e. S = N × N
(x 1 , y 1 ) r (x 2 , y 2 ) 4 x 1 ≤ x 2 and y 1 ≥ y 2
347
10. Both r and s are binary relations from P to C where P = 5people in theUnited States6, C = 5cities in the
United States6, x r y 4 x lives in y, and x s y 4 x works in y. Describe each of the following relations.
a. r d s
c. r d s′
b. r c s
d. r′ d s
11. Let S = 51, 2, 36. Test the following binary relations on S for reflexivity, symmetry, antisymmetry, and
transitivity.
a. r = 5(1, 3), (3, 3), (3, 1), (2, 2), (2, 3), (1, 1), (1, 2)6
b. r = 5(1, 1), (3, 3), (2, 2)6
c. r = 5(1, 1), (1, 2), (2, 3), (3, 1), (1, 3)6
d. r = 5(1, 1), (1, 2), (2, 3), (1, 3)6
12. Let S = 50, 1, 2, 4, 66. Test the following binary relations on S for reflexivity, symmetry, antisymmetry,
and transitivity.
a. r = 5(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (0, 1), (1, 2), (2, 4), (4, 6)6
b. r = 5(0, 1), (1, 0), (2, 4), (4, 2), (4, 6), (6, 4)6
c. r = 5(0, 1), (1, 2), (0, 2), (2, 0), (2, 1), (1, 0), (0, 0), (1, 1), (2, 2)6
d. r = 5(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (4, 6), (6, 4)6
e. r = [
13. Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry, and transitivity.
a. S = Q
x r y 4 0 x 0 ≤ 0 y 0
b. S = Z
x r y 4 x − y is an integral multiple of 3
c. S = N
x r y 4 x # y is even
d. S = N
x r y 4 x is odd
e. S = set of all squares in the plane
S 1 r S 2 4 length of side of S 1 = length of side of S 2
14. Test the following binary relations on the given sets S for reflexivity, symmetry, antisymmetry, and
transitivity.
a. S = set of all finite-length strings of characters
x r y 4 number of characters in x = number of characters in y
b. S = 50, 1, 2, 3, 4, 56
x r y 4 x + y = 5
c. S = `(51, 2, 3, 4, 5, 6, 7, 8, 96)
A r B 4 0 A0 = 0 B0
d. S = `(51, 2, 3, 4, 5, 6, 7, 8, 96)
A r B 4 0 A0 ∙ 0 B0
e. S = N × N
(x 1 , y 1 ) r (x 2 , y 2 ) 4 x 1 ≤ x 2 and y 1 ≥ y 2