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