Beweis (Mathematik)

Grundidee des mathematischen Beweises

Ein mathematischer Beweis ist eine als fehlerfrei anerkannte Herleitung dafür, dass eine Aussage richtig oder unrichtig ist. Ausgangspunkt sind Axiome, die als wahr vorausgesetzt werden, und Aussagen, die bereits bewiesen sind. Deshalb spricht man auch von axiomatischen Beweisen.

Größere Beweise werden meist in kleinere Teilbeweise gegliedert; dabei können Sätze und Hilfssätze verwendet werden. Die Beweistheorie, ein Gebiet der mathematischen Logik, betrachtet Beweise selbst als mathematische Objekte: Formale Ableitungen werden untersucht, um etwa die Beweisbarkeit oder Unbeweisbarkeit eines Satzes aus bestimmten Axiomen zu zeigen.

Ein formaler Beweis zerlegt jeden Schritt in festgelegte Operationen auf Zeichenketten. Solche Beweise entstehen meist nur mit Maschinenunterstützung, etwa mit Coq, und sind für Menschen oft schwer lesbar. Mathematiker begnügen sich gewöhnlich damit, dass ihre Argumentationskette grundsätzlich in einen formalen Beweis übertragbar wäre. Einige bekannte Sätze wurden aber bereits formalisiert und maschinell überprüft.

Konstruktive und nicht-konstruktive Existenzbeweise

Ein Existenzbeweis zeigt, dass ein gesuchtes Objekt oder eine Lösung existiert. Konstruktiv ist er, wenn die Lösung selbst genannt oder ein Verfahren zu ihrer Gewinnung angegeben wird. Nicht-konstruktiv ist er, wenn Eigenschaften lediglich auf die Existenz schließen lassen; aus ihm folgt dann nicht unbedingt, wie die Lösung gefunden wird.

Beispiel: Für f(x)=2x−1 besitzt das Intervall [0,1] mindestens eine Nullstelle. Konstruktiv kann man x₀=0,5 angeben, denn f(0,5)=2·0,5−1=0 und 0,5 liegt in [0,1]. Nicht-konstruktiv folgt die Existenz aus der Stetigkeit von f sowie f(0)=−1<0 und f(1)=1>0 nach dem Zwischenwertsatz. Dieser Beweis nennt den Wert der Nullstelle nicht.

In der auf ZFC aufgebauten Mengenlehre heißen Beweise insbesondere dann nicht-konstruktiv, wenn sie das Auswahlaxiom benutzen. Anders als die übrigen ZFC-Axiome postuliert es eine Auswahlmöglichkeit, ohne ihre Ausführung anzugeben. Auch Beweise mit dem Lemma von Zorn sind deshalb nicht-konstruktiv, da es zum Auswahlaxiom äquivalent ist. Die Mathematik lässt sich im Wesentlichen in ZFC aufbauen; weitergehende Annahmen wie die Kontinuumshypothese oder ihre Negation müssen angegeben werden.

Direkter und indirekter Schluss

Beim direkten Beweis wird aus einer bereits bewiesenen Prämisse durch logische Schlüsse die zu beweisende Konklusion abgeleitet. Für eine ungerade natürliche Zahl n=2k+1 gilt beispielsweise n²=(2k+1)²=4k²+4k+1=2·(2k²+2k)+1. Damit hat n² die Form einer ungeraden Zahl und ist ebenfalls ungerade.

Beim indirekten Beweis, der Reductio ad absurdum oder dem Widerspruchsbeweis, nimmt man an, die Behauptung sei falsch, und leitet daraus einen Widerspruch ab. Dann kann die Annahme nicht stimmen. Ist etwa n gerade und √n=k eine natürliche Zahl, kann k nicht ungerade sein: Dann wäre k²=n nach dem vorherigen Ergebnis ungerade, im Widerspruch dazu, dass n gerade ist.

Auch die Irrationalität von √2 lässt sich so zeigen. Nähme man √2=l/k mit teilerfremden natürlichen Zahlen l und k an, ergäbe das l²=2k². Dann sind l² und l gerade; aus k²=l²/2=2·(l/2)² folgen auch gerades k² und gerades k. l und k hätten beide den Teiler 2 und wären nicht teilerfremd – ein Widerspruch.

Die Grundform des indirekten Beweises benötigt den Satz vom ausgeschlossenen Dritten nicht in jeder Situation. In intuitionistischer Logik gilt sie jedoch nicht allgemein. Für das Finden von Beweisen ist es meist sinnvoll, indirektes Beweisen möglichst spät einzusetzen und zunächst nach direkten Beweiswegen zu suchen.

Induktion, Fälle und weitere Beweisverfahren

Die vollständige Induktion beweist Aussagen der Form „Für jede natürliche Zahl n gilt …“. Zuerst zeigt man den Induktionsanfang, etwa für n=0. Danach zeigt man im Induktionsschritt: Gilt die Aussage für n, so gilt sie auch für n+1. Dies ähnelt einer Reihe von Dominosteinen.

So gilt für alle natürlichen Zahlen n: 1+3+…+(2n+1)=(n+1)². Für n=0 ist 1=(0+1)². Gilt die Formel für n, dann ist 1+3+…+(2n+1)+(2n+3)=(n+1)²+2(n+1)+1=((n+1)+1)². Damit gilt sie auch für n+1.

Bei einer vollständigen Fallunterscheidung wird jeder mögliche Fall betrachtet; die Zahl der Fälle muss endlich sein, die Fälle müssen sich aber nicht gegenseitig ausschließen. Jede Primzahl p≥3 hat die Form p=4k±1: Von p=4k, 4k+1, 4k+2 und 4k+3=4(k+1)−1 sind die Fälle 4k und 4k+2 wegen Teilbarkeit nicht prim.

Das Schubfachprinzip besagt: Verteilt man n+1 Gegenstände auf n Schubfächer, enthält mindestens ein Fach zwei Gegenstände. Hat A⊂{1,2,…,2n} mindestens n+1 Elemente, gibt es daher a,b∈A mit a|b. Jedes Element hat die Form 2ᵏm mit ungeradem m; weil es nur n mögliche ungerade Teile m gibt, besitzen zwei Elemente denselben ungeraden Teil, und die kleinere der beiden Zahlen teilt die größere.

Beim ersten Cantorschen Diagonalverfahren zeigt eine Zuordnung natürlicher Zahlen zu allen Elementen die Abzählbarkeit einer Menge. Das zweite Diagonalverfahren nimmt indirekt Abzählbarkeit an und gewinnt einen Widerspruch, also Überabzählbarkeit. Die transfinite Induktion erweitert die vollständige Induktion auf wohlgeordnete Klassen: Bei Ordinalzahlen müssen der Fall 0, Nachfolgerordinalzahlen und zusätzlich Limesordinalzahlen behandelt werden.

Strategien und besondere Fachmethoden

Beweismethoden geben den grundsätzlichen Aufbau vor; Beweisstrategien helfen bei ihrer Umsetzung. Das Extremalprinzip wird besonders bei Existenzbeweisen verwendet. Es nutzt, dass an größtmöglichen oder kleinstmöglichen Objekten besondere Strukturen auftreten können. Grundlagen dafür sind etwa die Supremumseigenschaft – jede nichtleere, nach oben beschränkte Teilmenge der reellen Zahlen besitzt ein Supremum – und das Wohlordnungsprinzip: Jede nichtleere Menge natürlicher Zahlen enthält eine kleinste Zahl. Beim Beweis des Satzes von Sylvester-Gallai wird beispielsweise der Abstand eines Punktes p von einer Geraden G als extremales Objekt betrachtet.

Das Invarianzprinzip richtet den Blick auf Größen oder Eigenschaften, die bei Veränderungen unverändert bleiben. Es unterstützt Möglichkeits- und Unmöglichkeitsbeweise. Bei Schiebepuzzles mit einem freien Feld, etwa dem 15-Puzzle, kann es entscheiden, welche Konstellationen ineinander überführt werden können und welche nicht.

In der Analysis wird oft eine „konstruktive Null“ hinzuaddiert: Der Ausdruck bleibt gleich, aber eine hilfreiche Umformung wird möglich. Für eine konvergente Folge (aₙ) mit Grenzwert a gilt bei n,m≥N: |aₙ−aₘ|=|(aₙ−a)+(a−aₘ)|≤|aₙ−a|+|aₘ−a|<ε/2+ε/2=ε. Dazu wird 0=−a+a eingefügt. Somit ist jede konvergente Folge eine Cauchy-Folge.

In der Maßtheorie zeigt das Prinzip der guten Mengen Aussagen für alle Elemente einer σ-Algebra oder eines anderen Mengensystems; maßtheoretische Induktion betrifft vorgegebene Mengen messbarer Funktionen. In der homologischen Algebra dient die Diagrammjagd unter anderem zum Beweis des Fünferlemmas, Schlangenlemmas und Neunerlemmas.

Praktische Bedeutung und Computerbeweise

Beweise können praktische Folgen haben. Dazu gehört die eindeutige Darstellung ganzer Zahlen im Dezimal-, Dual- oder Hexadezimalsystem und in jedem anderen Stellenwertsystem. Der Hauptsatz der Differential- und Integralrechnung ist etwa für die Berechnung von Volumen und Oberflächen physischer Objekte sowie für Beschleunigung und andere physikalische Themen relevant. In der Informatik zeigt eine untere Schranke, dass n vergleichbare Objekte bei gegebener Hardware grundsätzlich nicht schneller als proportional zu n·log(n) sortiert werden können. Der Dijkstra-Algorithmus und der Bellman-Ford-Algorithmus liefern kürzeste Wege von Start- zu Zielknoten; ihre Grundlage sind kantengewichtete Graphen. Viele zahlentheoretische Beweise haben dagegen keine praktische Relevanz.

Maschinengestütztes Beweisen verwendet Programme, um vollständige formale Beweise mit Schritten und Zwischenergebnissen zu erzeugen und zu überprüfen. Davon unterscheidet sich ein Computerbeweis. Viele numerische Rechnungen sind kein allgemeingültiger Computerbeweis: Die Programmierung von Integralberechnungen wie der Simpsonregel beweist nicht den Hauptsatz der Differential- und Integralrechnung. Bekannte Beispiele maschinengestützten Beweisens sind der Vier-Farben-Satz und die Keplersche Vermutung. Ein früherer Beweisversuch zum Vier-Farben-Satz wurde später als unvollständig erkannt und widerlegt. Computerbeweise hängen nicht von der Zahl der Experimente oder untersuchten Dinge ab und haben nur bedingt das Problem von Messabweichungen.