Tweeplaatsige relatie: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
→Definitie: speciale spatiecode vervangen door spatie, gaf op sommige apparatuur rechthoekje als zijn de een niet leesbaar symbool |
idem |
||
Regel 24:
Het belangrijkste verschil tussen deze definities komt aan het licht wanneer tweeplaatsige relaties op gelijkheid getoetst worden. Neem de relaties ''R'' = ⟨''G'', ''X'', ''Y''⟩ en ''S'' = ⟨''G'', ''X'', ''Z''⟩, waarbij ''Y'' ≠ ''Z''. Het is evident dat in dit geval ''R'' ≠ ''S'', hoewel de verzameling geordende paren ''G'' in beide relaties hetzelfde is. Onder de tweede definitie zouden dezelfde relaties echter als volgt gedefinieerd worden: ''R'' = ''G'' en ''S'' = ''G'', waaruit volgt dat ''R'' = ''S''.
Regel 50 ⟶ 51:
Voor een ander voorbeeld beschrijven we eerst de verzamelingen waarover we de relatie definiëren.
:''X''
is een verzameling van vier willekeurige mensen en
:''Y''
is een verzameling van vijf objecten. Verder definiëren we
:''G''
Merk op dat alle linker leden van de paren in ''G'' uit ''X'' komen en alle rechter leden uit ''Y'' komen, waaruit volgt dat
:''G''
''B''
Als we met de relatie ''B'' het begrip ''bezitten'' willen beschrijven dan betekent ''B''(Dirk, Fiets) dat Dirk de fiets bezit en ''B''(Anna, Boek) dat Anna het boek bezit. Het eerste is volgens de door ons geconstrueerde relatie waar en het tweede niet waar. Merk op dat volgens onze relatie niemand de zon en de maan bezit, dat het boek in bezit is van zowel Christine als Dirk en dat Boris helemaal niets bezit.
Regel 64 ⟶ 65:
Zij ''R'' een tweeplaatsige relatie over ''A'' en ''B''. De volgende eigenschappen<ref>Merk op dat, omdat het ''eigenschappen'' zijn die gedefinieerd worden, de gedefinieerde woorden bijvoeglijke naamwoorden zijn. De afgeleide zelfstandige naamwoorden zouden op (klassen van) objecten in plaats van eigenschappen slaan, wat in dit geval neerkomt op subklassen van tweeplaatsige relaties. Deze zelfstandige naamwoorden (injectie, surjectie, etc.) zijn courant. De eigenschappen zijn echter fundamenteler dan de klassen van objecten, omdat de definitie van deze klassen afgeleid is van de eigenschappen.</ref> zijn nu gedefinieerd.
* Dat ''R'' '''links-volledig''' is, betekent dat voor alle ''a''
* Dat ''R'' '''rechts-volledig''' of '''[[Surjectie|surjectief]]''' is, betekent dat voor alle ''b''
* Dat ''R'' '''links-definiet''' of '''[[Injectie (wiskunde)|injectief]]''' is, betekent dat geen twee verschillende linker argumenten van ''R'' in relatie staan tot hetzelfde rechter argument van ''R''. Dat wil zeggen dat voor alle ''a''<sub>1</sub>,
* Dat ''R'' '''rechts-definiet''' of '''functioneel''' is, betekent dat geen enkel linker argument van ''R'' in relatie staat tot twee verschillende rechter argumenten van ''R''. Een andere beschrijving van dezelfde eigenschap is dat ieder linker argument van ''R'' in relatie staat tot ten hoogste één rechter argument van ''R''. Beide omschrijvingen willen zeggen dat voor alle ''a''
* Dat ''R'' '''[[Bijectie|bijectief]]''' is, betekent dat ''R'' links-volledig, rechts-volledig, links-definiet en rechts-definiet is.
Regel 78 ⟶ 79:
{{Zie ook|Zie [[Doorsnede (verzamelingenleer)|Doorsnede]] en [[Vereniging (verzamelingenleer)|Vereniging]] voor de doorsnede en de vereniging van verzamelingen in plaats van relaties.}}
Zij ''R'' en ''S'' tweeplaatsige relaties over ''A'' en ''B''. De '''doorsnede''' van ''R'' en ''S'', genoteerd als ''R''
:voor alle ''a''
De '''vereniging''' van ''R'' en ''S'', genoteerd als ''R''
:voor alle ''a''
Wanneer de definitie van ''tweeplaatsige relatie'' gebruikt wordt waarbij de relatie een verzameling geordende paren is, overeenkomstig met de grafiek van dezelfde relatie onder de andere genoemde definitie, dan zijn de doorsnede en vereniging van tweeplaatsige relaties simpelweg de doorsnede en de vereniging zoals gedefinieerd op verzamelingen in het algemeen.
Regel 90 ⟶ 91:
Zij ''R'' een tweeplaatsige relatie over ''A'' en ''B''. Het '''complement''' van ''R'', genoteerd als ''R'' <sup><font size="1">∁</font></sup> of als <span style="text-decoration: overline;">''R''</span>, is de tweeplaatsige relatie over ''A'' en ''B'' waarvoor geldt dat
:voor alle ''a''
Merk op dat voor alle tweeplaatsige relaties ''R'' geldt dat
:(''R'' <sup><font size="1">∁</font></sup>) <sup><font size="1">∁</font></sup>
===Compositie of samenstelling===
{{Zie ook|Zie ook: [[Samengestelde relatie]]}}
Zij ''R'' een tweeplaatsige relatie over ''A'' en ''B'', en ''S'' een tweeplaatsige relatie over ''B'' en ''C''. De '''compositie''' of '''samenstelling''' van ''R'' en ''S'', genoteerd als ''R''
:voor alle ''a''
Voor alle tweeplaatsige relaties ''R'' over ''A'' en ''B'', ''S'' over ''B'' en ''C'', en ''T'' over ''C'' en ''D'' geldt dat
:(''[[associativiteit]]'') (''R''
Daarom wordt meestal simpelweg ''R''
Vaak wordt de compositie van ''R'' en ''S'' genoteerd als ''S''
===Inverse of converse===
Regel 111 ⟶ 112:
Zij ''R'' een tweeplaatsige relatie over ''A'' en ''B''. De '''inverse''' of '''converse''' van ''R'', genoteerd als ''R'' <sup>−1</sup>, is de tweeplaatsige relatie over ''B'' en ''A'' waarvoor geldt dat
:voor alle ''a''
Merk op dat voor alle tweeplaatsige relaties ''R'' het volgende geldt:
* (''R'' <sup>−1</sup>) <sup>−1</sup>
* Als ''R'' links-volledig is, dan is ''R'' <sup>−1</sup> rechts-volledig.
* Als ''R'' rechts-volledig is, dan is ''R'' <sup>−1</sup> links-volledig.
Regel 125 ⟶ 126:
* De doorsnede van ''R'' en het complement van ''R'' is de lege relatie over ''A'' en ''B'':
::''R''
* De vereniging van ''R'' en het complement van ''R'' is de universele relatie over ''A'' en ''B'':
::''R''
* De inverse van het complement van ''R'' is hetzelfde als het complement van de inverse van ''R'':
::(''R'' <sup><font size="1">∁</font></sup>) <sup>−1</sup>
* De inverse van de compositie van ''R'' en ''Q'' is hetzelfde als de compositie van de inverse van ''Q'' en de inverse van ''R'':
::(''R''
* De inverse is [[distributief]] over zowel doorsnede als vereniging:
::(''R''
::(''R''
* Compositie is zowel links- als rechts-distributief over vereniging: (Merk op dat dit niet voor de doorsnede geldt.)
::''P''
::(''R''
==Een-op-een-correspondenties==
Regel 150 ⟶ 151:
Zij ''R'' een homogene tweeplaatsige relatie op ''X''.
* Dat ''R'' '''voortzettend''' is, betekent dat voor alle ''x''
* Dat ''R'' '''[[Reflexieve relatie|reflexief]]''' is, betekent dat voor alle ''x''
::(''Alternatieve definitie'') … betekent dat ''id''<sub>''X''</sub>
* Dat ''R'' '''irreflexief''' is, betekent dat er geen ''x''
* Dat ''R'' '''[[Symmetrie|symmetrisch]]''' is, betekent dat voor alle ''x'',
::(''Alternatieve definitie'') … betekent dat ''G′''
* Dat ''R'' '''asymmetrisch''' is, betekent dat er geen ''x'',
* Dat ''R'' '''antisymmetrisch''' is, betekent dat voor alle ''x'',
* Dat ''R'' '''[[transitiviteit (wiskunde)|transitief]]''' is, betekent dat voor alle ''x'',
::(''Alternatieve definitie'') … betekent dat ''G′''
* Dat ''R'' '''intransitief''' is, betekent dat er geen ''x'',
* Dat ''R'' '''[[Dichte relatie|dicht]]''' is, betekent dat voor alle ''x'',
* Dat ''R'' '''[[Euclidische relatie|Euclidisch]]''' is, betekent dat voor alle ''x'',
* Dat ''R'' '''[[Samenhangende relatie|samenhangend]]''' is, betekent dat voor alle ''x'',
<!-- Ben niet zeker van de volgende definitie: (misschien moet het de reflexief-symmetrisch-transitieve afsluiting ipv transitieve afsluiting zijn?)
* Dat ''R'' '''pad-samenhangend''' is, betekent dat voor alle ''x'',
-->
* Dat ''R'' '''[[Connex (wiskunde)|connex]]''' of '''totaal''' is, betekent dat voor alle ''x'',
* Dat ''R'' '''[[Trichotoom (wiskunde)|trichotoom]]''' is, betekent dat voor alle ''x'',
* Dat ''R'' '''[[Deterministische relatie|deterministisch]]''' is, betekent dat voor alle ''x'',
* Dat ''R'' '''[[Convergente relatie|convergent]]''' is, betekent dat voor alle ''x'',
* Dat ''R'' '''[[Convergente relatie|divergent]]''' is, betekent dat voor alle ''x'',
===Operaties op homogene tweeplaatsige relaties===
Regel 177 ⟶ 178:
{{Zie ook|Zie [[Restrictie (wiskunde)|Restrictie]] voor de restrictie van functies in plaats van relaties.}}
Zij ''R'' een homogene tweeplaatsige relatie op ''X''. Als ''Y''
:voor alle ''x'',
Informeel gesproken is een restrictie van een homogene tweeplaatsige relatie het resultaat van het inperken van zijn domein.
Regel 192 ⟶ 193:
Zij ''R'' een homogene tweeplaatsige relatie op ''X''.
* De '''reflexieve afsluiting''' van ''R'', genoteerd als ''R'' <sup>=</sup>, is de tweeplaatsige relatie ''R'' <sup>=</sup> op ''X'' waarvoor geldt dat voor alle ''x'',
* De '''reflexieve reductie''' van ''R'', genoteerd als ''R'' <sup>≠</sup>, is de tweeplaatsige relatie ''R'' <sup>≠</sup> op ''X'' waarvoor geldt dat voor alle ''x'',
* De '''[[transitieve afsluiting]]''' van ''R'', genoteerd als ''R'' <sup>+</sup>, is de kleinste transitieve tweeplaatsige relatie ''R'' <sup>+</sup> over ''X'' waarvoor geldt: als ''x'' ''R'' ''y'' dan ''x'' ''R'' <sup>+</sup> ''y''.
* De '''transitieve reductie''' van ''R'', genoteerd als ''R'' <sup>−</sup>, is de kleinste tweeplaatsige relatie over ''X'' met dezelfde transitieve afsluiting als ''R''.
* De '''reflexief-transitieve afsluiting''' van ''R'', genoteerd als ''R'' *, is de relatie (''R'' <sup>+</sup>) <sup>=</sup>
* De '''transitief-reflexieve reductie''' van ''R'' is de relatie (''R'' <sup>−</sup>) <sup>≠</sup>
===Equivalentierelaties===
Regel 206 ⟶ 207:
Een '''[[equivalentierelatie]]''' is een homogene tweeplaatsige relatie die ''reflexief'', ''symmetrisch'' en ''transitief'' is.
Gegeven een equivalentierelatie ~ op ''X'', kan voor iedere ''x''
:[''x'']
Deze verzameling wordt de '''[[Equivalentierelatie#Equivalentieklasse|equivalentieklasse]]''' van ''x'' genoemd, of ''een'' equivalentieklasse van ''X''.
Equivalentieklassen hebben de volgende eigenschappen:<ref name="EquivalentierelatiesBewijzen">Zie voor de bewijzen het hoofdartikel over dit onderwerp: ''[[Equivalentierelatie]]''.</ref>
* Voor alle ''x''
* Iedere ''x''
* Voor alle ''x'',
De verzameling
:''X'' ∕ ~
van alle equivalentieklassen van ''X'' wordt de '''[[Equivalentierelatie#Quotiëntverzameling|quotiëntverzameling]]''' van ''X'' onder ~ genoemd.
Quotiëntverzamelingen hebben de volgende eigenschappen:<ref name="EquivalentierelatiesBewijzen" />
* Iedere equivalentierelatie op ''X'' levert een unieke quotiëntverzameling op. Er zijn, met andere woorden, geen twee verschillende equivalentierelaties op ''X'' die dezelfde quotiëntverzameling van ''X'' opleveren.
* ''X'' ∕ ~ is een [[Partitie (wiskunde)|partitie]] van ''X''. Dat wil zeggen dat ieder element van ''X'' in precies een van de equivalentieklassen [''x'']
Het blijkt bovendien dat iedere partitie van ''X'' ook een quotiëntverzameling van ''X'' is onder een zekere equivalentierelatie op ''X''. Hieruit volgt, samen met de bovenstaande eigenschappen, dat er een een-op-een-correspondentie is tussen alle mogelijke partities van ''X'' en alle mogelijke equivalentierelaties op ''X''.
Regel 237 ⟶ 238:
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>
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.
Regel 261 ⟶ 262:
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 ''X'' kan de equivalentierelatie ~ op ''X'' gedefinieerd worden waarvoor geldt dat voor alle ''x'',
:''x''
Als vervolgens een relatie ≤ op ''X'' ∕ ~ afgeleid wordt door te stellen dat voor alle ''x'',
:[''x'']
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'',
:''x''
ofwel (de equivalente uitspraak) dat
:''x''
Onder deze constructies geldt voor alle ''x'',
:''x''
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 impliceren samen met de voorwaarde
:voor alle ''x'',
namelijk trichotomie, wat een strikte totale orde op zou leveren.
Regel 281 ⟶ 282:
====Strikte zwakke orde====
Een '''[[strikte zwakke orde]]''' is een strikte partiële orde < waarvoor de relatie “noch ''x''
:Voor alle ''x'',
Het complement van een strikte zwakke orde is een totale preorde en vice versa.
|