Math 360, Fall 2021, Assignment 9

The moving power of mathematical invention is not reasoning but the imagination.

- Augustus de Morgan

Read:

1. Section 8.

Carefully define the following terms, then give one example and one non-example of each:

1. Permutation (of a set $S$).
2. $\mathrm{Sym}(S)$ (the symmetric group on $S$).
3. $S_n$ (the symmetric group on $n$ letters).
4. Order (of a group; see the text for this definition).
5. $D_n$ (the $n$th dihedral group; see the text).

Carefully state the following theorems (you do not need to prove them):

1. Containment criterion for subgroups of $\mathbb{Z}_n$.
2. Theorem relating $\left\langle[a]\right\rangle$ to $\left\langle[\mathrm{gcd}(a,n)]\right\rangle$ (in $\mathbb{Z}_n$).
3. Classification of subgroups of $\mathbb{Z}_n$ ("Every subgroup of $\mathbb{Z}_n$ is generated by a unique...").
4. Theorem concerning the order of $S_n$.

Solve the following problems:

1. Section 6, problems 23, 25, and 27.
2. Section 8, problems 1, 3, 5, 7, 9, 11, 13, 17, 30, 31, and 33.
3. In class, we listed all permutations of the set $\{1,2,3\}$. Now, make a list of all permutations of the set $\{a,b,c\}$. Do you see any relationship between the two lists?
4. Suppose $S$ and $T$ are sets, and that $f:S\rightarrow T$ is a bijection. Define a function $\phi:\mathrm{Sym}(S)\rightarrow\mathrm{Sym}(T)$ by the formula $\phi(\pi)=f\circ\pi\circ f^{-1}$. Show that $\phi(\pi\circ\sigma)=\phi(\pi)\circ\phi(\sigma)$.
5. With notation as above, take $S=\{1,2,3\}$ and $T=\{a,b,c\}$, and let $f:S\rightarrow T$ be given by $f(1)=a, f(2)=b, f(3)=c$. For any specific $\pi\in\mathrm{Sym}(S)$ (e.g. for $\pi=\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}$), compute the permutation $\phi(\pi)\in\mathrm{Sym}(T)$. Do this in several more specific cases.
6. Returning to the general case, define a new function $\psi:\mathrm{Sym}(T)\rightarrow\mathrm{Sym}(S)$ by the formula $\psi(\tau)=f^{-1}\circ\tau\circ f$. Show that $\phi\circ\psi$ and $\psi\circ\phi$ are both the identity maps, so that $\psi$ is the inverse of $\phi$. (Note in particular that this shows that $\phi$ is an invertible function and hence is a bijection.)
7. Prove that $\phi$ is an isomorphism from $(\mathrm{Sym}(S),\circ)$ to $(\mathrm{Sym}(T),\circ)$.
8. Finally, show that whenever $S$ and $T$ are equinumerous sets, $\mathrm{Sym}(S)$ and $\mathrm{Sym}(T)$ are isomorphic groups.

--------------------End of assignment--------------------

Definitions:

1. Permutation (of a set $S$): Let $S$ be a set. A permutation of $S$ is a bijection from $S$ to itself.
2. $\mathrm{Sym}(S)$ (the symmetric group on $S$): $U(Fun(S, S), \circ) = (Sim(S), \circ)$. That is, $Sym(S)$ means the permutation of $S$, regarded as a group under function composition. It's called the symmetric group on $S$.
3. $S_n$ (the symmetric group on $n$ letters): $Sym(\{1,2,3 \cdots ,n\}) = S_n$.
4. Order (of a group; see the text for this definition): the number of elements present in that group $|S|$.
5. $D_n$ (the $n$th dihedral group; see the text): the group of symmetries of the regular n-gon.

Theorem:

1. Containment criterion for subgroups of $\mathbb{Z}_n$: In $\mathbb Z_n, \left\langle [a] \right\rangle \subseteq \left\langle [b] \right\rangle \iff gcd(b,n) | a.$
2. Theorem relating $\left\langle[a]\right\rangle$ to $\left\langle[\mathrm{gcd}(a,n)]\right\rangle$ (in $\mathbb{Z}_n$): In $\mathbb Z_n, \left\langle [a] \right\rangle = \left\langle [gcd(a,n)] \right\rangle$.
3. Classification of subgroups of $\mathbb{Z}_n$ ("Every subgroup of $\mathbb{Z}_n$ is generated by a unique..."): Each subgroup has a unique generator (between $1$ and $n$) which divides $n$.
4. Theorem concerning the order of $S_n$: $|S_n| = n!$.

Book Problems:

23. 0 1 2 3 4 6 9 12 18

25. 4

27. 6

1. (1 2 3 6 5 4)

3. (3 4 1 6 2 5)

5. (2 6 1 5 4 3)

7. 2

9. (1 2 3 4 5 6)

11. {1,2,3,4,5,6}.

13. {1,5}.

17. 4*1*3*2 = 24.

30. yes

31. no

33.no.

Other Problems:

1. (a b c) (a c b) (b a c) (b c a) (c b a) (c a b)
2. $\phi(\pi)=f\circ\pi\circ f^{-1}$, $\phi(\pi \circ \sigma)=f\circ \pi \circ \sigma \circ f^{-1}$, $\phi(\pi) \circ \phi(\sigma)= f\circ \pi \circ f^{-1} \circ f \circ \sigma \circ f^{-1}$, $= f\circ \pi \circ (f^{-1} \circ f) \circ \sigma \circ f^{-1}$, $ = f\circ \pi \circ \sigma \circ f^{-1} = \phi(\pi \circ \sigma)$.
3. $\begin{pmatrix}1&2&3\\a&b&c\end{pmatrix} \circ \begin{pmatrix}1&2&3\\3&2&1\end{pmatrix} = \begin{pmatrix}1&2&3\\c&b&a\end{pmatrix}$, $\begin{pmatrix}1&2&3\\c&b&a\end{pmatrix} \circ \begin{pmatrix}1&2&3\\a&b&c\end{pmatrix}^{-1}$ $= \begin{pmatrix}1&2&3\\c&b&a\end{pmatrix} \circ \begin{pmatrix}a&b&c\\1&2&3\end{pmatrix} = \begin{pmatrix}a&b&c\\c&b&a\end{pmatrix} \in Sym(T)$
4. Similar as second problem
5. Injection and Surjection and Operation