Make your own free website on Tripod.com
Let G and H be groups. A function f :GmapsH which satisfies (1) for all g, g' element of G is called a homomorphism of G into H. If f:GmapsH is a homomorphism. The kernel of f is ker(f) = {x element of G | f(x) = 1H}. Let G1 and G2 be groups. An isomorphism from G1 to G2 is an injection phi:G1mapsG2 such that phi(a · b) = phi(a) · phi(b)  (a,b element ofG1 if phi is also surjective G1 is isomorphic to G2). A function f : AmapsB is said to be injective (or one to one) if whenever f(x) = f(y), we have x = y. A function that is both one-to-one and onto, that is if f(x) = f(y) then x = y, and for every y of the domain there is an x of the range so that f(x) = y. A function f : AmapsB is said to be surjective (or onto) if for every y element of B there exists x element of A such that f(x) = y.

Cayley's Theorem

We have stated that on of the main objectives of group theory is to write down a complete list of non-isomorphic groups. At first, such a task appears hopeless. For, as we have seen, groups pop up in some very unexpected places and, therefore, if we set out to compile a list of all non-isomorphic groups, we would hardly begin to know where to look. The following theorem of Cayley solves this dilemma.

Theorem 1: Every group is isomorphic to a subgroup of a permutation group

Proof: Let G be a group, g element of G. define

rhog:G maps G
rhog(x) = xg-1   (x element of G).

If rhog(x) = rhog(y), then xg-1 = yg-1, so that x = y. Therefore, g is an injection. If y element of G, then rhog(yg) = yg · g-1 = y. Therefore, rhog is a surjection. Thus, since rhog is a bijection, rhog is a permutation of the elements of the set G, and rhog element of SG. Let us consider the mapping

G maps SG

defined by

(1)
g maps rhog

Since rhogg' = x(gg')-1 = rhogrhog'(x), the mapping (1) is a homomorphism. But rho = 1SG if and only if x · g = x for all x element of G, which occurs if and only if g = 1G. Therefore, the kernel of the homomorphism (1) is 1G, and therefore the mapping (1) is an injection. Thus we have shown that G is isomorphic to a subgroup of SG.

What Cayley's theorem tells us is that permutation groups and their subgroups are all the groups that can exist. Unfortunately, the problem of classifying the subgroups of a permutation group is extremely complicated, even in the case of a finite permutation group. Therefore, Cayley's theorem does not allow us to easily identify a complete list of groups.

The above argument actually proves somewhat more than claimed. For if G is finite, having order n, then G is isomorphic to a subgroup of SG. Therefore we have

Corollary 2: If G has finite order n, then G is isomorphic to a subgroup of Sn.