34
$\begingroup$

The concept of a monad is very well established, and there are very many examples of monads pertaining almost all areas of mathematics.

The dual concept, a comonad, is less popular.

What are examples of comonads, in different categories, and different fields of math?

$\endgroup$
4
  • 3
    $\begingroup$ I don't see how comonads are less popular. Coalgebras are a rather common thing. Any time you write a diagonal $(x,x)$, you are implicitly using a coalgebra structure. $\endgroup$ Apr 21, 2019 at 6:41
  • 2
    $\begingroup$ @NajibIdrissi It might mean less popular as an explicitly used concept and language. $\endgroup$
    – YCor
    Apr 21, 2019 at 7:53
  • 6
    $\begingroup$ @NajibIdrissi : well, here is an example: The free algebra on a module is a very simple, classical and well understood notion, and everybody know that Algebra are monadic over modules. On the other hand (unless you restrict to the conilpotent case) the 'cofree coalgebra' over a module is an awfully complicated object (in general: over a field, it is not as bad, but over $\mathbb{Z}$ it is truly awfull), to the point that people working in the fields don't always know if they exist or not. $\endgroup$ Apr 21, 2019 at 12:02
  • 3
    $\begingroup$ I really wish that this question gets more answers and thus more examples! $\endgroup$ Feb 7, 2020 at 10:05

8 Answers 8

25
$\begingroup$

Here are the examples of comonads that I personally find most helpful. First from topology:

  • The universal covering is an idempotent comonad on (suitably nice) pointed topological spaces. The functor takes a pointed space $(X,x_0)$ and gives the space of homotopy classes of paths starting at $x_0$. The counit forgets the path and just keeps the endpoint, the comultiplication is an isomorphism. Co-Kleisli morphisms are continuous functions that "depend on the path", such as the complex logarithm. Coalgebras are simply connected spaces. (This comonad appeared in the comments to another answer.)
  • Similar to the example above, the rooted tree comonad on the category of pointed directed multigraphs can be seen as a "discrete universal covering". The functor takes a pointed graph $(X,x_0)$ and gives the graph whose vertices are paths on the graph starting at $x_0$, and which have a unique edge between them if and only if they differ by an edge in $X$. Again this comonad is idempotent, and its unit forgets the path and only keeps the endpoint. Co-Kleisli morphisms are path-dependent incidence-preserving maps. Coalgebras are rooted trees.

The following two are used in theoretical computer science.

  • The reader comonad on the category of sets. Fix a set $A$ of "extra data". The functor maps a set $X$ to the set $X\times A$, "adding the extra data". The comultiplication copies the extra data, and the counit forgets it. Co-Kleisli morphisms are functions that have access to these extra data. Coalgebras are sets equipped with a "default choice" of the data, a function $X\to A$.
  • The stream comonad on sets. Fix a monoid $N$, that we can think of "time". The functor maps a set $X$ to the set of maps $N\to X$, or "sequences" or "trajectories" or "histories". The counit forgets the history and just keeps the present state, the comultiplication looks at the history of the history (which is the history except the latest states...and so on). Co-Kleisli morphisms are maps that may depend on the history, and coalgebras are dynamical systems.

These four examples are taken from my notes (arXiv:1912.10642), sections 5.3 and 5.4 - see there for all the details. I don't claim that I have invented any one of these myself. (In the future I'd like to add these examples, and maybe some more, to the nLab. If anyone wants to help, I'd appreciate that.)

$\endgroup$
4
  • 1
    $\begingroup$ Love the computer science examples, and your notes look very interesting. I'd offer to help add some of your examples to nLab, but realistically I can't commit to that at the moment. $\endgroup$ Feb 7, 2020 at 22:19
  • 3
    $\begingroup$ Great that my wish for more examples was heard! +1 May I ask a technical question here? I kind of remember that the universal covering of a (nice) space is not a functorial construction, very much like the algebraic closure of a field is not a functorial construction (without making too much choices like transcendence bases etc.). But your answer and also your notes show an easy way to define the action on morphisms. Is my memory completely wrong here, or do I mix things up here, i.e. is there a related covering space construction which is not functorial? $\endgroup$ Feb 8, 2020 at 0:05
  • $\begingroup$ @MartinBrandenburg Interesting question! I don't know honestly. I think that to make it functorial you have to choose a base point, without that choice it probably wouldn't work. But I'm not an expert...anyone? $\endgroup$ Feb 8, 2020 at 1:19
  • 5
    $\begingroup$ Now that you say it, maybe the base point is actually the answer already. In the algebraic setting, the base point corresponds to an embedding into an algebraically closed field. And inside such a fixed algebraically closed field, we can take functorial algebraic closures of subfields. $\endgroup$ Feb 8, 2020 at 1:21
16
$\begingroup$

Given a topology on a set $X$, let $2^X$ be the poset of subsets of $X$ ordered by inclusion. Then the interior operator for the topology is a comonad on $2^X$. In fact the topologies on $X$ correspond precisely to the finite-limit-preserving comonads on $2^X$. The coalgebras of the comonad are precisely the open sets.

Given a topological space $X$, define a bundle on $X$ to be a topological space $Y$ and a continuous map $f:Y\to X$. The category of bundles is the overcategory $\mathbf{Top}/X$. Say that a bundle is étalé if the map $f$ is a local homeomorphism. Then the étalé bundles form a coreflective subcategory of $\mathbf{Top}/X$, meaning that there is an étalification comonad on $\mathbf{Top}/X$. The coalgebras of the comonad are precisely the étalé bundles, which correspond to sheaves on $X$.

The first example is a special case of the second, in the sense that if we view a subset of $X$ with its inclusion map as a bundle then its étalification is precisely its interior. Note also that in the first example the coalgebras form a locale, and in the second they form a topos.

$\endgroup$
6
  • 1
    $\begingroup$ This is a very good example. By the way, is the universal covering an idempotent comonad? $\endgroup$
    – geodude
    Apr 21, 2019 at 9:24
  • $\begingroup$ @geodude The étalification comonad is idempotent. I don't know what you mean by "universal covering" in this context. $\endgroup$ Apr 21, 2019 at 9:26
  • $\begingroup$ I mean the following. Take for example the category of manifolds. Assign to each manifold its universal cover. If this is functorial, it seems to give an idempotent comonad related to your construction. $\endgroup$
    – geodude
    Apr 21, 2019 at 9:35
  • 2
    $\begingroup$ Probably in order for that to be functorial we need pointed manifolds though. $\endgroup$
    – geodude
    Apr 21, 2019 at 10:11
  • 1
    $\begingroup$ @SomaticCustard I've seen étalé bundles in various introductions to sheaves, and sometimes the word étalification is used. But I can't remember anywhere that explicitly treats them as comonads. $\endgroup$ Jul 5, 2023 at 7:07
8
$\begingroup$

The category $\mathrm{Mfd}$ of finite dimensional manifolds sits fully faithfully inside the larger category $\mathrm{LocProMfd}$ of locally pro-finite dimensional manifolds, which basically extends manifolds by spaces locally modeled on the Fréchet space $\mathbb{R}^\mathbb{N}$. Take a finite dimensional base manifold $\Sigma$ and consider the category $\mathrm{LocProMfd}_{\downarrow \Sigma}$ of fibered locally pro-finite dimensional manifolds over $\Sigma$. The functor $$ J^\infty_\Sigma \colon \mathrm{LocProMfd}_{\downarrow \Sigma} \to \mathrm{LocProMfd}_{\downarrow \Sigma} , \quad (F\to M) \mapsto (J^\infty_\Sigma(F) \to M) , $$ that assigns to a fibered manifold the bundle of jets of its sections over $\Sigma$ is a comonad. The fiber of the infinite order jet bundle of a finite dimensional fibered manifold is already infinite dimensional. So there is no way to escape this enlargement of $\mathrm{Mfd}$, or something like it. This comonadicity observation is due to Michal Marvan, first recorded in a conference proceedings note in 1986 and elaborated in his 1989 PhD thesis at Moscow State University.

Together with Urs Schreiber (arXiv:1701.06238) we have checked that the jet functor both survives in the much more general setting of synthetic differential geometry and maintains its comonad property for some basic category theoretic reasons (it is a base change comonad of another functor). Check the arXiv preprint for a detailed discussion and precise references to Marvan's original observations.

$\endgroup$
7
$\begingroup$

Another comonad used in CS is known as Store. It maps $X$ to $(A\to X)\times A$. The comultiplication takes $(f,a)$ to $((f,-),a)$, and the counit takes $(f,a)$ to $f(a)$.

$\endgroup$
3
  • 1
    $\begingroup$ Notice that this is the comonad induced from the adjunction $- \times A \dashv\hom(A,-)$. $\endgroup$ Feb 10, 2020 at 23:39
  • 2
    $\begingroup$ Yep, sure is. All three of these comonads have dual (or at least closely related) monads: Store is dual to State ($X\Rightarrow A \rightarrow (X\times A)$), Env ($X \Rightarrow X\times A$) is dual to Reader ($X\Rightarrow A\rightarrow X$), and Traced ($X\Rightarrow N\rightarrow X$) is dual to Writer ($X\Rightarrow X\times N$). $\endgroup$ Feb 13, 2020 at 22:46
  • 1
    $\begingroup$ Interestingly, though, Env and Reader are basically monad/comonad ways of doing the same thing, while the other pairs do different things. $\endgroup$ Feb 13, 2020 at 22:51
7
$\begingroup$

The so-called game comonads have been recently studied in the context of finite model theory. The main references are the following:

  • Samson Abramsky, Anuj Dawar, and Pengming Wang. "The pebbling comonad in finite model theory." 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 2017. (see also arXiv:1704.05124)
  • Samson Abramsky and Nihil Shah. "Relating Structure and Power: Comonadic semantics for computational resources." International Workshop on Coalgebraic Methods in Computer Science. Springer, Cham, 2018. (see also arXiv:1806.09031)

Game comonads are an active area of research. In nutshell, some of the well-known model comparison can be turned into a comonad. This is done by representing the states of the game semantically. For example, the Ehrenfeucht-Fraïssé comonad $\mathbb E_k$ is a comonad on the category of relational structures. The universe of $\mathbb E_k(A)$ consists of non-empty words of length ${\leq}k$, where the alphabet is taken to be the universe of $A$. A word $[a_1,a_2,\dots,a_n]$ represents spoiler's moves in $A$ in the one-way Ehrenfeucht-Fraïssé game.

$\endgroup$
6
$\begingroup$

In computer science a class of comonads emerges from sets of datastructures with distinguished positions, often equipped with some kind of notion of a neighbourhood of the distinguished position (often called a "focus").

From this perspective a certain functor $C:\mathit{Set}\rightarrow\mathit{Set}$, taking a set to the set of grids of set elements, together with a scheme for applying certain types of locally specified rule over the entire grid, can be considered a comonad. In other words, comonads give a perspective on cellular automata.

See A Categorical Outlook on Cellular Automata by Capobianco and Uustalu for details.

$\endgroup$
6
$\begingroup$

For any monoid $(M,e,*)$ in $\mathsf{Set}$ there is a corresponding comonad $y^M$ on $\mathsf{Set}$. It sends a set $A$ to the set of morphisms into $A$ from $M$, $$ A\mapsto A^M. $$ Note that $y=y^1$ is the identity endofunctor on $\mathsf{Set}$.

Under the Yoneda embedding, the counit $y^M\to y$ corresponds to the monoid unit $e\colon 1\to M$, and the comultiplication $y^M\to (y^M)^M\cong y^{M^2}$ corresponds to the monoid multiplication $*\colon M^2\to M$.

As an example, this class of comonads includes the stream comonad (mentioned above), using the monoid of $(\mathbb{N},0,+)$ of natural numbers under addition.

Here are three more polynomial comonads for any set $S$:

  • Store comonad (mentioned above), the functor $F(y)= Sy^S$.
  • Linear comonad, the functor $F(y)=Sy$, with projection and diagonal.
$\endgroup$
4
$\begingroup$

Maybe this is too obvious, but every adjunction gives a comonad. If $(F,G)$ is a pair of adjoint functors, then $F \circ G$ defines a comonad, just as $G \circ F$ defines a monad

$\endgroup$
6
  • $\begingroup$ Saying there are "at least as many" is false in some sense. Different adjuctions $(G,F)$ can give the same comonad $F\circ G$. $\endgroup$ Apr 21, 2019 at 7:38
  • $\begingroup$ @OscarCunningham Fair. I'll edit $\endgroup$
    – Exit path
    Apr 21, 2019 at 7:45
  • 6
    $\begingroup$ I would not count this as an example. It is more like a different general description of comonads. (Also since every comonad comes from an adjunction.) $\endgroup$ Feb 8, 2020 at 1:18
  • $\begingroup$ This seems the wrong way round $\endgroup$
    – wlad
    Nov 19, 2023 at 8:09
  • 1
    $\begingroup$ @wlad Fixed, thanks! $\endgroup$
    – Exit path
    Dec 25, 2023 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.