Blog / Technical reports
Discrete vs. filtered accessibility and presentability
Accessible and presentable categories are nice because they make calculating hom sets easy. But not all hom-sets-easily-calculable categories are accessible. In this post we suggest analogous notions, replacing “filtered colimits” with “discrete colimits” (i.e. coproducts), and similarly “compact objects” with “connected objects”. I’ll explain how this sort of accessibility is equally good for calculating.
1 Introduction
The attitude one may want to take regarding accessible categories is that
accessibility is a calculability assumption.
If a category \mathcal{C} is accessible, then knowing the set \mathcal{C}(c,d) of maps between any two objects can be reduced to knowing the sets of maps between simpler objects.
Definition 1 Let \kappa be a regular cardinal. An object c in \mathcal{C} is \kappa-compact if, for any \kappa-filtered category I and I-shaped diagram d\colon I\to\mathcal{C}, the canonical function \mathop{\mathrm{colim}}_i\mathcal{C}(c,d_i)\to\mathcal{C}(c,\mathop{\mathrm{colim}}_id_i) is an isomorphism.
Usually, colimits come out of the first variable as limits \mathcal{C}(\mathop{\mathrm{colim}}c_i,d)=\lim_i\mathcal{C}(c_i,d) and limits come out of the second variable as limits. But when an object c is compact, it makes colimits come out of the second variable as colimits.
Compact objects turn out to always feel small to us: when \kappa=\omega is countably infinite, being \omega-compact is usually called being finitely presentable, or finitary for short. Finitary vector spaces are the finite dimensional ones, finitary groups are the finitely presented ones, finitary sets are the finite ones, finitary graphs are the finite ones, etc. So clearly, being finitary or more generally compact does make us feel like “I can calculate with these.”
Being accessible means that this ability to calculate extends in a controlled way to the whole category.
Definition 2 A category \mathcal{C} is \kappa-accessible if it has \kappa-filtered colimits and there is a set S of \kappa-compact objects in \mathcal{C} for which every object of \mathcal{C} is a \kappa-filtered colimit of objects in S.
A category \mathcal{C} is presentable if it is \kappa-accessible for some \kappa and has all colimits.
The point is that in an accessible category, if you want to know the hom-set \mathcal{C}(c,d), you can realize c and d as each a colimit of compact objects and then have \begin{align*} \mathcal{C}(c,d)&\cong \mathcal{C}(\mathop{\mathrm{colim}}_ic_i,\mathop{\mathrm{colim}}_jd_j)\\&\cong \lim_i\mathcal{C}(c_i,\mathop{\mathrm{colim}}_jd_j)\\&\cong \lim_i\mathop{\mathrm{colim}}_j\mathcal{C}(c_i,d_j), \end{align*} where that last calculation looks complicated—a limit of colimits of hom-sets—but the point is that at least that limit is taken in \mathbf{Set}. So if you understand those mapping-sets between compact objects, then you understand the big mapping-sets.
But what is a filtered diagram? How central is filteredness to this story? Many categories are accessible: every Grothendieck topos is, as is every category of models of an algebraic theory.
However, the category of polynomial functors is not accessible, and there does not appear to be any fix. One can check that no representable \mathcal{y}^X with |X|\geq2 can be \kappa-compact, for any \kappa. 1 But in an accessible category every object is \kappa-compact for some regular \kappa: it is a colimit of a small diagram I of \kappa_i-compact objects, and it becomes compact itself as soon as \kappa surpasses both the size of the diagram and the \kappa_i’s of all its components. Since there is no \kappa for which \mathcal{y}^2 is \kappa-compact, \mathbf{Poly} is not accessible. Darn!
But is it really a problem? The impetus for this blog post is that I’ve met people who heard that \mathbf{Poly} is not accessible and feel like “oof, that’s gonna be complicated to work with...”. And I sat there feeling like “darn! They think \mathbf{Poly} is hard to calculate in, but it’s really not!” I wanted to understand how to explain that \mathbf{Poly} is easy to work with. It turns out that it’s easy in almost the same way.
2 Discrete accessibility
Let’s try to get \mathbf{Poly} to feel as calculable as a presentable category by defining what kind of calculability it has. We begin with the following well-known definition.
Definition 3 An object c in \mathcal{C} is connected if, for any discrete category I and I-shaped diagram d\colon I\to\mathcal{C}, the canonical function \coprod_i\mathcal{C}(c,d_i)\to\mathcal{C}(c,\coprod_id_i) is an isomorphism.
In sets, the only connected object is 1, because 2=1^c+1^c=2^c iff c=1. In graphs, the connected objects are the nonempty connected graphs in the usual sense (every two vertices connected by a zigzag of edges); in topological spaces, the connected objects are the (nonempty) connected spaces in the usual sense; in \mathbf{Poly}, the connected objects are the representables \mathcal{y}^S by the Yoneda lemma \mathbf{Poly}(\mathcal{y}^A,\sum_{i:I}p_i)=(\sum_{i:I}p_i)(A)=\sum_{i:I}\mathbf{Poly}(\mathcal{y}^A,p_i). Conversely if a polynomial has two or more positions then p=\mathcal{y}^A+p' and it has a map to 1+1 that does not factor through either side. Similarly \mathbf{Poly}(0,0)\neq\emptyset, so 0 is not connected. In other words, a polynomial p is connected iff it is representable p=\mathcal{y}^A.
In fact, every graph is a coproduct of its connected pieces and every polynomial is a coproduct of representables.
However, not every topological space is the coproduct of its connected components: consider the rationals \mathbb{Q}. It is not connected; Dedekind observed that every irrational number r gives a continuous map \mathbb{Q}\to 1+1 sending \{q<r\} to one piece and \{q>r\} to the other. And indeed, \mathbb{Q}\cong\{q<r\}+\{q>r\}, but then neither of those is connected either. The only connected subsets of \mathbb{Q} are points, and \mathbb{Q} cannot be written as a coproduct of its points. So there’s a sense in which graphs and \mathbf{Poly} are calculable in a way that topological spaces are not.
This leads to proposing the following definition.
Definition 4 A category \mathcal{C} is discretely accessible if \mathcal{C} has coproducts and every object of \mathcal{C} is a coproduct of connected objects.
A category \mathcal{C} is discretely presentable if it is discretely accessible and has all colimits.
For Grothendieck toposes, this property is known as local connectedness, but in general it does not appear to have a standard name.
Now we find that \mathbf{Poly} is discretely accessible and, since it has all colimits, discretely presentable. This means it’s easy to calculate; in my opinion it is much easier to calculate with than accessible categories. In any discretely accessible category \mathcal{C} we have \begin{align*} \mathcal{C}(c,d)&\cong \mathcal{C}(\sum_ic_i,\sum_jd_j)\\&\cong \prod_i\mathcal{C}(c_i,\sum_jd_j)\\&\cong \prod_i\sum_j\mathcal{C}(c_i,d_j), \end{align*} where that last calculation is a product (rather than filtered limit) of a coproduct (rather than filtered colimit) of hom-sets, taken in \mathbf{Set}. So if you understand the mapping sets between connected objects, then you can understand the big ones too. And for \mathbf{Poly}, the connected objects are the representables, so this whole thing reduces to just products and coproducts of function sets. That is, writing c\coloneqq\sum_{i:I}\mathcal{y}^{C_i} and d\coloneqq\sum_{j:J}\mathcal{y}^{D_j}, we have \mathbf{Poly}(c,d)=\prod_i\sum_j\mathbf{Poly}(\mathcal{y}^{C_i},\mathcal{y}^{D_j})=\prod_i\sum_j\mathbf{Set}(D_j,C_i)=\prod_i\sum_jC_i^{D_j}. So whatever hom-set advantage we get out of (filtered) accessibility, we get the same sort of advantage out of discrete accessibility.
The category of topological spaces is not discretely accessible. In fact, the category of sheaves on \mathbb{Q} is also not discretely accessible. Indeed, for toposes, this notion is already named: a topos is discretely presentable iff it is locally connected, and \mathbf{Sh}(\mathbb{Q}) is known to not be locally connected for the same reason as we discussed earlier regarding \mathbb{Q} itself. But it is (filtered) presentable, so neither notion implies the other.
3 \Phi-accessibility and presentability
We can run the same idea again for any class \Phi of diagram shapes.
Definition 5 An object c in \mathcal{C} is \Phi-compact if, for any category I\in\Phi and I-shaped diagram d\colon I\to\mathcal{C}, the canonical function \mathop{\mathrm{colim}}_i\mathcal{C}(c,d_i)\to\mathcal{C}(c,\mathop{\mathrm{colim}}_id_i) is an isomorphism.
A category \mathcal{C} is \Phi-accessible if \mathcal{C} has \Phi-colimits and there is a set S of \Phi-compact objects in \mathcal{C} such that every object of \mathcal{C} is a \Phi-colimit of objects in S. It is \Phi class-accessible if \mathcal{C} has \Phi-colimits and every object of \mathcal{C} is a \Phi-colimit of \Phi-compact objects.
It is \Phi-presentable (resp. \Phi class-presentable) if it is \Phi-accessible (resp. \Phi class-accessible) and has all small colimits.
When \Phi is the class of \kappa-filtered categories this returns the \kappa-compact objects and the \kappa-accessible categories, and when \Phi is the class of discrete categories it returns the connected objects, and the discretely accessible categories are the \Phi class-accessible ones. When \Phi is the class of all small categories, one might call the \Phi-compact objects tiny or atomic and the \Phi-accessible categories totally accessible. Note that a totally accessible category has all small colimits, so is automatically totally presentable.
It is well-known that a category \mathcal{C} is totally accessible in the above sense, “atomic and cocomplete”, iff it is a presheaf category \mathcal{C}\cong\mathbf{Set}^{\mathcal{D}^\textnormal{op}} for a small category \mathcal{D} (“A Characterization of Locally D-Presentable Categories” 2004 Thm. 2 and Ex. 3(3)). Presheaf categories are both (filtered) accessible and discretely accessible, so this notion is strictly stronger than the previously-considered two.
We collect a few of the examples we’ve mentioned so far, and we add \mathbf{Cat}:
| (filtered) accessible | discretely accessible | totally accessible | |
|---|---|---|---|
| \mathbf{Poly} | \times | \checkmark | \times |
| \mathbf{Sh}(\mathbb{Q}) | \checkmark | \times | \times |
| \mathbf{Set}^{\mathcal{C}^\textnormal{op}} (\mathcal{C} small) | \checkmark | \checkmark | \checkmark |
| \mathbf{Cat} | \checkmark | \checkmark | \times |
| \mathbf{Top} | \times | \times | \times |
There is also a version of the adjoint functor theorem for any \Phi. Recall that if L\colon\mathcal{C}\to\mathcal{D} is a functor between presentable categories and L preserves colimits then it has a right adjoint R. Concretely, R(d) is the terminal object of the comma category L\mathbin{\downarrow}d, equivalently the colimit of the projection (L\mathbin{\downarrow}d)\to\mathcal{C}.
But in fact we do not need all of L\mathbin{\downarrow}d. One can look only at the comma category \mathcal{A}\mathbin{\downarrow}_L d, whose objects are the \Phi-compact a\in\mathcal{A}\subseteq\mathcal{C} equipped with a map g\colon La\to d. If \mathcal{C} is \Phi class-accessible, again its colimit in \mathcal{C} must be R(d). And so the question is whether that colimit is the same as the colimit of a \Phi-shaped diagram. In the case \Phi=\kappa-filtered and \mathcal{A} is essentially small, the condition is automatic if \mathcal{C} is presentable and L preserves all small colimits. Indeed, \kappa-filtered colimits commute with \kappa-small limits in \mathbf{Set}, so the \kappa-compact objects are closed under all \kappa-small colimits, so every \mathcal{A}\mathbin{\downarrow}_L d has \kappa-small colimits because L preserves them, so \mathcal{A}\mathbin{\downarrow}_L d is \kappa-filtered; it is also essentially small since \mathcal{A} is.
Theorem 3.2. Let \Phi be a class of small categories, let \mathcal{C} be \Phi class-accessible, let \mathcal{A}\subseteq\mathcal{C} be its full subcategory of \Phi-compact objects, and let L\colon\mathcal{C}\to\mathcal{D} preserve \Phi-colimits. Then L has a right adjoint R if and only if, for every d\in\mathcal{D}, there exists a category I\in\Phi and a final functor (a_d,g_d)\colon I\to(\mathcal{A}\mathbin{\downarrow}_L d). In that case R(d)\coloneqq\mathop{\mathrm{colim}}_{i:I}a_{d,i} \tag{1} and the counit LR(d)\to d has components g_{d,i}\colon L(a_{d,i})\to d.
Proof. (Sketch). Suppose L has a right adjoint R. By \Phi class-accessibility, we have a category I\in\Phi and a diagram of \Phi-compact objects with \mathop{\mathrm{colim}}_{i:I}a_{d,i}\cong R(d). The question is whether the resulting functor is final. The inclusions a_{d,i}\to R(d), equivalently g_{d,i}\colon La_{d,i}\to d, assemble into a functor (a_d,g_d)\colon I\to(\mathcal{A}\mathbin{\downarrow}_L d). It is final because for any (a,g) the transpose a\to\mathop{\mathrm{colim}}_ia_{d,i} factors through some a_{d,i}, because a is \Phi-compact, and any two such factorizations become equal in \mathop{\mathrm{colim}}_i\mathcal{C}(a,a_{d,i}), hence are joined by a zigzag.
Conversely, given a final (a_d,g_d), define R(d) by the above colimit (Equation 1). For \Phi-compact a, note that \mathcal{A}\mathbin{\downarrow}_L d is the category of elements of a\mapsto\mathcal{D}(La,d). Thus since I is final in it, we have \mathcal{C}(a,R(d))\cong\mathop{\mathrm{colim}}_i\mathcal{C}(a,a_{d,i})\cong\mathcal{D}(La,d). Every object of \mathcal{C} is a \Phi-colimit of \Phi-compact ones and L preserves \Phi-colimits, so this isomorphism extends from \mathcal{A} to all of \mathcal{C}.
Taking \Phi to be the discrete categories, a category admits a final functor from a discrete one exactly when it has a set of connected components each with a terminal object. For many discretely-presentable categories this can fail, e.g. if the connected components form a proper class. Taking \Phi to be the \kappa-filtered categories recovers the usual adjoint functor theorem when \mathcal{C} is \kappa-accessible and cocomplete and L preserves all small colimits, and there we have no such issue because \mathcal{A}\mathbin{\downarrow}_L d is \kappa-filtered, as noted above, and it is essentially small so a small skeleton can serve as I. And taking \Phi to be all small categories, if \mathcal{C} is totally accessible then \mathcal{A}\mathbin{\downarrow}_L d is again essentially small and the condition is vacuous, which is why presheaf categories get an adjoint functor theorem with no hypotheses beyond preservation of all small colimits.
4 Conclusion
I’ve now given almost the same construction three times, each with a different class of colimit for the formula \mathop{\mathrm{colim}}_i \mathcal{C}(c,d_i)\cong\mathcal{C}(c,\mathop{\mathrm{colim}}_i d_i). In each case, we can also consider the corresponding cocompletion:
| shape | hom preserves colim | colim-generated categories | colim completion |
|---|---|---|---|
| \kappa-filtered | \kappa-compact | accessible | \mathbf{Ind}_\kappa(\mathcal{A}) |
| discrete | connected | discretely accessible | \mathbf{Fam}(\mathcal{A}) |
| all small | tiny | totally accessible | \mathbf{Set}^{\mathcal{A}^\textnormal{op}} |
Every (filtered) accessible category is \mathbf{Ind}_\kappa(\mathcal{A}) for some \mathcal{A}; every discretely accessible category is \mathbf{Fam}(\mathcal{A}) for some \mathcal{A}, and every totally accessible category is \mathbf{Set}^{\mathcal{A}^\textnormal{op}} for some \mathcal{A}.
The analogy looks quite tidy! But I said almost the same construction, because the discrete case is actually slightly better. First, the top and bottom rows of the above table require \mathcal{A} to be small and the middle row does not, which is exactly what we need for \mathbf{Poly}: its connected objects are the representables \mathcal{y}^S, one for each set S, so \mathbf{Poly}=\mathbf{Fam}(\mathbf{Set}^\textnormal{op}) and \mathbf{Set}^\textnormal{op} is not small.
Second, an object may have many filtered presentations, whereas in \mathbf{Poly} (and in any discretely accessible category) the decomposition into connected pieces is canonical: to compute \mathbf{Poly}(c,d)=\prod_i\sum_jC_i^{D_j} one does not have to choose a presentation.
So anyone who winces when they hear that some category \mathcal{C} is not presentable should at least consider whether it is \Phi class-presentable for another class \Phi of colimits. Choosing \Phi is choosing which calculus one gets, and I claim that a discrete calculus is at least as nice as a filtered one: \begin{array}{lll}\text{discrete}&\mathcal{C}(c,d)\cong\prod_i\sum_j\mathcal{C}(c_i,d_j)&\text{for \emph{the} decomposition of $c$ and $d$}\\[3pt]\text{$\kappa$-filtered}&\mathcal{C}(c,d)\cong\lim_i\mathop{\mathrm{colim}}_j\mathcal{C}(c_i,d_j)&\text{for \emph{some} presentation of $c$ and $d$.}\end{array}
This material is based upon work supported by the Air Force Office of Scientific Research under award numbers FA9550-23-1-0376. Thanks to Maximilien Péroux and Aaron Huntley for helpful conversations.
References
Footnotes
Take a big set S with |S|\geq\kappa and let I be the poset of all \kappa-small subsets S_i\subseteq S, ordered by inclusion. Then I is \kappa-filtered and S=\cup_{i:I}S_i, so since 2^- sends colimits to limits and \mathcal{y}^- sends connected limits to colimits, we find \mathop{\mathrm{colim}}_i\mathcal{y}^{2^{S_i}}=\mathcal{y}^{2^S}, and yet \mathbf{Poly}(\mathcal{y}^X,\mathop{\mathrm{colim}}_i\mathcal{y}^{2^{S_i}})=\mathbf{Set}(2^S,X)\neq\mathop{\mathrm{colim}}_i\mathbf{Set}(2^{S_i},X)=\mathop{\mathrm{colim}}_i\mathbf{Poly}(\mathcal{y}^X,\mathcal{y}^{2^{S_i}}), since a function 2^S\to X need not factor through any 2^{S_i}.
We used that the functor \mathcal{y}^-\colon\mathbf{Set}\to\mathbf{Poly}^\textnormal{op} preserves all connected limits, including the cofiltered one above. This comes from two facts: coproducts commute with connected limits in \mathbf{Set}, and every object in \mathbf{Poly} is a coproduct of representables. Indeed, for connected I and any q=\sum_j\mathcal{y}^{B_j} we have \mathbf{Poly}(\mathop{\mathrm{colim}}_i\mathcal{y}^{A_i}, q)=\lim_i\sum_jA_i^{B_j}=\sum_j\lim_iA_i^{B_j}=q(\lim_i A_i)=\mathbf{Poly}(\mathcal{y}^{\lim_iA_i},q).↩︎