- For each part below, provide a group $G$ and a proper, non-trivial subgroup $H$ of $G$ according to the different criteria. Provide a different group $G$ in each case.

(i) $G$ is infinite and $H$ is infinite and cyclic;

(ii) $G$ is infinite and $H$ is finite and cyclic;

(iii) $G$ is infinite and non-Abelian and $H$ is Abelian;

(iv) $G$ is infinite and Abelian and $H$ is infinite and not cyclic;

(v) $G$ is infinite and non-Abelian and $H$ is infinite and cyclic.

*Solution.*

(i) $G=\Bbb Z,H=2\Bbb Z$

(ii) $G=\mathrm{Dih}_∞,H=C_2$

(iii) $G=\mathrm{Dih}_∞,H=C_2$

(iv) $G=\Bbb R^+,H=\Bbb Q^+$

(v) $G=\mathrm{Dih}_∞,H=\Bbb Z$ - Let $G$ be a group and $H, K$ subgroups of $G$. Let $HK=\{hk:h∈H,k∈K\}$.

(i) Show that $H∩K$ is a subgroup of $G$.

(ii) Give an example where $H∪K$ is not a subgroup of $G$. Justify your answer.

(iii) Give an example where $HK$ is not a subgroup of $G$. Justify your answer.

(iv) Show that if $G$ is Abelian then $HK$ is a subgroup of $G$.

*Solution.*

(i)$e∈H,e∈K⇒e∈H∩K$. If $g_1,g_2∈H∩K$, then $g_1g_2∈H,g_1g_2∈K$, so $g_1g_2∈H∩K$. If $g∈H∩K$, then $g^{-1}∈H,g^{-1}∈K$, so $g^{-1}∈H∩K$.

(ii)$G=\Bbb Z,H=2\Bbb Z,K=3\Bbb Z$. $H∪K$ is not a subgroup of $G$: $2∈H,3∈K$ but $2\nmid5,3\nmid5$, so $5\notin H∪K$.

(iii)Take 2 groups generated by a transposition in $S_3$, say $H=\langle(12)\rangle$ and $K=\langle(23)\rangle$ in $S_3$. Then $|HK|=4\nmid |S_3|=6$ and thus is not a subgroup, by Lagrange's theorem.

(iv)$e∈H,e∈K⇒e∈HK$. If $h_1,h_2∈H,k_1,k_2∈K$, then $(h_1k_1)(h_2k_2)=(h_1h_2)(k_1k_2)∈HK$. If $h∈H,k∈K$, then $(hk)^{-1}=k^{-1}h^{-1}=h^{-1}k^{-1}∈HK$. - Which of the following groups are cyclic? Either find a generator or show that no generator exists.

For the cyclic groups, determine how many different generators there are.

$\mathbb{Z}^2;\quad C_2×C_4;\quad C_3×C_4;\quad⟨(12)(34)(56),(145)(236)⟩\leqslant S_6;\quad⟨(123),(456)⟩\leqslant S_6.$

*Solution.*

For all $a,b∈\Bbb Z$ it holds that $⟨(a,b)⟩=\{(ka,kb)∣k∈\Bbb Z\}≠\Bbb Z^2$. So $\Bbb Z^2$ is not generated by a single generator and hence not cyclic.

$C_2×C_4$ is not cyclic. Elements of $C_2×C_4$ have order ≤4 but a generator should be of order 8.

$C_3×C_4$ is cyclic. If $C_3=⟨g⟩,C_4=⟨h⟩$, then $C_3×C_4=⟨(g,h)⟩$. $C_3$ has 2 generators, $C_4$ has 2 generators, so $C_3×C_4$ has 4 generators.

Let $G=⟨(12)(34)(56)⟩$ and $H=⟨(145)(236)⟩$, then $∀g∈G,h∈H:gh=hg$ and $G≌C_2,H≌C_3$, therefore $⟨(12)(34)(56),(145)(236)⟩≌C_6$, which has φ(6)=2 generators.

(123),(456) are disjoint 3-cycles so have order 3, so an element of $⟨(123),(456)⟩$ has order 1 or 3, but $⟨(123),(456)⟩$ has order 9, so is not cyclic. - (i) By considering partitions, calculate the number of equivalence relations on a set with four elements.

(ii) Let $q_0=1$ and, for $n \geqslant 1$, let $q_{n}$ denote the number of equivalence relations of a set $X$ with $n$ elements. By considering the possible equivalence classes of the $(n+1)$ th element, show that$$q_{n+1}=\sum_{k=0}^{n}\left(\begin{array}{l}n \\k\end{array}\right) q_{n-k} .$$Use this recurrence relation to verify your answer for $q_4$ from part (i).

*Solution.*

(i)4 elements can be partitioned into 1,2,3,4 sets: 4=3+1=2+2=2+1+1=1+1+1+1. So the number of equivalence relations is 1+4+3+6+1=15.

(ii)The equivalence class containing the first element has $k$ elements apart from the first element, for some number $k$ that may range from $0$ to $n$. There are $\tbinom {n}{k}$ choices for the elements in this equivalence class apart from the first element, and $n-k$ elements are left, so there are $q_{n-k}$ choices of how to partition the remaining elements.

Starting with $q_0=q_1=1$, we get $q_2=2,q_3=5,q_4=15$. - Let $G$ be a finite group. We define a relation $\sim$ on $G \backslash\{e\}=\{g \in G: g \neq e\}$ by $g \sim h$ if and only there exists $k$ such that $g=h^k$.

(i) Show that $\sim$ is reflexive and transitive.

(ii) Show that $\sim$ is symmetric if and only if the order of $g$ is prime for every $g \neq e$.

*Proof.*

(i)$g=g^1$, so $g\sim g$, so $\sim$ is reflexive. If $g\sim h,h\sim i$, then $g=h^k,h=i^l$⇒$g=i^{kl}$, so $g\sim i$, so $\sim$ is transitive.

(ii)If the order of $g$ is not prime for some $g \neq e$, let $\operatorname{ord}g=pq,h=g^p$, where $p,q>1$ are integers, clearly $h≠e$, then $h\sim g$. Suppose that $g=h^k$, then $g=g^{pk}⇒pq|pk-1⇒p|pk-1,$ a contradiction, therefore $g\not\sim h$, therefore $\sim$ is not symmetric.

Conversely, if every element other than $e$ has prime order and $g\sim h$, then $g=h^k$ for some $k$, let the order of $h$ be a prime $p$, clearly $p\nmid k$, let $k'$ be the multiplicative inverse modulo $p$, then $h=h^{kk'}=g^{k'}$, so $\sim$ is symmetric.

*Extension:*If $\sim$ is symmetric, then $⟨g⟩∩⟨h⟩=\begin{cases}⟨g⟩&\text{if }g\sim h\\\{e\}&\text{if }g\not\sim h\end{cases}$ - Let $G$ be a finite group and $H,K$ subgroups of $G$. The map $ϕ:H×K→HK$ is defined by $(h, k)→hk$.

(i) Show that $\left|\phi^{-1}(g)\right|=|H∩K|$ for any $g∈HK$. Deduce that$$|H K|=\frac{|H||K|}{|H \cap K|} .$$(ii) Show that if $G$ is Abelian and $H \cap K=\{e\}$ then $HK$ is isomorphic to $H \times K$.

*Proof.*

(i)Claim:$H\cap K$ acts freely and transitively on $\phi^{-1}(g)$. [This implies $|\phi^{-1}(g)|=|H∩K|$]

Proof of Claim:

Action: $l\in H\cap K,(h,k)\in\phi^{-1}(g)$, then $l\cdot(h,k)=(hl^{-1},lk)$ is a homomorphism.

Free: If $(hl^{-1},lk)=(h,k)$, then $lk=k$, $l=e$.

Transitive: For $(h,k),(\tilde h,\tilde k)\in\phi^{-1}g,\exists l\in H\cap K$,s.t.$l\cdot(h,k)=(\tilde h,\tilde k)$.

If $hk=\tilde h\tilde k$, take $l=\tilde h^{-1}h=\tilde kk^{-1}\in H\cap K$, this $l$ works.

*Recall*: Let $L$ be linear map from vector space $V$ to $W$, then $L^{-1}(w)=\begin{cases}\emptyset\\v+\operatorname{ker}L\text{ for some }v\end{cases}$

(ii)\begin{aligned}\phi\big((x,y)(x',y')\big)&=\phi(xx',yy')\\&=xx'yy'\\&=xyx'y',\quad\text{because $G$ is Abelian}\\&=\phi(x,y)\phi(x',y').\end{aligned}So $\phi$ is a homomorphism. If $H \cap K=\{e\}$, by (i), $\phi$ is injective. Obviously, $\phi$ is surjective. Hence $ϕ$ is an isomorphism from $H\times K$ to $HK$.

**S1.**In the dihedral group $D_8$ (with the same notation as in lectures), what is the subgroup generated by $rs$? What is the subgroup $⟨rs, s⟩$?

*Solution.*

We have $⟨rs⟩ = \{(rs)^k: k ∈\mathbb Z\}$. But $(rs)^2 = e$, so we find that $⟨rs⟩ = \{e, rs\}≤ D_8$.

Now $⟨rs, s⟩$ is the smallest subgroup containing $rs$ and $s$, so it contains all products involving $rs$ and $s$. In particular, it contains their product $rss = r$. So $⟨rs, s⟩$ contains both $r$ and $s$. But these generate all elements of the group, so $⟨rs, s⟩=D_8$.

**S2.**In this question we work in the group $\mathbb Z$. Find all integers $m$ such that $\langle m\rangle=\langle 3,4,6\rangle$ and find all integers $n$ such that $\langle n\rangle=\langle 3\rangle \cap\langle 4\rangle \cap\langle 6\rangle$.

*Solution.*

Let $m$ be an integer such that $⟨m⟩ = ⟨3, 4, 6⟩$. Then $1 = 4 − 3 ∈ ⟨m⟩$, and since 1 generates $\mathbb Z$ this means that $⟨m⟩=\mathbb Z$. We see that the only possibilities for $m$ are 1 and −1.

Let $n$ be an integer such that $\langle n\rangle=\langle 3\rangle \cap\langle 4\rangle \cap\langle 6\rangle$. Now ⟨6⟩ ⊆ ⟨3⟩ (every multiple of 6 is a multiple of 3), so $⟨n⟩ = ⟨4⟩ ∩ ⟨6⟩ = ⟨12⟩$. We see that $n = 12$ or $n = −12$.

**S3.**Let $G$ be a group. Define a relation $\sim$ on $G$ via $x \sim y$ if and only if $x=y$ or $x=y^{-1} .$

Show that $\sim$ is an equivalence relation. What are the equivalence classes?

*Proof.*

- reflexive: for $x \in G$ we have $x=x$ and so $x \sim x$.
- symmetric: if $x \sim y$ then $x=y$ or $x=y^{-1}$, so $y=x$ or $y=x^{-1}$, so $y \sim x$
- transitive: if $x \sim y$ and $y \sim z$, then we have four cases to check. If $x=y$ and $y=z$, then $x=z$ so $x \sim z$. If $x=y$ and $y=z^{-1}$, then $x=z^{-1}$ so $x \sim z .$ If $x=y^{-1}$ and $y=z$, then $x=z^{-1}$ so $x \sim z .$ Finally, if $x=y^{-1}$ and $y=z^{-1}$ then $x=z$ so $x \sim z .$

**P1.**Let $G$ be a group with at least 2 elements. Suppose that $G$ has no proper non-trivial subgroups. Take $x \in G \backslash\{e\} .$ Is $x$ a generator for $G$? Is $x^{2}$ a generator for $G ?$ What can you say about the order of $x$?

*Solution.*

Let's consider $H=\langle x\rangle$. This is a subgroup of $G$. But $G$ has no proper non-trivial subgroups, and $x \neq e$ so $H \neq\{e\}$, so $H=G$. That is, $G=\langle x\rangle$, so $x$ generates $G$.

If $x^{2} \neq e$, then exactly the same argument (applied to $x^{2}$ in place of $x$ ) shows that $x^{2}$ generates $G .$ If $x^{2}=e$, then $\left\langle x^{2}\right\rangle=\{e\} \subsetneq G .$ But also we know that $x$ generates $G$, so then $G=\{e, x\} .$

I claim that if $x$ has finite order then the order of $x$ is a prime.

Let $d$ be the order of $x$, so also $|G|=d$ (as $x$ generates $G$ ). If $d=a b$ with $b>1$, then consider $\left\langle x^{a}\right\rangle$. Since $a<d$ we know that $x^{a} \neq e$, so $\left\langle x^{a}\right\rangle$ is a non-trivial subgroup of $G$ so must be $G .$ But $x^{a}$ has order $b$, so we need $b=d$ and hence $a=1$. So $d$ is prime.

If $x$ does not have finite order, then $G$ is infinite and cyclic, so is isomorphic to $\mathbb{Z}$. But $\mathbb{Z}$ does have proper non-trivial subgroups. So this case does not arise.

**P2.**

(i) Is there a non-cyclic group all of whose proper subgroups are cyclic?

(ii) Is there a non-Abelian group all of whose proper subgroups are Abelian?

*Solution.*

(i) Consider the smallest non-cyclic group $C_2×C_2$.

(ii) Consider the smallest non-Abelian group $S_3$.

**P3.**Let $m, n \in \mathbb{Z}$. What can you say about $\operatorname{hcf}(m, n) \times \operatorname{lcm}(m, n)$ (the product of their highest common factor and least common multiple)?

*Solution.*

Perhaps inspired by some experimentation with numbers, we might conjecture that $\operatorname{hcf}(m, n) \times$ $\operatorname{lcm}(m, n)=m n$. There are many ways to prove this. Here is one strategy, using properties from Proposition 22 in the notes.

Let $h=\operatorname{hcf}(m, n)$ and $l=\operatorname{lcm}(m, n)$. So we are trying to prove that $h l=m n$.

Let $k=\frac{m n}{h}$, so we want to prove that $k=l$.

First we show that $k$ is a common multiple of $m$ and $n$. Indeed, since $h \mid m$ we see that $k$ is an integer, and moreover $n \mid k$. Similarly, since $h \mid n$ we see that $m \mid k$. So $k$ is a common multiple of $m$ and $n$, so $l \mid k$.

Now take an arbitrary common multiple of $m$ and $n$, say $c$, so $m \mid c$ and $n \mid c$. We want to show that $k \mid c$. Since $h=\operatorname{hcf}(m, n)$, we know that there are integers $a, b$ such that $h=a m+b n$. Then$$\frac{c}{k}=\frac{c h}{m n}=\frac{c(a m+b n)}{m n}=\frac{a c}{n}+\frac{b c}{m},$$and since $m | c$ and $n | c$, this is an integer. That is, $k | c$.

So $k = l$, so indeed $hk = mn$.