Group

Abstract algebra/Groups

1

Abstract algebra/Groups A group is a set with a number of special properties. Groups are useful in studying many different areas of mathematics. Many sets we encounter in mathematics have some kind of structure when we associate it with an operation. For example, the integers have a lot of properties when we associate it with multiplication, or with addition. Group theory is the study of groups, their structure, and their nature.

Definitions and notations A group is a set, say properties: • closure under : If two elements from

, and a binary operation which we call , are in , then , and is not in

, satisfying the following

is also in . This means that if we have , can't be a group.

• associativity of : If , , are elements of , , as we have for addition and multiplication but not subtraction of natural numbers. • existence of an identity element: There is an element in , which we write , such that for any in , . We call the identity, which we sometimes also notate , , or . • existence of inverses: For any in , there exists some element in , such that . We usually write as . Any set with a binary operator that satisfies these four properties is a group. Technically, a group is a set and an operation, which can be written as an ordered pair , although it is common practice to speak of the group as the set . It is important to note, however, that one set can form two different groups under different operations. Note that the identity is unique, for if e and e' are identities, then e=ee'=e'.

Terminology We shall call the group additive if the operation is a kind of addition. In this case, it is standard to denote the operation by , the identity by , and the inverse of in by . We shall call the group multiplicative if the operation is a kind of multiplication. In this case we often use or a dot to denote the operation and write as for brevity. We often denote the identity by or , and the inverse of in by . Note that in our group axioms above we don't assume commutativity (which means that if we have any and , ), a property we're used to having when doing algebra on the real numbers. This property holds in some groups, but not others; if it holds for a particular group, we call that group abelian in honor of the mathematician Niels Abel. It is a convention that one only speaks of an additive group when the group is abelian (this is because there are plenty of common examples of non-commutative multiplication such as matrix multiplication, but none of addition). We call the number of elements in the set (that is, the cardinality of ) the order of the group, and we denote it (also or even , though we will use ). Groups can have finite or infinite order, and we call them finite and infinite groups respectively. Additionally, the order of an element a within G is the first natural number n such that is

Abstract algebra/Groups the identity. If no such n exists, then it is considered of infinite order, and all powers of a are different.

Examples Let us look at some simple finite groups to see how these rules apply, and then look at cases of some infinite groups.

(Z2,+) Z2={0,1} (see group table) is the set of remainders when dividing integers by 2. There are only two such possible remainders, 0 and 1. So in Z2, we have two elements {0,1}. This set is called the set of integers modulo 2. Note that an integer is equal to its remainder modulo 2. For example, 9=1 modulo 2 because This picture illustrates how the hours on a clock form a group under modular addition. when you divide 9 by 2 you end up with a remainder of 1. Let's denote the operation of addition modulo 2 by "+", defined as the usual addition of integers. So is (Z2,+) a group? Let us go through the requirements: • Closure: Can be verified quickly by going through all possible cases: 0+0=0, 0+1=1, 1+0=1, 1+1=0. Thus closure holds. • Associativity: a+(b+c)=(a+b)+c (a proof by going through all possible cases is not difficult, you should check for yourself). Associativity holds. • Identity: 0+0=0, 1+0=1, 0+1=1, so 0 is the identity element. Thus an identity exists, and is in fact 0. • Inverses: 1+1=2=0 modulo 2, so 1 is the inverse of 1. 0+0=0, so 0 is the inverse of 0. Since 0 and 1 are the only elements, every element thus has an inverse. Thus inverses exist. We have shown that each property of groups is satisfied. So (Z2,+) is a group. Moreover, each element is its own inverse, and the identity is 0. In the same way it can be shown that Zm={0,1,...m-1}, the set of remainders when dividing integers by m is also a group. The operation is addition modulo m.

( (Z5)*, × )

In (Z5)*, (see group table) which means Z5 without zero, we have {1,2,3,4}. These are just the elements of Z5 with multiplicative inverses (see Number theory). Take × to be regular multiplication modulo 5. Again, let us go through the requirements: • Closure: Can be verified quickly by inspection: e.g. 3×4=12=2 modulo 5. The remaining cases can be easily done as well. Thus closure holds.

2

Abstract algebra/Groups • Associativity: a×(b×c)=(a×b)×c (again, a proof by cases is not difficult). Associativity holds. • Identity: 1×1=1, 1×2=2, 1×3=3, 1×4=4. So 1 is the identity element for multiplication. Thus an identity exists. • Inverses: 1×1=1, so 1 is the inverse of 1. 2×3=6=1 modulo 5, so 2 and 3 are inverses of each other. And 4×4=16=1 modulo 5, so 4 is its own inverse. Thus inverses exist. Therefore ((Z5)*, ×) is a group. Note: Z5={0,1,2,3,4} is the additive group of integers modulo 5 and (Z5)*={1,2,3,4} is the multiplicative group of integers modulo 5. The multiplicative group is just the additive group without 0. The reason for this is because to form a group we need each element to have an inverse. But 0 does not have a multiplicative inverse (that is, there is no integer a such that 0×a=a×0=1), thus we exclude it to form the multiplicative group.

(Z, +) The integers form a group with the operation of addition +. Again, to show this, we must simply check that the four group axioms above, are satisfied. • Closure: We require that if a and b are integers, then a+b is an integer. But this is true by definition. Closure holds. • Associativity: We require that if a, b and c are integers, then (a+b)+c=a+(b+c). But again, we know this is true from normal addition. Thus associativity holds. • Identity: 0 is the identity since 0+a=a+0=a for any integer a. Thus an identity exists. • Inverses: a has inverse -a, for -a+a=a+-a=0 for any integer a. Thus inverses exist. So (Z,+) is a group.

(Q, ×) Q is the set of all rational numbers; that is numbers that can be formed as the ratio of two integers, . (Q, ×) is not a group. The closure, associative and identity axioms hold, but since 0 ∈ Q, the inverse of 0 would have to be 1/0 which has no meaning; 0 does not have an inverse, so (Q, ×) is not a group. If we instead take Q and remove 0, we do get a group. However it is a kind of object known as a monoid, which is basically a "group without inverses". There are several other types of objects like this (e.g. "groupoids" and "semigroups",) obeying some of the group properties but not others. We won't cover them in this section, though.

Permutations Groups can be more than just abstractions of numbers. Let us consider permutations: a permutation is a rearrangement of some symbols, so that these symbols are in a different order. So, for example, a permutation of (a, b, c) could be (b, c, a). We've rearranged (a, b, c) so a is last. For the moment, let's write a permutation of (a, b, c) by using an arrow, so the above permutation can be written as (a, b, c) → (b, c, a). We could even give this permutation a name, so, we could say that (a, b, c) → (b, c, a) is a permutation p.

3

Abstract algebra/Groups

4

The set of permutations with three elements forms a group. If we take * to be our operation, then let x*y mean "do y, and then do x" on the order of the three elements. For example, if we let: x represent (a, b, c) → (c, b, a), and y represent (a, b, c) → (a, c, b), then we have: x*y first turns (a, b, c) into (a, c, b) (remember we do y first), and then turns that into (b, c, a). Note: The reason we do y first instead of x may seem strange, but that is because this operation is based on the composition of functions. • closure: All rearrangements of three symbols are also rearrangements; something like (a,b,c) → (a,a,b) can not happen. • associativity: This can be verified by inspection. • identity: (a,b,c) → (a,b,c). • inverses: This can be verified by inspection. If we permute something, we can obviously undo what we did to get what we started with. If we flip the first two elements around, we can just flip them again to undo what we did. The group of all permutations on n objects, ie., {1,...,n}, is an important group. It is called the symmetric group and is written Sn, and has order n! (n factorial). We can extend this to permutations of any set S - in this case we write Sym(S). Notice: This is a perfect example of a group that is not abelian. See from the example above that: whereas, own.)This is generally true of most permutations.

. (Try verifying this on your

Subgroups With other concepts in mathematics, there is often a structure like a Russian doll. If we open the doll, there is often an identical but smaller doll inside. If we open that doll, there's another smaller doll inside, and so on. This sort of Russian-doll-like behaviour pervades things like vector spaces, fields, and so on. Inside some vector space could be another Nesting Russian Dolls smaller vector space, and so on. We have this same property occurring with groups. Inside groups could be other, smaller groups.

Definition A subgroup is a subset of a group which is also a group. To prove that a subgroup is a group, we need to only check for • closure • identity existence • inverse existence

Abstract algebra/Groups We do not need to check for associativity because this is "given" to us by the larger group. If the group is finite, then we do not need to check for the third one because if the order of an element in the subgroup is n, then is its inverse. It's clear that a set containing only the identity ({e}, *) will always be a subgroup. In the above example with Z2, ({0}, +) is a subgroup. The subgroup containing just the identity is known as the trivial subgroup. For example, the even numbers under addition form a subgroup of the integers under addition. But, the odd numbers do not (since 1+1=2, which is not odd, so closure is violated, and 0 is not odd, so they have no identity).

Problem set Given the above rules, answer the following (Answers follow to even-numbered questions). 1. 2. 3. 4.

Is Z2 a subgroup of Z under addition? Is (Z2, ×) a group? (× representing multiplication modulo 2). What about (Z2*, ×)? Identify all subgroups of Z3 Identify one subgroup of (Z, +)

5. Prove that permutations of three elements are associative and have inverses. (Hint: write out all valid permutations) 6. Find a nontrivial subgroup of the permutations of three elements. 7. Is Z2 a subgroup of Z5 with addition modulo 5? 8. Let S be a subset of the group G. We define the set generated by S, denoted <S>, to be the set of all finite products x0x1x2...xn with either xi or xi-1 ∈ S for each i, 0n. Show that <S> is a subgroup of G. Terminology and the "syntax" of formula can be confusing. Try converting the following group formulas from "additive" notation into "multiplictive" notation. Assume a,b,c∈G, but do not assume the group is abelian even though we are using the additive notation! 9. a + b - c 10. 2b + c 11. a + b - a 12. a - a = 0 13. if a + b = 0, then b = -a Now try converting these "multiplicitive" formula in "function composition" syntax. Ideally you can translate into both a ° b or a(b(x)) from ab. 14. a × b × c-1 = 1 15. aba-1 ∈ H Answers 2. Z2 is not, because 0 has no multiplicative inverse. Z2* is. 4. The even integers are a subgroup of (Z, +) 6. {(a,b,c)→(a,b,c), (a,b,c)→(c,b,a)} 8. We need to check three properties to ensure that H=<S> is a subgroup. • Closure: Since the elements in H are finite sequences of elements of S or their inverses multiplied by each other, for two elements of H, we can take the two sequences of S and concatenate them to get another sequence of elements in S, which yields another element of H.

5

Abstract algebra/Groups • Identity: Since for any element x in S, both x and x-1 are in H, by closure, so is x * x-1 = 1, the identity. • Inverses: This is given in the definition of H. Then H is a subgroup of G. 10. b2 × c or b2c 12. a × a-1 = 1 or aa-1 = 1 or even a ÷ a = 1. Notice how the "identity" element changed names. 14. a ° b ° c-1 = I, where I is the identity function I(x) ≡ x, for all x. or a(b(c-1(x))) = x

Problems without answers Here are some proof-style questions, for you to try. There are no answers here, since there may be more than one way to answer the following questions. 1. Consider a finite group G. Show that for all x ∈ G there exists an integer n such that xn=e. The smallest positive integer that satisfies this condition is called the order of the element x; we denote the order with |x| here. 2. Let a ∈ G. Prove that if a*b =e, then b*a = e. That is, any right inverse is a left inverse. 3. Prove that the identity is unique. 4. Prove that the inverse of an element is unique. 5. Let a ∈ G. Prove that (a-1)-1 = a. 6. (hard) Let G be a finite abelian group. Prove that there exists x0,x1,x2,...,xk such that x0a0x1a1x2a2...xkak uniquely generates the elements of G for 0 ≤ am ≤ |xm| for 0 ≤ m ≤ k.

Cosets A coset is related to the idea of a subgroup. Say we have a subgroup H of a group G. If we take an element g ∈ G, and we form the set {g*h|h ∈ H}, we obtain what is known as a left coset of H and we write this gH. Since commutativity is not assured, we also have a right coset of H which is {h*g|h ∈H} and is written Hg.

Example Let's look at (Z4,+), where + represents addition modulo 4. Z4 contains {0,1,2,3}, and, a subgroup of Z4 is {0, 2}. Now, from our definition, we can find the left cosets of Z4. We have {g+h|h ∈ H}, with g some element in G. Let's first take 0 ∈ G. Then the first coset we will encounter is {0+h|h ∈ H}={0, 2}. Take 1 ∈ G, so {1+h|h ∈ G} and we obtain {1, 3}. Take 2 ∈ G and we obtain {2, 0}={0, 2}. Finally, take 3 ∈ G and we get the final coset {1, 3} again.

6

Abstract algebra/Groups

7

Example In (Z12,+) ("clock arithmetic") there are several subgroups to choose from, and so there are many cosets collections to examine. Our group G is Z12 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; lets look at H6, H4, H3, and H2 Cosets of H6 H6 =

{

0

,

6

}

1→

{

1

,

7

}

2→

{

2

,

8

}

3→

{

3

,

9

}

4→

{

4

,

10

}

5→

{

5

,

11

}

Cosets of H4 H4 =

{

0

,

4

,

8

}

1→

{

1

,

5

,

9

}

2→

{

2

,

6

,

10

}

3→

{

3

,

7

,

11

}

Cosets of H3 H3 =

{

0

,

3

,

6

,

9

}

1→

{

1

,

4

,

7

,

10

}

2→

{

2

,

5

,

8

,

11

}

Cosets of H2 H3 =

{

0

,

2

,

4

,

6

,

8

,

10

}

1→

{

1

,

3

,

5

,

7

,

9

,

11

}

Definition: The index of a subgroup H is the number of cosets it has within G. This is sometimes written [G:H]

Properties What can we surmise from the above? We can see that, if G is the group, H the subgroup, • the cosets partition G; every element in G belongs to one and only one coset. Stated differently, the cosets are either identical or disjoint. This means that the cosets we obtain either must be equal (as above, {0, 2}, {2, 0} = {0, 2} are both the same set), or they have no elements in common (as above, {1, 3} and {0, 2} have no elements in common) • x and y are in the same coset iff x-1y ∈ H - because of this being an equivalence relation, we have the partition fact above. • the size of gH is equal to that of H because h → gh is a bijection, and if there is a bijection between two sets, then the sets must be of the same size.

Abstract algebra/Groups

8

Lagrange's theorem and cosets Cosets are used to prove an interesting result known as Lagrange's theorem, and tells us how the sizes of subgroups relate to the size of the larger group. To use our Russian-doll analogy, it tells us how small all the dolls inside are going to be. Firstly, Lagrange's theorem tells us: If G is a group and H is a subgroup, then the |G|=[G:H]|H| As a consequence of this, we can use Lagrange's theorem to obtain the number of cosets a group has when the group is finite If G is a group, H a subgroup, there are |G|/|H| cosets We write the number of cosets of H in G as (G:H). Why is this true? Remember that the cosets of a group partition it; every element in the group is in one and only one of the cosets - if we take the union of all the cosets, we will obtain the original group. Clearly the number of elements in all the cosets will be the same; recall from our definition that {g*h|h∈H} gives us a coset, we are multiplying all elements of H by g. So if we have |H| elements in a coset, and we have n cosets (and since we can't have a fraction of a coset) |H| must divide |G|.

Special groups In your study of group theory, you may come across many groups over and over again. They may be in fact quite special groups, and we will look at some of these groups in this section.

Normal subgroups, semidirect product, and quotient groups Consider the group (Z, +) and the subset of Z consisting of multiples of n, which is a subgroup of (Z,+) which we can write (n Z, +). Both these groups are abelian, since addition normally is commutative. If one considers this group and its cosets, one has the group Z/n Z of integers modulo n - this is just Zn. More generally, for any abelian group G and subgroup H, one can construct such a group above, which we call the quotient group of G by H as follows. If we define two elements of G to be equivalent if their difference lies in H i. e. they belong to the same coset. Since the cosets partition the group G, it is obviously an equivalence relation. Now let us define the semidirect product of two subsets of G, H and K, HK, to be simply all elements hk where h is in H and k is in K. We use the following result to establish the fact that HK is a group: Theorem: Let H and K be subgroups of G. The HK is a subgroup if and only if HK=KH, and HK is the group generated by the union of H and K. Proof: Since HK is a subgroup, the group of its inverses

must be the same. Since

since both H and K are groups. Thus, HK=KH. Conversely, let HK=KH. Then the set of the inverses

, so

it contains all inverses. Also, it is closed, because (HK)(HK)=H(KH)K=(HH)(KK)=HK. The subgroup HK must contain both H and K, so it is the group generated by its union. Now consider the cosets gH and g'H. Is the product of the two cosets gH and g'H the same as (gg')H? Not always, but it is possible to prove that this is the case with a single condition:

Abstract algebra/Groups

9

Theorem: Let H be a subgroup of G. Then the product of the two cosets (gH)(g'H) is the same as the coset (gg')H if and only if for all a within G. Proof: Suppose that

for all a within G. Then (gH)(g'H)= . Conversely, suppose that (gH)(g'H)=(gg')H. Then

must be a subset of since H contains the identity. This, of course, is the same as =H implying that is a subset of H. This also means that H is a subset of , and replacing a with , we get that H is a subset of , implying that is the same as H. If g is an arbitrary element of G and H is an arbitrary subgroup then the following statements are equivalent, and if they hold, then H is called a normal subgroup. 1. 2. 3. 4. 5.

gHg-1=H gHg-1⊂H gH = Hg Every left coset is a right coset. Every right coset is a left coset.

Note that any subgroup of an abelian group is normal. This is easy to see - take gH and Hg (again, with H a subgroup of G). If we write H={h0=e, h1, ..., hn}, then gH = {gh0=e, gh1, ..., ghn}, but, since we have that G is abelian, we can write {h0g=e, h1g, ..., hng} which is just Hg. Note that 3. does not imply that g commutes with every element of H, but only with the set H. Now we can construct the quotient group. Let H be a normal subgroup of G. Then take the left (or right - it doesn't matter) cosets of H. Then define (aH)(bH)=(ab)H. Note that this is well-defined because this group operation is essentially the set product, so that if a' and b' are within aH and bH, then a'H and b'H are the same cosets, so that (a'b')H=(a'H)(b'H) is the same as the product of aH and bH. Now we prove that the set of cosets under this operation is a group. First, it is obviously closed since, as we proved earlier, the product of two cosets is itself a coset. Associativity in this set follows from the associativity in the group, since (aH)(bH)=(ab)H. The identity element is 1H=H, which is the subgroup H itself. The inverse of aH is . This group of cosets of H within G is called the quotient group and is denoted G/H. Example Consider the group of permutations on three elements. For simplicity, write (2,3,1) for the permutation (1,2,3)→(2,3,1). Then, if we take N to be the normal subgroup { (1,2,3), (2,3,1), (3,1,2) }, this group commutes with each of the elements of S3. Consider each element s of S3: • s = (1,2,3): sN = N = Ns • s = (1,3,2): sN = { (1,3,2)(1,2,3), (1,3,2)(2,3,1), (1,3,2)(3,1,2) } = { (1,3,2), (2,1,3), (3,2,1) } = { (1,3,2), (3,2,1), (2,1,3) } = { (1,2,3)(1,3,2), (2,3,1)(1,3,2), (3,1,2)(1,3,2) } = Ns. • For other elements s ∈ S, sN gives on of the two cosets above. You can check this for yourself.

Abstract algebra/Groups

10

Notice that (1,3,2) does not commute with two of the elements of N, but it does commute with the subgroup N itself.

Cyclic groups Let's look at the group (Z5, +). This is a group under addition. Let's look at one specific element in Z5: 2. Observe, in Z5: 2 = 2 (of course) 2+2 = 4 2+2+2 = 6 = 1 2+2+2+2 = 8 = 3 2+2+2+2+2 = 10 = 0 On repeated addition of 2 to itself, we see that doing this has generated the entire set Z5! For this reason, we call this element a generator (There may be a case where one element may not generate the entire set, but a subset of the original group may do it, in this case we call that set a generating set). As stated before, regardless of whether the group operation is addition or multiplication, we write the application of the group operation n times to some element a, an, so if we want to represent 2+2+2+2 in Z5, we often just write 24. A group which has the property that one element generates the group is known as a cyclic group. Example (Z,+ ) In the group (Z,+) of integers under addition, every element x can be written in the form where n = x. This means that 1 is a generator for the group. Properties One interesting property to note is that all cyclic groups are abelian, since for any x = ga, y = gb ∈ G: . Exercise 1. Verify that 1, 3, and 4 are also generators for (Z5, +). 2. Let G be of order n, and let it be generated by a. Then prove that the following are equivalent: 1. The order of is n. 2. n and x are coprime. 3. There is a number y such that xy is congruent to 1 mod n.

Abstract algebra/Groups

11

The symmetric group We have already come into contact with the symmetric group before, so let's refresh our memory: the symmetric group of n elements is the group of all the permutations of n objects. We can also speak about the symmetric group of a set J, where the permutations are of the elements of J. If we are referring to the symmetric group of n elements, we write Sn, and of the set J, we write Sym(J). The order of Sn is n!. As such, the number of elements in Sn grows very fast as n does. The alternating group A special case of the symmetric group is the alternating group. For now, let's just take it as a given that for any finite sequence of objects, the composition of any odd number of transpositions would not give the identity permutation. We'll get back to the proof of this statement later. Firstly, if we have some permutation of objects and we wish to get it back to the identity permutation of objects (back in order), we can continually swap two objects until all the objects are back in order. If we have to swap these an odd number of times, we call the permutation an odd permutation, likewise, if we have to swap an even number of times, we call the permutation an even permutation. The group of even permutations only is a group as well, and we call it the alternating group of n elements, and we write it An The dihedral group The dihedral group of order 2n is the group with generators R and F such that: =I,

=I,

where I denotes the identity.

Here, we can consider R to be a rotation, and F to be a reflection. Intuitively, we can consider the dihedral group to be the group of all symmetries of a regular polygon.

Group morphisms So far we have only considered looking at how a set is related to its associated operation, ie., how the group itself works. However, how can we examine the relationships between two groups? We look at the relationships between groups by considering special functions which take elements from one group and map them to another. We call these functions a special name, morphisms, and they come in different types: • homomorphisms • • • • •

monomorphisms are injective or one-to-one homomorphisms. epimorphisms are surjective or onto homomorphisms. isomorphisms are bijective homomorphisms. endomorphisms are homomorphisms of a group to itself. automorphisms are isomorphisms of a group to itself.

(Isomorphisms and automorphisms are special cases of homomorphisms) Examining morphisms allow us to make important analyses of the relationships between groups. For example, two groups are essentially the same, if there is an isomorphism

Abstract algebra/Groups between them. The relationship between a subgroup and the original group can be characterised, in fact, by an injective homomorphism (see below). All these morphisms have an important and essential property: they are said to "respect group structure". We will see what this means below.

Homomorphisms If we have two groups (G1, *), and (G2, o), a homomorphism is a mapping or a function f from G1 to G2, and x, y being elements in G1, such that f(x * y) = f(x) o f(y). It's important to recognize that there are no restrictions on the mapping. This mapping behaves exactly like a function: it can be injective - the homomorphism maps all elements in G1 to a unique element of G2 (in this case the homomorphism is sometimes referred to as a monomorphism, or, it can be surjective: the homomorphism maps some (or all) elements in G1 to all elements in G2, (in this case the homomorphism is sometimes referred to as an epimorphism), or even both, in which case it is a isomorphism. Like in other areas of abstract algebra such as linear algebra (in which linear transformations are just homomorphisms), we have the concept of the kernel also in group theory. A homomorphism is a mapping of some elements in one group to another. The kernel of this homomorphism is the collection of all the elements of a group that get mapped to the identity of the other group. So if we have the most trivial of homomorphisms, one that maps the whole group to ({0},+), the kernel would be the whole group. On the other end of the spectrum, the kernel of a isomorphism consists of only the identity element. In fact, the converse to this is true. An example You have come across the group of permutations on three elements, and we have a subgroup of this group, namely {(a,b,c)→(a,b,c), (a,b,c)→(c,b,a)} under the operation of performing the first permutation followed by the second - denote it *. For convenience, we'll write e=(a,b,c)→(a,b,c), and x=(a,b,c)→(c,b,a). We've also come across the group Z2, {0, 1} under the operation of addition modulo 2. Verify these two groups are in fact groups for practice, if you wish. We'll define a mapping f such that e maps to 0, and x maps to 1. We can show that f is a homomorphism simply by cases, since these groups are small. However when they are large we can do this by algebra if f is suitably defined. f(e*x)=f(e)+f(x)=0+1=1, f(e*x)=f(x)=1 f(x*e)=f(x)+f(e)=1+0=1, f(x*e)=f(x)=1 f(e*e)=f(e)+f(e)=0, f(e*e)=f(e)=0 f(x*x)=f(x)+f(x)=0, f(x*x)=f(e)=0 So f is thus a group homomorphism.

12

Abstract algebra/Groups Kernel We call the elements of G1 that get mapped under f to the identity of G2 the kernel of f, denoted Ker(f). What can we discover about this set? Say a,b ∈ G1 and f(a) = f(b) = 1G2 , that is, a and b are in the kernel. Then f(a * b) = f(a) o f(b) = 1G2, so a * b is in the kernel also. That is, the kernel is closed. Also, f(1G1) = f(1G1 * 1G1) = f(1G1) o f(1G1), so f(1G1) = 1G2. That is, the identity of G1 is in the kernel. One more thing is that 1G2 = f(1G1) = f(a * a-1) = f(a) o f(a-1) = 1G2 o f(a-1) = f(a-1), i.e. the kernel has inverses. The kernel is closed, has the identity, and has its elements' inverses. That means the kernel is a subgroup of G1.

Kernel is also a normal subgroup. Proof. Let b ∈ Ker(f) and a ∈ G. Now f(a * b * a-1) = f(a) o f(b) o f(a-1) = f(a) o e o f(a-1) = f(a) o f(a)-1 = e, which means a * b * a-1 ∈ Ker(f) and thus it is a normal subgroup. So every homomorphism gives us a normal subgroup in G1. The converse is true also: every normal subgroup N gives a homomorphism. The homomorphism is given by f(a) = aN = Na for a ∈ G1 and aN ∈ G2. That is, the elements of G2 are the cosets of N. Try verifying that this is a homomorphism by checking that f(a * b) = f(a) o f(b). G2 is called a quotient group of G1, and this relationship is written G2 = G1/N. More on this later. Then the homomorphisms from G1 are in one-to-one correspondence with the normal subgroups of G1. Homomorphisms and normal subgroups are really two ways of looking at the same thing.

An example Kernels are also useful to characterise subgroups. Here's an example. Recall the alternating group is the subgroup of Sn containing even permutations. In selecting the even permutations, we have created a surjective homomorphism from Sn to (Z2,+). Even permutations are mapped to the identity, 0, whilst odd permutations are mapped to 1. The kernel then is all the even permutations of Sn. Note this also indicates why we don't choose all the odd permutations, since it's more natural to take the kernel instead.

Isomorphisms When considering some class of mathematical objects, a logical question to ask is when two objects are the same. For example, we often consider congruent triangles to be the same. Note, however, that there is usually more than one way to define the relation of sameness. For example, in a different context we might want to call all similar triangles the same. The relation of sameness for groups is called isomorphism. When working with sets, we consider two sets the same if they have the same cardinality that is, if one can be bijectively mapped to the other. Since groups are sets, for two groups to be the same, they should be the same as sets, so for two groups G and G' to be isomorphic,we require that there be a bijective mapping from G to G'. However, groups have more structure than sets, so we should require that our notion of sameness preserve that structure. With that in mind, we define that two groups (G, *) and (G', o) are isomorphic if there exists a bijection f: G → G' such that f(x * y) = f(x) o f(y). Such a bijection is called an isomorphism

13

Abstract algebra/Groups from G to G'. Any surjective homomorphism f whose kernel contains only the identity is an isomorphism. To establish that this is true, we must prove that f is injective. Suppose that f(g) = f(h). Then f(g*h-1) = f(g)*f(h-1) = f(g)*f(h)-1 = 1G2 => g*h-1 = 1G1 => g = h.

An example Let's look at two small groups B=(Z2,+) and C=({1, -1}, ×), where + represents addition modulo 2. For clarity we represent the element "1" in B as 1B, and the element "1" in C as 1C. We can create an isomorphism, by defining f to map 0 to 1C, 1B to -1. We need to show f satisfies the defining properties of isomorphisms. Clearly f is bijective since it is injective and surjective by inspection. It now only remains to show that f respects the group structure and we have shown that B and C are isomorphic. Recall to show f respects the group structure we need to show f(x+y)=f(x)×f(y). Since the two groups again are relatively small, we can do this easily by cases, however when they are large we can do this by algebra if f is suitably defined. f(0+0)=f(0)×f(0)=1C×1C=1C, f(0+0)=f(0)=1C f(0+1B)=f(0)×f(1B)=-1, f(0+1B)=f(1B)=-1 f(1B+0)=f(1B)×f(0)=-1×1C=-1, f(1B+0)=f(1B)=-1 f(1B+1B)=f(1B)×f(1B)=-1×-1=1C, f(1B+1B)=f(0)=1C f isomorphism, so B and C are isomorphic. Example where the two groups have the same set of elements We'll look at our familiar friend (Z3\{0}, ×) Normally, we have the multiplication table

Consider then the homomorphism f such that f(x)=2×x (modulo 3, naturally). Applying this homomorphism we obtain the multiplication table:

14

Abstract algebra/Groups

15

Cayley's Theorem Classically, only groups of permutations were considered. Our axiomatic approach clears away irrelevancies, but it in fact does not give us a more general class of objects. For there is a theorem due to Arthur Cayley that says that every finite group is isomorphic to a subgroup of a group of permutations - the symmetric group. Proof We prove that G is isomorphic to a subgroup of the group of permutations of itself, Sym(G). Given an element g ∈ G, we identify g with the function G → G sending an element h ∈ G to g*h. We need to show that this function is a bijective and therefore a permutation. Suppose g*x = g*y. Then multiplying on the left by g-1, we see that x = y, so the function is injective. To show that is is surjective, let y ∈ G, then the function sends g-1*y to g*g-1*y = y. Therefore the function is surjective and a transposition. We must show that each element g defines a different permutation. To see this, suppose that g*x = g'*x. Then multiplying by x-1 on the right, we see that g = g'. Finally, we must show that our map G → Sym(G) respects group structure. This is left as an exercise for the reader.

Automorphisms Definitions What if we have an isomorphism existing from a group (G, *) to (G, *) - in essence a isomorphism between a group and itself? When we can create such a isomorphism, we term it an automorphism. A specific type of automorphism is an inner automorphism, which conjugates all the elements, meaning that it is an automorphism of the form f:G->G given by f(h)=ghg-1. If an automorphism is not an inner automorphism, then we call it an outer automorphism. An example In Z3 we interchange 1 and 2. In this group "0" is different, but "1" and "2" are essentially the same: adding one of them to itself gives the other one, adding both give 0, adding 0 to any element gives (of course) the same. Thus interchanging 1 and 2 in the multiplication table gives the same table. We can think of "1", and "2" being different labels for two things which are the same - the automorphism swaps the two labels. If we had a multiplication (addition) table for this group, but with the elements labeled a, b, and c, we could recognize which one is the identity element, but we could not distinguish the other two. +

0

1

2

0

0

1

2

1

1

2

0

2

2

0

1

+

a

b

c

a

a

b

c

b

b

c

a

Abstract algebra/Groups

16

c

c

a

b

+

a

c

b

a

a

c

b

c

c

b

a

b

b

a

c

Notice that Zabc = Zacb. For example, b + c = a in both groups. The following consist of some unsorted definitions A simple group is a group with no proper normal subgroups. The automorphism group of a group is the group of all bijective transformations preserving the group structure. If we have a surjective homomorphism f:G->K with H as its kernel and a homomorphism g:K->G such that fg:K->K is the identity homomorphism, then we say G is (isomorphic to) a semidirect product of H and K. The center of the group is the subgroup which commutes with all the other elements of the group. Problem set 1. Prove that the center of a group is always a subgroup. 2. Prove that there is a one-to-one correspondence between the conjugacy classes of the permutation group Sn and the partitions of n.

Isomorphism Theorems Factor Theorem Let G be a group, and let N be a normal subgroup. Let f be a homomorphism from G to H with a kernel K that contains N. Let g be the homomorphism from G to the quotient space G/N where g(a)=gN i. e. the map from an element to the coset containing it. Then there exists a homomorphism f' from G/N to H such that f'(g(a))=f(a) for all elements of G. This f' will be an epimorphism only when f itself is an epimorphism, and it will be a monomorphism only when the kernel K does not contain any elements other than N i. e. K=N. Proof In order for f'(g(a)) to be the same as f(a), f'(aN) must be f(a) indicating that f' is unique. This function is well-defined, for suppose that a and b belong to the same coset. Then belongs on N, so it belongs on K, indicating that f( )=f(a)f( )=1 indicating that f(a)=f(b). To check that this function is a homomorphism, f'(aNbN)=f'((ab)N)=f(ab)=f(a)f(b)=f'(aN)f'(bN), so it is a homomorphism. Now, obviously the image of f' is the same as the image of f, f' is an epimorphism when f is an epimorphism. Now suppose that the kernel K=N, and that f'(aN)=f'(bN). Then f(a)=f(b), so f( )=1, so is within the kernel, and is thus within N. This indicates that a and b belong to the same coset, and aN and bN are thus the same cosets. Note that a result of this theorem is that when f is an epimorphism and K=N, then f' is an isomorphism. The following is an immediate result:

Abstract algebra/Groups

First Isomorphism Theorem Let f be a homomorphism from G to H with kernel K. Then the image of f is isomorphic to G/K. Proof Using the factor theorem above, with the subgroup being the same as the kernel, and with the homomorphism being an epimorphism over its image, G/K must have an isomorphism to H. Now let N be a normal subgroup, and let H be any subgroup. We have here the useful

Theorem 1. HN=NH, so HN is a subgroup of G. 2. N is a normal subgroup of HN 3. The intersection of H and N is a normal subgroup of H. Proof 1. hN=Nh for every h within H. 2. aN=Na for any a within G, so aN=Na for any a within HN. 3. Since N is a normal subgroup, hN=Nh for any h within H. Since H∩N is entirely within H, letting h be an element of h, h(H∩N) is entirely within H, and is a subset of hN, and is, in fact, the intersection H∩(hN) since it essentially contains all elements of H within the coset hN, and cannot possibly contain any other elements. Similarly (H∩N)h is also a subset of Nh, H∩(Nh). Since hN=Nh, h(H∩N)=(H∩N)h.

Second Isomorphism Theorem Let G be a group, and let H be a subgroup of G, and let N be a normal subgroup of G. Then H/(H∩N) is isomorphic to (HN)/N. Proof Let f be a function from G to G/N, such that f(a)=aN. Now we restrict the domain of the function to only points within H. Then this function is a function from H to G/N, with H∩N as its kernel. Thus, H/(H∩N) is isomorphic to the image of this restricted function, which is essentially all aN such that a is within H. This is simply (NH)/N because NH contains all the possible cosets hN with h within H, so that the quotient group is simply all hN with h in H.

Third Isomorphism Theorem Let G be a group, let N be a normal subgroup of G, and let H be a normal subgroup of G contained in N. Then G/N is isomorphic to (G/H)/(N/H). Proof Define the function to be f(aN)=aH. If aN=bN, then they belong to the same coset of N, and since N is a subgroup of H, thus belong to the same coset of H, and so it is well-defined. It is obvious that this is an epimorphism. The kernel is all the elements that map onto H, and is thus all the cosets of N that are within H, essentially meaning H/N. Therefore, by the first isomorphism theorem, G/N is isomorphic to (G/H)/(N/H).

17

Abstract algebra/Groups

Correspondence Theorem The main result of the isomorphism theorems is actually called the factor theorem. Let N be any normal subgroup of G, and let H be any subgroup of G containing N. It is quite obvious that N is a normal subgroup of H. Define the function f(A)=A/N mapping the set of subgroups of G containing N to the subgroups of G/N. This is a one-to-one correspondence. Moreover, is a subgroup of if and only if is a subgroup of , and the number of cosets is the same in both cases. In addition, H is a normal subgroup of G if and only if H/N is a normal subgroup of G/N, and is a normal subgroup of if and only if is a normal subgroup of . Proof Given the fact that this is one-to-one, we can also form the inverse of f by using , which is also a one-to-one function. Thus, f is a bijection. It is also quite obvious that when is a subgroup of , that is a subgroup of . Conversely, when is a subgroup of , the application of the inverse of f also makes it obvious that is a subgroup contained within , automatically making a subgroup of . We prove that the number of cosets in both cases is the same by defining the bijection which is well-defined because if then they belong to the same coset of , they also belong to the same coset of . Now suppose that H is a normal subgroup of G. Then indicating that H/N is a normal subgroup of G/N. Now let H/N be a normal subgroup of G/N. Now consider the function which is obviously a homomorphism. The kernel of this is all elements which map onto H/N, and is thus all cosets of N which map onto an element of H. Thus, H is the kernel of this, and so is a normal subgroup of G. Now suppose that is a normal subgroup of . Then if we consider N as a normal subgroup of , then we immediately get the result that whenever is normal in , that is normal in from what we had already proven. Conversely just use the third isomorphism theorem to prove the converse.

Group actions Before we go on with the technical details, let's examine one of the uses of groups. The description of symmetries (i.e. structure preserving automorphisms) acting upon a structure with an underlying set-theoretic structure can usually be done with a concept known as a group action. It basically tells us how any particular symmetry acts as a transformation upon a set. We have seen a lot of this use of groups. Example Conjugation Given a group defined by

and an element in , it's easily seen that the mapping is an automorphism of , so each element in gives rise to an

automorphism. Different elements may give rise to the same automorphisms. For example, if is abelian, then all such automorphisms are identity map. In this sense we say the group acts on the set : for any in the set , the group acts on it by sending to .

18

Abstract algebra/Groups

19

Definition Given a group and a set ,a -action on is a homomorphism from into the permutation group of . Recall that permutations on forms a group with composition of mappings as the group operation, so is a homomorphism implies, first of all, the identity in maps to the identity permutations, and secondly, given and in and in , ; that is, the product of two elements in has the same effect as the action of each element applied in turn. Orbit, stablizer and the class equation Having a group acting on a set makes it natural to ask, given an element of the set, how does the group affect this single element? What places does the group send it to? This is called the orbit of the element. Given an element of , the orbit of , denoted by is the set of points for all in . Exercise: An orbit is an equivalence class; that is, for any , in by iff such that is an equivalence relation.

,

, the relation defined

It is possible that two element of , whose permutations on are different, send to the same place. So how to find the number of possible different destinations of , the order of ? Instead of applying every element in on to see if they works differently, we look for the other extreme, elements in that do not move . For any in , the stablizer of , denoted by , is the set of elements of that leaves fixed. It can be checked that is a subgroup in . Consider the left cosets of . Any element in a left coset can be written as the product for some in . The action of on then becomes . On the other hand, given an element in that has the same effect on as , we have so . This implies belongs to , and , must belong to the same left coset of . We have proved the following Theorem: is a group acting on the set correspond 1-1 to the orbit of . Since

is a subgroup of

. Given

, the left cosets of

, number of cosets equals to

equivalent classes dividing the set Theorem (class equation):

. Since the orbits are

, we have the following while the element

is taken from each

equivalent class. If the stabilizer of every element of act freely.

is the trivial subgroup, then the

-action is said to

Problem set 1. Prove that any G-action on X partitions X into disjoint orbits. (Incidentally, this explains why if H is a subgroup of G, H partitions G into cosets. There is a canonical left H-action on G.) 2. Prove that the action of G upon any orbit is also a G-action. 3. Prove that the stabilizer is always a subgroup.

Abstract algebra/Groups If the G-action on X only contains one orbit, then it's said to be transitive. If ρ is injective, then the G-action is said to be faithful. Cayley's theorem: Every group G has a G-action which is transitive and acts freely (these two properties together is called simply transitive). Moreover, this G-action is unique up to isomorphism. Corollary: Every group G is isomorphic to a subgroup of a permutation group (which is not necessarily finite). Theorem: The orbit of any element x of X is isomorphic to the G-action on G/Stab(x) where Stab(x) is the stabilizer of x. Even so, when speaking about exponentiation, we need to consider this above notation. When speaking of groups in general, bc means b× b×b×..., b multiplied by itself c times. However, in a group under addition, we still write bc, but this means b+b+b' '...=cb. This can be confusing the first time you see an expression like or . -->

Direct Product Source: http:/ / en. wikibooks. org/ w/ index. php? title=Abstract_ algebra/ Groups Principal Authors: Dysprosia, Mjeff, Thebhgg, Pm5, Patrick, The Scarlet Letter, Isomorphic, MikeBorkowski, Jguk, F1sdz

20

License

License Shortcut:WP:GFDL Version 1.2, November 2002 Copyright (C) 2000,2001,2002 Free Software Foundation, Inc. 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed.

0.PREAMBLE The purpose of this License is to make a manual, textbook, or other functional and useful document "free" in the sense of freedom: to assure everyone the effective freedom to copy and redistribute it, with or without modifying it, either commercially or noncommercially. Secondarily, this License preserves for the author and publisher a way to get credit for their work, while not being considered responsible for modifications made by others. This License is a kind of "copyleft", which means that derivative works of the document must themselves be free in the same sense. It complements the GNU General Public License, which is a copyleft license designed for free software. We have designed this License in order to use it for manuals for free software, because free software needs free documentation: a free program should come with manuals providing the same freedoms that the software does. But this License is not limited to software manuals; it can be used for any textual work, regardless of subject matter or whether it is published as a printed book. We recommend this License principally for works whose purpose is instruction or reference.

1.APPLICABILITY AND DEFINITIONS This License applies to any manual or other work, in any medium, that contains a notice placed by the copyright holder saying it can be distributed under the terms of this License. Such a notice grants a world-wide, royalty-free license, unlimited in duration, to use that work under the conditions stated herein. The "Document", below, refers to any such manual or work. Any member of the public is a licensee, and is addressed as "you". You accept the license if you copy, modify or distribute the work in a way requiring permission under copyright law. A "Modified Version" of the Document means any work containing the Document or a portion of it, either copied verbatim, or with modifications and/or translated into another language. A "Secondary Section" is a named appendix or a front-matter section of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document's overall subject (or to related matters) and contains nothing that could fall directly within that overall subject. (Thus, if the Document is in part a textbook of mathematics, a Secondary Section may not explain any mathematics.) The relationship could be a matter of historical connection with the subject or with related matters, or of legal, commercial, philosophical, ethical or political position regarding them. The "Invariant Sections" are certain Secondary Sections whose titles are designated, as being those of Invariant Sections, in the notice that says that the Document is released

21

License under this License. If a section does not fit the above definition of Secondary then it is not allowed to be designated as Invariant. The Document may contain zero Invariant Sections. If the Document does not identify any Invariant Sections then there are none. The "Cover Texts" are certain short passages of text that are listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License. A Front-Cover Text may be at most 5 words, and a Back-Cover Text may be at most 25 words. A "Transparent" copy of the Document means a machine-readable copy, represented in a format whose specification is available to the general public, that is suitable for revising the document straightforwardly with generic text editors or (for images composed of pixels) generic paint programs or (for drawings) some widely available drawing editor, and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters. A copy made in an otherwise Transparent file format whose markup, or absence of markup, has been arranged to thwart or discourage subsequent modification by readers is not Transparent. An image format is not Transparent if used for any substantial amount of text. A copy that is not "Transparent" is called "Opaque". Examples of suitable formats for Transparent copies include plain ASCII without markup, Texinfo input format, LaTeX input format, SGML or XML using a publicly available DTD, and standard-conforming simple HTML, PostScript or PDF designed for human modification. Examples of transparent image formats include PNG, XCF and JPG. Opaque formats include proprietary formats that can be read and edited only by proprietary word processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated HTML, PostScript or PDF produced by some word processors for output purposes only. The "Title Page" means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, "Title Page" means the text near the most prominent appearance of the work's title, preceding the beginning of the body of the text. A section "Entitled XYZ" means a named subunit of the Document whose title either is precisely XYZ or contains XYZ in parentheses following text that translates XYZ in another language. (Here XYZ stands for a specific section name mentioned below, such as "Acknowledgements", "Dedications", "Endorsements", or "History".) To "Preserve the Title" of such a section when you modify the Document means that it remains a section "Entitled XYZ" according to this definition. The Document may include Warranty Disclaimers next to the notice which states that this License applies to the Document. These Warranty Disclaimers are considered to be included by reference in this License, but only as regards disclaiming warranties: any other implication that these Warranty Disclaimers may have is void and has no effect on the meaning of this License.

2.VERBATIM COPYING You may copy and distribute the Document in any medium, either commercially or noncommercially, provided that this License, the copyright notices, and the license notice

22

License saying this License applies to the Document are reproduced in all copies, and that you add no other conditions whatsoever to those of this License. You may not use technical measures to obstruct or control the reading or further copying of the copies you make or distribute. However, you may accept compensation in exchange for copies. If you distribute a large enough number of copies you must also follow the conditions in section 3. You may also lend copies, under the same conditions stated above, and you may publicly display copies.

3.COPYING IN QUANTITY If you publish printed copies (or copies in media that commonly have printed covers) of the Document, numbering more than 100, and the Document's license notice requires Cover Texts, you must enclose the copies in covers that carry, clearly and legibly, all these Cover Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on the back cover. Both covers must also clearly and legibly identify you as the publisher of these copies. The front cover must present the full title with all words of the title equally prominent and visible. You may add other material on the covers in addition. Copying with changes limited to the covers, as long as they preserve the title of the Document and satisfy these conditions, can be treated as verbatim copying in other respects. If the required texts for either cover are too voluminous to fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto adjacent pages. If you publish or distribute Opaque copies of the Document numbering more than 100, you must either include a machine-readable Transparent copy along with each Opaque copy, or state in or with each Opaque copy a computer-network location from which the general network-using public has access to download using public-standard network protocols a complete Transparent copy of the Document, free of added material. If you use the latter option, you must take reasonably prudent steps, when you begin distribution of Opaque copies in quantity, to ensure that this Transparent copy will remain thus accessible at the stated location until at least one year after the last time you distribute an Opaque copy (directly or through your agents or retailers) of that edition to the public. It is requested, but not required, that you contact the authors of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated version of the Document.

4.MODIFICATIONS You may copy and distribute a Modified Version of the Document under the conditions of sections 2 and 3 above, provided that you release the Modified Version under precisely this License, with the Modified Version filling the role of the Document, thus licensing distribution and modification of the Modified Version to whoever possesses a copy of it. In addition, you must do these things in the Modified Version: • A. Use in the Title Page (and on the covers, if any) a title distinct from that of the Document, and from those of previous versions (which should, if there were any, be listed in the History section of the Document). You may use the same title as a previous version if the original publisher of that version gives permission.

23

License • B. List on the Title Page, as authors, one or more persons or entities responsible for authorship of the modifications in the Modified Version, together with at least five of the principal authors of the Document (all of its principal authors, if it has fewer than five), unless they release you from this requirement. • C. State on the Title page the name of the publisher of the Modified Version, as the publisher. • D. Preserve all the copyright notices of the Document. • E. Add an appropriate copyright notice for your modifications adjacent to the other copyright notices. • F. Include, immediately after the copyright notices, a license notice giving the public permission to use the Modified Version under the terms of this License, in the form shown in the Addendum below. • G. Preserve in that license notice the full lists of Invariant Sections and required Cover Texts given in the Document's license notice. • H. Include an unaltered copy of this License. • I. Preserve the section Entitled "History", Preserve its Title, and add to it an item stating at least the title, year, new authors, and publisher of the Modified Version as given on the Title Page. If there is no section Entitled "History" in the Document, create one stating the title, year, authors, and publisher of the Document as given on its Title Page, then add an item describing the Modified Version as stated in the previous sentence. • J. Preserve the network location, if any, given in the Document for public access to a Transparent copy of the Document, and likewise the network locations given in the Document for previous versions it was based on. These may be placed in the "History" section. You may omit a network location for a work that was published at least four years before the Document itself, or if the original publisher of the version it refers to gives permission. • K. For any section Entitled "Acknowledgements" or "Dedications", Preserve the Title of the section, and preserve in the section all the substance and tone of each of the contributor acknowledgements and/or dedications given therein. • L. Preserve all the Invariant Sections of the Document, unaltered in their text and in their titles. Section numbers or the equivalent are not considered part of the section titles. • M. Delete any section Entitled "Endorsements". Such a section may not be included in the Modified Version. • N. Do not retitle any existing section to be Entitled "Endorsements" or to conflict in title with any Invariant Section. • O. Preserve any Warranty Disclaimers. If the Modified Version includes new front-matter sections or appendices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option designate some or all of these sections as invariant. To do this, add their titles to the list of Invariant Sections in the Modified Version's license notice. These titles must be distinct from any other section titles. You may add a section Entitled "Endorsements", provided it contains nothing but endorsements of your Modified Version by various parties--for example, statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard. You may add a passage of up to five words as a Front-Cover Text, and a passage of up to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified Version.

24

License Only one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one entity. If the Document already includes a cover text for the same cover, previously added by you or by arrangement made by the same entity you are acting on behalf of, you may not add another; but you may replace the old one, on explicit permission from the previous publisher that added the old one. The author(s) and publisher(s) of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version.

5.COMBINING DOCUMENTS You may combine the Document with other documents released under this License, under the terms defined in section 4 above for modified versions, provided that you include in the combination all of the Invariant Sections of all of the original documents, unmodified, and list them all as Invariant Sections of your combined work in its license notice, and that you preserve all their Warranty Disclaimers. The combined work need only contain one copy of this License, and multiple identical Invariant Sections may be replaced with a single copy. If there are multiple Invariant Sections with the same name but different contents, make the title of each such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work. In the combination, you must combine any sections Entitled "History" in the various original documents, forming one section Entitled "History"; likewise combine any sections Entitled "Acknowledgements", and any sections Entitled "Dedications". You must delete all sections Entitled "Endorsements."

6.COLLECTIONS OF DOCUMENTS You may make a collection consisting of the Document and other documents released under this License, and replace the individual copies of this License in the various documents with a single copy that is included in the collection, provided that you follow the rules of this License for verbatim copying of each of the documents in all other respects. You may extract a single document from such a collection, and distribute it individually under this License, provided you insert a copy of this License into the extracted document, and follow this License in all other respects regarding verbatim copying of that document.

7.AGGREGATION WITH INDEPENDENT WORKS A compilation of the Document or its derivatives with other separate and independent documents or works, in or on a volume of a storage or distribution medium, is called an "aggregate" if the copyright resulting from the compilation is not used to limit the legal rights of the compilation's users beyond what the individual works permit. When the Document is included in an aggregate, this License does not apply to the other works in the aggregate which are not themselves derivative works of the Document. If the Cover Text requirement of section 3 is applicable to these copies of the Document, then if the Document is less than one half of the entire aggregate, the Document's Cover Texts may be placed on covers that bracket the Document within the aggregate, or the electronic equivalent of covers if the Document is in electronic form. Otherwise they must

25

License appear on printed covers that bracket the whole aggregate.

8.TRANSLATION Translation is considered a kind of modification, so you may distribute translations of the Document under the terms of section 4. Replacing Invariant Sections with translations requires special permission from their copyright holders, but you may include translations of some or all Invariant Sections in addition to the original versions of these Invariant Sections. You may include a translation of this License, and all the license notices in the Document, and any Warranty Disclaimers, provided that you also include the original English version of this License and the original versions of those notices and disclaimers. In case of a disagreement between the translation and the original version of this License or a notice or disclaimer, the original version will prevail. If a section in the Document is Entitled "Acknowledgements", "Dedications", or "History", the requirement (section 4) to Preserve its Title (section 1) will typically require changing the actual title.

9.TERMINATION You may not copy, modify, sublicense, or distribute the Document except as expressly provided for under this License. Any other attempt to copy, modify, sublicense or distribute the Document is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance.

10.FUTURE REVISIONS OF THIS LICENSE The Free Software Foundation may publish new, revised versions of the GNU Free Documentation License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. See http:/ / www. gnu. org/ copyleft/ . Each version of the License is given a distinguishing version number. If the Document specifies that a particular numbered version of this License "or any later version" applies to it, you have the option of following the terms and conditions either of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If the Document does not specify a version number of this License, you may choose any version ever published (not as a draft) by the Free Software Foundation.

How to use this License for your documents To use this License in a document you have written, include a copy of the License in the document and put the following copyright and license notices just after the title page: Copyright (c) YEAR YOUR NAME. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License".

26

License If you have Invariant Sections, Front-Cover Texts and Back-Cover Texts, replace the "with...Texts." line with this: with the Invariant Sections being LIST THEIR TITLES, with the Front-Cover Texts being LIST, and with the Back-Cover Texts being LIST. If you have Invariant Sections without Cover Texts, or some other combination of the three, merge those two alternatives to suit the situation. If your document contains nontrivial examples of program code, we recommend releasing these examples in parallel under your choice of free software license, such as the GNU General Public License, to permit their use in free software.

27