10. Konstruktive Beweise

Im Gegensatz zu „Widerspruchsbeweis“ ist es nicht so leicht, relativ genau zu erklären, was ein „konstruktiver Beweis“ ist. Wir müssten hierzu ausführlich über logische Schlussregeln sprechen. Grob gesprochen gilt Folgendes:

Ein konstruktiver Beweis ist ein Beweis, der nur die Schlussregeln der konstruktiven Logik verwendet. Diese Schlussregeln sind eine echte Teilmenge der Schlussregeln der klassischen Logik. Die wichtigste in der konstruktiven Logik nicht vorhandene Schlussregel betrifft das Streichen einer doppelten Negation:

Haben wir ¬ ¬ A bewiesen, so haben wir A bewiesen.(Stabilität)

Man hört manchmal, dass in der konstruktiven Mathematik Widerspruchsbeweise nicht erlaubt sind. Das ist nicht richtig. Widerspruchsbeweise, die die Stabilitätsregel nicht verwenden, werden in der konstruktiven Mathematik ausdrücklich begrüßt. Dies zeigt sich vor allem darin, dass in der konstruktiven Mathematik die Negation oftmals als Implikation mit Hilfe des Falsums definiert wird:

¬ A wird definiert als A → ⊥.

Das ist sehr elegant und wir können es auch in der klassischen Mathematik so machen, wenn wir möchten. In jedem Fall gilt sowohl klassisch als auch konstruktiv für jede Aussage A:

(+) ¬ A ist äquivalent zu A → ⊥.

Ein Beweis von ¬ A kann damit konstruktiv als Widerspruchsbeweis geführt werden: Wir nehmen A an und zeigen ⊥ (ohne Verwendung der Stabilität). Dies zeigt A → ⊥ (Abbinden der Annahme A). Nach Definition der Negation oder (+) ist damit ¬ A bewiesen.

Was in der konstruktiven Mathematik dagegen nicht möglich ist, ist folgendes Beweisschema:

Nichtkonstruktiver Widerspruchsbeweis

Wir wollen eine Aussage A zeigen. Hierzu nehmen wir ¬ A an und leiten ⊥ her. Durch Abbinden der Annahme ¬ A haben wir ¬ A → ⊥ und damit nach (+) ¬ ¬ A gezeigt. Anwendung der Stabilität liefert A.

Aus konstruktiver Sicht liefert diese Beweismethode nur ¬ ¬ A. Der letzte Schritt des Streichens einer doppelten Negation wird nicht mitgetragen.

Dass Widerspruchsbeweise nicht konstruktiv seien, ist also in dieser Allgemeinheit eine falsche Behauptung. Wir müssen immer fragen, welche Form der Widerspruchsbeweis besitzt und welche Schlussregeln er benutzt. Dabei spielt es eine Schlüsselrolle, ob die zu beweisende Aussage negiert ist oder nicht. Ist sie negiert, also von der Form ¬ A, so ist ein Widerspruchsbeweis von ¬ A konstruktiv, sofern er zur Herleitung von ⊥ aus der Annahme A keine nichtkonstruktiven Schlussregeln verwendet. Für den Beweis von Euklid gilt:

Der Beweis ist konstruktiv.

Dabei spielt es keine Rolle, ob er, abhängig von der Definition von „unendlich“, als Widerspruchsbeweis präsentiert wird oder nicht.

Warum ist „konstruktiv“ wichtig?

Die konstruktive Mathematik verfolgt das Ziel, dass jeder Existenzbeweis auch ein Beispiel für die Existenz erzeugt. Betrachten wir hierzu den folgenden Satz der reellen Analysis:

Satz (Existenz von Nullstellen für Polynome dritten Grades)

Sei f : ℝ → ℝ ein reelles Polynom drittes Grades, d. h. es gibt a, b, c, d  ∈  ℝ mit a ≠ 0 und

f (x) = a x³ + b x² + c x + d für alle x  ∈  ℝ.

Dann besitzt f eine Nullstelle, d. h. es gibt ein x  ∈  ℝ mit f (x) = 0.

Ein konstruktiver Beweis dieses Satzes zeigt, wie eine Nullstelle des Polynoms mit Hilfe der Koeffizienten a, b, c, d des Polynoms effektiv berechnet werden kann. Das ist auch in der klassischen Mathematik von Interesse. In der klassischen Mathematik ist aber „Existenz“ umfassender als „(algorithmische) Berechenbarkeit“. In der konstruktiven Mathematik fallen die Begriffe zusammen.

Der Beweis von Euklid ist in diesem Sinne konstruktiv: Er erlaubt es, für endlich viele vorgegebene Primzahlen eine Primzahl zu finden, die von den gegebenen Primzahlen verschieden ist. Liegen p₁, …, p_n konkret vor, so berechnen wir a = p₁ … p_n + 1. Weiter berechnen wir einen Primteiler p von a (durch ein effektives Verfahren, das sich aus einem konstruktiven Beweis der Existenz eines Primteilers einer natürlichen Zahl größergleich 2 ergibt). Dann ist p wie gewünscht. Setzen wir p_n + 1 = p, so kann mit Hilfe von p₁, …, p_n + 1 eine weitere Primzahl p_n + 2 berechnet werden usw.

Der Unterschieds zwischen klassischer und konstruktiver „Existenz“ lässt sich schön mit Hilfe des folgenden Satzes illustrieren:

Satz (rationale Potenzen irrationaler Zahlen)

Es gibt irrationale Zahlen x, y > 0 derart, dass x^y rational ist.

Ein konstruktiver Beweis des Satzes würde es erlauben, konkrete Beispiele für x, y anzugeben. Dies gestattet der folgende klassische Beweis nicht:

Beweis

Wir setzen a = $\sqrt{2}$ . Dann ist $\sqrt{2}$ irrational. Weiter sei

b = a^a = $\sqrt{2}$ ^$\sqrt{2}$ (= e^{$\sqrt{2}$ log $\sqrt{2}$}).

Wir unterschieden zwei Fälle.

1. Fall: b ist rational.

Wir setzen x = y = a. Dann sind x, y > 0 irrational und die Potenz x^y ist rational.

2. Fall: b ist irrational.

Wir setzen x = b und und y = a. Dann sind x, y irrational ist die Potenz x^y ist rational, da

b^a = ( $\sqrt{2}$ ^$\sqrt{2}$)^$\sqrt{2}$ = $\sqrt{2}$ ² = 2.

Der Beweis verwendet eine nichtkonstruktive Fallunterscheidung bei der Betrachtung von b. Die Fallunterscheidung beruht auf

b ist rational oder b ist nicht rational.

Dies ist ein Spezialfall des klassischen Prinzips „tertium non datur“: Für jede Aussage A gilt

A ∨ ¬A.(tertium non datur)

Das „tertium von datur“ wird von der konstruktiven Mathematik ebenso abgelehnt wie die Stabilität. Ein konstruktiver Beweis einer Disjunktion A ∨ B muss zeigen, welche der beiden Aussagen gilt. Obiger Beweis lässt es offen, ob die Zahl

b = $\sqrt{2}$ ^$\sqrt{2}$

rational ist oder nicht. Wir wissen, dass es reelle Zahlen mit der gewünschten Eigenschaft gibt (im Sinne des klassischen Existenzbegriffs), aber wir können keine konkreten Beispiele für derartige Zahlen angeben. Erst ein stärkeres Ergebnis erlaubt die Entscheidung. Es verwendet den Begriff der algebraischen Zahl.

Definition (algebraische Zahl)

Eine reelle Zahl x heißt algebraisch, falls x eine Nullstelle eines reellen Polynoms beliebigen Grades mit ganzzahligen Koeffizienten ist. Andernfalls heißt x transzendent.

Jede rationale Zahl q = n/m mit ganzen Zahlen n und m ist algebraisch, da q Nullstelle des Polynoms f : ℝ → ℝ mit

f (x) = m x − n für alle x  ∈  ℝ

ist. Dies zeigt, dass jede transzendente Zahl irrational ist. Eines der wichtigsten (und alles andere als leicht zu beweisenden) Ergebnisse über transzendente Zahlen lautet:

Satz (Satz von Gelfond-Schneider 1934)

Seien x, y algebraische Zahlen. Es gelte x ≠ 0, 1 und y sei irrational. Dann ist x^y transzendent.

Wenden wir diesen starken allgemeinen Satz auf x = y = $\sqrt{2}$ an, so sehen wir, dass die Zahl

b = $\sqrt{2}$ ^$\sqrt{2}$

transzendent und damit insbesondere irrational ist.

Die überwiegende Mehrheit der Mathematiker argumentiert nach wie vor in der klassischen Logik und lehnt eine Gleichsetzung von Existenz und Algorithmus ab. Die konstruktive Mathematik hat aber ganz unabhängig von der Frage nach der „besten Logik“ mitgeholfen, die Grundlagen des mathematischen Argumentierens ans Licht zu bringen. Die Spielregeln des mathematischen Beweisens wurden im 20. Jahrhundert klar formuliert und auch klassische Mathematiker profitieren von ihrer Diskussion und Analyse. Ein klassischer Mathematiker kann prinzipiell jeden Beweis einer Aussage A mit der Annahme „Es gelte ¬A.“ beginnen und dann ⊥ anstreben. Er hat dann ¬ ¬ A gezeigt und erhält A durch Anwendung der Stabilitätsregel. Es stellt sich heraus, dass diese Beweise oft deutlich verwickelter und schwerer lesbar sind als andere. Es ist damit guter Stil, nichtkonstruktive Widerspruchsbeweise zu vermeiden, wenn es möglich ist. Einen Beweis von ¬ A in der implikativen Form A → ⊥ durch Widerspruch zu führen ist dagegen in jeder Logik die Methode der Wahl.