Partielle Ordnungen

 Im Folgenden ist wieder A eine beliebige Menge. Wir betrachten zunächst Relationen auf A, die die Menge A teilweise (partiell) ordnen. Teilweise bedeutet, dass für Elemente a, b der Menge eine Ordnungsbeziehung a < b, a = b, b < a bestehen kann aber nicht muss. Es kann also Elemente a, b von A geben, die nicht miteinander vergleichbar sind.

Definition (partielle Ordnungen)

Sei A eine Menge. Eine Relation < auf A heißt eine (partielle) Ordnungsrelation (vom strikten Typ) oder kurz Ordnung auf A, falls gilt:

(P1)∀a  ∈  A  non(a < a)(Irreflexivität)
(P2)∀a, b, c  ∈  A  (a < b  ∧  b < c  →  a < c)(Transitivität)

Das geordnete Paar (A, <) nennen wir eine Ordnungsstruktur oder ebenfalls kurz Ordnung (vom strikten Typ). Für alle a, b  ∈  A setzen wir

a  ≤  b  falls  a < b  oder  a = b.

Die so definierte Relation ≤ heißt die zugeordnete nichtstrikte Ordnung auf A.

 Für eine Ordnung verwenden wir Symbole wie <, <*, ≺, ⊲, … Die zugeordneten nichtstrikten Versionen sind ≤, ≤*, ≼, ⊴, …

 Als Erstes halten wir fest:

Satz (Eigenschaften von ≤)

Sei A eine Menge, und sei < eine Ordnung auf A. Dann gilt für die zugehörige nichtstrikte Ordnung ≤:

(Q1)∀a  ∈  A  a ≤ a(Reflexivität)
(Q2)∀a, b  ∈  A  (a ≤ b  ∧  b ≤ a  →  a = b)(Antisymmetrie)
(Q3)∀a, b, c  ∈  A  (a ≤ b  ∧  b ≤ c  →  a ≤ c)(Transitivität)

 Eine Relation ≤ auf A mit Eigenschaften die (Q1), (Q2) und (Q3) nennen wir eine (nichtstrikte partielle) Ordnung auf A. Gegeben ≤ setzen wir für alle a, b  ∈  A:

a  <  b  falls  a ≤ b  und  a ≠ b.(zugeordnete strikte Ordnung)

Dies definiert eine strikte Ordnung auf A, deren zugeordnete nichtstrikte Ordnung wieder ≤ ist. Kurz:

Wir haben stets zwei partielle Ordnungen < und ≤. Die strikte Version erfüllt (P1) und (P2), die nichtstrikte (Q1), (Q2) und (Q3).

 Die Aussagen (P1), (P2) bzw. (Q1), (Q2), (Q3) nennen wir auch die Axiome einer partiellen Ordnung.

 Ob dem Typ < oder dem Typ ≤ der Vorzug gegeben wird, ist Geschmackssache und kann kontextabhängig immer wieder neu entschieden werden. Die strikte Version hat den Vorteil, dass nur zwei Aussagen zu beweisen sind, wenn wir zeigen wollen, dass eine Relation eine partielle Ordnung ist.

Beispiele

(1)

Die üblichen Relationen < auf ℕ, ℤ, ℚ und ℝ sind Ordnungen.

(2)

Sei A eine beliebige Menge. Dann ist die Inklusion (Teilmengenrelation) ⊆ eine (nichtstrikte) Ordnung auf der Potenzmenge

℘(A)  =  { B | B ⊆ A }

von A. Die strikte Version ist die echte Inklusion ⊂ auf ℘(A).

(3)

Die Teilbarkeitsrelation ist eine partielle Ordnung auf den natürlichen Zahlen (vom nichtstrikten Typ), d. h. die Setzung

a ≤ b  falls  a ist ein Teiler von b

definiert eine Ordnung auf ℕ. Dagegen ist die Teilbarkeitsrelation keine Ordnung auf ℤ, denn in ℤ gilt zum Beispiel 1 | −1 und −1 | 1, aber 1 ≠ −1, sodass die Antisymmetrie verletzt ist.

(4)

Die Teilbarkeitsrelation auf ℤ gibt Anlass zur Einführung einer Äquivalenzrelation: Setzen wir für a, b  ∈  ℤ

a ≡  b  falls  |a| = |b|,

so erhalten wir durch dieses „Absehen vom Vorzeichen“ eine Äquivalenzrelation auf ℤ mit den Äquivalenzklassen [ a ] = { a, −a } für alle a  ∈  ℤ. Diese Klassen können wir nun durch die Setzung

[ a ]  ≤  [ b ]  falls  a ist ein Teiler von b

partiell ordnen. Die Relation ≤ ist eine Ordnung auf der Faktorisierung ℤ/≡ .

(5)

Sei S die Menge aller endlichen 0-1-Folgen,

S  =  { ( ), (0), (1), (0, 0), (0, 1), (1, 0), (1, 1), …},

wobei ( ) die leere Folge ist. Wir schreiben kurz a1…an statt (a1, …, an). Weiter nennen wir eine Folge s = a1…an ein Anfangsstück einer Folge t = b1…bm, falls n ≤ m und ai = bi für i = 1, …, n gilt. Ist zudem s ≠ t, so heißt s ein echtes Anfangsstück von t. Wir setzen nun für alle s, t  ∈  S:

s ⊲ t  falls  s ist ein echtes Anfangsstück von t.

Dann ist ⊲ eine Ordnung auf S. Es gilt zum Beispiel

001 ⊲ 001110,  nicht(001 ⊲ 001),  001 ⊴ 001,  nicht(101 ⊲ 10).

Die leere Folge ist Anfangsstück jeder Folge, d. h. ( ) ⊴ t für alle t  ∈  S.

(6)

Sei G = (E, K) ein Baum. Wir zeichnen ein e  ∈  E als Wurzel aus, sodass eine Stufung des Baumes entsteht. Nun setzen wir für alle a, b  ∈  E:

a  <  b  falls  „b liegt im Wurzelbaum über a“,

was genauer bedeutet: „a ≠ b und der Weg von der Wurzel e nach b besucht die Ecke a“. Die Relation < ist eine Ordnung auf E.

(7)

Sei G = (E, K) ein gerichteter Graph ohne Kreise. Wir setzen für alle a, b  ∈  E:

a ≤ b  falls  es gibt einen (gerichteten) Weg von a nach b in G.

Dann ist ≤ eine Ordnung auf E. Die Kreisfreiheit wird für die Antisymmetrie benötigt.