Prove that any partition induces a unique equivalence relation.

Question

Given any partition $D$ of $A$, $\exists !$ equivalence relation on $A$ from which it is derived.

Can someone please help me solve this problem? thanks.

Answer 1

Hint: Write the partition as $\{D_{\lambda} : \lambda \in \Lambda\}$, where $\Lambda$ is just an index set. Define $\sim$ by

$$x \sim y \iff \exists \alpha : x \in D_\alpha, y \in D_\alpha$$

Use the definition of a partition to show that this is an equivalence relation. Then show that given any equivalence relation, the equivalence classes form a partition.

Answer 2

For a partition $D = \{P_i : i \in I\}$ of $A$, the derived equivalence relation $E(D)$ is given by $$ a\sim b :\iff \exists i\in I : a,b\in P_i $$

Vice versa, for an equivalence relation $\sim$ on $A$, the equivalence classes form a partition $P(\sim)$ of $A$.

Now show that E(D) is indeed an equivalence relation on $A$ and $P(\sim)$ is indeed a partition of $A$. Moreover, show that $E$ and $P$ are mutually inverse:

• Starting with a partition $D$, show that $P(E(D)) = D$,
• Starting with an equivalence relation $\sim$, show that $E(P(\sim)) = {\sim}$.

Answer 3

Think in specific terms! Define an equivalence relation on the students in a lecture by saying two students are equivalent if they sit in the same row. How then are the students partitioned?