S4 is voort te brengen door transposities.

h.hofstede (h.hofstede@hogeland.nl)

       
We gaan het bewijs leveren met behulp van volledige inductie, en dat doen we door het aantal elementen van een verzameling steeds groter te maken.

inductie-aanname:
Stel dat een verzameling van n - 1 elementen(1, 2, 3, ..., n -1) helemaal door transposities kan worden weergegeven.

Neem nu het n-de element bij de verzameling.
Bekijk een willekeurige permutatie  P.
Nu zijn er twee mogelijkheden:
       
1. Bij permutatie P komt element n op zichzelf terecht.
2. Bij permutatie P komt element n op een ander element k terecht.
       
Het eerste geval is niet interessant: dan is de permutatie P precies zo op te bouwen uit transposities als bij de kleinere verzameling zonder element n.

Het tweede geval is wl interessant.
Pas in dit geval twee dingen na elkaar toe:    (verwissel nk) o (Permutatie P)
Samen laten die n op zijn plaats (bij P  gaat n naar k, daarna bij de verwisseling weer van k naar n)
Dus zijn die twee samen als een aantal verwisselingen te schrijven  (dat is de inductie-aanname: zonder element n)

Maar dan is:      (verwissel nk)(verwissel nk) o (Permutatie P)  ook een aantal verwisselingen. namelijk die blauwen plus eentje erbij.
Maar dit laatste is gelijk aan   Permutatie P  (die beide verwisselingen heffen elkaar op).
Dus is permutatie P als een serie verwisselingen te schrijven.

q.e.d.
       
       

h.hofstede (h.hofstede@hogeland.nl)