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 . 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'.

DefinitieBewerken

Een preorde   op een verzameling   is een homogene tweeplaatsige relatie die reflexief en transitief is.

Voor elementen   geldt dus:

  • reflexiviteit:   en
  • transitiviteit: als   en  , dan is ook  

Een preorde   heeft daarmee een ruimere betekenis dan een partiële orde. In een preorde is het mogelijk dat voor twee verschillende elementen   en   geldt dat zowel   als  . Daarmee wordt een equivalentierelatie   gedefinieerd door

  als   en  

Als vervolgens een relatie   op de equivalentieklassen   gedefinieerd wordt door:

  als  ,

dan is   een partiële orde op  .

Hieruit kan vervolgens een strikte partiële orde   op   afgeleid worden, bepaald door:

  als   en  

Met deze definities geldt voor alle  :

  dan en slechts dan als   of  

Dit verklaart de notatie  . Een preorde op   wordt dus gekarakteriseerd door een partitie van   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   is de reflexief-transitieve afsluiting   een preorde.

EigenschapBewerken

In een preorde zijn er de volgende mogelijkheden voor de relatie tussen twee elementen   en  :

  en  :   is kleiner dan  
  en  :   en   zijn equivalent, als de preorde een partiële orde is, betekent dit dat  
  en  :   is kleiner dan  
  en  :   en   kunnen niet met elkaar worden vergeleken. De elementen in een totale preorde is zijn wel allemaal met elkaar te vergelijken.

Gerichte graafBewerken

Een preorde kan voorgesteld worden als een gerichte graaf waarin een gericht pad van   naar   bestaat als  . Omgekeerd kan op elke gerichte graaf zonder cykels een preorde gedefinieerd worden door de relatie   tussen de knopen   en  , als er een gericht pad van   naar   is.

Speciale preordesBewerken

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

  en  

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   als   en  . 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.

VoorbeeldenBewerken

  • Een afbeelding   van een verzameling   in een partieel geordende verzameling   induceert een preorde met de relatie   als  .

Zwakke ordeBewerken

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.