Permutation monad

Question

Given a set $S$, say $S= \{a,b\}$, the set of permuations of $S$ is $\{[a,b],[b,a]\}$ (these are supposed to be lists like $ab$ and $ba$). Can we define a monad that captures this? This monad would be like the List monad.

The permutation monad $Perm = (P, \mu, \eta)$.

$$P:Set \rightarrow Set$$ such that, P returns the set of permutations of a given set.

$$\mu : P \cdot P \rightarrow P$$ by returning a set of permutations given by the first element in each permutation of permutations. (This I don't think works). $$\eta : 1_{Set} \rightarrow P$$ by sending a set element to it's permutation of itself.

Answer 1

Note that you have only defined $P$ on objects. There isn't a nice way of extending $P$ to a functor $\mathbf{Set} \to \mathbf{Set}$, however there is another category where your definition of $P$ does extend nicely. Namely, let $\mathbf{B}$ be the category of sets and bijections; then you can define $P(X)$ to be the set of permutations of $X$ and, given a bijection $f : X \to Y$, define $$P(f) : P(X) \to P(Y), \quad \sigma \mapsto f \circ \sigma \circ f^{-1}$$ Note that $P(f)$ is itself a bijection and that the assignment $f \mapsto P(f)$ is functorial, so this truly does define a functor $P : \mathbf{B} \to \mathbf{B}$.

Unfortunately, this is where the story ends. To define a natural transformation $\eta : 1 \to P$, you would need to define a bijection $\eta_X : X \to P(X)$ for each set $X$, but basic cardinality arguments demonstrate that this is impossible, since there are more permutations of a set $X$ than there are elements of $X$.

Answer 2

As Clive said, you problem is ill-defined. He gives one way to fix the settings. Here is another one, from species and operad theory.

Denote by $\mathbf P$ the category whose objects are natural numbers $0,1,2,\ldots$ and morphisms are defined as follow: $\mathbf P(n,n)$ is the permutation group on $n$ elements, and $\mathbf P(n,m)$ is empty when $m\neq n$. Otherwise put, it is a squeleton of the category of finite sets and bijections. Then define a functor $\mathrm{Perm} : \mathbf P \to \mathsf{Set}$ in the same way Clive did: for each $n \in \mathbb N$, $\mathrm{Perm}(n)$ is the set of permutations on $S$, and for each permutation $\sigma$ on $n$ elements, $\mathrm{Perm}(\sigma)$ is the conjugacy by $\sigma$.

Of course, there is another functor $i : \mathbf P \to \mathsf{Set}$ which is just the inclusion of each $n$ as the set $\{1,\ldots,n\}$ and each permutation as its action on that set. One can now recover a functor $\underline{\mathrm{Perm}} : \mathsf{Set}\to\mathsf{Set}$ by left Kan extension of $\mathrm{Perm}$ along $i$. Explicitely, this functor is given by $$ \underline{\mathrm{Perm}}(X) = \{ (n,\bar x,\sigma) : n\in \mathbb N, \bar x\in X^n, \sigma: n\to n)\}\, \big/\, {\sim}$$ where the relation $\sim$ identifies $(n,(x_1,\ldots,x_n),\sigma\circ \tau)$ with $(n,(x_{\sigma(1)},\dots,x_{\sigma(n)}),\tau)$.

There is an obvious map $\eta_X : X \to \underline{\mathrm{Perm}}(X)$ that maps $x$ to the class of $(1,(x),\mathrm{id})$, which is clearly natural in $X$ (by the way, I did not define $\underline{\mathrm{Perm}}$ on the functions $f: X \to Y$, you should do it properly). There is also a less obvious map $\mu_X : \underline{\mathrm{Perm}}(\underline{\mathrm{Perm}}(X)) \to \underline{\mathrm{Perm}}(X)$ that takes as input an element $(n,(p_1,\ldots,p_n),\sigma)$ where each $p_i$ is an element of $\underline{\mathrm{Perm}}(X)$, hence of the form $(m_i,(x^i_1,\ldots,x^i_{m_i}),\tau_i)$; the map $\mu_X$ on such an input returns $$ \left(\sum_{i=1}^n m_i,(x_1^1,\dots,x^1_{m_1},x^2_1,\dots,x^{n-1}_{m_{n-1}},x^n_1,\dots,x^n_{m_n}),\sigma\ast(\tau_1,\dots,\tau_n) \right) $$ where $\sigma\ast(\tau_1,\dots,\tau_n)$ is the permutation on $\sum_{i=1}^n m_i$ elements defined by blocks as $\tau_{\sigma(1)}$ on the first $m_1$ elements, as $\tau_{\sigma(2)}$ on the next $m_2$ elements, and so on until acting as $\tau_{\sigma(n)}$ on the last $m_n$ elements. This $\mu_X$ is also natural in $X$.

You can now check that $\underline{\mathrm{Perm}}$ is a monad with unit $\eta$ and multiplication $\mu$. (Actually you have a whole lot more to check, because I defined those maps without taking care of the equivalence relation in order to be more concise.) If I remember correctly, this is called the ($\mathsf{Set}$-based) associative (symmetric) operad in the literature.