Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 20 (Category Theory)

For a categorical presheaf $X:{\mathcal{C}}^{\mathrm{op}}\to \mathbf{Set}$ and $A\in \mathcal{C}$, the Yoneda lemma gives a natural bijectionTo construct its inverse, take $x\in X(A)$ and set ${\theta }_U^x(h)=X(h)x$ for $h:U\to A$. For $k:V\to U$, the functor law gives $X(k){\theta }_U^x(h)=X(hk)x={\theta }_V^x(hk)$, so ${\theta }^x$ is a natural transformation. Conversely, naturality of any $\theta$ at $h:U\to A$ gives ${\theta }_U(h)=X(h){\theta }_A(1_A)$. Thus the two constructions are inverse, proving the bijection.

The bijection is natural in $X$: a natural transformation $t:X\to Y$ sends the distinguished element $x$ to $t_A(x)$ on either side. It is natural in $A$: for $f:A\to B$, precomposing a transformation $\mathcal{C}(-,B)\to X$ with postcomposition by $f$ sends its distinguished element $x\in X(B)$ to $X(f)x$. These equations prove the claimed naturality, rather than just an objectwise correspondence. Reversing morphisms gives the covariant form $\mathrm{Nat}(\mathcal{C}(A,-),Z)\cong Z(A)$ for $Z:\mathcal{C}\to \mathbf{Set}$.

Define the Yoneda embedding $H_{\bullet }:\mathcal{C}\to [{\mathcal{C}}^{\mathrm{op}},\mathbf{Set}]$ by $H_A(U)=\mathcal{C}(U,A)$ and $H_A(k)(h)=hk$. For $f:A\to B$, define $H_{\bullet }(f{)}_U(h)=fh$. Associativity proves naturality in $U$, and preservation of identity morphisms and composition in a category proves that $H_{\bullet }$ is a functor.

Apply the Yoneda lemma to $X=H_B$. It givesThe natural transformation corresponding to $f$ has component $h\mapsto fh$, exactly $H_{\bullet }(f)$. Therefore the induced map on every hom-set is a bijection: the Yoneda embedding is full and faithful.

If $f:A\to B$ is a monomorphism, each function $\mathcal{C}(U,A)\to \mathcal{C}(U,B)$ given by postcomposition with $f$ is injective. Consequently, if two natural transformations into $H_A$ become equal after $H_{\bullet }(f)$, their components are equal, and the transformations themselves are equal. This proves that $H_{\bullet }(f)$ is a monomorphism in the presheaf category.

Conversely, suppose $H_{\bullet }(f)$ is a monomorphism and $u,v:U\to A$ satisfy $fu=fv$. Then $H_{\bullet }(f)H_{\bullet }(u)=H_{\bullet }(f)H_{\bullet }(v)$. Cancellation gives $H_{\bullet }(u)=H_{\bullet }(v)$, and faithfulness of the Yoneda embedding gives $u=v$. Hence $H_{\bullet }(f)$ is monic exactly when $f$ is monic.

We first justify the relevant pointwise epimorphism in a functor category criterion. A componentwise surjective function gives an epimorphism, because equality of two composites can be cancelled at each component. Conversely, for a natural transformation $t:X\to Y$, form the pointwise pushout $P=Y{⨿}_{X}Y$. Restrictions of $Y$ preserve the identifications imposed by $t$, so these pointwise sets and restrictions form a categorical presheaf. The two inclusions $j_1,j_2:Y\to P$ satisfy $j_{1}t=j_{2}t$. If $t$ is epic, $j_1=j_2$. At an object $U$, an element outside the image of $t_U$ would retain two distinct copies in $P(U)$, contradicting this equality. Thus every $t_U$ is surjective.

Apply this criterion to $H_{\bullet }(f)$ at $B$. Surjectivity of $\mathcal{C}(B,A)\to \mathcal{C}(B,B)$ supplies $g:B\to A$ with $fg=1_B$. Conversely, if $fg=1_B$, then $H_{\bullet }(f)H_{\bullet }(g)=1_{H_B}$, making $H_{\bullet }(f)$ a split epimorphism and hence an epimorphism. Therefore

Name the upper objects $A,B,C$ and the lower objects $D,E,F$, so the morphisms are $b:A\to B$, $c:B\to C$, $a:A\to D$, $g:B\to E$, $d:C\to F$, $f:D\to E$, and $e:E\to F$. The commutative diagram gives $gb=fa$ and $dc=eg$.

Take $u:T\to D$ and $v:T\to C$ with $efu=dv$. The right pullback in a category gives a unique $w:T\to B$ with $gw=fu$ and $cw=v$. The left pullback in a category then gives a unique $z:T\to A$ with $az=u$ and $bz=w$. It follows that $cbz=v$, giving the required factorization through the outside rectangle. Any other factorization has the same middle morphism by uniqueness in the right pullback in a category, and therefore is the same $z$ by uniqueness in the left pullback in a category. The outside rectangle is a pullback.

Keep the notation of the preceding part. For $u:T\to D$ and $w:T\to B$ satisfying $fu=gw$, we have $efu=egw=dcw$. The outside pullback in a category gives a unique $z:T\to A$ with $az=u$ and $cbz=cw$. Moreover $gbz=faz=fu=gw$. The morphisms $bz,w:T\to B$ thus have the same composites with $g$ and $c$. Uniqueness in the right pullback in a category gives $bz=w$. Any factorization through the left square also factors through the outside rectangle, so it is unique there. The left square is a pullback. Together these two arguments prove the pullback pasting lemma.

Here is a precise base change of a pullback square statement. Suppose $A=B{\times }_{D}C$ is a pullback in a category and $t:D^{\prime }\to D$ is a morphism. Assume the pullbacks in a categoryexist, where $A\to D$ is the common composite. The induced square with vertices $A^{\prime },B^{\prime },C^{\prime },D^{\prime }$ is a pullback in a category; equivalently,Indeed, compatible morphisms $T\to B^{\prime }$ and $T\to C^{\prime }$ give morphisms $b:T\to B$, $c:T\to C$, and a common $v:T\to D^{\prime }$, with the composites of $b,c$ to $D$ both equal to $tv$. The original pullback in a category gives a unique morphism $h:T\to A$ with projections $b,c$. Its composite to $D$ is $tv$, so the defining pullback in a category for $A^{\prime }$ gives a unique morphism $T\to A^{\prime }$ above $h,v$. Its maps to $B^{\prime }$ and $C^{\prime }$ are the prescribed ones by uniqueness in those pullbacks in a category. Conversely, these projections recover $b,c,v$, so every possible factorization is the same. This proves the universal property without requiring arbitrary categorical limits in the ambient category.

For a functor $D:\mathcal{J}\to \mathcal{C}$ with finite indexing category, form the finite products in a categoryDefine $s,t:P\rightrightarrows Q$ by requiring the coordinate indexed by $u:i\to j$ to be $D(u){\pi }_i$ for $s$ and ${\pi }_j$ for $t$. Let $e:L\to P$ be their equalizer, and put ${\lambda }_j={\pi }_{j}e$. The equality $se=te$ says exactly that $D(u){\lambda }_i={\lambda }_j$ for every morphism $u$, so these morphisms form a categorical cone.

For any other categorical cone $(x_j:X\to D(j))$, the product in a category gives a unique $x:X\to P$ with ${\pi }_{j}x=x_j$. The categorical cone equations give $sx=tx$, so the equalizer gives a unique $\bar{x}:X\to L$ with $e\bar{x}=x$. This is exactly the universal property of a categorical limit. Empty indexing products are terminal objects, so the construction includes the empty diagram in a category. Thus finite products and equalizers give all finite limits.

Let $1$ be a terminal object. The pullback in a category of $X\to 1\leftarrow Y$ has precisely the universal property of the binary product in a category $X\times Y$: every pair of morphisms to $X,Y$ is compatible over $1$. Repeated binary products in a category, together with $1$ as the empty product, give all finite products in a category.

For $f,g:X\rightrightarrows Y$, form the pullback in a category of the categorical diagonal ${\Delta }_Y:Y\to Y\times Y$ along $⟨f,g⟩:X\to Y\times Y$. Its projection $e:E\to X$ satisfies $fe=ge$. If $h:T\to X$ satisfies $fh=gh$, the pair $h,fh$ gives a unique morphism into this pullback in a category. Conversely any such morphism must project to that pair. Hence $e$ is the equalizer of $f,g$. The preceding construction now gives all finite limits.

For $D:\mathcal{I}\to \mathcal{C}$, define the functor $\mathrm{Cone}(-,D):{\mathcal{C}}^{\mathrm{op}}\to \mathbf{Set}$ bywhere $\Delta X$ is the constant diagram functor; a morphism into $X$ acts by precomposition on every categorical cone leg. A categorical limit is a representation of a functor of the formThe image of $1_L$ is the universal categorical cone $\lambda :\Delta L\to D$. By naturality of the representing isomorphism, the image of $h:X\to L$ is $\lambda \circ \Delta h$. Thus this definition is exactly existence and uniqueness of factorization of every categorical cone through $\lambda$. Conversely that universal property gives the representing natural bijection.

Choose for each $j\in \mathcal{J}$ a categorical limit $L_j$ of $F(-,j)$, with projections ${\lambda }_{i,j}:L_j\to F(i,j)$. For $v:j\to k$, the morphisms $F(1_i,v){\lambda }_{i,j}$ form a categorical cone over $F(-,k)$, since the two actions of the product functor $F$ commute. Define $L(v):L_j\to L_k$ by the equationsExistence and uniqueness follow from the universal property. The identity morphism of $L_j$ satisfies the equations for $v=1_j$, and $L(w)L(v)$ satisfies those for $wv$, so uniqueness gives $L(1_j)=1_{L_j}$ and $L(wv)=L(w)L(v)$. Hence $L:\mathcal{J}\to \mathcal{D}$ is a functor.

If $L_j^{\prime }$ with projections ${\lambda }_{i,j}^{\prime }$ are other choices, there is a unique isomorphism $u_j:L_j\to L_j^{\prime }$ carrying every projection to the corresponding projection. The same equations show $u_{k}L(v)=L^{\prime }(v)u_j$, because their composites with all ${\lambda }_{i,k}^{\prime }$ agree. Thus the choices give a unique natural isomorphism compatible with the chosen categorical limit categorical cones. Without the compatibility condition, uniqueness of an arbitrary natural isomorphism is not asserted.

Let $M$ be a categorical limit of $L:\mathcal{J}\to \mathcal{D}$, with projections $p_j:M\to L_j$. Set ${\gamma }_{i,j}={\lambda }_{i,j}{p}_j$. The equations for the categorical cones $\lambda$ and $p$, and the defining equations for $L(v)$, show that this family is a categorical cone over $F:\mathcal{I}\times \mathcal{J}\to \mathcal{D}$.

For any categorical cone $x_{i,j}:X\to F(i,j)$, fix $j$. Its $\mathcal{I}$-legs give a unique $h_j:X\to L_j$. For $v:j\to k$, both $L(v)h_j$ and $h_k$ have composite $x_{i,k}$ with every ${\lambda }_{i,k}$, so they are equal. Thus the $h_j$ form a categorical cone over $L$, which factors uniquely through $h:X\to M$. The equalities ${\gamma }_{i,j}h=x_{i,j}$ follow. Any other such $h$ has the same composites with every $p_j$, because the projections ${\lambda }_{i,j}$ detect equality; uniqueness for $M$ then makes it equal to $h$. Therefore $M$ is a categorical limit of the whole product diagram in a category.

A precise commutation of iterated categorical limits statement is the following. For small categories $\mathcal{I},\mathcal{J}$ and $F:\mathcal{I}\times \mathcal{J}\to \mathcal{D}$, if every column categorical limit and the resulting $\mathcal{J}$-limit exist, thenIf every row categorical limit and the resulting $\mathcal{I}$-limit also exist, thenEach isomorphism is the unique one identifying all projections to $F(i,j)$. Indeed, the preceding part proves that each iterated categorical limit has the universal property of the whole product diagram in a category. Its uniqueness gives the canonical isomorphism. Equivalently, categorical cones with vertex $X$ over the product diagram in a category are exactly compatible families, indexed by $j$, of categorical cones over $F(-,j)$; regrouping the same compatibility equations cannot change their representing object. In a complete category all the stated existence hypotheses hold for small $\mathcal{I},\mathcal{J}$. The theorem is about categorical limits with categorical limits, and makes no unconditional claim about commuting a categorical limit with a colimit.

Let $T:{\mathcal{C}}^{\mathrm{op}}\times \mathcal{C}\to \mathcal{D}$. A categorical end is an object $E$ with morphisms $e_A:E\to T(A,A)$ satisfying, for every $f:A\to B$,It is universal among such families: any $x_A:X\to T(A,A)$ satisfying the same equations is uniquely $e_{A}h$ for one $h:X\to E$. This is a universal dinatural transformation from the constant value $E$, and is written $E={\int }_{A}T(A,A)$.

Dually a categorical coend is $Q$ with morphisms $j_A:T(A,A)\to Q$ satisfyingAny family $x_A:T(A,A)\to X$ satisfying these equations is uniquely $h{j}_A$ for one $h:Q\to X$. Write $Q={\int }^{A}T(A,A)$. For small $\mathcal{C}$, the categorical end can be constructed as the equalizer of ${\prod }_{A}T(A,A)\rightrightarrows {\prod }_{f:A\to B}T(A,B)$ when these objects exist. The categorical coend is the coequalizer of ${\coprod }_{f:A\to B}T(B,A)\rightrightarrows {\coprod }_{A}T(A,A)$ when those objects exist. The two morphisms impose exactly the displayed equations for a dinatural transformation.

Working with a small category $\mathcal{C}$ (or in a fixed ambient universe), for a categorical presheaf $X$ and fixed $U$, apply the categorical coend construction to $T(A,B)=\mathcal{C}(U,B)\times X(A)$. It is the quotient of the disjoint union of pairs $(h:U\to W,x\in X(W))$ by the relationsDefine ${\Phi }_U([h,x])=X(h)x$. It respects every relation because $X(fh)x=X(h)X(f)x$. Define ${\Psi }_U(y)=[1_U,y]$. Then ${\Phi }_U{\Psi }_U(y)=y$. Conversely the relation with $f=h:U\to W$ gives $[h,x]=[1_U,X(h)x]$, so ${\Psi }_U{\Phi }_U$ is the identity morphism. ThereforeFor $k:V\to U$, restriction on the categorical coend sends $[h,x]$ to $[hk,x]$, and ${\Phi }_V([hk,x])=X(k){\Phi }_U([h,x])$. A natural transformation $X\to Y$ likewise acts on the second coordinate and commutes with $\Phi$. Thus the density formula for presheaves is a natural isomorphism, not just a family of unrelated bijections.

The category of elements $\int X$ has objects $(W,x)$ for $x\in X(W)$, and morphisms $f:(W,x)\to (V,y)$ with $X(f)y=x$. Send $(W,x)$ to the representable presheaf $H_W$, and a morphism $f$ to $H_{\bullet }(f)$. The element $x$ supplies a natural transformation $H_W\to X$ with component $h\mapsto X(h)x$, by the Yoneda lemma. These transformations form a cocone.

Pointwise at $U$, the colimit of this diagram in a category has representatives $(W,x,h:U\to W)$, with relation $(W,X(f)y,h)\sim (V,y,fh)$. These are exactly the relations of the preceding categorical coend. Its proved natural isomorphism with $X(U)$ therefore identifies the cocone with the universal colimit cocone. More directly, every representative equals $(U,X(h)x,1_U)$ through the morphism $h:(U,X(h)x)\to (W,x)$; two representatives with the same image therefore agree. As $\mathcal{C}$ is small, $\int X$ is small, so this is an ordinary small colimit. Consequently

Write the adjunction as a natural bijection ${\alpha }_{C,D}:\mathcal{D}(FC,D)\to \mathcal{C}(C,GD)$. The adjunction unit and adjunction counit are defined byNaturality of $\alpha$ implies $GF(u){\eta }_C={\eta }_{C^{\prime }}u$ for $u:C\to C^{\prime }$ and $v{\epsilon }_D={\epsilon }_{D^{\prime }}FG(v)$ for $v:D\to D^{\prime }$, so these are natural transformations $1_{\mathcal{C}}\to GF$ and $FG\to 1_{\mathcal{D}}$. More explicitly, naturality at $f:FC\to D$ and $g:C\to GD$ gives the two transpose formulasThese formulas will also prove the triangle identities for an adjunction.

Using the transpose formulas of the preceding part,Similarly,Thus the adjunction unit and adjunction counit satisfy both triangle identities for an adjunction,

Given the two natural transformations, defineNaturality of $\eta$ and the second triangle identity for an adjunction giveNaturality of $\epsilon$ and the first triangle identity for an adjunction giveThe maps are natural in $C,D$, since the defining compositions commute with precomposition in $C$ and postcomposition in $D$ by naturality of $\eta ,\epsilon$. They therefore define an adjunction $F⊣G$. Their values on identity morphisms recover precisely $\eta ,\epsilon$. Conversely any adjunction with these unit and counit of an adjunction must have the same transpose formulas, so it is unique with the prescribed unit and counit.

A poset $P$ becomes a category with the elements of $P$ as objects and exactly one morphism $x\to y$ when $x\le y$, with no morphism otherwise. Reflexivity supplies the identity morphisms and transitivity supplies composition in a category; uniqueness of morphisms proves associativity. A functor $f:P\to Q$ is exactly a monotone function: it must send $x\le y$ to $f(x)\le f(y)$, and this condition suffices because all the required morphisms are unique. Antisymmetry says that isomorphic objects of this category are equal.

Each hom-set in a poset is either empty or a singleton. Thus a natural bijection $Y(fx,y)\cong X(x,gy)$ is precisely the conditionThe naturality squares commute automatically, because maps between the relevant singleton hom-sets are unique. This is a Galois connection. Equivalently, the adjunction unit and adjunction counit are the inequalities $x\le gf(x)$ and $fg(y)\le y$. These inequalities imply the displayed equivalence: $f(x)\le y$ gives $x\le gf(x)\le g(y)$, and $x\le g(y)$ gives $f(x)\le fg(y)\le y$.

The two adjoints of inverse image on power sets areThese maps and $p^{\ast }(V)=p^{-1}(V)$ are monotone functions on the inclusion-ordered power sets. For $U\subseteq A$ and $V\subseteq B$,The first equivalence follows by following each element of $U$ through $p$. For the second, every fiber over $b\in V$ must lie in $U$, which is precisely the defining condition for $b\in {\forall }_p(U)$. These are the two Galois connections, proving ${\exists }_p⊣p^{\ast }⊣{\forall }_p$. In particular, a point outside $p(A)$ has an empty fiber and belongs to ${\forall }_p(U)$ even when $U$ is empty; omitting this case would give an incorrect right adjoint.

For a presheaf of sets on a topological space $P$, define $LP=P(\varnothing )$ and $RP=P(S)$. Then the adjoints to constant presheaves on open sets areTo prove the first adjunction, a natural transformation $a:P\to \Delta A$ must satisfy $a_U=a_{\varnothing }\circ {\mathrm{res}}_{U,\varnothing }$ by naturality at the inclusion $\varnothing \subseteq U$. Hence it is uniquely determined by a function $P(\varnothing )\to A$. Every such function defines a natural transformation by this formula, because restriction maps compose. This gives $\mathrm{Nat}(P,\Delta A)\cong \mathbf{Set}(P(\varnothing ),A)$.

For the second adjunction, a natural transformation $b:\Delta A\to P$ satisfies $b_U={\mathrm{res}}_{S,U}\circ b_S$, so it is uniquely determined by a function $A\to P(S)$. Every such function defines the remaining components by restriction, giving $\mathrm{Nat}(\Delta A,P)\cong \mathbf{Set}(A,P(S))$. Evaluation acts on presheaf morphisms componentwise, so these object assignments are indeed functors. The use of $P(\varnothing )$ is essential: a constant presheaf of sets has value $A$ there, whereas a sheaf has a singleton value there. No sheaf condition is imposed in this question.

For $c\in \mathcal{C}$ and $d\in \mathcal{D}$, define maps of hom-setsThey are natural in $c,d$, using naturality of $\eta ,\epsilon$. The one supplied triangle identity for an adjunction givesNaturality of $\epsilon$ also givesSince $\alpha \beta =1$, the composite $\beta \alpha$ is idempotent. Evaluating its equation $(\beta \alpha {)}^2=\beta \alpha$ on $f=1_{Fc}$ gives $e_c^2=e_c$. As $e$ is a composite of natural transformations, this proves that $e$ is an idempotent in the functor category, including the required naturality.

Suppose this one-triangle adjunction idempotent splits as natural transformations $F\stackrel{r}{\to }H\stackrel{i}{\to }F$ with $ri=1_H$ and $ir=e$. The maps $h\mapsto hr$ and $f\mapsto fi$ give inverse bijections between $\mathcal{D}(Hc,d)$ and the subset of $\mathcal{D}(Fc,d)$ consisting of maps with $f{e}_c=f$. Indeed $(hr)e_c=hrir=hr$, $(hr)i=h$, and $(fi)r=f{e}_c=f$. The maps $\alpha ,\beta$ give inverse bijections between that subset and $\mathcal{C}(c,Gd)$, since $\beta \alpha (f)=f{e}_c$ and $\alpha \beta =1$. Combining them gives the natural bijectionwith inverse $g\mapsto {\epsilon }_{d}F(g)i_c$. Hence $H⊣G$. Its adjunction unit is $Gr\eta$ and its adjunction counit is $\epsilon i_G$.

Conversely, suppose $H⊣G$, with natural bijection $\theta :\mathcal{D}(Hc,d)\cong \mathcal{C}(c,Gd)$. Set $\tau ={\theta }^{-1}\alpha$ and $\sigma =\beta \theta$. Then $\tau \sigma =1$ and $\sigma \tau (f)=f{e}_c$. By the covariant Yoneda lemma, the transformation $\tau :\mathcal{D}(Fc,-)\to \mathcal{D}(Hc,-)$ is precomposition with a unique morphism $i_c:Hc\to Fc$, and $\sigma$ is precomposition with a unique morphism $r_c:Fc\to Hc$. The equation $\tau \sigma =1$ evaluated at $1_{Hc}$ gives $r_c{i}_c=1_{Hc}$; the equation $\sigma \tau (f)=f{e}_c$ evaluated at $1_{Fc}$ gives $i_c{r}_c=e_c$. Naturality in $c$ of $\tau ,\sigma$ implies, again by the same Yoneda lemma, that $i,r$ are natural transformations. Thus they split $e$ in the whole functor category, rather than merely at individual objects. We have proved

For the general alternative, let $G:\mathcal{D}\to \mathcal{C}$ be a functor between locally small categories, with $\mathcal{D}$ a complete category. The Freyd general adjoint functor theorem says that $G$ has a left adjoint if and only if it preserves small categorical limits and satisfies the solution-set condition. Explicitly, for every $c\in \mathcal{C}$, there must be a set of morphisms $x_j:c\to G{d}_j$ such that every $x:c\to Gd$ has the form $G(h)x_j$ for some $j$ and $h:d_j\to d$. Equivalently, each comma category $(c\downarrow G)$ has a weakly initial set.

We prove the initial-object lemma for complete categories with a weakly initial set. Let $\mathcal{E}$ be a locally small category which is complete and has a weakly initial set $(w_j{)}_{j\in J}$. Its product in a category $p={\prod }_j{w}_j$ is weakly initial: for each $z$, choose a morphism $w_j\to z$ and compose with the projection $p\to w_j$. The hom-set $\mathcal{E}(p,p)$ is a set. Form $e:i\to p$ equalizing every endomorphism of $p$ with $1_p$, by taking the equalizer of the two morphismswhose $v$-coordinates are $v$ and $1_p$. Then $ve=e$ for every endomorphism $v$, and $e$ is monic. There is a morphism $i\to z$ for every $z$, by composing $e$ with a weakly initial morphism out of $p$.

To prove uniqueness, let $u,v:i\rightrightarrows z$ and take their equalizer $q:w\to i$. Weak initiality of $p$ gives $a:p\to w$. The composite $eqa:p\to p$ is an endomorphism, so $eqae=e$. Cancel the monomorphism $e$ to obtain $qae=1_i$. Thus $q$ is both monic and split epic, hence an isomorphism: if $qk=1$, cancellation from $qkq=q$ gives $kq=1$. Since $uq=vq$, it follows that $u=v$. Therefore $i$ is an initial object, proving the lemma fully.

Now assume categorical limit preservation and the solution-set condition. The comma category $(c\downarrow G)$ is locally small. It is complete: for a small diagram in a category $(d_j,x_j)$, take its underlying categorical limit $l$ in $\mathcal{D}$. Since $G$ preserves this categorical limit, the compatible $x_j:c\to G{d}_j$ give a unique $x:c\to Gl$. The same universal property shows that $(l,x)$ is the categorical limit in the comma category. Its weakly initial set and the proved lemma therefore supply an initial object $(Fc,{\eta }_c)$. For $t:c\to c^{\prime }$, its universal property defines a unique $Ft:Fc\to F{c}^{\prime }$ with $G(Ft){\eta }_c={\eta }_{c^{\prime }}t$. Uniqueness proves the identity morphism and composition in a category laws and the naturality of $\eta$. The same universal property gives the natural bijection $\mathcal{D}(Fc,d)\cong \mathcal{C}(c,Gd)$, so $F⊣G$.

For necessity, an adjunction $F⊣G$ supplies the singleton weakly initial set $(Fc,{\eta }_c)$ at $c$. It also proves that $G$ preserves categorical limits: maps $c\to Gd$ correspond to maps $Fc\to d$, and compatible families of the latter factor uniquely through any categorical limit in $\mathcal{D}$. Hence the image categorical cone under $G$ has the required universal property. This proves both directions of the general alternative.

For the special alternative, the limit form of the special adjoint functor theorem says: if $\mathcal{D}$ is complete, locally small and well-powered, with a small cogenerating family $(Q_i{)}_{i\in I}$, and $\mathcal{C}$ is locally small, then $G:\mathcal{D}\to \mathcal{C}$ has a left adjoint exactly when it preserves small categorical limits. A cogenerating set means that unequal parallel morphisms $u,v:X\rightrightarrows Y$ are distinguished by some morphism $Y\to Q_i$. We prove the needed solution-set condition, so that the general theorem applies.

Fix $x:c\to Gd$. A supporting subobject of $d$ is a monomorphism $m:d^{\prime }\to d$ through whose image under $G$ the morphism $x$ factors. There is at least one, namely $1_d$. Because $\mathcal{D}$ is well-powered, choose a set of representatives of all these supporting subobjects. A limit-preserving functor preserves monomorphisms: a map is monic exactly when its diagonal into its self-pullback in a category is an isomorphism, and both the pullback in a category and this isomorphism are preserved. Consequently each factorization of $x$ through $Gm$ is unique. Form the intersection of subobjects of the supporting representatives, as a wide pullback in a category over $d$. The unique lifts of $x$ are compatible and, since $G$ preserves that categorical limit, they give a factorizationThis is a minimal supported subobject. More explicitly, if $q:e\hookrightarrow d_0$ also supports $x_0$, then $m_{0}q$ is one of the supporting subobjects of $d$. The intersection therefore factors through $m_{0}q$, giving $r:d_0\to e$ with $m_{0}qr=m_0$. Monicity of $m_0$ gives $qr=1_{d_0}$; monicity of $q$ then makes $q$ invertible.

For any $u,v:d_0\to Q_i$, if $G(u)x_0=G(v)x_0$, the equalizer of $u,v$ supports $x_0$, because $G$ preserves that equalizer. Minimality makes it invertible, so $u=v$. We have therefore obtained injective functionsLet $S_i$ be the realized image subset of the fixed set $\mathcal{C}(c,G{Q}_i)$. Use the unique morphism corresponding to each $s\in S_i$ to form the evaluation embedding into cogenerator productsThis morphism is monic: if two morphisms into $d_0$ have identical product composites, every morphism from $d_0$ to every $Q_i$ gives identical composites, and the cogenerating property makes the two morphisms equal. There is only a set of possible families of subsets $(S_i)$, and hence a set of possible products $P_S$. Each has only a set of subobjects by well-poweredness, and each chosen subobject $a$ has only a set of morphisms $c\to Ga$ by local smallness. Take all these pairs $(a,z:c\to Ga)$ as a weakly initial set. Every original $(d,x)$ receives a morphism from a pair representing its $(d_0,x_0)$, through $m_0$. Thus the set is weakly initial in $(c\downarrow G)$.

The general theorem now supplies a left adjoint. Necessity again follows from preservation of categorical limits by a right adjoint. This proves the special alternative, including its size argument. Using only the realized subsets $S_i$ avoids assuming that an arbitrary object admits a morphism into every cogenerator. Both adjoint functor theorem alternatives are proved.

A monad on $\mathcal{C}$ consists of an endofunctor $T$ and natural transformations $\eta :1\to T$, $\mu :T^2\to T$ satisfying, at every object $A$,These are the associativity and unit laws. An algebra for a monad is $(A,a:TA\to A)$ withA monad algebra morphism $h:(A,a)\to (B,b)$ is a morphism $h:A\to B$ satisfying $ha=bTh$. Identity morphisms satisfy this equation, and if $h,k$ satisfy it, then $kha=kbTh=cTkTh=cT(kh)$. Hence these objects and morphisms form the Eilenberg-Moore category ${\mathcal{C}}^T$, with the forgetful functor $U(A,a)=A$ and $Uh=h$.

Define the free algebra functor $F^T$ by $F^{T}X=(TX,{\mu }_X)$ and $F^{T}f=Tf$. The monad laws make ${\mu }_X$ an algebra action, and naturality of $\mu$ makes $Tf$ a monad algebra morphism. For an algebra for a monad $(A,a)$, definewith proposed inverse $g\mapsto aTg$. This inverse is a monad algebra morphism, sinceOne composite is $aTg{\eta }_X=a{\eta }_{A}g=g$. For a monad algebra morphism $h$, the other is $aT(h{\eta }_X)=aThT{\eta }_X=h{\mu }_{X}T{\eta }_X=h$. Both formulas commute with composition in a category in $X$ and with monad algebra morphisms in $(A,a)$, so the bijection is natural. Thus