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).


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\}\}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.