H. Wolter

Die verschiedenen Methoden des Beweisens sind das Ergebnis einer langen Abstraktionsfähigkeit des menschlichen Denkens. Ein Beweis ist die Ableitung der Wahrheit einer Aussage aus schon als wahr anerkannten Aussagen. Daher sind bei Beweisen folgende grundlegende Überlegungen anzustellen:

1. Unter welchen Voraussetzungen (Prämissen) soll eine Behauptung (Conclusio) bewiesen werden, und inwieweit sind die Voraussetzungen als „gesichertes“ Wissen anzusehen?
2. Welche Schlüsse sind zulässig, um von wahren Voraussetzungen zu wahren Behauptungen zu gelangen?

(1) ist nur sehr schwierig zu handhaben und kann i. allg. nicht schlüssig beantwortet werden. Z. B. gilt die (axiomatische) Mengenlehre als Fundament der Mathematik, auf dem sich mit logischen Hilfsmitteln das Gesamtgebäude der Mathematik aufbauen läßt. Es ist jedoch unklar, ob die zugrundegelegten Axiome der Mengenlehre, die man zum Aufbau der klassischen Mathematik benötigt, wirklich widerspruchsfrei sind. Unter der Akzeptanz dieser Axiome lassen sich die verschiedenen Gebiete der Mathematik mit gesicherten logischen Hilfsmitteln entwickeln. Hierbei spielen die Überlegungen (2) eine entscheidende Rolle. Es gibt jedoch auch unterschiedliche philosophische Auffassungen in den verschiedenen Richtungen der mathematischen Logik zu der Frage, welche logischen Axiome uneingeschränkt gelten sollen und welche Schlußregeln (Beweisregeln) demzufolge zulässig sind. Ein strittiger Punkt ist z. B. das „tertium non datur“ (ein Drittes gibt es nicht), das die Zweiwertigkeit der Logik festschreibt. Unter dieser Voraussetzung (Prinzip der Zweiwertigkeit) ist jede (mathematische) Aussage entweder wahr oder falsch. In der klassischen Mathematik wird dieses Prinzip uneingeschränkt anerkannt. Lehnt man es jedoch ab, dann ist ein Beweisen nur noch unter eingeschränkten Bedingungen möglich. Entsprechend dieser (philosophischen) Auffassungen innerhalb der Logik verändert sich der Beweisbarkeitsbegriff und die zulässigen Beweismethoden. Z. B. ist in der intuitionistischen Mathematik, wo das Prinzip der Zweiwertigkeit keine Gültigkeit besitzt, die später skizzierte Methode des indirekten Beweisens unzulässig.

Um den allgemeinen Beweisbegriff zu präzisieren, ist eine Formalisierung der zugrundegelegten sprachlichen Hilfsmittel und damit auch der logischen Hilfsmittel (logische Axiome, Schlußregeln) unerläßlich.

Es sei L eine elementare Sprache (andere Sprachen werden hier nicht betrachtet, da dies zu weit führen würde) und Ax ein System logischer Axiome (das entsprechend der philosophischen Orientierung unterschiedlich gestaltet sein kann). Die logischen Axiome sind (im Rahmen dieser Orientierung) allgemeingültig und dienen als Grundvoraussetzungen für das Beweisen.

Ist Σ eine beliebige Menge von Ausdrücken aus L (Σ darf auch leer sein) und ϕ ein Ausdruck, dann ist ϕ aus Σ (im Rahmen der zugrundegelegten Logik) beweisbar (symbolisch Σ ⊢ ϕ), wenn es eine endliche Folge (ϕ₁,…,ϕ_n) von Ausdrücken in L gibt, so daß ϕ_n = ϕ und jedes ϕ_i eine der folgenden Bedingungen erfüllt:

1. E auf Null zutrifft, also E(0) gilt (Induktionsanfang) und
2. ∀n(E(n) → E(n + 1)) gilt (Induktionsschritt).

Eine All-Aussage ∀n(E(n) → E(n + 1)) ist genau dann gültig, wenn E(m) → E(m + l) für jede konkrete natürliche Zahl m gilt. Daher setzt man beim Induktionsschritt b) voraus, daß m eine beliebige, aber dann fixierte natürliche Zahl ist. Für dieses konkrete m ist E(m) → E(m + 1) zu beweisen. E(m) heißt dann Induktionsvoraussetzung und E(m + 1) Induktionsbehauptung. Eine Implikation ist schon immer dann wahr, wenn die Prämisse falsch ist. Wenn also E auf m nicht zutrifft, dann ist die Implikation trivialerweise richtig, und man hat nichts zu beweisen. Dieser triviale Fall wird meistens bei Induktionsbeweisen übergangen. Es bleibt nur der Fall zu betrachten, daß E(m) gilt. Unter dieser Voraussetzung ist E(m + l) nachzuweisen.

Wegen der Richtigkeit des Induktionsaxioms in der Form E(0) ∧ ∀n (E(n) → E(n + 1)) → ∀nE(n) ist somit ∀nE(n) gezeigt, da die Prämisse des Axioms als richtig nachgewiesen wurde.

Achtung! Häufig benutzte falsche Formulierung für die Induktionsvoraussetzung: „Für eine beliebige natürliche Zahl n gelte schon E(n)“. Wer dies so formuliert, hat die Behauptung bereits vorausgesetzt.

Die folgenden Modifikationen des Induktionsaxioms lassen entsprechend modifizierte Induktionsbeweise zu. Seien m, k natürliche Zahlen, dann gilt:

1. Ist α Nachfolgerzahl und gilt schon E(α), dann ist E(α + 1) zu beweisen.
2. Ist α Limeszahl und gilt E(β) für jedes β < α, dann ist E(α) nachzuweisen.

Bei Gültigkeit des Auswahlaxioms gilt auch der Wohlordnungssatz. Damit kann die transfinite Induktion nicht nur für Ordinalzahlen, sondern auch für beliebige Mengen genutzt werden, deren Elemente mit Ordinalzahlen „durchnumeriert“ sind.

Literatur

[1] Barwise, J.: Handbook of Mathematical Logic. North- Holland Amsterdam London New York Tokyo, 1993.

[2] Hilbert, D.; P. Bernays: Grundlagen der Mathematik I, II. Springer Berlin Heidelberg, 1939.

[3] Oberschelp, A.: Logik für Philosophen. BI Wissenschaftsverlag Mannheim Leipzig Wien Zürich, 1992.

[4] Pohlers, W.: Proof Theory, An Introduction. Springer Lecture Notes in Mathematics, Nr. 1407, Berlin, 1989.

[5] Schütte, K.: Proof-theory. Springer Berlin, 1977.

[6] Shoenfield, J.R.: Mathematical Logic. Reading London, 1967.