Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 119 (Introduction to Category Theory)

A monomorphism $m:A\to B$ is left cancellable: $mu=mv$ implies $u=v$ for all parallel arrows into $A$. A strong monomorphism is a monomorphism with the following lifting property: if $e:X\to Y$ is an epimorphism and $u:X\to A$, $v:Y\to B$ satisfy $mu=ve$, there is a diagonal $d:Y\to A$ with $de=u$ and $md=v$. It is unique by monicity. An extremal monomorphism is a monomorphism $m$ for which every factorization $m=he$ with $e$ an epimorphism forces $e$ to be an isomorphism. We use the strong lifting formulation for the paper's terminology; below we also justify its equivalence with the extremal formulation under the complete, well-powered hypotheses. A regular monomorphism is an equalizer of two parallel arrows.

First, a strong monomorphism is extremal. In a factorization $m=he$, apply its lifting property with upper arrow $1_A$ and lower arrow $h$. This gives $d$ with $de=1_A$. Since $e$ is an epimorphism, $ede=e$ implies $ed=1$, so $e$ is an isomorphism.

If $m:A\to B$ is an equalizer of $r,s:B\rightrightarrows C$, consider a lifting square as above. The equation $rve=smu=sve$ and the epimorphism property give $rv=sv$. The equalizer property therefore gives a unique $d$ with $md=v$. Monicity then gives $de=u$. Hence every regular monomorphism is a strong monomorphism.

For the intersection of strong subobjects, let $m_i:A_i\to B$ be strong and let $p_i:P\to A_i$ exhibit their intersection, with $m=m_1{p}_1=m_2{p}_2$. Given $mu=ve$ with $e$ an epimorphism, the two strong monomorphisms supply diagonals $d_i:Y\to A_i$ satisfying $d_{i}e=p_{i}u$ and $m_i{d}_i=v$. The pullback in a category property supplies $d:Y\to P$ with $p_{i}d=d_i$. Its two projections show $de=u$, and $md=v$. Thus the intersection is strong. The same argument works for every existing small intersection of strong monomorphisms. Also, composites of strong monomorphisms are strong: first lift through the outer one, then through the inner one.

Write $\mathcal{S}$ for the full subcategory formed by every saturated object with respect to anodyne morphisms, using the paper's anodyne morphism in a category convention. Let $m:C\to B$ be a strong monomorphism and $B$ saturated. For an anodyne morphism in a category $e:X\to Y$ and $u:X\to C$, saturation extends $mu$ to $v:Y\to B$. Since $e$ is an epimorphism, the strong lifting property supplies $d:Y\to C$ extending $u$. Therefore every strong subobject of a saturated object is saturated.

Now assume $\mathcal{C}$ is a complete category and a well-powered category, with the given saturated embeddings. Choose a monomorphism $a:A\to B$ into a saturated object. Intersect all strong subobjects of $B$ through which $a$ factors. They form a set by the well-powered category hypothesis, and the identity of $B$ is one of them. Completeness constructs their intersection, so we obtainBy the intersection of strong subobjects, $m$ is strong; hence $LA$ is saturated. Since $a$ is a monomorphism, so is ${\eta }_A$.

To prove that ${\eta }_A$ is an epimorphism, take $u,v:LA\rightrightarrows D$ with $u{\eta }_A=v{\eta }_A$. Their equalizer $j:E\to LA$ is a regular monomorphism, and ${\eta }_A$ factors through it. The composite $mj:E\to B$ is strong, so it belongs to the family defining $LA$. Minimality gives $t:LA\to E$ with $mjt=m$. Cancelling $m$ gives $jt=1_{LA}$; since $j$ is a monomorphism, also $tj=1_E$. Thus $j$ is an isomorphism and $u=v$. We have provedThis is the saturated reflection from a strong-subobject intersection.

The construction of a least strong subobject and the equalizer argument work for any morphism into any object, without requiring the source map to be monic or the target to be saturated. They give an epimorphism followed by a strong monomorphism. Applying this factorization to an extremal monomorphism makes the first factor invertible; thus the extremal and strong formulations agree under the present complete, well-powered hypotheses.

For every saturated $S$, saturation extends every $f:A\to S$ across the anodyne morphism in a category ${\eta }_A$ to $\bar{f}:LA\to S$. Its extension is unique because ${\eta }_A$ is an epimorphism. Consequentlynaturally in $S$ and $A$. In particular, for $h:A\to A^{\prime }$ define $Lh$ by $Lh{\eta }_A={\eta }_{A^{\prime }}h$; uniqueness proves the identity and composition laws. This constructs the reflector and proves that $\mathcal{S}$ is a reflective subcategory.

Finally we prove that $\mathcal{S}$ is a balanced category. If $e:U\to V$ is epic in $\mathcal{S}$ and $u,v:V\to X$ satisfy $ue=ve$, embed $X$ by a monomorphism $j:X\to Y$ into a saturated object. Fullness makes $ju,jv$ arrows of $\mathcal{S}$, so $ju=jv$ and hence $u=v$. Thus an epimorphism in $\mathcal{S}$ is also epic in $\mathcal{C}$.

A monomorphism $f:U\to V$ in $\mathcal{S}$ is also monic in $\mathcal{C}$: for $a,b:X\to U$, extend them uniquely along ${\eta }_X$ to $\bar{a},\bar{b}:LX\to U$. If $fa=fb$, cancellation of the ambient epimorphism ${\eta }_X$ gives $f\bar{a}=f\bar{b}$, so monicity in $\mathcal{S}$ gives $\bar{a}=\bar{b}$ and $a=b$. Now if $f$ is both monic and epic in $\mathcal{S}$, it is an anodyne morphism in a category in $\mathcal{C}$. Saturation of $U$ extends $1_U$ across $f$ to $r:V\to U$ with $rf=1_U$. Ambient epicity gives $fr=1_V$. Fullness puts this inverse in $\mathcal{S}$, proving

First address the unnumbered preliminaries. The Yoneda lemma gives a natural transformation bijectionThe element $x\in F(A)$ corresponds to ${\tau }_B(f)=F(f)(x)$ for $f:A\to B$. These bijections are natural in $A$ and $F$; the contravariant form replaces $\mathcal{C}(A,-)$ by $\mathcal{C}(-,A)$.

Let $E=(1\downarrow F)$ be the category of elements. Its objects are $(A,x)$ with $x\in F(A)$; an arrow $u:(A,x)\to (B,y)$ is $u:A\to B$ with $F(u)(x)=y$. Since $\mathcal{C}$ is a small category, $E$ is small. Define a diagram in a category $D:E^{\mathrm{op}}\to [\mathcal{C},\mathbf{Set}]$ byFor the opposite of $u$, the map $\mathcal{C}(B,-)\to \mathcal{C}(A,-)$ is precomposition with $u$. The Yoneda lemma gives a cocone under a diagram $D\to F$ whose $(A,x)$ component sends $f:A\to B$ to $F(f)(x)$.

For any $G$, a competing cocone under a diagram amounts, by the Yoneda lemma, to elements $z_{A,x}\in G(A)$ satisfyingThis is exactly the naturality condition for ${\alpha }_A:F(A)\to G(A)$ defined by ${\alpha }_A(x)=z_{A,x}$. It gives a unique natural transformation $\alpha :F\to G$ factoring the cocone. Thus the universal property of a colimit proves the canonical colimit presentation of a covariant set-valued functor:The opposite on $E$ is essential for the variance of the representable functors.

We now prove the four conditions equivalent by the cycle $(i)\Rightarrow (ii)\Rightarrow (iii)\Rightarrow (iv)\Rightarrow (i)$. Suppose $F$ is a finite-limit-preserving set-valued functor. For a finite diagram in a category in the comma category $(S\downarrow F)$, write its objects as $(A_i,s_i:S\to F(A_i))$. Take $L={\lim }_i{A}_i$ in $\mathcal{C}$. Since $F$ preserves this finite limit, the compatible maps $s_i$ determine a unique $s:S\to F(L)$ whose composites with $F(L)\to F(A_i)$ are $s_i$. The pair $(L,s)$ has the required categorical limit property in $(S\downarrow F)$, by the same universal properties. For the empty diagram, $F(1)$ is a singleton, so there is exactly one map $S\to F(1)$; this provides the terminal object. Hence $(i)\Rightarrow (ii)$ for every set $S$.

Apply condition $(ii)$ with the singleton $S=1$. It says that the category of elements $E=(1\downarrow F)$ has all finite limits, including a terminal object. The opposite category $E^{\mathrm{op}}$ therefore has all finite colimits. In particular it is nonempty; two objects map to their binary coproduct in a category; and any parallel arrows are equalized by their coequalizer. These are precisely the conditions for a filtered category. Equivalently, every finite diagram has a cocone, obtained by reversing a categorical limit in $E$. Thus

By the canonical colimit presentation of a covariant set-valued functor established in the first part,Each vertex is a representable functor. Under condition $(iii)$ the indexing category of elements, with its arrows reversed, is a filtered category, so this is a filtered colimit in a category. Therefore $(iii)\Rightarrow (iv)$, with the requested diagram itself providing the filtered presentation.

Suppose $F\cong {\mathrm{colim}}_{j\in J}{R}_j$, where $J$ is a filtered category and every $R_j$ is a representable functor. Every covariant representable functor $\mathcal{C}(A,-)$ preserves all existing categorical limits: maps from $A$ into a limiting object are exactly compatible families of maps into its diagram.

For a finite diagram in a category $K:I\to \mathcal{C}$, use pointwise colimits in the functor category, preservation by each $R_j$, and the permitted result that filtered colimits commute with finite limits in sets to obtainThe isomorphism is the canonical comparison, since every step respects the limiting projections. This also covers the empty finite diagram and hence the terminal object. Thus $(iv)\Rightarrow (i)$, completing the cycle:

The terminal object $1$ is an exponentiable object because $-\times 1\cong 1_{\mathcal{C}}$ has the identity as a right adjoint. If $A$ and $B$ are exponentiable objects, compose the two adjunctions to getConsequently exponentiable objects are closed under finite products in a category, including the empty product, and

Under the additional hypotheses, a coseparator $S$ detects unequal parallel arrows by postcomposition: for $u\ne v:X\to B$ there is $t:B\to S$ with $tu\ne tv$. Local smallness makes $I=\mathcal{C}(B,S)$ a set, and completeness forms the product in a category $S^I$. The evaluation arrowis a monomorphism, because $e_{B}u=e_{B}v$ forces $tu=tv$ for every $t$, and the coseparator then forces $u=v$.

By hypothesis this monomorphism is a regular monomorphism, so it is an equalizer of some $r,s:S^I\rightrightarrows Q$. Apply the same evaluation construction to $Q$: $J=\mathcal{C}(Q,S)$ is a set and $e_Q:Q\to S^J$ is monic. Cancelling $e_Q$ shows that equalizing $e_{Q}r,e_{Q}s$ is equivalent to equalizing $r,s$. We have therefore proved the equalizer presentation by powers of a coseparator:The notation $S^I$ here means a product indexed by a set, so its existence does not presuppose categorical exponentiation.

If $A$ is an exponentiable object, $\mathcal{C}(-\times A,S)\cong \mathcal{C}(-,S^A)$ is a representable functor. Conversely, suppose a representing object $E$ and a natural isomorphismare given. For any set $I$, the product in a category property givesThus maps into all powers of $S$ have representations. For an equalizer presentation $B\to S^I\rightrightarrows S^J$ with arrows $r,s$, postcomposition induces natural transformations between these represented functors. The Yoneda lemma identifies them with arrows $r_A,s_A:E^I\rightrightarrows E^J$. Form their equalizer $B_A$. ThenThese bijections are natural in $X$. For a morphism $B\to C$, postcomposition and the Yoneda lemma give the unique arrow $B_A\to C_A$ respecting them; uniqueness proves functoriality. Hence $B\mapsto B_A$ is a right adjoint to $-\times A$. This proves the exponentiability test using a coseparator:

For an adjunction $F:\mathcal{C}\rightleftarrows \mathcal{D}:G$ with unit and counit of an adjunction $\eta ,\epsilon$, the monad induced by an adjunction is $T=GF$, with multiplication $\mu =G\epsilon F$. Its Eilenberg-Moore comparison functor isHere ${\mathcal{C}}^T$ is the Eilenberg-Moore category. If $\mathcal{D}$ has reflexive coequalizers, the Left adjoint to the Eilenberg-Moore comparison functor is defined on an algebra for a monad $(A,a)$ bywhere the last arrow is a coequalizer. The parallel pair has common section $F{\eta }_A$, so it is a reflexive pair. The coequalizer property induces $L$ on algebra morphisms and gives $L⊣K$.

Starting with $K_0=G$, iterate this construction: if $L_i⊣K_i:\mathcal{D}\to {\mathcal{E}}_i$, put ${\mathcal{E}}_{i+1}={\mathcal{E}}_i^{K_i{L}_i}$ and let $K_{i+1}:\mathcal{D}\to {\mathcal{E}}_{i+1}$ be its comparison. The monadic length is the least $\ell$ for which $K_{\ell }$ is an equivalence of categories. Thus an equivalence has length zero, and an already monadic adjunction whose right adjoint is not an equivalence has length one. The assumed reflexive coequalizers ensure the needed left adjoints; in the example we identify them explicitly.

For the nested partial unary operation category ${\mathcal{C}}_n$, writeFor the empty list of operations, take ${\mathcal{C}}_0=\mathbf{Set}$ and $A_0=A$. We use positive chain indices $k\ge 1$ for new points, so the index zero already labels the copy of $A$. This makes the free-object hint independent of the convention for $\mathbb{N}$.

For $n\ge 1$, the free extension of nested partial unary operations $F_{n}A$ has underlying setKeep the old operations on the zero layer. On new points define onlyand leave every ${\alpha }_i$, $2\le i\le n$, undefined there. Define the new top operation byand leave it undefined elsewhere. These are precisely the permitted domains: the first unary operation on every new point moves it, so none of the higher operations is defined there. When $n=0$, take $F_{0}A=A\times {\mathbb{N}}_{\ge 0}$ with ${\alpha }_1(a,k)=(a,k+1)$. In either case the unit is $a\mapsto (a,0)$.

For $B\in {\mathcal{C}}_{n+1}$, let its operations be ${\beta }_i$. Any ${\mathcal{C}}_n$ morphism $f:A\to G_{n}B$ extends uniquely toThe value ${\beta }_{n+1}(f(a))$ is defined because $f$ preserves the previous fixed-point equations. The extension respects the top operation at old fixed points and respects the first operation along each new chain; there are no other defined operations on those chains to check. Uniqueness follows from the same forced formulas. For $n=0$ the formula is $\bar{f}(a,k)={\beta }_1^k(f(a))$. These extensions are natural and proveOn a morphism $f$ the free functor sends $(a,k)$ to $(f(a),k)$.

Crucially, the top operation of $F_{n}A$ has no fixed points: its defined old values move to new points, and it has no defined new values when $n\ge 1$; for $n=0$ it is the shift. The next free extension therefore adds no points and equips the object with an everywhere-undefined next operation. The same remains true at every subsequent free extension. Hence, for $m>n$, the composite left adjoint $F_{m-1}\cdots F_n$ has the same first $n+1$ operations and underlying set as $F_n$.

This agreement includes the monad structure, not just its underlying endofunctor. The units are the same zero-layer inclusions. The composite counit on an object of ${\mathcal{C}}_m$ is the same forced extension formula, depending only on its first $n+1$ operations. Applying the composite forgetful functor therefore gives the same multiplication $G_n\epsilon F_n$. Thus

Next prove creation of the required split coequalizers. Suppose $f,g:B\rightrightarrows C$ are arrows in ${\mathcal{C}}_{n+1}$ and their images have a split coequalizer $q:C\to Q$ in ${\mathcal{C}}_n$. Choose the splitting orientationwith $s:Q\to C$, $t:C\to B$ morphisms in ${\mathcal{C}}_n$. Denote the top operations on $B,C$ by $b,c$. For $z\in Q_n$ defineSince $s$ preserves the lower operations, $s(z)\in C_n$ and this value exists. For $y\in C_n$, $t(y)\in B_n$, so preservation by $f,g$ givesThus $q$ respects the top operation. The splitting $s$ and $qs=1$ also show that this is the unique operation on its prescribed domain $Q_n$ for which $q$ is a morphism. For $n=0$ all these domains mean the whole underlying set.

If $u:C\to D$ is a ${\mathcal{C}}_{n+1}$ morphism equalizing $f,g$, its unique factor $v:Q\to G_{n}D$ in ${\mathcal{C}}_n$ satisfies, on $Q_n$,where $d$ is the top operation of $D$. Hence $v$ is a ${\mathcal{C}}_{n+1}$ morphism. This proves $G_n$ creates coequalizers of $G_n$-split pairs.

Moreover, $G_n$ reflects isomorphisms: an isomorphism of the first $n$ operations reflects their fixed-point conditions, hence the domain of the next operation; the inverse of a bijective top-operation-preserving map then preserves that operation too. The Beck monadicity theorem now givesUnder this equivalence, the first Eilenberg-Moore comparison functor for the long composite is exactly forgetting all operations after the $(n+1)$st: its algebra structure is the top-operation extension formula already computed. Repeating the argument identifies its monadic tower with the successive categoriesAt each stage the corresponding comparison has the remaining composite of the already constructed free extensions as a left adjoint.

No earlier stage can be an equivalence of categories. For $j<m$, take the two-point set with its first $j$ operations all identities. One extension to ${\mathcal{C}}_m$ has every later operation the identity; another has its $(j+1)$st operation interchange the two points, and all subsequent operations undefined. Both have the same image in ${\mathcal{C}}_j$, but the identity function between those images is not a morphism between the extensions. Thus forgetting from ${\mathcal{C}}_m$ to ${\mathcal{C}}_j$ is not full. The final comparison at $j=m$ is an equivalence. This proves the monadic tower for nested partial unary operations has

First supply the unlettered preliminaries. Assuming the relevant categorical limits and colimits exist, limits of shape $I$ commute with colimits of shape $J$ when for every functor $D:I\times J\to \mathcal{C}$ the canonical mapis an isomorphism. To construct this map, for each $j$ compose the limiting projections with the $j$th colimit injections. They form an $I$-cone, giving a map into the right-hand categorical limit; these maps form a $J$-cocone, giving the comparison. This specifies the actual comparison required for commutation of limits and colimits.

A group regarded as a one-object category has its group elements as arrows, with composition given by multiplication. A functor from it to the Category of sets is a group action. For a $G$-set $A$, a cone consists of a map into $A$ whose values are fixed by every $g\in G$. Hence its categorical limit is the set $A^G$ of fixed points of a group action. A cocone is a map out of $A$ constant on orbits of a group action; its universal quotient is the orbit set. Thus

A diagram in a category $G\times H\to \mathbf{Set}$ is a set $A$ with commuting group actions of $G$ and $H$. Its limit–colimit comparison isCommutation makes $A^G$ stable under $H$. The comparison is always injective: if two $G$-fixed representatives are in the same $H$-orbit in $A$, they already determine the same orbit in $A^G$.

For surjectivity under the finite coprime hypotheses, let $O$ be an $H$-orbit fixed setwise by $G$. Its size divides $|H|$ by the orbit-stabilizer theorem. Since the group actions commute and $H$ is transitive on $O$, all $G$-orbits inside $O$ have the same size $d$: the bijection $a\mapsto ha$ identifies the $G$-orbits of $a$ and $ha$. Thus $d$ divides $|O|$, while the orbit-stabilizer theorem also gives $d\mid |G|$. The orders are coprime, so $d=1$. Every point in $O$ is therefore $G$-fixed, and $O$ lies in the image of $\theta$. We have proved commutation of fixed points and orbit quotients for coprime groups:The bijection is the canonical comparison and is natural in the set with commuting group actions, so it proves the requested commutation of limits and colimits in the Category of sets.

Let $q:G\twoheadrightarrow K$ and $r:H\twoheadrightarrow K$ be the two quotient homomorphisms. On the underlying set $A=K$, define the commuting group actionsThe inverse is essential for the right multiplication formula to define a left group action: $h_1\cdot (h_2\cdot k)=kr(h_2{)}^{-1}r(h_1{)}^{-1}=(h_1{h}_2)\cdot k$. Left and right multiplication commute.

Because $q$ is onto and $K$ is nontrivial, there is no fixed point of a group action for $G$: if every $q(g)k=k$, cancellation would make every element of $K$ the identity. Thus $A^G=\varnothing$. Because $r$ is onto, the $H$-action is transitive and $A/H$ is a singleton. The induced $G$-action on that singleton is trivial. Consequently the comparison iswhich is not an isomorphism. This proves the common quotient obstruction to commutation of fixed points and orbits, so limits of shape $G$ do not commute with colimits of shape $H$ in the Category of sets.

An abelian category is an additive category with a kernel in a category and a cokernel in a category for every morphism, in which every monomorphism is a kernel and every epimorphism is a cokernel. In particular, every epimorphism $p$ is the cokernel of its own kernel: if $p$ is initially a cokernel of $u$, then $u$ factors through $\ker p$, and the two cokernel universal properties agree. The dual statement holds for monomorphisms. Finite biproducts and kernels construct finite limits.

For pullback stability of epimorphisms in an abelian category, let $p:B\to C$ be an epimorphism and $k:C^{\prime }\to C$ any morphism. The mapis epic, since its restriction to the $B$ summand is $p$. Its kernel in a category $i=(h,p^{\prime }):B^{\prime }\to B\oplus C^{\prime }$ exhibits the pullback in a category: the equation $d(h,p^{\prime })=0$ means $ph=k{p}^{\prime }$ and has exactly that universal property.

Suppose $v:C^{\prime }\to D$ satisfies $v{p}^{\prime }=0$. The morphism $[0,v]:B\oplus C^{\prime }\to D$ annihilates $i$, so, because $d$ is the cokernel in a category of $i$, it factors as $[0,v]=wd$ for some $w:C\to D$. Restricting to $B$ gives $wp=0$, and epicity gives $w=0$. Hence $v=0$. Applying this to the difference of any two morphisms agreeing after $p^{\prime }$ proves that $p^{\prime }$ is an epimorphism. ThereforeThis proof uses normality from the definition, rather than assuming the stability to be proved.

For the pullback of a short exact sequence in an abelian category, use the displayed square's notation $g,g^{\prime },h,k$. Exactness makes $f:A\to B$ the kernel in a category of $g$. Since $gf=0=k0$, the pullback in a category gives a uniqueIf $u:X\to B^{\prime }$ has $g^{\prime }u=0$, then $g(hu)=k{g}^{\prime }u=0$, so there is a unique $v:X\to A$ with $fv=hu$. Both projections of the pullback give $f^{\prime }v=u$: their composites with $h$ are equal and their composites with $g^{\prime }$ are zero. The uniqueness of $v$ follows from monicity of $f$. Thus $f^{\prime }$ is the kernel in a category of $g^{\prime }$. By the preceding stability result, $g^{\prime }$ is an epimorphism. We obtain the required exact sequence in an abelian category:

Finally form the pullback in a category $E=P{\times }_C{P}^{\prime }$ of the two projective presentations. Pulling back each of their short exact sequences in an abelian category givesBecause each of $P^{\prime }$ and $P$ is a projective object in a category, the respective final epimorphisms have sections: lift their identity morphisms through those epimorphisms. The usual additive category splitting argument identifies each middle object with the biproduct of its kernel and quotient. Explicitly, a kernel inclusion $j$ and section $s$ give the isomorphism $[j,s]$ from that biproduct to the middle object; $1-sq$ factors through $j$ and provides its inverse's kernel component. Henceand we conclude the Schanuel lemma in an abelian category: