Transfinite Induktion

Verallgemeinerung der vollständigen Induktion auf die Klasse aller Ordinalzahlen als Index

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. Die erste transfinite Rekursion führte Georg Cantor 1897 durch.[1] Felix Hausdorff erhob sie zum allgemeinen Definitionsprinzip und führte auch die transfinite Induktion als Beweisprinzip ein.[2]

DefinitionBearbeiten

Als transfinite Induktion gilt das folgende für eine wohlgeordnete Klasse   erklärte Beweisschema:

Will man beweisen, dass für alle   die Aussage   gilt, so genügt es, die folgende Induktionsaussage zu beweisen:
Wenn   ist und für alle   mit   die Aussage   gilt, dann gilt auch  .

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

AnwendungBearbeiten

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

  •   ist wahr.
  • Ist   eine Ordinalzahl, so folgt aus   auch  .
  • Ist   eine Grenzzahl und gilt   für jede Ordinalzahl  , so gilt auch  .

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 RekursionBearbeiten

Als transfinite Rekursion gilt folgendes Definitionsverfahren in einer wohlgeordneten Klasse  :

Kann   ausschließlich durch die Werte   an Stellen   definiert werden, so ist bereits hierdurch   auf ganz   definiert.

Dieses Rekursionsprinzip wird nun formalisiert für Ordinalzahlen.

Rekursionssatz:   sei die Klasse der Ordinalzahlen,   die Klasse aller Mengen und   ein Term als Rekursionsvorschrift. Dann gibt es genau eine transfinite Folge  , so dass für alle Ordinalzahlen   die Aussage   gilt.

Beweisidee: Man „vereinigt“ alle rekursiv definierten ordinalen Folgen mit derselben Rekursionsvorschrift zu einer transfiniten Folge. Die Rekursion für eine Ordinalzahl   erfasst folgende als   bezeichnete Aussage:

Es gibt genau eine Abbildung  , so dass für alle   die Aussage   gilt.

Diese Abbildungen   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   für alle Ordinalzahlen   zeigt man durch transfinite Induktion, und zwar wie oben angemerkt in drei Teilaussagen (es sei daran erinnert, dass für Ordinalzahlen   gleichbedeutend ist mit   und dass  ):

  1. Die Aussage   ergibt sich unmittelbar, da es gar keine Ordinalzahlen   gibt und die Rekursionsvorschrift trivialerweise gilt und da es ohnehin nur eine Abbildung   gibt.
  2. Gilt  , dann gilt auch  : Die Existenz von   ergibt sich aus  , indem man   setzt, falls  , sowie (notwendigerweise)  . Ist   eine Funktion nach denselben Bedingungen, so folgt zunächst   aus der Eindeutigkeitsaussage in   und dann aus der Rekursionsvorschrift auch  , also insgesamt  .
  3. Ist   Grenzzahl und gilt   für alle  , dann gilt auch  : Ist  , so gibt es   mit  . Man setze  . Dies ist wohldefiniert, da für   mit   wegen der voraussetzbaren Aussagen   gewiss   gilt. So ergibt sich auch die Eindeutigkeit.

Somit gilt die Aussage   für alle Ordinalzahlen  . Man kann jetzt   definieren, indem man   für ein beliebiges   setzt. Dies ist wohldefiniert (also unabhängig von der Wahl von  ), so dass man einfach auch   wählen kann.

AnwendungBearbeiten

Wie bei der transfiniten Induktion kann man auch bei der transfiniten Rekursion statt mit einer Rekursionsvorschrift mit dreien arbeiten: mit einem Anfangsfunktionswert  , einer Regel   für Nachfolgerzahlen (oft in der einfacheren Form  ) und einer Regel   für Grenzzahlen. Die beiden ersten Rekursionsschritte decken sich mit der üblichen Rekursion für natürliche Zahlen.

BeispieleBearbeiten

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

EinzelnachweiseBearbeiten

  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, Egbert Brieskorn: Grundzüge der Mengenlehre. 1. Auflage. Springer, Berlin, 2002, ISBN 3-540-42224-2, S. 112 f. (eingeschränkte Vorschau in der Google-Buchsuche).