Section 1.3. Groups 23 (ii) A direct product of semigroups (or monoids) with cooordinatewise operation is again a semigroup (or monoid). In particular, the set Nn of all n-tuples of natural numbers is a commutative additive monoid. (iii) The set of integers Z is a monoid under multiplication, as are Q, R, and C. There are noncommutative monoids for example, Matn(R), the set of all n × n matrices with real entries, is a multiplicative monoid. Corollary 1.25 (Generalized Associativity). If S is a semigroup and a1,a2, . . . , an S, then the expression a1a2 · · · an needs no parentheses. Proof. The proof of Theorem 1.20 assumes neither the existence of an identity element nor the existence of inverses. Can two powers of an element a in a group coincide? Can am = an for m = n? If so, then ama−n = am−n = 1. Definition. Let G be a group and let a G. If ak = 1 for some k 1, then the smallest such exponent k 1 is called the order of a if no such power exists, then we say that a has infinite order. In any group G, the identity has order 1, and it is the only element of order 1. An element has order 2 if and only if it is equal to its own inverse for example, (1 2) has order 2 in Sn. The additive group of integers, Z, is a group, and 3 is an element in it having infinite order (because 3 + 3 + · · · + 3 = 3n = 0 if n 0). In fact, every nonzero element in Z has infinite order. The definition of order says that if x has order n and xm = 1 for some positive integer m, then n m. The next theorem says that n must be a divisor of m. Proposition 1.26. If a G is an element of order n, then am = 1 if and only if n | m. Proof. If m = nk, then am = ank = (an)k = 1k = 1. Conversely, assume that am = 1. The Division Algorithm provides integers q and r with m = nq + r, where 0 r n. It follows that ar = am−nq = ama−nq = 1. If r 0, then we contradict n being the smallest positive integer with an = 1. Hence, r = 0 and n | m. What is the order of a permutation in Sn? Proposition 1.27. Let α Sn. (i) If α is an r-cycle, then α has order r. (ii) If α = β1 · · · βt is a product of disjoint ri-cycles βi, then the order of α is lcm{r1,...,rt}.13 (iii) If p is prime, then α has order p if and only if it is a p-cycle or a product of disjoint p-cycles. Proof. (i) This is Exercise 1.13 on page 15. 13The least common multiple is abbreviated to lcm.
Previous Page Next Page