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

Als transfinite Induktion gilt das folgende für eine wohlgeordnete Klasse $(A,<)$ erklärte Beweisschema:

Will man beweisen, dass für alle $a\in A$ die Aussage $P(a)$ gilt, so genügt es, die folgende Induktionsaussage zu beweisen:

Wenn $a\in A$ ist und für alle $b\in A$ mit $b<a$ die Aussage $P(b)$ gilt, dann gilt auch $P(a)$.

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

Anwendung

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

• $P(0)$ ist wahr.
• Ist $a$ eine Ordinalzahl, so folgt aus $P(a)$ auch $P(a+1)$.
• Ist $a$ eine Grenzzahl und gilt $P(b)$ für jede Ordinalzahl $b<a$, so gilt auch $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 $(A,<)$:

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

Dieses Rekursionsprinzip wird nun formalisiert für Ordinalzahlen.

Rekursionssatz: $\mathrm {On}$ sei die Klasse der Ordinalzahlen, $V$ die Klasse aller Mengen und $R(x)$ ein Term als Rekursionsvorschrift. Dann gibt es genau eine transfinite Folge $F\colon \mathrm {On} \to V$, so dass für alle Ordinalzahlen $a$ die Aussage $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 $b$ erfasst folgende als $P(b)$ bezeichnete Aussage:

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

Diese Abbildungen $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 $P(b)$ für alle Ordinalzahlen $b$ zeigt man durch transfinite Induktion, und zwar wie oben angemerkt in drei Teilaussagen (es sei daran erinnert, dass für Ordinalzahlen $a<b$ gleichbedeutend ist mit $a\in b$ und dass $b+1=b\cup \{b\}$):

1. Die Aussage $P(0)$ ergibt sich unmittelbar, da es gar keine Ordinalzahlen $a<0$ gibt und die Rekursionsvorschrift trivialerweise gilt und da es ohnehin nur eine Abbildung $0\to V$ gibt.
2. Gilt $P(b)$, dann gilt auch $P(b+1)$: Die Existenz von $F_{b+1}\colon b+1\to V$ ergibt sich aus $F_{b}\colon b\to V$, indem man $F_{b+1}(a)=F_{b}(a)$ setzt, falls $a<b$, sowie (notwendigerweise) $F_{b+1}(b)=R(F_{b})$. Ist $G_{b+1}\colon b+1\to V$ eine Funktion nach denselben Bedingungen, so folgt zunächst $G_{b+1}|_{b}=F_{b+1}|_{b}$ aus der Eindeutigkeitsaussage in $P(b)$ und dann aus der Rekursionsvorschrift auch $G_{b+1}(b)=R(F_{b})=F_{b+1}(b)$, also insgesamt $G_{b+1}=F_{b+1}$.
3. Ist $b$ Grenzzahl und gilt $P(a)$ für alle $a<b$, dann gilt auch $P(b)$: Ist $a<b$, so gibt es $c$ mit $a<c<b$. Man setze $F_{b}(a)=F_{c}(a)$. Dies ist wohldefiniert, da für $c'$ mit $a<c'<b$ wegen der voraussetzbaren Aussagen $P(a),P(c),P(c')$ gewiss $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 $P(b)$ für alle Ordinalzahlen $b$. Man kann jetzt $F\colon \mathrm {On} \to V$ definieren, indem man $F(b)=F_{c}(b)$ für ein beliebiges $c>b$ setzt. Dies ist wohldefiniert (also unabhängig von der Wahl von $c$), so dass man einfach auch $c=b+1$ wählen kann.

Anwendung

Wie bei der transfiniten Induktion kann man auch bei der transfiniten Rekursion statt mit einer Rekursionsvorschrift mit dreien arbeiten: mit einem Anfangsfunktionswert $F(0)=R_{1}$, einer Regel $F(b+1)=R_{2}(F|_{b+1})$ für Nachfolgerzahlen (oft in der einfacheren Form $F(b+1)=R_{2}(F(b))$) und einer Regel $F(b)=R_{3}(F|_{b})$ für Grenzzahlen. Die beiden ersten Rekursionsschritte decken sich mit der üblichen Rekursion für natürliche Zahlen.

Beispiele

1. Sei $c$ eine fest gewählte Ordinalzahl und die Rekursionsvorschrift $G$ folgendermaßen gewählt: Falls $f$ der Graph einer Funktion ist, sei $R(f)$ die kleinste nicht in $c\cup \operatorname {Bild} (f)$ auftauchende Ordinalzahl (und ansonsten beliebig). Die hierdurch rekursiv (in Abhängigkeit von $c$) definierte Funktion $F$ liefert stets eine Ordinalzahl (folgt durch transfinite Induktion) und es gilt $F(0)=c$, $F(1)=c+1$ usw. Man schreibt $c+a$ für $F(a)$ und definiert so die Addition von Ordinalzahlen.
2. Die Addition kann auch – leichter nachvollziehbar – durch drei Rekursionsschritte definiert werden:
   • $c+0:=c$,
   • $c+(b+1):=(c+b)+1$ sowie
   • $c+b:=\sup\{c+a|a<b\}$, falls $b$ Grenzzahl ist.
3. Mit transfiniter Rekursion kann gezeigt werden: Jede wohlgeordnete Menge $(A,<)$ ist ordnungsisomorph zu einer Ordinalzahl. Beweisidee: Man versucht $F\colon \mathrm {On} \to A$ mittels der Rekursionsvorschrift $R(f)=\min(A\setminus \operatorname {Bild} f)$ zu definieren. Hierbei wäre $F$ automatisch injektiv, was aber nicht sein kann, da $A$ keine echte Klasse ist. Für die kleinste Ordinalzahl, an der die Rekursion scheitert, ergibt sich ein Ordnungsisomorphismus mit $(A,<)$.
4. Durch transfinite Rekursion wird auch die kumulative Hierarchie von Mengen definiert.