Wohlordnung

aus Wikipedia, der freien Enzyklopädie

Eine Wohlordnung auf einer Menge ist eine totale Ordnung, bei der jede nichtleere Teilmenge von ein kleinstes Element bezüglich dieser Ordnung hat, also eine totale fundierte Ordnung. Das Paar der Menge zusammen mit der Wohlordnung heißt dann eine wohlgeordnete Struktur oder unpräzise 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} eine wohlgeordnete Menge, wobei die Ordnung implizit ist. Die Begriffe stammen aus der Mengenlehre von Cantor.

Eigenschaften

In einer wohlgeordneten Struktur 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, <)} gibt es keine unendlich lange absteigende Kette, d. h. keine unendliche Folge 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 (a_i)_{i\in\N}} 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 S} , sodass für alle 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 i} gilt 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 a_{i+1} < a_i} . Unter Verwendung des Axioms der abhängigen Auswahl folgt auch die Umkehrung: Wenn es in keine unendliche absteigende Folge (bezüglich 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 {<}} ) gibt, so ist eine wohlgeordnete Struktur.

Im Kontext einer Wohlordnung gibt es die Begriffe von (direktem/unmittelbarem) Vorgänger und (direktem/unmittelbarem) Nachfolger.[Anm. 1] Für 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 a < b} heißt 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 a} der Vorgänger von und gleichwertig 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 b} der Nachfolger 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 a} , falls zwischen 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 a} und keine Elemente liegen. In einer wohlgeordneten Menge gibt es stets mindestens ein Element ohne Vorgänger, unter anderem das kleinste Element von selbst. Der Nachfolger eines Elements ist immer eindeutig bestimmt: Falls er existiert, ist er das eindeutige Minimum der Menge der Elemente, die größer sind. Es kann höchstens ein größtes Element geben, das keinen Nachfolger hat. Mehrere Elemente ohne Nachfolger sind nicht möglich. Dagegen kann es beliebig viele Elemente ohne direkten Vorgänger geben.

Wenn eine Menge wohlgeordnet ist, dann kann die Technik der transfiniten Induktion genutzt werden, um zu zeigen, dass eine gegebene Aussage für alle Elemente dieser Menge zutrifft. Die vollständige Induktion ist ein Spezialfall der transfiniten Induktion.

Der Wohlordnungssatz besagt, dass jede Menge wohlgeordnet werden kann. Unter Zugrundelegung der übrigen mengentheoretischen Axiome ist dieser Satz äquivalent zum Auswahlaxiom.

Der einzige Isomorphismus einer Wohlordnung (Ordnungsisomorphismus) auf sich selbst ist die Identität, und eine Wohlordnung ist niemals isomorph zu einem echten Anfangssegment ihrer selbst. Zwei Wohlordnungen sind entweder isomorph, oder genau eine ist isomorph zu einem echten Anfangssegment der anderen. Die jeweiligen Isomorphismen sind dann eindeutig. Betrachtet man nun die Äquivalenzklassen bezüglich Isomorphie, so gibt es in jeder einen kanonischen Vertreter, die zugehörige Ordinalzahl. Jede Wohlordnung ist also isomorph zu genau einer Ordinalzahl. Die Klasse der Ordinalzahlen selbst ist auch wohlgeordnet.[1]

Anmerkungen

  1. ↑ Manchmal werden alle Elemente, die kleiner als das betrachtete Element sind, als die Vorgänger bezeichnet, also auch die indirekten (= mittelbaren); analog für Nachfolger. Siehe Ordnungsrelation §Vorgänger und Nachfolger.
    Wiebke Petersen: Mathematische Grundlagen der Computerlinguistik – Ordnungsrelationen, 4. Foliensatz, Heinrich-Heine-Universität Düsseldorf, Institute of Language and Information, PDF: WS 2011/12 S. 93 WS 2013/14 S. 90, abgerufen am 21. April 2018.

Beispiele

Einfache Beispiele und Gegenbeispiele

Die normale Anordnung der natürlichen Zahlen ist bereits eine Wohlordnung, aber weder die normale Anordnung der ganzen Zahlen noch die der positiven reellen Zahlen ist eine Wohlordnung.

Auf einer endlichen Menge ist mit Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle x_{i}<x_{i+1}} eine Wohlordnung definiert. Gilt aber auch noch 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_n < x_1} , so gibt es einen Zyklus und es liegt keine Wohlordnung mehr vor.

Mehrere Elemente ohne Vorgänger

Die natürlichen Zahlen sollen so geordnet sein, dass jede gerade Zahl größer ist als jede ungerade Zahl. Untereinander sollen die geraden und die ungeraden Zahlen wie üblich geordnet sein, also in der folgenden Art:

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 1 < 3 < 5 < \cdots \; < \; 2 < 4 < 6 < \cdots }

Offenbar ist das eine wohlgeordnete Menge: Enthält eine Teilmenge irgendwelche ungeraden Zahlen, so ist die kleinste von ihnen auch kleinste Zahl der Teilmenge (alle geraden Zahlen sind größer); enthält sie nur gerade Zahlen, so ist die kleinste aus diesen auch die kleinste im Sinne der Wohlordnung, denn ungerade Zahlen, die kleiner wären, sind ja nicht vorhanden. Die Ordinalzahl zu dieser Wohlordnung wird üblicherweise mit Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \omega +\omega } oder 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 \omega\cdot 2} bezeichnet. Es gibt hier kein größtes Element, aber zwei Elemente ohne Vorgänger: die Eins und die Zwei.

Wohlgeordnete Klassen

Die obige Definition lässt sich wie folgt auf Klassen erweitern:

Eine wohlgeordnete Klasse ist eine Klasse 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} mit einer fundierten linearen Ordnung < auf 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} , die vorgängerklein ist. Das bedeutet, dass für alle 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 b \in S} die Klasse Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \{a\in S|a<b\}} der Vorgänger 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 b} eine Menge (d. h. keine eigentliche Klasse) ist.[2]

Literatur

  • Oliver Deiser: Einführung in die Mengenlehre, Springer, 2004, ISBN 978-3-540-20401-5, Seiten 222–230

Referenzen

  1. ↑ Thomas Jech: Set Theory. Hrsg.: Samuel Eilenberg und Hyman Bass. 1. Auflage. Academic Press Inc., 1978, ISBN 0-12-381950-4, S. 13–14 (englisch).
  2. ↑ Martin Ziegler: Vorlesung über Mengenlehre, Universität Freiburg, 1992–2014, Seite 12
Abgerufen von „https://de.wikiup.org/index.php?title=Wohlordnung&oldid=208101784“