Section 1.2. Permutations 5 (ii) Find the complex roots of f(x) = x4 2x2 + 8x 3. 1.4. Show that the quadratic formula does not hold for f(x) = ax2 + bx + c if we view the coefficients a, b, c as lying in the integers mod 2. Section 1.2. Permutations For Galois, groups consisted of certain permutations (of the roots of a polynomial), and groups of permutations remain important today. Definition. A permutation of a set X is a bijection2 from X to itself. A rearrangement of a set X is a list, with no repetitions, of all the elements of X. For example, there are six rearrangements of X = {1, 2, 3}: 123 132 213 231 312 321. Now let X = {1, 2,...,n}. All we can do with such lists is count the number of them there are exactly n! rearrangements of the n-element set X. Now a rearrangement i1,i2,...,in of X determines a function α: X X, namely, α(1) = i1,α(2) = i2,...,α(n) = in. For example, the rearrangement 213 determines the function α with α(1) = 2, α(2) = 1, and α(3) = 3. We use a two- rowed notation to denote the function corresponding to a rearrangement if α(j) is the jth item on the list, then α = 1 2 . . . j . . . n α(1) α(2) . . . α(j) . . . α(n) . That a list contains all the elements of X says that the corresponding function α is surjective, for the bottom row is im α 3 that there are no repetitions on the list says that distinct points have distinct values that is, α is injective. Thus, each list determines a bijection α: X X that is, each rearrangement determines a per- mutation. Conversely, every permutation α determines a rearrangement, namely, the list α(1), α(2),...,α(n) displayed as the bottom row. Therefore, rearrange- ment and permutation are simply different ways of describing the same thing. The advantage of viewing permutations as functions, however, is that they can now be composed and, by Exercise 1.7 on page 14, their composite is also a permutation. Definition. The family of all the permutations of a set X, denoted by SX , is called the symmetric group on X. We denote SX by Sn when X = {1, 2,...,n}, and we call it the symmetric group on n letters. The identity permutation 1X is usually denoted by (1). 2A function f : X Y is an injection (or is one-to-one) if x, x X and x = x implies f(x) = f(x ) equivalently, f(x) = f(x ) implies x = x . A function g : Y Z is a surjection (or is onto) if, for each z Z, there exists y Y with z = g(y). A function is a bijection (or is a one-one correspondence) if it is both an injection and a surjection. The identity function on a set X, denoted by 1X : X X, is given by 1X : x x for all x X it is a bijection. 3If f : X Y is a function, then X is called its domain, Y is called its target and, if x X, then f(x) is called the value. The image of f, denoted by im f, is the subset of the target Y consisting of all the values. Thus, im f Y , and im f = Y if and only if f is surjective.
Previous Page Next Page