Induktionsbeweise
Aussagen über die natürlichen Zahlen sind oftmals Allaussagen der Form
(+) Für alle natürlichen Zahlen n gilt die Eigenschaft ℰ(n).
Jede derartige Aussage können wir, wenn sie beweisbar ist, mit Hilfe vollständiger Induktion beweisen. Ein solcher Beweis hat zwei Schritte:
Struktur eines induktiven Beweises
Induktionsanfang n = 0:
Wir zeigen ℰ(0).
Induktionsschritt von n nach n + 1:
Es gelte ℰ(n) für eine natürliche Zahl n (Induktionsvoraussetzung). Wir zeigen ℰ(n + 1) unter Verwendung der Induktionsvoraussetzung ℰ(n).
Gelingt uns die Durchführung dieser beiden Schritte, so wissen wir nach dem Induktionsaxiom, dass jede natürliche Zahl die Eigenschaft ℰ besitzt:
Induktionsbeweise und Induktionsaxiom
Wir betrachten das Induktionsaxiom für die Eigenschaft ℰ in der folgenden kompakten Form:
ℰ(0) ∧ ∀n (ℰ(n) → ℰ(n + 1)) → ∀n ℰ(n).
Diese Aussage hat die Form A ∧ B → C mit
A = ℰ(0), B = ∀n (ℰ(n) → ℰ(n + 1)), C = ∀n ℰ(n).
Der Induktionsanfang zeigt A. Der Induktionsschritt zeigt B. Da A ∧ B → C nach dem Induktionsaxiom gilt, ergibt sich C. Diese logische Überlegung zeigt, dass eine Induktion zwei Teile hat (und nicht etwa drei, wie es oft zu finden ist: die Induktionsvoraussetzung ist Teil des Induktionsschritts). Der Induktionsschritt besteht im Nachweis von
B = ∀n (ℰ(n) → ℰ(n + 1)).
Die Aussage B ist eine Allaussage. Zu ihrem Beweis betrachten wir ein beliebiges n ∈ ℕ. Nun müssen wir zeigen:
ℰ(n) → ℰ(n + 1)
Diese Aussage über n hat die Form einer Implikation. Wir nehmen also ℰ(n) an (Induktionsvoraussetzung, kurz I.V.) und versuchen, ℰ(n + 1) zu beweisen (Induktionsbehauptung, Ziel des Induktionsschritts).
Der Beweis von ℰ(n + 1) mit Hilfe von ℰ(n) ist in der Regel die einzige Schwierigkeit eines induktiven Beweises. Der Rest ist äußere Form, an die man sich natürlich erst einmal gewöhnen muss. Wir betrachten ein klassisches Beispiel: