Transfinite Induktion

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. 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]

Inhaltsverzeichnis

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 | \neg P(x)\}, das ist die Klasse aller Elemente von A, für die P nicht zutrifft. Angenommen B sei nicht leer, dann gäbe es wegen der Wohlordnung ein kleinstes Element a \in B, und es gälte 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ändige 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: 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 Fb(a) = R(Fb | a) gilt.

Diese Abbildungen Fb 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 Fb + 1(a) = Fb(a) setzt, falls a < b, sowie (notwendigerweise) Fb + 1(b) = R(Fb). Ist G_{b+1}\colon b+1\to V eine Funktion nach denselben Bedingungen, so folgt zunächst Gb + 1 | b = Fb + 1 | b aus der Eindeutigkeitsaussage in P(b) und dann aus der Rekursionsvorschrift auch Gb + 1(b) = R(Fb) = Fb + 1(b), also insgesamt Gb + 1 = Fb + 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 Fb(a) = Fc(a). Dies ist wohldefiniert, da für c' mit a < c' < b wegen der voraussetzbaren Aussagen P(a),P(c),P(c') gewiss Fc'(a) = R(Fc' | a) = R(Fa) = R(Fc | a) = Fc(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) = Fc(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) = R1, einer Regel F(b + 1) = R2(F | b + 1) für Nachfolgerzahlen (oft in der einfacheren Form F(b + 1) = R2(F(b)) und einer Regel F(b) = R3(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 Ordnungsisiomorphismus mit (A, < ).
  4. Durch transfinite Rekursion wird auch die kumulative Hierarchie von Mengen definiert.

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

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Transfinite Rekursion — Transfinite Induktion ist eine Beweistechnik in der Mathematik, die die von den natürlichen Zahlen bekannte Induktion auf beliebige wohlgeordnete Mengen verallgemeinert, zum Beispiel auf Mengen von Ordinalzahlen oder Kardinalzahlen, oder sogar… …   Deutsch Wikipedia

  • Induktion — (lateinisch: inductio „(Her /Hin)Einführung“) steht für: Elektromagnetische Induktion, ein Phänomen im Zusammenhang mit Strom und Magnetismus Magnetische Induktion, alternative Bezeichnung für die magnetische Flussdichte Enzyminduktion in der… …   Deutsch Wikipedia

  • Noethersche Induktion — Eine fundierte Menge (auch wohlfundierte Menge, fundierte Ordnung, terminierende Ordnung, noethersche Ordnung) ist eine halbgeordnete Menge, die keine unendlichen absteigenden Ketten enthält. Äquivalent dazu heißt eine halbgeordnete Menge… …   Deutsch Wikipedia

  • Induktiv — Induktion (v. lat. inductio ‚Einführung, Hereinführung‘ und inducere ‚hineinführen‘) steht für: elektromagnetische Induktion, ein Phänomen im Zusammenhang mit Strom und Magnetismus magnetische Induktion, alternative Bezeichnung für die… …   Deutsch Wikipedia

  • Induzieren — Induktion (v. lat. inductio ‚Einführung, Hereinführung‘ und inducere ‚hineinführen‘) steht für: elektromagnetische Induktion, ein Phänomen im Zusammenhang mit Strom und Magnetismus magnetische Induktion, alternative Bezeichnung für die… …   Deutsch Wikipedia

  • Limeszahl — Beim Zählen benutzt man Ordinalzahlen (auch Ordnungszahlen genannt), um die Position eines Elements in einer Folge anzugeben: „Erstes, zweites, drittes, … Element“. Sprachlich benutzt man dazu bestimmte Zahlwörter. Auf diese Weise ordnet man… …   Deutsch Wikipedia

  • Ordinalzahlen — Beim Zählen benutzt man Ordinalzahlen (auch Ordnungszahlen genannt), um die Position eines Elements in einer Folge anzugeben: „Erstes, zweites, drittes, … Element“. Sprachlich benutzt man dazu bestimmte Zahlwörter. Auf diese Weise ordnet man… …   Deutsch Wikipedia

  • Ordnungsisomorphie — Beim Zählen benutzt man Ordinalzahlen (auch Ordnungszahlen genannt), um die Position eines Elements in einer Folge anzugeben: „Erstes, zweites, drittes, … Element“. Sprachlich benutzt man dazu bestimmte Zahlwörter. Auf diese Weise ordnet man… …   Deutsch Wikipedia

  • Ordnungsisomorphismus — Beim Zählen benutzt man Ordinalzahlen (auch Ordnungszahlen genannt), um die Position eines Elements in einer Folge anzugeben: „Erstes, zweites, drittes, … Element“. Sprachlich benutzt man dazu bestimmte Zahlwörter. Auf diese Weise ordnet man… …   Deutsch Wikipedia

  • Mathematische Beweismethode — Ein Beweis ist in der Mathematik die als fehlerfrei anerkannte Herleitung der Richtigkeit oder auch Unrichtigkeit einer Aussage aus einer Menge von Axiomen, die als wahr vorausgesetzt werden, und anderen Aussagen, die bereits bewiesen sind. Man… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”