Transfinite Induktion

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 S eine wohlgeordnete Menge und 0 bezeichne ihr kleinstes Element. Will man beweisen, dass die Eigenschaft P für alle Elemente von S zutrifft, dann beweist man mit transfiniter Induktion folgendes:

• P(0) ist wahr.
• Wenn a > 0 und P(b) wahr ist für alle Elemente b < a, dann ist auch P(a) wahr.

Der zweite Schritt wird bei transfiniter Induktion über Ordinalzahlen oft in zwei Fälle zerlegt: Falls a keine Grenzzahl ist (sondern eine Ordinalzahl mit Vorgänger), kann man wie bei der bekannten Induktion zeigen, dass allein aus P(a-1) die Gültigkeit von P(a) folgt. Falls a eine Grenzzahl ist (also keinen Vorgänger hat), funktioniert das nicht. Dann hilft oft die Tatsache, dass die Grenzzahl a nach Definition die Vereinigung aller Ordinalzahlen b < a ist.