Wohlordnungssatz

Theorem der Mengenlehre

Der Wohlordnungssatz, manchmal auch Wohlordnungsprinzip genannt, ist eine Aussage der Mengenlehre und besagt:

Jede Menge kann wohlgeordnet werden.

Dieses Theorem ist nützlich, denn es erlaubt die Anwendung der transfiniten Induktion auf jeder Menge. Der Wohlordnungssatz ist äquivalent zum Auswahlaxiom.

Eigenschaft der natürlichen Zahlen

Manchmal bezeichnet der Wohlordnungssatz oder das Wohlordnungsprinzip aber die Eigenschaft der Menge der natürlichen Zahlen, wohlgeordnet zu sein:

Jede nichtleere Menge natürlicher Zahlen enthält eine kleinste Zahl.

Dies wird ausgenutzt bei Beweisen durch unendlichen Abstieg oder die Methode des kleinsten Verbrechers: Um zu zeigen, dass eine Menge S alle natürlichen Zahl enthält, kann man annehmen, dass sie nicht jede enthält, und wegen des Wohlordnungsprinzips gibt es dann eine kleinste natürliche Zahl, die nicht enthalten ist (ein kleinstes Gegenbeispiel). Wenn man dann zeigt, dass es ein noch kleineres Gegenbeispiel gibt, hat man einen Widerspruch. (Alternativ kann man auch zeigen, dass man für jedes Gegenbeispiel ein kleineres findet, und somit unendlich oft absteigen kann, was aber in den natürlichen Zahlen nicht möglich ist.)

Diese Beweismethode ist eine Umkehrung der vollständigen Induktion (so wie "Aus nicht-B folgt nicht-A" eine Umkehrung von "Aus A folgt B" ist), basiert aber auf derselben Wohlordnungseigenschaft der natürlichen Zahlen.

Anwendungsbeispiel

Ein Beispiel für diese Beweismethode ist folgende Aussage:

Die Untergruppen der additiven Gruppe (Z,+) der ganzen Zahlen sind genau die Teilmengen mZ mit m>=0.

Beweis: Dass diese Teilmengen Untergruppen sind, ist leicht nachzuprüfen. Sei nun U eine beliebige Untergruppe von Z. Enthält U keine positive ganze Zahl, dann ist U={0}=0Z. Andernfalls sei m die kleinste positive ganze Zahl in U. Sei x irgendein Element aus U, wir müssen zeigen, dass x=mq für eine ganze Zahl q ist. Dazu dividieren wir x mit Rest durch m: x = mq+r, mit q,r ganzzahlig und 0<=r<m. Weil r=x-mq in U liegt, wäre 0<r<m ein Widerspruch zur Wahl von m als kleinstem positiven Element von U, also ist r=0 und x=mq.