I am aware that there are a couple of well-known proofs of this theorem, but I'm specifically grappling with the proof given in Fraleigh's A First Course in Abstract Algebra (Theorem 9.15 in the textbook).
Let $s$ be a permutation in the symmetric group of degree $n$, and let $t$ be a transposition $(i,j)$ in the same group. If $n$ is $1$ or infinite, we are done. Otherwise, ....[details of the proof omitted.] (We use the right-to-left convention to multiply permutations.)
Okay, we have shown that the number of orbits of $s$ and $ts$ differ by 1. This part, I understand. But I don't understand how to infer the theorem from here. I would be very grateful if someone can help me clear my blind spot. Thank you so much!
Added by Dylan. Here is Fraleigh's explanation (please don't sue me):
We have shown that the number of orbits of $\tau \sigma$ differs from the number of orbits of $\sigma$ by $1$. The identity permutation $\iota$ has $n$ orbits, because each element is the only member of its orbit. Now the number of orbits of a given permutation $\sigma \in S_n$ differs from $n$ by either an even or odd number, but not both. Thus it is impossible to write $$ \sigma = \tau_1 \tau_2 \cdots \tau_m \iota $$ where the $\tau_k$ are transpositions, in two ways, once with $m$ even and once with $m$ odd. $\qquad \diamond$