4
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ Assuming $a \neq b$, the set of permutations of $\{a, b\}$ comprises the identity function and the function that swaps $a$ and $b$. What does your notation $\{[a, b], [b, a]\}$ mean? $\endgroup$
    – Rob Arthan
    Feb 12, 2018 at 19:11
  • $\begingroup$ if you have two things $a$ and $b$, the set of permutations of those things is $ab$ and $ba$. Am I wrong? A permutation of elements is a list of those elements. $\endgroup$
    – Ben Sprott
    Feb 12, 2018 at 19:18
  • $\begingroup$ I see what you mean, but the notation with square brackets is not standard (the single line notation is usually written with no brackets or commas as you did in your comment: see en.wikipedia.org/wiki/Permutation#Definition_and_notations). $\endgroup$
    – Rob Arthan
    Feb 12, 2018 at 19:54
  • 3
    $\begingroup$ Moving on to your question about monads, the first thing you need to do is decide how to make $P$ into a functor, i.e., if $f : X \to Y$ is a morphism in the category of sets, what is $P(f) : P(X) \to P(Y)$? I can't see any natural way to define $P(f)$. Can you? $\endgroup$
    – Rob Arthan
    Feb 12, 2018 at 19:59

2 Answers 2

5
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ yes, unfortunate indeed. I was writing a paper that relied on the existence of a permutation monad. Lol, it was physics and so I just decided to keep going without knowing if it existed or not. Thanks for the proof outline. $\endgroup$
    – Ben Sprott
    Feb 12, 2018 at 20:18
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice!$~~~~~~~~$ $\endgroup$ Feb 13, 2018 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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