Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

March 21, 2012

Exact completions and small sheaves

Posted by Mike Shulman

At long last, the following paper is on the arXiv:

This was the subject of my talk at CT2011 last July, but it’s taken me this long to massage it into publishable form. (To be sure, I got distracted with other stuff, like hunting for a job and writing other papers.) For a brief overview, you can look at the slides from my CT2011 talk.

The paper is about “exact completions”, but to read it you don’t need to know already what an exact completion is, or even what an exact category is. However, let me tell you something about them anyway.

Roughly, an exact category is one with well-behaved quotients of internal equivalence relations. Every exact category is a regular category, i.e. it has well-behaved image factorizations. Specifically, given f:ABf\colon A\to B, we can define its kernel to be the equivalence relation on AA where aaa\sim a' means f(a)=f(a)f(a)=f(a'); then the quotient of this equivalence relation gives the image factorization of ff.

The easiest sort of “exact completion” to understand is that if you have a regular category CC, then there is a universal way to make it exact. In fact, we know what the objects of this “exact completion” should be: they should all be quotients of equivalence relations in CC, so we can just use the actual equivalence relations in CC to stand in for them. The morphisms between the quotients of two equivalence relations can also be characterized purely in terms of the equivalence relations — they are binary relations that are “entire” and “functional” with respect to the given equivalence relations — so we can use this to define the morphisms in the exact completion.

People often denote the exact completion of a regular category CC by C ex/regC_{ex/reg} (although I didn’t use that notation in the paper). This construction has a pleasing universal property: it exhibits exact categories as a reflective subcategory of regular ones. In particular, it is idempotent: the exact completion of an exact category is itself.

On the other hand, there is a slightly odd-looking construction, also called “exact completion”, where we start with a merely finitely complete category CC and produce an exact category. We can still look at internal equivalence relations in a finitely complete category, but in this case those aren’t enough to give us an exact category; instead we have to look at “pseudo equivalence relations”.

Sadly, the use of “pseudo” here has nothing to do with its usual meaning of “up to isomorphism” in higher category theory. A “pseudo equivalence relation” in this sense consists of an object X 0X_0, an object X 1X_1, two maps X 1X 0X_1 \;\rightrightarrows\; X_0 with a common “reflexivity” section X 0X 1X_0\to X_1, a “transitivity” map X 1× X 0X 1X 1X_1 \times_{X_0} X_1 \to X_1 over X 0×X 0X_0\times X_0, and a “symmetry” map X 1X 1X_1\to X_1 over the twist X 0×X 0X 0×X 0X_0\times X_0 \cong X_0\times X_0. In other words, it’s just like an internal equivalence relation, but we don’t demand that X 1X 0×X 0X_1 \to X_0\times X_0 be monic. The idea is that if CC were regular, then we could take the image of X 1X 0×X 0X_1 \to X_0\times X_0 and it would give us an equivalence relation — but since it isn’t, we can’t.

A pseudo equivalence relation could also be described as an “internal groupoid” but with no axioms imposed — or, better, as an internal 2-groupoid whose hom-categories are essentially discrete. With that in mind, you can define “functors” between such things, and these (modulo “natural transformations”) give the morphisms in the “exact completion” of our finitely complete CC. This is denoted C ex/lexC_{ex/lex}, to distinguish the fact that we are regarding the input CC as only finitely complete (i.e. “left exact” or “lex” for short).

This construction produces a left adjoint to the forgetful functor from exact categories to finitely complete ones. Since this forgetful functor is not full (a functor of exact categories must also preserve quotients, or equivalently regular epimorphisms), the exact completion of finitely complete categories is not idempotent. But as odd as this construction may seem (it certainly did to me at first), it is useful. For instance, the effective topos can be defined as the exact completion of a certain finitely complete category.

One pleasing property of exact completion (of either sort) is that it tends to make “weak” universal properties into “actual” universal properties. (Here “weak” refers to existence-but-not-uniqueness — again an unfortunate clash with the common higher-category-theory meaning of “up to isomorphism”!) For instance, suppose that CC has weak exponentials, in the sense that for any AA and BB there is an object FF and a map F×ABF\times A\to B such that for any map X×ABX\times A\to B, there exists a (not necessarily unique) map XFX\to F making the evident triangle commute. Then the exact completion of CC is cartesian closed: we can define exponentials by imposing a suitable (pseudo) equivalence relation on the weak exponentials in CC.

But this leads us into really weird territory, when we observe that the construction of the exact completion doesn’t actually require CC to have finite limits, but only weak finite limits. In particular, the notion of pseudo equivalence relation involves a pullback X 1× X 0X 1X_1\times_{X_0} X_1, but we can replace that by a weak pullback — roughly, because we only care about the “image” of X 1X 0×X 0X_1 \to X_0\times X_0, it doesn’t matter which weak pullback we use.

The exact completion of weakly finitely complete categories still defines a functor landing in exact categories, but this functor is not adjoint to the forgetful functor, no matter what class of functors we pick for the morphisms of weakly finitely complete categories. (The obvious choice is weak-finite-limit–preserving functors, which turn out to be the same as (representably) flat functors.) Instead, Carboni and Vitale proved that for weakly finitely complete CC and exact DD, the category of exact functors C ex/lexDC_{ex/lex}\to D is equivalent to the category of left covering functors CDC\to D. These are functors F:CDF\colon C\to D such that for any finite diagram GG in CC, the induced map F(limG)limF(G)F(\lim G) \to \lim F(G) is a regular epi in DD. What the heck?

You could say that the paper I’ve just posted today grew out of my deep dissatisfaction with this universal property.

The answer which makes me much happier is the following. There is a 2-category which contains weakly finitely complete categories and regular categories as two nearly disjoint full sub-2-categories. The sub-2-category of exact categories (sitting inside the sub-2-category of regular categories) is reflective, and when restricted to regular categories or to weakly finitely complete categories, the reflection becomes the two exact completions described above. Moreover, the morphisms in this larger 2-category from a weakly finitely complete category to an exact category are precisely the left covering functors.

In general, the objects of this bigger 2-category are a particular class of sites. The two sub-2-categories I mentioned come from equipping weakly finitely complete categories with trivial topologies (only split epis cover), and equipping regular categories with their regular topologies (all regular epis cover). In general, the sites that we allow have to satisfy two properties: first, that all their covering families are determined by single morphisms (such as “split epis” or “regular epis”), and second, that they have a sort of “weak finite limit relative to the topology”. For a trivial topology, this second condition is equivalent to ordinary weak finite limits; for nontrivial topologies it is a strictly weaker condition (and in particular is always satisfied by a site with finite limits).

I call sites satisfying these two conditions unary sites. The morphisms of unary sites are a slightly generalized version of the usual notion of “morphism of sites”, where we use a notion of flatness relative to the topology. I blogged about this kind of flatness last year.

This is nice enough, but it becomes even nicer when we realize that there is nothing particularly special about the number one. In fact, we can let κ\kappa be any regular cardinal, and define a κ\kappa-ary site to be a site whose covering families are determined by families of size <κ\lt\kappa and which has “weak finite κ\kappa-ary multi-limits relative to the topology”. Don’t worry about that latter condition at the moment; whatever it means, it gets weaker as κ\kappa gets bigger, until when κ\kappa reaches the size of the site itself it becomes automatic.

Similarly, we have a notion of κ\kappa-ary exact category, which has well-behaved quotients of “many-object equivalence relations” of size <κ\lt\kappa. This is equivalent to being exact in the unary sense plus having disjoint and universal coproducts of size <κ\lt\kappa. For instance, when κ=ω\kappa=\omega, an ω\omega-ary exact category is precisely a pretopos. And the same theorem is true: κ\kappa-ary exact categories are a reflective sub-2-category of κ\kappa-ary sites.

(The astute reader may have noticed that there is no regular cardinal κ\kappa such that κ\kappa-ary sites and exact categories reduce to unary ones. The closest we can get is κ=2={0,1}\kappa = 2 = \{0,1\}, which according to some definitions is a regular cardinal — but 22-ary sites can have empty covering families, and 22-ary exact categories must have initial objects. I dealt with this in the paper by letting κ\kappa be something a bit more general than a regular cardinal, which can also take the value “{1}\{1\}”.)

Finally, the very nice conclusion is that when κ\kappa is the “size of the universe” K\mathbf{K} (a “large regular cardinal”), then K\mathbf{K}-ary exactness becomes precisely the exactness conditions of Giraud’s theorem that characterizes sheaf toposes. Moreover, since K\mathbf{K} is large, any small site is K\mathbf{K}-ary, and therefore has a K\mathbf{K}-ary exact completion — which will no longer be small. In fact, the K\mathbf{K}-ary exact completion of a small site is precisely the category of sheaves on that site. And the universal property of this exact completion, as a reflection into a sub-2-category, reproduces precisely the classical theorem that the category of sheaves on a site is the classifying topos for flat cover-preserving functors.

One interesting possibility this raises is that if we start with a large K\mathbf{K}-ary site, then its K\mathbf{K}-ary exact completion could be regarded as a “category of small sheaves” on that site: it satisfies all the exactness properties of a sheaf topos, and has a similar universal property. (But in general it lacks a small generating set, is not cartesian closed or an elementary topos, and does not satisfy SAFT.)

I could go on and talk about how to construct the exact completion of a κ\kappa-ary site (it has three equivalent definitions, using either “profunctors” or “anafunctors” or “κ\kappa-sized sheaves”), but maybe I’ll stop here and let you read the paper. It has proarrow equipments, Cauchy completion, and even a coinductive definition!

Posted at March 21, 2012 3:12 AM UTC

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

15 Comments & 2 Trackbacks

Re: Exact completions and small sheaves

This looks really, really nice!

I haven’t read the paper closely yet, of course, but I think it answers a question I had a while ago about why realizability toposes arise as both exact completions and as categories of partial equivalence relations – both are obtained by splitting idempotents in (= adjoining Kleisli objects/collages to) an allegory and then taking the category of maps. Which I already believed, but I wasn’t sure how and at what level of generality to try and prove it.

Posted by: Finn Lawler on March 21, 2012 8:12 PM | Permalink | Reply to this

Re: Exact completions and small sheaves

Thanks!

…why realizability toposes arise as both exact completions and as categories of partial equivalence relations…

I don’t know a whole lot about realizability toposes, although I admit that one of my motivations for being interested in exact completion (and its categorifications) is a curiosity about whether there are “realizability higher toposes”. Is there a precise statement about realizability toposes and PERs that could be included as an example in the paper?

…splitting idempotents in (= adjoining Kleisli objects/collages to) an allegory…

This comment gives me an opportunity to remark on an aspect of the paper that I didn’t get to in the post. When translated into the world of allegories, the process of exact completion is traditionally expressed by splitting idempotents. But I think it is more appropriate to view it as adjoining Kleisli objects for monads. In a locally posetal 2-category, a monad is the same as a reflexive idempotent, and a Kleisli object is the same as a splitting. But in more general 2-categories, the concepts diverge, and it’s Kleisli objects for monads that are (I believe) the more interesting one. For instance, monads in SpanSpan are categories, and in ProfProf they are given Kleisli objects; but idempotents in SpanSpan are odd-looking beasts.

On the other hand, sometimes in an allegory one also wants to split non-reflexive idempotents. I believe this is one way that partial equivalence relations arise (the partiality comes from the non-reflexivity). But I have no idea how to categorify those.

Posted by: Mike Shulman on March 21, 2012 9:01 PM | Permalink | Reply to this

Re: Exact completions and small sheaves

I should have looked at my notes before mentioning Kleisli objects, because the idempotents that you split to get the category of pers of a tripos are the symmetric ones, which aren’t necessarily reflexive.

I don’t think I can give you a precise statement, but the general picture is that, starting with a partial combinatory algebra A, you either take the category of partitioned assemblies over A and then the ex/lex completion of that, or the realizability tripos associated to A and then the category of pers of that. The latter is the category of maps in the symmetric-idempotent splitting of the ‘framed allegory’ associated to the tripos.

If I recall correctly (this might be in Pieter Hofstra’s work), from a pca A you can form an indexed preorder Set(-,A) of sets over A and functions ‘tracked’ or ‘realized’ by an element of A, whose category of elements is that of partitioned assemblies over A. Alternatively, you can take the power set of A, which is again a pca, and do the same trick to get another indexed preorder, which is the realizability tripos over A. But I can’t say right now whether anything in that could reconcile the stuff in the previous paragraph with your paper.

Posted by: Finn Lawler on March 21, 2012 11:29 PM | Permalink | Reply to this

Re: Exact completions and small sheaves

Ah, I suspected that might be the case.

The splitting of symmetric idempotents in an allegory can be factored into splitting coreflexives (which, in an allegory, are automatically idempotent) and then splitting symmetric monads (= “equivalence relations”). If you split just the coreflexives in the framed allegory of the realizability tripos, do you get the framed allegory associated to the category of partitioned assemblies (with trivial unary topology)? If so, then it would explain why the further operation of splitting symmetric monads on each yields the same result.

Posted by: Mike Shulman on March 22, 2012 12:06 AM | Permalink | Reply to this

Re: Exact completions and small sheaves

I think if you split just the coreflexives then you get the category of assemblies, which is the reg/lex completion of the partitioned ones. (That’s what I have jotted down, but it’s a while since I’ve thought about this, and it still needs more work.)

Posted by: Finn Lawler on March 22, 2012 12:22 AM | Permalink | Reply to this

Re: Exact completions and small sheaves

Okay, well, that still works to show the equivalence, then, since the ex/reg completion of the reg/lex completion is the ex/lex completion. But I’m sure people who think about this stuff know all of that very well.

It feels as though the category of partitioned assemblies ought to be some sort of “free coproduct completion” of A, but only for “A-computable coproducts”. Is there any way to make sense of that?

Posted by: Mike Shulman on March 22, 2012 12:33 AM | Permalink | Reply to this

Re: Exact completions and small sheaves

If you mean a ‘“free coproduct completion” of Set’, then yes, indeed Robinson and Rosolini’s paper Colimit completions and the effective topos, JSL 55, 1990, is all about this. They say

The effective topos is the category obtained from the category of sets by first freely adjoining recursively-indexed coproducts (but being careful to preserve the empty set), and then adding quotients of (pseudo-)equivalence relations.

Posted by: Finn Lawler on March 22, 2012 2:36 AM | Permalink | Reply to this

Re: Exact completions and small sheaves

Hi Finn and Michael. It’s very interesting for me to see your discussion here since at the moment I’m writing my thesis on related things.

I think your last two posts (coproduct-cocompletion of A vs coproduct-cocompletion of Set) touch a central issue. As we see from the sentence that Finn cited, Robinson and Rosolini are thinking about partitioned assemblies as a “recursive-coproduct” cocompletion of Set, and consequently they see the effective topos as a category of “recursive presheaves on Set”. I think they were close, but at this point they weren’t quite right. Let me sketch my point of view.

  1. Carboni (“Some free constructions in proof theory and realizability”) showed that the presheaf construction on a small category with (weak) finite limits can be decomposed coproduct completion followed by exact completion.

  2. Robinson and Rosolini showed that the effective topos is the exact completion of partitioned assemblies.

  3. As Finn remarked, Hofstra (“All realizability is relative”) pointed out that the partitioned assemblies are the total category of the posetal fibration of families of natural numbers (more generally elements of the pca) where the fiberwise order relation is given by existence of a recursive function transforming one predicate into the other pointwise.

  4. The coproduct completion of a cartesian category is also a total category, namely of the family fibration of the category over Set.

  5. 1 and 2 only work in the presence of choice! This is interesting not only for constructivists but also for people who want to do topos theory on arbitrary bases.

  6. Without choice, we can not reconstruct the target categories from the total categories via the exact completion any more, but we can reconstruct them from the fibrations, using a construction I call the “fibred presheaf construction”, described in these slides: http://www.pps.jussieu.fr/~frey/li2012.pdf

  7. My reading of this is that we shouldn’t view the family construction as coproduct cocompletion in this context but rather as representation of a category in the fibrational world. The fibred poset from 3 should simply be viewed as generalized poset induced by a pca, and the effective topos (or rather the fibration obtained by glueing along Δ:SetEff\Delta:\mathrm{Set}\to\mathrm{Eff}) should be viewed as presheaf category/fibration on this generalized poset (I think this is close to what Michael wrote). This can be made precise by giving universal properties (in the slides).

  8. Interestingly, the fibred presheaf construction also gives an alternative description of the category of small presheaves on a possibly large category with finite limits: take the family fibration and apply the fibred presheaf construction. Thus the construction should more appropriately be called “fibred small presheaf construction”.

  9. Deviating a bit from the main line of thought, if we want to understand what goes wrong with Carboni’s decomposition (in 1) in the constructive context, one possibility of seeing it is that the distributive law between the monads for exact completion and coproduct completion is not definable without choice.

Posted by: Jonas Frey on March 22, 2012 10:11 AM | Permalink | Reply to this

Re: Exact completions and small sheaves

Unary topologies can replace choice in the construction of a realizability topos out of the category of partitioned assemblies. What we need is the following: let E be an exact category and let P be a dense subsite (restrict the regular topology etc.). Then E is the exact completion of P. This looks like a special case of Theorem 11.8. The dense subsite is the category of partitioned assemblies where the unary topology is the class of morphisms that are realized to be surjective.

Posted by: Wouter Stekelenburg on March 22, 2012 11:20 AM | Permalink | Reply to this

Re: Exact completions and small sheaves

That’s interesting, I wasn’t aware of this.

So apparently the fibred presheaf construction on a pre-stack can be expressed as applying Michael’s construction to the total category equipped with the unary topology generated by the epicartesian morphisms (cartesian maps over regular epis).

Posted by: Jonas Frey on March 22, 2012 12:48 PM | Permalink | Reply to this

Re: Exact completions and small sheaves

Is this related to Hofstra’s construction in Relative completions (JPAA 192, 2004)?

Posted by: Finn Lawler on March 22, 2012 4:10 PM | Permalink | Reply to this

Re: Exact completions and small sheaves

Finn, thanks for mentioning Hofstra’s paper! I wasn’t aware of it, but it looks like his “quasi-topologies” are exactly my “unary topologies” (in the finitely complete case), and his construction is a particular case of the unary regular completion. I’ll be sure to include a reference to it in my paper.

Posted by: Mike Shulman on March 22, 2012 9:31 PM | Permalink | Reply to this

Re: Exact completions and small sheaves

First a side note to everyone: the nCafe software has the feature that when you reply to a comment, your comment gets indented an extra level from the one you were replying to. This is useful in a discussion with many branching threads, but for a lengthy linear discussion it tends to cause a large accumulation of those vertical lines on the left side. The trick to avoiding this is that if you’re continuing a linear discussion, click “Reply to this” not on the last comment in that discussion, but on the comment that it was a reply to; you can find this by scrolling up until there is one fewer vertical line on the left side. (However, if you’re replying to an old post in the middle of a discussion, then it’s sometimes appropriate to reply directly to that post so that your comment appears immediately after it rather than at the bottom.)

Now: I want to thank you very much, Finn, for reminding me of the Robinson-Rosolini paper! It’s not what I had in mind up here, but last night I realized that it really points the way to unify the construction in my paper with constructions in realizability. Reading Jonas’s and Wouter’s thoughts this morning has only confirmed that.

Let κ\kappa be an arity class. (For those who haven’t read the paper yet, this is the “generalization of a regular cardinal” I mentioned.) Then we have a category Set κSet_\kappa of κ\kappa-small sets and all functions between them. The axioms of an arity class ensure that Set κSet_\kappa is closed under finite limits in SetSet (and not much more). Now all the definitions of κ\kappa-ary sites, κ\kappa-ary exact categories, and κ\kappa-ary exact completion utilize only κ\kappa-small families of objects and morphisms, and therefore can be phrased elementarily in terms of Set κSet_\kappa-indexed categories.

More generally, let KK be any finitely complete category. Then there is a notion of a KK-ary site, which we can get by taking the notion of κ\kappa-ary site, rephrasing it in terms of Set κSet_\kappa-indexed categories, and replacing Set κSet_\kappa by KK everywhere. Interestingly, it appears that a KK-ary site is equivalent to a fibration over KK together with a unary topology on the total category of the fibration. The total category, of course, is part of the free cocompletion under KK-indexed coproducts (the actual such cocompletion is another KK-indexed category). If KK is itself a site (such as a topos or a regular category), then we may want to require a KK-ary site to be a stack or a prestack, in which case we should also require the topology to satisfy a descent condition.

Now we should be able to perform the KK-ary exact completion of a KK-ary site, obtaining a KK-ary exact category — either by mimicking the construction of my paper in the KK-indexed world, or by first performing the KK-indexed coproduct completion (i.e. the total category of the fibration) and then the unary exact completion of that unary site. (I chose not to “factor” the exact completion in this way in my paper, because it introduces an extra level of β\beta-reduction when you try to extract an explicit description of the objects of the exact completion, but of course it works just as well to do it that way.) Moreover, since part of the notion of “KK-ary exact category” will be disjoint and universal KK-indexed coproducts, by Moens’ theorem (mentioned in Jonas’ slides) the KK-ary exact completion can equivalently be considered as a category equipped with a functor out of KK.

Now I believe that:

  • When K=Set κK=Set_\kappa, this reproduces the κ\kappa-ary exact completion from my paper.

  • In particular, when K=SetK=Set (with choice) and the fibration corresponds to a small category, it constructs the presheaf category. This looks like Jonas’s (1).

  • When KK is the category of subsets of \mathbb{N} with partial recursive functions, as in the Robinson-Rosolini paper, and our KK-indexed site is the naive indexing of SetSet with the topology that is trivial except that “the empty set is covered by the empty family” (or the category of inhabited sets with the trivial topology), then it reproduces the Robinson-Rosolini construction of the effective topos.

  • When KK is regular and our KK-indexed site has the smallest possible topology that satisfies descent along regular epis in KK (an indexed sort of “trivial topology”), then it reproduces Jonas’s “fibered presheaf construction”.

In other words, we can view the realizability topos of a PCA AA as either

  • The AA-ary exact completion of SetSet (with this slightly odd topology) or Set >0Set_{\gt 0} (with the trivial topology), or

  • The SetSet-ary exact completion of AA (regarded as a SetSet-indexed poset as in Jonas’s (3), with trivial topology).

In the second point of view, which seems to be more traditional, we view the functor Δ:SetEff\Delta \colon Set \to Eff as analogous to the “constant sheaf” functor (the inverse image part of a geometric morphism to SetSet). In the first point of view, which is that of the Robinson-Rosolini paper, we instead view Δ:SetEff\Delta \colon Set \to Eff as analogous to the sheafified Yoneda embedding of a site into its sheaf topos.

I don’t immediately see a reason why these two constructions should give the same result, but there is a pleasing symmetry that suggests the existence of a reason. It also suggests that by replacing SetSet with some other site, we could obtain categories that combine realizability with Grothendiecky sheaves.

Posted by: Mike Shulman on March 22, 2012 4:25 PM | Permalink | Reply to this

Re: Exact completions and small sheaves

This is starting to look like a lot of fun! But it will take me at least a fair while before I can understand most of it.

I had been wondering for some time whether it would be possible to treat realizability/H-set constructions and sheaf-topos constructions in the same sort of framework, so it’s really exciting to see several people converge on the same question from different directions.

Posted by: Finn Lawler on March 22, 2012 11:27 PM | Permalink | Reply to this
Read the post Postulated colimits and absolute colimits
Weblog: The n-Category Café
Excerpt: Absolute colimits, those which are preserved by any functor, are a special case of Anders Kock's notion of "postulated colimit."
Tracked: May 14, 2012 6:46 PM
Read the post Superextensive sites
Weblog: The n-Category Café
Excerpt: "Superextensive sites" allow us to replace covering families by singleton covers... sometimes.
Tracked: May 21, 2012 6:18 AM

Re: Exact completions and small sheaves

The final version of this paper has now appeared in the CT2011 proceedings volume of TAC. The main improvement over the first version, aside from various corrections and improvements thanks to the referee, is a discussion of the relationship of this sort of exact completion to Kock’s postulated colimits and Garner-Lack’s “lex-colimits”.

Posted by: Mike Shulman on September 5, 2012 8:02 PM | Permalink | Reply to this

Post a New Comment