558 views
1 votes
1 votes
Find the total number of equivalent relations possible on a set S={4,7,1}.

is there any other way to solve it without using bell formula?

2 Answers

Best answer
6 votes
6 votes

Bell formula is something complicated to remember..For smaller number of numbers , we can apply some basic combinatorics and the following fact :

No of equivalence relations = No of unordered partitions of the given set

Hence as the given set contains 3 elements , hence these can be partitioned in 3 possible ways..Lets find no of ways for each sort of unordered partition :

a)  1 partition containing all 3 elements  :  For this we have no of ways  =  3! / 3! = 1 way

b)  2 partitions , one containing 1 and other containing 2 elements : = 3! / (2! * 1!)  =  3 ways

c)  3 partitions , each containing 1 element    :    3! / ((1!)3 * 3!)   =   1  way

Hence total number of ways  =  1 + 3 + 1  =  5 ways

Hence no of equivalence relations for given set   =   5

EDIT : HOW TO FIND EQUIVALENCE RELATION GIVEN A PARTITION :                                                                                 ------------------------------------------------------------------------------------------------------------

To find the individual equivalence relations, we consider each partition one by one as :

For a given partition of set we consider cross product of each partition with itself in order to get the pairs of equivalence relation.

So , for example :

Consider the partition p  =  { {4,7} , {1} }

So equivalence relation will be constructed as indiviual cross products of p which is : {4,7} X {4,7}  and {1} X {1}

So on doing {4,7} X {4,7} , we get :   { (4,4) , (4,7) , (7,4) , (7,7) } and  { (1,1) } from second one doing union of which we get the equivalence relation as :    {  (4,4) , (4,7) , (7,4) , (7,7) , (1,1) } 

So equivalence relation corresponding to the partition { {4,7} , {1} } is :   {  (4,4) , (4,7) , (7,4) , (7,7) , (1,1) } .

Similarly we proceed for other partitions to find their corresponding equivalence relations 

edited by

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
2
Çșȇ ʛấẗẻ asked Mar 20, 2023
369 views
how to write if and only if symbolic form explain in detail????
0 votes
0 votes
0 answers
3
curious mind asked Jan 1, 2023
310 views
A relation R1 : aRb iff (a congruent b) modulo 5 and relation R2 : aRb iff (a congruent b modulo 7). What will be R1 U R2 ?
1 votes
1 votes
1 answer
4
dutta18 asked Dec 9, 2022
345 views
How to do this Boolean multiplication? And which Boolean law is applicable here ?( P' + Q ) ( Q' + P )