Pass from partition to the equivalence relations

Question

I have a set $A = \{ 1, 2, 3\}$, which possible partitions are:

$P_0 = \{ \{1, 2, 3 \} \}$

$P_1 = \{ \{1, 2 \}, \{3 \} \}$

$P_2 = \{ \{1 \}, \{2, 3 \} \}$

$P_3 = \{ \{1, 3 \}, \{2 \} \}$

$P_4 = \{ \{1 \}, \{2 \}, \{3 \} \}$

How can I find the equivalence relations corresponding to each partition? If I had not the partitions, how would I find the equivalence relations?

Answer 1

If $\mathcal P\subseteq \wp(A)$ denotes a partition of set $A$ then the corresponding equivalence relation on $A$ is determined by: $$xRy\iff x\text{ and }y\text{ belong to the same element of }\mathcal P$$

If you must find all equivalence relations on a set $A$ then I advice you to start always by finding all partitions (as you did here).

---

Example: $\mathcal P=\{\{1,3\},\{2\}\}$.

$R=\{\langle 1,1\rangle,\langle 1,3\rangle,\langle 3,1\rangle,\langle 3,3\rangle,\langle 2,2\rangle\}$

$1$ and $1$ both belong to $\{1,3\}$, $1$ and $3$ both belong to $\{1,3\}$,..., et cetera

Answer 2

Hint: Prove the following reasonably easy

If a set $\;A\;\;$ is partioned by $\;\left\{\;\;A_i\;:\;\;i\in I\;\right\}\;$ , then the equivalence relation determined by this partition is

$$x\sim y\iff \exists\;i\in I\;\;s.t.\;\;x,y\in A_i$$

Namely: prove the above indeed is an equivalence relation whose equivalence classes are exactly the sets $\;A_i\;$ .