5
$\begingroup$

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$?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ May 10, 2015 at 3:18

1 Answer 1

7
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ And E=aleph null for my example, right? $\endgroup$
    – PyRulez
    May 10, 2015 at 19:53
  • $\begingroup$ Yes, of course. $\endgroup$
    – Zhen Lin
    May 10, 2015 at 20:01
  • $\begingroup$ (The reader monad is common in haskell.) $\endgroup$
    – PyRulez
    May 10, 2015 at 20:16
  • $\begingroup$ 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! $\endgroup$ Oct 6, 2015 at 20:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .