dh-Materialien
Mathematische Begriffe
 

Vollständige Induktion


Die Peano’schen Axiome nach oben

Mit Hilfe seiner Axiome hat Giuseppe Peano (1858 - 1932) die grundlegenden Eigenschaften der Menge der natürlichen Zahlen beschrieben:

(1) 0 ist eine natürliche Zahl.
(2) Jede natürliche Zahl hat einen Nachfolger und dieser ist wieder eine natürliche Zahl.
(3) Enthält eine Menge S die Zahl 0 und mit jeder natürlichen Zahl auch stets deren Nachfolger, so enthält S alle natürlichen Zahlen.
(4) Sind die Nachfolger zweier natürlicher Zahlen a und b einander gleich, so gilt a = b.
(5) Kein Nachfolger einer natürlichen Zahl ist gleich der Zahl 0.

Die Formulierung dieser Axiome ist nicht ganz unproblematisch, denn die Begriffe „Zahl“, „0“ und „Nachfolger“ werden in (1) bis (5) im mathematischen Sinne nicht definiert.

Es gibt zu dem Axiomensystem (1) bis (5) von Peano folgende äquivalente Alternative unter Benutzung des Begriffs der Abbildung:

(I)   ℕ ist eine nichtleere Menge.
(II)  Es gibt eine injektive Abbildung succ: ℕ → ℕ.
(III) Genau ein Element in hat kein Urbild unter succ. Dieses Element soll „0“ heißen.
(IV) Sei M eine Teilmenge von mit folgenden Eigenschaften:
      (i)  0 ∈ M
      (ii) m ∈ M succ(m) ∈ M
      Dann folgt: M = .

Mit dieser Beschreibung von handelt man sich ein anderes Problem ein: Die Axiome (II) und (III) zur Definition der Abbildung succ auf der Menge setzt die Existenz von bereits voraus, obwohl ja erst mit Hilfe des Axiomensystems (I) bis (IV) die Menge definiert werden soll.

Man kann es drehen und wenden wie man will, im Grunde wird gefordert, dass eine wohlgeordnete und unendliche Menge ist mit 0 ∈ ℕ als kleinstem Element, und man setzt axiomatisch fest, dass die  Wohlgeordnetheit von mit der injektiven Abbildung succ gewährleistet ist.

Mit anderen Worten: Das elementare Tun des Hintereinanderreihens von wohlunterschiedenen Objekten, das heißt der Prozess des Zählens, wird von Peano nicht begründet und nicht hinterfragt.

Sei M eine nichtleere Menge gleichartiger Objekte und

R M x M = { (x;y):  xund  yM } 

eine Relation auf M. Dann heißt R genau dann Halbordnung, wenn für alle  x, y, zM  Folgendes gilt:

x R y  und  y R z  ⇒  x R z   (Transitivität)
x R y  und  y R x  ⇒  x = y   (Identitivität)
x R x
  (Reflexivität)

Existiert für eine Menge eine solche Halbordnung, so sagt man: „M ist teilweise geordnet“.

Gilt außerdem noch

x, yM  ⇒  x R y  oder  y R x  

dann heißt M total geordnet (oder linear geordnet).


Eine wohlgeordnete Menge ist eine teilweise geordnete Menge M, in der jede nichtleere Teilmenge T ein kleinstes Element xmin besitzt, das heißt für jede Teilmenge T  M muss gelten:

xmin T:  xmin R x  für alle x T

Die Menge der natürlichen Zahlen ist wohlgeordnet ( Beweis).

Alle Gesetze der natürlichen Zahlen (inklusive aller vertrauten Rechenregeln in ) beruhen im Wesentlichen auf der Tatsache, dass man die natürlichen Zahlen abzählen kann. Für die Herleitung der Gesetze in nur unter Voraussetzung der Axiome (I) bis (IV) formuliert man zweckmässigerweise auf Grundlage des Axioms (IV) das sogenannte Prinzip der vollständigen Induktion:


Das Prinzip der vollständigen Induktion nach oben

Wenn für irgendeine Aussage E, die in Abhängigkeit von n ∈ ℕ formuliert werden kann, gilt:
      (i)   E(0) ist wahr;
      (ii)  E(m) ist wahr für ein m ∈ ℕ   E(succ(m)) ist wahr,
dann folgt: E(n) ist wahr für alle n ∈ ℕ.

(i) heißt Induktionsanfang und (ii) heißt Induktionsschluss.

E(m) ist wahr für ein m ∈ ℕ“ heißt Induktionsvoraussetzung (oder Induktionsannahme).

Oftmals führt man einen Induktionsbeweis nur über einer (natürlich nach oben nicht beschränkten) Teilmenge von aus. Dann kann man auf Grundlage des Induktionsprinzips wie folgt argumentieren:

Wenn für irgendeine Aussage E, die in Abhängigkeit von n ∈ ℕ mit n  k formuliert werden kann, gilt:
      (i)   E(k) ist wahr;
      (ii)  E(m) ist wahr für ein m ≥ k   E(succ(m)) ist wahr,
dann folgt: E(n) ist wahr für alle n  k.

Richard Dedekind (1831−1916) hat in seiner Schrift Was sind und was sollen Zahlen? 1887 das Induktionsprinzip nicht als Axiom, sondern als beweisbaren Satz präsentiert. Dies liegt daran, dass Dedekind auf (nach heutigem Sprachgebrauch) mengentheoretischem Wege zu einer Charakterisierung der natürlichen Zahlen gelangt und dann hieraus den Satz der vollständigen Induktion ableitet. Der wesentliche Begriff hierbei ist der der „Kette“. Im Folgenden soll die Dedekind'sche Argumentation in heutiger Terminologie ( Definitionen) vorgestellt werden.

Sei K eine nichtleere Teilmenge einer gegebenen Menge S und φ: S S eine injektive Abbildung,
das heißt es gilt  a ǂ b  φ(a) ǂ φ(b) für alle a, b  S.
Dann heißt K eine φ-Kette (oder kurz Kette), wenn φ(K) K ist.

Sei A irgendeine nichtleere Teilmenge einer gegebenen Menge S und
φ: S S eine injektive Abbildung.
Dann heißt die Schnittmenge all derjenigen φ-Ketten K, für welche A K gilt, die Kette von A.
Die Kette von A soll mit KA bezeichnet werden.
Besteht die Menge A nur aus einem einzigen Element a, so soll Ka geschrieben werden.

Da S eine Kette ist, ist KA nie leer.
K
A ist die Schnittmenge von φ-Ketten, also ist KA ebenfalls eine φ-Kette.
Damit ist die Bezeichnung „Kette von A“ für KA gerechtfertigt.

Mit den eben verwendeten Bezeichnungen folgt unmittelbar

(K1)  A KA
(K2)  φ(KA)  KA
(K3)  A K   KA K.

A und B seien nichtleere Teilmengen von S, φ: S  S sei eine injektive Abbildung und es gelte A  B.
Dann gilt auch φ(A) φ(B) und mit (K1) folgt φ(A) φ(KA). Wegen (K2) hat man dann φ(A)  KA.

Sei M eine nichtleere Teilmenge von S. Dann gilt

M K   KM KA.

Beweis:
“: Aus  M KA  folgt unter Verwendung von (K3): KM KA, denn KA ist eine Kette.
“: Zusammen mit  M KM  folgt aus  KM KA:  M KA.

 Es gilt ferner

M K   φ(M) KA.

Beweis:
Aus  M KA  folgt aus dem vorherigen Satz  KM KA.
Zusammen mit  φ(M)  KM (wegen K2) folgt die Behauptung.

Der Dedekind' sche Satz der vollständigen Induktion lautet nun wie folgt:

Sei A irgendeine nichtleere Teilmenge einer Menge S und φ: S S eine injektive Abbildung.
Sei P irgendeine weitere Menge. Wenn gezeigt werden kann, dass

(1)  A P
(2)  φ(s)  P für alle s KAP,

dann gilt KA P.

Beweis:
Die Schnittmenge  KAP  wird im Folgenden mit G bezeichnet.
Es ist  A KA  und wegen (K1) A P folgt  A G.  G ist also eine nichtleere Menge.
G KA  und  KA S (wegen K3). Also folgt  G S.
Ferner folgt aus  G KA  wegen des zuletzt bewiesenen Satzes:  φ(G) KA.

Aufgrund der Bedingung (2) gilt φ(G) P.
Zusammen mit  φ(G) KA  folgt somit: φ(G) G, also ist G eine Kette.
Aus  A G  folgt hieraus wegen (K3) KA G.

Es gilt also gleichzeitig  G KA und  KA G. Also ist  KA = KAP.
Hieraus folgt die Behauptung.

Wenn man P interpretiert als Menge von Objekten, die allesamt eine bestimmte Eigenschaft E besitzen und zeigen kann, dass (1) alle Elemente aus A diese Eigenschaft besitzen und (2) das Bild φ(s) jedes Elements s  KA, das diese Eigenschaft besitzt, diese Eigenschaft ebenfalls hat, dann folgt mit dem Induktionssatz, dass alle Elemente der Kette KA die Eigenschaft E haben.

Eine Menge N mit dem Grundelement e heißt abzählbar unendlich, wenn folgende Bedingungen erfüllt sind:

(a) Es gibt eine Abbildung  φ: N N  mit φ(N) N.
(b) N = Ke.
(c) e ist nicht in φ(N) enthalten.
(d) Die Abbildung φ ist injektiv.

φ(n) mit n N wird das auf n folgende Element genannt. 

Dies ist im Wesentlichen die Dedekind'sche Charakterisierung einer abzählbar unendlichen Menge (von ihm damals einfach unendliche Menge genannt) und er sagt:

„Wenn man bei der Betrachtung eines einfach unendlichen, durch eine Abbildung φ geordneten Systems N von der besonderen Beschaffenheit der Elemente gänzlich absieht, lediglich ihre Unterscheidbarkeit festhält und nur die Beziehungen auffasst, in die sie durch die ordnende Abbildung φ zueinander gesetzt sind, so heißen diese Elemente natürliche Zahlen oder Ordinalzahlen...“
(R. Dedekind: Was sind und was sollen Zahlen?, Braunschweig 19113, S. 17)

Für jede natürliche Zahl n gilt

Kn = { n } φ(Kn).

Beweis:
Sei n irgendeine natürliche Zahl und φ(n) Teil einer φ-Kette L.
Setzt man K = {n} L, so ist φ(K) = {φ(n)} φ(L).
φ(L) L, weil L eine Kette ist, {φ(n)} L nach Voraussetzung, also folgt φ(K) L.
Da L K folgt φ(K) K und damit ist bewiesen, dass K = {n} L eine Kette ist.

Nun soll gezeigt werden, dass das Bild der Kette von n gleich der Kette des Bildes von n ist,
das heißt:

φ(Kn) = Kφ(n).

Kφ(n) ist eine φ-Kette, also gilt (wegen K1) φ(n) ∈ Kφ(n).
Nach dem Vorhergehenden gibt es dann eine Kette K mit n K und φ(K) Kφ(n).
Mit (K3) folgt Kn K und hiermit gilt auch φ(Kn) φ(K).
Aus φ(Kn) φ(K) und φ(K) Kφ(n) folgt φ(Kn) Kφ(n).

Andererseits ist wegen (K1) n ∈ Kn und damit auch φ(n) φ(Kn).
φ(Kn) ist als Bild der Kette Kn wieder eine Kette. Also folgt mit (K3): Kφ(n) φ(Kn).

Aus φ(Kn) Kφ(n) und Kφ(n) φ(Kn) folgt φ(Kn) = Kφ(n).

Sei nun K = {n} φ(Kn).
Weil φ(Kn) eine Kette ist, ist auch K eine Kette (siehe oben).
Nach Definition ist n K, also folgt mit (K3) Kn K.

Nach (K1) ist n Kn und nach (K2) Kφ(n) = φ(Kn) Kn.
Aus {n}   Kn und φ(Kn) Kn folgt K Kn.

Aus  Kn K  und  K Kn  folgt die Behauptung.

Es folgt unmittelbar

N = { e } φ(N).

Dies bedeutet, dass jede von der Grundzahl e verschiedene Zahl Element von φ(N) ist, das heißt, jede natürliche Zahl n mit  n ǂ e  ist das Bild einer anderen natürlichen Zahl. Insbesondere ist die auf e folgende Zahl auch Element von φ(N).

Wenn mit der abzählbar unendlichen Menge N die Menge der natürlichen Zahlen gemeint ist, soll nun statt „N“ „“ und statt „e „0“ geschrieben werden. (Dedekind bezeichnet das Grundelement der natürlichen Zahlen mit „1“, aber das ist im Hinblick auf die hier vorgestellten Gedankengänge ohne Belang.)

Sei nun  E = E(n)  eine Aussage, die in Abhängigkeit von n   hingeschrieben werden kann und sei ferner P diejenige Menge von Zahlen z, für die E(z) eine wahre Aussage darstellt. (Die Verwendung der Bezeichnung „z“ soll hier keine Verwirrung stiften, sondern nur andeuten, dass E(z) durchaus wahr sein kann, wenn z keine natürliche Zahl ist.)

Wenn man nun den Dedekind'schen Induktionssatz auf die natürlichen Zahlen anwendet und A durch {0}, S durch und φ durch succ ersetzt, dann erhält man genau das oben bereits formulierte Prinzip der vollständigen Induktion.

Es sollen jetzt alle Gesetze, die innerhalb der Menge der natürlichen Zahlen gelten, auf Grundlage des Axiomensystems (I) bis (IV) hergeleitet werden.


Addieren und Multiplizieren natürlicher Zahlen nach oben  

Die Abbildung addj: sei auf induktive Weise für jedes j ∈ ℕ wie folgt definiert:

(A1) addj(0)  =def  j
(A2) addj(succ(n))  =def  succ(addj(n))  für alle  n ∈ ℕ

Für alle n, k ∈ ℕ gilt dann succ(addk(n)) = addsucc(k)(n).

Beweis:
Sei k ∈ ℕ beliebig, aber fest gewählt.
Induktionsanfang:
Mit (A1) folgt succ(addk(0)) = succ(k) = addsucc(k)(0).
Das bedeutet, dass die behauptete Aussage für n = 0 wahr ist.
Induktionsvoraussetzung:
Es gelte succ(addk(m)) = addsucc(k)(m) für ein m ∈ ℕ.
Induktionsschluss:
  succ(addk(succ(m)))
= succ(succ(addk(m)))  wegen (A2)
= succ(addsucc(k)(m))  nach Induktionsvoraussetzung
= addsucc(k)(succ(m))  wegen (A2)
Hieraus folgt die Behauptung.

Mit succ(addk(n)) = addsucc(k)(n) folgt, dass für alle k, n ∈ ℕ gilt:

addk(n) = addn(k)

Beweis:
Zunächst wird gezeigt, dass für alle n ∈ ℕ die Aussage add0(n) = n wahr ist.
Induktionsanfang:
Nach (A1) gilt add0(0) = 0.
Induktionsvoraussetzung:
Angenommen, die Aussage add0(m) = m sei bereits für ein m ∈ ℕ bewiesen.
Induktionsschluss:
  add0(succ(m))
= succ(add0(m))  wegen (A2)
= succ(m)  nach Induktionsvoraussetzung.

Es ist nun zu zeigen, dass die Aussage addk(n) = addn(k) wahr ist für alle n, k ∈ ℕ.

Sei k im Folgenden eine beliebige, aber fest gewählte natürliche Zahl.
Induktionsanfang:
  addk(0)
= k  wegen (A1)
= add0(k)  weil add0(n) = n  für alle n ∈ ℕ.
Induktionsvoraussetzung:
Es gelte bereits addk(m) = addm(k) für ein m ∈ ℕ.
Induktionsschluss:
  addk(succ(m))
= succ(addk(m))  wegen (A2)
= succ(addm(k))  nach Induktionsvoraussetzung
= addsucc(m)(k)

Da hiernach die Aussage addk(n) = addn(k) für alle n ∈ ℕ und für jedes beliebige k ∈ ℕ wahr ist, ist damit die Behauptung bewiesen.

Mit der für jedes j ∈ ℕ induktiv definierten Abbildung mulj: ℕ → ℕ, gegeben durch
 

(M1) mulj(0)  =def  0
(M2) mulj(succ(n))  =def  addj(mulj(n))  für alle  n ∈ ℕ

folgt auf ganz ähnliche Art, dass für alle k, n ∈ ℕ gilt:

mulk(n) = muln(k).

Beweis:
(i) Als erstes wird gezeigt, dass addk(mulm(k)) = mulsucc(m)(k) für alle m, k ∈ ℕ.
Sei hierfür m ∈ ℕ beliebig, aber fest gewählt.
Induktionsanfang:
add0(mulm(0)) = add0(0) = 0 = mulsucc(m)(0)
Induktionsvoraussetzung:
Es gelte addK(mulm(K)) = mulsucc(m)(K) für ein K ∈ ℕ.
Induktionsschluss:
  addsucc(K)(mulm(succ(K)))
= addsucc(K)(addm(mulm(K)))  wegen (M2)
= succ(addK(addm(mulm(K))))  wegen addsucc(k)(n) = succ(addk(n)) für alle n, k ∈ ℕ.
= succ(addm(addK(mulm(K))))
= addsucc(m)(addK(mulm(K)))
= addsucc(m)(mulsucc(m)(K))  nach Induktionsvoraussetzung
= mulsucc
(m)(succ(K))  wegen (M2)

(ii) Im zweiten Schritt wird gezeigt, dass für alle n ∈ ℕ die Aussage mul0(n) = 0 wahr ist.
Induktionsanfang:
Nach (M1) gilt mul0(0) = 0.
Induktionsvoraussetzung:
Angenommen, die Aussage mul0(m) = 0 sei bereits für ein m ∈ ℕ bewiesen.
Induktionsschluss:
  mul0(succ(m))
= add0(mul0(m))  wegen (M2)
= add0(0)  nach Induktionsvoraussetzung
= 0

(iii) Es ist nun zu zeigen, dass die Aussage mulk(n) = muln(k) wahr ist für alle n, k ∈ ℕ.
Sei k im Folgenden eine beliebige, aber fest gewählte natürliche Zahl.
Induktionsanfang:
  mulk(0)
= 0  wegen (M1)
= mul0(k)
Induktionsvoraussetzung:
Es gelte bereits mulk(m) = mulm(k) für ein m ∈ ℕ.
Induktionsschluss:
  mulk(succ(m))
= addk(mulk(m))  wegen (M2)
= addk(mulm(k))  nach Induktionsvoraussetzung
= mulsucc(m)(k)  aufgrund der unter (i) bewiesenen Regel.

Da hiernach die Aussage mulk(n) = muln(k) für alle n ∈ ℕ und für jedes beliebige k ∈ ℕ wahr ist, ist damit die Behauptung bewiesen.

Nun werden die Addition und die Multiplikation als zweistellige Operationen auf definiert:

Eine 2-stellige Operation (oder eine Verknüpfung) auf einer Menge M ist eine Abbildung

„@“: M x M M ,

das heißt, jedem geordneten Paar (x;y) mit x M und y ∈ M wird durch eine Zuordnungsvorschrift in eindeutiger Weise ein Bild @(x;y) M zugeordnet.

Sei auf einer Menge M eine Verknüpfung „@“ definiert.
Seien x, y M und z M das Bild von (x;y) M2 unter „@“.
Dann sind folgende Schreibweisen gleichbedeutend: @((x;y)) = z     @(x;y) = z     x @ y = z


Die Verknüpfungen „+“ (Addition) und „·“ (Multiplikation) werden auf für alle k, n ∈ ℕ wie folgt definiert:

k + n  =def  addk(n)

k · n  =def  mulk(n)

Die Multiplikation hat gegenüber der Addition die höhere Prioriät, das heißt, für alle k, m, n ∈ ℕ gilt:

k + m · n  =def  k + (m · n)
k · m + n  =def  (k · m) + n

Anschaulich gesprochen: „Punktrechnung geht vor Strichrechnung“.

Wegen addk(n) = addn(k) bzw. mulk(n) = muln(k) für alle k, n ∈ ℕ sind die Verknüpfungen „+“ und „·“ kommutativ, das heißt, für alle k, n ∈ ℕ gilt:

k + n  =  n + k
k · n  =  n · k

Außerdem gelten nach dem oben Gesagten für alle k, n ∈ ℕ folgende Rechenregeln:

n + 0  =  n
k + succ(n)  =  succ(k + n)
n · 0  =  0
k · succ(n)  =  k + (k·n)

Hiermit kann man zeigen, dass die Verknüpfungen „+“ und „·“ auch assoziativ sind, das heißt, für alle k, m, n ∈ ℕ gilt

m + (n + k) = (m + n) + k
m · (n · k) = (m · n) · k

und es gilt das Distributivgesetz

k · (m + n) = k · m + k · n

Beweis:
Assoziativgesetz bezüglich der Addition.
Induktionsanfang:
m + (n + 0) = m + n = (m + n) + 0
Das bedeutet, dass die behauptete Aussage für k = 0 wahr ist.
Induktionsvoraussetzung:
Es gelte m + (n + K) = (m + n) + K für ein K ∈ ℕ.
Induktionsschluss:
  m + (n + succ(K))
= m + succ(n + K)
= succ(m + (n + K))
= succ((m + n) + K)
= (m + n) + succ(K)

Distributivgesetz.
Induktionsanfang:

k·(m + 0) =  k·m =  k·m + 0 = k·m + k·0
Induktionsvoraussetzung:
Es gelte k·(m + N) = k·m + k·N  für ein N ∈ ℕ.
Induktionsschluss:
   k·(m + succ(N))
=  k·succ(m + N)
= k + k·(m + N)
= k·(m + N) + k
= (k·m + k·N) + k
= k·m + (k·N + k)
= k·m + (k + k·N)
= k·m + k·succ(N)

Assoziativgesetz bezüglich der Multiplikation.
Induktionsanfang:
m·(n·0) = m·n = (m·n)·0
Induktionsvoraussetzung:
Es gelte m·(n·K) = (m·n)·K für ein K ∈ ℕ.
Induktionsschluss:
m·(n·succ(K))
= m·(n + (n·K))
= (m·n) + m·(n·K)
= (m·n) + ((m·n)·K)
= (m·n)·succ(K)

Neben den bisher für alle k, m, n ∈ ℕ bewiesenen Gesetzen

k + n = n + k
k · n = n · k

m + (n + k) = (m + n) + k
m · (n · k) = (m · n) · k

k · (m + n) = k · m + k · n

sind noch die sogenannten Kürzungsregeln (N1) und (N2) wichtig:

(N1) x + n = y + n     x = y   für alle  x, y, n ∈ ℕ
(N2) x · n = y · n     x = y   für alle  x, y, n ∈ ℕ  und  n ǂ 0

Beweis:
(N1):
Seien x und y irgendwelche natürliche Zahlen.
Induktionsanfang:
x + 0 = y + 0  ⇔  x = y wegen (A1)
Induktionsvoraussetzung:
Es gelte x + m = y + m  ⇔  x = y  für ein m ∈ ℕ.
Induktionsschluss:
Es ist zu zeigen, dass x + succ(m) = y + succ(m)  ⇔  x = y

“:
   x = y
x + m = y + m  nach Induktionsvoraussetzung
succ(x + m) = succ(y + m), denn succ ist eine Abbildung
 x + succ(m) = y + succ(m)

“:
  x + succ(m) = y + succ(m)
succ(x + m) = succ(y + m)
x + m = y + m, denn die Abbildung succ ist injektiv
x = y  nach Induktionsvoraussetzung

(N2) lässt sich auf analoge Art beweisen.

Die Regeln (N1) und (N2) spielen zum Beispiel eine wesentliche Rolle, wenn es darum geht zu zeigen, dass die Gleichungen von der Form  m + x = n  bzw.  m · x = n mit vorgegebenen Zahlen m und n im Falle der Lösbarkeit eindeutig lösbar sind (siehe: Gleichungen (G1) und (G2) im Kapitel Zahlenmengen).

Mit Hilfe der Rechenregeln bezüglich der Addition auf lassen sich die natürlichen Zahlen ordnen:

Seien m, n ∈ ℕ. Dann wird gesetzt:

mdef  p ∈ ℕ: m + p = n

Mit anderen Worten:
m ist genau dann kleiner oder gleich n, wenn eine natürliche Zahl p existiert mit der Eigenschaft, dass m + p = n.

Wenn für zwei natürliche Zahlen m und n  m n und  m ǂ n gilt, dann schreibt man: m < n.

Für alle natürlichen Zahlen n gilt dann:

0n

Beweis:
Induktionsanfang:
Es gilt 0 + 0 = 0, also ist 00.
Induktionsvoraussetzung:
Es gelte 0m für ein m ∈ ℕ.
Induktionsschluss:
   0m
0 + p = m  mit passend gewähltem p ∈ ℕ
(0 + p) + succ(0) = m + succ(0)
0 + (p + succ(0)) = m + succ(0)
0m + succ(0)
Mit (m + succ(0)) = succ(m + 0) = succ(m) folgt die Behauptung.

0 ist also die kleinste natürliche Zahl.

Nach Axiom (III) hat 0 kein Urbild unter der Abbildung succ. Deswegen gilt

succ(0) ǂ 0.

Mit der oben bewiesenen Rechenregel  k + succ(n)  =  succ(k + n) für alle k, n ∈ ℕ  folgt insbesondere
k + succ(0) = succ(k + 0) und damit 

succ(k) = k + succ(0)  für alle k ∈ ℕ

Aufgrund dieser Regel ist es jetzt in Verbindung mit der Ordnungsrelation < möglich, alle natürlichen Zahlen „der Reihe nach aufzuschreiben“, vornehmer ausgedrückt: „linear zu ordnen“:

0 < succ(0) < succ(succ(0)) < succ(succ(succ(0))) < ...

Mit der Relationist die Menge der natürlichen Zahlen wohlgeordnet.

Beweis:
Seien im Folgenden k, m, n ∈ ℕ beliebig gewählt.

(i) Transitivität:
   kund  nm
k + p1 = n  und  n + p2 = m  mit passend gewählten p1, p2 ∈ ℕ
(k + p1) + (n + p2) = m + n
(k + (p1 + p2)) + n = m + n
k + (p1 + p2) = m
km

(ii) Reflexivität:
   n + 0 = n
n denn 0 ∈ ℕ.

(iii) Jede nichtleere Teilmenge von hat ein kleinstes Element.
selbst hat ein kleinstes Element, nämlich 0.

Sei nun T ⊂ ℕ irgendeine nichtleere Teilmenge von .
Induktionsanfang:
Angenommen, T hat nur ein einziges Element t.
Dann ist t t und t ist trivialerweise kleinstes Element von T.
Induktionsvoraussetzung:
Sei T ⊂ ℕ eine Menge natürlicher Zahlen mit m Elementen und einem kleinsten Element,
es gibt also ein nmin T:  nmin für alle x T.
Induktionsschluss:
Sei nun p irgendeine natürliche Zahl mit p T.
Dann gilt entweder p < nmin oder nmin < p, weil die natürlichen Zahlen linear geordnet sind.
In der (m+1)-elementigen Menge T* = T { p } ist demzufolge unter Beachtung der Induktionsvoraussetzung entweder nmin oder p kleinstes Element.

(iv) Identitivität:
   mund  nm
m + p1 = n  und  n + p2 = m  mit passend gewählten p1, p2 ∈ ℕ
(m + p1) + (n + p2) = m + n
(m + n) + (p1 + p2) = m + n
(m + n) + (p1 + p2) = (m + n) + 0
p1 + p2 = 0
p10
p1 = 0,  denn 0 ist das kleinste Element in
m = n

Jeder, der die Menge der natürlichen Zahlen gut kennt, wird über die Resultate der vorstehenden Beweise nicht wirklich überrascht sein: Man kann die Elemente der Menge der Reihe nach abzählen und mit 0 geht es los. (Der Name der ersten natürlichen Zahl ist im Hinblick auf die Natur der natürlichen Zahlen völlig belanglos; man könnte diese Zahl auch Null nennen, oder zero oder egal-wie.) Es gibt zwei Operationen auf , die Addition und die Multiplikation, und beide sind kommutativ und assoziativ. Außerdem gelten das Distributivgesetz  k(m + n) = km + kn  für alle k, m, n ∈ ℕ sowie ein paar andere nützliche Rechenregeln. Es gibt ferner eine Relation auf , mit der die natürlichen Zahlen wohlgeordnet sind.

Das alles ist nicht erstaunlich. Erstaunlich ist vielmehr, das alle diese Eigenschaften von tatsächlich allein mit den wenigen Axiomen (I) bis (IV) zusammenfassend und vollständig beschreibbar sind. Man erschließt sich diese Eigenschaften der Reihe nach im Wesentlichen mit einem Beweisprinzip, und dies ist das Prinzip der vollständigen Induktion.

Bemerkenswert ist auch, dass sich alle Gesetze in samt ihrer Beweise formulieren lassen, ohne die natürlichen Zahlen in irgendeiner Weise bezeichnen zu müssen, mit Ausnahme der kleinsten natürlichen Zahl. Um in unter Benutzung dieser Gesetze praktisch rechnen zu können, muss man natürlich Namen für die natürlichen Zahlen erfinden.


Dezimalzahlen nach oben

Die Idee, die natürlichen Zahlen mit Hilfe von dezimalen Zahlzeichen zu bezeichnen, stammt ursprünglich aus Indien. Der persische Mathematiker Abu Ja'far Muhammad ibn Musa al-Chwarizmi (etwa 780 - 850) hat das Dezimalsystem in seinem berühmten Werk hisab al-jabr wal-muqabalah verwendet. Danach hat es noch viele Jahrhunderte gedauert, bis das indische Dezimalsystem auch in Europa genutzt wurde.

Man benötigt zur Darstellung der natürlichen Zahlen im Dezimalsystem zehn Zahlzeichen, die je nach Sprache bzw. Schrift ganz unterschiedlich aussehen können. Beispiele:

Zahlzeichen

Mit der Definition 

1 =def  succ(0)

ergibt sich aufgrund der Regel  succ(k) = k + succ(0)

succ(k) = k + 1  für alle k ∈ ℕ.

Also kann man schreiben:

2 =def 1 + 1;  3 =def 2 + 1;  4 =def 3 + 1;  5 =def 4 + 1;
6
=def 5 + 1;  7 =def 6 + 1;  8 =def 7 + 1;  9 =def 8 + 1;

Im Dezimalsystem haben die zehn Zahlzeichen zwei unterschiedliche Bedeutungen: zum einen dienen sie dazu, die ersten zehn natürlichen Zahlen zu bezeichnen, zum anderen benutzt man sie zur Bezeichnung aller weiteren natürlichen Zahlen, wobei sie als Ziffern abhängig von ihrer Stelle innerhalb der die natürlichen Zahlen beschreibenden Ziffernfolgen verschieden interpretiert werden.

Die erste 2-stellige natürliche Dezimalzahl ist die Zahl 10:

10 =def  9 + 1

Um fortfahren zu können, wird der Begriff der Zehnerpotenz benötigt:

Ein Ausdruck der Form 10i heißt Zehnerpotenz und wird wie folgt induktiv definiert:

100  =def  1
10i+1  =def  10·10i  für alle i ∈ ℕ.

Mit Hilfe der Zehnerpotenzen kann jede natürliche Zahl z ∈ ℕ wie folgt dargestellt werden:

z = z0·100 + z1·101 + z2·102 + ... + zn-1·10n-1.

Hierbei ist jedes der zi eine der Zahlen  0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
(n-1) ist die natürliche Zahl, für die gilt: (n-1) + 1 = n.

Beweis:
Induktionsanfang:
Es gilt 0 = 0·1 = 0·100.
Induktionsvoraussetzung:
Sei z ∈ ℕ dargestellt als n-stellige Dezimalzahl, das heißt,
es gelte z = z0·100 + z1·101 + z2·102 + ... + zn-1·10n-1 mit n ∈ ℕ;
z0, z1, z2, ..., zn-1 ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} und
zn-1 ǂ 0.
Induktionsschluss:
Es ist zu zeigen, dass (z + 1) auf die gleiche Art wie z dargestellt werden kann.

Fall 1: z0 ǂ 9.
Dann gilt
   z + 1
= 1 + (z0·100 + z1·101 + ... + zn-1·10n-1wegen der Kommutativität bezüglich „+“
= (1·100 + z0·100) + z1·101 + ... + zn-1·10n-1  wegen der Assoziativität bezüglich „+“
= (z0 + 1)·100 + z1·101 + ... + zn-1·10n-1  wegen des Distributivgesetzes in
=
Z0·100 + z1·101 + z2·102 + ... + zn-1·10n-1 mit Z0 ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Fall 2: z0 = 9 und z1 ǂ 9.
Dann gilt
   z + 1
= 1 + (9·100 + z1·101 + ... + zn-1·10n-1)
= 10·100 + z1·101 + ... + zn-1·10n-1
= 101 + z1·101 + ... + zn-1·10n-1
= 0·100 + (z1 + 1)·101 + z2·102 + ... + zn-1·10n-1 
= 0·100 + Z1·101 + ... + zn-1·10n-1   mit Z1 ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Fall 3: z0 = z1 = ... = zi = 9 und zi+1 ǂ 9 mit 0 < i < n-1
Dann gilt
   z + 1
= 1 + (9·100 + 9·101 + ... + zi+1·10i+1 + ... + zn-1·10n-1)
= 0·100 + 0·101 + ... + 0·10i + (zi+1 + 1)·10i+1 + ... + zn-1·10n-1
= 0·100 + 0·101 + ... + 0·10i + Zi+1·10i+1 + ... + zn-1·10n-1 mit Zi+1 ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Fall 4: z0 = z1 = ... = zn-1 = 9
Dann gilt
   z + 1
= 0·100 + 0·101 + ... + 0·10n-1 + 1·10n.

Für z = z0·100 + z1·101 + z2·102 + ... + zn-1·10n-1 schreibt man abkürzend:

z = zn-1...z2z1z0

In dem Ausdruck zn-1...z2z1z0 sind die zi keine Zahlen, sondern Ziffern, also Dezimalzeichen!
Beispielsweise ist 97132 = 2·100 + 3·101 + 1·102 + 7·103 + 9·104.

Im Kapitel Algorithmus wird unter anderem dargestellt, wie und warum das Verfahren der schriftlichen Multiplikation von Dezimalzahlen funktioniert.

Für succ(0), den Nachfolger der kleinsten natürlichen Zahl 0, haben wir die Bezeichnung „1“ hingeschrieben.
Es gilt

n·1 = n  für alle n ∈ ℕ.

Beweis:
Für alle n ∈ ℕ gilt
   n·1
= n·succ(0)
= muln(succ(0))
= addn(muln(0))  wegen (M2)
= addn(0)  wegen (M1)
= n + 0
= n


Spezielle Folgen und Reihen nach oben

Summe der ersten n Quadratzahlen
Sei n ∈ ℕ. Dann gilt für die Summe der ersten n Quadratzahlen:

formula

Beweis:
Induktionsanfang:
Die Behauptung ist für n = 0 offensichtlich richtig.
Induktionsvoraussetzung:
Sei nun angenommen, dass die Behauptung für eine beliebige natürliche Zahl n gilt.
Induktionsschluss:
Es ist zu zeigen, dass die Behauptung für n+1 ebenfalls wahr ist.
Zunächst hat man

formula

Insgesamt gilt also

formula

Man rechnet nach, dass
(n+1)((n+1) + 1)(2(n+1) + 1) = (n + 1)(n + 2)(2n + 3) = 2n3 + 9n2 + 13n + 6,
was zu beweisen war.


Die geometrische Reihe

 Sei n ∈ ℕ* und q ∈ ℝ. Dann heißt

formula

geometrische Reihe. q heißt „Quotient“ der Reihe.

Sn lässt sich einfach berechnen, indem die Gleichung  Sn = 1 + q + ... + qn  mit q multipliziert wird und das Ergebnis von der Ursprungsgleichung abgezogen wird:

formula

Mit Hilfe der Grenzwertsätze folgt sofort, dass die „Summenfolge“ (Sn) konvergiert, sofern nur die Bedingung |q| < 1 erfüllt ist:

formula

In Worten: Die Summe der unendlichen geometrischen Reihe mit q als Quotient ist gleich (1−q)−1, wenn |q| < 1 gilt. Oder (anders ausgedrückt): Die unendliche Reihe  1 + q + q2 + q3 + ....  konvergiert für |q| < 1 gegen (1−q)−1. Im Fall |q|  1 ist die unendliche geometrische Reihe divergent.

Die Euler’sche Reihe

formula

ist konvergent. Der Grenzwert dieser Reihe ist irrational.

Beweis:
Monoton steigende und nach oben beschränkte Folgen bzw. monoton fallende und nach unten beschränkte Folgen sind immer konvergent.( Beweis). Nun hat man mit

formula

erstens eine streng monoton wachsende Summenfolge (Sn) und zweitens ist die Folge (Sn) beschränkt. Die untere Schranke Su ist 0, die obere Schranke So ist 3, denn es gilt:

formula

Der Grenzwert der Euler’schen Reihe wird mit „e“ bezeichnet („Eulersche Zahl“).
(Sn) konvergiert recht rasch, die ersten fünfzehn Folgenglieder (mit 10 Dezimalstellen hinter dem Komma hingeschrieben) lauten:

Euler

Angenommen, e ist eine rationale Zahl. Dann gibt es zwei natürliche Zahlen p und q mit e = p/q und es folgt
formula
mit
formula

Nach unserer Annahme müsste die beschränkte und monoton wachsende Summenfolge (Rn) gegen eine natürliche Zahl streben. Es gilt aber
formula
und damit hat man mit
formula
einen Widerspruch zur Annahme.

1873 hat Charles Hermite darüberhinaus bewiesen, dass e eine transzendente Zahl ist.

Binomischer Lehrsatz
Für beliebige Zahlen a und b und für alle natürlichen Zahlen n gilt

Binomischer Lehrsatz

oder - in kürzerer Schreibweise:

Binomische Formel

Sei n, k ∈ ℕ und k n. Dann heißt der Ausdruck

Binomialkoeffizient

Binomialkoeffizient (lies: „n über k“).
Speziellerweise wird definiert:

n über 0 ist gleich 1


Beweis des binomischen Lehrsatzes:
Auf Grund der Definition des Binomialkoeffizienten gilt für alle natürlichen Zahlen n und k mit k n
formula
und hiermit hat man die wichtige Rechenregel

Rechenregel

Mit Hilfe dieser Rechenregel kann nun der binomische Satz bewiesen werden.

Induktionsanfang:
Für die Zahl 2 ist der binomische Satz wohlbekannt: (a + b)2 = a2 + 2ab + b2. Im übrigen ist der Satz auch für die Zahlen 1 und 0 richtig  (a + b)1 = a1b0 + b1a0  und  (a + b)0 = a0b0.


Induktionsvoraussetzung:
 
Sei nun angenommen, dass der binomische Satz richtig ist für irgendeine natürliche Zahl m. Das heißt, es gilt:

formula

Induktionsschluss:
Multiplikation mit (a + b) auf beiden Seiten liefert

formula

Ausmultiplizieren der rechten Seite ergibt den Ausdruck

formula

Unter Verwendung der obenstehenden Rechenregel lässt sich dieser Ausdruck umformen zu

formula

Hieraus folgt die Behauptung.

Die Binomialkoeffizienten der Rechenausdrücke  (a + b)0, (a + b)1, (a + b)2, (a + b)3, ... ergeben, wenn man sie in entsprechender Form hinschreibt, das sogenannte „Pascal’sche Dreieck“, welches bereits von den persischen Mathematikern Muhammad al-Karadschi (953 − 1029) und Omar Khayyam (1048 − 1131) beschrieben und untersucht wurde:

Pascal’sches Dreieck

Ungleichung von Bernoulli
Ist h+1 eine positive reelle Zahl, so gilt

(1 + h)n 1 + n·h für alle n ∈ ℕ+.

Beweis:
Induktionsanfang:
Es gilt (1 + h)1 = 1 + 1·h.
Induktionsvoraussetzung:
Es gelte (1 + h)m 1 + m·h für irgendeine natürliche Zahl m, die größer oder gleich 1 ist.
Induktionsschluss:
Aus der Induktionsannahme folgt durch Multiplikation mit (1 + h)
(1 + h)m+1 (1 + h)(1 + mh) = m·h2 + (m + 1)·h + 1.
Wegen m·h2 > 0 hat man (1 + h)m+1 (m + 1)·h + 1, was zu zeigen war.


Die Zahlenfolge (en), definiert durch

en = (1 + 1/n)n  für alle n ∈ ℕ*

ist konvergent und es gilt en  e (n → ∞).

Beweis:
Sei im Folgenden stets n ∈ ℕ*.
Unter Verwendung des binomischen Lehrsatzes folgtformula
und damit hat man
formula
Wegen (siehe oben)
formula
ist (en) beschränkt, außerdem ist (en) monoton wachsend:
formula
Der letzte Schritt folgt mit der Bernoulli-Ungleichung, wenn h = − 1/n gesetzt wird unter Beachtung, dass −1/n > −1. Es folgt
formula
und somit gilt

formula

womit die Monotonie von (en) nachgewiesen ist.

Aus der Begrenztheit und der Monotonie von (en) folgt die Konvergenz dieser Zahlenfolge gegen einen Grenzwert g.

Oben wurde gezeigt, dass sich en wie folgt schreiben lässt:formula
ferner haben wir gesehen, dass
formula
 Deswegen folgt für alle m ∈ ℕ* mit m > n
formula
und somit haben wir die Ungleichung
formula
Bei festem, aber beliebig gewählten n erhalten wir hiermit für m → ∞
formula
Wegen der Konvergenz der Euler’schen Reihe folgt hieraus e  g  e,
womit die Behauptung bewiesen ist.

Leonhard Euler (1707 − 1783) hat gezeigt, dass sich die nach ihm benannte irrationale Zahl e auf ganz merkwürdige Art schreiben lässt, nämlich als Kettenbruch:

Kettenbruch

Wenn man irgendetwas als Kettenbruch mit „einfacher Struktur“ ausdrücken kann, dann weist das in aller Regel darauf hin, dass es sich um etwas ganz Besonderes handelt.
 

Der Turm von Hanoi
Auf dem ersten von drei Stäben liegen n Scheiben - der Größe nach geordnet - übereinander.
Der gesamte Scheibenturm soll vom ersten auf den dritten Stab umgesetzt werden und zwar so,
dass nacheinander jede Scheibe einzeln von einem Stab auf einen anderen gelegt wird. Das Spiel
ist beendet, wenn zum Schluss der gesamte Scheibenturm in der ursprünglichen Anordnung der
Scheiben auf dem dritten Stab liegt. Es gilt zusätzlich die Regel, dass während des Spiels eine Scheibe nur dann umgesetzt werden darf, wenn die nach der Umsetzung unter ihr liegende Scheibe größer ist als sie selbst. Wie groß ist die minimale Anzahl der Umsetzungen?

Turm von Hanoi

Behauptung: Die Anzahl der Umsetzungen ist mindestens gleich 2n − 1.

Beweis:
Induktionsanfang:
Falls n = 1, braucht man nur eine Umsetzung und es ist 1 = 21 − 1.
Induktionsvoraussetzung:
Sei angenommen, dass die Behauptung für m Scheiben bereits bewiesen ist, wobei m eine beliebige, aber fest gewählte natürliche Zahl darstellt.
Induktionsschluss:
Auf dem ersten Stab sollen nun (m + 1) Scheiben liegen. Die gestellte Aufgabe ist nur dann lösbar, wenn es während des Spiels zu folgender Situation kommt:

Turm von Hanoi

Die größte Scheibe kann und muss jetzt direkt vom ersten Stab auf den dritten Stab umgesetzt werden, und zwar nachdem die zuvor über der größten Scheibe liegenden m anderen Scheiben vom ersten Stab auf den mittleren Stab umgesetzt worden sind, wofür man nach der Induktionsvoraussetzung mindestens 2m − 1 Schritte gebraucht hat. Wenn die größte Scheibe auf dem dritten Stab liegt, braucht man für die Umsetzung der m Scheiben vom mittleren auf den dritten Stab nochmals 2m − 1 Schritte, macht alles zusammen 2·(2m − 1)+1 Schritte. Diese Argumentation ist völlig unabhängig von der Wahl von m!

Es gilt 2·(2m − 1) + 1 = 2m+1 − 1, womit die Behauptung bewiesen ist.

Die Folge der 2n − 1 Spielzüge kann man automatisiert ablaufen lassen, und zwar mit Hilfe eines rekursiven Algorithmus (vgl. Einführung in Maple, Übung Türme von Hanoi):

function move (Zahl i, Stab a, Stab b, Stab c) {
    if (i > 0) {
        move (i−1, a, c, b);
        verschiebe oberste Scheibe von a nach c;
        move (i−1, b, a, c);
    }
}

Das Spiel „Turm von Hanoi“ ist übrigens 1883 vom Mathematiker Edouard Lucas (1842 − 1891) erfunden worden und wurde von ihm damals verkauft. In der Spielbeschreibung wurde der Turm von Hanoi (mit acht Scheiben) als verkleinerte Version des Turms von Brahma im Tempel der indischen Stadt Benares ausgewiesen. Der Turm von Brahma soll aus 64 goldenen Scheiben bestanden haben, die Schritt für Schritt gemäß der oben beschriebenen Regeln durch Tempelpriester umgelegt wurden. Martin Gardner schreibt dazu in seinem Buch Mathematische Rätsel und Probleme:

Bevor sie damit beendet sein werden, so sagte man, wird der Tempel in Staub zerfallen und die Welt wird mit einem Donnerschlag verschwinden. Das Untergehen der Welt mag fraglich sein, jedoch besteht wenig Zweifel am Zerfall des Tempels. Auf Grund der Formel 264 − 1 ergibt sich nämlich die 20-stellige Zahl 18.446.744.073.709.551.615. Unter der Annahme, daß die Priester Tag und Nacht arbeiten und in jeder Sekunde eine Scheibe umlegen, würden sie viele Milliarden Jahre brauchen, um ihre Arbeit zu vollenden.


 Home   Back   Top