Completion of a category

For a poset $P$ there exists an embedding $y$ into a complete and cocomplet poset $\hat{P}$ of downward closed subsets of $P$. It is easy to verify that the embedding preserves all existing limits and no non-trivial colimits --- i.e. colimits are freely generated. $\hat{P}$ may be equally described as the poset of all monotonic functions from $P^{op}$ to $2$, where $2$ is the two-valued boolean algebra. Then we see, that $P$ is nothing more than a $2$-enriched category, $2^{P^{op}}$ the $2$-enriched category of presheaves over $P$ and that $y$ is just the Yoneda functor for $2$-enriched categories.

However, for a poset $P$ there is also a completion that preserves both limits and colimits --- namely --- Dedekind-MacNeille completion link text, embedding $P$ into the poset of up-down-subsets of $P$.

Is it possible to carry the later construction to the categorical setting and reach something like a limit and colimit preserving embedding for any category $\mathbb{C}$ into a complete and cocomplete category?

-
The link to DM completion has rotted. I guess it used to point to what's now here: planetmath.org/macneillecompletion –  Tom Leinster Aug 7 '13 at 16:27
@TomLeinster, thanks --- I've just fixed the link. –  Michal R. Przybylek Sep 10 '13 at 10:26
So if the construction $DM(\mathbb{C})$ given below doesn't give a complete and cocomplete category into which $\mathbb{C}$ embeds, is there a different construction which does do this? –  Glen M Wilson Sep 23 '13 at 18:54
@GlenMWilson, I don't konw :-) I was to ask this question, but decided to postpone it until I have more time to think about the question by myself. –  Michal R. Przybylek Sep 27 '13 at 21:17
From what was going on below it seems that one has to switch from the contravariant adjunction $L\dashv R$ to the (again contravariant) adjunction between $LR$-coalgebras and $RL$-algebras, then again, and this might go on forever... –  მამუკა ჯიბლაძე Apr 1 at 5:55

Yes, it's a general construction which is related to so-called Isbell conjugation.

Let $C$ be a small category. It is well-known that the free colimit cocompletion is given by the Yoneda embedding into presheaves on $C$, $y: C \to Set^{C^{op}}$. The presheaf category is also complete. Dually, the free limit-completion is given by the dual Yoneda embedding $y^{op}: C \to (Set^C)^{op}$. The co-presheaf category is also cocomplete.

Therefore there is a cocontinuous functor $L: Set^{C^{op}} \to (Set^C)^{op}$ which extends $y^{op}$ along $y$. This is a left adjoint; its right adjoint is the (unique up to isomorphism) functor $R: (Set^C)^{op} \to Set^{C^{op}}$ which extends $y$ continuously along $y^{op}$. This adjoint pair is called Isbell conjugation.

As is the case for any adjoint pair, this restricts to an adjoint equivalence between the full subcategories consisting, on one side, of objects $F$ of $Set^{C^{op}}$ such that the unit component $F \to R L F$ is an iso, and on the other side of objects $G$ of $(Set^C)^{op}$ such that the counit $L R G \to G$ is an iso. Either side of this equivalence gives the Dedekind-MacNeille completion of $C$. By the Yoneda lemma, $y: C \to Set^{C^{op}}$ factors through the full subcategory of DM objects as a functor $C \to DM(C)$ which preserves any limits that exist in $C$, and dually $y^{op}: C \to (Set^C)^{op}$ factors as the same functor $C \to DM(C)$ which preserves any colimits that exist in $C$.

Edit: Perhaps it might help to spell this out a little more. The classical Dedekind-MacNeille completion is obtained by taking fixed points of a Galois connection between upward-closed sets and downward-closed sets of a poset $P$. So, if $A$ is downward-closed (i.e., a functor $A: P^{op} \to \mathbf{2}$), and $B: P \to \mathbf{2}$ is upward-closed, we define

$$A^u = \{p \in P: \forall_{x \in P} x \in A \Rightarrow x \leq p\}$$

$$B^d = \{q \in P: \forall_{y \in P} y \in B \Rightarrow q \leq y\}$$

and one has

$$A \subseteq B^d \qquad \text{iff} \qquad A \times B \subseteq (\leq) \qquad \text{iff} \qquad B \subseteq A^u$$

We thus have an adjunction

$$(L = (-)^u: \mathbf{2}^{P^{op}} \to (\mathbf{2}^P)^{op}) \qquad \dashv \qquad (R = (-)^d: (\mathbf{2}^P)^{op} \to \mathbf{2}^{P^{op}})$$

and the poset of downward-closed sets $A$ for which $A = (A^u)^d$ is isomorphic to the poset of upward-closed sets $B$ for which $(B^d)^u = B$.

All of this can be "categorified" so as to hold in a general enriched setting, where the base of enrichment is a complete, cocomplete, symmetric monoidal closed category $V$. We may take for example $V = Set$. Analogous to the formation of $B^d$, we may define half of the Isbell conjugation $R: (Set^C)^{op} \to Set^{C^{op}}$ by the formula

$$R(G) = \int_{d \in C} \hom(-, d)^{G(d)}$$

where $\hom$ plays the role of the poset relation $\leq$, exponentiation or cotensor plays the role of the implication operator, and the end plays the role of the universal quantifier. The other half $L: Set^{C^{op}} \to (Set^C)^{op}$ is also defined, at the object level, by

$$L(F) = \int_{c \in C} \hom(c, -)^{F(c)}$$

(the right-hand side is a set-valued functor $C \to Set$; when we interpret this in $(Set^C)^{op}$, the end is interpreted as a coend, and the cotensor is interpreted as a tensor). In any event, given $F: C^{op} \to Set$ and $G: C \to Set$, we have natural bijections between morphisms

$$\{F \to R(G)\} \qquad \cong \qquad \{F \times G \to \hom\} \qquad \cong \qquad \{G \to L(F)\}$$

and the analogue of the MacNeille completion is obtained by taking "fixed points" of the adjunction $L \dashv R$, as described above by full subcategories where the unit and counit $F \to RLF$ and $LRG \to G$ become isomorphisms. These full subcategories are equivalent; one side of the equivalence is complete because it is the category of algebras for an idempotent monad associated with $RL$, and the other side is cocomplete because it is the category of coalgebras for an idempotent comonad associated with $LR$, and thus both sides are complete and cocomplete.

Edit: It has been pointed out that there is a mistake in the argument at the end of the prior edit, asserting that the fixed points of the monad coincide with the algebras of an associated idempotent monad. See Michal's answer (posted 9/13/2013).

-
Great answer, thanks! –  Michal R. Przybylek Mar 23 '11 at 18:23
Todd, I think something's wrong in the last sentence. Let C be any small category that isn't a poset. Its MacNeille completion DM(C) contains C as a subcategory, so isn't a poset either. Hence, as long as DM(C) is small, it's neither complete nor cocomplete. And DM(C) is sometimes small (indeed, as far as I know, it always is for small C). E.g. if C is the category consisting of a parallel pair of arrows then DM(C) is C with an initial and a terminal object freely adjoined, which obviously isn't complete or cocomplete. –  Tom Leinster Aug 7 '13 at 15:39
Yes, I think you're right, @TomLeinster. I'll try to make time to think about this. Or if you have any ideas... –  Todd Trimble Aug 7 '13 at 16:25
Dude, do I have to call you @ToddTrimble now? I'm so behind the times! –  Tom Leinster Aug 7 '13 at 16:28
@TomLeinster: I know, I feel goofy addressing you that way (and maybe I don't; I should look up the fine print of this notification system). Would be cool if "dude" could be used to get to the right person! –  Todd Trimble Aug 7 '13 at 19:08

Let me give more details about the comments under Todd's answer.

As Tom pointed out, taking fixed points of the Isbell conjugation for the category $\mathbb{C}$: $$\overset{A}{} \stackrel{\longrightarrow}{\longrightarrow} \overset{B}{}$$ consisting of two parallel arrows between two different objects, freely adjoins an initial and terminal objects, yielding the category $\mathit{DM}(\mathbb{C})$: $$\overset{0\longrightarrow A}{} \stackrel{\longrightarrow}{\longrightarrow} \overset{B\longrightarrow 1}{}$$ which is neither complete nor cocomplete (in fact it does not have even binary (co)products).

To see why $\mathit{DM}(\mathbb{C})$ is of the above form, let us first observe that $\mathbb{C}$ is self-dual, therefore the categories of presheaves and coprseheaves over $\mathbb{C}$ are isomorphic. Both of these categories may be thought of as categories of directed graphs and graph homomorphisms. Let me compute the left part ($L$ in Todd's answer) of the Isbell conjugation $(-)^\star \colon \mathbf{Set}^{\mathbb{C}^{op}} \to (\mathbf{Set}^\mathbb{C})^{op}$: $$G^\star(Y) = \int_{X \in \mathbb{C}} \hom(X, Y)^{G(X)} = \mathit{nat}(G, \hom(-, Y))$$ The graph associated to the presheaf $\hom(-, A)$ consitsts of a single node: $$\bullet$$ so the set of edges $G^\star(A)$ of graph $G^\star$ is the set of homomorphisms from graph $G$ to graph $\bullet$. This set is either empty $\emptyset$ --- if $G$ contains any edge, or a singleton $1$ otherwise.

Similarly, the graph associated to the presheaf $\hom(-, B)$ is: $$\bullet \rightarrow \bullet$$ and so the set of nodes $G^\star(B)$ of graph $G^\star$ is the set of homomorphisms from graph $G$ to graph $\bullet \rightarrow \bullet$. This set is empty iff $G$ contains composable edges (loops $\looparrowright$ or sequences $\bullet \rightarrow \bullet \rightarrow \bullet$). If $G$ does not contain any sequence of composable edges, then the set of nodes is equal to $2^D$, where $D$ is the largest discrete full subgraph of $G$.

If there is an edge in $G^\star(A)$, and there are at least two distinct nodes in $G^\star(B)$ then the edge is non-degenerated (its source is different from its target).

By duality, the right part ($R$ in Todd's answer) of the Isbell conjugation $(\mathbf{Set}^\mathbb{C})^{op} \to \mathbf{Set}^{\mathbb{C}^{op}}$ is defined on graphs in essentially the same way.

Here are some examples of graphs $G$ with their corresponding graphs $G^\star$: \begin{array}{ccc} \emptyset & \mapsto & \looparrowright \newline \bullet & \mapsto & \bullet \rightarrow \bullet \newline \looparrowright & \mapsto & \emptyset \newline \bullet \rightarrow \bullet & \mapsto & \bullet \newline \bullet \rightarrow \bullet \; \bullet & \mapsto & \bullet \; \bullet \newline \bullet \; \bullet & \mapsto & \bullet \rightarrow \bullet \; \bullet \; \bullet \newline \bullet \rightarrow \bullet \; \bullet \; \bullet & \mapsto & \bullet \; \bullet \; \bullet \; \bullet \newline \end{array}

One may easily verify that, due to size issues (i.e. there are no isomorphism $2^K \approx K$ for any $K$) and the fact that in the image of $(-)^\star$ there are no graphs with more than one edge, only the first four graphs from the above table are fixed-points of the Isbell conjugation. Moreover, these graphs together with their homomorphism constitute a category isomorphic to: $$\overset{0\longrightarrow A}{} \stackrel{\longrightarrow}{\longrightarrow} \overset{B\longrightarrow 1}{}$$

The gap in Todd's proof of (co)completeness is in the implicit assumption that the fixed-points of a monad are the same as fixed-points of the associated idempotent monad. There is an abstract counterexample to this claim --- fixed-points of an idempotent monad constitute a reflective subcategory of the base category, whereas fixed-points of an arbitrary monad generally not (perhaps one of the idea of an associated idempotent monad is just to add "enough" fixed-points to the monad to make the subcategory of fixed-points reflective).

-
Should I delete my answer? That would be fine, but I think it has to be "unaccepted" first. –  Todd Trimble Sep 13 '13 at 17:12
Maybe it is better to keep with a proviso as to where it goes wrong? –  Benjamin Steinberg Sep 13 '13 at 17:15
@ToddTrimble, of course no! I've learnt much from your answer, and still like it very much. Additionally, in a sense, it answers my question, as it describes a categorification of Dedekind-MacNeille completion. –  Michal R. Przybylek Sep 13 '13 at 20:11
@ToddTrimble, is there any chance that in our case the category of algebras for the associated idempotent monad coincides with the category of coalgebras for the associated idempotent comonad? –  Michal R. Przybylek Sep 13 '13 at 20:37
@MichalR.Przybylek, the answer is no, and $\cdot \longrightarrow \cdot \stackrel{\longrightarrow}{\longrightarrow} \cdot$ is a counterexample. –  Michal R. Przybylek Sep 16 '13 at 17:43

Let $\mathcal{C}$ be a small regular category. Let $\mathcal{C}^<:=CAT(\mathcal{C} , Set)$ the category of set valued functors on $\mathcal{C}$ (in the Grothendieck notation) and $FL(\mathcal{C} , Set)$ the full subcategory of finite limit preserving functors. We have the Yoneda full embedding: $h^-: \mathcal{C}^{op} ,\to FL(\mathcal{C} , Set)$, let $\widetilde{\mathcal{C}}:=FL(\mathcal{C} Set)^{op}$ then define $Y: \mathcal{C} \to \widetilde{\mathcal{C}}$ as the dual of the Yoneda embedding.

The imbedding $FL(\mathcal{C} , Set) \subset \mathcal{C}^{<}$ create limits, (a limit of a finite limit preserving functors is finite limits preserving). Then $\widetilde{\mathcal{C}}$ has colimits.

Since $FL(\mathcal{C} , Set) \subset \mathcal{C}^{<}$ is a reflexive categories, $FL(\mathcal{C} , Set)$ has colimits i.e. $\widetilde{\mathcal{C}}$ has limits. This is a (not easy) fundamental theorem.

$Y: \mathcal{C} \to \widetilde{\mathcal{C}}$ preserves colimits (from the well-known property $h^{{\underrightarrow{\lim}}_{i\in I} X_i }\cong {\underleftarrow{\lim}}_{i\in I} h^{X_i}$)

$Y: \mathcal{C} \to \widetilde{\mathcal{C}}$ preserve finite limits: Let $X={\underleftarrow{\lim}}_{i\in I} X_i$ be a finite limit, we have the isomorphisms: $$\mathcal{C}^< (h^X, P) \cong P(X) \cong {\underleftarrow{\lim}}_{i\in I} P(X_i) \cong {\underleftarrow{\lim}}_{i\in I} \mathcal{C} ^<(h^{X_i}, P) \cong ({\underrightarrow{\lim}}_{i\in I} h^{X_i}, P )$$ natural in $P\in FL(\mathcal{C}, Set)$. Then, by the Yoneda lemma, $h^X \cong {\underrightarrow{\lim}}_{i\in I} h^{X_i}$ in $FL(\mathcal{C}, Set)$.

From above, $Y: \mathcal{C} \to \widetilde{\mathcal{C}}$ preserves monomorphisms, epimorphisms, regular monomorphisms, regular epimorphisms. Then it preserves the (regular.Epi, Mono) factorization of $\mathcal{C}$.

-