Suppose R is an equivalence relation on a set A with four eq

Suppose R is an equivalence relation on a set A, with four equivalence classes. How many different equivalence relations S on A are there for which R is a subset of S?

The answer is known to be 15, but this answer needs to be explained as to how it is true.

Hint: If R is contained in S (as sets of ordered pairs) then aRb implies aSb. So possibly more elements of A become equivalent to one another under S than under R. What effect does this have on the equivalence classes? How many different ways can you \"blend\" the equivalence classes of R to give equivalence classes of S?

Solution

It is given that R is having 4 equivalence classes.

It indirectly means that cardinality of A is 4 i.e., no. of elements of A is 4.

Let A = {1,2,3,4}

and let equivalence relation be R = {(1,1),(2,2),(3,3),(4,4)}

Now the four equivalence classes of R will be

[1] = {1}

[2] = {2}

[3] = {3}

[4] = {4}

Now that it is given R is subset of S,

We can form set S by keeping all the ordered pairs of R as it is and adding some more ordered pairs such that equivalence relation is satisfied.

So general form of S will be of the form

S=  {(1,1),(2,2),(3,3),(4,4),........}

Remaining elements can be choosen by merging the 4 equivalent classes in different ways.

No. of combinations can be

Same as R = 1

By merging two equivalence classes = 6

2 merged and another 2 merged = 3

3 merged = 4

all merged = 1

Total = 1 + 6 + 3 + 4 + 1 = 15