Skip to main content
some minor corrections
Source Link

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 thiswhy $\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))$$$$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)$ isconsitsts 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-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).

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 this, let us 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)$ is: $$\bullet$$ so the set of edges $G^\star(A)$ of $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 $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$), 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).

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

Source Link

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 this, let us 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)$ is: $$\bullet$$ so the set of edges $G^\star(A)$ of $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 $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$), 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).