Equivalence Classes & Partitions Questions and Answers

This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer

Answer: a
Explanation: 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, …}
View Answer

Answer: a
Explanation: 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)
View Answer

Answer: b
Explanation: {(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}
View Answer

Answer: b
Explanation: {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
View Answer

Answer: b
Explanation: 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 2³=8 relations.

Note: Join free Sanfoundry classes at Telegram or Youtube

6. Determine the number of possible relations in an antisymmetric set with 19 elements.
a) 23585
b) 2.02 * 10⁸⁷
c) 9.34 * 7⁹¹
d) 35893
View Answer

Answer: b
Explanation: Number of antisymmetric relation is given:-|A|=n, |AxA|=n xn. Then, N=total number of diagonal will n and we know that N = 2ⁿ * 3^(n²-n)/2. So, the number of relations should be = 2.02 * 10⁸⁷.

7. For a, b ∈ Z deﬁne 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
View Answer

Answer: b
Explanation: Suppose, a=0, then we know that 0 does not divide 0, 0 ∤ 0 and it is not reﬂexive. 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) (a²+c) ∈ Z
c) (ab+cd)/2 ∈ Z
d) (2c³)/3 ∈ Z
View Answer

Answer: b
Explanation: 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 -&gt 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}
View Answer

Answer: b
Explanation: 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 deﬁne 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,…}
View Answer

Answer: c
Explanation: 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}.

Sanfoundry Global Education & Learning Series – Discrete Mathematics.

To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

« Prev - Discrete Mathematics Questions and Answers – Relations – Partial Orderings

» Next - Discrete Mathematics Questions and Answers – Graphs – Diagraph

Related Posts:

Recommended Articles: