Permutation/Kein Fehlstand/Identität/Aufgabe/Lösung

Wenn ${}\pi$ die Identität ist, so ist für jedes ${}i<j$ natürlich auch ${}\pi (i)=i<j=\pi (j)$, sodass kein Fehlstand vorliegt. Die Umkehrung beweisen wir durch Induktion über ${}n$. Für ${}n=1$ ist die Aussage richtig. Es sei sie für ${}n$ schon bewiesen und sei eine Permutation ${}\pi$ auf ${}\{1,\ldots ,n+1\}$ ohne Fehlstand gegeben. Für jedes ${}i<n+1$ gilt dann ${}\pi (i)<\pi (n+1)$. Die ${}n$ verschiedenen Zahlen ${}\pi (i)$, ${}i={\{1,\ldots ,n\}}$, sind also kleiner als ${}\pi (n+1)$, und daher ist die einzige verbleibende Möglichkeit

${}\pi (n+1)=n+1\,.$

Daher ist ${}n+1$ ein Fixpunkt von ${}\pi$ und somit kann man ${}\pi$ als eine Permutation auf ${}{\{1,\ldots ,n\}}$ auffassen. Diese besitzt ebenfalls keinen Fehlstand und ist nach Induktionsvoraussetzung die Identität, also ist auch ${}\pi$ die Identität.

Zur gelösten Aufgabe