4.1.5 Equalisers

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

Definition 4.1.5.1.1 ▶ Equalisers of Sets

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

Construction 4.1.5.1.2 ▶ Construction of Equalisers of Sets

Concretely, the equaliser of $f$ and $g$ is the pair $\webleft (\operatorname {\mathrm{Eq}}\webleft (f,g\webright ),\operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright )$ consisting of:

  1. 1.

    The Limit. The set $\operatorname {\mathrm{Eq}}\webleft (f,g\webright )$ defined by

    \[ \operatorname {\mathrm{Eq}}\webleft (f,g\webright )\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in A\ \middle |\ f\webleft (a\webright )=g\webleft (a\webright )\right\} . \]
  2. 2.

    The Cone. The inclusion map

    \[ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\colon \operatorname {\mathrm{Eq}}\webleft (f,g\webright )\hookrightarrow A. \]

Proof of Construction 4.1.5.1.2.

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

\[ f\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )=g\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright ), \]

which indeed holds by the definition of the set $\operatorname {\mathrm{Eq}}\webleft (f,g\webright )$. Next, we prove that $\operatorname {\mathrm{Eq}}\webleft (f,g\webright )$ satisfies the universal property of the equaliser. Suppose we have a diagram of the form

in $\mathsf{Sets}$. Then there exists a unique map $\phi \colon E\to \operatorname {\mathrm{Eq}}\webleft (f,g\webright )$ making the diagram
commute, being uniquely determined by the condition

\[ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\circ \phi =e \]

via

\[ \phi \webleft (x\webright )=e\webleft (x\webright ) \]

for each $x\in E$, where we note that $e\webleft (x\webright )\in A$ indeed lies in $\operatorname {\mathrm{Eq}}\webleft (f,g\webright )$ by the condition

\[ f\circ e=g\circ e, \]

which gives

\[ f\webleft (e\webleft (x\webright )\webright )=g\webleft (e\webleft (x\webright )\webright ) \]

for each $x\in E$, so that $e\webleft (x\webright )\in \operatorname {\mathrm{Eq}}\webleft (f,g\webright )$.

Proposition 4.1.5.1.3 ▶ Properties of Equalisers of Sets

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

  1. 1.

    Associativity. We have isomorphisms of sets1

    \[ \underbrace{\operatorname {\mathrm{Eq}}\webleft (f\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright ),g\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright )\webright )}_{{}=\operatorname {\mathrm{Eq}}\webleft (f\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright ),h\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright )\webright )}\cong \operatorname {\mathrm{Eq}}\webleft (f,g,h\webright ) \cong \underbrace{\operatorname {\mathrm{Eq}}\webleft (f\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright ),h\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright )}_{{}=\operatorname {\mathrm{Eq}}\webleft (g\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright ),h\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright )}, \]
    where $\operatorname {\mathrm{Eq}}\webleft (f,g,h\webright )$ is the limit of the diagram
    in $\mathsf{Sets}$, being explicitly given by

    \[ \operatorname {\mathrm{Eq}}\webleft (f,g,h\webright )\cong \left\{ a\in A\ \middle |\ f\webleft (a\webright )=g\webleft (a\webright )=h\webleft (a\webright )\right\} . \]
  2. 2.

    Unitality. We have an isomorphism of sets

    \[ \operatorname {\mathrm{Eq}}\webleft (f,f\webright )\cong A. \]
  3. 3.

    Commutativity. We have an isomorphism of sets

    \[ \operatorname {\mathrm{Eq}}\webleft (f,g\webright ) \cong \operatorname {\mathrm{Eq}}\webleft (g,f\webright ). \]
  4. 4.

    Interaction With Composition. Let

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

    be functions. We have an inclusion of sets

    \[ \operatorname {\mathrm{Eq}}\webleft (h\circ f\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright ),k\circ g\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright ) \subset \operatorname {\mathrm{Eq}}\webleft (h\circ f,k\circ g\webright ), \]

    where $\operatorname {\mathrm{Eq}}\webleft (h\circ f\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright ),k\circ g\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright )$ is the equaliser of the composition

    \[ \operatorname {\mathrm{Eq}}\webleft (f,g\webright )\overset {\operatorname {\mathrm{eq}}\webleft (f,g\webright )}{\hookrightarrow }A\underset {g}{\overset {f}{\rightrightarrows }}B\underset {k}{\overset {h}{\rightrightarrows }}C. \]

  1. 1That is, the following three ways of forming “the” equaliser of $\webleft (f,g,h\webright )$ agree:
    1. (a)

      Take the equaliser of $\webleft (f,g,h\webright )$, i.e. the limit of the diagram

      in $\mathsf{Sets}$.

    2. (b)

      First take the equaliser of $f$ and $g$, forming a diagram

      \[ \operatorname {\mathrm{Eq}}\webleft (f,g\webright )\overset {\operatorname {\mathrm{eq}}\webleft (f,g\webright )}{\hookrightarrow }A\underset {g}{\overset {f}{\rightrightarrows }}B \]

      and then take the equaliser of the composition

      \[ \operatorname {\mathrm{Eq}}\webleft (f,g\webright )\overset {\operatorname {\mathrm{eq}}\webleft (f,g\webright )}{\hookrightarrow }A\underset {h}{\overset {f}{\rightrightarrows }}B, \]

      obtaining a subset

      \[ \operatorname {\mathrm{Eq}}\webleft (f\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright ),h\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright )=\operatorname {\mathrm{Eq}}\webleft (g\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright ),h\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright ) \]

      of $\operatorname {\mathrm{Eq}}\webleft (f,g\webright )$.

    3. (c)

      First take the equaliser of $g$ and $h$, forming a diagram

      \[ \operatorname {\mathrm{Eq}}\webleft (g,h\webright )\overset {\operatorname {\mathrm{eq}}\webleft (g,h\webright )}{\hookrightarrow }A\underset {h}{\overset {g}{\rightrightarrows }}B \]

      and then take the equaliser of the composition

      \[ \operatorname {\mathrm{Eq}}\webleft (g,h\webright )\overset {\operatorname {\mathrm{eq}}\webleft (g,h\webright )}{\hookrightarrow }A\underset {g}{\overset {f}{\rightrightarrows }}B, \]

      obtaining a subset

      \[ \operatorname {\mathrm{Eq}}\webleft (f\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright ),g\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright )\webright )=\operatorname {\mathrm{Eq}}\webleft (f\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright ),h\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright )\webright ) \]

      of $\operatorname {\mathrm{Eq}}\webleft (g,h\webright )$.

Proof of Proposition 4.1.5.1.3.

Item 1: Associativity
We first prove that $\operatorname {\mathrm{Eq}}\webleft (f,g,h\webright )$ is indeed given by

\[ \operatorname {\mathrm{Eq}}\webleft (f,g,h\webright )\cong \left\{ a\in A\ \middle |\ f\webleft (a\webright )=g\webleft (a\webright )=h\webleft (a\webright )\right\} . \]

Indeed, suppose we have a diagram of the form

in $\mathsf{Sets}$. Then there exists a unique map $\phi \colon E\to \operatorname {\mathrm{Eq}}\webleft (f,g,h\webright )$, uniquely determined by the condition

\[ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\circ \phi =e \]

being necessarily given by

\[ \phi \webleft (x\webright )=e\webleft (x\webright ) \]

for each $x\in E$, where we note that $e\webleft (x\webright )\in A$ indeed lies in $\operatorname {\mathrm{Eq}}\webleft (f,g,h\webright )$ by the condition

\[ f\circ e=g\circ e=h\circ e, \]

which gives

\[ f\webleft (e\webleft (x\webright )\webright )=g\webleft (e\webleft (x\webright )\webright )=h\webleft (e\webleft (x\webright )\webright ) \]

for each $x\in E$, so that $e\webleft (x\webright )\in \operatorname {\mathrm{Eq}}\webleft (f,g,h\webright )$.

We now check the equalities

\[ \operatorname {\mathrm{Eq}}\webleft (f\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright ),g\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright )\webright )\cong \operatorname {\mathrm{Eq}}\webleft (f,g,h\webright ) \cong \operatorname {\mathrm{Eq}}\webleft (f\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright ),h\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright ). \]

Indeed, we have

\begin{align*} \operatorname {\mathrm{Eq}}\webleft (f\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright ),g\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright )\webright ) & \cong \left\{ x\in \operatorname {\mathrm{Eq}}\webleft (g,h\webright )\ \middle |\ \webleft [f\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright )\webright ]\webleft (a\webright )=\webleft [g\circ \operatorname {\mathrm{eq}}\webleft (g,h\webright )\webright ]\webleft (a\webright )\right\} \\ & \cong \left\{ x\in \operatorname {\mathrm{Eq}}\webleft (g,h\webright )\ \middle |\ f\webleft (a\webright )=g\webleft (a\webright )\right\} \\ & \cong \left\{ x\in A\ \middle |\ \text{$f\webleft (a\webright )=g\webleft (a\webright )$ and $g\webleft (a\webright )=h\webleft (a\webright )$}\right\} \\ & \cong \left\{ x\in A\ \middle |\ \text{$f\webleft (a\webright )=g\webleft (a\webright )=h\webleft (a\webright )$}\right\} \\ & \cong \operatorname {\mathrm{Eq}}\webleft (f,g,h\webright ).\end{align*}
Similarly, we have
\begin{align*} \operatorname {\mathrm{Eq}}\webleft (f\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright ),h\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright ) & \cong \left\{ x\in \operatorname {\mathrm{Eq}}\webleft (f,g\webright )\ \middle |\ \webleft [f\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright ]\webleft (a\webright )=\webleft [h\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright ]\webleft (a\webright )\right\} \\ & \cong \left\{ x\in \operatorname {\mathrm{Eq}}\webleft (f,g\webright )\ \middle |\ f\webleft (a\webright )=h\webleft (a\webright )\right\} \\ & \cong \left\{ x\in A\ \middle |\ \text{$f\webleft (a\webright )=h\webleft (a\webright )$ and $f\webleft (a\webright )=g\webleft (a\webright )$}\right\} \\ & \cong \left\{ x\in A\ \middle |\ \text{$f\webleft (a\webright )=g\webleft (a\webright )=h\webleft (a\webright )$}\right\} \\ & \cong \operatorname {\mathrm{Eq}}\webleft (f,g,h\webright ).\end{align*}

Item 2: Unitality
Indeed, we have

\begin{align*} \operatorname {\mathrm{Eq}}\webleft (f,f\webright ) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in A\ \middle |\ f\webleft (a\webright )=f\webleft (a\webright )\right\} \\ & = A. \end{align*}

Item 3: Commutativity
Indeed, we have

\begin{align*} \operatorname {\mathrm{Eq}}\webleft (f,g\webright ) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in A\ \middle |\ f\webleft (a\webright )=g\webleft (a\webright )\right\} \\ & = \left\{ a\in A\ \middle |\ g\webleft (a\webright )=f\webleft (a\webright )\right\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\operatorname {\mathrm{Eq}}\webleft (g,f\webright ). \end{align*}

Item 4: Interaction With Composition
Indeed, we have
\begin{align*} \operatorname {\mathrm{Eq}}\webleft (h\circ f\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright ),k\circ g\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright ) & \cong \left\{ a\in \operatorname {\mathrm{Eq}}\webleft (f,g\webright )\ \middle |\ h\webleft (f\webleft (a\webright )\webright )=k\webleft (g\webleft (a\webright )\webright )\right\} \\ & \cong \left\{ a\in A\ \middle |\ \text{$f\webleft (a\webright )=g\webleft (a\webright )$ and $h\webleft (f\webleft (a\webright )\webright )=k\webleft (g\webleft (a\webright )\webright )$}\right\} .\end{align*}
and

\[ \operatorname {\mathrm{Eq}}\webleft (h\circ f,k\circ g\webright )\cong \left\{ a\in A\ \middle |\ h\webleft (f\webleft (a\webright )\webright )=k\webleft (g\webleft (a\webright )\webright )\right\} , \]

and thus there’s an inclusion from $\operatorname {\mathrm{Eq}}\webleft (h\circ f\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright ),k\circ g\circ \operatorname {\mathrm{eq}}\webleft (f,g\webright )\webright )$ to $\operatorname {\mathrm{Eq}}\webleft (h\circ f,k\circ g\webright )$.

Previous
Up
Next

View Construction 4.1.5.1.2 as PDF
Statistics Cite

Noticed something off, or have any comments? Feel free to reach out!

You can also use the contact form below: