Abstract-Algebra.tex

\documentclass[]{article}
\input{../mathdoc}
\input{../mathsym}
\input{../theorem}

\author{Presenter: Igor Erovenko, Notes by Michael Reed, Book: Thomas Judson 2017,}
\title{Abstract Algebra}
\date{Fall 2017, \today}

\begin{document}
\maketitle

%\begin{abstract}
%\end{abstract}

\section{Proofs}

Let $p$ and $q$ be statements. \say{If $p$ then $q$.} $p$ is the hypothesis and $q$ is the conclusion. \ul{Implication} is $p\implies q$, read \say{$p$ implies $q$.}
\begin{center}
\begin{tabular}{|c|c|c|}
	\hline 
	$p$ & $q$ & $p\implies q$ \\ 
	\hline 
	T & T & T \\ 
	\hline 
	T & F & F \\ 
	\hline 
	F & T & T \\ 
	\hline 
	F & F & T \\ 
	\hline 
\end{tabular}
\end{center}

\subsection*{Methods of proof}

\begin{enumerate}
	\item Direct proof. Assume $p$ is true, show $q$ is true. $p\implies \dots \implies \dots \implies\dots \implies q$.
	\begin{example}
		Show that if $n$ is an odd integer, then $n^2$ is odd. $p = $ \say{$n$ is odd} and $q = $ \say{$n^2$ is odd.}
		\begin{proof}
			Suppose $n$ is an odd integer. Then $n = 2k+1$ for some integer $k$. In this case, $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$. Notice that $2k^2+2k$ is an integer. So, $n^2$ is odd.
		\end{proof}
	\end{example}
	\item Reduction to cases. If $p$ is true, then one of $p_1,p_2,\dots,p_n$ must be true. Then show each $p_i \implies q$.
	\begin{example}
		Show that if $n$ is an integer, then $n^2-n$ is even. $p = $ \say{$n$ is an integer} and $q = $ \say{$n^2-n$ is even.}
		\begin{proof}
			Suppose $n$ is an integer. Then $n$ is even or odd.
			\ul{Case 1}: $n$ is even. In this case, $n=2k$ for some integer $k$ and $n^2-n = (2k)^2 - 2k = 4k^2 - 2k = 2(2k^2-k)$ is even. \ul{Case 2}: $n$ is odd. In this case $n = 2k+1$ for some integer $k$ and $n^2-n = (2k+1)^2-(2k+1) = 4k^2 + 4k + 1 - 2k -1 = 4k^2 +2k = 2(2k+k)$ is even.
		\end{proof}
	\end{example}
	\item Proof by contradiction. If $p$ is true, then either $q$ is true or it is not true. Show that $\neg q$ is impossible. Assume: $p$ is true and $q$ is false (not $q$ is true). Show: this leads to a contradiction.
	\begin{example}
		Show that $\sqrt{2}$ is irrational. If $r$ is rational, then $r^2 \neq 2$.
		\begin{proof}
			Assume $r$ is rational and $r^2 = 2$. Then $r = \frac{m}{n}$ for some integers $m$ and $n$, in lowest terms. Then $(\frac{m}{n})^2 = 2$. So, $m^2 = 2n^2$. It follows that $m^2$ is even, and hence $m$ is even. Then $m = 2k$ and we get $(2k)^2 = 4k^2 = 2n^2$ or $2k^2 = n^2$. Therefore $n^2$ is even, and consequently $n$ is even. Both $m$ and $n$ are even, which contradicts our assumption that $\frac{m}{n}$ is in lowest terms. Therefore $r^2 \neq 2$ and $\sqrt{2}$ is irrational.
		\end{proof}
	\end{example}
\end{enumerate}

To disprove a general statement: find one counterexample.

\begin{example}
	Every integer is odd. False, $4$ is not odd.
\end{example}

Equivalences: $p$ if and only if $q$. $p\Longleftrightarrow q$, needs proofs for both $p\implies q$ and $q\implies p$.

\section{Sets}

A \ul{set} is a well-defined collection of objects. Requires a criterion for determining set membership. $a\in A$ means $a$ is a \ul{member} or an \ul{element} of a set $A$.

$$X = \set{ x_1,x_2,\dots,x_n}, \, X = \setc{x}{x \text{ satisfies } P} = \setm{x}{x \text{ satisfies } P}.$$

$\mb N$ naturals $\set{1,2,3,\dots}$.
$\mb Z$ integers $\set{\dots,-3,-2,-1,0,1,2,3,\dots}$.
$\mb Q$ rationals $\setm{\frac{m}{n}}{m,n\in \mb Z, n\neq 0}/\sim$.
$\mb R$ reals.
$\mb C$ complex numbers $\setm{a+bi}{a,b\in\mb R}$.
$\mb H$ Hamiltonian quaternions $\setm{a+bi+cj+dk}{a,b,c,d\in\mb R}$.

\begin{definition}
	[Subset] $A\subset B$ or $A\subseteq B$, $a\in A \implies a\in B$.
\end{definition}
\begin{definition}
	[Equality of sets]
	$A = B \Longleftrightarrow A \subseteq B$ and $B\subseteq A$.
\end{definition}

\begin{definition}
	[Proper subset] $A\subsetneq B \Longleftrightarrow A\subseteq B$ and $A\neq B$.
\end{definition}
\begin{definition}
	[Empty set] $\emptyset \subseteq A$ for any set $A$.
\end{definition}

\begin{definition}
	[Union] $A\cup B = \setm{x}{x\in A \text{ or } x\in B}$.
\end{definition}
\begin{definition}
	[Intersection] $A\cap B = \setm{x}{x\in A\text{ and } x\in B}$.
\end{definition}
\begin{definition}
	[Difference] $A-B = A\backslash B = \setm{x}{x\in A \text{ and } x\notin B}$.
\end{definition}

\begin{proposition}
	Let $A,B,$ and $C$ be sets.
	\begin{enumerate}
		\item $A\cup A = A$, $A\cap A = A$, $A\backslash A = \emptyset $.
		\item $A\cup \emptyset = A$, $A\cap \emptyset = \emptyset$.
		\item $A\cup (B\cup C) = (A\cup B)\cup C$.
		$A\cap (B\cap C) = (A\cap B) \cap C$.
		\item $A\cup B = B\cup A$. $A\cap B = B\cap A$.
		\item $A\cup (B\cap C) = (A\cup B) \cap (A\cup C)$.
		\begin{proof}
			Let $x\in A\cup (B\cap C)$. Then $x\in A$ or $x\in B\cap C$. \ul{Case 1}: $x\in A$. In this case, $x\in A\cup B$ and $x\in A\cup C$, so $x\in (A\cup B)\cap (A\cup C)$. \ul{Case 2}: $x\in B\cap C$. In this case, $x \in B$ and $x\in C$. So, $x\in A\cup B$ and $x\in A\cup C$. Hence $x \in (A\cup B)\cap (A\cup C)$. Therefore $A\cup (B\cap C) \subseteq (A\cup B)\cap (A\cup C)$.
		\end{proof}
		\item $A\cap (B\cup C) = (A\cap B) \cup (A\cap C)$.
	\end{enumerate}
\end{proposition}

\subsection*{Cartesian products and mappings}

Cartesian product of $A$ and $B$ is $A\times B = \setm{(a,b)}{a\in A \text{ and } b\in B}$.
In general, $A_1\times A_2\times\dots\times A_n = \setm{(a_1,a_2,\dots,a_n)}{a_i\in A_i \text{ for } 1\leq i \leq n}$.
\ul{Notation}: $A\times A\times \dots\times A = A^n$.

\begin{example}
	$\mb R^2, \mb R^3$.
\end{example}

A \ul{relation} from $A$ to $B$ is a subset of $A\times B$.
A \ul{mapping} (or a \ul{function}) $f$ from $A$ to $B$ is a relation from $A$ to $B$ such that for every $a\in A$ there exists a unique $b\in B$ for which $(a,b)\in f$. \ul{Notation}: $(a,b) \in f \ra f(a) = b$ or $f:a\mapsto b$ and on the level of sets $f:A\ra B$. $A$ is the domain of $f$, $B$ is the codomain, $f(A) = \{f(a)\mid a\in A\}\subseteq B$ is the range of $f$.

\begin{definition}
	A mapping $f:A\ra B$ is
	\begin{enumerate}
		\item \ul{injective} (or one-to-one) if $f(a_1) = f(a_2) \implies a_1 = a_2$.
		\item \ul{surjective} (or onto) if $f(A) = B$, or for every $b\in B$ there exists $a\in A$ such that $f(a) = b$.
		\item \ul{bijective} (or one-to-one correspondence) if it's injective and surjective.
	\end{enumerate}
\end{definition}
\begin{example}
	$f:\mb R\ra \mb R$, $f(x) = e^x$. $e^{x_1} = e^{x_2} \overset{?}{\implies} x_1 = x_2$ then $\ln(e^{x_1}) = \ln(e^{x_2})$, so injective. $f(\mb R) = \mb R^+ = (0,\infty) \neq \mb R$, not surjective and not bijective.
	$f:\mb R \ra (0,\infty)$ is bijective.
\end{example}
\begin{example}
	$f:\mb Z\ra\mb Z$, $f(n) = n^2$. $f(-1) = 1 = f(1)$, not injective. $2\notin f(\mb Z)$, not surjective.% and not bijective.
\end{example}
\begin{example}
	$f:\mb{R}\ra \mb R$, $f(x) = 2x+1$. $2x_1 + 1 = 2x_2 + 1 \implies x_1 = x_2$, injective. Given any $y\in \mb R$ find $x\in \mb R$ such that $2x+1 = y$: $x = (y-1)/2$, surjective and bijective.
\end{example}

A \ul{composition} of mappings $f:A\ra B$ and $g:B\ra C$ is a mapping $g\circ f: A\ra C$ defined by $(g\circ f)(a) = g(f(a))$. $A \overset{f}{\lra} B \overset{g}{\lra} C$ or $a \rightsquigarrow f(a) \rightsquigarrow g(f(a))$.
\begin{theorem}
	Let $f:A\ra B$, $g:B\ra C$, and $h:C\ra D$ be mappings.
	\begin{enumerate}
		\item The composition of mappings is associative: $(h\circ g) \circ f = h\circ(g\circ f)$.
		\item If $f$ and $g$ are injective, then so is $g\circ f$.
		\item If $f$ and $g$ are surjective, then so is $g\circ f$.
		\item If $f$ and $g$ are bijective, then so is $g\circ f$.
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item Let $a\in A$. Then $((h\circ g)\circ f)(a) = (h\circ g)(f(a)) = h(g(f(a))) \equiv h((g\circ f)(a)) = (h\circ(g\circ f))(a)$.
		\item $(g\circ f)(a_1) = (g\circ f)(a_2) \implies g(f(a_1)) = g(f(a_2)) \implies f(a_1) = f(a_2) \implies a_1 = a_2$.
		\item $A\os{f}{\lra} B \os{g}{\lra} C$ or $A\os{g\circ f}{\lra} C$. $g(b) = c$, $f(a) = b$.
	\end{enumerate}
	Done.
\end{proof}

\begin{definition}
	The \ul{identity} mapping on a set $A$ is $\text{id}_A: A\ra A$, $\text{id}_A(a) = a$.
	An \ul{inverse} mapping of a mapping $f:A\ra B$ is a mapping $g:B\ra A$ such that $g\circ f = \text{id}_A \ra g(f(a)) = a$, $f\circ g = \text{id}_B \ra f(g(b)) = b$.
	A mapping is \ul{invertible} if it has an inverse mapping. \ul{Notation}: $f\inv$ inverse of $f$.
\end{definition}

\begin{theorem}
	A mapping is invertible $\Leftrightarrow$ it is bijective.
\end{theorem}

\subsection*{Equivalence relations}

\begin{definition}
	An \ul{equivalence relation} on a set $X$ is a relation $R\subset X\times X$ which is
	\begin{enumerate}
		\item \ul{Reflexive}: $(x,x)\in R$ for all $x\in X$
		\item \ul{Symmetric}: $(x,y)\in R \implies (y,x)\in R$
		\item \ul{Transitive}: $(x,y)\in R,(y,z)\in R\implies (x,z)\in R$
	\end{enumerate}
	\ul{Notation}: $x\sim y$ for $(x,y)\in R$.
\end{definition}
\begin{example}
	$X=\mb R$, $a\sim b$ if $a<b$. Reflexive: $0\nless 0$. Symmetric: $0<1$ but $1\nless 0$. Transitive: $a<b$ and $b<c\implies a<c$. However, for $a\neq b$ either $a<b$ or $b<a$ (antisymmetric).
\end{example}
\begin{example}
	$X = \mb R$, $a\sim b$ if $ab\geq 0$. \ul{Reflexive}: $a\sim a \Leftrightarrow a^2 \geq0$. \ul{Symmetric}: $a\sim b \implies b\sim a$ or $ab\geq 0\implies ba\geq 0$. \ul{Transitive}: $a\sim b,b\sim c\implies a\sim c$ or $ab\geq 0,bc\geq 0 \implies ac\geq 0$. Counterexample: $a=-1,b=0,c=1$.
\end{example}
\begin{example}
	$X$ any set, $x\sim y$ if $x=y$. \ul{Reflexive}: $x\sim x \Leftrightarrow x=x$. \ul{Symmetric}: $x\sim y\implies y\sim x$ or $x=y\implies y=x$. \ul{Transitive}: $x\sim y,y\sim z\implies x\sim z$ or $x=y,y=z\implies x=z$.
\end{example}
\begin{example}
	$X = $ all differentiable functions $\mb R\ra\mb R$. $f\sim g$ if $f' = g'$. \ul{Reflexive}: $f\sim f \Leftrightarrow f' = f'$. \ul{Symmetric}: $f\sim g \implies g\sim f$ or $f' = g' \implies g' = f'$. \ul{Transitive}: $f\sim g,g\sim h\implies f\sim h$ or $f' = g',g'=h'\implies f'=h'$.
\end{example}
\begin{example}
	$X = \mb R^2$, $(x_1,y_1)\sim (x_2,y_2)$ if $x_1^2 + y_1^2 = x_2^2 + y_2^2$.
\end{example}
\begin{example}
	$X = M_n(\mb R)$ all $n\times n$ matrices. $A\sim B$ if $\exists$ a nonsingular P such that $B = PAP\inv$. \ul{Reflexive}: $A = IAI\inv$ let $P = I$. \ul{Symmetric}: $A\sim B \implies B\sim A \lra A = *B*\inv$, then $B = PAP\inv \implies P\inv B = AP\inv \implies P\inv BP = A$, so let $* = P\inv$. \ul{Transitive}: $A\sim B,B\sim C\implies A\sim C$. $B = PAP\inv, C = SBS\inv \implies C = *A*\inv$. $C = SBS\inv = S(PAP\inv)S\inv = (SP)A(P\inv S\inv) = (SP)A(SP)\inv$, so $*= SP$.
\end{example}

\newpage

\begin{definition}
	Let $\sim$ be an equivalence relation on a set $X$, and let $x\in X$. Then the set $$[x] = \{y\in x \mid y\sim x\}$$ is the \ul{equivalence class} of $x$.
\end{definition}
\begin{example}
	$X$ is any set. $x\sim y$ if $x=y$. Then $[x] = \setm{y\in X}{y=x} = \set{x}$.
\end{example}
\begin{example}
	$X$ is the set of all differentiable functions from $\mb R\ra\mb R$. $f\sim g$ if $f' = g'$. $$[f] = \setm{g\in X}{g' = f'} = \setm{f + c}{c\in\mb R}.$$
\end{example}
\begin{example}
	$X = \mb R^2$. $(x_1,y_1)\sim (x_2,y_2)$ if $x_1^2 + y_1^2 = x_2^2 + y_2^2$. The equivalence class is a circle.
\end{example}

\begin{definition}
	A \ul{partition} of a set $X$ is a collection of disjoint nonempty subsets of $X$ which cover $X$.
	$$\mc P = \set{X_\alpha}_{\alpha\in \Lambda}, \quad X_\alpha\subseteq X,\ \forall \alpha,$$
	$X_\alpha \cap X_\beta = \emptyset \text{ if } \alpha \neq \beta$, disjoint, and $X = \bigcup_{\alpha\in\Lambda} X_\alpha$ cover $X$.
\end{definition}
\begin{theorem}
	Let $\sim $ be an equivalence relation on a set $X$. Then the equivalence classes of $\sim$ partition $X$. Conversely, given a partition $\mc P = \set{X_\alpha}_{\alpha\in\Lambda}$ of $X$, there exists an equivalence relation $\sim$ on $X$ such that $\set{X_\alpha}$ are the equivalence classes of $\sim$.
\end{theorem}
\begin{proof}
	Let $\sim$ be an equivalence relation on $X$. Then for every $x\in X$, $x\sim x$, so $x\in [x]$. Hence, $[x]\neq \emptyset$ for all $x\in X$. Also $\bigcup_{x\in X}[x] = X$. By definition $\bigcup_{x\in X}[x] \subseteq X$ and  every $x$ is in one of equivalence classes so $\bigcup_{x\in X}[x] \supseteq X$. It's left to prove that if $x,y\in X$ then $[x]\cap [y] = \emptyset$ or $[x]=[y]$.
	\ul{Case 1}: $[x]\cap[y] = \emptyset$ done. \ul{Case 2}: $[x]\cap[y]\neq \emptyset$ (WTS: $[x]=[y]$). There is $z\in[x]\cap[y]$. Then $z\in[x]$ and $z\in[y]$, so $z\sim x$ and $z\sim y$. By symmetric property $x\sim z$ and by transitive property $x\sim y$. Take any $a\in [x]$. Then $a\sim x$ and also $x\sim y$, so $a\sim y$ and thus $a\in [y]$. So $[x]\subseteq [y]$. If $x\sim y$ then $y\sim x \implies [y]\subseteq [x]$. Thus $[x]=[y]$.
	
	Conversely, let $\mc P = \{X_\alpha\}_{\alpha\in\Lambda}$ be a partition of $X$. Define a relation $\sim$ on $X$ by $x\sim y$ if $x$ and $y$ belong to the same $X_\alpha$ for some $\alpha\in\Lambda$. Show:
	\begin{enumerate}
		\item $\sim$ is an equivalence relation on $X$,
		\item the equivalence classes of $\sim$ are $X_\alpha$'s
	\end{enumerate}
	Done.
\end{proof}

\section*{Mathematical induction}

$$P(1),P(2),P(3),\dots,P(n),P(n+1),\dots$$

Mathematical induction: prove that $P(n)$ is true for all $n\geq 1$.

\begin{definition}
	[Well-Ordering Principle] Every nonempty subset of $\mb N$ contains a smallest element.
\end{definition}
\begin{theorem}
	[First principle of mathematical induction] Suppose $P(n)$ is a statement involving a positive integer $n$, and
	\begin{enumerate}
		\item \textit{Base}: $P(n_0)$ is true for some $n_0\in\mb N$
		\item \textit{Induction hypothesis}: $P(k)$ implies $P(k+1)$ for all $k\geq n_0$.
	\end{enumerate}
	$P(n)$ is true for all $n\geq n_0$.
\end{theorem}
\begin{remark}
	This is nothing but a \say{domino} effect. $P(k) = $ \say{domino $k$ falls}.
\end{remark}
\begin{proof}
	Assume on the contrary that not all $P(n)$ are true for $n\geq n_0$. Then $S = \{n\geq n_0\mid P(n) \text{ is false}\}\subseteq \mb N$ is a nonempty subset of $\mb N$. By the Well-Ordering Principle, the set $S$ contains a least element $m$. Then $P(m)$ is false and $m\neq n_0$ by assumption (1). This means that $m>n_0 \implies m-1\geq n_0$. So $P(m-1)$ is true since $m-1\notin S$. By assumption (2), if $P(m-1)$ is true, then $P(m)$ is true, which is a contradiction.
\end{proof}
\begin{example}
	$1+2+\dots+n = \frac{n(n+1)}{2}$ for all $n\geq 1$. $P(n) = $ \say{$1+2+\dots+n = \frac{n(n+1)}{2}$.}
	\ul{Base}: $P(1)$ is true since $1 = \frac{1\cdot(1+1)}{2}$.
	\ul{Inductive step}: Assume $P(k)$ is true for some fixed arbitrary $k \geq 1$. Want to show: $P(k+1)$ is true. Have: $1+2+\cdots+k = \frac{k(k+1)}{2}$. Want: $1+2+\dots+k + (k+1) = \frac{(k+1)(k+2)}{2}$.
	\begin{align*}
		1+2+\dots + k + (k+1) &= \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\
		&= \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}
	\end{align*}
	Therefore, $P(n)$ is true for all $n\geq 1$.
\end{example}
\begin{example}
	All cars are the same color. $P(n) = $ \say{in any collection of $n$ cars, all cars are the same color.} Will prove by induction that $P(n)$ is true for all $n\geq 1$. \ul{Base}: $P(1)$ is true. \ul{Inductive step}: $P(k)$ is true for some $k\geq 1$. WTS: $P(k+1)$ is true. Cars $c_1,\dots,c_k$ are same color. However $P(1)\nrightarrow P(2)$.
\end{example}

\begin{example}
	The UNCG poker club plays with \$5 and \$8 chips. What is the largest bet that cannot be made using these num? Largest bet that cannot be made is \$27.
	
	We need to show
	\begin{enumerate}
		\item A bet of \$27 cannot be made.
		\item Any bet $\geq \$28$ can be made.
	\end{enumerate}
	A bet of $\$n$ can be made if $n=5a+8b$, where $a$ and $b$ are nonnegative integers. Take this modulo 5, then $2\equiv 3b\pmod5$. Let $b=0$, then $2\not\equiv 0\pmod5$. Let $b=1$, then $2\not\equiv 3\pmod 5$. Let $b=2$, then $2\not\equiv 6\pmod5$. Let $b = 3$, then $2\not\equiv 9\pmod5$. Let $b=4$, then $2\equiv 12\pmod 12$. So $b\geq 4$ and $27 = 5a + 8b\geq 5a+32$ implies $5a\leq -5\implies a\leq -1$. $P(n) = $ \say{A bet of $\$n$ can be made} = \say{$n = 5a+8b$ for some nonnegative integers $a$ and $b$.} WTS: $P(n)$ is true for all $n\geq 28$.
	\ul{Base}: $P(28)$ is true since $28 = 5\cdot 4 + 8\cdot 1$.
	\ul{Inductive step}: Assume $P(k)$ is true for some arbitrary fixed $k\geq 28$. WTS: $P(k+1)$ is true. Assume: $k=5a+8b$. Want: $k+1 = 5\tilde a + 8\tilde b$. If $k = 5a+8b$ then $k+1 = 5a+8b+1$. Then $1 = 5\cdot(-3) + 8\cdot(2) = 5\cdot(5) + 8\cdot(-3)$. Then $5a+8b +1 = 5\cdot(a-3) + 8\cdot(b+2) = 5\cdot(a+5) + 8\cdot(b-3)$.
	\ul{Claim}: $a \geq 3$ or $b\geq 3$. Assume on the contrary $a<3$ and $b<3$. Then $k = 5a+8b \leq 5\cdot 2 + 8\cdot 2 = 26$. This is a contradiction.
	\ul{Case 1}: Let $a\geq 3$, then $k+1 = 5\cdot(a-3) + 8\cdot(b+2)$ is a valid bet.
	\ul{Case 2}: Let $b\geq 3$, then $k+1 = 5\cdot (a+5) + 8\cdot(b-3)$ is a valid bet.
\end{example}

\begin{theorem}
	[Second form of mathematical induction] Suppose $P(n)$ is a statement involving a positive integer $n$, and
	\begin{enumerate}
		\item $P(n)$ is true for some $n_0\in\mb N$.
		\item $P(n_0),P(n_0+1),\dots,P(k)\implies P(k+1)$ for all $k\geq n_0$.
	\end{enumerate}
	Then $P(n)$ is true for all $n\geq n_0$.
\end{theorem}
\begin{proof}
	Let $Q(n) = $ \say{$P(n_0),P(n_0+1),\dots,P(n)$ are true.} Apply the first principle of mathematical induction to the statements $Q(n)$. Let $Q(n_0) = $ \say{$P(n_0)$ is true}, then $Q(k) \implies Q(k+1)$.
\end{proof}
\begin{example}
	Every natural number $\geq 2$ is a product of primes.
	
	\ul{Base}: Let $n=2$, which is a prime.
	\ul{Inductive step}: Assume that all $2,3,\dots,k$ are products of primes. Look at $k+1$. \ul{Case 1}: $k+1$ is prime, then done. \ul{Case 2}: $k+1$ is composite, then $k+1 = uv$ with $u,v\geq 2$. Then $2\leq u,v\leq k$. Let $u = p_1p_2\cdots p_s$ and $v = q_1q_2\cdots q_r$, where $p_i,q_j$ are primes. Then $k+1 = p_1p_2\cdots p_sq_1q_2\cdots q_r$. m
\end{example}

\subsection{The division algorithm}
\begin{theorem}
	[The division algorithm] Let $a$ and $b>0$ be integers. Then there exist unique integers $q$ and $r$ such that $a = qb +r$, where $0\leq r < b$.
\end{theorem}
From now on: $a,b\in\mb Z$. If $a =kb$ for some $k\in\mb Z$ we say $b$ divides $a$ or $b\mid a$. An integer $d$ is a \ul{common divisor} of $a$ and $b$ if $d\mid a$ and $d\mid b$.
\begin{definition}
	The \ul{greatest common divisor} of integers $a$ and $b$ is a \ul{positive} integer $d$ such that
	\begin{enumerate}
		\item $d$ is a common divisor of $a$ and $b$
		\item any common divisor $d'$ of $a$ and $b$ divides $d$.
	\end{enumerate}
	\ul{Notation}: $d = \gcd(a,b) = (a,b)$.
	$a$ and $b$ are \ul{relatively prime} if $\gcd(a,b) = 1$.
\end{definition}
\begin{theorem}
	Let $a$ and $b$ be two integers ($\neq 0$).
	\begin{enumerate}
		\item $\gcd(a,b)$ is unique
		\item $\exists r,s\in\mb Z$ such that $\gcd(a,b) = ar+bs$.
	\end{enumerate}
	In particular, $\gcd$ exists.
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item Assume $d_1 = \gcd(a,b)$ and $d_2 = \gcd(a,b)$. WTS: $d_1 = d_2$.
		\begin{enumerate}
			\item[(a)] Assume $d_1$ is $\gcd$ and $d_2$ is common divisor, so $d_2\mid d_1 \implies d_2 \leq d_1$.
			\item[(b)] Assume $d_2$ is $\gcd$ and $d_1$ is common divisor, so $d_1\mid d_2 \implies d_1 \leq d_2$.
		\end{enumerate}
		So $d_1 = d_2$.
		
	\item $S = \setm{ am + bn}{m,n\in\mb Z;\ am+bn>0}\subseteq \mb N$. So $S$ is a nonempty subset of $\mb N$. Let $d$ be the least element of $S$ (Well-Ordering Principle). \ul{Claim}: $d = \gcd(a,b)$. Say $d = ar+bs$, for some $r,s\in\mb Z$. WTS: $d\mid a$ and $d\mid b$. By the division algorithm, $a = dq + \tilde{r}$, $0\leq \tilde{r}<d$. Solve for $\tilde{r} = a-dq = a-(ar+bs)q = a - arq - bsq = a(1-rq)+b(-sq) \geq 0$. Assum $\tilde r >0$. Then $\tilde r \in S$, but $\tilde r<d$, contradiction $\implies \tilde r = 0 \implies d\mid a$. For $d\mid b \ra$ similar to $d\mid a$.
		
		WTS: any common divisor $d'$ of $a$ and $b$ divides $d$. So $a = d' u$ and $b = d' v$ for some $u,v\in\mb Z$. Then $d = ar+bs = (d'u)r + (d'v)s = d'(ur + vs)$, where $ur+rs\in\mb Z$. So $d'\mid d$.
	\end{enumerate}
	Done.
\end{proof}

\subsection{Euclidean algorithm}
Given: $a$ and $b$, $a>b$.
Find: $d = \gcd(a,b)$ and $d = ar+bs$.

\begin{align*}
	a &= bq_1 + r_1 \\
	b &= r_1q_2 + r_2 \\
	r_1 &= r_2q_3 + r_3 \\
	&\ \,\vdots \\
	r_{n-2} &= r_{n-1}q_n + r_n \\
	r_{n-1} &= r_n q_n
\end{align*}
\ul{Claim}: $r_n = \gcd(a,b)$.
\begin{enumerate}
	\item WTS: $r_n\mid a$ and $r_n\mid b$. Last equation tells $r_n\mid r_{n-1} \implies r_n\mid r_{n-2} \implies \dots \implies r_n\mid b \implies r_n\mid a$.
	\item Assume $d'\mid a$ and $d'\mid b$. First equation tells $d'\mid r_1 \implies d'\mid r_2 \implies d'\mid r_3 \implies \dots \implies d'\mid r_n$.
\end{enumerate}
It stops: (assume $a,b>0$), so $b>r_1 > r_2 > \dots > r_n$.

\begin{example}
	1001 and 357.
	\begin{align*}
		1001 &= 357\cdot 2 + 287\\
		357 &= 287\cdot 1 + 70\\
		287 &= 70\cdot 4 + 7\\
		70 &= 7\cdot 10 
	\end{align*}
	So $7 = \gcd(1001,357)$. Then $7 = 287 - 70\cdot 4 = 287 - (357 - 287)\cdot 4 = 287 \cdot 5 - 357 \cdot 4 = (1001-357\cdot 2)\cdot 5 - 357\cdot 4 = 1001 \cdot 5 + 357 \cdot (-14)$.
\end{example}
\begin{corollary}
	If $a$ and $b$ are relatively prime, then there exist integers $r$ and $s$ such that $ar+bs = 1$.
\end{corollary}
If $d = \gcd(a,b)\implies d = ar+bs$.

An integer $p>1$ is \ul{prime} if the only divisors of $p$ are 1 and $p$. Not prime $\lra$ composite.

\begin{lemma}
	[Euclid] Let $a,b\in\mb Z$ and $p$ a prime number. If $p\mid ab$ then $p\mid a$ or $p\mid b$.
\end{lemma}
\begin{proof}
	\ul{Case 1}: $p\mid a$, done.
	\ul{Case 2}: $p\nmid a$. WTS $p\mid b$. If $p\nmid a$ then $\gcd(a,p) = 1 \implies \exists r,s\in\mb Z$ such that $ar+ps = 1$. Then $b = b\cdot 1 = b (ar+ps) = abr + pbs$. Since $p\mid ab$ and $p\mid pbs$, then $p\mid b$.
\end{proof}
\begin{theorem}
	[Euclid] There are infinitely many primes.
\end{theorem}
\begin{proof}
	Assume there are finitely many primes: $p_1,p_2,\dots,p_n$. Let $p = p_1p_2\dots p_n + 1$. So $p$ is a product of primes. However, $p_i\nmid p,\ 1\leq i\leq n \implies p$ is a prime number, a new prime (contradiction).
\end{proof}
\begin{theorem}
	[Fundamental Theorem of arithmetic] Let $n\geq 2$ be an integer. Then there exist primes $p_1,\dots p_s$ (not necessarily distinct) such that $n = p_1p_2\dots p_s$.
	Moreover, this factorization is unique.
\end{theorem}
\begin{proof}
	Assume $n = p_1 p_2\dots p_s = q_1 q_2\dots q_r$, primes. Notice that $p_1\mid n = q_1 q_2\dots q_r$. Recall Euclid's lemma: $p_1 \mid$ one of $q_i$'s $\implies p_1 = q_1$.
\end{proof}

\subsection*{Modular arithmetic}
Fix $n\in\mb N$. For $a,b\in\mb Z$, $a \equiv b\pmod{n}$ if $a-b$ is divisible by $n$.
Define a relation on $\mb Z$ by $a\sim b$ if $a\equiv b\pmod{n}$.
\ul{Claim}: This is an equivalence relation on $\mb Z$.
\begin{enumerate}
	\item Reflexive: $a\equiv a \pmod{n}$ since $n\mid 0 = a-a$ for all $a\in\mb Z$.
	\item Symmetric: $a\equiv b\pmod{n}\implies b\equiv a\pmod{n}$, since $n\mid(a-b) \lra a-b=nk \lra b-a = n(-k)$.
	\item Transitive: $a\equiv b\pmod{n}$ and $b\equiv c\pmod{n} \implies a\equiv c\pmod{n}$, since $a-b=nk$ and $b-c=nl$ and $a-c = (a-b)+(b-c) = nk+nl = n(k+l)$.
	Let $a = nq_1+r_1$ and $b=nq_2+r_2$, then $a-b = n(q_1-q_2) + (r_1-r_2)$ with $r_1-r_2 = 0$.
\end{enumerate}

\begin{example}
	\ul{$n=3$} Equivalence class:

	$[0] = \set{ \dots,-6,-3,0,3,6,9,12,\dots } \lra $ remainder 0.

	$[1] = \set{ \dots,-5,-2,1,4,7,10,13,\dots } \lra $ remainder 1.

	$[2] = \set{ \dots, -4,-1,2,5,8,11,14,\dots } \lra $ remainder 2.
\end{example}
In general, $\{[0],[1],[2],\dots,[n-1]\} = \mb Z_n$.
Define two operations:
\begin{enumerate}
	\item Addition: $[a]+[b] = [a+b]$.
	\item Multiplication: $[a]\cdot[b] = [ab]$.
	
\end{enumerate}
\begin{example}
	$\mb Z_6 = \{[0],[1],[2],[3],[4],[5]\}$. Take $[3]+[4] = [7]=[1]$, or $[0]+[3] = [0+3] = [3]$. Take $[2]\cdot[4] = [2\cdot 4] = [8] = [2]$, or $[2]\cdot[3] = [2\cdot 3] = [6] = [0]$. Now take $[1]+[2] = [3]$ and $[7]+[14]=[21]$, they are equal.
\end{example}

\newpage

\begin{lemma}
	Let $a\equiv a'\pmod n$ and $b\equiv b'\pmod n$. Then
	\begin{enumerate}
		\item $a+b \equiv a'+b'\pmod n$,
		\item $ab \equiv a'b'\pmod n$.
	\end{enumerate}
\end{lemma}
\begin{proof}
	$a\equiv a'\pmod n \lra n\mid (a-a')$ and $b\equiv b'\pmod n \lra n\mid(b-b')$.
	\begin{enumerate}
		\item $(a+b) - (a'+b') = (a-a') + (b-b')$
		\item $ab-a'b' = ab-a'b+a'b-a'b' = (a-a')b + a'(b-b')$
	\end{enumerate}
	Thus property 1 and 2 are true.
\end{proof}
\begin{proposition}
	Let $n\in\mb Z$.
	\begin{enumerate}
		\item $[a]+[b] = [b] + [a]$ and $[a][b] = [b][a]$.
		\item $([a]+[b])+[c] = [a] + ([b]+[c])$ and $([a][b])[c] = [a]([b][c])$.
		\item $[a]+[0] = [a]$ and $[a]\cdot [1] =[a]$.
		\item $[a]([b]+[c]) = [a][b] + [a][c]$.
		\item $[a]+[-a] = [0]$.
		\item Let $a\neq 0$. Then $[a]$ has a multiplicative inverse in $\mb Z_n \Llr \gcd(a,n) = 1$.
		\begin{proof}
			\ul{$\La$}: Assume $\gcd(a,n) = 1$. Then $\exists r,s\in\mb Z$ such that $ar+ns = 1$ implies $ar+ns \equiv 1\pmod n$ or $ar\equiv 1\pmod n$. Thus $[a][r] = [ar] = [1]$ and $[a]\inv = [r]$.

			\ul{$\Ra$}: Assume $[a]$ has a multiplicative inverse in $\mb Z_n$: $\exists r\in\mb Z$ such that $[a][r] = [1]$ or $[ar] = [1]$, implying $ar\equiv 1\pmod n$. Thus $ar-1 = ns$ for some $s\in\mb Z$. Rewrite as $ar+n(-s) = 1 \implies \gcd(a,n) = 1$.
		\end{proof}
	\end{enumerate}
\end{proposition}

\subsection{Symmetries}

\begin{example}
	[Triangle] Let $\Delta ABC$ be a triangle.
	\begin{itemize}
		\item $id$ is identity symmetry, leave things as they are.
		\item $\rho_1$ is rotation by one vertex.
		\item $\rho_2$ is $\rho_1$ applied twice.
		\item $\mu_1$ is a reflection about $A$'s axis.
		\item $\mu_2$ is a reflection about $B$'s axis.
		\item $\mu_3$ is a reflection about $C$'s axis.
	\end{itemize}
	If you apply a sequence of symmetries, the result must also be one of these.
	Symmetry: function $\{A,B,C\}\ra\{A,B,C\}$.
	$\mu_1(A) = A$, $\mu_2(B) = B$, $\mu_3(C) = C$.
	Compose symmetries $\llr$ composition of functions $\rho_1\circ \mu _1$.

	Multiplication table (Cayley table):
	$$\begin{array}{c|cccccc}
		\circ & id & \rho_1 & \rho_2 & \mu_1 & \mu_2 & \mu_3 \\ 
		\hline
		id & id & \rho_1 & \rho_2 & \mu_1 & \mu_2 & \mu_3 \\ 
		\rho_1 & \rho_1 & \rho_2 & id & \mu_3 & \mu_1 & \mu_2 \\ 
		\rho_2 & \rho_2 & id & \rho_1 & \mu_2 & \mu_3 & \mu_1 \\ 
		\mu_1 & \mu_1 & \mu_2 & \mu_3 & id & \rho_1 & \rho_2 \\ 
		\mu_2 & \mu_2 & \mu_3 & \mu_1 & \rho_2 & id & \rho_1 \\ 
		\mu_3 & \mu_3 & \mu_1 & \mu_2 & \rho_1 & \rho_2 & id
	\end{array}$$
	All of the elements can be generated by two elements, one of each $\rho_1,\mu_1$.
	\begin{align*}
		id &= \rho_1\circ \rho_1 \circ \rho_1 = \rho_1^3 \\
		   &= \mu_1\circ\mu_1 = \mu_1^2 \\
		\rho_2 &= \rho_1\circ\rho_1 = \rho_1^2 \\
		\mu_2 &= \mu_1\circ\rho_1 = \mu_1\rho_1 \\
		\mu_3 &= \mu_1\rho_1^2
	\end{align*}
	The table can be rewritten as:
	$$\begin{array}{c|cccccc}
		\circ & id & \rho_1 & \rho_1^2 & \mu_1 & \mu_1\rho_1 & \mu_1\rho_1^2 \\
     	\hline
     	id & id & \rho_1 & \rho_2 & \mu_1 & \mu_2 & \mu_3 \\
     	\rho_1 & \rho_1 & \rho_2 & id & \mu_3 & \mu_1 & \mu_2 \\
	 	\rho_1^2 & \rho_2 & id & \rho_1 & \mu_2 & \mu_3 & \mu_1 \\
     	\mu_1 & \mu_1 & \mu_2 & \mu_3 & id & \rho_1 & \rho_2 \\
     	\mu_1\rho_1 & \mu_2 & \mu_3 & \mu_1 & \rho_2 & id & \rho_1 \\
     	\mu_1\rho_1^2 & \mu_3 & \mu_1 & \mu_2 & \rho_1 & \rho_2 & id
 	\end{array}$$
	Generators: $\rho_1,\mu_1$.
	Relations: $\rho_1^3 id$, $\mu_1^2 = id$, $\rho_1\mu_1 = \mu_1\rho_1^2$.

	Define the gorup by generators and relations: $D_6 =\gen{\rho_1,\mu_1 \mid \rho_1^2 = id,\ \mu_1^2 = id,\ \rho_1\mu_1 = \mu_1\rho_1^2}$.

	So $\mu_1\rho_1\mu_1\rho_1^2 = \mu_1\mu_1\rho_1^2\rho_1^2 = \mu_1^2\rho_1^4 = \rho_1$.
\end{example}

\subsection{Binary operations}

\begin{definition}
	A binary operation $\circ$ on a set $S$ is a mapping $\circ:S\times S\ra S$.
	\begin{enumerate}
		\item $(a,b)$ and $(b,a)$ are different ordered pairs (if $a\neq b$), so $a\circ b$ and $b\circ a$ could be different. $$\circ(a,b) = a\circ b.$$
		\item $a\circ b$ exists for every $a,b\in S$.
		\item $a\circ b$ is well-defined.
		\item $a\circ b\in S$ for every $a,b\in S$, so $S$ is \ul{closed} under the operation.
	\end{enumerate}
\end{definition}
\begin{example}
	$S = \mb R$, $a\circ b = a/b$. Not a binary operation, since $(a,0)\ra a\circ 0$ does not exist.
\end{example}
\begin{example}
	$S = \mb R$, $a\circ b = $ number whose square is $|ab|$. Take $(2,8) \ra 2\circ 8 = 4,-4$, so not a binary op.
\end{example}
\begin{example}
	$S = \mb N$, $a\circ b = a-b$. Not a binary operation since $(1,2)\ra 1\circ 2=1-2 = -1\notin S$.
\end{example}
\begin{example}
	$S = \mb N$, $a\circ b = a+b$, $\checkmark$. It is a binary operation since it is closed.
\end{example}
\begin{example}
	$X$ any set, $S = \mc P(x) = \setm{A}{A\subseteq X}$. Consider $X = \set{\Box,\Delta}$, then $\mc P(x) = \set{\emptyset,\set{\Box},\set{\Delta},X}$.
\end{example}
\begin{example}
	$A\circ B = A\cup B$, $\checkmark$. Since $A,B\subseteq X \implies A\cup B \subseteq X$.

	$A*B = A\cap B$, $\checkmark$. Since $A,B\subseteq X \implies A\cap B\subseteq X$.
\end{example}

\begin{definition}
	A binary operation $\circ$ on a set $S$ is
	\begin{enumerate}
		\item \ul{commutative} if $a\circ b = b\circ a$ for all $a,b\in S$.
		\item \ul{associative} if $(a\circ b)\circ c = a\circ(b\circ c)$ for all $a,b,c\in S$.
	\end{enumerate}
\end{definition}
\begin{example}
	$S = \mb N$, $a\circ b = \min\{a,b\}$. Since $a\circ b = \min\{a,b\}$ and $b\circ a = \min\{b,a\}$, commutative $\checkmark$.
	Since $(a\circ b)\circ c = \min\{a,b\}\circ c = \min\{\min\{a,b\},c\}$ and $a\circ(b\circ c) = a\circ\min\{b,c\} = \min\{a,\min\{b,c\}\}$ are both equal to $\min\{a,b,c\}$, associative $\checkmark$.
\end{example}
\begin{example}
	$S = \mb N$, $a\circ b = a$. Since $1\circ 2 = 1$ but $2\circ 1 = 2$, not commutative.
	$(a\circ b)\circ c = a\circ c = a$ and $a\circ(b\circ c) = a\circ b = a$, associative $\checkmark$.
\end{example}
\begin{example}
	$S = \mb Z$, $a\circ b = a-b$. Since $1\circ 2 = 1-2 = -1$ but $2\circ 1 = 2 = 2-1 = 1$, not commutative.
	Since $(a\circ b)\circ c = (a-b)\circ c = (a-b)-c = a-b-c$ and $a\circ(b\circ c) = a\circ(b-c) = a-(b-c) = a-b+c$, it is not associative because $(0\circ 0)\circ 1 = -1$ and $0\circ(0\circ 1) = 1$.
\end{example}
\begin{example}
	$S = \mb Z$, $a\circ b = 3(a+b)$. Then $a\circ b = 3(a+b)$ and $b\circ a = 3(b+a)$, commutative $\checkmark$.
	Also, $(a\circ b)\circ c = [3(a+b)]\circ c = 3(3(a+b)+c) = 9a+9b + 3c$ and $a\circ(b\circ c) = a\circ[3(b+c)] = 3(a+3(b+c)) = 3a+9b+9c$, not associative.
\end{example}
\begin{example}
	$S = M_n(\mb R)$ $n\times n$ matrices. $A\circ B = AB$. Then $AB\neq BA$, not commutative in general. However, $(AB)C = A(BC)$, associative $\checkmark$.
\end{example}

\begin{example}
	[HW Review] $ar+bs = 1 \implies \gcd(a,b) = 1$ since $d\mid a$ and $d\mid b$ and $d\mid 1 \implies \gcd(a,b) = 1$. However, $3\cdot 1 + 2\cdot(-1) = 1 \implies 3\cdot d + 2\cdot(-d) = d$.
\end{example}

\subsection{Groups: definition and examples}

\begin{definition}
	A nonempty set $G$ with a binary operation $\circ$ is a \ul{group} if
	\begin{enumerate}
		\item $\circ$ is associative
		\item there exists an element $e\in G$ such that $a\circ e = e\circ a = a$ for all $a\in G$ (identity element)
		\item for every $a\in G$ there exists $b\in G$ such that $a\circ b = b\circ a = e$ (inverse of $a$)
	\end{enumerate}
	\ul{Notation}: $(G,\circ)$ or $G$.
\end{definition}
\begin{definition}
	A group $(G,\circ)$ is \ul{abelian} if $\circ$ is commutative.
\end{definition}
\begin{remark}
	An operation can be commutative, a group can be abelian.
\end{remark}
\begin{example}
	$(\mb Z,+)$: associative $\checkmark$. $e=0 \checkmark$. inverse of $n$ is $-n$, $\checkmark$. commutative $\checkmark$. \ul{abelian group}.
	$(\mb Q, +)$, abelian group. So is $(\mb R,+)$, $(\mb C,+)$. For $(\mb R,\cdot)$ it is associative $\checkmark$, $e=1$, inverse of $x$ is $\frac{1}{x}$, no inverse for 0, \ul{not a group}. However, $(\mb R\backslash \set0,\cdot)$ is an abelian group. $\mb R^\times$ is the multiplicative group of a field.
\end{example}
\begin{example}
	$(\mb Z_n,+)$: $[a]+[b] = [a+b]$ associative $\checkmark$. $e=[0]$. inverse of $[a]$ is $[-a]$. \ul{abelian group}.
\end{example}
\begin{example}
	$G = \{e\}$ is the trivial group, $e\circ e = e$, $e\inv = e$.
\end{example}
\begin{example}
	Symmetries of a regular $n$-gon. operation: composition. \ul{Claim}: non-abelian group. Notation can be $D_n$ or $D_{2n}$, they are called dihedral group.
\end{example}
\begin{example}
	$(M_n(\mb R),+)$, associative $\checkmark$, $e=0$ zero matrix, inverse of $A$ is $-A$, abelian group.
\end{example}
\begin{example}
	$(M_n(\mb R),\cdot)$: associative $\checkmark$, $e= I_n$, inverse of $A$ is $A\inv$ if $A$ is nonsingular. \ul{not a group}.
\end{example}
\begin{example}
	$GL_n(\mb R) = \setm{A\in M_n(\mb R)}{\det A \neq 0}$ nonsingular matrices. operation: multiplication. nonsingular $\cdot$ nonsingular $=$ nonsingular. associative $\checkmark$, $e = I_n$, inverse of $A$ is $A\inv$. \ul{nonabelian group} called \ul{general linear group}.
\end{example}
\begin{example}
	$(\mb Q^+,*)$, where $a*b = \frac{ab}{2}$.
	\begin{itemize}
		\item associative: $(a*b)*c = \frac{ab}{2} * c = \frac{ab/2\cdot c}{2} = \frac{abc}{4}$ and $a*(b*c) = a*\frac{bc}{2} = \frac{a\cdot bc/2}{2} = \frac{abc}{4}$.
		\item identity: $a*e = e*a = a$ or $\frac{ae}{2} = \frac{ea}{2} = a \implies e = 2$.
		\item inverses: $a*b = b*a = e$ or $\frac{ab}{2} = \frac{ba}{2} = 2 \implies b = \frac{4}{a}$ is inverse of $a$.
	\end{itemize}
	This is a \ul{group}.
\end{example}

\begin{definition}
	The \ul{order} of a group $(G,\circ)$ is the size of the set $G$: $|G|$. There are finite groups with $|G|<\infty$ and infinite groups with $|G|=\infty$.
\end{definition}

\subsection{Basic properties of groups}

\begin{proposition}
	[Uniqueness of identity]
	Each group has only one identity element.
\end{proposition}
\begin{proof}
	Let $(G,\circ)$ be a group and suppose $e_1,e_2\in G$ both satisfy the identity axiom.
	WTS: $e_1 = e_2$.
	Consider $$e_1 = e_1\circ e_2 = e_2.$$
\end{proof}
\begin{proposition}
	[Uniqueness of inverses]
	Every element of a group has only one inverse.
\end{proposition}
\begin{proof}
	Let $(G,\circ)$ be a group, $x\in G$ and $y_1,y_2\in G$ are inverses of $x$.
	WTS: $y_1 = y_2$.
	$$y_1= y_1\circ e =y_1\circ (x\circ y_2) = (y_1\circ x)\circ y_2 = e\circ y_2 = y_2.$$
	\ul{Notation}: $x\inv$ is \ul{the} inverse of $x$.
\end{proof}
\begin{proposition}
	Let $(G,\circ)$ be a group and $x\in G$. Then $(x\inv)\inv = x$.
\end{proposition}
\begin{proof}
	We have $x\circ x\inv = x\inv \circ x = e$. So $x\circ a = a\circ x = e \implies x = a\inv = (x\inv)\inv$.
\end{proof}
\begin{proposition}
	Let $(G,\circ)$ be a group and $x,y\in G$. Then $(x\circ y)\inv = y\inv \circ x\inv$.
\end{proposition}
\begin{remark}
	If you put your socks on and then your shows, you do not take your socks off first but you have to reverse the order in which you undo.
\end{remark}
\begin{proof}
	$(y\inv\circ x\inv)\circ(x\circ y) = y\inv\circ(x\inv\circ x)\circ y = y\inv\circ e\circ y = y\inv\circ y = e$.
	
	$(x\circ y)\circ(y\inv\circ x\inv) = x\circ(y\circ y\inv)\circ x\inv = x\circ e\circ x\inv = x\circ x\inv = e$.

	So $y\inv\circ x\inv$ is the inverse of $x\circ y$.
\end{proof}
\begin{proposition}
	[Cancellation laws]
	Let $(G,\circ)$ be a group and $x,y,z\in G$. Then
	\begin{enumerate}
		\item $x\circ z = y\circ z \implies y = x$ (right cancellation)
		\item $z\circ x = z\circ y \implies x = y$ (left cancellation)
	\end{enumerate}
\end{proposition}
\begin{proof}
	(1): $x\circ z = y\circ z$. So $(x\circ z)\circ z\inv = (y\circ z)\circ z\inv$ and $x\circ(z\circ z\inv) = y\circ(z\circ z\inv)$ implies $x\circ e = y\circ e$. Thus $x = y$.
\end{proof}

\subsection{Powers of elements in a group}

$$x\circ y \sim xy$$

$G$ is a group, $x\in G$.
Define the \ul{powers} of $x$ as follows:
$x^0 = e$, for $n\in\mb N$: $x^n=\us{n}{xx\cdots x}$ and $x^{-n} = (x\inv)^n = \us{n}{x\inv x\inv\cdots x\inv}$.

\begin{theorem}
	Let $G$ be a group, $x,y\in G$, and $m,n\in\mb Z$.
	\begin{enumerate}
		\item $x^mx^n = x^{m+n}$
		\item $(x^n)\inv = (x\inv)^n$
		\item $(x^m)^n = x^{mn}$
		\item if $G$ is abelian, then $(xy)^n = x^ny^n$
	\end{enumerate}
\end{theorem}
\newpage
\begin{proof}
	Cases:
	\begin{enumerate}
		\item \ul{Case 1}: $m\geq 0$ and $n\geq 0$. $x^mx^n = \us{m}{xx\cdots x} \us{n}{xx\cdots x} = \us{m+n}{xx\cdots x} = x^{m+n}$.
				
			\ul{Case 2}: $m<0$ and $n<0$. Write $m = -m_0$ and $n=-n_0$ for $m_0,n_0\in\mb N$. Then $x^mx^n = x^{-m_0}x^{-n_0} = (x\inv)^{m_0} (x\inv)^{n_0} \os{\text{Case 1}}{=} (x\inv)^{m_0+n_0} = x^{-(m_0+n_0)} = x^{m+n}$.
				
			\ul{Case 3}: $m\geq 0$ and $n<0$. Write $n=-n_0$ for $n_0\in\mb N$.
			$x^mx^n = x^mx^{-n_0} = \us{m}{x\cdots x}\us{n_0}{x\inv\cdots x\inv} = \otimes$.
			\ul{Subcase A}: $m\geq n_0$. $\otimes = \us{m-n_0}{xx\cdots x} = x^{m-n_0} = x^{m+n}$.
			\ul{Subcase B}: $m<n_0$. $\otimes = \us{n_0-m}{x\inv x\inv \cdots x\inv} = (x\inv)^{n_0-m} = x^{-(n_0-m)} = x^{m+n}$.

			\ul{Case 4}: $m<0$ and $n\geq 0$. Similar to Case 3.
		\item \ul{Case 1}: $n\geq 0$. $(x^n)\inv = (\us{n}{xx\cdots x})\inv = \us{n}{x\inv x\inv \cdots x\inv} = (x\inv)^n$.

			\ul{Case 2}: $n<0$. Write $n=-n_0$ for $n_0\in\mb N$. 
			$$(x^n)\inv = (x^{-n_0})\inv = (\us{n_0}{x\inv x\inv \cdots x\inv})\inv = \us{n_0}{(x\inv)\inv (x\inv)\inv\cdots(x\inv)\inv} = (x\inv)^{-n_0} = (x\inv)^n.$$
		\item \ul{Case 1}: $m\geq 0$ and $n\geq 0$. $(x^m)^n = \us{n}{\us{m}{xx\cdots x}\us{m}{xx\cdots x}\cdots\us{m}{xx\cdots x}} = \us{mn}{xx\cdots x} = x^{mn}$.
				
			\ul{Case 2}: $m<0$ and $n<0$. Write $m=-m_0$ and $n = -n_0$ for $m_0,n_0\in\mb N$. $(x^m)^n = (x^{-m_0})^{-n_0} = [(x\inv)^{m_0}]^{-n_0} = \{[(x\inv)^{m_0}]\inv\}^{n_0} = \{[(x\inv)\inv]^{m_0}\}^{n_0} = (x^{m_0})^{n_0} \os{\text{Case 1}}{=} x^{m_0n_0} = x^{mn}$.

			\ul{Case 3}: $m<0$ and $n\geq 0$. Write $m=-m_0$ for $m_0\in\mb N$. $(x^m)^n = (x^{-m_0})^n = [(x\inv)^{m_0}]^n \os{\text{Case 1}}{=} (x\inv)^{m_0n} = x^{-m_0n} = x^{mn}$.

			\ul{Case 4}: $m\geq 0$ and $n<0$. Write $n = -n_0$ for $n_0\in\mb N$. $(x^m)^n = (x^m)^{-n_0} = [(x^m)\inv]^{n_0} = [(x\inv)^m]^{n_0} = (x\inv)^{mn_0} = x^{-mn_0} = x^{mn}$.
		\item \ul{Case 1}: $n=0$. $(xy)^n = (xy)^0 = e$ and $x^ny^n = x^0 y^0 = ee = e$.

			\ul{case 2}: $n\geq 1$. Induction on $n$: \ul{Base}: $n=1$. $(xy)^1 = x^1 y^1$ and $xy = xy$. \ul{Induction step}: Assume $(xy)^n = x^n y^n$. WTS: $(xy)^{n+1} = x^{n+1} y^{n+1}$. So $(xy)^{n+1} \os{(1)}{=} (xy)^n(xy)^1 \os{\text{I.H.}}{=} x^n y^n xy \os{\text{abelian}}{=} x^n x y^n y \os{(1)}{=} x^{n+1}y^{n+1}$.

				\ul{Case 3}: $n<0$. Write $n=-n_0$ for $n_0\in\mb N$. $(xy)^n = (xy)^{-n_0} = [(xy)\inv]^{n_0} = (y\inv x\inv)^{n_0} \os{\text{Case 2}}{=} (y\inv)^{n_0}(x\inv)^{n_0} = y^{-n_0} x^{-n_0} = y^nx^n \os{\text{abelian}}{=} x^ny^n$.
			\begin{example}
				$(xy)^2 = x^2 y^2$ and $xyxy = xxyy$ and $yx = xy$.
			\end{example}
	\end{enumerate}
	Done.
\end{proof}

\subsection{Subgroups}

\begin{example}
	$(\mb Z,+),(\mb Q,+)$ are groups and $\mb Z\subseteq\mb Q$.
\end{example}
\begin{definition}
	A subset $H$ of a group $(G,\circ)$ is a \ul{subgroup} if $H$ is a group under $\circ$.
\end{definition}
\begin{example}
	$(\mb R\backslash\set0,\cdot)$ not a subgroup of $(\mb R,+)$ but $\mb R\backslash\set0\subseteq\mb R$.
\end{example}
\begin{proposition}
	A subset $H$ of a group $G$ is a subgroup of $G \Llr$
	\begin{enumerate}
		\item the identity $e$ of $G$ is in $H$
		\item $x,y\in H \implies xy\in H$ (closed under product)
		\item $x\in H \implies x\inv\in H$ (closed under inverses)
	\end{enumerate}
\end{proposition}
\begin{proof}
	\ul{$\implies$} Suppose $H$ is a subgroup.
	WTS: (1)-(3) hold.
	Let $e_H$ be the identity element of the group $H$. Then $e_He_H = e_H$ in $H \ra$ in $G$ and $e_H e_H = e_H e \implies H\ni e_H = e$ in $G$. So (1) holds.
	$H$ must be closed under the operation as a group, so (2) holds.
	Each $x\in H$ has an inverse $x'\in H$. Then $xx' = x'x = e_H$ and $xx' = x'x = e$. By the uniqueness of inverses, $x\inv = x'\in H$. So (3) holds.

	\ul{$\Lra$} Suppose (1)-(3) hold. WTS: $H$ is a subgroup of $G$.
	(2) says $H$ is closed under the operation, so we have a binary operation on $H$.
	Also $(ab)c = a(bc)$ for all $a,b,c\in G$ implies $(ab)c = a(bc)$ for all $a,b,c\in H$. So the operation on $H$ is associative.
	By (1), $H$ contains an identity element. By (3), each element of $H$ has an inverse in $H$.
	So $H$ is a group $\implies$ subgroup.
\end{proof}
\begin{example}
	$(\mb Z,+)\leq (\mb Q,+)\leq(\mb R,+)\leq(\mb C,+)$.
\end{example}
\begin{example}
	$G$ any gruop then trivial subgroup is $\{e\}\leq G$ and also $G\leq G$.
\end{example}
\begin{example}
	$G = GL_n(\mb R)$ is general linear group and $H = SL_n(\mb R) = \{A\in GL_n(\mb R) \mid \det A = 1\}$ is special linear group.
	$e = I_n\in GL_n(\mb R)$ and $\det I_n = 1 \implies I_n\in SL_n(\mb R)$.
	Let $A,B\in SL_n(\mb R) \os{?}{\implies} AB\in SL_n(\mb R)$. Since $\det(AB) = \det A \cdot \det B = 1\cdot 1 = 1 \implies AB\in SL_n(\mb R)$.
	$A\in SL_n(\mb R) \os{?}{\implies} A\inv\in SL_n(\mb R)$ and $\det(A\inv) = \frac{1}{\det A} = \frac{1}{1} = 1\implies A\inv\in SL_n(\mb R)$. Recall $AA\inv = I \implies \det(AA\inv) = \det I \implies \det A\cdot \det A\inv = 1$.
\end{example}
\begin{example}
	$G$ is any group and $S\subseteq G$ any subset.
	Let $\displaystyle \gen S = \bigcap_{\us{S\subseteq H}{H\leq G}} H$ subgroup of $G$ \ul{generated by $S$}. For example, $S = \set a$, then subgroup is $\set{a^0=e,a,a\inv,a^2,a^3,\dots}$.
\end{example}

\section{Cyclic Groups}

\begin{theorem}
	[Cyclic groups]
	Let $G$ be a group and $a\in G$. The set $\gen a = \setm{a^k}{k\in \mb Z}$ is the smallest subgroup of $G$ containing $a$.
\end{theorem}
\begin{proof}
	(1) Subgroup.
	\begin{itemize}
		\item $e = a^0 \in\gen a$
		\item closure under products: let $x,y\in\gen a$, then $x = a^n$ and $y=a^m$ for some $n,m\in\mb Z$, so $xy = a^na^m = a^{n+m}\in\gen a$
		\item closure under inverses: let $x\in\ <a>$, then $x=a^n$ for some $n\in\mb Z$, so $x\inv = (a^n)\inv = a^{-n}\in\gen a$
	\end{itemize}
	Therefore $\gen a\leq G$.

	(2) Smallest.
	Set $\{H\mid H\leq G \text{ and } a\in H\} = S$, then $<a>\ \in S$ since $a = a^1 \in\gen a$. \ul{Claim}: $\gen a \subseteq H$ for all $H\in S$.
	$a\in H \implies a^2 = aa\in H \implies a^3 = a^2a\in H \implies \dots$ and $a\in H\implies a\inv\in~H \implies a^{-2} = a\inv a\inv \in H \implies a^{-3} = a^{-2}a\inv \in H \implies \dots$ and $a^0 = e\in H$.
\end{proof}
\begin{note}
	$(G,+) \la\gen a = \setm{ka}{k\in\mb Z}$.
\end{note}
\begin{definition}
	Let $G$ be a group and $a\in G$. The subgroup $\gen a$ is called the \ul{cyclic subgroup} of $G$ \ul{generated by $a$}.
\end{definition}
\begin{definition}
	A group $G$ is a \ul{cyclic group} if $\exists a\in G$ such that $\gen a \in G$.
\end{definition}
\begin{example}
	$(\mb Z,+)$ infinite cyclic group, $\mb Z =\gen 1 =\gen{-1} = \setm{k}{k\in\mb Z} = \setm{-k}{k\in\mb Z}$. $1,-1$ are generators.
\end{example}
\begin{example}
	$G =\gen e = \set e$
\end{example}
\begin{remark}
	$G =\gen a = \gen{a\inv}$
\end{remark}
\begin{example}
	$\mb Z_n =\ \gen{[1]} =\gen{[n-1]}$ finite cyclic group, the number of generators of $\mb Z_n$ is $\phi(n)$.
\end{example}
\newpage
\begin{proposition}
	Every cyclic group is abelian.
\end{proposition}
\begin{note}
	cyclic $\subset$ abelian $\subset$ groups
\end{note}
\begin{proof}
	Let $G =\gen a$ and $x,y\in G$. Then $x = a^n$ and $y = a^m$. So $xy = a^na^m = a^{n+m} = a^{m+n} = a^ma^n = yx$. So $G$ is abelian.
\end{proof}
\begin{remark}
	cyclic $\implies$ abelian but abelian $\not\implies$ cyclic, like $(\mb Q,+),(\mb R,+), (\mb C,+)$.
\end{remark}

\begin{theorem}
	Every subgroup of a cyclic group is cyclic.
\end{theorem}
\begin{proof}
	Let $G =\gen a$ and $H\leq G$.
	WTS: $H$ is cyclic.
	
	\ul{Case 1}: $H = \set e$. In this case $H = \gen e$.

	\ul{Case 2}: $H\neq \set e$.
	Then $S = \setm{k\in \mb Z}{k \neq 0 \text{ and } a^k\in H}\neq \emptyset$.
	If $a^k\in H$ for some $k\in\mb N$, then $P = \setm{k\in\mb N}{a^k\in H}\neq\emptyset$.
	If $a^k\in H$ for $k<0$, then $(a\inv)^k\in H\implies a^{-k}\in H$ and $-k\in\mb N$.
	In any case, $P = \setm{k\in\mb N}{a^k\in H}\neq \emptyset$.
	Let $n$ be the least element in $P$ by Well-Ordering Principle.
	So $h = a^n\in H$. \ul{Claim}: $H =\gen k$.
	Clearly, $\gen h \subseteq H$. Let $x\in H$. WTS: $x = h^m$ for some $m\in\mb Z$.
	Write $x = a^l$ and $l = nq + r$ where $0\leq r<n$. Then $x = a^l = a^{nq+r} = a^{nq} a^r = (a^n)^qq^r = h^qa^r$. So $a^r = (h^q)\inv x = h^{-q}x\in H \implies a^r\in H \implies r = 0$ because $r<n$ and $n$ is the least element in $P$.
	Then $x = h^q \in\gen h$. So $H\subseteq\gen h \implies H =\gen h$.
\end{proof}

Group is cyclic $\implies$ every (proper) subgroup is cyclic, but the converse is not true. For example, $D_3$ is non-abelian $\implies$ not cyclic. Subgroups: $\gen e,\gen\rho,\gen{\mu_1},\gen{\mu_2},\gen{\mu_3}$.

\begin{example}
	$\mb Z =\gen 1$. Then $H\leq \mb Z \implies H =\gen n = n\mb Z$. Subgroups: $n\mb Z$, where $n\geq 0$.
\end{example}

\subsection{Order of an element of a group}
\begin{definition}
	Let $a$ be an element of a group $G$. The \ul{order of $a$}, denoted $o(a)$ or $|a|$, is the order of $\gen a$, that is, $o(a) = |\gen a|$.
	$$o(a) = \begin{cases} n & \text{for some } n\in\mb N \text{ - finite order} \\ \infty & \text{- infinite order} \end{cases}. $$
\end{definition}
\begin{example}
	$G = \mb Z$. Then $o(1) = \infty$ and $\gen z\ = \mb Z$, $o(2) = \infty$ and $\gen 2 = 2\mb Z$, $o(3) = \infty$ and $\gen 3 = 3\mb Z$, $o(0) = 1$ and $\gen 0 = \set0$.
\end{example}
\begin{note}
	Any $G$ has $o(e) = 1$ and $e$ is the only element of $G$ of order 1.
\end{note}
\begin{example}
	$GL_2(\mb R)$, $\mat{-1&0 \\0&-1}^2 = I_2$, this is a counter example that shows an infinite group can have a non-trivial finite subgroup.
\end{example}
\begin{example}
	Infinite group where every element has finite order $\prod_{n=1}^\infty \mb Z_2$.
\end{example}
\begin{example}
	$G = \mb Z_6$. Then $o([0]) = 1$, $o([1]) = 6$ since $\gen{[1]} = \mb Z_6$, $o([2]) = 3$ since $\gen{[2]} = \set{[0],[2],[4]}$, $o([3]) = 2$ since $\gen{[3]} = \set{[0],[3]}$, $o([4]) = 3$ since $\gen{[4]} = \set{[0],[4],[2]} =\gen{[2]}$, $o([5]) = 6$ since $\gen{[5]} = \set{[0],[5],[4],[3],[2],[1]}$.
\end{example}

\section{Permutation groups}

\begin{definition}
	A \ul{permutation} of a set $X$ is a bijective mapping $\pi: X\ra X$.
\end{definition}
\begin{example}
	$X = \{A,B,C\}$. $\text{id}_X = \pmat{A&B&C\\A&B&C}$, then $\rho_1 = \pmat{A&B&C \\ B&C&A}$, then $\rho_2 = \pmat{A&B&C\\C&A&B}$, then $\mu_1 = \pmat{A&B&C\\A&C&B}$, then $\mu_2 = \pmat{A&B&C\\C&B&A}$, and $\mu_3 = \pmat{A&B&C\\B&A&C}$.
\end{example}
\ul{Notation}: $S_X$ is the set of all permutations of $X$.

\begin{theorem}
	The set $S_X$ is a group (\ul{symmetric group}) with respect to the operatoin of composition of permutation mappings.
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item We have a binary operation on $S_X$. Permutation $\circ$ permutation = permutation because bijective $\circ$ bijective = bijective.
		\item Operation is associative: Composition of mappings is associative.
		\item $e = \text{id}_X$: $\text{id}_X \circ \pi = \pi\circ \text{id}_X = \pi$.
		\item Let $\pi\in S_X \implies \exists$ inverse mapping $\pi\inv: X\ra X$ bijective $\implies \pi\inv\in S_X$. So $\pi\circ\pi\inv = \pi\inv\circ\pi = \text{id}_x = e$. So $\pi\inv$ is the group inverse.
	\end{enumerate}
	Done.
\end{proof}

If $|X|<\infty$, write $X = \{1,2,\dots,n\}$ and $S_X\ra S_n \ra$ symmetric group on $n$ letters, then $|S_n| = n!$.

\begin{definition}
	A \ul{permutation group} is a subgroup of a symmetric group.
\end{definition}
\begin{example}
	Look at $S_4$. $\sigma = \pmat{1&2&3&4\\4&1&2&3}$, $\tau = \pmat{1&2&3&4 \\ 2&1&4&3}$. Compute composition of mappings goes from right to left: $\sigma \tau  = \pmat{1&2&3&4\\1&4&3&2}$, $\tau\sigma = \pmat{1&2&3&4\\3&2&1&4}$. So $\sigma\tau \neq \tau\sigma$.
\end{example}

\begin{definition}
	A permutation $\sigma\in S_X$ is a \ul{cycle of length $k$} (or \ul{$k$-cycle}) if:
	\begin{enumerate}
		\item there exist distinct elements $a_1,a_2,\dots,a_k\in X$ such that 
			$$\sigma(a_1) = a_2, \sigma(a_2) = a_3,\dots,\sigma(a_k) = a_1$$
		\item $\sigma(x) = x$ for all $x\in X\backslash\set{a_1,a_2,\dots,a_k}$.
	\end{enumerate}
	\ul{Notation}: $\sigma = (a_1\,a_2\,\cdots\,a_k)$.
\end{definition}
\begin{example}
	Consider $S_6$.

	$\sigma = \pmat{1&2&3&4&5&6\\5&6&2&4&3&1} = (1\,5\,3\,2\,6)$ is a 5-cycle. 
	
	$\tau = \pmat{1&2&3&4&5&6\\1&5&3&2&4&6} = (2\,5\,4)$ is a 3-cycle.

	$\pi = \pmat{1&2&3&4&5&6\\2&1&4&3&5&6} = (1\,2)(3\,4)$ not a cycle.
\end{example}

\begin{definition}
	Two cycles $\sigma = (a_1\, a_2\,\cdots\, a_k)$ and $\tau = (b_1\,b_2\,\cdots\,b_m)$ are \ul{disjoint} if $$\set{a_1,a_2,\dots,a_k}\cap \set{b_1,b_2,\dots,b_m} = \emptyset.$$
\end{definition}

\begin{proposition}
	Disjoint cycles commute.
\end{proposition}
\begin{proof}
	Let $\sigma = (a_1\,a_2\,\dots\,a_k)\in S_X$ and $\tau = (b_1\,b_2\,\dots\,b_k)\in S_X$ be such that $A\cap B = \set{a_1,a_2,\dots,a_k}\cap \set{b_1,b_2,\dots,b_m} = \emptyset$.
	WTS: $\sigma\tau = \tau\sigma \ra$ need to show: $\sigma\tau(x) = \tau\sigma(x)$ for all $x\in X$.

	\ul{Case 1}: $x\notin A$ and $x\notin B$. Then $\sigma(x) = x$ and $\tau(x) = x$ so $\sigma\tau(x) = \sigma(\tau(x)) = \sigma(x) = x$. Conversely, $\tau\sigma(x) = \tau(\sigma(x)) = \tau(x) = x$.

	\ul{Case 2}: $x\in A$ and $x\notin B$. Then $x = a_i$ for some $1\leq i\leq k$, and $\sigma(x) = \sigma(a_i) = a_{i+1\pmod k}\in A$ and $\tau(x) = x$. So $\sigma\tau(x) = \sigma(\tau(x)) = \sigma(x) = a_{i+1\pmod k}$. Conversely, $\tau\sigma(x) = \tau(\sigma(x)) = \tau(a_{i+1\pmod k}) = a_{i+1\pmod k}\in A$ and not in $B$.

	\ul{Case 3}: $x\in A$ and $x\notin B$. Similar to Case 2.

	\ul{Case 4}: $x\in A$ and $x\in B$. Impossible.
\end{proof}

\newpage

\begin{theorem}
	Every permutation in $S_n$ can be expressed \ul{uniquely} as a product of disjoint cycles.
\end{theorem}
\begin{example}
	$\pmat{1&2&3&4&5&6&7&8\\3&5&7&4&2&8&1&6} = (1\,3\,7)(2\,5)(6\,8) = (6\,8)(1\,3\,7)(2\,5)$
\end{example}
\begin{definition}
	A \ul{transposition} is a cycle of length 2.
\end{definition}
\begin{proposition}
	Every permutation in $S_n$ is a product of transpositions.
\end{proposition}
\begin{proof}
	Let $\sigma\in S_n$, then $\sigma = \prod$ cycles $\os{\text{WTS}}{\lla} \prod$ transpositions.
	
	Consider $(a_1\,a_2\,\dots\,a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_3)(a_1\,a_2)$, not unique.
\end{proof}
\begin{example}
	$\pmat{1&2&3&4&5&6\\6&5&2&4&3&1} = (1\,6)(2\,5\,3) = (1\,6)(2\,3)(2\,5)$
\end{example}

$\sigma\in S_n$, $\sigma = \tau_1\,\tau_2\,\dots,\tau_k$ product of transpositions.
So $\sigma$ is $\begin{cases} \text{\ul{even}} & \text{if $k$ is even} \\ \text{\ul{odd}} & \text{if $k$ is odd} \end{cases}$ is false, instead parity remains the same in \ul{every} presentation of $G$ as a product of transpositions. Efficient proof is using the group action concept.

Let $A_n$ be the set of all \ul{even} permutations in $S_n$.
\begin{proposition}
	$A_n\leq S_n$ ($A_n$ is the alternating group)
\end{proposition}
Try proof, check properties.

\begin{proof}
	Cases:
	\begin{enumerate}
		\item $\text{id}\in A_n$ since $\text{id} = (12)(12)$
		\item even $\cdot$ even = even. Consider $\sigma = t_1\,t_2\,\cdots\,t_{2k}$ and $\tau = s_1\,s_2\,\cdots\,s_{2m}$.
			
			Then $\sigma\tau = t_1\,t_2\,\cdots\,t_{2k}\,s_1\,s_2\,\cdots\,s_{2m}$ has $2k+2m$, so even.
		\item even$\inv =$ even. Consider $\sigma = t_1\,t_2\,\cdots\,t_{2k}$.
			
			Then $\sigma\inv = (t_1\,t_2\,\cdots\,t_{2k})\inv = t_{2k}\inv\,t_{2k-1}\inv\cdots\, t_2\inv\,t_1\inv = t_{2k}\,t_{2k-1}\,\cdots\,t_2\,t_1$ has $2k$ even.
	\end{enumerate}
	Done.
\end{proof}

\begin{proposition}
	$|A_n| = n!/2$
\end{proposition}
\begin{proof}
	Let $B_n\subset S_n$ be all odd permutations. Then $S_n = A_n\cup B_n$ is a partition of $S_n$. Let $f: A_n\ra B_n$ be defined by $f(\sigma) = (1\,2)\sigma$.
	WTS: $f$ is bijective.
	\begin{enumerate}
		\item $f$ is injective. Assume $f(\sigma) = f(\tau)$. Then $(1\,2)\sigma = (1\,2)\tau$ implies $\sigma = \tau$.
		\item $f$ is surjective. Let $\sigma\in B_n$. Need $\tau\in A_n$ such that $f(\tau) = \sigma$. Then $(1\,2)\tau = \sigma$ implies $\tau = (1\,2)\inv\sigma$. Let $\tau = (1\,2)\sigma\in A_n$. Then $f(\tau) = (1\,2)\tau = (1\,2)(1\,2)\sigma = \sigma$.
	\end{enumerate}
	Since $f$ is a bijective map, $|A_n| = |B_n| = |S_n|/2 = n!/2$.
\end{proof}

\subsection{Dihedral groups}

$D_n =$ symmetries of a regular $n$-gon or $D_{2n}$.
\begin{theorem}
	$D_n$ is a subgroup of $S_n$ of order $2n$.
\end{theorem}
\begin{proof}
	Label the vertices of the $n$-gon by $1,2,\dots,n$. Elements of $D_n$ can be thought of as a permutations of the vertices.
	Let $\sigma\in D_n$. Then $a\mapsto k$ with $n$ choices and $a+1\mapsto k+1$ or $k-1$ with 2 choices, so there are only $2n$ geometric posibilities.
\end{proof}
\begin{theorem}
	The group $D_n$, $n\geq 3$, is generated by two elements $r$ and $s$ satisfying the relations: $$r^n = \text{id},\,s^2 = \text{id},\,srs = r\inv$$
	or $$ D_n =\gen{r,s\mid r^n = s^2 = \text{id},srs = r\inv}$$ presentation of $D_n$ with generators $r,s$ and their defining relations.
\end{theorem}
\begin{proof}
	We have $n$ rotations: angles $0,2\pi/n,(2)2\pi/n,\dots,(n-1)2\pi/n$. Then $2\pi/n = r$. All rotations are $\set{r^0,r^1,r^2,\dots,r^{n-1}}$ and $r^n = \text{id}$.
	Let $s$ be the reflection which fixes vertex 1.
	It is clear that $s^2 = \text{id}$.
	%\begin{enumerate}
		%\item 
			
			$r$ and $s$ generate $D_n$. Let $\sigma\in D_n$, say $\sigma(1) = k$.
			
			\ul{Case 1}: $\sigma(2) = k+1 \implies \sigma = r^{k-1}$.
			
			\ul{Case 2}: $\sigma(2) = k-1 \implies \sigma = r^{k-1}s$.
	%\end{enumerate}
	
	It remains to prove $srs = r\inv$. It suffices to show $srs(1) = r\inv(1)$ and $srs(2) = r\inv(2)$.
	Compute $srs(1) = sr(1) = s(2) = n$ and $r\inv(1) = n$.
	Check $srs(2) = sr(n) = s(1) = 1$ and $r\inv(2) = 1$.
\end{proof}
Another group is the free group $F_2 =\gen{r,s}$ or $F_n =\gen{r_1,r_2,\dots,r_n}$.

\section{Cosets}

\begin{definition}
	Let $H$ be a subgroup of a group $G$.
	A \ul{left coset} of $H$ in $G$ \ul{with representative} $g$ is the set $$gH = \setm{gh}{h\in H}.$$
	Similarly, the \ul{right coset} is $$Hg = \setm{hg}{h\in H}.$$
\end{definition}
\begin{example}
	$G = \mb Z_9$, $H =\gen{[3]} = \set{[0],[3],[6]}$.
	\begin{align*}
		[0] + H &= \set{[0],[3],[6]} = [3] + H = \set{[3],[6],[0]} = [6] + H = \set{[6],[0],[3]} \\
		[1] + H &= \set{[1],[4],[7]} = [4] + H = \set{[4],[7],[1]} = [7] + H = \set{[7],[1],[4]} \\
		[2] + H &= \set{[2],[5],[8]} = [5] + H = \set{[5],[8],[2]} = [8] + H = \set{[8],[2],[5]}
	\end{align*}
	In this case, right cosets = left cosets.
\end{example}
\begin{example}
	$G = \mb Z$, $H =\gen 3 = 3\mb Z = \set{\dots,-6,-3,0,3,6,\dots}$.
	\begin{align*}
		0 + 3\mb Z &= \set{\dots,-6,-3,0,3,6,\dots} = 3+3\mb Z \\
		1 + 3\mb Z &= \set{\dots,-5,-2,1,4,7,\dots} = 4+3\mb Z \\
		2 + 3\mb Z &= \set{\dots,-4,-1,2,5,8,\dots} = 5+3\mb Z
	\end{align*}
	$G = \mb Z$, $H =\gen n$. \# of distinct cosets $=n$ and right cosets = left cosets.
\end{example}
\begin{example}
	$G = GL_n(\mb R)$, $H = SL_n(\mb R)$. Fix $A\in GL_n(\mb R)$.
	Then $$A\cdot SL_n(\mb R) \os{?}{=} \setm{X\in GL_n(\mb R)}{\det X = \det A}.$$
	\begin{proof}
		\say{$\subseteq$} Let $X\in A\cdot SL_n(\mb R)$, then $X = AZ$ for some $Z\in SL_n(\mb R)$. So $\det X = \det A \cdot \det Z = \det A\cdot 1$.
		
		\say{$\supseteq$} Let $X\in GL_n(\mb R)$ such that $\det X = \det A$.
		WTS: $X = AZ$ for some $Z\in SL_n(\mb R)$, so $Z = A\inv X$.
		Then $\det Z = \det(A\inv X) = \det(A\inv)\cdot \det X = \frac{1}{\det A}\cdot \det X = 1 \implies Z\in SL_n(\mb R)$.
	\end{proof}
	So \# of distinct left cosets $=\infty$. As an exercise, show that $A\cdot SL_n(\mb R) = SL_n(\mb R) \cdot A$.
\end{example}
\begin{remark}
	Infinite groups can have either an infinite and finite number of cosets, but finite groups can only have finite number of cosets.
\end{remark}
\begin{example}
	$G = S_3 = D_3$ is the smallest non-ablian group. $H =\gen{(1\,2\,3)}$ and $K =\gen{(1\,2)}$, write all right and left cosets.
\end{example}
\begin{example}
	In the universe $GL_2(\mb R)$, let $G = \setm{\mat{x&y\\0&1}}{x>0}$ and $H = \setm{\mat{x&0\\0&1}}{x>0}$ with $G\leq H$.
	Fix $A = \mat{x_0&y_0\\0&1}\in G$.
	Then
	$AH = \setm{\mat{xx_0&y_0\\0&1}}{x>0}$ and $HA = \setm{\mat{xx_0&xy_0\\0&1}}{ x>0}.$
	
	So $AH\neq HA$, but they are equal when $eH = He$.
\end{example}

\begin{lemma}
	[Key lemma] Let $H\leq G$ and $a,b\in G$. Then the following are equivalent:
	\begin{enumerate}
		\item $aH = bH$
		\item $Ha\inv = Hb\inv$
		\item $aH\subseteq bH$
		\item $a\in bH$
		\item $b\inv a\in H$
	\end{enumerate}
\end{lemma}
\begin{proof}
	$(1)\implies(2)$ Assume $aH = bH$. WTS: $Ha\inv = Hb\inv$.
	Let $x\in Ha\inv$ (want: $x\in Hb\inv$), then $x = ha\inv$ for some $h\in H$.
	So $x\inv = (ha\inv)\inv = ah\inv \in aH=bH\implies x\inv \in bH\implies x\inv = b\tilde{h}$ for some $\tilde{h}\in H$ (since $h\inv\in H$) $\implies x = (b\tilde{h})\inv = \tilde{h}\inv b\inv \in Hb\inv$ (since $\tilde{h}\in H$).
	Thus $Ha\inv\subseteq Hb\inv$. Similarly, $Hb\inv \subseteq Ha\inv$.
	Then $(2)\implies(1)$ is similar to $(1)\implies(2)$.

	$(1)\implies(3)$ is clear from above.

	$(3)\implies(4)$ Assume $aH\subseteq bH$. WTS: $a\in bH$. By assumption, $a = ae \in aH\subseteq bH \implies a\in bH$.
	
	$(4)\implies(5)$ Assume $a\in bH$. WTS: $b\inv a\in H$.
	$a\in bH\implies a = bh$ for some $h\in H \implies b\inv a = h\in H$.

	$(5)\implies(1)$ Assume $b\inv a\in H$. WTS: $aH = bH$.
	Let $x\in aH$, then $x = ah$ for some $h\in H$. So $x = ah = b(b\inv ah)\in bH$ since $b\inv a\in H$ and $h\in H$, $b\inv ah\in H$.
	So $aH\subseteq bH$.

	Let $y\in bH$, then $y = b\tilde{h}$ for some $\tilde{h}\in H$. So $y= b\tilde{h} = a(a\inv b\tilde{h}) = a((b\inv a)\inv \tilde{h})\in aH$ since $a\inv b = (b\inv a)\inv\in H$ and $\tilde{h}\in H$. Thus $bH\subseteq aH$.
\end{proof}

\begin{theorem}
	Let $H\leq G$. The left (right) cosets of $H$ partition $G$.
\end{theorem}
\begin{proof}
	First, $G = \bigcup_{g\in G} gH$ since $g = ge\in gH$.
	
	Second, we will prove that for $x,y\in G$ we have $xH = yH$ or $xH\cap yH = \emptyset$.
	
	\ul{Case 1}: $xH\cap yH = \emptyset$ done.
	
	\ul{Case 2}: $xH\cap yH \neq \emptyset$. WTS: $xH = yH$.
	Let $g\in xH\cap yH$. Then $xh_1 = yh_2$, where $h_1,h_2\in H$.
	
	This implies $x = y h_2 h_1\inv\in yH$ with $h_2 h_1\in H$, so $x\in yH \us{\text{K.L}}{\implies} xH = yH$.
\end{proof}

\begin{theorem}
	Let $H\leq G$. The number of distinct left cosets of $H$ in $G$ is the same as number of distinct right cosets of $H$ in $G$.
\end{theorem}
\begin{proof}
	Let $L_H$ be the set of left cosets of $H$ in $G$ and $R_H$ be the set of right cosets of $H$ in $G$.
	WTS: $|L_H| = |R_H|$.
	Let $f: L_H\ra R_H$ be defined by $f(aH) = Ha\inv$.
	\begin{enumerate}
		\item $f$ is injective: $f(aH) = f(bH) \os{?}{\implies} aH = bH$. So $f(aH) = f(bH) \rightsquigarrow Ha\inv = Hb\inv \us{\text{K.L}}{\rightsquigarrow} aH = bH$.
		\item $f$ is surjective: Let $Hg\in R_H$ then $f(g\inv H) = Hg$.
	\end{enumerate}
	Done.
\end{proof}

\begin{definition}
	Let $H\leq G$. The \ul{index} of $H$ in $G$ is the number of distinct left (or right) cosets of $H$ in $G$.
\end{definition}
\ul{Notation}: $[G:H]$.
\begin{example}
	$G = \mb Z_9$, $H =\gen{[3]}$, $[G:H] = 3$.
\end{example}
\begin{example}
	$G = \mb Z$, $H = n\mb Z$, $[G:H] = n$.
\end{example}
\begin{example}
	$G = GL_n(\mb R)$, $H = SL_n(\mb R)$, $[G:H] = \infty$.
\end{example}

\subsection{Lagrange's Theorem}

\begin{proposition}
	Let $H\leq G$ and $a\in G$. The map $f: H\ra aH$ defined by $f(h) = ah$ is bijective.
	In particular, any two left cosets of $H$ in $G$ contains the same number of elements.
\end{proposition}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item 
		$f(h_1) = f(h_2)$ implies $ah_1 = ah_2\implies h_1 = h_2$.
		\item 
		$f$ is surjective: Let $x\in aH$, then $x = ah$ for some $h\in H$. So $x = f(h)$.
	\end{enumerate}
	So $|H| = |aH| = |bH|$.
\end{proof}
\begin{theorem}
	[Lagrange's Theorem]
	Let $G$ be a \ul{finite} group, and let $H\leq G$. Then $|G| = |H|\cdot|[G:H]|$.
	In particular, $|H|$ divides $|G|$.
\end{theorem}
\begin{proof}
	Given $G$.
	Left cosets of $H$ partition $G$, $|G| = \sum |\text{cosets}| = \sum_{[G:H]} |H| = |H|\cdot|[G:H]|$.
\end{proof}
\begin{corollary}
	Let $G$ be a finite group and $a\in G$. Then $o(a)$ divides $|G|$.
\end{corollary}
\begin{proof}
	$o(a) = |\gen a|$ divides $|G|$.
\end{proof}
\begin{corollary}
	Let $|G| = p$ a prime number. Then $G$ is a cyclic and any non-identity element is a generator for $G$.
\end{corollary}
\begin{proof}
	Let $a\in G$, $a\neq e$. Then $|\gen a|\geq 2$ divides $p = |G|$. So $|\gen a| = p \implies \gen a = G$.
\end{proof}
\begin{proposition}
	Let $G$ be a finite group, $H\leq G$, and $K\leq H$. Then $[G:K]=[G:H][H:K]$.
	%$K\subseteq H\subseteq G$.
\end{proposition}
\begin{remark}
	It is possible to prove this for the infinite case too, but it is more involved than Lagrange's Theorem.
\end{remark}
\begin{proof}
	$[G:K] = \frac{|G|}{|K|} = \frac{|G|}{|H|}\cdot\frac{|H|}{|K|} = [G:H][H:K]$.
\end{proof}
\begin{remark}
	Lagrange's Theorem says the following: subgroup of $G \rightsquigarrow$ divisor of $|G|$. Does the converse hold? No, it is possible to have divisors for which there are no subgroups.
\end{remark}
\begin{example}
	$|A_4| = 12$ has no subgroup of order 6.
\end{example}

\begin{proposition}
	Every group of order $\leq 5$ is abelian.
%\iffalse
	\begin{center}
	\begin{tabular}{c|cc}
			 & Order & Group  \\
		\hline
	1 & $\{e\}$ &  identity \\
	2 & $\{e,a\}$  & cyclic \\
	3 & & cyclic $\ra$ abelian \\
	4 & & explained below \\
	5 & & cyclic $\ra$ abelian
	\end{tabular}
	\end{center}
%	  \fi
	Order 4 can have subgroups of order 1,2,4 $\ra \exists$ an element $a$ of order 4, so $|\gen a|\ = 4 \implies \gen a = G$ cyclic $\ra$ abelian. or $\ra$ every $\neq e$ has order 2 $\implies a^2 = e$ for all $a\in G \implies G$ is abelian, since $aa = e \implies a = a\inv$ so $xy = (xy)\inv = y\inv x\inv = yx$. This one is called Klein 4-group.
\end{proposition}

\section{Normal subgroups}

\begin{definition}
	A subgroup $H$ of a group $G$ is \ul{normal} if for every $h\in H$ and every $g\in G$, $ghg\inv\in H$.
\end{definition}
\ul{Notation}: $H\triangleleft G$

For $g\in G$, let $gHg\inv = \{ghg\inv \mid h\in H\}$.
A subgroup $H$ is normal in $G$ if $gHg\inv\subseteq H$ for all $g\in G$.

\begin{remark}
	$ghg\inv$ is the conjugate of $h$, we will see can also be written $g\inv hg$.
\end{remark}
\begin{note}
	$ghg\inv\in H$ but $ghg\inv \neq h$ in general, although $ghg\inv = h$ when $g = e$ or $h = e$ or if abelian.
\end{note}

\newpage

\begin{theorem}
	Let $H\leq G$. The following are equivalent:
	\begin{enumerate}
		\item $H$ is normal in $G$
		\item $gHg\inv = H$ for all $g\in G$
		\item $gH = Hg$ for all $g\in G$
	\end{enumerate}
\end{theorem}
\begin{proof}
	(2) $\implies$ (1) Clear.
	(1) $\implies$ (2) WTS: $H \subseteq gHg\inv$ for all $g\in G$. Fix $g\in G$ and take any $h\in H$.
	Consider 
	$g\inv hg = g\inv h(g\inv)\inv \in g\inv H(g\inv)\inv \us{(1)}{\subseteq} H.$
	So $g\inv hg \in H \implies g\inv hg = \tilde h$ for some $\tilde h\in H \implies h = g\tilde h g\inv\in gHg\inv$.
	What we've essentially done is $g\inv Hg \subseteq H$, so $Hg \subset gH$ implies $H\subseteq gHg\inv$.
	(2) $\iff$ (3) Clear.
\end{proof}
\begin{example}
	$G$ any group. Then $\{e\} \triangleleft G$ and $G\triangleleft G$.
\end{example}
\begin{example}
	$SL_n(\mb R) \triangleleft GL_n(\mb R)$ since right cosets = left cosets.
	Take $A\in SL_n(\mb R)$ and $X\in GL_n(\mb R)$. Is $XAX\inv \os{?}{\in} SL_n(\mb R)$. 
	Then $\det(XAX\inv) = \det X\cdot \det A\cdot \det(X\inv) = \det X\cdot \det A \cdot \frac{1}{\det X} = \det A = 1$.
\end{example}
\begin{example}
	Any subgroup of an abelian group is normal. Abelian group $G$ and $H\leq G$. Let $h\in H,g\in G$: $ghg\inv = hgg\inv = h\in H$.
\end{example}
\begin{example}
	$\gen{(1\,2)} \not\triangleleft\ S_3$ but $\gen{(1\,2\,3)} \triangleleft S_3$.
\end{example}

\begin{theorem}
	Every subgroup of index 2 is normal.
\end{theorem}
\begin{proof}
	Let $H\leq G$ and $[G:H] = 2$. We will prove that $gH = Hg$ for all $g\in G$.

	\ul{Case 1}: Let $g\in H$, then $gH = H = Hg$.

	\ul{Case 2}: Let $g\notin H$. Then $G = H\cup gH$ disjoint and $G = H\cup Hg$ disjoint. So $gH = G\bs H = Hg$.
\end{proof}
\begin{example}
	$A_n \triangleleft S_n$, so $[S_n:A_n] = \frac{|S_n|}{|A_n|} = \frac{n!}{n!/2} = 2$.
\end{example}
Abelian $\implies$ All subgroups are normal $\os{?}{\implies}$ Abelian (false). $Q_8 = \set{\pm 1,\pm i,\pm j, \pm k}$, $ij = k$, $ji = -k$.

\subsection{Quotient groups}

Let $H\leq G$ and $G / H =$ the set of left cosets of $H$ in $G$. Note that $|G/H|=[G:H]$.

\begin{theorem}
	If $N\triangleleft G$ then $G/N$ is a group with respect to the operation $aN\cdot bN = abN$.
\end{theorem}
\begin{definition}
	$G/N$ is called the \ul{quotient group} (or \ul{factor group}).
\end{definition}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item The operation is well-defined. If $aN = \tilde aN$ and $bN = \tilde bN$ then $abN = \tilde a\tilde bN$.

			Assume $aN = \tilde aN$ and $bN = \tilde bN$. Then $\tilde a\in aN$ and $\tilde b\in bN$. Thus $\tilde a = ah_1$ and $\tilde b = bh_2$ for some $h_1,h_2\in N$.
			Look at $\tilde a\tilde bN = (ah_1)(bh_2)N = (ah_1 b)h_2 N = ah_1bN$ since $h_2N = N$. Then $ah_1bN = ah_1Nb = aNb = abN$ since $bN = Nb$ due to $N\triangleleft G$.

		\item The operation is associative: $(aN\cdot bN)\cdot cN = aN\cdot(bN\cdot cN)$.

			$(aN\cdot bN)\cdot cN) = abN\cdot cN = (ab)cN$ and $aN\cdot(bN\cdot cN) = aN\cdot bcN = a(bc)N$. Since $(ab)c\in G$ and $a(bc)\in G$, they are abelian and thus equal.

		\item Identity: $e_{G/N} = eN = N$.

			$eN\cdot aN = eaN = aN$ and $aN\cdot eN = aeN = aN$.

		\item Inverses: $(aN)\inv = a\inv N$.

			$aN\cdot a\inv N = aa\inv N = eN = e_{G/N}$ and $a\inv N\cdot aN = a\inv aN = eN = e_{G/N}$.
	\end{enumerate}
	Done.
\end{proof}
\begin{example}
	$G = \mb Z$, $N = 3\mb Z$. $3\mb Z\ \triangleleft\ \mb Z$. $|\mb Z/3\mb Z| = [\mb Z:3\mb Z] = 3$. Then $\mb Z/3\mb Z = \set{3\mb Z, 1+3\mb Z,2+3\mb Z}$.
%\iffalse
	\begin{center}
	\begin{tabular}{c|ccc||c|ccc}
		$\mb Z/3\mb Z$ & $3\mb Z$ & $1+3\mb Z$ & $2+3\mb Z$ & $\mb Z_3$ & $[0]$ & $[1]$ & $[2]$ \\
	\hline 
	$3\mb Z$ & $3\mb Z$ & $1+3\mb Z$ & $2+3\mb Z$ & $[0]$ & $[0]$ & $[1]$ & $[2]$ \\
	$1+3\mb Z$ & $1+3\mb Z$ & $2+3\mb Z$ & $3\mb Z$ & $[1]$ & $[1]$ & $[2]$ & $[3]$ \\
	$2+3\mb Z$ & $2+3\mb Z$ & $3\mb Z$ & $1+3\mb Z$ & $[2]$ & $[2]$ & $[3]$ & $[1]$
	\end{tabular} 
	\end{center}
	$\mb Z/*\mb Z \llr \mb Z_*$ and $? + *\mb Z \llr [?]$.
\end{example}

\begin{example}
	Let $G$ abelian group and $H = $ elements of $G$ of finite order.

	\ul{Claim 1}: $H\leq G$
	\begin{enumerate}
		\item $e\in H$ since $o(e) = 1$
		\item closure under products $a,b\in H \os{?}{\implies} ab\in H$.

			Let $o(a) = n$ and $o(b) = m$, then $(ab)^{nm} = a^{nm}b^{nm} = (a^n)^m (b^m)^n = e^m e^n = e$ since $G$ is abelian. Thus $o(ab) \mid nm \implies o(ab) < \infty$.

		\item closure under inverses: $a\in H \os{?}\implies a\inv\in H$.

			$o(a) = n \implies o(a\inv) = n \implies a\inv\in H$.
	\end{enumerate}
	$G$ is abelian $\implies H\triangleleft G$, so $G/H$ quotient group.

	\ul{Claim 2}: $G/H$ is torsion-free (i.e. there are no elements of finite order).

	Assume $o(aH)<\infty$ then $\exists n\in\mb N$ such that $(aH)^n = e_{G/H} = H$. 
	Then $$a^n H = H \implies a^n\in H \implies o(a^n)<\infty$$ say $o(a^n) = m$.
	Then $o(a^n)^m = e$, so $$a^{nm} = e \implies o(a)\mid nm \implies o(a) < \infty \implies aH = H = e_{G/H}.$$
\end{example}

\section{Homomorphism}

\begin{definition}
	A \ul{homomorphism} from group $G$ to group $H$ is a mapping $\phi:G\ra H$ such that $\phi(xy) = \phi(x)\phi(y)$ for all $x,y\in G$.
\end{definition}
\begin{remark}
	Given $(G,*)$ and $(H,\circ)$, then $\phi(x*y) = \phi(x)\circ\phi(y)$.
\end{remark}
\begin{definition}
	[Monomorphism] injective homomorphism.
\end{definition}
\begin{definition}
	[Epimorphism] surjective homomorphism.
\end{definition}
\begin{definition}
	[Isomorphism] bijective homomorphism.
\end{definition}
If $\phi:G\ra H$ is an isomorphism, then $G$ and $H$ are \ul{isomorphic}.
\ul{Notation}: $G \cong H$.

\begin{example}
	$G$ any group. $\phi: G\ra G$. $\phi = \text{id}_G$. Then $\phi(xy) = xy$ and $\phi(x)\phi(y) = xy$, so it is bijective homomorphism and isomorphism (every group is isomorphic to itself).
\end{example}
\begin{example}
	$G$ any group. $\phi:G\ra G$, $\phi(x) = e$. Then $\phi(xy) = e$ and $\phi(x)\phi(y) = ee$. It is a trivial homomorphism.
\end{example}
\begin{example}
	$\phi:\mb Z\ra\mb Z$, $\phi(v) = 3x$. Then $\phi(x+y) = 3(x+y)$ and $\phi(x)+\phi(y) = 3x+3y$. It is surjective, but not injective, so monomorphism.
\end{example}
\begin{example}
	$\phi:\mb Z\ra\mb Z$, $\phi(x) = -x$. Then $\phi(x+y) = -(x+y)$ and $\phi(x)+\phi(y) = (-x)+(-y)$. It is bijective, so an isomorphism.
\end{example}
\begin{example}
	$G$ any group. $\phi:G\ra G$, $\phi(x) = x\inv$. Then $\phi(xy) = (xy)\inv = y\inv x\inv$ and $\phi(x)\phi(y) = x\inv y\inv$. So $\phi$ is an isomorphism if and only if $G$ is abelian. ($\phi(xy) = \phi(y)\phi(x)$ example of an antiautomorphism).
\end{example}
\begin{definition}
	$\phi: G\ra G$ isomorphism is an \ul{automorphism}.
\end{definition}
\begin{example}
	$\phi: GL_n(\mb R)\ra(\mb R\backslash\{0\},\cdot)$, $\phi(A) = \det A$. Then $\phi(AB) = \det(AB)$ and $\phi(A)\phi(B) = \det A \cdot \det B$. Since $\mat{1/2 & 0 \\ 0 & 2} \neq \mat{1&0\\0&1}$ not injective. But for $\alpha\neq 0$, $\mat{\alpha &0 \\ 0 & 1} \os{\det}{\lra} \alpha$ surjective, so it is an epimorphism.
\end{example}
\begin{example}
	$\phi: (\mb R,+)\ra (\mb R^+,\cdot)$, $\phi(x) = e^x$ exponential function, $e = \lim_{h\ra 0}(1+\frac{1}{h})^h$.
	Then $\phi(x+y) = e^{x+y}$ and $\phi(x)+\phi(y) = e^xe^y$. It is bijective: inverse is $\ln x$. $\psi:(\mb R^+,\cdot)\ra(\mb R,+)$, $\psi(x) = \ln x$.
	Then $\psi(xy) = \ln(xy)$ and $\psi(x)+\psi(y) = \ln x + \ln y$. Isomorphism.
\end{example}
\begin{remark}
	Analagously, in Lie algebra, the matrix exponential serves this role.
\end{remark}

\begin{theorem}
	Let $G,H$ and $K$ be groups.
	\begin{enumerate}
		\item If $\phi:G\ra H$ and $\psi:H\ra K$ are homomorphisms, then so is $\psi\circ\phi:G\ra K$.
		\item If $\phi$ and $\psi$ are isomorphisms, then so is $\psi\circ\phi$.
		\item If $\phi:G\ra H$ is an isomorphism, then so is $\phi\inv:H\ra G$.
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item WTS: $\psi\circ\phi:G\ra K$ is a homomorphism.
			Let $a,b\in G$, then $$(\psi\circ\phi)(ab) = \psi(\phi(ab)) = \psi(\phi(a)\phi(b)) = \psi(\phi(a))\psi(\phi(b)) = (\psi\circ\phi)(a)(\psi\circ\phi)(b).$$
		\item WTS: $\psi\circ\phi$ is bijective.
			Since it's a homomorphism by property 1, it's bijective as a composition of bijective maps.
		\item WTS: $\phi\inv:H\ra G$ is an isomorphism.
			$\phi\inv$ is bijective as an inverse of a bijective map.
			\ul{Left to show}: $\phi\inv(xy) = \phi\inv(x)\phi\inv(y)$ for all $x,y\in H$.
			We have $\phi(\phi\inv(xy)) = xy$ and $$\phi(\phi\inv(x)\phi\inv(y)) = \phi(\phi\inv(x))\phi(\phi\inv(y)) = xy.$$
			So, $\phi(\phi\inv(xy)) = \phi(\phi\inv(x)\phi\inv(y))$.
			Then $\phi\inv(xy) = \phi\inv(x)\phi\inv(y)$ since $\phi$ is injective.
	\end{enumerate}
	Done.
\end{proof}


\begin{theorem}
	Isomorphism is an equivalence relation from the set of all groups.
	$G\sim H$ if $G\cong H$.
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item Reflexive: $G\cong G$ via $\text{id}_G:G\ra G$
		\item Symmetric: $G\cong H\implies H\cong G$, since $G\cong H\ra \exists$ iso. $\phi:G\ra H \ra \phi\inv:H\ra G \ra H\cong G$.
		\item Transitive: $G\cong H$ and $H\cong K \implies G\cong K$, since $G\cong H \ra \exists$ iso. $\phi:G\ra H$ and $H\cong K\ra \exists$ iso. $\psi:H\ra K$ and $\psi\circ\phi:G\ra K$ iso. imply $G\cong K$.
	\end{enumerate}
	Done.
\end{proof}

\begin{theorem}
	Every infinite cyclic group is isomorphic to $\mb Z$.
\end{theorem}
\begin{proof}
	Let $G =\gen a$ be infinite. Define $\phi:\mb Z\ra G$ by $\phi(n) = a^n$.
	\begin{enumerate}
		\item $\phi$ is a homomorphism: $\phi(n+m) = a^{n+m}$ and $\phi(n)\phi(m) = a^na^m = a^{n+m}$.
		\item $\phi$ is injective: $\phi(n) = \phi(m) \implies n = m$, since $G$ is infinite.
		\item $\phi$ is surjective: $\forall x\in G$, $\exists n\in\mb Z$ such that $\phi(n) = x$, since $x = a^n$ for some $n\in\mb Z$ because $G$ is cyclic.
	\end{enumerate}
	$\phi$ is an isomorphism.
\end{proof}
\begin{remark}
	$\mb Z =\gen 1$ with $n = n$th power of 1 and $G =\gen a$ with $x = n$th power of $a$.
\end{remark}

\begin{theorem}
	Every cyclic group of order $n$ is isomorphic to $\mb Z_n$.
\end{theorem}
\begin{proof}
	Let $G =\gen a$, where $|G| = n$, so $G = \set{e=a^0,a^1,a^2,\dots,a^{n-1}}$.
	Let $\phi:\mb Z_n\ra G$ be defined by $\phi([k]) = a^k$.
	\begin{enumerate}
		\item $\phi$ is well-defined: $[k] = [m] \implies \phi([k]) = \phi([m]) \ra k = m+nq$. 
			So $$\phi([k]) = a^k = a^{m+nq} = a^ma^nq = a^m(a^n)^q = a^me^q = a^m = \phi([m]).$$
		\item $\phi$ is bijective - obvious.
		\item $\phi$ is a homomorphism: $\phi([k]+[m]) = \phi([k+m]) = a^{k+m}$ and $\phi([k])\phi([m]) = a^ka^m = a^{k+m}$.
	\end{enumerate}
	Done.
\end{proof}

\begin{theorem}
	Let $\phi :G\ra H$ be a group homomorphism.
	\begin{enumerate}
		\item $\phi(e_G) = e_H$
		\item For any $x\in G$ and any $n\in\mb Z$, $\phi(x^n) = \phi(x)^n$.
		\item If $x\in G$ and $o(x) = n$, then $o(\phi(x))$ divides $n$.
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item $e_G e_G = e_G$ and $\phi(e_G e_G) = \phi(e_G)$, then $\phi(e_G)\phi(e_G) = \phi(e_G) e_H$ implies $\phi(e_G) = e_H$.
		\item \ul{Case 1} $n=0$: $\phi(x^n) = \phi(x^0) = \phi(e_G)$ and $\phi(x)^n = \phi(x)^0 = e_H$.

			\ul{Case 2} $n>0$: WTS: $\phi(x^n) = \phi(x)^n$ for all $n\geq 1$.
			Proof by induction: \ul{Base} $n=1$. $\phi(x^1) = \phi(x)^1 \iff \phi(x) = \phi(x)$ true.
			\ul{Inductive step}: $\phi(x^n) = \phi(xx^{n-1}) = \phi(x)\phi(x^{n-1}) = \phi(x)\phi(x)^{n-1} = \phi(x)^n$

			\ul{Case 3} $n<0$: say $n=-n_0$ for some $n_0\in\mb N$. Then $x^n x^{-n} = e_G = x^n x^{n_0}$, so $\phi(x^nx^{n_0}) = \phi(e_G)$ and $\phi(x^n)\phi(x^{n_0}) = e_H$ imply $\phi(x^n) = \phi(x^{n_0})\inv = (\phi(x)^{n_0})\inv = \phi(x)^{-n_0} = \phi(x)^n$.
		\item $o(x) = n \implies x^n = e_G \implies \phi(x^n) = \phi(e_G) \implies \phi(x)^n = e_H \implies o(\phi(x))\mid n$.
	\end{enumerate}
	Done.
\end{proof}

\begin{theorem}
	Let $\phi:G_1\ra G_2$ be a group homomorphism.
	\begin{enumerate}
		\item If $H_1\leq G_1$ then $\phi(H_1) \leq G_2$.
		\item If $H_2\leq G_2$ then $\phi\inv(H_2)\leq G_1$.
		\item If $H_2\triangleleft G_2$ then $\phi\inv(G_2)\triangleleft G_1$.
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item - identity: $e_2 = \phi(e_1)\in\phi(H_1)$.

			- closure under products: Let $x,y\in\phi(H_1)$. (WTS: $xy\in\phi(H_1)$).
			So $x = \phi(a)$ and $y = \phi(b)$ for some $a,b\in H_1$. Then $xy = \phi(a)\phi(b) = \phi(ab)\in\phi(H_1)$ since $ab\in H_1$.

			- closure under inverses: $x\in \phi(H_1)\implies x = \phi(a)$ for $a\in H_1 \implies x\inv = \phi(a)\inv = \phi(a\inv)\in\phi(H_1)$ since $a\inv\in H_1$.
		\item - identity: $\phi(e_1) = e_2 \implies e_1\in\phi\inv(e_2) \subseteq \phi\inv(H_2) \implies e_1\in\phi\inv(H_2)$ since $\phi(e_1) = e_2\in H_2$.

			- closure under products: Let $a,b\in\phi\inv(H_2)$, then $\phi(a),\phi(b)\in H_2$. So $\phi(a)\phi(b) = \phi(ab)\in H_2$ implies $ab\in\phi\inv(H_2)$.

			- closure under inverses: Let $a\in\phi\inv(H_2)$, so $\phi(a)\in H_2$ and $\phi(a)\inv = \phi(a\inv)\in H_2$ imply $a\inv\in\phi\inv(H_2)$.
		\item By (2), $\phi\inv(H_2)\leq G_1$. WTS: $gag\inv\in\phi\inv(H_2)$ for all $a\in\phi\inv(H_2)$ and all $g\in G_1$.
			Then $\phi(gag\inv) = \phi(g)\phi(a)\phi(g)\inv$, where $\phi(a)\in H_2$, $\phi(g)\in G_2$, and $\phi(g)\inv\in G_2$. Thus $gag\inv\in\phi\inv(H_2)$.
	\end{enumerate}
	Done.
\end{proof}
\begin{example}
	\ul{Try to prove}: If $H_1\triangleleft G_1$ then $\phi(H_1)\triangleleft G_2$. (it is false unless $\phi$ is surjective epimorphism)
\end{example}
\begin{proof}
	WTS: $gxg\inv\in\phi(H_1)$ for all $x\in\phi(H_1)$ and all $g\in G_2$.
	Then $x = \phi(a)$ for some $a\in H_1$.
	\ul{Assume}: $\phi$ is surjective, $g = \phi(b)$ for some $b\in G_1$.
	So $g\phi(a)g\inv \ra \phi(b)\phi(a)\phi(b)\inv = \phi(bab\inv)\in\phi(H_1)$ since $bab\inv\in H_1$.
	Thus $gxg\inv\in\phi(H_1)$.
\end{proof}

\begin{theorem}
	[Cayley's Theorem] 
	Every group is isomorphic to a permutation group.
\end{theorem}
\begin{proof}
	Let $G$ be a group and $y\in G$. Define $\lambda_g:G\ra G$ by $\lambda_g(x) = gx$.
	Then $\lambda_g\in S_G$. (HW problem).
	Define $\phi:G\ra S_G$ by $\phi(g) = \lambda_g$.
	\ul{Claim 1}: $\phi$ is a homomorphism. WTS: $\phi(gh) = \phi(g)\phi(h)$.
	Then $\phi(gh) = \lambda_{gh}$ and $\phi(g)\phi(h) = \lambda_g\lambda_h$.
	Thus $\lambda_{gh}(x) = (gh)x$ and $(\lambda_g\lambda_h)(x) = \lambda_g(\lambda_h(x)) = \lambda_g(hx) = g(hx) = (gh)x$.
	So, $\lambda_{gh} = \lambda_g\lambda_h$ and hence $\phi$ is a homomorphism.

	A permutation group is a subgroup of a symmetric group.
	\ul{Claim 2}: $G\cong\phi(G)\leq S_G$.
	We have $\phi:G\ra\phi(G)$, a surjective homomorphism (epimorphism).
	It suffices to show $\phi$ is injective.
	Assume $\phi(g) = \phi(h)$, then $\lambda_g = \lambda_h \implies \lambda_g(e) = \lambda_h(e) \implies ge = he \implies g = h$.
\end{proof}

\subsection{Homomorphisms and normal subgroups}

\begin{definition}
	Let $\phi:G\ra H$ be a group homomorphism. The \ul{kernel} of $\phi$ is $$\ker\phi = \phi\inv(\{e_H\}) = \setm{x\in G}{\phi(x)=e_H}.$$
	Homomorphism from $G\lra $ Normal subgroup of $G$, $\phi:G\ra H\rightsquigarrow \ker\phi\triangleleft G$.
\end{definition}
\begin{theorem}
	$\ker\phi\triangleleft G$
\end{theorem}
\begin{proof}
	$\set{e_H}\triangleleft H\implies \phi\inv(\set{e_H})\triangleleft G$.
\end{proof}
\begin{proof}
	[Long proof] Cases:
	\begin{enumerate}
		\item $\ker\phi$ is a subgroup of $G$.

			- identity: 
			$e_G\in\ker\phi$ since $\phi(e_G)=e_H$.

			- closure under products:
			$x,y\in\ker\phi\os{?}{\lra}xy\in\ker\phi$.
			So $\phi(xy)=\phi(x)\phi(y)=e_He_H=e_H$.

			- closure under inverses:
			$x\in\ker\phi\os{?}{\implies}x\inv\in\ker\phi$.
			So $$\phi(x)=e_H\implies \phi(x)\inv = e_H\inv \implies \phi(x\inv) = e_H.$$
		
		\item $\ker\phi$ is normal:
			$gxg\inv\in\ker\phi$ for all $x\in\ker\phi$, for all $g\in G$.
			So \[\phi(gxg\inv) = \phi(g)\phi(x)\phi(g\inv) = \phi(g)e_H\phi(g)\inv = \phi(g)\phi(g)\inv = e_H.\]
			Done.
	\end{enumerate}
\end{proof}

\begin{example}
	$\phi:GL_n(\mb R)\ra(\mb R\backslash\{0\},\cdot)$.
	Let $\phi(A) = \det A$, then $\ker\phi = SL_n(\mb R) \triangleleft GL_n(\mb R)$.
\end{example}
\begin{example}
	Find all homomorphisms $\phi:\mb Z_5\ra\mb Z_{12}$.
	We know $\ker\phi\triangleleft\mb Z_5\implies |\ker\phi| = 1$ or 5.
	If $|\ker\phi| = 1 \implies \ker\phi = \set{[0]}$. If $|\ker\phi| = 5\implies \ker\phi = \mb Z_5$, then $\phi$ is the trivial homomorphism.
	Note that $\ker\phi = \{[0]\}\iff\phi$ is injective (will be HW). Then $|\phi(\mb Z_5)| = 5$ and $\phi(\mb Z_5)\leq\mb Z_{12}$, but $5\nmid 12$ impossible by Lagrange's theorem.
\end{example}

\section{Isomorphism Theorems}

$$\us{\phi\, :\, G\ra H}{\text{Homomorphisms}} \us{\os{?}{\lla}}{\lra} \us{\ker\phi\, \triangleleft\, G}{\text{Normal subgroups}}$$

Does every normal subgroup arise as a kernel of a homomorphism? Yes.

Let $N\triangleleft G$. Consider $\rho:G\ra G/N$ given by $\rho(a) = aN$.
\ul{Claim}: $\rho$ is a homomorphism.
Then $\rho(ab) = abN$ and $\rho(a)\rho(b) = aN\cdot bN$.
So $\rho$ is surjective. Take any $xN\in G/N$, then $\rho(x) = xN$.
Then $\ker\rho = \setm{a\in G}{\rho(a)=e_{G/N}} = \setm{a\in G}{\rho(a)=N} = \setm{a\in G}{aN=N} = N$ since $aN=eN$ implies $e\inv a\in N$.
We say $\rho$ is a \ul{canonical} homomorphism.

\begin{theorem}
	[First Isomorphism Theorem] Let $\phi:G\ra H$ be a surjective homomorphism. Then $$H\cong G/\ker\phi.$$
\end{theorem}
\begin{proof}
	Let $N = \ker\phi\triangleleft G$.
	%Draw commutative diagram.
	\begin{tikzcd}
		G \arrow{rr}{\phi} \arrow{dr}{\rho} & & H \\
											  %& A \arrow[ur,"\psi?",dashrightarrow] &
											& A \arrow{ur}{\psi?} &
	\end{tikzcd}
	Define: $\psi: G/N\ra H$ by $\psi(aN)=\phi(a)$.
	\begin{enumerate}
		\item $\psi$ is well-defined:
			$aN=bN\implies\psi(aN)=\psi(bN)$.

			Indeed, $aN=bN \os{\text{K.L.}}{\implies}b\inv a\in N \implies b\inv a\in \ker\phi \implies \phi(b\inv a)=e_H \implies \phi(b)\inv\phi(a)=e_H \implies \phi(a)=\phi(b) \implies \psi(aN)=\psi(bN)$.
		
		\item $\psi$ is a homomorphism:

			$\psi(aN\cdot bN) = \psi(abN) = \phi(ab)$ and $\psi(aN)\psi(bN) = \phi(a)\phi(b)$.

		\item $\psi$ is injective:
			$\psi(aN)=\psi(bN) \implies aN=bN$.

			Indeed, $\psi(aN) = \psi(bN) \implies \phi(a)=\phi(b) \implies \phi(b)\inv\phi(a) = e_H \implies \phi(b\inv a) = e_H \implies b\inv a\in\ker\phi \implies b\inv a\in N \os{\text{K.L.}}{\implies} aN=bN$.

		\item $\psi$ is surjective:

			Let $x\in H$. WTS: $\exists aN\in G/N$ such that $\psi(aN) = x$.
			Because $\phi$ is sujrective, $\exists a\in G$ such that $\phi(a) = x$.
			Then $\psi(aN)=\phi(a)=x$.
	\end{enumerate}
\end{proof}
\begin{corollary}
	Let $\phi:G\ra H$ be a homomorphism. Then $\phi(G)\cong G/\ker\phi$, i.e., $\ul{\phi:G\ra\phi(G)}\leq H$.
\end{corollary}
\begin{example}
	$\phi:GL_n(\mb R)\ra (\mb R\bs\set0,\cdot)$.
	Then $\phi(A) = \det A$ homomorphism, surjective; and $\ker\phi=SL_n(\mb R)$.
	$$GL_n(\mb R)/SL_n(\mb R)\cong(\mb R\bs\set0,\cdot).$$
\end{example}
\begin{example}
	$\phi:\mb Z\ra\mb Z_n$.
	Then $\phi(x)=[x]$ surjective homomorphism; and $\ker\phi=n\mb Z$.
	So $\mb Z/n\mb Z\cong\mb Z_n$.
\end{example}

\begin{theorem}
	[Second Isomorphism Theorem]
	Let $H\leq G$ and $N\triangleleft G$. Then
	\begin{enumerate}
		\item $HN\leq G$
		\item $H\cap N\triangleleft H$
		\item $H/H\cap N\cong HN/N$
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item $HN = \setm{hn}{h\in H,n\in N}$.
			\begin{itemize}
				\item identity: $e=ee\in HN$
				\item closure under products:
					let $x,y\in HN$. WTS: $xy\in HN$. We have $x=h_1n_1$ and $y=h_2n_2$ for some $h_1,h_2\in H$ and $n_1,n_2\in N$.
					So $xy=(h_1n_1)(h_2n_2) = h_1h_2h_2\inv n_1h_2n_2 = (h_1h_2)(h_2\inv n_1h_2n_2)$, where $h_1h_2\in H$ and $h_2\inv n_1h_2\in N$, so $xy\in HN$.
				\item closure under inverses:
					let $x\in HN$. WTS: $x\inv\in HN$. Then $x=hn$ for some $h\in H$ and $n\in N$. So $x\inv = (hn)\inv = n\inv h\inv = h\inv hn\inv h\inv = h\inv(hn\inv h\inv)$, where $h\inv\in H$ and $n\inv,hn\inv h\inv\in N$, so $x\inv\in HN$.
			\end{itemize}
			Thus $HN\leq G$.
		\item Clearly $H\cap N\subseteq H$ and $H\cap N$ is a subgroup as intersection of two subgroups.
			Need to show $H\cap N$ is normal in $H$.
			Let $x\in H\cap N$ and $h\in H$. WTS: $hxh\inv\in H\cap N$.
			Then $hxh\inv\in H$ since $h$ and $x$ are in $H$.
			Also $hxh\inv\in N$ since $x\in N$ and $N$ is normal.
		\item Define $\phi:H\ra \ul{HN/N}$ (makes sense: $HN\leq G$ group, $N\leq HN \ra N\triangleleft HN$) by $\phi(h)=hN$.
			\ul{Claim 1}: $\phi$ is a homomorphism.
			Then $\phi(h_1h_2) = h_1h_2N$ and $\phi(h_1)\phi(h_2) = h_1N\cdot h_2N$.
			\ul{Claim 2}: $\phi$ is surjective.
			Let $xN\in HN/N$. Then $x\in HN$ and $x=hn$ for some $h\in H$ and $n\in N$.
			Then $xN = (hn)N = hnN = hN = \phi(h)$.
			By the 1st Isomorphism Theorem, $H/\ker\phi\cong HN/N$.
			Then $\ker\phi = \setm{h\in H}{\phi(h) = e_{HN/N}} = \setm{h\in H}{N} = \setm{h\in H}{hN=N}$.
			Using the Key Lemma, $hN=N \iff hN=eN \iff e\inv h\in N \iff h\in N$.
			So $\ker\phi = \setm{h\in H}{h\in N} = H\cap N$.
	\end{enumerate}
	Done.
\end{proof}

\begin{theorem}
	[Correspondence Theorem]
	Let $N\triangleleft G$. Then there is a bijective correspondence between the set of subgroups of $G$ containing $N$ and the set of subsets of $G/N$.
	Normal subgroups of $G$ containing $N$ correspond to normal subgroups of $G/N$.
\end{theorem}
\begin{remark}
	What does this look like? $N\triangleleft H\leq G$, we are looking for $H \lr H/N\leq G/N$.
\end{remark}
\begin{note}
	If $H\triangleleft G$, then $H/N\triangleleft G/N$.
\end{note}
\begin{theorem}
	[Third Isomorphism Theorem]
	Let $N\triangleleft G$ and $H\triangleleft G$ with $N\subseteq H$. Then
	$$ G/H \cong \nicefrac{G/N}{H/N}.$$
\end{theorem}
Define $\phi: G/N\ra G/H$ by $\phi(gN)=gH$. Then $\ker\phi = H/N$, apply 1st Isomorphism Theorem.

\section{Rings}

\begin{definition}
	A \ul{ring} $R$ is a non-empty set with two binary operations: \say{addition} and \say{multiplication} such that:
	\begin{enumerate}
		\item $(R,+)$ is an abelian group
		\item $\cdot$ is associative
		\item $\cdot$ is distributive over addition
	\end{enumerate}
\end{definition}
\begin{enumerate}
	\item $(a+b)+c = a+(b+c)$
	
		$\exists 0\in R$ (identity for addition) such that $a+0=0+a=a$
	
		$\forall a\in R$ $\exists -a\in R$ (inverse of $a$ under addition) such that $a+(-a)=(-a)+a = 0$

		$a+b=b+a$
	\item $a(bc) = (ab)c$
	\item $a(b+c) = ab+ac$
		
		$(b+c)a = ba+ca$
\end{enumerate}

\begin{definition}
	A ring is \ul{commutative} if $\cdot$ is commutative.
\end{definition}
\begin{definition}
	A ring such that $\exists 1\neq 0$ (identity for multiplication) with $a1=1a$ for all $a\in R$ is a ring with \ul{unity} or \ul{identity}.
\end{definition}
\begin{definition}
	In a ring $R$ with unity, an element $a\in R$ is a \ul{unit} if it has a multiplicative inverse: $\exists a\inv\in R$ (inverse for $a$ under multiplication) such that $aa\inv=a\inv a = 1$.
	$\mb R^\times = $ the set of all units in $R$.
\end{definition}
\begin{definition}
	A \ul{division ring} is a ring $R$ with unity such that $R^\times = R\bs\set0$.
\end{definition}
\begin{definition}
	A \ul{field} is a commutative division ring.
\end{definition}

\begin{example}
	$(\mb Z,+,\cdot)$: ring, commutative, with unity, $\mb Z^\times=\set{-1,1}$.
\end{example}
\begin{example}
	$(\mb Q,+,\cdot)$: ring, commutative, with unity, $\mb Q^\times=\mb Q\bs\set0$, division ring, field.
\end{example}
\begin{example}
	$(\mb Z_n,+,\cdot)$: ring, commutative, with unity, $\mb Z_n^\times=\setm{[a]\in \mb Z_n}{\gcd(a,n)=1}$, $\ra$ division ring if $n$ is prime, $\ra$ not a division ring if $n$ is composite ($n=km$, $k,m>1$, $\ra[k],[m]\notin\mb Z_n^\times$).
	Vector space: $\mb Z_n^p$ has $p^n$ elements.
\end{example}
\begin{example}
	$(M_n(\mb R),+,\cdot)$: ring, noncommutative, with unity, $M_n(\mb R)^\times = GL_n(\mb R)$.
\end{example}
\begin{example}
	Ring without unity: $2\mb Z$.
\end{example}

\ul{Exam 2 Bonus}: $G = S_3$, $N = \gen{(1\,2\,3)} \ra$ abelian. Then $[G:N] = 2$ so $|G/N|=2 \ra $ cyclic $\ra$ abelian.

\begin{definition}
	A nonzero element $r$ of a ring $R$ is
	\begin{enumerate}
		\item a \ul{left zero divisor} if $\exists s\in R$, $s\neq 0$, such that $rs=0$,
		\item a \ul{right zero divisor} if $\exists s\in R$, $s\neq0$, such that $sr=0$,
		\item a \ul{zero divisor} if it's both left and right zero divisor.
	\end{enumerate}
\end{definition}
\begin{example}
	$\mb Z$ no zero divisors.
\end{example}
\begin{example}
	$\mb Z_n \ra n$ prime: no zero divisors, $n \ra$ composite: there are zero divisors. If $n=km$, $1<k,m<n$, then $[k][m]=[0]$.
\end{example}
\begin{example}
	$M_n(\mb R)$, let $A = \mat{0&1\\0&0}$, then $AA=0$.
\end{example}
\begin{example}
	idempotent element $\neq 0,1$ is a zero divisor. $a^2=a \la$ idempotent i.e., $0^2=0,1^2=1$. In $M_n(\mb R)$: $\mat{1&0\\0&0}^2 = \mat{1&-\\0&0}$. $a^2=a \ra a(a-1)=0$, where $a$ zero divisor.
\end{example}
\begin{example}
	units $\neq$ zero divisors. exercise.
\end{example}
\begin{definition}
	An \ul{integral domain} is commutative ring with unity which has no zero divisors.
\end{definition}
\begin{example}
	$\mb Z$
\end{example}
\begin{example}
	$\mb Z_p$
\end{example}

\begin{theorem}
	A finite integral domain is a field.
\end{theorem}
\begin{proof}
	Let $D$ be a finite integral domain. WTS: $D^\times = D\bs\set0$.
	Let $a\in D\bs\set0$. Define $\lambda_a:D\bs\set0\ra D\bs\set0$ by $\lambda_a = ax$.
	\ul{Claim}: $\lambda_a(D\bs\set0) \subseteq D\bs\set0$.
	Let $x\neq 0$, then $\lambda_a(x) = ax$ because integral domain has no zero divisors.
	\ul{Claim}: $\lambda_a$ is injective.
	Assume $\lambda_a(x) = \lambda_a(y)$, then $ax=ay \implies a(x-y)=0 \implies x=y$.
	Since $D$ is finite, $\lambda_a$ must be surjective.
	Then $\exists x\in D\bs\set0$ such that $$\lambda_a(x)=1 \implies ax=1 \implies xa = ax = 1 \implies x = a\inv \implies a\in D^\times.$$
	Done.
\end{proof}

\newpage
\begin{theorem}
	Let $R$ be a ring and $a,b\in R$.
	\begin{enumerate}
		\item $a0=0a=0$
		\item $a(-b)=(-a)b = -ab$
		\item $(-a)(-b)=ab$
	\end{enumerate}
\end{theorem}
\begin{proof}
	Cases:
	\begin{enumerate}
		\item $0a = (0+0)a = 0a + 0a \implies 0+0a = 0a + 0a \implies 0 = 0a$.
		\item WTS: $a(-b) = -ab$ i.e., $a(-b)$ is an additive inverse of $ab$.
			Then $a(-b)+ab = a((-b)+b) = a0 = 0$, so $a(-b)$ is inverse of $ab$.
		\item $(-a)(-b) \os{(2)}{=} -(-a)b = -(-ab) = ab$.
	\end{enumerate}
	Done.
\end{proof}

\begin{proposition}
$\set{\text{units}}\cap\set{\text{zero divisors}}\neq\emptyset$.
\end{proposition}
\begin{proof}
	Consider for $u$ \ul{unit} $\ra\exists u\inv$ and for a \ul{zero divisor} $\ra \exists v\neq 0$ such that $uv=0$. 
	So $u\inv uv = u\inv 0$ implies $v=0$, which is a contradiction.
\end{proof}

\section{Hamiltonian quaternions}

Consider $\mb R$. 
Then $\mb C = \setm{a+bi}{a,b\in\mb R,\, i^2=-1}$.
Let $\mb H = \setm{a+bi+cj+dk}{a,b,c,d\in\mb R}$.

Addition: $(a_1+b_1i+c_1j+d_1k)+(a_2+b_2i+c_2j+d_2k) = (a_1+a_2)+(b_1+b_2)i+(c_1+c_2)j+(d_1+d_2)k$, abelian group.

Multiplication: $i^2=j^2=k^2 = -1$. Consider $i \ra j \ra k$ in a circle in alphabetical order. If you are moving clockwise the sign is positive, counterclockwise is negative.
So
\begin{align*}
	ij &= k, &\qquad ik &=-j, &\qquad jk &= i, \\
	ji &=-k, &\qquad ki &= j, &\qquad kj &=-i.
\end{align*}
Then
\begin{align*}
	(a_1+b_1i+c_1j+d_1k)(a_2+b_2i+c_2j+d_2k)
	&= a_1a_2+a_1b_2i+a_1c_2j+a_1d_2k \\
	&+ b_1a_2i-b_1b_2+b_1c_2k-b_1d_2j \\
	&+ c_1a_2j-c_1b_2k-c_1c_2+c_1d_2i \\
	&+ d_1a_2k+d_1b_2j-d_1c_2i-d_1d_2 \\
	&= (a_1a_2-b_1b_2-c_1c_2-d_1d_2) \\
	&+ (a_2b_2+b_1a_2+c_1d_2-d_1c_2)i \\
	&+ (a_1c_2-b_1d_2+c_1a_2+d_1b_2)j \\
	&+ (a_1d_2+b_1c_2-c_1b_2+d_1a_1)k
\end{align*}
is associative and $\cdot$ distributes over +.
Identity: $1+0i+0j+0k = 1$.

$M_2(\mb C)$: $1 = \mat{1&0\\0&1}$, $i = \mat{0&1\\-1&0}$, $j = \mat{0&i\\i&0}$, $k = \mat{i&0\\0&-i}$.

WTS: $\mb H^\times = \mb H\bs\set0$.
Let $z = a+bi+cj+dk$.
\ul{Conjugate}: $\conj z = a-bi-cj-dk \ra$ $a_2=a_1$, $b_2=-b_1$, $c_2=-c_1$, $d_2=-d_1$.
\ul{Norm}: $||z|| = z\conj z = a^2+b^2+c^2+d^2$.
So $z\neq0\iff ||z||>0$.
If $z\neq0$ then $z\inv=\frac{\conj z}{||z||}$, so $zz\inv = \frac{z\conj z}{||z||} = \frac{||z||}{||z||} = 1$ since $z\inv = \frac{a}{a^2+b^2+c^2+d^2} - \frac{b}{a^2+b^2+c^2+d^2}i - \frac{c}{a^2+b^2+c^2+d^2}j - \frac{d}{a^2+b^2+c^2+d^2}k$.

\section{Review}

\begin{example}
	$G$ if finite. WTS: $G$ is cyclic $\iff\exists a\in G$ such that $o(a)=|G|$.
\end{example}
\begin{proof}
	\ul{$\implies$} Given: $G$ is cyclic, $\exists a\in G$ such that $\gen a=G$. So $o(a) = |\gen a| = |G|$.
	\ul{$\Lla$} Given: $\exists a\in G$ such that $o(a)=|G|$. Then $\gen a\leq G$ and $|\gen a|=o(a)=|G|\ra G$ is finite $\ra\gen a=G$.
\end{proof}

Homomorphic image $f:X\ra Y$, so image of $f=f(X)=Y$. Note $\phi:G\ra\mb Z_{10}$ then $\phi(G)=\mb Z_{10}$, preimage $\phi\inv(\mb Z_{10})\subseteq G$.
\begin{example}
	$\sigma=\sigma_1\,\sigma_2\,\dots\,\sigma_m$ is product of disjoint cycles, $\sigma\in S_n$. 
	WTS: $o(\sigma)=\text{lcm}\set{o(\sigma_i)}_{i=1}^m$.
\end{example}
\begin{proof}
	$\text{id}\,=\sigma^k=(\sigma_1\,\sigma_2\,\dots\,\sigma_m)^k=\sigma_1^k\,\sigma_2^k\,\dots\,\sigma_m^k$.
	Take $\sigma\tau=\,\text{id}$, then $\sigma=\tau\in=\,\text{id}$.

	So $\sigma_1^k=\,\text{id},\sigma_2^k=\,\text{id},\dots,\sigma_m^k=\,\text{id}\ra o(\sigma_1)\mid k,o(\sigma_2)\mid k,\dots,o(\sigma_m)\mid k$.
	Say $\sigma_i$ is a cycle of length $l_i$, then $l_i\mid k,l_2\mid k,\dots,l_m\mid k$.
	If $\sigma^k=\,\text{id}$, then $k$ is divisible by $l_2,l_2,\dots,l_m$.
	So $o(\sigma)$ is the \ul{least} such positive $k$ $\implies o(\sigma)=\text{lcm}(l_1,l_2,\dots,l_m)$.
\end{proof}

Consider $\mb Z_{30}/\ker\phi\cong G$, then $|\mb Z_{30}|/|\ker\phi|=5$, $|\mb Z_{30}/\ker\phi| = [\mb Z_{30}:\ker\phi] = |\mb Z_{30}|/|\ker\phi|$.
So $$|G/H|=|G|/|H|.$$

Consider $G$ group, and $C=\setm{xyx\inv y\inv}{x,y\in G}$ commutators.
Then $\gen C = [G,G]$ is the commutator subgroup.
Then $G^{\text{ab}}G/[G,G]$ abelianization of $G$.
Trivial if $G$ is abelian: $$xyx\inv y\inv=e\iff xyx\inv = y \iff xy=yx.$$
Then $[G,G]=\begin{cases}\set e & \text{if }G\text{ is abelian} \\ \text{in between} \\ [G,G]=G & \text{if }G\text{ is \ul{perfect}} \end{cases}$.

An example of a perfect group is $SL_n$.
For a perfect group, $G^{\text{ab}}=\set e$.

Field extensions, $F/K$ means $K\subseteq F$.
For example $\mb R/\mb Q$ or $\mb C/\mb R$.
The degree of an extension is $$[F:K]=\dim_k F.$$
So $\mb R/\mb Q$ has $\deg=\infty$.
For $\mb C = \setm{a+bi}{a,b\in\mb R}$ and $\deg=2$.

$\text{Aut}(F/K) = $ automorphism of $F$ which fix all elements of $K$.
$\text{Aut}(\mb C/\mb R)=\set{\text{id},\text{conjugation}}$, the number of such automorphisms cannot exceed the degree of the extension.
If the degree is finite, it is an algebraic extension.
$\mb C/\mb R$, consider $p(x) = x^2+1 \ra$ root: $\mb R(i)=\mb C$.
Automorphism permute the roots.
$i,-i$, so conjugation permutes $i,-i$.

Polynomial ring quotient: $\mb R[x]/(x^2+1)\cong\mb C$.
Must be separable (no repeated roots) if it has one root, it has all the other roots, then it is called Galois extension and $\text{Gal}(F/K)$ is the size of the extension.

In the field extension you can have fields intermediate fields $K\subseteq L\subseteq F$.
%The extension is normal if
An intermediate field extension is normal if and only if the corresponding subgroup of the Galois group is normal.

\end{document}