Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine
Posted by Emily Riehl
Guest post by Tim Campion
In the tenth installment of the Kan Extension Seminar, we take a break from all the 2-category theory we’ve been doing, in favor of some good old-fashioned 1-category theory (although if you keep an eye out, you may notice some higher dimensions lurking in the background!). This week’s paper is A Classification of Accessible Categories by Adámek, Borceux, Lack, and Rosický, which both generalizes and refines the classical theory of locally presentable and accessible categories by working relative to a new parameter, , called a limit doctrine. But don’t worry if you know nothing about locally presentable and accessible categories – I hope this post can serve as an introduction, from the -relative perspective.
The classical theory of locally presentable and accessible categories is notable partly because of its scope: many categories of intrinsic mathematical interest – from groups, rings, and fields, to categories themselves, to Banach spaces and contractive maps – are accessible. At the same time, the theory is notable for the richness of the categorical concepts that it brings together – from colimit completions, to sketches, to orthogonality classes. Both of these aspects will also be apparent in the generalized theory. We will recover, for example, not only the notion of a (multi sorted) Lawvere theory, but also much of the theory surrounding it.
I’d like to thank all my fellow seminar participants for thoughtful discussions so far, as well as everyone who’s joined the discussion at the Café. It’s been a fantastic experience , “popping open” the vacuum in which I’ve done category theory in the past! A special thanks to Emily for organizing all of this and providing feedback and support, and to Joe Hannon for what’s been a fruitful reading collaboration.
-Filtered Colimits
The whole business rests on the choice of a small set of small categories which we refer to as the doctrine of -limits, because we’re thinking of the categories as indices for limit diagrams. For most of the results of the paper we require to satisfy a technical condition called soundness; more on that later. Some examples to have in mind are
The doctrine of finite limits, consisting of all categories with finitely many morphisms.
More generally, the doctrine of -small limits for some regular cardinal , consisting of all categories with fewer than morphisms. So is .
The doctrine of finite products, consisting of all finite discrete categories.
Also worth considering are
The doctrine of finite connected limits, consisting of all finite connected categories.
The empty doctrine consisting of no categories. (This is 0.)
The doctrine of the terminal object, consisting of the empty category. (This is .)
The classical case of -accessible categories will be recovered if we choose .
Recall that for small categories , we say that -limits commute with -colimits in if, for every functor , the canonical map
is an isomorphism. We now say that a small category is -filtered if -limits commute with -colimits for every . In our examples,
The -filtered categories are usually just called filtered. A category is filtered iff there is a cone on every finite diagram in .
The -filtered categories are usually just called -filtered. A category is -filtered iff there is a cone on every diagram in with morphisms.
The -filtered categories are called sifted (en français: tamisante). Filtered categories are sifted, and so are the index category for reflexive coequalizers (two arrows with a common section) and the co-simplex category .
The -filtered categories are the coproducts of filtered categories.
Every category is -filtered.
The -filtered categories are the connected categories.
Finally, an object of a category is said to be -presentable if the covariant hom-functor preserves -filtered colimits. We will shortly see some examples of what this means for various and .
Locally -Presentable Categories
We could dive straight into the theory of -accessible categories, but the most important aspects of the theory are already present when we look at the locally -presentable categories, which are just the -accessible categories which are also cocomplete. Some simplifications are also possible in the locally -presentable setting, and lots of important examples are already encompassed. So let’s start with this case, and later discuss how the theory is modified in the more general case.
Definition 1: A locally -presentable category is a cocomplete category with a small full subcategory of -presentable objects such that every object is a -filtered colimit of objects of .
A locally -presentable category is just a category of presheaves on a small category . A presheaf is -presentable iff it is a retract of a representable.
A locally -presentable category is just the category of models for a (possibly multi-sorted) Lawvere theory: these are sometimes called the algebraic categories, or the many-sorted varieties. This includes the locally -presentable categories, as well as the categories of Groups, Rings, -Modules, Lattices, etc. The -presentable objects of any of these categories are the retracts of the free algebras.
A locally -presentable category is simply called locally finitely presentable. This includes all locally -presentable categories, as well as the category of Small Categories, the category of Posets, and many others. In these examples (including e.g. Categories and -Modules), a finitely presentable object is one which is finitely presentable in the usual sense: it is finitely generated, and subject to finitely many equations.
A locally -presentable category is called locally -presentable. In addition to the locally finitely presentable categories, these include the category of -Algebras, the category of Banach spaces and contractive maps (both locally -presentable) and other categories of algebras with infinitary operations, as well as any Grothendieck topos. And -presentability is analogous to finite presentability.
On the other hand, the category of topological spaces, for example, is not locally -presentable for any : we will see later that every locally -presentable category is locally -presentable for some , and the -presentable objects of are the discrete spaces with points (as discussed here and here); their colimits are again discrete. The category of Hilbert spaces is also not locally -presentable because it is self dual, and the opposite of a locally -presentable category is never -presentable.
Also, beware that the “hereditary” nature of the locally -presentable world, where if then locally -presentable categories are locally -presentable, does not carry over so nicely to the -accessible case.
… as -Filtered Cocompletions
Part of the power of the theory of locally -presentable and -accessible categories is that they are robust concepts admitting many equivalent definitions. Let’s look at a few of them.
The first one is of a very formal flavor. Consider the 2-category of categories with all -filtered colimits, functors preserving -filtered colimits, and natural transformations. There is an obvious forgetful 2-functor , which has a left 2-adjoint which we will call , so that is the free -filtered cocompletion of the category .
Definition 2: A locally -presentable category is a free -filtered cocompletion of a small -cocomplete category .
It’s a little funny that only adjoins -filtered colimits, and yet we end up with a cocomplete category. This comes down to the proviso that be -cocomplete (meaning that every diagram in with index for some has a colimit). This proviso will be lifted when we generalize to -accessible categories.
In order to relate Definition 2 to Definition 1, we must describe explicitly. It’s well-known that the free cocompletion of a small category is its category of presheaves – that is, . It turns out that restricted cocompletions like can be formed similarly: for any doctrine and small category , is the closure of the representables in under -filtered colimits. When the doctrine is sound (more on this later!), this colimit completion can be taken in one step – that is, a -filtered colimit of -filtered colimits of representables is a -filtered colimit of representables. This allows us to conclude that Definition 2 is equivalent, for a sound doctrine, to
Definition 3: A locally -presentable category is a full subcategory of , for some small, -cocomplete category , consisting of the -filtered colimits of representables.
Using this description, we can at least state the relationship between Definition 1 and Definitions 2 and 3. If is locally -presentable in the sense of Definition 1, then the nerve of the inclusion of the full subcategory of -presentables (which is essentially small and -cocomplete )
is an equivalence. Conversely, in the -presentable objects are the representables, and everything is a -filtered colimit of them.
… as Categories of Continuous Functors
Definition 3 gives us an explicit description of a locally -presentable category as a category of presheaves, but it would be better to have a more intrinsic characterization of exactly which presheaves on lie in . The answer is very nice: a presheaf is a -filtered colimit of representables if and only if preserves -indexed limits for all . This yields
Definition 4: A locally -presentable category is a category consisting of all -continuous presheaves for some small -cocomplete category .
A particularly nice example of this comes with . In this case, is a multi sorted Lawvere theory, and the associated locally -presentable category is exactly the category of models of the Lawvere theory.
More generally, this correspondence between -complete categories like and the associated locally -presentable categories extends to a duality of 2-categories with the proper definitions. In the case , this is known as Gabriel-Ulmer duality. The -relative case is due to Centazzo and Vitale.
A variation on this theme is to represent a locally -presentable category as a category of -valued functors preserving not all -limits, but just certain ones. This is the theory of -sketches, and it is in the spirit of the Freyd-Kelly paper we read a couple of months ago, Categories of Continuous Functors.
A limit -sketch consists of a small category and a set of cones in indexed by categories in . A model of the sketch consists of a functor sending the designated cones to limit cones. A morphism of models is a natural transformation between them. We have
Definition 5: A locally -presentable category is the category of models of a limit -sketch.
Of course, Definition 4 implies Definition 5 by taking and designating every limit cone with index in . The converse follows by completing under -limits in the opposite of its category of models.
The advantage of using a sketch is that the category can be smaller and more manageable than it has to be otherwise.
For example, when , the category of groups can be presented as the category of all finite-product preserving functors where , the Lawvere theory for groups, is the opposite of the category of all finitely-generated free groups. But if we use a sketch, we can take to consist just of the free groups on 0, 1, 2, and 3 generators, with appropriate product diagrams indicated: thus we essentially define a group to be a group object in .
This is even more apparent when . For example, to represent as a category of finitely-continuous functors , we must take to be all finitely presentable categories, which is rather awkward. But if we use a sketch, then we can take the category of simplices , with pullback diagrams indicating Segal conditions. Thus categories are represented by their simplicial nerves. We could even get away with consisting just of the 0,1,2, and 3-dimensional simplices – then the sketch corresponds pretty directly to the usual notion of a internal category.
… as -Orthogonality Classes
From the Freyd-Kelly paper, we know that categories of continuous functors can be thought of as orthogonality classes. And it turns out that locally -presentable categories can be recognized by the orthogonality classes defining them. We say that a -orthogonality class in a category is a full subcategory of consisting of the objects orthogonal to the arrows in a set , where the domains and codomains of arrows in are -presentable. Then we have
Definition 6: The locally -presentable categories are precisely the -orthogonality classes in presheaf categories.
More generally, a -orthogonality class in a locally -presentable category is always locally -presentable. These orthogonality classes are substantially simpler than the ones considered in the Freyd-Kelly paper: they are determined by a small set of arrows, and they are in functor categories with values in rather than a more general category.
-Accessible Categories
Now it’s time to relax the cocompleteness condition for locally -presentable categories and see where the chips fall. Rather than all small colimits, a -accessible category is required only to have -filtered colimits.
Definition 1’: A -accessible category is a category with -filtered colimits and a small set of -presentable objects of which every object is a -filtered colimit.
So the locally -presentable categories are just the cocomplete -accessible categories. What does this added generality buy us?
The -accessible categories are still just the presheaf categories.
The -accessible categories have been called generalized varieties. Besides the varieties, they include the algebraic categories, but also the category of fields and the category of linearly ordered sets.
The -accessible categories are just called finitely accessible. Beyond the locally finitely presentable case, finitely accessible posets are known as continuous posets, and they are important in Domain theory.
The -accessible categories are just called -accessible. They include the locally -presentable categories; a non-cocomplete example is the category of Hilbert Spaces and linear contractions, which is countably accessible.
The -accessible categories are just the free coproduct completions of accessible categories .
And how do the other equivalent definitions change? Definitions 2 and 3 actually simplify in the general case:
Definition 2’: A -accessible category is the free -filtered cocompletion of a small category .
Definition 3’: A -accessible category is a full subcategory of , for some small category , consisting of the -filtered colimits of representables.
The change is that can be an arbitrary small category; it is not required to be -cocomplete.
When we come to Definition 4, trying to provide an intrinsic characterization of the presheaves of , we hit a snag. If is not -cocomplete, then it doesn’t make much sense to consider -continuous functors , and in fact -continuity is not a strong enough condition to single out the presheaves in . Instead, we call the presheaves of the -flat functors, in analogy to the flat functors which are recovered as the -flat functors. The condition of soundness allows us to characterize these functors in a few different ways, in analogy to the classical case:
Theorem: (2.4 in the paper) If is sound and is a presheaf on a small category, then the following are equivalent:
The left Kan extension of along the Yoneda embedding preserves -limits of representables.
is -continuous.
is a -filtered colimit of representables (i.e. ).
The category of elements is -filtered.
These conditions collectively are taken to provide an adequate characterization of the -flat functors. If is -cocomplete, -flatness reduces to -continuity.
Definition 4’: A -accessible category is a category of -flat functors on a small category .
I should emphasize that this is not the only place where soundness comes up in the theory – just the most obvious.
Moving on, the theory of -sketches generalizes to the -accessible case. In addition to indicating certain -indexed cones to be sent to limits, we must allow ourselves to also specify certain colimit cones, of arbitrary index. Sketches provide a nice way to present -accessible categories. For example, the theory of fields can be sketched by sketching a ring and then indicating a decomposition of as the coproduct of two objects, one of which is equipped with an inverse operation, and the other of which contains only the zero element of the ring; see, for example here.
Unfortunately, though, there are -sketchable categories which are not -accessible. Examples exist even for and . It is a fact, though, that every -sketchable category is -accessible for some (this is how we know that -accessible categories are accessible, as I alluded to earlier), but it is not possible to make general conclusions within a given doctrine .
Non-Definition 5’: All -accessible categories are -sketchable, but not conversely.
Finally, -accessible categories are not cocomplete outside the locally -presentable case, so they are clearly not reflective in presheaf categories. So Definition 6 doesn’t really have an analogue for -accessible categories.
A Word About Soundness
The technical notion of soundness permeates this paper, but I’ve been trying to suppress it for the most part up to now. To define what it means for a doctrine to be sound, let me first say what it means for a category to be representably -filtered:
Recall that a category is -filtered if for every , and every , canonically. Similarly, is representably -filtered if this condition holds for of the form for some functor . (If we think of as a profunctor , these are the representable profunctors).
Certainly -filtered categories are representably -filtered. The doctrine is called sound if the converse holds, so that -filteredness coincides with representable -filteredness.
One nice thing about soundness is that it makes -filteredness easier to check, because representable -filteredness admits a nice combinatorial description. In fact, for an arbitrary doctrine and small category , the following are equivalent:
For each , every functor has a connected category of cocones.
For each , the diagonal functor is a final functor.
is representably -filtered.
The functor preserves -limits of representables.
Soundness is a very particular condition. All of the doctrines I mentioned above are sound. Some interesting unsound doctrines include:
The doctrine of discrete categories with morphisms. The unsoundness here is disappointing if one is interested in doing algebra with infinitary operations. Some of the theory can be extended, but the notion of -sifted colimit used has to be more subtle.
The doctrine of pullbacks. The category of small categories, for example, is sketchable by a pullback sketch, so it’s too bad that this doctrine is unsound.
The doctrine of pullbacks and terminal objects. This is striking given that all finite limits can be constructed out of pullbacks and terminal objects, and is sound.
Conclusion
Adámek, Borceux, Lack, and Rosický present their theory as a classification of accessible categories, emphasizing the perspective it brings on the menagerie of accessible categories out there. Most importantly, the theory puts -accessibility on the same formal footing as the theory of -accessibility– it’s not clear that there are really any other important sound doctrines out there. Consider this a challenge to find more sound doctrines! At least as great a contribution is provided by the perspective that the -relative approach brings in organizing the general theory of -accessibility, allowing us to see which parts are formal and where special facts enter in.
The theory of limits and colimits that commute in has seen interesting developments recently, some reported on this blog. It’s worth mentioning that according to Marie Bjerrum, who studies these things, the better concept to work with may actually representable -filteredness rather than -filteredness. It would be interesting to see if variations of these concepts might allow the theory of this paper to be extended beyond sound doctrines.
There are also other generalizations to consider. Besides changing our doctrine , there is a theory of enriched accessibility, and we can also talk about taking “models” in categories other than . All three directions of generalization are considered by Lack and Rosický in Notions of Lawvere Theory, but there is more to do. I believe there is also a theory of accessibility of quasicategories, and perhaps also in other contexts. All of these areas could potentially benefit from the perspective brought by relativizing to a limit doctrine.
Finally, there is more in this paper that I haven’t discussed, including a theory of -multipresentable categories and an interesting distributive law between the 2-monad and the free completion 2-monad. These might be worth discussing in the comments.
Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine
Another way to think about -flatness is that it is just a weighted version of -filteredness.
After all, in Thm 2.4 (quoted above), criterion (2) for flatness of says that the left Kan extension along the Yoneda embedding, , is -continuous. But has another name: It is just the functor which takes the -weighted colimit. So criterion (2) for -flatness really says that , considered as a colimit weight, is -filtered in a weighted sense.
Similarly, criterion (1) for -flatness of (which says that preserves -limits of representables) says that preserves -limits of representables, i.e. that is representably -filtered in a weighted sense. So it would make sense to call an satisfying criterion (1) “representably -flat”.
In fact, when you look at the proof of the theorem, you see that it actually shows that is representably -flat if and only if is representably -filtered – even if is unsound. This is a very interesting fact. Certainly every -weighted colimit can be expressed as a conical colimit over , but in the converse direction, an -diagram only corresponds to an -weighted diagram if it factors through the discrete opfibration .