Teilordnung (M, ≤)

Auch partielle Ordnung, Halbordnung. Achtung: manchmal einfach Ordnung genannt.

Eine endliche Menge M ist teilweise geordnet, wenn eine Relation R auf M selbst existiert, sodass die folgenden Bedingungen erfüllt sind:

Die Relation zwischen den Elementen muss

- reflexiv, z.B. a ≤ a für jedes Element a in M

- anti-symmetrisch, z.B. a ≤ b ∧ b ≤ a ⇒ a = b und

- transitiv, z.B. a ≤ b ∧ b ≤ c ⇒ a ≤ c

sein.

Darüber hinaus verlangt eine Teilordnung, dass jede daraus bildbare nichtleere Untermenge mindestens ein minimales Element aufweist.

Beispiel 1:

Die Vorfahrtsregelung im Straßenverkehr ist dem gemäß eine Teilordnung.

- reflexiv: ein Fahrzeug hat zu sich selbst Vorfahrt (wenn kein anderes Fahrzeug an der Kreuzung steht),

- anti-symmetrisch: wenn A Vorfahrt hat, dann hat B keine Vorfahrt (und umgekehrt),

- transitiv: wenn A Vorfahrt vor B hat und B vor C, dann hat auch A Vorfahrt vor C.

Beispiel 2:

Die Menge der nichtleeren Teilmengen (also die Potenzmenge ohne die Leermenge P(M)\{}) der Menge {0,1,2} ist bezüglich der Relation ⊆ halbgeordnet. Die minimalen Elemente sind {0}, {1} und {2}, allerdings ist keins von ihnen ein kleinstes Element, da z. B. {0} nicht größer (mächtiger) ist als {1} (denn {0} ist keine Teilmenge von {1}). Dagegen hat diese Menge ein größtes Element, {0,1,2}, denn alle anderen Elemente sind kleiner als dieses (sind Teilmengen davon); dies ist das einzige maximale Element der Menge.