Number of possible equivalence relations 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\}\}$.
 A: 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?
A: 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\}$
