Completion of a category - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T12:18:14Z http://mathoverflow.net/feeds/question/59291 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59291/completion-of-a-category Completion of a category Michal R. Przybylek 2011-03-23T11:54:32Z 2011-03-26T16:02:46Z <p>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.</p> <p>However, for a poset $P$ there is also a completion that preserves both limits and colimits --- namely --- Dedekind-MacNeille completion <a href="http://planetmath.org/encyclopedia/NormalCompletion.html" rel="nofollow">link text</a>, embedding $P$ into the poset of up-down-subsets of $P$.</p> <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? </p> http://mathoverflow.net/questions/59291/completion-of-a-category/59295#59295 Answer by Todd Trimble for Completion of a category Todd Trimble 2011-03-23T13:03:53Z 2011-03-23T17:48:05Z <p>Yes, it's a general construction which is related to so-called Isbell conjugation. </p> <p>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. </p> <p>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 <b>Isbell conjugation</b>. </p> <p>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$. </p> <hr> <p><b>Edit:</b> 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 </p> <p>$$A^u = \{p \in P: \forall_{x \in P} x \in A \Rightarrow x \leq p\}$$ </p> <p>$$B^d = \{q \in P: \forall_{y \in P} y \in B \Rightarrow q \leq y\}$$ </p> <p>and one has </p> <p>$$A \subseteq B^d \qquad \text{iff} \qquad A \times B \subseteq (\leq) \qquad \text{iff} \qquad B \subseteq A^u$$ </p> <p>We thus have an adjunction </p> <p>$$(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}})$$</p> <p>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$. </p> <p>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 </p> <p>$$R(G) = \int_{d \in C} \hom(-, d)^{G(d)}$$ </p> <p>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 </p> <p>$$L(F) = \int_{c \in C} \hom(c, -)^{F(c)}$$ </p> <p>(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 </p> <p>$$\{F \to R(G)\} \qquad \cong \qquad \{F \times G \to \hom\} \qquad \cong \qquad \{G \to L(F)\}$$ </p> <p>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. </p> http://mathoverflow.net/questions/59291/completion-of-a-category/59340#59340 Answer by Buschi Sergio for Completion of a category Buschi Sergio 2011-03-23T18:34:23Z 2011-03-26T16:02:46Z <p>Let $\mathcal{C}$ be a small regular category. Let $\mathcal{C}^&lt;:=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. </p> <p>The imbedding $FL(\mathcal{C} , Set) \subset \mathcal{C}^{&lt;}$ create limits, (a limit of a finite limit preserving functors is finite limits preserving). Then $\widetilde{\mathcal{C}}$ has colimits.</p> <p>Since $FL(\mathcal{C} , Set) \subset \mathcal{C}^{&lt;}$ is a reflexive categories, $FL(\mathcal{C} , Set)$ has colimits i.e. $\widetilde{\mathcal{C}}$ has limits. This is a (not easy) fundamental theorem.</p> <p>$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}$)</p> <p>$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}^&lt; (h^X, P) \cong P(X) \cong {\underleftarrow{\lim}}_{i\in I} P(X_i) \cong {\underleftarrow{\lim}}_{i\in I} \mathcal{C} ^&lt;(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)$.</p> <p>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}$. </p>