Prove that given a partition $\mathcal{P}$ of a set $A$ nonempty, there exists a unique equivalence relation on $A$ from which it is derived

Question

Prove that given a partition $\mathcal{P}$ of a set $A$ nonempty, there exists a unique equivalence relation on $A$ from which it is derived

sol:

Let $\mathcal{P} $ be the partition $\{ A_{\alpha} \}_{\alpha} $ where $A_{ \alpha } \cap A_{\beta} = \varnothing $ for $\alpha \neq \beta $.

My idea is to create an equivalence relation $R$ on $A$ as follows:

$$ (x,y) \in R \iff x,y \in A_{\alpha} \in \mathcal{P} \; \; \; \text{for some } \; \alpha $$

Since $x \in A_{\alpha}$ then $(x,x) \in R$ is clear. Now,

Suppose $(x,y) \in R$. That is, suppose $x,y$ are in $A_{\alpha}$, then $y,x \in A_{\alpha}$. So that $(y,x) \in R$. Is this that simple?

Now, if $(x,y) \in R$ and $(y,z) \in R$, then we show that $(x,z) \in R$. That is, we show $x,z \in A_{\alpha}$. We already know $x \in A_{\alpha}$. IF $z $ is ${\bf not}$ in there, then $z$ is in another $A_{\beta}$ and thus $y \in A_{\beta}$ but $y$ is in some $A_{\gamma}$ and so $A_{\beta} \cap A_{\gamma} \neq \varnothing$ which is a contradiction.

As for uniqueness, how can I show this? Any hint would be appreciated.

Answer 1

You've already done it: the equivalence relation you've defined IS, in fact, the partition you began with, or in other words: when I know the equivalence classes of an equivalence relation on some set I already know completely and uniquely that equivalence, and since those equivalence classes are the partition's sets we're then done.

Another way you could try: Suppose there is another equivalence relation $\;S\;$ @derived@ (in the way you showed) from the given partition. Then both equivalence relations $\;R,\,S\;l$ have the very same equivalence classes (which are the sets of the partition!), and it is then a mtter of simply check that we have $\;aRb\iff aSb\;$, as then $\;a,b\;$ belong to the same set in the partition...

Answer 2

Your solutions for existence is good, but can be simplified for transitivity (no need to do by contradiction). The proofs for both are not too complicated.

Transitivity: Suppose $(x,y) \in R$ and $(y,z) \in R$, so $x,y \in A_{\alpha_1}$ and $y,z \in A_{\alpha_2}$ for some indices $\alpha_1,\alpha_2$. Since $\mathcal{P}$ is a partition, $y \in A_{\alpha_1} \cap A_{\alpha_2} \implies A_{\alpha_1} = A_{\alpha_2}$. Thus, $z \in A_{\alpha_1}$, and since $x,z \in A_{\alpha_1}$, $(x,z) \in R$.

To prove uniqueness, let $R'$ be another relation such that the partition $\mathcal{P}$ forms the equivalence classes of $R'$ as well. First suppose $(x,y) \in R'$, so $x,y$ belongs to the same equivalence class, say $x,y \in A_\alpha$. By definition of $R$, $(x,y) \in R$, so $R' \subseteq R$. On the other hand, suppose $(x,y) \in R$, so $(x,y) \in A_\alpha$ for some $\alpha$. Since $A_\alpha$ is an equivalence class of $R'$, we have that $x$ and $y$ belongs to the same equivalence class of $R'$, so $(x,y) \in R'$.