I want to define the List-Permuation (co)monad as follows:

$List-Perm = (L, \mu, \eta, \nu, \zeta)$.

$$L:Set \rightarrow Set$$

such that, L returns the set of Lists of a given set.

$$\mu : L \cdot L \rightarrow L$$

by returning a list from a list of lists by concatenation.

$$\eta : 1_{Set} \rightarrow P$$

by sending a set to the set of lists with just those elements (eg $\eta:(\{a,b,c \}) \rightarrow \{ [a],[b],[c] \}$)

$$\nu : L \rightarrow L \cdot L$$

This works by sending each list, $w$ to a list of permutations of $w$. This can be done by defining for every set $S$

  1. a function $f_S$ such that, if $n$ is the cardinality of $S$, $f_{S}^{m} =I$ iff mModn = 0 and $I$ is the identity function on $S$.
  2. a map from $N$ to the set of functions $f^{i}$ which we use to define a list of functions $[f^{0}, f^1, f^2 \cdots]$.
  3. then define a list of permutations as, $A \in Set$, $w \in L(A)$, $L \cdot L (A) = [[f^0(w)], [f^1(w)], [f^2(w)], \cdots ]$

[Edit] I have defined the functions, $f$, to act on the set $S$. This is probably not going to work. We want the coproduct to take a list to a list of all of its permutations. Instead, given a list, $w$,of length $l$, we want to define a function on the set $W$ of natural numbers less than $l $. Then do as we did before so that $f_{w}$, rather than permuting set elements, it permutes the list positions.

  1. a function $f_w$ such that, if $l$ is the length of $w$, $f_{w}^{m} =I$ iff mMod$l $ = 0 and $I$ is the identity function on $W$.

    1. a map from the set of functions $f_{w}^{i}$ to $N $ which we use to define a list of functions $[f_{w}^{0}, f_{w}^1, f_{w}^2 \cdots]$.

[Edit] You might want to define a set of functions, one for every integer which we take as list length. Each function with the properties above.

[Edit] I realize now that this doesn't work, simply by cardinality: the list generated by $f_{l}$ has $l $ elements, and there are $n! $ permutations. We need to somehow have the permutation group act on the list in a natural way.

The counit:

$$\zeta : L \rightarrow I$$

This may not admit a counit. My only guess is that you take a List, $w = [a,b,c]$ and map it to $a \in S$, ie you map the head of the list to its itself in $S$.

Does this work?

  • 2
    $\begingroup$ I don't understand this 'comultiplication' $\eta$. Shouldn't it go $L\to L\cdot L$? How do the permutations of lists enter the picture here? $\endgroup$ – Berci Mar 7 '18 at 0:38
  • 1
    $\begingroup$ Sorry, it's about the $\nu$. $\endgroup$ – Berci Mar 7 '18 at 0:44
  • $\begingroup$ Yes that was a mistake thank you $\endgroup$ – Ben Sprott Mar 7 '18 at 1:22
  • $\begingroup$ Hi @Berci, I have been convinced that this will not work for the following reason: the species of linear orderings is not naturally isomorphic to the species of permutations. $\endgroup$ – Ben Sprott Mar 7 '18 at 21:40

Yes, the 'head' function $\zeta:=[a,b,c,\dots]\mapsto a\ $ works as counit, provided that the permutation $f$ for a list of length $n$ is the specific cycle $(1\,2\,\dots\,n)$.
The empty set and the empty list should not be considered here.

But, the two counit identities are satisfied: $$[a_1,a_2,\dots,a_n]\ \overset\nu\longmapsto\ \big[\overbrace{[a_1,a_2,\dots]},\ [a_2,a_3,\dots],\ \dots \big] \ \overset{\zeta L}\longmapsto\ [a_1,a_2,\dots] \\ [a_1,a_2,\dots,a_n]\ \overset\nu\longmapsto\ \big[[\underline{a_1},a_2,\dots],\ [\underline{a_2},a_3,\dots],\ \dots \big] \ \overset{L\zeta}\longmapsto\ [a_1,a_2,\dots]$$

Also, the comultiplication $\nu$ so defined is coassociative: the common ternary comultiplication will be $$[a_1,a_2,\dots,a_n]=:w\ \longmapsto\ \Big[ [w,fw,..];\ [fw,f^2w,..];\ [f^2w,f^3w,..];\ \dots \Big] $$

| cite | improve this answer | |

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.