----- Let $A$ and $B$ be sets and $f:A \to B$. > [!proposition]+ Proposition. ([[the canonical decomposition of a set function]]) > $f$ determines an [[equivalence relation]] $\sim$ on $A$ by declaring $a' \sim a'' \iff f(a')=f(a'')$. Then $f$ decomposes as > >```tikz \usepackage{amsmath} \usepackage{tikz} \usetikzlibrary{cd, arrows.meta, positioning} \begin{document} \begin{tikzcd}[scale=3] A \arrow[r, "f"] \arrow[d, two heads, "\pi" left] & B \\ A/\sim \arrow[r, "\sim" above, "\tilde{f}" below] & \text{im } f \arrow[u, hook, "\iota" right] \end{tikzcd} \end{document} >``` where $\pi$ is the canonical [[projection function|projection]] $a \xmapsto{\pi}[a]$, $\iota$ is [[inclusion map|inclusion]], and $\tilde{f}$ is a [[well-defined]] [[bijection]] $[a] \xmapsto{\tilde{f}}f(a)$. > > In one sense, since $\im f$ satisfies the [[universal property of quotient sets]], [[terminal objects are unique up to a unique isomorphism|it is immediate]] that $A / \sim \ \cong \im f$. But an explicit (still short) proof is below. ^proposition > [!intuition]+ > Though not the only way, one way to interpret this is as follows: > > The [[universal property of quotient sets]] allows one to take a function $f$ and, given data in the form of an [[equivalence relation]] $\sim$ and a guarantee that $a' \sim a'' \implies f(a')=f(a'')$, factor $f$. > But what if just have $f$, without that extra data? Then we may *create* the data by declaring an [[equivalence relation]] $a' \sim a'' \iff f(a')=f(a'')$. Note that the induced function in this case must in fact be an injection. ^intuition > [!proof]+ Proof. ([[the canonical decomposition of a set function]]) > The formula defining $\tilde{f}$ immediately shows the [[diagram]] commutes, so long as we verify that > > 1. That formula *does* define a function (i.e., it doesn't matter what representative of $[a]$ is chosen); > 2. Said function is in fact a [[bijection]]. > > **1.** $\tilde{f}$ is [[well-defined]] because if $[a']=[a'']$ then $f(a') = f(a'')$ by definition of $\sim$. > > **2.** if $f(a')=f(a'')$ then $a' \sim a''$, meaning $[a']=[a'']$. Hence $\tilde{f}$ is an [[injection]]. And given $b=f(a) \in \im f$ we obviously have $b=f(a)=\tilde{f}([a])$, so $\tilde{f}$ is a [[surjection]]. ^proof #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` #reformatrevisebatch02