Let Set denote the category of sets.

Let $T:$ Set $\to$ Set be the functor that sends a set $X$ to the set of finite words on $X$.

That is, $TX = \{[x_m,..,x_1] : m = 0,1,2,3..., x_i \in X\}$

$T$ can be considered a monad on Set with multiplication given by concatenation, and the unit by $x \to [x]$.

I'm trying to show explicitly that the category of $T$ algebras on Set is equivalent to the category of monoids (unital).

To do this we can define a functor $F:$ Mon $\to$ Alg$_T$(Set) by $F(m) = (m,a)$ where $a: Tm \to m$ is s.t $a([f_n,..,f_1]) = f_n...f_1$.

I have shown that this functor is fully faithful.

However I'm not sure I understand if it is essentially surjective.

Letting $(X,a_X) \in$ Alg$_T$(Set). I thought of defining a monoid $m$ as $TX$, where the action is concatenation, and the unit is simply the empty word.

Doing this yields a natural map in Alg$_T$(Set) from $TX$ to $X$, namely $a_X$. Clearly this map is onto because $a_X([x]) = x$ by definition of $(X, a_X)$ being an algebra.

But is this map injective?

  • $\begingroup$ Why would you want this map to be injective ? $\endgroup$ Dec 26 '18 at 14:58
  • $\begingroup$ @Max because I need to show that $F$ is essentially surjective, so I need that $(X,a_X)$ is in the essential range. $\endgroup$
    – Mariah
    Dec 26 '18 at 15:09
  • $\begingroup$ Oh right I didn't understand what you were trying to do. But it isn't injective. You want to see that $X$ is the underlying set of a monoid. To define the multiplication of $x,y$, put $x\times y := a_X([x,y])$ $\endgroup$ Dec 26 '18 at 15:13
  • $\begingroup$ @Max ok, but then what do we consider the identity element? It should be a word in $X$ by your statement, but this doesn't make sense. This structure you suggested allows for writing $a_X([x]) = x$ indeed, but don't we need the identity to be in $X$? $\endgroup$
    – Mariah
    Dec 26 '18 at 16:25
  • $\begingroup$ $a_X([])$ will be the identity. Let me write an answer it will be clearer $\endgroup$ Dec 26 '18 at 16:46

You're starting from a $T$-algebra $(X,a_X)$, and you wish to show that it is isomorphic to $F(M)$ for some monoid $M$.

In particular, since $F(M)$ is of the form $(M,h)$ for $h:TM\to M, [m_1,...,m_n]\mapsto m_1...m_n$, then if there is such an isomorphism $f:X\to M$ and if $x,y\in X$, then $h\circ T(f)([x,y]) = h([f(x),f(y)])=f(x)f(y)$ and $h\circ T(f)([x,y] ) = f\circ a_X([x,y])$.

Considering that $f$ is a bijection and thus identifying $M$ and $X$ with it, we get a monoid structure on $X$ such that $a_X([x,y]) = xy$.

Thus now if we want to find $M$, we know what we should do : define multiplication on $X$ by the formula $xy := a_X([x,y])$; and check that this makes $X$ into a monoid such that $F(X) \simeq (X,a_X)$ (actually it will be an equality !)

To prove that $X$ is indeed a monoid with this operation, you will need to use the different properties of the monad and axioms of $T$-algebra.

Associativity will follow from the associativity axiom of $T$-algebras that says that this should commute :

$\require{AMScd} \begin{CD} TTX @>{\mu_X}>> TX\\ @V{T(a_X)}VV @VV{a_X}V\\ TX @>>{a_X}> X \end{CD}$

and the unit will be $a_X([ ])$ and the fact that this is a unit will follow from the associativity axiom for $T$-algebras, together with the unit axiom of $T$-algebras that says that this should commute :

$\require{AMScd} \begin{CD} X @>{\eta_X}>> TX\\ @V{id_X}VV @VV{a_X}V\\ X @>>{id_X}> X \end{CD}$

You then need to prove that $a_X([x_1,...,x_n]) = x_1...x_n$ but this will follow from associativity again. I'll let you check the details.

  • $\begingroup$ To show that F is fully faithful do you not need to verify injectivity/surjectivity on the Hom sets as well? If I understand your answer correctly, you have only shown that F is surjective when viewed as a map of objects... $\endgroup$
    – gen
    Dec 31 '18 at 16:26
  • $\begingroup$ @gen : The OP states "I have shown that this functor is fully faithful" $\endgroup$ Dec 31 '18 at 16:35
  • $\begingroup$ Oh I see, thanks for clarifying! $\endgroup$
    – gen
    Dec 31 '18 at 16:36

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.