Understanding the Small Object Argument

Abstract

The small object argument is a transfinite construction which, starting from a set of maps in a category, generates a weak factorisation system on that category. As useful as it is, the small object argument has some problematic aspects: it possesses no universal property; it does not converge; and it does not seem to be related to other transfinite constructions occurring in categorical algebra. In this paper, we give an “algebraic” refinement of the small object argument, cast in terms of Grandis and Tholen’s natural weak factorisation systems, which rectifies each of these three deficiencies.

Appendix: Algebraically-free Implies Free

The purpose of this Appendix is to sketch a proof of the following result:

Theorem A.1

Let (L, R) be a n.w.f.s. on ${\mathcal C}$ which is algebraically-free on $I \colon {\mathcal J} \to {\mathcal C}^\mathbf 2$ . Then (L, R) is free on ${\mathcal J}$.

Proof

We first define a monoidal structure on the category $\mathbf{CAT} / {\mathcal C}^\mathbf 2$. Given $U \colon {\mathcal A} \to {\mathcal C}^\mathbf 2$ and $V \colon {\mathcal B} \to {\mathcal C}^\mathbf 2$, their tensor product $W \colon {\mathcal A} \otimes {\mathcal B} \to {\mathcal C}^\mathbf 2$ is obtained by first taking the pullback and then defining the projection W by W(a, b) = Ua ∘ Vb. The unit for this tensor product is the object $(s_0 \colon {\mathcal C} \to {\mathcal C}^\mathbf 2)$, where s ₀ is the functor induced by homming the unique map $\sigma_0 \colon \mathbf 2 \to \mathbf 1$ into ${\mathcal C}$; thus $s_0(c) = \mathrm{id}_c \colon c \to c$.

Next, we show that, for any n.w.f.s. (L, R) on ${\mathcal C}$, the object $(U_{\mathsf L} \colon \mathsf L\text-\mathbf{Map} \to {\mathcal C}^\mathbf 2)$ is a monoid with respect to this monoidal structure: the key point being that, given L-map structures on $f \colon X \to Y$ and $g \colon Y \to Z$, we may define an L-map structure on $gf \colon X \to Z$. Indeed, if these two L-map structures are provided by morphisms $s \colon Y \to Kf$ and $t \colon Z \to Kg$ (as in Section 2.15), then the L-map structure on the composite gf is given by:

$$ Z \xrightarrow{t} Kg \xrightarrow{K(s, \mathrm{id}_Z)} K(g \circ \rho_f) \xrightarrow{K(K(1, g), 1)} K\rho_{gf} \xrightarrow{\pi_{gf}} K(gf)\text. $$

The remaining details are routine; and by dualising, we see that $U_{\mathsf R} \colon \mathsf R\text-\mathbf{Map} \to {\mathcal C}^\mathbf 2$ is also a monoid in $\mathbf{CAT}/{\mathcal C}^\mathbf 2$.

We may now show that, if $\alpha \colon ({\mathsf L}, {\mathsf R}) \to ({\mathsf L}', {\mathsf R}')$ is a map of n.w.f.s.’s, then the induced functors $(\alpha_l)_\ast \colon \mathsf L\text-\mathbf{Map} \to {\mathsf L}'\text-\mathbf{Map}$ and $(\alpha_r)^\ast \colon {\mathsf R}'\text-\mathbf{Map} \to \mathsf R\text-\mathbf{Map}$ are maps of monoids; so that the semantics functors ${\mathcal G}$ and ${\mathcal H}$ may be lifted to functors

$$\begin{array}{rll} \hat {\mathcal G} \colon \mathbf{NWFS}({\mathcal C}) & \to &\mathbf{Mon}(\mathbf{CAT}/{\mathcal C}^\mathbf 2) \\ \text{and} \qquad \hat {\mathcal H} \colon \mathbf{NWFS}({\mathcal C}) & \to & \big(\mathbf{Mon}\left(\mathbf{CAT}/{\mathcal C}^\mathbf 2\right)\big)^\mathrm{op}\text. \end{array}$$

We now arrive at a crucial juncture in the proof: we show that $\hat {\mathcal G}$ and $\hat {\mathcal H}$ are fully faithful. In the case of $\hat {\mathcal G}$, for example, we consider n.w.f.s.’s (L, R) and (L′, R′) on ${\mathcal C}$, and a map of monoids $F \colon \mathsf L\text-\mathbf{Map} \to {\mathsf L}'\text-\mathbf{Map}$ over ${\mathcal C}^\mathbf 2$; and must show that there is a unique morphism $\alpha \colon ({\mathsf L}, {\mathsf R}) \to ({\mathsf L}', {\mathsf R}')$ for which F = (α _l )_∗. To do this, we consider squares of the following form: We can make ρ′ _f into an R′-map, since it is the free R′-map on f. Similarly, we can make λ _f into an L-map; and by applying the functor $F \colon \mathsf L\text-\mathbf{Map} \to {\mathsf L}'\text-\mathbf{Map}$, we may make it into an L′-map. Now we apply the lifting operation associated with (L′, R′) to obtain a morphism $\alpha_f \colon Kf \to K'f$. These maps α _f provide the components of a morphism between the underlying functorial factorisations of (L, R) and (L′, R′): it remains only to check that the comonad and monad structures are preserved. This is just a matter of checking details, but makes essential use of two facts: that F is a map of monoids; and that the distributivity axiom holds in (L, R) and (L′, R′).

Next, we prove that for any category $U \colon {\mathcal A} \to {\mathcal C}^\mathbf 2$ over ${\mathcal C}^\mathbf 2$, the category ${\mathcal A}^\pitchfork \to {\mathcal C}^\mathbf 2$ is a monoid in $\mathbf{CAT}/{\mathcal C}^\mathbf 2$. The key point is to show that, whenever we equip morphisms $f \colon C \to D$ and $g \colon D \to E$ of ${\mathcal C}$ with coherent choices of liftings against the elements of ${\mathcal A}$, we induce a corresponding equipment on the composite gf. Indeed, given $a \in {\mathcal A}$ and a square we obtain a lifting $\phi_{gf}(a, h, k) \colon B \to C$ by first forming the lifting $j := \phi_g(a, fh, k) \colon B \to D;$ and then the lifting $\phi_f(a, h, j) \colon B \to C$.

We may now check that if $F \colon {\mathcal A} \to {\mathcal B}$ is a morphism of $\mathbf{CAT}/{\mathcal C}^\mathbf 2$, then the morphism $F^\pitchfork \colon {\mathcal B}^\pitchfork \to {\mathcal A}^\pitchfork$ respects the monoid structures on ${\mathcal A}^\pitchfork$ and ${\mathcal B}^\pitchfork$, so that the functors $(\text{--})^\pitchfork$, and dually ${}^\pitchfork(\text{--})$, lift to functors

$$\begin{array}{rll} (\text{--})^\pitchfork & \!\colon\!& (\mathbf{CAT}/{\mathcal C}^\mathbf 2)^\mathrm{op} \to \mathbf{Mon}(\mathbf{CAT}/{\mathcal C}^\mathbf 2) \\ \text{and} \qquad {}^\pitchfork(\text{--}) & \!\colon\!& \mathbf{CAT}/{\mathcal C}^\mathbf 2 \to \big(\mathbf{Mon}(\mathbf{CAT}/{\mathcal C}^\mathbf 2)\big)^\mathrm{op}\text. \end{array}$$

Finally, we may show that for any n.w.f.s. (L, R) on ${\mathcal C}$, the canonical operation of lifting $\textsf{lift} \colon \mathsf R\text-\mathbf{Map} \to \mathsf L\text-\mathbf{Map}^\pitchfork$ is a monoid morphism in $\mathbf{CAT}/{\mathcal C}^\mathbf 2$. Again, this is simply a matter of checking details.

We now have all the material we need to prove the Theorem. We suppose ourselves given a n.w.f.s. (L, R) which is algebraically-free on $I \colon\! {\mathcal J} \!\to\! {\mathcal C}^\mathbf 2$ via the morphism $\eta \colon {\mathcal J} \to \mathsf L\text-\mathbf{Map}$: and are required to show that (L, R) is free on ${\mathcal J}$. So consider a further n.w.f.s. (L′, R′) on ${\mathcal C}$, and a morphism $F \colon {\mathcal J} \to {\mathsf L}'\text-\mathbf{Map}$ over ${\mathcal C}^\mathbf 2$. We can form the following diagram of functors over ${\mathcal C}^\mathbf 2$:

By algebraic-freeness, the composite along the top is invertible, and so we obtain from this diagram a functor ${\mathsf R}'\text-\mathbf{Map} \to {\mathsf R}\text-\mathbf{Map}$. But every map in the diagram is a map of monoids, and hence the induced functor ${\mathsf R}'\text-\mathbf{Map} \to {\mathsf R}\text-\mathbf{Map}$ is too; and so is induced by a unique morphism of n.w.f.s.’s $\alpha \colon ({\mathsf L}, {\mathsf R}) \to ({\mathsf L}', {\mathsf R}')$.

It requires a little more work to show (α _l )_∗ ∘ η = F, and that α is the unique morphism of n.w.f.s.’s with this property. The two essential facts that we need are that, for any n.w.f.s. (L, R), the canonical morphism $\mathsf L\text-\mathbf{Map} \to {}^\pitchfork(\mathsf R\text-\mathbf{Map})$ is a monomorphism; and that, for any morphism of n.w.f.s.’s $\alpha \colon ({\mathsf L}, {\mathsf R}) \to ({\mathsf L}', {\mathsf R}')$, the following diagram commutes: We leave these details to the reader.□