8
$\begingroup$

There is the power set functor, $T$, which gives raise to a monad: For a set $X$, we set $TX:=\mathcal P(X)$ and for $f:X\to Y$, we set $T(f):=S\mapsto f(S)$, where $f(S)$ denotes the direct image. The unit maps to the singleton $x\mapsto\{x\}$ and the second map gives a union, as in $\{\{a,b\},\{c\},\{\{d,e\},f\}\}\mapsto \{a,b,c,\{d,e\},f\}$. There is also the very similar list-monad, where $TX:=\bigcup_nX^n=X\cup (X\times X)\cup (X\times\dots$

What are the adjoint functor pairs $F,G$ for, so that $T=FG$ and what is the co-unit? I know there are at least "the two extremal solutions" - are they used somewhere?

$\endgroup$
7
  • 1
    $\begingroup$ In the powerset monad that I'm familiar with, the contravariant powerset functor is both the $F$ and the $G$, and the counit is the unit in $\mathbf{Set^{op}}$. $\endgroup$ Sep 11 '14 at 18:03
  • $\begingroup$ edit: For the list monad, it probably should be $X^0\cup X\cup(X\times\dots$. $\endgroup$
    – Nikolaj-K
    Sep 11 '14 at 20:20
  • $\begingroup$ @MaliceVidrine: I'm confused: If both $F$ and $G$ have the power set operation as object map, isn't then $T$ the twice applied power set operation? $\endgroup$
    – Nikolaj-K
    Sep 11 '14 at 20:52
  • $\begingroup$ Yes, though I've seen it referred to simply as the "powerset monad". It sounds like there are others I'm not familiar with, though. $\endgroup$ Sep 12 '14 at 1:02
  • 1
    $\begingroup$ The "twice applied power set operation" cannot be given the structure of a monad: mathstat.dal.ca/mfps2018/preproc/paper_4.pdf So, it's impossible to have an adjunction where both left and right adjoint are the covariant power set functor. $\endgroup$
    – John Baez
    Jun 9 '18 at 18:20
5
$\begingroup$

I prefer to write $F$ for the left-adjoint. So we have $T = GF$. You can consider for $F$ the free functor from the category of sets to the category of complete semi-lattices or the free functor from the category of sets to the category of free complete semi-lattices. The functor $G$ is the forgetful functor that takes a complete semi-lattice (resp. a free complete semi-lattice) and forgets the structure to give the set of its elements.

$\endgroup$
8
  • $\begingroup$ And, for the list-monad we get the free/forgetful adjuntion between $\bf{Set}$ and [free] semigroups. $\endgroup$
    – Berci
    Sep 11 '14 at 19:00
  • $\begingroup$ Yes, but it would be less ambiguous to write $TX = \bigcup_{n \geq 1} X^n$. Because if $TX = \bigcup_{n \geq 0} X^n$, we get the free/forgetful adjunction between Set and [free] monoids. It seems to me that usually the expression "list-monad" is used for the latter. $\endgroup$
    – user21929
    Sep 11 '14 at 19:13
  • $\begingroup$ So $F$ maps $\{a,b,c\}$ to $\langle\mathcal{P}(\{a,b,c\}),>\rangle$, where e.g. $\{a,c\}>\{c\}$, and then $G$ on that tuple projects out the first tuple? $\endgroup$
    – Nikolaj-K
    Sep 11 '14 at 20:27
  • $\begingroup$ Yes, but it can be confusing to write $(\mathcal{P}(\{ a, b, c \} ), >)$ for an object of the category of complete semi-lattices, because morphisms have to preserve joins and not only to be monotone. $\endgroup$
    – user21929
    Sep 11 '14 at 20:41
  • 1
    $\begingroup$ Example : $A = \mathcal{P}(\{ a, b \})$ and $B = \mathcal{P}(\{ a, b, c \})$. The function $f$ from $A$ to $B$ defined by $f(\emptyset) = \emptyset$, $f(\{ a \}) = \{ a \}$, $f(\{ b \}) = \{ a, b \}$ and $f(\{ a, b \}) = \{ a, b, c \}$ preserves $\subseteq$ but not $\bigcup$ : it is not a morphism of the category of complete semi-lattices. $\endgroup$
    – user21929
    Sep 11 '14 at 21:17

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.