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.