Item 2 (002U) — The Clowder Project

4.2.5 Coequalisers

Let $A$ and $B$ be sets and let $f,g\colon A\rightrightarrows B$ be functions.

Definition 4.2.5.1.1 ▶ Coequalisers of Sets

The coequaliser of $f$ and $g$ is the coequaliser of $f$ and $g$ in $\mathsf{Sets}$ as in , .

Construction 4.2.5.1.2 ▶ Construction of Coequalisers of Sets

Concretely, the coequaliser of $f$ and $g$ is the pair $(\operatorname {\mathrm{CoEq}}(f,g),\operatorname {\mathrm{coeq}}(f,g))$ consisting of:

1.
The Colimit. The set $\operatorname {\mathrm{CoEq}}(f,g)$ defined by

\[ \operatorname {\mathrm{CoEq}}(f,g)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}B/\mathord {\sim }, \]

where $\mathord {\sim }$ is the equivalence relation on $B$ generated by $f(a)\sim g(a)$.
2.
The Cocone. The map

\[ \operatorname {\mathrm{coeq}}(f,g)\colon B\twoheadrightarrow \operatorname {\mathrm{CoEq}}(f,g) \]

given by the quotient map $\pi \colon B\twoheadrightarrow B/\mathord {\sim }$ with respect to the equivalence relation generated by $f(a)\sim g(a)$.

Proof of Construction 4.2.5.1.2.

We claim that $\operatorname {\mathrm{CoEq}}(f,g)$ is the categorical coequaliser of $f$ and $g$ in $\mathsf{Sets}$. First we need to check that the relevant coequaliser diagram commutes, i.e. that we have

\[ \operatorname {\mathrm{coeq}}(f,g)\circ f=\operatorname {\mathrm{coeq}}(f,g)\circ g. \]

Indeed, we have

\begin{align*} [\operatorname {\mathrm{coeq}}(f,g)\circ f](a) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}[\operatorname {\mathrm{coeq}}(f,g)](f(a))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}[f(a)]\\ & = [g(a)]\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}[\operatorname {\mathrm{coeq}}(f,g)](g(a))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}[\operatorname {\mathrm{coeq}}(f,g)\circ g](a)\end{align*}

for each $a\in A$. Next, we prove that $\operatorname {\mathrm{CoEq}}(f,g)$ satisfies the universal property of the coequaliser. Suppose we have a diagram of the form

in $\mathsf{Sets}$. Then, since $c(f(a))=c(g(a))$ for each $a\in A$, it follows from Chapter 10: Conditions on Relations, Item 4 and Item 5 of Proposition 10.6.2.1.3 that there exists a unique map $\operatorname {\mathrm{CoEq}}(f,g)\overset {\exists !}{\to }C$ making the diagram

commute.

Remark 4.2.5.1.3 ▶ Unwinding Definition 4.2.5.1.1

In detail, by Chapter 10: Conditions on Relations, Construction 10.5.2.1.2, the relation $\mathord {\sim }$ of Definition 4.2.5.1.1 is given by declaring $a\sim b$ iff one of the following conditions is satisfied:

1.
We have $a=b$;
2.
There exist $x_{1},\ldots ,x_{n}\in B$ such that $a\sim 'x_{1}\sim '\cdots \sim 'x_{n}\sim 'b$, where we declare $x\sim 'y$ if one of the following conditions is satisfied:
1. (a)
  There exists $z\in A$ such that $x=f(z)$ and $y=g(z)$.
2. (b)
  There exists $z\in A$ such that $x=g(z)$ and $y=f(z)$.
In other words, there exist $x_{1},\ldots ,x_{n}\in B$ satisfying the following conditions:
1. (a)
  There exists $z_{0}\in A$ satisfying one of the following conditions:
  1. (i)
    We have $a=f(z_{0})$ and $x_{1}=g(z_{0})$.
  2. (ii)
    We have $a=g(z_{0})$ and $x_{1}=f(z_{0})$.
2. (b)
  For each $1\leq i\leq n-1$, there exists $z_{i}\in A$ satisfying one of the following conditions:
  1. (i)
    We have $x_{i}=f(z_{i})$ and $x_{i+1}=g(z_{i})$.
  2. (ii)
    We have $x_{i}=g(z_{i})$ and $x_{i+1}=f(z_{i})$.
3. (c)
  There exists $z_{n}\in A$ satisfying one of the following conditions:
  1. (i)
    We have $x_{n}=f(z_{n})$ and $b=g(z_{n})$.
  2. (ii)
    We have $x_{n}=g(z_{n})$ and $b=f(z_{n})$.

Example 4.2.5.1.4 ▶ Examples of Coequalisers of Sets

Here are some examples of coequalisers of sets.

1.
Quotients by Equivalence Relations. Let $R$ be an equivalence relation on a set $X$. We have a bijection of sets

\[ X/\mathord {\sim }_{R}\cong \operatorname {\mathrm{CoEq}}(R\hookrightarrow X\times X\underset {\operatorname {\mathrm{\mathrm{pr}}}_{2}}{\overset {\operatorname {\mathrm{\mathrm{pr}}}_{1}}{\rightrightarrows }}X). \]

Proof of Example 4.2.5.1.4.

Item 1: Quotients by Equivalence Relations

See [Proof Wiki Contributors, Quotient Mapping Is Coequalizer — Proof Wiki].

Proposition 4.2.5.1.5 ▶ Properties of Coequalisers of Sets

Let $A$, $B$, and $C$ be sets.

1.
Associativity. We have isomorphisms of sets¹

\[ \underbrace{\operatorname {\mathrm{CoEq}}(\operatorname {\mathrm{coeq}}(f,g)\circ f,\operatorname {\mathrm{coeq}}(f,g)\circ h)}_{{}=\operatorname {\mathrm{CoEq}}(\operatorname {\mathrm{coeq}}(f,g)\circ g,\operatorname {\mathrm{coeq}}(f,g)\circ h)}\cong \operatorname {\mathrm{CoEq}}(f,g,h) \cong \underbrace{\operatorname {\mathrm{CoEq}}(\operatorname {\mathrm{coeq}}(g,h)\circ f,\operatorname {\mathrm{coeq}}(g,h)\circ g)}_{{}=\operatorname {\mathrm{CoEq}}(\operatorname {\mathrm{coeq}}(g,h)\circ f,\operatorname {\mathrm{coeq}}(g,h)\circ h)}, \]
where $\operatorname {\mathrm{CoEq}}(f,g,h)$ is the colimit of the diagram
in $\mathsf{Sets}$.

2.
Unitality. We have an isomorphism of sets

\[ \operatorname {\mathrm{CoEq}}(f,f)\cong B. \]

Commutativity. We have an isomorphism of sets

\[ \operatorname {\mathrm{CoEq}}(f,g) \cong \operatorname {\mathrm{CoEq}}(g,f). \]

Interaction With Composition. Let

\[ A \underset {g}{\overset {f}{\rightrightarrows }} B \underset {k}{\overset {h}{\rightrightarrows }} C \]

be functions. We have a surjection

\[ \operatorname {\mathrm{CoEq}}(h\circ f,k\circ g)\twoheadrightarrow \operatorname {\mathrm{CoEq}}(\operatorname {\mathrm{coeq}}(h,k)\circ h\circ f,\operatorname {\mathrm{coeq}}(h,k)\circ k\circ g) \]

exhibiting $\operatorname {\mathrm{CoEq}}(\operatorname {\mathrm{coeq}}(h,k)\circ h\circ f,\operatorname {\mathrm{coeq}}(h,k)\circ k\circ g)$ as a quotient of $\operatorname {\mathrm{CoEq}}(h\circ f,k\circ g)$ by the relation generated by declaring $h(y)\sim k(y)$ for each $y\in B$.

¹That is, the following three ways of forming “the” coequaliser of $(f,g,h)$ agree:
1. (a)
  Take the coequaliser of $(f,g,h)$, i.e. the colimit of the diagram
  in $\mathsf{Sets}$.
2. (b)
  First take the coequaliser of $f$ and $g$, forming a diagram
  
  \[ A\underset {g}{\overset {f}{\rightrightarrows }}B\overset {\operatorname {\mathrm{coeq}}(f,g)}{\twoheadrightarrow }\operatorname {\mathrm{CoEq}}(f,g) \]
  
  and then take the coequaliser of the composition
  
  \[ A\underset {h}{\overset {f}{\rightrightarrows }}B\overset {\operatorname {\mathrm{coeq}}(f,g)}{\twoheadrightarrow }\operatorname {\mathrm{CoEq}}(f,g), \]
  
  obtaining a quotient
  
  \[ \operatorname {\mathrm{CoEq}}(\operatorname {\mathrm{coeq}}(f,g)\circ f,\operatorname {\mathrm{coeq}}(f,g)\circ h)=\operatorname {\mathrm{CoEq}}(\operatorname {\mathrm{coeq}}(f,g)\circ g,\operatorname {\mathrm{coeq}}(f,g)\circ h) \]
  of $\operatorname {\mathrm{CoEq}}(f,g)$
3. (c)
  First take the coequaliser of $g$ and $h$, forming a diagram
  
  \[ A\underset {h}{\overset {g}{\rightrightarrows }}B\overset {\operatorname {\mathrm{coeq}}(g,h)}{\twoheadrightarrow }\operatorname {\mathrm{CoEq}}(g,h) \]
  
  and then take the coequaliser of the composition
  
  \[ A\underset {g}{\overset {f}{\rightrightarrows }}B\overset {\operatorname {\mathrm{coeq}}(g,h)}{\twoheadrightarrow }\operatorname {\mathrm{CoEq}}(g,h), \]
  
  obtaining a quotient
  
  \[ \operatorname {\mathrm{CoEq}}(\operatorname {\mathrm{coeq}}(g,h)\circ f,\operatorname {\mathrm{coeq}}(g,h)\circ g)=\operatorname {\mathrm{CoEq}}(\operatorname {\mathrm{coeq}}(g,h)\circ f,\operatorname {\mathrm{coeq}}(g,h)\circ h) \]
  of $\operatorname {\mathrm{CoEq}}(g,h)$.