Universal Property of Quotient Set

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $X$ and $Y$ be sets.

Let $\sim$ be an equivalence relation on $X$.

Let $\pi : X \to X/\sim$ be the quotient mapping to the quotient set.

Let $f : X \to Y$ be $\sim$-invariant.


Then there exists a unique mapping $\overline f : X/\!\sim \to Y$ such that $f = \overline f \circ \pi$.

$\xymatrix{ X \ar[d]_\pi \ar[r]^f & Y\\ X/\sim \[email protected]{.>}[ru]_{\overline f} }$


Proof

Existence

For $x \in X$, let $[x] \in X/\sim$ denote its equivalence class under $\sim$.

Define the relation $\overline f : X/\sim \to Y$ by:

$([x], y) \in \overline f \iff f(x) = y$.

We check that this is a well-defined mapping.

By Quotient Mapping is Surjection, $f$ is left-total.

Let $[x] \in X/\sim$ and $y, z \in Y$ with:

$([x], y) \in \overline f$
$([x], z) \in \overline f$

We show that $y = z$.

By definition of $\overline f$, there exist $u, v \in X$ with $[u] = [v] = [x]$ and $f(u) = y$ and $f(v) = z$.

By definition of equivalence class, $u \sim v$.

Because $f$ is $\sim$-invariant, $y = z$.

Thus $\overline f$ is many-to-one.

Thus $\overline f$ is a well-defined mapping.

$\Box$


Uniqueness

Follows from:

$\blacksquare$