# Abstract Algebra/Older Version

A group is a set with a number of special properties. Groups are useful in studying many different areas of mathematics. Group theory is the study of groups, their structure, and their nature. 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. By generalising these properties in the form of groups, we are afforded a powerful tool for saying a lot about all mathematical objects which obey group laws.

## Definitions and notations

A group is a set, say $G$, and a binary operation which we call $*$, satisfying the following properties:
* closure under $*$: If $a$, $b$ are in $G$, then $a*b$ is also in $G$. This means that if we have two elements from $G$, and $a*b$ is not in $G$, $G$ can't be a group.
* associativity of $*$: If $a$, $b$, $c$ are elements of $G$, $(a*b)*c=a*(b*c)$, as we have for addition and multiplication but not subtraction of natural numbers.
* existence of an identity element: There is an element in $G$, which we write $e$, such that for any $a$ in $G$, $e*a=a*e=a$. We call $e$ the identity, which we sometimes also notate $I$, $1$, or $E$.
* existence of inverses: For any $a$ in $G$, there exists some element $q$ in $G$, such that $q*a=a*q=e$. We usually write $q$ as $a^{-1}$.
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 $(G,*)$, although it is common practice to speak of the group as the set $G$. It is important to note, however, that a given set can form 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 $0$, and the inverse of $a$ in $G$ by $-a$. 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 $a*b$ as $ab$ for brevity. We often denote the identity by $e$ or $1$, and the inverse of $a$ in $G$ by $a^{-1}$.
Note that in our group axioms above we don't assume commutativity (which means that if we have any $x$ and $y$, $x*y=y*x$), 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 $G$ (that is, the cardinality of $G$) the order of the group, and we denote it $|G|$ (also $O(G)$ or even $\#G$, though we will use $|G|$). 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 $a^{n}$ is 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.

### (Z$_2$,+)

Z$_2$={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 Z$_2$, 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 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 (Z$_2$,+) 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 (Z$_2$,+) is a group. Moreover, each element is its own inverse, and the identity is 0.
In the same way it can be shown that Z$_m$={0,1,...m-1}, the set of remainders when dividing integers by m is also a group. The operation is addition modulo m.

### ( (Z$_5$)$^*$, × )

In (Z$_5$)$^*$, (see group table) which means Z$_5$ without zero, we have {1,2,3,4}. These are just the elements of Z$_5$ 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.
* 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 ((Z$_5$)$^*$, ×) is a group.

#### Note

Z$_5$={0,1,2,3,4} is the additive group of integers modulo 5 and (Z$_5$)$^*$={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, $a/b$.
(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.
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 S$_n$, 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:
    $x*y(a,b,c)=(a,c,b)$ whereas, $y*x(a,b,c)=(c,a,b)$. (Try verifying this on your own.)This is generally true of most permutations.

## 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 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
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 $a^{n-1}$ is its inverse.
It's clear that a set containing only the identity ({e}, *) will always be a subgroup. In the above example with Z$_2$, ({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).
* Is Z$_2$ a subgroup of Z under addition?
* Is (Z$_2$, ×) a group? (× representing multiplication modulo 2). What about (Z$_2$$^*$, ×)?
* Identify all subgroups of Z$_3$
* Identify one subgroup of (Z, +)
* Prove that permutations of three elements are associative and have inverses. (Hint: write out all valid permutations)
* Find a nontrivial subgroup of the permutations of three elements.
* Is Z$_2$ a subgroup of Z$_5$ with addition modulo 5?
* 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 x$_0$x$_1$x$_2$...x$_n$ with either x$_i$ or x$_i$$^{−1}$ ∈ S for each i, 0<i>n. 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!
* a + b - c
* 2b + c
* a + b - a
* a - a = 0
* 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.
* a × b × c$^{−1}$ = 1
* aba$^{−1}$ ∈ H

##### Answers

    2. Z$_2$ is not, because 0 has no multiplicative inverse. Z$_2$$^*$ 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.
   * 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. b$^2$ × c or b$^2$c
    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.
* Consider a finite group G. Show that for all x ∈ G there exists an integer n such that x$^n$=e. The smallest positive integer that satisfies this condition is called the order of the element x; we denote the order with |x| here.
* Let a ∈ G. Prove that if a*b =e, then b*a = e. That is, any right inverse is a left inverse.
* Prove that the identity is unique.
* Prove that the inverse of an element is unique.
* Let a ∈ G. Prove that (a$^{−1}$)$^{−1}$ = a.
* (hard) Let G be a finite abelian group. Prove that there exists x$_0$,x$_1$,x$_2$,...,x$_k$ such that x$_0$$^{a0}$x$_1$$^{a1}$x$_2$$^{a2}$...x$_k$$^{ak}$ uniquely generates the elements of G for 0 ≤ a$_m$ ≤ |x$_m$| 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 ∈ H} 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.

### Example

In (Z12,+) ("clock arithmetic") there are several subgroups to choose from, and so there are many coset 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 :
| H2 = | { | 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$^{−1}$y ∈ 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.

### 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 Z$_n$.
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 $(HK)^{-1}$ must be the same. Since $HK=(HK)^{-1}=K^{-1}H^{-1}=KH$ since both H and K are groups. Thus, HK=KH. Conversely, let HK=KH. Then the set of the inverses $(HK)^{-1}=K^{-1}H^{-1}=KH=HK$, 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:
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 $aHa^{-1}=H$ for all a within G.
Proof: Suppose that $aHa^{-1}=H$ for all a within G. Then (gH)(g'H)=$(gg'(g'^{-1}Hg'H)=gg'HH=gg'H$. Conversely, suppose that (gH)(g'H)=(gg')H. Then $aHa^{-1}$ must be a subset of $aHa^{-1}H$ since H contains the identity. This, of course, is the same as $aa^{-1}H$=H implying that $aHa^{-1}$ is a subset of H. This also means that H is a subset of $a^{-1}Ha$, and replacing a with $a^{-1}$, we get that H is a subset of $aHa^{-1}$, implying that $aHa^{-1}$ 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.
* 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={h$_0$=e, h$_1$, ..., h$_n$}, then gH = {gh$_0$=e, gh$_1$, ..., gh$_n$}, but, since we have that G is abelian, we can write {h$_0$g=e, h$_1$g, ..., h$_n$g} 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 $a^{-1}H$.
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 S$_3$. Consider each element s of S$_3$:
* 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 one of the two cosets above. You can check this for yourself.
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 (Z$_5$, +). This is a group under addition. Let's look at one specific element in Z$_5$: 2.
Observe, in Z$_5$:
    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 Z$_5$! 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, a$^n$, so if we want to represent 2+2+2+2 in Z$_5$, we often just write 2$^4$.
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 $x=1^{n}=1+1+...+1$ 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 = g$^a$, y = g$^b$ ∈ G:
    $x\cdot y=g^{a}\cdot g^{b}=g^{a+b}=g^{b+a}=g^{b}\cdot g^{a}=y\cdot x$.

#### Exercise

* Verify that 1, 3, and 4 are also generators for (Z$_5$, +).
* Let G be of order n, and let it be generated by a. Then prove that the following are equivalent:
** The order of $a^{x}$ is n.
** n and x are coprime.
** There is a number y such that xy is congruent to 1 mod n.

### 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 S$_n$, and of the set J, we write Sym(J).
The order of S$_n$ is n!. As such, the number of elements in S$_n$ 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 A$_n$

#### The dihedral group

The dihedral group of order 2n is the group with generators R and F such that:
$R^{n}$=I, $F^{2}$=I, $RF=FR^{-}$ 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, i.e., 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 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 (G$_1$, *), and (G$_2$, o), a homomorphism is a mapping or a function f from G$_1$ to G$_2$, and x, y being elements in G$_1$, 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 G$_1$ to a unique element of G$_2$ (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 G$_1$ to all elements in G$_2$, (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 Z$_2$, {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.

#### Kernel

We call the elements of G$_1$ that get mapped under f to the identity of G$_2$ the kernel of f, denoted Ker(f). What can we discover about this set?
Say a,b ∈ G$_1$ and f(a) = f(b) = 1$_{G2}$, that is, a and b are in the kernel. Then f(a * b) = f(a) o f(b) = 1$_{G2}$, so a * b is in the kernel also. That is, the kernel is closed. Also, f(1$_{G1}$) = f(1$_{G1}$ * 1$_{G1}$) = f(1$_{G1}$) o f(1$_{G1}$), so f(1$_{G1}$) = 1$_{G2}$. That is, the identity of G$_1$ is in the kernel. One more thing is that 1$_{G2}$ = f(1$_{G1}$) = f(a * a$^{−1}$) = f(a) o f(a$^{−1}$) = 1$_{G2}$ 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 G$_1$.
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 G$_1$. The converse is true also: every normal subgroup N gives a homomorphism. The homomorphism is given by f(a) = aN = Na for a ∈ G$_1$ and aN ∈ G$_2$. That is, the elements of G$_2$ are the cosets of N. Try verifying that this is a homomorphism by checking that f(a * b) = f(a) o f(b). G$_2$ is called a quotient group of G$_1$, and this relationship is written G$_2$ = G$_1$/N. More on this later.
Then the homomorphisms from G$_1$ are in one-to-one correspondence with the normal subgroups of G$_1$. 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 S$_n$ containing even permutations. In selecting the even permutations, we have created a surjective homomorphism from S$_n$ to (Z$_2$,+). Even permutations are mapped to the identity, 0, whilst odd permutations are mapped to 1.
The kernel then is all the even permutations of S$_n$.
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 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}$ = 1$_{G2}$ => g*h$^{−1}$ = 1$_{G1}$ => g = h.

### An example

Let's look at two small groups B=(Z$_2$,+) and C=({1, -1}, ×), where + represents addition modulo 2.
For clarity we represent the element "1" in B as 1$_B$, and the element "1" in C as 1$_C$. We can create an isomorphism, by defining f to map 0 to 1$_C$, 1$_B$ 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)=1$_C$×1$_C$=1$_C$, f(0+0)=f(0)=1$_C$
    f(0+1$_B$)=f(0)×f(1$_B$)=-1, f(0+1$_B$)=f(1$_B$)=-1
    f(1$_B$+0)=f(1$_B$)×f(0)=-1×1$_C$=-1, f(1$_B$+0)=f(1$_B$)=-1
    f(1$_B$+1$_B$)=f(1$_B$)×f(1$_B$)=-1×-1=1$_C$, f(1$_B$+1$_B$)=f(0)=1$_C$
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 (Z$_3$\{0}, ×)
Normally, we have the multiplication table
    ${\begin{matrix}\times &1&2\\1&1&2\\2&2&1\\\end{matrix}}$
Consider then the homomorphism f such that f(x)=2×x (modulo 3, naturally). Applying this homomorphism we obtain the multiplication table:
    ${\begin{matrix}\times &1&2\\1&2&1\\2&1&2\\\end{matrix}}$

#### 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 it 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 Z$_3$ 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.
Z$_3$ :
| + | 0 | 1 | 2 |
| 0 | 0 | 1 | 2 |
| 1 | 1 | 2 | 0 |
| 2 | 2 | 0 | 1 |
Z$_{abc}$ : 0→a, 1→b, 2→c :
| + | a | b | c |
| a | a | b | c |
| b | b | c | a |
| c | c | a | b |
Z$_{acb}$ : 0→a, 1→c, 2→b :
| + | a | c | b |
| a | a | c | b |
| c | c | b | a |
| b | b | a | c |
Notice that Z$_{abc}$ = Z$_{acb}$. For example, b + c = a in both groups.
The following consists 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

* Prove that the center of a group is always a subgroup.
* Prove that there is a one-to-one correspondence between the conjugacy classes of the permutation group S$_n$ 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 $ab{-1}$ belongs on N, so it belongs on K, indicating that f($ab{-1}$)=f(a)f($b{-1}$)=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($ab{-1}$)=1, so $ab{-1}$ 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:

### 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

* HN=NH, so HN is a subgroup of G.
* N is a normal subgroup of HN
* The intersection of H and N is a normal subgroup of H.
Proof
* hN=Nh for every h within H.
* aN=Na for any a within G, so aN=Na for any a within HN.
* 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 $f:(G/N)\rightarrow G/H$ 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).

### 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, $H_{1}$ is a subgroup of $H_{2}$ if and only if $H_{1}/N$ is a subgroup of $H_{2}/N$, 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$H_{1}$ is a normal subgroup of $H_{2}$ if and only if $H_{1}/N$ is a normal subgroup of $H_{2}/N$.
Proof Given the fact that this is one-to-one, we can also form the inverse of f by using $f^{-1}(A/N)=A$, which is also a one-to-one function. Thus, f is a bijection. It is also quite obvious that when $H_{1}$ is a subgroup of $H_{2}$, that $H_{1}/N$ is a subgroup of $H_{2}/N$. Conversely, when $H_{1}/N$ is a subgroup of $H_{2}/N$, the application of the inverse of f also makes it obvious that $H_{1}$ is a subgroup contained within $H_{2}$, automatically making $H_{1}$ a subgroup of $H_{2}$. We prove that the number of cosets in both cases is the same by defining the bijection $g(aH_{1})=(aN)(H_{1}/N)$ which is well-defined because if $aH_{1}=bH_{1}$ then they belong to the same coset of $H_{1}$, they also belong to the same coset of $H_{1}/N$. Now suppose that H is a normal subgroup of G. Then $(aN)(H/N)(aN)^{-1}=(aHa^{-1})/N=H/N$ 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 $h(x)=(xN)(H/N)$ 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 $H_{1}$ is a normal subgroup of $H_{2}$. Then if we consider N as a normal subgroup of $H_{2}$, then we immediately get the result that whenever $H_{1}/N$ is normal in $H_{2}/N$, that $H_{1}$ is normal in $H_{2}$ 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 $G$ and an element $a$ in $G$, it's easily seen that the mapping $\phi :G\to G$ defined by $\phi (x)=a^{-1}xa$ is an automorphism of $G$, so each element in $G$ gives rise to an automorphism. Different elements may give rise to the same automorphisms. For example, if $G$ is abelian, then all such automorphisms are identity map. In this sense we say the group $G$ acts on the set $G$: for any $x$ in the set $G$, the group $G$ acts on it by sending $x$ to $a^{-1}xa$.

#### Definition

Given a group $G$ and a set $X$, a $G$-action on $X$ is a homomorphism $\rho$ from $G$ into the permutation group of $X$. Recall that permutations on $X$ forms a group with composition of mappings as the group operation, so $\rho$ is a homomorphism implies, first of all, the identity in $G$ maps to the identity permutations, and secondly, given $g$ and $h$ in $G$ and $x$ in $X$, $g(h(x))=(gh)(x)$; that is, the product of two elements in $G$ has the same effect as the action of each element applied in turn.

#### Orbit, stabilizer 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 $x$ of $X$, the orbit of $x$, denoted by $G_{x}$, is the set of points $g(x)$ for all $g$ in $G$.
Exercise: An orbit is an equivalence class; that is, for any $x$, $y$ in $X$, the relation defined by $x\sim y$ iff $\exists g\in G$ such that $g(x)=y\,$ is an equivalence relation.
It is possible that two element of $G$, whose permutations on $X$ are different, send $x$ to the same place. So how to find the number of possible different destinations of $x$, the order of $G_{x}$? Instead of applying every element in $G$ on $x$ to see if they works differently, we look for the other extreme, elements in $G$ that do not move $x$.
For any $x$ in $X$, the stabilizer of $x$, denoted by $S(x)$, is the set of elements of $G$ that leaves $x$ fixed. It can be checked that $S(x)$ is a subgroup in $G$. Consider the left cosets of $S(x)$. Any element in a left coset $aS(x)$ can be written as the product $as_{1}$ for some $s_{1}$ in $S(x)$. The action of $as_{1}$ on $x$ then becomes $as_{1}(x)=a(s_{1}(x))=a(x)$. On the other hand, given an element $b$ in $G$ that has the same effect on $x$ as $a$, we have $a(x)=b(x)$ so $b^{-1}a(x)=x$. This implies $b^{-1}a$ belongs to $S(x)$, and $a$, $b$ must belong to the same left coset of $S(x)$.
We have proved the following
Theorem: $G$ is a group acting on the set $X$. Given $x\in X$, the left cosets of $S(x)$ correspond 1-1 to the orbit of $x$.
Since $S(x)$ is a subgroup of $G$, number of cosets equals to ${|G| \over |S(x)|}$. Since the orbits are equivalent classes dividing the set $X$, we have the following
Theorem (class equation): $|X|=\sum _{x\in X}{|G| \over |S(x)|}$ while the element $x$ is taken from each equivalent class.
If the stabilizer of every element of $X$ is the trivial subgroup, then the $G$-action is said to act freely.

#### Problem set

* 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.)
* Prove that the action of G upon any orbit is also a G-action.
* Prove that the stabilizer is always a subgroup.
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, b$^c$ means b×b×b×..., b multiplied by itself c times. However, in a group under addition, we still write b$^c$, but this means b+b+b...=cb. This can be confusing the first time you see an expression like $2^{3}=6$ or $1^{4}=4$. -->