codiscrete cofibration



A 2-category is a good context for doing a lot of category theory (including internal category theory, enriched category theory, and so on), but there are some things that are hard to do there, such as to talk about weighted limits and colimits. This leads one to introduce the notion of a 2-category equipped with proarrows, which is a 2-category along with extra data that plays the role of profunctors, allowing the definition of weighted limits and other aspects of category theory.

However, it would also be nice if the extra data in a proarrow equipment were somehow determined by the 2-category we started with. This is especially so when talking about functors between equipments, since functors between 2-categories are often easier to construct. It turns out that in many cases, including the most common ones, this is the case: we can construct the proarrows in terms of the underlying 2-category. This was originally realized by Ross Street.

The idea is to identify a profunctor with its collage, aka its cograph, which is a special sort of cospan in CatCat (or VCatV Cat, or whatever other 2-category one wants to start with). One then simply has to characterize, in 2-categorical terms, which cospans are collages, and how to do things like compose them. It turns out that in most cases the characterization is precisely that they are the two-sided codiscrete cofibrations — i.e. the two-sided discrete fibrations in the opposite 2-category.


Suppose that KK is a 2-category with finite 2-colimits, and A,CKA,C\in K. A cofibration from AA to CC is a cospan ABCA\to B \leftarrow C which is an internal two-sided fibration in K opK^{op}. As remarked at fibration in a 2-category, there is a 2-monad on Span K op(A,C)Span_{K^{op}}(A,C) whose algebras are such fibrations. In other words, there is a 2-comonad on Cospan K(A,C)Cospan_K(A,C) whose coalgebras are such fibrations. This 2-comonad is defined by

(ABC)(A(A×I)+ AB+ C(C×I)C) (A\to B \leftarrow C) \quad \mapsto\quad (A \to (A\times I) +_A B +_C (C\times I) \leftarrow C)

where II is the interval category (01)(0\to 1) and (×I)(-\times I) denotes the copower with II. In the pushouts, the map AA×IA\to A\times I is the inclusion at 00 and CC×IC\to C\times I is the inclusion at 11.

A cospan ABCA\to B \leftarrow C in a 2-category KK is codiscrete if it is codiscrete in the 2-category Cospan K(A,C)(A+C)/KCospan_K(A,C)\simeq (A+C)/K. This means that for any XCospan(A,C)X\in Cospan(A,C), the hom-category Cospan(A,C)(B,X)Cospan(A,C)(B,X) is equivalent to a discrete category. Explicitly, it means that given any two morphisms BXB \;\rightrightarrows\; X of cospans, if there exists a 2-cell from one to the other in Cospan(A,C)Cospan(A,C), then it is unique and invertible.

A codiscrete cofibration is a two-sided cofibration which is codiscrete as a cospan.


Enriched categories

We sketch a characterization of cofibrations in VCatV Cat, where VV is any Bénabou cosmos. Let AfBgCA\overset{f}{\to} B \overset{g}{\leftarrow} C be a cospan and let D=(A×I)+ AB+ C(C×I)D = (A\times I) +_A B +_C (C\times I). We claim that DD has the following description.

That DD is a VV-category is immediate, and it is easy to check the universal property. We write AiDjCA \overset{i}{\to} D \overset{j}{\leftarrow} C for the inclusions.

Now suppose that BB is a coalgebra for the 2-comonad in question. Therefore, in particular we have a map h:BDh\colon B\to D in Cospan(A,C)Cospan(A,C), so that hf=ih f = i and hg=jh g = j (or perhaps only isomorphic; it really makes no difference here). Moreover, the counit of the comonad is the obvious map k:DBk\colon D\to B, so we must have kh=1 Bk h = 1_B.

Since ii and jj are injective on objects and have disjoint images, so must be ff and gg. And since ii and jj are fully faithful VV-functors, the action of ff and gg on homs must be split monic in VV, and the action of hh on homs in AA and BB must be split epic. But since hk=1 Bh k = 1_B, the action of hh on homs must also be split monic, hence an isomorphism, and hence so must that of ff and gg be. Therefore, ff and gg are fully faithful inclusions with disjoint images.

Clearly hh must take the images of ff and gg to the images of ii and jj, respectively. Because kh=1 Bk h = 1_B, it must be that hh takes the rest of BB to itself, sitting in the canonical copy of BB inside DD. This uniquely defines hh, as long as BB satisfies the condition that

It is then easy to check that if ff and gg are fully faithful with disjoint images and this condition holds, then BB is in fact a coalgebra for the comonad in question, i.e. a two-sided cofibration from AA to CC.

Note that such a cofibration from AA to CC can be identified with the following data: a category B=B(AC)B' = B\setminus (A\cup C), profunctors m:ABm\colon A ⇸ B, n:BCn\colon B ⇸ C, and p:ACp\colon A ⇸ C, and a morphism nmpn m \to p of profunctors. Such a thing is sometimes called a gamut from AA to CC.

Now a 2-cell in Cospan(A,C)Cospan(A,C) is simply a natural transformation between functors BXB \;\rightrightarrows\; X whose components on the images of AA and CC are isomorphisms. Thus, if BB is a cofibration as above with the property that B(AC)B \setminus (A\cup C) is empty, then it must be codiscrete. The converse is easy to check, taking XX to be the ordinal 4=(0123)4 = (0\le 1 \le 2\le 3) as a category. But a gamut with B=B'=\emptyset is nothing but a profunctor ACA ⇸C; hence codiscrete cofibrations in VCatV Cat can be precisely identified with the collages of profunctors.


A codiscrete cofibration in the 2-category TopoiTopoi of topoi can be identified with a left exact functor.

Double categories

Codiscrete cofibrations in the 2-category DblDbl of double categories, double functors, and horizontal transformations can be identified with double profunctors.

Construction of a proarrow equipment

The examples of profunctors suggest that given any 2-category KK with finite 2-colimits, we may try to canonically equip it with proarrows by defining the proarrows ACA ⇸C to be the codiscrete cofibrations. The sticky point is then how to define units and composition of such proarrows in order to obtain an equipment.

The unit is obvious: we should take the unit proarrow of AA to be the cospan AA×IAA\to A\times I \leftarrow A, which is always a codiscrete cofibration.

Binary composition is subtler. The obvious way to compose codiscrete cofibrations ABCA \to B \leftarrow C and CDEC\to D \leftarrow E, of course, is to take a pushout B+ CDB +_C D. It is not hard to show (see references):


In any 2-category with finite 2-colimits, if BB and DD are cofibrations, then so is B+ CDB +_C D.

However, B+ CDB +_C D will not be codiscrete even if BB and DD are. In VCatV Cat, if BB and DD are collages of profunctors mm and nn, then B+ CDB +_C D represents the gamut consisting of mm, nn, and the composite profunctor nmn m, with the middle category being CC. Thus, in order to obtain the correct composite, we need to forget about CC somehow. The best way to do this seems to be using a factorization system in a 2-category, akin the way in which we construct the bicategory of relations from any regular category.

Equippable 2-categories

We are looking for a 2-categorical factorization system (,)(\mathcal{E},\mathcal{M}) in KK such that if we have a two-sided cofibration ACBA\to C\leftarrow B and we factor A+BCA+B \to C into an \mathcal{E}-map and an \mathcal{M}-map, then the resulting cospan AEBA\to E \leftarrow B is a codiscrete cofibration. Codiscreteness means in particular that the \mathcal{E}-map A+BEA+B\to E should be codiscrete, i.e. representably cofaithful and co-conservative. Moreover, if ACBA\to C\leftarrow B was already a codiscrete cofibration, then A+BCA+B\to C should already be in \mathcal{E}. This suggests the following definition.


A 2-category with finite 2-limits and 2-colimits is pre-equippable if it has a factorization system (,)(\mathcal{E},\mathcal{M}) such that

  • if ACBA\to C \leftarrow B is a codiscrete cofibration, then A+BCA+B \to C is in \mathcal{E}, and
  • every morphism in \mathcal{E} is representably co-faithful and co-conservative.

It is equippable if in addition it satisfies:

  • Morphisms in \mathcal{M} are closed under pushout and tensors with II.

Co-conservative morphisms are also called liberal. Recall that by definition of codiscreteness, if ACBA\to C \leftarrow B is a codiscrete cofibration, then A+BCA+B\to C is cofaithful and liberal; thus the first two conditions are compatible.

The example to keep in mind is VCatV Cat, for any suitable VV, where \mathcal{E} is the class of essentially surjective VV-functors and \mathcal{M} is the class of VV-fully-faithful functors.


Any morphism which is right orthogonal to codiscrete cofibrations is representably fully faithful. In particular, if KK is pre-equippable, then every morphism in \mathcal{M} is representably fully faithful.


For any XX in KK, we have a codiscrete cofibration XX×IXX\to X \times I \leftarrow X, and thus X+XX×IX+X \to X\times I is in \mathcal{E}. But orthogonality with respect to all such morphisms is precisely representable fully-faithfulness.


Any representably fully faithful morphism is right orthogonal to any cocomma object?. In particular, KK is pre-equippable and every codiscrete cofibration is a cocomma object, then \mathcal{M} is precisely the class of representably fully faithful morphisms.


Maps out of a cocomma object are in canonical correspondence with 2-cells in KK. But representable fully-faithfulness means that 2-cells lift uniquely along such a map. Hence so do maps out of a cocomma object, and hence any representably fully faithful map is right orthogonal to all cocomma cospans.


If KK is pre-equippable, then any inverter or equifier is in \mathcal{M}, and every morphism in \mathcal{E} is cofaithful and liberal.


Any inverter is always right orthogonal to any liberal morphism, and any equifier is always right orthogonal to any cofaithful morphism.

The construction

In an equippable 2-category, we can compose cofibrations in the desired way.


If KK is equippable, AEBA\to E \leftarrow B is a two-sided cofibration, and A+BFEA+B \to F \to E is an (,)(\mathcal{E},\mathcal{M})-factorization, then AFBA\to F \leftarrow B is a codiscrete cofibration. In particular, the category CodCofib(A,B)CodCofib(A,B) is coreflective in the 2-category Cofib(A,B)Cofib(A,B).


Since \mathcal{E}-morphisms are cofaithful and liberal, AFBA\to F \leftarrow B is certainly codiscrete. That it is a cofibration is proven as in (MB, 4.18). Coreflectivity follows by orthogonality for the factorization system (,)(\mathcal{E},\mathcal{M}), since all codiscrete cofibrations are in \mathcal{E} by assumption.

Therefore, in an equippable 2-category, we can define the composite of codiscrete cofibrations ABCA\to B\leftarrow C and CDEC\to D\leftarrow E to be the codiscrete coreflection of the cofibration AB+ CDEA \to B +_C D\leftarrow E.


If KK is equippable, there is a 2-category CodCofib(K)CodCofib(K), with the same objects as KK, and with codiscrete cofibrations as 1-morphisms. Moreover, there is a locally fully faithful identity-on-objects (pseudo) 2-functor () *KCodCofib(K)(-)_* K\to CodCofib(K) such that each 1-morphism f *f_* has a right adjoint. Therefore, KK is canonically a 2-category equipped with proarrows (hence the term “equippable”).


This is essentially (MB, 4.20).

One can then impose additional axioms on KK to get good behavior of this equipment, and try to characterize the equipments arising in this way; see (MB, section 5) and (PC).

Canonical factorization systems

Note that since coreflections are determined by a universal property, the composite of codiscrete cofibrations is independent of the chosen factorization system (,)(\mathcal{E},\mathcal{M}). In fact, there are two different “extreme” ways that we might try to define an equippable factorization system; we could either

  1. Define \mathcal{E} to be the class of liberal and cofaithful morphisms, or
  2. Define \mathcal{E} to be generated by the class of codiscrete cofibrations.

In the second case we mean that \mathcal{M} is the class of all morphisms right orthogonal to the morphisms A+BCA+B\to C such that ACBA\to C \leftarrow B is a codiscrete cofibration, and then \mathcal{E} is the class of all morphisms left orthogonal to \mathcal{M}. This implies, of course, that \mathcal{E} contains the codiscrete cofibrations.

Neither of the above choices is guaranteed to produce a factorization system (since the factorizations may not exist), but if either one does, then that factorization system is automatically pre-equippable. In the first case this is obvious, since all codiscrete cofibrations are cofaithful and liberal, while in the second case, it follows since inverters and equifiers are then necessarily in \mathcal{M}, and anything left orthogonal to inverters and equifiers must be cofaithful and liberal. Thus, a 2-category is equippable if either of these two choices produces a factorization system for which \mathcal{M} is closed under pushout and tensors with II.


The (essentially surjective, VV-fully faithful) factorization system is generated by the codiscrete cofibrations, and is equippable.


It suffices to show that a VV-functor f:ABf\colon A\to B is right orthogonal to codiscrete cofibrations if and only if it is VV-fully faithful, i.e. each morphism A(a,a)B(fa,fa)A(a,a') \to B(f a, f a') is an isomorphism in VV. For “if”, it suffices to observe that VV-fully faithful functors are right orthogonal to all essentially surjective ones, and any codiscrete cofibration is essentially surjective. For “only if,” suppose given a,aAa,a'\in A, let X=Y=IX=Y=I be the unit VV-category, consider the object B(fa,fa)VB(f a,f a')\in V as a VV-profunctor XYX \to Y, and let EE be its collage. Then we have a square

XY [a,a] A E [fa,fa] B\array{X\sqcup Y & \overset{[a,a']}{\to} & A\\ \downarrow && \downarrow\\ E & \underset{[f a, f a']}{\to} & B}

where the bottom arrow is the identity on the nontrivial hom-object B(fa,fa)B(f a,f a'). A lifting in this square supplies a section of A(a,a)B(fa,fa)A(a,a') \to B(f a, f a'), and uniqueness of lifting against the collage of A(a,a)A(a,a') (also as a profunctor III\to I) shows that it is an inverse isomorphism; hence ff is VV-fully faithful.

Finally, it is straightforward to verify that VV-fully-faithful functors are closed under pushout and tensors with II.


In VCatV Cat, every liberal is automatically cofaithful, and there is a pre-equippable factorization system in which \mathcal{E} is the class of liberal morphisms. However, it is not equippable, even when V=SetV=Set.


This is essentially (MB, 3.4). In this case \mathcal{M} consists of the VV-fully faithful morphisms which are additionally closed under absolute colimits, while \mathcal{E} consists of the functors which are surjective up to absolute colimits (“Cauchy dense” functors). When V=SetV=Set, all absolute colimits are generated by retracts, and it is easy to construct an example of a fully faithful functor closed under retracts and a pushout of it which is no longer closed under retracts.

An equippable 2-category with =\mathcal{E} = liberal cofaithfuls = liberals is called faithfully co-conservational in (MB). This is the only case considered there, but the proofs generalize directly to any equippable 2-category. Note that VCatV Cat is not faithfully co-conservational, since the above factorization system is only pre-equippable: \mathcal{M} is not closed under pushout. Its sub-2-category VCat ccV Cat_{cc} of Cauchy complete VV-categories is faithfully co-conservational, but this is arguably just because when restricted to VCat ccV Cat_{cc}, the above factorization coincides with the other, better one. Thus, it seems that perhaps in general it is better to consider the factorization system generated by the codiscrete cofibrations.