Tweeplaatsige relatie: verschil tussen versies

Verwijderde inhoud Toegevoegde inhoud
Madyno (overleg | bijdragen)
Bewerkingen Madyno teruggedraaid
Regel 3:
In de [[wiskunde]] koppelt een '''tweeplaatsige relatie''' of '''binaire relatie''' [[Element (wiskunde)|elementen]] uit een [[Verzameling (wiskunde)|verzameling]] aan elementen uit een andere (of dezelfde) verzameling. Een tweeplaatsige relatie is een specifiek geval van een [[Relatie (wiskunde)|relatie]], namelijk een relatie met een [[Plaatsigheid|plaatsigheid of ariteit]] van 2. Anders geformuleerd is een tweeplaatsige relatie de wiskundige beschrijving van het al dan niet bestaan van een zeker verband tussen twee objecten.
 
Tweeplaatsige relaties worden vaak simpelweg "relaties"“relaties” genoemd. Historisch gezien werden met "relaties"“relaties” oorspronkelijk ook enkel tweeplaatsige relaties aangeduid. Later is het begrip uitgebreid. Zie het artikel ''[[Relatie (wiskunde)#Geschiedenis en achtergrond|Relatie]]'' voor meer over de oorsprong en de geschiedenis van het begrip.
 
==Inleiding==
<!--N.B. De volgende alinea is bedoeld als informele inleiding voor leken. Wiskundige terminologie wordt vermeden en termen als "koppelen“koppelen aan"aan” worden informeel bedoeld.-->
Een intuïtief alledaags voorbeeld van een tweeplaatsige relatie is het begrip ''bezitten''. De tweeplaatsige relatie ''bezitten'' koppelt mensen aan objecten, oftewel elementen uit de verzameling van alle mensen aan elementen uit de verzameling van alle objecten. De koning wordt door deze relatie aan de kroon gekoppeld en als Dirk en Anna samen een huis gekocht hebben, dan worden zij beiden aan dat huis gekoppeld. Niemand is aan de zon of de maan gekoppeld en mensen die niets bezitten worden door de relatie ''bezitten'' nergens aan gekoppeld.
 
<!--N.B. De volgende alinea is bedoeld als informele inleiding voor leken. Wiskundige terminologie wordt vermeden en termen als "koppelen“koppelen aan"aan” worden informeel bedoeld.-->
Een voorbeeld van een tweeplaatsige relatie die elementen uit een verzameling koppelt aan elementen uit dezelfde verzameling is de relatie ''houden van'', die mensen aan mensen koppelt. Deze relatie koppelt personen die van elkaar houden aan elkaar. Iets preciezer geformuleerd koppelt ''houden van'' persoon ''X'' aan persoon ''Y'' indien (en enkel indien) persoon ''X'' van persoon ''Y'' houdt. Aldus wordt [[Die Leiden des jungen Werthers|Werther]] bijvoorbeeld aan Charlotte gekoppeld, maar Charlotte niet aan Werther. Werther houdt, met andere woorden, van Charlotte, maar Charlotte houdt niet van Werther. De koppeling is in zekere zin dus gericht. Er zijn ook paren die wel in beide richtingen aan elkaar gekoppeld zijn, zoals [[Romeo en Julia]]. [[Giacomo Casanova|Casanova]] is een voorbeeld van iemand die aan vele personen gekoppeld is (en aan wie vele personen gekoppeld zijn) en het is voorstelbaar dat er mensen zijn die aan niemand gekoppeld zijn. [[Narcissus (mythologie)|Narcissus]], ten slotte, is iemand die aan zichzelf gekoppeld is.
 
Regel 15:
 
==Definitie==
Een tweeplaatsige relatie ''R'' is formeel gedefinieerd als een 3-[[tupel]] (''G'',&thinsp;''A'',&thinsp;''B'') waarbij ''A'' en ''B'' willekeurige verzamelingen zijn en
:''G'' ⊆ ''A'' × ''B''.
Deze voorwaarde betekent dat G een [[deelverzameling]] is van het [[cartesischCartesisch product]] van ''A'' en ''B'':.
:<math>G\subseteq A\times B</math>
 
De volgorde van de leden van het 3-tupel in de definitie kan variëren. Soms wordt een tweeplaatsige relatie bijvoorbeeld gedefinieerd als het 3-tupel (''A'',&thinsp;''B'',&thinsp;''G'') in plaats van (''G'',&thinsp;''A'',&thinsp;''B'').
 
Soms wordt de tweeplaatsige relatie simpelweg gedefinieerd als een verzameling [[Koppel (wiskunde)|geordende paren]], overeenkomstig met de ''G'' uit de eerste definitie. Uit welke verzamelingen de leden van de geordende paren komen, moet in dat geval expliciet genoemd worden of uit de context blijken. Strikt genomen wordt in dit geval niet het begrip ''tweeplaatsige relatie'' gedefinieerd, maar het begrip ''tweeplaatsige relatie over'' … ''en'' …, omdat een verzameling paren enkel een tweeplaatsige relatie is in de context van de verzamelingen waaruit de leden van de paren komen.<ref>Ook eigenschappen als links- en rechts-volledigheid (zie ''[[#Eigenschappen van tweeplaatsige relaties|Eigenschappen van tweeplaatsige relaties]]'') zijn enkel te definiëren in deze context.</ref> De verzameling { ⟨1, 2⟩, ⟨2, 3⟩ } is bijvoorbeeld wel een tweeplaatsige relatie over '''''[[Natuurlijke getallen|N]]''''', maar niet over de verzameling van alle meetkundige figuren. Een verzameling paren is, met andere woorden, niet een tweeplaatsige relatie zonder meer.
Ook wordt een tweeplaatsige relatie tussen de verzamelingen ''A'' en ''B'' simpelweg gedefinieerd als een verzameling [[Koppel (wiskunde)|geordende paren]] met het eerste element uit ''A'' en het tweede element uit ''B'', overeenkomstig met de ''G'' uit de eerste definitie.
 
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''.
 
In sommige systemen van de axiomatische [[verzamelingenleer]] worden relaties gedefinieerd op [[Klasse (verzamelingenleer)|klassen]] in plaats van verzamelingen. Deze aanpassing is onder andere nodig om de begrippen ''is een element van'' en ''is een deelverzameling van'' te kunnen beschrijven, zonder dat dit tot de [[Russellparadox|Russell-paradox]] leidt.
 
===Terminologie===
Als ''R''&nbsp;=&nbsp;( ⟨''G'',&thinsp;''A'',&thinsp;''B'') een tweeplaatsige relatie is, dan wordt ''G'' de '''[[Grafiek (wiskunde)|grafiek]]''' van ''R'' genoemd. ''A'' wordt het '''[[Domein (wiskunde)|domein]]''' van ''R'' genoemd en ''B'' wordt het '''[[codomein]]''' van ''R'' genoemd. Men zegt ook dat ''R'' een relatie over (of tussen)''A'' en ''B'' is. Van een tweeplaatsige relatie ''R''&nbsp;=&nbsp;( ⟨''G'',&thinsp;''A'',&thinsp;''A''), waarbij zowel het domein als het codomein de verzameling ''A'' is, wordt gezegd dat ''R'' een tweeplaatsige relatie over ''A'' is, of dat ''R'' een tweeplaatsige relatie op ''A'' is.
 
Als (''a'',&thinsp;''b'')&nbsp;∈&nbsp;⟩ ∈ ''G'', dan worden ''a'' en ''b'' '''[[Argument (wiskunde)|argumenten]]''' van ''R'' genoemd. Daarbij is ''a'' een ''linker argument'' en ''b'' een ''rechter argument''. Verder zegt men in dit geval dat ''a'' '''in''' ''R''-'''relatie staat tot''' ''b''. Als uit de context duidelijk is welke relatie bedoeld wordt dan zegt men ook simpelweg dat ''a'' in relatie tot ''b'' staat. Wanneer de definitie gebruikt wordt waarbij een tweeplaatsige relatie een verzameling geordende paren is, dan zegt men dat ''a'' in relatie tot ''b'' staat als (''a'',&thinsp;''b'')&nbsp;∈&nbsp;⟩ ∈ ''R''.
 
De '''lege relatie''' over ''A'' en ''B'' is de tweeplaatsige relatie over ''A'' en ''B'' waarvan de grafiek de [[lege verzameling]] is. Als ''R'' de lege relatie over ''A'' en ''B'' is, dan geldt dat er geen ''a''&nbsp;∈&nbsp; ∈ ''A'' en ''b''&nbsp;∈&nbsp; ∈ ''B'' zijn zodanig dat ''a'' in R-relatie staat tot ''b''.
 
De '''universele relatie''' over ''A'' en ''B'' is de tweeplaatsige relatie waarvan de grafiek het cartesischCartesisch product van ''A'' en ''B'' is. Als ''R'' de universele relatie over ''A'' en ''B'' is, dan geldt voor alle ''a''&nbsp;∈&nbsp; ∈ ''A'' en ''b''&nbsp;∈&nbsp; ∈ ''B'' dat ''a'' in R-relatie staat tot ''b''.
 
===Notatie===
De uitspraak "''a'' staat in ''R''-relatie tot ''b''", dus <math>(a,b)\in G</math>, wordt op verschillende manieren genoteerd:
 
* (''functienotatie'')&ensp;''R''(''a'',&thinsp;''b'')
* (''infixnotatie'')&ensp;''a''&thinsp;''R''&thinsp;''b''
* (''[[Prefix- en suffixnotatie|Poolse notatie]]'')&ensp;''R''&thinsp;''a''&thinsp;''b''
 
De functienotatie komt overeen met de [[Indicatorfunctie|karakteristieke functie]] van de grafiek van ''R''.
* (''functienotatie'')&ensp;''R''(''a'',&thinsp;''b'')
* (''infixnotatie'')&ensp;''a''&thinsp;''R''&thinsp;''b''
* (''[[Prefix- en suffixnotatie|Poolse notatie]]'')&ensp;''R''&thinsp;''a''&thinsp;''b''
 
==Voorbeelden==
Een voorbeeld van een tweeplaatsige relatie over de verzameling van alle mensen is ''houden van''. Wanneer we deze relatie aanduiden met de letter ''L'' (van liefde) dan betekent ''L''(Romeo,&thinsp;Julia Julia) dat Romeo van Julia houdt. ''L''(Julia,&thinsp;Romeo Romeo) zou betekenen dat Julia van Romeo houdt.<ref>Merk op dat ''houden van'' strikt genomen geen tweeplaatsige relatie is (in de wiskundige zin van het woord), maar een niet-wiskundig begrip dat met een tweeplaatsige relatie beschreven kan worden. De genoemde wiskundige relatie ''L'' is bedoeld een beschrijving te zijn van het alledaagse begrip ''houden van''.</ref>
 
Voor een ander voorbeeld beschrijven we eerst de verzamelingen waarover we de relatie definiëren.
:''X'' = { Anna, Boris, Christine, Dirk }
:''X''&nbsp;=&nbsp;{&nbsp;Anna,&nbsp;Boris,&nbsp;Christine,&nbsp;Dirk&nbsp;}
is een verzameling van vier willekeurige mensen en
:''Y'' = { Boek, Bal, Fiets, Zon, Maan }
:''Y''&nbsp;=&nbsp;{&nbsp;Boek,&nbsp;Bal,&nbsp;Fiets,&nbsp;Zon,&nbsp;Maan&nbsp;}
is een verzameling van vijf objecten. Verder definiëren we
:''G'' = { ⟨Anna, Bal⟩, ⟨Christine, Boek⟩, ⟨Dirk, Boek⟩, ⟨Dirk, Fiets⟩ }.
:''G''&nbsp;=&nbsp;{&nbsp;(Anna,&thinsp;Bal),&nbsp;(Christine,&thinsp;Boek),&nbsp;(Dirk,&thinsp;Boek),&nbsp;(Dirk,&thinsp;Fiets)&nbsp;}.
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''&nbsp;⊆&nbsp; ⊆ ''X''&nbsp;×&nbsp; × ''Y''.
''B''&nbsp;=&nbsp;( ⟨''G'',&thinsp;''X'',&thinsp;''Y'') is dus een tweeplaatsige relatie over ''X'' en ''Y''.
 
Als we met de relatie ''B'' het begrip ''bezitten'' willen beschrijven dan betekent ''B''(Dirk,&thinsp;Fiets Fiets) dat Dirk de fiets bezit en ''B''(Anna,&thinsp;Boek 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.
 
==Eigenschappen van tweeplaatsige relaties==
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''&nbsp;∈&nbsp; ∈ ''A'' er een ''b''&nbsp;∈&nbsp; ∈ ''B'' is, zodanig dat ''a''&thinsp;''R''&thinsp;''b''.
* Dat ''R'' '''rechts-volledig''' of '''[[Surjectie|surjectief]]''' is, betekent dat voor alle ''b''&nbsp;∈&nbsp; ∈ ''B'' er een ''a''&nbsp;∈&nbsp; ∈ ''A'' is, zodanig dat ''a''&thinsp;''R''&thinsp;''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>, ''a''<sub>2</sub>&nbsp;∈&nbsp; ∈ ''A'' en ''b''&nbsp;∈&nbsp; ∈ ''B'' geldt: als ''a''<sub>1</sub>&thinsp;''R''&thinsp;''b'' en ''a''<sub>2</sub>&thinsp;''R''&thinsp;''b'' dan ''a''<sub>1</sub>&nbsp;=&nbsp;''a''<sub>2</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''&nbsp;∈&nbsp; ∈ ''A'' en ''b''<sub>1</sub>, ''b''<sub>2</sub>&nbsp;∈&nbsp; ∈ ''B'' geldt: als ''a''&thinsp;''R''&thinsp;''b''<sub>1</sub> en ''a''&thinsp;''R''&thinsp;''b''<sub>2</sub> dan ''b''<sub>1</sub>&nbsp;=&nbsp;''b''<sub>2</sub>.
* Dat ''R'' '''[[Bijectie|bijectief]]''' is, betekent dat ''R'' links-volledig, rechts-volledig, links-definiet en rechts-definiet is.
 
Een functionele tweeplaatsige relatie wordt een ''[[Afbeelding (wiskunde)|afbeelding]]'' genoemd. Een afbeelding waarvan het het codomein een [[Lichaam_(Ned)_/_Veld_(Be)|lichaam]] (ook wel ''veld'') is, is een ''[[Functie (wiskunde)|functie]]''.<ref>Soms worden de termen "functie"“functie” en "afbeelding"“afbeelding” ook op andere wijzen gebruikt. Zie de betreffende artikelen voor een uitgebreidere beschrijving van de verschillende manieren waarop deze begrippen gebruikt worden.</ref>
 
Een tweeplaatsige relatie die links- en rechts-volledig is wordt een ''correspondentierelatie'' genoemd. De combinatie van functionaliteit en injectiviteit wordt ''een-eenduidigheid'' genoemd. Een een-eenduidige relatie heet ook wel een ''een-op-een-relatie''. Een bijectieve tweeplaatsige relatie wordt een ''een-op-een-correspondentie'' genoemd. Soms wordt "correspondentierelatie"“correspondentierelatie” echter als synoniem voor "(tweeplaatsige) relatie"relatie” gebruikt en het onderscheid tussen ''een-op-een-relatie'' en ''een-op-een-correspondentie'' wordt ook niet altijd gemaakt. Wanneer dit laatste niet het geval is dan moet uit de context blijken of met beide begrippen een bijectieve tweeplaatsige relatie bedoeld wordt, of een functionele en injectieve tweeplaatsige relatie.
 
==Operaties op tweeplaatsige relaties==
Regel 72 ⟶ 77:
{{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''&thinsp;∩&thinsp; ∩ ''S'', is de tweeplaatsige relatie over ''A'' en ''B'' waarvoor geldt dat
:voor alle ''a''&nbsp;∈&nbsp; ∈ ''A'' en ''b''&nbsp;∈&nbsp; ∈ ''B'' geldt: ''a''&thinsp;(''R''&thinsp;∩&thinsp; ∩ ''S'')&thinsp;''b'' [[desda]] ''a''&thinsp;''R''&thinsp;''b'' en ''a''&thinsp;''S''&thinsp;''b''.
 
De '''vereniging''' van ''R'' en ''S'', genoteerd als ''R''&thinsp;∪&thinsp; ∪ ''S'', is de tweeplaatsige relatie over ''A'' en ''B'' waarvoor geldt dat
:voor alle ''a''&nbsp;∈&nbsp; ∈ ''A'' en ''b''&nbsp;∈&nbsp; ∈ ''B'' geldt: ''a''&thinsp;(''R''&thinsp;∪&thinsp; ∪ ''S'')&thinsp;''b'' desda ''a''&thinsp;''R''&thinsp;''b'' of ''a''&thinsp;''S''&thinsp;''b'' (of beide).
 
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 83 ⟶ 88:
{{Zie ook|Zie [[Complement (verzamelingenleer)|Complement]] voor het complement van verzamelingen in plaats van relaties.}}
 
Zij ''R'' een tweeplaatsige relatie over ''A'' en ''B''. Het '''complement''' van ''R'', genoteerd als ''R''&thinsp;<sup>∁</sup> of als <span style="text-decoration: overline;">''R''</span>, is de tweeplaatsige relatie over ''A'' en ''B'' waarvoor geldt dat
:voor alle ''a''&nbsp;∈&nbsp; ∈ ''A'' en ''b''&nbsp;∈&nbsp; ∈ ''B'' geldt: ''a''&thinsp;''R''&thinsp;<sup>∁</sup>&thinsp;''b'' desda niet ''a''&thinsp;''R''&thinsp;''b''.
 
Merk op dat voor alle tweeplaatsige relaties ''R'' geldt dat
:(''R''&thinsp;<sup>∁</sup>)&thinsp;<sup>∁</sup>&nbsp;=&nbsp;''R''.
 
===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''&thinsp;∘&thinsp; ∘ ''S'', is de tweeplaatsige relatie over ''A'' en ''C'' waarvoor geldt dat
:voor alle ''a''&nbsp;∈&nbsp; ∈ ''A'' en ''c''&nbsp;∈&nbsp; ∈ ''C'' geldt: ''a''&thinsp;(''R''&thinsp;∘&thinsp; ∘ ''S'')&thinsp;''c'' desda er een ''b''&nbsp;∈&nbsp; ∈ ''B'' is zodanig dat ''a''&thinsp;''R''&thinsp;''b'' en ''b''&thinsp;''S''&thinsp;''c''.
 
Voor alle tweeplaatsige relaties ''R'' over ''A'' en ''B'', ''S'' over ''B'' en ''C'', en ''T'' over ''C'' en ''D'' geldt dat
:(''[[associativiteit]]'')&ensp;(''R''&thinsp;∘&thinsp; ∘ ''S'')&thinsp;∘&thinsp; ∘ ''T''&nbsp;=&nbsp;''R''&thinsp;∘&thinsp; ∘ (''S''&thinsp;∘&thinsp; ∘ ''T'').
Daarom wordt meestal simpelweg ''R''&thinsp;∘&thinsp; ∘ ''S''&thinsp;∘&thinsp; ∘ ''T'' geschreven in plaats van (''R''&thinsp;∘&thinsp; ∘ ''S'')&thinsp;∘&thinsp; ∘ ''T'' of ''R''&thinsp;∘&thinsp; ∘ (''S''&thinsp;∘&thinsp; ∘ ''T'').
 
Vaak wordt de compositie van ''R'' en ''S'' genoteerd als ''S''&thinsp;∘&thinsp; ∘ ''R'' in plaats van ''R''&thinsp;∘&thinsp; ∘ ''S'', zodat de notatie in overeenstemming is met de notatie voor [[functie-compositie]]. Deze keuze doet recht aan het inzicht dat compositie van tweeplaatsige relaties en compositie van functies hetzelfde inhouden, omdat functies bijzondere gevallen van tweeplaatsige relaties zijn.
 
===Inverse of converse===
{{Zie ook|Zie ook: [[Inverse]]}}
 
Zij ''R'' een tweeplaatsige relatie over ''A'' en ''B''. De '''inverse''' of '''converse''' van ''R'', genoteerd als ''R''&thinsp;<sup>−1</sup>, is de tweeplaatsige relatie over ''B'' en ''A'' waarvoor geldt dat
:voor alle ''a''&nbsp;∈&nbsp; ∈ ''A'' en ''b''&nbsp;∈&nbsp; ∈ ''B'' geldt: ''b''&thinsp;''R''&thinsp;<sup>−1</sup>&thinsp;''a'' desda ''a''&thinsp;''R''&thinsp;''b''.
 
Merk op dat voor alle tweeplaatsige relaties ''R'' het volgende geldt:
* (''R''&thinsp;<sup>−1</sup>)&thinsp;<sup>−1</sup>&nbsp;=&nbsp;''R''.
* Als ''R'' links-volledig is, dan is ''R''&thinsp;<sup>−1</sup> rechts-volledig.
* Als ''R'' rechts-volledig is, dan is ''R''&thinsp;<sup>−1</sup> links-volledig.
* Als ''R'' links-definiet is, dan is ''R''&thinsp;<sup>−1</sup> rechts-definiet.
* Als ''R'' rechts-definiet is, dan is ''R''&thinsp;<sup>−1</sup> links-definiet.
* Als ''R'' bijectief is, dan is ''R''&thinsp;<sup>−1</sup> ook bijectief.
 
===Eigenschappen van deze operaties===
Regel 119 ⟶ 124:
 
* De doorsnede van ''R'' en het complement van ''R'' is de lege relatie over ''A'' en ''B'':
::''R''&thinsp;∩&thinsp; ∩ ''R''&thinsp;<sup>∁</sup>&nbsp;=&nbsp;(∅ ⟨∅,&thinsp;''A'',&thinsp;''B'').
* De vereniging van ''R'' en het complement van ''R'' is de universele relatie over ''A'' en ''B'':
::''R''&thinsp;∪&thinsp; ∪ ''R''&thinsp;<sup>∁</sup>&nbsp;=&nbsp;( ⟨''A''&thinsp;×&thinsp; × ''B'',&thinsp;''A'',&thinsp;''B'').
* De inverse van het complement van ''R'' is hetzelfde als het complement van de inverse van ''R'':
::(''R''&thinsp;<sup>∁</sup>)&thinsp;<sup>−1</sup>&nbsp;=&nbsp;(''R''&thinsp;<sup>−1</sup>)&thinsp;<sup>∁</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''&thinsp;∘&thinsp; ∘ ''Q'')&thinsp;<sup>−1</sup>&nbsp;=&nbsp;''Q''&thinsp;<sup>−1</sup>&thinsp;∘&thinsp; ∘ ''R''&thinsp;<sup>−1</sup>.
* De inverse is [[distributief]] over zowel doorsnede als vereniging:
::(''R''&thinsp;∩&thinsp; ∩ ''S'')&thinsp;<sup>−1</sup>&nbsp;=&nbsp;''R''&thinsp;<sup>−1</sup>&thinsp;∩&thinsp; ∩ ''S''&thinsp;<sup>−1</sup>,
::(''R''&thinsp;∪&thinsp; ∪ ''S'')&thinsp;<sup>−1</sup>&nbsp;=&nbsp;''R''&thinsp;<sup>−1</sup>&thinsp;∪&thinsp; ∪ ''S''&thinsp;<sup>−1</sup>.
* Compositie is zowel links- als rechts-distributief over vereniging: (Merk op dat dit niet voor de doorsnede geldt.)
::''P''&thinsp;∘&thinsp; ∘ (''R''&thinsp;∪&thinsp; ∪ ''S'')&nbsp;=&nbsp;(''P''&thinsp;∘&thinsp; ∘ ''R'')&thinsp;∪&thinsp; ∪ (''P''&thinsp;∘&thinsp; ∘ ''S''),
::(''R''&thinsp;∪&thinsp; ∪ ''S'')&thinsp;∘&thinsp; ∘ ''Q''&nbsp;=&nbsp;(''R''&thinsp;∘&thinsp; ∘ ''Q'')&thinsp;∪&thinsp; ∪ (''S''&thinsp;∘&thinsp; ∘ ''Q'').
 
==Een-op-een-correspondenties==
Regel 139 ⟶ 144:
 
==Homogene tweeplaatsige relaties==
In het algemeen is een homogene relatie of endorelatie een relatie waarvan alle domeinen door één en dezelfde verzameling uitgemaakt worden. Een '''homegene''' ''tweeplaatsige'' relatie of tweeplaatsige '''endorelatie''' is dan ook een tweeplaatsige relatie waarvan het domein en het codomein dezelfde verzameling zijn. Als ''R'' een homogene tweeplaatsige relatie over ''X'' is, dan wordt ''R'' soms gedefinieerd als het het tupel (''G'',&thinsp;''X'') in plaats van het 3-tupel (''G'',&thinsp;''X'',&thinsp;''X''). Deze wijze van definiëren is bijvoorbeeld gebruikelijk in de [[grafentheorie]].
 
===Eigenschappen van homogene tweeplaatsige relaties===
Zij ''R'' een homogene tweeplaatsige relatie op ''X''.
 
* Dat ''R'' '''voortzettend''' is, betekent dat voor alle ''x''&nbsp;∈&nbsp; ∈ ''X'' er een ''y''&nbsp;∈&nbsp; ∈ ''X'' is zodanig dat ''x''&thinsp;''R''&thinsp;''y''.
* Dat ''R'' '''[[Reflexieve relatie|reflexief]]''' is, betekent dat voor alle ''x''&nbsp;∈&nbsp; ∈ ''X'' geldt dat ''x''&thinsp;''R''&thinsp;''x''.
::(''AlternatiefAlternatieve definitie'': ...) … betekent dat ''id''<sub>''X''</sub>&nbsp;⊆&nbsp; ⊆ ''G'', waarbij ''G'' de grafiek van ''R'' is en ''id''<sub>''X''</sub> de [[Identiteitsfunctie|identiteitsafbeelding]] van ''X''.
* Dat ''R'' '''irreflexief''' is, betekent dat er geen ''x''&nbsp;∈&nbsp; ∈ ''X'' is zodanig dat ''x''&thinsp;''R''&thinsp;''x''.
* Dat ''R'' '''[[Symmetrie|symmetrisch]]''' is, betekent dat voor alle ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' geldt: als ''x''&thinsp;''R''&thinsp;''y'' dan ''y''&thinsp;''R''&thinsp;''x''.
::(''AlternatiefAlternatieve definitie'': ...) … betekent dat ''G′''&nbsp;⊆&nbsp; ⊆ ''G'', waarbij ''G'' de grafiek van ''R'' is en ''G′'' de grafiek van ''R''&thinsp;<sup>−1</sup>.
* Dat ''R'' '''asymmetrisch''' is, betekent dat er geen ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' zijn zodanig dat ''x''&thinsp;''R''&thinsp;''y'' en ''y''&thinsp;''R''&thinsp;''x''.
* Dat ''R'' '''antisymmetrisch''' is, betekent dat voor alle ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' geldt: als ''x''&thinsp;''R''&thinsp;''y'' en ''y''&thinsp;''R''&thinsp;''x'', dan ''x''&nbsp;=&nbsp;''y''.
* Dat ''R'' '''[[transitiviteit (wiskunde)|transitief]]''' is, betekent dat voor alle ''x'',&nbsp;''y'',&nbsp;''z''&nbsp;∈&nbsp; ∈ ''X'' geldt: als ''x''&thinsp;''R''&thinsp;''y'' en ''y''&thinsp;''R''&thinsp;''z'', dan ''x''&thinsp;''R''&thinsp;''z''.
::(''AlternatiefAlternatieve definitie'': ...) … betekent dat ''G′''&nbsp;⊆&nbsp; ⊆ ''G'', waarbij ''G'' de grafiek van ''R'' is en ''G′'' de grafiek van ''R''&thinsp;∘&thinsp; ∘ ''R''.
* Dat ''R'' '''intransitief''' is, betekent dat er geen ''x'',&nbsp;''y'',&nbsp;''z''&nbsp;∈&nbsp; ∈ ''X'' zijn zodanig dat ''x''&thinsp;''R''&thinsp;''y'', ''y''&thinsp;''R''&thinsp;''z'' en ''x''&thinsp;''R''&thinsp;''z''.
* Dat ''R'' '''[[Dichte relatie|dicht]]''' is, betekent dat voor alle ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' geldt: als ''x''&thinsp;''R''&thinsp;''y'' dan is er een ''z''&nbsp;∈&nbsp; ∈ ''X'' zodanig dat ''x''&thinsp;''R''&thinsp;''z'' en ''z''&thinsp;''R''&thinsp;''y''.
* Dat ''R'' '''[[Euclidische relatie|Euclidisch]]''' is, betekent dat voor alle ''x'',&nbsp;''y'',&nbsp;''z''&nbsp;∈&nbsp; ∈ ''X'' geldt: als ''x''&thinsp;''R''&thinsp;''y'' en ''x''&thinsp;''R''&thinsp;''z'', dan ''y''&thinsp;''R''&thinsp;''z''.
* Dat ''R'' '''[[Samenhangende relatie|samenhangend]]''' is, betekent dat voor alle ''x'',&nbsp;''y'',&nbsp;''z''&nbsp;∈&nbsp; ∈ ''X'' geldt: als ''x''&thinsp;''R''&thinsp;''y'' en ''x''&thinsp;''R''&thinsp;''z'', dan ''y''&thinsp;''R''&thinsp;''z'' of ''z''&thinsp;''R''&thinsp;''y''.
<!-- 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'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' geldt dat ''x''&thinsp;''R''&thinsp;<sup>+</sup>&thinsp;''y'' of ''y''&thinsp;''R''&thinsp;<sup>+</sup>&thinsp;''x'' (of beide), waarbij ''R''&thinsp;<sup>+</sup> de [[#Afsluiting en reductie|transitieve afsluiting]] van ''R'' is.
-->
* Dat ''R'' '''[[Connex (wiskunde)|connex]]''' of '''totaal''' is, betekent dat voor alle ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' geldt dat ''x''&thinsp;''R''&thinsp;''y'' of ''y''&thinsp;''R''&thinsp;''x'' (of beide).
* Dat ''R'' '''[[Trichotoom (wiskunde)|trichotoom]]''' is, betekent dat voor alle ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' precies één van de volgende uitspraken waar is: ''x''&thinsp;''R''&thinsp;''y'', ''y''&thinsp;''R''&thinsp;''x'' of ''x''&nbsp;=&nbsp;''y''.
* Dat ''R'' '''[[Deterministische relatie|deterministisch]]''' is, betekent dat voor alle ''x'',&nbsp;''y'',&nbsp;''z''&nbsp;∈&nbsp; ∈ ''X'' geldt: als ''x''&thinsp;''R''&thinsp;''y'' en ''x''&thinsp;''R''&thinsp;''z'', dan ''y''&thinsp;=&thinsp;''z''. (Vgl. ''rechts-definitiet'' of ''functioneel''.)
* Dat ''R'' '''[[Convergente relatie|convergent]]''' is, betekent dat voor alle ''x'',&nbsp;''y'',&nbsp;''z''&nbsp;∈&nbsp; ∈ ''X'' geldt: als ''x''&thinsp;''R''&thinsp;''y'' en ''x''&thinsp;''R''&thinsp;''z'', dan is er een ''u''&nbsp;∈&nbsp; ∈ ''X'' zodanig dat ''y''&thinsp;''R''&thinsp;''u'' en ''z''&thinsp;''R''&thinsp;''u''.
* Dat ''R'' '''[[Convergente relatie|divergent]]''' is, betekent dat voor alle ''x'',&nbsp;''y'',&nbsp;''z''&nbsp;∈&nbsp; ∈ ''X'' geldt: als ''x''&thinsp;''R''&thinsp;''y'', ''x''&thinsp;''R''&thinsp;''z'' en ''y''&nbsp;≠&nbsp; ≠ ''z'' dan is er geen ''u''&nbsp;∈&nbsp; ∈ ''X'' zodanig dat ''y''&thinsp;''R''&thinsp;''u'' en ''z''&thinsp;''R''&thinsp;''u''.
 
===Operaties op homogene tweeplaatsige relaties===
Regel 168 ⟶ 176:
{{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''&nbsp;⊆&nbsp; ⊆ ''X'' dan is de '''restrictie''' van ''R'' tot ''Y'' de homogene tweeplaatsige relatie ''S'' op ''Y'' waarvoor geldt dat
 
:voor alle ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''Y'' geldt: ''x''&thinsp;''S''&thinsp;''y'' desda ''x''&thinsp;''R''&thinsp;''y''.
 
Informeel gesproken is een restrictie van een homogene tweeplaatsige relatie het resultaat van het inperken van zijn domein.
Regel 183 ⟶ 191:
Zij ''R'' een homogene tweeplaatsige relatie op ''X''.
 
* De '''reflexieve afsluiting''' van ''R'', genoteerd als ''R''&thinsp;<sup>=</sup>, is de tweeplaatsige relatie ''R''&thinsp;<sup>=</sup> op ''X'' waarvoor geldt dat voor alle ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' geldt dat ''x''&thinsp;''R''&thinsp;<sup>=</sup>&thinsp;''y'' desda ''x''&thinsp;''R''&thinsp;''y'' of ''x''&nbsp;=&nbsp;''y''.
* De '''reflexieve reductie''' van ''R'', genoteerd als ''R''&thinsp;<sup>≠</sup>, is de tweeplaatsige relatie ''R''&thinsp;<sup>≠</sup> op ''X'' waarvoor geldt dat voor alle ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' geldt dat ''x''&thinsp;''R''&thinsp;<sup>≠</sup>&thinsp;''y'' desda ''x''&thinsp;''R''&thinsp;''y'' en ''x''&nbsp;≠&nbsp; ≠ ''y''.
* De '''[[transitieve afsluiting]]''' van ''R'', genoteerd als ''R''&thinsp;<sup>+</sup>, is de kleinste transitieve tweeplaatsige relatie ''R''&thinsp;<sup>+</sup> over ''X'' waarvoor geldt: als ''x''&thinsp;''R''&thinsp;''y'' dan ''x''&thinsp;''R''&thinsp;<sup>+</sup>&thinsp;''y''.
* De '''transitieve reductie''' van ''R'', genoteerd als ''R''&thinsp;<sup>−</sup>, is de kleinste tweeplaatsige relatie over ''X'' met dezelfde transitieve afsluiting als ''R''.
* De '''reflexief-transitieve afsluiting''' van ''R'', genoteerd als ''R''&thinsp;*, is de relatie (''R''&thinsp;<sup>+</sup>)&thinsp;<sup>=</sup>&nbsp;=&nbsp;(''R''&thinsp;<sup>=</sup>)&thinsp;<sup>+</sup>.
* De '''transitief-reflexieve reductie''' van ''R'' is de relatie (''R''&thinsp;<sup>−</sup>)&thinsp;<sup>≠</sup>&nbsp;=&nbsp;(''R''&thinsp;<sup>≠</sup>)&thinsp;<sup>−</sup>.
 
===Equivalentierelaties===
Regel 197 ⟶ 205:
Een '''[[equivalentierelatie]]''' is een homogene tweeplaatsige relatie die ''reflexief'', ''symmetrisch'' en ''transitief'' is.
 
Gegeven een equivalentierelatie ~ op ''X'', kan voor iedere ''x''&nbsp;∈&nbsp; ∈ ''X'' de verzameling van alle elementen waarmee ''x'' in ~-relatie staat gedefinieerd worden:
:[''x'']&nbsp;=&nbsp;{&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X''&nbsp;∣&nbsp; ∣ ''x''&thinsp;~&thinsp;''y''&nbsp;}.
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''&nbsp;∈&nbsp; ∈ ''X'' geldt dat ''x''&nbsp;∈&nbsp; ∈ [''x''].
* Iedere ''x''&nbsp;∈&nbsp; ∈ ''X'' zit in precies één equivalentieklasse van ''X''.
* Voor alle ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' geldt: ''x''&thinsp;~&thinsp;''y'' [[desda]] ''x'' en ''y'' in dezelfde equivalentieklasse van ''X'' zitten.
 
De verzameling
:''X''/ ∕ ~&nbsp;=&nbsp;{&nbsp;[''x'']&nbsp;∣&nbsp; ∣ ''x''&nbsp;∈&nbsp; ∈ ''X''&nbsp;}
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'']&nbsp;∈&nbsp; ∈ ''X''/ ∕ ~ zit, de [[Vereniging (verzamelingenleer)|vereniging]] van alle equivalentieklassen [''x'']&nbsp;∈&nbsp; ∈ ''X''/ ∕ ~ gelijk is aan ''X'' en dat de [[lege verzameling]] geen element van ''X''/ ∕ ~ is.
 
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 228 ⟶ 236:
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 (≤&thinsp;≤ <sup>≠</sup>)&thinsp;<sup>=</sup>&nbsp;=&nbsp;≤ ≤. In het algemeen is het echter ''niet'' zo dat voor een willekeurige homogene tweeplaatsige relatie ''R'' geldt dat (''R''&thinsp;<sup>≠</sup>)&thinsp;<sup>=</sup>&nbsp;=&nbsp;''R''. Om precies te zijn geldt (''R''&thinsp;<sup>≠</sup>)&thinsp;<sup>=</sup>&nbsp;=&nbsp;''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.
Regel 246 ⟶ 254:
 
====Preorde====
Een '''[[preorde]]''' is een homogene tweeplaatsige relatie die ''reflexief'' en ''transitief'' is. Preordes worden vaak aangeduid met het symbool ≲. Van iedere homogene tweeplaatsige relatie ''R'' is de reflexief-transitieve afsluiting ''R''&thinsp;* 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 ≲.
Regel 252 ⟶ 260:
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'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'':
:''x''&thinsp;~&thinsp;''y'' [[desda]] ''x''&thinsp;≲&thinsp; ≲ ''y'' en ''y''&thinsp;≲&thinsp; ≲ ''x''.
Als vervolgens een relatie ≤ op ''X''/ ∕ ~ afgeleid wordt door te stellen dat voor alle ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' geldt dat
:[''x'']&thinsp;≤&thinsp; ≤ [''y''] desda ''x''&thinsp;≲&thinsp; ≲ ''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'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' geldt dat
:''x''&thinsp;<&thinsp;''y'' desda [''x'']&thinsp;≤&thinsp; ≤ [''y''] en [''x'']&nbsp;≠&nbsp; ≠ [''y''],
ofwel (de equivalente uitspraak) dat
:''x''&thinsp;<&thinsp;''y'' desda ''x''&thinsp;≲&thinsp; ≲ ''y'' en niet ''x''&thinsp;~&thinsp;''y''.
 
Onder deze constructies geldt voor alle ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' dat
:''x''&thinsp;≲&thinsp; ≲ ''y'' desda ''x''&thinsp;<&thinsp;''y'' of ''x''&thinsp;~&thinsp;''y''.
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“strikte preorde"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“strikte totale preorde"preorde”. Irreflexiviteit en transitiviteit impliceren samen met de voorwaarde
:voor alle ''x'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' geldt: als ''x''&nbsp;≠&nbsp; ≠ ''y'' dan ''x''&thinsp;''R''&thinsp;''y'' of ''y''&thinsp;''R''&thinsp;''x''&emsp;(vgl. ''totaliteit'')
namelijk trichotomie, wat een strikte totale orde op zou leveren.
 
Regel 272 ⟶ 280:
 
====Strikte zwakke orde====
Een '''[[strikte zwakke orde]]''' is een strikte partiële orde < waarvoor de relatie "noch“noch ''x''&thinsp;<&thinsp;''y'', noch ''y''&thinsp;<&thinsp;''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'',&nbsp;''y''&nbsp;∈&nbsp; ∈ ''X'' geldt: als ''x''&thinsp;<&thinsp;''y'' dan geldt voor alle ''z''&nbsp;∈&nbsp; ∈ ''X'' dat ''x''&thinsp;<&thinsp;''z'' of ''z''&thinsp;<&thinsp;''y'' (of beide).
 
Het complement van een strikte zwakke orde is een totale preorde en vice versa.
Regel 290 ⟶ 298:
 
===Het aantal mogelijke homogene tweeplaatsige relaties===
{| class="wikitable"
|+Aantal mogelijke tweeplaatsige relaties op een verzameling met ''n'' elementen
!''n''!!Alle relaties!!Reflexieve relaties!!Transitieve relaties!!Preordes!!Partiële ordes!!Totale preordes!!Totale ordes!!Equivalentierelaties
|-
|0||1||1||1||1||1||1||1||1
|-
|1||2||1||2||1||1||1||1||1
|-
|2||16||4||13||4||3||3||2||2
|-
|3||512||64||171||29||19||13||6||5
|-
|4||65536||4096||3994||355||219||75||24||15
|-
|[[On-Line Encyclopedia of Integer Sequences|OEIS]] || [[OEIS:A002416|A002416]] || [[OEIS:A053763|A053763]] || [[OEIS:A006905|A006905]] || [[OEIS:A000798|A000798]] || [[OEIS:A001035|A001035]] || [[OEIS:A000670|A000670]] || [[OEIS:A000142|A000142]] || [[OEIS:A000110|A000110]]
|}
 
* Het aantal irreflexieve relaties is gelijk aan het aantal reflexieve relaties.
Regel 324 ⟶ 332:
==Voetnoten==
{{References}}
 
==Bronnen==
* {{Citeer boek
| Achternaam = Bourbaki
| Voornaam = Nicolas
| Auteurlink = Nicolas Bourbaki
| Datum = 1994
| Titel = Elements of the History of Mathematics
| Uitgever = Springer
| Taal = en
}}
* {{Citeer boek
| Achternaam = Lucas
| Voornaam = J. R.
| Auteurlink = John Lucas
| Datum = 1999
| Titel = Conceptual Roots of Mathematics
| Uitgever = Routledge
| Taal = en
}}
* {{Citeer boek
| Achternaam = Russell
| Voornaam = Bertrand
| Auteurlink = Bertrand Russell
| Datum = 1903/1938
| Titel = The Principles of Mathematics, 2nd ed.
| Uitgever = Cambridge University Press
| Taal = en
}}
* {{Citeer web
| url = http://planetmath.org/encyclopedia/Relation.html
| titel = ''Relation'' op planetmath.org
| bezochtdatum = 15 januari 2009
| taal = en
}}
* {{Citeer web
| url = http://eom.springer.de/
| achternaam = Hazewinkel
| voornaam = Michiel
| titel = Encyclopaedia of Mathematics
| uitgever = Springer-Verlag
| bezochtdatum = 15 januari 2009
| taal = en
}}
}}
 
{{Etalage|16271131|2009|04|02}}