Preorde

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Jump to search

In de ordetheorie, een onderdeel van de wiskunde, is een preorde of quasi-orde, een homogene tweeplaatsige relatie die reflexief en transitief is. Preordes worden vaak aangeduid met het symbool . Van iedere homogene tweeplaatsige relatie is de reflexief-transitieve afsluiting een preorde.

Een preorde is een afgezwakte vorm van een partiële orde, het is "bijna" een partiële orde. In een preorde is het mogelijk dat twee elementen in beide richtingen vergelijkbaar zijn. Er kunnen dus verschillende elementen en zijn, waarvoor geldt dat zowel als .

Zwakke orde[bewerken]

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.


Een partiële orde is een antisymmetrische preorde en een equivalentierelatie is een symmetrische preorde. Een totale orde is een antisymmetrische totale preorde.

Voor iedere preorde op kan de equivalentierelatie op gedefinieerd worden waarvoor geldt dat voor alle :

dan en slechts dan 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, zodanig dat voor alle geldt:

als en ,

of equivalent hiermee:

als en .

Met deze definities geldt voor alle :

an en slechts dan als of .

Dit verklaart de notatie en geeft inzicht in de wijze waarop preordes zich verhouden tot (strikte) partiële ordes. Totale preordes verhouden zich tot (strikte) totale ordes zoals preordes zich tot (strikte) partiële ordes verhouden.

De term “strikte preorde” is niet gedefinieerd. Dit zou immers zoiets als een irreflexieve en transitieve homogene tweeplaatsige relatie moeten zijn, maar irreflexiviteit en transitiviteit impliceren samen asymmetrie, wat een strikte partiële orde op zou leveren. Hetzelfde geldt voor de term “strikte totale preorde”. Irreflexiviteit en transitiviteit van een relatie impliceren samen met de voorwaarde

voor alle geldt: als dan of  (vgl. totaliteit)

namelijk een trichotomie, wat een strikte totale orde op zou leveren.

Het is uiteraard wel mogelijk om (de inverse van) het complement van een preorde te nemen. Bij een totale preorde levert dit een strikte zwakke orde op.

Zie ook[bewerken]