--- title: Equalizers and Pullbacks module: Limits and Colimits moduleNumber: 4 lessonNumber: 2 order: 402 summary: > The equalizer of a parallel pair is the universal arrow that makes the two composites agree; the pullback of a cospan is the universal commutative square. In Set they are solution sets and fibered products, every equalizer is monic, monics are stable under pullback, and products plus equalizers together generate all limits. topics: [Limits and Colimits] sources: - book: Simmons ref: "Ch. 2 §2.6 Equalizers and coequalizers; §2.7 Pullbacks and pushouts" - book: Barr & Wells ref: "Ch. 9 §9.1 Equalizers; §9.3 Pullbacks" - book: Leinster ref: "§5.1 Limits: definition and examples; Prop. 5.1.26" draft: false --- The [general limit](/category-theory/limits-colimits/limits) over a shape category specializes, on the two smallest non-discrete shapes, to the two most common constructions in the subject. Over the parallel-pair shape $\bullet \rightrightarrows \bullet$ the limit is an **equalizer**, the categorical form of "the solutions of an equation"; over the corner shape $\bullet \to \bullet \leftarrow \bullet$ it is a **pullback**, the categorical form of "pairs that agree downstairs." Together with products they generate every limit there is: a category with products and equalizers is complete. ## Forks and equalizers Fix a parallel pair $s, t : X \to Y$, two arrows sharing a source and a target. An arrow $f : A \to X$ **makes the pair equal** if $s \circ f = t \circ f$. The data of $A \xrightarrow{f} X \rightrightarrows Y$ with $sf = tf$ is called a **fork**.[^lein-fork] Many arrows may make a pair equal; the equalizer is the universal one. > **Definition (Equalizer).** Let $s, t : X \to Y$ be a parallel pair in a > category $\mathcal{A}$. An **equalizer** of $s$ and $t$ is an object $E$ with > an arrow $i : E \to X$ such that $s \circ i = t \circ i$, and such that every > fork factors through it uniquely: for any $f : A \to X$ with $s \circ f = t > \circ f$ there is a unique $\bar f : A \to E$ with $i \circ \bar f = f$. $$ % caption: The equalizer fork. Any arrow f that makes the parallel pair agree % factors through i by a unique mediating arrow. \begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} \node (E) at (0,0) {$E$}; \node (X) at (2.4,0) {$X$}; \node (Y) at (5.2,0) {$Y$}; \node (A) at (0,1.8) {$A$}; \draw[->, acc, thick] (E) -- (X) node[midway, below] {$i$}; \draw[->] (2.75,0.09) -- (4.9,0.09) node[midway, above] {$s$}; \draw[->] (2.75,-0.09) -- (4.9,-0.09) node[midway, below] {$t$}; \draw[->, black] (A) -- (X) node[midway, above right] {$f$}; \draw[->, dashed] (A) -- (E) node[midway, left] {$u$}; \end{tikzpicture} $$ In the shape-category picture, a cone over the diagram $X \rightrightarrows Y$ consists of legs $f : A \to X$ and $g : A \to Y$ with $sf = g$ and $tf = g$; the second leg is determined by the first, so a cone is a fork, and the limit is the equalizer.[^lein-conefork] ### Equalizers in concrete categories - **$\mathbf{Set}$.** The equalizer of $s, t : X \to Y$ is the solution set $E = \{x \in X \mid s(x) = t(x)\}$ with the inclusion $i : E \hookrightarrow X$. Any $f : A \to X$ making the pair equal lands inside $E$ pointwise, and corestricting it is the unique mediating map.[^sim-eq] - **$\mathbf{Top}$.** The same set $E$, given the subspace topology from $X$. The subspace topology is the smallest making the inclusion continuous, and that is what makes the mediating map continuous. - **$\mathbf{Grp}$.** For a homomorphism $\theta : G \to H$, the fork $\ker\theta \hookrightarrow G \rightrightarrows H$ (against the trivial homomorphism) is an equalizer: **kernels are equalizers**. More generally the equalizer of $s, t$ is the subgroup $\{g \in G \mid s(g) = t(g)\}$. - **$\mathbf{Vect}_k$.** The equalizer of linear maps $s, t : V \to W$ is $\ker(t - s)$ with its inclusion, since $s(v) = t(v)$ exactly when $(t - s)(v) = 0$.[^lein-eq-ex] Combining equalizers with products expresses any system of simultaneous equations. Given a family of pairs $(s_\lambda, t_\lambda : X \to Y_\lambda)_{\lambda \in \Lambda}$ in $\mathbf{Set}$, the common solution set $\{x \mid s_\lambda(x) = t_\lambda(x) \text{ for all } \lambda\}$ is the equalizer of the induced pair $X \rightrightarrows \prod_\lambda Y_\lambda$. The same reduction of a limit to a product cut down by equations underlies the completeness theorem below. > **Worked example.** Let $X = \{a, b, c, d\}$ and $Y = \{1, 2\}$ with $s, t : X > \to Y$ given by > $$ > s : a \mapsto 1,\ b \mapsto 1,\ c \mapsto 2,\ d \mapsto 2, \qquad > t : a \mapsto 1,\ b \mapsto 2,\ c \mapsto 2,\ d \mapsto 1. > $$ > The equalizer is $E = \{x \mid s(x) = t(x)\} = \{a, c\}$ with $i : E > \hookrightarrow X$, since $s$ and $t$ agree on $a$ (both $1$) and on $c$ (both > $2$) and disagree on $b$ and $d$. For universality take $A = \{\ast\}$ and $f : > A \to X$ with $f(\ast) = c$; because $s(c) = t(c)$, $f$ is a fork, and it > factors as $f = i \circ \bar f$ with the forced $\bar f(\ast) = c$. A map $g$ > with $g(\ast) = b$ is not a fork ($s(b) = 1 \neq 2 = t(b)$) and has no > factorization through $E$. ### Equalizers are monic > **Lemma.** Every equalizer is a > [monomorphism](/category-theory/foundations/special-morphisms). > **Proof.** Let $i : E \to X$ equalize $s, t$, and let $a, b : A \to E$ satisfy $i > \circ a = i \circ b = f$. Then $f$ makes the pair equal, so it factors through > $i$ by a _unique_ arrow; $a$ and $b$ both qualify, so $a = b$. $\square$ The converse fails in general, and the gap has a name: a monic that arises as an equalizer of some pair is a **regular monic**. In $\mathbf{Set}$ and $\mathbf{Ab}$ every monic is regular; in $\mathbf{Top}$ the regular monics are the subspace embeddings, while an injective continuous map onto a subset with a finer-than-subspace topology is monic but not regular.[^lein-regular] The equalizer is best read as the categorical notion of an **embedded subobject cut out by equations**. ## Pullbacks A **cospan** consists of two arrows $s : X \to Z$ and $t : Y \to Z$ into a common target. > **Definition (Pullback).** A **pullback** of the cospan $X \xrightarrow{s} Z > \xleftarrow{t} Y$ is an object $P$ with arrows $p_1 : P \to X$ and $p_2 : P > \to Y$ such that $s \circ p_1 = t \circ p_2$, and universal with this > property: for any $A$ with arrows $f_1 : A \to X$, $f_2 : A \to Y$ satisfying > $s \circ f_1 = t \circ f_2$, there is a unique $\bar f : A \to P$ with $p_1 > \circ \bar f = f_1$ and $p_2 \circ \bar f = f_2$. The commuting square on > $(P, p_1, p_2)$ is a **pullback square**, and $P$ is also written $X > \times_Z Y$ and called the **fibered product**. $$ % caption: The pullback square with its universal property: any commutative % square over the same cospan factors through P by a unique corner arrow. \begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} \node (A) at (-2.1,3.0) {$A$}; \node (P) at (0,1.8) {$P$}; \node (X) at (0,0) {$X$}; \node (Y) at (2.6,1.8) {$Y$}; \node (Z) at (2.6,0) {$Z$}; \draw[->, acc, thick] (P) -- (X) node[midway, left] {$p_1$}; \draw[->, acc, thick] (P) -- (Y) node[midway, above] {$p_2$}; \draw[acc, thick] (0.3,1.5) -- (0.3,1.25) -- (0.55,1.25); \draw[->] (X) -- (Z) node[midway, below] {$s$}; \draw[->] (Y) -- (Z) node[midway, right] {$t$}; \draw[->, dashed] (A) -- (P) node[midway, above right] {$u$}; \draw[->, black, bend right=25] (A) to node[midway, left] {$f_1$} (X); \draw[->, black, bend left=18] (A) to node[midway, above] {$f_2$} (Y); \end{tikzpicture} $$ A cone over the corner-shaped diagram has three legs, but the leg into $Z$ is determined by either of the other two, so a cone is the same thing as a commutative square over the cospan; the pullback is the universal one.[^lein-pb] When $Z$ is a terminal object the commutativity condition is vacuous and the pullback degenerates to the product $X \times Y$: products are pullbacks over $1$. ### Pullbacks in Set In $\mathbf{Set}$ the pullback of $X \xrightarrow{s} Z \xleftarrow{t} Y$ always exists and has an explicit description: $$ X \times_Z Y \;=\; \{(x, y) \in X \times Y \mid s(x) = t(y)\}, $$ with $p_1(x,y) = x$ and $p_2(x,y) = y$: the subset of the product on which the two routes to $Z$ agree. Two familiar constructions are special cases.[^lein-pbset] - **Inverse images.** Given $f : X \to Y$ and a subset $Y' \subseteq Y$, the square formed by $f^{-1}Y' \hookrightarrow X$, the restriction $f' : f^{-1}Y' \to Y'$, and the inclusions into $X$ and $Y$ is a pullback. Preimage is pullback along the inclusion. - **Intersections.** For subsets $X, Y \subseteq Z$, the square of inclusions with $X \cap Y$ in the corner is a pullback; it is the previous case with $f$ itself an inclusion. > **Worked example.** Let $X = \{x_1, x_2, x_3\}$, $Y = \{y_1, y_2\}$, and $Z = > \{0, 1\}$, with $s : X \to Z$ sending $x_1, x_2 \mapsto 0$ and $x_3 \mapsto 1$, > and $t : Y \to Z$ sending $y_1 \mapsto 0$, $y_2 \mapsto 1$. Then > $$ > X \times_Z Y = \{(x, y) \mid s(x) = t(y)\} > = \{(x_1, y_1), (x_2, y_1), (x_3, y_2)\}. > $$ > The pairs collect one fiber at a time: over $0$ the fiber > $\{x_1, x_2\} \times \{y_1\}$ contributes two pairs, over $1$ the fiber > $\{x_3\} \times \{y_2\}$ contributes one. The projections $p_1(x, y) = x$ and > $p_2(x, y) = y$ satisfy $s \circ p_1 = t \circ p_2$ by construction, and any > commutative square $(f_1, f_2)$ over the cospan factors through the pairing > $\bar f(a) = (f_1(a), f_2(a))$. $$ % caption: Pullback in Set: the fibered product collects the pairs that map to % the same point of Z, one fiber at a time. \begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} % Z as a base line \draw[black, thick] (0,0) -- (5.2,0); \node[black, anchor=west] at (5.35,0) {$Z$}; \fill[black] (2.6,0) circle (1.6pt); \node[anchor=north] at (2.6,-0.1) {$z$}; % X above left \draw[acc, thick] (0.3,2.2) -- (2.1,2.2); \node[acc, anchor=east] at (0.15,2.2) {$X$}; \fill[acc] (1.2,2.2) circle (1.6pt); \node[acc, anchor=south] at (1.2,2.3) {$x$}; % Y above right \draw[acc, thick] (3.1,2.2) -- (4.9,2.2); \node[acc, anchor=west] at (5.05,2.2) {$Y$}; \fill[acc] (4.0,2.2) circle (1.6pt); \node[acc, anchor=south] at (4.0,2.3) {$y$}; % maps down to z \draw[->, black] (1.2,2.05) -- (2.5,0.15); \node[black] at (1.35,1.0) {$s$}; \draw[->, black] (4.0,2.05) -- (2.7,0.15); \node[black] at (3.85,1.0) {$t$}; % the pair \node[draw, acc, inner sep=2.5pt, font=\footnotesize] at (2.6,3.3) {$(x;\,y)$ with $s(x) = t(y)$}; \end{tikzpicture} $$ The same formula computes pullbacks in $\mathbf{Grp}$, $\mathbf{Vect}_k$, and $\mathbf{Top}$, with the structure carried along componentwise: the fibered product of groups is a subgroup of the direct product, and in $\mathbf{Top}$ the set $X \times_Z Y$ takes the subspace topology from the product. A worked topological pullback appears in [computing limits in concrete categories](/category-theory/limits-colimits/computing-limits). Barr and Wells read the $\mathbf{Set}$ pullback computationally: if a deterministic, terminating program fragment is an arrow $f : D \to E$ on states, and a postcondition is a subset $S \subseteq E$, then the pullback $f^{-1}(S)$ of $S$ along $f$ is the **weakest precondition** guaranteeing $S$. For $f(x) = x + 1$ and postcondition $x < 24$, the pullback is $\{x \mid x + 1 < 24\} = \{x \mid x < 23\}$.[^bw-wp] ## Monomorphisms through the limit lens Pullbacks detect and preserve monics. > **Lemma (Monic as a pullback).** An arrow $f : X \to Y$ is monic if and only > if the square with both legs $\mathrm{id}_X$ on top and $f$ on both sides, > > $$ > \begin{array}{ccc} > X & \xrightarrow{\;\mathrm{id}\;} & X \\ > {\scriptstyle \mathrm{id}} \downarrow & & \downarrow {\scriptstyle f} \\ > X & \xrightarrow{\;f\;} & Y > \end{array} > $$ > > is a pullback square.[^lein-monic] Unwound, the square is a pullback exactly when every pair $a, b : A \to X$ with $f \circ a = f \circ b$ arises from a unique arrow $A \to X$ equalizing both projections, which forces $a = b$. Any functor that preserves limits therefore preserves monics, since it preserves this square. The forgetful functors $\mathbf{Grp} \to \mathbf{Set}$ and $\mathbf{Vect}_k \to \mathbf{Set}$ [preserve limits](/category-theory/limits-colimits/limits-and-functors), so monic homomorphisms coincide with the injective ones. > **Lemma (Stability of monics).** In any pullback square, if $t : Y \to Z$ is > monic then so is its pullback $p_1 : X \times_Z Y \to X$. Briefly: a pullback > of a monic is monic.[^bw-monic-stab] > **Proof.** Take $a, b : A \to X \times_Z Y$ with $p_1 a = p_1 b$. Then $t > \circ p_2 a = s \circ p_1 a = s \circ p_1 b = t \circ p_2 b$, and $t$ monic > gives $p_2 a = p_2 b$. Agreement on both projections is agreement on the > mediating description of the pullback, so $a = b$. $\square$ The set-level version of this lemma is the fact that the preimage of a subset is a subset. It makes "subobject of $X$" a notion stable under change of base, which is the starting point for the subobject calculus in topos theory. > **Worked example.** In $\mathbf{Set}$ take $X = \{1, 2, 3\}$ and $Y = \{2, 3, > 4\}$ as subsets of $Z = \{1, 2, 3, 4\}$, with both inclusions monic. Their > pullback is > $$ > X \times_Z Y = \{(x, y) \mid x = y\} = \{(2, 2), (3, 3)\}, > $$ > in bijection with the intersection $X \cap Y = \{2, 3\}$. The projection $p_1 : > X \times_Z Y \to X$ has image $\{2, 3\}$ and is the inclusion $X \cap Y > \hookrightarrow X$, again monic: pulling the mono $Y \hookrightarrow Z$ back > along $X \hookrightarrow Z$ returns a mono, as the stability lemma predicts. ## The pasting lemma Pullback squares compose sideways, and the composition law has a partial converse. > **Theorem (Pasting lemma).** Consider a commutative diagram of two squares > sharing a middle edge, with outer rectangle formed by composing them. If the > right square is a pullback, then: the left square is a pullback if and only > if the outer rectangle is a pullback.[^sim-paste] $$ % caption: Two pullback squares pasted along a common edge. With the right % square a pullback, the left square and the outer rectangle stand or fall % together. \begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} \node (A) at (0,1.8) {$A$}; \node (B) at (2.6,1.8) {$B$}; \node (C) at (5.2,1.8) {$C$}; \node (D) at (0,0) {$D$}; \node (E) at (2.6,0) {$E$}; \node (F) at (5.2,0) {$F$}; \draw[->] (A) -- (B); \draw[->] (B) -- (C); \draw[->] (D) -- (E); \draw[->] (E) -- (F); \draw[->] (A) -- (D); \draw[->] (B) -- (E); \draw[->] (C) -- (F); \node[acc] at (3.9,0.9) {pullback}; \node[black] at (1.3,0.9) {?}; \draw[acc, thick] (2.9,1.5) -- (2.9,1.25) -- (3.15,1.25); \end{tikzpicture} $$ One direction says pullbacks paste: stacking a pullback of a pullback gives a pullback of the composite. The other says pullbacks cancel from the right: if the composite rectangle and the right square are both pullbacks, the left square is forced to be one. The lemma is used constantly, for instance to show that pulling back a composite monic factorization behaves well, and its dual form holds verbatim for pushouts. ## Generating all limits Products handle discrete data; equalizers impose equations. Every limit is these two steps performed once each. > **Theorem (Products and equalizers suffice).** Let $\mathcal{A}$ be a > category. > > - If $\mathcal{A}$ has all products and equalizers, it has all (small) > limits. > - If $\mathcal{A}$ has binary products, a terminal object, and equalizers, it > has all finite limits.[^lein-suffice] The construction mirrors the $\mathbf{Set}$ formula. Given $D : \mathsf{I} \to \mathcal{A}$, form two products, one over the nodes and one over the edges of the shape, and the parallel pair between them whose components compare "apply $D(u)$ then project" with "project at the target": $$ \lim_{\mathsf{I}} D \;=\; \mathrm{Eq}\Bigl(\; \prod_{I \in \mathsf{I}} D(I) \;\rightrightarrows\; \prod_{u : J \to K} D(K) \;\Bigr), $$ where the $u$-component of one map is $D(u) \circ \mathrm{pr}_J$ and of the other is $\mathrm{pr}_K$. The equalizer selects exactly the "tuples" whose coordinates are compatible with every edge of the diagram, which is the cone condition. Pullbacks in particular can be built this way, and there are two companion generation results in the same spirit: | Have | Get | Construction | | --- | --- | --- | | products + equalizers | all limits | equalizer inside a product | | binary products + $1$ + equalizers | finite limits | same, finitely | | pullbacks + $1$ | finite limits | products as pullbacks over $1$, equalizers from pullbacks | The third row is Barr and Wells' variant: with a terminal object, the product $X \times Y$ is the pullback of $X \to 1 \leftarrow Y$, and equalizers can then be extracted from pullbacks of pairing maps, so pullbacks and a terminal object already give finite completeness.[^bw-pbterm] $$ % caption: Every limit factors through the generic construction: a product of % the nodes, a product of the edge-targets, and an equalizer selecting the % compatible families. \begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize, bx/.style={draw, minimum width=27mm, minimum height=10mm, align=center}] \definecolor{acc}{HTML}{4A6FA5} \node[bx, draw=acc, text=acc, thick] (L) at (0,0) {$\lim D$}; \node[bx] (P1) at (4.4,0) {product over nodes}; \node[bx] (P2) at (9.2,0) {product over edges}; \draw[->, acc, thick] (L) -- (P1) node[midway, above] {equalizer}; \draw[->] (5.8,0.1) -- (7.8,0.1) node[midway, above] {$s$}; \draw[->] (5.8,-0.1) -- (7.8,-0.1) node[midway, below] {$t$}; \end{tikzpicture} $$ To verify that a category is complete or finitely complete, exhibit products and equalizers and stop. That is how $\mathbf{Set}$, $\mathbf{Grp}$, $\mathbf{Top}$, and $\mathbf{Vect}_k$ were shown complete under [cones and limits](/category-theory/limits-colimits/limits), how compact Hausdorff spaces inherit completeness from Tychonoff's theorem plus closed-subset equalizers, and how finite limits in $\mathbf{Vect}_k$ reduce to direct sums, the zero space, and kernels. Reversing every arrow turns these constructions into the [dual ones](/category-theory/limits-colimits/colimits): coequalizers and pushouts. [^lein-fork]: **Leinster**, _Basic Category Theory_, §5.1 — forks and Definition 5.1.11 of the equalizer. [^lein-conefork]: **Leinster**, _Basic Category Theory_, §5.1, Examples 5.1.21(b) — a cone on a parallel pair is a fork, so the limit of shape $\mathsf{E}$ is the equalizer. [^sim-eq]: **Simmons**, _An Introduction to Category Theory_, §2.6, Definition 2.6.2 and Example 2.6.5 — equalizers defined by the mediating property, and the solution-set equalizer in $\mathbf{Set}$. [^lein-eq-ex]: **Leinster**, _Basic Category Theory_, §5.1, Examples 5.1.12–5.1.15 — equalizers in $\mathbf{Set}$, $\mathbf{Top}$, $\mathbf{Grp}$ (kernels), and $\mathbf{Vect}_k$. [^lein-regular]: **Leinster**, _Basic Category Theory_, §5.2, Exercise 5.2.25 — split, regular, and plain monics; regularity in $\mathbf{Ab}$ and its failure in $\mathbf{Top}$. [^lein-pb]: **Leinster**, _Basic Category Theory_, §5.1, Definition 5.1.16 and Examples 5.1.21(c) — pullbacks and their identification as limits of shape $\mathsf{P}$; the fibered-product terminology and the product-over-$1$ remark. [^lein-pbset]: **Leinster**, _Basic Category Theory_, §5.1, Examples 5.1.17 — pullbacks in $\mathbf{Set}$: the fibered product, inverse images, and intersections. [^bw-wp]: **Barr & Wells**, _Category Theory for Computing Science_, §9.3.5 — weakest preconditions as pullbacks of postcondition subobjects along the program arrow. [^lein-monic]: **Leinster**, _Basic Category Theory_, §5.1, Lemma 5.1.32 — $f$ is monic iff the identity-identity square over $f$ is a pullback. [^bw-monic-stab]: **Barr & Wells**, _Category Theory for Computing Science_, §9.3.4 — a pullback of a monic is monic; also Leinster, Exercise 5.1.42, and Simmons, Exercise 2.7.4. [^sim-paste]: **Simmons**, _An Introduction to Category Theory_, §2.7, Exercise 2.7.3 — the two-cell pasting result for pullbacks; also Leinster, Exercise 5.1.35. [^lein-suffice]: **Leinster**, _Basic Category Theory_, §5.1, Proposition 5.1.26 and the discussion following it — building arbitrary limits from products and equalizers via the two comparison maps. [^bw-pbterm]: **Barr & Wells**, _Category Theory for Computing Science_, §9.3.7 — a category with a terminal object and all pullbacks has all finite limits; Leinster, Exercise 5.1.39.