1. Volgens Inverteerbaarheid bij gelijke dimensies voor domein en codomein is een afbeelding $f: \{1,\ldots,n\}\to\{1,\ldots,n\}$ dan en slechts dan bijectief als ze surjectief is, in welk geval de lijst $$\rv{f(1),f(2),\ldots,f(n)}$$ bestaat uit $n$ verschillende getallen in $\{1,\ldots,n\}$. Dit is dan en slechts dan het geval als $f$ een permutatie is.

2. We gebruiken de notatie $n!=1\cdot 2\cdots (n-1)\cdot n$ en laten met volledige inductie naar $n$ zien dat $n!$ het aantal manieren is om een lijst van lengte $n$ te vullen met elementen uit $\{1,2,\ldots,n\}$, waarbij elk element precies één keer gebruikt wordt. Dit volstaat voor het bewijs.

Voor $n=1$ is $1!=1$ inderdaad het aantal manieren om een lijst van lengte $1$ te vullen met $1$.

Voor de inductie stap in ons bewijs met volledige inductie naar $n$ veronderstellen we nu $n\gt 1$. Er zijn $n$ mogelijkheden om een getal $k\in \{1,\ldots,n\}$ op de eerste plaats te zetten. Als we dat gedaan hebben voor een bepaalde $k$, dan kunnen we de lijst ter lengte $n-1$ van de overige plaatsen vullen door elk van de $n-1$ getallen $1,\ldots,k-1,k+1,\ldots,n$ op één plaats te zetten. Dit aantal is, vanwege de inductiehypothese, $(n-1)!$ (het doet er immers niet toe hoe de $n-1$ getallen heten, als ze onderling maar verschillen). We concluderen dat $$n! = n\cdot (n-1)! = n\cdot (n-1)\cdot (n-2) \cdots 2 \cdot 1$$ het aantal manieren is om een lijst van lengte $n$ te vullen met elementen uit $\{1,2,\ldots,n\}$, waarbij elk element precies één keer gebruikt wordt.

3. Laat $\sigma$ een permutatie zijn. Als $\sigma$ de identiteit is, dat wil zeggen: $\sigma =\rv{1,2,\ldots,n}$, dan is $\sigma$ het product van $0$ transposities.

Zo niet, dan zijn er getallen die bewogen worden door $\sigma$. Laat $v$ het aantal getallen in $\{1,\ldots,n\}$ zijn dat bewogen wordt door $\sigma$. We bewijzen de uitspraak met inductie naar $v$. Als $v=0$, dan moet $\sigma$ de identiteit zijn, en die hebben we al behandeld. Stel nu $v\gt0$. Dan is er een $\ell \in \{1,\ldots,n\}$ met $\sigma(\ell)\ne \ell$. Schrijf $m=\sigma(\ell)$. Dan geldt ook $\sigma(m)\ne m$, want anders zou $\sigma(m)=m=\sigma(\ell)$ en $m\ne\ell$ gelden, wat tegenspreekt dat $\sigma$ injectief is. Dus zowel $\ell$ als $m$ dragen bij aan de $v$ bewogen getallen door $\sigma$. Bekijk nu het product $$\tau=\sigma\,(\ell,m)$$ van $\sigma$ met de transpositie $(\ell,m)$. Als $k\in\{1,\ldots,n\}$ ongelijk is aan $\ell$ en $m$, dan geldt $\tau(k)=\sigma(k)$, zodat de $v-2$ bewogen getallen van $\sigma$ ongelijk aan $\ell$ en $m$ ook de bewogen getallen van $\tau$ ongelijk aan $\ell$ en $m$ zijn. Bovendien geldt $$\tau[m]=\sigma\,(\ell,m)[m]=\sigma[\ell]=m$$ zodat $m$ een vast punt van $\tau$ is. Dus $\tau$ beweegt minder getallen dan $\sigma$. Volgens de inductiehypothese is $\tau$ dus een product van transposities. Daaruit volgt dat $\sigma=\tau \,(\ell,m)$ ook een product van transposities is.

4. Stel dat de permutatie $g$ kan worden geschreven als het product van transposities $\mu_1\cdots\mu_p$ met $p$ even, en stel dat $g$ ook kan worden geschreven als het product van transposities $\nu_1\cdots\nu_q$ met $q$ oneven. Dan kan de identiteit $e$ worden geschreven als $$e=gg^{-1}=\mu_1\cdots\mu_p\left(\nu_1\cdots \nu_q\right)^{-1}=\mu_1\cdots\mu_p\nu_q\cdots \nu_1$$ waarin het aantal transposities in het laatste product oneven is. We laten zien dat dit onmogelijk is.

Stel dat we de identiteit kunnen schrijven als het product van $m\geq 2$ transposities: $$e=\tau_1\cdots \tau_m$$ waarin $m$ zowel even als oneven mag zijn. We laten zien dat er een algoritme bestaat om dit product te vereenvoudigen tot een product van $m-2$ transposities. Als $m$ even is, dan kunnen we het product door herhaaldelijke toepassing van het algoritme vereenvoudigen tot een product van nul transposities, wat per definitie gelijk is aan de identiteit. Als $m$ oneven is, dan zouden we het product door herhaaldelijke toepassing van het algoritme kunnen vereenvoudigen tot een enkele transpositie, wat in tegenspraak is met de aanname dat het product gelijk is aan de identiteit. In de rest van het bewijs beschrijven we het genoemde algoritme.

We mogen aannemen dat $\tau_1=(1,2)$. Immers, als $\tau_1 = (i,j)$ ongelijk is aan $(1,2)$ dan definiëren we $\kappa\equiv(1,i)(2,j)$ en schrijven we: $$\begin{array}{rcl}e&=& \kappa\kappa^{-1}\\&=& \kappa e\kappa^{-1}\\ &=&\kappa\tau_1\cdots \tau_m\kappa^{-1}\\&=&\kappa\tau_1e\tau_2e\tau_3\cdots e\tau_{m-1}e\tau_m\kappa^{-1}\\&=&\kappa\tau_1\left(\kappa^{-1}\kappa\right)\tau_2\left(\kappa^{-1}\kappa\right)\tau_3\cdots\left(\kappa^{-1}\kappa\right)\tau_{m-1}\left(\kappa^{-1}\kappa\right)\tau_m\kappa^{-1}\\&=&\left(\kappa\tau_1\kappa^{-1}\right)\left(\kappa \tau_2\kappa^{-1}\right)\left(\kappa \tau_3\kappa^{-1}\right)\cdots \left(\kappa\tau_{m-1}\kappa^{-1}\right)\left(\kappa\tau_m\kappa^{-1}\right)\\ &=&\rho_1\cdots\rho_m\end{array}$$ waarin we $\rho_k\equiv\kappa\tau_k\kappa^{-1}$ hebben gedefinieerd voor alle $k$ in $\{1,\ldots,m\}$. Voor elke mogelijke waarde van $k$ passen we de commutatieregels toe op $\kappa$ en $\tau_k$ waarbij we de transposities in $\kappa$ ongewijzigd laten zodat, dankzij $\kappa\kappa^{-1}=e$, elke permutatie $\rho_k$ met $1\leq k\leq m$ vereenvoudigt tot één transpositie. In het bijzonder (we volgen de veranderingen van $\tau_1$ in het groen): $$\begin{array}{rcll}\rho_1&=&\kappa\color{green}{\tau_1}\kappa^{-1}&\phantom{xyzuvw}\color{blue}{\text{definitie }\rho_1}\\ &=&(1,i)(2,j)\color{green}{(i,j)}(2,j)(1,i)&\phantom{xyzuvw}\color{blue}{\kappa\equiv(1,i)(2,j), \tau_1=(i,j)}\\ &=&(1,i)\color{green}{(2,i)}(2,j)(2,j)(1,i)&\phantom{xyzuvw}\color{blue}{(2,j)(i,j)=(2,i)(2,j)}\\ &=&(1,i)\color{green}{(2,i)}(1,i)&\phantom{xyzuvw}\color{blue}{(2,j)(2,j)=e}\\ &=&\color{green}{(1,2)}(1,i)(1,i)&\phantom{xyzuvw}\color{blue}{(1,i)(2,i)=(1,2)(1,i)}\\&=&\color{green}{(1,2)}&\phantom{xyzuvw}\color{blue}{(1,i)(1,i)=e}\end{array}$$ Een product van transposities kunnen we dus altijd herschrijven tot een product van hetzelfde aantal transposities waarvan de eerste gelijk is aan $(1,2)$. We mogen daarom aannemen dat dit al gebeurd is in het oorspronkelijke product $\tau_1\cdots\tau_m$ zodat we mogen aannemen dat $\tau_1=(1,2)$.

We mogen verder aannemen dat er een natuurlijk getal $\ell$ in $\{1,\ldots,m\}$ bestaat waarvoor elk van de transposities $\tau_1,\ldots,\tau_\ell$ het getal $1$ bewegen (dat wil zeggen: de vorm $(1,a)$ hebben met $a$ in $\{2,\ldots,n\}$) en, indien $\ell\lt m$, elk van de transposities $\tau_{\ell+1},\ldots,\tau_m$ het getal $1$ vast houden. We kunnen immers de commutatieregels herhaaldelijk toepassen op naastgelegen transposities in het product $\tau_1\cdots\tau_m$ zodat alle transposities die $1$ bewegen links komen te staan ten opzichte van alle transposities die $1$ vast houden. We laten het totale aantal transposities in het product ongewijzigd door geen mogelijke vereenvoudigingen toe te passen. We nemen aan dat deze scheiding al heeft plaatsgevonden in het oorspronkelijke product $\tau_1\cdots \tau_m$.

Er geldt $\ell\geq 2$. Immers, voor $\ell=1$ vinden we $$\begin{array}{rcll}\tau_1(1)&=&\tau_1\tau_2\cdots\tau_m(1)&\phantom{xyzuvw}\color{blue}{m\geq 2\text{ en }\tau_2,\ldots,\tau_m\text{ houden }1\text{ vast}}\\&=&e(1)&\phantom{xyzuvw}\color{blue}{\tau_1\cdots\tau_m=e}\\&=&1&\phantom{xyzuvw}\color{blue}{\text{identiteit houdt elk getal vast}}\end{array}$$ in tegenspraak met $\tau_1(1)=2$.

Omdat $\ell\geq 2$ is het product $\tau_2\cdots\tau_\ell$ goed gedefinieerd, zodat we de werking daarvan op $1$ kunnen bekijken: $$\begin{array}{rcll}\tau_2\cdots\tau_\ell(1)&=& \tau_1\tau_1\tau_2\cdots\tau_\ell(1)&\phantom{xyzuvw}\color{blue}{\tau_1\tau_1=e}\\&=&\tau_1\tau_1\tau_2\cdots\tau_m(1)&\phantom{xyzuvw}\color{blue}{\ell=m\text{ of }\tau_{\ell+1},\ldots,\tau_m\text{ houden }1\text{ vast}}\\&=&\tau_1(1)&\phantom{xyzuvw}\color{blue}{\tau_1\cdots\tau_m=e}\\&=&2&\phantom{xyzuvw}\color{blue}{\tau_1=(1,2)}\end{array}$$ Er bestaat dus ten minste één index $j$ met $2\le j \le\ell$ zodat $\tau_j=(1,2)=\tau_1$. Laat $j$ de kleinste index zijn waarvoor dit geldt. Als $j=2$, dan volgt: $$\begin{array}{rcll}e&=&\tau_1\tau_1\tau_3\cdots \tau_m&\phantom{xyzuvw}\color{blue}{\tau_2=\tau_1\text{ ingevuld}}\\&=&\tau_3\cdots \tau_m&\phantom{xyzuvw}\color{blue}{\tau_1^2=e}\end{array}$$ zodat het totale aantal transposities met twee vermindert. Voor $j\geq 3$ geldt: $$\begin{array}{rcll}e&=&\tau_1\cdots \tau_{j-1}\tau_1\tau_{j+1}\cdots \tau_m&\phantom{xyzuvw}\color{blue}{\tau_j=\tau_1\text{ ingevuld}}\\&=&\left(\tau_1\tau_2\tau_1\right)\left(\tau_1\tau_3\tau_1\right)\cdots \left(\tau_1\tau_{j-1}\tau_1\right)\tau_{j+1}\cdots\tau_m&\phantom{xyzuvw}\color{blue}{\tau_1^2=e}\\&=&\sigma_2\sigma_3\cdots \sigma_{j-1}\tau_{j+1}\cdots\tau_m&\phantom{xyzuvw}\color{blue}{\sigma_i\equiv\tau_1\tau_i\tau_1}\end{array}$$ waarin we $\sigma_i\equiv\tau_1\tau_i\tau_1$ hebben gedefinieerd voor alle $i$ in $\{2,\ldots,j-1\}$. Wanneer we voor al deze waarden van $i$ de commutatieregels toepassen op $\tau_1$ en $\tau_i$ waarbij we $\tau_1$ ongewijzigd laten, dan volgt uit $\tau_1\tau_1=e$ dat elke $\sigma_i$ vereenvoudigt tot één transpositie. Dat laten we nu expliciet zien. Uit $i\lt j\leq\ell$ volgt dat er $j-2$ getallen $a_i\neq 2$ bestaan zodat $\tau_i=(1,a_i)$ en $$\begin{array}{rcll}\sigma_i&\equiv&\tau_1\tau_i\tau_1&\phantom{xyzuvw}\color{blue}{\text{definitie }\sigma_i\text{ voor }i\in\{2,\ldots,j-1\}}\\&=&(1,2)(1,a_i)(1,2)&\phantom{xyzuvw}\color{blue}{\tau_1=(1,2),\tau_i=(1,a_i)\text{ want }i\lt\ell}\\&=&(2,a_i)(1,2)(1,2)&\phantom{xyzuvw}\color{blue}{a_i\neq 2\text{ want }i\lt j}\\&=&(2,a_i)&\phantom{xyzuvw}\color{blue}{(1,2)(1,2)=e}\end{array}$$ We zien dat de identiteit in alle gevallen geschreven kan worden als een product van $m-2$ transposities: $$e=\underbrace{\sigma_2\sigma_3\cdots \sigma_{j-1}}_{j-2\text{ factoren}}\underbrace{\tau_{j+1}\cdots\tau_m}_{m-j\text{ factoren}}\qquad 2\leq j\leq m$$ Immers, $(j-2)+(m-j)=m-2$.