Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 26 (Category Theory)

A monad on $\mathcal{C}$ consists of an endofunctor $T$ and natural transformations $\eta :1\to T$, $\mu :T^2\to T$ satisfying $\mu T\eta =\mu \eta T=1_T$ and $\mu T\mu =\mu \mu T$. Its Eilenberg-Moore category has objects $(X,a)$ with $a:TX\to X$, $a{\eta }_X=1_X$ and $a{\mu }_X=aTa$. A morphism $f:(X,a)\to (Y,b)$ satisfies $fa=bTf$. An adjunction $F⊣G$, with unit $\eta$ and counit $\epsilon$, induces $T=GF$, $\mu =G\epsilon F$. It is a monadic adjunction if the Eilenberg-Moore comparison functor $K(D)=(GD,G{\epsilon }_D)$ is an equivalence with the Eilenberg-Moore category.

A fork $A\stackrel{p,q}{\rightrightarrows }B\stackrel{r}{\to }C$ is a split coequalizer if $rp=rq$ and there are $s:C\to B$, $t:B\to A$ with $rs=1$, $pt=1$ and $qt=sr$. It is indeed a coequalizer: if $hp=hq$, then $h=hpt=hqt=hsr$, so $h$ factors uniquely through $r$, which is split epic. Every functor preserves these splitting identities, making such coequalizers absolute.

The precise monadicity theorem states: for an adjunction $F:\mathcal{C}\rightleftarrows \mathcal{D}:G$, the comparison is an equivalence if and only if $G$ reflects isomorphisms and every pair in $\mathcal{D}$ whose $G$-image admits a split coequalizer has a coequalizer which $G$ preserves. Equivalently, the right adjoint creates these split-underlying coequalizers, with creation understood up to the canonical isomorphism of the prescribed underlying coequalizer. Here is a proof.

First consider the forgetful functor from monad algebras. It reflects isomorphisms: the inverse of an invertible algebra morphism also obeys the algebra-morphism identity, by multiplying that identity by the inverses. For an algebra pair with a split underlying coequalizer $r:B\to C$, all powers of $T$ preserve its coequalizer. If $b:TB\to B$ is the algebra structure on $B$, the map $rb$ coequalizes $Tp,Tq$, so there is a unique $c:TC\to C$ withThe unit law follows by composing with the epimorphism $r$: $c{\eta }_{C}r=cTr{\eta }_B=rb{\eta }_B=r$. For associativity, naturality and the algebra law giveCancel the epimorphism $T^{2}r$ to obtain $c{\mu }_C=cTc$. Thus $(C,c)$ is an algebra and $r$ is an algebra morphism. Any algebra morphism coequalizing the pair factors through $r$ on underlying objects, and its factor is an algebra morphism by cancellation of the epimorphism $Tr$. This creates the coequalizer. Transporting these facts through an equivalence proves necessity.

For sufficiency, let $(X,a)$ be a $T$-algebra. In $\mathcal{D}$ consider the free pairIts underlying pair is ${\mu }_X,Ta:T^{2}X\rightrightarrows TX$, with split coequalizer $a:TX\to X$: the splittings are $s={\eta }_X$ and $t={\eta }_{TX}$, using the algebra unit law, the monad unit law and naturality of $\eta$. By hypothesis its coequalizer $q:FX\to D$ exists and is preserved. Identify $GD$ with $X$ by the unique coequalizer isomorphism, so $Gq=a$. Naturality of the counit makes $Kq$ an algebra morphism, hence the comparison structure $c$ on $GD$ satisfies $cTa=a{\mu }_X=aTa$. The map $Ta$ is split epic because $a{\eta }_X=1$, so $c=a$. Every algebra is therefore isomorphic to a comparison algebra.

For an actual object $D$, its counit ${\epsilon }_D:FGD\to D$ is a coequalizer of the analogous free pair. It coequalizes that pair by counit naturality. Compare it with the coequalizer furnished by the hypothesis; applying $G$ gives an isomorphism, since both underlying arrows coequalize the same split pair. Reflection of isomorphisms makes the comparison map an isomorphism. This proves the counit's asserted coequalizer property.

Let $f:KD\to KE$ be an algebra morphism. Its transpose is $h_0={\epsilon }_{E}Ff:FGD\to E$. The two composites of $h_0$ with the free pair have adjunct transposes $G{\epsilon }_{E}Tf$ and $fG{\epsilon }_D$, equal because $f$ is an algebra morphism. Consequently $h_0$ factors uniquely through ${\epsilon }_D$ as $h:D\to E$. Applying $G$ gives $(Gh)G{\epsilon }_D=fG{\epsilon }_D$; the last factor is split epic, so $Gh=f$. Conversely any lift of $f$ must satisfy $h{\epsilon }_D={\epsilon }_{E}Ff$ by naturality and hence is unique. Thus $K$ is full and faithful, and the earlier construction makes it essentially surjective. The comparison is an equivalence, completing the theorem's proof.

Now take $G:\mathbf{CompHaus}\to \mathbf{Set}$. Its left adjoint exists by the permitted topological result; it can be realized as the Stone-Čech compactification of the discrete input set. A bijective continuous map from a compact space to a Hausdorff space is a homeomorphism, so $G$ reflects isomorphisms.

For continuous $f,g:X\rightrightarrows Y$ with a split underlying fork $q,s,t$, let $R$ be the relation of having the same $q$-image. We claimFor the forward inclusion choose $x=t(y)$, $x^{\prime }=t(y^{\prime })$: $ft=1$ and $gt=sq$ supply the equality. For the reverse inclusion use $qf=qg$. The subset $\{(x,x^{\prime }):g(x)=g(x^{\prime })\}\subset X^2$ is closed, because $Y$ is Hausdorff, and compact. Its continuous image $R\subset Y^2$ is compact and hence closed. A closed equivalence relation on a compact Hausdorff space has a compact Hausdorff quotient; its quotient map is a coequalizer here, since it identifies exactly the generated relation. Its underlying set coequalizer is the specified one up to the unique isomorphism. Thus $G$ preserves the needed coequalizers, andThe closedness argument is the closed relation generated by a set-split pair of compact Hausdorff maps lemma; the splitting maps themselves need not be continuous.

Theorems matter at least as much as definitions: they show when a categorical description captures actual mathematical structure. Definitions in category theory are exceptionally economical, but economy alone does not explain their applications.

An adjunction compresses a universal mapping property into natural hom-set bijections. The free-group adjunction, for example, records that assigning images to generators extends uniquely to a homomorphism. That is a useful definition, but proving that a free group exists and satisfies this property still requires mathematics. The definition organizes that proof rather than replaces it.

The Yoneda lemma offers a sharper example. A representable functor is easy to define; the theorem identifying natural transformations out of it with elements of another functor gives the definition its computational force. The representation of a set-valued functor as a colimit of representables is then a substantive consequence, and the theorem that filtered colimits commute with finite limits turns it into a criterion for finite-limit preservation. None of these conclusions follows merely from choosing attractive terminology.

Likewise a monad packages operations and their compatibility, while the Eilenberg-Moore category defines the corresponding algebras. The Beck monadicity theorem answers a different question: whether a given category is really recovered by that algebraic description. Applying it to compact Hausdorff spaces needs a topological argument about closed quotient relations. The definitions would not by themselves predict or justify the result.

Finally, abelian categories put kernels in a category, cokernels in a category and exactness into a setting where homological arguments can be reused. Some consequences, such as image factorization, become short because strong structural content has deliberately been included in the definition. Yet left derived functors, long exact sequences and the detection of projective objects supply information about obstructions to exactness which the terminology alone cannot provide.

Definitions and theorems therefore play complementary roles. A good definition states what should be invariant across examples; a theorem proves which constructions preserve it, which examples satisfy it, and what can be deduced from it. Category theory makes that partnership unusually visible, rather than making proofs less important.

The comma category $(A\downarrow F)$ has objects $(C,u)$ with $C\in \mathcal{C}$ and $u:A\to FC$ a set map. A morphism $(C,u)\to (D,v)$ is an arrow $h:C\to D$ such that $Fh\circ u=v$. Composition and identities are those of $\mathcal{C}$. For $A=1$, this is the category of elements $E$ of $F$: objects are $(C,x)$ with $x\in FC$ and arrows satisfy $Fh(x)=y$.

Associate to $(C,x)$ the covariant representable functor $H_C=\mathcal{C}(C,-)$. An arrow $h:(C,x)\to (D,y)$ of $E$ gives, by precomposition, $H_D\to H_C$. Thus this is a diagram $H:E^{\mathrm{op}}\to [\mathcal{C},\mathbf{Set}]$. There is a compatible natural map $H_C\to F$ sending $f:C\to B$ to $Ff(x)$.

Colimits in this functor category are pointwise. At an object $B$, the induced map from the colimit sends a class represented by $(C,x,f:C\to B)$ to $Ff(x)$. It is surjective because $z\in FB$ is represented by $(B,z,1_B)$. It is injective because every representative with value $z$ is identified with that same canonical representative: the arrow $f:(C,x)\to (B,z)$ in $E$ becomes an arrow of the indexing diagram sending $1_B$ to $f$. These bijections are natural in $B$, provingSmallness of $\mathcal{C}$ and set-valuedness of $F$ ensure that $E$ is small, so the displayed colimit is defined. This proves the introductory density request before the three equivalent conditions.

Assume $F$ preserves finite limits. Fix any set $A$ and a finite diagram of objects $(C_j,u_j)$ in $(A\downarrow F)$. Let $L$ be the categorical limit of its underlying diagram in $\mathcal{C}$, with projections $p_j$. Preservation gives $FL\cong {\lim }_{j}F{C}_j$. The maps $u_j:A\to F{C}_j$ form a compatible cone, so determine a unique $u:A\to FL$ with $F{p}_j\circ u=u_j$.

The object $(L,u)$ is the categorical limit in the comma category. Indeed a cone from $(B,v)$ gives a unique underlying $h:B\to L$, and the identities $F{p}_{j}Fhv=F{p}_{j}u$ for all $j$ force $Fhv=u$ by the categorical limit's uniqueness. For the empty diagram, $L$ is terminal and $FL$ is a one-element set, giving the unique map from $A$. Thus $(A\downarrow F)$ has all finite limits. This proves $\boxed{\text{(i)}\Rightarrow \text{(ii)}}$.

Take $A=1$. By assumption $E=(1\downarrow F)$ has finite limits, so $E^{\mathrm{op}}$ has finite colimits. A filtered category is nonempty, admits a cocone over every pair of objects, and admits a coequalizing arrow for every parallel pair. The initial object of $E^{\mathrm{op}}$ gives nonemptiness, its binary coproducts give the required two-object cocones, and its coequalizers equalize parallel arrows. Consequently $\boxed{\text{(ii)}\Rightarrow \text{(iii)}}$. These statements also handle the otherwise possible empty category of elements.

Every covariant representable functor preserves categorical limits: arrows from its representing object into a limiting object are exactly compatible cones of arrows into the diagram. Apply the density formula proved in the root solution. For any finite diagram $D:J\to \mathcal{C}$,The middle isomorphism uses exactly the permitted theorem that filtered colimits commute with finite limits in sets; it applies because $E^{\mathrm{op}}$ is filtered. All maps are the natural comparison maps, so $F$ preserves finite limits, including the terminal object. This proves $\boxed{\text{(iii)}\Rightarrow \text{(i)}}$ and completes the equivalence.

A balanced category is one in which every morphism that is both monic and epic is an isomorphism. If a faithful functor sends $f$ to an isomorphism, then $f$ is monic: equality $fg=fh$ becomes $FfFg=FfFh$, cancellation gives $Fg=Fh$, and faithfulness gives $g=h$. The same argument on the other side makes $f$ epic. Balance therefore makes $f$ an isomorphism. Thus a faithful functor out of a balanced category reflects isomorphisms.

Under the adjunction, the transpose of $Ff:FX\to FA$ is ${\eta }_{A}f:X\to GFA$. Hence if $F$ is faithful, ${\eta }_{A}f={\eta }_{A}g$ forces $Ff=Fg$ and then $f=g$, making every ${\eta }_A$ monic. Conversely, if the unit is pointwise monic and $Ff=Fg$, naturality gives ${\eta }_{B}f=GFf{\eta }_A=GFg{\eta }_A={\eta }_{B}g$, whence $f=g$. ThereforeWe also use the standard adjunction fact with its justification: $F$ is full and faithful exactly when $\eta$ is invertible. Indeed the composite hom-set map $\mathcal{C}(X,A)\to \mathcal{D}(FX,FA)\cong \mathcal{C}(X,GFA)$ is postcomposition by ${\eta }_A$. If $F$ is full and faithful these maps are bijective; taking $X=GFA$ produces a right inverse, and taking $X=A$ gives injectivity and therefore a left inverse. Conversely an invertible unit makes these hom-set maps bijective.

For the final example, view the two-element ordered set $0<1$ as a category $\mathcal{C}$, and let $\mathcal{D}$ have one object and only its identity. The unique $F:\mathcal{C}\to \mathcal{D}$ is left adjoint to the functor $G$ selecting $1$, since every $\mathcal{C}(x,1)$ is a singleton. Every arrow in an ordered-set category is monic, so the unit arrows $x\to 1$ and the identity counit are monic. But $F$ is not full: $\mathcal{C}(1,0)$ is empty whereas $\mathcal{D}(F1,F0)$ is a singleton. The example does not contradict the upcoming equivalence because $\mathcal{C}$ is not balanced; its arrow $0\to 1$ is both monic and epic but not invertible.

Assume both unit and counit are monic. The unit criterion makes $F$ faithful. The triangle identity is ${\epsilon }_{FA}F{\eta }_A=1_{FA}$. Since ${\epsilon }_{FA}$ is monic, this split epimorphism is an isomorphism: cancelling it in ${\epsilon }_{FA}(F{\eta }_A{\epsilon }_{FA})={\epsilon }_{FA}$ gives $F{\eta }_A{\epsilon }_{FA}=1$. Thus $F{\eta }_A$ is invertible. As $\mathcal{C}$ is balanced, the reflection result in the root solution makes ${\eta }_A$ invertible. Hence $F$ is full and faithful.

Let $q:FA\to B$ be a regular epimorphism. Its adjunct factorization is $q={\epsilon }_{B}Fh$ for $h:A\to GB$. A regular epimorphism is extremal: if a coequalizer $q$ factors through a monomorphism $m$, its other factor also coequalizes the defining pair, descends through $q$, and gives a right inverse for $m$; monicity then makes $m$ invertible. Apply this to the monic ${\epsilon }_B$. More explicitly, if $q$ coequalizes $r,s$, monicity gives $Fhr=Fhs$, so there is $d:B\to FGB$ with $dq=Fh$. Then ${\epsilon }_{B}dq=q$ implies ${\epsilon }_{B}d=1$, and monicity gives $d{\epsilon }_B=1$. Therefore $B\cong FGB$. The image is closed under regular quotients, proving $\boxed{\text{(i)}\Rightarrow \text{(ii)}}$.

Assume $F$ is full and faithful and its image is closed under regular quotients. Its unit is invertible, hence monic. Factor the counit using the hypothesis on $\mathcal{D}$:with $e$ regular epic and $m$ monic. Closure gives $I\cong F{A}^{\prime }$ for some $A^{\prime }$. A right adjoint preserves monomorphisms: postcomposition with $Gm$ on $\mathcal{C}(X,-)$ corresponds under adjunction to postcomposition with $m$ on $\mathcal{D}(FX,-)$, which is injective. Thus $Gm$ is monic.

The triangle identity and invertibility of ${\eta }_{GB}$ give $G{\epsilon }_B=({\eta }_{GB}{)}^{-1}$, so $GmGe$ is invertible. A monomorphism whose composite with another arrow is an isomorphism is itself split epic and hence an isomorphism; therefore both $Gm$ and $Ge$ are isomorphisms. The arrow $e$ is between objects in the essential image of the full and faithful $F$. After choosing $I\cong F{A}^{\prime }$, write it as $Fh$. Naturality of the invertible unit identifies $GFh$ with $h$, so $Ge$ invertible implies $h$ and hence $e$ invertible. Now ${\epsilon }_B=me$ is monic. This proves $\boxed{\text{(ii)}\Rightarrow \text{(i)}}$.

Since the full endofunctor subcategory contains $1$ and is closed under composition, $1,T^2,T^3$ all belong to it. Terminality supplies unique natural transformations $\eta :1\to T$ and $\mu :T^2\to T$. The monad unit laws compare arrows $T\to T$, both necessarily the unique endomorphism, namely the identity. The associativity law compares arrows $T^3\to T$, again necessarily equal. Every monad structure uses these two unique arrows, so $\boxed{T\text{ has a unique monad structure}}$.

For a monad $S$ with underlying functor in the subcategory, the unique $\alpha :S\to T$ is a monad morphism. Its unit and multiplication compatibility compare, respectively, arrows $1\to T$ and $S^2\to T$ and therefore follow from terminality. A $T$-algebra $a:TX\to X$ restricts to the $S$-algebra $b=a{\alpha }_X$. The unit law is immediate. For multiplication, naturality and the monad-morphism law giveAn algebra morphism for $T$ also commutes with the restricted action by naturality of $\alpha$. Keeping underlying objects and arrows gives the required functor ${\mathcal{C}}^T\to {\mathcal{C}}^S$.

Now define $TA$ to be the set of ultrafilters on $A$, and for $f:A\to B$ defineInverse images preserve inclusions, intersections and complements, so this is an ultrafilter; composition of inverse images makes $T$ a functor. There are no ultrafilters on the empty set. Every ultrafilter on a disjoint binary union chooses exactly one summand, and restriction to that summand gives an ultrafilter there; extension back is inverse to restriction. Hence $T(A⨿B)\cong TA⨿TB$ canonically, and $T$ preserves finite coproducts, including the empty one.

Let $H$ be any other finite-coproduct-preserving endofunctor. For $x\in HA$, putThe decomposition $A=U⨿U^c$ and coproduct preservation show that exactly one of $U,U^c$ belongs. Refining two subsets into the four disjoint parts $U\cap V,U\setminus V,V\setminus U,(U\cup V{)}^c$ shows that an element lying in both indicated summands lies in their intersection summand. The same refinement for $U\subseteq V$ proves upward closure. Thus ${\alpha }_A(x)$ is an ultrafilter. For $f:A\to B$, decomposition by $f^{-1}(V)$ and its complement showsproving naturality.

For uniqueness, suppose $\beta :H\to T$ is natural. Since $T1$ is a singleton, naturality on the two inclusions $1\to 2$ forces ${\beta }_2$ to send every element in each of the two $H1$ summands of $H2$ to the corresponding principal ultrafilter. Apply naturality to the characteristic map ${\chi }_U:A\to 2$. It gives $U\in {\beta }_A(x)$ precisely when $H{\chi }_U(x)$ lies in the selected summand, which by the decomposition is precisely when $x$ lies in $HU\subseteq HA$. Hence ${\beta }_A={\alpha }_A$ for every $A$. ThereforeThis proves ultrafilter functor. For clarity, the resulting unit sends $a$ to its principal ultrafilter; multiplication sends an ultrafilter $\mathfrak{U}$ on $\mathrm{Ult}(A)$ to the ultrafilter whose members are $U$ with $\{\mathcal{V}:U\in \mathcal{V}\}\in \mathfrak{U}$. Naturality and the monad laws for these formulas also follow from the terminal construction.

An abelian category is an additive category with kernels in a category and cokernels in a category in which the canonical comparison from coimage to image of every morphism is an isomorphism. This is the standard image-coimage form of the definition, equivalently expressed by normality of every monomorphism and epimorphism. Additivity means abelian-group hom-sets with bilinear composition, a zero object and finite biproducts. A sequence is exact at an object when the image of the incoming morphism is the kernel in a category of the outgoing one.

For $f:X\to Y$, construct $q:X\to \mathrm{coim}f=\mathrm{coker}(\ker f)$ and $j:\mathrm{im}f=\ker (\mathrm{coker}f)\to Y$. The universal properties give $f=j\bar{f}q$: first $f$ kills its kernel in a category and factors through $q$; then the resulting map is killed by $\mathrm{coker}f$ because $q$ is epic, so it factors through $j$. The comparison $\bar{f}$ is invertible by the abelian axiom. Cokernels in a category are epic and kernels in a category monic, directly by uniqueness in their universal properties, so $e=\bar{f}q$ is epic and $j$ monic. Thus $\boxed{f=je\text{ is an epimorphism-monomorphism factorization}}$.

In a short exact sequence $0\to X\stackrel{i}{\to }Y\stackrel{p}{\to }Z\to 0$, we have $i=\ker p$ and $p=\mathrm{coker}i$, up to the canonical isomorphisms. If $r:Y\to X$ retracts $i$, the map $1_Y-ir$ kills $i$ and factors as $sp$ for some $s:Z\to Y$. Composing with $p$ gives $psp=p$, so epicity gives $ps=1_Z$. Conversely if $ps=1_Z$, then $1_Y-sp$ is killed by $p$ and factors as $ir$. Composing with $i$ gives $iri=i$, so monicity gives $ri=1_X$. ConsequentlyIn that case $Y\cong X\oplus Z$.

For the derived-functor requests, use additive right exact functors, as customary in abelian homological algebra. An abelian category with enough projectives permits an augmented projective resolution $\cdots \to P_2\to P_1\to P_0\to X\to 0$, obtained by repeatedly taking an epimorphism from a projective onto the previous kernel in a category. Apply $F$ and defineProjective lifts construct maps of resolutions; the comparison and chain-homotopy results make the construction independent of choices and functorial. For a short exact sequence, the horseshoe construction produces a degreewise split short exact sequence of resolutions, hence of their images under additive $F$. Its homology objects give the long exact sequenceThis supplies the requested sketch; detailed comparison and functoriality proofs are not needed here.

A projective object $X$ has a resolution concentrated in degree zero, so $L_{1}F(X)=0$ for every such $F$. Conversely choose $0\to K\stackrel{i}{\to }P\to X\to 0$ with $P$ projective, and take $F=\mathcal{A}(-,K)$ with target ${\mathbf{Ab}}^{\mathrm{op}}$. Precomposition makes this covariant to the opposite category. The usual left exactness of contravariant Hom, which follows directly from the cokernel in a category universal property, says exactly that this $F$ is right exact in that opposite target. If $L_{1}F(X)=0$, the long exact sequence and $L_{1}F(P)=0$ make $F(K)\to F(P)$ monic in ${\mathbf{Ab}}^{\mathrm{op}}$. Equivalently,is epic, hence surjective, in abelian groups. The identity of $K$ has a preimage, giving a retraction of $i$. The sequence splits, and $X$ is a direct summand of $P$, hence projective: a lifting problem for $X$ extends along the projection $P\to X$, is solved for $P$, and restricts along the summand inclusion. ThereforeThis is projectivity detected by all first left derived functors. The following parts prove the three requested equivalent formulations of a hereditary abelian category with enough projectives.

Assume subobjects of projectives are projective. For any object $X$, choose $0\to K\to P\to X\to 0$ with $P$ projective. The kernel in a category $K$ is projective by the assumption. The derived long exact sequence gives a dimension-shifting isomorphismbecause $L_{2}F(P)=L_{1}F(P)=0$. The right side is zero because $K$ is projective. Since $X$ and the right exact functor $F$ were arbitrary, $\boxed{\text{(i)}\Rightarrow \text{(ii)}}$.

Assume $L_{2}F=0$ for every additive right exact functor into an abelian category. Given a subobject $K\hookrightarrow P$ of a projective, let $X$ be its cokernel in a category. The sequence $0\to K\to P\to X\to 0$ is exact, and dimension shifting gives $L_{1}F(K)\cong L_{2}F(X)=0$ for every $F$. The projectivity criterion proved in the root solution makes $K$ projective. This gives (ii)$\Rightarrow$(i).

For any short exact sequence $0\to X\to Y\to Z\to 0$, the long exact sequence now starts at the relevant place withIt is exact because the preceding term $L_{2}F(Z)$ vanishes. This is precisely left exactness of $L_{1}F$, proving $\boxed{\text{(ii)}\Rightarrow \text{(iii)}}$.

Assume $L_{1}F$ is left exact for every additive right exact $F$. For $0\to K\to P\to X\to 0$ with $P$ projective, left exactness makes $L_{1}F(K)\to L_{1}F(P)=0$ a monomorphism. Hence $L_{1}F(K)=0$. Dimension shifting then gives $L_{2}F(X)=0$. As $X,F$ are arbitrary, (iii)$\Rightarrow$(ii), completingThe argument also recovers projectivity of every such kernel in a category directly from the universal first-derived-functor criterion.