Zu beweisen: ´AA A sube NN : AA n in A: EE m in A: m <= n´

Vollständige Induktion:

Anfang:

Hat ´A´ nur ein einziges Element ´m´, dann ist ´m <= m´ und somit das kleinste Element.

Vorraussetzung:

Es sei ´A´ eine beliebige aber bestimmte nichtleere Teilmenge von ´NN´ mit ´n´ Elementen. Nicht endliche Teilmengen müssen auch noch beachtet werden!

´AA n in A: EE m in A: m <= n´

Behauptung:

Die Vorraussetzung gilt auch für ´A'´ mit ´n + 1´ Elementen

Beweis:

Sei ´x´ eine beliebige aber feste natürliche Zahl mit ´x !in A´. Dann gilt entweder ´x < n_min´ oder ´n_min < x´. Somit ist in der Menge ´A' = A uu {x}´ unter Annahme der Induktionsvorraussetzung entweder ´n_min´ oder ´x´ das neueste kleinste Element.

Fehlt: Jedes ´A'´ kann als ´A uu {x}´ dargestellt werden, wenn ´A´ ´n in NN^+´ Element hat.

Nach dem Prinzip der vollständigen Induktion ist durch die Anwendung des Induktionsbeweises auf den Induktionsanfang damit die ursprüngliche Aussage bewiesen.

∎