Symmetric group on a finite set is 2-generated

Statement

The Symmetric group (?) on a finite set is a 2-generated group (?): it can be generated by two elements.

Note that when the finite set has 3 or more elements (so the degree is 3 or more), the symmetric group is not cyclic, so we obtain that the Minimum size of generating set (?) is precisely 2.

Related facts

Stronger facts

• Dixon's Theorem

Also refer presentation theory of symmetric groups to learn about good choices of presentation for symmetric groups.

Facts used

1. Transpositions of adjacent elements generate the symmetric group on a finite set

Proof

A transposition and a cycle

Consider the set $\{1,2,3,\dots ,n\}$. We show that the symmetric group on this set is generated by the permutations:

$(1,2)$ and $(1,2,3,\dots ,n)$.

Proof: Observe that, for $0\le i<n-1$:

$(1,2,3,\dots ,n{)}^i(1,2)(1,2,3,\dots ,n{)}^{-i}=(i+1,i+2)$

Thus, all transpositions of adjacent elements are in the subgroup generated by these two permutations. Using fact (1), we see that these two permutations generate the whole group.