In den Lektionen, die zu dieser Website gehören, werden immer wieder mathematische Sätze angeführt, in denen Behauptungen zu mathematischen Sachverhalten aufgestellt werden. In den meisten Fällen wird darauf hingewiesen, dass solche mathematischen Sätze eigentlich bewiesen werden müssen, worauf hier aber in den meisten Fällen verzichtet wird. Denn das Beweisen gehört zu den schwierigeren Dingen in der Mathematik. Nun wollen wir in dieser Lektion aber ein oft verwendetes Beweisverfahren betrachten, dass vor allem dann verwendet wird, wenn Aussagen über natürliche Zahlen getroffen werden. Vorher aber ein paar allgemeine Hinweise zu Beweisverfahren im allgemeinen.

Bereits der griechische Mathematiker Euklid wies darauf hin, dass jeder mathematische Beweis immer aus drei Schritten besteht.

Voraussetzung

Behauptung

Beweis(durchführung)

Die meisten zu beweisenden mathematischen Aussagen werden in der sogenannten "Wenn..., dann... -Form" angegeben, weil diese Aussageform gut erkennen lässt, was Voraussetzung und was Behauptung ist. Betrachten wir ein Beispiel aus der Geometrie. Ein Beweis einer Aussage erfolgt durch eine endliche Kette wahrer Aussage, wobei nur die Voraussetzung der Aussage selbst, andere bereits bewiesene Sätze, logische Gesetze und äquivalente Umformungen verwendet dürfen. Für die Beweisführung unterscheidet man generell zwischen zwei Arten det Beweisführung.

• Der direkte Beweis

  Ausgangspunkt eines direkten Beweises sind bereits bewiesene Aussagen und deren jeweilige Voraussetzungen, die schrittweise zusammengesetzt zur Behauptung führen. Betrachten wir den Innenwinkelsatz für Dreiecke.

  ε und δ sind die Winkel, die durch die Parallele (blau) zur Strecke AB des Dreiecks ABC entstehen. Dann gilt: ( I )   δ  =  β   →   Wechselwinkelsatz ( II )   ε  =  α   →   Stufenwinkelsatz ( III )   ε  +  δ  +  γ  =  180°   →   gestreckter   Winkel ⇒   α  +  β  +  γ  =  180° q.e.d.

  Der Beweis nutzt den Wechselwinkelsatz, den Innenwinkelsatz und die Eigenschaft des gestreckten Winkels als bereits bewiesene Aussagen und fürht damit zur Behauptung des Innenwinkelsatzes.
  Wir halten fest: Beim direkten Beweis geht man von der Voraussetzung aus und leitet durch die schrittweises Begründen mit Hilfe bereits bewiesener Aussagen die Behauptung her.

• Der indirekte Beweis

  Ganz anders funktioniert ein indirekter Beweis. Hier wird im ersten Schritt die Behauptung negiert, diese wird also als nicht gültig angenommen. Danach werden ebenfalls mit Hilfe wahrer Aussagen schrittweise Schlüsse gezogen, die am Ende aber zu einem Widerspruch zur Voraussetzung oder anderer bewiesenen Sätze führen. Diesen Widerspruch kann man nur auflösen, indem man die Behauptung als wahr annimmt.
  Auch hier soll ein Beispiel (aus dem Bereich der Zahlentheorie) betrachtet werden.

  Im Unterricht der Klasse 9 wird der Zahlbereich der rationalen Zahlen auf den Bereich der reellen Zahlen erweitert. Dazu muss man natürlich nachweisen, dass es Zahlen gibt die nicht-rational sind. Daraus ergibt sich zum Beispiel der Satz:

  √2 ist keine rationale Zahl.

  Indirekter Beweis:
  Annahme der Negation der Behauptung: √2 sei eine rationale Zahl.
  → Daraus folgt, dass man √2 als gemeinen Bruch darstellen kann

  √ 2

  =

  p q,

  wobei

  p

  und

  q

  teilerfremd

  sein

  müssen.

  Quadieren liefert:

  ( √ 2 ) 2

  =

  ( p q ) 2

  Daraus folgt aufgrund der Potenzgesetze

  2

  =

  p 2 q 2

  |

  ·

  q 2

  →

  Äquivalenzumformung

  2q 2

  =

  p 2

  → p² ist eine gerade Zahl.
  → p ist eine gerade Zahl.
  → Man kann p=2r (r∈Z) setzen.
  Einsetzen liefert

  2q 2

  =

  ( 2r ) 2

  →

  2q 2

  =

  4r 2

  |

  :

  2

  →

  q 2

  =

  2r 2

  Daraus folgt, dass q² und deshalb auch q gerade Zahlen sind.
  Damit wären beide Zahlen p und q gerade und deshalb nicht teilerfremd. Das ist ein Widerspruch zur gemachten Annahme.
  q.e.d.

  Wir halten fest. Beim indirekten Beweis nehmen wir zunächst an, dass das Gegenteil der Behauptung gilt. In den folgenden Schritten des Beweises ergibt sich dann ein Widerspruch zu dieser Annahme, weshalb die eigentlich Behauptung gelten muss.

zurück

Dieses Beweisverfahren beruht auf den grundlegenden Eigenschaften der natürlichen Zahlen. Diese hier nicht zu beweisenden Eigenschaften sind:
1. Die Menge der natürlichen Zahlen besitzt ein kleinstes Element, die Zahl Null.
2. Jede natürliche Zahl n besitzt einen Nachfolger (n+1).
3. Die Menge der natürlichen Zahlen ist unendlich, es existiert kein größtes Element.

Auf Grundlage dieser Eigenschaften wird das Prinzip der vollständigen Induktion eingeführt.
⇒ Satz: Prinzip der vollständigen Induktion

Die Ausssage "Für alle natürlichen Zahlen n gilt H(n).", wenn folgendes gilt: 1. H(n) ist richtig für n=0. 2. Aus der Gültigkeit von H(n) für n=k folgt stets die Gültigkeit für n=k+1. Dabei ist k eine beliebige natürliche Zahl.

Auf den Beweis dieses Satzes soll hier verzichtet werden. Viel wichtiger ist es, daraus die Beweisschritte abzuleiten. Das Beweisverfahren besteht aus zwei Schritten.

(1.) Induktionsanfang
Man zeigt, dass die Aussage H(0) gilt.
(2.) Induktionsschritt
Man formuliert die (2.1.) Induktionsvoraussetzung, d.h. die Richtigkeit von H(k) wird vorausgesetzt.
Man stellt die (2.2.) Induktionsbehauptung auf, also die Aussage, die sich für H(k+1) ergibt.
Schließlich folgt der (2.3.) Induktionsbeweis), bei dem unter Verwendung der Induktionsvoraussetzung durch logisches Schließen die Induktionsbehauptung hergeleitet wird.

Am besten schauen wir uns das an einem einfachen Beispiel an.
zurück

An dieser Stelle soll kurz auf die Begriffe "Induktion" und "Deduktion" eingegangen werden, da damit zwei prinzipielle Vorgehensweisen beim logischen Herleiten neuer Aussagen beschrieben werden.

Der deutsche Astronom Johannes Kepler (1571-1630) schloss aus seinen Beobachtungen und Berechnungen ein grundlegendes Gesetz für die Bewegung von Planeten, das er im "Ersten Keplerschen Gesetz" zusammenfasste. Es lautet:
"Die Bahnen der Planeten sind Ellipsen, in deren einem Brennpunkt die Sonne steht."
Er verallgemeinerte die Beobachtungen der Bewegung einzelner Planeten zu einem Gesetz, das für alle Himmelskörper gelten sollte. Eine solche Vorgehenweise bezeichnet man als Induktion.

Betrachten wir ein anderes Beispiel.
Anfang des 19. Jahrhunderts beobachteten Astronomen, dass die Bewegungen des Uranus nicht so verliefen, wie man es erwartet hatte. Diese Abweichungen wurden auf der Grundlage des "Gravitationsgesetzes" mit der Existenz eines unbekannten Planeten begründet. Der französische Astronom Leverrier (1811-1877) berechnete aus den Abweichungen die Bahnelemente des angenommenen Planeten und der deutsche Astronom Galle (1812-1910) fand ihn am berechneten Ort. Dieser neue Planet wurde "Neptun" genannt.
Bei dieser Art der Schlussfolgerung ging man also vo der Gültigkeit des allgemeinen Gravitationsgesetzes aus und wies die Gütligkeit für ein spezielles Objekt (den neuen Planeten) nach. Diese Vorgehensweise wird als Deduktion bezeichnet.

Zusammengefasst kann man also festhalten:

Spezielle Aussagen		Allgemeine Aussage
Spezielle Aussagen		Allgemeine Aussage

Es bleibt natürlich die Frage nach der Wahrheit von Aussagen, die man durch diese Vorgehensweisen erhalten hat.Als gesichert kann man betrachten.

Von wahren Aussagen gelangt man durch deduktives Schießen stets wieder zu wahren Aussagen.

Von wahren Aussagen gelangt man durch induktives Schießen nicht immer zu wahren Aussagen.

Das Verfahren der vollständigen Induktion ist ein deduktives Verfahren.

zurück

Induktive Definitionen stehen in engem Zusammenhang mit dem gleichnamigen Beweisverfahren. Mit dieser Art von Definitionen können Funktionen erklärt werden, deren Definitionsbereich die Menge der natürlichen Zahlen ist. Auch hier gibt es einen Anfang durch Festlegen von f(0) und einen "Schritt von n zu (n+1)", indem der Funktionswert f(n+1) festgelegt wird.

Im speziellen soll hier die Definition der Fakultätsfunktion eingegangen werden.
⇒ Defintion Fakultätsfunktion

Die Funktion f(n)=n! (n∈N) besteht aus allen geordneten Paaren [n; n!], für die gilt: 1. Rekursionsanfang f ( 0 )  =  1 2. Reduktionsschritt f ( k  +  1 )  =  ( k  +  1 )  ·  f ( k ) ;   k  ∈  N

Der Ausdruck n! wird gesprochen als "n Fakultät". Aus der Definition folgt zum Beispiel

5!

=

1

·

2

·

3

·

4

·

5

=

120

Gesprochen "5 Fakultät ist gleich 120". Analog gilt dann:

n!

=

1

·

2

·

3

·

4

·

...

·

n

Eine der wichtigsten Anwendungen dieser Funktion findet sich in der Definition des Binomialkoeffizienten.