4. Beweise

Oft haben Äußerungen über (mathematische) Objekte noch Parameter und sind für gewisse Werte dieser Parameter wahr und für andere falsch, z.B. Aussage $\sf A = x>0$ mit Parameter $\sf x$.

So etwas nennt man eine Aussagenform und es kann z.B. interessieren, für welche Werte sich welcher Wahrheitswert einstellt.

Quantoren

Für zwei spezielle Situationen gibt es eigene Symbole, die Quantoren:

• der Allquantor $\sf \forall$ wie in

• den Existenzquantor $\sf \exists$ wie in

Aussagen und ihre Beweise

Wesentlicher Inhalt der Mathematik: Aussagen und ihre Beweise.

Mit den vorgestellten Mitteln sind wir nun in der Lage, Behauptungen formal aufzuschreiben. Um diese formalen Behauptungen zu beweisen, bzw. die Aussagen auf Wahrheit zu prüfen, gibt es nun verschiedene Beweistechniken, die wir uns anschauen wollen.

Beweistechniken

Direkter Beweis

Im direkten Beweis startet man mit Aussagen, deren Richtigkeit angenommen wird und leitet daraus neue Aussagen her, die - unter dieser Annahme - dann auch gelten.

Widerspruchsbeweis

Man nimmt das Gegenteil der Behauptung an und leitet daraus einen Widerspruch her - und wenn das Gegenteil nicht sein kann, muss die Behauptung wahr sein.

Beispiele

• $\sf \sqrt{2}$ ist irrational (kein Bruch).

  Annahme: $\sf \sqrt{2} = \dfrac{p}{q} \Rightarrow 2 = \dfrac{p^2}{q^2} \Rightarrow 2q^2 = p^2,\ p \ \text{\sf und}\ q$ teilerfremd. Dann muss $\sf p$ gerade sein, $\sf p=2r \rightarrow q^2 = 2r^2 \rightarrow q$ gerade.

• "Ein Schachbrett, dem zwei diagonal gegenüberliegende Ecken fehlen, kann nicht mit $\sf 1\times 2-$Dominosteinen lücken- und überschneidungslos ausgefüllt werden"'

• Wir nehmen das Gegenteil an, also dass es eine Anordnung von Dominosteinen gibt, die das Feld ausfüllen.

• Jeder Dominostein belegt genau ein weißes und ein schwarzes Feld.

• Dann belegt eine beliebige Menge von Dominosteinen genauso viele weiße wie schwarze Felder.

• Das fragliche Gebiet hat aber nur 30 weiße (und 32 schwarze) Felder.

• Das ist der Widerspruch: wenn es eine Anordnung gäbe, würde sie einerseits genauso viele weiße wie schwarze Felder bedecken, andererseits aber zwei schwarze Felder mehr als weiße.

Vollständige Induktion

Eine andere Standardtechnik ist die vollständige Induktion: wenn eine Aussage $\sf A(n)$ für $\sf n=1$ wahr ist und für alle ganzen Zahlen $\sf n\geq 1$ die Implikation $\sf A(n)\Rightarrow A(n+1)$ gilt, dann ist $\sf A(n)$ für alle $\sf n\in\mathbb{N}$ wahr.

Beispiel

Für jedes $\sf n\in \mathbb{R}$ gilt $\sf \sum_{i=1}^n (2i-1) = n^2.$

Induktionsanfang: $\sf n=1$:

Induktionsschritt: sei $\sf n\geq 1$ und die Behauptung sei für $\sf n$ wahr.Dann gilt sie auch für $\sf n+1$:$\sf \def\arraystretch{1.25} \begin{array}{ccc} \sf \sum_{i=1}^{n+1} (2i-1) & \sf = & \sf \underbrace{\left(\sum_{i=1}^{n} (2i-1)\right)}_{\text{\sf $n^2$ (Induktionsvoraussetzung)}} + 2(n+1)-1 \\ \sf & \sf = & \sf n^2 + 2n + 1 \\ \sf & \sf = & \sf (n+1)^2\end{array}$

Aufgaben