CS1231(S) Tutorial 8: Relations
Solutions
National University of Singapore
2019/20 Semester 1
The questions marked with an asterisk ∗ are more challenging ones intended for discussion
purposes during the tutorial class. The other questions are regular ones. Please attempt all
questions before the tutorial class.
1. Let A = {1, 2, . . . , 10} and B = {2, 4, 6, 8, 10, 12, 14}. We define a relation R from A to
B by: for all a ∈ A and b ∈ B, a R b if and only if a is a prime and divides b.
(a) Find the subset R of A × B. Your answer should list down all the elements of R.
(b) Find R−1 . You answer should list down all the elements of R−1 .
Solution.
(a) R = {(2, 2), (2, 4), (2, 6), (2, 8), (2, 10), (2, 12), (2, 14), (3, 6), (3, 12), (5, 10), (7, 14)}.
(b) R−1 = {(2, 2), (4, 2), (6, 2), (8, 2), (10, 2), (12, 2), (14, 2), (6, 3), (12, 3), (10, 5), (14, 7)}.
2. Let A be a non-empty set.
(a) Explain briefly why ∅ is a relation on A.
(b) Determine if ∅ is (as a relation on A) reflexive, symmetric, or transitive.
Solution.
(a) Every subset of A × A is a relation on A, and ∅ is a subset of A.
(b) Since A is non-empty, there exists a ∈ A. Since (a, a) ∈ / ∅, ∅ is not reflexive.
However ∅ is both symmetric and transitive since the following two statements
are true as their hypotheses are false:
∀x, y ∈ A (x, y) ∈ ∅ → (y, x) ∈ ∅
∀x, y, z ∈ A (x, y), (y, z) ∈ ∅ → (x, z) ∈ ∅
3. Let R be a relation on a set A. Show that R is symmetric if and only if R = R−1 .
Solution.
R is symmetric ⇔ ∀x, y ∈ A (x R y → y R x)
⇔ ∀x, y ∈ A (x R y ↔ y R x)
⇔ ∀x, y ∈ A (x, y) ∈ R ↔ (y, x) ∈ R
⇔ ∀x, y ∈ A (x, y) ∈ R ↔ (x, y) ∈ R−1
⇔ R = R−1 .
1
Solutions
National University of Singapore
2019/20 Semester 1
The questions marked with an asterisk ∗ are more challenging ones intended for discussion
purposes during the tutorial class. The other questions are regular ones. Please attempt all
questions before the tutorial class.
1. Let A = {1, 2, . . . , 10} and B = {2, 4, 6, 8, 10, 12, 14}. We define a relation R from A to
B by: for all a ∈ A and b ∈ B, a R b if and only if a is a prime and divides b.
(a) Find the subset R of A × B. Your answer should list down all the elements of R.
(b) Find R−1 . You answer should list down all the elements of R−1 .
Solution.
(a) R = {(2, 2), (2, 4), (2, 6), (2, 8), (2, 10), (2, 12), (2, 14), (3, 6), (3, 12), (5, 10), (7, 14)}.
(b) R−1 = {(2, 2), (4, 2), (6, 2), (8, 2), (10, 2), (12, 2), (14, 2), (6, 3), (12, 3), (10, 5), (14, 7)}.
2. Let A be a non-empty set.
(a) Explain briefly why ∅ is a relation on A.
(b) Determine if ∅ is (as a relation on A) reflexive, symmetric, or transitive.
Solution.
(a) Every subset of A × A is a relation on A, and ∅ is a subset of A.
(b) Since A is non-empty, there exists a ∈ A. Since (a, a) ∈ / ∅, ∅ is not reflexive.
However ∅ is both symmetric and transitive since the following two statements
are true as their hypotheses are false:
∀x, y ∈ A (x, y) ∈ ∅ → (y, x) ∈ ∅
∀x, y, z ∈ A (x, y), (y, z) ∈ ∅ → (x, z) ∈ ∅
3. Let R be a relation on a set A. Show that R is symmetric if and only if R = R−1 .
Solution.
R is symmetric ⇔ ∀x, y ∈ A (x R y → y R x)
⇔ ∀x, y ∈ A (x R y ↔ y R x)
⇔ ∀x, y ∈ A (x, y) ∈ R ↔ (y, x) ∈ R
⇔ ∀x, y ∈ A (x, y) ∈ R ↔ (x, y) ∈ R−1
⇔ R = R−1 .
1
