Bijective function from relations of equivalency set to partitions set

Question

I am proving that f: R->P, a function that associates a relation of equivalency to a partition is bijective. Let g: P->R. I showed that g(p=partition of X)={(a,b) belonging to X²| exists A belonging to p such as a,b belong to A} and i showed that g(p) is a relation of equivalency. I need to prove that g•f= identity of R and f•g= identity or P.

Answer 1

I would approach this problem in a slightly different way. I would construct the function and then prove it's one to one and onto.

---

Consider the set $X$.
Recall that an equivalence relation $R$ in $X$ is a subset of $X^2$ such that \begin{gather} \forall a\in X\,\colon(a,a)\in R\\ \forall a,b\in X\,\colon (a,b)\in R\Rightarrow (b,a)\in R\\ \left[(a,b)\in R\right]\wedge \left[(b,c)\in R \right]\Rightarrow (a,c)\in R \end{gather} Now, consider some $a\in X$, the equivalence class of $a$ is the subset $Ra$ of $X$ given by \begin{equation} Ra=\left\{b\in X\, \lvert \, (b,a)\in R\right\} \end{equation}

And a partition of $X$ is a covering $\left\{ A_\alpha\, \lvert \,\alpha \in I\right\}$ of $X$ such that $A_\alpha \cap A_\beta =\varnothing$ if and only if $\alpha \neq \beta$.
Covering just means that $\bigcup_{\alpha\in I} A_\alpha =X$.

Remark: The collection of sets $\left\{Ra\, \lvert \, a\in X\right\}$ is a partition of $X$ (using the relation $R$ as the 'equal' for the index $a$). This follows directly from the fact that $Ra =Rb$ if and only if $(a,b)\in R$.

With this definitions in mind, we want to show that there exists a bijective function $f$ from the set of equivalence relations in $X$ and the partitions of $X$.

---

So, for the proof:

Let $R$ be an equivalence relation in $X$. We claim that the map \begin{equation} R\mapsto \left\{Ra\, \lvert \, a\in X\right\} \end{equation} is the desired bijection.

Proof that $f$ is one to one:
Let $R$ and $S$ be equivalence relations in $X$, then, if $f(R)\neq f(S)$, it would mean that there exists (without losing generality) some $Rb$ in $ \left\{Ra\, \lvert \, a\in X\right\}$ such that $Rb$ is not in $\left\{Sa\, \lvert \, a\in X\right\}$, this meaning that $R\neq S$.

Proof that $f$ is onto:
Suppose $\left\{ A_\alpha\, \lvert \,\alpha \in I\right\}$ is a partition of $X$. It can be shown that the following is an equivalence relation \begin{equation} R = \bigcup\left\{ A_\alpha \times A_\alpha \,\lvert\, \alpha \in I \right\} \end{equation} And the equivalence classes would have the form $\left\{ A_\alpha\, \lvert \,\alpha \in I\right\}$. Hence $f(R)=\left\{ A_\alpha\, \lvert \,\alpha \in I\right\}$. This proves that $f$ is bijective.

Hope this helps you.