Find the distinct equivalence classes

Question

Let $B = \{0,1,2,3,4\}$ and let $\{0\},\{1,3,4\},\{2\}$ be a partition of $B$ that induces a relation $Q$. Find the distinct equivalence classes of $Q$.

Answer 1

You computed the equivalence relation $Q$, which is good for practice, but as you'll see, there's absolutely no reason to compute it in order to solve this problem. Review what you did to compute $Q$: you formed $p\times p$ for every $p\in$ the partition, then you took their union. All these products are disjoint. Two things $a,b\in B$ are $Q$-related $\iff$ they're in the same member of the partition. In fact, if you had to describe $Q$, you could say "$aQb\iff a, b$ are in the same member of the partition". Thus, the equivalence classes of $Q$ (the partition induced by $Q$) are exactly the members of the partition: you're back to what you started from.

Rephrased: the equivalence classes of (i.e. the partition induced by) the equivalence relation $Q$ which is induced by the partition $P = \{\{0\}, \{1,3,4\}, \{2\}\}$ is just that partition you started with: $P$.

This exemplifies a couple of general facts:

• A partition $P$ of a set $A$ induces an equivalence relation $\sim_P$ on $A$, where $a \sim_P b \iff a,b \text{ are in the same member of the partition}$, and
• an equivalence relation on $A$ induces a partition $R_P$ (equal to the set of equivalence classes of $R$).

It turns out that if $P$ is a partition then $P_{\sim_P} = P$, and if $R$ is an equivalence relation then $R_{P_R} = R$. In other words, these two operations are inverses of each other. [Proof on request, but proving this is an excellent exercise.]