The category of $T$ algebras on Set is equivalent to the category of monoids

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?

• Why would you want this map to be injective ? Dec 26 '18 at 14:58
• @Max because I need to show that $F$ is essentially surjective, so I need that $(X,a_X)$ is in the essential range. Dec 26 '18 at 15:09
• 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])$ Dec 26 '18 at 15:13
• @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$? Dec 26 '18 at 16:25
• $a_X([])$ will be the identity. Let me write an answer it will be clearer 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.

• 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...
– gen
Dec 31 '18 at 16:26
• @gen : The OP states "I have shown that this functor is fully faithful" Dec 31 '18 at 16:35
• Oh I see, thanks for clarifying!
– gen
Dec 31 '18 at 16:36