Quick answer: The smallest equivalence relation on a set A is the identity relation, which contains only the pairs (a, a) for every element a in A. On A = {1, 2, 3}, it is {(1,1), (2,2), (3,3)}. If a relation R is given, the smallest equivalence relation containing R is its reflexive, symmetric and transitive closure.
Many students learn the definition of an equivalence relation but get stuck when a question says “find the smallest equivalence relation.” This guide shows you exactly what that phrase means, how to solve both versions of the question, and how to avoid the usual mistakes. If you also practise aptitude and logic, you can pair it with [CAT mock tests https://www.catmock.com/ or visit the Cat Mock.
Key Takeaways
- The smallest equivalence relation on any set A is the identity relation. It has n pairs when A has n elements.
- The largest equivalence relation on A is the universal relation A x A, with n x n pairs.
- “Smallest equivalence relation containing R” is a different question. You solve it with the reflexive, symmetric and transitive closure of R.
- The number of equivalence relations on {1, 2, 3} is 5, which is the Bell number B3.
- Every equivalence relation matches exactly one partition of the set.
What Is an Equivalence Relation?
An equivalence relation on a set A is a relation that is reflexive, symmetric and transitive. In plain words, it groups elements that are “the same” in some sense. Equality, congruence of triangles and “has the same remainder when divided by 3” are common examples.
A relation R on A is a set of ordered pairs taken from the Cartesian product A x A. To be an equivalence relation, R must pass three tests:
- Reflexive: (a, a) is in R for every a in A.
- Symmetric: if (a, b) is in R, then (b, a) is in R.
- Transitive: if (a, b) and (b, c) are in R, then (a, c) is in R.
You can read a fuller definition in the Wikipedia article on equivalence relations or on Wolfram MathWorld. The standard school treatment is in the Class 12 Relations and Functions chapter of the NCERT textbooks.
What Is the Smallest Equivalence Relation?
The smallest equivalence relation on a set A is the identity relation I = {(a, a) : a in A}. Every equivalence relation must contain these pairs because of reflexivity, so no equivalence relation can be smaller. On a set with n elements, it has exactly n ordered pairs.
Let us check that the identity relation really is an equivalence relation.
- It is reflexive, because every (a, a) is in it by definition.
- It is symmetric, because the reverse of (a, a) is (a, a) itself.
- It is transitive, because the only chain is (a, a) and (a, a), which gives (a, a).
Now ask why nothing smaller works. Remove any pair (a, a) and reflexivity fails. So every equivalence relation on A contains the identity relation. That makes it the smallest one, and it is also the only equivalence relation with exactly n pairs.
Smallest overall vs. smallest containing R
These are two different questions, and mixing them up is the top source of lost marks.
- “Write the smallest equivalence relation on A” has one answer: the identity relation.
- “Find the smallest equivalence relation containing R” depends on the pairs already in R.
Smallest vs Largest Equivalence Relation
The smallest equivalence relation is the identity relation, where each element is related only to itself. The largest is the universal relation A x A, where every element is related to every element. Every other equivalence relation on A sits between these two.
The table below compares them side by side.
Table 1: Smallest vs largest equivalence relation
| Feature | Smallest | Largest |
|---|---|---|
| Name | Identity (diagonal) relation | Universal relation |
| Definition | {(a, a) : a in A} | A x A |
| Pairs on a set with n elements | n | n x n |
| Pairs on A = {1, 2, 3} | 3 | 9 |
| Equivalence classes | n classes, each with 1 element | 1 class with all n elements |
| Matching partition | All singletons | One single block |
| Contained in other equivalence relations? | Yes, it is inside every one of them | Yes, it contains every one of them |
| Everyday meaning | “Equal to” | “Belongs to the same set as” |
Notice the symmetry. The smallest relation relates nothing beyond what reflexivity forces. The largest relates everything. If you want the full list of what lies between them for three elements, jump to the section on the smallest equivalence relation in {1, 2, 3}.
How to Find the Smallest Equivalence Relation Containing a Given Relation
To find the smallest equivalence relation containing R, take the reflexive, symmetric and transitive closure of R. Add (a, a) for every a, add (b, a) for every (a, b), then add (a, c) whenever (a, b) and (b, c) are present. Repeat until no new pair appears.
Step-by-Step Method
- Write down the set A and the given relation R.
- Reflexive step: add (a, a) for every element a in A that is missing.
- Symmetric step: for every pair (a, b) in the list, add (b, a).
- Transitive step: whenever (a, b) and (b, c) are in the list, add (a, c).
- Repeat steps 3 and 4 until a full pass adds nothing new.
- Verify the final relation is reflexive, symmetric and transitive, and add nothing extra.
Why this method gives the smallest answer
The overlap (intersection) of any group of equivalence relations on A is again an equivalence relation. So if you intersect every equivalence relation that contains R, you get one that still contains R and is as small as possible. The closure method builds exactly that relation, and it adds only pairs that are forced.
A faster shortcut: link and group
You can also treat each pair in R as a link between two elements.
- Draw a point for each element of A.
- Join a and b whenever (a, b) is in R.
- Each connected group of points becomes one equivalence class.
- The smallest equivalence relation contains every ordered pair inside each group.
If the groups have sizes k1, k2, k3 and so on, the relation has k1 x k1 + k2 x k2 + k3 x k3 + … pairs. Singleton elements count as groups of size 1. You will use this shortcut in the examples below.
Smallest Equivalence Relation Example
The examples below move from easy to harder. Each one uses the same method, so work through them in order. All sets use plain-text notation, with A x A for the Cartesian product.
Example 1: Two links in a chain
Question: Let A = {1, 2, 3} and R = {(1,2), (2,3)}. Find the smallest equivalence relation containing R.
Solution:
- Reflexive step: add (1,1), (2,2), (3,3).
- Symmetric step: add (2,1) and (3,2).
- Transitive step: from (1,2) and (2,3) add (1,3). From (3,2) and (2,1) add (3,1).
- Check again. No new pair appears.
The result has all 9 pairs of A x A, so the smallest equivalence relation containing R is the universal relation. The link-and-group shortcut agrees: 1, 2 and 3 are all connected, so there is one group of size 3, and 3 x 3 = 9.
Example 2: One link only
Question: Let A = {1, 2, 3} and R = {(1,2)}. Find the smallest equivalence relation containing R.
Solution:
- Reflexive step: add (1,1), (2,2), (3,3).
- Symmetric step: add (2,1).
- Transitive step: the chains (1,2), (2,1) and (2,1), (1,2) only give (1,1) and (2,2), which are already there.
The answer is S = {(1,1), (2,2), (3,3), (1,2), (2,1)}. This has 5 pairs. The groups are {1, 2} and {3}, so 2 x 2 + 1 x 1 = 5.
Let us now verify S pair by pair.
Checking S = {(1,1), (2,2), (3,3), (1,2), (2,1)} for the three properties
| Pair in S | Reflexive check | Symmetric check | Transitive check |
|---|---|---|---|
| (1,1) | Needed, present | Its own reverse | (1,1), (1,2) gives (1,2), present |
| (2,2) | Needed, present | Its own reverse | (2,2), (2,1) gives (2,1), present |
| (3,3) | Needed, present | Its own reverse | (3,3), (3,3) gives (3,3), present |
| (1,2) | Not required | Reverse (2,1) is present | (1,2), (2,1) gives (1,1), present |
| (2,1) | Not required | Reverse (1,2) is present | (2,1), (1,2) gives (2,2), present |
Every check passes, so S is an equivalence relation. Since each pair in S was forced, nothing smaller will do.
Example 3: The relation is already the smallest
Question: Let A = {1, 2, 3} and R = {(1,1), (2,2), (3,3)}. Find the smallest equivalence relation containing R.
Solution: R is already reflexive, symmetric and transitive. Nothing needs to be added. The smallest equivalence relation containing R is R itself, which is the identity relation.
Example 4: Two separate links on four elements
Question: Let A = {1, 2, 3, 4} and R = {(1,2), (3,4)}. Find the smallest equivalence relation containing R and count its pairs.
Solution: Add the four reflexive pairs (1,1), (2,2), (3,3), (4,4). Add the symmetric pairs (2,1) and (4,3). Transitivity adds nothing new, because the two links never meet.
The result is {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (3,4), (4,3)}. That is 8 pairs. Shortcut check: groups {1, 2} and {3, 4} give 2 x 2 + 2 x 2 = 8.
Example 5: A longer chain with a separate link
Question: Let A = {1, 2, 3, 4, 5} and R = {(1,2), (2,3), (4,5)}. How many ordered pairs are in the smallest equivalence relation containing R?
Solution: Link 1 to 2 and 2 to 3, so {1, 2, 3} forms one group. Link 4 to 5, so {4, 5} forms another. No link joins the two groups.
Count the pairs: 3 x 3 + 2 x 2 = 9 + 4 = 13. The smallest equivalence relation containing R has 13 ordered pairs.
Smallest Equivalence Relation in 1, 2, 3 (Set A = {1, 2, 3})
The smallest equivalence relation on A = {1, 2, 3} is the identity relation {(1,1), (2,2), (3,3)}. The largest is A x A with 9 pairs. In between, there are three more equivalence relations, so the set {1, 2, 3} has exactly 5 equivalence relations in total.
This count is the Bell number B3. A Bell number counts the ways to split a set into non-empty groups, and B1 = 1, B2 = 2, B3 = 5, B4 = 15 and B5 = 52. You can read more about it on the Bell number page on Wikipedia.
Here is the complete list for {1, 2, 3}.
All equivalence relations on {1, 2, 3} and their partitions
| No. | Partition of A | Equivalence relation | Pairs |
|---|---|---|---|
| 1 | {1}, {2}, {3} | {(1,1), (2,2), (3,3)} | 3 (smallest) |
| 2 | {1, 2}, {3} | {(1,1), (2,2), (3,3), (1,2), (2,1)} | 5 |
| 3 | {1, 3}, {2} | {(1,1), (2,2), (3,3), (1,3), (3,1)} | 5 |
| 4 | {2, 3}, {1} | {(1,1), (2,2), (3,3), (2,3), (3,2)} | 5 |
| 5 | {1, 2, 3} | A x A (all 9 pairs) | 9 (largest) |
Two useful facts come from this table:
- Only two of the five relations contain the pair (1,2): number 2 and number 5. So the number of equivalence relations on {1, 2, 3} containing (1,2) is 2.
- The smallest one containing (1,2) is number 2, and it matches Example 2 above.
There is no equivalence relation with 4, 6, 7 or 8 pairs on this set. If you ever get one of those sizes in an answer, one of the three properties has failed.
Equivalence Classes and Partitions
An equivalence class of an element a is the set of all elements related to a. It is written [a] = {x in A : (a, x) is in R}. The classes of an equivalence relation never overlap, and together they cover the whole set. This is called a partition of the set.
This link between relations and partitions is what makes the topic easier. Instead of listing pairs, you can describe an equivalence relation by its groups.
- For the smallest equivalence relation, every class is a singleton. On {1, 2, 3}: [1] = {1}, [2] = {2}, [3] = {3}.
- For the largest, there is one class. On {1, 2, 3}: [1] = [2] = [3] = {1, 2, 3}.
- For Example 2, the classes are [1] = [2] = {1, 2} and [3] = {3}.
As a rule, every partition of a set gives exactly one equivalence relation, and every equivalence relation gives exactly one partition. That one-to-one match is why the number of equivalence relations on a set equals the number of its partitions. For more detail, see the pages on equivalence classes and the partition of a set.
To build the relation from a partition, put every ordered pair (x, y) in R when x and y lie in the same block. This is exactly the link-and-group shortcut from earlier.
Common Mistakes Students Make
The most common errors come from skipping a step or answering the wrong version of the question. Check this list before you submit an answer.
- Forgetting reflexive pairs for untouched elements. In Example 2, the element 3 is not in R, but (3,3) must still be added.
- Adding only half of a symmetric pair. If you add (1,2), you must also add (2,1).
- Stopping before transitivity is complete. After adding new pairs, check the chains again. New pairs can create more chains.
- Adding extra pairs “to be safe.” The smallest relation contains only pairs that are forced. Extra pairs make the answer wrong.
- Mixing up the two questions. “Smallest equivalence relation on A” is the identity relation. “Smallest containing R” depends on R.
- Calling the empty relation the smallest. On a non-empty set, the empty relation is not reflexive, so it is not an equivalence relation.
- Counting pairs wrongly. Count ordered pairs, so (1,2) and (2,1) are two different pairs.
Practice Questions with Answers
Try each question first, then check the answer below it. These cover all three question types: smallest overall, smallest containing R, and counting.
Q1. Write the smallest equivalence relation on A = {a, b, c, d}.
Answer: The identity relation {(a,a), (b,b), (c,c), (d,d)}, with 4 pairs.
Q2. Let A = {1, 2, 3} and R = {(1,3)}. Find the smallest equivalence relation containing R.
Answer: {(1,1), (2,2), (3,3), (1,3), (3,1)}. This has 5 pairs. The groups are {1, 3} and {2}.
Q3. Let A = {1, 2, 3, 4} and R = {(1,2), (1,3)}. How many ordered pairs are in the smallest equivalence relation containing R?
Answer: 10. The group {1, 2, 3} gives 3 x 3 = 9 pairs and {4} gives 1, so the total is 10.
Q4. Let A = {1, 2, 3, 4, 5} and R = {(1,2), (3,4)}. How many ordered pairs are in the smallest equivalence relation containing R?
Answer: 9. The groups are {1, 2}, {3, 4} and {5}, so 4 + 4 + 1 = 9.
Q5. How many equivalence relations on {1, 2, 3} contain (1,2)?
Answer: 2. They are the relation with partition {1, 2}, {3} and the universal relation A x A.
Want more practice with reasoning questions? Work through the PYQ hub, the CAT PYQ .
How Set Theory and Logic Help in Exam Preparation
Smallest equivalence relation questions belong to school and college mathematics. You should not expect this exact definition in aptitude-style entrance papers. But the thinking skills behind it carry over well to quantitative aptitude and DILR practice.
Here is how the skills connect:
- Grouping and classifying. Splitting a set into non-overlapping groups is the same skill you use in set and Venn-diagram questions.
- Chain reasoning. Transitivity is the idea behind “A is taller than B, B is taller than C” puzzles.
- Careful checking. Verifying three properties one by one builds the habit of checking every condition before answering.
If you are building these skills for management entrance exams, practise under timed conditions with CAT mock tests.
Frequently Asked Questions
What is the smallest equivalence relation on {1, 2, 3}?
The smallest equivalence relation on {1, 2, 3} is the identity relation {(1,1), (2,2), (3,3)}. It is reflexive because every element is related to itself. It is symmetric and transitive because it contains no pair that needs a reverse or a chain partner. It has exactly 3 pairs.
What is the largest equivalence relation on a set?
The largest equivalence relation on a set A is the universal relation A x A. It relates every element to every element, so it contains all n x n ordered pairs. On {1, 2, 3}, it has 9 pairs. Its only equivalence class is the whole set.
How many equivalence relations are there on a set with 3 elements?
There are 5 equivalence relations on a 3-element set. This equals the Bell number B3, which counts the ways to partition the set. They are one all-singletons relation, three relations that join exactly two elements, and one universal relation.
Is the empty relation an equivalence relation?
The empty relation is an equivalence relation only on the empty set. On any non-empty set, it fails reflexivity because pairs like (a, a) are missing. It is symmetric and transitive, but all three properties are needed.
Is the identity relation always an equivalence relation?
Yes. The identity relation on any set A is reflexive, symmetric and transitive. It relates each element only to itself, so every equivalence class has one element. That is why it is the smallest equivalence relation on A.
What is the difference between the smallest equivalence relation and the smallest one containing R?
The smallest equivalence relation on A is always the identity relation. The smallest one containing R is the closure of R, so it depends on the pairs in R. It always contains the identity relation, plus any symmetric and transitive pairs that R forces.
How do you count the pairs in the smallest equivalence relation containing R?
Join elements that appear together in a pair of R and find the connected groups. Square the size of each group and add the results. For groups of sizes 3 and 2, the count is 3 x 3 + 2 x 2 = 13 ordered pairs.
Developer note: Mark up with FAQPage schema.
Conclusion
The smallest equivalence relation on any set is the identity relation, because reflexivity forces every pair (a, a) and nothing else is required. On {1, 2, 3}, that is {(1,1), (2,2), (3,3)}. When a question gives you a relation R, switch to the closure method or the link-and-group shortcut.
Practise a few cases by hand, and always count ordered pairs carefully. For more aptitude and reasoning practice, explore the CatMock homepage, then continue with CAT PYQs and XAT PYQs.
