Michael Shulman 2-categorical logic collated

The internal logic of a 2-topos (one-page version)

This page is a collected version that includes most of the sub-pages about 2-categorical logic, for ease of printing. Keep in mind that everything here is rough, much is missing, and not all of the pages were designed to be read sequentially, so you may have to skip around.

What is a 2-topos?

Of course, a 2-topos is the 2-categorical version of a topos. In other words, it is a (vertically) categorified topos. However, as we know, categorification, like quantization and groupoidification, is an art rather than a science; it depends on deciding what the crucial properties are of the thing we want to categorify.

The problem is especially acute for toposes, because of their many-faceted nature. To speak figuratively, which attributes of an elephant do we want to categorify? It isn’t even necessarily clear that there is a single beast which decategorifies to all the aspects of an elephant at once; perhaps we have 2-legs, 2-trunks, 2-ears, 2-tails, and so on but no actual 2-elephant.

According to WeberYS2T,

This is evidently a categorification of a definition such as

On the other hand, according to StreetCBS,

  • a 2-topos is a 2-category which is equivalent to the 2-category of stacks (2-sheaves) on some 2-site.

This is evidently a categorification of a definition such as

  • a topos is a category which is equivalent to the category of sheaves on some site.

The definition I propose to categorify is

Of course, this definition contains a good deal of redundancy, but not all of that was apparent in the early days of topos theory, and there seems less reason to believe that the redundancy will remain under categorification. Moreover, for the purposes of logic, having a Heyting pretopos is the most important part of the definition; it is what enables the internal interpretation of first-order logic. (Local cartesian closure and a subobject classifier then enable the interpretation of higher-order logic.) It may be simply an accident that in the 1-categorical case, the higher-order structure automatically implies the first-order structure.

Thus, in order to obtain an internal logic of a 2-category, it is natural to start with a notion of Heyting 2-pretopos. This is especially attractive because it is less clear how to categorify the “higher-order structure” of local cartesian closure and a subobject classifier. The 2-category Cat, which one expects to be the prototypical 2-topos just as Set is the prototypical topos, does not have a subobject classifier, nor is it locally cartesian closed (though it is cartesian closed). What is true is that fibrations are exponentiable, and that it has objects (namely, full subcategories of SetSet) that classify some discrete opfibrations.

Another guiding desideratum for us will be that all the notions we consider should be stable under slicing, just like the corresponding 1-categorical notions. For instance, this demands the upgrading of ordinary cartesian closure to some sort of local cartesian closure. However, in the 2-categorical case it turns out that usually the correct notion to consider is not the slice 2-category but rather the fibrational slice.

Thus, the proposed definition we will arrive at will be something like:

  • an (elementary) 2-topos is a finitely complete and cocomplete Heyting 2-pretopos with exponentials and (some sort of discrete opfibration classifier).

The goal, again, is to find a notion of 2-topos that has an internal logic in which we can reason about categories. Street’s “Grothendieck 2-toposes” turn out to have (almost) all of these properties of an “elementary 2-topos.” The intersection of this notion with Weber’s consists of finite limits, cartesian closure (strictly weaker than our notion of “exponentials”), and a discrete fibration classifier. While some of our 2-toposes admit duality involutions, others (perhaps surprisingly) do not.

On the meaning of ‘categorified logic’

In talking about 2-toposes and classifying discrete opfibrations it is common to hear people talk about “the category of sets being a generalized object of truth values,” or more loosely of “treating sets as truth values.” (See, for instance, the discussion at this post.) The idea, of course, is that just as the functor

XSub(X)X\mapsto Sub(X)

from SetSet (or any topos) to posets is representable by the set Ω\Omega of truth values, the functor

XDOpf(X)X\mapsto DOpf(X)

from CatCat (or, hypothetically, any 2-topos) to categories is representable by the category SetSet of sets. Here DOpf(X)DOpf(X) means the category of discrete opfibrations over XX.

My current opinion is that there already exists a “logic which treats sets as truth values,” without the need for any categorification, namely type theory (more precisely, dependent type theory). It is central to categorical logic (although not always presented in this way) that the internal logic of a category CC actually takes place in the fibration XSub(X)X\mapsto Sub(X) of subobjects of objects of CC. In particular:

  • The Heyting algebra operations in each poset Sub(X)Sub(X) correspond to the logical connectives ,,,,,¬\wedge,\vee,\top,\bot,\Rightarrow,\neg.
  • The reindexing functors f *:Sub(Y)Sub(X)f^*:Sub(Y)\to Sub(X) correspond to logical substitution, weakening, and contraction.
  • Left adjoints to reindexing functors correspond to existential quantification.
  • Right adjoints to reindexing functors correspond to universal quantification.

The fact that the resulting logic is a “logic of truth values,” or as I would say a “logic of (-1,0)-categories,” depends on each Sub(X)Sub(X) being a poset; that is, a (0,1)-category. However, for an ordinary category CC we also have a fundamental fibration XC/XX\mapsto C/X of 1-categories, which has a corresponding “logic of 0-categories,” that is, sets. If CC is (for instance) a locally cartesian closed category with finite colimits, then each C/XC/X is a cartesian closed category with finite colimits (the 1-categorical analogue of a Heyting algebra) and the reindexing functors have left and right adjoints.

Now, instead of interpreting these operations as acting on logical statements that are either true or false, we interpret them as acting on types which can be inhabited or empty, but if inhabited can contain many different elements. For instance, instead of constructing a new proposition φψ\varphi\wedge\psi from propositions φ\varphi and ψ\psi, we construct a new type A×BA\times B from types AA and BB. And instead of constructing a new proposition (xA)φ(x)(\forall x\in A)\varphi(x) from a proposition φ\varphi that depends on a variable xx, we construct a new type Π xAB(x)\Pi_{x\in A} B(x) (a “dependent product”) from a type B(x)B(x) that depends on xx.

There are several different ways of thinking about this. From one perspective, we can think of these types as merely “souped up” versions of propositions that record not only whether something is true, but all the “ways” in which it can be true or all the “proofs” that it is true. Thus, our real interest is in whether a given type is inhabited or not, which is a close generalization of whether a given proposition is true. I believe this is often called the propositions as types paradigm.

On the other hand, we can treat the types as sets whose different elements we may care about, and it is from this perspective that I want to view it. In this case, we may also want to say things about the elements of those sets, which is to say, we also need a logic (of propositions) on top of our type theory (the “logic of sets”). This construction of a “logic over a type theory” is very common in type theory, and seems to be the generally accepted way to develop the internal logic of a Π\Pi-pretopos. From an nn-categorical point of view, what we have is a 1-category in which we have both a “logic of 0-categories” (type theory) that takes place in the slice categories C/XC/X and a “logic of (-1,0)-categories” (ordinary logic) that takes place in the slice posets Sub C(X)Sub_C(X).

It is now clear how to categorify this: in a 2-category KK we will have a “logic of 1-categories” that takes place in the slice 2-categories K/XK/X, a “logic of 0-categories” that takes place in the slice 1-categories disc(K/X)disc(K/X), and a “logic of (-1,0)-categories” that takes place in the slice posets Sub K(X)Sub_K(X). (Actually, we could easily add logics of (1,0)-categories and (0,1)-categories taking place in gpd(K/X)gpd(K/X) and pos(K/X)pos(K/X), respectively, but this doesn’t seem to be as useful.) The only possibly-unexpected wrinkle is that it turns out to be best to ues the fibrational slices Fib K(X)Fib_K(X) and Opf K(X)Opf_K(X) in place K/XK/X whenever possible.

From this perspective, it is evident that in “categorified logic” (at least as I conceive it) sets do not replace truth values. Rather, sets, and categories as well, have their own “logic” (aka “type theory”) which happens “underneath” the logic of truth values. The goal is that just as existing mathematical arguments involving sets can be formalized in the internal logic of a 1-topos, existing mathematical arguments involving categories should be formalizable in the internal logic of a 2-topos — and, empirically speaking, these arguments involving categories still use the same sort of (truth-valued) logic that arguments involving sets do. The only difference is that they involve categories (1-types) in addition to sets (0-types) and truth values ((-1)-types).

Something that would help me enormously (personally and convincing other philosophers) would be a concrete example to work with. It would be especially interesting if this could be in ‘natural language’, like my poodle example for 1-logic.

Perhaps an example from dependent type theory would do: During every month there exists a team for which there exists a day in that month on which every player on that team is fit.

It would be nicer though to have the meta-types be non-discrete categories.

You could try the following paper by Isar Stubbe: The canonical topology on a meet-semilattice which explicitly goes from Omega to Sets.

2-categorical conventions

In line with the rest of the nLab, 2-category means weak 2-category, or precisely bicategory. All notions such as limits, adjunctions, equivalences, and so on are understood in a suitably weak sense (without need for a prefix such as “bi-”). Note that without choice, even Cat is not a strict 2-category, since we must use anafunctors instead of functors; see regular 2-categories and choice.

If X has a meaning for 1-categories, then if X is used without a prefix for 2-categories it should include the existing notion for 1-categories as a special case (when 1-categories are considered as homwise-discrete 2-categories). If we consider a notion related to X but which is not a “conservative categorification” in this sense, we will call it 2-X; cf. subcategory. For instance, we say regular 2-category since a 1-category is regular as a 2-category iff it is regular as a 1-category, but 2-exact 2-category since an exact 1-category is almost never 2-exact as a 2-category.

nn-categories for n2n\le 2

In many cases it turns out to be just as easy to develop the theory not just for 2-categories, but for (s,r)(s,r)-categories for some 0s20\le s\le 2 and r>0r\gt 0. We will say that n2n\le 2 and nn is directed to mean that n=(s,r)n=(s,r) for some such s,rs,r. This includes the following cases:

2 = (2,2)
of course, a 2-category is just a 2-category
(2,1)
A (2,1)-category is a 2-category all of whose 2-cells are invertible, such as Gpd.
(1,2)
A (1,2)-category is a 2-category in which any two parallel 2-cells are equal, such as Pos.
1 = (1,1)
A 1-category is a 2-category in which any two parallel 2-cells are equal and invertible; that is, a 2-category which is both a (2,1)-category and a (1,2)-category. This means its hom-categories are equivalent to discrete sets, so it can be identified with a 1-category in the usual sense.
(0,1)
A (0,1)-category is a poset, or more precisely a preordered set.

The following values of n=(s,r)n=(s,r) are considered 2\le 2, but are not directed.

(2,0)
A (2,0)-category is a 2-groupoid: a 2-category in which all 2-cells are isomorphisms and all 1-cells are equivalences.
(1,0)
A (1,0)-category is a groupoid.
0=(0,0)
A 0-category is a set (or a category, or 2-category, that is equivalent to one).
-1 = (-1,0)
A (-1,0)-category is poset in which any two objects are isomorphic; thus it is a truth value (the truth value of “there exists an object”). Since there is no useful notion of (-1,-1)-category, (-1,0)-categories are often called (-1)-categories and we will sometimes use this convention.
-2 = (-2,-1)
A (-2,-1)-category is an inhabited (-1,0)-category; that is, it is the truth value “true.” As with (-1)-categories, (-2,-1)-categories are often called simply (-2)-categories.

These values of nn are also important, but for them one doesn’t expect a notion of nn-topos, nor of regularity, exactness, extensivity, or an internal logic. For instance, a nontrivial groupoid has no limits, so it certainly cannot be regular.

Actually, I’ve been mildly surprised not to see you use these values of nn. Sure, the concepts tend to be trivial then, but so they also tend to be when n<0n \lt 0.

And actually, I don't think it's appropriate to refer to n<0n \lt 0 as ‘directed’. Directedness is provided only by r>0r \gt 0.

—Toby

You’re right about directedness; I’ve fixed the page. What sort of “use” of nondirected nn were you expecting? They do come up, of course; for instance it’s important to talk about nn-truncated objects when nn is not necessarily directed. The only point is that no nontrivial nn-categories can be regular, exact, coherent, etc. unless nn is directed.

I guess it might be useful to distinguish nn-truncated 2-toposes even when nn is not directed. For instance, 0-truncated (Grothendieck) 2-toposes are just powers of CatCat, and (1,0)-truncated 1-toposes are toposes of actions by a groupoid. But you can’t say any more that an nn-truncated 2-topos is the category of 2-sheaves on an nn-topos, since there is no longer any notion of nn-topos.

I incorporated your other comments into the text. -Mike

By ‘use’ I meant at a minimum ‘mention’. That is, remark that no groupoid is regular, etc. Mind you, I've been only mildly surprised not to see this (and such surprise as I had came in part because you sometimes did mention n0n \leq 0); I like to mention degenerate cases, but I know that others don't. Possibly we can regard the paragraph above as covering it now. —Toby

We adopt the natural convention that (s,r)±1=(s±1,r±1)(s,r)\pm 1 = (s\pm 1,r\pm 1). Thus, for instance, saying that nn-categories form an (n+1)(n+1)-category includes the statements that:

  • sets form a 1-category
  • categories form a 2-category
  • groupoids form a (2,1)-category
  • posets form a (1,2)-category
  • truth values form a poset

and so on. For this convention it is important to remember that (-1)-category is a shorthand for (-1,0)-category, so that (1)+1=(0,1)(-1)+1 = (0,1), not (0,0). And of course, (2)+1=(1)(-2)+1=(-1). Note that nn is directed if and only if it is of the form m+1m+1 for some m(1,0)m\ge (-1,0).

Note that (s,r)(s,r)-categories are the same as (s,r)(s,r')-categories whenever either r,rs+1r,r'\ge s+1 or r,r0r,r'\le 0. (Although for monoidal categories, r=1r=-1 and r=0r=0 can be distinguished.) Thus, to avoid duplication, usually one restricts to 0rs+10\le r\le s+1. However, these requirements conflict when s=2s=-2 (which is something of a special case in other ways as well). We choose -2 to mean (-2,-1) so that we obtain (-1,0) upon adding 1 to it, although (-2,0) would work just as well as long as we remember that (0,2) and (0,1) are the same. Thus, our general restriction on rr and ss is min(0,s+1)rs+1min(0,s+1) \le r \le s+1.

Discussion

From a previous discussion at truncated object, which doesn't really belong there:

Yes, definitely. A so called ‘1-1-category’ (a truth value) is really a 1-1-groupoid or a 00-poset, that is a (1,0)(-1,0)-category, not a (1,1)(-1,-1)-category (which doesn't really make sense) at all. As you know. —Toby

Yeah. But (-1,0)-category is cumbersome to say when there is no different notion of (-1)-category that it needs to be distinguished from. (-: And it seems to break down at (-2) anyway; for the adding-one convention to continue to work we should write (-2,-1)-category instead of (-2)-category, but that doesn’t make sense in the general scheme of (n,r)-category. I suppose we could decide to write (n,)(n,\infty) instead of (n,n+1)(n,n+1) in all cases… -Mike

Partly, this would work better if we said ‘nn-poset’ all the time for various values of nn. In general, an (r,s)(r,s)-category is an (r+1,s)(r+1,s)-poset. The bad part is that now these pages focus on n(3,2)n \leq (3,2), which is not so slick to say. But the general theory works better; we require 0sr0 \leq s \leq r (with the same exception as before, now when r=1r = -1) and no glitch crossing from 1-1 to 2-2. —Toby

I suppose so, but I don’t think you’ll have much luck trying to get people to say “(3,2)-poset” instead of “2-category.” (-: -Mike

Nothing wrong with ‘22-category’, ‘22-groupoid’, etc as abbreviations, but we shouldn't lose sight of the fundamental concept. (Similarly, wasn't someone trying to come up with a general name for (n,1)(n,1)-category?) —Toby

What are you claiming is the “fundamental concept?” The only candidates for a fundamental concept that I see are either full-blown ω\omega-categories or (s,r)(s,r)-categories for arbitrary s,rs,r. The only remaining question is terminology, and I think saying that “2-category” is an abbreviation for “(2,2)-category” is much more likely to catch on than saying that it is an abbreviation for “(3,2)-poset.” (In fact, it has already caught on.) In particular, there is a virtue to continuing to use the word “category,” which communicates the behavior of these things much better than “poset.” Already I think “(1,2)-category” is a more descriptive name than “2-poset.” -Mike

I agree with Toby that one should say “(r+1,s)(r+1,s)-order” (I don’t use “poset”, since this word suggests that they have a set of objects) rather than “(n,r)(n,r)-category” and even VV-order instead of VV-category, because the word “category” carries the further meaning that there is some groupoidality (the homs are groupoidal orders in a category). For this reason, I think that “order” conveys better the general behaviour than “category”. The most fundamental concepts, for me, are the nn-orders, which are the most general ω\omega-orders of dimension nn. The study of higher-dimensional toposes would perhaps be more natural if the reference cases were modelled on Ord and 2-Ord rather than Set and Cat. —Mathieu

I disagree that “category” carries the meaning of groupoidality in the homs. I suppose it can mean whatever you choose it to mean, like Humpty Dumpty, but there is nothing in the past usage of the word “category” to suggest such an implication. Just because nn-categories, for natural numbers nn, happen to have homs that are groupoidal at the top dimension for which they have unequal parallel morphisms doesn’t mean that “category” necessarily implies such groupoidality. If in addition to 2-categories we allow (2,1)-categories then (2,3)-categories are just as natural. The existing meaning of VV-category includes categories enriched over orders (= (1,2)-categories) and categories enriched over truth values (= (0,1)-categories); why not allow “category” its existing, more inclusive, meaning?

Also, even in an nn-order (= (n1,n)(n-1,n)-category) there is some groupoidality; it just doesn’t kick in until the (n+1)(n+1)-cells. To me, a much stronger intuitive association is that “order” implies that parallel morphisms are equal. This is not true for nn-orders for any n>1n\gt 1, except at the nn-cells, and is not true for any dimension of cells in an ω\omega-order (= ω\omega-category). -Mike

My use of the phrase ‘fundamental concept’ was tongue in cheek, since (as you point out) it is the same concept. At best, one can say that the partial function from Z×Z\mathbf{Z} \times \mathbf{Z} to properties of \infty-categories that maps (s,r)(s,r) to being an (s,r)(s,r)-poset (or (s,r)(s,r)-order) is simpler (hence should be regarded as more fundamental, with the other defined in terms of it) than the partial function that maps (s,r)(s,r) to being an (s,r)(s,r)-category. Certainly the domain of the first partial function is nicer. So if we were inventing terminology afresh for the whole business, we would probably want to base it on that function. Even in the real world, where I titled an article (n,r)-category, one should talk about (s,r)(s,r)-posets when that helps explain a pattern.

Also, we're not going to get anywhere talking about the limiting connotations that various words have. Of course ‘category’ has the connotation of being groupoidal at and above level 22, since an ordinary category is groupoidal at and above level 22; and ‘order’ and ‘poset’ have the connotation of being trivial at and above level 22, since an ordinary order or poset is trivial at and above level 22. (But I don't see what's wrong with the connotation that a poset has an underlying set, since even an \infty-poset has an underlying set of equivalence classes of objects.) Any terminology that we choose to generalise will have limiting connotations from its previous use.

I think this is the last I'll say on the matter; it's not like I'm not trying to get Mike to renumber his work here.

—Toby

Regularity without choice

The 1-category SetSet is a 1-topos, and in particular regular, without any need for the axiom of choice, or indeed even any need for classical logic. Even predicativists generally agree that SetSet is a pretopos.

However, at first glance, the axiom of choice seems to be necessary in order for CatCat to be a regular 2-category. Specifically, given a commutative square of functors

A f C e m B g D\array{A & \overset{f}{\to} & C\\ e \downarrow && \downarrow m\\ B& \underset{g}{\to} & D}

in which mm is full and faithful and ee is essentially surjective, in order to define a lift h:BCh:B\to C we have to first choose, for each bBb\in B, an object a bAa_b\in A and an isomorphism e(a b)be(a_b)\cong b, then defining h(b)=f(a b)h(b)=f(a_b) with its action on morphisms determined by gg (since mm is ff).

Of course, there is a sense in which this is not a “real” use of choice, since f(a b)f(a_b) is determined by bb up to unique isomorphism. It is well-established that in the absence of choice, the usual notion of functor is too strict, and one should instead use anafunctors which determine their values only up to unique isomorphism. And it is not hard to check that if we define CatCat to be the (no longer strict) 2-category of categories, anafunctors, and natural transformations, then it is regular, and in fact a 2-pretopos, without any need for choice.

Discussion on cartesian closure

Toby: Something to consider: In Makkai's paper on anafunctors, he needs a (fairly weak) form of the axiom of choice to conclude that the bicategory of categories, and anafunctors, and ananatural transformations is cartesian closed. Maybe the right notions of exponentials don’t require even this.

Mike: Interesting point! Of course, in the absence of choice, one has to use anafunctors in order for CatCat to even be a regular 2-category, so this is an important question. However, it seems to me that his proof actually shows that without any choice at all, CatCat (his AnaCatAnaCat) is cartesian closed in the sense that there is an anaequivalence Cat(A×B,C)Cat(A,C B)Cat(A\times B,C) \simeq Cat(A, C^B), and this is all one ought to need or want. Am I wrong?

Toby: But without that SCSA thing, I don't know what C BC^B means in this context. That is, the category of small anafunctors from a small category BB to a small category CC is not itself small (at least not if BB is inhabited), and Makkai uses SCSA to prove the existence of an equivalent small category.

Now that I look at this stuff closely again, it seems unlikely to shed much light on the matter here. But there it is.

Mike: If you trace through his proof, it seems to me that what he really shows is that (without any choice) any anafunctor XAX\to A is isomorphic to one whose set of specifications is of the form

(x,a)SIso(a,a)\coprod_{(x,a)\in S} Iso(a,a)

for some SOb(X)×Ob(A)S\subset Ob(X)\times Ob(A). And there is clearly a set of these, so the full subcategory of Cat(X,A)Cat(X,A) on them should be an exponential A XA^X in CatCat.

You only need choice if you want there to be a function assigning to each anafunctor XAX\to A an isomorphism to one of the above form. And you can avoid using the full strength of choice by allowing yourself to replace Iso(a,a)Iso(a,a) by anything in some specified set of sets that are isomorphic to it.

Mike: No, what I said in the previous comment is wrong! What’s true is that for any saturated anafunctor FF, the set |F|(x,a){|F|}(x,a) of specifications from xx to aa is, if inhabited, isomorphic to Iso(a,a)Iso(a,a). However, that isomorphism is non-canonical (to be precise, |F|(x,a){|F|}(x,a) is a torsor over Iso(a,a)Iso(a,a)). Thus, in order to to replace your anafunctor by one whose set of specifications is of the above form, you need to choose simultaneously, for every xx and aa such that |F|(x,a){|F|}(x,a) is inhabited, an isomorphism |F|(x,a)Iso(a,a){|F|}(x,a)\overset{\cong}{\to} Iso(a,a), and that requires some choice. Where SCSA is weaker than AC is that you don’t need to be able to choose isomorphisms to Iso(a,a)Iso(a,a), you just need to be able to choose isomorphisms to something such that there is at most a set of targets of the somethings, and that’s enough to make the category of anafunctors essentially small.

Right now I feel as though even in the absence of choice, CatCat “ought” to have all these good properties, including cartesian closure. If anafunctors aren’t good enough to recover all of that without some form of choice, then maybe that just means that even with anafunctors, set-theoretic foundations just aren’t fully capable of mimicking truly categorial foundations.

David Roberts: Clearly WISC has some bearing here (and probably the kernel of the idea originated from this discussion). Is there a 2-categorical form of WISC? Is it useful? I suppose this depends on the analogue of what is considered 'small' in the 2-logic

Slice 2-categories

The slice 2-category of a 2-category KK over an object XX is the 2-category whose objects are morphisms AXA\to X in KK, whose morphisms are triangles in KK that commute up to a specified isomorphism, and whose 2-cells are 2-cells in KK forming a commutative 2-diagram with the specified isomorphisms in triangles.

In particular, any 2-cell in K/XK/X must become an isomorphism in XX. This means that more information is lost when passing to slice 2-categories than for slice 1-categories, and slice 2-categories are not always well-behaved; they often fail to inherit useful properties of KK. Frequently a better replacement is the fibrational slice.

Pullbacks and adjoints

If KK has pullbacks, then for any f:XYf:X\to Y there is a pullback functor f *:K/YK/Xf^*:K/Y\to K/X. However, this does not make the assignation XK/XX\mapsto K/X into a functor K opCatK^{op}\to Cat or K coopCatK^{coop}\to Cat, since there is no way to define it on 2-cells. This is one reason to use fibrational slices instead.

Just as in the 1-categorical case, the pullback functor f *:K/YK/Xf^*:K/Y\to K/X always has a left adjoint Σ f:K/XK/Y\Sigma_f:K/X\to K/Y given by composition with ff. However, f *f^* cannot be expected to have a right adjoint Π f\Pi_f for all maps ff, since this fails even in CatCat. It is true in CatCat when ff is a fibration or opfibration, however; see exponentials in a 2-category.

Fibrational slices

Definition

The fibrational slice of a 2-category KK over an object XX is the homwise-full sub-2-category Fib(X)Fib(X) of the slice 2-category K/XK/X whose objects are fibrations over XX and whose morphisms are morphisms of fibrations. Likewise, we have the opfibrational slice Opf(X)Opf(X) consisting of opfibrations.

The fibrational and opfibrational slices in a 2-category often play the role of the ordinary slice categories of a 1-category, replacing the ordinary slice 2-category. On this whole page we assume that KK has finite limits.

Basic properties

The 2-category Opf(X)Opf(X) is monadic over K/XK/X. The relevant monad on K/XK/X takes p:AXp:A\to X to the comma object (p/1 X)(p/1_X), or equivalently the pullback A× XX 2A\times_X X ^{\mathbf{2}} . It is lax-idempotent, so a morphism p:AXp:A\to X is an opfibration if and only if A(p/1 X)A\to (p/1_X) has a left adjoint with invertible counit in K/XK/X. Likewise, pp is a fibration iff A(1 X/p)A\to (1_X/p) has a right adjoint with invertible unit in K/XK/X.

Since the fibrational slices are monadic over K/XK/X, they inherit all limits from it. It follows that a fibration is a discrete object in Fib(X)Fib(X) iff it is discrete in K/XK/X. These are unsurprisingly called discrete fibrations; we write DFib(X)DFib(X) for the category of such. Every morphism in K/XK/X between discrete fibrations is a morphism of fibrations; thus DFib(X)DFib(X) is a full subcategory of both Fib(X)Fib(X) and K/XK/X.

Any pullback of an (op)fibration is again an (op)fibration. Therefore, any morphism f:YXf:Y\to X induces a pullback functor f *:Fib(X)Fib(Y)f^*:Fib(X)\to Fib(Y), which restricts to a functor f *:DFib(X)DFib(Y)f^*:DFib(X)\to DFib(Y), and dually. Regarding the existence of adjoints to these functors, see comprehensive factorization and exponentials in a 2-category.

Any morphism with groupoidal codomain is a fibration and opfibration. Therefore, if XX is groupoidal, Fib(X)K/XOpf(X)Fib(X)\simeq K/X\simeq Opf(X). In particular, for (2,1)-categories and thus also for 1-categories, the fibrational slices are no different from the ordinary slices.

Subobjects

Central for us is the following fact, which would be false if we replaced Opf(X)Opf(X) by K/XK/X. It underlies the inheritance of all sorts of structure by fibrational slices, such as regularity, coherency, extensivity, and exactness.

Theorem

A morphism in Opf(X)Opf(X) is ff in Opf(XOpf(X) iff its underlying morphism in KK is ff.

Proof

Suppose that a:AXa:A\to X and b:BXb:B\to X are opfibrations, and that f:ABf: A\to B is a morphism in Opf(X)Opf(X) which is ff in KK. Then since Opf(X)KOpf(X)\to K is homwise faithful, ff is clearly faithful in Opf(X)Opf(X). And given a 2-cell α:hk:TB\alpha: h\to k:T\rightrightarrows B in Opf(X)Opf(X), since ff is ff in KK, we must have α=fβ\alpha = f\beta for some 2-cell β:jl:TA\beta: j\to l:T\rightrightarrows A. But then aβbfβ=bαa\beta \cong b f\beta = b\alpha, so β\beta must also be a 2-cell in Opf(X)Opf(X).

Conversely, suppose that ff is ff in Opf(X)Opf(X), and that we have 2-cells α,β:xy:TA\alpha,\beta: x\rightrightarrows y: T\rightrightarrows A in KK such that fα=fβf\alpha=f\beta. Then since bfab f\cong a we have aα=aβa\alpha= a\beta; call this 2-cell ξ:axay\xi: a x\to a y. Since aa and bb are opfibrations and ff is a map of opfibrations, we have an opcartesian 2-cell xξ !(x)x\to \xi_!(x) lying over ξ\xi such that fxfξ !(x)f x \to f \xi_!(x) is also opcartesian. Then α\alpha and β\beta both factor through xξ !(x)x\to \xi_!(x) to give 2-cells γ,δ:ξ !(x)y\gamma,\delta: \xi_!(x)\rightrightarrows y in Opf(X)Opf(X) whose images under ff are equal. Since ff is faithful in Opf(X)Opf(X), we have γ=δ\gamma=\delta, and hence α=β\alpha=\beta. Thus, ff is faithful in KK. The proof of fullness is analogous.

Therefore, if AXA\to X is an (op)fibration in KK, we have Sub Opf(K)(A)Sub K(A)Sub_{Opf(K)}(A) \subset Sub_K(A), although in general the inclusion is proper. Of course, the dual result about Fib(X)Fib(X) is also true.

Iterated fibrations

It is well-known that a composite of fibrations is a fibration. Moreover:

Theorem

A morphism in Fib(X)Fib(X) is a fibration in the 2-category Fib(X)Fib(X) iff its underlying morphism in KK is a fibration.

This is a standard result, at least in the case K=CatK=Cat, and is apparently due to Benabou. References include:

  • J. Benabou, “Fibered categories and the foundations of naive category theory”
  • B. Jacobs, Categorical Logic and Type Theory, Chapter 9
  • C. Hermida, “Some properties of Fib as a fibred 2-category”

Therefore, for any fibration AXA\to X in KK we have Fib K(A)Fib Fib K(X)(AX)Fib_K(A) \simeq Fib_{Fib_K(X)}(A\to X), and similarly for opfibrations. This is a fibrational analogue of the standard equivalence K/A(K/X)/(AX)K/A \simeq (K/X)/(A\to X) for ordinary slice categories. It also implies that any morphism between discrete fibrations over XX is itself a (discrete) fibration in KK, since in Fib(X)Fib(X) it has a discrete (hence groupoidal) target and thus is a fibration there.

We will also need the corresponding result for mixed-variance iterated fibrations, which seems to be less well-known. First we recall:

Definition

A span ApEqBA \overset{p}{\leftarrow} E \overset{q}{\to} B is called a (two-sided) fibration from BB to AA if

  1. qq is an opfibration and pp takes qq-opcartesian 2-cells to isomorphisms,
  2. pp is a fibration and qq takes pp-cartesian 2-cells to isomorphisms, and
  3. for any e:XEe:X\to E, and any square
    α *e pcartesian e qopcartesian qopcartesian (α *e)β ! α *(eβ !) pcartesian eβ !\array{&& \alpha^*e & \overset{p-cartesian}{\to} & e\\ ^{q-opcartesian} & \swarrow && & \downarrow & ^{q-opcartesian}\\ (\alpha^* e)\beta_! & \to & \alpha^* (e \beta_!) & \overset{p-cartesian}{\to} & e \beta_!}

    of 2-cells, (α *e)β !α *(eβ !)(\alpha^* e)\beta_! \to \alpha^* (e \beta_!) is an isomorphism.

Such two-sided fibrations in CatCat correspond to functors B×A opCatB\times A^{op} \to Cat. The third condition corresponds precisely to the “interchange” equality (β,1)(1,α)=(1,α)(β,1)(\beta,1)(1,\alpha) = (1,\alpha)(\beta,1) in B×A opB\times A^{op}. We write Fib(B,A)Fib(B,A) for the 2-category of two-sided fibrations from BB to AA.

Theorem

A span ApEqBA \overset{p}{\leftarrow} E \overset{q}{\to} B is a two-sided fibration from BB to AA if and only if

  1. p:EAp:E\to A is a fibration and
  2. (p,q):EA×B(p,q):E\to A\times B is an opfibration in Fib(A)Fib(A).
Proof

Recall that the projection A×BAA\times B \to A is a fibration (and also an opfibration, although that is irrelevant here), and the cartesian 2-cells are precisely those whose component in BB is an isomorphism. Therefore, saying that (p,q)(p,q) is a morphism in Fib(A)Fib(A), i.e. that it preserves cartesian 2-cells, says precisely that qq takes pp-cartesian 2-cells to isomorphisms.

Now, by the remarks above, qq is an opfibration in KK iff E(q/1 B)E\to (q/1_B) has a left adjoint with invertible counit in K/BK/B, and (p,q)(p,q) is an opfibration in Fib(A)Fib(A) iff E((p,q)/1 A×B)E\to ((p,q)/1_{A\times B}) has a left adjoint with invertible counit in Fib(A)/(A×B)Fib(A)/(A\times B). Of crucial importance is that here ((p,q)/1 A×B)((p,q)/1_{A\times B}) denotes the comma object calculated in the 2-category Fib(A)Fib(A), or equivalently in K/AK/A, and it is easy to check that this is in fact equivalent to the comma object (q/1 B)(q/1_B) calculated in KK.

Therefore, (p,q)(p,q) is an opfibration in Fib(A)Fib(A) iff qq is an opfibration in KK and the left adjoint of E(q/1 B)E\to (q/1_B) is a morphism in Fib(A)Fib(A). It is then easy to check that this left adjoint is a morphism in K/AK/A iff pp inverts qq-opcartesian arrows, and that it is a morphism of fibrations iff the final condition in Definition is satisfied.

In particular, we have Fib(B,A)Opf Fib(A)(A×B)Fib(B,A) \simeq Opf_{Fib(A)}(A\times B). By duality, Fib(B,A)Fib Opf(B)(A×B)Fib(B,A) \simeq Fib_{Opf(B)}(A\times B), and therefore Fib Opf(B)(A×B)Opf Fib(A)(A×B)Fib_{Opf(B)}(A\times B) \simeq Opf_{Fib(A)}(A\times B), a commutation result that is not immediately obvious.

It follows that the 2-categories Fib(B,A)Fib(B,A) of two-sided fibrations also inherit any properties that can be shown to be inherited by the “one-sided” fibrational slices Fib(X)Fib(X) and Opf(X)Opf(X). Thus, we will usually concentrate on the latter, although two-sided fibrations will make an appearance in our treatment of duality involutions.

2-congruences

Idea

The correct notions of regularity and exactness for 2-categories is one of the subtler parts of the theory of first-order structure. In particular, we need a suitable replacement for the 1-categorical notion of equivalence relation. The (almost) correct definition was probably first written down in StreetCBS.

One way to express the idea is that in an nn-category, every object is internally a (n1)(n-1)-category; exactness says that conversely every “internal (n1)(n-1)-category” is represented by an object. When n=1n=1, an “internal 0-category” means an internal equivalence relation; thus exactness for 1-categories says that every equivalence relation is a kernel (i.e. is represented by some object). Thus, we need to find a good notion of “internal 1-category” in a 2-category.

Of course, there is an obvious notion of an internal category in a 2-category, as a straightforward generalization of internal categories in a 1-category. But internal categories in Cat are double categories, so we need to somehow cut down the double categories to those that really represent honest 1-categories. These are the 2-congruences.

Definition

If KK is a finitely complete 2-category, a homwise-discrete category in KK consists of a discrete morphism D 1D 0×D 0D_1\to D_0\times D_0, together with composition and identity maps D 0D 1D_0\to D_1 and D 1× D 0D 1D 1D_1\times_{D_0} D_1\to D_1 in K/(D 0×D 0)K/(D_0\times D_0), which satisfy the usual axioms of an internal category up to isomorphism. (Since D 1D 0×D 0D_1\to D_0\times D_0 is discrete, these isomorphisms will automatically satisfy any coherence axioms one might care to impose.)

The notions of functor and transformation between such categories are evident. The first point worth noting is that the transformations between functors DED\to E are a version of the notion for internal categories, thus given by a morphism D 0E 1D_0\to E_1 in KK. The 2-cells in K(D 0,E 0)K(D_0,E_0) play no explicit role, but we will recapture them below. The second point worth noting is that by homwise-discreteness, any “modification” between transformations is necessarily a unique isomorphism, so (after performing some quotienting, if we want to be pedantic) we really have a 2-category HDC(K)HDC(K) rather than a 3-category.

If f:ABf:A\to B is any morphism in KK, there is a canonical homwise-discrete category (f/f)A×A(f/f) \to A\times A, where (f/f)(f/f) is the comma object of ff with itself. We call this the kernel ker(f)ker(f) of ff. In particular, if f=1 Af=1_A then (1 A/1 A)=A 2(1_A/1_A) = A^{\mathbf{2}}, so we have a canonical homwise-discrete category A 2A×AA^{\mathbf{2}} \to A\times A called the kernel ker(A)ker(A) of AA. It is easy to check that taking kernels of objects defines a functor Φ:KHDC(K)\Phi:K \to HDC(K); this might first have been noticed by Street.

Theorem

If D 1D 0D_1\,\rightrightarrows\, D_0 is a homwise-discrete category in KK, the following are equivalent. 1. D 0D 1D 0D_0 \leftarrow D_1 \to D_0 is a two-sided fibration in KK. 1. There is a functor ker(D 0)D\ker(D_0)\to D whose object-map D 0D 0D_0\to D_0 is the identity.

Actually, homwise-discreteness is not necessary for this result, but we include it to avoid worrying about coherence isomorphisms, and since that is the case we are most interested in here.

Proof

We consider the case K=CatK=Cat; the general case follows because all the notions are defined representably. A homwise-discrete category in CatCat is, essentially, a double category whose horizontal 2-category is homwise-discrete (hence equivalent to a 1-category). We say “essentially” because the pullbacks and diagrams only commute up to isomorphism, but up to equivalence we may replace D 1D 0×D 0D_1\to D_0\times D_0 by an isofibration, obtaining a (pseudo) double category in the usual sense. Now the key is to compare both properties to a third: the existence of a companion for any vertical arrow.

Suppose first that D 0D 1D 0D_0 \leftarrow D_1 \to D_0 is a two-sided fibration. Then for any (vertical) arrow f:xyf:x\to y in D 0D_0 we have cartesian and opcartesian morphisms (squares) in D 1D_1:

x id x x f 1 y opcart f f cart x f 2 y y id y \array{x & \overset{id}{\to} & x & \qquad & x & \overset{f_1}{\to} & y' \\ \cong \downarrow & opcart & \downarrow f & \qquad & f \downarrow & cart & \downarrow \cong\\ x' & \overset{f_2}{\to} & y & \qquad & y & \overset{id}{\to} & y}

The vertical arrows marked as isomorphisms are so by one of the axioms for a two-sided fibration. Moreover, the final compatibility axiom for a 2-sided fibration says that the square

x f 1 y x f 2 y, \array{ x & \overset{f_1}{\to} & y'\\ \cong \downarrow & & \downarrow\cong \\ x' & \overset{f_2}{\to} & y,}

induced by factoring the horizontal identity square of ff through these cartesian and opcartesian squares, must be an isomorphism. We can then show that f 1f_1 (or equivalently f 2f_2) is a companion for ff just as in Theorem 4.1 here. Conversely, from a companion pair we can show that D 0D 1D 0D_0 \leftarrow D_1 \to D_0 is a two-sided fibration just as as in loc cit.

The equivalence between the existence of companions and the existence of a functor from the kernel of D 0D_0 is essentially found in this paper, although stated only for the “edge-symmetric” case. In their language, a kernel ker(A)ker(A) is the double category A\Box A of commutative squares in AA, and a functor ker(D 0)Dker(D_0)\to D which is the identity on D 0D_0 is a thin structure on DD. In one direction, clearly ker(D 0)ker(D_0) has companions, and this property is preserved by any functor ker(D 0)Dker(D_0)\to D. In the other direction, sending any vertical arrow to its horizontal companion is easily checked to define a functor ker(D 0)Dker(D_0)\to D.

In particular, we conclude that up to isomorphism, there can be at most one functor ker(D 0)Dker(D_0)\to D which is the identity on objects.

Definition

A 2-congruence in a finitely complete 2-category KK is a homwise-discrete category in KK satisfying the equivalent conditions of Theorem .

Of course, the kernel ker(A)ker(A) of any object is a 2-congruence. More generally it is easy to see that the kernel ker(f)ker(f) of any morphism is also a 2-congruence.

2-Forks and Quotients

The idea of a 2-fork is to characterize the structure that relates a morphism ff to its kernel ker(f)ker(f). The kernel then becomes the universal 2-fork on ff, while the quotient of a 2-congruence is the couniversal 2-fork constructed from it.

Definition

A 2-fork in a 2-category consists of a 2-congruence s,t:D 1D 0s,t:D_1\;\rightrightarrows\; D_0, i:D 0D 1i:D_0\to D_1, c:D 1× D 0D 1D 1c:D_1\times_{D_0} D_1\to D_1, and a morphism f:D 0Xf:D_0\to X, together with a 2-cell ϕ:fsft\phi:f s \to f t such that ϕi=f\phi i = f and such that

D 1× D 0D 1 D 1 = D 1 ϕ D 1 D 0 D 0 || ϕ f f D 1 D 0 f X=D 1× D 0D 1 c D 1 D 0 ϕ f D 1 f X.\array{ D_1\times_{D_0} D_1 & \to & D_1 & = & D_1\\ \downarrow && \downarrow & \Downarrow_\phi & \downarrow\\ D_1 & \to & D_0 && D_0\\ || &\Downarrow_\phi && \searrow^f & \downarrow f\\ D_1 & \to & D_0 & \overset{f}{\to} & X } \qquad = \qquad \array{ D_1\times_{D_0} D_1 \\ & \searrow^c\\ && D_1 & \to & D_0\\ && \downarrow & \Downarrow_\phi & \downarrow f\\ && D_1 & \overset{f}{\to} & X. }

The comma square in the definition of the kernel of a morphism f:ABf:A\to B gives a canonical 2-fork

(f/f)AfB.(f/f) \;\rightrightarrows\; A \overset{f}{\to} B.

It is easy to see that any other 2-fork

D 1D 0=AfBD_1 \;\rightrightarrows\; D_0 = A \overset{f}{\to} B

factors through the kernel by an essentially unique functor Dker(f)D \to ker(f) that is the identity on AA.

If D 1D 0fXD_1 \;\rightrightarrows\; D_0 \overset{f}{\to} X is a 2-fork, we say that it equips ff with an action by the 2-congruence DD. If g:D 0Xg:D_0\to X also has an action by DD, say ψ:gsgt\psi:g s \to g t, a 2-cell α:fg\alpha:f\to g is called an action 2-cell if (αt).ϕ=ψ.(αs)(\alpha t).\phi= \psi . (\alpha s). There is an evident category Act(D,X)Act(D,X) of morphisms D 0XD_0\to X equipped with actions.

Definition

A quotient for a 2-congruence D 1D 0D_1\;\rightrightarrows\; D_0 in a 2-category KK is a 2-fork D 1D 0qQD_1 \;\rightrightarrows\; D_0 \overset{q}{\to} Q such that for any object XX, composition with qq defines an equivalence of categories

K(Q,X)Act(D,X).K(Q,X) \simeq Act(D,X).

A quotient can also, of course, be defined as a suitable 2-categorical limit.

Lemma

The quotient qq in any 2-congruence is eso.

Proof

If m:ABm\colon A\to B is ff, then the square we must show to be a pullback is

Act(D,A) Act(D,B) K(D 0,A) K(D 0,B)\array{Act(D,A) & \overset{}{\to} & Act(D,B)\\ \downarrow && \downarrow\\ K(D_0,A)& \underset{}{\to} & K(D_0,B)}

But this just says that an action of DD on AA is the same as an action of DD on BB which happens to factor through mm, and this follows directly from the assumption that mm is ff.

Definition

A 2-fork D 1D 0fXD_1 \;\rightrightarrows\; D_0 \overset{f}{\to} X is called exact if ff is a quotient of DD and DD is a kernel of ff.

This is the 2-categorical analogue of the notion of exact fork in a 1-category, and plays an analogous role in the definition of a regular 2-category and an exact 2-category.

Opposites

The opposite of a homwise-discrete category is again a homwise-discrete category. However, the opposite of a 2-congruence in KK is a 2-congruence in K coK^{co}, since 2-cell duals interchange fibrations and opfibrations. Likewise, passage to opposites takes 2-forks in KK to 2-forks in K coK^{co}, and preserves and reflects kernels, quotients, and exactness.

Regular 2-categories

Definition

A 2-category KK is called regular if 1. It is finitely complete, 2. esos are stable under pullback, and 3. Every 2-congruence which is a kernel can be completed to an exact 2-fork.

In particular, the last condition implies that every 2-congruence which is a kernel has a quotient.

Examples

  • Cat is regular.

  • A 1-category is regular as a 2-category iff it is regular as a 1-category, since the esos in a 1-category are precisely the strong epics.

  • Every finitely complete (0,1)-category (that is, every meet-semilattice) is regular.

Factorizations

In StreetCBS the last condition is replaced by

  • Every morphism ff factors as fmef\cong m e where mm is ff and ee is eso.

We now show that this follows from our definition. First we need:

Lemma

(Street’s Lemma) Let KK be a finitely complete 2-category where esos are stable under pullback, let e:ABe:A\to B be eso, and let n:BCn:B\to C be a map. 1. If the induced morphism ker(e)ker(ne)ker(e) \to ker(n e) is ff, then nn is faithful. 1. If ker(e)ker(ne)ker(e) \to ker(n e) is an equivalence, then nn is ff.

Proof

First note that ker(e)ker(ne)ker(e)\to ker(n e) being ff means that if a 1,a 2:YAa_1,a_2: Y \rightrightarrows A and δ 1,δ 2:ea 1ea 2\delta_1,\delta_2 : e a_1 \;\rightrightarrows\; e a_2 are such that nδ 1=nδ 2n \delta_1 = n \delta_2, then δ 1=δ 2\delta_1=\delta_2. Likewise, ker(e)ker(ne)ker(e)\to ker(n e) being an equivalence means that given any α:nea 1nea 2\alpha: n e a_1 \to n e a_2, there exists a unique δ:ea 1ea 2\delta: e a_1 \to e a_2 such that nδ=αn \delta = \alpha.

We first show that nn is faithful under the first hypothesis. Suppose we have b 1,b 2:XBb_1,b_2:X \rightrightarrows B and β 1,β 2:b 1b 2\beta_1,\beta_2:b_1\to b_2 with nβ 1=nβ 2n \beta_1 = n \beta_2. Take the pullback

Y r X (a 1,a 2) (b 1,b 2) A×A e×e B×B\array{&Y & \overset{r}{\to} & X \\ (a_1,a_2) & \downarrow && \downarrow & (b_1,b_2)\\ & A\times A & \overset{e\times e}{\to} & B\times B}

Then we have two 2-cells

β 1r,β 2r:b 1rb 2r\beta_1 r, \beta_2 r: b_1 r \;\rightrightarrows\; b_2 r

such that the composites

nea 1nb 1rnβ 1r=nβ 2rnb 2rnea 2n e a_1 \cong n b_1 r \overset{n \beta_1 r = n \beta_2 r}{\to} n b_2 r \cong n e a_2

are equal. By the hypothesis, nβ 1r=nβ 2rn \beta_1 r = n \beta_2 r implies β 1r=β 2r\beta_1 r = \beta_2 r. But rr is eso, since it is a pullback of the eso e×ee\times e, so this implies β 1=β 2\beta_1=\beta_2. Thus, nn is faithful.

Now suppose the (stronger) second hypothesis, and form the pair of pullbacks:

(ne/ne) g n/n C 2 A×A e×e B×B n×n C×C\array{(n e / n e) & \overset{g}{\to} & n / n & \to & C^{\mathbf{2}}\\ \downarrow && \downarrow && \downarrow \\ A\times A & \overset{e\times e}{\to} & B\times B & \overset{n\times n}{\to} & C\times C}

Then gg, being a pullback of e×ee\times e, is eso. We also have a commutative square

(e/e) (ne/ne) g B 2 (n/n).\array{(e/e) & \to & (n e / n e)\\ \downarrow && \downarrow g \\ B^{\mathbf{2}} & \to & (n/n).}

By assumption, (e/e)(ne/ne)(e/e) \to (n e / n e) is an equivalence. Since we have shown that nn is faithful, the bottom map B 2(n/n)B^{\mathbf{2}} \to (n/n) is ff, so since the eso gg factors through it, it must be an equivalence as well. But this says precisely that nn is ff.

Theorem

A 2-category is regular if and only if 1. it has finite limits, 2. esos are stable under pullback, 3. every morphism ff factors as fmef\cong m e where mm is ff and ee is eso, and 4. every eso is the quotient of its kernel.

Proof

First suppose KK is regular; we must show the last two conditions. Let f:ABf:A\to B be any morphism. By assumption, the kernel ker(f)ker(f) can be completed to an exact 2-fork ker(f)AeCker(f) \rightrightarrows A \overset{e}{\to} C. Since ee is the quotient of the 2-congruence ker(f)ker(f), it is eso, and since ff comes with an action by ker(f)ker(f), we have an induced map m:CBm:C\to B with fmef\cong m e. But since the 2-fork is exact, we also have ker(f)ker(e)ker(f)\simeq ker(e), so by Street’s Lemma, mm is ff.

Now suppose that in the previous paragraph ff were already eso. Then since it factors through the ff mm, mm must be an equivalence; thus ff is equivalent to ee and hence is a quotient of its kernel.

Now suppose KK satisfies the conditions in the lemma. Let f:ABf:A\to B be any morphism; we must show that ker(f)ker(f) can be completed to an exact 2-fork. Factor f=mef = m e where mm is ff and ee is eso. Since mm is ff, we have ker(f)ker(e)ker(f)\simeq ker(e). But every eso is the quotient of its kernel, so the fork ker(f)AeCker(f) \rightrightarrows A \overset{e} \to C is exact.

In StreetCBS it is claimed that the final condition in Theorem follows from the other three, but there is a flaw in the proof.

Subobjects

In a regular 2-category KK, we call a ff m:AXm:A\to X with codomain XX a subobject of XX. We write Sub(X)Sub(X) for the preorder of subobjects of XX, as a full sub-2-category of the slice 2-category K/XK/X. Since KK is finitely complete and pullbacks preserve ffs, we have pullback functors f *:Sub(Y)Sub(X)f^*:Sub(Y)\to Sub(X) for any f:XYf:X\to Y.

If gmeg \cong m e where mm is ff and ee is eso, we call mm the image of gg. Taking images defines a left adjoint f:Sub(X)Sub(Y)\exists_f:Sub(X)\to Sub(Y) to f *f^* in any regular 2-category, and the Beck-Chevalley condition is satisfied for any pullback square, because esos are stable under pullback.

Preservation

It is easy to check that if KK is regular, so are:

The slice 2-category K/XK/X does not, in general, inherit regularity, but we have:

Theorem

If KK is regular, so are the fibrational slices Opf(X)Opf(X) and Fib(X)Fib(X).

Classification of congruences

In general, the idea is that an nn-congruence in an mm-category KK, where nmn\le m, is an “internal (n1)(n-1)-category” in KK. Of course, we only deal formally with the case m2m\le 2, although we allow nn and mm to be of the form (r,s)(r,s); see n-prefix.

Definition

Let DD be a 2-congruence in a 2-category KK.

  • DD is a (2,1)-congruence if it is an internal groupoid, i.e. there is a map D 1D 1D_1\to D_1 providing “inverses”.
  • It is a (1,2)-congruence if D 1D 0×D 0D_1\to D_0\times D_0 is ff.
  • It is a 1-congruence if it is both a (2,1)-congruence and a (1,2)-congruence.
  • it is a (0,1)-congruence if D 1D 0×D 0D_1\to D_0\times D_0 is an equivalence.

Note that in a 1-category,

  • a 2-congruence is just an internal category (a 1-category),
  • a (2,1)-congruence is an internal groupoid (a (1,0)-category),
  • a (1,2)-congruence is an internal poset (a (0,1)-category), and
  • a 1-congruence is an internal equivalence relation (a 0-category).

Of course, a (0,1)-congruence in any 2-category is completely determined by any object D 0D_0.

Theorem

Let q:XYq:X\to Y be a morphism in KK. If YY is nn-truncated for n1n\ge -1, then ker(q)ker(q) is an (n+1)(n+1)-congruence. This means that:

  1. If YY is groupoidal, then ker(q)ker(q) is a (2,1)-congruence.
  2. If YY is posetal, then ker(q)ker(q) is a (1,2)-congruence.
  3. If YY is discrete, then ker(q)ker(q) is a 1-congruence.
  4. If YY is subterminal, then ker(q)ker(q) is a (0,1)-congruence.

In all these cases the converse is true if KK is regular and qq is eso.

Proof

The forward directions are fairly obvious; it is the converses which take work. Suppose first that ker(q)ker(q) is a (2,1)-congruence, and let α:fg:XY\alpha: f \to g: X \rightrightarrows Y be any 2-cell. Pulling back the eso qq along ff and gg gives P 1TP_1\to T and P 2TP_2\to T; let r:PTr:P \to T be the pullback P 1× XP 2P_1\times_X P_2. Since KK is regular, rr is eso. By definition of kernels, the 2-cell αr\alpha r corresponds to a map P(q/q)P\to (q/q). But (q/q)C(q/q)\rightrightarrows C is a (2,1)-congruence, so composing this map with the “inverse” map (q/q)(q/q)(q/q)\to(q/q) gives another map P(q/q)P\to (q/q), and thereby another 2-cell frgrf r \to g r which is inverse to αr\alpha r. Finally, since rr is eso, precomposing with it reflects invertibility, so α\alpha must also be invertible. Thus YY is groupoidal.

Now suppose that ker(q)ker(q) is a (1,2)-congruence, and let α,β:fg:TY\alpha,\beta: f\to g: T\to Y be two parallel 2-cells. With notation as in the previous paragraph, the 2-cells αr\alpha r and βr\beta r correspond to morphisms P(q/q)P\rightrightarrows (q/q) which become isomorphic in XX. But since (q/q)X(q/q)\rightrightarrows X is a (1,2)-congruence, this implies that the two maps P(q/q)P\rightrightarrows (q/q) are isomorphic, and hence αr=βr\alpha r = \beta r. And since rr is eso, precomposing with it is faithful, so α=β\alpha=\beta; thus YY is posetal.

The discrete case follows by combining the posetal and groupoidal cases, so it remains to show that if ker(q)ker(q) is a (0,1)-congruence then YY is subterminal. We know it is discrete, so it suffices to show that given two f,g:TYf,g:T \rightrightarrows Y we have a 2-cell fgf\to g. Continuing with the same notation, and letting h,k:PXh,k:P\to X be the induced maps with qhfrq h \cong f r and qkgrq k \cong g r, we have (h,k):PX×X=(q/q)(h,k):P\to X\times X = (q/q), and therefore the 2-cell defining the fork (q/q)XqY(q/q) \;\rightrightarrows\;X \overset{q}{\to} Y gives us a 2-cell qhqkq h \to q k and therefore frgrf r \to g r. Now rr is the quotient of its kernel, so for this 2-cell to induce a 2-cell fgf\to g it suffices for it to be an action 2-cell for the actions of ker(r)ker(r) on frf r and grg r; but this is automatic since we know YY to be posetal. Thus we have a 2-cell fgf\to g as desired, so YY is subterminal.

Exact 2-categories

A regular 1-category is exact when every congruence has a kernel. The definition for 2-categories is analogous.

Definition

Let 1<n2-1\lt n\le 2 be directed (see n-prefix). A 2-category is nn-exact if it is regular and every n-congruence is a kernel.

Recall that a 1-category is regular as a 1-category iff it is regular as a homwise-discrete 2-category. However, a regular 1-category is exact as a 1-category precisely when it is 1-exact as a 2-category. Since general 2-congruences in a 1-category are internal categories, they will obviously not all be kernels. This is why we add a prefix to “exact:” the best notion for 2-categories, which we call “2-exact,” is not a conservative extension of the established meaning of “exact” for 1-categories.

Likewise, it is unreasonable to expect a (2,1)-category to be any more than (2,1)-exact, or a (1,2)-category to be any more than (1,2)-exact.

Examples

  • Cat is 2-exact. Likewise, Gpd is (2,1)-exact, Pos is (1,2)-exact, and of course Set is 1-exact.

  • Every regular (0,1)-category (that is, every meet-semilattice) is (0,1)-exact, and in fact even 2-exact, since there are no nontrivial congruences of any sort in a poset.

  • If KK is 2-exact, then by the classification of congruences, gpd(K)gpd(K) is (2,1)-exact, pos(K)pos(K) is (1,2)-exact, disc(K)disc(K) is 1-exact, and Sub(1)Sub(1) is (0,1)-exact.

  • If KK is nn-exact, then so is K coK^{co}, by the remarks about opposite 2-congruences. For 1-categories and (2,1)-categories, of course, this is contentless, but for 2-categories and (1,2)-categories it is contentful.

Coherent 2-categories

Definition

A 2-category is called coherent if 1. it has finite limits, 1. finite jointly-eso families are stable under pullback, and 1. every finitary 2-polycongruence which is a kernel can be completed to an exact 2-polyfork.

Here a family {f i:A iB}\{f_i:A_i \to B\} is said to be jointly-eso if whenever m:CBm:C\to B is ff and every f if_i factors through mm (up to isomorphism), then mm is an equivalence.

Likewise, we have infinitary coherent 2-categories in which “finite” in the second two conditions is replaced by “small.”

Examples

  • CatCat is coherent.

  • A 1-category is coherent as a 2-category iff it is coherent as a 1-category.

  • A (0,1)-category (= poset) is coherent iff it is a distributive lattice, and infinitary-coherent iff it is a frame.

Factorizations

The following are proven just like their unary analogues in a regular 2-category.

Lemma

(Street’s Lemma) In a finitely complete 2-category where finite jointly-eso families are stable under pullback, if {e i:A iB}\{e_i:A_i \to B\} is finite and jointly-eso and n:BCn:B\to C is such that the induced functor ker(e i)ker(ne i)\ker(e_i) \to ker(n e_i) is an equivalence, then nn is ff.

Theorem

A 2-category is coherent if and only if 1. it has finite limits, 1. finite jointly-eso families are stable under pullback, 1. every finite family {f i}\{f_i\} factors as f i=me if_i = m e_i where mm is ff and {e i}\{e_i\} is jointly-eso, and 1. every jointly-eso family is the quotient of its kernel.

Of course, there are infinitary versions. In particular, we conclude that in a coherent (resp. infinitary-coherent) 2-category, the posets Sub(X)Sub(X) have finite (resp. small) unions that are preserved by pullback.

Colimits

Lemma

A coherent 2-category has a strict initial object; that is an initial object 00 such that any morphism X0X\to 0 is an equivalence.

Proof

The empty 2-congruence is the kernel of the empty family (over any object), so it must have a quotient 00, which is clearly an initial object. The empty family over 00 is jointly-eso, so for any X0X\to 0 the empty family over XX is also jointly-eso; but this clearly makes XX initial as well.

Two ffs m:AXm:A\to X and n:BXn:B\to X are said to be disjoint if the comma objects (m/n)(m/n) and (n/m)(n/m) are initial objects. If initial objects are strict, then this implies that the pullback A× XBA\times_X B is also initial, but it is strictly stronger already in PosPos.

Lemma

In a coherent 2-category, if AXA\to X and BXB\to X are disjoint subobjects, then their union ABA\cup B in Sub(X)Sub(X) is also their coproduct A+BA+B.

Proof

If AA and BB are disjoint subobjects of XX, then the kernel of {AX,BX}\{A\to X, B\to X\} is the disjoint union of ker(A)ker(A) and ker(B)ker(B). Therefore, a quotient of it (which is a union of AA and BB in Sub(X)Sub(X)) will be a coproduct of AA and BB.

A coproduct A+BA+B in a 2-category is disjoint if AA and BB are disjoint subobjects of A+BA+B. We say a coherent 2-category is positive if any two objects have a disjoint coproduct. By Lemma , this is equivalent to saying that any two objects can be embedded as disjoint subobjects of some other object. Disjoint coproducts in a coherent 2-category are automatically stable under pullback, so a positive coherent 2-category is necessarily extensive. Conversely, we have:

Lemma

A regular and extensive 2-category is coherent (and positive).

In the presence of finite coproducts, a family {e i:A iB}\{e_i:A_i\to B\} is jointly-eso iff iA iB\coprod_i A_i \to B is eso; thus regularity and universal coproducts imply that finite jointly-eso families are stable under pullback. And assuming extensivity, any 2-polycongruence {C ij}{C i}\{C_{i j}\} \rightrightarrows \{C_i\} gives rise to an ordinary 2-congruence ijC ij iC i\coprod_{i j} C_{i j} \rightrightarrows \coprod_i C_i. Likewise, 2-polyforks {C ij}{C i}X\{C_{i j}\} \rightrightarrows \{C_i\} \to X correspond to 2-forks ijC ij iC iX\coprod_{i j} C_{i j} \rightrightarrows \coprod_i C_i \to X, and the property of being a kernel or a quotient is preserved; thus regularity implies coherency.

Preservation

If KK is coherent, then easily so are K coK^{co}, disc(K)disc(K), gpd(K)gpd(K), pos(K)pos(K), and Sub(1)Sub(1). Moreover, we have:

Theorem

If KK is a coherent 2-category, so are the fibrational slices Opf(X)Opf(X) and Fib(X)Fib(X) for any XKX\in K.

Extensive 2-categories

A coproduct A+BA+B in a 2-category is said to be disjoint if we have comma squares

A 2 A B 2 B 0 A 0 B A A+B B A+B B A+B A A+B \array{ A^{\mathbf{2}} & \to & A & \quad & B^{\mathbf{2}} & \to & B & \quad & 0 & \to & A & \quad & 0 & \to & B \\ \downarrow & \Downarrow & \downarrow & \quad & \downarrow & \Downarrow & \downarrow & \quad & \downarrow & \Downarrow & \downarrow & \quad & \downarrow & \Downarrow & \downarrow & \quad\\ A & \to & A+B & \quad & B & \to & A+B & \quad & B & \to & A+B & \quad & A & \to & A+B & \quad}

The first two say that AA+BA\to A+B and BA+BB\to A+B are ff and the second two say that they are disjoint subobjects of A+BA+B.

A coproduct A+BA+B is said to be universal if for any morphism ZA+BZ\to A+B, the pullbacks

X Z Y A A+B B\array{X & \to & Z & \leftarrow & Y\\ \downarrow & & \downarrow & & \downarrow\\ A & \to & A+B & \leftarrow & B}

exist and exhibit ZZ as a coproduct X+YX+Y.

Finally, we say a 2-category is extensive if it has finite coproducts which are disjoint and universal. If it also has finite limits we say it is lextensive, and if it is also coherent we call it positive. (Note that disjoint coproducts in a coherent 2-category are always universal.)

An extensive 2-category does satisfy 2-categorical versions of the additional characterizations of an extensive 1-category, but unlike in the 1-categorical case, these alternate conditions do not seem to suffice to characterize extensivity. In particular, though, a 1-category is extensive as a 1-category iff it is so as a homwise-discrete 2-category.

Preservation

If KK is extensive, so is K coK^{co}, obviously. Less obvious is:

Lemma

If KK is extensive, so are gpd(K)gpd(K), pos(K)pos(K), and disc(K)disc(K). In other words, if KK is extensive, so is its (n+1)(n+1)-category trunc n(K)trunc_n(K) of nn-truncated objects for 0n0\le n.

Proof

Since the three given categories are closed in KK under limits and strict initial objects, it suffices to show they are closed under coproducts. First suppose given two morphisms f,g:ZA 1+A 2f,g:Z\to A_1+A_2. Then ff decomposes Z=X 1+X 2Z=X_1+X_2, and gg decomposes Z=Y 1+Y 2Z=Y_1+Y_2. Then the inclusions X iZ=Y 1+Y 2X_i \to Z = Y_1+Y_2 also decompose each X i=X i1+X i2X_i=X_{i 1} + X_{i 2}. Now if there exists a 2-cell fgf\to g, it induces a map from each X ijX_{i j} to the comma object of A 1A_1 and A 2A_2. Since coproducts are disjoint and initials are strict, this implies that X 12=X 21=0X_{12}=X_{21}=0. Therefore, we have a decomposition Z=X 11+X 22Z=X_{11}+X_{22} so that f=f 1+f 2f=f_1+f_2 and g=g 1+g 2g=g_1+g_2, where f i:X iiA if_i:X_{i i} \to A_i and g i:X iiA ig_i:X_{i i} \to A_i.

Now, by universality of the coproduct X 11+X 22X_{11}+X_{22}, it follows that 2-cells fgf\to g are determined uniquely by pairs of 2-cells f 1g 1f_1\to g_1 and f 2g 2f_2\to g_2. Therefore, if A 1A_1 and A 2A_2 are groupoidal, any 2-cells f 1g 1f_1\to g_1 and f 2g 2f_2\to g_2 are invertible, and thus so is any 2-cell fgf\to g; so A 1+A 2A_1+A_2 is groupoidal. And if A 1A_1 and A 2A_2 are posetal, any parallel 2-cells f 1g 1f_1 \;\rightrightarrows\; g_1 and f 2g 2f_2 \;\rightrightarrows\; g_2 are equal, and thus so are any fgf \;\rightrightarrows\; g; so A 1+A 2A_1+A_2 is posetal. And of course the discrete case follows by combining these.

However, the (0,1)-category (= poset) Sub(1)Sub(1) of (-1)-truncated objects (= subterminal objects) does not inherit extensivity, and in fact posets are almost never extensive: the only disjoint coproduct is 0+00+0.

We also have:

Lemma

If KK is extensive, so are the fibrational slices Opf(X)Opf(X) and Fib(X)Fib(X) for any XKX\in K.

2-pretoposes

Definition

Let nn be 2, (2,1), (1,2), or 1. That is, 1n21\le n\le 2 and nn is directed; see n-prefix.

Definition

An nn-pretopos is an nn-exact nn-category which is also extensive. An infinitary nn-pretopos is an nn-pretopos which is infinitary-extensive.

As remarked here, regularity plus extensivity implies coherency. Thus an nn-pretopos is, in particular, a coherent nn-category. Conversely, we have:

Theorem

An nn-category is an nn-pretopos if and only if it is coherent and every (finitary) nn-polycongruence is a kernel.

Examples

  • CatCat is a 2-pretopos. Likewise, GpdGpd is a (2,1)-pretopos and PosPos is a (1,2)-pretopos.

  • A 1-category is a 1-pretopos precisely when it is a pretopos in the usual sense. Note that, as remarked for exactness, a 1-category is unlikely to be an nn-pretopos for any n>1n\gt 1.

  • Since no nontrivial (0,1)-categories are extensive, the definition as phrased above is not reasonable for n=(0,1)n=(0,1). However, for some purposes (such as the n-Giraud theorem), it is convenient to define an (infinitary) (0,1)-pretopos to simply be an (infinitary) coherent (0,1)-category (exactness being automatic).

Colimits

An nn-pretopos has coproducts and quotients of nn-congruences, which are an important class of colimits. However, it can fail to admit all finite colimits, for essentially the same reason as when n=1n=1: namely, some ostensibly “finite” colimits secretly involve infinitary processes. In a 1-category, this manifests in the construction of arbitrary coequalizers and pushouts, where we must first generate an equivalence relation by an infinitary process and then take its quotient.

For 2-categories it is even easier to find counterexamples: the 1-pretopos FinSetFinSet does in fact have all finite colimits, but the 2-pretopos FinCatFinCat of finite categories (that is, finitely many objects and finitely many morphisms) does not have coinserters, coinverters, or coequifiers. (The category FPCatFPCat of finitely presented categories does have finite colimits, but fails to have finite limits.)

However, I conjecture that just as in the case n=1n=1, once an nn-pretopos is also countably-coherent, it does become finitely cocomplete. See colimits in an n-pretopos.

Heyting 2-categories

Definition

Definition

A 2-category is Heyting if it is coherent and each pullback functor f *:Sub(Y)Sub(X)f^*:Sub(Y)\to Sub(X) has a right adjoint f\forall_f.

As in the 1-categorical case, this also ensures that each Sub(X)Sub(X) is a Heyting algebra and that each f *f^* is a homomorphism of Heyting algebras. Moreover, the right adjoints f\forall_f satisfy the Beck-Chevalley condition for pullback squares, because the left adjoints f\exists_f do. This is just what is necessary for the internal interpretation of (finitary) first-order logic.

Examples

  • CatCat is Heyting.

  • A 1-category is Heyting as a 2-category iff it is Heyting as a 1-category.

  • A (0,1)-category is Heyting iff it is a Heyting algebra.

  • Any well-powered infinitary-coherent 2-category is Heyting, by the adjoint functor theorem for posets. In particular, any Grothendieck 2-topos is Heyting.

  • Unlike in the 1-categorical case, there seems no reason why a coherent 2-category with exponentials must be Heyting. It does, however have adjoints to pullback along fibrations and opfibrations, and in particular along product projections, which is enough for some uses of universal quantification in the internal logic.

Preservation

Clearly if KK is Heyting, so are K coK^{co}, gpd(K)gpd(K), pos(K)pos(K), disc(K)disc(K), and Sub(1)Sub(1) (the Heyting algebra of subterminals).

Moreover, Heytingness is also preserved by fibrational slicing. First we show:

Theorem

If KK is Heyting, then for any XX and any AOpf(X)A\in Opf(X), Sub Opf(X)(A)Sub_{Opf(X)}(A) is a coreflective sub-poset of Sub K(A)Sub_K(A).

Proof

As proven here, Sub Opf(X)(A)Sub_{Opf(X)}(A) is a full sub-poset of Sub K(A)Sub_K(A). Moreover, it is easy to see that a ff BAB\to A is in Sub Opf(X)(A)Sub_{Opf(X)}(A) precisely when

  1. BXB\to X is an opfibration and
  2. BAB\to A is a morphism of opfibrations.

In general, the first condition does not imply the second. It is also easy to check that these two conditions together are equivalent to saying that the composite

B× XX 2A× XX 2aAB\times_X X ^{\mathbf{2}} \to A\times_X X ^{\mathbf{2}} \overset{a}{\to} A

factors through BAB\to A, where aa is the action making AA into a fibration. Note that B× XX 2B\times_X X ^{\mathbf{2}} is alternately written as p *Bp^*B, where p:A× XX 2Ap:A\times_X X ^{\mathbf{2}} \to A is the projection onto the first factor. Therefore, BB is in Sub Opf(X)(A)Sub_{Opf(X)}(A) just when pa *BB\exists_p a^*B\le B, or equivalently when B ap *BB\le \forall_a p^*B.

We claim that B ap *BB\mapsto \forall_a p^* B coreflects Sub(A)Sub(A) into Sub Opf(X)(A)Sub_{Opf(X)}(A), and given the above, it suffices to verify that it is a comonad. First, let i:AA× XX 2i:A\to A\times_X X ^{\mathbf{2}} be the inclusion of identities; then ai1a i\cong 1 and pi1p i \cong 1, so we have

i *a *B= B a *B iB pa *B p iB=B. \begin{aligned} i^*a^*B =& B\\ a^*B \le& \forall_i B\\ \forall_p a^* B \le& \forall_p \forall_i B = B. \end{aligned}

This gives the counit of the comonad. The comultiplication is a little more involved. First note that we have a pullback square

A× XX 2× XX 2 q A× XX 2 a×1 a A× XX 2 p A\array{ A\times_X X ^{\mathbf{2}} \times_X X ^{\mathbf{2}} & \overset{q}{\to} & A\times_X X ^{\mathbf{2}} \\ ^{a\times 1}\downarrow && \downarrow^a\\ A\times_X X ^{\mathbf{2}} & \underset{p}{\to} & A}

where qq denotes projection onto the first two factors. Thus, by the Beck-Chevalley condition, a * p= q(a×1) *a^*\forall_p = \forall_q (a\times 1)^* and therefore

pa * pa *B= p q(a×1) *a *B= p q(1×m) *a *B\forall_p a^*\forall_p a^* B = \forall_p \forall_q (a\times 1)^* a^* B = \forall_p \forall_q (1\times m)^* a^* B

where m:X 2× XX 2X 2m:X ^{\mathbf{2}} \times_X X ^{\mathbf{2}} \to X^{\mathbf{2}} is the “composition” morphism.

Let us write X X^{\to\to} for X 2× XX 2X ^{\mathbf{2}} \times_X X ^{\mathbf{2}}, the object of composable arrows in XX, and write X X^{\overset{\nearrow}{\to}\to} for the power of XX with the category

\array{&& \bullet\\ & \nearrow\\ \bullet &\to & \bullet & \to &\bullet}

Let r:X X r:X^{\overset{\nearrow}{\to}\to} \to X^{\to\to} forget the “lonely” arrow, and let c:X X c:X^{\to\to} \to X^{\overset{\nearrow}{\to}\to} make the lonely arrow into the composite of the other two. Then rc1r c \cong 1, and moreover pqc1×mp' q' c\cong 1\times m, where pp' and qq' are pp and qq applied to the non-lonely arrows. Thus, we have

c *(q) *(p) *a *B= (1×m) *a *B (q) *(p) *a *B c(1×m) *a *B r(q) *(p) *a *B r c(1×m) *a *B r(q) *(p) *a *B (1×m) *a *B q *p * pa *B (1×m) *a *B pa *B p q(1×m) *a *B pa *B pa * pa *B.\begin{aligned} c^* (q')^* (p')^* a^* B =& (1\times m)^* a^* B\\ (q')^* (p')^* a^* B \le& \forall_c (1\times m)^* a^* B\\ \forall_r (q')^* (p')^* a^* B \le& \forall_r \forall_c (1\times m)^* a^* B\\ \forall_r (q')^* (p')^* a^* B \le& (1\times m)^* a^* B\\ q^* p^* \forall_p a^* B \le& (1\times m)^* a^* B\\ \forall_p a^* B \le& \forall_p \forall_q (1\times m)^* a^* B\\ \forall_p a^* B \le& \forall_p a^*\forall_p a^* B. \end{aligned}

as desired. (Here we have used another Beck-Chevalley condition to move rr past qq' and pp', turning them into pp and qq and it into pp.)

Corollary

If KK is Heyting, so is each fibrational slice Opf(X)Opf(X) and Fib(X)Fib(X).

Proof

This follows from the adjoint lifting theorem for posets: for any f:ABf:A\to B in Opf(X)Opf(X) we have a commutative square

Sub Opf(X)(B) f * Sub Opf(X)(A) Sub K(B) f * Sub K(A)\array{Sub_{Opf(X)}(B) & \overset{f^*}{\to} & Sub_{Opf(X)}(A)\\ \downarrow && \downarrow\\ Sub_K(B)& \underset{f^*}{\to} & Sub_K(A)}

where the vertical arrows are comonadic (inclusions of coreflective sub-posets) and the bottom horizontal arrow has a right adjoint; hence so does the top horizontal arrow.

Booleanness

We may naturally say that a coherent 2-category KK is Boolean if each Sub(X)Sub(X) is a Boolean algebra. As usual, this implies that KK is Heyting; we have f=¬ f¬\forall_f = \neg \exists_f \neg.

Note that a subobject and its complement in Sub(X)Sub(X) need not be “disjoint” in the sense introduced here; only their pullback, not their comma object, need be initial. Note also that unlike in the 1-categorical case, Booleanness is not stable under slicing; this fails already in the (1,2)-category PosPos (though it holds in any (2,1)-category).

Cores

Cores

The core of a category AA is the maximal subcategory of AA that is a groupoid, consisting of all its objects and all isomorphisms between them. The core is not a functor on the 2-category CatCat, but it is a functor on the (2,1)-category Cat gCat_g of categories, functors, and natural isomorphisms. In fact, it is a coreflection of Cat gCat_g into GpdGpd.

In general, for any 2-category KK we write K gK_g for its “homwise core:” the sub-2-category determined by all the objects and morphisms but only the iso 2-cells. Of course, K gK_g is a (2,1)-category. Then gpd(K)gpd(K) is a full sub-2-category of K gK_g, and we can ask whether it is coreflective. In a regular 2-category, however, it turns out that there is a stronger and more useful notion which implies this coreflectivity.

Definition

A core of an object AA in a regular 2-category is a morphism JAJ\to A which is eso, pseudomonic, and where JJ is groupoidal.

Lemma

In a regular 2-category KK, any core JAJ\to A is a coreflection of AA from K gK_g into gpd(K)gpd(K).

Proof

We must show that for any groupoidal GG, the functor

gpd(K)(G,J)=K g(G,J)K g(G,A)gpd(K)(G,J)=K_g(G,J)\to K_g(G,A)

is an equivalence. Since JAJ\to A is pseudomonic in KK, it is ff in K gK_g, so this functor is full and faithful; thus it remains to show it is eso. Given any map GAG\to A, take the pullback

P J G A\array{P & \to & J\\ \downarrow && \downarrow \\ G & \to & A}

and let P 1PP_1\;\rightrightarrows\; P be the kernel of PGP\to G. Since the composite PAP\to A descends to GG, it comes equipped with an action by this kernel. However, since GG is groupoidal, P 1PP_1\;\rightrightarrows\; P is a (2,1)-congruence, so the 2-cell defining the action must be an isomorphism. Therefore, it must factor uniquely through the pseudomonic JAJ\to A, so PJP\to J has an action as well; thus it descends to a map GJG\to J, as desired.

In particular, cores in a regular 2-category are unique up to unique equivalence. We write J(A)J(A) for the core of AA, when it exists.

Lemma

An object AA of a (2,1)-exact 2-category has a core if and only if there is an eso CAC\to A where CC is groupoidal.

Proof

“Only if” is clear, so suppose that p:CAp:C\to A is eso and CC is groupoidal. Let C 1=C× ACC_1 = C\times_A C be the pullback. Then C 1C_1 is also groupoidal and is a (2,1)-congruence on CC, so by exactness it is the kernel of some eso q:CJq:C\to J. There is an evident induced map m:JAm:J\to A; we claim that this is a core of AA.

Evidently m:JAm:J\to A is eso, since the eso CAC\to A factors through it. And since C 1C_1 is a (2,1)-congruence, the classification of congruences implies that JJ is groupoidal; thus it remains to show that mm is pseudomonic.

First suppose given f,g:XJf,g: X\;\rightrightarrows\; J. Pulling back qq along ff and gg gives esos P 1XP_1\to X and P 2XP_2\to X, whose pullback P=P 1× XP 2P = P_1\times_X P_2 comes with an eso r:PTr:P \to T and two morphisms h,k:PCh,k:P \to C with qhfrq h \cong f r and qkgrq k \cong g r. Then any pair of 2-cells α,β:fg\alpha,\beta: f\to g induce maps PC 1P\;\rightrightarrows\; C_1, since C 1C_1 is the kernel (q/q)(q/q). But if mα=mβm\alpha = m\beta, then these two maps must be equal, since C 1C_1 is also the kernel (p/p)(p/p). Therefore, αr=βr\alpha r=\beta r, and since rr is eso, α=β\alpha=\beta; thus mm is faithful.

On the other hand, again given f,g:XJf,g: X\;\rightrightarrows\; J, any isomorphism α:mfmg\alpha: m f\cong m g induces a map PC 1P\to C_1 and therefore a 2-cell β:frgr\beta: f r\to g r with mβ=αrm\beta = \alpha r. To show that β\beta descends to a 2-cell fgf\to g, we must verify that it is an action 2-cell for the actions of PJP\;\rightrightarrows\; J on frf r and grg r. But mβm\beta is an action 2-cell, since mβ=αrm\beta = \alpha r, and we now know that mm is faithful, so it reflects the axiom for an action 2-cell. Therefore, mm is full-on-isomorphisms, and hence pseudomonic.

Enough groupoids

We say that a regular 2-category has enough groupoids if every object admits an eso from a groupoidal one. Thus, a (2,1)-exact 2-category has cores if and only if it has enough groupoids.

Likewise, we say that a regular 2-category has enough discretes if every object admits an eso from a discrete one. Clearly this is a stronger condition. Note, though, that if KK has enough groupoids, then pos(K)pos(K) has enough discretes, since the core of any posetal object is discrete.

Having enough discretes, or at least enough groupoids, is a very familiar aspect of 2-categories such as CatCat. It also turns out to make the internal logic noticeably easier to work with. However, in a sense none of the really “new” 2-categories have enough groupoids or discretes.

  • The 2-exact 2-categories having enough discretes are precisely the categories of internal categories and anafunctors in 1-exact 1-categories; see exact completion of a 2-category. Likewise, any 2-exact 2-categories having enough groupoids consists of certain internal categories in a (2,1)-category.

  • Basically the only Grothendieck 2-toposes having enough discretes are the 2-categories of stacks on 1-sites, and the only ones having enough groupoids are the 2-categories of stacks on (2,1)-sites. The “honestly 2-dimensional” case of stacks on 2-sites (almost?) never have enough of either.

Subobjects

We also remark that cores, when they exist, “capture all the information about subobjects.”

Proposition

If KK is a regular 2-category and AA is an object having a core j:JAj:J\to A, then j *:Sub(A)Sub(J)j^*:Sub(A)\to Sub(J) is an equivalence.

Proof

It is a general fact in a regular 2-category that for any eso f:XYf:X\to Y, f *:Sub(Y)Sub(X)f^*:Sub(Y)\to Sub(X) is full (and faithful, which of course is automatic for a functor between posets). For if f *Uf *Vf^*U \le f^*V, then we have a square

f *U f *V V U Y\array{f^*U & \to & f^*V & \to & V\\ \downarrow &&&& \downarrow\\ U & & \to & & Y}

in which f *UUf^*U \to U is eso and VYV\to Y is ff, hence we have UVU\to V over YY.

Thus, in our case, j *j^* is full and faithful since jj is eso, so it suffices to show that for any ff UJU\to J we have j * jUUj^* \exists_j U \le U in Sub(J)Sub(J). But we have a commutative square

U jU J X\array{U & \to & \exists_j U\\ \downarrow && \downarrow\\ J & \to & X}

where the vertical arrows are ff and the bottom arrow JXJ\to X is faithful and pseudomonic, from which it follows that U jUU\to \exists_j U is also faithful and pseudomonic. Since U jUU\to \exists_j U is eso by definition, UU is a core of jU\exists_j U, and since j * jUj^*\exists_j U is a groupoid mapping to jU\exists_j U, it factors through UU, as desired.

NNOs in a 2-category

If KK is a 2-category with finite limits, a successor algebra in KK is an object XX equipped with morphisms o:1Xo:1\to X and s:XXs:X\to X. A morphism of successor algebras is a morphism f:XYf:X\to Y with isomorphisms fo Xo Yf o_X \cong o_Y and fs Xs Yff s_X \cong s_Y f. Likewise a 2-cell of successor algebras is a 2-cell α:fg\alpha: f\to g commuting with the above isomorphisms in an obvious way.

Finally, a natural numbers object in KK is an initial object NN in the 2-category SuccAlg(K)SuccAlg(K) of successor algebras. This means that for any successor algebra XX there is a morphism NXN\to X of successor algebras, unique up to unique isomorphism. Clearly any NNO in KK is also an NNO, in the usual sense, in disc(K)disc(K).

If KK doesn’t have enough exponentials, then perhaps this definition should be augmented with some parametricity, as in the 1-categorical case.

As in a 1-category, we can prove that:

  • If KK has coproducts, then [o,s]:1+NN[o,s]:1+N \to N is an equivalence, since NN is an initial algebra for the endofunctor 1+()1+(-).
  • Therefore, if KK is extensive, then o:1No:1\to N and s:NNs:N\to N are disjoint subobjects of NN.
  • NN satisfies the fifth Peano axiom: if NN' is a subobject of NN containing oo and closed under ss, then N=NN'=N.

This enables us to show the following, using the internal logic.

Theorem

If KK is a positive Heyting coherent 2-category with an NNO NN, then NN is discrete.

Proof

First note that since N1+NN\simeq 1+N and coproducts are disjoint, we have

x:N,f:hom N(o,x),g:hom N(x,o) f=gand is an isomorphism x:N,f:hom N(x,o),g:hom N(o,x) f=gand is an isomorphism\begin{aligned} x:N, f:hom_N(o,x), g:hom_N(x,o) &\vdash f=g\;\text{and is an isomorphism}\\ x:N, f:hom_N(x,o), g:hom_N(o,x) &\vdash f=g\;\text{and is an isomorphism} \end{aligned}

Now consider the subobject SNS\hookrightarrow N described in the internal logic as determined by those y:Ny:N for which the above sequents remain true when oo is replaced by yy. (This requires universal quantification over x,f,gx,f,g.) The above observation shows that oSo\in S. Suppose that ySy\in S, x:Nx:N, and f:hom N(sy,x)f:hom_N(s y, x), g:hom N(sy,x)g:hom_N(s y,x). If x=ox=o then f=gf=g and is an isomorphism; otherwise x=szx = s z; but ss is ff, so we have f:hom N(y,z)f':hom_N(y,z) and g:hom N(y,z)g':hom_N(y,z) which are equal and isomorphisms; hence so are f=s(f)f= s(f') and g=s(g)g=s(g'). Thus, SS is closed under ss, so it is all of NN. Therefore, NN is discrete.

Exponentials in a 2-category

Cat is not locally cartesian closed

The 2-category CatCat is cartesian closed, in an appropriate 2-categorical sense; see also the discussion here. However, it is not locally cartesian closed. This failure is fundamental and has nothing to do with strictness or size issues; pullbacks just don’t preserve colimits. For example, let X=(012)X=(0\to 1\to 2) be the ordinal 3\mathbf{3}; then there is a pushout

(1) (12) (01) (012)\array{(1) & \to & (1\to 2)\\ \downarrow && \downarrow\\ (0\to 1) & \to & (0\to 1\to 2)}

in Cat/XCat/X which pulls back along the inclusion (02)X(0\to 2)\to X to

(2) (0) (02)\array{\emptyset & \to & (2)\\ \downarrow && \downarrow\\ (0) & \to & (0\to 2)}

which is certainly not a pushout. Note that the same counterexample applies in PosPos.

It is similarly easy to write down examples of coinserters, coinverters, and coequifiers that are not preserved by pullbacks. Coproducts are preserved by pullback (in fact, CatCat is extensive), as are quotients of 2-congruences (since CatCat is regular), but these seem to be about it for pullback-stable colimits in CatCat.

2-categories with exponentials

However, there are a number of other useful exponentiability properties that do hold when K=CatK=Cat.

  1. Fibrations and opfibrations are exponentiable. That is, if f:AXf:A\to X is an (op)fibration, then exponentials (BX) (AX)(B\to X)^{(A\to X)} exist in the slice 2-category K/XK/X. Equivalently, f *:K/XK/Af^*:K/X\to K/A has a right adjoint Π f\Pi_f. (Fibrations and opfibrations are not the only exponentiable morphisms in CatCat, but they are some of the most important, commonly encountered, and easily characterized ones.)

  2. If AXA\to X is an opfibration and BXB\to X is a fibration, then the exponential (BX) (AX)(B\to X)^{(A\to X)} in K/XK/X is a fibration, and dually.

  3. For any f:YXf:Y\to X, the functor f *:Fib(X)Fib(Y)f^*:Fib(X)\to Fib(Y) has a right adjoint Ran fRan_f, and likewise for f *:Opf(X)Opf(Y)f^*:Opf(X)\to Opf(Y).

  4. For any f:YXf:Y\to X, the functors f *:DFib(X)DFib(Y)f^*:DFib(X)\to DFib(Y) and f *:DOpf(X)DOpf(Y)f^*:DOpf(X)\to DOpf(Y) have right adjoints Ran fRan_f.

  5. The 2-categories Fib(X)Fib(X) and Opf(X)Opf(X) are all cartesian closed.

  6. KK itself is cartesian closed.

  7. The 2-categories DFib(X)DFib(X) and DOpf(X)DOpf(X) are all locally cartesian closed.

Note that Ran fRan_f and Π f\Pi_f are not the same even when both exist, and likewise the exponentials in Fib(X)Fib(X) are not the same as the exponentials in K/XK/X even when both exist. The latter are better-behaved in some ways, for instance they are stable under pullback (because they are “fiberwise”).

Perhaps surprisingly, it turns out that the first of these properties is sufficient to imply all the others. The goal of the rest of this page is to prove this claim. Therefore, we define:

Definition

A 2-category KK with finite limits is said to have exponentials if all fibrations and opfibrations in KK are exponentiable.

Note that a 1-category, and in fact any (2,1)-category, has exponentials if and only if it is locally cartesian closed, since every morphism is a fibration and opfibration.

Basic observations

We begin with a couple of easy observations.

Proposition

If either fibrations or opfibrations are exponentiable in KK, then KK is cartesian closed.

Proof

Of course, KK is cartesian closed just when every morphism A1A\to 1 is exponentiable; but every such morphism is both a fibration and an opfibration.

Proposition

If AXA\to X is an opfibration and BXB\to X is a fibration, then the exponential (BX) (AX)(B\to X)^{(A\to X)} in K/XK/X (if it exists) is a fibration, and dually.

Proof

We say briefly how to construct an action morphism

X 2× X(BX) (AX)(BX) (AX).X ^{\mathbf{2}} \times_X(B\to X)^{(A\to X)} \to (B\to X)^{(A\to X)}.

Of course, by adjointness it suffices to construct a morphism

A× XX 2× X(BX) (AX)BA\times_X X ^{\mathbf{2}} \times_X (B\to X)^{(A\to X)} \to B

over XX. Now the left-hand side is a limit of the diagram

(BX) (AX) X 2 X A X.\array{ &&&& (B\to X)^{(A\to X)}\\ &&&& \downarrow\\ && X ^{\mathbf{2}} &\to & X\\ && \downarrow\\ A & \to & X.}

We first map it via a diagonal to the limit of

(BX) (AX) X 2 X A X X 2\array{ &&&& (B\to X)^{(A\to X)}\\ &&&& \downarrow\\ && X ^{\mathbf{2}} &\to & X\\ && \downarrow && \uparrow\\ A & \to & X & \leftarrow & X ^{\mathbf{2}}}

then use the covariant action of XX on AA to map to the limit of

(BX) (AX) A X X X 2\array{ && (B\to X)^{(A\to X)}\\ && \downarrow\\ A &\to & X\\ && \uparrow\\ X & \leftarrow & X ^{\mathbf{2}}}

then the evaluation A× X(BX) (AX)BA\times_X (B\to X)^{(A\to X)} \to B to get to the limit of

B X X X 2\array{ && B\\ && \downarrow\\ && X\\ && \uparrow\\ X & \leftarrow & X ^{\mathbf{2}}}

and finally the contravariant action of XX on BB to get to

B X.\array{ B\\ \downarrow \\ X.}

It is then straightforward to check that this action makes (BX) (AX)(B\to X)^{(A\to X)} into a fibration.

Comonadicity

The key observation for many of the proofs below is the following.

Lemma

If KK has exponentials, then for any XX, Fib(X)Fib(X) and Opf(X)Opf(X) are comonadic, as well as monadic, over K/XK/X.

Proof

The monad on K/XK/X whose category of algebras is Fib(X)Fib(X) takes AXA\to X to X 2× XAX ^{\mathbf{2}} \times_X A, or equivalently Σ st *A\Sigma_s t^*A where (s,t):X 2X(s,t):X ^{\mathbf{2}} \;\rightrightarrows\; X are the two projections. But tt is an opfibration, so Σ st *\Sigma_s t^* has a right adjoint Π ts *\Pi_t s^*. And it is a standard result, valid for 2-categories as for 1-categories, that when the underlying functor of a monad has a right adjoint, its right adjoint becomes a comonad whose category of coalgebras is equivalent to the category of algebras for the original monad.

Corollary

If KK has exponentials, then Fib(X)Fib(X) and Opf(X)Opf(X) inherit any colimits possessed by KK.

Proof

The category of coalgebras for any comonad inherits colimits from the base category, and slice (2-)categories always inherit colimits.

For our main applications of comonadicity, we require the following observation.

Proposition

Given a commutative square

D 1 G¯ D 2 U 1 U 2 C 1 G C 2\array{D_1 & \overset{\overline{G}}{\to} & D_2\\ ^{U_1}\downarrow && \downarrow ^{U_2}\\ C_1 & \underset{G}{\to} & C_2}

of functors between 2-categories, if U 1U_1 and U 2U_2 are monadic, D 1D_1 has reflexive codescent objects, and GG has a left adjoint, then G¯\overline{G} also has a left adjoint. Dually, if U 1U_1 and U 2U_2 are comonadic, D 1D_1 has reflexive descent objects, and GG has a right adjoint, then G¯\overline{G} also has a right adjoint.

Proof

The 1-categorical version of this, referring to reflexive (co)equalizers, is well-known; see for instance

  • P. T. Johnstone, Adjoint lifting theorems for categories of algebras.

The idea is the same as that in Beck’s (co)monadicity theorem: we express any object of D 2D_2 as a reflexive coequalizer of free algebras, then apply the left adjoint of GG to obtain a reflexive pair of free algebras in D 1D_1 and take its coequalizer. The 2-categorical version is analogous, using the ideas of a 2-categorical monadicity theorem as found, for example, in

  • Claudio Hermida, Descent on 2-fibrations and strongly 2-regular 2-categories.

The dual is, of course, obvious.

Slicing and cartesian closure

Using comonadicity, we can show that certain exponentials are stable under slicing. First we observe:

Lemma

If YXY\to X is a fibration, then Fib(X)/YFib(X)/Y is monadic over K/YK/Y. If additionally KK has exponentials, then Fib(X)/YFib(X)/Y is also comonadic over K/YK/Y.

Proof

The first statement is an instance of a general fact: if TT is a monad on a (2-)category CC and YY is a TT-algebra, then there is an induced monad T YT_Y on C/YC/Y whose (2-)category of algebras is TAlg/YT Alg/Y, defined by taking AYA\to Y to the composite TATYYT A \to T Y \to Y.

The second statement is also an instance of a general fact: if such a TT has a right adjoint GG, then T YT_Y also has a right adjoint G YG_Y defined to take AYA\to Y to the pullback

G YA GA Y GY.\array{G_Y A & \to & G A\\ \downarrow && \downarrow\\ Y & \to & G Y.}

Here the lower map YGYY\to G Y is the adjunct of the algebra structure map TYYT Y\to Y.

Proposition

If KK has exponentials, then a morphism in Fib(X)Fib(X) or Opf(X)Opf(X) is exponentiable if its underlying morphism in KK is so. In particular, if KK has exponentials, then for any XX, fibrations are exponentiable in Fib(X)Fib(X) and opfibrations are exponentiable in Opf(X)Opf(X).

Proof

Suppose that f:ZYf:Z\to Y is a morphism in Fib(X)Fib(X) and that ff is exponentiable in KK. Then we have a commutative square

Fib(X)/Y f * Fib(X)/Z K/Y f * K/Z\array{Fib(X)/Y & \overset{f^*}{\to} & Fib(X)/Z\\ \downarrow && \downarrow\\ K/Y& \underset{f^*}{\to} & K/Z}

in which the vertical functors are comonadic by Lemma , and the bottom functor f *f^* has a right adjoint since ff is exponentiable in KK. Therefore, by Proposition , the top functor f *f^* has a right adjoint as well. The second statement follows because the underlying morphism in KK of any fibration in Fib(X)Fib(X) is a fibration in KK, and dually (see the theorems on iterated fibrations).

Corollary

If KK has exponentials and a duality involution, then Fib(X)Fib(X) and Opf(X)Opf(X) also have exponentials for any XX.

Proof

After Proposition , it remains to show that opfibrations are exponentiable in Fib(X)Fib(X) (and dually, fibrations are exponentiable in Opf(X)Opf(X)). Note that an opfibration in Fib(X)Fib(X) will not, in general, be an opfibration in KK. But with a duality involution we have Fib(X)Opf(X o)Fib(X)\simeq Opf(X^o), and opfibrations are exponentiable in Opf(X o)Opf(X^o), hence also in Fib(X)Fib(X).

We say that a 2-category KK has local exponentials if KK has exponentials and each 2-category Fib(X)Fib(X) and Opf(X)Opf(X) also has local exponentials. Of course, the recursion in this definition is not well-founded, but we can reformulate it in explicit terms to say that

  1. KK has exponentials,
  2. Each Opf(X)Opf(X) and Fib(X)Fib(X) has exponentials,
  3. Each Opf Fib(X)(AX)Opf_{Fib(X)}(A\to X) and Fib Opf(X)(AX)Fib_{Opf(X)}(A\to X) has exponentials,
  4. and so on.

Since duality involutions are stable under fibrational slicing, Corollary implies that if KK has exponentials and a duality involution, then it has local exponentials. It would be nice to have a finite list of axioms that implies local exponentials without invoking a duality involution (since not all Grothendieck 2-toposes have dualities).

Corollary

If KK has exponentials, then the 2-categories Fib(X)Fib(X) and Opf(X)Opf(X) are all cartesian closed.

Proof

Combine Propositions and .

Corollary

If KK has exponentials, then the categories DFib(X)DFib(X) and DOpf(X)DOpf(X) are all locally cartesian closed.

Proof

Since right adjoints preserve discrete objects, Corollary implies that DFib(X)DFib(X) and DOpf(X)DOpf(X) are cartesian closed for any XX. Now, given a discrete fibration AXA\to X, we have Fib K(A)Fib Fib(X)(AX)Fib_K(A) \simeq Fib_{Fib(X)}(A\to X) by the theorem on iterated fibrations, and so DFib K(A)DFib Fib(X)(AX)DFib K(X)/(AX)DFib_K(A) \simeq DFib_{Fib(X)}(A\to X) \simeq DFib_K(X)/(A\to X). Thus, since DFib K(A)DFib_K(A) is cartesian closed, so is DFib K(X)/(AX)DFib_K(X)/(A\to X), and thus DFib K(X)DFib_K(X) is locally cartesian closed.

Left Kan extensions

We now turn to the existence of left and right adjoints to pullback functors. So far what we know is

  • f *:K/YK/Xf^*:K/Y\to K/X always has a left adjoint Σ f\Sigma_f given by composition with ff.
  • If KK has exponentials and ff is a fibration or opfibration, then (by definition) f *:K/YK/Xf^*:K/Y\to K/X has a right adjoint Π f\Pi_f.
  • If KK has a comprehensive factorization (such as when it is countably-coherent), then f *:DFib(Y)DFib(X)f^*:DFib(Y)\to DFib(X) and f *:DOpf(Y)DOpf(X)f^*:DOpf(Y)\to DOpf(X) have left adjoints Lan fLan_f, which satisfy the Beck-Chevalley condition for comma squares.

Note that even if ff is a fibration, so that Σ f\Sigma_f maps Fib(Y)Fib(Y) to Fib(X)Fib(X), it will not in general be a left adjoint to f *:Fib(X)Fib(Y)f^*:Fib(X)\to Fib(Y). However, if ff is a discrete fibration, then Σ f:DFib(Y)DFib(X)\Sigma_f:DFib(Y)\to DFib(X) is left adjoint to f *:DFib(X)DFib(Y)f^*:DFib(X)\to DFib(Y), since DFib(X)DFib(X) is a full sub-2-category of K/XK/X.

We now consider how to construct left adjoints for non-discrete fibrations.

Proposition

If KK has exponentials and reflexive codescent objects, then each pullback functor f *:Fib(Y)Fib(X)f^*:Fib(Y)\to Fib(X) and f *:Opf(Y)Opf(X)f^*:Opf(Y)\to Opf(X) has a left adjoint Lan fLan_f.

Proof

Because of the existence of Σ f\Sigma_f, by Proposition it suffices to show that Fib(X)Fib(X) and Opf(X)Opf(X) always have reflexive codescent objects; but this follows from Corollary .

The basic first-order structure we are interested in doesn’t imply the existence of such codescent objects, and a Heyting 2-pretopos, such as FinCatFinCat, need not have them. But they can be constructed with some infinitary structure; see colimits in an n-pretopos.

I do not know whether these adjunctions always satisfy the Beck-Chevalley condition for comma squares (although they do in one important case; see below).

Right Kan extensions

We now consider the existence of right adjoints to pullback functors between fibrational slices.

Proposition

If KK has exponentials, then f *:Opf(X)Opf(Y)f^*:Opf(X)\to Opf(Y) and f *:Fib(X)Fib(Y)f^*:Fib(X)\to Fib(Y) have right adjoints Ran fRan_f for any ff.

Proof

If ff is exponentiable in KK, this follows directly from Lemma and Proposition . In particular, this applies when ff is a fibration or opfibration.

Now let f:YXf:Y\to X be any morphism, and consider the comma square:

Comma Square ( 1 / f ) (1/f) X X Y Y X X t t s s 1 1 f f

Suppose first that all the left adjoints Lan gLan_g exist for opfibrational slices and satisfy the Beck-Chevalley condition for comma squares. Then this comma square gives us an equivalence f *Lan ts *f^*\simeq Lan_t s^*, so that f *:Opf(X)Opf(Y)f^*:Opf(X)\to Opf(Y) has the right adjoint Ran f:=Ran st *Ran_f := Ran_s t^*.

We now show that regardless of the overall existence of left adjoints, the particular value Lan ts *(A)Lan_t s^*(A) exists for any AOpf(X)A\in Opf(X) and is given by f *Af^*A. This clearly suffices to prove the result.

According to the proof of Proposition , Lan ts *(A)Lan_t s^*(A) should be given by the codescent object of

Descent object R R S S T T

where

T= Σ ts *A× YY 2 S= Σ t(s *A× (1/f)(1/f) 2)× YY 2 R= Σ t(s *A× (1/f)(1/f) 2× (1/f)(1/f) 2)× YY 2. \begin{aligned} T =& \Sigma_t s^* A \times_Y Y ^{\mathbf{2}}\\ S =& \Sigma_t \left(s^* A\times_{(1/f)} (1/f)^{\mathbf{2}}\right) \times_Y Y ^{\mathbf{2}}\\ R =& \Sigma_t \left(s^* A\times_{(1/f)} (1/f)^{\mathbf{2}} \times_{(1/f)} (1/f)^{\mathbf{2}}\right) \times_Y Y ^{\mathbf{2}}. \end{aligned}

Now we have a map

q:Σ ts *A× YY 2f *A× YY 2f *A;q:\Sigma_t s^* A \times_Y Y ^{\mathbf{2}} \to f^* A \times_Y Y ^{\mathbf{2}} \to f^*A;

the first map is a Beck-Chevalley morphism, and the second comes from the fact that f *Af^*A is an opfibration. We claim that qq is actually a codescent object of the above diagram, and in fact it is a split codescent object. Recall from

  • Claudio Hermida, Descent on 2-fibrations and strongly 2-regular 2-categories.

that a split codescent object is a diagram

Descent object R R π 01 \pi_{01} π 12 \pi_{12} π 02 \pi_{02} μ \mu S S c c d d τ \tau T T q q σ \sigma Q Q

with isomorphisms cτσqc\tau \cong \sigma q, π 12μτc\pi_{12} \mu \cong \tau c, π 02μτd\pi_{02}\mu \cong \tau d, 1π 01μ1\cong\pi_{01}\mu, 1dτ1\cong d\tau, and 1qσ1\cong q\sigma satisfying certain axioms. In this situation, qq is necessarily the codescent object of the diagram composed of d,c,π 01,π 02,π 12d,c,\pi_{01},\pi_{02},\pi_{12}.

Tracing through the definitions above, we see that our TT is the limit of the span AXYA\to X \leftarrow Y weighted by

(0)(012)(12).(0) \;\to\; (0\to 1\to 2) \;\leftarrow\; (1\to 2).

Likewise, SS is the limit of AXYA\to X \leftarrow Y weighted by

(0)(0 1 2 3 4)(234)(0) \;\to\; \left(\array{0&\to&1\\ \downarrow && \downarrow \\ 2 &\to & 3& \to & 4}\right) \;\leftarrow\; (2 \to 3\to 4)

and RR is the limit by an evident more complicated weight. Finally, f *Af^*A itself is the limit of the same span weighted by

()()().(\cdot) \;\to\; (\cdot) \;\leftarrow\; (\cdot).

The morphism qq is induced by the action of XX on the opfibration AA, applied twice. The morphism dd is induced by the inclusion of the second arrow in a composable pair and the action of XX on AA applied once. The morphism cc is induced by the composition of a composable pair. We define the splitting σ,τ,μ\sigma,\tau,\mu in terms of the limit weights by adding in identity morphisms in appropriate places. It is then straightforward to check that the axioms for a split codescent object are satisfied.

Corollary

If KK has exponentials, then f *:DOpf(X)DOpf(Y)f^*:DOpf(X)\to DOpf(Y) and f *:DFib(X)DFib(Y)f^*:DFib(X)\to DFib(Y) have right adjoints Ran fRan_f for any ff.

Proof

Right adjoints preserve discrete objects.

This completes the proof that exponentiability of fibrations and opfibrations implies all the other notable exponentiability properties we might want to require of a 2-category.

Enrichment

One further observation:

Proposition

If KK has exponentials, then each category DFib(X)DFib(X) is enriched over the cartesian closed category disc(K)disc(K).

Proof

We define the hom-object DFib(X)(A,B)\mathbf{DFib(X)}(A,B) to be Ran XB ARan_X B^A, where B AB^A is the exponential in DFib(X)DFib(X) and

Ran X:DFib(X)DFib(1)disc(K)Ran_X:DFib(X) \to DFib(1)\simeq disc(K)

is the right adjoint to X *X^*. A composition map is obtained by adjointness in the usual way. We also have

K(1,DFib(X)(A,B)) K(1,Ran XB A) DFib(X)(1 X,B A) DFib(X)(A,B)\begin{aligned} K(1,\mathbf{DFib(X)}(A,B)) \cong& K(1, Ran_X B^A)\\ \cong& DFib(X)(1_X, B^A)\\ \cong& DFib(X)(A,B) \end{aligned}

so the underlying ordinary category of this disc(K)disc(K)-enriched category is the ordinary category DFib(X)DFib(X).

In fact, more is true: I believe DFib(X)DFib(X) can be made into a locally internal category, or equivalently a locally small fibration, over disc(K)disc(K). Its fiber over a discrete object ZKZ\in K is the category DFib(X×Z)DFib(X\times Z). This follows by localizing the previous lemma in the slices Fib(Z)K/ZFib(Z)\simeq K/Z; one also has to check that a suitable Beck-Chevalley condition is satisfied by the right adjoints Ran fRan_f.

Duality involutions

An important structure possessed by the 2-category CatCat is the duality involution () op:Cat coCat(-)^{op}:Cat^{co}\to Cat. Here we consider what the important properties of this involution are that should be generalized to other 2-categories.

Involutions

The most obvious property of () op(-)^{op} is that it is coherently self-inverse. To state this formally, let JJ be the walking isomorphism (01)(0 \overset{\cong}{\to} 1), considered as a 3-category with only identity 2-cells and 3-cells. Thus, a (pseudo) functor from JJ to any 3-category TT can be considered an “internal adjoint (bi)equivalence in TT.” If TT is a 3-category, let C 3opC^{3op} denote the 3-cell dual of TT; note that J 3opJJ^{3op}\cong J and that () co(-)^{co} is a functor 2Cat2Cat 3op2Cat\to 2Cat^{3op}. Finally, let τ:JJJ 3op\tau:J\to J\cong J^{3op} be the evident involution that switches 00 and 11.

Definition

A 2-contravariant involution (hereafter merely an involution) on a 2-category KK is functor W:J2CatW:J\to 2Cat such that W(0)=KW(0)=K and the square

J τ J 3op W W 2Cat () co 2Cat 3op\array{J & \overset{\tau}{\to} & J^{3op}\\ ^W \downarrow && \downarrow^W\\ 2Cat & \underset{(-)^{co}}{\to} & 2Cat^{3op}}

commutes (on the nose).

We write () o:KK co(-)^o:K\to K^{co} (or equivalently K coKK^{co}\to K) for the functor W(01)W(0\to 1); the rest of the data of WW simply says that (() o) oId((-)^o)^o\cong Id in a coherent way.

Example

Any (2,1)-category KK admits a canonical involution that is the identity on objects and morphisms and sends each 2-cell to its inverse.

Example

Let CC be a 2-category equipped with an involution and let K=[C,Cat]K=[C,Cat]. Then KK has a canonical induced involution defined by

[C,Cat] co[C co,Cat co][C,Cat co]() op[C,Cat].[C,Cat]^{co} \overset{\simeq}{\to} [C^{co},Cat^{co}] \overset{\simeq}{\to} [C, Cat^{co}] \overset{(-)^{op}\circ -}{\to} [C,Cat].

Conversely, if CC is Cauchy-complete, then C opC^{op} can be identified with the full subcategory of indecomposable projectives in KK, and thus an involution on KK induces an involution on CC.

Thus, in particular, any (2,1)-truncated 2-presheaf 2-topos admits a canonical involution. However, in general a 2-category that admits an involution will admit many involutions.

Proposition

For any 2-category KK, the 2-category Inv(K)Inv(K) of involutions on KK, if nonempty, is a torsor for the 3-group Aut(K)Aut(K) of (covariant) automorphisms of KK.

Proof

Easy.

In particular, any automorphism of a (2,1)-category CC induces an involution on [C,Cat][C,Cat].

Duality Involutions

As observed by WeberYS2T, experience suggests that the most important additional property of the involution () op(-)^{op} on CatCat is that fibrations over AA can be identified with opfibrations over A opA^{op}, since both are equivalent to functors A opCatA^{op}\to Cat. So it is reasonable to consider, together with an involution () o(-)^o on a 2-category KK, a family of equivalences Fib(X)Opf(X o)Fib(X)\simeq Opf(X^o).

The next question is what additional properties should be required of such a family. The following definition is provisional, but I believe whatever eventual definition we settle on should allow the construction of all the data given below.

Definition

A duality involution on a 2-category KK is an involution () o(-)^o together with the following data.

  1. Equivalences of 2-categories
    V X:Fib(X)Opf(X o)V_X:Fib(X) \simeq Opf(X^o)

    which are natural in XX (that is, VV is a natural equivalence between functors K coop2CatK^{coop}\to 2Cat),

  2. An equivalence between V 1:Fib(1)Opf(1 o)V_1:Fib(1)\simeq Opf(1^o) and the composite Fib(1)KOpf(1)Opf(1 o)Fib(1)\simeq K \simeq Opf(1)\simeq Opf(1^o) (note 1 o11^o\simeq 1 since () o(-)^o is an equivalence).
  3. For any pullback square
    P A B X\array{P & \to & A\\ \downarrow && \downarrow\\ B & \to & X}

    in which all the displayed maps are fibrations, an invertible modification between the two composites

    Fib(P)V POpf(P o)Opf Opf(A o)(P oA o)V A 1Opf Fib(A)(V AP oA) Opf Fib Fib(X)(AX)(V AP oA)Fib Fib(X)(V X 1B o,A)\begin{gathered} Fib(P) \overset{V_P}{\to} Opf(P^o) \simeq Opf_{Opf(A^o)}(P^o\to A^o) \overset{V_A^{-1}}{\to} Opf_{Fib(A)}(V_A P^o \to A)\\ \simeq Opf_{Fib_{Fib(X)}(A\to X)}(V_A P^o\to A) \simeq Fib_{Fib(X)}(V_X^{-1} B^o, A) \end{gathered}

    and

    Fib(P)Fib Fib(B)(PB)V BFib Opf(B o)(V BPB o)Fib Opf Opf(X o)(B oX o)(V BPB o) V X 1Fib Opf Fib(X)(V X 1B oX)(V X 1V BPV X 1B o)Fib Fib(X)(V X 1B o,A).\begin{gathered} Fib(P) \simeq Fib_{Fib(B)}(P\to B) \overset{V_B}{\to} Fib_{Opf(B^o)}(V_B P\to B^o) \simeq Fib_{Opf_{Opf(X^o)}(B^o\to X^o)}(V_B P\to B^o)\\ \overset{V_X^{-1}}{\to} Fib_{Opf_{Fib(X)}(V_X^{-1} B^o\to X)}(V_X^{-1} V_B P\to V_X^{-1} B^o) \simeq Fib_{Fib(X)}(V_X^{-1} B^o, A). \end{gathered}
  4. An invertible modification filling the square
    Fib(X) V X Opf(X o) () o () o Opf(X o) co V X 1 Fib(X) co.\array{Fib(X) & \overset{V_X}{\to} & Opf(X^o)\\ (-)^o\downarrow && \downarrow (-)^o\\ Opf(X^o)^{co}& \underset{V_X^{-1}}{\to} & Fib(X)^{co}.}

    which commutes with the previous two equivalences.

Perhaps there should also be some coherence data and axioms relating these data to each other.

The first two data should be fairly self-explanatory, but the third datum may seem quite complicated. In fact, it requires some thought to see that the two displayed composites are even well-defined. Note first that since P=A× XBP=A\times_X B, by naturality of VV we have V BPB o× X oV XAV_B P \simeq B^o\times_{X^o} V_X A, and thus V X 1V BPV X 1B o× XAV_X^{-1} V_B P \simeq V_X^{-1} B^o\times_X A. Also, P oB o× X oA oP^o \simeq B^o\times_{X^o} A^o, so again by naturality V A 1P oV X 1B o× XAV_A^{-1} P^o \simeq V_X^{-1} B^o \times_X A. Thus V X 1V BPV A 1P oV_X^{-1} V_B P\simeq V_A^{-1} P^o, and the final two equivalences in each displayed composite are instances of the theorem on iterated fibrations. One way to think about this datum is as sort of an “inclusion-exclusion” property for reversal of arrows.

We call the final datum commutation of opposites. To explain it, observe that because () o(-)^o is a 2-contravariant involution, we automatically have equivalences Fib K(X)Fib K co(X o)=Opf K(X o) coFib_K(X) \simeq Fib_{K^{co}}(X^o) = Opf_K(X^o)^{co} (these are the vertical maps in the displayed square). In CatCat, this equivalence corresponds to composing a functor A opCatA^{op}\to Cat with () op:CatCat(-)^{op}:Cat\to Cat as well as reinterpreting it as an opfibration. Commutation of opposites then says that this operation commutes with VV.

One immediate application of commutation of opposites is to deduce a version of the third datum for a pullback square of opfibrations, by passage along the equivalences Fib(X)Opf(X o) coFib(X)\simeq Opf(X^o)^{co}. We will see others below.

Example

If KK is a (2,1)-category, then its canonical involution extends to a canonical duality involution, since Fib(X)K/XOpf(X)Fib(X)\simeq K/X\simeq Opf(X).

Example

If CC is a (2,1)-category, then the canonical involution on K=[C,Cat]K=[C,Cat] extends in a natural way to a duality involution. This does not seem to be the case if CC is merely a 2-category equipped with an involution.

The 3-group Aut(K)Aut(K) also acts on the 2-category DualInv(K)DualInv(K) of duality involutions on KK; the action is free but (seemingly) no longer necessarily transitive. However, I do not know an example of two inequivalent duality involutions having the same underlying involution (as would be necessary for non-transitivity).

The differences between Definition and the definition of WeberYS2T are threefold.

  1. Our definition is less strict; () o(-)^o is only required to be self-inverse in a 2-categorically non-evil way.
  2. Our definition refers to arbitrary fibrations and opfibrations, rather than merely discrete ones.
  3. Our definition refers only to one-sided fibrations, whereas WeberYS2T requires an equivalence DFib(A×B,C)DFib(A,B o×C)DFib(A\times B, C)\simeq DFib(A,B^o\times C).

Of course, since any equivalence of 2-categories preserves discrete objects, our definition implies an equivalence DFib(X)DOpf(X o)DFib(X)\simeq DOpf(X^o). More surprisingly, it turns out that the seemingly stronger two-sided version is a consequence of our definition.

Theorem

If KK is equipped with a duality involution, then we have natural equivalences Fib(A×B,C)Fib(A,B o×C)Fib(A\times B,C)\simeq Fib(A, B^o\times C).

Proof

We first construct an equivalence Opf(A×B)Fib(A,B o)Opf(A\times B)\simeq Fib(A,B^o). Note that since Fib(1)Opf(1 o)Fib(1)\simeq Opf(1^o) is the identity, naturality implies that V A(A×B)A o×BV_A(A\times B) \simeq A^o\times B. Also, since () o(-)^o is an equivalence, and products in KK are the same as products in K coK^{co}, we have (A×B) oA o×B o(A\times B)^o \simeq A^o\times B^o. Now we have the composite equivalence (using the theorem on iterated fibrations):

Opf(A×B)Opf Opf(B)(A×BB)V BOpf Fib(B o)(A×B oB o)Fib(A,B o).Opf(A\times B) \simeq Opf_{Opf(B)}(A\times B \to B) \overset{V_B}{\to} Opf_{Fib(B^o)}(A\times B^o \to B^o) \simeq Fib(A,B^o).

Note that there is also another equivalence

Opf(A×B)V A×BFib((A×B) o)Fib Fib(A o)(A o×B oA o)V AFib Opf(A)(A×B oA)Fib(A,B o),Opf(A\times B) \overset{V_{A\times B}}{\to} Fib((A\times B)^o) \simeq Fib_{Fib(A^o)}(A^o\times B^o\to A^o) \overset{V_A}{\to} Fib_{Opf(A)}(A\times B^o\to A) \simeq Fib(A,B^o),

but the second and third data in the definition of a duality involution supply a canonical equivalence between these composites, so it doesn’t matter which we use. Finally, for the general case, we simply apply this twice:

Fib(A×B,C)Opf(A×B×C o)Opf(A×(B o×C) o)Fib(A,B o×C).Fib(A\times B, C) \simeq Opf(A\times B\times C^o) \simeq Opf(A\times (B^o\times C)^o) \simeq Fib(A, B^o\times C).

This gives our desired equivalence.

Note, though, that this proof crucially requires that the duality involution come with an equivalence Fib(X)Opf(X o)Fib(X)\simeq Opf(X^o), and not merely DFib(X)DOpf(X o)DFib(X)\simeq DOpf(X^o).

Commutation of opposites, which we have not yet used, is necessary for the following important, and perhaps also surprising, result: duality involutions are preserved by (fibrational) slicing.

Theorem

Any duality involution on KK induces a duality involution on each fibrational slice Fib K(X)Fib_K(X) and Opf K(X)Opf_K(X).

Proof

We define () o X:Fib(X) coFib(X)(-)^{o_X}:Fib(X)^{co}\to Fib(X) to be the composite

Fib(X)() oOpf(X o) coV X 1Fib(X) co.Fib(X) \overset{(-)^o}{\to} Opf(X^o)^{co} \overset{V_{X}^{-1}}{\to} Fib(X)^{co}.

To show that () o X(-)^{o_X} is an involution, we verify

(A o X) o X=V X 1((V X 1(A o)) o)V X 1(V X((A o) o))(A o) oA.(A^{o_X})^{o_X} = V_X^{-1}((V_X^{-1}(A^o))^o) \simeq V_X^{-1}(V_X((A^o)^o)) \simeq (A^o)^o \simeq A.

Here we use commutation of opposites in KK to commute () o(-)^o past V XV_X. We now define

V A X:Fib Fib(X)(A)Opf Fib(X)(A o X)V^X_A: Fib_{Fib(X)}(A) \simeq Opf_{Fib(X)}(A^{o_X})

to be the composite

Fib Fib(X)(A)Fib(A)V AOpf(A o)Opf Opf(X o)(A o)V X 1Opf Fib(X)(V X(A o))=Opf Fib(X)(A o X).Fib_{Fib(X)}(A) \simeq Fib(A) \overset{V_A}{\to} Opf(A^o) \simeq Opf_{Opf(X^o)}(A^o) \overset{V_X^{-1}}{\to} Opf_{Fib(X)}(V_X(A^o)) = Opf_{Fib(X)}(A^{o_X}).

It is easy to see that V 1 X XV X 1V X1V^X_{1_X}\simeq V_X^{-1}\circ V_X \simeq 1, and to construct the pullback-commutation equivalence. Finally, we construct commutation of opposites in Fib(X)Fib(X) as the composite

(V A X(B)) o XV X 1((V X 1(V A(B))) o)V X 1(V X((V A(B)) o))(V A(B)) oV A 1(B o)V A 1(V X(V X 1(B o)))=(V A X) 1(B o X).(V^X_A(B))^{o_X} \simeq V_X^{-1}((V_X^{-1}(V_A(B)))^o) \simeq V_X^{-1}(V_X((V_A(B))^o)) \simeq (V_A(B))^o\simeq V_A^{-1}(B^o)\simeq V_A^{-1}(V_X(V_X^{-1}(B^o))) = (V^X_A)^{-1}(B^{o_X}).

The case of Opf(X)Opf(X) is dual.

Fixing groupoids

We saw above that in general, a 2-category admitting an involution or duality involution will admit many. One way to get rid of some of these spurious involutions is to require that () o(-)^o fix groupoidal objects, as is clearly the case for the involution of CatCat and the “canonical” involutions of (2,1)-truncated 2-presheaf 2-toposes.

Note that any involution takes groupoidal objects to groupoidal objects.

Definition

An involution () o(-)^o on KK fixes groupoids it it restricts to the canonical involution on gpd(K)gpd(K), i.e. if X oXX^o\simeq X coherently whenever XX is groupoidal.

Lemma

If KK is a regular nn-category having enough groupoids, then it admits, up to equivalence, at most one involution that fixes groupoids. If KK is also nn-exact, then it admits exactly one such involution.

Proof

Suppose that () o(-)^o is an involution on KK that fixes groupoids. Then for any AA and any groupoidal XX, we have

K(X,A o)K co(X o,A)K co(X,A)K(X,A) op.K(X,A^o) \cong K^{co}(X^o,A) \cong K^{co}(X,A) \cong K(X,A)^{op}.

Now given BB as well, with an eso p:XBp:X\to B where XX is groupoidal, any morphism BA oB\to A^o is determined by a map XA oX\to A^o with an action by ker(p)ker(p). But ker(p)=(p/p)ker(p)=(p/p) is also groupoidal, so morphisms BA oB\to A^o are completely determined by morphisms to AA out of groupoidal objects. Thus, by the Yoneda lemma, any two values of A oA^o must be canonically isomorphic.

Now suppose KK is exact, and let p:XAp:X\to A be an eso where XX is groupoidal. Then its kernel (p/p)(p/p) is also groupoidal, and so ker(p)ker(p) is a homwise-discrete category in gpd(K)gpd(K). Thus we can consider its opposite, which is also a homwise-discrete category in gpd(K)gpd(K). In general, the opposite of a 2-congruence in a 2-category will not be a 2-congruence, since the condition of being a two-sided fibration is not preserved. But in a (2,1)-category such as gpd(K)gpd(K), this extra condition is automatic, so this opposite of is also a 2-congruence in gpd(K)gpd(K) (and, in fact, an nn-congruence when KK is an nn-category). Thus, since KK is nn-exact, this opposite has a quotient, which we call A oA^o. It is straightforward to verify that this defines an involution on KK that fixes groupoids.

Of course, the only interesting values of nn in the above lemma are 2 and (1,2), since any groupoid-fixing involution on a (2,1)-category is equivalent to the canonical one. Of particular note is that any (2,1)-truncated Grothendieck 2-topos admits a unique groupoid-fixing involution.

In fact, this groupoid-fixing involution should also extend to a duality involution. For when KK is nn-exact, the functor Opf:K op2CatOpf:K^{op}\to 2Cat ought to be a 3-sheaf? (a 2-stack). This means that if p:XAp:X\to A is an eso with XX groupoidal, then Opf(A)Opf(A) can be reconstructed from Opf(X)Opf(X) and Opf(p/p)Opf(p/p) with descent data. Similarly, Fib:K coop2CatFib:K^{coop}\to 2Cat should also be a 3-sheaf, and so Fib(A)Fib(A) can be recovered from Fib(X)Fib(X) and Fib(p/p)Fib(p/p) with “op-descent data.” But since XX is groupoidal, Opf(X)Fib(X)Opf(X)\simeq Fib(X), and likewise for (p/p)(p/p). Therefore, descent data for ker(p)ker(p) over Opf(X)Opf(X), which determines an object of Opf(A)Opf(A), is the same as op-descent data for the opposite of ker(p)ker(p) over Fib(X)Fib(X), which determines an object of Fib(A o)Fib(A^o). This gives the equivalence Opf(A)Fib(A o)Opf(A) \simeq Fib(A^{o}).

Alternately, there is also a stronger theorem that if KK is 2-exact with enough groupoids, then it is equivalent to a particular 2-category of internal categories and anafunctors in the (2,1)-category gpd(K)gpd(K) (more precisely, it is the 2-exact completion of gpd(K)gpd(K)). And it is fairly easy to see, by its construction, that this 2-category has a duality involution, just as the 2-category of internal categories in any 1-category does.

Modulo the action of automorphisms, these are the only examples of duality involutions that I know. I do not know an example of a duality involution on a 2-category that does not have enough groupoids.

Fixing groupoids locally

Now, since a duality involution on KK extends to a duality involution on Fib K(X)Fib_K(X) and Opf K(X)Opf_K(X), it is natural to strengthen the notion of groupoid-fixing so that it carries over to fibrational slices. We write GFib(X)=gpd(Fib(X))GFib(X) = gpd(Fib(X)) and similarly GOpf(X)GOpf(X).

Definition

A duality involution () o(-)^o on KK fixes groupoids locally if we have a equivalence modification between V X:GFib(X)GOpf(X o)V_X:GFib(X)\to GOpf(X^o) and the composite GFib(X)() oGOpf(X o) coGOpf(X o)GFib(X) \overset{(-)^o}{\to} GOpf(X^o)^{co} \simeq GOpf(X^o).

The latter equivalence GOpf(X o) coGOpf(X o)GOpf(X^o)^{co} \simeq GOpf(X^o) is the canonical involution on the (2,1)-category GOpf(X o)GOpf(X^o). Taking X=1X=1, together with the second condition in the definition of a duality involution, this implies that () o(-)^o fixes groupoids in the previous sense. Moreover, we have:

Theorem

If () o(-)^o is a duality involution that fixes groupoids locally, then the induced duality involutions on Fib(X)Fib(X) and Opf(X)Opf(X) also fix groupoids locally.

Proof

For a fibration AXA\to X, on Fib Fib(X)(A)Fib_{Fib(X)}(A) we have () o X=V X 1() o(-)^{o_X} = V_X^{-1}\circ (-)^o and V A X=V X 1V AV^X_A = V_X^{-1}\circ V_A, so the equivalence between () o(-)^o and V AV_A in KK induces one between () o X(-)^{o_X} and V A XV^X_A in Fib(X)Fib(X).

Now, suppose that () o(-)^o is a duality involution that fixes groupoids locally. Then for any AA and BB, the pullback-commutation datum shows that the composite equivalence

Fib(A×B o)Fib(B,A)Opf(A o×B)Opf((A×B o) o)Fib(A\times B^o) \simeq Fib(B,A) \simeq Opf(A^o\times B)\simeq Opf((A\times B^o)^o)

derived from Theorem is equivalent to V A×B oV_{A\times B^o}. But if we restrict to groupoidal fibrations, then

V A×B o:GFib(A×B o)GOpf(A o×B)V_{A\times B^o}:GFib(A\times B^o) \simeq GOpf(A^o\times B)

is equivalent to () o(-)^o. Together with commutation of opposites, this implies that the canonical equivalence

GFib(B,A)GFib(A o,B o)GFib(B,A)\simeq GFib(A^o,B^o)

is, up to equivalence, simply given by () o(-)^o. In particular, since () o(-)^o preserves powers, the canonical equivalence

DFib(A,A)DFib(A o,A o)DFib(A,A)\simeq DFib(A^o,A^o)

takes A 2A^{\mathbf{2}} to (A o) 2(A^o)^{\mathbf{2}}. In the 2-internal logic, this corresponds to the statement that “hom A(x,y)hom A o(y,x)hom_A(x,y) \cong hom_{A^o}(y,x),” which is certainly an expected part of the behavior of opposite categories. Of course, for this it suffices that () o(-)^o fix discretes locally, which has the evident definition.

Further axioms

Another natural requirement is that when XX is groupoidal, V XV_X should be equivalent to the composite

Fib(X)K/XOpf(X)Opf(X o).Fib(X)\simeq K/X \simeq Opf(X)\simeq Opf(X^o).

Note that this includes the second datum in the definition of a duality involution as a special case, since 11 is groupoidal. There seems no reason for this condition to be stable under slicing, but it could be stabilized.

Grothendieck 2-toposes

Definition

A Grothendieck 2-topos is a 2-category that is equivalent to the 2-category of 2-sheaves (aka stacks) on some 2-site. More generally, a Grothendieck nn-topos is an nn-category that is equivalent to the nn-category of nn-sheaves on some nn-site (for n2n\le 2); see truncated 2-topos.

The 2-Giraud theorem due to StreetCBS characterizes Grothendieck nn-toposes as the infinitary n-pretoposes having a small eso-generating set of objects.

Cores and opposites

The most familiar Grothendieck 2-toposes are those of 2-sheaves on a 1-site. Even 2-presheaves on a 2-category that is not a 1-category can exhibit unexpected behavior; for instance they do not in general have cores or opposites. (2-presheaves on a (2,1)-category do have cores and opposites, though.)

The 2-Giraud theorem implies that if KK is a Grothendieck 2-topos, so is K coK^{co}. In the case of 2-presheaves, we can identify this as:

[C,Cat] co[C co,Cat co][C co,Cat][C,Cat]^{co} \simeq [C^{co},Cat^{co}] \simeq [C^{co},Cat]

since we have () op:Cat coCat(-)^{op} : Cat^{co} \simeq Cat. In other words, the “2-topos of presheaves” functor from 2-categories to 2-toposes preserves the 2-cell-dual involution. Another way to say this is that only for 2-sheaves on a (2,1)-category is “oppositization” an endofunctor; in other cases “passage to opposites” means passage to a different 2-topos.

2-sheaves (stacks) on a 2-site

Definition

A coverage on a 2-category CC consists of, for each object UCU\in C, a collection of families (f i:U iU) i(f_i: U_i\to U)_i of morphisms with codomain UU, called covering families, such that

  • If (f i:U iU) i(f_i:U_i\to U)_i is a covering family and g:VUg:V\to U is a morphism, then there exists a covering family (h j:V jV) j(h_j:V_j\to V)_j such that each composite gh jg h_j factors through some f if_i, up to isomorphism.

This is the 2-categorical analogue of the 1-categorical notion of coverage introduced in the Elephant.

A 2-category equipped with a coverage is called a 2-site.

Examples

  • If CC is a regular 2-category, then the collection of all singleton families (f:VU)(f:V\to U), where ff is eso, forms a coverage called the regular coverage.

  • Likewise, if CC is a coherent 2-category, the collection of all finite jointly-eso families forms a coverage called the coherent coverage.

  • On CatCat, the canonical coverage consists of all families that are jointly essentially surjective on objects.

2-sheaves

Let CC be a 2-site having finite limits (for convenience). For a covering family (f i:U iU) i(f_i:U_i\to U)_i we have the comma objects

Comma Square ( f i / f j ) (f_i/f_j) U i U_i U j U_j U U f i f_i f j f_j q ij q_{i j} p ij p_{i j} μ ij \mu_{i j}

We also have the double comma objects (f i/f j/f k)=(f i/f j)× U j(f j/f k)(f_i/f_j/f_k) = (f_i/f_j)\times_{U_j} (f_j/f_k) with projections r ijk:(f i/f j/f k)(f i/f j)r_{i j k}:(f_i/f_j/f_k)\to (f_i/f_j), s ijk:(f i/f j/f k)(f j/f k)s_{i j k}:(f_i/f_j/f_k)\to (f_j/f_k), and t ijk:(f i/f j/f k)(f i/f k)t_{i j k}:(f_i/f_j/f_k)\to (f_i/f_k).

Now, a functor X:C opCatX:C^{op} \to Cat is called a 2-presheaf. It is 1-separated if

  • For any covering family (f i:U iU) i(f_i:U_i\to U)_i and any x,yX(U)x,y\in X(U) and a,b:xya,b: x\to y, if X(f i)(a)=X(f i)(b)X(f_i)(a) = X(f_i)(b) for all ii, then a=ba=b.

It is 2-separated if it is 1-separated and

  • For any covering family (f i:U iU) i(f_i:U_i\to U)_i and any x,yX(U)x,y\in X(U), given b i:X(f i)(x)X(f i)(y)b_i:X(f_i)(x) \to X(f_i)(y) such that μ ij(y)X(p ij)(b i)=X(q ij)(b i)μ ij(x)\mu_{i j}(y) \circ X(p_{i j})(b_i) = X(q_{i j})(b_i) \circ \mu_{i j}(x), there exists a (necessarily unique) b:xyb:x\to y such that b i=X(f i)(b)b_i = X(f_i)(b).

It is a 2-sheaf if it is 2-separated and

  • For any covering family (f i:U iU) i(f_i:U_i\to U)_i and any x iX(U i)x_i\in X(U_i) together with morphisms ζ ij:X(p ij)(x i)X(q ij)(x j)\zeta_{i j}:X(p_{i j})(x_i) \to X(q_{i j})(x_j) such that the following diagram commutes:
    X(r ijk)X(p ij)(x i) X(r ijk)(ζ ij) X(r ijk)X(q ij)(x j) X(s ijk)X(p jk)(x j) X(s ijk)(ζ jk) X(t ijk)X(p ik)(x i) X(t ijk)(ζ ik) X(t ijk)X(q ik)(x k) X(s ijk)X(q jk)(x k)\array{X(r_{i j k})X(p_{i j})(x_i) & \overset{X(r_{i j k})(\zeta_{i j})}{\to} & X(r_{i j k})X(q_{i j})(x_j) & \overset{\cong}{\to} & X(s_{i j k})X(p_{j k})(x_j)\\ ^\cong \downarrow && && \downarrow ^{X(s_{i j k})(\zeta_{j k})}\\ X(t_{i j k}) X(p_{i k})(x_i) & \underset{X(t_{i j k})(\zeta_{i k})}{\to} & X(t_{i j k}) X(q_{i k})(x_k) & \underset{\cong}{\to} & X(s_{i j k}) X(q_{j k})(x_k)}

    there exists an object xX(U)x\in X(U) and isomorphisms X(f i)(x)x iX(f_i)(x)\cong x_i such that for all i,ji,j the following square commutes:

    X(p ij)X(f i)(X) X(p ij)(x i) X(μ ij) ζ ij X(q ij)X(f j)(x) X(q ij)(x j).\array{ X(p_{i j})X(f_i)(X) & \overset{\cong}{\to} & X(p_{i j})(x_i)\\ ^{X(\mu_{i j})}\downarrow && \downarrow^{\zeta_{i j}}\\ X(q_{i j})X(f_j)(x) & \underset{\cong}{\to} & X(q_{i j})(x_j).}

A 2-sheaf, especially on a 1-site, is frequently called a stack. However, this has the unfortunate consequence that a 3-sheaf is then called a 2-stack, and so on with the numbering all offset by one. Also, it can be helpful to use a new term because of the notable differences between 2-sheaves on 2-sites and 2-sheaves on 1-sites. The main novelty is that μ ij\mu_{i j} and ζ ij\zeta_{i j} need not be invertible.

Note, though, they must be invertible as soon as CC is (2,1)-site: μ ij\mu_{i j} by definition and ζ ij\zeta_{i j} since an inverse is provided by ι ij *(ζ ij)\iota_{i j}^*(\zeta_{i j}), where ι ijmaps(f i/f j)(f j/f i)\iota_{i j}\maps (f_i/f_j) \to (f_j/f_i) is the symmetry equivalence.

If CC lacks finite limits, then in the definitions of “2-separated” and “2-sheaf” instead of the comma objects (f i/f j)(f_i/f_j), we need to use arbitrary objects VV equipped with maps p:VU ip:V\to U_i, q:VU jq:V\to U_j, and a 2-cell f ipf jqf_i p \to f_j q. We leave the precise definition to the reader.

A 2-site is said to be subcanonical if for any UCU\in C, the representable functor C(,U)C(-,U) is a 2-sheaf. When CC has finite limits, it is easy to verify that this is true precisely when every covering family is a (necessarily pullback-stable) quotient of its kernel 2-polycongruence. In particular, the regular coverage on a regular 2-category is subcanonical, as is the coherent coverage on a coherent 2-category.

The 2-category 2Sh(C)2Sh(C) of 2-sheaves on a small 2-site CC is, by definition, a Grothendieck 2-topos.

Saturation conditions

A pre-Grothendieck coverage on a 2-category is a coverage satisfying the following additional conditions:

  • If f:VUf:V\to U is an equivalence, then the one-element family (f:VU)(f:V\to U) is a covering family.

  • If (f i:U iU) iI(f_i:U_i\to U)_{i\in I} is a covering family and for each ii, so is (h ij:U ijU i) jJ i(h_{i j}:U_{i j} \to U_i)_{j\in J_i}, then (f ih ij:U ijU) iI,jU i(f_i h_{i j}:U_{i j}\to U)_{i\in I, j\in U_i} is also a covering family.

This is the 2-categorical version of a Grothendieck pretopology.

Now, a sieve on an object UCU\in C is defined to be a functor R:C opCatR:C^{op}\to Cat with a transformation RC(,U)R\to C(-,U) which is objectwise fully faithful (equivalently, it is ff in [C op,Cat][C^{op},Cat]). Every family (f i:U iU) i(f_i:U_i\to U)_i generates a sieve by defining R(V)R(V) to be the full subcategory of C(V,U)C(V,U) on those g:VUg:V\to U such that gf ihg \cong f_i h for some ii and some h:VU ih:V\to U_i. The following observation is due to StreetCBS.

Lemma

A 2-presheaf X:C opCatX:C^{op}\to Cat is a 2-sheaf for a covering family (f i:U iU) i(f_i:U_i\to U)_i if and only if

X(U)[C op,Cat](C(,U),X)[C op,Cat](R,X)X(U) \simeq[C^{op},Cat](C(-,U),X) \to [C^{op},Cat](R,X)

is an equivalence, where RR is the sieve on UU generated by (f i:U iU) i(f_i:U_i\to U)_i.

Therefore, just as in the 1-categorical case, it is natural to restrict attention to covering sieves. We define a Grothendieck coverage on a 2-category CC to consist of, for each object UU, a collection of sieves on UU called covering sieves, such that

  • If RR is a covering sieve on UU and g:VUg:V\to U is any morphism, then g *(R)g^*(R) is a covering sieve on VV.

  • For each UU the sieve M UM_U consisting of all morphisms into UU (the sieve generated by the singleton family (1 U)(1_U)) is a covering sieve.

  • If RR is a covering sieve on UU and SS is an arbitrary sieve on UU such that for each f:VUf:V\to U in RR, f *(S)f^*(S) is a covering sieve on VV, then SS is also a covering sieve on UU.

Here if RR is a sieve on UU and g:VUg:V\to U is a morphism, g *(R)g^*(R) denotes the sieve on VV consisting of all morphisms hh into VV such that ghg h factors, up to isomorphism, through some morphism in RR.

As in the 1-categorical case, one can then show that every coverage generates a unique Grothendieck coverage having the same 2-sheaves.

Truncated 2-toposes

Definition

Let KK be a Grothendieck 2-topos. We say that KK is nn-truncated if it has a small eso-generator consisting of (n1)(n-1)-truncated objects. It is easy to see that if a coproduct of (n1)(n-1)-truncated objects is (n1)(n-1)-truncated (as is the case for all n1n\ge 1), then this is equivalent to saying that KK has enough (n1)(n-1)-truncated objects (i.e. every object admits an eso from an (n1)(n-1)-truncated one). In particular:

  • KK is always 2-truncated.
  • KK is (2,1)-truncated if it has enough groupoids.
  • KK is 1-truncated if it has enough discretes.
  • KK is (0,1)-truncated if the subterminal objects are eso-generating.
  • KK is (-1)-truncated if the terminal object is an eso-generator.

nn-sites and nn-sheaves

By the 2-Giraud theorem, small eso-generating sets of objects correspond to small 2-sites of definition for KK. Thus, if we define an nn-site to be a 2-site which is an nn-category (where n2n\le 2 as usual), we have:

Theorem

A Grothendieck 2-topos is nn-truncated iff it is equivalent to the 2-category of 2-sheaves on some nn-site.

Note that a 1-site is the same as the usual notion of site, and a (0,1)(0,1)-site is sometimes called a posite. In particular, any frame is a (0,1)-site with its canonical coverage (the covering families are given by unions).

Particular cases include:

  • KK is 1-truncated iff it is equivalent to the 2-category of 2-sheaves (stacks) on an ordinary small (1-)site, and therefore to the 2-category of stacks for the canonical coverage on some Grothendieck 1-topos.

  • KK is (0,1)-truncated iff it is equivalent to the 2-category of stacks on a posite, and therefore also to the 2-category of stacks on some locale. We call such a KK localic.

  • If KK is (-1)-truncated, then it is in particular localic, and its terminal object is a (strong) generator. It is not hard to see that this is equivalent to saying that the corresponding locale XX is a sublocale of the terminal locale 11. Thus, just as (-1)-categories are subsets of 11, (-1)-toposes are sublocales of 11. If CatCat has classical logic, this implies that either X0X\cong 0 or X1X\cong 1; and hence that either K1K\simeq 1 or KCatK\simeq Cat. However, constructively there may be many other sublocales of 11.

  • It would be nice if the only (-2)-truncated Grothendieck 2-topos were CatCat. However, I don’t see a way to make this happen except by fiat.

Grothendieck nn-toposes

Now, if CC is an nn-site, it is also reasonable to consider nn-sheaves on CC, by which we mean 2-sheaves taking values in (n1)(n-1)-categories. Thus, a 1-sheaf on a 1-site is precisely the usual notion of sheaf on a site. And a (0,1)-sheaf on a (0,1)-site is easily seen to be a lower set that is an “ideal” for the coverage.

We define a Grothendieck nn-topos to be an nn-category equivalent to the nn-category of nn-sheaves on an nn-site. The case n=1n=1 gives classical Grothendieck toposes; the case n=(0,1)n=(0,1) gives locales. Note the distinction between a Grothendieck nn-topos and an nn-truncated Grothendieck 2-topos. The relationship is that

  1. The 2-category of 2-sheaves for the canonical coverage on a Grothendieck nn-topos is an nn-truncated Grothendieck 2-topos, and
  2. Any nn-truncated Grothendieck 2-topos arises in this way from the Grothendieck nn-topos which is its full subcategory of (n1)(n-1)-truncated objects.

This relationship is completely analogous to the classical relationship between locales and localic toposes. In fact, if GrnTopGr n Top denotes the (n+1)(n+1)-category of Grothendieck nn-toposes (that is, nn-categories of nn-sheaves on an nn-site), we have inclusions

Gr(1,2)Top Gr(1)Top Gr(0,1)Top Gr1Top Gr2Top Gr(2,1)Top\array{ &&&&&& Gr(1,2)Top\\ &&&&& \nearrow && \searrow\\ Gr (-1) Top &\to& Gr(0,1)Top &\to & Gr1Top &&&& Gr2Top\\ &&&&& \searrow && \nearrow\\ &&&&&& Gr(2,1)Top }

where the inclusion from GrnTopGr n Top to Gr(n+1)TopGr (n+1) Top is given by taking the (n+1)(n+1)-category of (n+1)(n+1)-sheaves for the canonical coverage. (See 2-geometric morphism for the morphisms in these categories.)

2-geometric morphisms

If KK and LL are Grothendieck n-toposes, an nn-geometric morphism f:KLf:K\to L consists of an adjoint pair f *f *f^*\dashv f_*, where f *:KLf_*:K\to L is the direct image and f *:LKf^*:L\to K is the inverse image, such that f *f^* preserves finite limits (in the nn-categorical sense).

When n=1n=1 this is, of course, the usual definition. When n=(0,1)n=(0,1) this reduces to a continuous map between locales.

In general, we expect that Grothendieck nn-toposes satisfy an nn-categorical version of the adjoint functor theorem, so that any functor f *:LKf^*:L\to K that preserves finite limits and small colimits is the inverse image of some nn-geometric morphism.

We define transformations and modifications between nn-geometric morphisms to be transformations and modifications between their inverse image functors. We then have an (n+1)(n+1)-category GrnTopGr n Top of Grothendieck nn-toposes and nn-geometric morphisms.

Truncation in an exact 2-category

In a suitably exact 2-category, we can construct truncations as quotients of suitable congruences.

(-1)-truncation

This case is easy and just like for 1-categories.

Theorem

In any regular 2-category KK the inclusion Sub(1)KSub(1) \hookrightarrow K of the subterminal objects has a left adjoint called the support or (-1)-truncation.

Proof

Define the support supp(A)=A 1supp(A) = A_{\le -1} of an object AA to be the image of the unique morphism A1A\to 1. That, is Asupp(A)1A\to supp(A) \to 1 is an eso-ff factorization. Since supp(A)1supp(A)\to 1 is ff, supp(A)supp(A) is subterminal, and since esos are orthogonal to ffs, it is a reflection into Sub(1)Sub(1).

(0,1)-truncation

Perhaps surprisingly, the next easiest case is the posetal reflection.

Theorem

In any (1,2)-exact 2-category KK the inclusion pos(K)Kpos(K) \hookrightarrow K of the posetal objects has a left adjoint called the (0,1)-truncation.

Proof

Given AA, define A 1A_1 to be the (ff) image of A 2A×AA^{\mathbf{2}} \to A\times A. Since esos are stable under pullback, A 1AA_1\;\rightrightarrows\; A is a homwise-discrete category, and it clearly has a functor from ker(A)ker(A), so it is a (1,2)-congruence. Let APA\to P be its quotient. By the classification of congruences, PP is posetal. And if we have any f:AQf:A\to Q where QQ is posetal, then we have an induced functor ker(A)ker(f)ker(A) \to ker(f). But QQ is posetal, so ker(f)ker(f) is a (1,2)-congruence, and thus ker(A)ker(f)ker(A) \to ker(f) factors through a functor A 1ker(f)A_1\to ker(f). This then equips ff with an action by the (1,2)-congruence A 1AA_1\;\rightrightarrows\; A, so that it descends to a map PQP\to Q. It is easy to check that 2-cells also descend, so PP is a reflection of AA into pos(K)pos(K).

This is actually a special case of the (eso+full,faithful) factorization system?, since an object AA is posetal iff A1A\to 1 is faithful. The proof is also an evident specialization of that.

0-truncation

The discrete reflection, on the other hand, requires some additional structure.

Theorem

In any 1-exact and countably-coherent 2-category KK, the inclusion disc(K)Kdisc(K) \hookrightarrow K of the discrete objects has a left adjoint called the 0-truncation or discretization.

Proof

Given AA, define A 1A_1 to be the equivalence relation generated by the image of A 2A×AA^{\mathbf{2}} \to A\times A; this can be constructed with countable unions in the usual way. Then A 1AA_1\;\rightrightarrows\; A is a 1-congruence, and as in the posetal case we can show that its quotient is a discrete reflection of AA.

There are other sufficient conditions on KK for the discretization to exist; see for instance classifying cosieve. We can also derive it if we have groupoid reflections, since the discretization is the groupoid reflection of the posetal reflection.

(1,0)-truncation

The groupoid reflection is the hardest and also requires infinitary structure. Note that the 2-pretopos FinCatFinCat does not admit groupoid reflections (the groupoid reflection of the “walking parallel pair of arrows” is BZB Z).

Theorem

In any (2,1)-exact and countably-extensive 2-category KK, the inclusion gpd(K)Kgpd(K) \hookrightarrow K of the groupoidal objects has a left adjoint called the (1,0)-truncation.

The comprehensive factorization system

In Cat there is a factorization system (E,M)(E,M) where EE is the class of initial functors and MM is the class of discrete opfibrations; see

  • Street, Walters, The comprehensive factorization of a functor. Bull. Amer. Math. Soc. 79, 1973.

We can construct an analogous factorization system in any 1-exact and countably-coherent 2-category.

Definition

A morphism f:ABf:A\to B in a 2-category KK is initial if it is left orthogonal to discrete opfibrations. That is, whenever g:CDg:C\to D is a discrete opfibration, the following square is a pullback in CatCat:

K(B,C) K(B,D) K(A,C) K(A,D)\array{ K(B,C) & \to & K(B,D)\\ \downarrow & & \downarrow\\ K(A,C) & \to & K(A,D)}
Theorem

Every morphism in a 1-exact countably-coherent 2-category (in particular, in an nn-pretopos for n1n\ge 1) factors, up to isomorphism, as an initial morphism followed by a discrete opfibration.

Proof

By the 2-categorical analogue of a standard theorem about factorization systems in 1-categories, it suffices to show that

  1. discrete opfibrations are closed under composition, and
  2. for every XX, the discrete opfibrational slice DOpf(X)DOpf(X) is a full reflective subcategory of the slice 2-category K/XK/X.

The first point is true in any 2-category. For the second, we factor the inclusion as

DOpf(X)Opf(X)K/X DOpf(X) \to Opf(X) \to K/X

and observe that both forgetful functors have left adjoints. The left adjoint to DOpf(X)Opf(X)DOpf(X) \to Opf(X) is discretization in the 1-exact and countably-coherent 2-category Opf(X)Opf(X). The left adjoint to Opf(X)K/X Opf(X) \to K/X constructs the “free opfibration” on a functor f:AXf:A\to X, which is given by A× XX 2A\times_X X^{\mathbf{2}}.

Corollary

In any 1-exact countably-coherent 2-category, (initial, discrete opfibration) is a (2-categorical) factorization system.

Corollary

In any 1-exact countably-coherent 2-category, each pullback functor f *:DOpf(Y)DOpf(X)f^*:DOpf(Y)\to DOpf(X) has a left adjoint Lan fLan_f.

Proof

Lan fLan_f is given by composing with ff, then factoring into an initial morphism followed by a discrete opfibration.

Examples

  • In a 1-category, every morphism is a discrete opfibration, so the only initial morphisms are isomorphisms. The factorization system (isomorphisms,all morphisms) is well-known.

  • In a (2,1)-category, the discrete opfibrations are precisely the faithful morphisms. Thus, in this case the comprehensive factorization system coincides with the (eso+full, faithful) factorization system.

Beck-Chevalley conditions

The appropriate Beck-Chevalley condition for the adjunctions Lan ff *Lan_f\dashv f^* refers not to pullback squares, but to comma squares. The easiest proof of this fact uses the internal logic. We start with an internal characterization of initial morphisms, analogous to the classical characterization in CatCat as the functors f:ABf:A\to B for which each comma category (f/b)(f/b), for bBb\in B, is nonempty and connected.

For the rest of this page we make the standing assumption that KK is a 1-exact and countably-coherent 2-category.

Lemma

A morphism f:ABf:A\to B in KK is initial iff the following are internally valid:

b:B|(a:A)(α:hom B(f(a),b)) b:B,a 1:A,a 2:A,α 1:hom B(f(a 1),b),α 2:hom B(f(a 2),b)| iφ i \begin{gathered} b:B | \top \vdash (\exists a:A)(\exists \alpha:hom_B(f(a),b))\\ b:B, a_1:A, a_2:A, \alpha_1:hom_B(f(a_1),b), \alpha_2:hom_B(f(a_2),b) | \top \vdash \bigvee_{i\in \mathbb{N}} \varphi_i \end{gathered}

where for each ii, φ i\varphi_i expresses “there is a zigzag of length ii connecting α 1\alpha_1 and α 2\alpha_2 over bb.”

Thus, for instance, we have

φ 1 (γ:hom A(a 1,a 2))(α 2f(γ)=α 1) φ 2 (c:A)(β:hom B(f(c),b))(γ 1:hom A(a 1,c))(γ 2:hom A(a 2,c))(α 1=βf(γ 1)α 2=βf(γ 2)) \begin{aligned} \varphi_1 \equiv& (\exists \gamma:hom_A(a_1,a_2)) (\alpha_2 \circ f(\gamma) = \alpha_1)\\ \varphi_2 \equiv& (\exists c:A)(\exists \beta:hom_B(f(c),b))(\exists \gamma_1:hom_A(a_1,c))(\exists \gamma_2:hom_A(a_2,c)) (\alpha_1 = \beta \circ f(\gamma_1) \wedge \alpha_2 = \beta \circ f(\gamma_2)) \end{aligned}

and so on.

Proof

f:ABf:A\to B will be initial iff the discrete-opfibration part of its factorization is an equivalence. By construction, this factorization is the discrete reflection of X=A× BB 2BX = A\times_B B ^{\mathbf{2}} \to B in Opf(B)Opf(B), which is constructed as the quotient of the equivalence relation X 1X_1 generated by X 2X ^{\mathbf{2}} (the power taken in Opf(B)Opf(B)). Therefore, this discrete reflection will be the terminal object 1 B1_B iff

  1. XBX\to B is eso and
  2. the kernel of XBX\to B in Opf(B)Opf(B) is X 1X_1.

It is fairly evident that XBX\to B is eso iff the first displayed sequent holds in KK. For the second, note that the kernel of XBX\to B in Opf(B)Opf(B) (or equivalently, in K/BK/B) is just the pullback X× BXX\times_B X, since BB is discrete as an object of K/BK/B. By definition of XX, this pullback can be computed as the lax limit

Lax pullback X × B X X\times_B X A A A A B B f f f f

and therefore it is precisely the context of the second displayed sequent. Since X 1X_1 is the equivalence relation generated by X 2X ^{\mathbf{2}} , it is necessarily contained in this kernel, so it suffices to show the converse implication. But X 1X_1 is defined as the symmetric transitive closure of the image of X 2X ^{\mathbf{2}} , which makes it essentially a countable union of “zigzags” from X 2X ^{\mathbf{2}} , and this translates directly into the conclusion of the second sequent.

Lemma

Initial morphisms in KK are stable under transfer across comma squares, in the sense that if

Comma Square ( f / g ) (f/g) A A B B C C f f g g q q p p

is a comma square with ff initial, then qq is also initial.

Proof

Given the characterization of initial morphisms in Lemma , we can simply observe that the usual proof of this fact in CatCat takes place entirely in countably-coherent logic.

Theorem

The adjunctions Lan ff *Lan_f\dashv f^* for discrete opfibrations in KK satisfy the Beck-Chevalley condition for comma squares. That is, if

Comma Square ( f / g ) (f/g) A A B B C C f f g g q q p p

is a comma square, then the canonical transformation Lan qp *g *Lan fLan_q p^* \to g^* Lan_f between functors DOpf(A)DOpf(B)DOpf(A)\to DOpf(B) is an equivalence.

Note that unlike the case for a pullback square, there is no possible “handedness” ambiguity in saying that a comma square satisfies the Beck-Chevalley condition; there is no transformation Lan pq *f *Lan gLan_p q^* \to f^* Lan_g at all.

The existence of the transformation in the correct direction also depends on the fact that opfibrational slices are functorial at the level of 2-cells. In particular, for a comma square there is no transformation Σ qp *g *Σ f\Sigma_q p^* \to g^*\Sigma_f between functors K/AK/BK/A\to K/B.

Proof

Given a discrete opfibration XAX\to A, let XLan fXCX\to Lan_f X \to C be the (initial,discrete-opfibration) factorization of the composite XAfCX\to A \overset{f}{\to} C. Now by properties of comma squares and pullbacks, the pasting composite

Composite Square 1 p * X p^* X X X ( f / g ) (f/g) A A B B C C f f g g q q p p

is also a comma square, and thus so is

Composite Square 2 p * X p^* X X X g * Lan f X g^* Lan_f X Lan f X Lan_f X B B C C g g

where the upper 2-cell is opcartesian for the opfibration Lan fXCLan_f X \to C, and the map p *Xg *Lan fXp^* X \to g^* Lan_f X is obtained from the universal property of the pullback square on the bottom. Again, it follows from general properties of pullbacks and comma squares that the top square in this latter diagram is also a comma square. Thus, by Lemma , its left-hand morphism is initial. But then the left-hand composite p *Xg *Lan fXBp^*X \to g^* Lan_f X \to B is an (initial, discrete-opfibration) factorization of p *X(f/g)Bp^*X \to (f/g) \to B, and hence it exhibits the desired equivalence Lan qp *Xg *Lan fXLan_q p^*X \simeq g^* Lan_f X.

Passing to 2-cell duals, we obtain:

Corollary

For a comma square as above, the canonical transformation Lan pq *f *Lan gLan_p q^* \to f^* Lan_g between functors DFib(B)DFib(A)DFib(B)\to DFib(A) is an equivalence.

Full morphisms and (eso+full, faithful) factorization

In Cat and Gpd, in addition to the (eso, ff) factorization system that is enshrined in the notion of regular 2-category, there is also an (eso+full, faithful) factorization system. In Gpd, the (eso+full, faithful) factorization is the same as the comprehensive factorization, but in Cat they are different.

Mathieu Dupont has pointed out that given sufficient exactness, (eso+full, faithful) factorizations can be constructed from (eso,ff) factorizations. Here we give the argument.

eso+full and full morphisms

Recall that a morphism m:CDm:C\to D is said to be faithful if K(X,C)K(X,D)K(X,C)\to K(X,D) is faithful for any XX.

Definition

A morphism e:ABe:A\to B in a 2-category KK is eso+full if for any faithful m:CDm:C\to D, the following square is a pullback:

K(B,C) K(B,D) K(A,C) K(A,D)\array{K(B,C) & \to & K(B,D)\\ \downarrow & & \downarrow\\ K(A,C) & \to & K(A,D)}
Definition

A morphism ff is said to be full if we have fmef \cong m e where mm is ff and ee is eso+full.

Luckily, the terminology is consistent:

Lemma

In any 2-category, 1. ff is eso+full if and only if it is both eso and full. 1. ff is ff if and only if it is both faithful and full.

Proof

Since ffs are faithful, any eso+full is eso, and any eso+full clearly factors as an eso+full (itself) followed by an ff (the identity). Conversely, if ff is eso and fmef \cong m e where ee is eso+full and mm is ff, then mm is an equivalence, and hence ff, like ee, is eso+full.

Now, ffs are clearly faithful, and any ff clearly factors as an eso+full (the identity) followed by an ff (itself). Conversely, if ff is faithful and we have fmef\cong m e where ee is eso+full and mm is ff, then ee is also faithful, and hence an equivalence; thus ff, like mm, is ff.

Lemma

Any eso+full morphism is co-ff.

Proof

Let f:ABf:A\to B be eso+full; we want to show that K(B,C)K(A,C)K(B,C)\to K(A,C) is ff. It is faithful since ff is eso, so suppose that g,h:BCg,h:B \;\rightrightarrows\; C and that α:gfhf\alpha: g f \to h f; we want to show α=βf\alpha = \beta f for some β:gh\beta: g\to h. Let p:EBp:E\to B with γ:gphp\gamma: g p \to h p be the inserter of g,hg,h. Then we have a k:AEk:A\to E such that pkfp k\cong f and (modulo this isomorphism) γk=α\gamma k = \alpha. But since pp, being an inserter, is faithful, and ff is eso+full, we have q:BEq:B\to E with kqfk\cong q f and therefore α=γk=γqf\alpha = \gamma k = \gamma q f; thus β=γq\beta=\gamma q is our desired 2-cell.

Factorizations

Lemma

If A 1AA_1 \;\rightrightarrows\; A is a 2-congruence such that A 2A 1A^{\mathbf{2}} \to A_1 is eso, then its quotient f:ABf:A\to B (if it has one) is eso+full.

Proof

Suppose that m:CDm:C\to D is faithful and that mghfm g\cong h f; we want to show there is a k:BCk:B\to C with gkfg\cong k f and hmkh\cong m k (the rest follows by standard arguments). Since mgm g comes with an action by A 1AA_1 \;\rightrightarrows\; A, it suffices to lift this action to gg itself, and since mm is faithful it suffices to lift the 2-cell defining the action. This follows by the existence of a diagonal lift in the following rectangle:

A 2 C 2 A 1 (f/f) (m/m)\array{A^{\mathbf{2}} && \to && C^{\mathbf{2}} \\ \downarrow && && \downarrow\\ A_1 & \to & (f/f) & \to & (m/m)}

which exists since A 2A 1A^{\mathbf{2}} \to A_1 is eso (by assumption) and C 2(m/m)C^{\mathbf{2}}\to (m/m) is ff (since mm is faithful).

Lemma

In a regular 2-category, if f:ABf\colon A\to B is a map such that A 2(f/f)A^{\mathbf{2}} \to (f/f) is eso, then ff is full.

Proof

The (eso,ff) factorization of ff is constructed by taking the quotient of ker(f)ker(f). But by assumption, this kernel has the property of Lemma , so the eso part of the (eso,ff) factorization of ff is eso+full. Hence ff is full, by definition.

For comparison, recall that

  • A 2(f/f)A^{\mathbf{2}} \to (f/f) is always faithful,
  • A 2(f/f)A^{\mathbf{2}} \to (f/f) is full (equivalently, ff) iff ff is faithful, and
  • A 2(f/f)A^{\mathbf{2}} \to (f/f) is an equivalence iff ff is ff.

I do not know whether the converse of Lemma is true in general, but it is at least true in an exact 2-category.

Theorem

Let KK be an nn-exact nn-category, where nn is 2, (2,1), (1,2), or 1. Then: 1. Every morphism ff factors as fmef\cong m e where ee is eso+full and mm is faithful. Thus, (eso+full, faithful) is a factorization system on KK. 1. A morphism f:ABf:A\to B is full iff A 2(f/f)A^{\mathbf{2}} \to (f/f) is eso. 1. Therefore, ff is eso+full iff it is the quotient of a 2-congruence A 1AA_1 \;\rightrightarrows\; A such that A 2A 1A^{\mathbf{2}} \to A_1 is eso.

Of course, the cases n=1n=1 and (1,2)(1,2) are fairly trivial, since in those cases every morphism in an nn-category is faithful and thus the only eso+full morphisms are the equivalences. However, we include them for completeness.

Proof

For the first statement, let f:ABf:A\to B be any morphism, and factor A 2(f/f)A^{\mathbf{2}} \to (f/f) as an eso followed by a ff to get A 2A 1(f/f)A^{\mathbf{2}} \to A_1 \to (f/f). Then A 1A_1 inherits the structure of a 2-congruence, which is an nn-congruence since (f/f)(f/f) is. Since KK is nn-exact, this nn-congruence has a quotient e:AQe:A\to Q, which is eso+full by Lemma , and clearly ff factors through ee as fmef\cong m e. Finally, since (e/e)=A 1(f/f)(e/e) = A_1 \to (f/f) is ff by definition, Street's Lemma implies that mm is faithful.

The “if” direction of the second statement is Lemma . Conversely, if fmef\cong m e where mm is ff and ee is eso+full, then ee must be obtained, up to equivalence, as the quotient of the nn-congruence A 1AA_1 \;\rightrightarrows\; A constructed above, for which A 2A 1A^{\mathbf{2}}\to A_1 is eso. But since mm is ff, we have (f/f)(e/e)=A 1(f/f)\simeq (e/e)= A_1, so A 2(f/f)A^{\mathbf{2}} \to (f/f) is eso as desired.

One direction of the third statement is Lemma . For the other, if ff is eso+full, then by the second statement A 2(f/f)A^{\mathbf{2}} \to (f/f) is eso, and because ff is eso it is the quotient of its kernel, namely (f/f)A(f/f) \;\rightrightarrows\; A.

Inspecting the proof shows that we don’t need the full strength of exactness, either; all we need is that any sub-congruence of a kernel has a quotient. This is a property in between regularity and exactness. For instance, it is satisfied by FinCatFinCat, which is not exact.

Corollary

In a (2,1)-exact (2,1)-category, eso+full morphisms are stable under pullback, and therefore so are full ones.

Proof

If p:ABp:A\to B is eso+full, then it is the quotient of its kernel, which in a (2,1)-category is A× BAAA\times_B A \to A. And since pp is eso+full, by Theorem , AA× BAA\to A\times_B A is eso. If

D A q p C f B\array{D & \to & A \\ ^q\downarrow && \downarrow ^p\\ C & \overset{f}{\to} & B}

is a pullback square, then the kernel D× CDD\times_C D is also the pullback of A× BAA\times_B A along ff. Thus, by properties of pullback squares, DD× CDD \to D\times_C D is a pullback of AA× BAA\to A\times_B A, and hence also eso. But qq, being eso (as a pullback of pp), is also the quotient of its kernel, so by Lemma qq is eso+full. The second statement follows since ffs are certainly stable under pullback.

Corollary

Let KK be an nn-exact nn-category. Then: 1. Full morphisms are stable under composition. 1. A morphism is full iff it is (isomorphic to) a composite of eso+full and ff morphisms. 1. If gfg f is full and ff is eso, then gg is full.

Proof

Given f:ABf:A\to B and g:BCg:B\to C, we have two pullback squares

(f/f) (gf/gf) A×A B 2 (g/g) B×B.\array{ (f/f) & \to & (g f / g f) & \to & A\times A\\ \downarrow &&\downarrow && \downarrow\\ B ^{\mathbf{2}} & \to & (g/g) & \to & B\times B.}

Thus, if ff and gg are full, so that A 2(f/f)A^{\mathbf{2}} \to (f/f) and B 2(g/g)B^{\mathbf{2}} \to (g/g) are eso, then (f/f)(gf/gf)(f/f) \to (g f / g f) is also eso, hence so is A 2(gf/gf)A ^{\mathbf{2}} \to (g f / g f); thus gfg f is full. This proves the first statement, from which the second follows. For the third, if gfg f is full and ff is eso, then A 2(gf/gf)A ^{\mathbf{2}} \to (g f / g f) is eso, and so is (gf/gf)(g/g)(g f / g f) \to (g/g) since it is a pullback of f×ff\times f. Thus the composite A 2(g/g)A ^{\mathbf{2}} \to (g/g) is eso, and since it factors through B 2B ^{\mathbf{2}}, it follows that B 2(g/g)B ^{\mathbf{2}} \to (g/g) is also eso; hence gg is full.

The Cauchy factorization system

Definitions

A morphism m:ABm:A\to B in a 2-category KK is called ff and retract-closed or rff if K(X,A)K(X,B)K(X,A)\to K(X,B) is fully faithful and closed under retracts for all XX. Explicitly this means that (in addition to being ff) if b:XBb:X\to B is a retract of mam a for some a:XAa:X\to A, then bmab\cong m a' for some aAa'\in A.

A morphism e:ABe:A\to B is called Cauchy surjective or cso if it is left orthogonal to all rffs; that is, if

K(B,C) K(B,D) K(A,C) K(A,D)\array{K(B,C) & \to & K(B,D)\\ \downarrow & & \downarrow \\ K(A,C) & \to & K(A,D)}

is a pullback whenever m:CDm:C\to D is rff.

Remarks

  • Since rffs are stable under pullback, ee is cso if and only if whenever it factors through an rff m:CBm:C\to B, then mm is an equivalence.

  • Every eso is cso, since every rff is ff. Conversely, in a (2,1)-category, every ff is rff, and thus every cso is eso.

  • In CatCat, the Cauchy surjective functors are those for which every object of BB is a retract of an object of AA.

  • Every equifier or inverter is rff. Therefore, every Cauchy surjective morphism is cofaithful and coconservative. In “Modulated bicategories” by Carboni, Johnson, Street, and Verity it is shown that conversely, every coconservative functor in CatCat is Cauchy surjective.

Factorization System

In CatCat, (cso,rff) is a factorization system. We now show that the same is true in any regular 2-category.

Given f:ABf:A\to B, let R fR_f be its retractor. This is a 2-categorical finite limit which comes with projections p:R fAp:R_f\to A and q:R fBq:R_f\to B and 2-cells ρ:fpq\rho:f p \to q and σ:qfp\sigma:q \to f p such that ρσ=1 q\rho \sigma = 1_q, and which is universal with these properties.

Lemma

In any 2-category, if q:R fBq:R_f\to B is eso, then ff is Cauchy surjective.

Proof

Suppose that qq is eso and let AgCmBA\overset{g}{\to} C \overset{m}{\to} B be such that fmgf\cong m g and mm is rff; we want to show mm is an equivalence. But since mm is rff and qq is a retract of fpmgpf p \cong m g p, it follows that qq factors through mm; whence mm is an equivalence since qq is eso.

Now suppose that KK is regular, and for any f:ABf:A\to B, let R fjC fmBR_f \overset{j}{\to} C_f \overset{m}{\to} B be an (eso,ff) factorization of qq. Since ff is a retract of f1 Af 1_A, there is a canonical s:AR fs:A\to R_f with ps1 Ap s \cong 1_A and fqsmjsf\cong q s \cong m j s.

Lemma

In a regular 2-category, if f:ABf:A\to B is ff and C fAC_f\subset A (hence C fAC_f\simeq A), then ff is rff.

Proof

Suppose ff is ff and C fAC_f\simeq A, and let b:XBb:X\to B and a:XAa:X\to A be such that bb is a retract of aa. Then bqcb \cong q c and apca\cong p c for some c:XR fc:X\to R_f. Then we have jc:XC fj c:X\to C_f with mjcbm j c \cong b. But since C fAC_f\simeq A in Sub(B)Sub(B), we have a y:XAy:X\to A with fybf y \cong b as well; hence ff is rff.

Theorem

In a regular 2-category KK, 1. Every morphism ff factors as a Cauchy surjective morphism followed by an rff. 1. Therefore, (cso,rff) is a factorization system on KK. 1. A morphism ff is cso if and only if q:R fBq:R_f\to B is eso. 1. Likewise, ff is rff if and only if it is ff and C fAC_f\simeq A.

Proof

Given any f:ABf:A\to B, let jj, mm, and ss be as above, and define e=js:AC fe = j s:A\to C_f. Then memjsqsfm e \cong m j s\cong q s \cong f. Is easy to check that R fR eR_f \cong R_e; thus R eC fR_e\to C_f is eso, so by Lemma ee is Cauchy surjective.

Now let R mR_m be the retractor of mm, with p:R mC fp':R_m\to C_f, q:R mBq':R_m\to B, and corresponding factorization R mjC mmBR_m \overset{j'}{\to} C_m \overset{m'}{\to} B. Let

P u R f v j R m p C f\array{P & \overset{u}{\to}& R_f\\ ^v \downarrow && \downarrow ^j\\ R_m & \underset{p'}{\to} & C_f}

be a pullback. Then vv, like jj, is eso, and thus so is jv:PC mj' v:P \to C_m. Now mjvqvm' j' v \cong q' v is a retract of mpvmjuqum p' v\cong m j u \cong q u, and qq is a retract of fpf p, so quq u is a retract of fpuf p u. Therefore, mjv:PBm' j' v:P\to B is also a retract of fpuf p u, so there is a morphism w:PR fw:P\to R_f with mjwqwmjvm j w \cong q w \cong m' j' v (and pwpup w\cong p u). Now in the square

P jw C f jv m C m m B,\array{P & \overset{j w}{\to} & C_f\\ ^{j' v}\downarrow && \downarrow ^m\\ C_m & \underset{m'}{\to} & B,}

mm is ff and jvj' v is eso, so we have C mC fC_m\subset C_f in Sub(B)Sub(B); thus by Lemma mm is rff.

Therefore, with fmef\cong m e we have factored ff as a cso followed by an rff; this shows the first two statements. Moreover, ee satisfies the condition of Lemma , so if ff is cso and hence equivalent to ee, so does it. Likewise, mm satisfies the condition of Lemma , so if ff is rff and hence equivalent to mm, so does it.

Internal logic

From the characterization of csos and rffs in Theorem , we can conclude that csos and rffs have the expected descriptions in the internal logic.

Corollary

In a regular 2-category, a morphism f:ABf:A\to B is Cauchy surjective if and only if the following sequent is valid in the internal logic:

y:B|(x:A)(ρ:hom B(f(x),y))(σ:hom B(y,f(x)))(ρσ=1 y).y:B | \top \vdash (\exists x:A)(\exists \rho:hom_B(f(x),y))(\exists \sigma:hom_B(y,f(x)))(\rho \sigma = 1_y).
Proof

The context y:B,x:A,ρ:hom B(f(x),y),σ:hom B(y,f(x))|ρσ=1 yy:B, x:A, \rho:hom_B(f(x),y), \sigma:hom_B(y,f(x)) | \rho \sigma = 1_y is easily seen to be precisely R fR_f.

Corollary

In a regular 2-category, a morphism f:ABf:A\to B is rff if and only if it is ff and the following sequent is valid in the internal logic:

x:A,y:B,ρ:hom B(f(x),y),σ:hom B(y,f(x))|ρσ=1 y(x:A)(f(x)y)x:A,y:B,\rho:hom_B(f(x),y), \sigma:hom_B(y,f(x)) | \rho \sigma = 1_y \vdash (\exists x':A)(f(x')\cong y)
Proof

The validity of this sequent says that the pullback of f:ABf:A\to B along q:R fBq:R_f \to B is eso. But since both ff and qq factor through the ff m:C fBm:C_f\to B, this pullback is equivalent to the pullback of e:AC fe:A\to C_f along j:R fC fj:R_f\to C_f. Since jj is eso, this pullback being eso is equivalent to e:AC fe:A\to C_f being eso. And since ff is ff, so is ee; thus this is equivalent to ee being an equivalence.

Colimits in 2-pretopoi

An nn-pretopos has coproducts and quotients of nn-congruences, which are important classes of colimits. From these we can construct some other colimits, such as the following.

Theorem

A 2-pretopos admits copowers with any finite category.

Proof

If CC is a finite category and AKA\in K is an object, we build a finite 2-polycongruence with one copy of AA indexed by each object cCc\in C, and with the hom-object from A cA_c to A dA_d being C(c,d)A 2\sum_{C(c,d)} A ^{\mathbf{2}}. It is easy to check that a quotient of this congruence is a copower ACA\bullet C.

However, an nn-pretopos can fail to admit all finite colimits, for essentially the same reason as when n=1n=1: some ostensibly “finite” colimits secretly involve infinitary processes. In a 1-category, this manifests in the construction of arbitrary coequalizers and pushouts, where we must first generate an equivalence relation by an infinitary process and then take its quotient. Likewise, a 2-pretopos can fail to admit pushouts, coinserters, coinverters, and coequifiers.

For 2-categories it is even easier to find counterexamples. The 1-pretopos FinSetFinSet does in fact have all finite colimits, but the 2-pretopos FinCatFinCat of finite categories does not have coinserters or coinverters. (It does have coequifiers, for the same reason that FinSetFinSet has coequalizers). The category FPCatFPCat of finitely presented categories, on the other hand, does have finite colimits, but fails to have finite limits.

You can also generate the equivalence relation using a higher-order process. Thus a topos (where higher-order processes occur) has all coequalisers, even if it's not a WW-pretopos (where countably infinitary processes occur).

Incidentally, this is the example that first made me agree that predicativity was a reasonable constructive restriction. I just asked myself which way of generating an equivalence relation seemed more ‘constructive’.

—Toby

Indeed so. I noted at classifying cosieve that you can do the same thing in a 2-category if you have only a poset of truth values rather than a set. All this work on 2-toposes is actually making me more sympathetic to predicativism as well, because in the 2-dimensional case there isn’t really a “higher-order” version you can recourse to; you have to do things the “more constructive” way. Put differently, why is it okay to have a set (or poset) of all truth values, but not a category of all sets?

(Mathieu Dupont and I have been speculating about whether there could actually be a category of all sets; i.e. whether there could be a 2-pretopos having (exponentials, duality, and) a classifying discrete opfibration that classifies all discrete opfibrations. This would have marvelous consequences like that Set has all (not just small) limits and colimits, and so the adjoint functor theorem can be just true without any messing around with generators. But it is inconsistent with there being enough groupoids, or with Set being a topos, and hence also inconsistent with classical logic. I don’t really have very high hopes that it is consistent at all. Having a (1,2)-category of all posets appears to be inconsistent with just exponentials and duality.)

BTW, I assume that by “Π\Pi-pretopos” you meant “Π\Pi-pretopos with a NNO?” In my limited experience “Π\Pi-pretopos” means “locally cartesian closed pretopos” which certainly includes all toposes.

-Mike

Sorry, I removed the wrong letter from ‘Π\Pi-WW-pretopos’. I meant a WW-pretopos, that is a pretopos in which every polynomial functor has pullback-stable initial algebras in every slice category (which may follow from simply a pullback-stable NNO, I forget).

In my experience, when you can't find an inconsistency but you're sure that one exists, then the Burali-Forti paradox always works. There may be a simpler one, but Burali-Forti is the surest.

—Toby

I think that Burali-Forti works in this case to get a contradiction from having enough groupoids. But I can’t make it do anything else, because without cores, all I can construct is a poset of ordinals, which isn’t itself an ordinal because an ordinal is a set equipped with a certain sort of relation.

Why are you changing my Π\Pis to characters that I can’t type?

-Mike

Sorry, I started to fix the ‘Π’s (and ‘Π\Pi’s), then realised that I was fixing some inappropriately and so changed them back (but apparently not always to what they had been before). And you can type that character, as &Pi;. Actually, since you're using Ubuntu like me, you can install SCIM and use that to type it directly (the TeX input method is pretty neat). That said, ‘Π\Pi’ (also ‘WW’), in math mode, is probably more appropriate, as it refers to closure under a type operation with that name.

I'll try to think about it and see if I can make a paradox work. I don't quite understand how you construct these posets that don't have underlying sets. Although it reminds of me of Paul Taylor's Abstract Stone Duality, where there is a topological space of truth values (in fact one free on a poset) but no underlying set of such.

—Toby

I can type &Pi; but when I view the source that you’ve typed, I don’t see &Pi; but rather an actual Pi-character.

-Mike

It produces the same output in the displayed XHTML. If you want to get &Pi; in your Markdown source, either cut and paste from the display of &Pi;, or install SCIM (or something along those lines) like I did. —Toby

Also, see the new page category of all sets regarding posets and categories that don’t have underlying sets.

-Mike

Will do. —Toby

I don’t want to get a Pi-character in my Markdown source; my point was rather that I wished you wouldn’t put it in yours! I thought the whole point of things like HTML entities like &Pi; and TeX code like $\Pi$ was so that we could produce nice-looking math just by inputting ordinary ASCII text that can be read and edited without installing any fancy fonts or software.

-Mike

OK, fair enough, it's your web, so all special characters will be implemented as XHTML or SGML character entities (unless available through Instiki, of course). —Toby

However, once we have some infinitary structure, this problem goes away.

Theorem

A countably-extensive nn-pretopos has all countable colimits.

1-pretoposes are balanced

It is well-known that in a 1-pretopos,

  1. every monic is regular, and as a consequence
  2. a 1-pretopos is balanced (every monic epic is an isomorphism), and
  3. every epic is regular.

2-pretoposes are not balanced

For a similar statement in an nn-pretopos for n>1n\gt 1, the natural first guess is to replace “monic” by “ff” and “regular epic” by “eso.” However, there are (at least) two reasonable replacements for “epic” and “regular monic:”

  1. We could replace “epic” by “cofaithful” and “regular monic” by “equifier,” or
  2. we could replace “epic” by “coconservative” (aka “liberal”) and “regular monic” by “inverter.”

Since esos in Cat are cofaithful and liberal but not co-ff, it wouldn’t work to replace “epic” by “co-ff.” Unfortunately, both ideas fail in Cat, where equifiers and inverters are not just ff but are closed under retracts. Likewise, the map from a category to its Cauchy completion is full, faithful, cofaithful, and liberal, but generally not an equivalence.

There are two ways to deal with this problem. One is to restrict to smaller values of nn, for which there are no nontrivial retracts. The other is to go back and change “ff” to “ff and closed under retracts” and change “eso” to “surjective up to retracts.”

(2,1)-pretoposes are balanced

Theorem

In a (2,1)-exact positive coherent 2-category, every ff with groupoidal codomain is an equifier (in fact, an identifier of an involution).

Recall that an identifier of a 2-cell α:ff:AB\alpha:f\to f:A\to B in a 2-category is the equifier of α\alpha and 1 f1_f. By an involution we mean an (invertible) 2-cell that is its own inverse.

Proof

Let m:ABm:A\to B be ff with BB groupoidal, and consider first the (2,1)-congruence given by B+BBB+B \;\rightrightarrows\; B, where one copy of BB gives the identities, and the composition treats the other copy of BB as an involution. Its quotient is the copower of BB by the “walking involution.”

Now consider the following equivalence relation on B+BB+B in disc(K/B×B)disc(K/B\times B). We have

(B+B)× B×B(B+B)(B× B×BB)+(B× B×BB)+(B× B×BB)+(B× B×BB)(B+B)\times_{B\times B}(B+B) \simeq (B\times_{B\times B} B)+(B\times_{B\times B} B)+(B\times_{B\times B} B)+(B\times_{B\times B} B)

and we define the relation to be given by

B+A+A+B (B× B×BB)+(B× B×BB)+(B× B×BB)+(B× B×BB).\array{B+A+A+B \\ \downarrow\\ (B\times_{B\times B} B)+(B\times_{B\times B} B)+(B\times_{B\times B} B)+(B\times_{B\times B} B).}

Since disc(K/B×B)disc(Fib K(B×B))disc(K/B\times B) \simeq disc(Fib_K(B\times B)) is a 1-pretopos, this relation has a quotient, say [f,g]:B+BC[f,g]:B+B \to C. It is easy to verify that a,b:CBa,b:C\;\rightrightarrows\; B is then a (2,1)-congruence on BB with af=ag=bf=bg=1 Ba f = a g = b f = b g = 1_B. (This depends on BB being groupoidal; otherwise it would be a homwise-discrete category but not necessarily a congruence.) Let q:BDq:B\to D be the quotient in KK of this (2,1)-congruence. Then we have a 2-fork ϕ:qaqb\phi:q a \to q b such that ϕf=1 q\phi f = 1_q and ϕg\phi g is an involution of qq.

We claim that mm is an identifier of ϕg\phi g. By construction of CC, we have ϕgm=1 qm\phi g m = 1_{q m}, so since mm is ff, it suffices to show that for any x:XBx:X\to B with ϕgx=1 qx\phi g x = 1_{q x}, xx factors through mm. But since CC with ϕ\phi is the kernel of qq, the assumption ϕgx=1 qx=ϕfx\phi g x = 1_{q x} = \phi f x implies that in fact fx=gxf x = g x. If we write i,j:BB+Bi,j:B\;\rightrightarrows\; B+B for the two inclusions, this means that ix:XB+Bi x:X\to B+B and jx:XB+Bj x:X\to B+B become equal in CC, and therefore factor through the kernel pair of [f,g][f,g], namely B+A+A+BB+A+A+B. But this is evidently tantamount to saying that xx factors through AA.

Corollary

In a (2,1)-pretopos, 1. every ff is an equifier, 1. every cofaithful ff is an equivalence, and 1. every cofaithful morphism is eso.

Proof

Theorem shows the first statement. Then any ff f:ABf:A\to B is an equifier of α,β:gh:BC\alpha,\beta:g\;\rightrightarrows\;h:B\;\rightrightarrows\; C, so in particular αf=βf\alpha f = \beta f; but if ff is also cofaithful, this implies α=β\alpha=\beta, and thus their equifier ff is an equivalence. Finally, if ff is just cofaithful, we factor it as f=mef=m e where mm is ff and ee is eso; but then mm is also cofaithful, hence an equivalence, and so ff, like ee, is eso.

(1,2)-pretoposes are balanced

Theorem

In a (1,2)-exact positive coherent 2-category, every ff with posetal codomain is an inverter.

Proof

Let m:ABm:A\to B be ff, and consider the 2-congruence on B+BB+B defined as follows. We have

(B 0+B 1)×(B 0+B 1)=(B 0×B 0)+(B 0×B 1)+(B 1×B 0)+(B 1×B 1),(B_0+B_1)\times (B_0+B_1) = (B_0\times B_0)+(B_0\times B_1)+(B_1\times B_0)+(B_1\times B_1),

(adding subscripts to distinguish the two copies of BB) and the congruence is given by

B 2 + B 2 + Y + B 2 (B 0×B 0) + (B 0×B 1) + (B 1×B 0) + (B 1×B 1).\array{ B ^{\mathbf{2}} &+& B ^{\mathbf{2}} &+& Y &+& B ^{\mathbf{2}}\\ &&& \downarrow\\ (B_0\times B_0) &+& (B_0\times B_1) &+& (B_1\times B_0) &+& (B_1\times B_1).}

Here YB 2Y\hookrightarrow B ^{\mathbf{2}} is defined to be the ff image of the “composition” morphism (1 B/m/1 B)B 2(1_B/m/1_B) \to B ^{\mathbf{2}}; in other words it is “the object of arrows in BB which factor through some element of AA.” The composition is easy to define making this into a 2-congruence, and if BB is posetal, then it is a (1,2)-congruence.

Let [p,q]:B+BC[p,q]:B+B\to C be the quotient of this congruence. Analogously to the proof of Theorem , the fork defining this quotient gives a 2-cell ϕ:pq\phi:p\to q such that ϕm\phi m is an isomorphism. Thus, to show that mm is the inverter of ϕ\phi, it suffices to show that for any x:XBx:X\to B with ϕx\phi x invertible, xx factors through mm. Now ϕx\phi x is induced by the fork defining CC together with the composite XBB 2X\to B \to B ^{\mathbf{2}}. If ϕx\phi x is invertible, then its inverse is given by some map y:XYy:X\to Y, which must lie over the diagonal XBB×BX\to B \to B\times B.

Now, pulling back the eso (1/m/1)Y(1/m/1)\to Y along yy we obtain an eso r:ZXr:Z\to X with a morphism s:ZAs:Z\to A such that the identity 2-cell of xrx r is the composite of 2-cells xrmsxrx r \to m s \to x r; in other words, xrx r is a retract of msm s. But since BB is posetal, this means xrmsx r \cong m s, and then the fact that rr is eso implies that xx factors through mm, as desired.

Corollary

In a (1,2)-pretopos, 1. every ff is an inverter, 1. every liberal ff is an equivalence, and 1. every liberal morphism is eso.

Proof

Just like Corollary but using Theorem instead.

2-pretoposes are Cauchy balanced

Now, in any regular 2-category, in addition to the (eso,ff) factorization system we also have a Cauchy factorization system consisting of the cso (Cauchy surjective) and rff (ff and retract-closed) morphisms. Moreover, every cso is cofaithful and liberal. In “Modulated bicategories” by Carboni, Johnson, Street, and Verity (CJSV), it is shown that the liberal functors in Cat are precisely the Cauchy surjective ones; we now show that the same is true in any 2-pretopos.

Corollary

In a 2-pretopos, 1. every rff is an inverter, 1. every liberal rff is an equivalence, and 1. every liberal morphism is Cauchy surjective.

In particular, every liberal morphism is cofaithful.

Proof

The first statement is proven exactly like Theorem , except that at the last step we use the assumption that mm is retract-closed rather than the assumption that BB is posetal. The other statements follow as before, recalling that Cauchy surjective morphisms are cofaithful.

In (CJSV) a 2-category is defined to be co-conservational (liberational?) if

  • it has finite colimits,
  • it has (liberal, strong conservative) factorizations,
  • strong conservative morphisms are preserved by copowers with 2{\mathbf{2}}, and
  • strong conservative morphisms are stable under pushout,

and faithfully co-conservational if moreover

  • every liberal morphism is cofaithful.

Here a strong conservative morphism is one that is right orthogonal to all liberals. Theorem shows that in a 2-pretopos, strong conservatives coincide with rffs, since liberals coincide with csos; thus any 2-pretopos satisfies the second condition to be co-conservational. It need not have finite colimits, but this can be remedied with some infinitary structure. The construction of copowers in a 2-pretopos can be used to show that rffs are preserved by copowers with 2{\mathbf{2}}. And we have also seen that since every liberal is cso, it is cofaithful.

However, even CatCat fails the final condition, as shown in (CJSV, Prop. 3.4). This can be remedied by passing to the 2-category Cat ccCat_{cc} of Cauchy-complete categories. I do not yet know whether a similar construction is possible in any 2-pretopos.

Regular completion

Recall that there is a 2-category HDC(K)HDC(K) of homwise-discrete categories in any finitely complete 2-category KK. We write nCong s(K)n Cong_s(K) for its full sub-2-category spanned by the nn-congruences (always we take n=n= 2, (2,1), (1,2), or 1). Recall that there is a functor Φ:K2Cong s(K)\Phi:K\to 2Cong_s(K) sending each object to its kernel; if KK is an nn-category then the image of Φ\Phi is contained in nCong(K)n Cong(K).

Lemma

Suppose that KK has finite limits. Then:

  1. HDC(K)HDC(K) has finite limits.
  2. nCong s(K)n Cong_s(K) is closed under finite limits in HDC(K)HDC(K).
  3. Φ\Phi is 2-fully-faithful (that is, an equivalence on hom-categories) and preserves finite limits.
Proof

It suffices to deal with finite products, inserters, and equifiers. Evidently Φ(1)\Phi(1) is a terminal object. If DD and EE are homwise-discrete categories, define P 0=D 0×E 0P_0 = D_0\times E_0 and P 1=D 1×E 1P_1 = D_1\times E_1; it is easy to check that then P 1P 0P_1 \;\rightrightarrows\; P_0 is a homwise-discrete category that is the product D×ED\times E in HDC(K)HDC(K). Since (D 0×E 0) 2(D 0) 2×(E 0) 2(D_0\times E_0) ^{\mathbf{2}} \simeq (D_0) ^{\mathbf{2}} \times (E_0) ^{\mathbf{2}}, and products preserve ffs, we see that PP is an nn-congruence if DD and EE are and that Φ\Phi preserves products.

For inserters, let f,g:CDf,g:C \;\rightrightarrows\; D be functors in HDC(K)HDC(K), define i 0:I 0C 0i_0:I_0\to C_0 by the pullback

I 0 D 1 i 0 C 0 (f 0,g 0) D 0×D 0,\array{I_0 & \to & D_1\\ i_0 \downarrow && \downarrow \\ C_0 & \overset{(f_0,g_0)}{\to} & D_0\times D_0,}

and define i 1:I 1C 1i_1:I_1 \to C_1 by the pullback

I 1 X i 1 C 1 (f 1,g 1) D 1×D 1\array{I_1 & \to & X\\ i_1\downarrow && \downarrow\\ C_1 & \overset{(f_1,g_1)}{\to} & D_1\times D_1}

where XX is the “object of commutative squares in DD.” Then I 1I 0I_1 \;\rightrightarrows\; I_0 is a homwise-discrete category and i:ICi:I\to C is an inserter of f,gf,g. Also, II is an nn-congruence if CC is, and Φ\Phi preserves inserters.

Finally, for equifiers, suppose we have functors f,g:CDf,g:C \;\rightrightarrows\; D and 2-cells α,β:fg\alpha,\beta:f \;\rightrightarrows\; g in HDC(K)HDC(K), represented by morphisms a,b:C 0D 1a,b:C_0 \;\rightrightarrows\; D_1 such that (s,t)a(f 0,g 0)(s,t)b(s,t) a \cong (f_0,g_0)\cong (s,t) b. Let e 0:E 0C 0e_0:E_0\to C_0 be the universal morphism equipped with an isomorphism ϕ:ae 0be 0\phi:a e_0 \cong b e_0 such that (s,t)ϕ(s,t)\phi is the given isomorphism (s,t)a(s,t)b(s,t) a\cong (s,t) b (this is a finite limit in KK.) Note that since (s,t):D 1D 0×D 0(s,t):D_1\to D_0\times D_0 is discrete, e 0e_0 is ff. Now let E 1=(e 0×e 0) *C 1E_1 = (e_0\times e_0)^*C_1; then E 1E 0E_1 \;\rightrightarrows\; E_0 is a homwise-discrete category and e:ECe:E\to C is an equifier of α\alpha and β\beta in HDC(K)HDC(K). Also EE is an nn-congruence if CC is, and Φ\Phi preserves equifiers.

For any morphism f:ABf:A\to B in KK, Φ(f)\Phi(f) is the functor ker(A)ker(B)ker(A)\to ker(B) that consists of f:ABf:A\to B and f 2:A 2B 2f^{\mathbf{2}}: A^{\mathbf{2}} \to B^{\mathbf{2}}. A transformation between Φ(f)\Phi(f) and Φ(g)\Phi(g) is a morphism AB 2A\to B ^{\mathbf{2}} whose composites AB 2BA\to B ^{\mathbf{2}} \;\rightrightarrows\; B are ff and gg; but this is just a transformation fgf\to g in KK. Thus, Φ\Phi is homwise fully faithful. And homwise essential-surjectivity follows from the essential uniqueness of thin structures, or equivalently a version of Prop 6.4 in FBMF.

Moreover, we have:

Theorem

If KK is an nn-category with finite limits, then nCong s(K)n Cong_s(K) is regular.

Proof

It is easy to see that a functor f:CDf:C\to D between nn-congruences is ff in nCong s(K)n Cong_s(K) iff the square

C 1 D 1 C 0×C 0 D 0×D 0\array{C_1 & \to & D_1\\ \downarrow && \downarrow\\ C_0\times C_0 & \to & D_0\times D_0}

is a pullback in KK.

We claim that if e:EDe:E\to D is a functor such that e 0:E 0D 0e_0:E_0\to D_0 is split (that is, e 0s1 D 0e_0 s\cong 1_{D_0} for some s:D 0E 0s:D_0\to E_0), then ee is eso in nCong s(K)n Cong_s(K). For if efge\cong f g for some ff f:CDf:C\to D as above, then we have g 0s:D 0C 0g_0 s:D_0 \to C_0 with f 0g 0se 0s1 D 0f_0 g_0 s \cong e_0 s \cong 1_{D_0}, and so the fact that C 1C_1 is a pullback induces a functor h:DCh:D\to C with h 0=g 0sh_0=g_0 s and fh1 Df h\cong 1_D. But this implies ff is an equivalence; thus ee is eso.

Moreover, if e 0:E 0D 0e_0:E_0\to D_0 is split, then the same is true for any pullback of ee. For the pullback of e:EDe:E\to D along some k:CDk:C\to D is given by a PP where P 0=E 0× D 0D iso× D 0C 0P_0 = E_0 \times_{D_0} D_{iso} \times_{D_0} C_0; here D isoD 1D_{iso}\hookrightarrow D_1 is the “object of isomorphisms” in DD. What matters is that the projection P 0C 0P_0\to C_0 has a splitting given by combining the splitting of e 0e_0 with the “identities” morphism D 0D isoD_0\to D_{iso}.

Now suppose that f:DEf:D\to E is any functor in nCong s(K)n Cong_s(K). It is easy to see that if we define Q 0=D 0Q_0=D_0 and let Q 1Q_1 be the pullback

Q 1 E 1 Q 0×Q 0 f 0×f 0 E 0×E 0\array{ Q_1 & \to & E_1 \\ \downarrow && \downarrow\\ Q_0 \times Q_0 & \overset{f_0\times f_0}{\to} & E_0\times E_0}

then fmef \cong m e where e:DQe:D \to Q and m:QEm:Q\to E are the obvious functors. Moreover, clearly mm is ff, and ee satisfies the condition above, so any pullback of it is eso. It follows that if ff itself were eso, then it would be equivalent to ee, and thus any pullback of it would also be eso; hence esos are stable under pullback.

Since mm is ff, the kernel of ff is the same as the kernel of ee, so to prove KK regular it remains only to show that ee is a quotient of that kernel. If CDC \;\rightrightarrows\; D denotes ker(f)ker(f), then CC is the comma object (f/f)(f/f) and thus we can calculate

C 0=D 0× E 0E 1× E 0D 0Q 1.C_0 = D_0\times_{E_0} E_1 \times_{E_0} D_0 \cong Q_1.

Therefore, if g:DXg:D\to X is equipped with an action by ker(f)ker(f), then the action 2-cell is given by a morphism Q 1=C 0X 1Q_1=C_0\to X_1, and the action axioms evidently make this into a functor QXQ\to X. Thus, QQ is a quotient of ker(f)ker(f), as desired.

However, there are three problems with the 2-category nCong s(K)n Cong_s(K).

  1. It is too big. It is not necessary to include every nn-congruence in order to get a regular category containing KK, only those that occur as kernels of morphisms in KK.
  2. It is too small. While it is regular, it is not exact.
  3. It doesn’t remember information about KK. If KK is already regular, then passing to nCong s(K)n Cong_s(K) destroys most of the esos and quotients already present in KK.

The solution to the first problem is straightforward. If KK is a 2-category with finite limits, define K reg/lexK_{reg/lex} to be the sub-2-category of 2Cong s(K)2 Cong_s(K) spanned by the 2-congruences which occur as kernels of morphisms in KK. If KK is an nn-category then any such kernel is an nn-congruence, so in this case K reg/lexK_{reg/lex} is contained in nCong s(K)n Cong_s(K) and is an nn-category. Also, clearly Φ\Phi factors through K reg/lexK_{reg/lex}.

Theorem

For any finitely complete 2-category KK, the 2-category K reg/lexK_{reg/lex} is regular, and the functor Φ:KK reg/lex\Phi:K\to K_{reg/lex} induces an equivalence

Reg(K reg/lex,L)Lex(K,L)Reg(K_{reg/lex},L) \simeq Lex(K,L)

for any regular 2-category KK.

Here Reg(,)Reg(-,-) denotes the 2-category of regular functors, transformations, and modifications between two regular 2-categories, and likewise Lex(,)Lex(-,-) denotes the 2-category of finite-limit-preserving functors, transformations, and modifications between two finitely complete 2-categories.

Proof

It is easy to verify that K reg/lexK_{reg/lex} is closed under finite limits in 2Cong s(K)2 Cong_s(K), and also under the eso-ff factorization constructed in Theorem ; thus it is regular. If F:KLF:K\to L is a lex functor where LL is regular, we extend it to K reg/lexK_{reg/lex} by sending ker(f)ker(f) to the quotient in LL of ker(Ff)ker(F f), which exists since LL is regular. It is easy to verify that this is regular and is the unique regular extension of FF.

In particular, if KK is a regular 1-category, K reg/lexK_{reg/lex} is the ordinary regular completion of KK. In this case our construction reduces to one of the usual constructions (see, for example, the Elephant).

To solve the second and third problems with nCong s(K)n Cong_s(K), we need to modify its morphisms.

Exact completion

Recall that 2-congruences in CatCat can be identified with certain double categories. As noted in PAPDC, edge-symmetric double categories with a thin structure are essentially the same as 2-categories, and homwise-discreteness makes them the same as 1-categories. Our lack of edge-symmetry means that we really have a 1-category with distinguished subclass of morphisms (the vertical ones), which must be preserved by functors between congruences. (Note that the transformations are “horizontal” and need not have distinguished components. Since every vertical arrow has a horizontal companion, any vertical transformation is represented by a horizontal one.) In order to eliminate the effect of the distinguished vertical morphisms, we can replace functors between congruences by anafunctors.

Definition

Suppose that KK is a finitely complete 2-site and that DD, EE, and FF are 2-congruences in KK. A functor g:FDg:F\to D is a weak equivalence if 1. the square

F 1 g 1 D 1 F 0×F 0 g 0×g 0 D 0×D 0\array{F_1 &\overset{g_1}{\to} & D_1 \\ \downarrow && \downarrow\\ F_0\times F_0 & \overset{g_0\times g_0}{\to} & D_0\times D_0}

is a pullback, and 1. g 0:F 0D 0g_0:F_0\to D_0 is a cover (a one-element covering family). An anafunctor DED\to E is a span of functors Df sFf tED \overset{f^s}{\leftarrow} F \overset{f^t}{\to} E such that f sf^s is a weak equivalence.

The primary example we have in mind is when KK is a regular 2-category with its regular coverage, but it is useful to consider the general case.

Definition

If DFED \leftarrow F \to E and DGED \leftarrow G \to E are anafunctors between 2-congruences, then a transformation FGF\to G is a transformation between the two induced functors F× DGEF\times_D G\;\rightrightarrows\; E.

(Here F× DGF\times_D G denotes the pullback in 2Cong s(K)2 Cong_s(K).)

Theorem

For any subcanonical and finitely complete 2-site KK (such as a regular nn-category with its regular coverage), there is a finitely complete 2-category 2Cong(K)2Cong(K) of 2-congruences, anafunctors, and transformations in KK. It contains 2Cong s(K)2Cong_s(K) as a homwise-full sub-2-category (that is, 2Cong s(K)(D,E)2Cong(K)(D,E)2Cong_s(K)(D,E)\hookrightarrow 2Cong(K)(D,E) is ff) closed under finite limits.

Proof

Composition is, of course, by pullback. Since covers are stable under pullback and composition, the composite of anafunctors is again an anafunctor. The coverage must be subcanonical in order to define the vertical composite of natural transformations. We regard a functor as an anafunctor by taking f sf^s to be the identity; it is then clear that a transformation between functors is the same as a transformation between their corresponding anafunctors.

It is easy to see that products in 2Cong S(K)2 Cong_S(K) remain products in nCong(K)n Cong(K). Before dealing with inserters and equifiers, we observe that if AFBA\leftarrow F \to B is an anafunctor in 2Cong(K)2 Cong(K) and e:X 0F 0e:X_0\to F_0 is any eso, then pulling back F 1F_1 to X 0×X 0X_0\times X_0 defines a new congruence XX and an anafunctor AXBA \leftarrow X \to B which is isomorphic to the original in 2Cong(K)(A,B)2 Cong(K)(A,B). Thus, if AFBA\leftarrow F\to B and AGBA\leftarrow G\to B are parallel anafunctors in 2Cong(K)2 Cong(K), by pulling them both back to F× AGF\times_A G we may assume that they are defined by spans with the same first leg, i.e. we have AXBA\leftarrow X \;\rightrightarrows\; B.

Now, for the inserter of FF and GG as above, let EXE\to X be the inserter of XBX \;\rightrightarrows\; B in 2Cong s(K)2 Cong_s(K). It is easy to check that the composite EXAE\to X \to A is an inserter of F,GF,G in 2Cong(K)2 Cong(K). Likewise, given α,β:FG\alpha,\beta: F \;\rightrightarrows\; G with FF and GG as above, we have transformations between the two functors XBX \;\rightrightarrows\; B in 2Cong s(K)2 Cong_s(K), and it is again easy to check that their equifier in 2Cong s(K)2 Cong_s(K) is again the equifier in 2Cong(K)2 Cong(K) of the original 2-cells α,β\alpha,\beta. Thus, 2Cong(K)2 Cong(K) has finite limits. Finally, by construction clearly the inclusion of 2Cong s(K)2 Cong_s(K) preserves finite limits.

We write nCong(K)n Cong(K) for the full sub-2-category of 2Cong(K)2Cong(K) on the nn-congruences, which is a finitely complete nn-category. Of course, it contains nCong s(K)n Cong_s(K) as a homwise-full sub-nn-category closed under finite limits, and when KK is an nn-category we have Φ:KnCong(K)\Phi:K \to n Cong(K).

Theorem

If KK is a subcanonical finitely complete nn-site, then the functor Φ:KnCong(K)\Phi:K\to n Cong(K) is 2-fully-faithful. If KK is an nn-exact nn-category equipped with its regular coverage, then Φ:KnCong(K)\Phi:K\to n Cong(K) is an equivalence of 2-categories.

Proof

Since Φ:KnCong s(K)\Phi:K \to n Cong_s(K) is 2-fully-faithful and nCong s(K)nCong(K)n Cong_s(K)\to n Cong(K) is homwise fully faithful, Φ:KnCong(K)\Phi:K \to n Cong(K) is homwise fully faithful. For homwise essential-surjectivity, suppose that ker(A)Fker(B)ker(A) \leftarrow F \to ker(B) is an anafunctor. Then h:F 0Ah:F_0 \to A is a cover and F 1F_1 is the pullback of A 2A ^{\mathbf{2}} along it; but this just says that F 1=(h/h)F_1 = (h/h). The functor FBF\to B consists of morphisms g:F 0Bg:F_0\to B and F 1=(h/h)B 2F_1 = (h/h) \to B ^{\mathbf{2}}, and functoriality says precisely that the resulting 2-cell equips gg with an action by the congruence FF. But since FF is precisely the kernel of h:F 0Ah:F_0\to A, which is a cover in a subcanonical 2-site and hence the quotient of this kernel, we have an induced morphism f:ABf:A\to B in KK. It is then easy to check that ff is isomorphic, as an anafunctor, to FF. Thus, Φ\Phi is homwise an equivalence.

Now suppose that KK is an nn-exact nn-category and that DD is an nn-congruence. Since KK is nn-exact, DD has a quotient q:D 0Qq:D_0\to Q, and since DD is the kernel of qq, we have a functor Dker(Q)D \to ker(Q) which is a weak equivalence. Thus, we can regard it either as an anafunctor Dker(Q)D\to ker(Q) or ker(Q)Dker(Q)\to D, and it is easy to see that these are inverse equivalences in nCong(K)n Cong(K). Thus, Φ\Phi is essentially surjective, and hence an equivalence.

Note that by working in the generality of 2-sites, this construction includes the previous one. Specifically, if KK is a finitely complete 2-category equipped with its minimal coverage, in which the covering families are those that contain a split epic, then nCong(K)nCong s(K)n Cong(K) \simeq n Cong_s(K). This is immediate from the proof of Theorem , which implies that the first leg of any anafunctor relative to this coverage is both eso and ff in nCong s(K)n Cong_s(K), and hence an equivalence.

We also remark in passing that this allows us to reconstruct 2-exact 2-categories with enough groupoids or discretes from their subcategories of such.

Theorem

If KK is a 2-exact 2-category with enough groupoids, then K2Cong(gpd(K))K\simeq 2 Cong(gpd(K)). Likewise, if KK is 2-exact and has enough discretes, then K2Cong(disc(K))K\simeq 2 Cong(disc(K)).

Proof

Define a functor K2Cong(gpd(K))K\to 2Cong(gpd(K)) by taking each object AA to the kernel of j:JAj:J\to A where jj is eso and JJ is groupoidal (for example, it might be the core of AA). Note that this kernel lives in 2Cong(gpd(K))2Cong(gpd(K)) since (j/j)J×J(j/j)\to J\times J is discrete, hence (j/j)(j/j) is also groupoidal. The same argument as in Theorem shows that this functor is 2-fully-faithful for any regular 2-category KK with enough groupoids, and essentially-surjective when KK is 2-exact; thus it is an equivalence. The same argument works for discrete objects.

In particular, the 2-exact 2-categories having enough discretes are precisely the 2-categories of internal categories and anafunctors in 1-exact 1-categories.

Our final goal is to construct the nn-exact completion of a regular nn-category, and a first step towards that is the following.

Theorem

If KK is a regular nn-category, so is nCong(K)n Cong(K). The functor Φ:KnCong(K)\Phi:K\to n Cong(K) is regular, and moreover for any nn-exact 2-category LL it induces an equivalence

Reg(nCong(K),L)Reg(K,L).Reg(n Cong(K), L) \to Reg(K,L).
Proof

We already know that nCong(K)n Cong(K) has finite limits and Φ\Phi preserves finite limits. The rest is very similar to Theorem . We first observe that an anafunctor AFBA \leftarrow F \to B is an equivalence as soon as FBF\to B is also a weak equivalence (its reverse span BFAB\leftarrow F \to A then provides an inverse.) Also, AFBA \leftarrow F \to B is ff if and only if

F 1 B 1 F 0×F 0 B 0×B 0\array{F_1 & \to & B_1\\ \downarrow && \downarrow \\ F_0\times F_0 & \to & B_0\times B_0}

is a pullback.

Now we claim that if AFBA\leftarrow F \to B is an anafunctor such that F 0B 0F_0\to B_0 is eso, then FF is eso. For if we have a composition

F G M A C B\array{ &&&& F \\ &&& \swarrow && \searrow\\ && G &&&& M\\ & \swarrow && \searrow && \swarrow && \searrow\\ A &&&& C &&&& B}

such that MM is ff, then F 0B 0F_0\to B_0 being eso implies that M 0B 0M_0\to B_0 is also eso; thus MBM\to B is a weak equivalence and so MM is an equivalence. Moreover, by the construction of pullbacks in nCong(K)n Cong(K), anafunctors with this property are stable under pullback.

Now suppose that AFBA \leftarrow F \to B is any anafunctor, and define C 0=F 0C_0=F_0 and let C 1C_1 be the pullback of B 1B_1 to C 0×C 0C_0\times C_0 along C 0=F 0toB 0C_0 = F_0 to B_0. Then CC is an nn-congruence, CBC\to B is ff in nCong s(K)n Cong_s(K) and thus also in nCong(K)n Cong(K), and AFBA \leftarrow F \to B factors through CC. (In fact, CC is the image of FBF\to B in nCong s(K)n Cong_s(K).) The kernel of AFBA\leftarrow F\to B can equally well be calculated as the kernel of FBF\to B, which is the same as the kernel of FCF\to C.

Finally, given any AGDA\leftarrow G \to D with an action by this kernel, we may as well assume (by pullbacks) that F=GF=G (which leaves CC unchanged up to equivalence). Then since the kernel acting is the same as the kernel of FCF\to C, regularity of nCong s(K)n Cong_s(K) gives a descended functor CDC\to D. Thus, AFCA\leftarrow F \to C is the quotient of its kernel; so nCong(K)n Cong(K) is regular.

Finally, if LL is nn-exact, then any functor KLK\to L induces one nCong(K)nCong(L)n Cong(K) \to n Cong(L), but nCong(L)Ln Cong(L)\simeq L, so we have our extension, which it can be shown is unique up to equivalence.

When KK is a regular 1-category, it is well-known that 1Cong(K)1 Cong(K) (which, in that case, is the category of internal equivalence relations and functional relations) is the 1-exact completion of KK (the reflection of KK from regular 1-categories into 1-exact 1-categories). Theorem shows that in general, nCong(K)n Cong(K) will be the nn-exact completion of KK whenver it is nn-exact. However, in general for n>1n\gt 1 we need to “build up exactness” in stages by iterating this construction.

It is possible that the iteration will converge at some finite stage, but for now, define nCong r(K)=nCong(nCong r1(K))n Cong^r(K) = n Cong(n Cong^{r-1}(K)) and let K nex/reg=colim rnCong r(K)K_{n ex/reg} = colim_r n Cong^r(K).

Theorem

For any regular nn-category KK, K nex/regK_{n ex/reg} is an nn-exact nn-category and there is a 2-fully-faithful regular functor Φ:KK nex/reg\Phi:K\to K_{n ex/reg} that induces an equivalence

Reg(K nex/reg,L)Reg(K,L)Reg(K_{n ex/reg},L) \simeq Reg(K,L)

for any nn-exact 2-category LL.

Proof

Sequential colimits preserve 2-fully-faithful functors as well as functors that preserve finite limits and quotients, and the final statement follows easily from Theorem . Thus it remains only to show that K nex/regK_{n ex/reg} is nn-exact. But for any nn-congruence D 1D 0D_1 \;\rightrightarrows\; D_0 in K nex/regK_{n ex/reg}, there is some rr such that D 0D_0 and D 1D_1 both live in nCong r(K)n Cong^r(K), and thus so does the congruence since nCong r(K)n Cong^r(K) sits 2-fully-faithfully in K nex/regK_{n ex/reg} preserving finite limits. This congruence in nCong r(K)n Cong^r(K) is then an object of nCong r+1(K)n Cong^{r+1}(K) which supplies a quotient there, and thus also in K nex/regK_{n ex/reg}.

2-internal logic

Introduction

This page, and subsequent ones, contains an overview of my current thinking about the “internal logic of a 2-category”, as part of the 2-categorical logic project. This logic is not by any means set in stone; it’s simply the most recent incarnation (or, more accurately, the most recent incarnation that I’ve managed to write up) of evolving ideas. Any suggestions for improvement are greatly appreciated.

As adumbrated at categorified logic, the logic we use will be a logic of dependent types. In general, we allow three different sorts of types, which we call 1-types (categories, sort denoted CatCat), 0-types (sets, sort denoted SetSet), and (-1)-types (propositions, sort denoted PropProp). We could include (0,1)-types (posets) and (1,0)-types (groupoids) as well, but these rarely seem as important as the other three; thus we will just identify posets and groupoids with particular categories. (Note that by using the word “set” for the 0-types, we do not in general intend to imply any smallness condition on them.)

Eventually, we will allow dependent types, with dependencies of nn-types on mm-types whenever nmn\le m. This will eventually involve additional subtleties with dependent products and sums, which require the “variance” of the dependencies to be specified. For now, however, we will focus on first-order logic, with no “real” type dependencies. We will also make minimal use of the sort SetSet. We do, however, require two type dependencies: dependency of propositions on types (i.e. predicate logic) and homhom-types which are dependent on objects. The latter will be the only types of sort SetSet we consider for now. However, we set up some of the basic notions in more generality, so as not to have to re-do them later.

Hom-types and equality types

A basic tenet of higher category theory is that if AA is an nn-category and x,yAx,y\in A then hom A(x,y)hom_A(x,y) is an (n1)(n-1)-category. For us, this means that if AA is an nn-type and x:A,y:Ax:A,y:A then we have a dependent (n1)(n-1)-type hom A(x,y)hom_A(x,y). For instance, if n=1n=1, then hom A(x,y)hom_A(x,y) is a 0-type: the type of arrows from xx to yy. And if n=0n=0, then hom A(x,y)hom_A(x,y) is a (-1)-type; in other words, a proposition, which we of course interpret as the assertion x=yx=y. (If n=(0,1)n=(0,1), it would instead be the assertion xyx\le y.) So equality is a special case of the formation of hom-types.

In particular, note that equality, as a proposition, is only defined between elements of a 0-type. Thus, our language doesn’t even have the terminology to speak about equality between objects of a 1-type (category), only equality between elements of a 0-type (such as arrows in a category). This is also known as the “Speak No Evil” approach to category theory.

But if thought corrupts language, language can also corrupt thought. – George Orwell

Of course, these arrow-types are notably similar to the identity types in many versions of traditional Martin-Lof dependent type theory. In fact, it is well-known by now that equality types can be usefully interpreted in categories of groupoids or in homotopical categories. (Hoffman-Striecher, “The groupoid interpretation of type theory”; Awodey-Warren, “Homotopy theoretic models of identity types”.) Of course, the main difference is that arrow-types are (in general) directional. This makes it trickier to formulate “elimination rules” that generalize the rules for ordinary identity types, but we can still have a go?. We ought also to be able to construct “iso-types” iso A(x,y)iso_A(x,y) as subtypes of hom A(x,y)hom_A(x,y), which will behave like identity types. This will all come later, however.

Contexts and Judgments

Treating nn-types on an equal footing for all nn, we can say that our theories will consist only of two sorts of judgments:

  • ΓA:nType\Gamma \vdash A:n Type (type declarations)
  • Γa:A\Gamma \vdash a:A (term declaration)

In each case Γ\Gamma is a context, such as x:A,y:B,z:Cx:A,y:B,z:C, which declares the variables that occur in the rest of the judgement. Each type occurring in Γ\Gamma can depend on the variables occurring before it; thus we can have x:A,y:B(x)x:A, y:B(x) but not x:A(y),y:Bx:A(y), y:B. Formally, this means that the contexts are generated inductively according to the following rules:

  • The empty list is a context.
  • If Γ\Gamma is a context and ΓA:nType\Gamma \vdash A:n Type is derivable (where variables of Γ\Gamma can appear in AA), and xx is a fresh variable not appearing in Γ\Gamma, then Γ,x:A\Gamma, x:A is a context.

Whenever we write a context it is assumed that there is no duplication of variables; this results in implicit hypotheses on the derivation rules.

To keep things looking familiar, we will usually write PropProp instead of (1)Type(-1)Type, SetSet instead of 0Type0 Type, and CatCat instead of 1Type1Type. Moreover, since any two inhabitants of a (-1)-type are indistinguishable (since our type theory is extensional and proof-irrelevant), we will generally write merely φ\varphi instead of x:φx:\varphi when φ\varphi is a (-1)-type (a proposition). For the same reason, we never need to think about equality for inhabitants of propositions. Likewise, there can be no interesting dependence of a proposition on another proposition, so we omit propositions from the declarations of other propositions. We do, however, allow terms of an nn-type to depend on a variable of an mm-type for any nn and mm, even m=1m=-1.

Rules for deriving judgements

As is usual in type theories, we write

ABC\frac{A \qquad B}{C}

to mean that from the judgements AA and BB, we can deduce the judgement CC. We write JJ for the right-hand side of an arbitrary judgement of any sort. We write J[a/x]J[a/x] for the result of substituting the term aa for the variable xx in JJ, and we do the same for contexts.

The following rules are the basic ones for first-order 2-categorical logic. We will add additional rules in later sections, to deal with size and type dependency. Of course, any particular theory will have its own additional basic types, terms, and axioms as well.

Structural rules

These are just the same as in ordinary type theory, and fairly boring.

ΓA:nTypeΓ,x:Ax:A(projection)\frac{\Gamma\vdash A:n Type}{\Gamma, x:A \vdash x:A} (projection)

Γa:AΓ,x:A,ΔJΓ,Δ[a/x]J[a/x](substitution)\frac{\Gamma\vdash a:A \qquad \Gamma, x:A, \Delta \vdash J} {\Gamma, \Delta[a/x] \vdash J[a/x]} (substitution)

Γ,x:A,y:A,ΔJΓ,x:A,Δ[x/y]J[x/y](contraction)\frac{\Gamma, x:A, y:A, \Delta \vdash J} {\Gamma,x:A, \Delta[x/y] \vdash J[x/y]} (contraction)

ΓA:nTypeΓJΓ,x:AJ(weakening)\frac{\Gamma \vdash A:n Type \qquad \Gamma\vdash J}{\Gamma, x:A \vdash J} (weakening)

Γ,x:A,y:B,ΔJΓ,y:B,x:A,ΔJ(exchange)\frac{\Gamma, x:A, y:B, \Delta \vdash J} {\Gamma, y:B, x:A, \Delta \vdash J} (exchange)

The exchange rule has, of course, the extra restriction that xx cannot occur freely in the type BB.

Propositional equality

As suggested above, propositional equality is only meaningful for terms of a 0-type. Recall that for now, the only 0-types we consider will be hom-sets (or constructed from hom-sets).

ΓA:SetΓ,x:A,y:A(x=y):Prop(equality)\frac{\Gamma \vdash A:Set} {\Gamma, x:A, y:A \vdash (x=y):Prop} (equality)

ΓA:SetΓ,x:A(x=x)(reflexivity)\frac{\Gamma \vdash A:Set}{\Gamma, x:A \vdash (x=x)} (reflexivity)

There are also the usual symmetry, transitivity, and substitution rules for equality. These can probably be formulated only using substitution, in the style of identity types.

Arrow types

ΓA:CatΓ,x:A,y:Ahom A(x,y):Set(arrowtype)\frac{\Gamma \vdash A:Cat} {\Gamma, x:A, y:A \vdash hom_A(x,y):Set} (arrow type)

ΓA:CatΓ,x:A1 x:hom A(x,x)(identities)\frac{\Gamma \vdash A:Cat} {\Gamma, x:A\vdash 1_x:hom_A(x,x)} (identities)

In theory, there should be a “directional elimination rule” for arrow-types, akin to the elimination rule for identity types in ordinary intensional type theory. However, for its correct formulation this will certainly require functorially dependent types, and it’s not even entirely clear what it should say then. So we will just directly assert the following basic operations on arrows.

ΓA:CatΓ,x:A,y:A,z:A,f:hom A(x,y),g:hom A(y,z)gf:hom A(x,z)(composition)\frac{\Gamma \vdash A:Cat} {\Gamma, x:A, y:A, z:A, f:hom_A(x,y), g:hom_A(y,z)\vdash g\circ f: hom_A(x,z)} (composition)

ΓA:CatΓ,x:A,y:A,z:A,w:A,f:hom A(x,y),g:hom A(y,z),h:hom A(z,w)(h(gf)=(hg)f)(associativity)\frac{\Gamma \vdash A:Cat} {\Gamma, x:A, y:A, z:A, w:A, f: hom_A(x,y), g:hom_A(y,z), h:hom_A(z,w) \vdash (h \circ (g\circ f) = (h\circ g)\circ f)} (associativity)

ΓA:CatΓ,x:A,y:A,f:hom A(x,y)((f1 x)=f)(rightunit)\frac{\Gamma \vdash A:Cat} {\Gamma, x:A, y:A, f:hom_A(x,y) \vdash ((f\circ 1_x) = f)}(right unit)

ΓA:TypeΓ,x:A,y:A,f:hom A(x,y)|((1 yf)=f)(leftunit)\frac{\Gamma \vdash A:Type} {\Gamma, x:A, y:A, f:hom_A(x,y) | \top \vdash ((1_y\circ f) = f)}(left unit)

Functoriality and naturality

Functoriality is probably the most subtle of the rules for arrow types. The idea is that a term declaration of the form Γb:B\Gamma \vdash b:B describes a morphism in the ambient 2-category from the object representing the context Γ\Gamma to the object representing the term BB. But morphisms in a 2-category act like functors in the internal logic, and functors act on arrows as well as objects.

B:CatΓ,x:Ab:BΓ,y:A,z:A,f:hom A(y,z)b(f/x):hom B(b[y/x],b[z/x])(functoriality)\frac{\vdash B:Cat \qquad \Gamma, x:A \vdash b:B} {\Gamma, y:A, z:A, f:hom_A(y,z) \vdash b(f/x): hom_B(b[y/x],b[z/x])} (functoriality)

The term b(f/x)b(f/x) does not indicate any actual substitution of ff for xx (which would be nonsensical since they have different types). Rather, it is a decoration which converts the term b:Bb:B with free variable x:Ax:A into a term b(f/x):hom B(b[y/x],b[z/x])b(f/x): hom_B(b[y/x],b[z/x]) with free variable f:hom A(y,z)f:hom_A(y,z). In particular, ff is free in b(f/x)b(f/x) while xx is no longer free.

Γ,x:AB:CatΓ,x:Ab:BΓ,x:A(b(1 y/x)=1 b[y/x])(functorialityonidentities)\frac{\Gamma,x:A \vdash B:Cat \qquad \Gamma, x:A \vdash b:B} {\Gamma, x:A \vdash (b(1_y/x) = 1_{b[y/x]})} (functoriality on identities)

Γ,x:AB:CatΓ,x:Ab:BΓ,y:A,z:A,w:A,f:hom A(y,z),g:hom A(z,w)b(g/x)b(f/x)=b(gf/x)(functorialityoncomposition)\frac{\Gamma, x:A \vdash B:Cat \qquad \Gamma, x:A \vdash b:B} {\Gamma, y:A, z:A, w:A, f:hom_A(y,z), g:hom_A(z,w) \vdash b(g/x) \circ b(f/x) = b(g\circ f/x)} (functoriality on composition)

Similarly, a term Γ,x:Aj:hom B(b 1,b 2)\Gamma, x:A \vdash j:hom_B(b_1,b_2) should represent a 2-cell between the morphisms represented by b 1b_1 and b 2b_2, which should be a natural transformation in the internal logic.

Γ,x:AB:CatΓ,x:Aj:hom B(b 1,b 2)Γ,y:A,z:A,f:hom A(y,z)(j[z/x]b 1(f/x)=b 2(g/x)j[y/x])(naturality)\frac{\Gamma, x:A \vdash B:Cat \qquad \Gamma, x:A \vdash j:hom_B(b_1,b_2)} {\Gamma, y:A, z:A, f:hom_A(y,z) \vdash (j[z/x] \circ b_1(f/x) = b_2(g/x) \circ j[y/x])}(naturality)

Logical operations

The logical operations on propositions are morally special cases of operations on dependent types. But real dependent types will come later, so we introduce the logical operations explicitly now. We list all the possible logical operations here, but we will also be interested in fragments of logic containing only some of these operations.

Truth:

:Prop\frac{}{\vdash \top:Prop}

\frac{}{\vdash \top}

Conjunction:

Γφ:PropΓψ:PropΓ(φψ):Prop\frac{\Gamma \vdash \varphi:Prop \qquad \Gamma \vdash \psi:Prop}{\Gamma \vdash (\varphi\wedge\psi) :Prop}

ΓφΓψΓ(φψ)\frac{\Gamma \vdash \varphi \qquad \Gamma \vdash \psi}{\Gamma \vdash (\varphi\wedge\psi)}

Γ(φψ)ΓφΓψ\frac{\Gamma \vdash (\varphi\wedge\psi)}{\Gamma \vdash \varphi \qquad \Gamma \vdash \psi}

We may also have infinitary conjunctions, with an evident extension of the rules.

Falsity:

:Prop\frac{}{\vdash \bot:Prop}

ΓΓφ:PropΓφ\frac{\Gamma \vdash \bot \qquad \Gamma \vdash \varphi:Prop}{\Gamma \vdash \varphi}

Disjunction:

Γφ:PropΓψ:PropΓ(φψ):Prop\frac{\Gamma \vdash \varphi:Prop \qquad \Gamma \vdash \psi:Prop}{\Gamma \vdash (\varphi\vee\psi) :Prop}

ΓφΓ(φψ)\frac{\Gamma \vdash \varphi}{\Gamma\vdash (\varphi\vee\psi)}

ΓψΓ(φψ)\frac{\Gamma \vdash \psi}{\Gamma\vdash (\varphi\vee\psi)}

Γ,φχΓ,ψχΓ,(φψ)χ\frac{\Gamma, \varphi \vdash \chi \qquad \Gamma,\psi \vdash \chi}{\Gamma, (\varphi\vee\psi) \vdash \chi}

We may also have infinitary disjunctions, with an evident extension of the rules. In a theory lacking implication, we also require explicitly the distributive axiom:

Γ(φ(ψχ))Γ(φψ)(φχ)\frac{\Gamma \vdash (\varphi\wedge (\psi\vee\chi))}{\Gamma \vdash (\varphi\wedge \psi)\vee(\varphi\wedge \chi)}

Implication:

Γφ:PropΓψ:PropΓφψ:Prop\frac{\Gamma \vdash \varphi:Prop \qquad \Gamma \vdash \psi :Prop}{\Gamma \vdash \varphi\Rightarrow\psi :Prop}

Γ,φψΓφψ\frac{\Gamma, \varphi \vdash \psi}{\Gamma \vdash \varphi\Rightarrow\psi}

ΓφψΓ,φψ\frac{\Gamma \vdash \varphi\Rightarrow\psi}{\Gamma, \varphi \vdash \psi}

We have quantification over both 1-types and 0-types, beginning with existential quantification:

ΓA:nTypeΓ,x:Aφ(x):PropΓ(x:A)φ(x):Prop\frac{\Gamma \vdash A:n Type\qquad \Gamma, x:A \vdash \varphi(x):Prop}{\Gamma \vdash (\exists x:A) \varphi(x) :Prop}

Γt:AΓφ(t)Γ(x:A)φ(x)\frac{\Gamma \vdash t:A \qquad \Gamma \vdash \varphi(t)}{\Gamma \vdash (\exists x:A) \varphi(x)}

Γ,x:A,φ(x)ψΓ,(x:A)φ(x)ψ\frac{\Gamma, x:A, \varphi(x) \vdash \psi}{\Gamma, (\exists x:A)\varphi(x) \vdash \psi}

In the above elimination rule, xx cannot occur free in ψ\psi. In a theory lacking implication, we must also assert the Frobenius axiom:

Γ(φ(x:A)ψ(x))Γ(x:A)(φψ(x))\frac{\Gamma \vdash (\varphi \wedge (\exists x:A)\psi(x))}{\Gamma \vdash (\exists x:A)(\varphi\wedge \psi(x))}

Universal quantification:

ΓA:nTypeΓ,x:Aφ(x):PropΓ(x:A)φ(x):Prop\frac{\Gamma \vdash A:n Type\qquad \Gamma, x:A \vdash \varphi(x):Prop}{\Gamma \vdash (\forall x:A) \varphi(x) :Prop}

Γ,x:Aφ(x)Γ(x:A)φ(x)\frac{\Gamma, x:A \vdash \varphi(x)}{\Gamma \vdash (\forall x:A) \varphi(x)}

Γ(x:A)φ(x)Γ,x:Aφ(x)\frac{\Gamma \vdash (\forall x:A)\varphi(x)}{\Gamma, x:A \vdash \varphi(x)}

First-order 2-categorical theories

A 2-categorical first-order theory, or a first-order 2-theory for short, consists of:

  • the choice of a particular fragment of the logical rules.

  • a set of basic (non-dependent) 1-types A,B,A,B,\dots, i.e. axioms of the form A:1Type\vdash A:1 Type.

  • a set of basic (non-dependent) 0-types, i.e. axioms of the form A:0Type\vdash A:0 Type.

  • a set of basic dependent propositions, i.e. axioms of the form Γφ:Prop\Gamma \vdash \varphi:Prop. Here φ\varphi will depend on the typed variables occurring in Γ\Gamma.

  • a set of basic terms-in-context, i.e. axioms of the form Γt:A\Gamma \vdash t:A. We require that these axioms come with a well-founded ordering, such that ΓA:nType\Gamma \vdash A:n Type is provable from axioms preceeding it and based on the chosen logical fragment. Note that we also allow Γ\Gamma to contain propositions.

  • strictly speaking, the previous list of axioms includes logical axioms, but we can state these separately anyway: a set of axioms of the form Γφ\Gamma \vdash \varphi, where Γφ:Prop\Gamma \vdash \varphi:Prop is provable. Note that of course, Γ\Gamma can include propositions as well as 1-types and 0-types.

Note that we do not allow axiomatic dependent 1-types or 0-types. The problem with these is that they generally need to be “functorially” dependent, and we don’t want to get into that now.

Fragments of logic

The most commonly relevant fragments of logic are:

  • cartesian logic: the only logical constructors are \top and binary \wedge. (Of course, we always have equality for terms of a 0-type as atomic formulas.)

  • regular logic: \top, binary \wedge, and \exists (plus the Frobenius rule).

  • coherent logic: \top, binary \wedge, \bot, binary \vee, and \exists (plus the distributivity and Frobenius rules).

  • geometric logic: \top, binary \wedge, \bot, arbitrary \bigvee, and \exists (plus the (infinitary) distributivity and Frobenius rules).

  • (finitary: first-order logic: \top, binary \wedge, \bot, binary \vee, \Rightarrow, \exists, and \forall.

Examples of 2-categorical theories

Firstly, any ordinary 1-categorical theory can be regarded as a 2-categorical theory with no basic 1-types, and whose basic 0-types, terms, and propositions are those of the given theory. The necessary fragment of logic will be the same. As a special case of this, any propositional theory can be regarded as a 2-categorical theory with no 1-types or 0-types.

The theory of a monoidal category

In this theory there is one basic 1-type, call it VV, and no basic 0-types or propositions. We have the following axiomatic terms:

  • i:V\vdash i:V
  • x:V,y:V(xy):Vx:V,y:V\vdash (x\otimes y):V
  • x:V,y:V,z:Vα x,y,z:hom V((xy)z,x(yz))x:V,y:V,z:V \vdash \alpha_{x,y,z}:hom_V((x\otimes y)\otimes z, x\otimes (y\otimes z))
  • x:Vλ x:hom V(ix,x)x:V \vdash \lambda_x : hom_V(i\otimes x,x)
  • x:Vρ x:hom V(xi,x)x:V \vdash \rho_x : hom_V(x\otimes i,x)
  • x:V,y:V,z:V,w:Vα x,y,zwα xy,z,w=(xα y,z,w)α x,yz,w(α x,y,zw)x:V,y:V,z:V,w:V \vdash \alpha_{x,y,z\otimes w} \circ \alpha_{x\otimes y, z,w} = (x\otimes \alpha_{y,z,w})\circ \alpha_{x,y\otimes z,w} \circ (\alpha_{x,y,z}\otimes w)
  • x:V,y:V(ρ xy)=(xλ y)α x,i,yx:V,y:V \vdash (\rho_x\otimes y) = (x\otimes \lambda_y) \circ \alpha_{x,i,y}

Note the necessary use of the functoriality term-constructors in stating the two coherence axioms. Strictly speaking, we should have stated the multiplication as x:V,y:Vmult:Vx:V,y:V\vdash mult:V, so that then aba\otimes b would be written as mult[a/x,b/y]mult[a/x,b/y], and the action of functoriality such as xα y,z,wx\otimes \alpha_{y,z,w} would be written as mult(α y,z,w/y)mult(\alpha_{y,z,w}/y).

The theory of a monad

Again there is one basic 1-type, call it AA, no basic 0-types or propositions, and the following axiomatic terms:

  • x:At(x):Ax:A \vdash t(x):A
  • x:Aη x:hom A(x,t(x))x:A \vdash \eta_x : hom_A(x,t(x))
  • x:Aμ x:hom A(t(t(x)),t(x))x:A \vdash \mu_x : hom_A(t(t(x)),t(x))
  • x:Aμ xt(η x/x)=1 t(x)x:A \vdash \mu_x \circ t(\eta_x/x) = 1_{t(x)}
  • x:Aμ xη t(x)=1 t(x)x:A \vdash \mu_x \circ \eta_{t(x)} = 1_{t(x)}
  • x:Aμ xμ t(x)=μ xt(μ x/x)x:A \vdash \mu_x \circ \mu_{t(x)} = \mu_x \circ t(\mu_x/x)

The theory of an adjunction

Here we have two basic 1-types AA and BB, no basic 0-types or propositions, and the following terms:

  • x:Af(x):Bx:A \vdash f(x):B
  • y:Bg(y):Ay:B \vdash g(y):A
  • x:Aη x:hom A(x,g(f(x)))x:A \vdash \eta_x:hom_A(x,g(f(x)))
  • y:Bε y:hom B(f(g(y)),y)y:B \vdash \varepsilon_y:hom_B(f(g(y)),y)
  • x:Aε f(x)f(η x)=1 f(x)x:A \vdash \varepsilon_{f(x)} \circ f(\eta_x) = 1_{f(x)}
  • y:Bg(ε y)η g(y)=1 g(y)y:B \vdash g(\varepsilon_{y}) \circ \eta_{g(y)} = 1_{g(y)}

However, see also the page adjunctions in 2-logic for some other equivalent ways of describing adjunctions.

Interpretation in a 2-category

One subtle point of difference with the 1-categorical theory is that propositions are always interpreted by subobjects in KK, no matter what the context. Since not every subobject of an object of a slice 2-category K/AK/A is necessarily a subobject in KK, that means that working in KK in a nonempty context Γ\Gamma is not quite the same as working in K/[Γ]K/[\Gamma] in the empty context. Other than that, things are pretty straightforward.

Let TT be a 2-categorical theory KK be a 2-category with sufficient structure to interpret TT. That means that:

  • if TT is cartesian, then KK has finite limits,
  • if TT is regular, then KK is regular,
  • if TT is coherent, then KK is coherent,
  • if TT is geometric, then KK is infinitary-coherent, and
  • if TT is finitary first-order, then KK is Heyting.

We now define the following things by mutual induction:

  • for any context Γ\Gamma, an object [Γ][\Gamma] of KK,
  • for any judgment ΓA:nType\Gamma\vdash A:n Type, a morphism [A] Γ[Γ][A]_\Gamma\to [\Gamma] which is nn-truncated, and
  • for every term Γt:A\Gamma \vdash t:A, a section of the above morphism.

Here is the definition:

  • Given [Γ][\Gamma] and the interpretation [A] Γ[Γ][A]_\Gamma\to [\Gamma], we interpret the extended context Γ,x:A\Gamma, x:A by [Γ,x:A]=[A] Γ[\Gamma,x:A] = [A]_\Gamma.
  • For each basic 1-type AA, we pick an object [A][A] of KK, and for any Γ\Gamma we set [A] Γ=[Γ]×[A][A]_\Gamma = [\Gamma] \times [A].
  • For each basic 0-type BB, we pick a discrete object [B][B] of KK, and we likewise set [B] Γ=[Γ]×[B][B]_\Gamma = [\Gamma] \times [B].
  • For each basic dependent proposition Γφ:Prop\Gamma \vdash \varphi:Prop, we pick a subobject of [Γ][\Gamma], and we set [φ] Γ=[φ][\varphi]_\Gamma = [\varphi].
  • If Γ\Gamma contains the variable x:Ax:A, then we interpret the term Γx:A\Gamma \vdash x:A via the evident projection.
  • Given terms Γx:A\Gamma\vdash x:A and Γy:A\Gamma\vdash y:A, for AA a 1-type, we therefore have two projections [x],[y]:[Γ][A][x],[y]\colon [\Gamma] \to [A], and we let [hom A(x,y)] Γ[hom_A(x,y)]_\Gamma be the inserter of [x][x] and [y][y].
  • Given terms Γx:B\Gamma\vdash x:B and Γy:B\Gamma\vdash y:B where ΓB:Set\Gamma\vdash B: Set, we let [x=y] Γ[x=y]_\Gamma be the equalizer of [x],[y]:[Γ][B] Γ[x],[y]:[\Gamma] \to [B]_\Gamma. This is sensible since [B] Γ[B]_\Gamma is discrete.
  • As a special case of the latter, given terms Γx:A\Gamma\vdash x:A and Γy:A\Gamma\vdash y:A and Γf:hom A(x,y)\Gamma\vdash f:hom_A(x,y) and Γg:hom A(x,y)\Gamma\vdash g:hom_A(x,y) for AA a 1-type, and therefore having two projections [x],[y]:[Γ][A][x],[y]:[\Gamma] \to [A] and two 2-cells [f],[g]:[x][y][f],[g]\colon [x]\to [y], we let [f=g] Γ[f=g]_\Gamma be the equifier of [f][f] and [g][g].
  • For each basic term Γt:A\Gamma \vdash t:A, we pick a section of [A] Γ[Γ][A]_\Gamma \to [\Gamma].
  • We let [] Γ=[Γ][Γ][\top]_\Gamma = [\Gamma] \to [\Gamma], of course, and [φψ] Γ=[φ] Γ[ψ] Γ[\varphi\wedge \psi]_\Gamma = [\varphi]_\Gamma \cap [\psi]_\Gamma (intersection as subobjects of [Γ][\Gamma].
  • If KK is coherent, we let [] Γ[\bot]_\Gamma be the initial object, and [φψ] Γ=[φ] Γ[ψ] Γ[\varphi\vee \psi]_\Gamma = [\varphi]_\Gamma \cup [\psi]_\Gamma (union as subobjects of [Γ][\Gamma]. Similarly for \bigvee if KK is infinitary-coherent.
  • If KK is regular, given Γ,x:Aφ(x)\Gamma, x:A \vdash \varphi(x) with [φ] Γ,x:A[Γ,x:A][Γ][\varphi]_{\Gamma, x:A} \hookrightarrow [\Gamma, x:A] \to [\Gamma], we let [(x:A)φ(x)] Γ[Γ][(\exists x:A)\varphi(x)]_\Gamma \hookrightarrow [\Gamma] be the image of [φ] Γ,x:A[\varphi]_{\Gamma, x:A} along the projection [Γ,x:A][Γ][\Gamma, x:A] \to [\Gamma].
  • Finally, if KK is Heyting, given Γ,x:Aφ(x)\Gamma, x:A \vdash \varphi(x) with [φ] Γ,x:A[Γ,x:A][Γ][\varphi]_{\Gamma, x:A} \hookrightarrow [\Gamma, x:A] \to [\Gamma], we let [(x:A)φ(x)] Γ[Γ][(\forall x:A)\varphi(x)]_\Gamma \hookrightarrow [\Gamma] be the dual image of [φ] Γ,x:A[\varphi]_{\Gamma, x:A} along the projection [Γ,x:A][Γ][\Gamma, x:A] \to [\Gamma].
Theorem

This interpretation is sound. In other words, the induction succeeds, and all the rules for term-formation (including all the logical rules) can be interpreted.

Of course, the definition of the interpretation depends on our choosing interpretations of the basic types and terms. For example:

  • A model in KK of the theory of a monoidal category is precisely a pseudomonoid in KK.
  • Of course, a model in KK of the theory of a monad, or an adjunction, is precisely a monad or adjunction in KK.
  • If TT is a 1-categorical theory, then a model of TT (regarded as a 2-categorical theory) in KK is precisely a model of the original theory TT in the category of discrete objects in KK.
  • Similarly, if TT is a propositional theory, then a model of TT in KK lives in the poset of subterminal objects.

The internal theory of a 2-category

Any 2-category KK comes with a “canonical” theory associated to it, which has a canonical model in KK. In this theory:

  • the basic 1-types are all the objects of KK, with interpretation the identity.
  • the basic 0-types are all the discrete objects of KK, with interpretation the identity.
  • the basic dependent propositions in a context Γ\Gamma, are all the subobjects of [Γ][\Gamma] in KK.
  • the basic terms of a type AA in context Γ\Gamma are all the sections in KK of the morphism [A] Γ[Γ][A]_\Gamma \to [\Gamma].

Of course, this definition is again inductive, so one has to prove that the induction succeeds. Usually when we refer to the internal logic of a 2-category it is this logic we are talking about. Of course, whatever logical structure KK has (regular, coherent, etc.) can be reflected in its internal logic.

Classifying discrete opfibrations

Definition

As in WeberYS2T, a classifying discrete opfibration in a finitely complete 2-category KK is a discrete opfibration p:ESp:E\to S such that for any XX, the functor

K(X,S)DOpf(X), K(X,S) \to DOpf(X),

given by pullback of pp, is full and faithful.

The canonical example is when KK is some 2-category of “large categories” and SS is the category of (small) sets. More generally, we could take KK to be the 2-category CatCat and SS the category of sets of cardinality bounded by some cardinal λ\lambda.

When KK is equipped with a classifying discrete opfibration, we make the following definitions.

  • A discrete opfibration is small if it is in the image of the above functor.
  • A discrete object XX is small if X1X\to 1 is a small discrete opfibration.
  • If KK has a duality involution, we say an object AA is locally small or arrow-small if the discrete opfibration XA×A opX\to A\times A^{\op} corresponding to the 2-sided fibration AA 2AA \leftarrow A ^{\mathbf{2}} \to A is small.
  • A not-necessarily-discrete object AA is small if it is locally small and admits an eso from a small discrete object.

If KK lacks a duality involution, then merely giving the discrete opfibration ESE\to S doesn’t suffice to characterize the notion of “smallness,” since we can’t define what it means to be locally small. This suggests the definition of a size structure.

Additional axioms

We may impose additional axiom on a classifying discrete opfibration, many of which assert closure conditions of the class of small maps.

  • Identity maps are small.
  • The composite of small discrete opfibrations is small (the “axiom of replacement”).
  • All cosieves are small (the “axiom of separation”).
  • If qrq r and qq are small discrete opfibrations, then so is rr (“full slices”).
  • If qq is a discrete opfibration, qrq r is a small discrete opfibration and rr is eso, then qq is a small discrete opfibration (“quotients”).
  • If qq is a discrete opfibration whose pullback along an eso is a small discrete opfibration, then qq is small (“descent”).
  • The map p:ESp\colon E\to S is exponentiable.

Some immediate consequences are:

  • If identity maps are small, then each category K(X,S)K(X,S) has a natural terminal object, and so SS “has a terminal object” internally, i.e. S1S\to 1 has a right adjoint.
  • If small discrete opfibrations are closed under composition, then if YXY\to X and ZXZ\to X are small discrete opfibrations, so is Y× XZYY\times_X Z \to Y, and thus so is the composite Y× XZXY\times_X Z\to X. Hence K(X,S)K(X,S) has binary products naturally, and thus SS “has binary products” internally, i.e. the diagonal SS×SS\to S\times S has a right adjoint.
  • In particular, if small discrete opfibrations form a subcategory, then SS is a cartesian object.
  • One can also show that the “axiom of replacement” implies that any small object is the quotient of an internal category (2-congruence) in sm(disc(K))sm(disc(K)), the category of small discrete objects.

We will see some further consequences of these axioms below.

The universal map as a comma object

Theorem

Suppose that p:ESp\colon E\to S is a classifying discrete opfibration for which identity maps are small. Then there is a comma square

E 1 p 1 S id S\array{E & \overset{}{\to} & 1\\ ^p\downarrow &\Downarrow& \downarrow^1\\ S & \underset{id}{\to} & S}

in which the map 1S1\to S classifies the discrete opfibration id 1:11id_1\colon 1\to 1.

Proof

A map XEX\to E is the same as a discrete opfibration q:YXq\colon Y\to X equipped with a section s:XYs\colon X\to Y with ps1p s \cong 1. Thus, it suffices to show that giving such data is equivalent to giving a square

X 1 S id S\array{X & \overset{}{\to} & 1\\ \downarrow & \Downarrow& \downarrow\\ S & \underset{id}{\to} & S}

in which the left-hand vertical map XSX\to S classifies qq. But the composite X1SX\to 1 \to S classifies id:XXid\colon X\to X, so since pullback of pp is full and faithful into discrete opfibrations, giving such a 2-cell is the same as giving a map idqid \to q of discrete opfibrations over XX, which is precisely to give a section of qq.

Families

Suppose that p:ESp\colon E\to S is a CDO which is exponentiable. Then for any object AA, we call the exponential

Fam(A)(S×AS) (ES) Fam(A) \coloneqq (S\times A \to S)^{(E\to S)}

the object of (small) families in AA. It comes with a projection to SS which “assigns to each family its indexing set.” Moreover, as observed in our study of exponentials, since pp is an opfibration and S×ASS\times A\to S is a fibration, then Fam(A)SFam(A)\to S is also a fibration, as we would expect.

Fam(A)Fam(A) has a universal property that can be directly expressed as follows. Evidently, to give a morphism XFam(A)X\to Fam(A) is equivalent to giving a map XSX\to S together with a map X× SES×AX\times_S E \to S\times A over SS. But X× SEX\times_S E is simply the discrete opfibration classified by XSX\to S, and a map to S×AS\times A over SS is just an arbitrary map to AA. Thus to give a map XFam(A)X\to Fam(A) is the same as to give a small discrete opfibration YXY\to X together with a map YAY\to A: in other words, an XX-indexed family of small sets, each of which indexes a family of objects of AA.

(This sort of thing is closely related to the construction of generic families in Algebraic Set Theory.)

Families of sets as a codomain fibration

Now consider the special case when A=SA=S. As above, to give a map XFam(S)X\to Fam(S) is to give a small discrete opfibration YXY\to X and a map YSY\to S. But a map YSY\to S is in turn equivalent to a small discrete opfibration ZYZ\to Y. Thus K(X,Fam(S))K(X,Fam(S)) is naturally equivalent the category of composable pairs ZYXZ\to Y\to X of small discrete opfibrations. Recalling that any map between discrete opfibrations over XX is again a discrete opfibration, we observe that the 1-category DOpf(K/X) 2DOpf(K/X)^{\mathbf{2}} consists of composable pairs ZYXZ\to Y\to X of discrete opfibrations; thus K(X,Fam(S))K(X,Fam(S)) is naturally a full subcategory of this category.

On the other hand, we can consider another full subcategory of DOpf(K/X) 2DOpf(K/X)^{\mathbf{2}} determined by those composable pairs ZYXZ\to Y\to X in which YXY\to X and the composite ZXZ\to X are small. This is precisely the subcategory SDOpf(K/X) 2SDOpf(K/X)^{\mathbf{2}}, where SDOpf(K/X)SDOpf(K/X) consists of small discrete opfibrations, and is thus equivalent to K(X,S)K(X,S). It follows that this second full subcategory of DOpf(K/X) 2DOpf(K/X)^{\mathbf{2}} is equivalent to K(X,S 2)K(X,S^{\mathbf{2}}). Clearly these two subcategories agree if and only if small discrete opfibrations are closed under composition and have full slices, in the terminology defined above. Thus we have proven:

Theorem

Let p:ESp\colon E\to S be an exponentiable classifying discrete opfibration; the following are equivalent.

  1. Small discrete opfibrations are closed under composition and have full slices.
  2. For each XX, the categories K(X,Fam(S))K(X,Fam(S)) and K(X,S 2)K(X,S^{\mathbf{2}}) are equivalent as full subcategories of DOpf(K/X) 2DOpf(K/X)^{\mathbf{2}}.

When these conditions hold, we clearly have a natural equivalence K(X,Fam(S))K(X,S 2)K(X,Fam(S))\simeq K(X,S^{\mathbf{2}}) lying over K(X,S)K(X,S), and therefore, by the Yoneda lemma, an equivalence over SS between Fam(S)SFam(S)\to S and the codomain fibration S 2SS^{\mathbf{2}}\to S.

(Note the slight peculiarity of this result: it is more common, when showing that two things are equivalent under certain conditions, to construct a canonical map between them which always exists and happens to be an equivalence in the cases of interest. Here instead we have constructed a canonical cospan which induces an equivalence in the cases of interest.)

Colloquially speaking, this theorem says that the category SS of sets satisfies the “replacement axiom” if and only if the “naive indexing” Fam(S)Fam(S) of SS over itself is equivalent to its “self-indexing” S 2S^{\mathbf{2}}. In classical material set theory, this is well-known to be equivalent to the usual axiom of replacement.

Note, though, that depending on what KK is, Fam(S)Fam(S) may not be the “naive indexing” at all. For instance, if KK is the category of stacks on a topos EE, then the self-indexing of EE is a classifying discrete opfibration in KK, which always satisfies the “axiom of replacement,” essentially by construction. Analogous facts are well-known in algebraic set theory, and are one reason why “the axiom of replacement” is a bit slippery in structural set theory. Generally, in intuitionistic logic, the axioms of replacement and collection add no extra proof-theoretic strength because they can be made to hold internally in suitable (2-)topoi of sheaves/stacks; it is the axiom of separation which carries all the power distinguishing IZF from IETCS.

Constructing familiar categories

Given a classifying discrete opfibration, we can use finite 2-categorical limits and the “internal logic” to construct all the usual concrete categories out of the object SS. For instance, if small discrete opfibrations are a subcategory, so that SS is a cartesian object, then we have the composite SS×SSS \to S\times S \to S of the diagonal with the “binary products” morphism which, intuitively, takes a set AA to the set A×AA\times A. Now the inserter of this composite and id Sid_S can be considered “the category of sets AA equipped with a function A×AAA\times A\to A,” i.e. the category of magmas.

Now we have a forgetful morphism magmasetmagma\to set, and also a functor magmasetmagma \to set which takes a magma to the triple product A×A×AA\times A\times A, and there are two 2-cells relating these constructed from two different composites of the inserter 2-cell defining the category of magmas. It makes sense to call the equifier of these 2-cells “the category of semigroups” (sets with an associative binary operation). Proceeding in this way we can construct the categories of monoids, groups, abelian groups, and eventually rings.

A more direct way to describe these categories with a universal property is as follows. Since SS is a cartesian object, each hom-category K(X,S)K(X,S) has finite products, so we can define the category ring(K(X,S))ring(K(X,S)) of rings internal to it. Then the category ringring is equipped with a forgetful functor ringsetring\to set which has the structure of a ring in K(ring,set)K(ring,set), and which is universal in the sense that we have a natural equivalence ring(K(X,S))K(X,ring)ring(K(X,S))\simeq K(X,ring). The above construction then just shows that such a representing object exists.

Preservation

If KK has a duality involution and p:ESp:E\to S is a classifying discrete opfibration, then p o:E oS op^o:E^o\to S^o is a “classifying discrete fibration,” and therefore also a classifying discrete opfibration in K coK^{co}.

A classifying discrete opfibration in KK is not inherited by any category of truncated objects in KK, since EE and SS will generally not be truncated. However, it is inherited by (op)fibrational slices.

Recall first that opfibrations in Opf(X)Opf(X) can be identified with morphisms in Opf(X)Opf(X) whose underlying morphism in KK is an opfibration. Moreover, such an opfibration is discrete if and only if its underlying morphism in KK is so. Thus, it is natural to hope for the following.

Theorem

If KK has exponentials and a classifying discrete opfibration, then each 2-category Opf K(X)Opf_K(X) has a classifying discrete opfibration, and the small opfibrations in Opf(X)Opf(X) are those whose underlying opfibrations in KK are small.

Proof

Recall that when KK has exponentials, Opf(X)Opf(X) is comonadic over K/XK/X; let G XG_X denote the comonad. For any AA, write SOpf(A)SOpf(A) for the category of small discrete opfibrations over AA. Then our goal is for SOpf Opf(X)(AX):=SOpf(A)SOpf_{Opf(X)}(A\to X) := SOpf(A) to be representable. But we have

SOpf(A)K(A,S)K(Σ X(AX),S)K/X(A,X×S)Opf(X)(A,G X(X×S)).SOpf(A) \simeq K(A,S) \simeq K(\Sigma_X (A\to X), S) \simeq K/X(A, X\times S) \simeq Opf(X)(A,G_X(X\times S)).

Therefore, defining S X=G X(X×SX)S_X = G_X(X\times S\to X) we obtain a classifying discrete opfibration in Opf(X)Opf(X) that classifies the desired small opfibrations.

Corollary

If KK has exponentials, a duality involution, and a classifying discrete opfibration, then each 2-category Fib K(X)Fib_K(X) also has a classifying discrete opfibration.

Proof

This follows from Theorem since Fib(X)Opf(X o)Fib(X) \simeq Opf(X^o). The classifying object is explicitly given by V X(G X o(X o×SX o))V_X(G_{X^o}(X^o\times S\to X^o)), although the small maps are not as explicitly characterized.

Classifying cosieves

A cosieve is a morphism AXA\to X in a 2-category that is both ff and a discrete opfibration. Equivalently, it is a subterminal object in Opf(X)Opf(X). It is easy to check that in CatCat, this is equivalent to saying that AA is a full subcategory of XX such that if aAa\in A and f:abf:a\to b, then bAb\in A.

A classifying cosieve is a classifying discrete opfibration which is a cosieve—and hence classifies only cosieves, since cosieves are stable under pullback. We write ζΩ\zeta\to \Omega for a classifying cosieve. Clearly any such Ω\Omega is posetal.

A cosieve classifier is a classifying cosieve which classifies all cosieves. In this case one can show, just as for the subobject classifier in a topos, that ζ=1\zeta=1. In CatCat, the “walking arrow” 2\mathbf{2} is a cosieve classifier.

Construction from classifying discrete opfibrations

If ESE\to S is any classifying discrete opfibration in a Heyting 2-pretopos KK, then the subobject of SS described in the internal logic by

{x:S|(a:E(x))(b:E(x))(f:hom E(a,b))}\{x:S | (\forall a:E(x))(\forall b:E(x))(\exists f:hom_E(a,b))\top \}

is the largest subobject ΩS\Omega\hookrightarrow S such that the pullback of EE to Ω\Omega is a cosieve. (Verifying this is a straightforward argument using the Kripke-Joyal semantics?.) It is thus a classifying cosieve, which is canonically associated to ESE\to S.

In CatCat, the cosieve classifier 2\mathbf{2} arises from SetSet (or any full subcategory of it containing 00 and 11) in this way.

From cosieve classifiers to subobject classifiers

If XX is groupoidal, then every ff into XX is a cosieve. Therefore, maps from a groupoidal XX into a cosieve classifier Ω\Omega classify all subobjects of XX. Since subobjects of XX are the same as subobjects of its core J(X)J(X) if that exists, subobjects of XX can be classified by maps J(X)ΩJ(X) \to \Omega.

Moreover, if a cosieve classifier Ω\Omega itself has a core, then since J(Ω)J(\Omega) is a coreflection of Ω\Omega into gpd(K)gpd(K), it is a subobject classifier in gpd(K)gpd(K) in a suitable (2,1)-categorical sense. Moreover, since Ω\Omega is posetal, its core (if it exists) is discrete. Thus:

Theorem

If KK is a 2-category having a cosieve classifier and enough groupoids, then disc(K)disc(K) has a subobject classifier.

In particular, if KK also has (discrete) exponentials, then disc(K)disc(K) is a topos.

However, disc(K)disc(K) can have both a subobject classifier and a cosieve classifier without the former being a core of the latter. For instance, in the 2-presheaf 2-topos K=[C,Cat]K=[C,Cat], the category disc(K)disc(K) is the 1-topos of 1-sheaves on the homwise-discrete reflection of CC, but there will not in general be a map in either direction relating its subobject classifier to the cosieve classifier.

A subobject classifier can also be constructed from a cosieve classifier in a Heyting 2-category with a duality involution. For then if Ω\Omega is a cosieve classifier, Ω o\Omega^o is a sieve opclassifier, i.e. K(X,Ω o)K(X,\Omega^o) is equivalent to the opposite of the poset of sieves on XX. On Ω×Ω o\Omega\times\Omega^o we thus have both a sieve RR and a cosieve SS, pulled back from Ω\Omega and Ω o\Omega^o; let Ω d\Omega_d be the subobject of Ω×Ω o\Omega\times\Omega^o defined as RSR\Leftrightarrow S in the Heyting algebra structure. Now maps into Ω d\Omega_d classify sieves and cosieves that are equal as subobjects, which is to say, subobjects that are both sieves and cosieves. And transformations between maps XΩ dX\to \Omega_d correspond to both inclusions of cosieves and coinclusions of sieves, which is to say, identities; thus Ω d\Omega_d is discrete, and hence a subobject classifier in disc(K)disc(K).

Theorem

If KK is a Heyting 2-category having a cosieve classifier and a duality involution, then disc(K)disc(K) has a subobject classifier.

Replacing subobject classifiers

If KK has a cosieve classifier and (discrete) exponentials, but not enough groupoids, then disc(K)disc(K) may not be a topos. But it retains many of the properties of a topos, because even though the “power object” PX=Ω XP X = \Omega^X is not an object of disc(K)disc(K), it can still be quantified over in the internal logic of KK to define objects and properties in disc(K)disc(K), and even in gpd(K)gpd(K), where all subobjects are cosieves.

For example, if KK is also Heyting, then for any groupoidal XX we can construct the “internally least” subobject of XX with some property, as

{x:X|(S:PX)(φ(S)xS)}.\{x:X | (\forall S:P X)(\varphi(S) \Rightarrow x\in S)\}.

This allows the construction of all sorts of “closure” operations that exist in a topos, such as the equivalence relation generated by any given relation on a groupoidal object. In particular:

Proposition

If KK is 1-exact and Heyting with exponentials and a cosieve classifier, then disc(K)disc(K) is finitely cocomplete.

If XX is not groupoidal, then the above technique only constructs cosieves in XX rather than arbitrary subobjects of it. However, if there are enough groupoids, we can construct arbitrary subobjects of any object XX in this way, since subobjects of XX are bijective with subobjects of its core J(X)J(X). In particular:

Proposition

If KK is 1-exact and Heyting with exponentials, a cosieve classifier, and either enough groupoids or a duality involution, then it has discrete reflections.

Proof

It suffices to be able to construct the equivalence relation generated by the image of A 2A×AA ^{\mathbf{2}} \to A\times A, for any AA. Note that these relations are not cosieves on A×AA\times A, but as remarked above, we can get around this if A×AA\times A has a core. Alternately, since the relations we care about are all “2-sided sieves” (subterminals in Fib(A,A)Fib(A,A)), if there is a duality involution we can turn them into cosieves on A op×AA^{op}\times A and perform the closure there.

In another vein, if KK is a positive Heyting 2-category with a (necessarily discrete) natural numbers object NN, we can of course construct the discrete object of rational numbers QQ in the usual way, and then define the Dedekind real numbers as two-sided cuts. Thus, RR is a subobject of PQ×PQP Q \times P Q, and hence posetal, but since the order relation on RR inherited from the two copies of PQP Q would go in different directions, in fact RR is discrete.

I haven’t made a concerted effort yet, but I haven’t yet thought of any really important aspect of topos-ness for disc(K)disc(K) that isn’t almost as well-served by having a posetal power-object rather than a discrete one. Mathieu Dupont was the one who originally pointed out to me that 2-categorically, power-objects are naturally posets rather than sets.

Created on January 22, 2010 at 19:52:35. See the history of this page for a list of all contributions to it.