Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 18 (Category Theory)

Use the covariant Yoneda embedding $Y(A)=\mathcal{C}(A,-)$. An arrow $f:B\to A$, viewed as an arrow $A\to B$ in the opposite category, induces precomposition $h\mapsto hf$. Identities and composition are preserved because composition in $\mathcal{C}$ is associative.

The covariant Yoneda lemma is the bijectionIts inverse sends $x\in F(A)$ to ${\alpha }_B(h)=F(h)(x)$. This is a natural transformation: for $k:B\to C$, functoriality gives $F(k){\alpha }_B(h)=F(kh)(x)={\alpha }_C(kh)$. Conversely, naturality of an arbitrary $\alpha$ at $h:A\to B$ gives ${\alpha }_B(h)=F(h){\alpha }_A(1_A)$. Evaluation at the identity morphism therefore makes the two constructions inverse. Their formulas also prove naturality in $F$ and, contravariantly, in $A$.

Taking $F=Y(B)$ identifies natural transformations $Y(A)\to Y(B)$ with $\mathcal{C}(B,A)$. Thus $Y$ is full and faithful, and reflects isomorphisms; two image objects are isomorphic exactly when the original objects are isomorphic. It also carries existing colimits in $\mathcal{C}$ to categorical limits of covariant representable functors: maps out of a colimit are exactly compatible families of maps out of its diagram. Equivalently, this embedding preserves existing categorical limits in ${\mathcal{C}}^{\mathrm{op}}$. The direction matters: the paper uses covariant representables, rather than the more usual contravariant Yoneda embedding.

A representation of a functor $F$ is $(A,x)$ with $x\in F(A)$ such that $h\mapsto F(h)(x)$ is a bijection $\mathcal{C}(A,B)\to F(B)$ for every $B$. These bijections are natural by functoriality. The element $x$ is its universal element.

If $(B,y)$ is another representation, universality gives unique arrows $f:A\to B$ and $g:B\to A$ satisfying $F(f)x=y$ and $F(g)y=x$. Consequently $F(gf)x=x=F(1_A)x$, so $gf=1_A$ by injectivity of the representing bijection. Similarly $fg=1_B$. Therefore $f$ is the unique compatible isomorphism. This proves uniqueness of functor representations; uniqueness refers to an isomorphism carrying the specified universal elements to one another, rather than to every isomorphism between the underlying objects.

A monomorphism $m:A\to B$ satisfies $mu=mv\Rightarrow u=v$, and an epimorphism $e:A\to B$ satisfies $ue=ve\Rightarrow u=v$. A strong monomorphism is a monomorphism with the right lifting property against all epimorphisms: every square $mu=ve$ has a diagonal $d$ satisfying $de=u$ and $md=v$. The diagonal is unique by monicity. A regular monomorphism is an equalizer of some pair $h,k:B\rightrightarrows Z$. It is monic because two equalizer factorizations of the same arrow must agree.

The converted TeX omits the remainder of this subpart. For the printed strict monomorphism condition, an arrow $g:C\to B$ is admissible when, for every pair $h,k$ out of $B$, the implication $hm=km\Rightarrow hg=kg$ holds; strictness says each such $g$ factors uniquely through $m$. If $m$ equalizes $h_0,k_0$, every admissible $g$ satisfies $h_{0}g=k_{0}g$, and the equalizer property supplies its unique factorization. Hence every regular monomorphism is strict.

Strictness itself implies monicity: whenever $mu=mv$, the common composite is admissible, so uniqueness of its factor through $m$ gives $u=v$. Now take a square $mu=ve$ with $e$ epic. Whenever $hm=km$, we have $hve=hmu=kmu=kve$, hence $hv=kv$. Thus $v$ is admissible and has a unique factor $d$ through $m$. Monicity gives $de=u$. We have proved the chain

A split coequalizer consists of $f,g:A\rightrightarrows B$, $q:B\to Q$, $s:Q\to B$ and $t:B\to A$ with $qf=qg$, $qs=1_Q$, $ft=1_B$ and $gt=sq$. If $hf=hg$, then $h=hft=hgt=hsq$. Thus $hs$ factors $h$ through $q$, and the factor is unique because $q$ has the right inverse $s$. This proves the coequalizer property directly. Every functor preserves the diagram, since all these equations are preserved.

For idempotent splitting through a coequalizer, first suppose $e=ir$ with $ri=1_Q$. Then $re=r$. Any $h:E\to Z$ satisfying $he=h$ factors as $h=(hi)r$, uniquely since $r$ is a split epimorphism. Hence $r$ coequalizes $(e,1_E)$.

Conversely, let $q:E\to Q$ coequalize $(e,1_E)$. Since $e^2=e$, the arrow $e:E\to E$ itself equalizes the pair, so there is a unique $i:Q\to E$ with $iq=e$. Then $qiq=qe=q$, and every coequalizer is an epimorphism, so $qi=1_Q$. Thus $e=iq$ is a splitting of an idempotent morphism.

For a diagram $D:\mathcal{J}\to \mathcal{C}$, a limit-preserving functor carries every limiting cone over a diagram to a limiting categorical cone. A limit-reflecting functor has the converse property: a categorical cone is limiting whenever its image is limiting. A limit-creating functor uniquely lifts every specified limiting categorical cone over the image diagram to a categorical cone over $D$, and the lift is limiting. These definitions concern diagrams of the stipulated shape; creation includes the lifting requirement, not merely reflection.

Let $(L,(p_j))$ be a categorical limit of $D$. The mapis a bijection: the right side consists exactly of compatible families of arrows from $A$, and the categorical limit's universal property gives their unique factorization through $L$. The bijection is induced by the categorical limit projections, so it proves that covariant representables preserve limits, including the empty diagram and its terminal object.

Construct pointwise limits in a functor category. For $H:\mathcal{J}\to [\mathcal{D},\mathcal{C}]$, choose at each object $d$ a categorical limit $L(d)$ of $j\mapsto H_j(d)$, with projections $p_j(d)$. For $u:d\to d^{\prime }$, the family $H_j(u)p_j(d)$ is compatible; define $L(u)$ uniquely byThe universal property gives $L(1_d)=1_{L(d)}$ and $L(vu)=L(v)L(u)$, since those equalities hold after every projection. Thus $L$ is a functor, and each $p_j:L\Rightarrow H_j$ is a natural transformation.

For any categorical cone $(M,(a_j))$, the pointwise categorical limits give unique maps $a(d):M(d)\to L(d)$. To check naturality, compose $L(u)a(d)$ and $a(d^{\prime })M(u)$ with every $p_j(d^{\prime })$; both become $H_j(u)a_j(d)=a_j(d^{\prime })M(u)$. The projections distinguish arrows into their categorical limit, so the two maps agree. Componentwise uniqueness gives uniqueness of the natural transformation $a$. This proves that $(L,p_j)$ really is the required categorical limit, rather than merely a family of objectwise candidates.

A specified categorical limit categorical cone in ${\mathcal{C}}^{\mathrm{ob}\mathcal{D}}$ fixes these objectwise vertices and projections. The displayed equation forces every arrow $L(u)$, and the argument forces every categorical cone factorization. Hence the forgetful functor uniquely lifts that categorical cone and is a limit-creating functor. The construction only takes small categorical limits in $\mathcal{C}$; it does not require $\mathcal{D}$ to be small. As usual, the functor categories are understood in a universe where their collections of transformations are meaningful.

An adjunction $F⊣G$ is a family of bijectionsnatural in both variables. Its adjunction unit and adjunction counit are ${\eta }_A={\Phi }_{A,FA}(1_{FA})$ and ${\epsilon }_B={\Phi }_{GB,B}^{-1}(1_{GB})$. Naturality of the correspondence givesFor $f:A\to A^{\prime }$, naturality in both variables evaluates $\Phi (Ff)$ in two ways, giving $GFf{\eta }_A={\eta }_{A^{\prime }}f$. Thus $\eta$ is a natural transformation; the dual calculation gives naturality of $\epsilon$.

Applying the inverse correspondence to ${\eta }_A$ and the correspondence to ${\epsilon }_B$ yields the triangle identities for an adjunction:They express that transposing an identity morphism and transposing back returns that identity.

Define the correspondence from the given natural transformations by $u\mapsto Gu{\eta }_A$, with candidate inverse $v\mapsto {\epsilon }_{B}Fv$. For $u:FA\to B$, naturality of $\epsilon$ and a triangle identity for an adjunction giveFor $v:A\to GB$, naturality of $\eta$ and the other triangle identity giveThese are inverse bijections. Naturality of $\eta$, $\epsilon$, $F$ and $G$ makes the bijections natural in $A$ and $B$, so they define an adjunction with the required unit and counit. Uniqueness follows from the formulas in the previous part: any adjunction with that unit and counit must have exactly these transposition maps.

The currying adjunction for small categories uses the bijectionIt sends $H$ to the functor $d\mapsto H(d,-)$, with an arrow $u:d\to d^{\prime }$ inducing the natural transformation whose $c$-component is $H(u,1_c)$. Conversely, for $K:\mathcal{D}\to [\mathcal{C},\mathcal{E}]$, define its uncurried functor by $(d,c)\mapsto K(d)(c)$ andNaturality of $K(u)$ allows the two factors to be interchanged in the appropriate order, giving functoriality. The constructions are inverse and natural in $\mathcal{D}$ and $\mathcal{E}$. Hence $-\times \mathcal{C}$ is a left adjoint to $[\mathcal{C},-]$ on the category of small categories.

The unit sends $d$ to the functor $c\mapsto (d,c)$ and $u$ to the transformation $(u,1_c)$. The counit is evaluation $[\mathcal{C},\mathcal{E}]\times \mathcal{C}\to \mathcal{E}$: $(H,c)\mapsto H(c)$ and $(\alpha ,v)\mapsto H^{\prime }(v){\alpha }_c={\alpha }_{c^{\prime }}H(v)$.

The comma category $(X\downarrow G)$ has objects $(A,x)$ with $A\in \mathcal{C}$ and a function $x:X\to GA$. A morphism $(A,x)\to (B,y)$ is an arrow $f:A\to B$ such that $Gfx=y$. Identities and composition come from $\mathcal{C}$. When $X=1$, a map $1\to GA$ selects an element of $GA$, so this is the covariant category of elements of $G$.

A representation of a functor $(A,x)$ for $G$ says precisely that for every object $(B,y)$ of $(1\downarrow G)$ there is a unique arrow $f:A\to B$ with $Gf(x)=y$. This is exactly the initial object property for $(A,x)$ in that comma category. Conversely, an initial object supplies these unique arrows, hence the representing bijections $\mathcal{C}(A,B)\cong GB$.

An initial object by itself is a weakly initial set. For the converse, let $(W_i{)}_{i\in I}$ be a small weakly initial family and form its product in a category $W$. Given $X$, choose an arrow $W_i\to X$; its composite with the projection $W\to W_i$ shows that $W$ is weakly initial.

Local smallness makes $\mathrm{End}(W)$ a set, so completeness supplies the simultaneous equalizer $e:E\to W$ of all endomorphisms of $W$ with $1_W$. Thus $he=e$ for every $h\in \mathrm{End}(W)$. The object $E$ is weakly initial because it maps to $W$.

For parallel arrows $a,b:E\to X$, take their equalizer $j:Y\to E$. Weak initiality of $W$ supplies $t:W\to Y$. The endomorphism $ejt$ of $W$ satisfies $(ejt)e=e$, and monicity of $e$ gives $jte=1_E$. Therefore $j$ is both a monomorphism and a split epimorphism, hence an isomorphism. Since $aj=bj$, we obtain $a=b$. There is already at least one arrow from $E$ to every $X$, so $E$ is initial. This proves the initial-object lemma for complete categories with a weakly initial set, with smallness used exactly where the endomorphisms are equalized.

If $G$ is representable, it is a limit-preserving functor, and its universal element gives an initial object of $(1\downarrow G)$, hence a weakly initial singleton.

Conversely, a limit-preserving $G$ makes $(1\downarrow G)$ a complete category. For a small diagram $(A_j,x_j)$, take $L={\lim }_j{A}_j$ in $\mathcal{C}$. Its distinguished elements form a compatible family in ${\lim }_{j}G{A}_j$. Categorical limit preservation gives a unique $x\in GL$ with $G{p}_j(x)=x_j$. The underlying categorical limit factorization of a categorical cone preserves this element, proving the comma-category universal property. For the empty diagram, this uses $G1\cong 1$. This is the construction of limits in a comma category of a limit-preserving functor.

The comma category is locally small since its arrows are subsets of the hom-sets in $\mathcal{C}$. By the previous part, its weakly initial set therefore yields an initial object. Part (b) then yields a representation of $G$. Thus representability from a solution set follows with all small categorical limits, rather than finite categorical limits alone.

For the monad $(T,\eta ,\mu )$, an algebra for a monad is $(A,a:TA\to A)$ with $a{\eta }_A=1_A$ and $aT(a)=a{\mu }_A$. A morphism of algebras for a monad $f:(A,a)\to (B,b)$ satisfies $fa=bTf$. These objects and arrows form the Eilenberg-Moore category ${\mathcal{C}}^T$.

The free algebra functor sends $A$ to $(TA,{\mu }_A)$ and $f$ to $Tf$. The monad identities verify the algebra laws. For the forgetful functor $U$, the free adjunction iswith inverse $v\mapsto bTv$. The algebra law makes the latter an monad algebra morphism. The identities $h{\eta }_A\mapsto bT(h{\eta }_A)=h{\mu }_{A}T{\eta }_A=h$ and $bTv{\eta }_A=b{\eta }_{B}v=v$ prove the bijection.

In the category of adjunctions inducing a fixed monad, objects are adjunctions $F⊣G$ with their induced monad identified with $T$. A morphism to $F^{\prime }⊣G^{\prime }$ is a functor $H$ between the right-hand categories satisfying $G^{\prime }H=G$, $HF=F^{\prime }$ and compatibility with units and counits. With these strict identifications, defineThe triangle identities give the unit algebra law; naturality of $\epsilon$ at ${\epsilon }_B$ gives the multiplication law. Naturality at $f$ makes $Gf$ an monad algebra morphism. Moreover $UK=G$, $KF=F^T$ because $G{\epsilon }_{FA}={\mu }_A$, and $K{\epsilon }_B$ is the free-adjunction counit at $K(B)$. Hence $K$ is a morphism into the Eilenberg-Moore adjunction.

For any other such $H$, its underlying object at $B$ must be $GB$. Counit compatibility forces its algebra action to be $G{\epsilon }_B$, and the forgetful functor, which is a faithful functor, forces $H(f)=Gf$. Thus $H=K$. This proves terminality of the Eilenberg-Moore adjunction. If adjunctions are specified only up to coherent isomorphisms, the same argument gives uniqueness up to the corresponding compatible natural isomorphism.

We prove full faithfulness from counit coequalizers. Let $B,C\in \mathcal{D}$ and let $\alpha :K(B)\to K(C)$ be an monad algebra morphism. ThusSet $u={\epsilon }_{C}F\alpha :FGB\to C$. Its composites with the two arrows of the printed presentation are equal: naturality of $\epsilon$ givesIn the last equality we used naturality at $F\alpha$. The coequalizer property therefore gives a unique $v:B\to C$ satisfying $v{\epsilon }_B=u$.

Apply $G$ to that identity. The algebra-morphism equation gives $GvG{\epsilon }_B=\alpha G{\epsilon }_B$. The triangle identity makes $G{\epsilon }_B$ a split epimorphism with section ${\eta }_{GB}$, so $Gv=\alpha$. This proves fullness of $K$.

If $v,w:B\to C$ have $Gv=Gw$, naturality gives $v{\epsilon }_B={\epsilon }_{C}FGv={\epsilon }_{C}FGw=w{\epsilon }_B$. The counit is epic since it is a coequalizer, so $v=w$. Thus $K$ is a faithful functor. Both parallel arrows matter: the converted TeX loses the second one, ${\epsilon }_{FGB}$, which is visible in the original PDF.

The crude monadicity theorem in its reflexive-coequalizer form says: if $F⊣G:\mathcal{D}\to \mathcal{C}$, $G$ is a conservative functor, $\mathcal{D}$ has reflexive coequalizers, and $G$ preserves them, then the Eilenberg-Moore comparison functor $K:\mathcal{D}\to {\mathcal{C}}^T$, for $T=GF$, is an equivalence of categories. Requiring all coequalizers to exist and be preserved is a stronger sufficient form.

For an algebra $(A,a)$, form in $\mathcal{D}$ the coequalizerThe pair is a reflexive pair with common section $F{\eta }_A$: both composites are the identity by the algebra unit law and the triangle identity. An arrow $u:FA\to B$ transposes to $v=Gu{\eta }_A:A\to GB$. The two composites $uFa$ and $u{\epsilon }_{FA}$ transpose to $va$ and $G{\epsilon }_{B}Tv$, respectively. Indeed the latter transpose is $Gu{\mu }_A{\eta }_{TA}=Gu$, while $G{\epsilon }_{B}Tv=Gu{\mu }_{A}T{\eta }_A=Gu$ by counit naturality. Thus $u$ equalizes the pair exactly when $v$ is an monad algebra morphism $(A,a)\to K(B)$. The coequalizer property gives natural bijectionsThese define $L$ on arrows by uniqueness, so $L⊣K$. Its unit has underlying arrow $\beta =Gq{\eta }_A:A\to GL(A,a)$.

By preservation, $Gq$ coequalizes $Ta$ and ${\mu }_A$ in $\mathcal{C}$. The action $a:TA\to A$ is a split coequalizer of that pair: take $s={\eta }_A$ and $t={\eta }_{TA}$, with ${\mu }_{A}t=1_{TA}$ and $Tat={\eta }_{A}a$. Thus there is a unique isomorphism $\alpha :GL(A,a)\to A$ with $\alpha Gq=a$. We have $\alpha \beta =a{\eta }_A=1_A$. AlsoConsequently $\beta \alpha Gq=Gq$, and epimorphic cancellation gives $\beta \alpha =1$. The adjunction unit $\beta$ is an monad algebra morphism; its invertible underlying arrow has an algebra-morphism inverse. Thus the unit of $L⊣K$ is an isomorphism.

For its counit $c_B:LK(B)\to B$, the triangle identity gives $K(c_B){\beta }_{K(B)}=1_{K(B)}$. Hence $K(c_B)$, and therefore $G(c_B)$, is an isomorphism. Since $G$ is a conservative functor, $c_B$ is an isomorphism too. Both unit and counit of $L⊣K$ are invertible, which proves the claimed equivalence. This proof uses only reflexive coequalizers in $\mathcal{D}$ and split coequalizers in $\mathcal{C}$.

Use the kernel squares in an abelian category argument. If $b$ is monic and $r:X\to A$, $s:X\to K^{\prime }$ satisfy $ar=f^{\prime }s$, then $bgr=g^{\prime }ar=g^{\prime }{f}^{\prime }s=0$, so $gr=0$. The kernel in a category property gives a unique $t:X\to K$ with $ft=r$. The equation $f^{\prime }kt=aft=ar=f^{\prime }s$ and monicity of $f^{\prime }$ give $kt=s$. This proves the left square is a pullback in a category.

Now suppose the right square is a pullback, without imposing the earlier monicity hypothesis on $b$. The pair $(f^{\prime },0):K^{\prime }\to A^{\prime }{\times }_{B^{\prime }}B$ gives a unique $r:K^{\prime }\to A$ with $ar=f^{\prime }$ and $gr=0$. Factor $r=f\ell$ through the kernel. Then $f^{\prime }k\ell =af\ell =ar=f^{\prime }$, so $k\ell =1_{K^{\prime }}$. Also $rk$ and $f$ have the same two pullback projections, hence $rk=f$. Thus $f\ell k=f$ and $\ell k=1_K$. Therefore $k$ is an isomorphism. These arguments use only the relevant kernels, zero arrows and pullback properties; the abelian hypothesis supplies them.

In an abelian category, the image factorization in an abelian category of $f:A\to B$ iswhere the abelian-category axiom identifies coimage with image. Thus $p$ is epic and $i$ is monic. Any other epi-mono factorization $f=jq$ has $\ker q=\ker f$ and $\mathrm{coker}j=\mathrm{coker}f$. Since epimorphisms are cokernels of their kernels, its middle object is canonically isomorphic to $\mathrm{im}f$, uniquely compatibly with the two factors.

For a square $vf=f^{\prime }u$, define $I(u,v):\mathrm{im}f\to \mathrm{im}{f}^{\prime }$ byThe first arrow exists because $u\ker f$ factors through $\ker f^{\prime }$, so $p^{\prime }u$ annihilates $\ker f$. Its composite with $i^{\prime }$ equals $vi$ after the epimorphism $p$, proving the second equation. Uniqueness after $p$ proves preservation of identities and composition. This gives the functoriality of abelian image factorization as a functor from the arrow category.

For pullback stability of abelian image factorization, state the standard facts that pullbacks preserve monomorphisms, epimorphisms in an abelian category are stable under pullback, and two adjoining pullback squares have pullback outer rectangle. In the given diagram, $i^{\prime }$ is therefore monic and $p^{\prime }$ is epic, while the composite $i^{\prime }{p}^{\prime }$ is the pullback of $f$. Its epi-mono factorization is an image factorization by the uniqueness just proved. Thus the top row is the image factorization of the pulled-back arrow, with its middle object canonically the pullback of the original image subobject.