Wikipedia

Tweeplaatsige relatie: verschil tussen versies

Interactief door geschiedenis bladeren
← Oudere bewerkingNieuwere bewerking →
Verwijderde inhoud Toegevoegde inhoud
VisueelWikitekst
Madyno (overleg | bijdragen)
34.753 bewerkingen
Madyno (overleg | bijdragen)
34.753 bewerkingen
Regel 230:
{{Zie ook|Zie ook: [[Ordetheorie]]}}
 
Een belangrijke toepassing van (homogene) tweeplaatsige relaties is het beschrijven van orde door middel van orderelaties. Vier basale soorten orderelaties zijn [[partiële ordesorde]]s, [[totale ordesorde]]s, preordes[[preorde]]s en [[strikte zwakke ordes,orde]]s. maarDaarnaast bestaan er zijn ooknog andere soorten orderelaties.
 
====Partiële orde====
[[Bestand:Partiële orde.svg|thumb|Schematische weergave van een partiële orde. Merk op dat alleen de transitief-reflexieve reductie getoond wordt.]]
 
Een '''[[partiële orde]]''' is een homogene tweeplaatsige relatie die ''reflexief'', ''antisymmetrisch'' en ''transitief'' is. Partiële ordes worden vaak aangeduid met het symbool ≤.
 
Een '''[[Partiële orde|strikte partiële orde]]''' is een homogene tweeplaatsige relatie die ''asymmetrisch'' en ''transitief'' is. Asymmetrie impliceert bovendien irreflexiviteit. De strikte partiële orde kan ook gedefinieerd worden als een irreflexieve, transitieve, homogene tweeplaatsige relatie, want irreflexiviteit en transitiviteit impliceren samen asymmetrie. Strikte partiële ordes worden vaak aangeduid met het symbool <.
 
Er is een één-op-één-correspondentie tussen alle partiële ordes op een verzameling ''X'' en alle strikte partiële ordes op dezelfde verzameling ''X'', die verkregen wordt door iedere partiële orde af te beelden op zijn reflexieve reductie. Van iedere partiële orde op ''X'' is zijn reflexieve reductie namelijk een strikte partiële orde op ''X''. Verder is het zo dat de inverse van deze één-op-één-correspondentie iedere strikte partiële orde afbeeldt op zijn reflexieve afsluiting.<ref>Voor partiële ordes ≤ geldt (≤ <sup>≠</sup>) <sup>=</sup> = ≤. In het algemeen is het echter ''niet'' zo dat voor een willekeurige homogene tweeplaatsige relatie ''R'' geldt dat (''R'' <sup>≠</sup>) <sup>=</sup> = ''R''. Om precies te zijn geldt (''R'' <sup>≠</sup>) <sup>=</sup> = ''R'' desda ''R'' reflexief is.</ref> De reflexieve afsluiting van een strikte partiële orde op ''X'' is een partiële orde op ''X''. Merk op dat de inverse van het complement van een partiële orde ≤ de reflexieve reductie van ≤ is en dat de inverse van het complement van een strikte partiële orde < de reflexieve afsluiting van < is.
 
De inverse van een partiële orde ≤ wordt vaak genoteerd als ≥ en is zelf ook een partiële orde. De inverse van een strikte partiële orde < wordt vaak genoteerd als > en is zelf ook een strikte partiële orde. Het complement van een partiële orde is een strikte partiële orde en vice versa.
 
Een partiële orde waarbij ieder paar argumenten een uniek [[Bovengrens en ondergrens|infimum]] en een uniek [[Bovengrens en ondergrens|supremum]] heeft, heet een [[Tralie (wiskunde)|tralie]].
 
====Totale orde====
[[Bestand:Totale orde.svg|thumb|Schematische weergave van een totale of lineaire orde. Merk op dat alleen de transitief-reflexieve reductie getoond wordt.]]
 
Een '''[[totale orde]]''' of '''lineaire orde''' is een homogene tweeplaatsige relatie die ''antisymmetrisch'', ''transitief'' en ''totaal'' is. Totaliteit impliceert reflexiviteit, waardoor de totale orde een specifiek geval van de partiële orde is. Totale ordes worden vaak aangeduid met het symbool ≤.
 
Een '''[[Totale orde|strikte totale orde]]''' of '''strikte lineaire orde''' is een homogene tweeplaatsige relatie die ''transitief'' en ''trichotoom'' is. Trichotomie impliceert asymmetrie, waardoor de strikte totale orde een specifiek geval van de strikte partiële orde is. Strikte totale ordes worden vaak aangeduid met het symbool <.
 
Op dezelfde wijze als bij partiële ordes kan er een één-op-één-correspondentie geconstrueerd worden tussen alle totale ordes op een verzameling ''X'' en alle strikte totale ordes op dezelfde verzameling ''X''. Ook hierbij geldt dat de inverse van het complement van een totale orde ≤ de reflexieve reductie van ≤ is en dat de inverse van het complement van een strikte totale orde < de reflexieve afsluiting van < is.
 
De inverse van een totale orde ≤ wordt vaak genoteerd als ≥ en is zelf ook een totale orde. De inverse van een strikte totale orde < wordt vaak genoteerd als > en is zelf ook een strikte totale orde. Het complement van een totale orde is een strikte totale orde en vice versa.
 
====Preorde====
Een '''[[preorde]]''' is een homogene tweeplaatsige relatie die ''reflexief'' en ''transitief'' is. Preordes worden vaak aangeduid met het symbool <math>\preccurlyeq</math>. Van iedere homogene tweeplaatsige relatie ''R'' is de reflexief-transitieve afsluiting ''R'' * een preorde.
 
Een '''[[Preorde|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. Totale preordes worden vaak aangeduid met het symbool <math>\preccurlyeq</math>.
 
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 <math>\preccurlyeq</math> op ''X'' kan de equivalentierelatie ~ op ''X'' gedefinieerd worden waarvoor geldt dat voor alle ''x'', ''y'' ∈ ''X'':
:''x'' ~ ''y'' [[desda]] ''x'' <math>\preccurlyeq</math> ''y'' en ''y'' <math>\preccurlyeq</math> ''x''.
Als vervolgens een relatie ≤ op ''X'' ∕ ~ afgeleid wordt door te stellen dat voor alle ''x'', ''y'' ∈ ''X'' geldt dat
:[''x''] ≤ [''y''] desda ''x'' <math>\preccurlyeq</math> ''y'',
dan is ≤ een partiële orde op ''X'' ∕ ~. Hieruit kan vervolgens een strikte partiële orde < op ''X'' afgeleid worden, zodanig dat voor alle ''x'', ''y'' ∈ ''X'' geldt dat
:''x'' < ''y'' desda [''x''] ≤ [''y''] en [''x''] ≠ [''y''],
ofwel (de equivalente uitspraak) dat
:''x'' < ''y'' desda ''x'' <math>\preccurlyeq</math> ''y'' en niet ''x'' ~ ''y''.
 
Onder deze constructies geldt voor alle ''x'', ''y'' ∈ ''X'' dat
:''x'' <math>\preccurlyeq</math> ''y'' desda ''x'' < ''y'' of ''x'' ~ ''y''.
Dit verklaart de notatie <math>\preccurlyeq</math> 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 impliceren samen met de voorwaarde
:voor alle ''x'', ''y'' ∈ ''X'' geldt: als ''x'' ≠ ''y'' dan ''x'' ''R'' ''y'' of ''y'' ''R'' ''x'' (vgl. ''totaliteit'')
namelijk 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.
 
====Strikte zwakke orde====
Een '''[[strikte zwakke orde]]''' is een strikte partiële orde < waarvoor de relatie “noch ''x'' < ''y'', noch ''y'' < ''x''” transitief is. Deze voorwaarde wordt ook wel ''transitiviteit van onvergelijkbaarheid'' genoemd. Een alternatieve, [[logische equivalentie|equivalente]], manier om deze voorwaarde te formuleren is:
:Voor alle ''x'', ''y'' ∈ ''X'' geldt: als ''x'' < ''y'' dan geldt voor alle ''z'' ∈ ''X'' dat ''x'' < ''z'' of ''z'' < ''y'' (of beide).
 
Het complement van een strikte zwakke orde is een totale preorde en vice versa.
 
===Grafen===
Overgenomen van "https://nl.wikipedia.org/wiki/Tweeplaatsige_relatie"