Discrete Math.
& Linear Programming BES 114
Tutorial #4
”Relations”
1. Let A = {0, 1, 2, 3, 4} and B = {0, 1, 2, 3}. The ordered pairs in the relation R are:
(a) a = b (c) a > b
(b) a + b = 4 (d) a | b (i.e., a divides b)
2. (a) List all the ordered pairs in the relation R = {(a, b) | a divides b} on the set {1, 2, 3, 4, 5, 6}
(b) Display this relation graphically.
3. For each of these relations on the set {1, 2, 3, 4}, decide whether it is reflexive, symmetric, antisymmet-
ric, and transitive.
(a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} (d) {(1, 2), (2, 3), (3, 4)}
(b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)} (e) {(1, 1), (2, 2), (3, 3), (4, 4)}
(c) {(2, 4), (4, 2)} (f) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}
4. Determine whether the relation R on the set of all real numbers is reflexive, symmetric, antisym-
metric, and/or transitive,
(a) (x, y) ∈ R if and only if x + y = 0. (c) (x, y) ∈ R if and only if x = 2y.
(b) (x, y) ∈ R if and only if x = ±y. (d) (x, y) ∈ R if and only if xy = 0.
5. Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric,
and/or transitive, where (x, y) ∈ R if and only if:
(a) x ̸= y. (c) x and y are both negative or both nonnegative.
(b) x ≡ y (mod 7).
6. Show that the relation R = ∅ on a nonempty set S is symmetric and transitive, but not reflexive.
7. Which relations in items 3 and 4 are irreflexive?
Remark. A relation R on the set A is irreflexive if for every a ∈ A, (a, a) ∈
/ R. That is, R is
irreflexive if no element in A is related to itself.
8. Which relations in items 3 and 4 are asymmetric?
Remark. A relation R is called asymmetric if (a, b) ∈ R implies that (b, a) ∈
/ R.
9. Let R be the relation R = {(a, b) | a < b} on the set of integers. Find:
(a) R−1 (b) R
Remark. Let R be a relation from a set A to a set B. The inverse relation from B to A, denoted
by R−1 , is the set of ordered pairs {(b, a) | (a, b) ∈ R}. The complementary relation R is the set of
ordered pairs {(a, b) | (a, b) ∈
/ R}.
10. Let R1 = {(1, 2), (2, 3), (3, 4)} and R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (3, 4)} be
relations from {1, 2, 3} to {1, 2, 3, 4}. Find:
(a) R1 ∪ R2 (b) R1 ∩ R2 (c) R1 − R2 (d) R2 − R1
11. Let R be the relation R = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 1)}, and let S be the relation
S = {(2, 1), (3, 1), (3, 2), (4, 2)}. Find S ◦ R.
12. These relations on the set of real numbers:
R1 = {(a, b) ∈ R2 | a > b}, the ”greater than” relation,
R2 = {(a, b) ∈ R2 | a ≥ b}, the ”greater than or equal to” relation,
R3 = {(a, b) ∈ R2 | a < b}, the ”less than” relation,
R4 = {(a, b) ∈ R2 | a ≤ b}, the ”less than or equal to” relation,
R5 = {(a, b) ∈ R2 | a = b}, the ”equal to” relation,
R6 = {(a, b) ∈ R2 | a ̸= b}, the ”unequal to” relation.
Find
a) R1 ∪ R3 c) R2 ∩ R4 e) R1 − R2
b) R1 ∪ R5 d) R3 ∩ R5 f) R2 − R1
13. Let R1 and R2 be the “divides” and “is a multiple of” relations on the set of all positive integers,
respectively. That is,
R1 = {(a, b) | a divides b}, R2 = {(a, b) | a is a multiple of b}.
Find:
(a) R1 ∪ R2 (c) R1 − R2 (e) R1 ⊕ R2
(b) R1 ∩ R2 (d) R2 − R1
14. Let R be the relation on the set {1, 2, 3, 4, 5} containing the ordered pairs
(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (3, 1), (3, 4), (3, 5), (4, 2), (4, 5), (5, 1), (5, 2), (5, 4).
Find:
(a) R2 (b) R3 (c) R4 (d) R5
Test Yourself
1. Determine whether the relation R on the set of all real numbers is reflexive, symmetric, antisymmetric,
and/or transitive,
(a) (x, y) ∈ R if and only if x − y ∈ Q.
(b) (x, y) ∈ R if and only if xy ≥ 0.
(c) (x, y) ∈ R if and only if x = 1 or y = 1.
2. Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric,
and/or transitive, where (x, y) ∈ R if and only if:
(a) xy ≥ 1. (b) x = y + 1 or x = y − 1. (c) x is a multiple of y.
3. Show that the relation R = ∅ on the empty set S = ∅ is reflexive, symmetric, and transitive.
4. Let R be the relation R = {(a, b) | a divides b} on the set of positive integers. Find:
(a) R−1 (b) R
5. Suppose that the function f from A to B is a one-to-one correspondence. Let R be the relation that
equals the graph of f , that is, R = {(a, f (a)) | a ∈ A}. What is the inverse relation R−1 ?
6. These relations on the set of real numbers:
R1 = {(a, b) ∈ R2 | a > b}, the ”greater than” relation,
R2 = {(a, b) ∈ R2 | a ≥ b}, the ”greater than or equal to” relation,
R3 = {(a, b) ∈ R2 | a < b}, the ”less than” relation,
R4 = {(a, b) ∈ R2 | a ≤ b}, the ”less than or equal to” relation,
R5 = {(a, b) ∈ R2 | a = b}, the ”equal to” relation,
R6 = {(a, b) ∈ R2 | a ̸= b}, the ”unequal to” relation.
Find
a) R2 ∪ R4 c) R3 ∩ R6 e) R3 − R6 g) R2 ⊕ R6
b) R3 ∪ R6 d) R4 ∩ R6 f) R6 − R3
7. Let R1 and R2 be the “congruent modulo 3” and the “congruent modulo 4” relations, respectively, on
the set of integers. That is,
R1 = {(a, b) | a ≡ b (mod 3)}, R2 = {(a, b) | a ≡ b (mod 4)}.
Find:
(a) R1 ∪ R2 (b) R1 ∩ R2 (c) R1 − R2 (d) R2 − R1 (e) R1 ⊕ R2
8. How many relations are there on a set with n elements that are:
(a) symmetric? (b) antisymmetric? (e) reflexive and symmetric?
9. Suppose that R and S are reflexive relations on a set A. Prove or disprove each of these statements:
(a) R ∪ S is reflexive. (c) R ⊕ S is irreflexive. (e) S ◦ R is reflexive.
(b) R ∩ S is reflexive. (d) R − S is irreflexive.
10. Show that the relation R on a set A is reflexive if and only if the inverse relation R−1 is reflexive.
More Complex Problems
1. Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric,
and/or transitive, where (x, y) ∈ R if and only if:
(a) x = y 2 . (b) x ≥ y 2 .
2. Give an example of a relation on a set that is:
(a) both symmetric and antisymmetric. (b) neither symmetric nor antisymmetric.
3. These relations on the set of real numbers:
R1 = {(a, b) ∈ R2 | a > b}, the ”greater than” relation,
R2 = {(a, b) ∈ R2 | a ≥ b}, the ”greater than or equal to” relation,
R3 = {(a, b) ∈ R2 | a < b}, the ”less than” relation,
R4 = {(a, b) ∈ R2 | a ≤ b}, the ”less than or equal to” relation,
R5 = {(a, b) ∈ R2 | a = b}, the ”equal to” relation,
R6 = {(a, b) ∈ R2 | a ̸= b}, the ”unequal to” relation.
Find
a) R1 ◦ R1 e) R1 ◦ R5 i) R2 ◦ R1 m) R5 ◦ R3
b) R1 ◦ R2 f) R1 ◦ R6 j) R2 ◦ R2 n) R3 ◦ R6
c) R1 ◦ R3 g) R2 ◦ R3 k) R3 ◦ R5 o) R4 ◦ R6
d) R1 ◦ R4 h) R3 ◦ R3 l) R4 ◦ R1 p) R6 ◦ R6