Gut geordnet - Well-order

In der Mathematik ist eine Ordnung (oder Ordnung oder Ordnung ) in einer Menge S eine Gesamtordnung in S mit der Eigenschaft, dass jede nicht leere Teilmenge von S ein kleinstes Element in dieser Ordnung hat. Der Satz S zusammen mit der guten Ordnung Relation dann aufgerufen wird , gut geordneten Menge . In einigen wissenschaftlichen Artikeln und Lehrbüchern werden diese Begriffe statt wie geschrieben wellorder , wellordered und wellordering oder auch bestellen , gut geordnet und gut Bestellung .

Jeder nicht leere, gut geordnete Satz hat ein kleinstes Element. Jedes Element s einer geordneten Menge, mit Ausnahme eines möglichen größten Elements , hat einen eindeutigen Nachfolger (nächstes Element), nämlich das kleinste Element der Teilmenge aller Elemente, die größer als s sind . Neben dem kleinsten Element kann es Elemente geben, die keinen Vorgänger haben (siehe § Natürliche Zahlen unten für ein Beispiel). Ein gut geordneten Menge S enthält , die für jede Teilmenge T mit einer oberen Grenze einer wenigstens oberen Grenze , nämlich das kleinste Element der Teilmenge aller oberen Grenzen der T in S .

Wenn ≤ eine nicht strenge Ordnung ist, dann ist <eine strenge Ordnung. Eine Beziehung ist genau dann eine strenge Ordnung, wenn es sich um eine begründete strenge Gesamtordnung handelt . Die Unterscheidung zwischen strengen und nicht strengen Bohrlochordnungen wird oft ignoriert, da sie leicht untereinander konvertierbar sind.

Jeder geordnete Satz ist eindeutig isomorph zu einer eindeutigen Ordnungszahl , die als Auftragstyp des geordneten Satzes bezeichnet wird. Der Satz der Ordnung , der dem Axiom der Wahl entspricht , besagt, dass jede Menge gut geordnet sein kann. Wenn eine Menge gut geordnet ist (oder auch nur eine fundierte Beziehung zulässt ), kann die Beweismethode der transfiniten Induktion verwendet werden, um zu beweisen, dass eine gegebene Aussage für alle Elemente der Menge wahr ist.

Die Beobachtung, dass die natürlichen Zahlen durch die übliche Relation kleiner als gut geordnet sind, wird allgemein als Prinzip der guten Ordnung (für natürliche Zahlen) bezeichnet.

Ordnungszahlen

Hauptartikel: Ordnungszahl

Jeder geordnete Satz ist eindeutig isomorph zu einer eindeutigen Ordnungszahl , die als Auftragstyp des geordneten Satzes bezeichnet wird. Die Position jedes Elements innerhalb der geordneten Menge wird auch durch eine Ordnungszahl angegeben. Im Fall einer endlichen Menge entspricht die grundlegende Operation des Zählens , um die Ordnungszahl eines bestimmten Objekts zu finden oder um das Objekt mit einer bestimmten Ordnungszahl zu finden, der Zuweisung von Ordnungszahlen nacheinander zu den Objekten. Die Größe (Anzahl der Elemente, Kardinalzahl ) einer endlichen Menge entspricht dem Auftragstyp. Das Zählen im alltäglichen Sinne beginnt normalerweise bei eins, daher wird jedem Objekt die Größe des Anfangssegments mit diesem Objekt als letztem Element zugewiesen. Beachten Sie, dass diese Zahlen gemäß der isomorphen Reihenfolge eins mehr sind als die formalen Ordnungszahlen, da diese der Anzahl früherer Objekte entsprechen (was dem Zählen von Null entspricht). Für endliches n erfordert der Ausdruck " n- te Element" einer gut geordneten Menge den Kontext, um zu wissen, ob dies von Null oder Eins zählt. In einer Notation "β-te Element", in der β auch eine unendliche Ordnungszahl sein kann, zählt es typischerweise von Null an.

Für eine unendliche Menge bestimmt der Auftragstyp die Kardinalität , aber nicht umgekehrt: Gut geordnete Sätze einer bestimmten Kardinalität können viele verschiedene Auftragstypen haben. Ein einfaches Beispiel finden Sie in Abschnitt #Natürliche Zahlen . Für eine zählbar unendliche Menge ist die Menge möglicher Auftragstypen sogar unzählbar.

Beispiele und Gegenbeispiele

Natürliche Zahlen

Die Standardreihenfolge ≤ der natürlichen Zahlen ist gut geordnet und hat die zusätzliche Eigenschaft, dass jede natürliche Zahl ungleich Null einen eindeutigen Vorgänger hat.

Eine weitere gute Reihenfolge der natürlichen Zahlen ergibt sich aus der Definition, dass alle geraden Zahlen kleiner sind als alle ungeraden Zahlen, und die übliche Reihenfolge gilt innerhalb der Abend- und Gewinnchancen:

0 2 4 6 8 ... 1 3 5 7 9 ...

Dies ist eine gut geordnete Menge des Ordnungstyps ω + ω. Jedes Element hat einen Nachfolger (es gibt kein größtes Element). Zwei Elementen fehlt ein Vorgänger: 0 und 1.

Ganzzahlen

Im Gegensatz zur Standardreihenfolge ≤ der natürlichen Zahlen ist die Standardreihenfolge ≤ der ganzen Zahlen keine gute Ordnung, da beispielsweise die Menge der negativen ganzen Zahlen kein kleinstes Element enthält.

Die folgende Beziehung R ist ein Beispiel für eine gute Ordnung der ganzen Zahlen: x R y genau dann, wenn eine der folgenden Bedingungen gilt:

  1. x = 0
  2. x ist positiv und y ist negativ
  3. x und y sind beide positiv und x ≤ y
  4. x und y sind beide negativ und | x | ≤ | y |

Diese Beziehung R kann wie folgt visualisiert werden:

0 1 2 3 4 ... −1 −2 −3 ...

R ist isomorph zur Ordnungszahl ω + ω.

Eine andere Beziehung zum guten Ordnen der ganzen Zahlen ist die folgende Definition: x  ≤ z   y genau dann, wenn (| x | <| y | oder (| x | = | y | und x  ≤  y )). Diese Brunnenreihenfolge kann wie folgt visualisiert werden:

0 −1 1 −2 2 −3 3 −4 4 ...

Dies hat den Auftragstyp ω.

Reals

Die Standardreihenfolge ≤ eines reellen Intervalls ist keine gute Ordnung, da beispielsweise das offene Intervall (0, 1) ⊆ [0,1] kein kleinstes Element enthält. Aus den ZFC- Axiomen der Mengenlehre (einschließlich des Axioms der Wahl ) kann man zeigen, dass es eine gute Ordnung der Reals gibt. Auch Wacław Sierpiński hat bewiesen, dass ZF + GCH (die verallgemeinerte Kontinuumshypothese ) das Axiom der Wahl und damit eine gute Ordnung der Reals impliziert. Es kann jedoch gezeigt werden, dass die ZFC + GCH-Axiome allein nicht ausreichen, um die Existenz einer definierbaren (durch eine Formel) Well-Ordnung der Realzahlen zu beweisen. Es stimmt jedoch mit ZFC überein, dass eine definierbare Well-Ordnung der Reals existiert - zum Beispiel ist es mit ZFC konsistent, dass V = L ist , und aus ZFC + V = L folgt, dass eine bestimmte Formel die Reals gut ordnet, oder tatsächlich eine einstellen.

Eine unzählige Teilmenge der reellen Zahlen mit der Standardreihenfolge ≤ kann keine Brunnenordnung sein: Angenommen, X ist eine Teilmenge von R, die nach ≤ gut geordnet ist. Für jedes x in X sei s ( x ) der Nachfolger von x in ≤ Reihenfolge auf X (es sei denn, x ist das letzte Element von X ). Sei A = {( x , s ( x )) | x ∈ X }, deren Elemente nicht leere und disjunkte Intervalle sind. Jedes solche Intervall enthält mindestens eine rationale Zahl, so dass es eine Injektionsfunktion von A bis Q gibt . Es gibt eine Injektion von X nach A (außer möglicherweise für ein letztes Element von X, das später auf Null abgebildet werden könnte). Und es ist bekannt, dass es eine Injektion von Q in die natürlichen Zahlen gibt (die gewählt werden könnte, um ein Erreichen von Null zu vermeiden). Somit erfolgt eine Injektion von X in die natürlichen Zahlen, was bedeutet, dass X zählbar ist. Andererseits kann eine zählbar unendliche Teilmenge der Realzahlen eine gute Ordnung mit dem Standard "≤" sein oder auch nicht. Beispielsweise,

  • Die natürlichen Zahlen sind eine gute Ordnung unter der Standardreihenfolge ≤.
  • Die Menge {1 / n: n = 1,2,3, ...} hat kein kleinstes Element und ist daher keine gute Ordnung unter Standardreihenfolge ≤.

Beispiele für Brunnenbestellungen:

  • Die Menge der Zahlen {- 2 - n | 0 ≤ n <ω} hat den Ordnungstyp ω.
  • Die Menge der Zahlen {- 2 - n - 2 - m - n | 0 ≤ m , n <ω} hat den Ordnungstyp ω 2 . Der vorherige Satz ist der Satz von Grenzpunkten innerhalb des Satzes. Innerhalb der Menge reeller Zahlen, entweder mit der gewöhnlichen Topologie oder der Ordnungstopologie, ist 0 auch ein Grenzpunkt der Menge. Es ist auch ein Grenzpunkt der Menge der Grenzpunkte.
  • Die Menge der Zahlen {- 2 - n | 0 ≤ n <ω} ∪ {1} hat den Ordnungstyp ω + 1. Bei der Ordnungstopologie dieser Menge ist 1 ein Grenzpunkt der Menge. Mit der gewöhnlichen Topologie (oder äquivalent der Ordnungstopologie) der reellen Zahlen ist dies nicht der Fall.

Äquivalente Formulierungen

Wenn ein Set vollständig bestellt ist , entsprechen die folgenden Elemente einander:

  1. Das Set ist gut bestellt. Das heißt, jede nicht leere Teilmenge hat ein kleinstes Element.
  2. Die transfinite Induktion funktioniert für den gesamten bestellten Satz.
  3. Jede streng abnehmende Folge von Elementen der Menge muss nach nur endlich vielen Schritten enden (unter der Annahme des Axioms der abhängigen Wahl ).
  4. Jede Unterordnung ist isomorph zu einem Anfangssegment.

Auftragstopologie

Jeder gut geordnete Satz kann zu einem topologischen Raum gemacht werden, indem er mit der Ordnungstopologie versehen wird .

In Bezug auf diese Topologie kann es zwei Arten von Elementen geben:

  • isolierte Punkte - dies sind das Minimum und die Elemente mit einem Vorgänger.
  • Grenzpunkte - Dieser Typ tritt nicht in endlichen Mengen auf und kann in einer unendlichen Menge auftreten oder nicht. die unendlichen Mengen ohne Grenzpunkt sind die Sätze von Auftragsart ω, beispielsweise N .

Für Teilmengen können wir unterscheiden:

  • Teilmengen mit einem Maximum (dh Teilmengen, die durch sich selbst begrenzt sind); Dies kann ein isolierter Punkt oder ein Grenzpunkt der gesamten Menge sein. im letzteren Fall kann es auch ein Grenzpunkt der Teilmenge sein oder nicht.
  • Teilmengen, die für sich unbegrenzt, aber in der gesamten Menge begrenzt sind; sie haben kein Maximum, sondern ein Supremum außerhalb der Teilmenge; Wenn die Teilmenge nicht leer ist, ist dieses Supremum ein Grenzpunkt der Teilmenge und damit auch der gesamten Menge. Wenn die Teilmenge leer ist, ist dieses Supremum das Minimum der gesamten Menge.
  • Teilmengen, die in der gesamten Menge unbegrenzt sind.

Eine Teilmenge ist in der gesamten Menge genau dann kofinal, wenn sie in der gesamten Menge unbegrenzt ist oder ein Maximum aufweist, das auch das Maximum der gesamten Menge ist.

Eine gut geordnete Menge als topologischer Raum ist genau dann ein erstzählbarer Raum, wenn sie einen Ordnungstyp kleiner oder gleich ω 1 ( Omega-1 ) hat, dh genau dann, wenn die Menge zählbar ist oder den kleinsten hat unzählige Auftragsarten.

Siehe auch

Verweise

  1. ^ Feferman, S. (1964). "Einige Anwendungen der Begriffe Forcing und Generic Sets" . Fundamenta Mathematicae . 56 (3): 325–345. doi : 10.4064 / fm-56-3-325-345 .