Completion of a category - MathOverflow

Completion of a category

2011-03-23T11:54:32Z

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 by Todd Trimble for Completion of a category

2011-03-23T13:03:53Z

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.

Answer by Buschi Sergio for Completion of a category

2011-03-23T18:34:23Z

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