M-sets and Yoneda for monoids

The Yoneda lemma says that for a category $\mathbb{C}$, an object $C$ in $\mathbb{C}$, and a functor $S:\mathbb{C}\to\textbf{Sets}$, $\operatorname{Nat}(\operatorname{hom}(C,-),S)$ is in bijection with $S(C)$. These bijections are given by $\alpha: \operatorname{Nat}(\operatorname{hom}(C,-),S)\to S(C)$ and $\beta: S(C) \to \operatorname{Nat}(\operatorname{hom}(C,-),S)$ defined as $\alpha(\sigma)=\sigma_ {C}(1_ {C})$ and $\beta(c)_ {A}(f)=S(f)(c)$¹. This is the covariant form of the Yoneda lemma. There is also a contravariant form that specifies the bijective correspondence $\operatorname{Nat}(\operatorname{hom}(-,C),S)\approx S(C)$. Setting $S=\operatorname{hom}(-,C’)$, the Yoneda lemma tells us that natural transformations between the functors $\operatorname{hom}(-,C)$ and $\operatorname{hom}(-,C’)$ are in bijection with elements of the set $\operatorname{hom}(C,C’)$.

Let $M$ be a monoid, then a left $M$-set $\mathcal{X}$ is an object in the functor category $\textbf{Sets}^M$¹. Let $\mathcal{X}:M\to\textbf{Sets}$ be a covariant functor then $\mathcal{X}$ specifies an object $X$ in $\textbf{Sets}$, the image of the unique object of $M$ under $\mathcal{X}$, together with an endomorphism $\mathcal{X}(u):X\to X$ for each morphism $u$ of $M$ (i.e. an element of the monoid $M$) that maps $x\mapsto ux$ such that $\mathcal{X}(u)\mathcal{X}(v)=\mathcal{X}(uv)$ and $\mathcal{X}(e)=1_ {X}$. Similarly, a contravariant functor $\mathcal{X}:M^{op}\to\textbf{Sets}$ is a right $M$-set (or equivalently, an $M^{op}$-set), but must instead satisfy $\mathcal{X}(vu) = \mathcal{X}(u)\mathcal{X}(v)$. When we refer to “$M$-sets” we mean left $M$-sets.

The monoid $M$ itself is an $M$-set. Since $M$, viewed as a category, has only a single object, the set $\operatorname{hom}_ {M}({M},{M})$ is the set of $M$-set endomorphisms of ${M}$ in $M$ and so $\operatorname{hom}_ {M}({M},{M})=M$. Note that the set $\operatorname{hom}_ {M}({M},{M})$ inherits the monoid structure from the properties of composition of morphisms in a category. The covariant functor $\operatorname{hom}_ {M}({M},-):M\to \textbf{Sets}$ is a $M$-set $U(M)$ (where $U:\textbf{Mon}\to\textbf{Sets}$ is the forgetful functor) with $M$ acting on $U(M)$ by left multiplication since for $u\in M$, $\operatorname{hom}_ {M}({M},u):M\to M$ is defined by $\operatorname{hom}_ {M}({M},u)(x)=ux$ for all $x\in M$. Similarly, the contravariant functor $\operatorname{hom}_ {M}(-,{M}):M^{op}\to \textbf{Sets}$ is a $M$-set $U(M)$ with $M$ acting on $U(M)$ by right multiplication. As a result, we denote the $M$-set $U(M)$ as $M$.

Consider an $M$-set $S:M\to \textbf{Sets}$, then a natural transformation $\tau : M \to S$ is an $M$-set homomorphism from $M$ to $S$¹. The map $\tau : M\to S$ is the unique component of the natural transformation. The naturality condition is satisfied since $\tau$ is a $M$-set homomorphism, that is, for $u$ a morphism in $M$, $$\tau (M(u)(x))=\tau (ux)=u\tau (x)=S(u)(\tau (x))$$ for all $x\in M$.

Now, we can form the set $\operatorname{hom}_ {\textbf{Sets}^M}(M,S)$ which consists of morphisms $M\to S$ of $M$-sets (i.e. $M$-set homomorphisms). These morphisms are natural transformations of the functors $M$ and $S$, so $$\operatorname{hom}_ {\textbf{Sets}^M}(M,S)=\operatorname{Nat}(M,S)=\operatorname{Nat}(\operatorname{hom}_ {M}({M},-),S)$$ since we can represent $M$ with the functor $\operatorname{hom}_ {M}({M},-)$ as every monoid acts on itself by left or right multiplication. Hence by the Yoneda lemma, $$\operatorname{hom}_ {\textbf{Sets}^M}(M,S) = \operatorname{Nat}(\operatorname{hom}_ {M}({M},-),S)\approx S({M})=S.$$ We have proved the following result,

$M$-set homomorphisms $M\to S$ correspond bijectively to elements of $S$.

This bijection is given by the maps $\alpha:\operatorname{hom}_ {\textbf{Sets}^M}(M,S)\to S$ and $\beta:S\to\operatorname{hom}_ {\textbf{Sets}^M}(M,S)$ defined by $$\alpha(\sigma)=\sigma(e)\text{ and,}$$$$\beta(s)(x)=S(x)(s)=xs.$$ They are inverse to each other since $$\alpha(\beta(s)(x))=\beta(s)(e)=es=s\text{ and,}$$$$\beta(\alpha(\sigma))(x)=S(x)(\alpha(\sigma))=x\alpha(\sigma)=x\sigma(e)=\sigma(xe)=\sigma(x).$$ We can interpret this bijection as follows, the choice of $\sigma(e)$ determines every other value $\sigma(x)$ for $x\in M$ since $$\sigma(x)=\sigma(xe)=x\sigma(e)$$ as $\sigma$ is an $M$-set homomorphism².

Cayley’s Theorem arises as a special case of the above result. For a group $G$, set $M=S=G$ then we have that $$\operatorname{hom}(G,G)\approx G$$ and since the set $\operatorname{hom}(G,G)$ contains automorphisms of $G$, it is a subgroup of the group of all permutations on $G$.

There is a counterpart to the bijection $\operatorname{hom}(M,S)\approx S$ in linear algebra. Consider a field $\mathbb{K}$ and a $\mathbb{K}$-vector space $V$, then $\operatorname{hom}(\mathbb{K},V)\approx V$. This bijection is given by $\alpha:\operatorname{hom}(\mathbb{K},V)\to V$ defined as $\alpha(\sigma)=\sigma(1)$. The map $\alpha$ is clearly linear and injective. To see that it is surjective, notice that for any $v\in V$, there is a map $\sigma\in\operatorname{hom}(\mathbb{K},V)$ that maps the multiplicative identity $1$ onto $v$, namely, $\sigma(k)=kv$. The inverse map $\beta:V\to\operatorname{hom}(\mathbb{K},V)$ is given by $\beta(v)(k)=kv$, and we have that $$\alpha(\beta(v)(k))=\beta(v)(1)=1v=v\text{ and,}$$$$\beta(\alpha(\sigma))(k)=\beta(\sigma(1))(k)=k\sigma(1)=\sigma(k).$$ However, we are not able to obtain this result from the Yoneda lemma as it has been formulated here. A stronger result, the enriched Yoneda lemma, is required³.

Let $\mathbb{C}$ be a category, then the Yoneda embedding is the functor $Y:\mathbb{C}\to\textbf{Sets}^{\mathbb{C}^{op}}$ that maps every object $C$ in $\mathbb{C}$ to the functor $\operatorname{hom}(-,C):\mathbb{C}^{op}\to\textbf{Sets}$ and every morphism $c:C\to C’$ in $\mathbb{C}$ to the natural transformation $\operatorname{hom}(-,c):\operatorname{hom}(-,C)\to\operatorname{hom}(-,C’)$, where each component of the natural transformation is defined by $\operatorname{hom}(-,c)_ {A}=\operatorname{hom}(A,c)$ for each object $A$ in $\mathbb{C}$ (i.e. postcomposition with $c$). The Yoneda embedding is fully faithful which follows from the Yoneda lemma¹. This means that the functor $Y$ preserves the relationships that $C$ shares with every other object in $\mathbb{C}$ and so $Y$ fully faithfully embeds $\mathbb{C}$ into $\textbf{Sets}^{\mathbb{C}^{op}}$. That is, for every natural transformation $\tau:\operatorname{hom}(-,C)\to\operatorname{hom}(-,C’)$ there is exactly one morphism $c:C\to C’$ such that $\operatorname{hom}(-,c)=\tau$. Using this embedding, we are able to work with any category $\mathbb{C}$ by embedding it in $\textbf{Sets}^{\mathbb{C}^{op}}$ which, in general, has `nicer’ properties and is easier to work with³.

We are able to obtain the Yoneda embedding by using the Yoneda lemma in the case where $S=\operatorname{hom}(-,C’)$ for some object $C’$ in $\mathbb{C}$ since the Yoneda lemma says that $\operatorname{Nat}(\operatorname{hom}(-,C),\operatorname{hom}(-,C’))$ is in bijection with $\operatorname{hom}(C,C’)$, which is exactly the Yoneda embedding which assigns to each morphism $c:C\to C’$ in $\mathbb{C}$ the natural transformation $\operatorname{hom}(-,c)$ in $\textbf{Sets}^{\mathbb{C}^{op}}$.

Since the Yoneda embedding $Y$ fully faithfully embeds $\mathbb{C}$ into $\textbf{Sets}^{\mathbb{C}^{op}}$, we have that, for any two objects $C$ and $C’$ in $\mathbb{C}$, $$\operatorname{Nat}(Y(C),Y(C’))=\operatorname{Nat}(\operatorname{hom}(-,C),\operatorname{hom}(-,C’))\approx \operatorname{hom}(C,C’)$$ and hence, there is a relationship $\mathbb{C}\longleftrightarrow\textbf{Sets}^{\mathbb{C}^{op}}\longleftrightarrow\textbf{Sets}$ that allows us to characterise an object $C$ in $\mathbb{C}$ by its relationships to all other objects $C’$ in $\mathbb{C}$. That is, the properties of any object $C$ in $\mathbb{C}$ are encoded in the sets $\operatorname{hom}(C,C’)$ for each $C’$ in $\mathbb{C}$.

Let $\hat{M}$ be the monoid of all maps $M\to M$ (not just monoid homomorphisms) and $f:M\to\hat{M}$ map each $x\in M$ to the map $f(x):M\to M$ defined by $f(x)(y)=xy$. Let $Y: M\to\textbf{Sets}^{M^{op}}$ be the Yoneda embedding of $M$ into $\textbf{Sets}^{M^{op}}$. Then $f(x) = \operatorname{hom}({M},x) = \operatorname{hom}(-,x)=Y(x)$ and $Y({M})=\operatorname{hom}(-,{M})=\operatorname{hom}({M},{M})=M$ since $M$ is a single object category. Now, since $Y$ is fully faithful, the induced functor, $$Y_ {{M},{M}}:\operatorname{hom}_ {M}({M},{M})\to\operatorname{hom}_ {\textbf{Sets}^{M^{op}}}(Y({M}),Y({M}))$$ is bijective. But, $\operatorname{hom}_ {M}({M},{M})=M$ and $$\operatorname{hom}_ {\textbf{Sets}^{M^{op}}}(Y({M}),Y({M}))=\operatorname{hom}_ {\textbf{Sets}^{M^{op}}}(M,M)\subset\operatorname{hom}_ {\textbf{Sets}}(M,M) = \hat{M}$$ since $Y({M})$ is the $M^{op}$-set $U(M)$ which is $M$ viewed as a right $M$-set. So we have that the induced functor $$Y_ {{M},{M}}:M\to\hat{M},$$ defined by $Y_ {{M},{M}}(x) =Y(x)= f(x)$, is bijective onto $\operatorname{hom}_ {\textbf{Sets}^{M^{op}}}(M,M)$. However, it is only injective into $\hat{M}$. Now, since $f(uv)(y)=(uv)y=u(vy)=f(u)(vy)=f(u)f(v)(y)$, $f:M\to\hat{M}$ is an injective homomorphism of monoids. The image of $f$ is the image of the induced functor which is just the set $\operatorname{hom}_ {\textbf{Sets}^{M^{op}}}(M,M)$ of all $M^{op}$-set homomorphisms from $M$ to $M$ (or equivalently, right $M$-set homomorphisms from $M$ to $M$).