| Definition: Eine geordnete Menge ist wohlgeordnet, falls jede nichtleere Teilmenge ein kleinstes Element enthält. |
Wohlordnungen sind immer linear geordnet.
Die Wohlordnung von (N,
)
wird zum Beweisprinzip des "kleinsten Verbrechers"
(eine Variation der vollständigen Induktion) genutzt
(Beispiel).
Außerdem kann man das Prinzip der vollständigen
Induktion auf Wohlordnungen verallgemeinern:
Prinzip der transfiniten Induktion:
(W,<) sei eine wohlgeordnete linear geordnete Menge.
und für jedes w  W sei P(w)
eine Aussage.
W richtig.
|
|
Beweis durch Widerspruch.
Angenommen die beiden Voraussetzungen wären erfüllt,
und P(w) wäre trotzdem für gewisse
w W falsch.
Dann ist die Menge F aller w W,
für die P(w) falsch ist, nichtleer.
Da W wohlgeordnet ist hat F ein kleinstes Element x.
Da x der "kleinste Verbrecher" ist, ist
für jedes y mit y < x die Aussage P(y) richtig.
Nach der zweiten Voraussetzung (Induktionsschritt)
ist somit P(x) richtig, ein Widerspruch.
|
Ein Beispiel zur transfiniten Induktion.....
Zu jeder nichtwohlgeordneten linearen Ordnung (M,<) gibt es eine
Teilmenge X, so daß (X,<) zu (Z-,<)
isomorph ist. (Z- ist die Menge
der negativen ganzen Zahlen.)