Maps between Equivalence Relations and Partitions

Question

NOTE: [I’m not (yet) interested in proving that there is a bijection] ~ not a duplicate

---

Consider the following definition.

Definition: Let $A$ be a non-empty set. Let $\varepsilon(A)$ denote the set of all equivalence relations on $A$, and let $\mathcal{T}_{A}$ be the set of all partitions of $A$.

Define a map $\Phi:\varepsilon(A) \to \mathcal{T}_{A}$ as follows. If $\sim$ is an equivalence relation on $A$, let $\Phi(\sim)$ be the quotient set $A/\sim$.

Define the map $\Psi: \mathcal{T}_{A} \to \varepsilon(A)$ as follows. If $\mathcal{D}$ is a partition of $A$, let $\Psi(\mathcal{D})$ be the relation on $A$ given by $x \Psi(\mathcal{D}) y$ if and only if ther is some $P \in \mathcal{D}$ such that $x, y \in P$, for all $x, y \in A$.

Then, consider the following lemma.

Lemma: Let $A$ be a non-empty set. The maps $\Phi$ and $\Psi$ in the above definition are well-defined.

I want to prove this result. Although I don’t know what I should do in order to show the well-definition of these maps.

The problem: Generally speaking, let $A, B$ be non-empty sets and let $f: A \to B$. To show that $f$ is well-defined we need to show:

1. that $x = y$ implies $f(x) = f(y)$ for all $x, y \in A$

OR

2. that $f(x) \in B$ for all $x \in A$.

And how do I apply the correct strategy in the case of the maps $\Phi$ and $\Psi$?

Thank you so much in advance!

Answer 1

To show that the maps $\Phi$ and $\Psi$ are well-defined, it suffice to show that

1. for all equivalence relations $\sim$ on $A$, $\Phi(\sim)$ is a partition of $A$ (so $\Phi(A) \in \mathcal{T}_A$),

2. for all partitions $\mathcal{D}$ of $A$, $\Psi(\mathcal{D})$ is an equivalence relation on $A$ (so $\Psi(\mathcal{D}) \in \varepsilon(A)$).

---

Proof: By the definition of the map $\Phi$, we see that $\Phi(\sim)$ is the quotient set $A/\sim$, which is a partition of the set $A$. So this case is really straightforward.

Now, let $\mathcal{D}$ be a partition of the set $A$, and let $\Psi(\mathcal{D})$ be a relation on $A$ such that, for all $x, y \in A$, $x \Psi(\mathcal{D}) y$ if and only if there exists some $P \in \mathcal{D}$ such that $x, y \in P$.

Let $a$ be any element of $A$. Since $\mathcal{D}$ is a partition of $A$, we know that $\bigcup_{P \in \mathcal{D}} = A$. Hence $a \in \bigcup_{P \in \mathcal{D}}$. Therefore, there exists $P \in \mathcal{D}$ such that $x \in P$. Then $x \Psi(\mathcal{D}) x$. Therefore $\Psi(\mathcal{D})$ is reflexive.

Let $b, c \in A$ such that $b \Psi(\mathcal{D}) c$. By definition, there exists a $P \in \mathcal{D}$ such that $b, c \in P$. It follows right from here, that $c \Psi(\mathcal{D}) b$. Therefore $\Psi(\mathcal{D})$ is symmetric.

Let $d, e, f \in A$ such that $d \Psi(\mathcal{D}) e$ and $e \Psi(\mathcal{D}) f$. By definition there exists $P_1, P_2 \in \mathcal{D}$ such that $d,e \in P_1$ and $e,f \in P_2$. Note that $\mathcal{D}$ is a partition of $A$ and $P_1 \cap P_2 \neq \emptyset$. So $P_1 = P_2$. Then $x,z \in P_1=P_2$. So $d \Psi(\mathcal{D}) f$. Therefore $\Psi(\mathcal{D})$ is transitive.

We conclude that $\Psi(\mathcal{D})$ is an equivalence relation on $A$, therefore it belongs to $\varepsilon(A)$.

This proves that these maps are both well-defined. $\square$