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

A monomorphism is a left-cancellable morphism. A strong monomorphism $m:S\to A$ has the right lifting property against every epimorphism: from a commutative squarewith $e$ epic, one obtains $d:Y\to S$ satisfying $de=u$ and $md=v$. A regular monomorphism is an equalizer of a parallel pair.

Suppose $m:S\to A$ equalizes $r,s:A\rightrightarrows C$. In the square above,Since $e$ is epic, $rv=sv$, so the universal property of the equalizer gives the required $d$. Thus every regular monomorphism is strong.

Let $m_i:S_i\to A$ be strong for $i=1,2$, and let $P=S_1{\times }_A{S}_2$. Given a lifting square against $P\to A$, compose its top map with each projection. Strength of $m_i$ produces maps $d_i:Y\to S_i$ with $m_i{d}_i=v$. The pair $(d_1,d_2)$ has equal composites to $A$, hence induces $d:Y\to P$. Therefore intersections of strong subobjects are strong.

Call a morphism anodyne when it is both monic and epic, and call an object saturated when it is injective with respect to every such morphism. Let $m:S\to B$ be a strong subobject of a saturated object. Given an anodyne $e:X\to Y$ and $u:X\to S$, saturation of $B$ extends $mu$ to some $v:Y\to B$. Strength of $m$ applied to $mu=ve$ lifts $v$ to $d:Y\to S$ with $de=u$. Hence $S$ is saturated.

Now embed $A$ as a subobject of a saturated object $B$. Since the category is well-powered, the strong subobjects of $B$ through which $A\to B$ factors form a set; completeness supplies their intersection $j:R\to B$. The same coordinatewise lifting argument used for two factors shows that $j$ is strong, so $R$ is saturated.

The induced map $\eta :A\to R$ is monic. To prove it epic, let $f,g:R\rightrightarrows C$ satisfy $f\eta =g\eta$. Their equalizer $q:E\to R$ is regular and hence strong. Composites of strong monomorphisms are strong, so $jq:E\to B$ is a strong subobject containing $A$. Minimality of the intersection forces $R\to B$ to factor through $E$, which implies $f=g$. Thus $\eta$ is epic and therefore anodyne.

For every saturated $S$, each map $a:A\to S$ extends across $\eta$ to a map $\bar{a}:R\to S$. This extension is unique because $\eta$ is epic. Consequently $A\mapsto R$ is left adjoint to the inclusion of saturated objects: the full subcategory $\mathcal{S}$ is reflective. This is the saturated reflection from a strong-subobject intersection.

It remains to prove that $\mathcal{S}$ is balanced. First let $e:X\to Y$ be epic in $\mathcal{S}$. If $f,g:Y\rightrightarrows Z$ are morphisms in the ambient category, embed $Z$ into a saturated object $T$. Equality $fe=ge$ then implies equality after composing with $Z\to T$; epicity in the full subcategory gives equality there, and monicity of $Z\to T$ gives $f=g$. Thus $e$ is epic in the ambient category.

If $e:X\to Y$ is also monic in $\mathcal{S}$, it is monic in the ambient category as well. Indeed, for $u,v:W\rightrightarrows X$ with $eu=ev$, reflect $W$ by an anodyne map $W\to RW$. Saturation extends $u$ and $v$ to $\bar{u},\bar{v}:RW\rightrightarrows X$; ambient epicity of $W\to RW$ and monicity of $e$ inside $\mathcal{S}$ give $\bar{u}=\bar{v}$, hence $u=v$. Therefore $e$ is anodyne in the ambient category. Saturation of $X$ extends $1_X$ across $e$ to a retraction $r:Y\to X$. Since $e$ is epic, $ere=e$ implies $er=1_Y$, so $e$ is an isomorphism. Hence $\mathcal{S}$ is balanced.

Let $B$ be a subterminal object in a cartesian closed category. For every $X$ and $A$, the exponential object adjunction givesThe set on the right has at most one element because $B$ is subterminal. Hence $B^A$ is subterminal, proving that $\mathrm{Sub}(1)$ is an exponential ideal.

Now let $\mathcal{D}\subseteq \mathcal{C}$ be reflective, with reflector $L$ and unit ${\eta }_A:A\to LA$. Recall the useful form of its universal property: an object $D$ lies in $\mathcal{D}$ precisely when every map $f:A\to D$ factors uniquely through ${\eta }_A$.

Suppose first that $\mathcal{D}$ is an exponential ideal. Reflective subcategories are closed under ambient limits, so $LA\times LB$ lies in $\mathcal{D}$. Given $f:A\times B\to D$ with $D\in \mathcal{D}$, curry in the first variable to obtain $A\to D^B$. Since $D^B\in \mathcal{D}$, this factors uniquely through ${\eta }_A$ and uncurries to $LA\times B\to D$. Curry once more, now in $B$; since $D^{LA}\in \mathcal{D}$, the result factors uniquely through ${\eta }_B$. Thus every $f$ factors uniquely throughThis makes $LA\times LB$ a reflection of $A\times B$, so uniqueness of reflections gives

Conversely, suppose $L$ preserves binary products, and take $D\in \mathcal{D}$. To prove $D^A\in \mathcal{D}$, start with $f:X\to D^A$ and let $\tilde{f}:X\times A\to D$ be its transpose. Since $D$ is reflective, $\tilde{f}$ factors uniquely throughComposing the resulting map $LX\times LA\to D$ with $1_{LX}\times {\eta }_A$ and currying produces an extension $LX\to D^A$ of $f$. Product preservation identifies the unit on $LX\times A$ with $1_{LX}\times {\eta }_A$, so the same universal property proves uniqueness. Therefore $D^A$ is reflective, and $\mathcal{D}$ is an exponential ideal. This proves the reflector product criterion for an exponential ideal.

Finally consider the arrow category $[2,\mathbf{Set}]$. For arrows $a:A_0\to A_1$ and $b:B_0\to B_1$, letThen the exponential $b^a$ is the arrowIndeed, a commutative square from $c:C_0\to C_1$ to this arrow is, after currying, exactly a commutative square $a\times c\to b$. This establishes the required exponential adjunction and proves that $[2,\mathbf{Set}]$ is cartesian closed.

If $b$ is injective, two elements $(u_0,u_1)$ and $(u_0^{\prime },u_1)$ of $F$ haveso injectivity gives $u_0=u_0^{\prime }$. Hence $F\to B_1^{A_1}$ is injective. The category of injective functions is therefore an exponential ideal in the arrow category. Its terminal object and binary products are inherited pointwise, so these same exponential objects make $\mathrm{Mono}(\mathbf{Set})$ cartesian closed.

Consider the commutative squarewhere $F$ is a final functor and $G$ is a discrete fibration. For $B\in \mathcal{B}$, choose an object $(A,\beta :B\to FA)$ of the nonempty comma category $(B\downarrow F)$. Commutativity gives an arrowLift it uniquely through $G$ with codomain $HA$, and define $LB$ to be the domain of this lift.

This definition does not depend on the choice of $(A,\beta )$. A morphism $u:(A,\beta )\to (A^{\prime },{\beta }^{\prime })$ in the comma category satisfies $Fu\beta ={\beta }^{\prime }$. The composite of the lift of $K\beta$ with $Hu$ is then a lift of $K{\beta }^{\prime }$ with codomain $H{A}^{\prime }$, so uniqueness of discrete-fibration lifts says that it is the chosen lift and has the same domain. Since $(B\downarrow F)$ is connected, all choices give the same object $LB$.

For $v:B\to B^{\prime }$, define $Lv$ as the unique lift through $G$ of $Kv:KB\to K{B}^{\prime }=G(L{B}^{\prime })$ with codomain $L{B}^{\prime }$. Its domain is $LB$: choose ${\beta }^{\prime }:B^{\prime }\to FA$, and observe that composing this lift with the lift of $K{\beta }^{\prime }$ yields the lift associated with ${\beta }^{\prime }v:B\to FA$. Uniqueness of lifting also proves preservation of identities and composition, so $L$ is a functor and $GL=K$.

For $B=FA$, choose $(A,1_{FA})$ in $(FA\downarrow F)$. The lift of $1_{GHA}$ is $1_{HA}$, hence $LFA=HA$; the same lifting argument on arrows gives $LF=H$. Finally, if $L^{\prime }$ is another filler, then for every $\beta :B\to FA$, the arrow $L^{\prime }\beta :L^{\prime }B\to HA$ is a lift of $K\beta$. Unique lifting forces $L^{\prime }B=LB$ and then forces equality on arrows. Thus $L$ is unique, proving orthogonality of final functors and discrete fibrations.

For an arbitrary functor $F:\mathcal{C}\to \mathcal{D}$, define a category $\mathcal{E}$ as follows. Its objects are pairs $(B,c)$, where $B\in \mathcal{D}$ and $c$ is a connected component of $(B\downarrow F)$. Precomposition by an arrow $g:B\to B^{\prime }$ definesThere is one morphism $(B,c)\to (B^{\prime },c^{\prime })$ over $g$ exactly when $g^{\ast }(c^{\prime })=c$. Functoriality of precomposition makes this a category, and projectionis a discrete fibration: given $g:B\to B^{\prime }=G(B^{\prime },c^{\prime })$, its unique lift with codomain $(B^{\prime },c^{\prime })$ has domain $(B,g^{\ast }{c}^{\prime })$.

Define $H:\mathcal{C}\to \mathcal{E}$ bywhere $[1_{FA}]$ is the component of the identity object in $(FA\downarrow F)$. For $u:A\to A^{\prime }$, use the unique arrow over $Fu$. It exists because $(Fu{)}^{\ast }[1_{F{A}^{\prime }}]$ contains the object $Fu:FA\to F{A}^{\prime }$, and this object is joined to $1_{FA}$ by the morphism $u$ in $(FA\downarrow F)$. Plainly $GH=F$.

For $(B,c)\in \mathcal{E}$, an object of $((B,c)\downarrow H)$ is exactly an arrow $\beta :B\to FA$ lying in the component $c$: the condition for an arrow $(B,c)\to H(A)$ is precisely ${\beta }^{\ast }[1_{FA}]=c$. Morphisms agree with those in $(B\downarrow F)$. Hencewhich is nonempty and connected by definition. Therefore $H$ is final. We have factored $F=GH$ as a final functor followed by a discrete fibration, giving the final-discrete-fibration factorization.

A monad on a category $\mathcal{C}$ consists of an endofunctor $T$, a unit $\eta :1_{\mathcal{C}}\Rightarrow T$, and a multiplication $\mu :T^2\Rightarrow T$ satisfyingIf $F:\mathcal{C}\rightleftarrows \mathcal{D}:G$ is an adjunction with unit $\eta$ and counit $\epsilon$, thendefines the monad induced by an adjunction. The two triangle identities give the unit laws, while naturality of $\epsilon$ gives associativity.

Let $\mathcal{D}$ now be a full subcategory of $[\mathcal{C},\mathcal{C}]$ that contains the identity endofunctor and is closed under composition, and suppose $T$ is terminal in $\mathcal{D}$. There is exactly one natural transformationand exactly oneBoth sides of either unit law are endomorphisms of the terminal object $T$, so they equal $1_T$; both sides of associativity are maps $T^3\to T$, so they are equal as well. This gives a monad, and terminality also makes both structure maps unique. This is the monad structure on a terminal endofunctor.

For a set $A$, let $\mathcal{U}(A)$ be the set of ultrafilters on $A$. A function $f:A\to A^{\prime }$ induces the pushforwardwhich makes $\mathcal{U}$ the ultrafilter functor. There is no ultrafilter on the empty set. Moreover, every ultrafilter on $A\bigsqcup B$ contains exactly one of the complementary summands $A$ and $B$, and restriction gives a unique ultrafilter on that summand. Thereforeso $\mathcal{U}$ preserves finite coproducts.

Let $F:\mathbf{Set}\to \mathbf{Set}$ preserve finite coproducts. For $x\in F(A)$ defineThe decomposition $A=B\bigsqcup (A\setminus B)$ and preservation of coproducts say that $x$ lies in exactly one of the two corresponding images. Thus exactly one of $B$ and its complement belongs to ${\Phi }_A(x)$. Upward closure follows by factoring subset inclusions. If $B,C\in {\Phi }_A(x)$, decompose $A$ into the four disjoint Boolean cells determined by $B$ and $C$. The unique cell containing $x$ must lie inside both sets, so $B\cap C\in {\Phi }_A(x)$. Hence ${\Phi }_A(x)$ is an ultrafilter.

For $f:A\to A^{\prime }$, the decompositionsshow thatThus $\Phi :F\Rightarrow \mathcal{U}$ is natural.

It is the only such natural transformation. For $B\subseteq A$, let ${\chi }_B:A\to \{0,1\}$ be its characteristic function. Sinceand the two ultrafilters on $\{0,1\}$ are the principal ones, naturality with the two singleton inclusions forces any transformation $F\Rightarrow \mathcal{U}$ to send each summand to the corresponding principal ultrafilter. Naturality with ${\chi }_B$ then says that $B$ belongs to the image ultrafilter exactly when $x$ lies in the image of $F(B)\to F(A)$. Hence the transformation must be $\Phi$.

The ultrafilter functor is therefore the terminal finite-coproduct-preserving set endofunctor. The preceding terminal-object argument supplies its unique ultrafilter monad structure.

The assertion that filtered colimits commute with finite limits in sets means that for every filtered category $\mathcal{J}$, every finite category $\mathcal{I}$, and every functor $D:\mathcal{I}\times \mathcal{J}\to \mathbf{Set}$, the canonical comparisonis a bijection. Surjectivity follows because an element on the right uses only finitely many representatives and compatibility equations, so filteredness moves all of them to one common stage. For injectivity, equality likewise consists of finitely many equalities, which become true at one later common stage.

The dual assertion fails in ${\mathbf{Set}}^{\mathrm{op}}$. Equivalently, cofiltered limits need not commute with finite colimits in sets. Index inverse systems by $n\in \mathbb{N}$, with arrows $n+1\to n$, and putusing the inclusions $A_{n+1}\hookrightarrow A_n$ and the unique maps $A_n\to B_n,C_n$. Since $A_n$ is nonempty, the pushout $B_n{\bigsqcup }_{A_n}{C}_n$ is a singleton at every stage, so its inverse limit is a singleton. Butand the pushout of the inverse limits is $1{\bigsqcup }_{\varnothing }1$, which has two elements. Thus a cofiltered limit fails to preserve this finite pushout.

Let $F$ be a presheaf of sets on a topological space $X$. The neighborhoods of $x$, ordered by reverse inclusion, form a filtered category, andThe first result therefore says that the stalk functor for presheaves of sets preserves finite limits.

For a set $S$, define a presheaf $R_{x}S$ bywith identity restrictions between neighborhoods of $x$ and the unique maps to $1$ otherwise. A natural transformation $F\to R_{x}S$ is exactly a compatible family of maps $F(U)\to S$ over neighborhoods of $x$, hence exactly a map $F_x\to S$. Thusso $R_x$ is right adjoint to the stalk functor.

Now restrict to sheaves. Suppose two morphisms $\alpha ,\beta :F\rightrightarrows G$ induce the same map on every stalk. For $s\in F(U)$ and every $x\in U$, equality of the two germs gives a neighborhood $V_x\subseteq U$ on which $\alpha (s)$ and $\beta (s)$ agree. The $V_x$ cover $U$, so the uniqueness axiom for $G$ gives $\alpha (s)=\beta (s)$. Therefore the joint stalk functor on sheaves of setsis faithful.

The presheaf $R_{x}S$ above is already a sheaf: an open containing $x$ has a cover member containing $x$, and compatibility forces one common element of $S$. Hence a right adjoint to $P$ sends a family $(S_x)$ to the product ${\prod }_x{R}_x{S}_x$, whose existence follows from the assumed closure of $\mathbf{Sh}(X)$ under limits.

Each stalk preserves finite limits, so $P$ preserves equalizers. If $P(f)$ is an isomorphism, its monicity and epicity are reflected by the faithful functor $P$; since $\mathbf{Sh}(X)$ is assumed balanced, $f$ is an isomorphism. Thus $P$ reflects isomorphisms. The Beck comonadicity theorem now applies: $P$ has a right adjoint, reflects isomorphisms, and preserves the required equalizers. Consequently $P$ is comonadic.

A semi-additive category is a category whose hom-sets are commutative monoids and whose composition is additive in each variable, with finite products and coproducts.

Suppose first that $P=A\times B$ is a binary product in a category, with projections $p_1,p_2$. The zero morphisms and the product property define mapsbyThe two projections of $i_1{p}_1+i_2{p}_2$ equal those of $1_P$, soFor $f:A\to C$ and $g:B\to C$, the mapsatisfies $h{i}_1=f$ and $h{i}_2=g$. If $k$ has the same restrictions, thenThus $(P,i_1,i_2)$ is also the binary coproduct. The dual argument starts from a coproduct and makes it a product. Hence binary products and coproducts coincide canonically as biproducts.

Let $f,g:A\rightrightarrows B$ be a reflexive pair in an additive category, with $fr=gr=1_B$. For every object $C$, regard $x:C\to A$ as an arrow from $fx$ to $gx$ between objects of $\mathcal{C}(C,B)$. The identity at $b:C\to B$ is $rb$.

If $gx=fy$, define the composite byIts source and target areThe identities follow fromand associativity follows immediately by expanding both iterated composites and using the matching equations. The inverse of $x$ iswhose source is $gx$, whose target is $fx$, and whose two composites with $x$ are the appropriate identity arrows. These formulas are natural in $C$, so the Yoneda lemma identifies them with structure morphisms in $\mathcal{C}$. The pair is therefore an internal groupoid, proving that every reflexive pair in an additive category is an internal groupoid.

This fails for semi-additive categories. In the category of commutative monoids, letunder coordinatewise addition. The two projections $f,g:R\rightrightarrows \mathbb{N}$ have the common splitting $r(n)=(n,n)$, so they form a reflexive pair. Its underlying reflexive graph is the usual order category on $\mathbb{N}$: there is an arrow $m\to n$ exactly when $m\le n$. If it were an internal groupoid, the arrow $0\to 1$ would have an inverse $1\to 0$, but $(1,0)\notin R$. Therefore this reflexive pair is not an internal groupoid, and “additive” cannot be weakened to “semi-additive.”