Discrete Mathematics Multiple Choice Questions on “Relations – Equivalence Classes and Partitions”.
1. Suppose a relation R = {(3, 3), (5, 5), (5, 3), (5, 5), (6, 6)} on S = {3, 5, 6}. Here R is known as _________
a) equivalence relation
b) reflexive relation
c) symmetric relation
d) transitive relation
Answer: a
Clarification: Here, [3] = {3, 5}, [5] = {3, 5}, [5] = {5}. We can see that [3] = [5] and that S/R will be {[3], [6]} which is a partition of S. Thus, we can choose either {3, 6} or {5, 6} as a set of representatives of the equivalence classes.
2. Consider the congruence 45≡3(mod 7). Find the set of equivalence class representatives.
a) {…, 0, 7, 14, 28, …}
b) {…, -3, 0, 6, 21, …}
c) {…, 0, 4, 8, 16, …}
d) {…, 3, 8, 15, 21, …}
Answer: a
Clarification: Note that a set of class representatives is the subset of a set which contains exactly one element from each equivalence class. Now, for integers n, a and b, we have congruence a≡b(mod n), then the set of equivalence classes are {…, -2n, -n, 0, n, 2n,…}, {…, 1-2n, 1-n, 1, 1+n, 1+2n,…}. The required answer is {…, 0, 7, 14, 28, …}.
3. Which of the following relations is the reflexive relation over the set {1, 2, 3, 4}?
a) {(0,0), (1,1), (2,2), (2,3)}
b) {(1,1), (1,2), (2,2), (3,3), (4,3), (4,4)}
c) {,(1,1), (1,2), (2,1), (2,3), (3,4)}
d) {(0,1), (1,1), (2,3), (2,2), (3,4), (3,1)
Answer: b
Clarification: {(1,1), (1,2), (2,2), (3,3), (4,3), (4,4)} is a reflexive relation because it contains set = {(1,1), (2,2), (3,3), (4,4)}.
4. Determine the partitions of the set {3, 4, 5, 6, 7} from the following subsets.
a) {3,5}, {3,6,7}, {4,5,6}
b) {3}, {4,6}, {5}, {7}
c) {3,4,6}, {7}
d) {5,6}, {5,7}
Answer: b
Clarification: {3,5}, {3,6,7}, {4,5,6}. It is not a partition because these sets are not pairwise disjoint. The elements 3, 5 and 6 appear repeatedly these sets. {1}, {2,3,6}, {4}, {5} – this is a partition as they are pairwise disjoint. {3,4,6}, {7} – this is not a partition as element 5 is missing.
{5,6}, {5,7} – this is not a partition because it is missing the elements 3, 4 in any of the sets.
5. Determine the number of equivalence classes that can be described by the set {2, 4, 5}.
a) 125
b) 5
c) 16
d) 72
Answer: b
Clarification: Suppose B={2, 4, 5} and B×B = (2,2), (4,4), (5,5), (2,4), (4,2), (4,5), (5,4), (2,5), (5,2). A relation R on set B is said to be equivalence relation if R is reflexive, Symmetric, transitive. Hence, total number of equivalence relation=5 out of 23=8 relations.
6. Determine the number of possible relations in an antisymmetric set with 19 elements.
a) 23585
b) 2.02 * 1087
c) 9.34 * 791
d) 35893
Answer: b
Clarification: Number of antisymmetric relation is given:-|A|=n, |AxA|=n xn. Then, N=total number of diagonal will n and we know that N = 2n * 3(n2-n)/2. So, the number of relations should be = 2.02 * 1087.
7. For a, b ∈ Z define a | b to mean that a divides b is a relation which does not satisfy ___________
a) irreflexive and symmetric relation
b) reflexive relation and symmetric relation
c) transitive relation
d) symmetric relation
Answer: b
Clarification: Suppose, a=0, then we know that 0 does not divide 0, 0 ∤ 0 and it is not reflexive. Again, 2 | 4 but 4 does not 2 and so it is not a symmetric relation.
8. Which of the following is an equivalence relation on R, for a, b ∈ Z?
a) (a-b) ∈ Z
b) (a2+c) ∈ Z
c) (ab+cd)/2 ∈ Z
d) (2c3)/3 ∈ Z
Answer: b
Clarification: Let a ∈ R, then a−a = 0 and 0 ∈ Z, so it is reflexive. To see that a-b ∈ Z is symmetric, then a−b ∈ Z -> say, a−b = m, where m ∈ Z ⇒ b−a = −(a−b)=−m and −m ∈ Z. Thus, a-b is symmetric. To see that a-b is transitive, let a, b, c ∈ R. Thus, a−b ∈ Z; b−c ∈ Z. Let a−b = i and b−c = j, for integers i,j ∈ Z. Then a−c ='(a−b)+(b−c)=i + j. So, a−c ∈ Z. Therefore a – c is transitive. Hence, (a-b) is an equivalence relation on the set R. Rest of the options are not equivalence relations.
9. Determine the set of all integers a such that a ≡ 3 (mod 7) such that −21 ≤ x ≤ 21.
a) {−21, −18, −11, −4, 3, 10, 16}
b) {−21, −18, −11, −4, 3, 10, 17, 24}
c) {−24, -19, -15, 5, 0, 6, 10}
d) {−23, −17, −11, 0, 2, 8, 16}
Answer: b
Clarification: For an integer a we have x ≡ 3 (mod 7) if and only if a = 7m + 3. Thus, by calculating multiples of 7, add 3 and restrict the value of a, so that −21 ≤ x ≤ 21. The set for a = {−21, −18, −11, −4, 3, 10, 17, 24}.
10. For a, b ∈ R define a = b to mean that |x| = |y|. If [x] is an equivalence relation in R. Find the equivalence relation for [17].
a) {,…,-11, -7, 0, 7, 11,…}
b) {2, 4, 9, 11, 15,…}
c) {-17, 17}
d) {5, 25, 125,…}
Answer: c
Clarification: We can find that [17] = {a ∈ R|a = 17} = {a ∈ R||a| = |17|} = {-17, 17} and [−17] = {a ∈ R|a = −17} = {a ∈ R||a| = |−17|}= {−17, 17}. Hence, the required equivalence relation is {-17, 17}.