6 CHAPTER 1 IB Let X be an arbitrary nonempty set. We denote by Sym(X) the set of all bijections from X to itself. (These bijections on X are also called permutations, and if X is finite, this is, in fact, the more common term.) The object Sym(X) is called the symmetric group on X. (Note that if X is finite, containing n elements, say, then Sym(X) consists of precisely n! permutations.) (1.2) COROLLARY. Let G = Sym(X). a. ix e G. b. g~l exists and lies in G for each g G. c. gh G for each g,h e G. Proof. Part (a) is immediate, and (b) follows from Lemma 1.1. It is not hard to prove (c) directly, but we prefer the following argument. Given g, h e G, we see that (gh)(h-lg-l) = i = (h-lg-l)gh, and thus gh has a left and right inverse. It follows by Lemma 1.1 that gh e Sym(X). (1.3) DEFINITION. Let X be any set. A permutation group on X is any nonempty subset G c Sym(X) such that i. g~l e G for each g e G and ii. G is closed under function composition. Note that for g e G, there is no question that the mapping g~l exists and lies in Sym(X). The point of condition (i) is that g~l actually lies in the subset G. Conditions (i) and (ii), together with the assumption that G ^ 0, imply that ix G, and so this need not be assumed. Given a nonempty set G of mappings on some set X, perhaps the best strategy for showing that G is a permutation group is first to verify that each element g e G has both a left and a right inverse in G. From this it follows that G c Sym(X) and this condition need not be verified separately. All that remains, then, is to check the closure condition. Some obvious examples of permutation groups are Sym(X) and the singleton set {ix} for arbitrary nonempty X. We devote the next few pages to descriptions of several more interesting examples. Consider a square ABCD and let X = {A, B, C, D} be its vertex set (see Figure 1.1). Within Sym(X), let G denote the set of permutations of X that can be realized by a physical motion of the square through 3-space. For instance, imagine the square being rotated 90° counterclockwise about its center. This brings A to the position formerly occupied by D, and so on, and the associated element of G is the map g:Ah+D\-+C\-B\-+A. Similarly, a "flip" about the vertical axis v yields the map h : A M* B I- A C H D H C . If we first do the rotation and then the flip, the result is the same as a flip about the diagonal axis d, and the corresponding element of G is precisely the composition gh : A \-+ C \- A, B \-+ B\ D \-+ D.
Previous Page Next Page