Preorde

Een preorde ${\displaystyle \lesssim }$  op een verzameling ${\displaystyle X}$  is een homogene tweeplaatsige relatie die reflexief en transitief is.

Voor elementen ${\displaystyle x,y,z\in X}$  geldt dus:

• reflexiviteit: ${\displaystyle x\lesssim x}$  en
• transitiviteit: als ${\displaystyle x\lesssim y}$  en ${\displaystyle y\lesssim z}$ , dan is ook ${\displaystyle x\lesssim z}$ 

Een preorde ${\displaystyle \lesssim }$  heeft daarmee een ruimere betekenis dan een partiële orde. In een preorde is het mogelijk dat voor twee verschillende elementen ${\displaystyle x}$  en ${\displaystyle y}$  geldt dat zowel ${\displaystyle x\lesssim y}$  als ${\displaystyle y\lesssim x}$ . Daarmee wordt een equivalentierelatie ${\displaystyle \sim }$  gedefinieerd door

${\displaystyle x\sim y}$  als ${\displaystyle x\lesssim y}$  en ${\displaystyle y\lesssim x}$ 

Als vervolgens een relatie ${\displaystyle \leq }$  op de equivalentieklassen ${\displaystyle X/\sim }$  gedefinieerd wordt door:

${\displaystyle [x]\leq [y]}$  als ${\displaystyle x\lesssim y}$ ,

dan is ${\displaystyle \leq }$  een partiële orde op ${\displaystyle X/\sim }$ .

Hieruit kan vervolgens een strikte partiële orde ${\displaystyle <}$  op ${\displaystyle X}$  afgeleid worden, bepaald door:

${\displaystyle x<y}$  als ${\displaystyle x\lesssim y}$  en ${\displaystyle [x]\neq [y]}$ 

Met deze definities geldt voor alle ${\displaystyle x,y\in X}$ :

${\displaystyle x\lesssim y}$  dan en slechts dan als ${\displaystyle x<y}$  of ${\displaystyle x\sim y}$ 

Dit verklaart de notatie ${\displaystyle \lesssim }$ . Een preorde op ${\displaystyle X}$  wordt dus gekarakteriseerd door een partitie van ${\displaystyle X}$  waarvan de klassen partieel geordend zijn. Als de klassen totaal geordend zijn is de preorde een totale preorde. Als de klassen singletons zijn, elk precies één element bevat, dan is de preorde een partiële orde. Als beide gelden is de preorde een totale orde. Van iedere homogene tweeplaatsige relatie ${\displaystyle R}$  is de reflexief-transitieve afsluiting ${\displaystyle R^{*}}$  een preorde.

In een preorde zijn er de volgende mogelijkheden voor de relatie tussen twee elementen ${\displaystyle a}$  en ${\displaystyle b}$ :

${\displaystyle a\lesssim b}$  en ${\displaystyle b\not \lesssim a}$ : ${\displaystyle a}$  is kleiner dan ${\displaystyle b}$ 

${\displaystyle a\lesssim b}$  en ${\displaystyle b\lesssim a}$ : ${\displaystyle a}$  en ${\displaystyle b}$  zijn equivalent, als de preorde een partiële orde is, betekent dit dat ${\displaystyle a=b}$ 

${\displaystyle a\not \lesssim b}$  en ${\displaystyle b\lesssim a}$ : ${\displaystyle b}$  is kleiner dan ${\displaystyle a}$ 

${\displaystyle a\not \lesssim b}$  en ${\displaystyle b\not \lesssim a}$ : ${\displaystyle a}$  en ${\displaystyle b}$  kunnen niet met elkaar worden vergeleken. De elementen in een totale preorde is zijn wel allemaal met elkaar te vergelijken.

Een preorde kan voorgesteld worden als een gerichte graaf waarin een gericht pad van ${\displaystyle A}$  naar ${\displaystyle B}$  bestaat als ${\displaystyle A\lesssim B}$ . Omgekeerd kan op elke gerichte graaf zonder cykels een preorde gedefinieerd worden door de relatie ${\displaystyle A\lesssim B}$  tussen de knopen ${\displaystyle A}$  en ${\displaystyle B}$ , als er een gericht pad van ${\displaystyle A}$  naar ${\displaystyle B}$  is.

Een antisymmetrische preorde is een partiële orde, antisymmetrie betekent immers

${\displaystyle (x\lesssim y\ }$  en ${\displaystyle \ y\lesssim x)\Longrightarrow x=y}$ 

Een equivalentierelatie is een symmetrische preorde en een totale orde is een antisymmetrische totale preorde.

De strikte versie van een preorde kan worden gedefinieerd als ${\displaystyle x<y}$  als ${\displaystyle x\lesssim y}$  en ${\displaystyle x\not \sim y}$ . Dit is een irreflexieve homogene tweeplaatsige relatie die transitief is. Irreflexiviteit en transitiviteit impliceren samen asymmetrie, wat een strikte partiële orde oplevert. Verschillende preordes kunnen zo dezelfde strikte partiële orde opleveren. Toegepast op een totale preorde hoeft dit geen strikte totale orde op te leveren.

Bij een totale preorde levert (de inverse van) het complement van een preorde een strikte zwakke orde op.

• Een afbeelding ${\displaystyle f}$  van een verzameling ${\displaystyle V}$  in een partieel geordende verzameling ${\displaystyle W}$  induceert een preorde met de relatie ${\displaystyle x\lesssim y}$  als ${\displaystyle f(x)\leq f(y)}$ .

Een zwakke orde of totale preorde is een homogene tweeplaatsige relatie die transitief en totaal is. Merk op dat totaliteit reflexiviteit impliceert en iedere totale preorde dus een specifiek geval van een preorde is.