Todd Trimble
Small cocompletions

Contents

Introduction

For CC a small category, it is well-known (and fundamental) that the presheaf category Set C opSet^{C^{op}} is the free cocompletion of CC with respect to small colimits. Analogously, if VV is a complete and cocomplete symmetric monoidal closed category and CC is a small VV-enriched category, the enriched presheaf category V C opV^{C^{op}} is the free (co)completion of CC with respect to VV-colimits.

If CC is merely locally small (or merely takes homs in VV as above), the presheaf category may be too large to be a free small-colimit cocompletion. Nevertheless, the small-colimit cocompletion of CC exists, as the full subcategory of Set C opSet^{C^{op}} consisting of functors C opSetC^{op} \to Set that are small colimits of representables.

However, this cocompletion (which we denote by Colim(C)Colim(C)) typically does not have the properties one associates with presheaf toposes; for example, Colim(C)Colim(C) might not even be complete, or might not even have a terminal object. But Colim(C)Colim(C) may inherit some good properties from CC if CC has them. While it is rare for Colim(C)Colim(C) to be a Grothendieck topos even if CC is, it is at least true in this case that Colim(C)Colim(C) is a locally cartesian closed pretopos, thus satisfying many of the topos-like properties one needs to internalize large chunks of mathematics.

In these notes, we wish to prove that if CC is a complete and cocomplete locally cartesian closed pretopos (or a cocomplete Π\Pi-pretopos; see below), then so is Colim(C)Colim(C). The expectation is that this result can be strengthened to incorporate WW-types (i.e., Π\Pi-pretoposes which admit initial algebras for polynomial functors). Eventually, we hope to study the initial algebra or final coalgebra for the ColimColim construction itself, which again should have all these properties.

Free coproduct cocompletions

As a stepping stone, consider the cocompletion of a category CC with respect to small coproducts (denoted ΣC\Sigma C). This may be constructed explicitly by a comma category construction: objects of ΣC\Sigma C are pairs (X,f:X dC)(X, f: X_d \to C) where XX is a set and ff is a functor from the discrete category X dX_d on XX to CC. Morphisms (X,f)(Y,g)(X, f) \to (Y, g) are pairs (h,Φ)(h, \Phi) where h:XYh: X \to Y is a function and Φ:fgh d\Phi: f \to g \circ h_d is a natural transformation. The idea is that a pair (X,f)(X, f) is a formal coproduct

x:Xf(x)\sum_{x : X} f(x)

of objects of CC.

If EE is a Grothendieck topos, and Δ:SetE\Delta: Set \to E is the essentially unique left exact left adjoint, a functor X dEX_d \to E may be identified with an object in the slice E/Δ(X)E/\Delta(X), and the comma category construction for ΣE\Sigma E may be written as

ΣE=EΔ.\Sigma E = E \downarrow \Delta.

This is an example of Artin-Wraith gluing, and EΔE \downarrow \Delta is again a Grothendieck topos.

As a special case, when EE is a presheaf topos Set D opSet^{D^{op}}, we have

EΔSet D + opE \downarrow \Delta \simeq Set^{D_{+}^{op}}

where D +D_+ is obtained by formally adjoining a (new) initial object to DD.

Rather more generally, if CC is an \infty-lextensive category, then we have an essentially unique left exact coproduct-preserving functor

Δ:SetC\Delta: Set \to C

which takes a set XX to a coproduct of an XX-indexed collection of copies of the terminal object 11 of CC, and the infinite extensivity means that we again have an equivalence

Σ(C)CΔ.\Sigma(C) \simeq C \downarrow \Delta.

This applies in particular to the case where CC is a Π\Pi-pretopos. In the next section, we will prove a general result that has the following corollary: if CC is a complete and cocomplete Π\Pi-pretopos, then so is Σ(C)\Sigma(C).

Pullback-preserving comonads on Π\Pi-pretoposes

Analogously to the case for toposes, we will show that if GG is a left exact (or even just a pullback-preserving) comonad on a cocomplete Π\Pi-pretopos, then the category of GG-coalgebras is also a cocomplete Π\Pi-pretopos.

Lemma

A cocomplete locally cartesian closed extensive category is \infty-extensive.

This is essentially obvious: infinite coproducts are still disjoint, and stable under pullbacks by local cartesian closure.

Lemma

A cocomplete locally cartesian closed extensive category CC is complete.

Proof

The condition of local cartesian closure includes the existence of finite limits, so it suffices to see that CC has arbitrary products. Let B iB_i be a collection of objects of CC indexed over a set II. By cocompleteness, we have a map in CC:

p: iIB iΔI,p: \sum_{i \in I} B_i \to \Delta I,

where ΔI= iI1\Delta I = \sum_{i \in I} 1, sending the summand B iB_i to ii (the i thi^{th} copy of 11). Then

iIB i=Π !p\prod_{i \in I} B_i = \Pi_! p

is the product, where !! is the unique map ΔI1\Delta I \to 1. Indeed, maps XΠ !pX \to \Pi_! p are in natural bijection with maps ! *Xp!^\ast X \to p in E/Δ(I)E IE/\Delta(I) \simeq E^I (this equivalence holds by infinite extensivity), i.e., with an II-indexed family of maps XB iX \to B_i, as required.

In particular, cocomplete Π\Pi-pretoposes are also complete.

Theorem

Let GG be a pullback-preserving comonad on a cocomplete Π\Pi-pretopos EE. Then the category of GG-coalgebras Coalg GCoalg_G is also a cocomplete Π\Pi-pretopos.

Proof

The underlying functor U:Coalg GEU: Coalg_G \to E preserves and reflects colimits, so it is clear that Coalg GCoalg_G is cocomplete. It has a terminal object G1G 1 and has pullbacks since GG preserves pullbacks, so Coalg GCoalg_G is finitely complete. To show Coalg GCoalg_G is locally cartesian closed, we must check that for each GG-coalgebra ZZ the slice Coalg G/ZCoalg_G/Z is cartesian closed. Now the forgetful functor U Z:Coalg G/ZE/ZU_Z: Coalg_G/Z \to E/Z is left exact: it clearly preserves the terminal object 1 Z:ZZ1_Z: Z \to Z, and preserves pullbacks because U:Coalg GEU: Coalg_G \to E does. It is also comonadic with respect to a comonad G ZG_Z whose functor part takes an object f:XZf: X \to Z of E/ZE/Z to the pullback of the diagram

Z η Z GX Gf GZ,\array{ & & Z \\ & & \downarrow \mathrlap{\eta_Z} \\ G X & \underset{G f}{\to} & G Z, }

as may be checked directly (or using a crude monadicity theorem). Then we use the familiar fact that if CC is cartesian closed and H:CCH: C \to C is a lex comonad, then Coalg HCoalg_H is also cartesian closed; apply this to H=G Z:E/ZE/ZH = G_Z: E/Z \to E/Z to conclude Coalg G/ZCoalg_G/Z is cartesian closed.

It remains to see that Coalg GCoalg_G is a pretopos.

In brief, Coalg GCoalg_G is a pretopos because the pretopos axioms are expressed in terms of pullbacks and colimits. If G:EEG: E \to E is preserves pullbacks, then the underlying functor U:Coalg GEU: Coalg_G \to E preserves and reflects colimits and pullbacks, and this means that the pretopos axioms hold on Coalg GCoalg_G if they hold on EE.

For example, UU preserves and reflects monos. Thus, a pushout diagram in Coalg GCoalg_G of the form

0 X Y X+Y\array{ 0 & \to & X \\ \downarrow & & \downarrow \\ Y & \to & X + Y }

is also a pullback in which all arrows are monic, since this is true as a diagram in EE by extensivity. Also such coproducts are stable under pullback (say by local cartesian closure). Therefore Coalg GCoalg_G is extensive.

It is also regular: given f:XYf: X \to Y in Coalg GCoalg_G, the coequalizer of the kernel pair of ff can be computed at the level of EE (again by the preservation and reflection properties of UU), and this gives the regular epi-mono factorization in Coalg GCoalg_G. Of course, regular epis in Coalg GCoalg_G, being coequalizers, are stable under pullback by local cartesian closure. Hence Coalg GCoalg_G is regular. And congruences in Coalg GCoalg_G are kernel pairs, again by the same reasoning about preservation and reflection of finite limits and colimits. Hence Coalg GCoalg_G is (Barr-)exact. This completes the proof.

Corollary

Let CC be a cocomplete Π\Pi-pretopos, and let Δ:SetC\Delta: Set \to C be the (essentially unique) left exact left adjoint. Then

Σ(C)=CΔ\Sigma(C) = C \downarrow \Delta

is a cocomplete Π\Pi-pretopos.

Proof

Let G:C×SetC×SetG: C \times Set \to C \times Set be the functor defined by G(c,X)=(c×ΔX,X)G(c, X) = (c \times \Delta X, X). Then GG is left exact and carries an obvious comonad structure. The category of GG-coalgebras is CΔC \downarrow \Delta, and this is a cocomplete Π\Pi-pretopos by the theorem.

Quotients and exact completions

For a finitely complete category CC, let C exC_{ex} denote its exact or ex/lex completion.

Lemma

(Carboni) If CC is a small lex category, then (ΣC) exSet C op(\Sigma C)_{ex} \simeq Set^{C^{op}}.

Proof

The category ΣC\Sigma C is \infty-lextensive if CC is lex, and the exact completion of an \infty-lextensive category is cocomplete, exact, and \infty-lextensive. The projective objects in (ΣC) ex(\Sigma C)_{ex} are the objects in ΣC\Sigma C, and the connected projective objects in (ΣC) ex(\Sigma C)_{ex} are the objects of CC. Thus all the Giraud conditions are satisfied, making (ΣC) ex(\Sigma C)_{ex} a Grothendieck topos with a generating set of objects given by objects of CC, and since these generators are connected and projective, this topos is actually a presheaf topos Set C opSet^{C^{op}}.

Lemma

(Rosický) If CC is finitely complete, then Colim(C)(ΣC) exColim(C) \simeq (\Sigma C)_{ex}.

Proof

CC is a (large) union of small lex categories C iC_i, and we have a series of equivalences

(ΣC) ex i(ΣC i) ex iSet C i op=Colim(C)(\Sigma C)_{ex} \simeq \bigcup_i (\Sigma C_i)_{ex} \simeq \bigcup_i Set^{C_i^{op}} = Colim(C)

where the colimit given by the second expression is over the system of exact functors (ΣC i) ex(ΣC j) ex(\Sigma C_i)_{ex} \to (\Sigma C_j)_{ex} that are identified with left Kan extensions along inclusions C iC jC_i \to C_j.

(Possible mention of work by Pitts et al. on reflexive coqualizer completions, etc.)

Theorem

If EE is a cocomplete Π\Pi-pretopos, then so is E exE_{ex}.

Proof

First, if EE is cocomplete, so is E exE_{ex} (reference needed). It is known that E exE_{ex} is locally cartesian closed if EE has weak dependent products (and hence if EE has dependent products, i.e., if EE is locally cartesian closed), and that E exE_{ex} is a pretopos if EE is extensive. This is all we need.

Corollary

If EE is a cocomplete Π\Pi-pretopos, then so is the free small-colimit cocompletion Colim(E)Colim(E).

Proof

Combine Corollary 1, Lemma 4, and Theorem 2.

Inductive types

Now we reprise some of the above development, but this time adding in WW-types.

Suppose given a cocomplete Π\Pi-pretopos EE, and let f:YXf: Y \to X be a morphism in EE. The polynomial endofunctor P f:EEP_f: E \to E is defined to be the composite

EY *E/YΠ fE/XΣ XEE \stackrel{Y^\ast}{\to} E/Y \stackrel{\Pi_f}{\to} E/X \stackrel{\Sigma_X}{\to} E

which, informally, takes an object XX to the “polynomial” a:AX f 1(a)\sum_{a: A} X^{f^{-1}(a)}.

The WW-type W(f)W(f), if it exists, is the initial P fP_f-algebra. A ΠW\Pi W-pretopos is a Π\Pi-pretopos EE which admits a WW-type W(f)W(f) for every morphism ff of EE.

More generally, one speaks of inductive types. One thing we can point out immediately is that the construction of the corresponding coinductive types, i.e., terminal P fP_f-coalgebras, is completely unproblematic.

Proposition

Terminal P fP_f-coalgebras exist for any f:YXf: Y \to X in any Π\Pi-pretopos.

Proof

Since cocomplete Π\Pi-pretoposes EE are complete, the limit of the following diagram exists in EE:

(P f) n+1(1)(P f) n!(P f) n(1)P f(1)!1.\ldots \to (P_f)^{n+1}(1) \stackrel{(P_f)^n !}{\to} (P_f)^n(1) \to \ldots \to P_f (1) \stackrel{!}{\to} 1.

Moreover, P fP_f preserves this limit because (a) this is a connected limit, and (b) the functors Y *Y^\ast, Π f\Pi_f, and Σ X\Sigma_X all preserve connected limits. Then the result follows from Adámek’s theorem, which asserts that this limit LL, with coalgebra structure LP fLL \to P_f L the isomorphism that obtains by the limit preservation by P fP_f, is the terminal coalgebra.

Below, we hope to exploit this to give a relatively painless proof of the following theorem, by situating initial algebras inside terminal coalgebras. The proof we give now is somewhat technical; it is adapted from a result in a paper of Moerdijk and Palmgren, who cite Alex Simpson as the originator of the proof they give the slice topos case.

Theorem

If EE is a ΠW\Pi W-pretopos and G:EEG: E \to E is a pullback-preserving comonad on EE, then Coalg GCoalg_G is also a ΠW\Pi W-pretopos.

Lemma

If EE is a Π\Pi-pretopos and

P k B h g A f C\array{ P & \stackrel{k}{\to} & B \\ ^\mathllap{h} \downarrow & & \downarrow^\mathrlap{g} \\ A & \underset{f}{\to} & C }

is a pullback diagram in EE, then there is an isomorphism

E/A Π f E/C h * g * E/P Π k E/B\array{ E/A & \stackrel{\Pi_f}{\to} & E/C \\ ^\mathllap{h^\ast} \downarrow & \cong & \downarrow^\mathrlap{g^\ast} \\ E/P & \underset{\Pi_k}{\to} & E/B }

of Beck-Chevalley type.

Proof of Theorem

(This “proof” isn’t correct, but I’m letting it sit as is while I ponder…) Let f:BAf: B \to A be a map between GG-coalgebras, and let W(f)W(f) denote the WW-type of ff seen as a morphism of EE. We will denote the to-be-constructed WW-type of ff, regarded as a morphism of Coalg GCoalg_G, by W G(f)W_G(f).

We construct W G(f)W_G(f) as an equalizer

W G(f)jW(f)βαW(Gf).W_G(f) \stackrel{j}{\to} W(f) \stackrel{\overset{\alpha}{\to}}{\underset{\beta}{\to}} W(G f).

To define α\alpha, first observe that there is a natural transformation P fP GfP_f \to P_{G f}, obtained by pasting together a 2-cell diagram

E/GB Π Gf E/GA Σ GA E GB * η B * η A * Σ A E B * E/B Π f E/A \array{ & & E/G B & \stackrel{\Pi_{G f}}{\to} & E/G A & \stackrel{\Sigma_{G A}}{\to} & E \\ & ^\mathllap{G B^\ast} \nearrow \cong & ^\mathllap{\eta_B^\ast} \downarrow & \cong & ^\mathllap{\eta_A^\ast} \downarrow & ^\Uparrow \nearrow^\mathrlap{\Sigma_A} & \\ E & \underset{B^\ast}{\to} & E/B & \underset{\Pi_f}{\to} & E/A & & }

where the η\eta‘s refer to the given coalgebra structures, the middle 2-cell is a Beck-Chevalley isomorphism, and the transformation Σ Aη A *Σ GA\Sigma_A \eta_A^\ast \to \Sigma_{G A} is mated to the canonical isomorphism Σ AΣ GAΣ η A\Sigma_A \to \Sigma_{G A} \Sigma_{\eta_A}. Then, we have a composite

P f(W(Gf))P Gf(W(Gf))W(Gf)P_f(W(G f)) \to P_{G f}(W(G f)) \cong W(G f)

where the isomorphism obtains by initiality of W(Gf)W(G f). Thus W(Gf)W(G f) carries a P fP_f-algebra structure, whence there is a unique P fP_f-algebra map

α:W(f)W(Gf).\alpha: W(f) \to W(G f).

To define β\beta, let S=Struct G(A)GA AS = Struct_G(A) \hookrightarrow G A^A be the object of possible structures on AA as a coalgebra over the comonad GG (this is easily defined in a Π\Pi-pretopos EE). There is of course a point [η A]:1Struct G(A)[\eta_A]: 1 \to Struct_G(A) where η A\eta_A is the given coalgebra structure on AA. We begin by exhibiting a canonical P fP_f-algebra structure on the exponential W(Gf) SW(G f)^S, which is tantamount to giving a map

P f(W(Gf) S)×SP Gf(W(Gf))(W(Gf)).P_f(W(G f)^S) \times S \to P_{G f}(W(G f)) (\cong W(G f)).

It is probably simplest to describe this map in the internal language of Π\Pi-pretoposes (or in dependent type theory); it is the mapping

(a:A,S×f 1(a)tX;η:S)(η(a),λu:(Gf) 1(η(a)).t(η,ε B(u)):(Gf) 1(η(a))X).(a: A, S \times f^{-1}(a) \stackrel{t}{\to} X; \eta: S) \mapsto (\eta(a), \lambda u: (G f)^{-1}(\eta(a)). t(\eta, \varepsilon_B(u)): (G f)^{-1}(\eta(a)) \to X).

Here ε:G1 E\varepsilon: G \to 1_E is the counit of the comonad, and the definition makes sense because the judgment ε Bu:f 1(a)\varepsilon_B u: f^{-1}(a) is valid, given the judgment (Gf)(u)=η(a):GA(G f)(u) = \eta(a): G A. Indeed, we have

f(ε B(u))=(fε B)(u)=(ε AGf)(u)=ε A((Gf)(u))=ε A(η(a))=af(\varepsilon_B(u)) = (f \circ \varepsilon_B)(u) = (\varepsilon_A \circ G f)(u) = \varepsilon_A((G f)(u)) = \varepsilon_A (\eta (a)) = a

where the last equation holds since ε Aη\varepsilon_A \circ \eta for any GG-coalgebra structure η\eta.

(It is straightforward – although somewhat tedious – to write out the definition in purely categorical language.)

Since we have a P fP_f-algebra structure on W(Gf) SW(G f)^S, we obtain a unique P fP_f-algebra map W(f)W(Gf) SW(f) \to W(G f)^S, and the map β\beta is the composite

W(f)W(Gf) Seval η AW(Gf).W(f) \to W(G f)^S \stackrel{eval_{\eta_A}}{\to} W(G f).

(To be continued.)

References

Revised on October 9, 2016 at 14:19:10 by Todd Trimble