The Clowder Project

Let $f:X\to Y$ be a function and let $R$ be a relation on $X$.

1. 1. As a Coequaliser. We have an isomorphism of sets
   $$X/{\sim }_R^{\mathrm{eq}}\cong \text{CoEq}(R\hookrightarrow X\times X\stackrel{\stackrel{{\text{pr}}_1}{\to }}{\overrightarrow{{\text{pr}}_2}}X),$$

   where ${\sim }_R^{\mathrm{eq}}$ is the equivalence relation generated by ${\sim }_R$.

2. 2. As a Pushout. We have an isomorphism of sets¹
   
   where ${\sim }_R^{\mathrm{eq}}$ is the equivalence relation generated by ${\sim }_R$.
3. 3. The First Isomorphism Theorem for Sets. We have an isomorphism of sets²³
   $$X/{\sim }_{\mathrm{Ker}\left(f\right)}\cong \mathrm{Im}\left(f\right).$$
4. 4. Descending Functions to Quotient Sets, I. Let $R$ be an equivalence relation on $X$. The following conditions are equivalent:
   1. (a) There exists a map
      $$\bar{f}:X/{\sim }_R\to Y$$

      making the diagram

      

      commute.

   2. (b) We have $R\subset \mathrm{Ker}\left(f\right)$.
   3. (c) For each $x,y\in X$, if $x{\sim }_{R}y$, then $f\left(x\right)=f\left(y\right)$.
5. 5. Descending Functions to Quotient Sets, II. Let $R$ be an equivalence relation on $X$. If the conditions of Item 4 hold, then $\bar{f}$ is the unique map making the diagram
   

   commute.

6. 6. Descending Functions to Quotient Sets, III. Let $R$ be an equivalence relation on $X$. We have a bijection
   $${\text{Hom}}_{\mathsf{Sets}}(X/{\sim }_R,Y)\cong {\text{Hom}}_{\mathsf{Sets}}^R(X,Y),$$

   natural in $X,Y\in \text{Obj}\left(\mathsf{Sets}\right)$, given by the assignment $f\mapsto \bar{f}$ of Item 4 and Item 5, where ${\text{Hom}}_{\mathsf{Sets}}^R(X,Y)$ is the set defined by

   $${\text{Hom}}_{\mathsf{Sets}}^R(X,Y)\stackrel{\text{def}}{=}\{f\in {\text{Hom}}_{\mathsf{Sets}}(X,Y)|\begin{array}{rl}& \text{for each }x,y\in X\text{,}\\ & \text{if }x{\sim }_{R}y\text{, then}\\ & f\left(x\right)=f\left(y\right)\end{array}\}.$$
7. 7. Descending Functions to Quotient Sets, IV. Let $R$ be an equivalence relation on $X$. If the conditions of Item 4 hold, then the following conditions are equivalent:
   1. (a) The map $\bar{f}$ is an injection.
   2. (b) We have $R=\mathrm{Ker}\left(f\right)$.
   3. (c) For each $x,y\in X$, we have $x{\sim }_{R}y$ iff $f\left(x\right)=f\left(y\right)$.
8. 8. Descending Functions to Quotient Sets, V. Let $R$ be an equivalence relation on $X$. If the conditions of Item 4 hold, then the following conditions are equivalent:
   1. (a) The map $f:X\to Y$ is surjective.
   2. (b) The map $\bar{f}:X/{\sim }_R\to Y$ is surjective.
9. 9. Descending Functions to Quotient Sets, VI. Let $R$ be a relation on $X$ and let ${\sim }_R^{\mathrm{eq}}$ be the equivalence relation associated to $R$. The following conditions are equivalent:
   1. (a) The map $f$ satisfies the equivalent conditions of Item 4:
      • There exists a map
        $$\bar{f}:X/{\sim }_R^{\mathrm{eq}}\to Y$$

        making the diagram

        

        commute.

      • For each $x,y\in X$, if $x{\sim }_R^{\mathrm{eq}}y$, then $f\left(x\right)=f\left(y\right)$.

   2. (b) For each $x,y\in X$, if $x{\sim }_{R}y$, then $f\left(x\right)=f\left(y\right)$.

---

¹Dually, we also have an isomorphism of sets

²Further Terminology: The set $X/{\sim }_{\mathrm{Ker}\left(f\right)}$ is often called the coimage of $f$, and denoted by $\mathrm{CoIm}\left(f\right)$.

³In a sense this is a result relating the monad in $\mathbf{\text{Rel}}$ induced by $f$ with the comonad in $\mathbf{\text{Rel}}$ induced by $f$, as the kernel and image

$$\begin{array}{c}\mathrm{Ker}\left(f\right):X\to |X,\\ \mathrm{Im}\left(f\right)\subset Y\end{array}$$

of $f$ are the underlying functors of (respectively) the induced monad and comonad of the adjunction

of Chapter 7: Constructions With Relations, Item 2 of Proposition 7.3.1.1.2.