Completion of a category

Question

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?

Answer 1

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).

Answer 2

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).

Answer 3

The following is what I wrote about six months ago during a private discussion (posted on request :-)

Let me start with a positive (obvious :-) result. $\newcommand{\word}[1] { \mathit{#1} } \newcommand{\catl}[1] { \mathbb{#1} } \newcommand{\catw}[1] { \mathbf{#1} } \newcommand{\mor}[3] { {#1 \colon #2 \rightarrow #3} }$

1) Let $\catl{C}$ be a small category. Denote by $\word{Cont}(\catl{C}^{op}, \catw{Set})$ the full subcategory of presheaves $\catw{Set}^{\catl{C}^{op}}$ that consists of such $\mor{H}{\catl{C}^{op}}{\catw{Set}}$ that preserve small limits that exist in $\catl{C}^{op}$ (i.e. map existing colimits from $\catl{C}$ to limits in $\catw{Set}$). It follows from abstract nonsense that $\word{Cont}(\catl{C}^{op}, \catw{Set})$ has small (co)limits and, in fact, is a reflective subcategory of $\catw{Set}^{\catl{C}^{op}}$.

Of course, every presheaf preserves colimits, therefore the restricted Yoneda embedding $A \mapsto \hom(-, A)$ gives functor: $$\mor{y}{\catl{C}}{\word{Cont}(\catl{C}^{op}, \catw{Set})}$$ This functor almost by definition preserves all limits that exist in $\catl{C}$. Observe, that it also preserves colimits. Let $\mor{F}{\catl{J}}{\catl{C}}$ be a functor from a small category, and assume that the colimit $\mathit{colim}(F)$ exists in $\catl{C}$. Consider any $H \in \word{Cont}(\catl{C}^{op}, \catw{Set})$. Then morphisms: $$y(\mathit{colim}(F)) = \hom(-, \mathit{colim}(F)) \rightarrow H(-)$$ by Yoneda, are tantamount to elements: $$H(\mathit{colim}(F)) \approx \mathit{lim}(H \circ F)$$ Similarly, morphisms: $$y(F(J)) = \hom(-, F(J)) \rightarrow H(-)$$ are tantamount to elements: $$H(F(J))$$ and one may easily verify, that the above exhibits $\hom(-, \mathit{colim}(F))$ as the limit $\mathit{lim}(y \circ F)$.

The above construction is described, for example, in "Basic concepts of enriched categories" of Max Kelly (Section 3.12). Moreover, as pointed out there, $\word{Cont}(\catl{C}^{op}, \catw{Set})$ inherits any monoidal (closed) structure from $\catl{C}$ via (restricted) convolution.

On the other hand, if $\catl{C}$ is not (monoidal) closed, then $\word{Cont}(\catl{C}^{op}, \catw{Set})$ generally will not be (monoidal) closed, due to the following fact.

2) There is no universal limit and colimit preserving fully faithful embedding of a small category to a cartesian closed complete and cocomplete category.

In fact, there is no universal embedding into cartesian closed category that preserves terminal object and binary coproducts.

For let us assume that $\catl{C}$ is non-degenerated and has a costrict terminal object (terminal object $1$ is costrict if whenever there exists a morphism $1 \rightarrow X$ then $X \approx 1$) and binary coproducts (you may take $\catl{C} = \catw{FinSet}^{op}$), and there is such an embedding $\mor{E}{\catl{C}}{\overline{\catl{C}}}$.

Because $1$ is costrict in $\catl{C}$ we have that $1 \sqcup 1 \approx 1$ in $\catl{C}$ and since coproduct and the terminal object are preserved by $E$, we have also $1 \sqcup 1 \approx 1$ in $\overline{\catl{C}}$. Let $\mor{f,g}{1}{A}$ be two morphisms in $\overline{\catl{C}}$. By the universal property of coproducts they induce the copairing morphism $\mor{[f,g]}{1 \sqcup 1}{A}$ that commutes with the coproduct's injections. However, since $1\approx 1 \sqcup 1$, the coproducts injections are identities and so $f = [f,g] = g$. Therefore, for every $A \in \overline{\catl{C}}$ there is at most one arrow $1 \rightarrow A$. If we take for $A$ an exponent $E(Y)^{E(X)}$, then by cartesian clossedness of $\overline{\catl{C}}$ and faithfulness of $E$:

$$\hom_\catl{C}(X, Y) \leq \hom_\overline{\catl{C}}(E(X), E(Y)) \approx \hom_\overline{\catl{C}}(1, E(Y)^{E(X)}) \leq 1$$

which contradicts the fact that $\catl{C}$ is non-degenerated.

3) Generally, the completions obtained in any of the mentioned ways will not be the smallest completion. In fact, for a general $\catl{C}$, the smallest reflective subcategory of $\catw{Set}^{\catl{C}^{op}}$ containing representables may not be a smallest limit and colimit completion of $\catl{C}$.

Let us take for example $\mathcal{Z}_3$ group thought as of a category with a single object. Actually one may easily compute the category $\overline{\mathcal{Z}_3}$ induced by the idempotent monad associated to the monad $T$ on the Isbell cojugation for $\mathcal{Z}_3$ (by the theorem of Fakir this category can be computed by taking the objects that respects $T$-weak equivalences). Explicitly, category $\overline{\mathcal{Z}_3}$ is the full subcategory of $\catw{Set}^{\mathcal{Z}_3^{op}}$ on free permutations, together with the terminal permutation (up to the terminal permutation it is equivalent to the Kleisli resolution of the monad $\mor{(-) \times \mathcal{Z}_3}{\catw{Set}}{\catw{Set}}$, but I'm not sure if this is deep or meaningless...).

One may easily see that $\overline{\mathcal{Z}_3}$ is not self-dual, thus cannot be the smallest limit and colimit completion (since $\mathcal{Z}_3$ is self-dual, if $\overline{\mathcal{Z}_3}$ was the smallest, then $(\overline{\mathcal{Z}_3})^{op}$ would be the smallest). Moreover, $\overline{\mathcal{Z}_3}$ satisfies the following properties:

• its every object is a colimit over $\mathcal{Z}_3$,
• its every object is a double-limit over $\mathcal{Z}_3$

Therefore (by the second property) $\overline{\mathcal{Z}_3}$ is the smallest reflective subcategory of $\catw{Set}^{\mathcal{Z}_3^{op}}$ containing representables.

4) The Dedekind-MacNeille construction as described in Todd's answer works when the monad induced by the Isbell conjugation is itself idempotent. For example, this is always true in the world of posets, in the world of Lawvere metric spaces, and more generally in the world of categories enriched over affine quantales (because in such a case every enriched monad is idempotent).

I actually think that only Dedekind-MacNeille completitions for categories enriched over (co)complete posets deserve the name.

The reason is that there is a subtlety here (which may look minor at first, but I think is crucial for the whole construction) that makes that the direct categorification of the original Dedekind-MacNeille requirements for completion have no sense --- the completion should be complete and cocomplete, which means that it should be closed under all limits/colimits. On the other hand, the term "a category is complete and cocomplete" means that the category is closed under small limits and small colimits (obviously, there is no (co)completion under all (co)limits in a $\catw{Set}$-enriched world). Therefore, the direct categorification of the requirement is possible only when the base of the enrichment has all limits/colimits, which in turn, implies that the base of the enrichment is a poset (at least in the classical mathematics).

As I said, the distinction between small and all may look minor at first, but in fact the distinction is not about quantity, but about quality. This distinction shows up on many occasions. For example, constructively if a category is complete (with respect to all cones) then it is also cocomplete (with respect to all cocones), and every colimit can be expressed as a limit; however, this is no longer true if the category is only small complete --- the cone from the canonical representation of a small cocone may be large, and there may be no reason for its limit to exists.

Answer 4

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}$.