## May 20, 2014

### 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, $\mathbb{D}$, 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 $\mathbb{D}$-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.

### $\mathbb{D}$-Filtered Colimits

The whole business rests on the choice of a small set $\mathbb{D}$ of small categories which we refer to as the doctrine of $\mathbb{D}$-limits, because we’re thinking of the categories $\mathcal{D} \in \mathbb{D}$ as indices for limit diagrams. For most of the results of the paper we require $\mathbb{D}$ to satisfy a technical condition called soundness; more on that later. Some examples to have in mind are

• The doctrine $\mathbf{FIN}$ of finite limits, consisting of all categories with finitely many morphisms.

• More generally, the doctrine $\lambda\mathbf{-LIM}$ of $\lambda$-small limits for some regular cardinal $\lambda$, consisting of all categories with fewer than $\lambda$ morphisms. So $\mathbf{FIN}$ is $\aleph_0\mathbf{-LIM}$.

• The doctrine $\mathbf{FINPR}$ of finite products, consisting of all finite discrete categories.

Also worth considering are

• The doctrine $\mathbf{FINCL}$ of finite connected limits, consisting of all finite connected categories.

• The empty doctrine $\emptyset$ consisting of no categories. (This is 0$\mathbf{-LIM}$.)

• The doctrine $\mathbf{TERM}$ of the terminal object, consisting of the empty category. (This is $1\mathbf{-LIM}$.)

The classical case of $\lambda$-accessible categories will be recovered if we choose $\mathbb{D}=\lambda\mathbf{-LIM}$.

Recall that for small categories $\mathcal{C}, \mathcal{D}$, we say that $\mathcal{D}$-limits commute with $\mathcal{C}$-colimits in $\mathbf{Set}$ if, for every functor $F: \mathcal{C} \times \mathcal{D} \to \mathbf{Set}$, the canonical map

$\operatorname{colim}_{c \in \mathcal{C}} \operatorname{lim}_{d \in \mathcal{D}} F(c,d) \to \operatorname{lim}_{d \in \mathcal{D}} \operatorname{colim}_{c \in \mathcal{C}} F(c,d)$

is an isomorphism. We now say that a small category $\mathcal{C}$ is $\mathbb{D}$-filtered if $\mathcal{D}$-limits commute with $\mathcal{C}$-colimits for every $\mathcal{D} \in \mathbb{D}$. In our examples,

• The $\mathbf{FIN}$-filtered categories are usually just called filtered. A category $\mathcal{C}$ is filtered iff there is a cone on every finite diagram in $\mathcal{C}$.

• The $\lambda\mathbf{-LIM}$-filtered categories are usually just called $\lambda$-filtered. A category $\mathcal{C}$ is $\lambda$-filtered iff there is a cone on every diagram in $\mathcal{C}$ with $\lt\lambda$ morphisms.

• The $\mathbf{FINPR}$-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 $\Delta^\mathrm{op}$.

• The $\mathbf{FINCL}$-filtered categories are the coproducts of filtered categories.

• Every category is $\emptyset$-filtered.

• The $\mathbf{TERM}$-filtered categories are the connected categories.

Finally, an object $x$ of a category $\mathcal{K}$ is said to be $\mathbb{D}$-presentable if the covariant hom-functor $\mathcal{K}(x,-): \mathcal{K} \to \mathbf{Set}$ preserves $\mathbb{D}$-filtered colimits. We will shortly see some examples of what this means for various $\mathbb{D}$ and $\mathcal{K}$.

### Locally $\mathbb{D}$-Presentable Categories

We could dive straight into the theory of $\mathbb{D}$-accessible categories, but the most important aspects of the theory are already present when we look at the locally $\mathbb{D}$-presentable categories, which are just the $\mathbb{D}$-accessible categories which are also cocomplete. Some simplifications are also possible in the locally $\mathbb{D}$-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 $\mathbb{D}$-presentable category is a cocomplete category $\mathcal{K}$ with a small full subcategory $\mathcal{A}$ of $\mathbb{D}$-presentable objects such that every object is a $\mathbb{D}$-filtered colimit of objects of $\mathcal{A}$.

• A locally $\emptyset$-presentable category $\mathcal{K}$ is just a category $[\mathcal{A}^\op, \mathbb{Set}]$ of presheaves on a small category $\mathcal{A}$. A presheaf is $\emptyset$-presentable iff it is a retract of a representable.

• A locally $\mathbf{FINPR}$-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 $\emptyset$-presentable categories, as well as the categories of Groups, Rings, $R$-Modules, Lattices, etc. The $\mathbf{FINPR}$-presentable objects of any of these categories are the retracts of the free algebras.

• A locally $\mathbf{FIN}$-presentable category is simply called locally finitely presentable. This includes all locally $\mathbf{FINPR}$-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 $R$-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 $\lambda\mathbf{-LIM}$-presentable category is called locally $\lambda$-presentable. In addition to the locally finitely presentable categories, these include the category of $C^{\ast}$-Algebras, the category of Banach spaces and contractive maps (both locally $\aleph_1$-presentable) and other categories of algebras with infinitary operations, as well as any Grothendieck topos. And $\lambda$-presentability is analogous to finite presentability.

On the other hand, the category $\mathbf{Top}$ of topological spaces, for example, is not locally $\mathbb{D}$-presentable for any $\mathbb{D}$: we will see later that every locally $\mathbb{D}$-presentable category is locally $\lambda$-presentable for some $\lambda$, and the $\lambda$-presentable objects of $\mathbf{Top}$ are the discrete spaces with $\lt\lambda$ points (as discussed here and here); their colimits are again discrete. The category of Hilbert spaces is also not locally $\mathbb{D}$-presentable because it is self dual, and the opposite of a locally $\mathbb{D}$-presentable category is never $\mathbb{D}$-presentable.

Also, beware that the “hereditary” nature of the locally $\mathbb{D}$-presentable world, where if $\mathbb{D} \subseteq \mathbb{D}'$ then locally $\mathbb{D}$-presentable categories are locally $\mathbb{D}'$-presentable, does not carry over so nicely to the $\mathbb{D}$-accessible case.

### … as $\mathbb{D}$-Filtered Cocompletions

Part of the power of the theory of locally $\mathbb{D}$-presentable and $\mathbb{D}$-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 $\mathbf{\mathbb{D}-Fil-Cocts}$ of categories with all $\mathbb{D}$-filtered colimits, functors preserving $\mathbb{D}$-filtered colimits, and natural transformations. There is an obvious forgetful 2-functor $U: \mathbf{\mathbb{D}-Fil-Cocts} \to \mathbf{Cat}$, which has a left 2-adjoint which we will call $\mathbb{D}\mathbf{-Ind}$, so that $\mathbf{\mathbb{D}-Ind}(\mathcal{A})$ is the free $\mathbb{D}$-filtered cocompletion of the category $\mathcal{A}$.

Definition 2: A locally $\mathbb{D}$-presentable category $\mathcal{K}$ is a free $\mathbb{D}$-filtered cocompletion $\mathbf{\mathbb{D}-Ind}(\mathcal{A})$ of a small $\mathbb{D}^{\mathrm{op}}$-cocomplete category $\mathcal{A}$.

It’s a little funny that $\mathbf{\mathbb{D}-Ind}$ only adjoins $\mathbb{D}$-filtered colimits, and yet we end up with a cocomplete category. This comes down to the proviso that $\mathcal{A}$ be $\mathbb{D}^{\mathrm{op}}$-cocomplete (meaning that every diagram in $\mathcal{A}$ with index $\mathcal{D}^{\mathrm{op}}$ for some $\mathcal{D} \in \mathbb{D}$ has a colimit). This proviso will be lifted when we generalize to $\mathbb{D}$-accessible categories.

In order to relate Definition 2 to Definition 1, we must describe $\mathbf{\mathbb{D}-Ind}(\mathcal{A})$ explicitly. It’s well-known that the free cocompletion of a small category $\mathcal{A}$ is its category of presheaves $[\mathcal{A}^{\mathrm{op}}, \mathbf{Set}]$ – that is, $\mathbf{\emptyset-Ind}(\mathcal{A}) = [\mathcal{A}^{\mathrm{op}}, \mathbf{Set}]$. It turns out that restricted cocompletions like $\mathbf{\mathbb{D}-Ind}$ can be formed similarly: for any doctrine $\mathbb{D}$ and small category $\mathcal{A}$, $\mathbf{\mathbb{D}-Ind}(\mathcal{A})$ is the closure of the representables in $[A^{\mathrm{op}}, \mathbf{Set}]$ under $\mathbb{D}$-filtered colimits. When the doctrine $\mathbb{D}$ is sound (more on this later!), this colimit completion can be taken in one step – that is, a $\mathbb{D}$-filtered colimit of $\mathbb{D}$-filtered colimits of representables is a $\mathbb{D}$-filtered colimit of representables. This allows us to conclude that Definition 2 is equivalent, for a sound doctrine, to

Definition 3: A locally $\mathbb{D}$-presentable category $\mathcal{K}$ is a full subcategory of $[\mathcal{A}^{\mathrm{op}}, \mathbf{Set}]$, for some small, $\mathbb{D}^{\mathrm{op}}$-cocomplete category $\mathcal{A}$, consisting of the $\mathbb{D}$-filtered colimits of representables.

Using this description, we can at least state the relationship between Definition 1 and Definitions 2 and 3. If $\mathcal{K}$ is locally $\mathbb{D}$-presentable in the sense of Definition 1, then the nerve of the inclusion $i: \mathcal{K}_{\mathbb{D}} \to \mathcal{K}$ of the full subcategory $\mathcal{K}_{\mathbb{D}}$ of $\mathbb{D}$-presentables (which is essentially small and $\mathbb{D}^{\mathrm{op}}$-cocomplete )

$\begin{matrix} \mathcal{K} &\to &\mathbf{\mathbb{D}-Ind}(\mathcal{K}_{\mathbb{D}}) \\ K &\mapsto &\mathcal{K}(i-, K) \end{matrix}$

is an equivalence. Conversely, in $\mathbf{\mathbb{D}-Ind}(\mathcal{A})$ the $\mathbb{D}$-presentable objects are the representables, and everything is a $\mathbb{D}$-filtered colimit of them.

### … as Categories of Continuous Functors

Definition 3 gives us an explicit description of a locally $\mathbb{D}$-presentable category as a category of presheaves, but it would be better to have a more intrinsic characterization of exactly which presheaves on $\mathcal{A}$ lie in $\mathbf{\mathbb{D}-Ind}(\mathcal{A})$. The answer is very nice: a presheaf $F: \mathcal{A}^{\mathrm{op}} \to \mathbf{Set}$ is a $\mathbb{D}$-filtered colimit of representables if and only if $F$ preserves $\mathcal{D}$-indexed limits for all $\mathcal{D} \in \mathbb{D}$. This yields

Definition 4: A locally $\mathbb{D}$-presentable category is a category consisting of all $\mathbb{D}$-continuous presheaves $F: \mathcal{A}^{\mathrm{op}} \to \mathbf{Set}$ for some small $\mathbb{D}^{\mathrm{op}}$-cocomplete category $\mathcal{A}$.

A particularly nice example of this comes with $\mathbb{D}=\mathbf{FINPR}$. In this case, $\mathcal{A}^{\mathrm{op}}$ is a multi sorted Lawvere theory, and the associated locally $\mathbf{FINPR}$-presentable category is exactly the category of models of the Lawvere theory.

More generally, this correspondence between $\mathbb{D}$-complete categories like $\mathcal{A}^{\mathrm{op}}$ and the associated locally $\mathbb{D}$-presentable categories extends to a duality of 2-categories with the proper definitions. In the case $\mathbb{D} = \mathbf{FIN}$, this is known as Gabriel-Ulmer duality. The $\mathbb{D}$-relative case is due to Centazzo and Vitale.

A variation on this theme is to represent a locally $\mathbb{D}$-presentable category as a category of $\mathbf{Set}$-valued functors preserving not all $\mathbb{D}$-limits, but just certain ones. This is the theory of $\mathbb{D}$-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 $\mathbb{D}$-sketch consists of a small category $\mathcal{T}$ and a set of cones in $\mathcal{T}$ indexed by categories in $\mathbb{D}$. A model of the sketch consists of a functor $\mathcal{T} \to \mathbf{Set}$ sending the designated cones to limit cones. A morphism of models is a natural transformation between them. We have

Definition 5: A locally $\mathbb{D}$-presentable category is the category of models of a limit $\mathbb{D}$-sketch.

Of course, Definition 4 implies Definition 5 by taking $\mathcal{T} = \mathcal{A}^{\mathrm{op}}$ and designating every limit cone with index in $\mathbb{D}$. The converse follows by completing $\mathcal{T}$ under $\mathbb{D}$-limits in the opposite of its category of models.

The advantage of using a sketch is that the category $\mathcal{T}$ can be smaller and more manageable than it has to be otherwise.

For example, when $\mathbb{D} = \mathbf{FINPR}$, the category of groups can be presented as the category of all finite-product preserving functors $\mathcal{A}^{\mathrm{op}} \to \mathbf{Set}$ where $\mathcal{A}^{\mathrm{op}}$, 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 $\mathcal{T}$ 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 $\mathbf{Set}$.

This is even more apparent when $\mathbb{D} = \mathbf{FIN}$. For example, to represent $\mathbf{Cat}$ as a category of finitely-continuous functors $\mathcal{A}^{\mathrm{op}} \to \mathbf{Set}$, we must take $\mathcal{A}^\mathrm{op}$ to be all finitely presentable categories, which is rather awkward. But if we use a sketch, then we can take the category of simplices $\mathcal{T} = \Delta^{\mathrm{op}}$, with pullback diagrams indicating Segal conditions. Thus categories are represented by their simplicial nerves. We could even get away with $\mathcal{T}$ 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 $\mathbb{D}$-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 $\mathbb{D}$-presentable categories can be recognized by the orthogonality classes defining them. We say that a $\mathbb{D}$-orthogonality class in a category $\mathcal{L}$ is a full subcategory of $\mathcal{L}$ consisting of the objects orthogonal to the arrows in a set $\mathcal{M}$, where the domains and codomains of arrows in $\mathcal{M}$ are $\mathbb{D}$-presentable. Then we have

Definition 6: The locally $\mathbb{D}$-presentable categories $\mathcal{K}$ are precisely the $\mathbb{D}$-orthogonality classes in presheaf categories.

More generally, a $\mathbb{D}$-orthogonality class in a locally $\mathbb{D}$-presentable category is always locally $\mathbb{D}$-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 $\mathbf{Set}$ rather than a more general category.

### $\mathbb{D}$-Accessible Categories

Now it’s time to relax the cocompleteness condition for locally $\mathbb{D}$-presentable categories and see where the chips fall. Rather than all small colimits, a $\mathbb{D}$-accessible category is required only to have $\mathbb{D}$-filtered colimits.

Definition 1’: A $\mathbb{D}$-accessible category $\mathcal{K}$ is a category with $\mathbb{D}$-filtered colimits and a small set $\mathcal{A}$ of $\mathbb{D}$-presentable objects of which every object is a $\mathbb{D}$-filtered colimit.

So the locally $\mathbb{D}$-presentable categories are just the cocomplete $\mathbb{D}$-accessible categories. What does this added generality buy us?

• The $\emptyset$-accessible categories are still just the presheaf categories.

• The $\mathbf{FINPR}$-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 $\mathbf{FIN}$-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 $\mathbf{\lambda-\mathbf{LIM}}$-accessible categories are just called $\lambda$-accessible. They include the locally $\lambda$-presentable categories; a non-cocomplete example is the category of Hilbert Spaces and linear contractions, which is countably accessible.

• The $\mathbf{FINCL}$-accessible categories are just the free coproduct completions $\mathbf{Fam}(\mathcal{K})$ of accessible categories $\mathcal{K}$.

And how do the other equivalent definitions change? Definitions 2 and 3 actually simplify in the general case:

Definition 2’: A $\mathbb{D}$-accessible category $\mathcal{K}$ is the free $\mathbb{D}$-filtered cocompletion $\mathbf{\mathbb{D}-Ind}(\mathcal{A})$ of a small category $\mathcal{A}$.

Definition 3’: A $\mathbb{D}$-accessible category $\mathcal{K}$ is a full subcategory of $[\mathcal{A}^{\mathrm{op}}, \mathbf{Set}]$, for some small category $\mathcal{A}$, consisting of the $\mathbb{D}$-filtered colimits of representables.

The change is that $\mathcal{A}$ can be an arbitrary small category; it is not required to be $\mathbb{D}^\mathrm{op}$-cocomplete.

When we come to Definition 4, trying to provide an intrinsic characterization of the presheaves of $\mathbf{\mathbb{D}-Ind}(\mathcal{A})$, we hit a snag. If $\mathcal{A}$ is not $\mathbb{D}^\mathrm{op}$-cocomplete, then it doesn’t make much sense to consider $\mathbb{D}$-continuous functors $\mathcal{A}^{\mathrm{op}} \to \mathbf{Set}$, and in fact $\mathbb{D}$-continuity is not a strong enough condition to single out the presheaves in $\mathbf{\mathbb{D}-Ind}(\mathcal{A})$. Instead, we call the presheaves of $\mathbf{\mathbb{D}-Ind}(\mathcal{A})$ the $\mathbb{D}$-flat functors, in analogy to the flat functors which are recovered as the $\mathbf{FIN}$-flat functors. The condition of soundness allows us to characterize these functors in a few different ways, in analogy to the classical $\mathbb{D}=\mathbf{FIN}$ case:

Theorem: (2.4 in the paper) If $\mathbb{D}$ is sound and $F: \mathcal{A}^{\mathrm{op}} \to \mathbf{Set}$ is a presheaf on a small category, then the following are equivalent:

1. The left Kan extension $\operatorname{Lan}_Y F : [A, \mathbf{Set}] \to \mathbf{Set}$ of $F$ along the Yoneda embedding preserves $\mathbb{D}$-limits of representables.

2. $\operatorname{Lan}_Y F$ is $\mathbb{D}$-continuous.

3. $F$ is a $\mathbb{D}$-filtered colimit of representables (i.e. $F \in \mathbf{\mathbb{D}-Ind}(\mathcal{A})$).

4. The category of elements $\operatorname{Elts}(F)^\mathrm{op}$ is $\mathbb{D}$-filtered.

These conditions collectively are taken to provide an adequate characterization of the $\mathbb{D}$-flat functors. If $\mathcal{A}$ is $\mathbb{D}$-cocomplete, $\mathbb{D}$-flatness reduces to $\mathbb{D}$-continuity.

Definition 4’: A $\mathbb{D}$-accessible category $\mathcal{K}$ is a category of $\mathbb{D}$-flat functors on a small category $\mathcal{A}$.

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 $\mathbb{D}$-sketches generalizes to the $\mathbb{D}$-accessible case. In addition to indicating certain $\mathbb{D}$-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 $\mathbb{D}$-accessible categories. For example, the theory of fields can be sketched by sketching a ring $R$ and then indicating a decomposition of $R$ 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 $\mathbb{D}$-sketchable categories which are not $\mathbb{D}$-accessible. Examples exist even for $\mathbb{D} = \mathbf{FIN}$ and $\mathbb{D} = \mathbf{FINPR}$. It is a fact, though, that every $\mathbb{D}$-sketchable category is $\lambda$-accessible for some $\lambda$ (this is how we know that $\mathbb{D}$-accessible categories are accessible, as I alluded to earlier), but it is not possible to make general conclusions within a given doctrine $\mathbb{D}$.

Non-Definition 5’: All $\mathbb{D}$-accessible categories are $\mathbb{D}$-sketchable, but not conversely.

Finally, $\mathbb{D}$-accessible categories are not cocomplete outside the locally $\mathbb{D}$-presentable case, so they are clearly not reflective in presheaf categories. So Definition 6 doesn’t really have an analogue for $\mathbb{D}$-accessible categories.

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 $\mathbb{D}$ to be sound, let me first say what it means for a category to be representably $\mathbb{D}$-filtered:

Recall that a category $\mathcal{C}$ is $\mathbb{D}$-filtered if for every $\mathcal{D} \in \mathbb{D}$, and every $F: \mathcal{D} \times \mathcal{C} \to \mathbf{Set}$, $\mathrm{colim}\,\mathrm{lim}\, F \cong \mathrm{lim}\,\mathrm{colim}\, F$ canonically. Similarly, $\mathcal{C}$ is representably $\mathbb{D}$-filtered if this condition holds for $F$ of the form $C(S,1)$ for some functor $S: \mathcal{D}^\mathrm{op} \to \mathcal{C}$. (If we think of $F$ as a profunctor $\mathcal{D}^\mathrm{op} \to \mathcal{C}$, these are the representable profunctors).

Certainly $\mathbb{D}$-filtered categories are representably $\mathbb{D}$-filtered. The doctrine $\mathbb{D}$ is called sound if the converse holds, so that $\mathbb{D}$-filteredness coincides with representable $\mathbb{D}$-filteredness.

One nice thing about soundness is that it makes $\mathbb{D}$-filteredness easier to check, because representable $\mathbb{D}$-filteredness admits a nice combinatorial description. In fact, for an arbitrary doctrine $\mathbb{D}$ and small category $\mathcal{C}$, the following are equivalent:

• For each $\mathcal{D} \in \mathbb{D}$, every functor $S: \mathcal{D}^\mathrm{op} \to \mathcal{C}$ has a connected category of cocones.

• For each $\mathcal{D} \in \mathbb{D}$, the diagonal functor $\Delta: \mathcal{C} \to [\mathcal{D}^\mathrm{op}, \mathcal{C}]$ is a final functor.

• $\mathcal{C}$ is representably $\mathbb{D}$-filtered.

• The functor $\mathrm{colim}: [\mathcal{C},\mathbf{Set}] \to \mathbf{Set}$ preserves $\mathbb{D}$-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 $\lambda\mathbf{-PR}$ of discrete categories with $\lt \lambda$ 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 $\lambda$-sifted colimit used has to be more subtle.

• The doctrine $\mathbf{PB}$ 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 $\mathbf{PB} \cup \mathbf{TERM}$ of pullbacks and terminal objects. This is striking given that all finite limits can be constructed out of pullbacks and terminal objects, and $\mathbf{FIN}$ 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 $\mathbf{FINPR}$-accessibility on the same formal footing as the theory of $\lambda$-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 $\mathbb{D}$-relative approach brings in organizing the general theory of $\mathbb{D}$-accessibility, allowing us to see which parts are formal and where special facts enter in.

The theory of limits and colimits that commute in $\mathbf{Set}$ 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 $\mathbb{D}$-filteredness rather than $\mathbb{D}$-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 $\mathbb{D}$, there is a theory of enriched accessibility, and we can also talk about taking “models” in categories other than $\mathbf{Set}$. 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 $\mathbb{D}$-multipresentable categories and an interesting distributive law between the 2-monad $\mathbb{D}\mathbf{-Ind}$ and the free completion 2-monad. These might be worth discussing in the comments.

Posted at May 20, 2014 7:40 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2741

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Another way to think about $\mathbb{D}$-flatness is that it is just a weighted version of $\mathbb{D}$-filteredness.

After all, in Thm 2.4 (quoted above), criterion (2) for flatness of $F: \mathcal{A}^\mathrm{op} \to \mathbf{Set}$ says that the left Kan extension along the Yoneda embedding, $\mathrm{Lan}_Y F: [\mathcal{A}, \mathbf{Set}] \to \mathbf{Set}$, is $\mathbb{D}$-continuous. But $\mathrm{Lan}_Y F$ has another name: It is just the functor $F * (-)$ which takes the $F$-weighted colimit. So criterion (2) for $\mathbb{D}$-flatness really says that $F$, considered as a colimit weight, is $\mathbb{D}$-filtered in a weighted sense.

Similarly, criterion (1) for $\mathbb{D}$-flatness of $F$ (which says that $\mathrm{Lan}_Y F$ preserves $\mathbb{D}$-limits of representables) says that $F *(-)$ preserves $\mathbb{D}$-limits of representables, i.e. that $F$ is representably $\mathbb{D}$-filtered in a weighted sense. So it would make sense to call an $F$ satisfying criterion (1) “representably $\mathbb{D}$-flat”.

In fact, when you look at the proof of the theorem, you see that it actually shows that $F$ is representably $\mathbb{D}$-flat if and only if $\mathsf{Elts}(F)^\mathrm{op}$ is representably $\mathbb{D}$-filtered – even if $\mathbb{D}$ is unsound. This is a very interesting fact. Certainly every $F$-weighted colimit can be expressed as a conical colimit over $\mathsf{Elts}(F)^\mathrm{op}$, but in the converse direction, an $\mathsf{Elts}(F)^\mathrm{op}$-diagram only corresponds to an $F$-weighted diagram if it factors through the discrete opfibration $\mathsf{Elts}(F)^\mathrm{op} \to \mathcal{A}$.

Posted by: Tim Campion on May 21, 2014 2:23 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

This fits well with the definitions in enriched accessible categories, where the things that are filtered are the weights, not the categories. In ordinary category theory, a weight is filtered if and only if the corresponding category of elements is filtered. I remember thinking that “soundness” is actually a generalisation of this, but I don’t remember why…

Posted by: Zhen Lin on May 21, 2014 8:39 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

I’ve never been able to get much intuition for the notion of “soundness”. Should it be considered a sort of “saturation” condition?

Posted by: Mike Shulman on May 21, 2014 5:04 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

I don’t really understand the interplay between soundness and saturation in the sense of Albert and Kelly. A doctrine doesn’t have to be saturated to be sound – witness finite limits. Is every saturated doctrine sound? I’m not sure. At one point I convinced myself that the doctrine of simply-connected L-finite limits (the “conical saturation” of the doctrine of pullbacks) was just as unsound as the doctrine of pullbacks.

But I take it you meant something else – maybe the question is whether there’s a minimal sound doctrine $\overline{\mathbb{D}}$ containing a given doctrine $\mathbb{D}$. In the best case scenario, the $\overline{\mathbb{D}}$-filtered categories would even coincide with the representably $\mathbb{D}$-filtered categories. In order to do this, we would need to choose, for each representably $\mathbb{D}$-filtered$\mathcal{C}$ but not $\mathbb{D}$-filtered $\mathcal{C}$, a category $\mathcal{D}$ such that $\mathcal{C}$ is not representably $\mathcal{D}$-filtered. This doesn’t seem very promising.

For general doctrines $\mathbb{D}$, one nice fact is that the class of $\mathbb{D}$-flat weights is always saturated in the Albert-Kelly sense, and the class of $\mathbb{D}$-filtered categories is “conically saturated” (so any colimit that can be constructed out of $\mathbb{D}$-filtered colimits is itself $\mathbb{D}$-filtered…). This is essentially because $\mathbb{D}$-filteredness of $\mathcal{C}$ can be defined by the condition that certain functors, namely functors $\mathrm{lim}: [\mathcal{D}, \mathbf{Set}] \to \mathbf{Set}$ for $\mathcal{D} \in \mathbb{D}$, preserve $\mathcal{C}$-colimits.

This property fails for representable $\mathbb{D}$-filteredness (or at least an analogous sort of argument doesn’t work) because representable $\mathbb{D}$-filteredness of $\mathcal{C}$ is not simply a $\mathcal{C}$-cocontinuity condition, but rather says that certain functors preserve certain $\mathcal{C}$-colimits.

I don’t know whether the lack of a “soundification” is related to the non-saturation of the representably $\mathbb{D}$-filtered categories, but I’d like to guess that it is. This leads me to speculate that we might get better behaved notions if we considered an intermediate notion: $\mathbb{D}$-filteredness of $\mathcal{C}$ says that $\colim: [\mathcal{C}, \mathbf{Set} \to \mathbf{Set}$ preserves all $\mathbb{D}$-limits, while representable $\mathbb{D}$-filteredness of $\mathcal{C}$ says that the same functor preserves $\mathbb{D}$-limits of representables. The intermediate notion would say that this functor preserves $\mathbb{D}$-limits of functors which land in the iterated $\mathbb{D}$-limits of representables. This is a little exotic, though, because it means considering $\mathbb{D}$-limits in a free cocompletion of $\mathcal{C}^\mathrm{op}$. So maybe it’s off the mark.

Posted by: Tim Campion on May 22, 2014 3:21 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

But I take it you meant something else — maybe the question is whether there’s a minimal sound doctrine $\overline{\mathbb{D}}$ containing a given doctrine $\mathbb{D}$

Yes, that’s why I put “saturation” in quotes in that comment.

The notion of “representable $\mathbb{D}$-filteredness” does seem quite odd from the perspective of saturation.

Posted by: Mike Shulman on May 22, 2014 4:30 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

As mentioned by Tim above, I prefere to define a category C to be D-filtered iff the category of cocones over any D-diagram in C is connected. Then if we denote D the class/doctrine of D-filtered categories , we have that a doctrine D is sound iff D^+=D-FILT, i.e. iff the colimits that commute with D-limits in Set are exactly the D-filtered colimits.

I tend to think that the “soundness condition” is not a lot more than “its easier if we restrict to (pointwise) representable diagrams F:I*J–>Set”.

Posted by: Marie Bjerrum on May 22, 2014 1:43 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

I tend to think that the “soundness condition” is not a lot more than “its easier if we restrict to (pointwise) representable diagrams $F:I\times J\to Set$

Unfortunately, that doesn’t give me any intuition. (-:

(You can make math here by putting it in dollar-signs just as in TeX.)

Posted by: Mike Shulman on May 22, 2014 4:29 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

I mean, it’s essentially like this. You sit down and say, I’d like a theory which is like the theory of finite limits–filtered colimits, but for an arbitrary class of weights $\Phi$. So I impose an axiom called “soundness” on $\Phi$ which says, “$\Phi$ admits a theory like the theory of finite limits–filtered colimits”. It doesn’t reduce, except in trivial ways, the problem of what is actually required for such a theory.

Posted by: Richard Garner on May 24, 2014 7:41 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

I wasn’t sure which of the two previous comments to reply to, so I’m starting a new thread.

There’s some new work that’s very relevant to this that appeared on the arXiv just last week by Matěj Dostál and Jiří Velebil:

Their aim is to extend this work to categories enriched over a bicomplete closed symmetric monoidal category $\mathcal{V}$.

Here, the doctrine $\mathbb{D}$ should be replaced by a class of weights $\Psi$. The class of $\Psi$-flat weights is then the class of functors $\phi \colon \mathcal{E}^{op} \to \mathcal{V}$ so that the weighted colimit:

$\phi \star - \colon [\mathcal{E},\mathcal{V}] \to \mathcal{V}$

preserves $\Psi$-limits.

The class $\Psi$ is sound if any weight $\phi$ so that $\phi \star -$ preserves $\Psi$-limits of representables is $\Psi$-flat. As Tim mentions above, this is exactly the ABLR notion of flatness in the case $\mathcal{V} = Set$.

The authors call a class of weights $\Phi$ (for colimits) saturated if for any small category $\mathcal{D}$, the free cocompletion under $\Phi$-colimits is the subcategory of $[\mathcal{D}^{op},\mathcal{V}]$ of $\Phi$-colimits of representables.

For classes of weights that are saturated and locally small (meaning the $\Phi$-colimit completion is (essentially?) small), the authors show that soundness is equivalent to another characterization that is satisfied by the doctrine of pullbacks and terminal objects. So in that case at least, lack of soundness is a failure of saturation.

As the title suggests, particular attention is given to the class of sifted weights, but I’m running late for a talk, so I’ll have to leave this to another post.

Posted by: Emily Riehl on May 21, 2014 8:27 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Ah, excellent! Looking at weights often clarifies these sorts of things. After reading Tim’s comment, it occurred to me as well that criterion (3) for $\mathbb{D}$-flatness implies that $F$ lies in the saturation of the $\mathbb{D}$-filtered colimits, in the sense of Albert and Kelly. And his first remark about soundness in the post says that in the sound case, the converse of this also holds.

Dostal and Velebil claim that they are using the Albert-Kelly notion of “saturated”, but I don’t see how their definition is equivalent to it. As you say, they say that $\Phi$ is saturated if the free $\Phi$-cocompletion of $\mathcal{D}$ is the subcategory of $\Phi$-colimits of representables in $[\mathcal{D}^{op},\mathcal{V}]$, but Albert-Kelly’s definition (or, more precisely, their characterization theorem) requires instead that the free $\Phi$-cocompletion of $\mathcal{D}$ (which is always the closure of the representables under $\Phi$-colimits) is the subcategory of weights in $[\mathcal{D}^{op},\mathcal{V}]$ which belong to $\Phi$.

They also claim that the saturation of $\mathbf{PB}\cup\mathbf{TERM}$ is the class of finitely presentable colimits; I believe that actually, it is the slightly larger class of L-finite colimits (which is also the saturation of $\mathbf{FIN}$). This raises an interesting question: for any $\mathbb{D}$, consider the class of all limits that commute with $\mathbb{D}$-filtered colimits in Set; is it saturated and/or sound?

Posted by: Mike Shulman on May 21, 2014 2:07 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

So Dostal and Velebil’s condition on $\Phi$ is that the free $\Phi$-cocompletion be taken in one step…. This follows from saturation in the Albert-Kelly step, right?

Actually, the converse is not true: for example, the free filtered cocompletion of a category is taken in one step, but the filtered weights are all terminal weights on their categories!

Posted by: Tim Campion on May 22, 2014 3:47 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Yes, that’s right: Dostal and Velebil’s condition is strictly weaker than saturation. Maybe they should call it “weakly saturated” or “pre-saturated”.

Posted by: Mike Shulman on May 22, 2014 4:33 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Lets, for some doctrine D of finite limits, call the class of limits that commute with D-filtered colimits in Set, the Galois closure of D and denote it D^{+-}.

We then say that a doctrine D is Galois closed iff D^{+-}=D.

I call a doctrine D essentially Galois closed (EGC) iff D^{+-} is just the saturation of D together with (the shape for) idempotentsplitting (D\cup IDEM)^*.

Now all sound classes are essentially Galois closed (essentially generator of their Galois closure) and the class PB\cup TERM is EGC but not sound, i.e yes it is the saturation of FIN.

The class PB and the class EQ (equalisers) are neither EGC nor sound. However the Galois closure of PB and of EQ is the saturation of FINCON (finite connected categories).

My feeling is that that the notion EGC could in many cases replace the soundness condition.

Posted by: Marie Bjerrum on May 22, 2014 12:15 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Why “Galois”?

Posted by: Mike Shulman on May 22, 2014 4:32 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

If I understand Marie correctly, “Galois” refers to the Galois connection from which the closure operation is defined, namely the one given by the commutation of limits with colimits.

Posted by: Tim Campion on May 23, 2014 12:14 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

If that’s all, then maybe it would be better to use a more descriptive adjective. After all, there are lots of Galois connections in the world… (-:

Posted by: Mike Shulman on May 24, 2014 12:09 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

The theorem that Emily teased says that a saturated doctrine $\mathbb{D}$ is sound if and only if the $\mathbb{D}$-filtered colimits of representable presheaves on any $\mathbb{D}^\mathrm{op}$-cocomplete category coincide with the $\mathbb{D}$-continuous presheaves. In terms of ABLR’s theorem 2.4, this says that criterion (1) implies criterion (3) for $\mathbb{D}^\mathrm{op}$-cocomplete categories. A slightly weaker condition (that criterion (1) imply criterion (2) for $\mathbb{D}^\mathrm{op}$-cocomplete categories) was mentioned in ABLR Rmk 2.6 as a possible weakening of soundness. It’s interesting because it’s a condition that only looks at functors defined on $\mathbb{D}$-complete categories.

Posted by: Tim Campion on May 22, 2014 11:02 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

I’m frequently asked questions of the following form: in category $K$ do $\mathcal{D}$-limits commute with $\mathcal{C}$-colimits?

If $\mathcal{D}$ is in a sound limit doctrine $\mathbb{D}$ – actually does soundness matter here? I’m not sure – and $\mathcal{C}$ is $\mathbb{D}$-filtered, then this is true in any $\mathbb{D}$-accessible category $K$.

Here’s a proof: We’re asking whether for any functor $F \colon \mathcal{C} \times \mathcal{D} \to K$, the canonical map $colim_\mathcal{C} lim_\mathcal{D} F \to lim_\mathcal{D} colim_\mathcal{C} F$ is an isomorphism in $K$. The collection representable functors $K(a,-)$, where $a \in K$ is $\mathbb{D}$-presentable, is jointly conservative, so it suffices to detect this isomorphism after hom-ing out of a $\mathbb{D}$-presentable object. The rest is straightforward.

Now here’s my question: are there other categories for which this is true? I’m interested both in classes of examples and in particular examples. And is soundness of $\mathbb{D}$ necessary? (I suppose if I thought about this carefully I could work it out for myself.)

Posted by: Emily Riehl on May 22, 2014 9:12 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Oddly enough, there is a well-known instance of “filtered colimits preserve finite limits” that is not an instance of this theorem: namely, in Grothendieck toposes. The proof in that case relies heavily on the fact that the associated sheaf functor preserves (filtered) colimits and finite limits. (Of course, Grothendieck toposes are always accessible, but the point is that they need not be finitely accessible.)

Posted by: Zhen Lin on May 22, 2014 11:17 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

One class of categories for which finite limits commute with filtered colimits would be the precontinuous categories: i.e. complete categories $\mathcal{K}$ with filtered colimits such that the functor $\colim: \mathbf{Ind}(\mathcal{K}) \to \mathcal{K}$ is continuous. These are the algebras for the distributive law discussed at the end of the ABLR paper in the case $\mathbb{D} = \mathbf{FIN}$, and the categories which satisfy all the same “equational conditions” as locally finitely presentable categories. This implies that finite limits commute with filtered colimits, and also that “(arbitrary) products distribute over filtered colimits” in the sense that if $(D_i)_{i \in I}$ is a set of filtered diagrams, then the canonical map $\mathrm{colim}_{d \in \Pi_i D_i} \Pi_i D_i d_i \to \Pi_i \mathrm{colim}_{d_i \in D_i} D_i d_i$ is an isomorphism. I don’t really know any examples, except to say that if $\mathcal{K}$ is a poset, then precontinuity means that $\mathcal{K}$ is a so-called continuous lattice, which I gather is an important concept in Domain theory.

As another way to generalize, finite limits and filtered colimits should commute in a category of the form $\mathbf{Ind}(\mathcal{A})$ even if $\mathcal{A}$ is large. But again, I don’t know any good examples.

Posted by: Tim Campion on May 22, 2014 12:58 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Indeed, filtered colimits preserve finite limits in $\mathbf{Ind}(\mathcal{A})$ even when $\mathcal{A}$ is large (but, to avoid set-theoretic difficulties, we should assume $\mathcal{A}$ is locally small). The proof is the same: $\mathbf{Ind}(\mathcal{A})$ has a dense family of finitely presented objects. The only serious example of this I know of is the category of ind-schemes, which generalise formal schemes. Far more common is the dual notion, $\mathbf{Pro}(\mathcal{A}) = \mathbf{Ind}(\mathcal{A}^\mathrm{op})^\mathrm{op}$.

Posted by: Zhen Lin on May 22, 2014 1:42 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

For the case of finite limits and filtered colimits, see Day–Street “Localisation of locally presentable categories”. They show that the cocomplete categories with a small strong generator and finite limits commuting with finite colimits are precisely the localisations of locally presentable categories.

More generally, if $\mathbb{D}$ is any sound doctrine, then you can look at (a) $\mathbb{D}$-locally presentable categories (b) reflective subcategories thereof for which the reflector preserves $\mathbb{D}$-limits.

Any such category will be cocomplete and have $\mathbb{D}$-limits commuting with $\mathbb{D}$-filtered colimits. Maybe the Day–Street proof can be generalised to show that (assuming also the existence of a small generator) every example arises in this way.

Posted by: Richard Garner on May 24, 2014 7:56 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

The title misled me. Day and Street don’t characterize the localizations of all locally presentable categories – just the localizations of locally finitely presentable categories. This makes things simpler from a doctrinal perspective, because both the notion of “localization” (meaning “reflective subcategory with finitely-continuous reflector”), and the notion of finite limits commuting with filtered colimits, are tied down to the particular doctrine of finite limits. So it makes sense to similarly tie down the notion of locally $\lambda$-presentable category to the particular doctrine $\lambda = \aleph_0$, too, rather than letting $\lambda$ be arbitrary.

Now, a reflective subcategory of a locally finitely presentable category which is closed under filtered colimits is again locally finitely presentable (and a continuation of the study of $\mathbb{D}$-orthogonality classes in the ABLR paper should show that a reflective subcategory of a locally $\mathbb{D}$-presentable category which is closed under $\mathbb{D}$-filtered colimits is locally $\mathbb{D}$-presentable). So the only way a localization of a locally finitely presentable category can fail to be locally finitely presentable is if it is not closed under filtered colimits. I didn’t find any examples in Day and Street’s paper. What would be a good one?

Posted by: Tim Campion on May 24, 2014 1:44 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Any locally $\kappa$-presentable category ($\kappa \gt \aleph_0$) is an example. Indeed, every locally $\kappa$-presentable category is admits a fully faithful functor to a presheaf topos with a left adjoint, and every presheaf topos is locally finitely presentable.

Posted by: Zhen Lin on May 24, 2014 5:52 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

True, a locally presentable category is a reflective subcategory of a presheaf category. I guess I was wondering about those which have the extra property that the reflector preserves finite limits, so that Day and Street would call it a localization, and so that (apparently) finite limits will commute with filtered colimits (in a locally $\lambda$-presentable category, $\lambda$-small limits commute with $\lambda$-filtered colimits, but the $\lambda$s are the same across the board).

By your observation, every Grothendieck topos is an example (recovering what you talked about earlier). I wonder if the category of models of a finite-limit sketch in a given category of sheaves on a site $(C,J)$ might be an example? Is such a category a localization of the category of models in the category of presheaves on $C$?

Posted by: Tim Campion on May 24, 2014 7:25 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Yes, there is a associated sheaf functor for finite limit sketches. One just verifies everything componentwise. So, for example, the category of abelian sheaves is a reflective “localisation” of the category of abelian presheaves. This observation is important in showing that the category of abelian sheaves is a Grothendieck abelian category.

This goes horribly wrong once you allow colimit sketches: then the inclusion of sheaves into presheaves doesn’t even send models to models!

Posted by: Zhen Lin on May 24, 2014 11:30 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Arg, yes, there was a “finitely” missing from my original reply.

As for a locally presentable, but not locally finitely presentable, localisation of a presheaf category, well, just take any Grothendieck topos that is not locally finitely presentable. $\mathbf{Sh}(\mathbb{R})$ would do.

For an explicit example of a filtered colimit not preserved by the inclusion of sheaves into presheaves on $\mathbb{R}$ consider the chain

$1 \to 1 + 1 \to 1 + 1 + 1 \to \dots$

of left coproduct injections in $\mathbf{Sh}(\mathbb{R})$. The $n$th term in this sequence is the sheaf $\Delta n$ of locally constant functions taking values in $\{1, \dots, n\}$; so its value at an open set $U$ is the set of functions

$(\Delta n)(U) = \{1, \dots, n\}^{\pi_0(U)} .$

The colimit of this chain in sheaves is the sheaf $\Delta \mathbb{N}$ of locally constant functions taking values in $\mathbb{N}$, with value at $U$ given by

$(\Delta \mathbb{N})(U) = \mathbb{N}^{\pi_0(U)} .$

But the colimit $Z$ of this chain in presheaves is computed pointwise, and so has value at $U$ given by

$Z(U) = \{f \in \mathbb{N}^{\pi_0(U)} : f \text{has finite range}\} .$

So at any $U$ with infinitely many connected components, these two do not coincide.

Posted by: Richard Garner on May 25, 2014 1:27 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

I have a question about the relation of sketches to logical theories. (I’m not really a logician so forgive me if anything I say doesn’t make sense). I can see how sketches generalise (multi-sorted) algebraic theories: you have a bunch of sorts, and a bunch of operations between them. In an algebraic theory you can define new sorts by taking formal products of old ones, and in a $\mathbb{D}$-sketch you can take $\mathbb{D}$-limits and arbitrary colimits of sorts. So sketches generalise algebraic theories by allowing more complicated operations. On the other hand, first-order logic (or other fragments of it) generalise algebraic theories by allowing more complicated formulae (by introducing logical connectives and quantifiers).

My question is: is there any relation between these two generalisations? Is there some fragment of first-order logic that describes “sketchable” theories?

Posted by: Tom Avery on May 22, 2014 5:15 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

The class of theories that can be sketched using finite limits and arbitrary colimits is precisely the class of geometric theories. I think more generally, the class of theories sketchable using $\kappa$-small limits and arbitrary colimits should be the class of theories axiomatisable in a generalised geometric logic where $\kappa$-ary conjunctions and sequences of $\kappa$-many existential quantifiers are allowed.

Posted by: Zhen Lin on May 22, 2014 7:25 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

This is discussed in section 3.2 of Makkai-Pare Accessible categories. The sketchable theories are those axiomatizable by sets of sequents-in-context $\phi \vdash \psi$, where $\phi$ and $\psi$ are “positive-existential formulas”, built up from atomic formulas using only (infinitary) conjunction, disjunction, and existential quantification.

Posted by: Mike Shulman on May 22, 2014 10:52 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Ah, interesting. Thanks for this!

Posted by: Tom Avery on May 23, 2014 1:36 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

In the ABLR treatment, an important part of the yoga of a sound doctrine is that a weight $F$ is representably $\mathbb{D}$-flat if and only if $\mathsf{Elts}(F)^\mathrm{op}$ is representably $\mathbb{D}$-filtered; soundness lets us drop “representably”. Not only do I find the proof of this (Thm 2.4, as quoted above) quite mysterious, but I don’t suppose it’s available in the enriched context. But in the comments here we’ve already seen two treatments of enriched soundness: Lack and Rosicky and Dostal and Velebil. Is there a high concept explanation for how soundness works in the enriched context, in particular for how the analogue of Thm 2.4 is proven?

Posted by: Tim Campion on May 22, 2014 11:12 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Prop. 2.1 in the paper is fundamental to establish and understand the notion of soundness: I tried to produce a more verbose proof in my notepad, and I discovered chatting with others that it was a different perspective on the situation.

Once again, I’m fascinated by the power of coends in action!

First of all one has to justify the fact that $\ccn(S)\cong \lim \; \mathcal{C}(S,1)$: I didn’t know this result, but at a second glance it’s easy. One simply checks that a cocone on the left is an element of the limit on the right and live happy for the rest of the proof.

But now there’s this misterious result according to which $\pi_0(\Elts\; F)\cong \colim\; F$ for any functor $F\colon \mathcal{E}\to \mathbf{Set}$. I had a hard time in trying to explain myself why this should be true: the better I could do is argue that $\Elts\; F$ can be written as a weighted colimit, $\Elts\; F\cong \int^C J C\times F C$ (where $J\colon \mathcal{C}\to\mathbf{Cat}$ sends $C$ into the slice $\mathcal{C}/C$) and this colimit is preserved by $\pi_0$, since it happens to have a right adjoint (more precisely, $\pi_0\dashv \delta \dashv (-)_0 \dashv \mathcal{G}$, where $\delta$ sends a set into the discrete category on that set, $(-)_0$ takes the set of objects of a category $\mathcal{C}$ and $\mathcal{G}$ takes a set $X$ into the groupoid which has exactly one isomorphism between any two arrows). So now $\pi_0\left( \Elts\; F\right)\cong \pi_0\left(\int^C J C\times F C \right)\cong \int^C \pi_0 J C\times F C$ since $\pi_0$, being cocontinuous, preserves the $\mathbf{Set}$-tensoring of $\mathbf{Cat}$), and since $J C$ is connected (it has a terminal object, $1_C$!), we remain with $\pi_0\left( \Elts\; F\right)\cong \int^C F C\cong\colim\; F$ which concludes: the rest of the proof is automatic (but I had to discover that there’s a pattern in taking limits/colimits of representable functors, and to remember, once again, that the limit of a constant is not always the constant itself! :) ).

Each of these step is natural: glueing all these local trivialities gives a nontrivial result which especially Tim seemed to appreciate.

Thank you again, Tim!!!

Posted by: Fosco Loregian on May 23, 2014 8:16 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

We can also see the fact $\text{colim} F \cong \pi (\text{el} F)$ as a consequence of the result $\text{colim} (\Delta 1 \colon \mathcal{A} \to \text{Set}) \cong \pi(\mathcal{A})$ together with some basic facts about weighted colimits. Firstly we can express the colimit as a weighted colimit $\text{colim} F \cong \Delta 1 \ast F \cong F \ast \Delta 1,$ using the commutativity of weighted colimits into Set. Now we can express this weighted colimit as a conical colimit using the category of elements, giving $\text{colim} F \cong \text{colim} \left( (\text{el} F)^{op} \to \mathcal{C} \to^{\Delta 1} \text{Set} \right) \cong \text{colim}\left( (\text{el} F)^{op} \to^{\Delta 1} \text{Set} \right),$ the composite begin again the constant diagram. And then from the first stated result we get $\text{colim} F \cong \pi (\text{el} F)$ as desired.

Posted by: Alexander Campbell on May 23, 2014 9:22 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Oh, cool! Not only does this approach link this fact to the construction of $F$-weighted colimits as $\mathsf{Elts}(F)^\mathrm{op}$-indexed colimits (which still seems mysterious to me), but it also uses the isomorphism $F \star G \cong G \star F$, which I’m starting to grow rather fond of (for instance, it shows up in the proof that $\mathrm{Lan}_Y F(G) = G \star F = F \star G$).

Posted by: Tim Campion on May 23, 2014 11:45 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

I thought it was cool to see a conceptual proof like this; I was thinking of this as more of a “brute fact,” where you look at the equivalence relations involved and notice that they’re the same!

Another “brute fact” about the category of elements is that if $F$ is a presheaf on $\mathcal{C}$ and $G: \mathcal{C} \to \mathcal{D}$, then the weighted colimit $F \star G$ is given by the conical colimit after precomposing with the discrete opfibration $\mathsf{Elts}(F)^\mathrm{op} \to \mathcal{C}$. Again, the proof I’m familiar with involves simply checking by hand. Is there a more conceptual proof of this fact?

Really, everything involving the category of elements tends to seem very mysterious to me. I like the colimit-type characterization $\mathsf{Elts}(F) = \int^c J c \times F c$ because I haven’t been getting very far with the limit-type characterizations I’ve been using (for instance, $\mathsf{Elts}(F)$ is the inserter from $\Delta 1$ to $F$, equivalently the lax limit of $F$; this can also be expressed using pullbacks or comma objects).

The coincidence of a colimit expression with a limit expression suggests to me that some sort of 2-categorical exactness property is at work, but how does concept defined on the nlab come into play here?

Posted by: Tim Campion on May 23, 2014 11:41 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

I’ve gotten in the habit of defining the category of elements of a presheaf $F \colon C^{op} \to Set$ so that there is a covariant forgetful functor $Elts(F) \to C$. One nice thing is that we then have an isomorphism between $Elts(F)$ and the comma category $y \downarrow F$, where $y \colon C \to [C^{op},Set]$ is the Yoneda embedding. Another is that an $F$-weighted colimit is then a colimit indexed by $Elts(F)$.

For full disclosure, I should also admit that I typically define the category of elements of a covariant functor $G \colon C \to Set$ so that there is again a covariant functor $Elts(G) \to C$. So my preference is internally inconsistent: whether a category is “an opposite category” or not is a matter of convention, not an innate characteristic.

So is there a standard convention for the variance of the Grothendieck construction? I’ll have to chance something, but it’s not obvious to me which I should change to.

Posted by: Emily Riehl on May 23, 2014 2:29 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

I don’t know what the usual conventions are. But one way to defend your usage would be to insist that you take the category of elements of a module (profunctor), and part of the data is whether it’s a left or right module (profunctor from or to the unit category). You regard the category of elements construction as being two separate constructions, one for left modules and one for right modules. Then there’s handedness data to remember. I tend to remember that a presheaf $C^\mathrm{op} \to \mathbf{Set}$ is a profunctor $I \nrightarrow C$ from the unit category to $C$, because a presheaf is a generalized object (and an object is a functor $I \to C$). So a copresheaf $C \to \mathbf{Set}$ is a profunctor $C \nrightarrow I$. But I can’t remember which one is considered a left module and which one a right module.

Posted by: Tim Campion on May 23, 2014 7:24 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Concerning the expression of (ordinary) weighted colimits as conical colimits: I like to think of the formula as arising in the following way. Weighted colimits can be given in terms of left Kan extensions; we have that

$\begin{matrix} A & \overset{Y}{\rightarrow} & [A^{op}, Set] \\ {}_G \searrow & \overset{\cong}{\Rightarrow} & \swarrow_{-*G} \\ . & B \end{matrix}$

is a left Kan extension, by which I mean it is a pointwise left extension. Hence it has the property that pasting any comma square on top gives another left extension diagram. So, since $\text{el}(F)^{op} \cong Y/F$, we have that

$\begin{matrix} \text{el}(F)^{op} & \longrightarrow & 1 \\ \downarrow & \Rightarrow & \downarrow^{F} \\ A & \overset{Y}{\rightarrow} & [A^{op}, Set] \\ {}_G \searrow & \overset{\cong}{\Rightarrow} & \swarrow_{-*G} \\ . & B \end{matrix}$

is a left extension. But this just says that $F \ast G$ is the colimit of the left leg of the diagram. Hence the formula.

So we have shifted the question to: why do pointwise extensions have this pasting property?

(This property is sometimes taken as the definition of pointwise extension, so by pointwise here I mean something like being preserved by representables - maybe it’s enough to assume the resulting extension exists. )

Posted by: Alexander Campbell on May 23, 2014 2:33 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Or, to put it more simply: the formula is a special case of Lawvere’s formula for Kan extensions.

Posted by: Alexander Campbell on May 23, 2014 2:50 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Another perspective on this comes by thinking about proarrow equipments. From that point of view, the natural general notion of “colimit” is the colimit of an arrow (functor) $f:A\to B$ weighted by a proarrow (profunctor) $J:K ⇸ A$. For example:

• If $K$ is the terminal category (or more generally the unit enriched category), this gives the usual notion of weighted colimit.
• If $J$ is representable as $K(j,1) = j^\bullet$, then this gives a pointwise Kan extension along $j:A\to K$.
• If $J$ is representable as $A(1,j) = j_\bullet$, then this gives precomposition with $j:K\to A$.

One nice thing about this notion is that it has a functoriality that’s hard to express with less generality: if $J_1:K ⇸ A$ and also $J_2:L ⇸ K$, then the $J_2$-colimit of a $J_1$-colimit is the $(J_2\odot J_1)$-colimit. With this in hand, we can say that the “reason” every weighted colimit for $Set$-categories reduces to a conical one is that in $Set\text{-}Prof$, every profunctor $J:K ⇸ A$ can be written as $p^\bullet \odot q_\bullet$ for some span $K \xleftarrow{p} E \xrightarrow{q} A$ (such as $E=$ the category of elements of $J$).

Does this “explain” what’s going on? I’m not sure, but seeing something in multiple ways can help us feel like we understand it better.

The relationship to your remark about pasting comma squares is that $F \cong F_\bullet \odot Y^\bullet$. Thus, one could say that the point is that your comma square has the property that the induced map $p^\bullet \odot q_\bullet \to F_\bullet \odot Y^\bullet$ is an isomorphism. In a general proarrow equipment, a square with this property is called exact, and it just so happens that in $Set\text{-}Prof$ every comma square is exact.

So we could also shift the question to: why is every comma square (in $Cat$) exact in $Set\text{-}Prof$?

Posted by: Mike Shulman on May 24, 2014 5:31 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

The cheapest proof of that formula I know of relies on the fact that $(-) \star G$ preserves colimits (plus the Yoneda lemma for weighted colimits). Thus the problem is reduced to showing that every presheaf is the colimit of the canonical diagram of representables. The same idea can be used to extract necessary and sufficient conditions for reducing weighted (co)limits to conical (co)limits.

Posted by: Zhen Lin on May 23, 2014 3:15 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Again, the proof I’m familiar with involves simply checking by hand. Is there a more conceptual proof of this fact?

Coend juggling, again! Do you want to try on your own or… :)

Posted by: Fosco Loregian on May 24, 2014 4:38 PM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

Taking in consideration all these aforementioned wiseful perspectives , it would be valuable , too , consider the concepts of inaccessibility notion as mathematical syntactic rule , and the Scott ( 1961 ) comparative approach in the limitation of the constructibility hypothesis ( derived from number-theory ) ; that is , only as an epistemological tool , applied to Accessible Categories .Very amenable syntactic standpoint , derives , too , from hyerarchy of structures. Comment the article of Paré R et al - Colimits of accessible categories in Math Proc Camb Philos Soc 2013 ; 155 . No 1 : 47 -50 around directed colimits of accessible categories -cardinals and accessibility.

Posted by: Sabino Guillermo Echebarria Mendieta on May 23, 2014 11:45 AM | Permalink | Reply to this

### Re: Classifying by Generalizing: The Theory of Accessibility Relative to a Limit Doctrine

These are allusions to interesting-sounding ideas. Could you be more explicit? You covered a lot of ground, so I’d be interested to hear more about even just one of these things!

How does one think of accessibility as a syntactic rule? Category theorists tend to think of sketches as the “syntactic” end of the theory. Is what you had in mind related to this?

A Google scholar search reveals that Dana Scott published a paper on models of arithmetic in 1961, with a review behind a paywall here. Is this the paper you’re referring to? Just from the review I don’t see the relationship to accessible categories, but I’d be interested to hear about it. My understanding is that Scott later founded Domain theory, which uses the poset case of accessible categories – is this connected to what you’re talking about, or am I way off?

What’s this “hierarchy of structures”?

What is your comment on the Pare-Rosicky article? They show that directed colimits of accessible full embeddings between accessible categories are accessible, and remove the fullness condition using large cardinals. Large cardinals are related to logic, but now we’re light-years from the nonstandard models of arithmetic we started with!

Posted by: Tim Campion on May 23, 2014 12:12 PM | Permalink | Reply to this

### Duality

…this correspondence between $\mathbb{D}$-complete categories like $\mathcal{A}^{\mathrm{op}}$ and the associated locally $\mathbb{D}$-presentable categories extends to a duality of 2-categories with the proper definitions. In the case $\mathbb{D} = \mathbf{FIN}$, this is known as Gabriel-Ulmer duality. The $\mathbb{D}$-relative case is due to Centazzo and Vitale.

It seems that the $(\infty, 1)$-version of Gabriel-Ulmer duality works.

Is there a notion of sound doctrines in $(\infty,1)$-category theory to allow for a $\mathbb{D}$-relative case too?

Posted by: David Corfield on February 24, 2018 9:42 AM | Permalink | Reply to this

Post a New Comment