Question

How many equivalence relations are there on the set 1, 2, 3]?

Answer 1

Answer:

We need to find how many number of equivalence relations are on the set {1,2,3}

A relation is an equivalence relation if it is reflexive, transitive and symmetric.

equivalence relation R on {1,2,3}

1.For reflexive, it must contain (1,1),(2,2),(3,3)

2.For transitive, it must satisfy: if (x,y)∈R then (y,x)∈R

3. For symmetric, it must satisfy: if (x,y)∈R,(y,z)∈R then (x,z)∈R

Since (1,1),(2,2),(3,3) must be there is R, (1,2),(2,1),(2,3),(3,2),(1,3),(3,1). By symmetry,

we just need to count the number of ways in which we can use the pairs (1,2),(2,3),(1,3) to construct equivalence relations.

This is because if (1,2) is in the relation then (2,1) must be there in the relation.

the relation will be an equivalence relation if we use none of these pairs (1,2),(2,3),(1,3) . There is only one such relation: {(1,1),(2,2),(3,3)}

we can have three possible equivalence relations:

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

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

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