The maximum number of equivalence relations on the set A = {1, 2, 3} are
Correct Answer :
5
Solution :
The correct option is 5.
An equivalence relation on a set is a relation that is reflexive, symmetric, and transitive.
There is a fundamental theorem in set theory: The number of equivalence relations on a set is equal to the number of partitions of that set .
A partition of a set is a collection of disjoint, non-empty subsets of whose union is . These subsets are called equivalence classes.
Given the set containing 3 elements, we want to find the number of ways to partition . We can group the partitions based on the number of subsets (equivalence classes) they contain:
1. Partition into 1 subset:
We place all elements into a single subset.
(This corresponds to the universal relation on ).
There is 1 such partition.
2. Partition into 2 subsets:
We partition the set into two subsets. This can be done by grouping one element in one subset and the other two elements in another subset. The possibilities are:
-
-
-
There are 3 such partitions.
3. Partition into 3 subsets:
Each element is placed in its own single-element subset.
(This corresponds to the identity relation on ).
There is 1 such partition.
Adding all the possibilities together, the total number of partitions (and thus the total number of equivalence relations) is:
Alternatively, the number of partitions of a set of size is given by the Bell number, .
For ,
For ,
For ,
For ,
Thus, the maximum number of equivalence relations on the set is 5.
Access expert-curated educational resources and study materials—completely free.
Create, conduct, and manage professional online assessments with Crey. Perfect for teachers and institutes.
Copyright © 2026 Crey. All Rights Reserved.