\documentclass{uebblatt}

\geometry{tmargin=2.7cm,bmargin=2.7cm,lmargin=3.1cm,rmargin=3.1cm}

\newenvironment{indentblock}{%
  \list{}{\leftmargin\leftmargin}%
  \item\relax
}{%
  \endlist
}

\newcommand{\hil}[1]{\textcolor{blue}{#1}}

\newcommand{\vorlage}{\textbf{\textsf{Vorlage.}}\xspace}
\newcommand{\beispiel}{\textbf{\textsf{Beispiel.}}\xspace}
\newcommand{\antibeispiel}{\textbf{\textsf{Nichtbeispiel.}}\xspace}

\begin{document}

\vspace*{-5em}

\let\raggedsection\centering
\section*{Beweistechniken}
\let\raggedsection\raggedright

\begin{center}
\rotatebox{90}{\tiny\qquad\qquad\href{http://abstrusegoose.com/353}{http:/\!/abstrusegoose.com/353}}%
\includegraphics[width=0.5\textwidth]{images/saint_curious_george.png}
\end{center}


Bis man zum eigentlichen Kern eines mathematischen Problems vordringt, muss man
im Allgemeinen mehrere Definitionen entfalten. Das gelingt meist mit der
Technik des direkten Beweisens ("`immer der Nase nach"').

\beispiel Seien $f : X \to Y$ und $g : Y \to Z$ zwei Abbildungen. Wir
wollen zeigen:
\[ \text{$f$ injektiv} \,\wedge\, \text{$g$ injektiv} \ \Longrightarrow\ 
  \text{$g \circ f$ injektiv}. \]
Mit den auf der Rückseite beschriebenen Vorlagen lautet ein sehr ausführlicher Beweis wie
folgt:

\begin{indentblock}
\small
Gelte, dass~$f$ und~$g$ injektiv sind. Um dann die Injektivität von~$g
\circ f$ zu zeigen, seien~$x, \tilde x \in X$
beliebig und gelte~$(g \circ f)(x) = (g \circ f)(\tilde x)$. Nach Definition
der Abbildungsverkettung gilt also
\begin{align*}g(f(x)) &= g(f(\tilde x)). \\
\intertext{Da $g$ injektiv ist, folgt daraus}
f(x) &= f(\tilde x). \\
\intertext{Da auch $f$ injektiv ist, folgt daraus wiederum}
x &= \tilde x. \\
\intertext{Das war zu zeigen.}\end{align*}
\end{indentblock}
\vspace{-2em}
Der Kern der Argumentation liegt in den Folgerungen zwischen den drei
abgesetzten Gleichungen, der Vorbau ist aber trotzdem wichtig; insbesondere ist
es wichtig, die Variablen~$x$ und~$\tilde x$ richtig einzuführen.
Setzt man Vertrautheit des Lesers mit den Voraussetzungen der
Angabenstellung voraus, kann man den Beweis etwas kürzer auch so formulieren:
\begin{indentblock}
\small
Seien~$x, \tilde x \in X$ beliebig mit~$(g \circ f)(x) = (g \circ f)(\tilde
x)$. Dann folgt:
\[ g(f(x)) = g(f(\tilde x)) \ \stackrel{\text{$g$ inj.}}{\Longrightarrow}\ 
   f(x) = f(\tilde x) \ \stackrel{\text{$f$ inj.}}{\Longrightarrow}\ 
   x = \tilde x, \]
das war zu zeigen.
\end{indentblock}
Mathematische Beweise sind in erster Linie (deutsche, englische, \ldots)
\emph{Texte}. Natürlich kommen in Beweisen Formeln durchaus vor, aber von der
äußeren Struktur her muss ein Beweis eine logisch schlüssige Argumentation
sein. Daher ist folgender Beweisversuch ungenügend:
\begin{indentblock}
\small
\[ g(f(x)) = g(f(\tilde x)) \qquad
   f(x) = f(\tilde x) \qquad
   x = \tilde x \]
\end{indentblock}


\let\raggedsection\centering
\section*{Direkter Beweis}
\let\raggedsection\raggedright

\subsection*{Konjunktion ("`und"')}

Um \hil{$A \wedge B$} direkt zu zeigen, muss man sowohl~$A$ als auch~$B$ zeigen.

\vorlage Da \ldots, gilt $A$. Da außerdem \ldots, gilt auch~$B$.


\subsection*{Disjunktion ("`oder"')}

Um \hil{$A \vee B$} direkt zu zeigen, muss man zeigen, dass~$A$ oder~$B$ (oder beide
-- das sagt man selten dazu) gelten. Meistens muss man dazu eine
Fallunterscheidung führen.

\begin{tabbing}
  \vorlage \= \kill
  \vorlage \> Wegen $\ldots$ können nur folgende Fälle eintreten: \\
  \> \emph{Fall 1}: Wegen~$\ldots$ gilt dann~$A$. \\
  \> \emph{Fall 2}: Wegen~$\ldots$ gilt dann~$B$.
\end{tabbing}


\subsection*{Negation (Verneinung)}

Um~\hil{$\neg A$} direkt zu zeigen, zeigt man, dass die Annahme, dass~$A$ doch stimmt,
zu einem Widerspruch führt.

\vorlage Angenommen, es gilt doch~$A$. Dann \ldots, das kann nicht sein.


\subsection*{Implikation ("`wenn, dann"')}

Um \hil{$A \Rightarrow B$} direkt zu zeigen, setzt man die Gültigkeit von~$A$ voraus
und zeigt dann~$B$. Ob~$A$ tatsächlich stimmt, ist für die Argumentation nicht
relevant, es geht nur um die hypothetische Schlussfolgerung.

\vorlage Gelte~$A$. Dann \ldots, daher gilt~$B$.


\subsection*{Äquivalenz ("`genau dann, wenn"')}

Um \hil{$A \Leftrightarrow B$} direkt zu zeigen, zeigt man~$A \Rightarrow B$
(die sog. Hinrichtung) und~$B \Rightarrow A$ (die sog. Rückrichtung). Ob
dabei~$A$ und~$B$ tatsächlich stimmen, ist nicht relevant.

\begin{tabbing}
  \vorlage \= \kill
  \vorlage \> "`$\Rightarrow$"': Gelte~$A$. Dann \ldots, daher gilt~$B$. \\
  \> "`$\Leftarrow$"': Gelte~$B$. Dann \ldots, daher gilt~$A$.
\end{tabbing}

Manchmal sind die Beweise der beiden Richtungen so ähnlich, dass man sie zu
einem zusammenfassen kann:

\begin{tabbing}
  \vorlage \= \kill
  \vorlage \> $A$ gilt genau dann, wenn \ldots; das ist genau dann der
Fall, wenn \ldots; \ldots; \\
  \> das ist genau dann der Fall, wenn~$B$ gilt.
\end{tabbing}

Oder kürzer notiert:

\vorlage $A \Leftrightarrow \ldots \Leftrightarrow \ldots
\Leftrightarrow \ldots \Leftrightarrow \ldots \Leftrightarrow B.$


\subsection*{Allquantifikation ("`für alle"')}

Um \hil{$\forall x\in X{:}\, A(x)$} direkt zu zeigen, zeigt man, dass für
jedes~$x \in X$ jeweils die Aussage~$A(x)$ gilt. Das macht man durch ein
einziges, einheitliches Argument.

\vorlage Sei~$x \in X$ beliebig. Da \ldots, gilt~$A(x)$.

Der bei den Auslassungspunkten auszuführende Beweis darf dabei von~$x$ nur
voraussetzen, dass es ein Element der Menge~$X$ ist: Der Beweis muss mit
jedem~$x \in X$ zurechtkommen.

\beispiel Wir möchten zeigen: $\forall x \in \RR{:}\, (x+1)^2 = x^2 + 2x + 1$.
Das geht so: Sei~$x \in \RR$ beliebig. Dann gilt~$(x+1)^2 = (x+1) \cdot (x+1) =
x^2 + x\cdot1 + 1\cdot x + 1\cdot1 = x^2 + 2x + 1$.

Der folgende Versuch gibt dagegen keinen gültigen Beweis ab. Er setzt implizit
von~$x$ voraus, dass~$x$ größer als 2 ist.

\antibeispiel Sei~$\PP$ die Menge aller Primzahlen. Wir möchten versuchen,
die falsche Behauptung "`$\forall x \in \PP{:}\, \text{$x$ ist
ungerade}$"' nachzuweisen. Das scheint so zu gehen: Sei~$x \in \PP$ beliebig.
Wenn~$x$ durch~2 teilbar wäre, so bestünde~$x$ aus mehr als einem Primfaktor
und wäre daher nicht prim. Nach Voraussetzung ist~$x$ aber prim. Somit ist~$x$
nicht durch~2 teilbar, also ungerade.


\subsection*{Existenzquantifikation ("`es gibt"')}

Um \hil{$\exists x \in X{:}\, A(x)$} direkt zu zeigen, gibt man explizit ein~$x
\in X$ an, für das~$A(x)$ gilt. Um eine geeignete Definition für~$x$ zu finden,
benötigt man meist etwas Kreativität. Gelegentlich kann es helfen, diese Stelle
im Beweis zunächst freizulassen und mit dem Rest des Beweises fortzufahren; so
kann man auf eine Idee kommen, wie~$x$ zu setzen ist.

\begin{tabbing}
  \vorlage \= \kill
  \vorlage \> Setze~$x \defeq \ldots$. Dann liegt~$x$ in der Tat in~$X$,
denn \ldots; und wegen \ldots{} gilt~$A(x)$.
\end{tabbing}

\beispiel Seien~$p_1,\ldots,p_n$ irgendwelche Primzahlen. Wir möchten die
Behauptung "`$\exists x \in \NN{:}\, \text{$x$ ist prim und
ungleich~$p_1,\ldots,p_n$}$"' zeigen. Das geht so: Wir definieren~$N \defeq p_1
\cdots p_n + 1$. Da~$N$ mindestens 2 ist, besteht~$N$ aus irgendwelchen
Primfaktoren. Nennen wir den ersten von ihnen~$x$. [Jetzt haben wir unseren
Kandidat für~$x$ gefunden!] Diese Zahl~$x$ ist also prim
und zudem ungleich den~$p_1,\ldots,p_n$ (denn~$N$ ist durch diese Zahlen nicht
teilbar -- es bleibt der Rest~1). [Und somit haben wir bestätigt, dass~$x$ alle
Anforderung erfüllt.]

Bemerkenswert ist, dass die Definition von~$N$ (und somit von~$x$) unser
eigener Einfall war. In der Formulierung der zu zeigenden Behauptung kam sie
nicht vor.


\subsection*{Teilmengenbeziehung}

Um~\hil{$X \subseteq Y$} direkt zu zeigen, wobei~$X$ und~$Y$ Mengen sind,
zeigt man, dass jedes Element von~$X$ auch in~$Y$ liegt.

\vorlage Sei~$x \in X$ beliebig. Dann \ldots, daher gilt~$x \in Y$.


\subsection*{Gleichheit von Mengen}

Um~\hil{$X = Y$} direkt zu zeigen, zeigt man~$X \subseteq Y$ und~$Y \subseteq
X$.

\begin{tabbing}
  \vorlage \= \kill
  \vorlage \> "`$\subseteq$"': Sei~$x \in X$ beliebig. Dann \ldots,
  daher gilt~$x \in Y$. \\
  \> "`$\supseteq$"': Sei~$y \in Y$ beliebig. Dann \ldots, daher gilt~$y \in
  X$.
\end{tabbing}

Manchmal kann man die beiden Teilbeweise auch zu einem kombinieren.


\subsection*{Gleichheit von Abbildungen}

Um \hil{$f = g$} direkt zu zeigen, wobei~$f$ und~$g$ beides Abbildungen
$X \to Y$ sind (also dieselbe Definitions- und Zielmenge haben), zeigt
man, dass die beiden Funktionen an allen Stellen ihres Definitionsbereichs
übereinstimmen.

\vorlage Sei~$x \in X$ beliebig. Dann \ldots, daher gilt~$f(x) = g(x)$.


\let\raggedsection\centering
\section*{Beweis durch Widerspruch}

Um eine Aussage~$A$ zu zeigen, kann man auch zeigen, dass die Annahme von~$\neg
A$ zu einem Widerspruch führt.

\vorlage Angenommen,~$A$ wäre falsch. Dann \ldots, das kann nicht sein.


\section*{Beweis durch Kontraposition}

Um eine Implikation der Form~$A \Rightarrow B$ zu zeigen, kann man auch~$\neg B
\Rightarrow \neg A$ zeigen, d.\,h. unter der Voraussetzung von~$\neg B$ einen
Beweis von~$\neg A$ führen.
Das ist häufig dann hilfreich, wenn~$A$ und~$B$ selbst negierte Aussagen sind.

\beispiel Wenn man sich direkt an einem Beweis der Implikation
\begin{align*}\text{$k$ ist undorig} &\ \Longrightarrow\  \text{$k$ ist unfoberant} \\
\intertext{versucht,
wird man durch die vielen Verneinungen vielleicht verwirrt. Möglicherweise ist
es daher einfacher, die Kontraposition}
\text{$k$ ist foberant} &\ \Longrightarrow\  \text{$k$ ist dorig} \\
\intertext{zu zeigen.}\end{align*}
\vspace{-3.5em}


\section*{Beweis durch Induktion}

Die Beweistechnik der Induktion kann man (nur) auf Behauptungen der Form "`für
alle natürlichen Zahlen gilt"' oder "`für alle natürlichen Zahlen ab 47 gilt"'
anwenden. Wenn man sie verwendet, beweist man eine Allaussage der Form~"`$\forall n \in
\NN{:}\, P(n)$"' weder durch Überprüfen aller unendlich vieler Fälle noch
durch einen direkten Beweis ("`Sei~$n \in \NN$ beliebig. Dann gilt~$P(n)$, denn
$\ldots$"').

Stattdessen weist man getrennt voneinander Induktionsanfang und Induktionsschritt nach:
\[ P(0) \qquad\wedge\qquad \forall n\in\NN{:}\, (P(n) \Rightarrow P(n+1)) \]

Das notiert man auf die in der Vorlesung und in den Übungen besprochene Art und
Weise:

\begin{tabbing}
  \vorlage \= Induktionsschritt~$n \to n+1$: \= \kill
  \vorlage \> Beweis durch Induktion über~$n$. \\
  \> Induktionsanfang~$n = 0$: \> Es gilt~$P(0)$, denn \ldots \\
  \> Induktionsschritt~$n \to n+1$: \> Sei~$n \in \NN$ beliebig. Gelte die
  Induktionsvoraussetzung~$P(n)$. \\
  \> \> Dann gilt~$P(n+1)$, denn \ldots
\end{tabbing}

\end{document}
