Transfinite Induktion

Transfinite Induktion ist eine Beweistechnik in der Mathematik, die die von den natürlichen Zahlen bekannte Induktion auf beliebige wohlgeordnete Klassen verallgemeinert, zum Beispiel auf Mengen von Ordinalzahlen oder Kardinalzahlen, oder sogar auf die echte Klasse aller Ordinalzahlen. Entsprechend ist die transfinite Rekursion ein Definitionsprinzip, das die Rekursion bei natürlichen Zahlen verallgemeinert. Sie ist ein deduktives Verfahren.

Die erste transfinite Rekursion führte Georg Cantor 1897 durch. Felix Hausdorff erhob sie zum allgemeinen Definitionsprinzip und führte auch die transfinite Induktion als Beweisprinzip ein.

Definition

Sei ${\displaystyle (A,<)}$ eine wohlgeordnete Klasse. Als transfinite Induktion gilt das folgende Beweisschema: Will man beweisen, dass für alle ${\displaystyle a\in A}$ die Aussage ${\displaystyle P(a)}$ gilt, genügt es zu zeigen:

Für jedes ${\displaystyle a\in A}$ gilt: wenn die Aussage ${\displaystyle P(b)}$ für alle ${\displaystyle b<a}$ gilt, dann gilt auch ${\displaystyle P(a)}$.

Kurz in Formeln:

${\displaystyle \forall a\in A:\ (\forall b<a:\ P(b))\Rightarrow P(a)}$

Die Wohlordnung impliziert, dass aus ${\displaystyle b<a}$ bereits ${\displaystyle b\in A}$ folgt.

Dass diese bewiesene Induktionsaussage tatsächlich genügt, sieht man so ein: Sei ${\displaystyle B=\{x\in A\mid \neg P(x)\}}$; das ist die Klasse aller Elemente von ${\displaystyle A}$, für die ${\displaystyle P}$ nicht zutrifft. Angenommen ${\displaystyle B}$ wäre nicht leer, dann gäbe es wegen der Wohlordnung ein kleinstes Element ${\displaystyle a\in B}$ (welches o. B. d. A. auch das Element ist, das die Aussage für kleinere Elemente ${\displaystyle b<a}$ beweist), und es gälte für jedes ${\displaystyle b}$ mit ${\displaystyle b<a}$ auch ${\displaystyle b\notin B}$, nach Definition von ${\displaystyle B}$ also ${\displaystyle P(b)}$. Dann gilt aber nach der bewiesenen Induktionsaussage auch ${\displaystyle P(a)}$. Andererseits folgt jedoch aus ${\displaystyle a\in B}$ sofort auch ${\displaystyle \neg P(a)}$. Wegen dieses Widerspruchs war die Annahme, ${\displaystyle B}$ sei nicht leer, falsch, so dass tatsächlich ${\displaystyle P}$ für alle Elemente von ${\displaystyle A}$ zutrifft.

Anwendung

Wenn ${\displaystyle A}$ die Klasse der Ordinalzahlen ist, zerlegt man den Beweis oft in folgende drei Beweisschritte:

• ${\displaystyle P(0)}$ ist wahr.
• Ist ${\displaystyle a}$ eine Ordinalzahl, so folgt aus ${\displaystyle P(a)}$ auch ${\displaystyle P(a+1)}$.
• Ist ${\displaystyle a}$ eine Grenzzahl und gilt ${\displaystyle P(b)}$ für jede Ordinalzahl ${\displaystyle b<a}$, so gilt auch ${\displaystyle P(a)}$.

Die ersten beiden Schritte decken sich mit der vollständigen Induktion für natürliche Zahlen, denn die Menge der natürlichen Zahlen ist der bis an die erste Grenzzahl reichende Abschnitt der Klasse der Ordinalzahlen.

Transfinite Rekursion

Als transfinite Rekursion gilt folgendes Definitionsverfahren in einer wohlgeordneten Klasse ${\displaystyle (A,<)}$:

Kann ${\displaystyle f(a)}$ ausschließlich durch die Werte ${\displaystyle f(b)}$ an Stellen ${\displaystyle b<a}$ definiert werden, so ist bereits hierdurch ${\displaystyle f}$ auf ganz ${\displaystyle A}$ definiert.

Dieses Rekursionsprinzip wird nun formalisiert für Ordinalzahlen.

Rekursionssatz: ${\displaystyle \mathrm {On} }$ sei die Klasse der Ordinalzahlen, ${\displaystyle V}$ die Klasse aller Mengen und ${\displaystyle R(x)}$ ein Term als Rekursionsvorschrift. Dann gibt es genau eine transfinite Folge ${\displaystyle F\colon \mathrm {On} \to V}$, so dass für alle Ordinalzahlen ${\displaystyle a}$ die Aussage ${\displaystyle F(a)=R(F|_{a})}$ gilt.

Beweisidee: Man „vereinigt“ alle rekursiv definierten ordinalen Folgen mit derselben Rekursionsvorschrift zu einer transfiniten Folge. Die Rekursion für eine Ordinalzahl ${\displaystyle b}$ erfasst folgende als ${\displaystyle P(b)}$ bezeichnete Aussage:

Es gibt genau eine Abbildung ${\displaystyle F_{b}\colon b\to V}$, so dass für alle ${\displaystyle a<b}$ die Aussage ${\displaystyle F_{b}(a)=R(F_{b}|_{a})}$ gilt.

Diese Abbildungen ${\displaystyle F_{b}}$ erfüllen also dieselbe Rekursionsvorschrift, sind aber jeweils nicht auf der ganzen Klasse der Ordinalzahlen definiert. Aus der Eindeutigkeit ergibt sich jedoch, dass diese Funktionen Fortsetzungen voneinander sind und zu einer einzigen transfiniten Folge vereinigt werden können. Die Gültigkeit von ${\displaystyle P(b)}$ für alle Ordinalzahlen ${\displaystyle b}$ zeigt man durch transfinite Induktion, und zwar wie oben angemerkt in drei Teilaussagen (es sei daran erinnert, dass für Ordinalzahlen ${\displaystyle a<b}$ gleichbedeutend ist mit ${\displaystyle a\in b}$ und dass ${\displaystyle b+1=b\cup \{b\}}$):

1. Die Aussage ${\displaystyle P(0)}$ ergibt sich unmittelbar, da es gar keine Ordinalzahlen ${\displaystyle a<0}$ gibt und die Rekursionsvorschrift trivialerweise gilt und da es ohnehin nur eine Abbildung ${\displaystyle 0\to V}$ gibt.
2. Gilt ${\displaystyle P(b)}$, dann gilt auch ${\displaystyle P(b+1)}$: Die Existenz von ${\displaystyle F_{b+1}\colon b+1\to V}$ ergibt sich aus ${\displaystyle F_{b}\colon b\to V}$, indem man ${\displaystyle F_{b+1}(a)=F_{b}(a)}$ setzt, falls ${\displaystyle a<b}$, sowie (notwendigerweise) ${\displaystyle F_{b+1}(b)=R(F_{b})}$. Ist ${\displaystyle G_{b+1}\colon b+1\to V}$ eine Funktion nach denselben Bedingungen, so folgt zunächst ${\displaystyle G_{b+1}|_{b}=F_{b+1}|_{b}}$ aus der Eindeutigkeitsaussage in ${\displaystyle P(b)}$ und dann aus der Rekursionsvorschrift auch ${\displaystyle G_{b+1}(b)=R(F_{b})=F_{b+1}(b)}$, also insgesamt ${\displaystyle G_{b+1}=F_{b+1}}$.
3. Ist ${\displaystyle b}$ Grenzzahl und gilt ${\displaystyle P(a)}$ für alle ${\displaystyle a<b}$, dann gilt auch ${\displaystyle P(b)}$: Ist ${\displaystyle a<b}$, so gibt es ${\displaystyle c}$ mit ${\displaystyle a<c<b}$. Man setze ${\displaystyle F_{b}(a)=F_{c}(a)}$. Dies ist wohldefiniert, da für ${\displaystyle c'}$ mit ${\displaystyle a<c'<b}$ wegen der voraussetzbaren Aussagen ${\displaystyle P(a),P(c),P(c')}$ gewiss ${\displaystyle F_{c'}(a)=R(F_{c'}|_{a})=R(F_{a})=R(F_{c}|_{a})=F_{c}(a)}$ gilt. So ergibt sich auch die Eindeutigkeit.

Somit gilt die Aussage ${\displaystyle P(b)}$ für alle Ordinalzahlen ${\displaystyle b}$. Man kann jetzt ${\displaystyle F\colon \mathrm {On} \to V}$ definieren, indem man ${\displaystyle F(b)=F_{c}(b)}$ für ein beliebiges ${\displaystyle c>b}$ setzt. Dies ist wohldefiniert (also unabhängig von der Wahl von ${\displaystyle c}$), so dass man einfach auch ${\displaystyle c=b+1}$ wählen kann.

Einzelnachweise

1. ↑ transfinite Rekursion zur Definition der Potenz von Ordinalzahlen, in: Cantor: Beiträge zur Begründung der transfiniten Mengenlehre 2., in: Mathematische Annalen 49 (1897), §18, 231f.
2. ↑ Felix Hausdorff: Grundzüge der Mengenlehre, Leipzig 1914, S. 112f