Preorde

In de ordetheorie, een onderdeel van de wiskunde, is een preorde of quasi-orde, een relatie tussen de elementen van een verzameling die veel lijkt op een orderelatie, maar waarin elementen kunnen voorkomen die niet met elkaar vergeleken kunnen worden en elementen die van elkaar verschillen en in beide richtingen met elkaar te vergelijken zijn, wat wil zeggen dat ze op dezelfde plaats in de ordening staan. Wat de orde betreft zijn deze laatste gelijkwaardig of equivalent. De relatie is te omschrijven als 'kleiner of equivalent' in plaats van 'kleiner of gelijk'. Preordes in het algemeen en preordes die geen partiële ordes zijn, worden vaak aangeduid met het symbool ${\displaystyle \lesssim }$. Een preorde ontstaat bijvoorbeeld als een groep mensen ingedeeld wordt naar de leeftijd, in jaren. Er zullen mensen zijn die even oud zijn en van wie dus niet uitgemaakt kan worden wie eerder of later in de rangschikking komt. De relatie is in dit geval: 'jonger of even oud'.

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.