Categories by Kan extension

David I. Spivak · 2025

Read Categories by Kan extension by David I. Spivak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-21974.txt.

Introduction

David Spivak wrote a 2025 math paper on a fresh way to build categories. A category can be matched, up to renaming, with a kind of structured machine on sets. One standard process, called a Kan extension, always yields such a machine when a map is extended along itself.

Spivak gives several broad ways to grow new categories from old ones by that route. Known builds, such as Lawvere theories and product completions of small categories, fall out as cases. The classic simplex index category does as well. He also treats a less known build, the selection category, in depth, and shows cases where the machines that arise are not of the simple polynomial kind.

Catalog record

CREATORDavid I. Spivak
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE113 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-21974

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Categories by Kan extension David I. Spivak Abstract Categories can be identified—up to isomorphism—with polynomial comonads on 𝐒𝐞𝐭 \mathbf{Set} . The left Kan extension of a functor along itself is always a comonad—called the density comonad—so it defines a category when its carrier is polynomial. We provide a number of generalizations of this to produce new categories from old, as well as from distributive laws of monads over comonads. For example, all Lawvere theories, all product completions of small categories, and the simplicial indexing category 𝚫 op \mathbf{\Delta}^{\textnormal{op}} arise in this way. Another, seemingly much less well-known, example constructs a so-called selection category from a polynomial comonad in a way that’s somehow dual to the construction of a Lawvere theory category from a monad; we’ll discuss this in more detail. Along the way, we will see various constructions of non-polynomial comonads as well. \settrims 0pt0pt \settypeblocksize *35.1pc* \setlrmargins **1 \setulmarginsandblock .98in.98in* \setheadfoot \onelineskip 2 \onelineskip \setheaderspaces *1.5 \onelineskip * \checkandfixthelayout \setlistdepth 6 \setsecnumdepth section \settocdepth section keywords Kan extension, parametric right adjoint (pra-)functor, comonad, density comonad, polynomial comonad, selection category. Chapter 1 Introduction In this paper we provide new methods for constructing categories from other data, using left Kan extensions [ Kan58 , Mac98 ] . Of course, left Kan extensions (of functors along functors) are functors ; in what sense could they also be categories ? A recent result of Ahman and Uustalu [ AU16 ] allows us to make the connection by showing that categories \mathcal{C} (up to isomorphism) can be identified with comonads on \mathbf{Set} for which the underlying functor k_{\mathcal{C}}\colon\mathbf{Set}\to\mathbf{Set} is polynomial (preserves all connected limits). 1 1 1 In a mathoverflow post Simon Henry and Kevin Carlson explained that comonads whose underlying functor \mathbf{Set}\to\mathbf{Set} preserves finite connected limits can be identified with ionads : Grothendieck toposes equipped with a separating set of points [ Gar11 ] . Aaron David Fairbanks gave examples of still more general comonads on \mathbf{Set} . Chapters 2 and 4 give constructions for such comonads. The purpose of this paper is to give a variety of ways to produce comonads using Kan extensions. We denote a left Kan extension of p along q by \begin{bmatrix}{\vphantom{f}q}\\ {\vphantom{f}p}\end{bmatrix}\coloneqq\mathrm{Lan}_{q}(p) . 2 2 2 This paper uses a large line-spread in order to typographically accommodate the \begin{bmatrix}{\vphantom{f}-}\\ {\vphantom{f}-}\end{bmatrix} notation. It is well-known that the left Kan extension \begin{bmatrix}{\vphantom{f}p}\\ {\vphantom{f}p}\end{bmatrix} of a functor p\colon\mathcal{C}\to\mathcal{D} along itself, when it exists, always carries a comonad structure. We will generalize this by showing that if \mathcal{C} and \mathcal{D} are accessible categories, e.g. copresheaf categories, then for any accessible monad t , accessible comonad k , and distributive law t\circ k\to k\circ t , the left Kan extension \begin{bmatrix}{\vphantom{f}p\circ t}\\ {\vphantom{f}p\circ k}\end{bmatrix} exists and has a comonad structure. We will see in Theorem 4.3 that—with no further assumptions on t —when p and k are polynomial functors, this left Kan extension comonad, so it can be identified with a category. We offer several examples. It is not too surprising that every category \mathcal{C} arises in this way—as we will see in Example 0.18 —essentially because the functor U_{\mathcal{C}}\colon\mathcal{C}\textnormal{-}\mathbf{Set}\to\mathbf{Set} given by U_{\mathcal{C}}(X)\coloneq\sum_{c:\ob\mathcal{C}}X(c)) is comonadic {\lx@inpgf@ignorespaces\mathcal{C}\textnormal{-}\mathbf{Set}} {\lx@inpgf@ignorespaces\mathbf{Set}} {\lx@inpgf@ignorespaces\mathbf{Set}} \scriptstyle{\lx@inpgf@ignorespaces U_{\mathcal{C}}} \scriptstyle{\lx@inpgf@ignorespaces U_{\mathcal{C}}} \scriptstyle{\lx@inpgf@ignorespaces k_{\mathcal{C}}} In other words, \mathcal{C} corresponds to the “density” comonad associated to U_{\mathcal{C}} . But it is more interesting to “get more out than you put in,” i.e. to find interesting categories arising from much less data. For example, we will see that • the simplicial indexing category, \mathbf{\Delta}^{\textnormal{op}} arises as the left Kan extension \begin{bmatrix}{\vphantom{f}\textit{paths}\;\circ\;\textit{frcat}}\\ {\vphantom{f}\textit{paths}}\end{bmatrix} of one functor from the category of graphs to \mathbf{Set} along another ( Proposition 0.43 ), • the walking arrow \bullet\to\bullet arises as the left Kan extension \begin{bmatrix}{\vphantom{f}{\mathcal{y}}+1}\\ {\vphantom{f}{\mathcal{y}}+1}\end{bmatrix} of the maybe monad along itself ( Example 0.42 ), and • the free product completion of a category \mathcal{C} arises as the left Kan extension \begin{bmatrix}{\vphantom{f}\textit{list}}\\ {\vphantom{f}\textit{list}\circ k_{\mathcal{C}}}\end{bmatrix} ( Proposition 0.36 ). In particular \begin{bmatrix}{\vphantom{f}\textit{list}}\\ {\vphantom{f}\textit{list}}\end{bmatrix} corresponds to the category \mathbf{FinSet}^{\textnormal{op}} . It is well-known that S -sorted finitary Lawvere theories \mathcal{T} [ Law63 ] have associated finitary monads t on S\textnormal{-}\mathbf{Set} . Namely, the finite product category associated to t is the full subcategory of the opposite of the Kleisli category S\textnormal{-}\mathbf{Set}_{t} spanned by the finite S -sets. The previous sentence is a mouthful, but we can recover this category more concisely again using a generalization of the density comonad: \mathcal{T}\cong\begin{bmatrix}{\vphantom{f}\textit{list}\,\circ\,t}\\ {\vphantom{f}\textit{list}}\end{bmatrix} ; see Example 0.41 . Categories of the form \begin{bmatrix}{\vphantom{f}p}\\ {\vphantom{f}p\circ k_{\mathcal{C}}}\end{bmatrix} seem to be new, other than being discussed in a blog post by the author. There they were called selection categories , referring to their proposed use in modeling natural selection. They arise from Theorem 4.1 , which says that in a fairly general setting, the functor \begin{bmatrix}{\vphantom{f}p}\\ {\vphantom{f}p\circ-}\end{bmatrix} is colax monoidal: \begin{bmatrix}{\vphantom{f}p}\\ {\vphantom{f}p}\end{bmatrix}\Rightarrow\mathrm{id}_{\mathcal{C}}.\qquad\textnormal{and}\qquad\begin{bmatrix}{\vphantom{f}p}\\ {\vphantom{f}p\circ q\circ r}\end{bmatrix}\Rightarrow\begin{bmatrix}{\vphantom{f}p}\\ {\vphantom{f}p\circ q}\end{bmatrix}\circ\begin{bmatrix}{\vphantom{f}p}\\ {\vphantom{f}p\circ r}\end{bmatrix}. In Theorems 6.1 and 0.55 , we prove that the selection category construction \begin{bmatrix}{\vphantom{f}p}\\ {\vphantom{f}p\circ-}\end{bmatrix} comprises a functor \mathbf{Cat}\to\mathbb{P}\mathbf{rof}_{\,}\textnormal{-}\mathbf{Cat} , from the category of small categories to that of \mathbb{P}\mathbf{rof} -enriched categories, and that this functor respects the bijective-on-objects, fully-faithful factorization system. Notation and Terminology 1.1 . We may denote composition A\xrightarrow{\textnormal{$f$}}B\xrightarrow{\textnormal{$g$}}C by f\mathbin{\fatsemi}g or by g\circ f . We denote the identity map (e.g. on an object A ) by A\xrightarrow{\textnormal{$\mathrm{id}_{A}$}}A . We use 1 to denote a terminal object in any category that has one. Given a set I and a I -shaped diagram A\colon I\to\mathcal{S} , we denote the coproduct—when it exists—by \sum_{i:I}A_{i} . As here, we sometimes write A_{i} in place of A(i) . For any small category \mathcal{C} and object c:\ob\mathcal{C} , let \mathcal{C}[c]\coloneqq\sum_{c^{\prime}:\ob\mathcal{C}}\mathcal{C}(c,c^{\prime}) denote the set of all \mathcal{C} -morphisms emanating from c . If I\colon\mathcal{C}\to\mathbf{Set} is any functor, we denote its category of elements by \el_{\mathcal{C}}I . We denote by \mathcal{C}\textnormal{-}\mathbf{Set} the category of \mathcal{C} -copresheaves, i.e. of functors \mathcal{C}\to\mathbf{Set} and natural transformations between them. We denote the 1-category of small categories and functors by \mathbf{Cat} ; we denote by \mathbb{C}\mathbf{at} the 2-category that also includes natural transformations. We denote by \mathbb{L}\mathbf{Adj}\subseteq\mathbb{C}\mathbf{at} its wide and locally-full subcategory consisting of small categories, left adjoint functors, and natural transformations between left adjoints. We denote by \mathbb{C}\mathbf{at}_{\mathbf{A}}\subseteq\mathbb{C}\mathbf{at} the locally-full subcategory consisting of accessible categories, accessible functors, and all natural transformations. Whenever we speak of an accessible functor, we will implicitly assume it is between accessible categories. Given an accessible category \mathcal{C} , we write \mathbf{End}(\mathcal{C}) for the category of accessible endofunctors \mathcal{C}\to\mathcal{C} ; it comes equipped with a monoidal structure (\mathrm{id}_{\mathcal{C}},\circ) . We denote the categories of accessible monads and comonads on \mathcal{C} by \mathbf{Mnd}(\mathcal{C}) and \mathbf{Cmd}(\mathcal{C}) respectively. Given a set A , we denote the endofunctor it represents by {\mathcal{y}}^{A}\coloneqq\mathbf{Set}(A,-)\colon\mathbf{Set}\to\mathbf{Set}. We may write 1 for {\mathcal{y}}^{0} and {\mathcal{y}} for {\mathcal{y}}^{1} ; note that 1 is terminal and that {\mathcal{y}} is the identity functor and the unit for the (\circ )-monoidal product on \mathbf{End}(\mathbf{Set}) . When a map is unique up to unique isomorphism, we may refer to it using the definite article “the”, rather than “a”. Chapter 2 Left Kan extensions This section is probably mostly review for experts, though we have not found all the material written elsewhere; see [ Kel82 ] , [ Di 20 , Appendix A] .

Read the complete text