# Tuesday August 20th

## The Fundamental Homomorphism Theorems

**Theorem 1:**
Let $\varphi: G \to G'$ be a homomorphism.
Then there is a canonical homomorphism $\eta: G \to G/\ker \varphi$ such that the usual diagram commutes.

Moreover, this map induces an isomorphism $G /\ker \varphi \cong \im \varphi$.

**Theorem 2:**
Let $K, N \leq G$ and suppose $N \normal G$.
Then there is an isomorphism
$$
\frac K {K \intersect N} \cong \frac {NK} {N}
$$

*Proof Sketch:*
Show that $K \intersect N \normal G$, and $NK$ is a subgroup exactly because $N$ is normal.

**Theorem 3:**
Let $H, K \normal G$ such that $H \leq K$.

Then

1. $H/K$ is normal in $G/K$.

2. The quotient $(G/K) / (H/K) \cong G/H$.

*Proof:*
We'll use the first theorem.

Define a map
\begin{align*}
\phi: G/K &\to G/H \\
gk &\mapsto gH
.\end{align*}

*Exercise*:
Show that $\phi$ is surjective, and that $\ker \phi \cong H/K$.

$\qed$

## Permutation Groups

Let $A$ be a set, then a *permutation* on $A$ is a bijective map $A \selfmap$.
This can be made into a group with a binary operation given by composition of functions.
Denote $S_{A}$ the set of permutations on $A$.

**Theorem:**
$S_{A}$ is in fact a group.

*Proof:*
Exercise.
Follows from checking associativity, inverses, identity, etc.

$\qed$

In the special case that $A = \theset{1, 2, \cdots n}$, then $S_{n} \definedas S_{A}$.

Recall two line notation
$$
\left(\begin{matrix}
1 & 2 & \cdots & n\\
\sigma(1) & \sigma(2) & \cdots & \sigma(n)
\end{matrix}\right)
$$

Moreover, $\abs{S_{n}} = n!$ by a combinatorial counting argument.

*Example:*
$S_{3}$ is the symmetries of a triangle.

*Example:*
The symmetries of a square are *not* given by $S_{4}$, it is instead $D_{4}$.

## Orbits and the Symmetric Group

Permutations $S_{A}$ *act* on $A$, and if $\sigma \in S_{A}$, then $\generators{\sigma}$ also acts on $A$.

Define $a \sim b$ iff there is some $n$ such that $\sigma^{n}(a) = b$. This is an equivalence relation, and thus induces a partition of $A$. See notes for diagram.
The equivalence classes under this relation are called the *orbits* under $\sigma$.

*Example:*
$$
\left(\begin{matrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
8 & 2 & 6 & 3 & 7 & 4 & 5 & 1
\end{matrix}\right) = (1 8)(2)(3 6 4)(5 7).
$$

**Definition:**
A permutation $\sigma \in S_{n}$ is a *cycle* iff it contains at most one orbit with more than one element.

The *length* of a cycle is the number of elements in the largest orbit.

Recall cycle notation: $\sigma = (\sigma(1) \sigma(2) \cdots \sigma(n))$.

> Note that this is read right-to-left by convention!

**Theorem:**
Every permutation $\sigma \in S_{n}$ can be written as a product of disjoint cycles.

**Definition:**
A *transposition* is a cycle of length 2.


**Proposition:**
Every permutation is a product of transpositions.

*Proof:*
$$
(a_{1} a_{2} \cdots a_{n}) = (a_{1} a_{n}) (a_{1} a_{n-1}) \cdots (a_{1} a_{2})
.$$

$\qed$

This is not a unique decomposition, however, as e.g. $\id = (1 2)^{2} = (3 4)^{2}$.

**Theorem:**
Any $\sigma \in S_{n}$ can be written as **either**

- An even number of transpositions, or

- An odd number of transpositions.

*Proof:*

Define
$$
A_{n} = \theset{\sigma \in S_{n} \suchthat \sigma\text{ is even}}
.$$

We claim that $A_{n} \normal S_{n}$.

1. Closure: If $\tau_{1}, \tau_{2}$ are both even, then $\tau_{1}\tau_{2}$ also has an even number of transpositions.

2. The identity has an even number of transpositions, since zero is even.

3. Inverses: If $\sigma = \prod_{i=1}^{s} \tau_{i}$ where $s$ is even, then $\sigma\inv = \prod_{i=1}^{s} \tau_{s-i}$.
But each $\tau$ is order 2, so $\tau\inv = \tau$, so there are still an even number of transpositions.

So $A_{n}$ is a subgroup.

It is normal because it is index 2, or the kernel of a homomorphism, or by a direct computation.

## Groups Acting on Sets

Think of this as a generalization of a $G\dash$module.

**Definition:**
A group $G$ is said to *act* on a set $X$ if there exists a map $G\cross X \to X$ such that

1. $e\actson x = x$

2. $(g_{1} g_{2})\actson x = g_{1} \actson (g_{2} \actson x)$.

*Examples:*

1. $G = S_{A} \actson A$

2. $H \leq G$, then $G \actson X = G/H$ where $g \actson xH = (gx)H$.

3. $G \actson G$ by conjugation, i.e. $g\actson x = gxg\inv$.

**Definition:**
Let $x\in X$, then define the **stabilizer subgroup**
$$
G_{x} = \theset{g\in G \suchthat g\actson x = x} \leq G
$$

We can also look at the dual notion,
$$
X_{g} = \theset{x\in X \suchthat g\actson x = x}.
$$

We then define the *orbit* of an element $x$ as
$$
Gx = \theset{g\actson x \suchthat g\in G}
$$
and we have a similar result where $x\sim y \iff x\in Gy$, and the orbits partition $X$.


**Theorem:**
Let $G$ act on $X$. We want to know the number of elements in an orbit, and it turns out that

\begin{align*}
\abs{Gx} = [G: G_{x}]
\end{align*}

*Proof:*
Construct a map $Gx \mapsvia{\psi} G/Gx$ where $\psi(g\actson x) = g Gx$.

*Exercise:*
Show that this is well-defined, so if 2 elements are equal then they go to the same coset.

*Exercise*:
Show that this is surjective.

Injectivity: $\psi(g_{1} x) = \psi(g_{2} x)$, so $g_{1} Gx = g_{2} Gx$ and $(g_{2}\inv g_{1}) Gx = Gx$ so
$$
g_{2}\inv g_{1} \in Gx \iff g_{2}\inv g_{1} \actson x = x \iff g_{1}x = g_{2} x
.$$
$\qed$

Next time: Burnside's theorem, proving the Sylow theorems.