Cayley's Theorem

Today we're going to culminate the last few posts into a theorem that combines the idea of symmetric groups and isomorphisms into something quite useful. I'm going to present a proof because its a good example of a constructive proof. Cayley's theorem claims the existence of something (particularly a permutation group isomorphic to a given group) and most theorems about existence only show a theoretical existence, but constructive proofs show that something exists by actually constructing the thing for which they're claiming existence. The statement and proof of Cayley's Theorem is given below.

Theorem: Cayley's Theorem
Every group is isomorphic to a group of permutations.

Proof:

Before we can prove the isomporphism, we must first build this permutation group. ∀g∈G, define T_g:G→G by T_g(x) = g∙x ∀x∈G. We recall that the definition of a permutation is a bijection from a set to itself. G is a set, T_g is a function from G to G ∀g∈G, and it is easy to verify that T_g is also a bijection ∀g∈G, thus making T_g a permutation on G. Now let G* = {T_g : g∈G}. Then G* is a group under the operation of function composition. I will verify this, but only briefly. Choose T_g,T_h∈G*, let x∈G, and observe that (T_g∘T_h)(x) = T_g(T_h(x)) = T_g(h∙x) = g∙(h∙x) = (g∙h)∙x = T_g∙h(x). Then T_g∘T_h = T_g∙h and T_g∘T_h∈G* which gives closure. Since T_g∘T_h = T_g∙h, it is then clear that T_e is the identity of G* and that (T_g)^-1 = T_g^-1. Finally, all function composition is associative, so G* is a group.

The isomporphism between G and G* is now obvious - define θ:G→G* by θ(g) = T_g ∀g∈G. Suppose that g,h∈G and θ(g) = θ(h). Then T_g = T_h and T_g(e) = T_h(e) so g∙e = h∙e giving g = h. Thus θ is injective. Since G* = {T_g : g∈G}, it is clear that ∀T_g∈G*, θ(g) = T_g so θ is surjective. To see that θ is operation-preserving, observe that ∀a,b∈G, θ(a∙b) = T_a∙b = T_a∘T_b = θ(a)∘θ(b). Finally, θ is an isomporphism and G ≈ G* where G* is a group of permutations, as desired.

Cayley's theorem tells us some neat things. Note that it doesn't say that every group is isomorphic to a symmetric group, but that it is isomorphic to some permutation group. I know I never formally defined a permutation group, but as you might think, its some set of permutations that form a group under function composition, and I did define a permutation. Now suppose G is any arbitrary group, Cayley's Theorem tells us that G ≈ G* where G* is a permutation group and, in particular, G* is a group of permutations on the set G. When we first discussed permutations of symmetric groups, we thought of them as "rearrangements" of the set Ω_n. Similarly, we can think of the permutations in G* as rearrangements of the elements of G. So now we can assign each element of G an integer from Ω_|G| and in this manner, each element of G* corresponds to an element of S_|G|. This correspondence is certainly injective and operation-preserving, but may or may not be surjective. It may require a bit of an imaginative leap of faith, but what this gives us is that G* ≈ H where H is some subgroup of S_|G|. The final result here, is that any group is isomorphic to some subgroup of a symmetric group (that is that G≈G*≈H where H is a subgroup of a symmetric group). This is important because even the most abstract of groups can be represented in a very concrete way. And that is very, very cool.

References

Previous Related Post: Properties of Isomorphisms

Text Reference: Gallain Chapter 6

Wikipedia: Cayley's Theorem