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

For a locally small category $\mathcal{C}$, a representation of a functor $F:\mathcal{C}\to \mathbf{Set}$ is an object $A$ and an element $a\in F(A)$ such thatis a bijection for every $B$, naturally in $B$. Equivalently, $\theta :\mathcal{C}(A,-)\cong F$ is a natural isomorphism.

Suppose $(A,a)$ and $(A^{\prime },a^{\prime })$ are two representations. Universality gives unique mapssuch that $F(u)(a)=a^{\prime }$ and $F(v)(a^{\prime })=a$. Then $F(vu)(a)=a$, and uniqueness applied to the element $a$ gives $vu=1_A$. Similarly $uv=1_{A^{\prime }}$. Thus the representing objects are uniquely isomorphic in a way carrying one universal element of a set-valued functor to the other.

For $F:\mathcal{C}\to \mathcal{D}$ and $B\in \mathcal{D}$, the comma category $(B\downarrow F)$ has objects $(A,u)$ with $u:B\to F(A)$. A morphism $(A,u)\to (A^{\prime },u^{\prime })$ is a map $h:A\to A^{\prime }$ satisfyingThe universal arrow from an object to a functor criterion says that $F$ has a left adjoint exactly when $(B\downarrow F)$ has an initial object for every $B$. Indeed, an initial $(LB,{\eta }_B)$ represents the functor $A\mapsto \mathcal{D}(B,FA)$, and uniqueness makes $B\mapsto LB$ functorial.

When $F:\mathcal{C}\to \mathbf{Set}$ and $1$ is a singleton, an arrow $1\to F(A)$ is just an element $a\in F(A)$. Hence $(1\downarrow F)$ is the category of elements, and its initial objects are exactly the representations of $F$. This proves

If $F$ has a left adjoint, the universal-arrow criterion immediately makes it representable. Conversely, suppose $\mathcal{C}$ is cocomplete and $F\cong \mathcal{C}(A,-)$. For a set $S$, form the copowerThe coproduct in a category universal property gives natural bijectionsso $L⊣F$.

Cocompleteness cannot be omitted. Let $\mathcal{C}$ be the category of ordinals in reverse order: there is one arrow $\alpha \to \beta$ exactly when $\alpha \ge \beta$ in the ordinary ordering. This large poset is locally small and complete. For a set-indexed family $({\alpha }_i)$, its product in the reversed order is the ordinary supremum ${\sup }_i{\alpha }_i$, and equalizers in a poset are automatic. But $\mathcal{C}$ has no initial object, since that would be a largest ordinal. Any representable functor $\mathcal{C}(A,-)$ is therefore the requested example: if it had a left adjoint $L$, thenwould be a singleton for every $B$, making $L(\varnothing )$ initial, a contradiction.

A balanced category is one in which every morphism that is both a monomorphism and an epimorphism is an isomorphism. A faithful functor reflects monomorphisms and epimorphisms: cancellation after applying the functor can be pulled back by injectivity on hom-sets. Therefore, if $F:\mathcal{C}\to \mathcal{D}$ is faithful, $\mathcal{C}$ is balanced, and $F(f)$ is an isomorphism, then $f$ is both monic and epic and hence is an isomorphism. Thus $F$ reflects isomorphisms.

Now let $F:\mathcal{C}\rightleftarrows \mathcal{D}:G$ be an adjunction with unit $\eta$ and counit $\epsilon$. Under the adjunction bijectionthe morphism $Fu$ corresponds to ${\eta }_{A}u$. If $F$ is faithful and ${\eta }_{A}u={\eta }_{A}v$, then $Fu=Fv$ and hence $u=v$, so every ${\eta }_A$ is monic. Conversely, if every ${\eta }_B$ is monic and $Fu=Fv$ for $u,v:A\to B$, naturality givesand monicity gives $u=v$. This proves the faithful left adjoint criterion.

Assume next that $\mathcal{C}$ is balanced, every arrow in $\mathcal{D}$ factors as a strong epimorphism followed by a monomorphism, and both $\eta$ and $\epsilon$ are pointwise monic. The unit criterion makes $F$ faithful. The triangle identitymakes the monomorphism ${\epsilon }_{FA}$ a split epimorphism, hence an isomorphism. Thus $F({\eta }_A)$ is an isomorphism. The first paragraph shows that $F$ reflects isomorphisms, so ${\eta }_A$ is an isomorphism for every $A$. By the fully faithful adjoint criterion, $F$ is full and faithful.

To prove closure under strong quotients, let $q:FA\twoheadrightarrow B$ be a strong epimorphism. Naturality givesThe right side is a strong epimorphism, while ${\epsilon }_B$ is monic. The lifting property supplies $s:B\to FGB$ withSince ${\epsilon }_B$ is also monic, it is an isomorphism. Hence $B\cong F(GB)$ lies in the essential image of $F$.

Conversely, assume $F$ is full and faithful and its image is closed under strong quotients. Then $\eta$ is an isomorphism and in particular pointwise monic. Factor a counit component aswith $e$ strong epic and $m$ monic. Closure under strong quotients gives $C\cong F{A}^{\prime }$ for some $A^{\prime }$. After choosing this isomorphism, fullness writes $e=Fh$ for a map $h:GB\to A^{\prime }$. Since $e$ is epic and $F$ is faithful, $h$ is epic. The transpose ofis $1_{GB}$, soThus $h$ is also monic. Balancedness makes $h$ an isomorphism, hence $e$ is an isomorphism and ${\epsilon }_B=me$ is monic. This proves the pointwise-monic unit-and-counit criterion.

Balancedness is necessary. Let $\mathcal{C}$ be the two-element poset $0<1$, viewed as a category, and let $\mathcal{D}$ be the terminal category. The unique $F:\mathcal{C}\to \mathcal{D}$ is left adjoint to the functor $G$ selecting $1$. Every morphism in a poset is monic, so the unit and counit are pointwise monic. But $F$ is not full: the unique arrow $F1\to F0$ has no preimage $1\to 0$. This is the pointwise-monic adjunction over a non-balanced poset.

A diagram in a category is a functor $D:\mathcal{J}\to \mathcal{C}$. A cone over a diagram with vertex $A$ is a familysuch that $D(u){\gamma }_i={\gamma }_j$ for every $u:i\to j$. A categorical limit is a terminal cone: for every cone $(A,\gamma )$ there is a unique map $A\to \lim D$ commuting with all legs.

Suppose $\mathcal{C}$ has small products and equalizers. For a small diagram $D$, formThere are two maps $r,s:P\rightrightarrows Q$. In the coordinate indexed by $u:i\to j$, letThe equalizer $E\to P$ imposes exactly the cone equations. Maps $A\to E$ are therefore naturally the same as cones from $A$ to $D$, so $E\cong \lim D$. This is the construction of small limits from products and equalizers.

Let $F:\mathcal{I}\to \mathcal{J}$ be initial, so every $(F\downarrow j)$ is nonempty and connected. Restriction sends a cone $(A,{\gamma }_j)$ over $D$ to $(A,{\gamma }_{Fi})$ over $DF$. Conversely, given a cone $(A,{\delta }_i)$ over $DF$, choose an objectand defineA morphism in the comma category shows that this expression is unchanged along one edge, and connectedness makes it independent of the chosen object. The cone equations follow by choosing $(i,vu)$ for an arrow $v:j\to j^{\prime }$. This construction is inverse to restriction and acts identically on vertex maps, proving the cone restriction along an initial functor isomorphism.

Terminal objects in the two cone categories therefore correspond. Whenever the $\mathcal{I}$-shaped limit exists,naturally in $D$. Equivalently, the triangle formed by precompositionand the two limit functors commutes up to natural isomorphism.

For the converse, suppose this commutation holds for $\mathcal{C}={\mathbf{Set}}^{\mathrm{op}}$. Passing to opposite categories says that restriction along $F^{\mathrm{op}}$ preserves all set-valued colimits. Fix $j\in \mathcal{J}$ and take the representable functorIts colimit is a singleton: the category of its elements has the initial object $(j,1_j)$. The restricted colimit iswhose elements are precisely the connected components of $(F\downarrow j)$. By the assumed comparison this set is also a singleton. Thus $(F\downarrow j)$ is nonempty and connected for every $j$, so $F$ is initial.

Because $F:\mathbf{Set}\to \mathbf{Set}$ preserves finite limits and colimits, $F(1)$ is a singleton and $F(\varnothing )=\varnothing$. For $x\in X$, let $\bar{x}:1\to X$ select $x$ and definewhere $\ast$ is the unique element of $F(1)$. This is natural in $X$. Any natural transformation $1_{\mathbf{Set}}\to F$ has the unique possible component at $1$, and naturality along every $\bar{x}$ forces the displayed value, so $\alpha$ is unique.

If $x\ne y$, the equalizer of $\bar{x},\bar{y}:1\rightrightarrows X$ is empty. Since $F$ preserves this equalizer, $F(\bar{x})(\ast )\ne F(\bar{y})(\ast )$. Hence every ${\alpha }_X$ is injective, so $\alpha$ is pointwise monic.

Finite-colimit preservation makes ${\alpha }_n:n\to F(n)$ bijective for every finite set. Use the stated characterization of $\mathbb{N}$ by the coproduct diagramand the coequalizer of $s,1_{\mathbb{N}}:\mathbb{N}\rightrightarrows \mathbb{N}$. Applying $F$ preserves both diagrams. Naturality and uniqueness in this characterization identify ${\alpha }_{\mathbb{N}}:\mathbb{N}\to F(\mathbb{N})$ as an isomorphism.

For a countable family $(A_n)$, let $p:{\coprod }_n{A}_n\to \mathbb{N}$ record the summand. Each squareis a pullback. Applying $F$ and using $F(1)\cong 1$ and $F(\mathbb{N})\cong \mathbb{N}$ shows that $F(A_n)$ is exactly the fiber of $F(p)$ over $n$. Those fibers partition $F({\coprod }_n{A}_n)$, so the canonical mapis bijective. Thus $F$ preserves countable coproducts.

Now choose $x\in F(A)\setminus {\alpha }_A(A)$ and defineIt is upward closed. Since $A=A^{\prime }\bigsqcup (A\setminus A^{\prime })$ and $F$ preserves binary coproducts, $x$ lies in exactly one of the two summands, so exactly one of $A^{\prime }$ and its complement lies in $U$. Pullback preservation gives closure under finite intersections.

For countable completeness, take $A_n\in U$ and put $B={\bigcap }_n{A}_n$. If $B\notin U$, then $A\setminus B\in U$. Partition $A$ into $B$ and the setswhich record the first failed membership. Since $F$ preserves countable coproducts, exactly one cell of this partition lies in $U$. It cannot be $B$, so some $C_n\in U$. But $C_n\subseteq A\setminus A_n$, forcing $A\setminus A_n\in U$, contrary to $A_n\in U$. Hence $B\in U$.

Finally no finite $K$ belongs to $U$. Indeed, $F(K)\cong K$ through ${\alpha }_K$, so if $x$ came from $F(K)$ then naturality would put $x$ in the image of ${\alpha }_A$. Thus $U$ is a countably complete ultrafilter and is nonprincipal.

Conversely, let $U$ be such an ultrafilter on $A$ and define the ultrapower endofunctor of setsIt preserves the terminal object and products: the mapis bijective because $U$ is closed under finite intersections. It preserves equalizers because an equality holding for an equivalence class holds on a $U$-large set, and the representative can be changed off that set to land in the equalizer. Hence it preserves all finite limits.

For $f:A\to {\coprod }_n{B}_n$, countable completeness implies that one index fiberbelongs to $U$; otherwise the countable intersection of all complementary fibers would be empty and belong to $U$. Thus every class $[f]$ lies in one and only one $F(B_n)$, proving preservation of countable coproducts.

The class of the identity map $A\to A$ is not represented by a constant map, since every equality set $\{a:a=a_0\}$ is a singleton and is not in $U$. Therefore ${\alpha }_A:A\to F(A)$ is not surjective. Since $\alpha$ is the unique natural transformation from the identity functor to $F$, a natural isomorphism $1_{\mathbf{Set}}\cong F$ would have to equal $\alpha$, which is impossible.

An exponentiable object $X$ in a category with finite products is one for whichhas a right adjoint $[X,-]$. The terminal object is exponentiable because $-\times 1\cong 1_{\mathcal{C}}$. If $X$ and $Y$ are exponentiable, thenis a composite of two left adjoints and therefore has the composite right adjoint $[X,[Y,-]]$. Exponentiable objects are consequently closed under finite products.

In the category of metric spaces and non-expansive maps, the terminal object is the one-point space. The product of $X$ and $Y$ has underlying set $X\times Y$ and metricThis is the smallest metric making both projections non-expansive, and the product pairing of two non-expansive maps is non-expansive. If $X$ and $Y$ are bounded, so is this product. Hence both $\mathbf{Met}$ and the category of bounded metric spaces and non-expansive maps ${\mathbf{Met}}_b$ have finite products.

For bounded $X,Y$, define the metric exponential candidateThe supremum is finite because $Y$ is bounded. For every $x,y$ one has the useful evaluation inequalityIndeed, if the second term does not already dominate, the pair $(x,y)$ occurs in the defining supremum.

Assume $\bar{d}$ is a metric. The evaluation mapis non-expansive by this inequality. Postcomposition by a non-expansive $k:Y\to Y^{\prime }$ is non-expansive on function spaces, because every pair contributing to $\bar{d}(kf,kg)$ also contributes a no-smaller bound to $\bar{d}(f,g)$. Thus $[X,-]$ is a functor.

If $h:Z\times X\to Y$ is non-expansive, each $h_z(x)=h(z,x)$ is non-expansive. Whenevernon-expansiveness of $h$ forces the latter distance to be at most $d_Z(z,z^{\prime })$. Hence $z\mapsto h_z$ is non-expansive into $[X,Y]$. Conversely, a non-expansive $Z\to [X,Y]$ followed by evaluation gives a non-expansive $Z\times X\to Y$. These inverse operations are natural, proving

It remains to obtain the triangle inequality from interpolation. Nonnegativity and symmetry of $\bar{d}$ are immediate. If $f\ne g$, taking $x=y$ where $f(x)\ne g(x)$ proves separation; and $\bar{d}(f,f)=0$ follows from non-expansiveness of $f$.

LetFix a pair $x,y$ contributing $D=d_Y(fx,hy)$, so $t=d_X(x,y)<D$. Suppose for contradiction that $D>a+b$. If $t\le a+b$, choose $r+s=t$ with $r\le a$ and $s\le b$. If $t>a+b$, choose $r+s=t$ with $r>a$ and $s>b$. Since $X$ is an interpolating metric space, there is $z$ with $d(x,z)=r$ and $d(z,y)=s$. Applying the evaluation inequality twice givesIn the first case the right side is at most $a+b$, and in the second it equals $r+s=t<D$. Both are contradictions. Therefore $D\le a+b$ for every contributing pair, and taking the supremum givesThus $\bar{d}$ is a metric whenever $X$ is interpolating, and the preceding adjunction proves every bounded interpolating space is exponentiable in ${\mathbf{Met}}_b$.

Let $\mathcal{E}$ be an elementary topos with subobject classifier $\top :1\to \Omega$. A local operator is a map $j:\Omega \to \Omega$ which is inflationary, idempotent, preserves truth, and preserves binary meets:If $m:A^{\prime }\hookrightarrow A$ is classified by ${\chi }_m:A\to \Omega$, its closure operation of a local operator is classified by $j{\chi }_m$. The mono is j-dense monomorphism when this closure is all of $A$, and $j$-closed when it equals its closure. An object $X$ is a j-sheaf when every map $A^{\prime }\to X$ along a $j$-dense mono $A^{\prime }\hookrightarrow A$ extends uniquely to $A\to X$.

The closed-subobject classifier is the equalizerThus maps to ${\Omega }_j$ classify precisely the $j$-closed subobjects. Idempotence factors $j$ as

To prove that ${\Omega }_j$ is a $j$-sheaf, let $m:B\hookrightarrow A$ be dense and let $f:B\to {\Omega }_j$ classify a closed subobject $C\hookrightarrow B$. Take the closure in $A$ of the composite $C\hookrightarrow A$. Pullback stability of closure givesso the classifier $A\to {\Omega }_j$ of ${\overline{C}}^{,A}$ extends $f$. If two closed subobjects of $A$ restrict to the same subobject of dense $B$, the equalizer of their classifiers is a closed subobject containing $B$; it is both closed and dense and hence equals $A$. The extension is therefore unique.

Letbe the sheaf reflector for a local operator. The subobject classifier in the sheaf topos is ${\Omega }_j$. We prove the four assertions through the cycle

The canonical map comparing the reflected ambient classifier with the sheaf classifier isConsequently $L$ preserves the subobject classifier exactly when $L(q)$ is an isomorphism. This proves $(i)⟺(ii)$.

Since $qi=1_{{\Omega }_j}$, one hasIf $L(q)$ is an isomorphism then $L(i)$ is its inverse. Conversely, if $L(i)$ is an isomorphism, the same equation makes $L(q)$ its inverse. A monomorphism is sent to an isomorphism by sheafification exactly when it is $j$-dense, so $(ii)⟺(iii)$.

Assume $(iii)$ and let $m:A^{\prime }\hookrightarrow A$ have characteristic map $\chi :A\to \Omega$. Form the pullbackBecause dense monos are pullback-stable, $d:A^{\prime \prime }\hookrightarrow A$ is $j$-dense. The original $A^{\prime }$ factors through $A^{\prime \prime }$, and its characteristic map inside $A^{\prime \prime }$ is the top horizontal map followed by $i$, which is fixed by $j$. Hence $A^{\prime }\hookrightarrow A^{\prime \prime }$ is $j$-closed. This proves $(iv)$.

Finally assume $(iv)$ and apply it to $i:{\Omega }_j\hookrightarrow \Omega$:where $c$ is closed and $d$ is dense. Since $d$ is monic and $i=dc$, the map $c$ is the pullback of $d$ along $i$. It is therefore dense as well as closed, and hence is an isomorphism. Thus $i$ is, up to an isomorphism, the dense mono $d$, proving $(iii)$. All four conditions are equivalent, as summarized by the subobject-classifier preservation criterion for a sheaf reflector.