Proof that conjugacy classes of the symmetric group correspond to cycle types

Proof

The key is the formula for conjugating a cycle: conjugation by $\pi$ applies $\pi$ to each entry.

1. Let $\sigma, \tau \in S_n$, the symmetric group on $X = \{1, \dots, n\}$. By the definition of conjugate elements, they are conjugate when $\tau = \pi \sigma \pi^{-1}$ for some $\pi \in S_n$.
2. Let $c = (a_1\ \dots\ a_k)$ be a cycle with $k \ge 1$, and let $\pi \in S_n$. We claim $\pi c \pi^{-1} = (\pi(a_1)\ \dots\ \pi(a_k))$. The points $\pi(a_p)$ are distinct, since $\pi$ is injective.
3. Let $y = \pi(a_p)$. Then $\pi c \pi^{-1}(y) = \pi(c(a_p))$, which is $\pi(a_{p+1})$ for $p < k$ and $\pi(a_1)$ for $p = k$.
4. Let $y$ not be of the form $\pi(a_p)$. Then $\pi^{-1}(y)$ is not one of the $a_p$, so $c$ fixes it, and $\pi c \pi^{-1}(y) = y$. With step 3, this proves the claim of step 2.
5. Let $\rho \in S_n$, with disjoint cycle decomposition $\rho = c_1 \cdots c_r$. Let $M_i$ be the set of moved points of $c_i$.
6. For $z \in M_i$, $c_i(z) \in M_i$, because $c_i(c_i(z)) = c_i(z)$ would force $c_i(z) = z$ by injectivity. The other factors fix $M_i$ pointwise. So $\rho(z) = c_i(z) \ne z$.
7. A point outside all $M_i$ is fixed by each factor, hence by $\rho$. So the fixed points of $\rho$ are exactly the points outside all $M_i$.
8. Add a $1$-cycle $(a)$ for each fixed point $a$; it is the identity, so the product is still $\rho$. By step 7, the point sets of all these cycles partition $X$.
9. By the definition of the cycle type, the cycle type of $\rho$ is the multiset of the lengths of the cycles in step 8. We call such a product a full cycle form of $\rho$.
10. Assume $\tau = \pi \sigma \pi^{-1}$. Let $\sigma = c_1 \cdots c_s$ be a full cycle form, where $c_i$ has point set $P_i$.
11. Inserting $\pi^{-1} \pi$ between the factors gives $\tau = (\pi c_1 \pi^{-1})(\pi c_2 \pi^{-1}) \cdots (\pi c_s \pi^{-1})$.
12. By step 2, $\pi c_i \pi^{-1}$ is a cycle with point set $\pi(P_i)$ and the same length as $c_i$. Since $\pi$ is a bijection, the sets $\pi(P_i)$ partition $X$.
13. The factors in step 11 of length at least $2$ have pairwise disjoint sets of moved points. By uniqueness in the disjoint cycle decomposition, they are the cycles of $\tau$ of length at least $2$.
14. By step 7 for $\tau$, the remaining points are the fixed points of $\tau$, and they are the sets $\pi(P_i)$ of size $1$. So step 11 is a full cycle form of $\tau$.
15. By steps 12 and 14, $\tau$ has the same cycle type as $\sigma$.
16. Conversely, assume $\sigma$ and $\tau$ have the same cycle type. Take full cycle forms $\sigma = c_1 \cdots c_s$ and $\tau = d_1 \cdots d_s$, numbered so that $c_i$ and $d_i$ have the same length $k_i$.
17. Write $c_i = (a_{i,1}\ \dots\ a_{i,k_i})$ and $d_i = (b_{i,1}\ \dots\ b_{i,k_i})$. By step 8, each point of $X$ is exactly one $a_{i,j}$, and exactly one $b_{i,j}$.
18. So $\pi(a_{i,j}) = b_{i,j}$ defines a map $\pi \colon X \to X$. The rule $b_{i,j} \mapsto a_{i,j}$ is a two-sided inverse, so $\pi$ is bijective and $\pi \in S_n$.
19. By step 2, $\pi c_i \pi^{-1} = d_i$ for each $i$. As in step 11, $\pi \sigma \pi^{-1} = d_1 \cdots d_s = \tau$. So $\sigma$ and $\tau$ are conjugate.