On Wikipedia’s page for Yoneda lemma (https://en.wikipedia.org/wiki/Yoneda_lemma) the authors mentions that the lemma is a vast generalization of the Cayley’s theorem. Whoever has ever seen the usual proof of these theorems has the intuition that there is a kind of similitude between them.
In Cayley’s theorem case you take a function that composes its input by a constant \(g\) and discover that it shifts the element of the group, it sort of rearranges the elements of this group which is another way to say that it’s a member of the symmetric group of \(G\). By varying the \(g\) you end up with a group of functions and this group is included in the group of all symmetric group.
In Yoneda’s lemma case if we consider the Yoneda embedding functor, lifting a morphism yields a function which postpend this morphism to the input of the function, transforming a homset into another homset. If the source and destination homset are the same, we’re again somehow rearranging a set.
While this handwavy explanation suffices to give some intuition, let us dive into a more solid proof.
Group definitions
We recall some basic definitions so that everyone gets to the same point.
A group is a set G with a composition law which we may call $\otimes$ that has the following properties:
- It has a neutral element \(e\) on the left- and right-hand side: for all element \(g\) of \(G\), \(e \otimes g = g \otimes e = g\).
- It is associative : for all \(x, y, z\) we have \((x \otimes y) \otimes z = x \otimes (y \times z)\) which we may abbreviate by omitting the parenthesis as \(x \otimes y \otimes z\).
- And for all element \(x\) there is an inverse noted \(x^{-1}\) such that \( x \otimes x^{-1} = e\).
The symmetric group over \(X\) is the group of function from \(X\) to \(X\) that are bijective: an element of this group can be seen as a « permutation » of all elements of \(X\). We may also call it the group of automorphism of \(X\).
Given a group \(G\) and a set \(X\), an action on group is a function \(\phi: G\times X\to X\) such that :
- For the identity element, \(\phi(e, x) = x\).
- For any element \(x, y\in G\), we say that the composition is compatible: \(\phi ( x \otimes y, z) = \phi (x, \phi (y, z))\).
In a way an action on group is « applying » a group structure to a set. It is obviously an automorphism as an action \(\phi(g, .)\) has an inverse \(\phi(g^{-1}, .)\).
The group of all actions of a group on \(X\) is included in the group of automorphism of \(X\).
Then the Cayley theorem states that a group \(G\) is isomorphic to a subgroup of the symmetric group over \(G\).
Category theory definitions
We recall some basic definitions.
Given a (small) category \(\mathcal{C}\), a homset between x and y is the set of all arrow between object x and y and is noted \(Hom(x, y)\). This is really a set, that is an object of the category \(\textbf{Set}\).
Given an object \(X\), the Hom functor \(Hom(X, -)\) is a functor from \(\mathcal{C}\) to \(\textbf{Set}\) which maps an object \(Y\) to \(Hom(X,Y)\) and which maps an arrow \(f:A\to B\) to a function \(Hom(X,f): Hom(X, A)\to Hom(X, B)\) such that forall arrow \(g\) in \(Hom(X,A)\), we have \(Hom(X,f)(g) = g.f\) (we postpend the function).
The Yoneda embedding \(Y\) takes a step back: it’s a functor that maps an object \(X\) to the Hom functor \(Hom(X, -)\). Any arrow \(f:Y\to X\) maps a functor \(Hom(X, -)\) to a functor \(Hom(Y, -)\) (note that we take the reverse arrow) ; this mapping happens to be a natural transformation.
A functor \(F\) between a category \(\mathcal{C}\) and \(\mathcal{D}\) induces a mapping on homsets : if \(X\) and \(Y\) are objects in \(\mathcal{C}\), there is a mapping \(Hom(X,Y)\to Hom(F(X), F(Y))\). We say that this functor is faithfull if this mapping is injective, full if this mapping is surjective.
There are two versions of the Yoneda lemma available: the first one states that the Yoneda functor is full and faithful. The second one is a bit more generic and states that \(Nat(Hom(X, .), F(.))\) and \(F(X)\) are naturally isomorphic for all X but we won’t use it.
Group in a category
Now we will look at group with a categorical point of view.
A group \(G\) can be regarded as a category with a single arbitrary object and all elements as arrows. Composition, associativity, and existence of an identity morphism are respected by virtue of the group laws. In the following the arbitrary object will be represented by \(\bullet\).
A functor \(F\) between a group and the \(\textbf{Set}\) category is an action on group :
- For every arrow \(f:\bullet\to\bullet\), \(F(f)\) is an arrow from \(F(\bullet)\) in \(\textbf{Set}\) to \(F(\bullet)\), which means it’s a function from a set to itself.
- The identity arrow \(Id_{\bullet}\) is lifted to \(Id_{F(\bullet)}\).
- For all arrow x and y \(\bullet\to\bullet\), \(x . y\) is lifted to \(F(x . y) = F(x) . F(y)\) which is the compatibility property of the action on law.
The converse is also true : given a group action \(\phi: G \times X \to X\), we can build a functor \(F\) by taking \(F(\bullet) = X\), and for \(x\in G, F(x) = \phi(x, .)\). If we got another \(y\) then the compatibility property ensures that \(F(x).F(y) = \phi(x, \phi(y, .)) = \phi(x\otimes y, .) = F(x.y)\).
Proving the connection
We already saw some functors between a group and the \(\textbf{Set}\) category: the hom functors. We even got the Yoneda embedding \(Y\) which is a functor that provides us with such functor.
Let’s apply the Yoneda lemma on our group category’s object: \(Hom(\bullet, \bullet)\to Hom(Y(\bullet), Y(\bullet))\) is an isomorphism.
Now let’s have a closer look at the mapping: the left hand-side is \(Hom(\bullet, \bullet)\), that is all the morphisms of our group as a category. If you remember how we built our group as a category this means this set consists of all the elements of our group.
If we look at the right hand-side of the mapping, \(Hom(Y(\bullet), Y(\bullet))\) are the morphisms of a functor from the group as a category to \(\textbf{Set}\), that is the action of the group on a set.
And this is not any set : the expression of the Yoneda embedding tells us that \(Y(\bullet) = Hom(\bullet, -)\) and again, there is only a single object of the category so we’re talking about \(Hom(\bullet, \bullet)\) here that is the group itself.
If we recap the Yoneda lemma on a group as a category tells us that a group is isomorphic to the group of action of this group on itself. Since the group of action of this group on itself is a subgroup of the group of automorphism of the group, we have proven that a group is isomorphic to a subgroup of the symmetric group of this group.
References
In french : http://www.les-mathematiques.net/phorum/read.php?16,2085554