Beweis (Mathematik)

aus Wikipedia, der freien Enzyklopädie
Datei:Aufbau eines Beweises.svg
Beispielhafter, schematischer Aufbau eines Beweises

Ein Beweis ist in der Mathematik die als fehlerfrei anerkannte Herleitung der Richtigkeit bzw. der Unrichtigkeit einer Aussage aus einer Menge von Axiomen, die als wahr vorausgesetzt werden, und anderen Aussagen, die bereits bewiesen sind. Man spricht daher auch von axiomatischen Beweisen.

Umfangreichere Beweise von mathematischen Sätzen werden in der Regel in mehrere kleine Teilbeweise aufgeteilt, siehe dazu Satz und Hilfssatz.

In der Beweistheorie, einem Teilgebiet der mathematischen Logik, werden Beweise formal als Ableitungen aufgefasst und selbst als mathematische Objekte betrachtet, um etwa die Beweisbarkeit oder Unbeweisbarkeit von Sätzen aus gegebenen Axiomen selbst zu beweisen.

Konstruktive und nicht-konstruktive Beweise

Existenzbeweise

Bei einem konstruktiven Existenzbeweis wird entweder die Lösung selbst genannt, deren Existenz zu zeigen ist, oder ein Verfahren angegeben, das zur Lösung führt, das heißt, es wird eine Lösung konstruiert.

Bei einem nicht-konstruktiven Beweis wird anhand von Eigenschaften auf die Existenz einer Lösung geschlossen. Manchmal wird sogar indirekt die Annahme, es gäbe keine Lösung, zum Widerspruch geführt, woraus folgt, 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: Die Funktion mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x) = 2x - 1} besitzt im Intervall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [0,1]} mindestens eine Nullstelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0} .

Konstruktiver Beweis: Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0 = 0{,}5} . Dann gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x_0) = 2\cdot x_0 - 1 = 2\cdot 0{,}5 - 1 = 1 - 1 = 0} . Ferner liegt im Intervall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [0,1]} . Damit ist die Behauptung bewiesen. Die Nullstelle ist sogar mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0 = 0{,}5} angegeben.

Nicht-konstruktiver Beweis: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} ist stetig. Ferner ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(0) = -1 < 0} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(1) = 1 > 0} . Nach dem Zwischenwertsatz für stetige Funktionen folgt die Behauptung. Über den Wert der Nullstelle liefert dieser Beweis jedoch keine Information.

Mengenlehre

In der auf dem Axiomensystem ZFC aufbauenden Mengenlehre nennt man Beweise nicht-konstruktiv, wenn sie das Auswahlaxiom 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 (der mathematische Konstruktivismus vermeidet bewusst das Auswahlaxiom), daher rührt seine Sonderstellung nicht nur in der abstrakten Mengenlehre, sondern auch bei Beweisen in anderen Teilgebieten der Mathematik. In diesem Sinne gelten alle Beweise, die das Lemma 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 die Kontinuumshypothese oder ihre Negation verwendet.

Formale Beweise

Formale Beweise reduzieren die Beweisschritte auf eine Reihe definierter Operationen auf Zeichenketten. Solche Beweise können in der Regel nur mit Maschinenunterstützung erstellt werden (siehe etwa Coq (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.

Beweismethoden

Einige mathematische Sätze oder logische Schlussregeln 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 als Beweismethode, Beweisverfahren, Beweistechnik oder Beweisprinzip. 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 in intuitionistischer Logik, und eine transfinite Induktion über alle Kardinalzahlen nur unter Voraussetzung des Wohlordnungssatzes möglich). Hier eine Auswahl von Standard-Beweismethoden:

Direkter Beweis

Für einen direkten 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} ist stets ungerade.

Beweis: Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} eine ungerade natürliche Zahl. Das heißt, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} lässt sich darstellen als , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} eine natürliche Zahl oder Null ist. Daraus folgt mit Hilfe der ersten binomischen Formel

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^2 = (2k+1)^2 = 4k^2+4k+1 = 2 \cdot (2k^2+2k)+1} .

Aus der Möglichkeit, so darzustellen folgt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^2} ungerade ist.

Indirekter Beweis

Bei einem indirekten 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 Behauptung falsch 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} eine natürliche Zahl, so ist diese gerade.

Beweis: Angenommen, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sqrt{n} = k} wäre ungerade. Dann ist auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k^2 = n} 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.

Ein weiteres klassisches Beispiel:

Behauptung: Die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sqrt{2}} ist irrational.

Beweis: Angenommen, diese Zahl wäre rational. Dann kann man sie als Bruch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sqrt{2} = \tfrac{l}{k}} darstellen, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} natürliche Zahlen und ohne Beschränkung der Allgemeinheit teilerfremd sind (sonst kann man den Bruch soweit kürzen, bis das der Fall ist). Daraus folgt durch Quadrieren

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 = \frac{l^2}{k^2} \,} , also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \, l^2 = 2 k^2.}

Folglich ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l^2} eine gerade Zahl. Da die Wurzel aus einer geraden Quadratzahl auch gerade ist (siehe vorangegangene Behauptung), ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l} selbst gerade, also ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac{l}{2}} eine natürliche Zahl. Durch Umformung der letzten Gleichung erhält man

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k^2 = \frac{l^2}{2} = 2 \cdot \left(\frac{l}{2}\right)^2.}

Das zeigt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k^2} und somit auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} gerade natürliche Zahlen sind. Also sind und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} beide gerade und haben somit beide den Teiler 2. Damit sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} nicht teilerfremd – im Widerspruch zu der Annahme ihrer Teilerfremdheit. Also ist auch die ursprüngliche Annahme, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sqrt{2}} sei rational, falsch.

Vollständige Induktion

Datei:Veranschaulichung der vollständigen Induktion.svg
Veranschaulichung der vollständigen Induktion

Der Beweis durch vollständige Induktion ist ein oft angewendetes Verfahren zum Beweis von Sätzen der Form „Für jede natürliche Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} gilt …“. Dazu zeigt man zuerst, dass die Aussage für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n = 0} (oder auch einen anderen Anfangswert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n_0} ) gilt, und danach, dass sie immer auch für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n+1} gilt, wenn sie für ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} gilt. Die vollständige Induktion lässt sich mit einem Domino-Effekt veranschaulichen. Man stellt die Steine so auf, dass, wenn einer umfällt, auch immer der nächste umfällt (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} → Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n+1} ), und stößt den ersten Stein um (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n = 0} ).

Ein einfaches Beispiel:

Behauptung: Es gilt für alle natürlichen Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} : Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 + 3 + \dotsb + (2n+1) = (n+1)^2}

Beweis:

  1. Die Behauptung gilt für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n = 0} : Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (2\cdot 0+1) = 1 = (0+1)^2} ist eine wahre Aussage.
  2. Die Behauptung sei für ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} gültig. Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n+1} untersucht man die Summe
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 + 3 + \dotsb + (2n+1) + (2n+3)}
Da die Behauptung für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} gültig ist, folgt
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} 1 + 3 + \dotsb + (2n+1) + (2n+3) &= (n+1)^2 + (2n+3) \\ &= (n+1)^2 + 2(n+1) + 1 \\ &= ((n+1) + 1)^2 \end{align}}
Also gilt die Behauptung auch für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n+1} , damit ist die Aussage nach dem Induktionsprinzip bewiesen.

Vollständige Fallunterscheidung

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: Jede Primzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p \ge 3} hat die Form Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 4 \cdot k \pm 1} mit einer natürlichen Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} .

Beweis: Man unterscheidet folgende vier Fälle für die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} , von denen immer genau einer eintritt:

  1. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 4k}
  2. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 4k + 1}
  3. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 4k + 2}
  4. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 4k + 3 = 4(k+1) - 1}

Im ersten dieser Fälle ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} durch 4 teilbar und damit keine Primzahl, im dritten Fall ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} durch 2 teilbar und somit ebenfalls keine Primzahl. Also muss einer der Fälle zwei oder vier eintreten, das heißt, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} hat die Form Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 4 \cdot k \pm 1} mit einer natürlichen Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} .

Es sei angemerkt, dass die Fallunterscheidung zwar vollständig sein muss, aber die untersuchten Fälle sich nicht gegenseitig ausschließen müssen.

Diagonalverfahren

Die Diagonalverfahren wurden von Georg Cantor zum Beweis zweier spezieller Aussagen entwickelt. Sie haben sich seitdem als allgemeine Beweismethoden bewährt.

Das erste Cantorsche Diagonalverfahren ist ein direkter 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.

Das zweite Cantorsche Diagonalverfahren ist ein indirekter Beweis fü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.

Schubfachprinzip/Taubenschlagprinzip

Das Schubfachprinzip geht auf den deutschen Mathematiker Dirichlet zurück und kann sehr anschaulich formuliert werden: Verteilt man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n+1} Gegenstände auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Schubfächer, dann befinden sich in mindestens einem Schubfach mindestens zwei Gegenstände. Als Beispiel betrachten wir:

Behauptung: Hat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A\subset \{1,2,\ldots,2n\}} mindestens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n+1} Elemente, so gibt es Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a,b\in A} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a|b} .

Beweis: Alle Elemente aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} haben die Gestalt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^km} mit einer ungeraden Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} . Von diesen gibt es aber nur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} verschiedene in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{1,2,\ldots,2n\}} , so dass eine ungerade Zahl bei obiger Zerlegung der mindestens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n+1} Zahlen aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} zweimal vorkommen muss (das ist das Schubfachprinzip). Daher enthält Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} zwei Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^km} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^lm} mit derselben ungeraden Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} . Offenbar teilt die kleinere die größere.[1]

Transfinite Induktion

Bei der transfiniten Induktion wird die vollständige Induktion auf beliebige wohlgeordnete Klassen verallgemeinert.

Häufig hat man es mit Aussagen über alle Ordinalzahlen zu tun. Wie auch bei der oben vorgestellten vollständigen Induktion in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \N} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0,1,2,\ldots} . Man erhält dann die gewöhnliche vollständige Induktion in den natürlichen Zahlen, denn diese sind die Ordinalzahlen bis zur ersten Limesordinalzahl.

Beweisstrategien

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.

Extremalprinzip

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, das 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 ein Supremum, 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)

Invarianzprinzip

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]

Nahrhafte Null

Beweise in der Analysis 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 jede konvergente Folge eine Cauchy-Folge ist, so bedient man sich einer nahrhaften Null Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0=a-a} , um die Dreiecksungleichung auszunutzen. Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a_n)_{n\in \mathbb{N}}} eine beliebige konvergente Folge und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} ihr Grenzwert. Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon>0 } , dann gibt es nach Definition der (Folgen-)Konvergenz ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N\in \mathbb{N}} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |a-a_n|<\frac{\varepsilon}{2}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |a-a_m|<\frac{\varepsilon}{2}} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n,m\geq N} . Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n,m\geq N} nun beliebig, so gilt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |a_n-a_m|=|a_n\overbrace{-a+a}^{=0}-a_m|=|(a_n-a)+(a-a_m)|\leq |a_n-a|+|a_m-a|<\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon }

Somit ist jede konvergente Folge sogleich eine Cauchy-Folge, was zu beweisen war. Der Beweis lebt vom Hinzuaddieren einer nahrhaften Null im zweiten Schritt.

Siehe auch

Literatur

Weblinks

Wikibooks: Mathe für Nicht-Freaks: Beweis – Lern- und Lehrmaterialien
Wikibooks: Beweisarchiv – Lern- und Lehrmaterialien

Einzelnachweise

  1. ↑ M. Aigner, G. M. Ziegler: Proofs from THE BOOK, Springer-Verlag 1998, ISBN 3-540-63698-6, Kapitel 20: Pigeon-hole and double counting.
  2. ↑ 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.
  3. ↑ 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.
Abgerufen von „https://de.wikiup.org/index.php?title=Beweis_(Mathematik)&oldid=223970767“