Noethersche Induktion

Das Beweisprinzip der Induktion ist nicht auf die Struktur der natürlichen Zahlen beschränkt. Die einzige Voraussetzung ist, dass die zugrundeliegende Struktur einen oder mehrere Anfänge besitzt. Solche Strukturen sind die vollständigen oder wohlbegründeten Ordnungen. Soll gezeigt werden, dass eine Aussage P(x) für alle x gilt, müsste es, um das Gegenteil zu beweisen, wenigstens für ein x geben, für das P(x) falsch ist. Dies führt auf einen Beweis durch Widerspruch. Diese Beweisführung ist nach der deutschen Mathematikerin Emmy NOETHER (1882 - 1935) benannt.

Das Prinzip der Noetherschen Induktion besagt, dass eine Aussage P für alle Elemente einer wohlbegründeten Ordnung ( X,≺) gilt, wenn für jedes Element von X gezeigt werden kann, dass die Aussage für das Element selbst gilt, wenn sie für alle Vorgänger des Elements gilt.

x, y, z seien Elemente einer wohlfundierten Ordnung (X,≺). Wenn für jedesx∈X, für das für jedes y∈X mit y≺x die Aussage P(y) gilt, auch P(x) gilt, dann gilt für jedes z∈X die Aussage P(z).

\( \left\{ {\forall x \in X:\left[ { \forall y \prec x:P(y) \Rightarrow P\left( x \right)} \right]} \right\} \Rightarrow \forall z \in X:P\left( z \right) \) Gl. 27

In der Noetherschen Induktion ist die Bedingung \( \forall y \prec x:P\left(y \right) \) die Induktionsvoraussetzung für P(x). Sie ist also in der Induktion implizit enthalten. Für den Fall, dass x das minimale (kleinste) Element der Ordnung ist, hat x keinen Vorgänger. Folglich ist die Aussage \(\forall y \prec x:P\left( y \right)\) trivial, denn die Aussage P(y) ist dann eine Aussage über die leere Menge! Die Richtigkeit der Aussage P(xmin) ist daher ohne weitere Vorraussetzung zu beweisen, was ja Bedingung für den Induktionsanfang ist.