On this page
You do not need to test hundreds of relations one by one. Every equivalence relation is a way of cutting the set into groups, so you count the groupings instead.
What is an equivalence relation, in one line?
In the NCERT Class 12 textbook, a relation R in a set A is said to be an equivalence relation if R is reflexive, symmetric and transitive (NCERT Mathematics Class 12, Chapter 1). The same chapter shows that an equivalence relation divides the set into mutually disjoint subsets called equivalence classes, and notes that you can go in reverse too, building an equivalence relation from a subdivision of the set.
That two-way link is the counting method: each equivalence relation matches exactly one partition into non-empty, non-overlapping groups. To test the three properties first, see our guide to reflexive, symmetric and transitive relations in Class 12.
How many equivalence relations are there on a set of 3 elements?
Take A = {1, 2, 3}. A relation in A is any subset of A × A (NCERT, Chapter 1), and A × A has 9 pairs, so there are 2^9 = 512 relations in all. Only five of them are equivalence relations, one for each way to group the elements:
{1, 2, 3} together: the universal relation, all 9 pairs.
{1, 2} and {3}: the three pairs (a, a) plus (1, 2) and (2, 1).
{1, 3} and {2}: the three pairs (a, a) plus (1, 3) and (3, 1).
{2, 3} and {1}: the three pairs (a, a) plus (2, 3) and (3, 2).
{1}, {2}, {3} apart: only (1, 1), (2, 2), (3, 3), the identity relation.
The Online Encyclopedia of Integer Sequences describes the Bell numbers as both the number of ways to partition a set of n labelled elements and the number of equivalence relations on such a set (OEIS A000110). For n = 3 it is 5, matching the list.
How many equivalence relations are on a set of 4 elements?
For {1, 2, 3, 4}, sort groupings by number of groups. The Stirling numbers of the second kind count partitions of an n-set into k non-empty subsets, and for n = 4 they are 1, 7, 6, 1 (OEIS A008277). In words:
One group: {1, 2, 3, 4}, 1 way.
Two groups: a 3 and a 1 (4 ways, pick the loner) or a 2 and a 2 (3 ways, pair 1 with 2, 3 or 4), 7 ways.
Three groups: one pair and two singletons, choose the pair in 4C2 = 6 ways.
Four groups: all apart, 1 way.
The total is 1 + 7 + 6 + 1 = 15 equivalence relations, which is the Bell number for n = 4 (OEIS A000110). The diagram at the top of this post draws all 15.
OEIS also gives a recurrence, B(n+1) = sum over k from 0 to n of nCk × B(k). With B(0) = B(1) = 1 and B(2) = 2, you get B(3) = 1 + 2 + 2 = 5 and B(4) = 1 + 3 + 6 + 5 = 15. For five elements the count jumps to 52.
Counting reflexive or symmetric relations needs other formulas; see counting relations and functions between finite sets.
How many equivalence relations contain a given pair?
If the relation must contain (1, 2), then 1 and 2 share a group. Glue them into one item and count partitions of what is left.
On {1, 2, 3}, containing (1, 2): glue 1 and 2, leaving two items, so B(2) = 2 relations, namely {1, 2}{3} and {1, 2, 3}.
On {1, 2, 3, 4}, containing (1, 2): three items remain, so B(3) = 5.
On {1, 2, 3, 4}, containing (1, 2) and (3, 4): two items remain, so B(2) = 2.
On {1, 2, 3, 4}, containing (1, 2) and (2, 3): 1, 2 and 3 become one item, plus 4, so again 2.
What is the smallest equivalence relation containing given pairs?
Say A = {1, 2, 3, 4} and you must include (1, 2) and (2, 3). Work in four steps:
Mark who is linked: 1 to 2, and 2 to 3.
Follow the chains: transitivity puts 1, 2 and 3 in one class.
Any element not mentioned, here 4, sits alone.
Write every pair inside each class, including (a, a) for every element of A.
The classes are {1, 2, 3} and {4}, so the relation is all 9 ordered pairs from {1, 2, 3} plus (4, 4), which is 10 pairs. Quick check: a class of size s contributes s × s pairs.
If Cartesian products feel shaky, revise sets and types of relations from Class 11. For practice, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer, so you can see where your count went wrong.
