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

A regular epimorphism $e:A\to B$ is the coequalizer of some parallel pair $r,s:R\rightrightarrows A$. A strong epimorphism has the left lifting property against every monomorphism: in every commutative squarewith $m$ monic, there is $d:B\to C$ satisfying $de=u$ and $md=v$.

If $e$ coequalizes $r,s$, then $mur=ver=ves=mus$. Monicity gives $ur=us$, so the coequalizer property gives a unique $d$ with $de=u$. Now $mde=mu=ve$; every coequalizer is epic, hence $md=v$. This proves that every regular epimorphism has the lifting property of a strong epimorphism.

For an arbitrary $f:A\to B$, form its kernel pair $r,s:R=A{\times }_{B}A\rightrightarrows A$ and let $e:A\to I$ be its coequalizer. There is a unique $m:I\to B$ with $f=me$. To show $m$ monic, suppose $mu=mv$ for $u,v:X\rightrightarrows I$. Pull back $e$ along $u$, obtaining an epic $p:P\to X$ and $a:P\to A$ with $ea=up$. Pull back $e$ along $vp$, obtaining an epic $q:Q\to P$ and $b:Q\to A$ with $eb=vpq$. Thenso $(aq,b)$ factors through the kernel pair of $f$. Since $e$ coequalizes that pair, $eaq=eb$, and hence $upq=vpq$. The composite $pq$ is epic, so $u=v$. This proves the regular-epimorphism-monomorphism factorization from kernel pairs.

If $f$ is strong, apply its lifting property to $f=me$:A diagonal $d:B\to I$ satisfies $md=1_B$. Since $m$ is also monic, $dm=1_I$, so $m$ is an isomorphism and $f$ is regular.

For the category of small categories, let $\mathcal{A}$ have objects $0,1,1^{\prime },2$, nonidentity arrows $a:0\to 1$ and $b:1^{\prime }\to 2$, and no other nonidentity generators. Send it to the ordinal category $[2]=(0\to 1\to 2)$ by identifying $1$ with $1^{\prime }$ and sending $a,b$ to the two generating arrows. The image generates $[2]$, so this is a strong epimorphism in the category of small categories, but it is not full because the composite $0\to 2$ has no preimage; therefore it is not regular.

Every functor factors through the subcategory of its codomain generated by its image. The first functor is strong epic and the inclusion is monic, so strong-epi--mono factorizations always exist in $\mathbf{Cat}$. Regular-epi--mono factorizations do not always exist: the displayed strong nonregular functor would make its monic factor an isomorphism by strongness, forcing the original functor to be regular.

A congruence on a category is an equivalence relation on every hom-set such that $f\sim f^{\prime }$ and $g\sim g^{\prime }$ imply $gf\sim g^{\prime }{f}^{\prime }$ whenever the composites exist. The quotient has the same objects and equivalence classes $[f]$ as morphisms.

For the proposed $\Phi$-maps, reflexivity uses $W=U$, symmetry is immediate, and transitivity is obtained as follows. If representatives over $U$ and $V$ agree after restriction to $W$, while those over $V$ and $T$ agree after restriction to $W^{\prime }$, then their first and third representatives agree over $W\times W^{\prime }$. This object belongs to $\Phi$ and maps below $U\times T$, proving transitivity.

The identity of $A$ is represented by the projection $A\times 1\to A$. If $f:A\times U\to B$ and $g:B\times V\to C$, define their composite over $U\times V$ byPassing to a smaller member of $\Phi$ shows that this is independent of representatives. Associativity follows from associativity of products and composition, and the projection representatives satisfy the identity laws. This constructs the category of partial maps localized at subterminal objects ${\mathcal{C}}_{\Phi }$.

The terminal object remains $1$. Products are the products of $\mathcal{C}$: representatives $f:C\times U\to A$ and $g:C\times V\to B$ pair after restriction to $U\times V$,The product universal property follows after restricting competing representatives to a common member of $\Phi$. The functor $P_{\Phi }$ sends the original projections and pairings to these, so it preserves finite products.

If $\mathcal{C}$ is Cartesian closed, use the same exponential object $B^A$. A representativemay be rearranged as $(C\times U)\times A\to B$ and curried in $\mathcal{C}$ to $C\times U\to B^A$. Currying respects restriction and gives a natural bijectionThus ${\mathcal{C}}_{\Phi }$ is cartesian closed and $P_{\Phi }$ preserves exponentials.

In general this is not a quotient by a congruence. A congruence can identify existing parallel morphisms but cannot create a morphism between two objects. Take $\mathcal{C}=\mathbf{Set}$ and $\Phi =\{0,1\}$, the filter containing the empty subobject of the terminal set. Then every $A\times 0\to B$ represents a $\Phi$-map, so in particular ${\mathcal{C}}_{\Phi }(A,\varnothing )$ is nonempty for nonempty $A$, whereas $\mathbf{Set}(A,\varnothing )$ is empty. Hence no quotient of $\mathbf{Set}$ by a congruence is isomorphic to this ${\mathcal{C}}_{\Phi }$ by an identity-on-objects functor.

An adjunction $F⊣G$ is equivalently specified by a unit and counit of an adjunctionsatisfying the triangle identities

Let $F_i⊣G_i$ have units ${\eta }_i$ and counits ${\epsilon }_i$. The mate correspondence sends $\alpha :F_1\to F_2$ toConversely, $\beta :G_2\to G_1$ givesNaturality and the triangle identities show that the two constructions are inverse, yielding the required bijection of natural transformations.

Now let the endofunctor $F$ carry a monad $(F,\eta ,\mu )$ and let $F⊣G$. Taking right mates turnsinto a counit $ϵ:G\to 1$ and comultiplication $\delta :G\to G^2$. Since mates reverse composition, the monad unit and associativity laws become the comonad counit and coassociativity laws. Moreover, a map $FA\to A$ corresponds under the adjunction to a map $A\to GA$, and the algebra axioms correspond exactly to the coalgebra axioms. This is the monad on a left adjoint induces a comonad on its right adjoint construction and gives an isomorphism of the two structure categories.

For a monoid $M$, the free-$M$-set functor is $F(X)=M\times X$, and its algebras are precisely left $M$-sets, the objects of $[M,\mathbf{Set}]$. Its right adjoint is $G(X)=X^M$. The preceding isomorphism identifies $[M,\mathbf{Set}]$ with the Eilenberg-Moore category of coalgebras for the induced comonad on sets, compatibly with the forgetful functor. Therefore

For $F⊣G$ with unit $\eta$ and counit $\epsilon$, the monad induced by an adjunction iswith unit $\eta$. An algebra for a monad is $(A,a:TA\to A)$ satisfying $a{\eta }_A=1_A$ and $aT(a)=a{\mu }_A$.

The Eilenberg-Moore comparison functor isIf $\mathcal{D}$ has coequalizers of reflexive pairs, definefor a $T$-algebra $(A,a)$. The pair has common section $F{\eta }_A$. Maps $L(A,a)\to D$ correspond by the coequalizer property and the adjunction exactly to algebra morphisms $(A,a)\to K(D)$, naturally in both variables. Hence this is the Left adjoint to the Eilenberg-Moore comparison functor. The monadic length is the least number of successive comparison steps required for the resulting monadic tower to become an equivalence.

For $A\in {\mathcal{C}}_n$, let $A_n=\{a:{\alpha }_n(a)=a\}$. The free ${\mathcal{C}}_{n+1}$-object has underlying setRetain all old operations on $A\times \{0\}$. Putand on every new chain putFor $i>1$, ${\alpha }_i$ is undefined on the new points because none is fixed by ${\alpha }_1$. These definitions satisfy the domain conditions. If $f:A\to U(B^{\prime })$ is a ${\mathcal{C}}_n$-morphism, its unique extension sendsThis proves the required left adjoint.

After adjoining ${\alpha }_{m+1}$ freely, the newly added points lie on fixed-point-free ${\alpha }_1$-chains, while each old point where ${\alpha }_{m+1}$ was added is no longer fixed by ${\alpha }_{m+1}$. Consequently there are no points at which a further free operation must be adjoined. Thus for every $n>m$ the endofunctor and unit/multiplication of the monad induced on ${\mathcal{C}}_m$ are already those induced by ${\mathcal{C}}_m\rightleftarrows {\mathcal{C}}_{m+1}$.

By assumption each adjacent adjunction is a monadic adjunction. The first comparison for ${\mathcal{C}}_m\rightleftarrows {\mathcal{C}}_n$ therefore recovers ${\mathcal{C}}_{m+1}$, and iteration successively recovers ${\mathcal{C}}_{m+2},\dots ,{\mathcal{C}}_n$. None of the intervening forgetful functors is an equivalence, since the next partial operation can be chosen differently on a fixed point. Starting at ${\mathcal{C}}_0$ takes exactly $n$ steps:

An object $E$ in a finite-product category is exponentiable when $-\times E$ has a right adjoint $(-{)}^E$. The terminal object is exponentiable. If $E$ and $F$ are exponentiable, thenhas the composite of their right adjoints as a right adjoint. Hence the product of exponentiable objects is exponentiable, including the empty product.

Suppose $0$ is both initial and terminal. Since $-\times E$ is a left adjoint for exponentiable $E$, it preserves the initial object, so $0\times E\cong 0$. Since $0$ is terminal, $0\times E\cong E$. Therefore the zero object is the only exponentiable object in a pointed category.

Let $G=\mathbf{Top}(X,S)$ for a T0 space $X$ and the Sierpiński space $S$. The evaluation mapis injective because characteristic maps of open sets distinguish distinct points. Every open $U\subseteq X$ equals $g_U^{-1}(1)$ for its characteristic map $g_U:X\to S$, so the subspace topology induced by $e$ is the original topology. This is the Embedding of a T0 space into a power of the Sierpiński space.

A subspace inclusion between $T_0$ spaces is a regular monomorphism, hence an equalizer. Embedding its codomain into another power of $S$ and composing the parallel pair preserves the equalizer because the embedding is monic. Consequentlyis an equalizer for suitable sets $G,H$.

If $E$ is exponentiable, ${\mathbf{Top}}_0(-\times E,S)$ is represented by $S^E$. Conversely, suppose it is represented by $R$. Products giveExpress any $T_0$ space $X$ as the displayed equalizer $S^G\rightrightarrows S^H$ and take the corresponding equalizer $R^G\rightrightarrows R^H$. Since hom-functors preserve limits, this equalizer represents ${\mathbf{Top}}_0(-\times E,X)$. Thus $-\times E$ has a right adjoint on every target, proving the Exponentiability criterion in the category of T0 spaces.

For a locally small category $\mathcal{C}$, the Yoneda lemma states thatnaturally in both $A\in \mathcal{C}$ and $F:{\mathcal{C}}^{\mathrm{op}}\to \mathbf{Set}$. Taking $F=\mathcal{C}(-,B)$ givesso the Yoneda embedding is full and faithful.

For small $\mathcal{C}$, the presheaf category has pointwise finite limits and colimits, exponentialand a subobject classifier whose elements at $C$ are sieves on $C$. Hence it is a presheaf topos.

If $\mathcal{C}$ has finite limits, the Yoneda embedding preserves them: maps into a limiting object are the corresponding limits of hom-sets. Its essential image is therefore a full subcategory of the presheaf topos closed under finite limits. Since Yoneda is full and faithful, this proves the assertion up to equivalence.

Suppose the small category $\mathcal{C}$ is Cartesian closed. The Yoneda embedding preserves finite products. For $A,B,X\in \mathcal{C}$, the Yoneda lemma and the exponential object adjunction giveThe bijections are natural in $X$, soThus the essential image of $\mathcal{C}$ in its presheaf topos is full and closed under finite products and exponentials.

Assume $\mathcal{C}$ has finite products and every idempotent morphism splits. For a representable presheaf $yA$, the exponential formula givesThus exponentiation by $yA$ is precomposition with $-\times A$. Precomposition has a Right Kan extension as right adjoint, so every representable presheaf is a tiny object.

Conversely, let $P$ be tiny. Then $(-{)}^P$ is a left adjoint and preserves all small colimits. Since $\mathcal{C}$ has a terminal object $1$, the terminal presheaf is $y1$, and evaluation at $1$ preserves colimits. Thereforepreserves all small colimits as a functor of $F$. By the result supplied in the question, splitting idempotents implies that $P$ is representable. Hence the representable presheaves are the tiny objects of an idempotent-complete finite-product category, and Yoneda identifies $\mathcal{C}$ with the full subcategory of tiny objects of its presheaf topos.