The hint hat was given for this problem is 'HINT: Find a pair of 2-cycles that do not commute'
So, starting off I interpret this question to mean prove this by induction (given that it's a statement of proof about a proposition indexed by the natural numbers) so I will start with a base case.
Base Case: $n = 3$
The group $S_3$ has the elements $(), (1 2), (1 3), (2 3), (1 2 3), (1 3 2)$ so looking at the pair of transpositions $(1 2)$ and $(2 3)$ we see that: $(1 2)(2 3) = (1 2 3) \neq (1 3 2) = (2 3)(1 2)$
Inductive Hypothesis:
Assume that multiplication in $S_r$ is noncommutative $\forall r \in \mathbb{N}$ such that $4 \leq r \leq k$ for some $k \geq 3$
Inductive Step:
We want to show that multiplication is noncommutative in $S_{k+1}$. Note that any $k$-Cycle can be written as a product of $(k-1)$ $2$-cycles. So we can say that any $(k+1)$-cycle (i.e., any element of $S_{k+1}$) can be written as a product of $(k)$ $2$-cycles, but as we've shown transpositions are not commutative in general. Thus multiplication in $S_{k+1}$ is noncommutative.
I just want to make sure that
- I was correct in that we could use a proof by induction to prove this statement
- My setup for each step of the proof was right
- The logic in the inductive step was right – I'm not sure if by showing that 2 transpositions in $S_3$ are noncommutative would be sufficient for saying that any transpositions in $S_{k+1}$ would also be noncommutative.
Thanks for any help!
Best Answer
What you have is fine but you do not need induction.
Since $(12)(23)\neq(23)(12)$, it suffices to embed these elements into $S_n$ for $n\ge 4$ by, in essence, noticing that you can multiplying each of $(12),(23)$ by $(i)$ for $i\in\{1,\dots, n\}$; more concretely: define $\varphi: S_3\to S_n$ by
$$\varphi_\sigma(i) =\begin{cases} \sigma(i) &: i\in\{1,2,3\}\\ i &: i\in\{4,\dots, n\} \end{cases}$$
for each $\sigma\in S_3$. It is routine to check that $\varphi$ is an injective homomorphism.