Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 23 (Category Theory)

Let $D:I\to \mathcal{C}$ be a finite diagram. Form the finite categorical productsThere are two morphisms $s,t:P\rightrightarrows Q$: their components at $u:i\to j$ are $D(u){\pi }_i$ and ${\pi }_j$, respectively. Let $e:L\to P$ be their equaliser. Then ${\ell }_i={\pi }_{i}e$ satisfy $D(u){\ell }_i={\ell }_j$, so they constitute a cone over a diagram.

Any other cone $x_i:X\to D(i)$ uniquely determines $x:X\to P$. Its cone equations say precisely that $sx=tx$. The equaliser therefore gives a unique $h:X\to L$ with $eh=x$, and thus ${\ell }_{i}h=x_i$. Conversely these component equations force $eh=x$ by the categorical product universal property, so there is exactly one such mediator. This proves that $(L,{\ell }_i)$ is a categorical limit of $D$.

The empty categorical products are included: if $I$ is empty, $P$ and $Q$ are terminal and the construction gives the empty categorical limit. Thus finite categorical products and equalisers give every finite categorical limit, as a special case of the construction of small limits from products and equalizers.

Let $1$ be a terminal object. The pullback of the unique arrows $A\to 1\leftarrow B$ is a binary categorical product: maps $X\to A$ and $X\to B$ automatically have equal composites into $1$, so the pullback universal property is exactly the categorical product universal property.

For parallel arrows $f,g:A\rightrightarrows B$, form $B\times B$ and take the pullback of $⟨f,g⟩:A\to B\times B$ along the diagonal $\delta :B\to B\times B$. Write the resulting projections as $e:E\to A$ and $b:E\to B$. The pullback equation givesIf $u:X\to A$ satisfies $fu=gu$, the pair $(u,fu)$ is a pullback cone, producing a unique $v:X\to E$ with $ev=u$ and $bv=fu$. The second condition is forced by the first, since $b=fe$. Thus $e$ is the equaliser of $f,g$.

The terminal object and iterated binary categorical products give all finite categorical products, including the nullary one. Part (a) therefore proves pullbacks and a terminal object give all finite categorical limits.

For a diagram shape $I$, a functor $F:\mathcal{C}\to \mathcal{D}$ preserves categorical limits of shape $I$ if every limiting cone $(L,{\ell }_i)$ over every diagram $D:I\to \mathcal{C}$ is carried to a limiting cone $(FL,F{\ell }_i)$ over $FD$. It reflects categorical limits of that shape if a cone in $\mathcal{C}$ is limiting whenever its image cone is limiting. These properties concern cones which are given; reflection is not an assertion that every cone in the target lifts.

Suppose $F$ is a full and faithful functor and the image of $(L,{\ell }_i)$ is limiting. A cone $(X,x_i)$ in $\mathcal{C}$ becomes a cone in $\mathcal{D}$, so there is a unique $h:FX\to FL$ with $(F{\ell }_i)h=F{x}_i$. Fullness writes $h=Fk$ for some $k:X\to L$. Faithfulness gives ${\ell }_{i}k=x_i$, and also ensures uniqueness: two such $k$ would have the same image, by uniqueness of $h$. Hence the original cone is limiting. This proves every full and faithful functor reflects categorical limits, the limits reflected by full and faithful functors criterion, with no essential-surjectivity requirement.

Take any limiting cone ${\ell }_i:L\to D(i)$ in $\mathcal{C}$ of the given shape. Since $GF$ preserves such categorical limits, the cone $GF{\ell }_i:GFL\to GFD(i)$ is limiting in $\mathcal{E}$. It is the image under $G$ of the cone $F{\ell }_i$ in $\mathcal{D}$. Reflection by $G$ therefore says that $F{\ell }_i$ is limiting in $\mathcal{D}$. Since this works for every diagram and every limiting cone of the specified shape, $F$ preserves categorical limits of that shape.

Write an object of the slice category $\mathcal{D}/X$ as $a:A\to X$. Its morphisms are arrows in $\mathcal{D}$ commuting with these structure maps, and the forgetful functor $U_X$ removes the structure map.

Suppose a square in the slice becomes a pullback square in $\mathcal{D}$, with vertex $p:P\to X$. Given a compatible pair of slice arrows $u:Z\to A$ and $v:Z\to B$, the underlying pullback gives a unique $h:Z\to P$ with the required projection equations. If $r:P\to A$ is one projection, thenwhere $z:Z\to X$ is the structure map. Thus $h$ is automatically a slice morphism, and underlying uniqueness gives uniqueness in the slice. Hence $U_X$ reflects pullbacks.

Now let $e:(E,c)\to (A,a)$ be an equaliser of slice arrows $f,g:(A,a)\rightrightarrows (B,b)$. Consider any underlying arrow $u:Z\to A$ with $fu=gu$. Give $Z$ the structure map $au:Z\to X$. Then $u$ is a slice arrow into $(A,a)$, and the slice equaliser gives a unique $h:Z\to E$ with $eh=u$. Conversely any underlying $h$ with that equation automatically obeys $ch=aeh=au$, so there are no additional factorization possibilities outside the slice. Therefore $U_{X}e$ has the ordinary equaliser universal property in $\mathcal{D}$. This proves $U_X$ preserves equalisers.

Let ${!}_A:A\to 1$ be the unique arrow to the terminal object of $\mathcal{C}$. DefineThis is a functor into the slice category $\mathcal{D}/F1$, because ${!}_{B}f={!}_A$, and $U_{F1}\hat{F}=F$. The terminal object of this slice is $1_{F1}:F1\to F1$, exactly $\hat{F}(1)$, so $\hat{F}$ preserves the terminal object.

The composite $U_{F1}\hat{F}$ preserves pullbacks by hypothesis, and $U_{F1}$ reflects pullbacks by part (b). Part (a), restricted to the pullback shape, therefore shows that $\hat{F}$ preserves pullbacks. The allowed finite-limit criterion now gives that $\hat{F}$ preserves all finite categorical limits, and hence equalisers. Since $U_{F1}$ preserves equalisers, their composite does too. ThusThis is equalizer preservation by pullback-preserving functors. The factorization supplies terminal-object preservation only in the slice; none is asserted for the original $F$.

Write $H_c=\mathcal{C}(-,c)$. The category of elements $\int P$ of a categorical presheaf $P$ has objects $(c,x)$ with $x\in P(c)$; a morphism $(c,x)\to (d,y)$ is $u:c\to d$ satisfying $P(u)y=x$. It is a small category because $\mathcal{C}$ is small and each $P(c)$ is a set. Consider the diagram sending $(c,x)$ to $H_c$ and $u$ to the natural transformation given by postcomposition with $u$.

There is a canonical cocone ${\alpha }_{c,x}:H_c\to P$ withFunctoriality makes it a natural transformation, and the equation $P(u)y=x$ makes these transformations a cocone.

To prove its universal property, let $Q$ be any categorical presheaf with a compatible cocone ${\beta }_{c,x}:H_c\to Q$. DefineFor $u:c\to d$ and $y\in P(d)$, compatibility with the arrow $(c,P(u)y)\to (d,y)$ givesThus $t:P\to Q$ is natural. Naturality of each ${\beta }_{c,x}$ shows $t{\alpha }_{c,x}={\beta }_{c,x}$. Conversely any transformation with these equations must have the displayed values $t_c(x)$, so it is unique. We have proved the canonical colimit presentation of a presheaf:

A Cartesian closed category has finite categorical products and, for every $P,Q$, an exponential object $Q^P$ with an evaluation morphism $\mathrm{ev}:Q^P\times P\to Q$ such that composition with evaluation gives natural bijectionsFinite categorical products in the presheaf category are pointwise; in particular its terminal object is the constant singleton categorical presheaf. For categorical presheaves $P,Q$ defineFor $u:d\to c$, restriction sends $\alpha$ to $\alpha \circ (H_u\times 1_P)$. Composition and identity laws follow from those of the Yoneda embedding, so this is a categorical presheaf.

Define evaluation at $c$ by ${\mathrm{ev}}_c(\alpha ,x)={\alpha }_c(1_c,x)$. For $u:d\to c$, naturality of $\alpha$ gives $Q(u){\alpha }_c(1_c,x)={\alpha }_d(u,P(u)x)$, which is the evaluation of the restricted pair. Hence evaluation is a natural transformation.

Given $t:R\times P\to Q$, its currying sends $z\in R(c)$ to the transformation whose component at $a$ isNaturality in $a$ follows from that of $t$, and naturality in $c$ follows by composing $v$ with the relevant arrow. Evaluating $\hat{t}$ at $(1_c,x)$ recovers $t_c(z,x)$. Conversely, if $s:R\to Q^P$, naturality of $s$ along $v:a\to c$ says that evaluating $s_a(R(v)z)$ at $(1_a,x)$ gives $(s_c(z){)}_a(v,x)$. Thus currying the evaluation of $s$ recovers $s$. These constructions are inverse and natural, proving the universal property. This is the exponential in a presheaf category, and proves the presheaf category is Cartesian closed.

The Yoneda embedding preserves categorical products: for any $a$, maps $a\to c\times Y$ correspond naturally to pairs of maps $a\to c$ and $a\to Y$. Hence $H_{c\times Y}\cong H_c\times H_Y$. Using the exponential in a presheaf category, the Yoneda lemma and the exponential universal property in $\mathcal{C}$ givesEvery bijection is natural in $c$, since it is given by precomposition or the natural exponential adjunction. Thus these component bijections are a natural isomorphism of categorical presheaves:

The Yoneda embedding sends $c$ to the representable presheaf $H_c=\mathcal{C}(-,c)$. On a morphism $f:c\to d$, it sends a map $u:a\to c$ to $fu:a\to d$, giving $H_f:H_c\to H_d$.

The Yoneda lemma states that for every categorical presheaf $P$ there is a bijection, natural in both variables,Its inverse sends $x\in P(c)$ to the transformation $u:a\to c\mapsto P(u)x$. Apply it to $P=H_d$ to obtainUnder this bijection $H_f$ corresponds exactly to $f$, so the map induced by the embedding on each hom-set is bijective. Therefore the Yoneda embedding is full and faithful.

The equations $pi=1_A$ give $(ip)i=i$, so $i$ equalizes $ip$ and $1_B$. If $h:X\to B$ satisfies $(ip)h=h$, put $k=ph:X\to A$. Then $ik=iph=h$. If $k^{\prime }$ is another such factorization, applying $p$ gives $k^{\prime }=pi{k}^{\prime }=ph=k$. This provesIn particular the inclusion in a retract in a category is a monomorphism.

By part (b), $i:P\to H_B$ is the equaliser of $ip$ and $1_{H_B}$. Full faithfulness of the Yoneda embedding writes $ip=H_b$ for a unique endomorphism $b:B\to B$. Choose an equaliser $e:A\to B$ of $b$ and $1_B$ in $\mathcal{C}$.

For each $c$, the maps $c\to A$ are precisely the maps $u:c\to B$ with $bu=u$. Thus $H_e:H_A\to H_B$ is the pointwise equaliser of $H_b$ and $1_{H_B}$, hence their equaliser in the presheaf category. Both $i$ and $H_e$ have the same universal property, so their vertices are isomorphic. This proves the representable retract criterion:

Use 0-presentable object in the specified sense: its hom-functor preserves all small colimits. For a representable $H_c$, the Yoneda lemma identifies this hom-functor with evaluation at $c$. Given any small diagram $P_j$, pointwise colimits giveThese are the canonical comparison bijections, including for an empty diagram. Therefore every representable presheaf is 0-presentable, or a small projective object in this sense.

By the canonical colimit presentation of a presheaf, writewith structure maps ${\alpha }_{c,x}:H_c\to P$. Since $P$ is a 0-presentable object, the canonical mapis bijective. Every element of a set-valued colimit has a representative in some component. In particular $1_P$ is the image of a transformation $s:P\to H_c$ for some $(c,x)$, soThus $P$ is a retract of $H_c$. The representable retract criterion from part (c), using the assumed equalisers in $\mathcal{C}$, now gives $P$ is representable. Only existence of the representative of $1_P$ is needed; no stronger uniqueness-of-factorization assertion about individual colimit injections has been assumed.

A poset becomes a category whose objects are its elements and whose hom-set $X(x,y)$ is a singleton if $x\le y$ and empty otherwise. Reflexivity supplies identity arrows and transitivity supplies composition; all possible composites are unique, so the category axioms hold. Antisymmetry says that isomorphic objects are equal. A functor between such categories is exactly an order-preserving function: an inequality must be sent to an inequality, and there is no further choice of arrow map.

Since the hom-sets in these categories are either empty or singleton, an adjunction $f⊣g$ is precisely the conditionThe hom-set bijections are then the unique possible ones, and naturality is automatic. This is a Galois connection between the two posets.

Equivalently, the monotone functions satisfy the unit and counit inequalities $x\le gf(x)$ and $fg(y)\le y$. The equivalence implies these by taking $y=f(x)$ and $x=g(y)$. Conversely, if the inequalities hold, $f(x)\le y$ implies $x\le gf(x)\le g(y)$, while $x\le g(y)$ implies $f(x)\le fg(y)\le y$.

For $X\subseteq A$, defineBoth are monotone maps $PA\to PB$. For $Y\subseteq B$,so direct image is a left adjoint to inverse image. Also,so the fiberwise universal condition gives the right adjoint. ThereforeAn empty fiber satisfies the universal condition vacuously, so every point outside $p[A]$ belongs to ${\forall }_p(X)$, regardless of $X$. This is essential when $p$ is not surjective.

For a categorical presheaf $P$ on the open subsets, define the functors on objects byTo prove $L⊣\Delta$, a natural transformation $t:P\to \Delta A$ must satisfyfor every open $U$, since the restrictions of $\Delta A$ are identities. Thus it is determined by the function $P(\varnothing )\to A$. Conversely such a function defines all $t_U$ by that equation, and the categorical presheaf restriction laws make the components compatible. HenceFor the other adjunction, a transformation $s:\Delta A\to P$ is determined by its component $s_S:A\to P(S)$, sinceEvery function $A\to P(S)$ supplies compatible components by this formula. Therefore $\mathrm{Nat}(\Delta A,P)\cong \mathrm{Set}(A,P(S))$, giving the adjoints to constant presheaves on open sets:These are adjoints of the stated constant-presheaf functor, with its value at every open set including the empty one; no sheafification is involved.

The Freyd general adjoint functor theorem is as follows. Let $G:\mathcal{D}\to \mathcal{C}$, with $\mathcal{D}$ a complete category which is locally small. Then $G$ has a left adjoint if and only if it preserves all small categorical limits and satisfies the solution-set condition: for each $c\in \mathcal{C}$, there is a set-indexed familysuch that every $u:c\to Gd$ can be written $u=G(h)u_i$ for some $i$ and some $h:d_i\to d$. The target category need not be complete. We prove all the existence steps.

First establish the initial-object lemma for complete categories with a weakly initial set. Let $\mathcal{E}$ be locally small and complete, with a weakly initial set $\{w_i\}$, meaning every object receives a map from at least one $w_i$. Its categorical product $w={\prod }_i{w}_i$ is weakly initial: compose a categorical product projection with the map from the appropriate $w_i$. Local smallness makes $\mathcal{E}(w,w)$ a set. Let $e:v\to w$ be the simultaneous equaliser of every endomorphism of $w$ and the identity. Explicitly it is the equaliser of the two arrowswith components $k$ and $1_w$. Thus $ke=e$ for every endomorphism $k$, and $e$ is monic.

Every object $x$ receives a morphism from $v$, by composing $e$ with a map $w\to x$. To prove uniqueness, take parallel maps $a,b:v\to x$ and their equaliser $m:y\to v$. Weak initiality of $w$ gives $t:w\to y$. The composite $emt$ is an endomorphism of $w$, so $(emt)e=e$. Cancelling the monomorphism $e$ gives $mte=1_v$. Hence $m$ is both monic and a split epimorphism, and is therefore invertible. Since $am=bm$, this forces $a=b$. We have proved $v$ is initial, without using a class-sized categorical product or equaliser.

For sufficiency in the theorem, fix $c$ and consider the comma category $(c\downarrow G)$. Its objects are pairs $(d,u:c\to Gd)$; a morphism $h:(d,u)\to (d^{\prime },u^{\prime })$ satisfies $G(h)u=u^{\prime }$. This category is locally small because each hom-set is a subset of $\mathcal{D}(d,d^{\prime })$. It is complete: for a small diagram of such pairs, take the underlying categorical limit $d$ in $\mathcal{D}$. The arrows from $c$ form a cone to its image under $G$, and preservation of the categorical limit gives a unique $u:c\to Gd$ inducing them. The same universal property gives all mediators in the comma category. The solution-set family is a weakly initial set in this comma category, so the lemma supplies an initial pairFor $f:c\to c^{\prime }$, initiality defines a unique $Ff:Fc\to F{c}^{\prime }$ satisfying $G(Ff){\eta }_c={\eta }_{c^{\prime }}f$. Uniqueness proves the identity and composition laws, making $F$ a functor. Initiality also gives bijectionsThe definition of $Ff$ proves naturality in $c$, and postcomposition proves naturality in $d$. These bijections are the required adjunction $F⊣G$.

For necessity, if $F⊣G$, the single arrow ${\eta }_c:c\to GFc$ is a solution set: the transpose of any $u:c\to Gd$ gives its factorization through ${\eta }_c$. If $d$ is a limiting cone vertex of a small diagram $D_j$ in $\mathcal{D}$, then, naturally in $c$,These are the canonical cone-factorization bijections, so $Gd$ with its image projections is a categorical limit of $G{D}_j$. Thus $G$ preserves all small categorical limits, completing both directions of the theorem.

A monad on $\mathcal{C}$ consists of an endofunctor $T:\mathcal{C}\to \mathcal{C}$ and natural transformations $\eta :1_{\mathcal{C}}\Rightarrow T$ and $\mu :T^2\Rightarrow T$ satisfying, at every object $A$,These are the unit and associativity laws for the unit and multiplication of a monad.

An algebra for a monad is a pair $(A,a)$ with $a:TA\to A$ satisfyingA monad algebra morphism $f:(A,a)\to (B,b)$ is a morphism $f:A\to B$ with $fa=bTf$. Identities satisfy this condition, and composing two such maps preserves it by functoriality of $T$. The resulting Eilenberg-Moore category is denoted ${\mathcal{C}}^T$. Its forgetful functor $U:{\mathcal{C}}^T\to \mathcal{C}$ sends $(A,a)$ to $A$ and leaves the underlying arrows unchanged.

Write the adjunction unit as $\eta :1_{\mathcal{C}}\Rightarrow GF$ and the adjunction counit as $\epsilon :FG\Rightarrow 1_{\mathcal{D}}$. Define the monad induced by an adjunction bywith unit $\eta$. Naturality of $\epsilon$ makes $\mu$ a natural transformation.

The triangle identities for an adjunction give the two unit laws:For associativity, apply naturality of $\epsilon$ to the arrow ${\epsilon }_{FA}:FGFA\to FA$ in $\mathcal{D}$:Applying $G$ yieldsThus the induced data satisfy all the monad laws, rather than merely supplying an endofunctor and two transformations.

Define the free algebra functor byThe monad laws say precisely that ${\mu }_X$ defines an monad algebra structure on $TX$, while naturality of $\mu$ makes $Tf$ an monad algebra morphism. We construct the adjunction explicitly.

For an monad algebra $(A,a)$ and a morphism $f:X\to A$, put $\overline{f}=aTf:TX\to A$. It is an monad algebra morphism becauseConversely, from an monad algebra morphism $h:(TX,{\mu }_X)\to (A,a)$ obtain $h{\eta }_X:X\to A$. These operations are inverse: naturality of $\eta$ and the monad algebra unit law giveand the algebra-morphism equation together with the monad unit law givesThe formulas commute with precomposition in $X$ and composition with monad algebra morphisms in $(A,a)$, so the bijections are natural. Therefore the free-forgetful Eilenberg-Moore adjunction isIts unit is ${\eta }_X$ and its counit at $(A,a)$ is the monad algebra action $a$.

With $T=GF$, unit $\eta$ and multiplication $G\epsilon F$, the Eilenberg-Moore comparison functor isHere $G{\epsilon }_d:T(Gd)=GFGd\to Gd$ is the monad algebra action, and the underlying functor satisfies $UK=G$. The triangle identities and counit naturality provide the monad algebra laws and the compatibility of $Gh$, as required for this definition.

For each algebra for a monad $(A,a)$, consider the specific pair in $\mathcal{D}$Then the exact condition isEach pair is reflexive, with common section $F{\eta }_A$: the two composite identities follow from $a{\eta }_A=1_A$ and ${\epsilon }_{FA}F{\eta }_A=1_{FA}$. Thus existence of all reflexive coequalizers is sufficient, but the displayed specified pairs give the necessary-and-sufficient condition.

To prove it, take $h:FA\to d$ and its adjoint transpose $x=Gh{\eta }_A:A\to Gd$. The transpose of $hFa$ is $xa$, by naturality of $\eta$. The transpose of $h{\epsilon }_{FA}$ isMoreover counit naturality and a triangle identity giveBecause transposition is bijective, the coequalizing equation is therefore equivalent toThe right side says exactly that $x:(A,a)\to Kd$ is a monad algebra morphism.

For sufficiency, choose a coequalizer $q_a:FA\to L(A,a)$ for every monad algebra. Its universal property and the equivalence just proved give natural bijectionsTo see explicitly that the chosen objects form a functor, an monad algebra morphism $u:(A,a)\to (B,b)$ makes $q_{b}Fu$ coequalize the pair for $a$: use $ua=bTu$ and naturality of the counit. Hence there is a unique $Lu$ with $Lu{q}_a=q_{b}Fu$. Uniqueness proves its identity and composition laws and the naturality of the displayed bijections. Thus $L⊣K$.

Conversely, suppose $L⊣K$ with unit ${\lambda }_{(A,a)}:(A,a)\to KL(A,a)$. Transpose its underlying arrow $A\to GL(A,a)$ through $F⊣G$ to obtain $q_a:FA\to L(A,a)$. Since the unit is an monad algebra morphism, the equivalence above shows that $q_a$ coequalizes the specified pair. Any coequalizing $h:FA\to d$ transposes to an monad algebra map $(A,a)\to Kd$, which factors uniquely through the unit by $L⊣K$. Transposing back gives a unique factorization of $h$ through $q_a$. Thus $q_a$ is the required coequalizer. This proves both directions of the Left adjoint to the Eilenberg-Moore comparison functor criterion.

Assume the coequalizers from part (b) exist and write them $q_a:FA\to L(A,a)$. The underlying arrow of the comparison-adjunction unit isWe first relate it to the monad algebra action. Naturality of $\eta$, the coequalizer equation and a monad unit law giveIn $\mathcal{C}$, $a:TA\to A$ is itself a split coequalizer of $Ta,{\mu }_A:T^{2}A\rightrightarrows TA$. Indeed,For an explicit universal-property proof, if $r:TA\to X$ satisfies $rTa=r{\mu }_A$, then $s=r{\eta }_A$ obeysIts uniqueness follows by composing any equation $sa=r$ with ${\eta }_A$.

Now $G{q}_a$ equalizes $Ta$ and ${\mu }_A$. If it is a coequalizer, then $a$ and $G{q}_a$ are coequalizers of the same pair. Their unique comparison map is ${\lambda }_a$, since ${\lambda }_{a}a=G{q}_a$, and is therefore invertible. Conversely, if ${\lambda }_a$ is invertible, $G{q}_a={\lambda }_{a}a$ is an isomorphic copy of the coequalizer $a$, so it is a coequalizer too.

The forgetful functor ${\mathcal{C}}^T\to \mathcal{C}$ reflects isomorphisms: if an monad algebra morphism $u$ has an inverse as an underlying arrow, the equation $ua=bTu$ rearranges to $u^{-1}b=aT(u^{-1})$, making that inverse an monad algebra morphism. Thus underlying invertibility here is exactly invertibility of the unit component. For all monad algebras together, the comparison-adjunction unit criterion isEquivalently, the necessary-and-sufficient conditions for a left adjoint with invertible unit are existence of the coequalizers in part (b) and their preservation by $G$. No preservation of arbitrary coequalizers is required.