# Universal cocompletion without leaving our universe

Let $\mathcal{U}$ be a universe and $\mathcal{U}^+$ a universe with $\mathcal{U} \in \mathcal{U}^+$. Denote by $\text{Cat}(\mathcal{U})$ the $\mathcal{U}^+$-category of all $\mathcal{U}$-categories, and by $\text{Cat}_c(\mathcal{U})$ the full subcategory consisting of $\mathcal{U}$-cocomplete categories, i.e. in which $\mathcal{U}$-small colimits exist. Consider $\mathcal{U}$ as the $\mathcal{U}$-category of all sets in $\mathcal{U}$.

Question. Does the inclusion $\text{Cat}_c(\mathcal{U}) \to \text{Cat}(\mathcal{U})$ have a left adjoint?

Remark that if $C \in \text{Cat}(\mathcal{U})$, then $\widehat{C} = \text{Hom}(C^{\text{op}},\mathcal{U})$, what is usually called the universal cocompletion of $C$, is a $\mathcal{U}^+$-category (the universum jumps!) which is $\mathcal{U}$-cocomplete, which satisfies the following universal property: $\mathcal{U}$-Functors $C \to D$, where $D$ is a $\mathcal{U}$-cocomplete $\mathcal{U}^+$-category, correspond to $\mathcal{U}$-cocontinuous $\mathcal{U}^+$-functors $\widehat{C} \to D$. Thus we have no adjointness property in the usual sense, right?

Actually I doubt that there is a left adjoint in the usual sense. But often universal cocompletions are quite useful and seem to be used without any discussion of the set-theoretic problems above (for example one restricts to small categories). Is that because it's not bad that we leave the universe, at least in some contexts?

Or is it possible to repair this? Is there a universe $\mathcal{U}$ which is big enough so that the above jumps "stabilize" below $\mathcal{U}$? Perhaps we can use Mahlo cardinals? Or can we repair this by restricting to finite colimits? Isn't this more reasonable since the definition of a universe is finitary? How does the left adjoint to $\text{Cat}_{fc}(\mathcal{U}) \to \text{Cat}(\mathcal{U})$ look like explictly, if it exists?

So my question is basically about the set theoretic subtletlies behind the universal cocompletion of a category. Feel free to write anything you know about them ...

-
$\newcommand{\C}{\mathbf{C}} \newcommand{\U}{\mathcal{U}} \newcommand{\Hom}{\mathrm{Hom}} \newcommand{\op}{\mathrm{op}}$ Very nice question! I’m not quite sure the cocompleteness of $\Hom(C,\U)$ is quite right as stands, though. Generally, $\Hom(C^\op,\U)$ will be a $\U^+$-category, but will only be $\U$-cocomplete, not $\U^+$-cocomplete; and similarly, its universal property refers to $\U$-cocomplete functors. A little more: $\Hom(C^\op,\U)$ will be $\U^+$-small provided $\C$ is $\U^+$-small and $\U$-locally-small; and it will additionally be $\U$-locally small if $\C$ is $\U$-small. – Peter LeFanu Lumsdaine Feb 18 '11 at 16:16
Thanks Peter, I've corrected it. – Martin Brandenburg Feb 18 '11 at 17:55
I think the answers below already at least explain the universal cocompletion. The intuition, I think (and I'm not sure, so this is a comment, not an answer), is that you write your essentially-large category as a "union" of essentially-small categories, cocomplete each one of those, and then paste back together. – Theo Johnson-Freyd Feb 18 '11 at 19:04
In any case, whatever is your construction of a "universal cocompletion", it should satisfy an adjunction, but you'll need to be a bit careful. Cat(U) is not naturally a category, but a 2-category, and these "universal" constructions are not universal in the 1-sense, but only in a weaker 2-sense. So what I mean is that if $C$ is a category with universal cocompletion $C \to \hat C$, and $D$ is cocomplete, then the universality/adjunction statement should be that pullback $\hom_{\text{coconts}}(\hat C,D) \to \hom(C,D)$ is an equivalence of categories (rather than, say, a bijection on objects). – Theo Johnson-Freyd Feb 18 '11 at 19:07
Yes of course, I mean a $2$-adjunction. – Martin Brandenburg Feb 18 '11 at 20:24

you can generalizing the $Ind(\mathcal{C})$ construction (see SGA.4-I) for general small diagrams (no neccessarly directed), using the general criterion that characterizes the purpose of a diagram $D: I \to \mathcal{C}$ in terms of connecting category paragraph $X \downarrow D, \ X \in \mathcal{C}$). In this way you get a cocompletion of a (big) category $\mathcal{C}$ relatively to the small colimits (without escape from base universe).

Is this generalization $Ind(\mathcal{C})$ is equivalent to the category $\mathcal{C}^>$ of presheaves on $\mathcal{C}$ formed by the elements $P\in \mathcal{C}^>$ such that the comma category (said also the Grothendieck costruction) $\mathcal{C}\downarrow P$ ha a small final subcategory.

You can find this construction in:

Shape Theory: Categorical Methods of Approximation di J. M. Cordier, T. Porter.

Or if you can read Italian language, I send you a my script about Category theory (involving aspect of completions of categories).\

This a Sketch:

Then give a morphism $\underline{f}: P \to Q$ we can represent it chosing for any $i\in I$ a lifting $h_{X_i} \to h_{Y_j(i)}$ i.e. $X_i \to Y_j$ of the morphism $h_{X_i} \to P \to Q$ then we have a map $\phi : |I|_0 \to |J|_0$ and a family of morphism $f_i: X_i \to Y_{\phi (i)}$ such that for a arrow $i \to i'$ in $I$ the morphisms $f_i: X_i \to Y_{\phi(i)}$ and $X_i \to X_{i'} \to Y_{\phi(i') }$ are connected as objects of $X_i \downarrow \underline{Y}$, and a such data make a unique (but Iso) morphism $P \to Q$. We call $(\phi , (f_i)_i)$ a representation of $\underline{f}$, and two representation $(\phi , (f_i)_i), \ (\phi' , (f'_i)_i)$ of $\underline{f}$ correspond to the some morphism $P \to Q$ IFF for every $i\in I$ the morphisms $f_i: X_i \to Y_{\phi(i) },\ f'_i: X_i \to Y_{\phi'(i) }$ are connected in $X_i \downarrow \underline{Y}$.

To a composition $\underline{g}\circ \underline{f}: P \to Q \to R$ we have in terms of representation:

$(\psi, (g_j))\circ(\phi,(f_i)) = (\psi\circ \phi,(g_{\eta(i)}\circ f_i)_i)$

Then we have the category of representations data as above, and call it $Ind_0(\mathcal{C})$ the (generalized Ind-category os $\mathcal{C}$, and a equivalence $Ind_0(\mathcal{C}) \sim P_0(\mathcal{C})$.

Now is $\mathcal{A}$ has small colimits any funtors $F: \mathcal{C} \to \mathcal{A}$ has a unique (but ISo) extention to a colimits preserving funtors: $P_0(F): \mathcal{C} \to \mathcal{A}$ where $P_0(-)$ is the (puntual) left-Kan-extention , this is "computable" in terms of Ind-representation: let give $\underline{f}: P \to Q$ in $P_0(\mathcal{C})$ as above, then we can define $P_0(P)= {\underrightarrow{lim}}_{i\in I} F(X_i)$, $P_0(Q)= {\underrightarrow{lim}}_{j\in J} F(Y_j)$, and $P_0(\underline{f})$ inducted by the family $F(f_i): F(X_i)\to F(Y_{\phi (i)}$ (follow a well defined morphism $P_0(\underline{f})$ for the connection relation described above).

Excuse my poor English..

-
This sounds very good! So you define a full subcategory of $\widehat{C}$, consisting of those presheaves whose category of elements is cofinally small. This will be the universal cocompletion of $C$. – Martin Brandenburg Feb 18 '11 at 18:16
Does anybody know another reference? Apparently my library does not have the boook on Shape Theory. – Martin Brandenburg Feb 18 '11 at 18:18
Try "Limits of small functors" by Day and Lack. – Mike Shulman May 25 '11 at 21:42

Funny, I was reading some remarks by Lawvere just last night which are related to this, over here; see especially part III.

Anyway, the small-colimit completion does exist for locally small categories $C$ and is itself locally small, but it is not identified with the exponential $U^{C^{op}}$ unless $C$ is small.

A construction which is similar but easier to describe is the free small-coproduct completion $Coprod(C)$ of a locally small category $C$. The objects of $Coprod(C)$ are pairs $(S, x: S \to Ob(C))$ where $S$ is a small set and $x$ is a function; morphisms $(S, x) \to (T, y)$ are pairs $(f, \phi)$ where $f: S \to T$ is a function and $\phi$ can be described as a 2-cell, having components which are morphisms $\phi_s: x(s) \to y(f(s))$ in $C$, where $s$ ranges over $S$. You can check that $Coprod(C)$ is locally small. An object $(S, x)$ should be viewed as a coproduct $\sum_{s \in S} x(s)$, and you can verify the appropriate universal property that makes this a coproduct completion.

One can then construct a free coequalizer cocompletion of $Coprod(C)$, and this will be the free small-colimit completion. It is relevant here that there is a distributive law (in the sense of Beck or Barr-Beck) between freely adjoining coproducts and freely adjoining coequalizers, to the effect that a coproduct of coequalizers can be construed as a coequalizer of coproducts. The result is locally small if $C$ is.

Actually, this question you ask is, I'm almost embarrassed to say, a minor obsession of mine. I have this oddball little project in my private web at the nLab called epistemologies which you can look at, but it's in a very preliminary, rough, incomplete form.

-
$\newcommand{\C}{\mathbf{C}} \newcommand{\U}{\mathcal{U}} \newcommand{\Hom}{\mathrm{Hom}} \newcommand{\op}{\mathrm{op}}$…and a very nice answer! Quick check on what smallness conditions are where: Am I right in understanding this as an adjoint from “$\U^+$-small, $\U$-locally-small categories” to “$\U^+$-small, $\U$-locally-small, $\U$-cocomplete categories”? And when restricted to “$\U$-small categories”, it does agree, up to (?pseudo-)natural equivalence, with the presheaves construction $\Hom(-^\op,\U)$? – Peter LeFanu Lumsdaine Feb 18 '11 at 16:23
@Peter: yes, you seem to have gotten those sizes right. You probably know this already (hence this might be a nitpick), but I wouldn't write $\hom(-^{op}, \mathcal{U})$: it's okay on objects, but as written that's contravariant on 1-cells. The small-cocompletion monad $P$ applied to a functor $f: C \to D$ between $\mathcal{U}$-small categories is the left adjoint to $\hom(f^{op}, \mathcal{U})$, in other words is the left Kan extension along $f^{op}$. – Todd Trimble Feb 18 '11 at 17:33