# Introduction to group theory

Group theory is the study of algebraic structures called groups. This introduction will rely heavily on set theory and modular arithmetic as well. Later on it will require an understanding of mathematical induction, functions, bijections, and partitions. Lessons may utilize matrices and complex numbers as well.
After completing this section move on to Introduction to group theory/Part 2 Subgroups and cyclic groups.

## Introduction

What is a group? A more rigorous definition will come shortly but to give a very rough idea of a group it is a set and a operation. For example the integers under addition form a group, notated as ($\mathbb {Z}$, +) or simply $\mathbb {Z}$, where the operation is assumed to be addition.
Some more examples of groups are
* The real numbers under addition: ($\mathbb {R}$, +) or simply $\mathbb {R}$
* The rational numbers under addition: ($\mathbb {Q}$, +) or simply $\mathbb {Q}$
* The non-zero real numbers under multiplication: ($\mathbb {R}$$^*$, ×)
* The set of 2x2 matrices with integer entries under matrix addition: (M$_2$($\mathbb {Z}$), +)
All of these structures have things in common; they are all integral to being groups. They also have things in common that aren't necessary to groups. Let's examine some of these similarities.

### Closure Under the Operation

All of these groups have a closed binary operation. For example in ($\mathbb {Z}$, +) any two integers added together will be another integer. In other words if n,m ∈$\mathbb {Z}$ then (n+m)∈$\mathbb {Z}$.
In general for (G, *) to be a group where G is a set and * is a binary operation, if a,b are in G then (a*b) is also in G. This is called closure. Notice that all of the groups in the above examples are closed under their respective operations.

### Associativity

With the integers under addition
    $2+(11+5)=(2+11)+5\,$
With the non-zero real numbers under multiplication
    $3*(2*5)=(3*2)*5\,$
This is called associativity and is required for a structure to be a group. In general if (G,*) is a group and a,b,c∈G then
    $a*(b*c)=(a*b)*c\,$

### Identity

When we look at $\mathbb {Z}$ there's something special about the element 0. Notice that for any integer m
    $0+m=m+0=m\,$
Zero is the only element in this group with this property and it's called the identity of the group.
Zero is also the identity in the groups $\mathbb {Q}$, and $\mathbb {R}$.
In $\mathbb {R}$* the element $1$ is the identity as
    $1*a=a*1=a$
for all a in $\mathbb {R}$.
In general if (G,*) is a group then there exists an identity element e in G such that for any g in G
    $e*g=g*e=g$
This element is called the identity of G or e$_G$.

### Inverses

In $\mathbb {Z}$ if $m$ is an integer consider
    $m+x=0$
It would then follow that $x=(-m)$ and in fact $x$ is an integer as well.
In $\mathbb {R}$$^*$ if r is a non-zero real number then
    $r*x=1$
has a solution. Further $x=1/r=r^{-1}$ and x is also a non-zero real number.
In general if (G, *) is a group with identity $e$ and $a$ is an element of G then there exists an element $a^{-1}$ also in G such that
    $a*a^{-1}=e=a^{-1}*a$.
Note that $a^{-1}$ at this point is purely notational. If we are looking at the group of integers under addition then $3^{-1}$ means $-3$ since
    $3+(-3)=0$.
It does not mean $1/3$ in this group.

### Possible Misconceptions

In all of the above examples the underlying set of the groups are infinite, but groups need not be infinite. Note that with the requirement of an identity element the underlying set cannot be the empty set.
All of the groups above are commutative. That is that $a*b=b*a$. This is not true of all groups in general. Groups that are commutative are called Abelian Groups.

### Non-groups

To solidify our understanding let's look at some structures that aren't groups.
Firstly ({0,1,2,3},+) is not a group as $2+3=5$ and $5$ is not in {0,1,2,3} and this set is not closed under our operation.
Consider $\mathbb {N}$ under addition. This set is closed but it doesn't have inverses therefore it is not a group.
Consider the set of all matrices under addition. This is not a group because not all matrices can be added. Consider for example a 2x2 matrix and a 3x3 matrix.
Consider ($\mathbb {R}$, *). This is not a group because 0 doesn't have an inverse and since $0*1\neq 1$, there is no identity.

## Definition

A set G under the closed binary operation * is a group denoted (G,*) or simply G iff
* G under * is associative: $\forall a,b,c\in G,a*(b*c)=(a*b)*c$
* G under * has an identity element: $\exists e\in G$ such that $\forall a\in G,a*e=a=e*a$
* Each element in G has an inverse under *: $\forall g\in G\exists g^{-1}\in G$ such that $g*g^{-1}=e=g^{-1}*g$ where $e$ is the identity in G.

### Notation Notes

Since groups are associative it is common place to drop the parentheses when one is working with something shown to be a group. If a structure has yet to be shown to be associative do not drop the parentheses when working with elements of it. Do not however drop parentheses when working with inverses. For example $(ab)^{-1}$ and $ab^{-1}$ are not necessarily the same. Note that $ab^{-1}$ is assumed to mean $a*(b^{-1})$.
Since groups only have one operation it is usually dropped much like multiplication in elementary algebra. For example:
    $a*b=c$ becomes $ab=c$.
Dropping both the parentheses and the operation symbol leads to long strings of elements being unambiguous. For example any interpretation of $abcx$ is equivalent. I.e.
    $a*(b*(c*x)))=(a*b)*(c*x)=((a*b)*c)*x$
In most groups $e$ is assumed to be the identity and is used in arbitrary groups where the identity is unknown.
When strings of the same element are being multiplied we use exponent notation to represent it. For example
    $a*a*a*a=a^{4}$
Do note that we must be careful not to assume elements commute. Thus
    $a*b*b*a*b=a*b^{2}*a*b$ but can be simplified no further.
In abelian groups (commutative groups) and later on in the study of Rings additive notation can be used in place of multiplicative. For example
    $a^{2}*b*c^{-1}$ becomes $2a+b-c$.

### Multiplying

Note that "=" is an equivalence relation and thus we can substitute. For example in a group G suppose $a,b,c\in G$ such that $a=b$. Then by closure $ac\in G$, and by reflexivity $ac=ac$. We may substitute to arrive at $ac=bc$. Thus
    $a=b\implies ac=bc$
This is called multiplying on the right by $c$. Similarly
    $a=b\implies ca=cb$
is called multiplying on the left.

### Advice

Now we may begin to play with some equations. Moving on it is best to try to "forget" our assumptions about algebra we have learned from our elementary courses and only use what is explicitly proven.

## Theorems From the Definition

These are important theorems that follow directly from the definition of a group. Attempt the proofs yourself before looking at the solutions.

### Uniqueness of the Identity Element

An important theorem to begin with is the uniqueness of the identity. More precisely stated: Let G be a group. If
    $\exists e,e'\in G$ such that
    $(\forall a\in Ga*e=a=e*a)\land (\forall a\in Ga*e'=a=e'*a)$
then
    $e=e'$
Proof

### Cancellation

This theorem lets us cancel elements exactly opposite of how we multiply them.
Right Cancellation Theorem: $ac=bc\implies a=b$.
Right Cancellation Proof
Left cancellation is similarly proven. Theorem: $ca=cb\implies a=b$.

### Uniqueness of Inverses

This theorem states that each element has only one inverse. Theorem: Let G be a group. Then if $g,a,b\in G$ such that $a$ and $b$ are both inverses of $g$ then $a=b$.
Proof

### Socks and Shoes

This theorem is a way to distribute inverses.
Theorem: For group elements $a$ and $b$,
    $(ab)^{-1}=b^{-1}a^{-1}$.
Induction can be used to prove the more powerful socks and shoes theorem.
Theorem: For groups elements $a_{1},a_{2},\ldots ,a_{n}$
    $(a_{1}*a_{2}*\ldots *a_{n})^{-1}=a_{n}^{-1}*\ldots *a_{2}^{-1}*a_{1}^{-1}$.
Proof

## Integer Modulo Groups

Note that $\mathbb {Z} _{n}$= {0,1,2,...,n-1}. It happens that ($\mathbb {Z} _{n}$,+mod(n)) is a group and is written $\mathbb {Z} _{n}$ for short.

### Arithmetic Examples

In $\mathbb {Z} _{8}$
    $2+2=4$
    $5+5=2$
    $7+1=0$
In $\mathbb {Z} _{5}$
    $4+4=3$
    $1+1=2$

## Dihedral Groups

The dihedral groups arise from looking at the symmetries of regular polygons.

## Cayley Tables

A Cayley table is a table that displays the products of elements of the group under the operation.
For example, the Cayley table of $(\mathbb {Z} _{3},+mod(n))$ is:
| + | 0 | 1 | 2 |
| 0 | 0 | 1 | 2 |
| 1 | 1 | 2 | 0 |
| 2 | 2 | 0 | 1 |

## Homework

Attempt the proofs and problems on your own before looking at the solutions.
Problem 1.
    Prove that cross cancellation implies commutativity. That is assume
$ac=cb\implies a=b$ and show $\forall x,y\in G,xy=yx$ Solution