Equalizers and Pullbacks

The general limit 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\stackrel{f}{\to }X\rightrightarrows Y$ with $sf=tf$ is called a fork.¹ Many arrows may make a pair equal; the equalizer is the universal one.

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.²

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.³
• $\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$.⁴

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.

Equalizers are monic

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.⁵ 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.

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.⁶ 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\stackrel{s}{\to }Z\stackrel{t}{\leftarrow }Y$ always exists and has an explicit description:

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.⁷

• Inverse images. Given $f:X\to Y$ and a subset $Y^{\prime }\subseteq Y$, the square formed by $f^{-1}{Y}^{\prime }\hookrightarrow X$, the restriction $f^{\prime }:f^{-1}{Y}^{\prime }\to Y^{\prime }$, 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.

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.

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\}$.⁸

Monomorphisms through the limit lens

Pullbacks detect and preserve monics.

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, so monic homomorphisms coincide with the injective ones.

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.

The pasting lemma

Pullback squares compose sideways, and the composition law has a partial converse.

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.

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:

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:

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.¹³

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, 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: coequalizers and pushouts.