Let G and H be groups. A function f :GH which satisfies (1) for all g, g' G is called a homomorphism of G into H. If f:GH is a homomorphism. The kernel of f is ker(f) = {x G | f(x) = 1H}. Let G1 and G2 be groups. An isomorphism from G1 to G2 is an injection :G1G2 such that (a · b) = (a) · (b)  (a,b G1 if is also surjective G1 is isomorphic to G2). A function f : AB 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 : AB is said to be surjective (or onto) if for every y B there exists x 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 G. define

g:G G
g(x) = xg-1   (x G).

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

G SG

defined by

(1)
g g

Since gg' = x(gg')-1 = gg'(x), the mapping (1) is a homomorphism. But = 1SG if and only if x · g = x for all x 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.