Wohlordnungssatz

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

Jede Menge kann wohlgeordnet werden.

Dieses Theorem erlaubt die Anwendung der transfiniten Induktion auf jeder Menge. Der Wohlordnungssatz ist äquivalent zum Auswahlaxiom.

Georg Cantor, der Begründer der Mengenlehre, hielt den Wohlordnungssatz für ein „grundlegendes Denkgesetz“. Vielen Mathematikern schien aber schwer vorstellbar, dass etwa auf der Menge der reellen Zahlen eine Wohlordnung existieren solle. So glaubte denn auch 1904 Julius König, dies widerlegt zu haben; Felix Hausdorff fand jedoch wenig später einen Fehler im Widerlegversuch. Ernst Zermelo führte das Auswahlaxiom als „unbedenkliches logisches Prinzip“ ein, um den Wohlordnungssatz zu beweisen; dieses stellte sich jedoch schnell als äquivalent zum Wohlordnungssatz heraus. Das Auswahlaxiom und somit der Wohlordnungssatz sind unabhängig von der Zermelo-Fraenkel-Mengenlehre, d. h. sowohl der Satz als auch sein Gegenteil lassen sich widerspruchsfrei voraussetzen, wenn man die Widerspruchsfreiheit aller übrigen Axiome voraussetzt. Tatsächlich lässt sich zeigen, dass zumindest die Axiome der Zermelo-Fraenkel-Mengenlehre allein (inklusive des Auswahlaxioms) die explizite Konstruktion einer solchen Wohlordnung nicht zulassen.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} alle natürlichen Zahlen enthält, kann man zunächst annehmen, dass sie nicht jede enthält. 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, erhält man einen Widerspruch zu der getroffenen Annahme. 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \neg B \Rightarrow \neg A} logisch äquivalent zu $A\Rightarrow 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\Z,+)} der ganzen Zahlen sind genau die Teilmengen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m\Z} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m\geq0} .

Beweis:

Dass diese Teilmengen Untergruppen sind, ist leicht nachzuprüfen. Sei nun $U$ eine beliebige Untergruppe von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Z} . Enthält Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U} keine positive ganze Zahl, dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U=\left\{0\right\}=0\Z} . Andernfalls sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} die kleinste positive ganze Zahl in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U} . Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} irgendein Element aus $U$, wir müssen zeigen, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=mq} für eine ganze Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} ist. Dazu dividieren wir $x$ mit Rest durch $m$, also $x=mq+r$, mit $q,r$ ganzzahlig und $0\leq r<m$. Weil $r=x-mq$ in $U$ liegt, wäre Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 0<r<m} ein Widerspruch zur Wahl von $m$ als kleinstem positiven Element von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle U} , also ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r=0} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=mq} .

Literatur

• Oliver Deiser: Einführung in die Mengenlehre, Springer, 2004, ISBN 978-3540204015, Seite 238–250

Weblinks

Wikibooks: Beweis des Wohlordnungssatzes und der Äquivalenz zum Auswahlaxiom – Lern- und Lehrmaterialien