Transfinite Induktion

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Transfinite Rekursion)
Zur Navigation springen Zur Suche springen

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

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 wäre 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 gelte 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.

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 Rekursion

[Bearbeiten | Quelltext bearbeiten]

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.

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.

  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.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  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 [1]