Let $A=\{1,2,3,4,5,6,7,8\}$ and let $R=\{(1,2),(5,4),(4,5),(6,2),(4,4),(6,5),(7,8)\}$ be a relation on A.
What it the number of equivalence relations $S$ that satisfies $R \subseteq S$
I know what an equivalence relation is, but I'm kinda lost in this exercise.. I have no idea how to calculate this. I know that if $(1,2) \in S$, then I'm committed to also take $(2,1)$.. but counting like this won't get me nowhere.
Can anyone show me how to solve this?
Many thanks.
Because of $R$, we must have $1=2=4=5=6$, $7=8$, and $3=3$. So there are at most three equivalence classes. You can also combine them in various ways, e.g. $1=2=4=5=6$ and $3=7=8$.