in Set Theory & Algebra
304 views
3 votes
3 votes

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

  1. 8   
  2. 64   
  3. 5     
  4. 3
     
in Set Theory & Algebra
by
304 views

2 Answers

3 votes
3 votes
Best answer

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

selected by
1 vote
1 vote
No of equivalance classes are nothing but Bell Number.
Bell Number for 3 number is 5.

4 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.
0
0

@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

1
1
Got it. Thanks a lot, sir. :)
0
0
Answer:

Related questions