Question

How many equivalence classes can be made form {1,2,3}?

a. 3

b. 5

c. 7

d. 8

 

How to solve this type of Questions?

Answer 1

Let $A =\left \{ 1,2,3 \right \}$

$A\times A ={ (1,1) (2,2) (3,3) (1,2) (2,1) (2,3) (3,2) (1,3) (3,1) }$

A relation $R$ on set  $A$ is said to be Equivalence relation if $R$ is

(1)Reflexive                                     (2)Symmetric                             (3)Transitive  

For all Equivalence relation, all $(x R x) \forall A \varepsilon A$  should be present which is Reflexive Relation property.

For Equivalence relation at least ${ (1,1) (2,2) (3,3) }$ elements should be present.

Now For remaining elements ${ (1,2) (2,1) (2,3) (3,2) (1,3) (3,1) }$

According to Symmetric Relation if $(xRy)$ then $(yRx) \forall x,y\varepsilon A \\$

Hence, for all 3 pairs, $(1,2) (2,1) , (2,3) (3,2) ,(1,3) (3,1)$we have 2 choices either it can include or it can't include.

Number of relation of these type=$2^{3}=8$

$R_{1}=\left \{ (1,1)(2,2)(3,3) \right \} \ \ \ R{\color{Green} \checkmark} \ \ \ S {\color{Green} \checkmark} \ \ \ T{\color{Green} \checkmark}$

$R_{2}=\left \{ (1,1)(2,2)(3,3)(1,2) (2,1)\right \}\ \ \ R{\color{Green} \checkmark} \ \ \ S {\color{Green} \checkmark} \ \ \ T{\color{Green} \checkmark}$

$R_{3}=\left \{ (1,1)(2,2)(3,3) (1,3)(3,1)\right \}\ \ \ R{\color{Green} \checkmark} \ \ \ S {\color{Green} \checkmark} \ \ \ T{\color{Green} \checkmark}$

$R_{4}=\left \{ (1,1)(2,2)(3,3) (2,3)(3,2)\right \}\ \ \ R{\color{Green} \checkmark} \ \ \ S {\color{Green} \checkmark} \ \ \ T{\color{Green} \checkmark}$

$R_{5}=\left \{ (1,1)(2,2)(3,3)(1,2) (2,1) (1,3)(3,1)\right \}\ \ \ R{\color{Green} \checkmark} \ \ \ S {\color{Green} \checkmark} \ \ \ T{\color{Red} \times}$

$R_{6}=\left \{ (1,1)(2,2)(3,3) (1,2)(2,1)(2,3)(3,2)\right \}\ \ \ R{\color{Green} \checkmark} \ \ \ S {\color{Green} \checkmark} \ \ \ T{\color{Red} \times}$

$R_{7}=\left \{ (1,1)(2,2)(3,3) (1,3)(3,1)(2,3)(3,2)\right \}\ \ \ R{\color{Green} \checkmark} \ \ \ S {\color{Green} \checkmark} \ \ \ T{\color{Red} \times}$

$R_{8}=\left \{ (1,1)(2,2)(3,3)(1,2) (2,1) (1,3)(3,1)(2,3)(3,2)\right \}\ \ \ R{\color{Green} \checkmark} \ \ \ S {\color{Green} \checkmark} \ \ \ T{\color{Green} \checkmark}$

Here we can see relation $R_{5}$,$R_{6}$ and $R_{7}$ are failed to satisfy the properties of transitive relation.

Hence, total number of equivalence relation=5

Option(B) 5 is the correct choice.                                                            

Comments

But there is a theorem which says : 

Corresponding to every equivalent relation there is an equivalent partitioning of the set..

So our task basically is to find no of of unordered partitions of set S = {1,2,3} ..Corresponding to each of which we will have an equivalence relation..

So if in partition we have equivalence classes having each class size = 1

So no of unordered partitions  = 3! / (1)³ 3!    =   1

If we partition such that one class is having 2 elements and other one , then no of ways = 3! / (2!)  = 3

And finally if we have only one equivalence class then no of ways = 3! /  3! = 1

So total no of ways of partitioning the set = 5

So no of equivalence relations                = 5

Correct me if I m wrong somewhere..

---

We can also use the concept of Bell no.

Which will also result 5.

Ref:- https://en.wikipedia.org/wiki/Bell_number

---

How many equivalence classes can be made form {1,2,3}?

is no. of equivalence classes and equivalence relation same ?