(Ordnungs-) Relationen

totale Ordnung

Es sei $X$ eine (nichtleere) Menge und ``$<$'' sei eine zweistellige Relation auf $X$ (das heißt folgendes: für $x,y\in X$ gilt entweder ``$x<y$'' oder ``nicht $y<x$''). Wir nennen ``$<$'' Ordnung oder Anordnung auf $X$, falls folgendes für alle $x,y,z\in X$ gilt:

1. $\left(O_{1}\right)\;$Entweder $x<y$ oder $x=y$ oder $x<y$ (genau 1er dieser 3 Fälle)
2. Transitivität
   $\left(O_{2}\right)\;$Falls $x<y$ und $y<z$, so gilt auch $x<z$

partielle Ordnung

Eine partielle Ordnungsrelation $R$ auf einer Menge $M$ ist eine Teilmenge von $M\times M$ die die folgenden Eigenschaften besitzt:

1. Reflexivität
   $\left(x,x\right)\in R$ für alle $x\in M$
2. antisymmetrisch
   $\left(x,y\right)\in R\wedge\left(y,x\right)\in R\Rightarrow x=y$
3. transitiv
   $\left(x,y\right)\in R\wedge\left(y,z\right)\in R\Rightarrow\left(x,z\right)\in R$

Wir schreiben anstatt $\left(x,y\right)\in R$ auch $x\leq y$ und sagen, dass $R$ auf $M$ eine partielle Ordnung definiert.

• Nicht alle Elemente müssen vergleichbar sein.