The number of non-empty equival ence relations on the set {1,2,3} is : (1)6 (2)7 (3)5 (4)4

🔍 What is an Equivalence Relation?

An equivalence relation on a set $S$ must satisfy three properties for every $a,b,c \in S$:

1. Reflexive: $a \sim a$
2. Symmetric: $a \sim b \Rightarrow b \sim a$
3. Transitive: $a \sim b \ \text{and}\ b \sim c \Rightarrow a \sim c$

These rules force the relation to behave like a "belongs to the same group" test.

🔗 Link to Partitions

A beautiful theorem says:

$\text{Equivalence relations on }S \;\longleftrightarrow\; \text{Partitions of }S$

• Each partition chops $S$ into non-overlapping, non-empty blocks (bags) whose union is $S$.
• Each block is an equivalence class.

Therefore, counting equivalence relations = counting partitions.

🧮 Counting Partitions of $\{1,2,3\}$

We need all the ways to split $\{1,2,3\}$ into bags:

1. Three singletons: $\{\{1\},\{2\},\{3\}\}$
2. One pair + one singleton (three possibilities):
   $\{\{1,2\},\{3\}\}$, $\{\{1,3\},\{2\}\}$, $\{\{2,3\},\{1\}\}$
3. One triple: $\{\{1,2,3\}\}$

Total = $1+3+1 = 5$.

These numbers are the Bell numbers. For $n=3$ the Bell number $B(3)=5$.

🎈 Imagine you have 3 colorful marbles: Red (1), Green (2) and Blue (3)

Your job is to put these marbles into bags so that:

1. Every marble must be in some bag (nobody is left on the table).
2. If Red and Green are in the same bag, then whenever you look at Green, Red must definitely be there too (so the bag rule works both ways).
3. Each marble always stays with itself in its own bag (sounds trivial – a bag always contains itself).

Every unique way of bagging the marbles is called a partition.
Mathematicians say each partition matches an equivalence relation.
So, the question is really asking: How many different ways can you bag the 3 marbles?
When you list them, you get exactly 5 ways.

Step-by-Step Solution

1. Recognize the Link
   Counting equivalence relations on a finite set $S$ is identical to counting partitions of $S$.

2. List All Partitions of $\{1,2,3\}$

   [ \begin{aligned} &\text{(i) } {{1},{2},{3}} \ &\text{(ii) } {{1,2},{3}} \ &\text{(iii) } {{1,3},{2}} \ &\text{(iv) } {{2,3},{1}} \ &\text{(v) } {{1,2,3}} \end{aligned} ]

3. Count Them
   There are $5$ distinct partitions.

4. Conclude
   Hence, the number of non-empty equivalence relations on $\{1,2,3\}$ is

   $5$

5. Match with Options
   Option (3) 5 is correct.