Prinzip der Vollständigen Induktion

Zunächst eine grundlegende Erklärung: Ein induktives System S ist eine Teilmenge von ℝ mit der Eigenschaft:

• 1 ∈ S

• Mit x ∈ S ist auch x + 1 ∈ S.

Dies ist die Idee der Vollständigen Induktion, also wenn etwas Element einer Menge ist, oder dass für etwas eine gewisse Vorschrift oder Eigenschaft gilt (zb. größer kleiner), diese auch für das nächste Glied (also +1) gilt.

Sei A(n) eine Aussage mit natürlichen Zahlen als Parameter, z.B. “(n+1)² = n²+2n+1" oder “n ist eine Primzahl”. Insbesondere muss A(n) nicht notwendig für alle n ∈ℕ richtig sein. Es seien die folgenden Bedingungen erfüllt:

1. Induktionsanfang: A(1) ist wahr.
2. Induktionsschritt: Falls für ein n ∈ ℕ die Aussage A(n) wahr ist, dann ist auch A(n + 1) wahr.

Dann ist A(n) (also die Aussage) wahr für alle n ∈ℕ. Offenbar ergibt sich das Prinzip der vollständigen Induktion aus der obigen Eigenschaft. Sei dazu E:={n∈ℕ|A(n) ist wahr}, Induktionsanfang und -schritt garantieren, dass E die Bedingungen von oben erfüllt. Daher ist E = ℕ und A(n) für alle natürlichen Zahlen wahr. Vollständige Induktion ist vielleicht die wichtigste Beweismethode zur Verifizierung von Aussagen, die explizit (oder implizit) von natürlichen Zahlen als Argument abhängen.

Behauptung: Jede natürliche Zahl ist positiv.

Beweis: (mit Hilfe induktiver Systeme) ℝ+ := {x ∈ℝ|0 < x} ist ein induktives System.

Also erstmal der Induktionsanfang: In der Tat, 1 ∈ℝ+

Induktionsschritt: Außerdem impliziert x ∈ ℝ+ die Aussage x + 1 ∈ ℝ+ da wenn eine Zahl positiv ist und mit einer positiven Zahl addiert wird diese auch Positiv ist. Also ist ℝ+ tatsächlich ein induktives System. Per definitionem ist ℕ⊂ ℝ+, d.h. die Aussage ist bewiesen.

Weteres Beispiel: