_02-Beweise.tex

\setchapterpreamble[c][.7\textwidth]{\itshape\color{gray}\small
    In diesem Vortrag werden die grundlegenden logischen Schlussregeln und Beweistechniken erklärt und anhand von Beispielbeweisen vorgestellt. Dabei werden auch vorherrschende Normen für das Schreiben schöner und gut lesbarer Beweise besprochen.
\vspace{24pt}}

    
\chapter{Beweise} \label{chap:beweise}


\section{Logisches Schließen}


\begin{bem}[Buchtipp]
    Dieses Vorkurs-Kapitel bietet nur einen Crashkurs im Beweisen. Eine freundliche und weit ausführlichere (aber auch sehr seitenstarke) Darstellung bietet das Buch \cite{Vel06}. Über den Link im Literaturverzeichnis kannst du es als Pdf herunterladen.
\end{bem}


\begin{defin} \index{Schlussregel} \label{schlussregel}
    Eine \textbf{logische Schlussregel} ist ein Prinzip der Gestalt „Aus den Aussagen $X$ kann auf die Aussage $Y$ geschlossen werden“. Die Aussagen $X$ heißen dabei die \textbf{Prämissen} der Schlussregel und die Aussage $Y$ heißt ihre \textbf{Konklusion}. Die Anwendung einer Schlussregel heißt \textbf{logische Schlussfolgerung} oder auch \textbf{deduktiver Schluss}.
\end{defin}


\begin{bsp} \label{bsp:schlussregel}
    Seien $A,B$ irgend zwei Aussagen. Die Schlussregel \emph{Modus tollens} (die später in \cref{reductio} eingeführt wird) geht folgendermaßen:
    \[\begin{tabular}{r}
        $A\to B$ \\
        $\neg B$ \\
        \midrule
        $\neg A$
    \end{tabular}\]
    Sie besagt: „Aus $A\to B$ und $\neg B$ kann auf $\neg A$ geschlossen werden.“ Die Prämissen dieser Schlussregel sind $A\to B$ und $\neg B$ und die Konklusion ist $\neg A$.
    
    Die folgenden Schlüsse stellen drei \emph{Instanzen} dieser Schlussregel dar:
    \begingroup
    \allowdisplaybreaks
    \begin{align*}
        & \begin{tabular}{l}
            Wäre ich reich, würde ich jeden Tag ins Restaurant gehen. \\
            Ich gehe nicht jeden Tag ins Restaurant. \\
            \midrule
            Also gilt: Ich bin nicht reich.
        \end{tabular} \\[1em]
        & \begin{tabular}{l}
            Ist $n$ eine gerade Zahl, so ist auch $3n$ eine gerade Zahl. \\
            $3n$ ist keine gerade Zahl. \\
            \midrule
            Also gilt: $n$ ist keine gerade Zahl.
        \end{tabular} \qquad (n\in \N) \\[1em]
        & \begin{tabular}{l}
            Wenn der Fluxkompensator in Unwucht gerät, misslingt der Chronosprung. \\
            Der Chronosprung ist gelungen. \\
            \midrule
            Also gilt: Der Fluxkompensator ist nicht in Unwucht geraten.
        \end{tabular}
    \end{align*}
    \endgroup
    Obwohl die drei Schlüsse inhaltlich grundverschieden sind, haben sie dieselbe logische Struktur gemein.
\end{bsp}


\begin{defin}[Axiom] \index{Axiom}
    In der Regel liegen einer mathematischen Theorie einige Aussagen zugrunde, die nicht bewiesen, sondern schlicht als „gegeben“ vorausgesetzt werden. Sie heißen \textbf{Axiome} und kodieren oftmals Eigenschaften derjenigen Objekte, von denen die Theorie handelt.
\end{defin}


\begin{defin}[„Es gilt\dots“]
    Sei $A$ eine Aussage. Wir schreiben „$A$ ist gültig“ oder „Es gilt $A$“ oder „$A$ ist wahr“, falls es möglich ist, die Aussage $A$ mit einer Abfolge logischer Schlussfolgerungen aus den im Kontext angenommenen Axiomen herzuleiten.
\end{defin}
 
 
\begin{bem}[* Beweisbarkeit vs. Wahrheit] \label{beweisbarvswahr}
    Beachte, dass dies erst einmal nichts mit dem Wahrheitswert „w“ aus \cref{def:interpretation} zu tun hat. Wahrheit und Herleitbarkeit sind zwei verschiedene Dinge. Zumindest gibt es folgende Zusammenhänge:
    \begin{itemize}
        \item Die logischen Schlussregeln sind so beschaffen, dass sich aus wahren Prämissen auch nur wahre Konklusionen ableiten lassen. Man nennt dies die \emph{Korrektheit} (englisch: ``soundness'') der Schlussregeln. Wenn du aus wahren Prämissen etwas Falsches hergeleitet hast, muss dir zwangsläufig ein Fehlschluss unterlaufen sein.
        \item Aus falschen Prämissen lassen sich dagegen sowohl wahre als auch falsche Aussagen herleiten. Dennoch ändert dies nichts an der Korrektheit. Unabhängig davon, ob $3n$ nun „in Wirklichkeit“ eine gerade Zahl ist oder nicht, ist der Schluss aus \cref{bsp:schlussregel} korrekt, weil er eben nur von einer solchen Situation handelt, in der die Prämissen als wahr vorausgesetzt sind.
        \item Lässt sich jede wahre Aussage mittels logischer Schlüsse herleiten, so heißt der Logikkalkül \emph{vollständig}. Die Vollständigkeit ist eine weitaus kompliziertere Angelegenheit als die Korrektheit und in der mathematischen Logik gibt es diverse \href{https://ncatlab.org/nlab/show/completeness+theorem}{Vollständigkeitssätze} und \href{https://ncatlab.org/nlab/show/incompleteness+theorem}{Unvollständigkeitssätze} (deren berühmteste diejenigen von Gödel\footnote{\href{https://de.wikipedia.org/wiki/Kurt_G\%C3\%B6del}{Kurt Gödel (1906-1978)}} sind), die die Vollständigkeit und Unvollständigkeit gewisser Logikkalküle hinsichtlich gewisser Interpretationen beweisen.
    \end{itemize}
\end{bem}


\begin{defin}[Satz und Beweis] \index{Beweis}
    Ein \textbf{mathematischer Satz} ist die Feststellung in einem mathematischen Text, dass eine Aussage $A$ „gilt“, d.h. dass sie vermöge der in der Mathematik üblichen logischen Schlussregeln aus denjenigen Aussagen, die im Umfeld des Satzes axiomatisch angenommen werden oder bereits für gültig befunden wurden, hergeleitet werden kann.
    
    Ein \textbf{mathematischer Beweis} für $A$ ist eine (mehr oder weniger ausführliche) Beschreibung einer solchen Herleitung, die dich von der Gültigkeit von $A$ überzeugt.
\end{defin}


\begin{bsp}[*]
    In der synthetischen affinen und projektiven Geometrie ist die Aussage
    \begin{quote}
        (A) Durch je zwei verschiedene Punkte verläuft genau eine Gerade.
    \end{quote}
    ein Axiom, das nicht hergeleitet wird, sondern einen Teil unseres Verständnisses von „Punkten“ und „Geraden“ kodiert. Allein aus diesem Axiom kann nun schon die folgende Aussage hergeleitet werden:
    \begin{satz}
        Zwei verschiedene Geraden schneiden sich in höchstens einem gemeinsamen Punkt.
    \end{satz}
    \begin{proof}
        Seien $g,h$ zwei verschiedene Geraden, die sich in zwei Punkten $P$ und $Q$ schneiden. Weil es dann mehr als eine Gerade gibt, die durch $P$ und $Q$ verläuft, können $P,Q$ nach (A) nicht verschieden sein, sodass $P=Q$.
    \end{proof}
\end{bsp}


\begin{bem}[*]
    Dieser Beweis behält seine Gültigkeit auch dann, wenn das Wort „Gerade“ überall durch das Wort „Bierkrug“ ersetzt wird: Wenn durch je zwei verschiedene Punkte stets genau ein Bierkrug verläuft, so schneiden sich zwei verschiedene Bierkrüge in höchstens einem gemeinsamen Punkt. Dies ist typisch für die Logik: für die Gültigkeit logischer Schlüsse kommt es gar nicht auf den Inhalt der Aussagen an, sondern nur auf ihre Struktur. Beispielsweise ist es auch für die Korrektheit des dritten Schlusses aus \cref{bsp:schlussregel} völlig egal, was eigentlich „Fluxkompensator“ und „Chronosprung“ überhaupt bedeuten.
\end{bem}


\begin{bem}[Ausführlichkeit eines Beweises]
    Komplizierte Beweise involvieren dutzende logische Schlussfolgerungen und ein Mathe-Lehrbuch würde, schriebe man alle Beweise in größter Ausführlichkeit auf, den halben Regenwald verschlingen. Daher listen mathematische Beweise selten jede einzelne logische Schlussfolgerung auf, sondern beschreiben mehrere logische Schlüsse auf einmal und führen „Routine-Argumente“, von denen erwartet werden kann, dass sie der Leser mit Leichtigkeit selbst ergänzen kann, gar nicht erst aus. Aus der Schule bist du es ja auch gewohnt, in einer langen Rechnung nicht jeden einzelnen Rechenschritt separat aufzuschreiben, sondern mitunter mehrere Zwischenschritte auf einmal durchzuführen. Im extremsten Fall wird in einem Beweis gar nicht argumentiert, sondern es wird lediglich behauptet, die Aussage gelte „offensichtlicherweise“ oder „sei klar“. In vielen Fällen sind solche Aussagen tatsächlich „offensichtlich“; manchmal kommt es aber auch vor, dass der Prof. selbst nicht weiß, dass die Zwischenschritte, die er gerade überspringt, weil er sie für „trivial“ hält, einer komplizierten Begründung bedürfen. Dann kann es passieren, dass er/sie bei einer Zwischenfrage minutenlang auf dem Schlauch steht. Mit Floskeln wie „gilt offensichtlich“ oder „ist trivial“ solltest du vorsichtig umgehen und sie nicht aus Verlegenheit verwenden, wenn dir keine bessere Begründung einfällt. In vielen Fällen ist ihre Verwendung, selbst wenn sie legitim ist, schlechter Stil.
    \begin{figure}[ht]
        \includegraphics[width=10cm]{./_img/Istklar.jpeg}
        \centering \caption{Beispiel aus einer LA1-Vorlesung für einen „Beweis“, in dem gar nichts argumentiert wurde. Vgl. die Begründung von \cref{def:surjektiv}.}
    \end{figure}
\end{bem}


\begin{bem}[Subjektivität des Beweisbegriffs]
    Das Wort „überzeugt“ in meiner Beweisdefinition deutet eine subjektive Komponente an. Wenn dich ein Vorlesungs-„Beweis“ nicht überzeugen kann, dann ist er für dich eben auch kein Beweis. Ein Beweistext kann für den Einen eine befriedigende Begründung sein, während er für den Anderen völlig unverständlich und praktisch wertlos ist. Wenn dir unmittelbar einsichtig ist, dass eine Aussage gilt, kann sogar ein „Ist-klar“-Beweis überzeugend sein.
    
    Nichtsdestotrotz gibt es gewisse Regeln und Techniken, über deren Zulässigkeit ein Konsens besteht. Beweise, die diesen Regeln unterliegen, muss ein Mathematiker anerkennen. Dass Beweise nicht überzeugend sind, kommt nur selten von Verstößen gegen die Logik her; sondern eher von der Verwendung obskurer Begriffe, dem Mangel an Erläuterung komplizierter Beweisschritte, Flüchtigkeitsfehlern, dem Verschleiern von Beweislücken oder der unbegründeten Verwendung von Aussagen, die, wenn überhaupt, irgendwo fünfzig Seiten vorher einmal in einem unscheinbaren Lemma hergeleitet wurden.
\end{bem}


Bereits in diesem Kapitel werde ich Beweise führen, nämlich um zu demonstrieren, wie sich gewisse logische Schlussregeln und Beweistechniken aus anderen ableiten lassen. Setz dich aber nicht unter Druck, die Herleitungen der Beweistechniken lückenlos nachvollziehen zu müssen, sondern begreife sie als Erklärungen, die plausibel machen sollen, warum die Beweistechniken zulässig sind. Letztendlich musst du dich selbst davon überzeugen, wie genau ist gar nicht so wichtig. In den Mathevorlesungen (mal abgesehen von Vorlesungen über Logik, wo es genau darum geht) werden die üblichen Beweistechniken größtenteils ohne weitere Begründung verwendet und ab der zweiten Semesterwoche erwartet auch niemand mehr, dass du die Logik, die deinen Beweisen zugrundeliegt, rechtfertigst (solange sie halt nicht „unlogisch“ ist).


\begin{bem}[Tipps zur Beweisfindung]
    In \cref{anhang:entstehungsprozess} findest du ein Beispiel und allgemeine Hinweise, wie sich eine konkrete Übungszettelaufgabe in Angriff nehmen lässt.
\end{bem}





\section{Implikationen}


In diesem Abschnitt seien $A,B$ stets zwei beliebige Aussagen.


\begin{axiom}[Der direkte Beweis] \label{direkterbeweis} \index{direkter Beweis}
    Um die Implikation $A\to B$ zu beweisen, kannst du die Technik des \textbf{direkten Beweises} benutzen:
    
    Nimm an, dass die Aussage $A$ gilt, und zeige nun mithilfe dieser Annahme (und aller weiteren Aussagen, die dir zur Verfügung stehen), dass auch $B$ gilt.
\end{axiom}


\begin{bsp}
    Sofern Bayer 04 Leverkusen nach dem 29. Spieltag sechzehn Punkte vor dem Tabellenzweiten steht, werden sie Deutscher Meister.
\end{bsp}
\begin{proof}
    Angenommen, Leverkusen liegt nach dem 29. Spieltag sechzehn Punkte vor dem Tabellenzweiten. Weil nur noch fünf Spieltage verbleiben, kann der Zweite (und jeder weiter unten stehende Verein) nur noch $5\cdot 3=15$ Punkte aufholen. Also ist der Bayer uneinholbar und wird (nach all den Jahren endlich) Deutscher Meister.
\end{proof}
  
  
\begin{bem}[Signalwörter]
    Wenn du die Implikation $A\to B$ direkt beweist, kannst du dies deutlich machen, indem du den Beweis mit „Es gelte $A$“, „Es sei angenommen, dass $A$ gilt“ oder Ähnlichem beginnst.
\end{bem}

  
\begin{satz}[* Jede Aussage impliziert sich selbst] \label{implikationref}
    Es gilt
    \[ A\to A \]
\end{satz}
\begin{proof}
    Für einen direkten Beweis sei angenommen, dass $A$ gilt. Weil unter dieser Annahme ja $A$ gilt, ist schon alles bewiesen.
\end{proof}

  
\begin{satz}[* Wahres folgt aus Beliebigem]\label{wahresausbeliebigem}
    Es gilt
        \[ A \to (B\to A)   \]
    Mit anderen Worten: Sofern $A$ gilt, wird $A$ auch von allen anderen Aussagen impliziert.
\end{satz}
\begin{proof}
    Für einen direkten Beweis sei angenommen, dass $A$ gilt. Nun ist zu zeigen, dass auch $B\to A$ gilt. Dazu sei zusätzlich angenommen, dass $B$ gilt. Nun gilt auch $A$, weil dies ja schon ganz zu Beginn des Beweises angenommen wurde.
\end{proof}


\begin{bem}[„$\to$“ bedeutet keine Kausalität!] \label{keinekausalitaet}
    Die Aussage, dass Wahres aus Beliebigem folgt, mag seltsam erscheinen (und wird unter die \href{https://de.wikipedia.org/wiki/Paradoxien_der_materialen_Implikation}{„Paradoxien der materialen Implikation“} gezählt), da dann ja auch Wahres aus solchen Aussagen folgt, die gar nichts damit zu tun haben. Beispielsweise ist „Sofern der Döner in Deutschland erfunden wurde, ist $4$ eine Quadratzahl“ eine wahre Aussage. Dass dies „paradox“ anmutet, kommt von einer inadäquaten Interpretation des Implikationspfeils „$\to$“.
    
    In ihrer üblichsten Interpretation besagt die Aussage $A\to B$ nicht, dass es einen kausalen Zusammenhang zwischen $A$ und $B$ geben muss; sondern nur, dass $B$ unter Annahme von $A$ gilt, egal ob diese Annahme in die Herleitung von $B$ mit einfließt oder nicht.

    Logiken, die sich darum bemühen, dass „$\to$“ wirklich die Bedeutung einer kausalen Implikation trägt, heißen „Relevanzlogiken“, da dort für eine Implikation $A\to B$ gefordert wird, dass $A$ in irgendeiner Hinsicht „relevant“ für $B$ ist. In Relevanzlogiken ist die Technik des direkten Beweises nicht mehr uneingeschränkt zulässig.
\end{bem}


\begin{axiom}[Modus ponens] \label{modusponens} \index{Modus Ponens}
    Die logische Schlussregel
    \[\begin{tabular}{r}
        $A\to B$ \\
        $A$ \\
        \hline
        $B$
   \end{tabular}\]
    heißt „Modus ponens“. Sie besagt: Wann immer dir gegeben ist, dass sowohl $A\to B$ als auch $A$ gültig sind, kannst du daraus $B$ schlussfolgern.
\end{axiom}


\begin{bsp}
    Ich habe angekündigt, dass ich, sofern ich zum Bürgermeister gewählt werde, Freibier für alle stiften werde. Nun wurde ich tatsächlich zum Bürgermeister gewählt, sodass jedem Freibier ausgeschenkt wird.
\end{bsp}


\begin{bem}[Logik-Latein]
    Du brauchst dir nicht merken, dass diese Schlussregel „Modus ponens“ heißt. Ebensowenig brauchst du dir die anderen lateinischen Bezeichnungen in diesem Kapitel merken. Sie sollen dir jedoch das Nachschlagen in Internet und Literatur erleichtern.
\end{bem}


\begin{bem}
    Anfänger machen gelegentlich den Fehler, aus $A\to B$ und $B$ auf die Aussage $A$ zu schließen. Hier ist ein Beispiel für diesen Fehlschluss:
    \begin{quote}
        Wenn sie heimlich mit nem anderen Typen schläft, kommt sie später als sonst nach Hause. Heute ist sie schon wieder später nach Hause gekommen, also ist klar, dass sie es mit jemand Anderem treibt.
    \end{quote}
    Mach dir klar, warum diese Schlussfolgerung nicht logisch valide ist.
\end{bem}


\begin{satz}[Direkter Beweis mit Zwischenschritten] \label{implikationtrans}
    Seien $n\in \N$ und $Z_1,\dots , Z_n$ eine Handvoll Aussagen. Um die Implikation $A\to B$ zu beweisen, kannst du die Implikationen
        \[ A\to Z_1,\quad Z_1\to Z_2,\quad \dots ,\quad Z_{n-1}\to Z_n\quad \text{und}\quad Z_n\to B \]
    beweisen. In diesem Fall fungieren die Aussagen $Z_1,\dots , Z_n$ als \textbf{Zwischenschritte}.
\end{satz}
\begin{proof}
    Es sei angenommen, dass ich alle Implikationen $A\to Z_1$, $Z_1\to Z_2$, \dots , $Z_n\to B$ bewiesen habe. Um zu zeigen, dass dann auch $A\to B$ gilt, sei angenommen, dass $A$ gilt. Wegen $A\to Z_1$ folgt, dass dann auch $Z_1$ gilt. Wegen $Z_1\to Z_2$ folgt, dass auch $Z_2$ gilt. Auf diese Weise kann ich schrittweise die $Z$'s durchgehen, bis am Ende auch $Z_n$ bewiesen ist. Und wegen $Z_n\to B$ gilt dann auch $B$.
\end{proof}


\begin{bsp}
    Falls es nächsten Sommer (schon wieder) zu wenig regnet, wird der Fichtenwald in meiner Heimatstadt gerodet werden.
\end{bsp}
\begin{proof}
    Wenn es nächstes Jahr wieder zu wenig regnet, fehlt es den Fichten an Flüssigkeit, um ausreichend Harz für eine widerstandsfähige Rinde auszubilden. Dies erleichtert es Borkenkäfern, innerhalb der Rinde zu nisten, sodass sich die Borkenkäferpopulation im Wald stark vergrößert und Bäume teilweise absterben werden. Unter diesem Umstand wird die örtliche Forstbehörde beschließen, den Wald zum Schutz vor umstürzenden Bäumen und einer weiteren Ausbreitung der Borkenkäfer zu roden.
\end{proof}





\section{Äquivalenzen}


In diesem Abschnitt seien $A,B$ stets zwei beliebige Aussagen.


\begin{axiom}[Hin- und Rückrichtung] \label{hinruck} \index{Hinrichtung} \index{Rueckrichtung@Rückrichtung} \index{Aequivalenzbeweis@Äquivalenzbeweis}
    Aus dem Vorliegen der beiden Implikationen $A\to B$ und $B\to A$ kann auf die Äquivalenz $A\leftrightarrow B$ geschlossen werden.
    \[\begin{tabular}{r}
        $A\to B$ \\
        $B\to A$ \\
        \hline
        $A\leftrightarrow B$
    \end{tabular}\]
    Wenn du die Äquivalenz $A\leftrightarrow B$ beweisen willst, kannst du deinen Beweis also in zwei Teile aufteilen: In der \textbf{Hinrichtung} beweist du die Implikation $A\to B$. In der \textbf{Rückrichtung} beweist du die Implikation $B\to A$.
\end{axiom}


\begin{bsp} \label{bsp:hinruck}
    Eine ganze Zahl $n\in \Z$ ist genau dann ein Vielfaches von $6$, wenn sie zugleich ein Vielfaches von $2$ und ein Vielfaches von $3$ ist.
\end{bsp}
\begin{proof}
    \begin{labeling}
        \item[„$\Rightarrow$“:] Sei $n$ ein Vielfaches von $6$. Dies besagt, dass es ein $k\in \Z$ gibt mit $n=6\cdot k$. Es folgt $n=2\cdot (3k)$ und $n=3\cdot (2k)$. Also ist $n$ sowohl ein Vielfaches von $2$ als auch von $3$.
        \item[„$\Leftarrow$“:] Es sei $n$ sowohl ein Vielfaches von $2$ als auch von $3$. Demzufolge gibt es $k,l\in \Z$ mit $n=2k$ und $n=3l$. Es folgt
        \begin{align*}
            n & = 3n - 2n \\
            & = 3\cdot 2k - 2\cdot 3l & (\text{wegen $n=2k$ und $n=3l$})\\
            & = 6k - 6l \\
            & = 6\cdot (k-l)
        \end{align*}
        Also ist $n$ auch ein Vielfaches von $6$. \qedhere
    \end{labeling}
\end{proof}


\begin{bem}
    Die Methoden, die in diesen Beweis eingingen, gehören zur \emph{Teilbarkeitstheorie}. Mehr darüber wirst du im zweiten Semester in der Vorlesung „Lineare Algebra 2“ lernen.
\end{bem}


\begin{bem}[Guter Stil]
    Wenn du eine Äquivalenz per Hin- und Rückrichtung beweist, solltest du die jeweiligen Beweisabschnitte mit „$\Rightarrow$“ und „$\Leftarrow$“ (so wie im Beispiel gerade eben) oder mit Floskeln wie „Ich beweise zuerst die Hinrichtung“ und „Für den Beweis der Rückrichtung sei nun\dots“ beginnen, damit deinem Leser jederzeit klar ist, um welche der beiden Richtungen es gerade geht.
\end{bem}


\begin{axiom}
    Aus der Äquivalenz $A\leftrightarrow B$ kann sowohl auf $A\to B$ als auch auf $B\to A$ geschlossen werden.
    \[\begin{tabular}{r}
        $A\leftrightarrow B$ \\
        \hline 
        $A\to B$ 
    \end{tabular} \qquad\text{und}\qquad \begin{tabular}{r}
        $A\leftrightarrow B$ \\
        \hline 
        $B\to A$ 
    \end{tabular}\]
\end{axiom}


\begin{bsp}
    Es wurde angekündigt, dass man die Prüfung genau dann besteht, wenn man mehr als 50 Punkte erreicht hat. Dann weiß ich einerseits, dass ich, wenn ich die Prüfung bestanden habe, mehr als 50 Punkte erreicht haben muss; andererseits weiß ich, dass ich, sofern ich mehr als 50 Punkte erreicht habe, auf jeden Fall bestanden habe.
\end{bsp}


\begin{satz}[* Äquivalenzbeweis mit Zwischenschritten] \label{ifftrans}
    Seien $n\in\N$ und $Z_1,\dots , Z_n$ Aussagen. Dann kannst du die Äquivalenz $A\leftrightarrow B$ beweisen, indem du die Äquivalenzen
        \[ A\leftrightarrow Z_1,\quad Z_1\leftrightarrow Z_2,\quad \dots\quad Z_{n-1}\leftrightarrow Z_n \quad\text{und}\quad Z_n\leftrightarrow B \]
    beweist. In diesem Fall fungieren die Aussagen $Z_1,\dots , Z_n$ als \textbf{Zwischenschritte}.
\end{satz}
\begin{proof}
    \begin{labeling}
        \item[„$\Rightarrow$“:] Die Äquivalenzen $A\leftrightarrow Z_1$, $Z_1\leftrightarrow Z_2$, \dots, $Z_n\leftrightarrow B$ beinhalten die Implikationen $A\to Z_1$, $Z_1\to Z_2$, \dots, $Z_n\to B$, woraus sich mittels \cref{implikationtrans} ergibt, dass $A\to B$ gilt.
        \item[„$\Leftarrow$“:] Ebenso beinhalten die Äquivalenzen $A\leftrightarrow Z_1$, $Z_1\leftrightarrow Z_2$, \dots, $Z_n\leftrightarrow B$ auch die Implikationen $B\to Z_n$, $Z_n\to Z_{n-1}$, \dots, $Z_1\to A$, woraus sich mittels \cref{implikationtrans} auch $B\to A$ ergibt. \qedhere
    \end{labeling}
\end{proof}


\begin{nota}[*] \label{todotsto}
    Für $n\in \N$ und Aussagen $Z_1,\dots , Z_n$ schreibt man kurz:
    \begin{align*}
        Z_1\to \ldots \to Z_n \qquad &:\Leftrightarrow\qquad Z_1\to Z_2\ \land \ldots \land\ Z_{n-1}\to Z_n \\
        Z_1\leftrightarrow \ldots \leftrightarrow Z_n \qquad &:\Leftrightarrow\qquad Z_1\leftrightarrow Z_2\ \land \ldots \land\ Z_{n-1}\leftrightarrow Z_n
    \end{align*}
\end{nota}


\begin{bsp}[*]
    Sei $x\in \R_{>0}$. Genau dann ist $x$ eine Lösung der Gleichung $x^2-x=1$, wenn $x= \frac{1+\sqrt{5}}{2}$.\footnote{Die Zahl $\frac{1+\sqrt{5}}{2}$ heißt \href{https://de.wikipedia.org/wiki/Goldener_Schnitt}{Goldener Schnitt}.}
\end{bsp}
\begin{proof}
    Es gilt:
    \begin{alignat*}{5}
        x^2-x& =1 \quad&\leftrightarrow\quad&& \left(x-\frac{1}{2}\right)^2 - \frac{1}{4} &= 1 &&& \qquad(\text{quadratische Ergänzung}) \\
        && \leftrightarrow\quad&& \left(x-\frac{1}{2}\right)^2&=\frac{5}{4} \\
        && \leftrightarrow\quad&& x-\frac{1}{2} &= \pm \sqrt{\frac{5}{4}} \\
        && \leftrightarrow\quad&& x  &= \frac{1\pm \sqrt{5}}{2} 
    \end{alignat*}
    Weil $x$ positiv ist und $\frac{1-\sqrt{5}}{2}<0$ wäre, ist dies wiederum äquivalent zu $x=\frac{1+\sqrt{5}}{2}$.
\end{proof}


\begin{satz}[* Jede Aussage ist äquivalent zu sich selbst]\label{iffref}
    Es gilt
        \[ A\leftrightarrow A \]
\end{satz}
\begin{proof}
    Mit \cref{implikationref} ist zugleich die Hinrichtung und die Rückrichtung bewiesen.
\end{proof}


\begin{satz}[* Kommutativgesetz für $\leftrightarrow$]\label{iffkomm}
    Es gilt
        \[ (A\leftrightarrow B)\leftrightarrow(B\leftrightarrow A) \]
\end{satz}
\begin{proof}
    \begin{labeling}
        \item[„$\Rightarrow$“:] Es gelte $A\leftrightarrow B$. Daraus folgt, dass sowohl $A\to B$ als auch $B\to A$ gelten. Aber dies sind genau Rück- und Hinrichtung für $B\leftrightarrow A$.
        \item[„$\Leftarrow$“:] Die Rückrichtung beweist man analog zur Hinrichtung, unter Vertauschung der Rollen von $A$ und $B$. \qedhere
    \end{labeling}
\end{proof}


\begin{bem}[Substitutionsprinzip] \index{Substitutionsprinzip}
    Seien $A,B$ zwei äquivalente Aussagen. Dann kannst du in Beweisen die Aussagen $A$ und $B$ beliebig miteinander vertauschen. Möchtest du beispielsweise $A$ beweisen, kannst du genausogut $B$ beweisen. Oder ist dir eine Aussage der Gestalt $(A\land C)\to D$ gegeben, so kannst du genausogut auch mit der Aussage $(B\land C)\to D$ arbeiten.
    
    Aus diesem Grund sind Äquivalenzaussagen wertvoll und nützlich. Sie erlauben es, Aussagen von mehreren Blickwinkeln zu beleuchten und dadurch ein „tieferes“ Verständnis für sie zu gewinnen.
\end{bem}


\begin{satz}[* Curry-Paradoxon] \label{curryparadox}
    Es gilt
        \[ (A\leftrightarrow (A\to B))\to B \]
    Mit anderen Worten: Ist $A$ bereits äquivalent dazu, dass $B$ von $A$ impliziert wird, so gilt $B$.
\end{satz}
\begin{proof}
    Für einen direkten Beweis sei angenommen, dass $A\leftrightarrow (A\to B)$ gilt. Nun ist zu beweisen, dass $B$ gilt.
    \begin{enumerate}[(1)]
        \item Es gilt $A\to B$, denn: Für einen direkten Beweis sei angenommen, dass $A$ gilt. Wegen $A\leftrightarrow (A\to B)$ gilt dann auch $A\to B$. Und weil $A$ als gültig angenommen wurde, folgt daraus $B$.
        \item Es gilt $B$, denn: Nach Schritt (1) gilt $A\to B$. Wegen $A\leftrightarrow (A\to B)$ gilt dann auch $A$. Weil nach Schritt (1) auch $A\to B$ gilt, folgt nun, dass auch $B$ gilt. \qedhere
    \end{enumerate}
\end{proof}


\begin{bem}[* Selbstreferenzielle Aussagen]
    Das Curry-Paradoxon wird deshalb als „Paradoxon“ gehandelt, da es zumindest in der Alltagssprache ziemlich leicht ist, Aussagen $A$ zu konstruieren, für die $A\leftrightarrow (A\to B)$ gilt. Zum Beispiel seien
    \begin{labeling}[labelindent=1.5em]
        \item[$A:=$] „Wenn diese Aussage wahr ist, gewinne ich morgen im Lotto.“
        \item[$B:=$] „Morgen gewinne ich im Lotto.“
    \end{labeling}
    Dann gilt tatsächlich $A\leftrightarrow (A\to B)$, sodass aus \cref{curryparadox} folgt, dass ich morgen Millionär bin. Lotterien hassen diesen Trick.
    
    Damit sich mit dem Curry-Paradoxon nicht einfach \emph{jede} mathematische Aussage beweisen lässt, muss in der mathematischen Logik sichergestellt werden, dass sich die Selbstreferenzialität „Wenn \emph{diese Aussage} wahr ist, dann \dots“, die alltagssprachlich problemlos erzeugbar ist, nicht in formaler mathematischer Sprache nachbilden lässt.
\end{bem}





\subsection*{* Zwei Fehler im Umgang mit Äquivalenzumformungen}


\begin{bem}[„Gleichungs-U's“]
    Aus der Schule sind es manche Studienanfänger gewohnt, Gleichungen dadurch zu beweisen, dass sie sie sovielen Äquivalenzumformungen unterziehen, bis am Ende eine „offensichtliche“ Gleichung rauskommt. Hier ein Beispiel für diese Vorgehensweise:
    \begin{bsp}
    Seien $x,y$ zwei reelle Zahlen. Dann gilt:
        \[ x\cdot (y+1)-x = (x+1)\cdot y-y\]
    \end{bsp}
    \begin{proof}[Mieser Beweis]\let\qed\relax
        Es gilt:
        \begin{alignat*}{3}
            && x\cdot (y+1)-x& \quad=\quad (x+1)\cdot y-y \\
            &\leftrightarrow\qquad& xy + x  -x& \quad=\quad xy + y - y \\
            &\leftrightarrow\qquad& xy & \quad=\quad xy
        \end{alignat*}
    \end{proof}
    Diesen „Beweisstil“ solltest du dir nicht aneignen bzw. so bald es geht abgewöhnen. Denn bei so einer Äquivalenzenkette geschieht bei jeder Äquivalenzumformung auf jeder der beiden Seiten eine arithmetische Umformung, die der Leser nachvollziehen muss. Und diese arithmetischen Umformungen bilden den eigentlichen Kern des Beweises, letztendlich hat der Leser die Gleichungskette also in einer „U-Form“, deren beide Stränge erst ganz am Schluss zusammenfinden, zu lesen:
    \[\begin{tikzcd}
        && x\cdot (y+1)-x\ar[red, d, dash] & =& (x+1)\cdot y-y \ar[red, d, dash] \\
        \leftrightarrow&& xy + x-x  \ar[red, d, dash] & =& xy + y - y \ar[red, d, dash] \\
        \leftrightarrow&& xy \ar[red, rr, dash, bend right] & =& xy
    \end{tikzcd}\]
    Schöner ist es, diese Kette arithmetischer Umformungen gar nicht erst als „U“, sondern als die Kette, als die sie letztendlich auch zu lesen ist, hinzuschreiben:
    \begin{proof}[Schönerer Beweis]
        Es gilt:
        \begin{align*}
            x\cdot (y+1) -x& = xy + x -x\\
            & = xy  \\
            & = xy + y - y \\
            & = (x+1)\cdot y -y  &&&& \qedhere
        \end{align*}
    \end{proof}
    Unterscheide dabei sorgfältig von der Art und Weise, wie du den Beweis \emph{findest} und der Art und Weise, wie du ihn am Ende \emph{aufschreibst}: Während des Beweisfindungsprozesses auf dem Schmierblatt ist alles erlaubt. Aber am Ende, wenn es darum geht, den Beweis ansprechend aufzuschreiben, solltest du alle Unsauberkeiten tilgen und den Beweis in eine gut lesbare Form bringen. Ein mathematischer Beweis, wie du ihn in einem Lehrbuch findest oder wie ihn ein Dozent in der Vorlesung vorführt, gibt nur selten seinen Entstehungsprozess preis. (Was in didaktischer Hinsicht manchmal bedauerlich und einer der Hauptgründe dafür ist, dass sich Erstsemester mit dem Verfassen von Beweisen schwertun.)
\end{bem}


\begin{bem}[Beweise „rückwärts“ führen] \label{hintennachvorne}
    Mal angenommen, ich möchte beweisen, dass die Kubikwurzel von $3$ größer ist als die Quadratwurzel von $2$. Auf der Suche nach einem Beweis beginne ich einfach mal mit der zu zeigenden Ungleichung $\sqrt[3]{3}>\sqrt{2}$ und forme ein bisschen um:
    \begin{alignat*}{3}
        &\qquad\qquad& \sqrt[3]{3}& >\sqrt{2} \\
        & \to& \sqrt[3]{3}^{3\cdot 2} & > \sqrt{2}^{2\cdot 3} && (\text{beide Seiten mit $6$ potenzieren}) \\
        & \to & (\sqrt[3]{3}^3)^2 & > (\sqrt{2}^2)^3 &\qquad\qquad& (\text{Potenzgesetz anwenden})\\
        & \to & 3^2 & > 2^3 \\
        & \to & 9 & > 8
    \end{alignat*}
    Das sieht schonmal gut aus! Durch ein paar Umformungen bin ich zu einer wahren Aussage gelangt. Mancher Anfänger würde nun denken, dass das Problem damit erledigt ist und die obige Ungleichungskette als Beweis taugt.
    
    Das ist aber falsch. Denn die Ungleichungskette beginnt ja mit der zu beweisenden Aussage. Hier wurde also nur die Aussage „Wenn $\sqrt[3]{3} >\sqrt{2}$ gilt, dann ist $9>8$“ bewiesen, die aber leider nichts darüber aussagt, ob nun tatsächlich $\sqrt[3]{3} >\sqrt{2}$ gilt. Glücklicherweise handelt es sich aber bei allen Umformungen um Äquivalenzumformungen, sodass die Ungleichungskette auch in umgekehrter Richtung gültig ist:
    \begin{alignat*}{3}
        &\qquad\qquad& 9 & > 8 \\
        & \to & 3^2 & > 2^3 \\
        & \to & (\sqrt[3]{3}^3)^2 & > (\sqrt{2}^2)^3 \\
        & \to& \sqrt[3]{3}^{3\cdot 2} & > \sqrt{2}^{2\cdot 3} &\qquad\qquad& (\text{Potenzgesetz anwenden}) \\
        &\to &  \sqrt[3]{3}& >\sqrt{2}  && (\text{sechste Wurzel ziehen})
    \end{alignat*}
    Nun ist die Argumentation zumindest mal nicht mehr logisch falsch. Wenn ich jetzt noch das „Ungleichungs"~U“ loswerde, kann sich der Beweis sehen lassen. Hier ist der finale Beweis:
    \begin{proof}
        Es gilt
        \begingroup
        \allowdisplaybreaks
        \begin{align*}
            \sqrt[3]{3} & = \sqrt[3]{\sqrt{9}} \\
            & = \sqrt[6]{9} \\
            & > \sqrt[6]{8} & (\text{da $\sqrt[6]{-}$ eine ordnungserhaltende Operation und $9>8$ ist}) \\
            & = \sqrt{\sqrt[3]{8}} \\
            & = \sqrt{2} && \qedhere
        \end{align*}
        \endgroup
    \end{proof}
    Beachte, dass die Struktur dieses Beweises nicht meinen Denkprozess bei der Beweissuche wiederspiegelt. Das ist aber völlig normal und ok. Sollte dein Beweis sehr kompliziert sein, wäre es natürlich trotzdem nett, wenn du, wo es deinem Leser hilft, ein paar Meta-Bemerkungen darüber, welche Idee hinter dem aktuellen Beweisschritt steckt, einstreust.
    
    Auch Profis stoßen manchmal auf einen Beweis, indem sie die Argumentation „rückwärts“ ausprobieren, also mit der zu beweisenden Aussage starten und schauen, was sich damit anfangen lässt. Während diese Strategie völlig legitim zur Beweis\emph{findung} ist, ist sie es aber nicht zur Beweis\emph{niederschrift}. Dein zum Schluss aufgeschriebener Beweis muss das Problem sauber von den gegebenen Aussagen auf die zu beweisenden Aussagen durchgehen.
    
    Der Versuch, einen Beweis rückwärts zu führen, kann auch Fehler erzeugen, die du, sofern du den Rückwärts-Gedankengang am Ende nicht kritisch reflektierst, übersiehst. Zum Beispiel könnte man meinen, dass für jede reelle Zahl $x$ gilt: $\cos(x)=\sqrt{1-\sin^2(x)}$. Denn man kann ja umformen
    \begin{align*}
        && \cos(x) & =\sqrt{1-\sin^2(x)} &&&& \\
        \to && \cos^2(x) & = 1-\sin^2(x) &&&& \\
        \to && \cos^2(x) + \sin^2(x) & = 1 &&&&
    \end{align*}
    und letzteres ist eine wohlbekannte wahre Aussage (die manchmal als „Satz des Pythagoras“\footnote{\href{https://de.wikipedia.org/wiki/Pythagoras}{Pythagoras (6. Jhd. v. Chr.)}} bezeichnet wird). Jedoch ist
        \[ \cos(\pi) = -1 \neq \sqrt{\strut 1-0^2} = \sqrt{1-\sin^2(\pi)} \]
    sodass irgendetwas nicht stimmen kann. Kannst du ausmachen, wie und wo sich der Fehler eingeschlichen hat?
\end{bem}


\begin{bem}[Weitere Anfängerfehler]
 Eine lange Liste von sowohl studentischen als auch dozentischen Fehlern, die ihm während seiner Lehrtätigkeit aufgefallen sind, hat Eric Schechter auf \href{https://math.vanderbilt.edu/schectex/commerrs/}{seiner Homepage} zusammengetragen.
\end{bem}





\subsection*{* Mehrfach-Äquivalenzen}


\begin{defin}[„Die folgenden Aussagen sind äquivalent“] \label{def:tfae}
    Einige mathematische Sätze haben die Gestalt einer größeren Äquivalenzaussage und sehen folgendermaßen aus:
    \begin{quote}
        Es seien \dots und es gelte \dots. Dann sind die folgenden Aussagen äquivalent:
        \begin{itemize}
            \item[(i)] \dots
            \item[(ii)] \dots
            \item[(iii)] \dots
            \item[(iv)] \dots
            \item[\dots]
        \end{itemize}
    \end{quote}
    Diese Satzstruktur kommt so häufig vor, dass sie im Englischen mit ``tfae'' abgekürzt wird (für ``the following are equivalent''). Sie besagt, dass je zwei der Aussagen (i), (ii), (iii), usw. zueinander äquivalent sind, also dass alle Äquivalenzen
        \[ \text{(i)$\leftrightarrow$(ii),\quad (i)$\leftrightarrow$(iii), \quad (ii)$\leftrightarrow$(iii),\quad (i)$\leftrightarrow$(iv),\quad (ii)$\leftrightarrow$(iv), \quad (iii)$\leftrightarrow$(iv),\quad \dots} \]
    gelten. Man sagt auch, die Aussagen seien „paarweise äquivalent“.
 \end{defin}
 
 
\begin{bsp}
    Sei $D$ ein Dreieck in der euklidischen Ebene. Dann sind die folgenden Aussagen äquivalent:
    \begin{enumerate}[(i)]
        \item $D$ ist ein gleichseitiges Dreieck, d.h. alle Seiten von $D$ haben dieselbe Länge.
        \item Alle Innenwinkel von $D$ sind gleich groß.
        \item Der Schwerpunkt von $D$ stimmt mit seinem Umkreismittelpunkt überein.
        \item Der Schwerpunkt von $D$ stimmt mit seinem Inkreismittelpunkt überein.
    \end{enumerate}
Würde man hier die Äquivalenz jedes Aussagenpaars per Hin- und Rückrichtung beweisen, müsste man insgesamt zwölf Implikationen beweisen. Mit der folgenden Beweistechnik lässt sich in solchen Fällen erheblich Arbeit einsparen:
\end{bsp}


\begin{satz}[Ringschluss] \label{ringschluss} \index{Ringschluss}
    Seien $n\in \N$ und $A_1,\dots , A_n$ eine Handvoll Aussagen, von denen du beweisen möchtest, dass sie paarweise äquivalent sind. Dann kannst du dies mit der Technik des \textbf{Ringschlusses} erledigen, indem du lediglich die Implikationen
        \[ A_1\to A_2,\quad \dots ,\quad A_{n-1}\to A_n,\quad A_n\to A_1 \]
    beweist. Auf diese Weise „schließt du einen Ring“ zwischen den Aussagen $A_1,\dots , A_n$.
\end{satz}
\begin{proof}
    Durch den Ringschluss wurden alle Implikationen im folgenden Diagramm bewiesen:
    \[\begin{tikzcd}
        &&& A_1 \ar[rrd] &&& \\
        &A_n\ar[rru]&&&& A_2 \ar[ld]& \\
        && \dots \ar[lu] && A_3 \ar[ll]&& 
    \end{tikzcd} \]
    Man sieht, dass sich nun von jeder Aussage mittels Zwischenschritten zu jeder anderen Aussage gelangen lässt, indem man nur lang genug „im Uhrzeigersinn läuft“. Sind nun $A_i,A_j$ zwei Aussagen aus $A_1,\dots , A_n$, so gilt wegen \cref{implikationtrans} sowohl $A_i\to A_j$ als auch $A_j\to A_i$, also insgesamt $A_i\leftrightarrow A_j$.
\end{proof}


\begin{bsp} \label{bsp:ringschluss}
    Für $n\in \Z$ sind äquivalent:
    \begin{enumerate}[(i)]
        \item Es ist $n\ge 1$.
        \item Für alle $m\in \Z$ ist $m+n>m$.
        \item Es gibt ein $m\in \Z$ mit $m+n>m$.
    \end{enumerate}
\end{bsp}
\begin{proof}
    (i)$\to$(ii): Es gelte (i). Für alle $m\in \Z$ ist dann
    \begin{align*}
        m+n & \ge m+1 > m
    \end{align*}
    (ii)$\to$(iii) ist trivial (da ganze Zahlen existieren).

    (iii)$\to$(i): Sei $m\in \Z$ mit $m+n>m$. Subtraktion von $m$ liefert die Ungleichung $n>0$. Weil $n$ ganzzahlig ist, muss dann schon $n\ge 1$ gelten.
\end{proof}


\begin{bem}
    Ein gelegentlicher Anfängerirrtum besteht darin, zu denken, der Ringschluss müsse \emph{immer} in der Form (i)$\to$(ii), (ii)$\to$(iii), (iii)$\to$(i) durchgeführt werden. Das ist Unsinn und führt dazu, dass sich manche Anfänger einen Haufen unnötige Mehrarbeit aufhalsen.
    
    Genausogut kannst du etwa auch einen Ringschluss über die Implikationen (ii)$\to$(i), (iii)$\to$(ii) und (i)$\to$(iii) durchführen.
    
    Manchmal ist die Ringschluss-Methode auch unangebracht, wenn etwa die beiden Aussagen (ii) und (iii) so widerspenstig gegeneinander sind, dass keine Beweise für (ii)$\to$(iii) und (iii)$\to$(ii) in Sicht sind. In diesem Fall ist es vielleicht einfacher, den scheinbar längeren Weg zu gehen und (i)$\to$(ii), (ii)$\to$(i), (i)$\to$(iii) und (iii)$\to$(i) zu beweisen.
    \[\begin{tikzcd}[column sep=small]
        & (ii) \ar[rd] & \\
        (iii)\ar[ru] && (i)\ar[ll]
    \end{tikzcd}\qquad\text{anstelle von}\qquad\begin{tikzcd}[column sep=small]
        & (i) \ar[rd] & \\
        (iii)\ar[ru] && (ii)\ar[ll]    
    \end{tikzcd}\qquad\text{geht auch.}\]
    \[\text{Manchmal funktioniert aber nur}\qquad \begin{tikzcd}
        & (i) \ar[ld, bend right=20]  \ar[rd, bend right=20] & \\
        (iii)\ar[ru, bend right=20] && (ii) \ar[lu, bend right=20]
    \end{tikzcd}\]
    Entscheidend ist, dass du am Ende genügend viele Implikationen bewiesen hast, dass man mittels Zwischenschritten von jeder Aussage zu jeder anderen Aussage gelangen kann.

    Wenn du eine umfangreiche Äquivalenzaussage beweisen möchtest, solltest du immer Ausschau nach Implikationen halten, die „geschenkt“ sind, d.h. deren Beweis besonders naheliegend und einfach ist (in \cref{bsp:ringschluss} war das die Implikation (ii)$\to$(iii)). Daran kannst du dann deine Beweisstrategie orientieren. Ein \href{https://mampf.mathi.uni-heidelberg.de/media/105/play?time=2609}{Äquivalenzbeweis aus meiner LA1-Vorlesung vom Wintersemester 2016/17} verlief so speziell, dass unser Dozent Denis Vogel zu Beginn seines Beweises einen „Plan“ aufschrieb, um seinen Hörern die Orientierung zu erleichtern.
    \begin{figure}[ht]
        \includegraphics[width=10cm]{./_img/equivbeweis.jpeg}
        \centering \caption{Eine Äquivalenzaussage aus der LA1 vom WS16/17. Hier sind die Implikationen (ii)$\to$(iii) und (ii)$\to$(iv) „geschenkt“.}
    \end{figure}
\end{bem}


\begin{bem}[Guter Stil]
    Wenn du eine Aussage der Gestalt „Folgende Aussagen sind äquivalent: \dots“ beweist, solltest du den Beweis jeder einzelnen Implikation mit „(i)$\to$(ii)“, „(iii)$\to$(i)“ oder Ähnlichem betiteln, damit deinem Leser jederzeit klar ist, welche Implikation gerade Thema ist.
\end{bem}





\section{Und und Oder}


In diesem Abschnitt seien $A,B$ stets zwei beliebige Aussagen.


\begin{axiom}[*]\label{undoderaxiome}
    Für je zwei Aussagen $A,B$ gelten:
    \begin{align*}
        (A\land B) & \to A & A & \to (A\lor B) \\
        (A\land B) & \to B & B & \to (A\lor B)
    \end{align*}
    Mit anderen Worten: Aus $A\land B$ folgen sowohl $A$ als auch $B$; und $A$ und $B$ sind wiederum hinreichende Bedingungen für $A\lor B$.
\end{axiom}


\begin{bem}[*]
    Wenn dir die Aussage $A\land B$ gegeben ist, kannst du das also so behandeln, als seien dir zwei Aussagen gegeben, nämlich $A$ und $B$.
    
    Und wenn du $A\lor B$ beweisen möchtest, würde es schon reichen, wenn du $A$ beweist oder wenn du $B$ beweist.
\end{bem}


\begin{axiom}[Und-Aussagen beweisen] \label{undbeweise}
    Um die Aussage $A\land B$ zu beweisen, genügt es, sowohl $A$ als auch $B$ zu beweisen:
    \[\begin{tabular}{r}
        $A$ \\
        $B$ \\
        \hline 
        $A\land B$
    \end{tabular} \]
\end{axiom}


\begin{bsp}[*]
    Die $25$ ist eine Quadratzahl, die sich als Summe zweier echt kleinerer Quadratzahlen schreiben lässt. Außerdem ist sie die kleinste Quadratzahl mit dieser Eigenschaft.
\end{bsp}
\begin{proof}
    (1) Aus
        \[ 25=5^2 \qquad\text{und}\qquad 25 = 9 + 16 = 3^2 + 4^2 \]
    folgt, dass $25$ eine Quadratzahl ist, die sich als Summe zweier echt kleinerer Quadratzahlen schreiben lässt.

    (2) Die einzigen Quadratzahlen $\neq 0$, die noch kleiner als $25$ sind, sind
        \[ 1\qquad 4\qquad 9\qquad 16 \]
    Wäre eine dieser vier Zahlen eine Summe zweier echt kleinerer Quadratzahlen, so müssten auch diese beiden Summanden in der Liste dieser vier Zahlen vorkommen. Aber alle möglichen Kombinationen
    \begin{align*}
        1+1 & = 2 & 1+4 & = 5 \\
        1+ 9 & = 10 & 1+16 & = 17 \\
        4 + 4 & = 8 & 4+9 & = 13 \\
        4+16 & = 20 & 9+9 & = 18
    \end{align*}
    ergeben keine Quadratzahl.
\end{proof}


\begin{bem}[*]
    Drei natürliche Zahlen $a,b,c$, für die $a^2+b^2=c^2$ gilt, heißen ein \textbf{pythagoräisches Tripel}. Also wurde soeben bewiesen, dass $(2,3,5)$ das kleinste pythagoräische Tripel ist. Dagegen besitzt nach dem berühmten \href{https://de.wikipedia.org/wiki/Gro\%C3\%9Fer_Fermatscher_Satz}{Großen Satz von Fermat}\footnote{\href{https://de.wikipedia.org/wiki/Pierre_de_Fermat}{Pierre de Fermat (1607-1665)}} die Gleichung $a^n+b^n=c^n$ für $n\in \N_{\ge 3}$ keine positive ganzzahlige Lösung.
\end{bem}


\begin{axiom}[Beweis mit Fallunterscheidung] \label{fallunterscheidung} \index{Fallunterscheidung (in einem Beweis)}
    Sei $X$ eine Aussage, die du beweisen möchtest. Außerdem sei gegeben, dass $A\lor B$ gilt\footnote{Im Englischen sagt man: ``the two cases $A$ and $B$ are \emph{exhausting}''.}. Dann kannst du $X$ mit einer \textbf{Fallunterscheidung} beweisen, indem du sowohl zeigst, dass $A\to X$ gilt, als auch, dass $B\to X$ gilt.
\end{axiom}


\begin{bsp} \label{bsp:fallunterscheidung}
    Für alle $n\in \N$ ist $n\cdot (n+1)$ eine gerade Zahl.
\end{bsp}
\begin{proof}
    Ich unterscheide zwei Fälle:
    \begin{enumerate}[1)]
        \item Der Fall, dass $n$ eine gerade Zahl ist. In diesem Fall ist $n\cdot (n+1)$ als Vielfaches der geraden Zahl $n$ ebenfalls eine gerade Zahl.
        \item Der Fall, dass $n$ eine ungerade Zahl ist. In diesem Fall ist $n+1$ eine gerade Zahl, sodass $n\cdot (n+1)$ als Vielfaches der Zahl $n+1$ ebenfalls eine gerade Zahl ist.
    \end{enumerate}
    Also ist $n\cdot(n+1)$ in jedem Fall gerade.
\end{proof}





\section{Quantoren}


In diesem Abschnitt sei $E(x)$ stets ein einstelliges Prädikat.


\begin{axiom}[*] \label{quantorenaxiom}
    Für jedes Objekt $a$ vom Typ der Variablen $x$ gelten die folgenden beiden Implikationen:
    \begin{align*}
         \forall x: E(x) \quad& \to\quad E(a) \\
         E(a) \quad & \to\quad \exists x: E(x)
    \end{align*}
\end{axiom}

 
\begin{bsp}[*] \quad
    \begin{enumerate}
        \item Weil in $\R$ jede positive Zahl eine Qudaratwurzel besitzt, existiert in $\R$ insbesondere auch eine Quadratwurzel der Drei.
        \item Es existieren $p,q,m,n\in \N_{\ge 1}$ mit $m^p-n^q=1$, denn es ist $3^2-2^3=1$. (Nach dem \href{https://de.wikipedia.org/wiki/Catalansche_Vermutung}{Satz von Catalan-Mihăilescu}\footnote{\href{https://de.wikipedia.org/wiki/Eug\%C3\%A8ne_Charles_Catalan}{Eugène Charles Catalan (1814-1894)}}\footnote{\href{https://de.wikipedia.org/wiki/Preda_Mih\%C4\%83ilescu}{Preda Mihăilescu (*1955)}} gibt es aber keine weiteren Möglichkeiten)
    \end{enumerate}
\end{bsp}


\begin{satz}[Beweis per Beispiel] \label{beweisperbsp} \index{Beispiel (in einem Beweis)}
    Du kannst die Existenzaussage $\exists x: E(x)$ dadurch beweisen, dass du ein konkretes Objekt $a$ findest, das die Eigenschaft $E$ besitzt. Man nennt dann $a$ ein \textbf{Beispiel} für die Existenzaussage $\exists x: E(x)$.
\end{satz}
\begin{proof}
    Ergibt sich direkt aus der Formel $E(a)\to\exists x:E(x)$.
\end{proof}


\begin{bsp}
    Es gibt eine Zahl $n\in \N_{\ge 1}$, die gleich der Summe ihrer echten Teiler ist.\footnote{Zahlen, die gleich der Summe ihrer echten Teiler sind, heißen \href{https://de.wikipedia.org/wiki/Vollkommene_Zahl}{vollkommene Zahlen}.}
\end{bsp}
\begin{proof}
    Ein Beispiel ist die Zahl $28$. Denn die echten Teiler der $28$ sind genau
        \[ 1 \qquad 2 \qquad 4 \qquad 7 \qquad 14 \]
    und es ist $1+2+4+7+14=28$.
\end{proof}

  
\begin{bem}
    Lässt sich eine Existenzaussage mit einem Beispiel beweisen, so ist es eigentlich schlechter Stil, in einem Buch oder einem Vortrag nur die Existenzaussage anzugeben. Beispielsweise ist ja die Information „Die $28$ ist gleich der Summe ihrer echten Teiler“ umfangreicher als die Information „Es gibt eine natürliche Zahl, die gleich der Summe ihrer echten Teiler ist“. Du solltest dir nicht einfach nur die Existenzaussage merken, sondern, sofern es welche gibt, auch ein paar Beispiele und deren Konstruktion im Hinterkopf behalten. Auch die mathematische Essenz des Satzes von Euklid \cref{euklid} besteht weniger in der Aussage „Es gibt eine Primzahl, die größer als $n$ ist“ als vielmehr in der trickreichen Art und Weise, wie eine solche Primzahl aufgespürt wird.
    
    Es gibt allerdings Situationen, in denen eine Existenzaussage beweisbar ist, obwohl es unmöglich ist, konkrete Beispiele anzugeben. Falls in einer Vorlesung keine Beispiele gegeben werden (was bedauerlicherweise recht häufig vorkommt und dem Zeitdruck im Vorlesungsbetrieb zuschulden kommt), solltest du beim Prof. nachhaken, ob er/sie vielleicht deshalb keine Beispiele bringt, weil es gar keine gibt oder die wenigen bekannten Beispiele zu kompliziert und zeitaufwendig sind. Gute Bücher und Vorlesungen erkennt man daran, dass sie, wenn sie keine Beispiele geben, auch erklären, warum.
\end{bem}


\begin{axiom}[Allaussagen an einem „beliebigen“ Objekt nachweisen]\label{allbeweis} \index{beliebig}
    Um die Allaussage $\forall x: E(x)$ zu beweisen, kannst du folgendermaßen vorgehen:
    
    Führe eine Variable $a$, die bislang noch nicht im Beweis verwendet wurde und ein \emph{beliebiges} Objekt vom Typ der Variablen $x$ bezeichnen soll, ein und beweise nun, dass $a$ die Eigenschaft $E$ besitzt.
\end{axiom}


\begin{bsp} \label{bsp:allbeweis}
    Für jede reelle Zahl $y\neq 1$ existiert eine reelle Zahl $x\neq 2$ mit $y=\frac{x+1}{x-2}$.
\end{bsp}
\begin{proof}
    Sei $y\in \R$ mit $y\neq 1$. Dann ist durch $x:= \frac{1+2y}{y-1}$ eine wohldefinierte reelle Zahl gegeben. Nun rechnet man nach, dass $x\neq 2$ und $\frac{x+1}{x-2}=y$.
\end{proof}

  
\begin{bem}[Signalwörter]
    Ein Beweis einer Allaussage beginnt meist mit Floskeln wie „Sei $x$ ein beliebiges\dots“ oder „Die Zahl $n$ sei beliebig aber fest“. Viele Texte lassen das Signalwort „beliebig“ auch weg und beginnen schlicht mit sowas wie „Sei $x\in \R$. Dann \dots“. So auch der Beweis gerade eben. Sie setzen vom Leser voraus, dass er erkennt, dass hier gerade der Beweis einer Allaussage beginnt.
\end{bem}


\begin{bsp}[* Satz von Euklid\protect\footnotemark] \label{euklid}
    \footnotetext{\href{https://de.wikipedia.org/wiki/Euklid}{Euklid (ca. 3. Jhd. v. Chr.)}}
    Für alle $n\in \N$ gibt es eine Primzahl $P$, die größer als $n$ ist.
\end{bsp}
\begin{bem}
    Die logische Struktur dieses Satzes ist
        \[ \forall\ (\text{natürliche Zahl $n$})\ \exists\ (\text{Primzahl $P$}):\ P>n \]
    Da es sich insgesamt um eine Allaussage handelt, sollte der Beweis mit „Sei $n$ eine (beliebige) natürliche Zahl“ beginnen. Da daraufhin die Existenzaussage
        \[ \exists P\in \N:\ \text{$P$ ist eine Primzahl und größer als $n$} \]
    übrig bleibt, fährt der Beweis sodann mit der geschickten Konstruktion eines Beispiels fort:
\end{bem}
\begin{proof}
    Sei $n\in \N$. Da es nur endlich viele natürliche Zahlen gibt, die $\le n$ sind, gibt es auch nur endlich viele Primzahlen, die $\le n$ sind. Seien $k$ deren Anzahl und $p_1,\dots , p_k$ diese Primzahlen. Betrachte die Zahl\footnote{Im Fall $k=0$ ist $N=2$, weil dann ein „leeres Produkt“ involviert ist. Siehe \cref{mehrfachprodukt}.}
        \[ N := p_1\cdot\ldots\cdot p_k + 1 \]
    Dann lässt $N$ bei der Division durch $p_1,\dots , p_k$ jedes Mal den Rest Eins übrig, ist also nicht durch $p_1,\dots , p_k$ teilbar. Wegen $N\ge 2$ muss $N$ gemäß dem Fundamentalsatz der Arithmetik aber mindestens einen Primteiler $P$ besitzen. Da $P$ keines der $p_1,\dots ,p_k$ sein kann, aber die $p_1,\dots , p_k$ alle Primzahlen sind, die $\le n$ sind, muss $P$ größer als $n$ sein.
\end{proof}


\begin{bem}[*]
    Manche behalten den Beweis des Satzes von Euklid fehlerhaft im Gedächtnis mit der Meinung, für $k\in \N$ und die ersten $k$ Primzahlen $p_1,\dots , p_k$ müsse die Zahl $p_1\cdot\ldots\cdot p_k + 1$ zwangsläufig ebenfalls eine Primzahl sein. Dies ist jedoch falsch. Beispielsweise ist $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=59\cdot 509$ keine Primzahl. Ein weiterer verbreiteter Irrtum ist die Meinung, es würde sich um einen Widerspruchsbeweis handeln.
\end{bem}


\begin{bem}[*]
    Achte darauf, dass die zum Beweis einer Allaussage von dir eingeführte Variable, die das „beliebige“ Objekt bezeichnen soll, auch wirklich nirgendwo sonst im bisherigen Beweis aufgetaucht ist, also auch wirklich „beliebig“ ist. Ansonsten könnte dir ein Fehler wie der folgende passieren:
    \begin{bsp}[*]
        Es gibt eine natürliche Zahl $n$, die größergleich jede andere natürliche Zahl ist.
    \end{bsp}
    \begin{proof}\let\qed\relax
        Setze $n=0$. Es bleibt zu zeigen, dass jede natürliche Zahl kleinergleich $n$ ist. Dazu sei $n$ eine beliebige natürliche Zahl. Weil bekanntlich stets $n\le n$ gilt, ist also jede beliebige Zahl kleinergleich $n$.
    \end{proof}
\end{bem}


\begin{axiom}[* Verwenden von Existenzaussagen] \label{exverwendung}
    Sofern dir in einem Beweis eine Aussage der Gestalt $\exists x: E(x)$ gegeben ist, kannst du eine Variable $a$, die bisher noch nirgends im Beweis aufgetaucht ist, einführen, und die Aussage $E(a)$ als gegeben annehmen.
\end{axiom}
  
  
\begin{bsp}[*] \label{bsp:exverwendung}
    Die Gleichung $x^5=x+1$ besitzt eine reelle Lösung.\footnote{vgl. \cref{zeichendefinieren}}
\end{bsp}
\begin{proof}
    Betrachte die reelle Funktion
        \[ f(x) = x^5-x-1 \]
    Dann gilt $f(1)=-1$ und $f(2)=29$. Nach dem Zwischenwertsatz der Analysis muss dann $f$ irgendwo zwischen $1$ und $2$ eine Nullstelle haben. Sei $\xi$ eine solche Nullstelle (hier wird \cref{exverwendung} genutzt). Dann gilt $\xi^5-\xi-1=0$, also $\xi^5=\xi +1$.
\end{proof}


\begin{satz}[* Vertauschbarkeit von Quantoren derselben Sorte] \label{quantorentausch}
    Sei $R$ ein zweistelliges Prädikat. Dann gilt:
    \begin{align*}
        \forall x\ \forall y: R(x,y) \quad &\leftrightarrow\quad \forall y\ \forall x: R(x,y) \\
        \exists x\ \exists y: R(x,y) \quad &\leftrightarrow\quad  \exists y\ \exists x: R(x,y)
    \end{align*}
\end{satz}
\begin{proof}
    Ich beweise jeweils nur die Hinrichtung „$\to$“. Die Rückrichtung wird, unter Vertauschung der Rollen von $x$ und $y$, analog bewiesen.
    \begin{labeling}
        \item[„$\forall$“:] Seien $a,b$ zwei beliebige Objekte und es gelte $\forall x\ \forall y: R(x,y)$. Mit \cref{quantorenaxiom} folgt durch Einsetzen von $a$, dass $\forall y: R(a,y)$, und durch Einsetzen von $b$, dass $R(a,b)$. Da $a$ beliebig gewählt war, gilt somit sogar $\forall x: R(x,b)$. Und da auch $b$ beliebig gewählt war, folgt hieraus, dass $\forall y\ \forall x: R(x,y)$.
        \item[„$\exists$“:] Es sei angenommen, dass $\exists x\ \exists y: R(x,y)$ gilt. Dann gibt es ein Objekt $a$, für das $\exists y: R(a,y)$ gilt (hier wird \cref{exverwendung} genutzt). Somit gibt es auch ein Objekt $b$, für das $R(a,b)$ gilt. Wegen $R(a,b)$ gilt insbesondere $\exists x: R(x,b)$ und daraus folgt wiederum $\exists y\ \exists x: R(x,y)$. \qedhere
    \end{labeling}
\end{proof}


\begin{satz}[* Quantoren verschiedener Art sind nicht miteinander vertauschbar!]
    Sei $R$ ein zweistelliges Prädikat. Dann gilt zwar
        \[ \exists x\ \forall y: R(x,y) \quad\to\quad \forall y\ \exists x: R(x,y) \]  
    die umgekehrte Implikation „$\leftarrow$“ ist im Allgemeinen aber falsch, vgl. \cref{quantorreihenfolge}.
\end{satz}
\begin{proof}
    Sei $b$ ein beliebiges Objekt und es gelte $\exists x\ \forall y: R(x,y)$. Dann gibt es ein Objekt $a$, für das $\forall y: R(a,y)$ gilt. Also gilt insbesondere $R(a,b)$. Daraus folgt $\exists x: R(x,b)$ und da das Objekt $b$ beliebig gewählt war, impliziert dies $\forall y\ \exists x: R(x,y)$.
\end{proof}




\subsection*{Eindeutigkeitsbeweise}


In \cref{eindquantzerlegung} wurde thematisiert, wie sich der Eindeutigkeitsquantor $\exists !$ aus dem Allquantor und dem Existenzquantor zusammensetzt:
    \[ \underbrace{\exists x:\ E(x)}_{\text{Es gibt mindestens ein\dots}}\quad \land\quad \underbrace{\forall y,z:\ (E(y)\land E(z)) \to y=z}_{\text{Es gibt höchstens ein\dots}}\]
Diese Und-Aussage kann gemäß \cref{undbeweise} als zwei separate Aussagen behandelt werden:


\begin{axiom}[Existenz- und Eindeutigkeitsbeweis] \label{eindbeweis} \index{Eindeutigkeitsbeweis}
    Wenn du eine Aussage der Form $\exists ! x: E(x)$ beweisen möchtest, kannst du deinen Beweis in einen Existenz-Teil und einen Eindeutigkeit-Teil aufteilen:
    \begin{itemize}
        \item Im Existenz-Teil beweist du, dass es mindestens ein Objekt gibt, das die Eigenschaft $E$ besitzt (z.B. durch Angabe eines Beispiels).
        \item Im Eindeutigkeit-Teil beweist du, dass je zwei Objekte, die die Eigenschaft $E$ besitzen, identisch sind.
    \end{itemize}
    Dabei spielt es keine Rolle, ob du erst den Existenz- und dann den Eindeutigkeit-Teil aufschreibst oder umgekehrt.
\end{axiom}


\begin{bsp} \label{bsp:eindbeweis}
    Es gibt genau ein $a\in \R$ mit $ax=a$ für alle $x\in \R$.
\end{bsp}
\begin{proof}
    Eindeutigkeit): Seien $a,b\in \R$ mit $ax=a$ und $bx=b$ für alle $x\in \R$. Dann ist
    \begin{align*}
        a & = a\cdot b & (\text{wegen der besonderen Eigenschaft von $a$}) \\
        & = b \cdot a  \\
        & = b & (\text{wegen der besonderen Eigenschaft von $b$})
    \end{align*}
    (Existenz): Für alle $x\in \R$ ist $0x=0$, sodass die Zahl $0$ die gewünschte Eigenschaft besitzt.
\end{proof}


\begin{bem}[Guter Stil]
    Du solltest den Existenz-Teil und den Eindeutigkeit-Teil deines Beweises immer auch als solchen betiteln, so wie es gerade im Beispiel geschah.
\end{bem}


\begin{bem}[Wechselspiel zwischen Formeln und Umgangssprache]
    Studienanfänger neigen dazu, in ihren Beweisen möglichst alle Sachverhalte in Formelsprache auszudrücken und logische Schritte möglichst rechnerisch, als symbolische Manipulation gewisser Formelterme, durchzuführen. Versuche stattdessen, in deinen Beweisen ein Gleichgewicht aus Formeln und Alltagssprache herzustellen. Wo ein kurzer deutscher Satz dasselbe sagt wie eine Formel, ziehe in Erwägung, den deutschen Satz hinzuschreiben. Gedruckte Beweise (wie in diesem Skript) enthalten oft mehr Fließtext als handschriftliche Beweise (wie sie dein Prof. an die Tafel schreibt).
\end{bem}





\begin{comment}
\section{Induktionsbeweise}


Im Sonderfall, dass sich Allaussagen auf natürliche Zahlen beziehen, stehen Beweistechniken zur Verfügung, die zur Gattung der „Induktionsbeweise“ gehören.


\begin{bem}[Erklärung des Induktionsbeweises]
    Die natürlichen Zahlen lassen sich „abzählen“. Das heißt, wenn ich mit der Null starte und dann anfange zu zählen „Null, Eins, Zwei, Drei,\dots“, so werde ich zwar nie fertig, da es ja unendlich viele Zahlen gibt -- ich werde aber jede beliebige Zahl nach hinreichend langer Zeit abgezählt haben. Mit anderen Worten: Der Zählprozess schöpft die Gesamtheit aller natürlichen Zahlen vollständig aus. Oder: Die Gesamtheit aller natürlichen Zahlen kann durch den Zählprozess „vollständig abgetragen“ werden.

    Zählen heißt, mit der Null zu starten und nach jeder genannten Zahl mit der kleinsten noch nicht genannten Zahl fortzufahren. Die natürlichen Zahlen lassen sich also restlos durch die beiden Operationen
    \begin{itemize}
        \item Mit der Null beginnen.
        \item Sofern man schon ein paar Zahlen abgezählt hat, mit der kleinsten Zahl fortfahren, die noch nicht drankam.
    \end{itemize}
    „abtragen“. Diese Eigenschaft der natürlichen Zahlen liegt dem Prinzip des Induktionsbeweises zugrunde.
\end{bem}


\begin{axiom}[Induktionsbeweis]
    Möchtest du beweisen, dass jede natürliche Zahl die Eigenschaft $E$ besitzt, so kannst du dies folgendermaßen erledigen:
    \begin{itemize}
        \item Im sogenannten \textbf{Induktionsanfang} beweist du, dass $E(0)$ gilt. (Je nach Kontext kann der Induktionsanfang auch bei $n=1$ oder sogar noch höher stattfinden)
        \item Im sogenannten \textbf{Induktionsschritt} fixierst du eine beliebige natürliche Zahl $n\ge 1$ und nimmst an, dass jede Zahl, die kleiner als $n$ ist, die Eigenschaft $E$ besitzt (diese Annahme heißt \textbf{Induktionsannahme} oder auch \textbf{Induktionsvoraussetzung}). Mithilfe dieser Annahme beweist du nun, dass auch $n$ die Eigenschaft $E$ besitzt.
        %\[ \forall n \ge 1:\ (\forall k\le n: E(k)) \to E(n) \]
    \end{itemize}
\end{axiom}


\begin{bsp}[Division mit Rest]
    Seien $a,b$ zwei natürliche Zahlen und $b\neq 0$. Dann gibt es eindeutig bestimmte natürliche Zahlen $q,r$, für die gilt
        \[ a=qb+r \qquad\text{und}\qquad r< b \]
\end{bsp}


\begin{proof}
    (Existenz): Im Fall $a<b$ kann man einfach $q=0$ und $r=a$ setzen. Deshalb sei ab sofort angenommen, dass $a\ge b$ gilt. Der Beweis geschieht nun per Induktion über $a$.

    (Induktionsanfang): Im Fall $a=0$ folgt aus $b\neq 0$, dass $a<b$, sodass man einfach $q=0$ und $r=a$ wählen kann.

    (Induktionsschritt): Wegen $a\ge b$ ist auch $a-b$ eine natürliche Zahl. Wegen $a-b< a$ gibt es nach Induktionsvoraussetzung eine natürliche Zahl $p$ und eine Zahl $r<b$, für die
        \[ a-b = pb + r \]
    gilt. Setzt man $q:=p+1$, so folgt
        \[ a = (p+1)b + r = qb+r\]
    (Eindeutigkeit): Seien $q,q,r,r'$ natürliche Zahlen mit $r,r'<b$ und $a=qb+r=q'b+r'$. OBdA sei $r\le r'$. Man erhält $r'-r=(q-q')b$, d.h. die Differenz $r'-r$ ist ein Vielfaches von $b$. Wegen $0\le r'-r<b$ ist dies nur dann möglich, wenn $r'-r=0$, also $r'=r$. Damit ist auch $q=\frac{a-r}{b} = \frac{a-r'}{b} = q'$.
\end{proof}


\begin{bem}[Guter Stil]
    An diesem Beweis werden eine Reihe wichtiger Punkte deutlich.
    \begin{itemize}
        \item Wenn im Beweis mehrere Variablen vom Typ „natürliche Zahl“ auftreten, musst du deutlich machen, über welche Variable dein Induktionsbeweis verläuft.
        \item Induktionsanfang und Induktionsschritt musst du klar und deutlich kennzeichnen. Deinem Leser muss zu jedem Zeitpunkt klar sein, ob er sich gerade im Induktionsschritt befindet.
        \item Wenn du im Induktionsschritt von der Induktionsannahme Gebrauch musst, musst du das deutlich hervorheben. Diese Stelle ist meist das Herzstück des ganzen Beweises!
    \end{itemize}
\end{bem}


\begin{bem}
    Es gibt einen Haufen Varianten dieser Induktionstechnik. Oftmals wird gar nicht benötigt, dass \emph{alle} kleineren Zahlen als $n$ die Eigenschaft $E$ besitzen und man kann beweisen, dass $E(n)$ allein schon aus $E(n-1)$ folgt. Manchmal führt man den Induktionsanfang auch für $n=1$ oder $n=2$ durch, sofern man etwa sowieso nur beweisen möchte, dass die Eigenschaft für alle Zahlen $\ge 1$ oder $\ge 2$ gilt.
    
    Die allgemeine Technik des Induktionsbeweises beschränkt sich nicht nur auf natürliche Zahlen, sondern auf alle möglichen Objekte, die in gewisser Weise „induktiv“ definiert sind. Beispielsweise besagt das \emph{Fundierungsaxiom} der Mengenlehre, dass auch Aussagen über alle Mengen mit einer Induktionstechnik bewiesen werden können. Mehr darüber kannst du in Büchern und Vorlesungen über mathematische Logik und Mengenlehre lernen.
\end{bem}
\end{comment}


\section{Widerlegen}


Alle bisher besprochenen Beweistechniken zielten darauf ab, die „Wahrheit“ von Aussagen zu etablieren. Nun soll es darum gehen, wie man von einer Aussage nachweisen kann, dass sie „falsch“ ist.

In diesem Abschnitt seien $A,B$ stets zwei Aussagen.


\begin{defin}[Widerlegung] \index{Widerlegung}
    Eine \textbf{Widerlegung} der Aussage $A$ ist ein Beweis ihrer Negation $\neg A$.
    
    Anstelle von „Es gilt $\neg A$“ schreiben wir auch „$A$ ist falsch“\footnote{Mit dem Wahrheitswert „f“ aus \cref{def:interpretation} hat dies erstmal nichts zu tun, vgl. \cref{beweisbarvswahr}}.
\end{defin}


\subsection*{Indirekt Argumentieren}


\begin{axiom}[Indirekte Widerlegung] \label{reductio}
    Die Schlussregel \emph{Modus tollens} besagt:
    \[\begin{tabular}{r}
        $A\to B$ \\
        $\neg B$ \\ \hline
        $\neg A$
    \end{tabular} \]
    Mit anderen Worten: Wenn aus $A$ etwas Falsches folgt, muss $A$ selbst falsch sein.
    
    Du kannst die Aussage $A$ also dadurch widerlegen, dass du eine falsche Aussage $B$ findest, die aus $A$ folgen würde. Man nennt diese Technik eine \textbf{indirekte Widerlegung} oder auch \textbf{Reductio ad absurdum} (latein für „Rückführung auf das Widersinnige“).
\end{axiom}


\begin{bsp} \label{bsp:reductio}
    $198$ ist nicht durch $17$ teilbar.
\end{bsp}
\begin{proof}
    Es ist $187=11\cdot 17$. Wäre $198$ durch $17$ teilbar, so auch die Differenz $198-187 = 11$. Aber $11$ ist kein Vielfaches von $17$.
\end{proof}


\begin{satz}[Widerlegung einer Allaussage per Gegenbeispiel] \label{gegenbeispiel} \index{Gegenbeispiel}
    Wenn du eine Aussage der Gestalt $\forall x: E(x)$ widerlegen möchtest, genügt es, irgendein Objekt $a$ zu finden, für das du $\neg E(a)$ beweisen kannst. Man nennt dann das Objekt $a$ ein \textbf{Gegenbeispiel} zur Allaussage $\forall x: E(x)$.
\end{satz}
\begin{proof}
    Angenommen, es wurde $\neg E(a)$ bewiesen. Wegen $(\forall x: E(x)) \to E(a)$ würde dann aus $\forall x:E(x)$ eine falsche Aussage folgen, sodass $\forall x:E(x)$ selbst schon falsch sein muss.
\end{proof}

 
\begin{bsp}
    Nicht jeder Mensch findet im Leben die große Liebe.
\end{bsp}
\begin{proof}
    Schauen wir uns \href{https://de.wikipedia.org/wiki/Franz_Schubert}{Franz Schubert (1797-1828)} an. Mit Mitte Zwanzig an der Syphilis erkrankt, mit 31 Jahren gestorben, war es dem Armen nicht leicht gemacht, einen Herzenspartner zu finden. Mehr als kurzzeitige Liebschaften, die er nicht frei ausleben konnte, waren dem Wiener Komponisten zu Lebzeiten nicht vergönnt. Ich meine, hör dir seine \href{https://youtu.be/F6I6Y1LhMKo?t=1665}{Winterreise} nur mal an! --
\end{proof}


\begin{bem}
    In manchen Situationen mag man geneigt sein, eine Allaussage, statt mit einem Gegenbeispiel, mit der entgegengesetzten Allaussage zu widerlegen. Beispielsweise würde man die Aussage „Für alle $x\in \R$ ist $x^2<0$“ widerlegen wollen mit der Feststellung, dass ja, ganz im Gegenteil, $x^2\ge 0$ ist für alle $x\in \R$. In der Praxis ist diese Argumentationsweise schon ok, weil ja klar ist, dass sich dann jede reelle Zahl, sagen wir $x=1$, als Gegenbeispiel anbietet, und die Argumentation die zusätzliche Information übermittelt, dass solche Gegenbeispiele sogar ganz beliebig wählbar und nichts Besonderes sind.

    Streng logisch ist diese Argumentationsweise jedoch unzulässig, da Allaussagen keine Existenzaussagen implizieren. Betrachten wir dazu die Aussage $A:\Leftrightarrow$ „Alle Vampire sind Veganer“. Man wäre vielleicht geneigt, diese Aussage zu widerlegen mit der Feststellung, dass ja, ganz im Gegenteil, alle Vampire Blut trinken, also keine Veganer sind. $A$ wäre also falsch. Allerdings würde nun mit der Regel aus \cref{quantorennegieren} folgen, dass es mindestens einen Vampir geben muss, der kein Veganer ist. Aber dies kann ja auch nicht stimmen, weil es keine Vampire gibt.

    Siehe hierzu auch \cref{vacuoustruth}.
\end{bem}


\begin{satz}[* Implikationen widerlegen]
    Du kannst die Implikation $A\to B$ dadurch widerlegen, dass du beweist, dass $A$ und $\neg B$ gelten.
\end{satz}
\begin{proof}
    Angenommen, es wurden $A$ und $\neg B$ bewiesen. Da $A$ gilt, würde dann aus $A\to B$ die falsche Aussage $B$ folgen. Gemäß \cref{reductio} ist dadurch $A\to B$ widerlegt.
\end{proof}


\begin{bem}[*]
    Die indirekte Widerlegung basiert darauf, dass eine Aussage, aus der etwas Falsches folgt, nicht stimmen kann. Dass aus einer Aussage etwas Wahres folgt, lässt dagegen keinen Rückschluss auf ihren Wahrheitsgehalt zu, da nach \cref{wahresausbeliebigem} ja Wahres aus Beliebigem folgt.
    
    Betrachte z.B. die (falsche) Aussage $A=$ „Jedes Kind weiß, dass die Summe der Zahlen $1$ bis $100$ gleich $5050$ ist“. Dann folgt aus $A$, dass auch der neunjährige Gauß\footnote{\href{https://de.wikipedia.org/wiki/Carl_Friedrich_Gau\%C3\%9F}{Carl Friedrich Gauß (1777-1855)}} dies wusste, was der \href{https://de.wikipedia.org/wiki/Gau\%C3\%9Fsche_Summenformel#Geschichte_der_Bezeichnung}{Anekdote} zufolge sogar eine wahre Aussage ist. Das ändert allerdings nichts daran, dass $A$ wohl trotzdem falsch ist.
\end{bem}


\begin{defin}[Kontraposition] \index{Kontraposition}
    Die Implikation $\neg B \to \neg A$ heißt die \textbf{Kontraposition} der Implikation $A\to B$.
\end{defin}


\begin{bsp}
    Die Kontraposition der Aussage „Wenn ich krank bin, bleibe ich zuhause“ ist „Wenn ich nicht zuhause bleibe, bin ich nicht krank“.
\end{bsp}


\begin{satz}[Der indirekte Beweis] \label{indirekterbeweis} \index{indirekter Beweis}
    Die Implikation $\neg A\to \neg B$ kannst du dadurch beweisen, dass du stattdessen die Implikation $B\to A$ beweist. Diese Technik heißt \textbf{indirekter Beweis} oder auch \textbf{Beweis per Kontraposition}.
\end{satz}
\begin{proof}
    Angenommen, es wurde $B\to A$ bewiesen. Dass nun $\neg A\to \neg B$ gilt, zeige ich per direktem Beweis. Dazu sei angenommen, dass $\neg A$ gilt. Wegen $B\to A$ würde dann aus $B$ die falsche Aussage $A$ folgen. Mit \cref{reductio} folgt nun $\neg B$.
\end{proof}


\begin{bsp}
    Seien $m,n\in \N$ mit $m^2>n^2$. Dann ist auch $m>n$.
\end{bsp}
\begin{proof}
    Für einen indirekten Beweis sei angenommen, dass $m\le n$. Multiplikation dieser Ungleichung mit $m$ bzw. $n$ liefert $m^2\le mn$ und $mn\le n^2$. Insgesamt also $m^2\le mn\le n^2$.
\end{proof}
  
  
\begin{bem}[Guter Stil]
    Wenn du einen indirekten Beweis führst, solltest du dies ankündigen, beispielsweise mit „Ich führe einen indirekten Beweis“, „Der Beweis geschieht indirekt“ oder „Beweis per Kontraposition:“.
\end{bem}





\subsection*{Widersprüche}


\begin{defin} \index{Widerspruch}
    Ein \textbf{Widerspruch} ist eine Aussage der Gestalt $A\land \neg A$.
\end{defin}


\begin{bsp}
    Für $A:=$ „Schrödingers Katze geht es gut“ besagt $A\land \neg A$, dass es der Katze sowohl gut geht als auch nicht gut geht.
\end{bsp}


\begin{axiom}[Satz vom Widerspruch] \index{Satz vom Widerspruch}
    Für jede Aussage $A$ gilt
        \[ \neg(A\land \neg A) \]
    Mit anderen Worten: Jeder Widerspruch ist eine falsche Aussage.
\end{axiom}


\begin{satz}[Der Widerspruchsbeweis] \label{widerspruchsbeweis} \index{Widerspruchsbeweis}
    Du kannst die Aussage $A$ dadurch widerlegen, dass du aus ihr einen Widerspruch herleitest. Diese Beweistechnik heißt \textbf{Widerspruchsbeweis}.
\end{satz}
\begin{proof}
    Es sei angenommen, dass aus $A$ ein Widerspruch der Gestalt $B\land \neg B$ folgt. Nach dem Satz vom Widerspruch gilt $\neg (B\land \neg B)$, sodass aus $A$ eine falsche Aussage folgt. Wegen \cref{reductio} ist $A$ somit falsch.
\end{proof}

  
\begin{bsp} \label{bsp:widerspruchsbeweis}
    Unter den positiven reellen Zahlen gibt es keine kleinste.
\end{bsp}
\begin{proof}
    Für einen Widerspruchsbeweis sei angenommen, es gäbe eine kleinste positive reelle Zahl $x$. Da $x$ positiv ist, wäre auch $\frac{x}{2}$ eine positive reelle Zahl. Ferner wäre $\frac{x}{2}<x$. Aber dies widerspräche der Annahme, dass $x$ die kleinste positive reelle Zahl sei.
\end{proof}
  
  
\begin{bem}[Guter Stil]
    Wenn du dich in einem Widerspruchsbeweis befindest, kannst du, um deinem Leser zu signalisieren, dass du gerade mit \emph{falschen} Aussagen arbeitest, den Konjunktiv II verwenden („dann wäre“, „nun gälte“). Außerdem solltest du die Annahme einer falschen Aussage stets mit „Angenommen, dass\dots“ oder Ähnlichem beginnen. Für den Leser ist es äußerst wichtig zu wissen, zu welchem Zeitpunkt im Beweis es gerade um die Herleitung wahrer Aussagen geht, und wann es (um eines Widerspruchsbeweises willen) um die Herleitung falscher Aussagen geht.
    
    Die Stelle im Beweis, an der ein Widerspruch erreicht wird, wird handschriftlich gerne mit einem Blitz $\lightning$ markiert. In gedruckten Texten ist der Blitz weniger gängig. Egal wie du es handhabst: du solltest den Moment, an dem du bei einem Widerspruch angelangt bist, stets sprachlich hervorheben.
\end{bem}


\begin{satz}[*] \label{paradox}
    Es gilt
        \[ \neg (A\leftrightarrow \neg A) \]
\end{satz}
\begin{proof}
    Für einen Widerspruchsbeweis sei angenommen, dass $A\leftrightarrow \neg A$ gilt. Daraus folgte $A\to \neg A$ und wegen $A\to A$ gälte dann insgesamt $A\to (A\land \neg A)$. Wegen \cref{widerspruchsbeweis} müsste $A$ demnach falsch sein, d.h. es müsste $\neg A$ gelten. Wegen $A\leftrightarrow \neg A$ folgte aus $\neg A$, dass auch $A$ gälte. Insgesamt läge nun der Widerspruch $A\land \neg A$ vor.
\end{proof}



\begin{bsp}[*] \label{bsp:paradox}
    Aus diesem Grund werden auch Aussagen der Gestalt $A\leftrightarrow \neg A$ gelegentlich als „Widerspruch“ bezeichnet.  Ich persönlich bevorzuge es, Aussagen, die zu ihrer eigenen Negation äquivalent sind, „Paradoxa“ zu nennen.
    \begin{enumerate}
        \item Das Standardbeispiel für eine Aussage, die äquivalent zu ihrer Negation ist, ist das (selbstreferenzielle) \textbf{Lügner-Paradoxon}:
        \begin{quote}
            $A:=$ „Diese Aussage ist falsch.“
        \end{quote}
        Hier gilt tatsächlich $A\leftrightarrow \neg A$.
        \item Eine weitere bekannte Situation, in der eine Aussage äquivalent zu ihrer Negation ist, ist das „Barbier-Paradoxon“, das wiederum ein Spezialfall der Russellschen Antinomie \cref{russell} ist:
        \begin{satz}
            In Sevilla lebt kein Mann, der genau denjenigen Männern Sevillas den Bart rasiert, die sich nicht selbst den Bart rasieren.
        \end{satz}
        \begin{proof}
            Für einen Widerspruchsbeweis sei einmal angenommen, dass es doch einen solchen Mann gäbe. Aus der Beschreibung leitet man ab, dass sich dieser Mann genau dann selbst den Bart rasierte, wenn er ihn sich nicht selbst rasierte. Aber das ist unmöglich.
        \end{proof}
    \end{enumerate}
\end{bsp}

  
\begin{satz}[* Existenzaussagen widerlegen] \label{existenzwiderleg}
    Sei $E$ eine Eigenschaft. Dann kannst du $\nexists x: E(x)$ dadurch beweisen, dass du eine Variable $a$ einführst, die ein beliebiges Objekt vom Typ der Variablen $x$ bezeichnet, und nun die Aussage $E(a)$ widerlegst.
\end{satz}
\begin{proof}
    Damit wäre dann $\neg E(a)$ bewiesen. Weil $a$ beliebig gewählt war, folgt aus \cref{allbeweis} die Aussage $\forall x: \neg E(x)$. Für einen Widerspruchsbeweis sei nun angenommen, dass dennoch $\exists x: E(x)$ gälte. Dann gäbe es ein Objekt $b$, für das $E(b)$ gälte. Aber wegen $\forall x: \neg E(x)$ gälte auch $\neg E(b)$ und dies ist ein Widerspruch.
\end{proof}


\begin{satz}[* Russellsche Antinomie\protect\footnotemark] \label{russell} \index{Russellsche Antinomie}
    \footnotetext{\href{https://de.wikipedia.org/wiki/Bertrand_Russell}{Bertrand Russell 1872-1970}}
    Sei $R$ ein zweistelliges Prädikat, dessen beide Variablen vom selben Typ sind. Dann gilt:
        \[ \nexists x\ \forall y:\ (R(x,y) \leftrightarrow \neg R(y,y))\]
    Mit anderen Worten: Es gibt kein Objekt $x$ derart, dass jedes Objekt $y$ genau dann in Relation zu $x$ stünde, wenn es nicht in Relation zu sich selbst stünde.
\end{satz}
\begin{proof}
    Für einen Widerspruchsbeweis sei einmal angenommen, es gäbe ein Objekt $a$, für das
        \[ \forall y:\ R(a,y) \leftrightarrow \neg R(y,y) \]
    gälte. Weil es sich hierbei um eine Allaussage handelt, könnten wir für $y$ das Objekt $a$ einsetzen und erhielten die Äquivalenz
        \[ R(a,a) \leftrightarrow \neg R(a,a) \]
    Aber dies mündet mit \cref{paradox} in einen Widerspruch.
\end{proof}
 

\begin{bem}[*]
    Definiert man hierbei $R(x,y):\Leftrightarrow$ „$x$ rasiert $y$ den Bart“, so ergibt sich genau das Barbier-Paradoxon aus \cref{bsp:paradox}. Bezeichnen andererseits $x,y$ zwei Mengen und $R(x,y):\Leftrightarrow y\in x$, so erhält man die Aussage, dass es keine Menge gibt, deren Elemente genau diejenigen Mengen sind, die kein Element von sich selbst sind. Diese Aussage löste zu Beginn des 20. Jahrhunderts die \href{https://de.wikipedia.org/wiki/Grundlagenkrise_der_Mathematik}{Grundlagenkrise} aus.
\end{bem}
  
  

  
    
\section{Aus Falschem folgt Beliebiges}


In diesem Abschnitt seien $A,B$ stets zwei Aussagen.


\begin{axiom}[Modus tollendo ponens] \label{modustp}
    Aus $A\lor B$ und $\neg A$ kannst du schlussfolgern, dass $B$ gilt:
    \[\begin{tabular}{r}
        $A\lor B$ \\
        $\neg A$ \\
        \hline 
        $B$
    \end{tabular} \]
    Diese Schlussregel kommt bei der Entscheidungsfindung durch Ausschlusskriterien zum Einsatz: Wenn ich weiß, dass von einer Handvoll Aussagen mindestens eine gelten muss, kann ich die wahre Aussage finden, falls ich alle anderen Aussagen ausschließen kann.
\end{axiom}


\begin{bsp}
    Ich habe beschlossen, meiner Freundin einen Erdbeerkuchen oder einen Käsekuchen zum Geburtstag zu backen. Falls ich morgen keine Erdbeeren mehr auftreiben kann, werde ich ihr also einen Käsekuchen backen.
\end{bsp}


\begin{satz}[Aus Falschem folgt Beliebiges] \label{exfalso} \index{ex falso quodlibet}
    Es gelten die folgenden beiden Implikationen:
    \begin{align*}
        \neg A & \to (A\to B) \\
        (A\land \neg A) & \to B
    \end{align*}
    Mit anderen Worten: Aus einer falschen Aussage oder einem Widerspruch lässt sich jede beliebige Aussage ableiten. Auf Latein heißt dieses Prinzip \textbf{ex falso quodlibet}.
\end{satz}
\begin{proof}
    Für einen direkten Beweis sei angenommen, dass $\neg A$ und $A$ gelten. Aus $A$ folgt $A\lor B$, und wegen $\neg A$ muss gemäß \cref{modustp} dann schon $B$ gelten.
\end{proof}


\begin{vorschau}[principle of explosion] \label{explosion}
    Da aus Widersprüchen Beliebiges folgt, ist in die Logik eine Art „Bombe“ eingebaut (in der englischen Literatur spricht man sogar vom ``principle of explosion''). Denn wenn es uns gelingen sollte, auch nur eine einzige Aussage sowohl zu beweisen als auch zu widerlegen, folgt aus \cref{exfalso}, dass \emph{jede} beliebige mathematische Aussage beweisbar ist, so unsinnig sie auch sei. Das Angeben von Beweisen wäre dann nicht mehr dazu geeignet, die „Wahrheit“ irgendwelcher Aussagen zu begründen.
    
    Logiken, in denen das ex falso quodlibet nicht gilt, heißen \href{https://ncatlab.org/nlab/show/paraconsistent+logic}{parakonsistente Logiken}. In solchen Logiken hält sich der von Widersprüchen verursachte Schaden in Grenzen und wird teils sogar absichtlich in Kauf genommen; dafür ist dort die Schlussregel aus \cref{modustp} nicht uneingeschränkt anwendbar.
\end{vorschau}





\section{Der Satz vom ausgeschlossenen Dritten}


In diesem Abschnitt seien $A,B$ stets zwei Aussagen.

Die bisherigen Axiome und Beweistechniken bilden zusammen die \emph{intuitionistische Logik} oder auch „konstruktive Logik“. Zur \emph{klassischen Logik}, die der Mainstream-Mathematik zugrundeliegt, fehlt nur noch das folgende Axiom:


\begin{axiom}[Satz vom ausgeschlossenen Dritten] \label{excludedmiddle} \index{tertium non datur} \index{Satz vom ausgeschlossenen Dritten}
    Es gilt:
        \[ A\lor \neg A \]
    Dieses Prinzip heißt auch \textbf{tertium non datur}, was Latein für „ein Drittes kommt nicht vor“ ist. Im Englischen spricht man vom \emph{principle of excluded middle}.
\end{axiom}


\begin{bsp}
    Sei $A:=$ „Heute ist Mittwoch“. Dann ergibt sich aus dem tertium non datur die Aussage „Heute ist Mittwoch oder heute ist nicht Mittwoch“.
\end{bsp}


\begin{bem}
    Der Satz vom ausgeschlossenen Dritten ist nicht zu verwechseln mit dem Bivalenzprinzip aus \cref{bivalenz}. Das tertium non datur schließt (entgegen seinem Namen -- die Terminologie ist unglücklich kontraintuitiv) nicht aus, dass es mehr als nur zwei Wahrheitswerte gibt; es besagt lediglich, dass sich die beiden Wahrheitswerte von $A$ und $\neg A$ „in der Summe immer zu `absolut wahr' kombinieren“.
    
    Dagegen wird in der philosophischen Logik mitunter das Bivalenzprinzip als „Satz vom ausgeschlossenen Dritten“ bezeichnet. Per Wahrheitstafel sieht man, dass $A\lor \neg A$ eine Tautologie hinsichtlich bivalenter Interpretationen ist.
\end{bem}


\begin{bem}[Konsequenz für Fallunterscheidungsbeweise]
    Mit dem tertium non datur stehen uns bedingungslos Oder-Aussagen der Gestalt $A\lor \neg A$ zur Verfügung, die wir für Fallunterscheidungsbeweise einsetzen können. Möchten wir eine Aussage $X$ beweisen und ist $A$ irgendeine beliebige weitere Aussage, so genügt es, $X$ einmal unter der Annahme, dass $A$ gilt, zu beweisen, und andererseits unter der Annahme, dass $A$ falsch ist.
    
    Eine der berühmtesten bisher unentschiedenen Aussagen der Mathematik ist die \href{https://de.wikipedia.org/wiki/Riemannsche_Vermutung}{Riemannsche Vermutung}\footnote{\href{https://de.wikipedia.org/wiki/Bernhard_Riemann}{Bernhard Riemann (1826 - 1866)}}. Obwohl bislang unbekannt ist, ob die Vermutung zutrifft oder nicht, konnten \href{https://en.wikipedia.org/wiki/Riemann_hypothesis#Excluded_middle}{diverse Aussagen} dadurch bewiesen werden, dass sie sowohl für den Fall, dass die Vermutung zutrifft, bewiesen wurden, als auch für den Fall, dass die Vermutung falsch wäre. Hierbei wird essenziell auf das tertium non datur zurückgegriffen.
\end{bem}


\begin{bsp}
    Es existieren zwei positive irrationale Zahlen $a,b$, für die $a^b$ eine rationale Zahl ist.
\end{bsp}
\begin{proof}
    Ich setze als bekannt voraus, dass $\sqrt{2}$ eine irrationale Zahl ist. Betrachte nun die Aussage
    \begin{quote}
        $A:=$ „$\sqrt{2}^{\sqrt{2}}$ ist eine rationale Zahl.“
    \end{quote}
    Gemäß dem tertium non datur gilt entweder $A$ oder $\neg A$, sodass eine Fallunterscheidung durchgeführt werden kann:
    \begin{enumerate}[1)]
        \item Falls $A$ gilt, setze einfach $a=b=\sqrt{2}$.
        \item Falls $A$ falsch ist, setze $a=\sqrt{2}^{\sqrt{2}}$ und $b=\sqrt{2}$. Weil $A$ falsch ist, ist $a$ eine irrationale Zahl und es ist
            \[ a^b = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^{\sqrt{2}\cdot\sqrt{2}} = \sqrt{2}^2 = 2 \]
        eine rationale Zahl. \qedhere
    \end{enumerate}
\end{proof}

   
\begin{vorschau}[* Nichtkonstruktivität des tertium non datur] \label{nichtkonstruktiv} \index{nichtkonstruktiver Beweis}
    Der vorige Beweis ist ein bekanntes Beispiel für einen „nichtkonstruktiven Beweis“. In ihm wird die Existenz zweier Zahlen $a,b$ mit besonderen Eigenschaften bewiesen, ohne dass am Ende des Beweises ein konkretes Beispiel für ein solches Zahlenpaar vorliegt. Zwar wird aus dem Beweis deutlich, dass mindestens eine der beiden Wahlen
    \begin{align*}
        b=\sqrt{2}\ \text{und}\ a=\sqrt{2} \qquad \text{oder}\qquad  b=\sqrt{2}\ \text{und}\ a=\sqrt{2}^{\sqrt{2}}
    \end{align*}
    funktioniert -- welche genau, bleibt jedoch im Dunklen. (Tatsächlich ist $\sqrt{2}^{\sqrt{2}}$ eine irrationale Zahl, sodass $a=\sqrt{2}^{\sqrt{2}}$ gewählt werden muss -- aber dies ist deutlich schwieriger zu beweisen.)
    
    Mit dem tertium non datur kommt ein weiteres seltsames Phänomen auf: In der Mathematik gibt es Aussagen, die, sofern keine Widersprüche herleitbar sind (denn dann wäre nach \cref{exfalso} ja \emph{alles} beweisbar), weder beweisbar noch widerlegbar sind. Die berühmteste dieser „unentscheidbaren“ Aussagen ist vielleicht die \href{https://de.wikipedia.org/wiki/Kontinuumshypothese}{Kontinuumshypothese}. Ist nun $A$ eine unentscheidbare Aussage und ist die Theorie widerspruchsfrei, so sind weder $A$ noch $\neg A$ beweisbar, obwohl dem tertium non datur gemäß $A\lor \neg A$ gilt. Es liegt also die Situation vor, dass eine Aussage der Gestalt „$X$ oder $Y$“ beweisbar ist, obwohl weder $X$ noch $Y$ beweisbar sind.
    
    In der \emph{intuitionistischen Logik}, die aus allen bisherigen Axiomen mit Ausnahme des tertium non datur besteht, kann dies nicht vorkommen. Mit fortgeschrittenen semantischen Methoden lässt sich zeigen, dass sich, sofern sich eine Aussage der Gestalt „$X$ oder $Y$“ ohne Rückgriff aufs tertium non datur beweisen lässt, stets auch schon eine der beiden Aussagen $X$ oder $Y$ beweisen lässt\footnote{Auf Englisch nennt man dies die \href{https://en.wikipedia.org/wiki/Disjunction_and_existence_properties}{``Disjunction property''} der intuitionistischen Logik.}. Allerdings lassen sich ohne Rückgriff aufs tertium non datur eben auch weniger Aussagen überhaupt beweisen.
\end{vorschau}

   
\begin{satz}[Regel der doppelten Verneinung] \label{doppelneg}
    Es gilt
    \[ A\leftrightarrow \neg \neg A \]
\end{satz}
\begin{proof}[*]
    \begin{labeling}
        \item[„$\Rightarrow$“:] Es gelte $A$. Dann würde aus $\neg A$ sofort der Widerspruch $A\land \neg A$ folgen, sodass $\neg A$ falsch sein muss. Also gilt $\neg\neg A$.
        \item[„$\Leftarrow$“:] Es gelte $\neg \neg A$. Gemäß tertium non datur gilt $A\lor \neg A$. Da $\neg A$ falsch ist, folgt vermöge \cref{modustp}, dass $A$ gelten muss. \qedhere
    \end{labeling}
\end{proof}


\begin{bem}
    Aufgrund der Regel der doppelten Verneinung kann jede Aussage $A$ mit der verneinenden Aussage $\neg\neg A$ identifiziert werden. Die Aussage $A$ zu beweisen, ist dann gleichwertig dazu, die Aussage $\neg A$ zu widerlegen. Diese Verlagerung macht für den Beweis von $A$ auch alle Widerlegetechniken nutzbar.
\end{bem}


\begin{satz} \label{implikationchar}
    Es gilt:
        \[ A\to B\quad \leftrightarrow\quad \neg A\lor B \]
\end{satz}
\begin{proof}[*]
    \begin{labeling}
        \item[„$\Rightarrow$“:] Es gelte $A\to B$. Um nun „$\neg A\lor B$“ zu beweisen, unterscheide ich zwei Fälle:
        \begin{enumerate}[1)]
            \item Der Fall, dass $A$ wahr ist. In diesem Fall folgt aus der Annahme $A\to B$, dass auch $B$ gilt. Aber dann ist insbesondere auch $\neg A\lor B$ korrekt.
            \item Der Fall, dass $A$ falsch ist. In diesem Fall gilt $\neg A\lor B$ ebenfalls, da ja schon $\neg A$ gilt.
        \end{enumerate}
        Also gilt in jedem Fall $\neg A\lor B$.
        \item[„$\Leftarrow$“:] Es gelte $\neg A\lor B$. Für einen direkten Beweis von $A\to B$ sei angenommen, dass $A$ gilt. Aber dann ist $\neg A$ falsch nach \cref{doppelneg}, sodass wegen $\neg A\lor B$ nur noch die Option übrig bleibt, dass $B$ gilt. \qedhere
    \end{labeling}
\end{proof}


\begin{satz}[*] \label{oderperimplikation}
    Möchtest du eine Aussage der Gestalt $A\lor B$ beweisen, so kannst du stattdessen auch $\neg A\to B$ beweisen.
\end{satz}
\begin{proof}
    Es ist
    \begin{align*}
        \neg A\to B \qquad &\leftrightarrow\qquad \neg\neg A\lor B && (\text{wegen \cref{implikationchar}})\\
        & \leftrightarrow\qquad A\lor B && (\text{Regel der doppelten Verneinung}) \qedhere
    \end{align*}
\end{proof}


\begin{bsp}[*]
    In der Ebene sind zwei Geraden zueinander parallel oder sie schneiden sich in einem Punkt.
\end{bsp}
\begin{proof}
    Wenn zwei Geraden nicht parallel sind, so laufen sie in einer Richtung aufeinander zu. Weil in dieser Richtung der Abstand beider Geraden mit konstanter Rate abnimmt, müssen sich die Geraden in dieser Richtung irgendwann schneiden.
\end{proof}


\begin{satz}[Regeln von De Morgan\protect\footnotemark] \label{demorgan} \index{De Morgansche Regeln}
    \footnotetext{\href{https://de.wikipedia.org/wiki/Augustus_De_Morgan}{Augustus De Morgan (1806 - 1871)}}
    Es gilt:
    \begin{align*}
        \neg (A\lor B) \quad& \leftrightarrow\quad \neg A\land \neg B \\
        \neg(A\land B) \quad& \leftrightarrow\quad \neg A\lor \neg B
    \end{align*}
\end{satz}


\begin{proof}[*]
    Es müssen insgesamt vier Implikationen
    \begin{align}
    \neg (A\lor B) \quad& \to\quad \neg A\land \neg B \tag{1}\\
    \neg A\land \neg B\quad& \to\quad  \neg (A\lor B) \tag{2}\\
    \neg(A\land B) \quad& \to \quad \neg A\lor \neg B \tag{3}\\
    \neg A\lor \neg B \quad& \to \quad \neg(A\land B) \tag{4}
    \end{align}
    bewiesen werden.
    \begin{enumerate}
        \item[(1)] Aus $A\to (A\lor B)$ und $B\to (A\lor B)$ folgt per Kontraposition, dass $\neg (A\lor B)\to \neg A$ und $\neg(A\lor B) \to \neg B$ gelten muss. Insgesamt also $\neg(A\lor B)\to( \neg A\land\neg B)$.
        \item[(4)] Aus $(A\land B)\to A$ und $(A\land B) \to B$ folgt per Kontraposition, dass $\neg A\to \neg(A\land B)$ und $\neg B\to \neg(A\land B)$ gelten muss. Insgesamt dann $(\neg A\lor \neg B)\to \neg(A\land B)$.
        \item[(2)] Sowohl im Fall $A$ als auch im Fall $B$ würde aus $\neg A\land \neg B$ ein Widerspruch folgen. Somit gilt $(A\lor B)\to \neg (\neg A\land \neg B)$. Per Kontraposition folgt daraus $(\neg A\land \neg B) \to \neg(A\lor B)$.
        \item[(3)] Für einen indirekten Beweis sei angenommen, dass $\neg (\neg A\lor\neg B)$ gilt. Mit der (bereits bewiesenen) Implikation (1) folgt $\neg\neg A\land\neg\neg B$, was mit der Regel der doppelten Verneinung zu $A\land B$ vereinfacht werden kann. \qedhere
    \end{enumerate}
\end{proof}

 
\begin{satz}[Implikationen per Widerspruch beweisen]
    Um die Implikation $A\to B$ zu beweisen, kannst du folgendermaßen vorgehen: Nimm an, dass sowohl $A$ als auch $\neg B$ gelten, und versuche nun, einen Widerspruch herzuleiten.
\end{satz}
\begin{proof}
    Folgt aus der Annahme $A\land \neg B$ ein Widerspruch, so ist damit $\neg(A\land \neg B)$ bewiesen. Wegen
    \begin{align*}
        \neg (A\land \neg B) \quad&\leftrightarrow\quad \neg A\lor \neg\neg B && (\text{Regel von De Morgan}) \\
        &\leftrightarrow\quad \neg A\lor B && (\text{Regel der doppelten Verneinung}) \\
        & \leftrightarrow\quad A\to B && (\text{nach \cref{implikationchar}})
    \end{align*}
    gilt dann auch $A\to B$.
\end{proof}

 
\begin{bem}[Tücken des Widerspruchsbeweises]
    Im Vergleich zum direkten Beweis ist ein Widerspruchsbeweis für $A\to B$ oft leichter zu finden, weil ja eine Annahme mehr als beim direkten Beweis zur Verfügung steht (nämlich $\neg B$). Einige Anfänger machen es sich zur Gewohnheit, alle möglichen Aussagen per Widerspruch zu beweisen. Das bringt allerdings Nachteile mit sich:
    \begin{itemize}
        \item Wo auch ein direkter oder indirekter Beweis möglich ist, sind Widerspruchsbeweise oft unnötig kompliziert.
        \item Beweist du eine Implikation $A\to B$ direkt, sagen wir über eine Reihe von Zwischenschritten $A\to Z_1\to\ldots\to Z_n\to B$, so sind damit auch gleich alle Implikationen $A\to Z_1,\dots , A\to Z_n$ mitbewiesen worden. Manchmal kann es vorkommen, dass eine der Aussagen $Z_1,\dots , Z_n$ letztendlich bedeutender ist, als die Aussage $B$, auf die du es ursprünglich abgesehen hattest. Beweist du dagegen die Implikation $A\to B$ über einen Widerspruchsbeweis, so müssen alle Aussagen, die im Laufe des Beweises unter der Annahme $A\land \neg B$ hergeleitet wurden, am Ende wieder verworfen werden, weil sie ja auf der letztendlich falschen Prämisse $A\land \neg B$ basierten. Insofern sind direkte Beweise prinzipiell ergiebiger und lehrreicher.
        \item Häufig ist der mutmaßliche „Widerspruchsbeweis“ für $A\to B$ eigentlich nur ein direkter Beweis der Kontraposition $\neg B\to \neg A$, sagen wir über eine Reihe von Zwischenschritten $\neg B \to Z_1\to\ldots\to Z_n\to \neg A$. In diesem Fall sind dann auch gleich alle Implikationen $\neg B\to Z_1,\dots , \neg B\to Z_n$ mitbewiesen, und die Impliktation $A\to B$ folgt am Ende indirekt aus $\neg B\to \neg A$.
    \end{itemize}
    Aus diesem Grund solltest du, wenn du einen validen Widerspruchsbeweis gefunden hast, immer noch einmal überprüfen, ob er sich nicht leicht in einen direkten Beweis umformulieren lässt. Zugegebenermaßen gibt es jedoch Situationen, in denen ein direkter Beweis unmöglich und ein Widerspruchsbeweis unvermeidlich ist.
\end{bem}


\begin{satz}[Quantoren negieren] \label{quantorennegieren} \index{Negation von Quantoren}
    Sei $E$ eine Eigenschaft. Es gilt:
    \begin{align*}
        \nexists x: E(x) \quad& \leftrightarrow\quad \forall x: \neg E(x) \\
        \neg (\forall x: E(x)) \quad& \leftrightarrow\quad \exists x: \neg E(x)
    \end{align*}
\end{satz}
\begin{proof}[*]
    Nach Aufteilung in Hin- und Rückrichtungen bleiben insgesamt vier Implikationen übrig, die bewiesen werden müssen:
    \begin{align}
        \neg (\exists x:\ E(x)) \quad& \to\quad (\forall x:\ \neg E(x)) \tag{1} \\
        (\forall x:\ \neg E(x)) \quad& \to\quad \neg (\exists x:\ E(x)) \tag{2} \\
        \neg (\forall x:\ E(x)) \quad& \to\quad (\exists x:\ \neg E(x)) \tag{3} \\
        (\exists x:\ \neg E(x)) \quad& \to\quad \neg (\forall x:\ E(x)) \tag{4}
    \end{align}
    \begin{enumerate}
        \item[(1)] Es gelte $\nexists x : E(x)$. Sei nun $a$ ein beliebiges Objekt. Aus $E(a)\to\exists x: E(x)$ folgt per Kontraposition, dass $\neg E(a)$ gelten muss. Weil $a$ beliebig gewählt war, ist damit bewiesen, dass $\forall x: \neg E(x)$ gilt.
        \item[(4)] Ergibt sich aus \cref{gegenbeispiel}.
        \item[(2)] Wurde schon im Beweis von \cref{existenzwiderleg} gezeigt.
        \item[(3)] Für einen indirekten Beweis sei angenommen, dass $\nexists x: \neg E(x)$ gilt. Mit der (bereits bewiesenen) Implikation (1) folgt $\forall x: \neg\neg E(x)$, was mit der Regel der doppelten Verneinung zu $\forall x: E(x)$ vereinfacht werden kann. \qedhere
    \end{enumerate}
\end{proof}


\begin{bem}[* Vollständigkeit der erststufigen Prädikatenlogik] \label{goedelvollstaendig}
    Jede Formel, die bisher als Axiom gewählt oder hergeleitet wurde, ist eine Tautologie, d.h. wahr unter jeder möglichen (zweiwertigen) Interpretation im Sinne von \cref{def:interpretation}. Der \emph{Gödelsche Vollständigkeitssatz} besagt auch das Umgekehrte: Jede Tautologie (im Sinne zweiwertiger Interpretationen) lässt sich mithilfe der Axiome und Beweistechniken aus diesem Kapitel herleiten.
    
    In manchen Lehrbüchern und Vorlesungen werden die Junktoren über Wahrheitstafeln \emph{definiert} und Beweistechniken aus Wahrheitstafeln „hergeleitet“. Beispielsweise wird dort die Tatsache, dass die Formel $((A\to B)\land \neg B)\to \neg A$ eine (zweiwertige) Tautologie im Sinne von \cref{def:tautologie} ist, zum „Beweis“ erklärt dafür, dass die Beweistechnik der indirekten Widerlegung (\cref{reductio}) zulässig ist.

    Aufgrund des Vollständigkeitssatzes ist dieser Zugang legitim und liefert am Ende dieselben Beweistechniken, die im Laufe dieses Kapitels axiomatisch eingeführt wurden. In meinen Augen ist er jedoch irreführend, da er eine stufenweise Auseinandersetzung mit logischen Prinzipien verhindert und die Syntax von vornherein an eine unangemessen strikte Semantik koppelt (vgl. \cref{bivalenz}).
\end{bem}


\begin{bem}
    Eine Liste mit vielen aussagenlogischen und prädikatenlogischen Tautologien findest du in \cref{anhang:formelsammlung}. Such dir einmal zwei oder drei davon raus und versuche, sie zu beweisen.
\end{bem}





\clearpage
\section{Aufgabenvorschläge}


\begin{aufg}[(Un)Logische Schlussfolgerungen]
    Seien $A,B,C$ drei beliebige Aussagen und $E,F,G$ drei Eigenschaften. Beurteilt die nachfolgenden Schlussfolgerungen danach, ob sie logisch haltbar sind:
    \begin{enumerate}
        \item \begin{tabular}{l}
            Wenn sich niemand von uns ins Zeug legt, kriegen wir das Projekt nie \\
            \qquad im September fertig. \\
            Wir haben das Projekt im September fertig gekriegt. \\ \midrule
            Also gilt: Jeder von uns hat sich ins Zeug gelegt.
        \end{tabular}
        \item \begin{tabular}{l}
            Im Sterben sagen alle Menschen die Wahrheit. \\
            Im Sterben sagte Siddhartha: „Alles Geschaffene ist vergänglich.“ \\ \midrule
            Also gilt: Alles Geschaffene ist vergänglich.
        \end{tabular}
        \item \begin{tabular}{l}
            Entweder ist der Butler oder der Koch der Mörder. \\
            Entweder ist der Koch oder der Gärtner der Mörder. \\ \midrule
            Also gilt: Entweder ist der Butler oder der Gärtner der Mörder.
        \end{tabular}
        \item \begin{tabular}{r}
            $A\to B$ \\
            $C\to \neg B$ \\ \midrule
            $A\leftrightarrow \neg C$
        \end{tabular} \qquad\qquad\qquad \text{e)}\quad \begin{tabular}{r}
            $\nexists x:\ F(x)\land G(x)$ \\
            $\forall x:\ E(x)\to F(x)$ \\ \midrule
            $\nexists x:\ E(x)\land G(x)$
        \end{tabular} \qquad (\text{Modus Celarent})
        \item \begin{labeling}[font=\scshape]
            \item[Anna:] Wenn Ben verschläft, kommt er immer zu spät zur Vorlesung. Heute kam er schon wieder zu spät, also muss er mal wieder verschlafen haben.
            \item[Chloe:] Dir ist ein Fehlschluss unterlaufen. Du hast von $A\to B$ und $B$ auf $A$ geschlossen, aber diese Schlussweise ist nicht valide.
            \item[Anna:] Ups, stimmt ja. Also ist er heute mal pünktlich aufgestanden.
        \end{labeling}
    \end{enumerate}
\end{aufg}


\begin{aufg}[Fehlersuche I]
    Findet die Fehler in den folgenden Argumentationen\footnote{entnommen aus \cite{Vel06}} und beweist, dass alle drei Sätze falsch sind:
    \begin{enumerate}
        \item {\color{dred}\textbf{Satz}.}\enspace Seien $x,y\in \R$ mit $x+y=10$. Dann sind $x\neq 3$ und $y\neq 8$. \newline
        {\color{gray}\textbf{Beweis}.}\enspace Angenommen nicht. Dann wären $x=3$ und $y=8$ und damit $x+y=11\neq 10$. \qed
        \item {\color{dred}\textbf{Satz}.}\enspace Für alle $x,y\in \R$ ist $x^2+xy-2y^2=0$. \newline
        {\color{gray}\textbf{Beweis}.}\enspace Seien $x,y$ gleich einer beliebigen reellen Zahl $r$. Dann ist
        \[ x^2+xy-2y^2 = r^2+rr - 2r^2=0 \qed\]
        \item {\color{dred}\textbf{Satz}.}\enspace Seien $m,n\in \N_0$ mit $m$ gerade und $n$ ungerade. Dann ist $n^2-m^2=m+n$. \newline
        {\color{gray}\textbf{Beweis}.}\enspace Weil $m$ gerade ist, gibt es ein $k\in \N_0$ mit $m=2k$. Analog gibt es, da $n$ ungerade ist, ein $k\in \N_0$ mit $n=2k+1$. Es folgt
        \[ n^2-m^2 = (2k+1)^2-(2k)^2 = (4k^2+4k+1)-4k^2 = 2k+(2k+1) = m+n \qed \]
    \end{enumerate}
\end{aufg}


\begin{aufg}[Fehlersuche II]
    Analysiert den folgenden Beweis. Enthält er Fehler oder Lücken? Stimmt der Satz überhaupt?
    \begin{satz}
        Für jede natürliche Zahl $m$ existiert eine natürliche Zahl $n$ derart, dass keine der Zahlen $n+1,n+2,\dots , n+m$ eine Primzahl ist. Mit anderen Worten: Es gibt beliebig große Primzahllücken.
    \end{satz}
    \begin{proof}
        Für $m\in \N$ setze
            \[ n:= (1 \cdot 2 \cdot 3 \cdot \ldots \cdot m \cdot(m+1)) +1 \]
        Dann ist $n+1$ durch $2$ teilbar, $n+2$ durch $3$ teilbar und allgemein $n+k$ durch $k+1$ teilbar für jedes $k\le m$. Also ist keine der Zahlen $n+1,n+2,\dots , n+m$ eine Primzahl.
    \end{proof}
\end{aufg}


\begin{aufg}[Das Dorf der Lügner]
    Im beschaulichen Dörfchen Lügenscheid im Sauerland leben genau siebzig Menschen. Jeder dieser Einwohner 
    \begin{itemize}
        \item sagt entweder immer die Wahrheit
        \item oder aber alles was er sagt ist immer gelogen.
    \end{itemize}
    Fasziniert von dieser Begebenheit reist Beate Weiß, eine Mathematik-Postdoktorandin aus Wahrschau, deren Habilitation im Bereich der angewandten Logik seit Monaten von ihrer Fakultät ausgebremst wird, um sie solange es geht mit prekären befristeten Anstellungen bei der Stange zu halten, in das Dorf, um endlich einen Aufhänger für ihre Arbeit zu finden. Nachdem sie sich im Gasthaus eingerichtet hat, lädt sie alle siebzig Einwohner nacheinander zu einer Befragung ein, bei der sie nur eine einzige Frage stellt: „Wieviele Einwohner dieses Dorfs lügen immer?“
    
    Die erste Person, die zur Befragung erscheint, ein gutmütig aussehender, älterer Herr im Pullunder, sagt ihr, sie müsse sich keine Sorgen machen: im Dorf gebe es nur einen einzigen Lügner -- alle anderen Einwohner sagten dagegen immer die Wahrheit.
    
    Die zweite Person in der Befragung, eine großgewachsene, elegant gekleidete Dame mittleren Alters, sagt ihr, es gebe genau zwei Lügner im Ort.
    
    So geht es immer weiter: Die dritte Person meint, es gebe genau drei Lügner im Dorf, die vierte Person sagt, es gebe genau vier Lügner, usw.
    
    Als bereits der Abend angebrochen ist, erscheint endlich auch Einwohner Nummer siebzig, eine greise, etwas orientierungslos wirkende Dame, zur Befragung und krächzt: „Der Teufel soll uns holen. In diesem Dorf gibt es keinen einzigen ehrlichen Menschen. Wir alle sind dazu verflucht, tagein, tagaus zu lügen!“
    
    Frau Weiß ist zufrieden: innerhalb eines Tages ist es ihr gelungen, jeden einzelnen Bewohner des Dorfs zu befragen. Bei einem Bierchen in der Ortskneipe knobelt sie über dem Ergebnis ihrer Studie und versucht herauszufinden, wieviele Lügner es denn nun tatsächlich in Lügenscheid gibt.
    \begin{enumerate}
        \item Findet heraus, wieviele Lügner es in Lügenscheid gibt, und formuliert einen Beweis für eure Behauptung.
        \item Analysiert eure Argumentation. Welche Techniken (z.B. direkter Beweis, indirekter Beweis, Widerspruchsbeweis, Fallunterscheidung) kommen darin zum Einsatz? Kann der Beweis vielleicht noch vereinfacht werden?
    \end{enumerate}
\end{aufg}