Find the number of equivalence relations on $\{1,2,3,4\}$ that contains $\{ (1,2), (3,4)\}$.

Question

Find the number of equivalence relations on $\{1,2,3,4\}$ that contains $\{ (1,2), (3,4)\}$.

What I've been doing:

I tried to find the matrix for that relation:

$\begin{pmatrix} 1 & 1 & * & *\\ 1 & 1 & * & * \\ * & * & 1 & 1 \\ * & * & 1 & 1 \end{pmatrix}$

Let $\Delta$ be the main diagonal for that matrix, so the number of ways to put $1$ or $0$s on $\Delta$ is $1^4$ (only one, because it's reflexive).

Then the number of ways to put $1$ or $0$s on $\bar \Delta$ (the numbers outside the main diagonal), such that the relation is simetric is $2^4$ ($4$ = the number of stars in my matrix such that they're eiher $0$ or $1$).

Now I don't have a clue how to count the number of transitive relations. My idea was to count all the reflexive, simetric and transitive relations and then multiply them (because of the product rule).

Answer 1

There is a one-to-one correspondence between equivalence relations on a set and partitions of that set. Since you already know $1$ and $2$ are in the same part and $3$ and $4$ are as well, you are left with just two possible partitions: the trivial partition and $\{\{1,2\},\{3,4\}\}$.