GATE Overflow | Mathematics | Test 1 | Question: 22

Question

Total number of Equivalent Relations that can be defined on set $\{1,2,3\}$ ?

• A. 8   
• B. 64   
• C. 5     
• D. 3
   

Answer 1

Number of equivalence relations = number of partitions

Number of partitions can be given by using Bell Number.

For smaller numbers we can construct Bell's triangle by taking B₀=B₁=1.

Than by taking the last number of the previous row as the starting number in the next row, adding the numbers column wise and writing it next.

eg:

1

1   2

2   3   5

5   7    10   15

B₀ = 1

B₁= 1

B₂= 2

B₃₌ 5

B_{4= 15}

Answer 2

No of equivalance classes are nothing but Bell Number.
Bell Number for 3 number is 5.

Comments

@bikram sir,
Equivalent relation means it should be reflexive, symmetric and transitive. Here we have {1,2,3}.

So for it to be reflexive we should have {1,1},{2,2},{3,3}. This can be done in 1 way.

And any combination of the following 3 groups can be present:- This can be done in 8 ways.

1) {1,2},{2,1}

2) {1,3},{3,1}

3) {2,3},{3,2}

So total 8*1 = 8 ways...but how is the answer 5? Please explain.

---

@shraddha

Yes, it is correct that Equivalent relation means it should be reflexive, symmetric and transitive . 

​​​​​​​but the question says - number of equivalence relation on a given set . And number of equivalence relation on set is same as the number of disjoint partition of a set. 

go through it https://www.quora.com/How-many-equivalence-relations-on-the-set-1-2-3-containing-1-2-2-1-are-there-in-all

---

Got it. Thanks a lot, sir. :)