title: Preorde
text: 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'.
  
  Definitie 
  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.
  
  Eigenschap 
  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 graaf 
  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 preordes 
  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.
  
  Voorbeelden 
   Een afbeelding  van een verzameling  in een partieel geordende verzameling  induceert een preorde met de relatie  als .
  
  Zwakke orde 
  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.
  
  Ordetheorie