in der Logik meint man damit den Schluss von speziellen Sachverhalten auf allgemeine Regeln, siehe Induktion (Logik)

---

Vollständige Induktion oder der „Schluss von n auf n + 1“ ist eine mathematische Beweismethode, die üblicherweise eine Aussage für alle natürlichen Zahlen beweist (verallgemeinert). Sie funktioniert aber auch für allgemeinere Fälle (siehe unten).

Begriff

---

Der Name dieses Beweisverfahrens leitet sich von lat. inductio (= Hereinführung) ab. Obwohl auch bei der vollständigen Induktion vom Speziellen auf das Allgemeine geschlossen wird, ist sie jedoch kein induktives, sondern ein deduktives Prinzip.

Historisches

---

Die vollständige Induktion ist zuerst 1654 bei Blaise Pascal und 1659 bei Pierre de Fermat zu finden. Sie wurde jedoch bis 1879 nur für arithmetische Probleme benutzt. Erst als Gottlob Frege mit ihr die Klasse der natürlichen Zahlen definierte, wurde sie zu einem allgemeingültigen Beweisverfahren in der Mathematik.

Übersicht

---

Vereinfacht gesprochen geht es um folgende Argumentation: Lässt sich die bestimmte Behauptung über natürliche Zahlen für eine gewisse Anfangszahl begründen (Induktionsanfang oder seltener auch Induktionsverankerung), und lässt sich außerdem zeigen, dass aus ihrer Geltung für eine beliebige Zahl $n$ ihre Geltung für die nächste Zahl $n\; +\; 1$ folgt (Induktionsannahme oder Induktionsvoraussetzung), so gilt diese Behauptung für alle auf die Anfangszahl folgenden natürlichen Zahlen (Induktionsschritt). Die Induktion kann also in folgende Stadien unterteilt werden:

1. Induktionsanfang
2. Induktionsannahme
3. Induktionsschritt

Definition

---

Das Beweisverfahren der vollständigen Induktion beruht auf dem 5. Peano-Axiom für die natürlichen Zahlen $\backslash mathbb\{N\}$, dem Induktionsaxiom. Dieses besagt:

Ist $K$ eine Teilmenge von $\backslash mathbb\{N\}$ mit den Eigenschaften, dass 0 (bzw. 1) in $K$ liegt und für jedes Element $k$ von $K$ auch $k\; +1$ in $K$ liegt, dann ist $K$ gleich $\backslash mathbb\{N\}$.

(Ob man bei 0 oder 1 beginnt, hängt davon ab, ob 0 als Element von $\backslash mathbb\{N\}$ gezählt wird. Je nach Zweckmäßigkeit ist dies unterschiedlich definiert.)

Um zu beweisen, dass eine bestimmte logische Formel $p(n)$ für jede beliebige natürliche Zahl $n$ gilt, setzt man $K$ als die Menge aller natürlichen Zahlen $k$, für die die Aussage $p(k)$ gilt und wendet anschließend das Induktionsverfahren auf diese Menge an. Somit zeigt man, dass die Aussage $p(1)$ wahr ist und damit das Element 1 in $K$ liegt und dass für jede Aussage $p(k)$ auch die Aussage $p(k+1)$ stimmt, sodass auch $k$ und $k+1$ in der Menge $K$ liegen. Nach dem Induktionsaxiom gilt deshalb $K\; =\; \backslash mathbb\{N\}$ und die Aussage $p(n)$ besitzt für alle natürlichen Zahlen $n\backslash ge\; 1$ Gültigkeit.

Motivation

Es wird vermutet, dass eine Aussage für alle natürlichen Zahlen gilt. Bei der gegebenen Problemstellung ist es allerdings noch nicht gelungen, eine für alle natürlichen Zahlen gültige Aussage anzugeben. Da die Menge der natürlichen Zahlen unendlich ist, ist es ebenso nicht möglich die Richtigkeit der Aussage für jede Zahl einzeln zu beweisen. Durch die Methode der vollständigen Induktion kann aber trotzdem gezeigt werden, ob die Aussage für die gesamte Menge richtig ist.

Beispiel

Zu beweisen ist, dass $1+2+...+n\; =\; \backslash frac\{n(n+1)\}\{2\}$.

Für einzelne Zahlen ist die Formel leicht nachzurechnen:

• $n\; =\; 1$:

$1\; =\; \backslash frac\{1(1+1)\}\{2\}$

• $n\; =\; 2$:

$1\; +\; 2\; =\; 3\; =\; \backslash frac\{2(2+1)\}\{2\}$

• und so weiter ...

Für den folgenden Beweis reicht bereits der Fall n = 1. Auf der Suche nach einer allgemein gültigen Aussage, wird man die Behauptung konsequenterweise für viele andere $n$ überprüfen.

Die Idee

Ist bekannt,

• dass eine bestimmte von $n$ abhängige Aussage für $n\; =\; 1$ gilt und
• dass für jede beliebige natürliche Zahl $k$ aus der Gültigkeit der Aussage für $n\; =\; k$ auch die Gültigkeit für $n\; =\; k\; +1$ folgt,

dann folgt nach dem Induktionsaxiom, dass diese Aussage für alle $n$ gilt.

Auf den ersten Blick scheint das Problem nur anders formuliert worden zu sein, indem die nächste Zahl einfach als die vorhergehende plus 1 bezeichnet wurde. Immer noch sind es unendlich viele Zahlen, doch durch den allgemeinen Ausdruck $n=k+1$ kann davon ausgegangen werden, dass die Aussage für $n=1$ bis $n=k$ gilt. Selbst die Formel, die man zu beweisen sucht, kann im Beweis als Voraussetzung für Zahlen unterhalb der aktuellen Zahl (das bedeutet unterhalb von $k+1$) verwendet werden.

Angewandt auf obiges Beispiel bedeutet dies folgendes:

Angenommen, die Formel wurde bereits bis zur Zahl $n=k$ bewiesen. Nun soll gezeigt werden, dass die Formel für $n=k+1$ ebenso Gültigkeit besitzt (d.h. nach dem Beispiel soll die Summe $1\; +\; 2\; +\; 3\; +\; \backslash dots\; +\; k\; +\; (k+1)$ berechnet werden).

Die ersten $k$ Summanden bilden eine solche Summe, und zwar für $k$, was kleiner ist als $k+1$. Also darf man – durch die Voraussetzung, dass die Formel für $n=k$ bereits bewiesen ist – diesen Schritt abermals anwenden:

$1\; +\; 2\; +\; 3\; +\; \backslash dots\; +\; k\; +\; (k+1)\; =\; \backslash frac\{k(k+1)\}\{2\}\; +\; (k+1)$

In diesem Ausdruck wird ($k$+1) ausgeklammert:

$=\; (k+1)\; \backslash cdot\; \backslash left(\backslash frac\{k\}\{2\}+1\; \backslash right)$

und dies weiter umgeformt zu

$=\; (k+1)\; \backslash cdot\; \backslash frac\{k+2\}\{2\}$

$=\; \backslash frac\{(k+1)\; \backslash cdot\; (k+2)\}\{2\}$

$=\; \backslash frac\{(k+1)\backslash cdot\; ((k+1)+1)\}\{2\}$

Zu beachten ist, dass $k$ beliebig gewählt werden darf. Beim Vergleich dieses Ausdrucks mit dem zu beweisenden Ausdruck ist festzustellen, dass lediglich $k$ durch $k+1$ ersetzt ist. Damit ist der Schritt von $k$ zu $k+1$ für allgemeine Werte von $k$ bewiesen.

Der große Vorteil des Induktionsbeweises zeigt sich darin, dass die Schritte nicht mehr einzeln durchgeführt werden müssen. Bewiesen werden muss nur, dass eine Aussage für die unterste Zahl (entweder 0 oder 1) gilt und ebenso, wenn sie bis zu einer beliebigen Zahl gilt, dass sie auch für die nächste Gültigkeit besitzt. (So ist es theoretisch möglich jede Zahl durch die ständige Anwendung der einzelnen Schritte zu erreichen.)

In der Praxis wird üblicherweise für $n$ und $k$ der gleiche Buchstabe $n$ gewählt. Dies stellt insofern kein Problem dar, solange man sich der unterschiedlichen Bedeutung von $n$ in "$p(n)$ gilt für alle natürlichen Zahlen $n$" in der zu beweisenden Aussage und "$p(n)$ gilt für ein konkretes $n=k$" in der Induktionsvoraussetzung bewusst ist. Die Nichtbeachtung führt dazu, dass die zu beweisende Aussage auch als Voraussetzung verwendet wird und es ergibt sich ein (mathematisch wertloser) Zirkelschluss. Ist die zu beweisende Formel hingegen falsch, so führt der Induktionsschritt nicht zum Ziel, die Formel erfüllt den Induktionsanfang nicht, oder es tritt beides auf.

Anderes Beispiel: Summe der ungeraden Zahlen

---

Es soll eine Formel gefunden werden, die die Summe aller ungeraden Zahlen von 1 bis $n$ vereinfacht und diese Formel soll bewiesen werden:

1 = 1; 1 + 3 = 4; 1 + 3 + 5 = 9; 1 + 3 + 5 + 7 = 16

Vermutung: Die Summe aller ungeraden Zahlen von 1 bis $2n-1$ ist gleich dem Quadrat von $n$. Genauer gesagt:

$\backslash sum^n\_\{i=1\}\; (2i-1)\; =\; n^2$

Um diese Formel zu beweisen, müssen die folgenden zwei Punkte erfüllt sein:

1. $\backslash sum^1\_\{i=1\}\; (2i-1)\; =\; 1^2$
2. Wenn $\backslash sum^n\_\{i=1\}\; (2i-1)\; =\; n^2$, so ist $\backslash sum^\{n+1\}\_\{i=1\}\; (2i-1)\; =\; (n+1)^2$

Da $\backslash sum^1\_\{i=1\}\; (2i-1)\; =\; 1\; =1^2$ ist, ist der erste Punkt erfüllt. Die Richtigkeit des zweiten Punktes zeigt man durch die Gleichung $\backslash sum^\{n+1\}\_\{i=1\}\; (2i-1)\; =\; \backslash sum^n\_\{i=1\}\; (2i-1)\; +\; (2(n+1)-1)\; =\; n^2\; +\; 2(n+1)-1\; =\; n^2\; +\; 2n\; +1\; =\; (n+1)^2$ (Im letzten Schritt wird eine binomische Formel angewendet).

Damit ist die vollständige Induktion für $\backslash sum^n\_\{i=1\}\; (2i-1)\; =\; n^2$ abgeschlossen und bewiesen.

Bezeichnungen

---

Den Beweis der Aussage für die erste Zahl nennt man Induktionsanfang, den Beweis für $n+1$ unter der Annahme (Induktionsannahme, Induktionsvoraussetzung), dass sie bis $n$ gilt, nennt man Induktionsschritt.

Wurden beide Beweisschritte durchgeführt, ist somit die Aussage für alle natürlichen Zahlen bewiesen. In Kurzform:

Gewählt wird eine beliebige aber feste natürliche Zahl $N$ und man zeigt, dass die Aussage für $N$ wahr ist:

• Die Aussage ist wahr für $n\; =\; 0$ (Induktionsanfang)
• und deshalb für $n\; =\; 1$ (Induktionsschritt)
• und deshalb für $n\; =\; 2$ (Induktionsschritt)
• ...
• und deshalb für $n\; =\; N$ (Induktionsschritt)

Nach endlich vielen Induktionsschritten gelangt man schließlich zur Aussage für $N$.

Oft wird diese Methode mit dem Dominoeffekt verglichen: Wenn der erste Dominostein fällt und durch jeden fallenden Dominostein ein weiterer umgestoßen wird, so fallen schließlich alle Dominosteine.

Indirekte Sichtweise

---

Eine andere Sichtweise ist die eines indirekten Beweises: Angenommen, die Aussage gälte nicht für alle natürlichen Zahlen. Dann gibt es eine kleinste Zahl $n\_0$, für die sie falsch ist. Es gibt nun zwei Fälle:

• $n\_0=0$: Dies wird durch den Induktionsanfang ausgeschlossen.
• $n\_0\backslash ne0$: Nach Voraussetzung ist $n\_0$ die kleinste Zahl, für die die Aussage falsch ist, also ist sie für $n\_0-1$ wahr. Wendet man nun den Induktionsschritt an, kann man daraus schließen, dass die Aussage auch für $(n\_0-1)+1=n\_0$ richtig ist. $n\_0$ war aber definiert als die kleinste Zahl, für die die Aussage falsch ist: Widerspruch.

Beide Fälle können also ausgeschlossen werden, damit ist die Aussage für alle natürlichen Zahlen wahr.

Beweis von Ungleichungen

---

Vollständige Induktion kann auch zum Beweis von Ungleichungen verwendet werden. Diese Beweise sind aber häufig schwieriger als die Beweise von Gleichungen, da sie üblicherweise mehr oder weniger naheliegende Abschätzungen erfordern. Als Beispiel werde folgende Ungleichung bewiesen: Für reelle $x\_i>0\backslash !$, $i=1,\backslash dots,n$ mit $\backslash prod\_\{i=1\}^n\; x\_i\; =1$ folgt, dass $\backslash sum\_\{i=1\}^n\; x\_i\; \backslash geq\; n$.

Die Bedeutung dieser Ungleichung liegt darin, dass sie in weiterer Folge für den Beweis der Ungleichung vom arithmetischen und geometrischen Mittel verwendet werden kann.

Der Induktionsanfang für den Fall $n=1$ ist offensichtlich. Gilt im Fall $n=2$, dass $x\_1=x\_2=1$, so gilt offensichtlich $x\_1+x\_2\; =\; 2\backslash geq\; 2$. $x\_1$ und $x\_2$ können nicht beide größer oder beide kleiner als 1 sein. Nimmt man an, dass $x\_1\backslash leq1$ und $x\_2\backslash geq1$ gilt, so folgt

$0\backslash leq(1-x\_1)(x\_2-1)=x\_1+x\_2-x\_1\backslash cdot\; x\_2\; -\; 1\; =\; x\_1+x\_2\; -\; 2$

wegen $x\_1\backslash cdot\; x\_2=1$, also

$2\backslash leq\; x\_1+x\_2$. Der Fall $x\_1\backslash geq1$ und $x\_2\backslash leq1$ ist vollkommen analog zu behandeln.

Für den Induktionsschritt sei nun $n\backslash geq\; 2$. Zu zeigen ist, dass für beliebige $n+1$ positive $x\_i\backslash !$ mit $\backslash prod\_\{i=1\}^\{n+1\}\; x\_i\; =1$ folgt, dass $\backslash sum\_\{i=1\}^\{n+1\}\; x\_i\; \backslash geq\; n+1$. Als Induktionsvoraussetzung darf angenommen werden, dass für $n$ andere beliebige Zahlen (zur einfacheren Unterscheidung nennen wir sie $y\_i$) aus $\backslash prod\_\{i=1\}^\{n\}\; y\_i\; =1$ die Ungleichung $\backslash sum\_\{i=1\}^\{n\}\; y\_i\; \backslash geq\; n$ folgt.

Sind alle $x\_i=1$, so gilt $\backslash sum\_\{i=1\}^\{n+1\}\; x\_i\; =\; n+1$ und der Beweis ist fertig. Andernfalls gibt es mindestens ein $x\_i>\; 1$, sonst wäre das Produkt ; ebenso gibt es ein anderes . O. B. d. A. sei also und $x\_\{n+1\}>1$. Die Bedeutung dieser Wahl wird erst später klar.

Setzt man nun $y\_i=x\_i$ für $i=1,\backslash dots,n-1$ und $y\_n=x\_n\backslash cdot\; x\_\{n+1\}$, so gilt

$\backslash prod\_\{i=1\}^\{n\}\; y\_i\; =\; \backslash prod\_\{i=1\}^\{n+1\}\; x\_i\; =1$.

Somit kann die Induktionsvoraussetzung angewendet werden und es folgt

$n\backslash leq\; \backslash sum\_\{i=1\}^\{n\}\; y\_i\; =\; \backslash sum\_\{i=1\}^\{n-1\}\; x\_i\; +\; x\_n\backslash cdot\; x\_\{n+1\}$.

Nun kommt ins Spiel, dass die Indizes $n$ und $n+1$ so gewählt wurden, dass und $x\_\{n+1\}>1$ gilt. Daraus folgt nämlich

$0\backslash leq\; \backslash left(1-x\_n\backslash right)\backslash left(x\_\{n+1\}-1\backslash right)=x\_n+x\_\{n+1\}-x\_n\backslash cdot\; x\_\{n+1\}\; -1$.

Addiert man die beiden Ungleichungen, so erhält man

$n\backslash leq\; \backslash sum\_\{i=1\}^\{n-1\}\; x\_i\; +\; x\_n+\; x\_\{n+1\}\; -1\; =\; \backslash sum\_\{i=1\}^\{n+1\}\; x\_i\; -1$,

also genau die Behauptung

$n+1\; \backslash leq\; \backslash sum\_\{i=1\}^\{n+1\}\; x\_i$.

Tipps zur Anwendung

---

Es kann sich beim Beweis von Summenformeln mitunter als sehr mühsam erweisen, beim Induktionsschritt von $n$ zu $n+1$ durch Umformungen die Struktur der Ausgangsformel neu zu konstruieren. Dies ist jedoch zur Beweisführung unerlässlich. Da ist es dann manchmal hilfreich, das Pferd von hinten aufzuzäumen. Beispielsweise ist das Ausmultiplizieren und Zusammenfassen von Gliedern oftmals leichter zu bewerkstelligen als das phantasievolle Aufspalten und Umordnen von Gliedern, um etwas ausklammern zu können. Um diesen Umstand zu nutzen, setzt man in die zu beweisende Formel $n+1$ für $n$ ein und versucht, durch äquivalente Umformungen die Ausgangsformel für $n$ zu isolieren. Da die Formel für $n$ laut Voraussetzung gilt, ist der Beweis geführt, sobald das, was bei den äquivalenten Umformungen außer der isolierten Formel z. B. als Summand oder als zusätzlicher Faktor entsteht, dem entspricht, was beim Induktionsschritt hinzugefügt wird.

Häufige Fehler

Beim Beweis durch Induktion treten zwei Fehler besonders häufig auf.

• Der Induktionsschritt funktioniert zwar, die Behauptung gilt für die Anfangsbedingung aber nicht. Man könnte z.B. behaupten, dass

$1\; +\; 2\; +\; 3\; +\; \backslash dots\; +\; n\; =\; \backslash frac\{n(n+1)\}\{2\}\; +\; 7$.

Falls diese Behauptung für ein n gelten würde, dann würde sie auch für $n\; +\; 1$ gelten! Da sie aber für $n\; =\; 1$ nicht gilt, ist sie falsch!

• Der Induktionsschritt ist nicht für alle $n$ gültig, d.h. es gibt mindestens ein $n$ ($>=\; n0$ der Verankerung), für das er nicht anwendbar ist. Hier ein Beispiel für so einen falschen Beweis:

Behauptung: Alle Zahlen sind gleich.

Beweis: Wir vergleichen Mengen von Zahlen, dabei sei $n$ die Anzahl der Elemente der Menge.

Induktionsbeginn: Für $n\; =\; 1$ sind alle Elemente der Menge gleich, es gibt ja nur eines!

Induktionsvoraussetzung: Angenommen, in einer Menge mit $n$ Zahlen sind stets alle Zahlen gleich

Induktionsschritt: Dann sind auch alle Zahlen in einer Menge mit $n\; +\; 1$ Zahlen gleich, denn: Entfernt man aus der $n\; +\; 1$-elementigen Menge eine Zahl $x$, dann erhalten wir eine $n$-elementige Menge, in der nach Voraussetzung alle Zahlen gleich sind. Fügen wir $x$ wieder hinzu und entfernen eine andere Zahl $y$, dann sind wieder alle Zahlen der Restmenge gleich. Es folgt, dass $x\; =\; y$ gelten muss, also sind alle Zahlen der Menge gleich.

Der Fehler liegt darin, dass man nur dann verschiedene Zahlen $x$ und $y$ entfernen kann,

wenn die Menge mindestens 2 Elemente hat ($n>=2$).

Der Schluss von $n$ auf $n+1$ ist also nur für $n>=2$ korrekt! Dass die Behauptung für $n\; =\; 1$ richtig ist hilft uns nicht, da auf diesen Fall der Induktionsschritt überhaupt nicht anwendbar ist!

Anwendungen

---

Baut man die natürlichen Zahlen auf den Peano-Axiomen auf, so werden die arithmetischen Grundgesetze wie Assoziativgesetz, Kommutativgesetz und Distributivgesetz für die Addition und Multiplikation natürlicher Zahlen mit vollständiger Induktion bewiesen. Eine ausführliche Ausarbeitung dieser Beweise findet sich in Edmund Landau: Grundlagen der Analysis (Das Rechnen mit ganzen, rationalen, irrationalen, komplexen Zahlen), Leipzig 1930.

Weitere wichtige mathematische Sätze, die üblicherweise mit Induktion bewiesen werden, sind beispielsweise der Binomische Lehrsatz und die Bernoullische Ungleichung.

Verallgemeinerungen und Variationen

---

Beweis für fast alle natürlichen Zahlen

Der Induktionsbeweis ist auch für Aussagen möglich, die nicht für alle natürlichen Zahlen, sondern nur für alle Zahlen ab einem gewissen Startwert gelten. So lässt sich beispielsweise für die Ungleichung $2^n\backslash ge\; n^2$ der Induktionsschritt für $n\backslash ge\; 3$ durchführen:

$2^\{n+1\}=2\backslash cdot\; 2^n\backslash ge\; 2n^2$ laut Induktionsvoraussetzung,

$2n^2\; =n^2+n^2\backslash ge\; n^2+3n\; >\; n^2+2n+1=(n+1)^2$ für $n\backslash ge\; 3$.

Die Ungleichung ist allerdings für $n=3$ falsch, gilt aber für $n=4$; der Induktionsbeweis zeigt also die Gültigkeit der Ungleichung für $n\backslash ge\; 4$. Die endlich vielen Fälle, die durch den Induktionsbeweis nicht abgedeckt sind, können einzeln untersucht werden.

Verwendung mehrerer Vorgänger

Manchmal ist es notwendig, für den Beweis der Aussage für $n+1$ die Gültigkeit sowohl für $n$ als auch für $n-1$ (oder für noch mehr Vorgänger) vorauszusetzen. Der Induktionsanfang muss dann allerdings für mehrere Startwerte (also z.B. $n=0$ und $n=1$) durchgeführt werden, da ja beispielsweise für den Induktionsschritt für $n=1$ auch die Voraussetzung für $n=-1$ benötigt würde. Ein Beispiel wäre der Beweis der Formeln von Binet

$f\_n=\backslash frac\{1\}\{\backslash sqrt\{5\}\}(a^n-b^n)$ mit a = $\backslash frac\{1+\backslash sqrt\{5\}\}\{2\}$ und b = $\backslash frac\{1-\backslash sqrt\{5\}\}\{2\}$

für die Fibonacci-Folge $f\_n$.

Vorwärts-rückwärts-Induktion

Eine andere Variante ist die "Vorwärts-rückwärts-Induktion". Dabei wird in einem Vorwärtsschritt die Aussage für beliebig große Zahlen bewiesen, indem z.B. von $n$ auf $2n$ geschlossen wird. Danach werden die Lücken mit einem Rückwärtsschritt geschlossen, in dem z.B. aus der Gültigkeit für $n$ die Gültigkeit für $n-1$ bewiesen wird. Diese Technik wurde beispielsweise von Augustin Louis Cauchy, in Cours d'analyse de l'Ecole Royale Polytechnique, premier partie, Analyse algebrique, Paris 1821, S 457ff zum Beweis der Ungleichung vom arithmetischen und geometrischen Mittel verwendet.

Sonstige

Eine andere Verallgemeinerung wäre, als Induktionsvoraussetzung nicht nur eine Aussage für die Zahl $n$ zu verwenden, sondern eine Aussage für alle Zahlen $m$ mit $0\; \backslash leq\; m\; \backslash leq\; n$. D.h. man darf beim Beweis für $n+1$ annehmen, dass die Aussage für alle $m\; \backslash leq\; n$ gilt. Dies eröffnet der Beweisführung mehr Möglichkeiten.

Aus rechentechnischen Gründen wird oft als Induktionsschritt nicht von $n$ auf $n\; +\; 1$ geschlossen sondern von $n\; -\; 1$ auf $n$. Dies ist allerdings lediglich eine Notationsänderung, die manchmal die Umformungen vereinfacht, aber ansonsten keinen Unterschied macht.

Wenn man zu allgemeineren Mengen übergehen will, so zeigt sich, dass die vollständige Induktion auf allen Mengen anwendbar ist, auf denen eine partielle Ordnung definiert ist, wobei keine unendlichen absteigenden Ketten auftreten dürfen (weil sonst keine Anfangselemente gefunden werden können). Eine solche Menge heißt fundierte Menge.

Diese Art der Induktion kann auf Ordinalzahlen angewendet werden (Ordinalzahlen können unendlich und größer werden). In diesem Fall wird die Methode transfinite Induktion genannt. Sie ist wichtig in der Mengenlehre und der Topologie. In der Metamathematik verwendet man eine so genannte unendliche Induktion (auch $\backslash omega$-Regel genannt). In halbformalen Systemen der Mathematik lassen sich damit Vollständigkeitsbeweise und Widerspruchsfreiheitsbeweise durchführen.

Weblinks

---

• Cauchy, Augustin-Louis. Analyse algébrique. Der Beweis der Ungleichung vom arithmetischen und geometrischen Mittel mittels Vorwärts-rückwärts-Induktion ist auf Seite 457ff.
• http://henked.de/begriffe/induktion.htm Vollständige Induktion
• Aufgaben mit Beweisen zur Induktion (pdf)

Mathematik

Математическа индукция | Matematická indukce | Induktion (matematik) | Mathematical induction | Inducción matemática | Raisonnement par récurrence | אינדוקציה מתמטית | Þrepun | Principio di induzione | 数学的帰納法 | Индукција | Inductie (wiskunde) | Indukcja matematyczna | Indução matemática | Математическая индукция | Matematická indukcia | Matematična indukcija | Induktion (matematik) | Matematiksel tümevarım | 数学归纳法