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:
![]()
|
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.)