Diskussion:Transfinite Induktion

Kleine Frage von ups: Muss in der wohlgeordneten Menge das Element a - 1 vertreten sein?

Sprich: kann man überhaupt von P(a-1) sprechen oder muss man dies nicht anders formulieren (z.B.: das nach der Ordnung nächstkleinere Element von S)?

... das ist a-1 per. Def.

Einschrittinduktion

Transfinite Induktion geht schon bei fundierten Mengen, da ist nicht unbedingt eindeutig, was die Null sein soll.

Man kann allerdings Schritte 1 und 2 zusammenfassen zu:

• Zeige: Wenn P(b) wahr ist für alle Elemente b < a, dann ist auch P(a) wahr.

Manchmal ergibt sich's, dass der Beweis für Elemente ohne Vorgänger anders verläuft, als mit Vorgänger (wie in der klassischen Induktion). Es gibt aber auch Fälle (in denen beispielsweise der Induktionsschritt ohnehin eine Fallunterscheidung enthält, bei der die Induktionsvoraussetzung nicht in jedem Fall genutzt wird), bei denen eine Extrabehandlung der Vorgängerlosen Elemente nicht notwendig ist.

Beispiele für transfinite Induktion

Kennt jemand Beispiele für Sätze die sich mit transfiniter Induktion beweise lassen?
Wäre interressant, wenn man solche hier erwähnen würde.

Habe mal transfinite Rekursion eingeführt, wobei gleichzeitig ein beispielhafter Beweis per t.I. auftritt. Bin zwar noch nicht ganz glücklich mit der Formulierung, hoffe aber, daß dies schon mal als erstes Beispiel herhält.--Hagman 10:23, 8. Feb. 2007 (CET)

In der Funktionalanalysis wird der Satz von Hahn-Banach mit transfiniter Induktion bewiesen. Dieser Satz besagt, daß eine Aussage, die unter bestimmten Voraussetzungen in einem Unterraum eines Benachraums erfüllt ist, auch in dem gesamten Raum gilt.

Beim Beweis zeigt man zunächst, daß die Aussage auch in einer Erweiterung dieses Unterraum um eine Dimension erfüllt ist; mit transfiniter Induktion folgt schließlich, daß die Aussage dann in dem gesamten Raum gilt. (Sorry, wenn ich das zu schwammig formuliert haben sollte.)--Acfrinke 05:10, 5. Aug. 2007 (CEST)

Was ist denn transzendente Induktion? -- 790 16:59, 10. Jan. 2007 (CET)

Verständnisfrage

Irgendwie kriege ich den Sinn gerade nicht zusammen. Was ist mit dem folgenden Beispiel:

Die Menge sei $M=\{2,4,6,7,9,11\}$ und $P(x)$ sei wahr, wenn $x$ gerade ist. Wählt man jetzt $a=7$, so gilt wohl $P(b)$ für alle $b<a$. Bedeutet das jetzt, dass 7 gerade ist?

Sofern du die Hilfsaussage

Wenn $P(b)$ für alle $b<a$ gilt, so gilt auch $P(a)$

nachweisen kannst (und das wird dir in diesem Beispiel nicht gelingen, und zwar genau im Fall $a=7$), hast du als Ergebnis, dass $P(a)$ für alle $a$ gilt.--Hagman 07:55, 15. Feb. 2008 (CET)

Abgrenzung zur Vollständigen Induktion

Hallo Ich fände es nützlich, wenn mehr oder weniger verständlich erklärt würde, was der Unterschied ist zwischen der "klassischen" vollständigen Induktion und der transfiniten Induktion ist.

Oder zur strukturellen Induktion ... Sachen gibt's... -- Euronymous 00:12, 2. Mai 2010 (CEST)

Grenzzahl

Die hier angegebene Definition der Grenzzahl ist verkehrt. Da wäre jede Ordinalzahl eine Grenzzahl. Die Definition müsste mit dem Artikel "Ordinalzahl" übereinstimmen.--Wilfried Neumaier 12:11, 7. Apr. 2008 (CEST)

Jetzt ist der falsche Passus getilgt, aber es wird vorausgesetzt, dass man weiß, was eine Grenzzahl ist. Man findet die Information zwar im Artikel Ordinalzahl, aber relativ versteckt. Ich habe versucht einen Link zu setzen in das Unterkapitel 3.1 Limes- oder Nachfolgerzahlen, aber das hat nicht funktioniert. Vielleicht kennt sich da jemand besser aus, wie man dorthin verlinkt.--Wilfried Neumaier 00:20, 9. Apr. 2008 (CEST)

Hä?

Ich habe Verständnisprobleme mit folgender Aussage:

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)$.

Warum wird behauptet, "nach dem Gezeigten folgt P(a)"? a haben wir doch zwei Sätze zuvor als kleinstes Element der Menge B definiert, für welche die Aussage $\neg P(x)$ zutrifft. Wo wurde "P(a) ist wahr" gezeigt?

--Abdull 17:19, 2. Jul. 2009 (CEST)

Die Voraussetzung war ja, dass gilt"Wenn P(b) für alle b < a gilt, folgt P(a)". (nicht signierter Beitrag von 87.166.185.63 (Diskussion | Beiträge) 16:23, 17. Sep. 2009 (CEST))

Auch ich hatte mit dem Kommentar "nach dem Gezeigten folgt P(a)" Probleme. Er ist unglücklich formuliert. Es müsste heißen: "Dann gilt aber nach der Voraussetzung P(a)". --Wilfried Neumaier 13:02, 30. Jun. 2011 (CEST)

zur transfiniten Rekursion

1. Wieso wird hier die Menge $A_{\leq a}$ eingeführt, die gar nirgends im Artikel gebraucht wird?--Wilfried Neumaier 22:52, 23. Aug. 2011 (CEST)

2. Die transfinite Rekursion, die mir in Büchern begegnet, ist oft auf Ordinalzahlen zugeschnitten und dann auch dreistufig für 0, Nachfolger- und Limeszahlen. Das gehört auch in den Abschnitt 'Anwendung', der dann natürlich umbenannt werden müsste als "Transfinite Induktion und Rekursion bei Ordinalzahlen".--Wilfried Neumaier 13:42, 25. Aug. 2011 (CEST)

3. Die formale Erläuterung der transfiniten Rekursion ist äußerst undidaktisch. Was hier eigentlich läuft, sollte irgendwie klarer herauskommen. Der Artikel ist ja nicht für Mathematiker gedacht, die die Sache schon kennen. Ich finde deshalb, dass der ganze Abschnitt überarbeitet werden sollte.--Wilfried Neumaier 13:42, 25. Aug. 2011 (CEST)

4. Ich finde auch sachliche Mängel: Die Einführung der Abbildung $r_{a}$ liest sich so, als ob für jede Ordinalzahl eine solche Abbildung gegeben ist. Hier ist gar keine Abbildung gemeint, sondern nur der einzelne zugeordnete Wert, der mit $r_{a}$ bezeichnet wird. Irreführend finde ich auch das sehr beiläufig eingeführte $f_{a}$, verwechselbar mit $f(a)$.--Wilfried Neumaier 13:52, 25. Aug. 2011 (CEST)

Kann ich nachvollziehen. Ich arbeite mal an einer Umformulierung etwa wie folgt: 1) T.R. funktioniert für alle Wohlordnungen. 2) Genaue Formulierung der T.R im Falle der Klasse der Ordinalzahlen. 3) Beweis hierzu - der dann auch hinreichend einfach für einen in der wikipedia stehenden Beweis formuliert werden kann, denn das ganze Abschnittsgeschwurbel kann man sich da ja definitionsgemäß sparen 4) Wieder übertragen auf beliebige wohlgeordnete Mengen preOrdnungsisomorphie (die gleichzeitig ein Beispiel einer rekursiv definierten Abbildung ist). 5) (vielleicht auch vor 4) vielleicht rekursive Definition der Addition als Beispiel?--Hagman 20:39, 25. Aug. 2011 (CEST)

Textvorschlag

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$). Auf dieselbe Weise gehört zur transfiniten Induktion das Definitionsverfahren der transfiniten Rekursion:

Ist $A$ wohlgeordnet und kann man $f(a)$ definieren, indem man voraussetzt, dass die Werte $f(b)$ an allen Stellen $b<a$ definiert sind, so ist hierdurch bereits $f$ auf ganz $A$ definiert.

Formaler gilt der folgende (hier für die Klasse der Ordinalzahlen formulierte

Rekursionssatz: Es bezeichne $\mathrm {On}$ die Klasse der Ordinalzahlen und $V$ die Klasse aller Mengen. Sei $G\colon V\to V$ eine Klassenfunktion. Dann gibt es genau eine transfinite Folge $F\colon \mathrm {On} \to V$ mit der Eigenschaft, dass für alle Ordinalzahlen $a$ die Aussage $F(a)=G(F|_{a})$ gilt.

Beweisidee: Für eine Ordinalzahl $b$ sei $P(b)$ die folgende Aussage:

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

Die Gültigkeit von $P(b)$ für alle Ordinalzahlen $b$ zeigt man durch transfinite Induktion, und zwar wie oben angemerkt in drei Teilaussagen aufgeteilt:

1. Die Aussage $P(0)$ gilt trivialerweise, da es ohnehin nur eine Abbildung $\emptyset \to V$ gibt und die einschränkende Eigenschaft gar keine Einschränkung bedeutet, da es gar keine Ordinalzahlen $a<0$ gibt.
2. Es gelte $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)=G(F_{b})$. Ist $F'_{b+1}\colon b+1\to V$ eine weitere geeignete Funktion, so folgt zunächst $F'_{b+1}|_{b}=F_{b+1}|_{b}$ aus der Eindeutigkeitsaussage in $P(b)$ und dann auch $F'_{b+1}(b)=G(F_{b})=F(_{b+1}$, also insgesamt $F'_{b+1}=F_{b+1}$.
3. Sei $b$ Grenzzahl und es gelte $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 $P(a),P(c),P(c')$ gewiss $F_{c'}(a)=G(F_{c'}|_{a})=G(F_{a})=G(F_{c}|_{a})=F_{c}(a)$ gilt. So ergibt sich auch die Eindeutigkeit.

Somit gilt $P(b)$ für alle Ordinalzahlen $b$. Man kann jetzt $F\colon \mathrm {On} \to V$ definieren, indem man $F(b)=F_{b+1}(b)$ setzt.

Anwendung

Wiederum analog zur transfiniten Induktion kann man auch bei der transfiniten Rekursion anstelle einer allgemeinen Klassenfunktion $G$ mit drei Teilfällen arbeiten. Man gibt dann einen Anfangsfunktionswert $F(0)=g_{1}$ an, eine Regel der Form $F(b+1)=G_{2}(F|_{b})$ für Nachfolgerzahlen und eine der Form $F(b)=G_{3}(F|_{b})$ für Grenzzahlen.

Beispiele

1. Sei $c$ eine fest gewählte Ordinalzahl. Die Rekursionsfunktion $G$ sei wie folgt gewählt: Falls $A$ der Graph einer Funktion ist, sei $G(A)$ die kleinste nicht in $c\cup \operatorname {Bild} (A)$ 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 ebenso – leichter nachvollziehbar – definiert werden durch
   • $c+0:=c$,
   • $c+(b+1):=(c+b)+1$ sowie
   • $c+b:=\sup\{c+a|a<b\}$, falls $b$ Grenzzahl ist.

Klassenfunktion verlinkt nicht dahin, wo ich dachte. Habe ich die deutsche Bezeichnung für so was falsch im Kopf?--Hagman 23:32, 25. Aug. 2011 (CEST)

Diskussion des Vorschlags

1) Die Verlinkung von Klassenfunktion ist sinnlos, denn im Zielartikel kommt das Stichwort "Klassenfunktion" gar nicht vor. Eine Klassenfunktion braucht man aber eigentlich auch nicht. Dieser Begriff ist lediglich eine unschöne Umschreibung für einen Term $G(A)$ mit der Variablen $A$. Jeder Term ist im Rahmen einer Mengenlehre automatisch eine solche Klassenfunktion. Der Artikel Term ist hier schon brauchbar.--Wilfried Neumaier 07:00, 26. Aug. 2011 (CEST)

2) Die Strategie des Beweises ist jetzt wesentlich besser. Die Beweisidee ließe sich noch besser motivieren. Die Abbildung $F_{b}$ ist ja eine rekursiv definierte Folge mit Definitionsbereich $b$. Man vereinigt alle rekursiv definierten ordinalen Folgen $F_{b}$ mit derselben Rekursionsvorschrift $G(A)$ zu einer transfiniten Folge.--Wilfried Neumaier 07:14, 26. Aug. 2011 (CEST)

Verbesserungsvorschlag:

Dieses Rekursionsprinzip wird nun formalisiert für Ordinalzahlen.

Rekursionssatz: $\,\mathrm {On}$ sei die Klasse der Ordinalzahlen, $\,V$ die Klasse aller Mengen und $\,G(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)=G(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)=G(F_{b}|_{a})$ gilt.

Weiter wie oben; man müsste nur alle Formelteile in gleicher Größe schreiben.--Wilfried Neumaier 07:35, 26. Aug. 2011 (CEST)

Falls zu zwecks "Formelteile in gelicher Größe" auf Erzwungene PNG-Erzeugung umsteigen wolltest, ist dies zwar machbar, wird aber i.A. nicht gewünscht. Ich bin mal mutig und lade zu ebensolchem Mut ein.--Hagman 17:31, 26. Aug. 2011 (CEST)

Wenn man die umgekehrte Richtung erzwingen könnte, also die kleinere HTML-Schrift, wäre das Druckbild schärfer und besser und man hätte keine herausragenden Formeln. Kann man das? Ich habe es mit \textstyle probiert, aber leider erfolglos.--Wilfried Neumaier 17:58, 26. Aug. 2011 (CEST)