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

Write $h_A=\mathcal{C}(A,-)$. The covariant Yoneda lemma gives the natural bijectionwhose inverse sends $x\in F(A)$ to the natural transformation with component $u:A\to B\mapsto F(u)(x)$. This also identifies the two variables' naturality.

To prove that $h_A$ is a projective object in a category, let $p:G\twoheadrightarrow F$ be an epimorphism in the functor category and $\alpha :h_A\to F$. By pointwise epimorphism in a functor category, lift ${\alpha }_A(1_A)$ through the surjective function $p_A$. The Yoneda lemma turns this lift into $\beta :h_A\to G$ with $p\beta =\alpha$.

For a small category, the set of pairs $(A,x)$ with $x\in F(A)$ indexes the canonical mapIt is natural, and every $y\in F(B)$ is the image of $(B,y,1_B)$. Thus it is an epimorphism, establishing the projective cover of a set-valued functor by representables construction. Here cover means a projective presentation; no minimality is asserted.

For the equivalence's first step, if $f:B\to D$ is a monomorphism, then $h_A(f)$, the map $u\mapsto fu$, is injective for every $A$. Hence every representable functor is a monofunctor. Conversely, injectivity of every $h_A(f)$ is exactly left cancellation against every $u,v:A\to B$, so it implies that $f$ is a monomorphism. Therefore

Assume (b). A coproduct in a category of monofunctors in $[\mathcal{C},\mathbf{Set}]$ is again a monofunctor: at an object it is the disjoint union of the values, and every arrow acts within the same summand by an injective function. Distinct summands cannot become identified, and injectivity within a summand follows from its monofunctor property.

Apply this to the coproduct of representable functors constructed in part (a). Its canonical map to $F$ is a pointwise epimorphism in a functor category. Thus every $F$ is an epimorphic image of a monofunctor, proving

Assume (c), and take an epimorphism $p:M\twoheadrightarrow h_A$ with $M$ a monofunctor. Since $h_A$ is a projective object in a category, there is a natural transformation $s:h_A\to M$ with $ps=1_{h_A}$. A retract in a category of a monofunctor is a monofunctor: if $h_A(f)(u)=h_A(f)(v)$, then naturality of $s$ gives $M(f)s(u)=M(f)s(v)$, injectivity of $M(f)$ gives $s(u)=s(v)$, and applying $p$ gives $u=v$. Thus (c) implies (b), completing

The stronger assertion that every set-valued functor is a monofunctor holds exactly when $\mathcal{C}$ is a groupoid. Sufficiency follows because a functor preserves inverses, so sends every arrow to a bijection.

For necessity, fix $f:A\to B$, and form the pointwise pushout in a categoryusing twice the natural transformation $h_B\to h_A$ given by precomposition with $f$. At an object $X$, $P(X)$ consists of two copies of $\mathcal{C}(A,X)$, with the two copies of $kf$ identified for every $k:B\to X$. No different underlying elements are identified: each generating relation simply joins the two copies of one element. In $P(B)$, the two copies of $f$ coincide, since $f=1_{B}f$. Hence $P(f)$ sends the two copies of $1_A$ in $P(A)$ to the same element. If $P$ is a monofunctor, those copies of $1_A$ coincide. The description of the pushout implies $rf=1_A$ for some $r:B\to A$. Thus every morphism is a split monomorphism.

Apply the same conclusion to $r$: there is $t:A\to B$ with $tr=1_B$. Then $t=trf=f$, and so $fr=1_B$ as well. Every arrow is invertible, proving

Let ${\lambda }_A:GF(A)\to Z$ be the given cocone under a diagram. For $B\in \mathcal{D}$, choose an object $(A,u:B\to FA)$ of the comma category $(B\downarrow F)$ and defineSuch a choice exists because $F$ is a final functor. If $a:A\to A^{\prime }$ gives a morphism $(A,u)\to (A^{\prime },u^{\prime })$, so $F(a)u=u^{\prime }$, the cocone relation givesThe connected category condition makes the result independent of the choice along any zigzag.

For $v:B\to B^{\prime }$, choose $(A,u:B^{\prime }\to FA)$; then $(A,uv)$ is available for $B$, giving ${\bar{\lambda }}_B={\bar{\lambda }}_{B^{\prime }}G(v)$. Thus the maps form a cocone under a diagram on $G$. Choosing $(A,1_{FA})$ shows that restriction recovers ${\lambda }_A$. Any extension must satisfy ${\bar{\lambda }}_B={\bar{\lambda }}_{FA}G(u)={\lambda }_{A}G(u)$, proving uniqueness. This is cocone extension along a final functor.

If $GF$ has a colimit, extend its universal cocone in this way. Every cocone on $G$ restricts to one on $GF$, factors uniquely through that colimit, and then agrees with its extension by uniqueness. Hence the same vertex is a colimit of $G$. In particular,and existence of all $\mathcal{C}$-shaped colimits in $\mathcal{E}$ implies existence of all $\mathcal{D}$-shaped colimits.

Use the square's notation $HF=KG$. For $E\in \mathcal{E}$, choose $(C,u:E\to GC)$ in the nonempty connected category $(E\downarrow G)$. Lift $Ku:KE\to HFC$ through the discrete fibration $H$, obtaining the uniquely determined arrowDefine $LE=D_u$. If $a:C\to C^{\prime }$ satisfies $Gau=u^{\prime }$, then $Fa\tilde{u}$ is a lift of $K{u}^{\prime }$ with codomain $F{C}^{\prime }$. Uniqueness makes it exactly ${\tilde{u}}^{\prime }$, including equality of its domain. Connectedness of the comma category therefore makes $LE$ independent of the chosen object, with strict equality rather than merely an isomorphism.

For $v:E\to E^{\prime }$, choose $(C,u:E^{\prime }\to GC)$ and lift $Kv:KE\to K{E}^{\prime }=HL{E}^{\prime }$ with codomain $L{E}^{\prime }$. Write this lift as $w:D\to L{E}^{\prime }$. Its composite with $\tilde{u}$ is the lift of $K(uv)$ to $FC$, so its domain is $LE$. Set $Lv=w$. The lift of an identity is an identity, and the composite of two lifts is the lift of the composite with the specified codomain. Thus $L$ is a functor, and $HL=K$.

At $E=GC$, choose $(C,1_{GC})$; its lift is $1_{FC}$, giving $LGC=FC$. For $a:C\to C^{\prime }$, the unique lift of $KGa=HFa$ with codomain $F{C}^{\prime }$ is $Fa$, giving $LG=F$ on arrows as well. Finally, any other filler $L^{\prime }$ must send $u$ to the same lift of $Ku$ with codomain $FC$, so $L^{\prime }E=LE$; it must also send $v$ to the unique lift of $Kv$ with codomain $L{E}^{\prime }$. This proves orthogonality of final functors and discrete fibrations:

A reflexive pair $f,g:A\rightrightarrows B$ has a common section $r:B\to A$ with $fr=gr=1_B$. Form the pushout in a category of $f$ and $g$, and write its two maps from $B$ as $j_1,j_2$. Its relation $j_{1}f=j_{2}g$, composed with $r$, gives $j_1=j_2=q$. Thus $qf=qg$. Any $h:B\to C$ with $hf=hg$ gives the compatible pair $(h,h)$ for this pushout and therefore factors uniquely through $q$. This proves the coequalizer of a reflexive pair from a pushout construction.

There is a genuine transcription difference: the original PDF says finite products in the finite-colimit assertion, while the TeX says finite coproducts. The PDF assertion is false with products. Even retaining a pushout-existence assumption, the full subcategory of the Category of sets on nonempty sets has finite products, pushouts, and all coequalizers, but no initial object, hence no empty colimit. Regard the poset with elements $0,a,b,u_0,u_1,\dots$, orderand incomparable $a,b$ as a category. It has finite meets and top $u_0$, hence finite products in a category. Every reflexive pair in a poset is an equal pair and has its identity as a coequalizer. But $a,b$ have no least upper bound, so they have no coproduct in a category.

For the corrected construction using finite coproducts, let $D:\mathcal{J}\to \mathcal{C}$ be a finite diagram in a category. PutDefine $s,t:Y\rightrightarrows X$ on the summand indexed by $a:i\to j$ as ${\nu }_i$ and ${\nu }_{j}D(a)$. Maps $h:X\to Z$ with $hs=ht$ are exactly cocone under a diagram data on $D$. Hence their universal coequalizer is its colimit. Replace $s,t$ by the reflexive pairwhose common section is the second injection and whose coequalizer is unchanged. This proves construction of finite colimits from coproducts and reflexive coequalizers, including the empty diagram via the empty coproduct:

Let $r:B\to A$ split the reflexive pair $f,g$. Fix $C$, and take objects $u:C\to B$ and arrows $a:C\to A$ with source $fa$ and target $ga$. Since $\mathcal{C}$ is an additive category, its hom-sets are abelian groups, and composition is additive.

The identity at $u$ is $ru$. For $a:u\to v$ and $b:v\to w$, defineIts source is $fa-v+fb=u-v+v=u$ and its target is $ga-v+gb=v-v+w=w$. The two identity laws follow from $a-rv+rv=a$ and $ru-ru+a=a$. For $c:w\to x$, both parenthesizations of the triple composite are $a-rv+b-rw+c$, so composition is associative.

Define the inverse byIts source is $u+v-u=v$ and its target is $u+v-v=u$. Moreover $a^{-1}\star a=ru$ and $a\star a^{-1}=rv$. Thus these data form a groupoid, proving the represented form of reflexive pair in an additive category is an internal groupoid:

Use the category of commutative monoids, which is a semi-additive category: hom-sets have pointwise addition, composition is additive in each variable, and finite cartesian products are also coproducts. Explicitly, maps $M_i\to N$ extend from the coordinate injections by $(m_i)\mapsto {\sum }_i{f}_i(m_i)$.

Take the submonoidwith coordinatewise addition, and the two projections $f(m,n)=m$, $g(m,n)=n$. The homomorphism $r(m)=(m,m)$ satisfies $fr=gr=1_B$, so this is a reflexive pair. For $C=\mathbb{N}$, evaluation at $1$ identifies $\mathcal{C}(C,B)$ with $B$ and $\mathcal{C}(C,A)$ with $A$.

The element $(1,2)$ gives an arrow from $1$ to $2$ in the prescribed graph. An inverse would require an element $(2,1)$ of $A$, which does not exist. Therefore no groupoid structure with these source and target maps is possible, regardless of the proposed composition rule:

A monad is an endofunctor $T:\mathcal{C}\to \mathcal{C}$ with natural transformations $\eta :1_{\mathcal{C}}\to T$ and $\mu :T^2\to T$ satisfyingIts Kleisli category has the same objects as $\mathcal{C}$, with ${\mathcal{C}}_T(A,B)=\mathcal{C}(A,TB)$, identity ${\eta }_A$, and compositeThe unit laws follow from naturality of $\eta$ and the two monad unit laws. For $h:C\to TD$, the two triple composites reduce, using naturality of $\mu$, tothey agree by the monad associativity law. Thus this is a category.

Define the free functor into a Kleisli category $J$ and the right-hand functor $U$ byThe identity and composition formulas for $J$ areFor $U$, $U({\eta }_A)={\mu }_{A}T{\eta }_A=1_{TA}$, andwhere the last step is naturality of $\mu$. Hence both mappings are functors. The hom-set identity ${\mathcal{C}}_T(JA,B)=\mathcal{C}(A,UB)$ gives the adjunction $J⊣U$. Its unit is $\eta$, and its counit at $B$ is the Kleisli arrow represented by $1_{TB}:TB\to TB$. Applying $U$ to that counit gives ${\mu }_B$, so the induced monad is the specified one.

For any $L⊣R:\mathcal{D}\to \mathcal{C}$ inducing this same monad, with counit $\epsilon$, define the Kleisli comparison functorThe triangular identities give $K({\eta }_A)=1_{LA}$, and naturality of the counit together with $\mu =R\epsilon L$ gives $K(g\star f)=K(g)K(f)$. Explicitly, naturality moves ${\epsilon }_{LB}$ past $L(g)$, then moves the resulting counit past ${\epsilon }_{LC}$, reducing the composite to ${\epsilon }_{LC}L({\mu }_{C}T(g)f)$. Thus $K$ is a functor, with $KJ=L$ and $RK=U$, and it sends the Kleisli counit to ${\epsilon }_L$.

An adjunction morphism here is required to commute with the left and right adjoints and preserve their adjunction structure. Such a morphism must have the above object map; every Kleisli arrow $f$ factors as its counit after $J(f)$, so its arrow map is forced as well. This proves initiality of the Kleisli adjunction:

For $L⊣R$ inducing $T$, the Kleisli comparison functor is always full and faithful, since the adjunction givesTherefore it is part of an equivalence of categories if and only if every object of $\mathcal{D}$ is isomorphic to $LA$ for some $A$.

For an idempotent monad, multiplication is invertible. The unit laws imply $T\eta =\eta T={\mu }^{-1}$. If $(A,a)$ is an algebra for a monad, then $a{\eta }_A=1_A$, while naturality of $\eta$ givesThus $a:TA\to A$ is an isomorphism with inverse ${\eta }_A$. The algebra law $a{\mu }_A=aT(a)$ says that $a$ is a morphism of algebras for a monad from the free algebra $(TA,{\mu }_A)$ to $(A,a)$, so every object of the Eilenberg-Moore category is isomorphic to a free algebra. The criterion above yields

Use $\mathbb{N}=\{0,1,\dots \}$, as required by the formula at zero, and composition of functions as multiplication in $M$. The displayed $T$ preserves identities, and for $n>0$,both sides send zero to zero. Thus $T$ is a functor on the one-object category.

For the shift monad on order-preserving maps of natural numbers, setThese are order-preserving functions. The equations $Tf\eta =\eta f$ and $\mu T^{2}f=Tf\mu$ hold pointwise, giving the required natural transformations. For the second equation, both sides are zero at $n=0,1$, and are $f(n-2)+1$ for $n\ge 2$. The two unit laws are $\mu \eta =\mu T\eta =1$. Associativity is checked byConsequently these maps define a monad. It is not an idempotent monad, since $\mu (0)=\mu (1)$, so $\mu$ cannot be invertible.

An algebra for a monad is a map $a\in M$ with $a\eta =1$ and $aTa=a\mu$. The first equation forces $a(n+1)=n$; monotonicity then forces $a(0)=0$. Thus $a=\mu$, which satisfies the second equation by the monad associativity law. The Eilenberg-Moore category therefore has exactly one object. Its endomorphisms $h$ satisfy $h\mu =\mu Th$, and this equation holds precisely when $h(0)=0$: evaluate at zero for necessity, and at $n>0$ both sides equal $h(n-1)$.

The Kleisli comparison functor takes its only object to this only algebra and sends $f\in M$ toIt is a bijection from the Kleisli arrows to the algebra endomorphisms, with inverse $h\mapsto (n\mapsto h(n+1))$. It preserves identities and composition by the comparison construction; directly, $K(\eta )=1$ and $K(g\star f)=K(g)K(f)$. Bijectivity on objects and arrows makes it an isomorphism of categories:

A Cartesian closed category has finite products in a category and, for every $F$, an exponential object $G^F$ characterized naturally byIn $[\mathcal{C},\mathbf{Set}]$, finite products and the terminal functor are computed pointwise. With $h_B=\mathcal{C}(B,-)$, defineThis is a set because $\mathcal{C}$ is a small category. For $v:B\to B^{\prime }$, precomposition $h_{B^{\prime }}\to h_B$ induces $(G^F)(v)$ by precomposition of natural transformations, making $G^F$ a covariant functor.

Given $\alpha :K\times F\to G$, define its curry $\hat{\alpha }:K\to G^F$ byFor $a:C\to C^{\prime }$, naturality of $\alpha$ gives $G(a){\alpha }_C(K(u)y,x)={\alpha }_{C^{\prime }}(K(au)y,F(a)x)$, proving that this is a natural transformation $h_B\times F\to G$. The same formula with $u$ precomposed proves naturality of $\hat{\alpha }$ in $B$.

Conversely, from $\beta :K\to G^F$ defineNaturality of $\beta$ and its values proves naturality of $\alpha$. Currying this result recovers $\beta$, since ${\beta }_C(K(u)y)=(G^F)(u)({\beta }_B(y))$; uncurrying a curry recovers $\alpha$ by setting $u=1_B$. These mutually inverse constructions are natural in $K,G$, giving the adjunction required for an exponential object. Therefore

For a tiny object $A$, the exponential functor $E_A=(-{)}^A$ has a right adjoint, say $R_A$. The defining exponential adjunction gives the natural isomorphismsince $(X^B{)}^A\cong X^{A\times B}$. If $A,B$ are tiny objects, the composite on the right is a left adjoint with right adjoint $R_B{R}_A$. Thus $A\times B$ is tiny. The terminal object is tiny because exponentiation by it is naturally the identity, which is its own right adjoint. Induction, including this empty-product case, proves tiny objects are closed under finite products:

Fix $A$, and let $S(B)=B⨿A$ be the functor obtained from the chosen binary coproduct in a category construction. Its arrow map is $S(v)=v⨿1_A$. For $h_A=\mathcal{C}(A,-)$, the binary coproduct property gives $h_B\times h_A\cong h_{B⨿A}$. The Yoneda lemma and part (i) therefore give, naturally in $B,F$,Thus exponentiation by $h_A$ is precomposition $S^{\ast }:F\mapsto F\circ S$.

This precomposition has a right adjoint given by Right Kan extension. Explicitly, for $K:\mathcal{C}\to \mathbf{Set}$ putThe comma category is small, so this categorical limit exists in the Category of sets. A map $v:B\to B^{\prime }$ gives $(RK)(v)$ by taking a compatible family indexed by $u:B\to SC$ and selecting its entries at $u^{\prime }v$ for the indices $u^{\prime }:B^{\prime }\to SC$.

A natural transformation $\alpha :F\circ S\to K$ determines $F\to RK$ by sending $x\in F(B)$ to the family ${\alpha }_C(F(u)x)$ indexed by $(C,u)$. Conversely, a map $F\to RK$ determines $F(SC)\to K(C)$ by projecting to the index $(C,1_{SC})$. Naturality and the limit's compatibility relations make these constructions inverse. Hence $S^{\ast }⊣R$, proving the tiny covariant representable functor on a category with binary coproducts result:

Let $P$ be a tiny object of $[\mathcal{C},\mathbf{Set}]$, and let $0$ be the initial object of $\mathcal{C}$. The representable functor $h_0=\mathcal{C}(0,-)$ is the terminal functor, since each of its values is a singleton. The exponential adjunction and the Yoneda lemma giveSince $P$ is tiny, $E_P:F\mapsto F^P$ is itself a left adjoint, so preserves all colimits. Evaluation at $0$ also preserves colimits, because they are pointwise in a set-valued functor category. Therefore $\mathrm{Nat}(P,-)$ preserves the coproduct construction.

It also preserves epimorphisms. Indeed, every such epimorphism is a pointwise epimorphism in a functor category, hence the coequalizer of its kernel pair, as can be checked pointwise in sets. A left adjoint preserves that coequalizer and therefore sends it to a regular epimorphism, which is an epimorphism; evaluation at zero preserves surjectivity. Thus $P$ is an irreducible projective in a set-valued functor category.

A Cauchy-complete category is one in which every idempotent morphism splits. By the characterization allowed in the question, irreducible projectives are representable functors for such an indexing category. Applying it to $P$ proves the tiny covariant functor on a Cauchy-complete category with an initial object is representable conclusion:

In a semi-additive category, hom-sets are commutative monoids and composition is additive in both variables. Write $S={\coprod }_i{A}_i$, $P={\prod }_i{A}_i$, with injections ${\nu }_i$ and projections ${\pi }_i$. The canonical $c:S\to P$ has ${\pi }_{i}c{\nu }_j=1_{A_i}$ when $i=j$ and zero otherwise. DefineBilinearity givesThe universal properties of the product in a category and coproduct in a category imply $cd=1_P$ and $dc=1_S$. For the empty family, $S$ is initial and $P$ terminal. Their endomorphisms are necessarily the identity and the zero morphism; the zero map $P\to S$ therefore also gives inverse composites. Thus the comparison is an isomorphism for every finite family, giving a biproduct:

Use countably many copies of $A$, and let $c:S={\coprod }_{i\ge 1}A\to P={\prod }_{i\ge 1}A$ be the assumed isomorphism. Write $p_i={\pi }_{i}c:S\to A$, let $\delta :A\to P$ be the diagonal with every component $1_A$, and put $q=c^{-1}\delta$. Thus $p_{i}q=1_A$ for every $i$. Let $s:S\to S$ shift the injections, $s{\nu }_i={\nu }_{i+1}$, and let $\sigma :S\to A$ be the fold map, $\sigma {\nu }_i=1_A$.

The coordinate relations give $p_{1}s=0$ and $p_{i+1}s=p_i$, while $p_1{\nu }_1=1_A$ and $p_{i+1}{\nu }_1=0$. Therefore $q$ and ${\nu }_1+sq$ have identical $p_i$-coordinates. Since $c$ is invertible, these coordinates jointly distinguish arrows into $S$, soThe coproduct property gives $\sigma s=\sigma$, because both have value $1_A$ on each injection. Consequently $z=\sigma q$ satisfiesThis proves the absorbing-endomorphism assertion without assuming an infinite addition operation on hom-sets.

If the category is an additive category, each hom-set is an abelian group, so cancellation gives $1_A=0$. Any arrow $f:A\to B$ is then $f{1}_A=f0=0$. Every hom-set has exactly one arrow, and every object is isomorphic to the zero object. This is countable biproducts in an additive category force triviality:

In the category of complete join-semilattices, define addition of arrows pointwise byand let the zero arrow be the constant-bottom map. These form commutative monoids. Pointwise join of join-preserving maps again preserves all joins, including the empty join, and composition is additive in each variable. Thus the category has the required semi-additive enrichment.

For an arbitrary set-indexed family $(A_i)$, the product poset $P={\prod }_i{A}_i$, with coordinatewise joins, is the product in a category. Define ${\nu }_i:A_i\to P$ by putting an element in coordinate $i$ and bottom in all others. Given join-preserving $f_i:A_i\to B$, defineThis preserves arbitrary joins by interchanging the two joins, and $h{\nu }_i=f_i$. It is unique because every tuple is ${\bigvee }_i{\nu }_i(a_i)$. Therefore $P$ is also the coproduct in a category with these injections, and its canonical coproduct-to-product map is the identity. This proves the biproducts of complete join-semilattices property, even for arbitrary set-indexed families, and in particular makes this a semi-additive category with the hypotheses of part (ii).

The two-element chain has distinct identity and constant-bottom endomorphisms, so the category is not equivalent to $1$. Its addition is idempotent rather than cancellative; for example $1_A+1_A=1_A$ itself supplies an absorbing endomorphism. Hence