The Eilenberg-Moore category of a monad $(T:C \to C, \eta, \mu)$ has as objects pairs $(x \in Ob(C), h:Tx \to x)$ such that $h \circ \mu_x = h \circ Th:T(Tx) \to x$ and $h \circ \eta_x = id_{x}$. A morphism $f:(x, h) \to (x', h')$ in this category is a morphism in $f:x \to x'$ in $C$ such that $f \circ h = h' \circ Tf:Tx \to x'$ in $C$.

An example is the monad that sends a set to finite sequences of the members of that set (for example $\{A, B, C\} \mapsto \{[], [A], \ldots, [BCAAB], \ldots\}$) and functions to functions that act on each element of the sequence individually, with $\eta(x) = [x]$ and $\mu([[x1x2\ldots][y1y2\ldots]\ldots]) = [x1x2\ldots y1y2\ldots,\ldots]$. This is a monad, and its EM-category is equivalent to the category of monoids.

My question is based on the monad I will call $T$. It is a monad on $SET$. It sends a set $A$ to the set of infinite sequences of the elements of $A$. It sends a function $f: A \to B$ to the function that takes an infinite sequence of $x \in A$ to to the infinite sequence of $f(x)$s. $\eta(x) = [x, x, x \ldots]$ repeated forever. $\mu$ is based on diagonalization. Namely, given an infinite sequence of infinite sequences of $A$, it gives the following sequence: the first element of the first sequence, the second element of the second sequence, the third element of the third sequence, etc... . For example: $$\mu([[x1, x2, x3 \ldots],[y1, y2, y3 \ldots], [z1, z2, z3 \ldots], \ldots] = [x1, y2, z3, \ldots].$$

My question is, is the EM-category of this equivalent to the category of some common algebraic structure? What is the EM-category of this monad on $SET$?

  • I suspect that there is an algebra for every pair $(X, U)$ of a compact Hausdorff space $X$ and an ultrafilter $U$ on $\mathbb{N}$, with structure map sending an infinite sequence in $X$ to its $U$-ultralimit. But I'm not sure off the top of my head if ultralimits respect diagonals in the necessary way. In particular there is an algebra for every pair $(X, n)$ of a set $X$ and a positive integer $n$ (these correspond to the principal ultrafilters); the structure map sends a sequence of elements of $X$ to its $n^{th}$ term. – Qiaochu Yuan May 10 '15 at 3:18
up vote 6 down vote accepted

This is a special case of the so-called "reader monad" or "environment monad", which is defined as follows for every object $E$ in a cartesian closed category $\mathcal{S}$:

  • The endofunctor is $[E, -] : \mathcal{S} \to \mathcal{S}$.
  • The unit $\eta_X : X \to [E, X]$ is the diagonal embedding, i.e. the morphism $[1, X] \to [E, X]$ induced by the unique morphism $E \to 1$.
  • The multiplication $\mu_X : [E, [E, X]] \to [E, X]$ corresponds to the morphism $[E \times E, X] \to [E, X]$ induced by the diagonal embedding $E \to E \times E$.

In fact, assuming $\mathcal{S}$ also has finite limits, this is the monad induced by the adjunction $$E^* \dashv \Pi_E : \mathcal{S}_{/ E} \to \mathcal{S}$$ defined as follows:

  • $E^* : \mathcal{S} \to \mathcal{S}_{/ E}$ sends each object $X$ in $\mathcal{S}$ to the object $(E \times X, \pi_X)$ in $\mathcal{S}_{/ E}$, where $\pi_X : E \times X \to E$ is the projection.
  • $\Pi_E : \mathcal{S}_{/ E} \to \mathcal{S}$ sends each object $(Y, q)$ in $\mathcal{S}_{/ E}$ to the object $\Pi_E (Y, q)$ defined by the following pullback diagram, $$\require{AMScd} \begin{CD} \Pi_E (Y, q) @>>> [E, Y] \\ @VVV @VV{[E, q]}V \\ 1 @>>{u}> [E, E] \end{CD}$$ where $u : 1 \to [E, E]$ corresponds to $\mathrm{id} : E \to E$.

In particular, there is a canonical comparison functor from $\mathcal{S}_{/ E}$ to the category of algebras for the induced monad. Unfortunately, it is not usually faithful, let alone an equivalence. (This reflects the fact that $\Pi_E : \mathcal{S}_{/ E} \to \mathcal{S}$ is not usually faithful.)

It seems to me that there is no good description of the algebras for this monad other than as "objects of generalised functions". For example, when $\mathcal{S} = \mathbf{Set}$, given a map $p : I \to E$ and a set $X (i)$ for each $i \in I$, we can make $A = \prod_{i \in I} X (i)$ into an algebra with action $\alpha : [E, A] \to A$ given by $\alpha (f) (i) = f (p (i)) (i)$. (Here, we are thinking of elements of $\prod_{i \in I} X (i)$ as special functions with domain $I$ and codomain $\bigcup_{i \in I} X (i)$.) Note that $$\alpha (\mu_A (f)) (i) = \mu_A (f) (p (i)) (i) = f (p (i)) (p (i)) (i) = [E, \alpha] (f) (p (i)) (i) = \alpha ([E, \alpha] (f)) (i)$$ so $\alpha : [E, A] \to A$ is indeed an action.

In the case where $I = E$, $p = \mathrm{id}_E$, and $X (i)$ does not depend on $i$, $(A, \alpha)$ is a free algebra. Qiaochu's remark about principal ultrafilters can be seen as the special case where $I = 1$.

  • And E=aleph null for my example, right? – PyRulez May 10 '15 at 19:53
  • Yes, of course. – Zhen Lin May 10 '15 at 20:01
  • (The reader monad is common in haskell.) – PyRulez May 10 '15 at 20:16
  • for those not comfortable with categories, see the simpler presentation at blog.higher-order.com/blog/2015/09/30/… ---which is inspired by this solution! – Musa Al-hassy Oct 6 '15 at 20:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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