Transfinite Induktion

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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 auf die echte Klasse aller Ordinalzahlen.

Sei $A$ eine wohlgeordnete Menge (oder Klasse). Will man beweisen, dass die Eigenschaft $P$ für alle Elemente von $A$ zutrifft, so genügt es Folgendes zu beweisen:

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

Dass dies ausreicht, sieht man wie folgt:

Sei $B = \{x \in A | \neg P(x)\}$ die Menge (bzw. Klasse) derjenigen Elemente $x$ von $A$ , für die $P (x)$ nicht zutrifft. Träfe die Eigenschaft $P$ nicht für alle Elemente von $A$ zu, so wäre $B$ nicht leer und enthielte aufgrund der Wohlordnung ein kleinstes Element $a$ . Für jedes $b$ mit $b < a$ gilt dann $b \notin B$ , also $P (b)$ . Nach dem gezeigten folgt $P (a)$ .

Andererseits folgt aus $a \in B$ sofort $\neg P(a)$ . Da sich somit ein Widerspruch ergibt, muss die Annahme, dass $P$ nicht für alle Elemente von $A$ zutrifft, falsch gewesen sein.

Wenn $A$ die Klasse der Ordinalzahlen ist, zerlegt man den Beweis aus technischen Gründen häufig in folgende drei einzeln zu beweisende Fälle:

$P (0)$ ist wahr.
Ist $a$ eine Ordinalzahl, so folgt aus $P (a)$ auch $P (a + 1)$ .
Ist $a$ eine Grenzzahl (d.i. nach Definition die Vereinigung aller kleineren Ordinalzahlen) und gilt $P (b)$ für jede Ordinalzahl $b < a$ , so gilt auch $P (a)$ .

[Bearbeiten] Transfinite Rekursion

Bei den natürlichen Zahlen ist es bekanntlich möglich, Funktionen rekursiv zu definieren, also auf eine dem Beweis durch vollständige Induktion analoge Methode (Beispiel: $0!: = 1$ und $n!:=n \cdot (n-1)!$ für $n > 0$ ). Ebenso hat die transfinite Induktion das Definitionsverfahren der transfiniten Reduktion als "Schwester":

Ist $A$ wohlgeordnet und kann man $f (a)$ durch die Werte $f (b)$ ausschließlich an Stellen $b < a$ definieren, so ist hierdurch bereits $f$ auf ganz $A$ definiert.

Formaler gilt: Führen wir die Bezeichnungen $A_{<a}:=\{x\in A\mid x<a\}$ und $A_{\le a}:=\{x\in A\mid x \le a\}$ ein, so gilt der folgende

Rekursionssatz: Sei $A$ eine wohlgeordnete Menge, $B$ eine beliebige Menge.

Für alle $a \in A$ sei eine Abbildung $r_a: \mathrm{Abb}(A_{<a},B) \rightarrow B$ gegeben.

Dann existiert genau eine Abbildung $f: A \rightarrow B$ mit $f(a) = r_a( f \mid_{A_{<a}} )$ für alle $a \in A$ .

Beweis: Unter einem Abschnitt von $A$ wollen wir eine Teilmenge $C \subseteq A$ verstehen, bei der aus $a \in C$ stets auch $A_{<a} \subseteq C$ folgt. Ist $C$ ein Abschnitt von $A$ und existiert eine geeignete (d.h. im Folgenden: die Rekursion erfüllende) Abbildung $f_C:C\rightarrow B$ , so ist diese gewiß eindeutig bestimmt. Ist nämlich $g C$ eine weitere solche Abbildung und hat $a \in C$ die Eigenschaft, dass $f C (b) = g C (b)$ für alle $b < a$ gilt, so folgt auch $f_C(a) = r_a( f_C\mid_{A_a} ) = r_a( g_C\mid_{A_a} ) = g_C(a)$ .

Durch transfinite Induktion folgt also $f C = g C$ .

Ist $\{C_i\}_{i \in I}$ eine Familie von Abschnitten von $A$ und haben wir zugehörige geeignete Abbildungen $f_i:C_i\rightarrow B$ , so können wir wegen dieser Eindeutigkeit auf dem Abschnitt $C:=\bigcup_{i \in I} C_i$ eine Abbildung $f_C: C \rightarrow B$ definieren, indem wir $f C (a): = f i (a)$ setzen für ein beliebiges $i \in I$ mit $a \in C_i$ . Es folgt unmittelbar, dass auch $f C$ die Rekursion erfüllt.

Ist nun $a \in A$ und existiert zu jedem $b < a$ eine geeignete Abbildung $f_b:A_{\le b}\rightarrow B$ , so existiert wegen $A_{<a} = \bigcup_{b<a}A_{\le b}$ auch eine geeignete Abbildung $g_a: A_{<a} \rightarrow B$ . Indem wir $f a (a): = r a (g a)$ sowie $f a (b): = g a (b)$ für $b < a$ setzen, erhalten wir eine Abbildung $f_a:A_{\le a}\rightarrow B$ , die ebenfalls die Rekursion erfüllt.

Durch transfinite Induktion folgt also, dass es zu jedem $a \in A$ eine geeignete Abbildung $f_a:A_{\le a}\rightarrow B$ gibt.

Wegen $A=\bigcup_{a \in A} A_{\le a}$ gibt es dann aber auch eine geeignete Abbildung $f:A\rightarrow B$ , die dann, wie bereits gezeigt, auch eindeutig bestimmt ist.

Von „http://de.wikipedia.org../../../t/r/a/Transfinite_Induktion_aefe.html“

Kategorie: Logik

Transfinite Induktion

aus Wikipedia, der freien Enzyklopädie

[Bearbeiten] Transfinite Rekursion

Views

Navigation

Mitmachen

Suche

Andere Sprachen