Preorde: verschil tussen versies

In de [[ordetheorie]], een onderdeel van de [[wiskunde]], is een '''preorde''' of '''quasi-orde''', een relatie tussen de [[Element (wiskunde)|elementen]] van een [[Verzameling (wiskunde)|verzameling]] die veel lijkt op een orderelatie, maar waarin elementen kunnen voorkomen die niet met elkaar vergeleken kunnen worden, of die van elkaar verschillen en in beide richtingen met elkaar te vergelijken zijn, wat wil zeggen dat zeof op dezelfde plaats in de ordening staan. Wat de orde betreft zijndeze zelaatste 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 <math>\lesssim</math>. 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'' <math>\lesssim</math> op een verzameling <math>X</math> is een [[HomogeniteitTweeplaatsige (relatie)#Homogene tweeplaatsige relaties|homogene]] [[tweeplaatsige relatie]] die [[reflexieveReflexieve relatie|reflexief]] en [[transitiviteitTransitiviteit (wiskunde)|transitief]] is.

Hieruit kan vervolgens een [[Partiële orde#Strikte partiële orde|strikte partiële orde]] <math><</math> op <math>X</math> afgeleid worden, bepaald door:

Dit verklaart de notatie <math>\lesssim</math>. Een preorde op <math>X</math> wordt dus gekarakteriseerd door een [[partitiePartitie (verzamelingenleer)|partitie]] van <math>X</math> waarvan de klassen partieel geordend zijn. Als de klassen totaal geordend zijn is de preorde een [[totale preorde]]. Als de klassen [[Singleton (wiskunde)|singletonsingletons]]s 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 <math>R</math> is de reflexief-transitieve afsluiting <math>R^*</math> een preorde.

== Eigenschap ==

:<math>a \lesssim b</math> en <math>b \not \lesssim a</math>: <math>a</math> is kleiner dan <math>b</math>

:<math>a \lesssim b</math> en <math>b \lesssim a</math>: <math>a</math> en <math>b</math> zijn equivalent, (als de preorde een partiële orde is, isbetekent dit alleen het geval alsdat <math>a=b</math>)

:<math>a \not \lesssim b</math> en <math>b \lesssim a</math>: <math>b</math> is kleiner dan <math>a</math>

:<math>a \not \lesssim b</math> en <math>b \not \lesssim a</math>: <math>a</math> en <math>b</math> zijnkunnen niet vergelijkbaarmet (nietelkaar mogelijkworden alsvergeleken. deDe preordeelementen in een totale preorde is) zijn wel allemaal met elkaar te vergelijken.

== Gerichte graaf ==

== Speciale preordes ==

Een [[AntisymmetrischeTweeplaatsige relatie#Eigenschappen van homogene tweeplaatsige relatierelaties|antisymmetrische]] preorde is een [[partiële orde]], antisymmetrie betekent immers

De strikte versie van een preorde kan worden gedefinieerd als <math>x<y</math> als <math>x \lesssim y</math> en <math>x \not \sim y</math>. Dit is een irreflexieve homogene tweeplaatsige relatie die transitief is. Irreflexiviteit en transitiviteit impliceren samen asymmetrie, wat een [[Partiële orde#Strikte partiële orde|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.

== Voorbeelden ==

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.