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.
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 Tg:G→G by Tg(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, Tg is a function from G to G ∀g∈G, and it is easy to verify that Tg is also a bijection ∀g∈G, thus making Tg a permutation on G. Now let G* = {Tg : g∈G}. Then G* is a group under the operation of function composition. I will verify this, but only briefly. Choose Tg,Th∈G*, let x∈G, and observe that (Tg∘Th)(x) = Tg(Th(x)) = Tg(h∙x) = g∙(h∙x) = (g∙h)∙x = Tg∙h(x). Then Tg∘Th = Tg∙h and Tg∘Th∈G* which gives closure. Since Tg∘Th = Tg∙h, it is then clear that Te is the identity of G* and that (Tg)-1 = Tg-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) = Tg ∀g∈G. Suppose that g,h∈G and θ(g) = θ(h). Then Tg = Th and Tg(e) = Th(e) so g∙e = h∙e giving g = h. Thus θ is injective. Since G* = {Tg : g∈G}, it is clear that ∀Tg∈G*, θ(g) = Tg so θ is surjective. To see that θ is operation-preserving, observe that ∀a,b∈G, θ(a∙b) = Ta∙b = Ta∘Tb = θ(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
No comments:
Post a Comment