Wikipedia:Reference desk/Archives/Mathematics/2019 July 6

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 6

Describe the Kleisli category of the power-set monad as the category of "sets and relations"

This is left as an exercise in the book Abstract and Concrete Categories and in other references, I've passed by. I would like to have access to a complete proof for understanding it completely as I have made some advancements:

• The category of sets and relations has sets as objects and relations as morphisms.
• Functions in the category Set can be described as binary relations.
• The power-set monad is a monad in Set that has as the unit the morphism that takes an element to a set with it and as the multiplication the union operation in sets.
• The Kleisli category on the power-set monad is then the category that its objects are sets and morphisms are the equivalent morphisms (those that have the target as the power set).

I couldn't connect those two categories and see how they are equal or even equivalent.Zorkedon (talk) 20:36, 6 July 2019 (UTC)

(I corrected the link, just so you know.) --RDBury (talk) 21:24, 7 July 2019 (UTC)

@Zorkedon: Okay, so I think you're basically there. The key thing to note is just that a relation $R\colon X\to Y$ is the same thing as a function $f_{R}\colon X\to {\mathcal {P}}(Y),$ where $f_{R}(x)=\{y\in Y\mid xRy\},$ which in turn is a morphism $X\to Y$ in the Kleisli category. There are still a couple thing to check with respect to this identification: that the identity relation corresponds to the identity morphism in the Kleisli category (easy), and that composition of relations corresponds to composition of morphisms in the Kleisli category (less easy, but still straightforward). Hope this helps, –Deacon Vorbis (carbon • videos) 02:52, 8 July 2019 (UTC)

I'm not sure if anyone's still watching this, but I looked back here and realized that I was maybe a bit too quick. What I described above was a functor $\mathbf {Setrel} \to \mathbf {Set} _{\mathcal {P}}$ (category of sets and relations to the Kleisli category of the power set monad), and then verifying that it's actually a functor. To really be complete, you should also give an inverse functor (and again verify that it's actually a functor) (and verify that both compositions are the identity). But if you can follow the first part, hopefully this should follow without too much more trouble. –Deacon Vorbis (carbon • videos) 14:49, 9 July 2019 (UTC)

@Deacon Vorbis: First of all: in the category ${Set}_{\mathcal {P}}$, the composition of morphisms (functions with target the power-set) should be defined by $g\circ _{\mathcal {P}}f=\mu _{Z}\circ {\mathcal {P}}g\circ f:X\to {\mathcal {P}}Y\to {\mathcal {P}}^{2}Z\to {\mathcal {P}}Z$ as in the definition of the Kleisli category, with $\mu _{Z}$ as the union operation understood as a function, how would that be? I can see that in your interpretation of the functor $F\colon \mathbf {Setrel} \to \mathbf {Set} _{\mathcal {P}}$, the identity $1_{X}\colon X\to X$ is the $\eta$ of the power-set monad, and for the proof of composition, one could construct binary relations $R\subseteq X\times Y$ and $S\subseteq Y\times Z$ and their respective functions from the functor $F_{R}(x)\colon X\to {\mathcal {P}}Y=\{y\in Y\mid xRy\}$ and $F_{S}(y)\colon Y\to {\mathcal {P}}Z=\{z\in Z\mid ySz\}$, and the composite relation $SR\subseteq X\times Z$ and it's functor equivalent $F_{SR}\colon X\to {\mathcal {P}}Z=\{z\in Z\mid xSRz\}$. But how can I prove that $F_{SR}=F_{S}\circ _{\mathcal {P}}F_{R}$? Zorkedon (talk) 21:33, 9 July 2019 (UTC)

@Zorkedon: To make the notation a bit easier, for a relation $R\colon X\to Y,$ define $R_{x}=\{y\in Y\mid xRy\}.$ Then, for $F_{S}F_{R}\colon X\to {\mathcal {P}}Y\to {\mathcal {PP}}Z\to {\mathcal {P}}Z,$

$x\mapsto R_{x}\mapsto \{S_{y}\mid y\in R_{x}\}\mapsto \bigcup _{y\in R_{x}}S_{y}.$

So, an element $z$ is in the ultimate image if it's in $S_{y}$ for some $y\in R_{x},$ but that's exactly the same thing as saying that there's some $y$ such that $ySz$ and $xRy,$ which in turn is exactly what it means to say that $xSRz.$ –Deacon Vorbis (carbon • videos) 14:32, 10 July 2019 (UTC)

@Deacon Vorbis: Ok, I understand the relation of functions with relations, but the union function should be defined as: for some $A=\{a\}$ its ${\mathcal {P}}A=\{\emptyset ;\{a\}\}$ and ${\mathcal {P}}({\mathcal {P}}A)=\{\emptyset ;\{\emptyset \};\{\{a\}\}\}$, and then the union would take out the brackets, and thus sending a set of sets to its respective set? ($\{\{a\}\}\mapsto \{a\}$ ) Zorkedon (talk) 15:29, 10 July 2019 (UTC)

Quick side note: you left out one element from ${\mathcal {PP}}A,$ namely $\{\emptyset ,\{a\}\}.$ But anyway, maybe a better example for the union would be a bigger set, say $\mathbb {N} .$ Then for example, one element $T\in {\mathcal {PP}}\mathbb {N}$ might be $T=\{\{1,2,3\},\{1,10\},\{100,101,102,\ldots \}\}.$ Then

$\mu _{\mathbb {N} }(T)=\{1,2,3\}\cup \{1,10\}\cup \{100,101,102,\ldots \}=\{1,2,3,10,100,101,\ldots \}\in {\mathcal {P}}\mathbb {N} .$

–Deacon Vorbis (carbon • videos) 23:54, 10 July 2019 (UTC)

But just to verify, in the case of $A$ you mentioned, yes; in fact, $\mu _{A}$ would send both $\{\{a\}\}$ and $\{\emptyset ,\{a\}\}$ to $\{a\},$ while it would send $\emptyset$ and $\{\emptyset \}$ to $\emptyset .$ –Deacon Vorbis (carbon • videos) 00:13, 11 July 2019 (UTC)