How many equivalence relations $S$ on $A$ are there for which $R⊆S$ ($R$ is an equivalence relation on a set $A$, with $4$ equivalence classes) 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⊆S$?
Thanks in advance
 A: Let's imagine $R$ is an equivalence relation on $A$ with four equivalence classes exactly. But for $R$ to have exactly four equivalence classes then $A$ must be a four-element set. For example
$A=\{a,b,c,d\}$
and $R=\{(a,a),(b,b),(c,c),(d,d)\}$
Then the four equivalence classes of $R$ are
$$[a] = \{a\}$$
$$[b] = \{b\}$$
$$[c] = \{c\}$$
$$[d] = \{d\}$$
Now, the reason your book says there are 15 total equivalence relations (which is the correct answer) is because $R$ is a subset of all possible equivalence relations (since each equivalence relation must be reflexive and will have all ordered pairs found in $R$).
It's easy to see that
$R=\{(a,a),(b,b),(c,c),(d,d)\}$
and that $R$ a subset of $R_1$ through $R_{15}$ below which is the total number of equivalence relations $S$ on $A$.
Thus you could list out all $15$ equivalence relations:
$$R_1=\{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a)\}\\
R_1=\{(a,a),(b,b),(c,c),(d,d),(a,c),(c,a)\}\\
R_2=\{(a,a),(b,b),(c,c),(d,d),(a,d),(d,a)\}\\
R_3=\{(a,a),(b,b),(c,c),(d,d),(b,c),(c,b)\}\\
R_4=\{(a,a),(b,b),(c,c),(d,d),(b,d),(d,b)\}\\
R_5=\{(a,a),(b,b),(c,c),(d,d),(c,d),(d,c)\}\\
R_6=\{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(a,c),(c,a),(b,c),(c,b)\}\\
\vdots\\
R_{15}\{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(a,c),(c,a),(b,c),(c,b),\cdots,(d,a),(a,d)\}$$
But this would take a long time!
It is easier to recognize that the total number of equivalence relations possible on a set is equal to the number of possible equivalence classes on a set. Knowing the number of equivalence classes can be determined by using Bell numbers. https://en.wikipedia.org/wiki/Bell_number
Since this is the bell number $B_{4}=15$ then $15$ is the answer.
A: Since R is a subset of S the equivalence classes can be the same as R or we can merge a few together. We can have S=R (1 case) or two equivalence classes merged(6 cases), or two merged and another  two merged (6 cases) or three merged(4 cases) or all of them merged together (1 case).
