For faster navigation, this Iframe is preloading the Wikiwand page for Preorde.

Preorde

Uit Wikipedia, de vrije encyclopedie

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.

{{bottomLinkPreText}} {{bottomLinkText}}
Preorde
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.