Q.The maximum number of equivalence relations on the set $A = \{1, 2, 3\}$ are
(A) 1
(B) 2
(C) 3
(D) 5

Concept: Relation Counting — Equivalence relations correspond to partitions of the set.

Step 1: An equivalence relation on $A$ is determined by how we partition $A$ into disjoint, non-empty subsets (the equivalence classes).

Step 2: List all possible partitions of $\{1,2,3\}$:

• One block: $\{\{1,2,3\}\}$ — 1 partition.
• Two blocks: $\{\{1\},\{2,3\}\}$, $\{\{2\},\{1,3\}\}$, $\{\{3\},\{1,2\}\}$ — 3 partitions.
• Three blocks: $\{\{1\},\{2\},\{3\}\}$ — 1 partition. …

The key idea: equivalence relations and partitions are the same thing. Every equivalence relation on a set splits the set into disjoint, non-empty subsets called equivalence classes. Conversely, every partition gives you an equivalence relation (two elements are related if they belong to the same block). So counting equivalence relations is exactly counting partitions.

For a 3-element set, we can systematically list all possible ways to group the elements.

1. One block (all elements together)

   Only one partition: $\{1,2,3\}$. This gives the equivalence relation where every element is related to every other. That's 1 relation.

2. Two blocks (one block of size 2, one block of size 1)

   We choose which two elements go together. The possibilities:

   • $\{1,2\}$ and $\{3\}$
   • $\{1,3\}$ and $\{2\}$
   • $\{2,3\}$ and $\{1\}$ That's 3 partitions, hence 3 relations.

3. Three blocks (each element alone)

   Only one partition: $\{1\}, \{2\}, \{3\}$. This is the equality relation (each element related only to itself). That's 1 relation.

Adding them up: $1 + 3 + 1 = 5$. …

Method: Counting equivalence relations via partitions

Use this whenever you must count the number of equivalence relations on a small finite set.

Steps

Step 1: Use the equivalence-relation = partition correspondence.

Every equivalence relation splits the set into disjoint non-empty blocks (equivalence classes), and every such partition gives back exactly one equivalence relation. So counting equivalence relations means counting partitions — never counting all relations.

Step 2: Organise partitions by block-size pattern.

List the ways to break the set into blocks, grouped by how many blocks and their sizes. For a $3$-element set: one block of $3$; a $2+1$ split; three singletons.

Step 3: Count the arrangements within each pattern. …

Common Mistakes

Mistake 1: Counting all relations instead of equivalence relations.

Why it's wrong: there are $2^{3\times 3}=512$ relations on $\{1,2,3\}$, but only those that are reflexive, symmetric AND transitive count — a far smaller number. Correct approach: count partitions of the set, which correspond one-to-one with equivalence relations.

Mistake 2: Missing some partitions of the $2+1$ type. …