Martin's Blog

Cayley's Theorem and the Yoneda Lemma

Posted by Martin Orr on Sunday, 10 May 2009 at 16:07

When I wrote my first post on Cayley's theorem, I noticed that Wikipedia claims that the Yoneda lemma is "a vast generalisation of Cayley's theorem". In this post I will try to understand why, and end up concluding that this is probably false.

The general statement of the Yoneda lemma is:

Let C be a category, T : C \to \mathrm{Set} a functor and x an object in C. Then there is a bijection y : \mathop{\mathrm{Nat}}(\mathop{\mathrm{Hom}}(x, -), T) \to Tx, natural in T and x.

(Here Nat(S, T) is the set of natural transformations from functor S to functor T. Don't worry about "natural in T and x" for now.)

Now we will apply this to the case of groups. Let C be the category corresponding to the group G. Recall that C has only one object * and functors C \to \mathrm{Set} correspond to G-sets. If S, T are functors C \to \mathrm{Set} corresponding to G-sets X, Y, then Nat(S, T) corresponds to the set of G-homomorphisms X \to Y.

To apply the Yoneda lemma to C, we must take x = * so \mathop{\mathrm{Hom}}(x, -) corresponds to the regular action of G on itself. Let X be a G-set corresponding to the functor T : C \to \mathrm{Set}. Then the Yoneda lemma tells us that the set of G-homomorphisms G \to X is in bijection with X itself.

This result is clear without any category theory: to specify a G-homomorphism u : G \to X, you just pick an element e of X for u(1). Indeed we saw this before when describing (G, 1) as a universal pointed G-set.

So the Yoneda lemma for groups re-expresses the universality of the regular action, showing that this is not an accident but comes from the fact that the regular action is just a way of viewing the functor \mathop{\mathrm{Hom}}(*, -).

Now in what sense is this a generalisation of Cayley's theorem? I am not convinced that it is, although it may depend on precisely how you state Cayley's theorem. Let's use Wikipedia's statement:

Every group G is isomorphic to a subgroup of the symmetric group on G.

In terms of actions, this says that G acts faithfully on itself. In terms of category theory, it says that \mathop{\mathrm{Hom}}(*, -) is a faithful functor C \to \mathrm{Set}.

This does not generalise to a statement about arbitrary categories because Hom-functors are not always faithful. Indeed, the obvious generalisation of Cayley's theorem to monoids, "Every monoid M is isomorphic to a submonoid of the symmetric monoid on M", is false. (A monoid is an object satisfying all the axioms of a group except the existence of inverses, or equivalently any one-object category. For a counter-example, consider the monoid {1, x} with xx = x.)

The problem here seems to be that "faithful functor" is not a terribly nice condition (as James pointed out). The right way to characterise the regular action categorically (which is generalised by Yoneda) is by the universal property. But in terms of group actions, the universal property says that the regular action is free and transitive, much stronger than faithful.

So I don't think that the Yoneda lemma does generalise Cayley's theorem, although it does generalise the universal property description of the regular action of G.

Tags categories, groups, maths, yoneda


  1. Naturality in the Yoneda lemma for groups From Martin's Blog

    In my last post on the Yoneda lemma for groups, I ignored the naturality part of the lemma. I want to work in detail what this means once - it is a lot of fiddly composing of morphisms and I probably won’t do it again (at least in public). I...


No comments.

Post a comment

Markdown syntax with embedded LaTeX.
Type LaTeX between dollar signs, and enclose them between backticks to protect it from Markdown.
All comments are subject to moderation before they appear on the blog.