Number of possible equivalence relations

Question

Consider the set $A = \{1, 2, 3, 4, 5\}$.

How many are the equivalence relations $R$ on $A$ such that $1 \,R\, 5$, $3 \,R\, 4$ and $5 \,\not R\, 4$? Motivate the answer.

I know that $1$ is in relation with $5$, $3$ is in relation with $4$ and $5$ is not in relation with $4$. How can I find the exact number of possible equivalence relations with these features? Should I try writing down all the cases? Even if I do how do I know when to stop?

I think the number of possible equivalence relations is three:

$\{\{1,5\},\{3,4\},\{2\}\}$,

$\{\{1,5,2\},\{3,4\}\}$,

$\{\{1,5\},\{3,4,2\}\}$.

Answer 1

Hint: Equivalence relations induce a partition and vice versa. If $R$ is an equivalence relation on $A$, then $\{ \{a \in A \mid a R b \} \mid b \in A \}$ is a partition of $A$ and conversely for a partition $X$ of $A$, $$ a R b \iff \exists x \in X \colon a,b \in x $$ is an equivalence relation.

Hence we may count the number of partitions $X$ of $A$ such that $1,5$ and $3,4$ lie in a common set of $X$ and $4,5$ lie in different elements.

The number of those is the same as the number of partitions of $A' = \{2,4,5\}$ where 4,5 lie in different sets of the partition. How many of those partitions do exist?

Answer 2

This is a 'motivational' answer.

Five people with names $1$ thru $5$ live in the USA. Consider the relation $x R y$ defined by $x$ lives in the same state as $y$.

Given the OP's info, we start with the relation/set decomposition

$\{1,5\} \text{ live in NY}$

$\{3,4\} \text{ live in CA}$

Hmm. so what state does $2$ live in? Since we have no other info, $2$ might live in $\text{NY}$,

ANS: $\{1,2,5\},\{3,4\}$

or perhaps $\text{CA}$,

ANS: $\{1,5\},\{2,3,4\}$

Of course if $2$ lives somewhere else we have

ANS: $\{1,5\},\{2\},\{3,4\}$