Isomorphic equivalence relations and partitions

elementary-set-theoryequivalence-relationsrelations

Let $R_1$, $R_2$ $∈ R(X)$ be equivalence relations on $X$. Define $R_1$ and $R_2$ to be isomorphic
if there exists a bijection $f : X → X$ such that the following holds:

For all $y$, $z ∈ X : (y, z) ∈$ $R_1$ if and only if $(f(y), f(z)) ∈$ $R_2$.

$(a)$ Define what it means for two partitions $P_1$, $P_2$ $∈ P(X)$ to be isomorphic. (An answer to this
is correct if it lets you prove the next part.)

$(b)$ Prove two equivalence relations $R_1 and R_2$ are isomorphic if and only if the partitions $φ$($R_1$)
and $φ$($R_2$) are isomorphic. (Here $φ$ is the bijection from the previous problem.)

(c) Let $X = \{1, 2, 3, 4, 5\}$. Up to isomorphism, how many equivalence relations are there on $X$?

My attempt:
As I understand it, equivalence relations can be put in a bijection with partitions, and so if there is a bijection between elements of one relation to another, then there is a bijection between elements of one partition with another. This would make the partitions fit the definition of isomorphism mentioned in the question, therefore proving $(b)$.
I do not understand what $(c)$ is asking at all, and I am looking for a formal proof/way to write what I am thinking if what I'm thinking is correct at all.

Best Answer

Hint: In c) one requires to enumerate all partitions of the set $X$ (up to isomorphism). First calculate the number of partitions of $X$. This is the Bell number $B(5)$, where $B(n) = \sum_{k=1}^n S(n,k)$ and $S(n,k)$ is the number of partitions of $n$ into $k$ parts (Stirling number of the 2nd kind).

We have $B(1)=1$, with partition $\{\{1\}\}$,

$B(2)=2$ with partitions $\{\{1,2\}\}$, $\{\{1\},\{2\}\}$,

$B(3)=5$ with partitions $\{\{1\},\{\{2\},\{3\}\}$, $\{\{1,2\},\{3\}\}$, $\{\{1,3\},\{2\}\}$, $\{\{2,3\},\{1\}\}$, $\{\{1,2,3\}\}$, and so on.

In view of the isomorphism classes, you just need to consider the types of partitions (see comment below).

BY REQUEST: For instance, take the bijection $f=\left(\begin{array}{ccc}1&2&3\\2&3&1\end{array}\right)$. Then the partition $\{\{1,2\},\{3\}\}$ is mapped to the partition $\{\{f(1),f(2)\},\{f(3)\}\} = \{\{2,3\},\{1\}\}$.