Beispielhafter, schematischer Aufbau eines Beweises
EinBeweis ist in derMathematik die als fehlerfrei anerkannte Herleitung der Richtigkeit bzw. der Unrichtigkeit einer Aussage aus einer Menge vonAxiomen, die als wahr vorausgesetzt werden, und anderenAussagen, die bereits bewiesen sind. Man spricht daher auch vonaxiomatischen Beweisen.
Umfangreichere Beweise von mathematischen Sätzen werden in der Regel in mehrere kleine Teilbeweise aufgeteilt, siehe dazuSatz undHilfssatz.
In derBeweistheorie, einem Teilgebiet dermathematischen Logik, werden Beweise formal alsAbleitungen aufgefasst und selbst als mathematische Objekte betrachtet, um etwa die Beweisbarkeit oder Unbeweisbarkeit von Sätzen aus gegebenen Axiomen selbst zu beweisen.
Bei einemkonstruktivenExistenzbeweis wird entweder die Lösung selbst genannt, deren Existenz zu zeigen ist, oder ein Verfahren angegeben, daszur Lösung führt, das heißt, es wird eine Lösungkonstruiert.
Bei einemnicht-konstruktiven Beweis wird anhand von Eigenschaften auf die Existenz einer Lösunggeschlossen. Manchmal wird sogar indirekt die Annahme, es gäbe keine Lösung, zum Widerspruch geführt, worausfolgt, dass es eine Lösung gibt. Aus solchen Beweisen geht nicht hervor, wie man die Lösung gewinnt.
Ein einfaches Beispiel soll dies verdeutlichen.
Behauptung: DieFunktion mit besitzt im Intervall mindestens eine Nullstelle.
Konstruktiver Beweis: Sei. Dann gilt. Ferner liegt im Intervall. Damit ist die Behauptung bewiesen. DieNullstelle ist sogar mit angegeben.
Nicht-konstruktiver Beweis: iststetig. Ferner ist und. Nach demZwischenwertsatz für stetige Funktionen folgt die Behauptung. Über den Wert der Nullstelle liefert dieser Beweis jedoch keine Information.
In der auf dem AxiomensystemZFC aufbauenden Mengenlehre nennt man Beweise nicht-konstruktiv, wenn sie dasAuswahlaxiom verwenden. Denn alle anderen Axiome von ZFC beschreiben, welche Mengen es gibt bzw. was man mit Mengen machen kann, und geben die konstruierten Mengen an. Nur das Auswahlaxiom postuliert die Existenz einer gewissen Auswahlmöglichkeit, ohne anzugeben, wie diese Auswahl auszuführen wäre. In der Anfangszeit der Mengenlehre war das Auswahlaxiom wegen seines nicht-konstruktiven Charakters heftig umstritten (dermathematische Konstruktivismus vermeidet bewusst das Auswahlaxiom), daher rührt seine Sonderstellung nicht nur in der abstrakten Mengenlehre, sondern auch bei Beweisen in anderenTeilgebieten der Mathematik. In diesem Sinne gelten alle Beweise, die dasLemma von Zorn verwenden, als nicht-konstruktiv, denn dieses Lemma ist äquivalent zum Auswahlaxiom.
Die gesamte Mathematik kann im Wesentlichen auf ZFC aufgebaut und im Rahmen von ZFC bewiesen werden. Über die Grundlagen der Mengenlehre legt der arbeitende Mathematiker in der Regel keine Rechenschaft ab, lediglich die Verwendung des Auswahlaxioms findet Erwähnung, in der Regel in der Form des Lemmas von Zorn. Darüber hinausgehende mengentheoretische Annahmen werden stets angegeben, zum Beispiel wenn man dieKontinuumshypothese oder ihre Negation verwendet.
Formale Beweise reduzieren die Beweisschritte auf eine Reihe definierter Operationen auf Zeichenketten. Solche Beweise können in der Regel nur mitMaschinenunterstützung erstellt werden (siehe etwaCoq (Software)) und sind für Menschen kaum lesbar, schon allein die Übertragung der zu beweisenden Sätze in eine rein formale Sprache führt zu sehr langen, umständlichen und unverständlichen Zeichenketten. Eine Reihe bekannter Sätze wurde inzwischen formalisiert und deren formaler Beweis maschinell überprüft.In der Regel genügt den Mathematikern jedoch die Gewissheit, dass ihre Argumentationsketten prinzipiell in formale Beweise übertragbar wären, ohne dass dies tatsächlich ausgeführt wird, sie verwenden die im Folgenden vorgestellten Beweismethoden.
Einige mathematische Sätze oder logischeSchlussregeln lassen sich für eine Vielzahl von Beweisen einsetzen und beeinflussen die Struktur des Beweises besonders stark. Die systematische Vorgehensweise zur Anwendung dieser bezeichnet man dann alsBeweismethode,Beweisverfahren,Beweistechnik oderBeweisprinzip. Die Gültigkeit einer Beweismethode bedarf selbst eines Beweises, im Rahmen der Axiome und der Logik gültig zu sein (etwa ist die Reductio ad absurdum (s. u.) in der Grundform nicht inintuitionistischer Logik, und eine transfinite Induktion über alleKardinalzahlen nur unter Voraussetzung desWohlordnungssatzes möglich). Hier eine Auswahl von Standard-Beweismethoden:
Für einendirekten Beweis (direkter Schluss) nimmt man einen bereits als richtig bewiesenen Satz (Prämisse) und leitet, durch logische Schlussfolgerungen, daraus den zu beweisenden Satz (Konklusion) ab. Als einfaches Beispiel diene Folgendes:
Behauptung: Das Quadrat einer ungeraden natürlichen Zahl ist stets ungerade.
Beweis: Es sei eine ungerade natürliche Zahl. Das heißt, lässt sich darstellen als, wobei eine natürliche Zahl oder Null ist. Daraus folgt mit Hilfe derersten binomischen Formel
.
Aus der Möglichkeit, so darzustellen folgt, dass ungerade ist.
Bei einemindirekten Beweis (Reductio ad absurdum,Widerspruchsbeweis) zeigt man, dass ein Widerspruch entsteht, wenn die zu beweisende Behauptung falsch wäre. Dazu nimmt man an, dass die Behauptungfalsch ist, und wendet dann die gleichen Methoden wie beim direkten Beweis an. Wenn daraus ein Widerspruch entsteht, dann kann die Behauptung nicht falsch sein, also muss sie richtig sein (Satz vom ausgeschlossenen Dritten).
Nun ein Beispiel für eine reductio ad absurdum:
Behauptung: Ist die Wurzel aus einer geraden natürlichen Zahl eine natürliche Zahl, so ist diese gerade.
Beweis: Angenommen, wäre ungerade. Dann ist auch ungerade (siehe obiges Beispiel zum direkten Beweis), und das ist ein Widerspruch zu der Voraussetzung, dass gerade ist. Also ist die getroffene Annahme falsch, das heißt, ist gerade.
Beweis: Angenommen, diese Zahl wäre rational. Dann kann man sie als Bruch darstellen, wobei und natürliche Zahlen undohne Beschränkung der Allgemeinheitteilerfremd sind (sonst kann man den Bruch soweit kürzen, bis das der Fall ist). Daraus folgt durch Quadrieren
, also
Folglich ist eine gerade Zahl. Da die Wurzel aus einer geraden Quadratzahl auch gerade ist (siehe vorangegangene Behauptung), ist selbst gerade, also ist eine natürliche Zahl.Durch Umformung der letzten Gleichung erhält man
Das zeigt, dass und somit auch gerade natürliche Zahlen sind. Also sind und beide gerade und haben somit beide den Teiler 2. Damit sind und nicht teilerfremd – im Widerspruch zu der Annahme ihrer Teilerfremdheit. Also ist auch die ursprüngliche Annahme, seirational, falsch.
Die vorangegangenen Beispiele sind nicht darauf angewiesen, dass das Prinzip vom ausgeschlossenen Dritten zur Verfügung steht, wenn man „x ist irrational“ als „x ist nicht rational“ definiert. Was die Form angeht, ist das zweite eher ein direkter Beweis einer Negation.
Ein Beispiel, für das tatsächlichklassische Logik benötigt wird (und wir verwenden das Prinzip des indirekten Beweises ineffizienterweise zunächst ausschließlich ganz außen):
Behauptung: (C):.
Beweis: Wir nehmen die Negation von (C), also (A):, an und führen diese Annahme zu einem Widerspruch:Zunächst gilt (B):, denn angenommen, gilt natürlich auch, was (A) widerspricht.Daher gilt aber auch (C), denn, angenommen, haben wir einen Widerspruch zu (B).(C) widerspricht nun offenbar der Annahme (A), wir haben also den gewünschten Widerspruch.
Besserer Beweis: Wir nehmen an und zeigen unter dieser Annahme, indem wir zu einem Widerspruch führen: Gilt nämlich, dann auch, weil die Annahme von zu einem Widerspruch führt. widerspricht dann aber der globalen Annahme.
An diesem Beispiel sieht man einen Hinweis zur Pragmatik des Beweisfindens: In der Regel ist es von Vorteil, das Prinzip des indirekten Beweisens möglichst spät anzuwenden und so lange, wie es geht, Pfade zum Finden direkter Beweise zu verfolgen.Überdies zeigt dieBeweistheorie, dass man durch Verfolgen der Strategie, das Prinzip des indirekten Beweisens möglichst spät anzuwenden, und dabei keine unmotivierten Wahlen zu treffen, nicht in einer Situation landen kann, in der man Unmögliches zu beweisen hat, ein früheres Abbiegen auf einen Pfad zu einem indirekten (Teil-)Beweis aber von Erfolg gekrönt gewesen wäre.
Der Beweis durchvollständige Induktion ist ein oft angewendetes Verfahren zum Beweis von Sätzen der Form„Für jedenatürliche Zahl gilt …“. Dazu zeigt man zuerst, dass die Aussage für (oder auch einen anderen Anfangswert) gilt, und danach, dass sie immer auch für gilt, wenn sie für ein gilt. Die vollständige Induktion lässt sich mit einemDomino-Effekt veranschaulichen. Man stellt die Steine so auf, dass, wenn einer umfällt, auchimmer der nächste umfällt ( →), und stößt den ersten Stein um ().
Ein einfaches Beispiel:
Behauptung: Es gilt für alle natürlichen Zahlen:
Beweis:
Die Behauptung gilt für: ist eine wahre Aussage.
Die Behauptung sei für ein gültig. Für untersucht man die Summe
Da die Behauptung für gültig ist, folgt
Also gilt die Behauptung auch für, damit ist die Aussage nach dem Induktionsprinzip bewiesen.
Bei einem Beweis durch vollständige Fallunterscheidung (engl.proof by exhaustion „durch Ausschöpfung“) wird jeder der möglichen Fälle einzeln betrachtet. Die Zahl der möglichen Fälle muss daher endlich sein.
Behauptung: JedePrimzahl hat die Form mit einernatürlichen Zahl.
Beweis:Man unterscheidet folgende vier Fälle für die Zahl, von denen immer genau einer eintritt:
Im ersten dieser Fälle ist durch 4 teilbar und damit keine Primzahl, im dritten Fall ist durch 2 teilbar und somit ebenfalls keine Primzahl. Alsomuss einer der Fälle zwei oder vier eintreten, das heißt, hat die Form mit einer natürlichen Zahl.
Es sei angemerkt, dass die Fallunterscheidung zwarvollständig sein muss, aber die untersuchten Fälle sichnicht gegenseitig ausschließen müssen.
Die Diagonalverfahren wurden vonGeorg Cantor zum Beweis zweier spezieller Aussagen entwickelt. Sie haben sich seitdem als allgemeine Beweismethoden bewährt.
Daserste Cantorsche Diagonalverfahren ist eindirekter Beweis für die Abzählbarkeit einer Menge. Es wird gezeigt, dass man jedem Element der zu untersuchenden Menge eine natürliche Zahl zuordnen kann.
Daszweite Cantorsche Diagonalverfahren ist einindirekter Beweisfür die Überabzählbarkeit einer Menge. Es wird also das Gegenteil angenommen, nämlich dass die Menge abzählbar wäre. Dann wird aus dieser Annahme ein Widerspruch hergeleitet, sodass sie fallen gelassen werden muss.
DasSchubfachprinzip geht auf den deutschen MathematikerDirichlet zurück und kann sehr anschaulich formuliert werden: Verteilt man Gegenstände auf Schubfächer, dann befinden sich in mindestens einem Schubfach mindestens zwei Gegenstände. Als Beispiel betrachten wir:
Behauptung: Hat mindestens Elemente, so gibt es mit.
Beweis: Alle Elemente aus haben die Gestalt mit einer ungeraden Zahl. Von diesen gibt es aber nur verschiedene in, so dass eine ungerade Zahl bei obiger Zerlegung der mindestens Zahlen aus zweimal vorkommen muss (das ist das Schubfachprinzip). Daher enthält zwei Zahlen und mit derselben ungeraden Zahl. Offenbar teilt die kleinere die größere.[1]
Häufig hat man es mit Aussagen über alleOrdinalzahlen zu tun. Wie auch bei der oben vorgestellten vollständigen Induktion in muss man die Behauptung für die erste Ordinalzahl 0 beweisen, und dann, dass, wenn die Behauptung für eine Ordinalzahl vorausgesetzt wird, sie auch für deren Nachfolger gilt. Im Gegensatz zu obiger Induktion muss man zusätzlich zeigen, dass die Behauptung auch für jede Limesordinalzahl gilt, wenn sie für alle kleineren Ordinalzahlen zutrifft. Verzichtet man auf diesen zusätzlichen Teil, so funktioniert die transfinite Induktion nur bis unterhalb der ersten Limesordinalzahl, das heißt nur für die Ordinalzahlen. Man erhält dann die gewöhnliche vollständige Induktion in den natürlichen Zahlen, denn diese sind die Ordinalzahlen bis zur ersten Limesordinalzahl.
DasPrinzip der guten Mengen wird in der Maßtheorie verwendet, um zu beweisen, dass eine Aussage für alle Elemente einerσ-Algebra oder eines anderenMengensystems zutrifft. Außerdem bedient man sich dermaßtheoretische Induktion als Beweismethode, um Aussagen für eine vorgegebene Menge von messbaren Funktionen zu zeigen.
Neben den Beweismethoden gibt es einige hilfreiche Beweisstrategien: Entscheidet man sich beim Beweis einer Aussage für eine der oben beschriebenen Methoden, so hilft bei der Umsetzung dieser Methode eine Beweisstrategie.
Das Extremalprinzip tritt insbesondere bei Existenzbeweisen auf: Genauer immer dann, wenn es darum geht, die Existenz eines Objekts innerhalb einer Menge zu beweisen. Das allgemeine Extremalprinzip knüpft an der Idee an, dass dort, wo etwas extremal (etwa größtmöglich, kleinstmöglich usw.) wird, besondere Strukturen entstehen, aus denen im Rahmen der mathematischen Beweisführung wertvolle Fakten abgeleitet werden können.[2] Diese Extremalität findet sich in der Mathematik häufig, etwa in folgenden Eigenschaften:
Jede nichtleere, nach oben beschränkte Teilmenge reeller Zahlen besitzt einSupremum, d. h. eine kleinste obere Schranke (Supremumseigenschaft). Umgekehrt besitzt eine nach unten beschränkte, nichtleere Teilmenge der reellen Zahlen ein Infimum, also eine größte untere Schranke.
Jede nichtleere Menge natürlicher Zahlen enthält eine kleinste Zahl. (Wohlordnungsprinzip)
Das Invarianzprinzip folgt dem Grundsatz, ein Hauptaugenmerk auf dasjenige zu richten, was invariant (d. h. unverändert) unter Veränderung bleibt. Oft versteht man ein komplexes System besser, wenn man versteht, wie sich dessen Einzelteile verhalten. Das Invarianzprinzip ist hilfreich für Unmöglichkeitsbeweise.[3]
Beweise in derAnalysis bedienen sich oft der Strategie des „Hinzuaddierens einer nahrhaften Null“. Der Zusatz „nahrhaft“ rührt daher, dass das Addieren einer Null einen Ausdruck zwar nicht verändert, allerdings in einigen Fällen nahrhaften Boden für eine elegante algebraische Umformung bietet.
Beispiel
Möchte man zeigen, dass jedekonvergente Folge eineCauchy-Folge ist, so bedient man sich einer nahrhaften Null, um dieDreiecksungleichung auszunutzen. Sei eine beliebige konvergente Folge und ihr Grenzwert. Sei, dann gibt es nach Definition der (Folgen-)Konvergenz ein mit und für alle. Sei nun beliebig, so gilt:
Somit ist jede konvergente Folge sogleich eine Cauchy-Folge,was zu beweisen war. Der Beweis lebt vom Hinzuaddieren einer nahrhaften Null im zweiten Schritt.
↑M. Aigner, G. M. Ziegler:Proofs from THE BOOK, Springer-Verlag 1998,ISBN 3-540-63698-6, Kapitel 20:Pigeon-hole and double counting.
↑Daniel Grieser:Mathematisches Problemlösen und Beweisen: Eine Entdeckungsreise in die Mathematik. 2. Auflage. Springer Spektrum, 2016,ISBN 978-3-658-14764-8,S.213–214.
↑Daniel Grieser:Mathematisches Problemlösen und Beweisen: Eine Entdeckungsreise in die Mathematik. 2. Auflage. Springer Spektrum, 2016,ISBN 978-3-658-14764-8,S.248.
