Halbordnung

In der Mathematik sind Ordnungsrelationen Verallgemeinerungen der "kleiner-gleich"-Beziehung. Sie erlauben es, Elemente einer Menge miteinander zu vergleichen.

Eine Ordnungsrelation ist formal eine zweistellige Relation

auf einer Menge M mit bestimmten, unten genannten Eigenschaften.

Ist eine Menge M mit einer Ordnungsrelation R gegeben, dann nennt man das Paar (M, R) eine geordnete Menge. Statt a R b schreibt man meist (je nach Art der Ordnung) a ≤ b oder a < b.

Eine (totale) Ordnung auf einer Menge liefert eine bestimmte Anordnung der Elemente, z.B. die Anordnung der Buchstaben A bis Z im lateinischen Alphabet. Die Reihenfolge der Buchstaben ist willkürlich festgelegt, und jede andere Reihenfolge wäre ebenfalls eine Ordnung.

Arten von Ordnungsrelationen

Es folgt eine Auflistung verschiedener Arten von Ordnungsrelationen mit Beispielen. Für Definitionen der Eigenschaften siehe reflexiv und irreflexiv, antisymmetrisch, transitiv, oder den Artikel Relation (Mathematik).

• eine Quasiordnung ist reflexiv und transitiv.

  Bsp: Für a, b aus C, a R b falls |a| ≤ |b| (s. Absolutbetrag).

• eine partielle Ordnung, Halbordnung, Teilordnung oder Ordnungsrelation im engeren Sinne ist reflexiv, antisymmetrisch und transitiv.

  Bsp: Die Teilmengenrelation in einer Potenzmenge. Die Relation "komponentenweise kleinergleich" auf dem Vektorraum Rⁿ.

• eine strenge Halbordnung ist irreflexiv und transitiv.

  Bsp: Die Relation "Echte Teilmenge" in einer Potenzmenge. Die Relation "komponentenweise kleiner, aber nicht gleich" auf dem Vektorraum Rⁿ.
  

• eine Totalordnung, lineare Ordnung oder auch Kette ist eine Halbordnung, die total (im Sinne der Definition von Relation (Mathematik)) ist.

  Der Begriff linear orientiert sich an der Vorstellung, die ganze Menge in einer Kette ... R a1 R a2 R a3 R ... aufzuzählen.

  Bsp: "Kleinergleich" auf Z.

  Bsp: "Teilmenge" auf der Potenzmenge einer Menge ist nicht total, da zwar { a } und { b } Teilmengen von { a, b } sind, aber weder { a } noch { b } Teilmengen voneinander sind.

• eine strenge Totalordnung ist trichotomisch, irreflexiv und transitiv.

  Bsp: "Kleiner" auf Z.

  Bsp: Eine topologische Sortierung eines Graphen

  Die Irreflexivität folgt schon aus der Trichotomie. Damit sind die oben angegebenen Axiome zwar nicht mehr unabhängig, andererseits kann man so leichter erkennen, dass eine strenge Totalordnung eine trichotomische, strenge Halbordnung ist.

  Übrigens: Auch wenn der Begriff an sich einen anderen Schluss nahelegt - eine strenge Totalordnung ist wegen der Irreflexivität i.A. nicht total.

• eine Wohlordnung ist eine totale Ordnung, bei der jede nichtleere Teilmenge ein kleinstes Element besitzt.

  Bsp: "Kleinergleich" auf N.

  Bsp: Z mit der Ordnung 0 < 1 < -1 < 2 < -2 < 3 < -3 < ... .

  Das so genannte Wohlordnungsprinzip garantiert die Existenz einer Wohlordnung für jede Menge, z.B. auch für R. Das Wohlordnungsprinzip folgt aus dem Auswahlaxiom, ist ohne dieses aber nicht beweisbar.

• eine fundierte Ordnung ist eine Halbordnung, bei der jede nichtleere Teilmenge ein minimales Element besitzt.

  Bsp: Die Relation "Gleich oder Element von" in einer Menge von Mengen.

• eine Wohlquasiordnung ist eine Quasiordnung mit der Eigenschaft, dass es zu jeder Folge (p₁, p₂, p₃, ...) zwei natürliche Zahlen k<n gibt, sodass p_k ≤ p_n gilt.
• ein Verband ist eine Halbordnung, in der es zu je zwei Elementen immer eine kleinste obere Schranke und eine größte untere Schranke gibt.
• eine vollständige Halbordnung (engl. complete partial order, CPO) ist eine partielle Ordnung mit der Eigenschaft, dass jede aufsteigende Kette x₀ ≤ x₁ ≤ x₂ ≤ ... ein Supremum besitzt.

Beachte: Verschiedene Autoren benutzen den Begriff "Ordnung" unterschiedlich. Er kann eine Halbordnung oder eine totale Ordnung bezeichnen. Man hat also oft die Bezeichnungen

"Ordnung" (= Halbordnung) - "totale Ordnung"

oder die Bezeichnungen

"Halbordnung" - "Ordnung" (= totale Ordnung).

Minimale, maximale und andere Elemente

Sei T eine Teilmenge einer partiell geordneten Menge P. Falls es ein Element m in T gibt, das ≤ allen anderen Elementen von T ist, dann heißt m das kleinste Element von T.

Wenn m in T die Eigenschaft hat, dass es kein x in T mit x<m gibt, dann heißt m minimales Element von T. Ein kleinstes Element von T (wenn es das gibt; zB hat die Menge der ganzen Zahlen kein kleinstes Element) ist immer eindeutig bestimmt, und natürlich auch minimal. In einer Totalordnung bedeutet "kleinstes Element" und "minimales Element" dasselbe, aber in allgemeinen Halbordnungen kann eine Menge mehrere minimale Elemente haben, von denen dann keines das kleinste ist. Es kann sogar vorkommen, dass eine (unendliche) Menge T zwar ein einziges minimales Element hat, dieses aber nicht das kleinste Element der Menge ist. Siehe auch Minimum (Mathematik).

Wenn T eine Teilmenge von P ist, und p in P die Eigenschaft hat, dass für alle t in T die Beziehung p≤t gilt, dann heißt p eine untere Schranke von T. (p kann, muss aber nicht, Element von T sein.)

Wenn es eine größte untere Schranke der Menge T gibt, dann nennt man diese auch das Infimum von T.

Analog sind die Begriffe größtes Element, maximales Element, obere Schranke, Supremum definiert.

Eine Menge, die sowohl eine obere wie eine untere Schranke hat, heißt beschränkt. (Analog sind "nach oben beschränkt" und "nach unten beschränkt" definiert.)

Man nennt eine Funktion f, die eine beliebige Menge X in eine partiell oder total geordnete Menge P abbildet, beschränkt, wenn die Menge der Funktionswerte beschränkt ist, also wenn es ein p und ein q in P gibt, sodass für alle x in X gilt: p ≤ f(x) ≤ q.

See also: Halbordnung, Absoluter Betrag, Antisymmetrie, Antisymmetrisch, Auswahlaxiom, Fundierte Menge, Funktion (Mathematik), Ganze Zahlen, Graph (Graphentheorie), Komplexe Zahlen