1.8 Beweise

Die Mathematik hat als eine von wenigen Wissenschaften die Eigenschaft, dass alle Resultate der Vergangenheit (abgesehen von menschlichen Fehlern und gewissen Perioden, in denen wieder nach der korrekten Methode gesucht wurde) nach wie vor richtig sind (und nicht bloss in erster Näherung). Das Erfolgsrezept dafür liegt im Aufbau der Mathematik. Das Fundament bilden die Axiome (beispielsweise jene der Mengenlehre oder die Peano-Axiome der natürlichen Zahlen), die als bekannt und richtig angenommen werden. Mittels Definitionen werden neue Begriffe eingeführt und mittels Lemmata und Propositionen untersucht und in Verbindung zueinander gebracht, bis aus diesen Sätze und Theoreme bewiesen werden können. Selbstverständlich kann man bezweifeln, ob die so entstandenen Theorien interessant oder relevant sind. Über Interessen lässt sich natürlich streiten. Dennoch ist die Relevanz der heutigen mathematischen Theorien in vielen anderen Bereichen schwer zu bestreiten und dies obwohl wir in der Mathematik beispielsweise die $0$ und die Zahl $10^{-10^{80}}$ (mit so vielen Nullen nach dem Komma wie nach derzeitigen Schätzungen Atome im Weltall) strikt unterscheiden. Zu diesem Thema möchten wir dieses Video, basierend auf dem lesenswerten Artikel „The unreasonable effectiveness of mathematics in the natural sciences“ von Eugene Wigner, empfehlen. In eine ähnliche Richtung geht das für ein allgemeines Publikum gedachte Video mit geringerer Informationsdichte, das die teilweise überraschende Nützlichkeit der Mathematik in anderen Naturwissenschaften besonders hervorhebt.

Wir möchten an dieser Stelle einige Bemerkungen zu Beweisen machen. Ein Beweis, wie der Name schon sagt, soll die behauptete Aussage unter Verwendung von einfachen logischen Schritten aus vorher Bekanntem (zum Beispiel Axiomen) ableiten. Es gibt dafür einige Methoden, die wir zum Teil schon angewendet haben und die unter anderem auch verknüpft werden können.

Manche von Ihnen werden sich fragen, warum wir in dieser Vorlesung immer „diese Beweise“ besprechen müssen. Diese Frage lässt sich vielleicht mit der Frage an einen Physik-Professor vergleichen, wieso denn immer so viele Experimente durchgeführt werden müssen. Beweise sind im Aufbau der Mathematik unersetzlich. Selbst wenn Sie die hier entwickelte Theorie später möglicherweise nicht in der hier verwendeten Exaktheit und Genauigkeit benötigen, werden Sie bei aktiver Mitarbeit abstraktes Denken erlernen, welches für die Mathematik aber auch für andere Wissenschaften und in der Praxis äusserst nützlich sein wird.

1.8.1 Widerspruchsbeweise

Angenommen wir wollen eine Aussage $A$ beweisen. Dann ist es manchmal einfacher zu zeigen, dass $\neg A$ nicht sein kann, also zu einem Widerspruch führt, als direkt $A$ zu zeigen. Wir nennen $\neg A$ die indirekte Annahme und den Beweis einen Widerspruchsbeweis. Man spricht auch vom „Satz vom ausgeschlossenen Dritten“, da entweder $A$ oder $\neg A$ gelten muss und es keine dritte Möglichkeit gibt.†† Man sollte dabei darauf achten, dass die Aussage $A$ nicht von einer freien Variablen $x$ abhängt, denn wenn die Aussage eigentlich $\forall x\in X:A\left(x\right)$ ist, dann ist die Negation $\exists x\in X:\neg A\left(x\right)$ und nicht $\forall x\in X:\neg A\left(x\right)$.

1.8.2 Kontraposition

Sind $A,B$ zwei Aussagen, dann sind die Aussagen $A\Rightarrow B$ und $\neg B\Rightarrow \neg A$ äquivalent. Die Aussage $\neg B\Rightarrow \neg A$ wird die Kontraposition der Aussage $A\Rightarrow B$ genannt. Wie man sich dies in einem Beweis zunutze machen kann, wollen wir in einem Beispiel illustrieren.

Beispiel 1.84 (Überdeckungen mit Dreiecken).

Folgendes Beispiel entstammt dem Buch von Blatter [Bla03] (Kapitel 1, Seite 6). Sei $D$ das gleichseitige Dreieck mit Kantenlänge $2$ und sei $a$ eine Zahl kleiner als $2$. Wir betrachten folgende Aussagen:

$A\left(a\right)$: $D$ lässt sich mit $4$ gleichseitigen Dreiecken der Kantenlänge $a$ überdecken.

$B\left(a\right)$: $D$ lässt sich mit $5$ gleichseitigen Dreiecken der Kantenlänge $a$ überdecken.

Bei einer Überdeckung durch Dreiecke sind auch Überlappungen erlaubt. Wir behaupten nun, dass $\forall a>0:A\left(a\right)\iff B\left(a\right)$ gilt. Auf Grund deren Definitionen impliziert die Aussage $A\left(a\right)$ die Aussage $B\left(a\right)$; in Symbolen $A\left(a\right)\Rightarrow B\left(a\right)$. Wir fixieren $a>0$ und beweisen nun die Implikation $B\left(a\right)\Rightarrow A\left(a\right)$, in dem wir die Kontraposition $\neg A\left(a\right)\Rightarrow \neg B\left(a\right)$ beweisen. Wir nehmen $\neg A\left(a\right)$ an, also dass sich $D$ nicht mit $4$ gleichseitigen Dreiecken überdecken lässt. Dann muss $a<1$ gelten, denn sonst könnte man $D$ wie folgt mit Dreiecken der Kantenlänge $1$ (und also auch der Kantenlänge $a$) überdecken:

Gegeben eine Überdeckung von $D$ durch Dreiecke der Seitenlänge $a$, dann müssen die in obiger Grafik erhaltenen $6$ Punkte (unten in rot markiert)

in jeweils verschiedenen gleichseitigen Dreiecken der Kantenlänge $a$ enthalten sein, da wir bereits erkannt haben, dass die Kantenlänge $a$ kleiner als $1$ ist. Insbesondere sind mindestens $6$ solche Dreiecke notwendig, um $D$ zu überdecken; also gilt $\neg B\left(a\right)$.

1.8.3 Induktionsbeweise

Wir haben die Beweismethode der vollständigen Induktion schon im Beweis von Lemma 1.3 gesehen (und wissen jetzt, dass diese Methode genau einem definierenden Axiom von $\mathbb{N}$ entspricht). Diese wird verwendet, um eine Aussage $A\left(n\right)$ für alle natürlichen Zahlen $n$ zu zeigen. Der Induktionsbeweis hat zwei wichtige Teilschritte:

Man kann einen Beweis mit vollständiger Induktion mit einem rekursiven Algorithmus vergleichen, der die Aussage für alle natürlichen Zahlen beweist: Wenn man wissen will, warum die Aussage für $n=10$ stimmt, dann zeigt der Induktionsschritt, dass die Aussage stimmt, weil sie schon für $n=9$ richtig ist. Die Aussage für $n=9$ stimmt wiederum, weil sie für $n=8$ stimmt und so weiter bis man bei $n=1$ angelangt ist. Der Fall $n=1$ verankert (daher „Induktionsverankerung“) die Rekursion und den Beweis, da wir diesen Fall direkt und ohne Annahme einer anderen, noch zu verifizierenden Aussage überprüfen. Im nächsten Kapitel werden wir weitere Varianten des Induktionsbeweises kennenlernen.

Wir möchten auch etwas „geometrischere“ Probleme behandeln.

Beispiel 1.86 (Eine geometrische Induktion).

Sei $n$ eine natürliche Zahl. Wir betrachten das Quadrat mit Kantenlänge $2^n$, aus dem ein kleines Quadrat der Kantenlänge $1$ entfernt wurde.

Bei diesen beiden Quadraten und auch bei allen noch zu erscheinenden Konstrukten möchten wir nur Ecken an ganzzahligen Stellen (d.h. in ${\mathbb{Z}}^2$) zulassen. Wir behaupten nun, dass sich das obige „Quadrat mit Loch“ durch Objekte der Art (rotieren ist erlaubt)

abdecken lässt und beweisen dies per Induktion über $n$. Zum Induktionsanfang $n=1$: Das grössere Quadrat hat Kantenlänge $2$, also ist das Bild

und die Aussage stimmt. Angenommen wir wissen, dass die Behauptung für $n$ korrekt ist. Wir zerlegen das Quadrat mit Kantenlänge $2^{n+1}$ in $4$ Quadrate der Kantenlänge $2^n$ und entfernen aus einem dieser Quadrate ein kleines Quadrat der Kantenlänge $1$. Zusätzlich entfernen wir aus den anderen Quadraten je ein kleines Quadrat wie in folgendem Bild

Die $4$ so entstandenen Objekte (Quadrate mit Loch) lassen sich aber jeweils abdecken nach dem Induktionsschritt, also folgt die Behauptung.

Vollständige Induktion ist ein unentbehrliches Hilfsmittel für Beweise in der Mathematik, genauso wie die Rekursion als Programmiermethode in der Informatik. Manchmal hat man jedoch das Gefühl, dass Induktion zwar den Zweck erfüllt (also das Lemma, die Proposition oder den Satz beweist), aber trotzdem nicht erklärt, warum eine Aussage richtig sein soll. Ein Beispiel dazu liefert Lemma 1.3, da wir aus dem Beweis beispielsweise nicht erkennen können, wie wir das Lemma für $1^4+2^4+3^4+\cdots +n^4$ verallgemeinern könnten. Vielleicht würden Sie vermuten, dass diese Summe gleich einem Ausdruck der Form $\frac{n^5}{5}+a{n}^4+b{n}^3+c^2+dn+e$ für gewisse rationale Zahlen $a,b,c,d,e$ ist. Es fragt sich jedoch, wie wir diese Konstanten finden könnten. Die Induktionsmethode ist dabei nicht sehr hilfreich, da sie verwendet werden kann um die Wahrheit zu bestätigen, wenn man sie woanders bereits gefunden hat. Wir werden einen zweiten allgemeineren Beweis von Lemma 1.3 im Abschnitt 3.3 besprechen.

1.8.4 Das Schubfachprinzip

Mancher Existenzbeweis kann auf das Schubfachprinzip (Proposition 1.75) zurückgeführt werden. Ein Beispiel aus dem Alltag haben wir gleich nach Proposition 1.75 erklärt. Hier möchten wir das Schubfachprinzip an einem mathematischen Beispiel illustrieren.

Das Schubfachprinzip ist gemeinsam mit vielen Weiterentwicklungen eine sehr verbreitete Beweismethode in der Mathematik. Die allgemeine Einsetzbarkeit hat aber gewissermassen auch einen Preis, denn wenn das Schubfachprinzip für einen Existenzbeweis verwendet wird, so gibt der Beweis meist keinerlei Aufschlüsse, wie man denn das Objekt (im Beispiel die konkrete, durch 17 teilbare Zahl) effektiv (also abgesehen von ausprobieren) finden könnte.

1.8.5 Weitere Methoden

Es gibt noch viele weitere Beweismethoden. Beispielsweise gibt es Aussagen, die in verschiedenen Fällen einfachere (aber verschiedene) Beweise haben. Falls diese Fälle alle Möglichkeiten abdecken, haben wir den Beweis der Aussage mittels Fallunterscheidung erhalten.

Ein anderes Beispiel einer Beweismethode (vor allem aus der Kombinatorik) ist die folgende: Angenommen wir wollen die endliche Kardinalität einer Menge bestimmen. Mit Hilfe einer geschickt gewählten Bijektion von dieser Menge in eine andere kann man dieses Zählproblem an einen Ort transportieren, wo man die Antwort einfacher zu finden ist oder bereits kennt.

Wir haben auch bereits erwähnt, dass manche Beweise sozusagen durch die Definitionen der involvierten Objekte erzwungen werden. Letzteres können Sie aber nur bemerken, wenn Sie die bereits besprochenen Definitionen im Gedächnis haben. Wir werden klare Fälle derartiger Beweise im eSkript als 🪆 Matrjoschkabeweise kennzeichnen, da diese Beweise aus mehreren Schichten bestehen, die genauso wie die russischen Matrjoschkapuppen auf nur eine Art und Weise vernünftig zusammengebaut werden können. Bei Auffinden der Matrjoschkapuppe im eSkript, empfehlen wir Ihnen den folgenden Beweis eigenständig nach folgendem Schema zu formulieren: Angenommen wir wollen für bereits definierte Aussagen $A,B,C$ zeigen, dass $A\wedge B$ die Aussage $C$ impliziert. Wenn sie die Definition von $C$ nachsehen, wird dort üblicherweise wiederum eine Vorraussetzung über die Objekte (Zahlen, Vektoren, Funktionen, …) von Interesse auftauchen. Nun nehmnen sie diese Vorraussetzung und erinnern sich an die Definitionen von $A$ und $B$, mit dem Ziel zu sehen, was sie mit der Vorraussetzung in $C$ zum Beispiel mittels $A$ erhalten können. Diese Aussage ist dann aber vielleicht genau die Vorrausetzung in $B$, womit sie eine weitere Aussage über die Objekte erhalten. Mit etwas Glück ist dies nun die gewünschte Aussage, die in $C$ behauptet wird, und sie haben damit $A\wedge B\Rightarrow C$ bewiesen. Dieses Schema tauchte zum Beispiel im Beweis von Lemma 1.40(i) auf, wobei in diesem Fall $A,B,C$ jeweils die Injektivität der Funktionen $g,f,g\circ f$ besagten. Mit Übung werden sie dieses Schema aber auch in deutlich komplizierteren Beweisen zumindest teilweise wiederfinden.

1.8.6 Ansprüche an Beweise

Wie bereits angedeutet, gibt es mehrere Wünsche, die man an einen Beweis stellen könnte. In erster Linie muss dieser natürlich einen vollständigen Beweis darstellen, doch könnte man sich auch folgende Punkte wünschen: Der Beweis könnte eine gute Erklärung für die Aussage liefert, könnte Verallgemeinerungen zulassen oder könnte bereits als Anleitung gelesen werden, wie man aus dem Existenzbeweis einen Algorithmus zum Auffinden des gesuchten Objektes erstellen kann. Für all diese Aussagen werden wir viele Beispiele sehen. Das Auffinden eines zweiten Beweises einer Aussage ist zwar logisch gesehen unnötig (und für uns aus Zeitgründen oft nicht möglich), kann aber mitunter diese weiteren Wünsche besser abdecken und insgesamt das Verständnis der Theorie stärken.

1.8.7 Beweise finden

Sie fragen sich vielleicht bereits, wie man Beweise (wie zum Beispiel für die Übungen) finden kann. Die Antwort ist mit Übung, Hartnäckigkeit und Glück. Des Weiteren empfehlen wir Ihnen, Beweise aus der Vorlesung, diesem Skript oder anderer Literatur aus dem Gedächtnis zu wiederholen. Dadurch bekommen Sie Übung und ein gewisses Gespür für die inneren Mechanismen von Beweisen. Zusätzlich erkennen Sie vielleicht, dass viele Beweise ähnliche Bauformen aufweisen. Wenn sie die frühere Beweise bereits im Gedächnis haben, so werden sie diese Ähnlichkeiten schneller sehen und Teile dieser Beweise wiederverwenden können.

1.8.8 Beweise aufschreiben

Nachdem Sie die Idee für den Beweis gefunden haben, wollen Sie diesen kommunizieren und aufschreiben. Auch dazu ist (viel) Übung nötig und Sie müssen den Beweis vielleicht umstellen oder komplett neu formulieren, bevor er für andere verständlich wird (was das Ziel sein sollte). Mitunter ist die Reihenfolge der Argumente, wie man sie gefunden hat, möglicherweise komplett anders als die Reihenfolge der Argumente, wie man sie präsentieren sollte. Weiters darf ein Beweis nicht nur aus Formeln bestehen, sondern muss dieser auch die Gedanken enthalten, die diesen Formeln Sinn und Zusammenhang geben. Wir verweisen auf [SS12] und das Buch „ Das ist o.B.d.A. trivial“ ([Beu09]) von Beutelspacher für weitere Tipps in diese Richtung.

An dieser Stelle möchten wir noch die Wörter „o.B.d.A.“ und „trivial“ im obigen Buchtitel kommentieren. Die Abkürzung „o.B.d.A.“steht für „ohne Beschränkung der Allgemeinheit“. Wir verwenden diese, wenn wir den Beweis einer Aussage auf den Beweis eines Spezialfalls reduzieren. Folgendes Beispiel illustriert dies:

Das Wort „ trivial“ (abgeleitet von lat. „trivium“) bedeutet „bekannt“ oder „allgemein bekannt“ und sollte entgegen dem üblichen Gebrauch nicht mit dem Wort „offensichtlich“ verwechselt werden. Wenn also „…ist trivial“ geschrieben wird, so sollte man dies als Aufforderung verstehen, zu verifizieren, wieso genau die Aussage „bekannt“ sein sollte. Dennoch werden wir und sollten Sie auf den Gebrauch dieses Wortes komplett verzichten. Selbiges betrifft Wörter wie

oder Phrasen wie

Grund dafür ist, dass diese Ausdrücke aus Sicht des Lesers als Affront aufgefasst werden können; es liegt nicht an der Verfasserin oder dem Verfasser, die Schwierigkeit einer Aussage zu beurteilen, die sie oder er selbst hingeschrieben hat. Des Weiteren kann man eine (vermeintlich) einfache Aussage oft auch in wenigen Worten erklären.

1.8.9 Beweise lesen

Ein wichtiger erster Schritt ist die zu beweisende Aussage zu lesen, zu verstehen und zu erkennen, was überhaupt zu beweisen ist. Wenn Sie dann den Beweis lesen, dann sollten Sie jeden Schritt hinterfragen und dabei fast so stur wie ein Computer beim Abarbeiten eines Programms vorgehen. Man kann dazu auch das Motto der Royal Society zitieren:

„Nullus in verba“ oder „Take nobody’s word for it“.

Sollten Sie einen Schritt nicht verstehen oder nicht einsehen, wieso dieser möglich sein soll, dann fragen Sie bei Mitstudenten, bei Assistenten oder beim Professor nach, bis Sie eine zufriedenstellende Antwort bekommen haben. Bemühen Sie sich jetzt, wo die Themen noch nicht so verflochten sind, ein vollständiges Verständnis der besprochenen Begriffe und Sätze zu entwickeln, und warten Sie nicht darauf bis die Themen „interessanter“ werden. Denn dann werden diese auch schwieriger und es wird zunehmend schwieriger werden, den Einstieg zu finden.

Umgekehrt sollten Ihre Beweise auch so aufgeschrieben sein, dass auch ein sturer Leser nicht umhin kommt, die von Ihnen bewiesene Aussage zu akzeptieren. Es hilft, wenn Sie Ihren Beweis einen oder zwei Tage später nochmals lesen, da es für Sie dann wahrscheinlich leichter ist, bewusst zu vergessen, was Sie sich beim Niederschreiben gedacht haben und dann vielmehr lesen, was Sie tatsächlich niedergeschrieben haben.

1.8.10 Prädikatenlogik vs Umgangssprache

Wir werden unsere Beweise in der Umgangssprache (also in Deutsch anstatt in formalen Symbolen) formulieren, doch empfehlen wir Ihnen, die Übersetzung zwischen Umgangssprache und Prädikatenlogik zu üben. Wenn wir die Analogie zur Informatik etwas weiter ziehen, dann sollten Sie die Prädikatenlogik als Maschinensprache der Beweise verstehen und die Umgangssprache als die höhere Programmiersprache, die es uns Menschen leichter machen wird, Zusammenhänge zu sehen, eine Intuition für die Theorie zu entwickeln und Konversationen über den Beweis zu führen. Der Autor eines Beweises muss also „als Programmierer“ sicherstellen, dass die umgangssprachliche Formulierung ohne Zweideutigkeiten in die Prädikatenlogik übersetzt werden kann. Genauso sollte der Leser die Rolle des „sturen Computers“ spielen und überprüfen, ob der Beweis „ ohne Fehler abläuft“.

Wir werden anfangs unsere Diskussionen näher an der Prädikatenlogik halten und mitunter (entgegen üblichen mathematischen Konventionen) auch die Quantoren $\forall ,\exists ,\exists !$ in Symbolen verwenden. Doch werden wir sehen, dass weder die Lineare Algebra noch die Analysis sinnlose Formelsammlungen in Buchstaben und den Symbolen $\neg$, $\wedge$, $\vee$, $\Rightarrow$, $\iff$, $\forall$, $\exists$, $\exists !$, $=$, $\in$, $\subseteq$, …bilden. Vielmehr stellen sie zwei sehr massive Gebäude mit vielen Stockwerken, interessanten Verzierungen und Erkern sowie mehreren Brücken zwischen einander und anderen Gebäuden dar. Wenn Sie das „Gebäude“ der Linearen Algebra oder das „Gebäude“ der Analysis verstehen wollen, dann müssen Sie zwar die einzelnen Bausteine (in Form von Definitionen, Lemmata und Sätzen), aber eben auch den Lageplan des Gebäudes (das wären die Zusammenhänge) kennen. Es sind diese Zusammenhänge, die in umgangsprachlich formulierten Beweisen klarer werden.

Wir wollen Ihnen am Ende des Hauptteiles dieses Kapitels noch einen Podcast der BBC empfehlen, der neben geschichtlichen Informationen auch noch eine Zusammenfassung vieler Themen dieses Kapitels bietet.