> [!NOTE] Lemma (For every partition there is a unique equivalence relation) > Let $X$ be a set and $E$ an [[Equivalence relations|equivalence relation]] on $X.$ Let $\Pi(E)=X/E$ denote the function that $E$ to the [[Equivalence relations|quotient]]. Then the function $\Pi$ is a [[Bijection|bijection]]. ^a16324 *Proof*. Suppose that $\mathbb{P}$ is [[Partition of a Set|partition]] of $X.$ We define a relation $Q_{\mathbb{P}}$ on $X$ where $xQ_{\mathbb{P}}y$ iff $x$ and $y$ lie in the same part of $\mathbb{P}.$ Note that $Q$ is an equivalence relation by [[Partition induces equivalence relation]]. This gives a function $\Sigma(\mathbb{P}) = Q_{\mathbb{P}}$ from partitions to equivalence relations. Suppose that $E$ is an equivalence relation. Then $Q=\sum(\Pi(E))$ is also an equivalence relation. By construction $Q$ and $E$ have the same equivalence classes. Thus $E=Q.$ It follows that $\Sigma$ is a left inverse for $\Pi.$ Suppose that $\mathbb{P}$ is a partition. Then by [[Fundamental Theorem on Equivalence Relations]], $\mathbb{Q}=\Pi(\Sigma(\mathbb{P}))$ is also a partition. So the parts of $\mathbb{Q}$ are equivalence classes of $\Sigma(\mathbb{P}).$ But these are, by construction, the parts of $\mathbb{P}.$ So $\mathbb{P}=\mathbb{Q}.$ It follows that $\Sigma$ is a right inverse for $\Pi.$ Thus by [[Bijection#^db677e|bijection iff invertible]], $\Pi$ is a bijection.