\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amssymb, amsmath
}
\newcommand{\ds}{\displaystyle}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Var}{\operatorname{Var}}
\newcommand{\norm}{\vartriangleleft}
\newcommand{\PP}{\mathcal{P}}
\renewcommand{\phi}{\varphi}
\newpagestyle{main}[\small]{
\headrule
\sethead[\usepage][][]
{}{}{\usepage}
}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}
\title{\sc Math 31 -- Homework 7 \framebox{Solutions!}}
\author{due Wednesday, August 16}
\titleformat{\section}{\large\sc}{\thesection.}{1em}{}
\date{}
\begin{document}
\maketitle
\pagestyle{main}
\textbf{Instructions:} This assignment is due at the \emph{beginning} of class. Staple your work together (do not just fold over the corner). Please write the questions in the correct order. If I cannot read your handwriting, you won't receive full credit.
\begin{enumerate}
\item Let $X$ be a set (not necessarily finite) and let $Y \subseteq X$. Recall the group $(\PP(X), \triangle)$ from Homework 1. Prove without using any material from Chapter 14 that
\[
\PP(X)/\PP(Y) \cong \PP(X \smallsetminus Y).
\]
(Don't forget to make sure you verify that $\PP(Y)$ is a subgroup!)
\textbf{Proof:} We actually don't need to separately verify that $\PP(Y)$ is a subgroup. We will define a map $\phi :\PP(X) \to \PP(X \smallsetminus Y)$, show that $\phi$ is a surjective homomorphism, check the $\ker(\phi) = \PP(Y)$, and then Theorem 13.1 and the First Isomorphism Theorem (Theorem 13.2) do the rest---Theorem 13.1 will confirm that $\PP(Y)$ is a normal subgroup and the First Isomorphism Theorem will give the desired isomorphism.
Before we try to come up with a $\phi$, let's think about what $\PP(X)/\PP(Y)$ looks like. The elements in this groups are cosets of $\PP(Y)$:
\[
\PP(X)/\PP(Y) = \{\PP(Y) + S : S \in \PP(X)\}
\]
Two elements of $\PP(X)$ get ``compressed'' into the same coset of $\PP(X)/\PP(Y)$ if and only if they differ (with respect to the operation $\triangle$) by a subset of $Y$. Put another way, two elements $S$ and $T$ of $\PP(X)$ get ``compressed'' to the same coset if $S \smallsetminus Y = T \smallsetminus Y$.
We don't need to realize this to find $\phi$, but it does help.
We know that we want a map whose kernel is $\PP(Y)$. In other words, we want $\phi(S) = \emptyset$ for all $S \subseteq Y$. One such map is that defined by $\phi(S) = S \smallsetminus Y$ for all $S \in \PP(X)$. Let's check if it works.
Is $\phi$ a homomorphism? Let $S,T \in \PP(X)$. Then,
\[
\phi(S \triangle T) = (S \triangle T) \smallsetminus Y
\]
while
\[
\phi(S) \triangle \phi(T) = (S \smallsetminus Y) \triangle (T \smallsetminus Y).
\]
Are these two the same?
\[
(S \triangle T) \smallsetminus Y = \{x \in X : x \not\in Y\text{ and $x$ is in exactly one of $S$ and $T$}\} = (S \triangle T) \cap \overline{Y}
\]
and
\begin{align*}
(S \smallsetminus Y) \triangle (T \smallsetminus Y) &= \{x \in X : \text{$x$ is in exactly one of $S\smallsetminus Y$ and $T\smallsetminus Y$}\}\\
&= \overline{Y} \cap \{x \in X : \text{$x$ is in exactly one of $S$ and $T$}\}\\
&= (S \triangle T) \cap \overline{Y}.
\end{align*}
So, $\phi$ is a homomorphism.
Moreover, $\phi$ is surjective because for any $T \in \PP(X \smallsetminus Y)$, it's obvious that $\phi(T) = T$.
Lastly, $\ker(\phi) = \{T \in \PP(X) : T \smallsetminus Y = \emptyset\} = \{T \in \PP(X \smallsetminus Y) : T \subseteq Y = \emptyset\} = \PP(Y)$.
By the Theorem 13.1 and the First Isomorphism Theorem, $\PP(Y) \norm \PP(X)$ and $\PP(X)/\PP(Y) \cong \PP(X \smallsetminus Y)$.
\hfill $\square$
\hrulefill
\item (13.11) Suppose $H \norm G$ and $K \norm G$.
\begin{enumerate}
\item Prove that $G/H \times G/K$ has a subgroup that is isomorphic to $G/(H \cap K)$.
\textbf{Proof:} We probably suspect we need to define a homomorphism somewhere, but where? As we're looking to show that a \emph{subgroup} of $G/H \times G/K$ is isomorphic to all of $G/(H \cap K)$, it is hopeless to try to define a homomorphism whose domain is $G/H \times G/K$. Instead, we'll try the other direction.
There is a remark right below the First Isomorphism Theorem which says that if we find a homomorphism $\phi : A \to B$ which is not necessarily onto, then although we can't conclude that $A/\ker(\phi) \cong B$ we can still have that $A / \ker(\phi) \cong \phi(A)$. (In other words, $A/\ker(\phi)$ is isomorphic to the range of $\phi$---if $\phi$ is surjective, then the range is all of $B$, otherwise the range is just some subgroup $\phi(A) \leq B$.) Given that we're looking for a \emph{subgroup} of $G/H \times G/K$ that is isomorphic to something, this seems to be the way to go.
So, the game-plan is to find a homomorphism $\phi : G \to (G/H \times G/K)$ whose kernel is $H \cap K$. The input to $\phi$ is an element $g$, and the output is some pair of cosets $(Hx, Ky)$, for some $x,y \in G$. The most natural map that does this is the \emph{natural homomorphism} on each component of the pair. Thus, define
\[
\phi(g) = (Hg, Kg).
\]
This map is a homomorphism because
\[
\phi(g_1g_2) = (H(g_1g_2), K(g_1g_2)) = (Hg_1Hg_2, Kg_1Kg_2) = (Hg_1,Kg_1)(Hg_2,Kg_2) = \phi(g_1)\phi(g_2).
\]
The kernel of this map is
\begin{align*}
\ker(\phi) &= \{g \in G : \phi(g) = e_{G/H \times G/K}\}\\
&= \{g \in G : \phi(g) = (H, K)\}\\
&= \{g \in G : (Hg, Kg) = (H,K)\}\\
&= \{g \in G : g \in H\text{ and }g \in K\}\\
&= H \cap K.
\end{align*}
We \emph{did not} show that $\phi$ is surjective, and it might not be. So we can only conclude that
\[
G/(H \cap K) \cong \phi(G),
\]
but since $\phi(G)$ is a subgroup of $G/H \times G/K$ (Theorem 12.6(a)), this is enough to prove the theorem. \hfill $\square$
\item Prove that if $G = HK$ then $G/(H \cap K) \cong G/H \times G/K$.
\textbf{Proof:} If we can show that when $G = HK$ the map $\phi$ from part (a) is surjective, then we're done.
Let $(Hx, Ky) \in G/H \times G/K$ be arbitrary. Our goal is to find $g \in G$ such that
\[
\phi(g) = (Hx,Ky),
\]
or equivalently,
\[
(Hg, Kg) = (Hx, Ky).
\]
As $g$ cannot be both $x$ and $y$ at the same time, we have to be more sneaky. We know we have to use the assumption that $G = HK$ somewhere. Since we've picked some element $(Hx, Ky)$, we might as well apply it here to conclude that
\[
x = h_1k_1 \qquad \text{ and } \qquad y = h_2k_2
\]
for some $h_1, h_2 \in H$ and $k_1, k_2 \in K$. This lets us simplify
\[
Hx = H(h_1k_1) = Hk_1
\]
and
\[
Ky = K(h_2k_2) = (Kh_2)(Kk_2) = (Kh_2)(K) = Kh_2.
\]
Hence,
\[
(Hx, Ky) = (Hk_1, Kh_2).
\]
Now, set $g = h_2k_1$ and see that
\begin{align*}
\phi(g) &= \phi(h_2k_1)\\
&= (H(h_2k_1), K(h_2k_1))\\
&= ((Hh_2)(Hk_1), (Kh_2)(Kk_1))\\
&= ((H)(Hk_1), (Kh_2)(K)\\
&= (Hk_1, Kh_2)\\
&= (Hx, Ky).
\end{align*}
The First Isomorphism Theorem now tells us that
\[
G/(H \cap K) \cong G/H \times G/K.
\]
\ \hfill $\square$
\end{enumerate}
\hrulefill
\item (13.19) Let $\varphi : G \to K$ be a homomorphism. Prove that $\phi$ is injective if and only if $\ker(\varphi) = \{e_G\}$.
\textbf{Proof:} To prove an if and only if statement, we need to prove two separate directions.
$(\Longrightarrow)$ First assume that $\phi$ is injective. Let $a \in \ker(\phi)$. We also know that $e_G \in \ker(\phi)$. Hence, $\phi(a) = \phi(e_G) = e_K$, and injectivity proves that $a = e_G$. Since $a$ was an arbitrary element of $\ker(\phi)$, we've shown that all elements in the kernel are just $e_G$.
$(\Longleftarrow)$ Assume that $\ker(\varphi) = \{e_G\}$. To show injectivity, suppose that $a$ and $b$ are elements of $G$ such that $\phi(a) = \phi(b)$. Then,
\begin{align*}
e_K &= \phi(a)(\phi(b))^{-1}\\
&= \phi(a)\phi(b^{-1})\\
&= \phi(ab^{-1}).
\end{align*}
Since $\phi(ab^{-1}) = e_K$ we know $ab^{-1} \in \ker(\phi)$. The only element in $\ker(\phi)$ is $e_G$! So,
\[
ab^{-1} = e_G,
\]
implying that $a = b$. This proves injectivity. \hfill $\square$
\hrulefill
\item (13.22) Let $\varphi : G \to K$ be a surjective homomorphism and assume that $K$ is abelian. Show that every subgroup of $G$ containing $\ker(\varphi)$ is normal.
\textbf{Proof, version 1:} Let $H$ be a subgroup of $G$ that contains the kernel. By a fact from class, since $\phi$ is a homomorphism and since $H$ contains the kernel, we have that $H = \phi^{-1}(\phi(H))$. Since $\phi(H) \leq K$ and since $K$ is abelian, we have $\phi(H) \norm K$. By Theorem 12.6, it follows that $\phi^{-1}(\phi(H)) \norm G$, and thus $H \norm G$. \hfill $\square$
\textbf{Proof, version 2:} The first proof is quick and efficient, but not at all enlightening. It doesn't tell us anything about \emph{why} it's true. Let's prove the statement again in a longer, but more elucidatory, manner.
Let $H$ be a subgroup of $G$ that contains $\ker(\phi)$ and let $h \in H$. Let $g \in G$ be arbitrary. If $H$ is to be normal, then we must have $ghg^{-1} \in H$. Let's imagine what it would mean for this to go wrong. That is, suppose $ghg^{-1} \not\in H$. How could this happen?
We have two elements in $G$ ($h$ and $ghg^{-1}$). What does $\phi$ do to them? Notice that because $K$ is abelian and $\phi$ is a homomorphism,
\[
\phi(ghg^{-1}) = \phi(g)\phi(h)\phi(g)^{-1} = \phi(h).
\]
Thus we have two elements in $G$, not both in $H$, but both map to the same element of $K$.
Let's forget the context of the problem for a moment and explore that. What does it mean to have two elements $a,b \in G$ which map to the same element $\phi(a) = \phi(b)$ in $K$? This implies that $\phi(ab^{-1}) = e_K$, i.e., that $ab^{-1}$ is in the kernel of $\phi$.
For us, with $a = ghg^{-1}$ and $b = h$, this lets us conclude that $ghg^{-1}h^{-1} \in \ker(\phi) \subseteq H$. It follows from this that $ghg^{-1} \in H$, proving that $H \norm G$. \hfill $\square$
\hrulefill
\item (14.4) Let $n$ be a positive integer. Show that every abelian group of order $n$ is cyclic if and only if $n$ is not divisible by the square of any prime.
\textbf{Proof:}
$(\Longrightarrow)$ We prove this direction by contrapositive. Assume that $n$ is divisible by the square of some prime $p$, so that we can write
\[
n = p^2q.
\]
where $p$ is a prime and $q$ is a positive integer (possibly $q=1$). One group of order $n$ is $\Z_p \times \Z_{pq}$ which is not cyclic by Theorem 6.1
$(\Longleftarrow)$ Again the contrapositive seems easier (to me, at least). Suppose that $n$ is a number such that \emph{not every abelian group is cyclic}. Let $G$ be an abelian group of order $n$ that is not cyclic. By the Fundamental Theorem of Finite Abelian Groups (Theorem 14.2), $G$ is isomorphic to the direct product of finitely many nontrivial finite cyclic groups of prime-power order. Since every finite cyclic group is isomorphic to $\Z_m$ for some $m$, we can write
\[
G \cong \Z_{{p_1}^{k_1}}\times \Z_{{p_2}^{k_2}} \times \cdots \times \Z_{{p_\ell}^{k_\ell}}
\]
where the $p_i$ are primes (not necessarily distinct), and the $k_i$ are positive integers. Note that this implies
\[
n = {p_1}^{k_1}{p_2}^{k_2}\cdots{p_\ell}^{k_\ell}.
\]
Since we seek to show that $n$ is divisible by the square of some prime, we only need to show that $k_i \geq 2$ for some $i$, or that $p_i = p_j$ for some non-equal $i$ and $j$.
As $G$ is not cyclic, Theorem 6.1 implies that there is some pair $r,s$ such that $|\Z_{{p_r}^{k_r}}|$ and $|\Z_{{p_s}^{k_s}}|$ are \emph{not} relatively prime. This implies that ${p_r}^{k_r}$ and ${p_s}^{k_s}$ share some non-trivial factor. Because $p_r$ and $p_s$ are prime, this is only possible if $p_r = p_s$.
This implies that $n$ is divisible by ${p_r}^2$, completing the proof. \hfill $\square$
\hrulefill
\end{enumerate}
\end{document}