304 views

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

1. 8
2. 64
3. 5
4. 3

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 B0=B1=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

B0 = 1

B1= 1

B2= 2

B3= 5

B4= 15

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

@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.

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.

Got it. Thanks a lot, sir. :)

1 vote
1
179 views
1 vote