Tweeplaatsige relatie

In de wiskunde koppelt een tweeplaatsige relatie of binaire relatie tussen twee verzamelingen elementen van de ene verzameling aan elementen van de andere. Anders geformuleerd is een tweeplaatsige relatie de wiskundige beschrijving van een zeker verband tussen de elementen van twee verzamelingen. Een tweeplaatsige relatie is een relatie met een plaatsigheid twee.

Tweeplaatsige relatie, die de relatie tussen de elementen in twee verzamelingen $X$ en $Y$ vastlegt

Tweeplaatsige relaties worden vaak kort relatie genoemd. Historisch gezien werden met relaties alleen tweeplaatsige relaties aangeduid, maar het begrip is later uitgebreid.

Inleiding

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. Mensen die niets bezitten worden door de relatie bezitten nergens aan gekoppeld. De koppeling is in zekere zin dus gericht.

Tweeplaatsige relaties zijn in de wiskunde alomtegenwoordig. Voorbeelden zijn de ongelijkheid en deelbaarheid in de rekenkunde en congruentie in de meetkunde. Daarnaast wordt functie, een van de belangrijkste begrippen in de wiskunde, meestal gedefinieerd als een speciaal geval van een tweeplaatsige relatie. Andere exacte wetenschappen passen tweeplaatsige relaties ook veelvuldig toe, in uiteenlopende gebieden. Ze worden in de informatica onder andere gebruikt in het relationele model voor databases, maar ook in de economie, biologie, natuurkunde en andere wetenschappen worden diverse fenomenen met tweeplaatsige relaties gemodelleerd.

Tweeplaatsige relaties liggen aan de basis van de ordetheorie. Een ordening op een verzameling is pas bepaald als de orde tussen ieder paar elementen bekend is of bekend is dat die twee elementen niet met elkaar kunnen worden vergeleken.

Definitie

Een tweeplaatsige relatie $R$ tussen de verzamelingen $A$ en $B$ is een 3-tupel $(G,A,B)$ waarin

$G\subseteq A\times B$,

dus waarin $G$ een deelverzameling is van het cartesisch product van $A$ en $B$. Alternatief wordt een tweeplaatsige relatie wel gedefinieerd als het 3-tupel $(A,B,G)$ in plaats van $(G,A,B)$.

Als $A=B$ spreekt men van een homogene relatie, of van een endorelatie.

Als duidelijk wordt vermeld of uit de context blijkt, uit welke verzamelingen de leden van de geordende paren komen, wordt een tweeplaatsige relatie soms eenvoudiger gedefinieerd als een verzameling geordende paren, overeenkomend met $G$ uit de definitie.

In sommige systemen van de axiomatische verzamelingenleer worden relaties gedefinieerd op 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 leidt.

Terminologie

Van een tweeplaatsige relatie $R=(G,A,B)$ tussen de verzamelingen $A$ en $B$ wordt $A$ wel aangeduid als de bron(verzameling) en $B$ als de doelverzameling of kort als het doel. De verzameling $G$ heet de grafiek van $R$. In de theorie over relaties worden de verzamelingen $A$ en $B$ ook wel aangeduid als de domeinen van $R$, wat een zekere verwarring schept met het begrip domein als de deelverzameling $\mathrm {dom} (R)$ van $A$ met de elementen waarvoor $R$ gedefinieerd is (dat kan een strikte deelverzameling van $A$ zijn). De verzameling $B$ wordt ook wel het codomein van $R$ genoemd.

Men zegt ook wel dat $R$ een relatie over $A$ en $B$ is. Van een tweeplaatsige relatie $R=(G,A,A)$ wordt gezegd dat $R$ een tweeplaatsige relatie op $A$ is of dat $R$ een tweeplaatsige relatie over $A$ is.

Van het geordende paar $(a,b)\in G$ worden $a$ en $b$ 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 wordt bedoeld, zegt men ook dat $a$ in relatie tot $b$ staat. Als de definitie gebruikt wordt waarbij een tweeplaatsige relatie een verzameling geordende paren is, zegt men dat $a$ in relatie tot $b$ staat als $(a,b)\in R$.

De lege relatie over $A$ en $B$ is de tweeplaatsige relatie tussen $A$ en $B$ waarvan de grafiek de lege verzameling is. Als $R$ de lege relatie tussen $A$ en $B$ is, geldt dat er geen $a\in A$ en $b\in B$ zijn zodanig dat $a$ in $R$ in relatie tot $b$ staat.

De universele relatie tussen $A$ en $B$ is de tweeplaatsige relatie waarvan de grafiek het cartesisch product van $A$ en $B$ is. Als $R$ de universele relatie tussen $A$ en $B$ is, geldt voor alle $a\in A$ en $b\in B$ dat $a$ in $R$ in relatie tot $b$ staat.

Notatie

De uitspraak '$a$ staat in relatie $R$ tot $b$' wordt op verschillende manieren genoteerd:

• functienotatie: $R(a,b)$
• infixnotatie: $aRb$
• Poolse notatie: $Rab$

De functienotatie komt overeen met de indicatorfunctie van de grafiek van $R$.

Voorbeeld

Oceanen en werelddelen

	NA	ZA	AF	EU	AZ	AU	AA
Indische Oceaan	0	0	1	0	1	1	1
Noordelijke IJszee	1	0	0	1	1	0	0
Atlantische Oceaan	1	1	1	1	0	0	1
Stille Oceaan	1	1	0	0	1	1	1

Oceanen en werelddelen

Geef in een tweeplaatsige relatie $R=(G,A,B)$ weer welke oceanen in de wereld aan welke werelddelen liggen.

$A=\{$Indische Oceaan, Noordelijke IJszee, Atlantische Oceaan, Stille Oceaan $\}$ zijn de oceanen en
$B=\{$ Noord-Amerika, Zuid-Amerika, Afrika, Europa, Azië, Australië, Antarctica $\}$ de werelddelen in de wereld.
$aRb$ betekent dat oceaan $a$ tegen werelddeel $b$ aan ligt (op basis van de infixnotatie $aRb$ is $R$ dus 'ligt aan tegen'). De overeenkomende incidentiematrix is:

$R={\begin{pmatrix}0&0&1&0&1&1&1\\1&0&0&1&1&0&0\\1&1&1&1&0&0&1\\1&1&0&0&1&1&1\end{pmatrix}}.$

De verzameling paren is:

$G=\{($Indische Oceaan, Afrika$),($Indische Oceaan, Azië$),($Indische Oceaan, Australië$),$

$($Indische Oceaan, Antarctica$),($Noordelijke IJszee, Noord-Amerika$),($Noordelijke IJszee, Europa$),$

$($Noordelijke IJszee, Azië$),($Atlantische Oceaan, Noord-Amerika$),($Atlantische Oceaan, Zuid-Amerika$),$

$($Atlantische Oceaan, Afrika$),($Atlantische Oceaan, Europa$),($Atlantische Oceaan, Antarctica$),$

$($Stille Oceaan, Noord-Amerika$),($Stille Oceaan, Zuid-Amerika$),($Stille Oceaan, Azië$),$

$($Stille Oceaan, Australië$),($Stille Oceaan, Antarctica$)\}$

Deze tweeplaatsige relatie is noch een functie, noch een afbeelding.

Eigenschappen van tweeplaatsige relaties

Een tweeplaatsige relatie $R$ tussen $A$ en $B$ heet:

• links-volledig: als voor alle $a\in A$ er een $b\in B$ is, zodanig dat $aRb$.
• surjectief of rechts-volledig: als voor alle $b\in B$ er een $a\in A$ is, zodanig dat $aRb$.
• injectief of links-definiet: als geen twee verschillende linkerargumenten van $R$ in relatie staan tot hetzelfde rechterargument van $R$. Dat wil zeggen dat voor alle $a_{1},a_{2}\in A$ en $b\in B$ geldt: als $a_{1}Rb$ en $a_{2}Rb$ dan $a_{1}=a_{2}$.
• rechts-definiet of functioneel: als geen enkel linkerargument van $R$ in relatie staat tot twee verschillende rechter argumenten van $R$. Een andere beschrijving van dezelfde eigenschap is dat ieder linkerargument van $R$ in relatie staat tot ten hoogste één rechterargument van $R$. Beide omschrijvingen willen zeggen dat voor alle $a\in A$ en $b_{1},b_{2}\in B$ geldt: als $aRb_{1}$ en $aRb_{2}$ dan $b_{1}=b_{2}$.
• bijectief of een-eenduidig: als $R$ zowel surjectief als injectief is, of anders gezegd links-volledig, rechts-volledig, links-definiet en rechts-definiet is.

Een links-volledige rechts-definiete tweeplaatsige relatie over $A$ en $B$ wordt een afbeelding van $A$ naar $B$ genoemd. Een afbeelding waarvan het het codomein een lichaam (Ned) / veld (Be) is, is een functie.

Een tweeplaatsige relatie die links- en rechts-volledig is wordt een correspondentierelatie genoemd, maar is niet noodzakelijk functioneel. De combinatie van functionaliteit en injectiviteit wordt een-eenduidigheid of een-op-een genoemd, maar is noch noodzakelijk links-volledig, noch rechts-volledig. Een bijectieve tweeplaatsige relatie wordt meestal een bijectie genoemd, maar ook een een-op-een-correspondentie. Het verschil tussen een-op-een en correspondentie wordt niet altijd gemaakt. Het verschil is dus dat in een bijectie de beide verzamelingen $A$ en $B$ evenveel elementen hebben en dat alle elementen uit beide verzamelingen met een element van de andere verzameling zijn gekoppeld en dat in een functionele en injectieve tweeplaatsige relatie er elementen in $A$ en $B$ kunnen voorkomen, die niet aan een element uit de andere verzameling zijn gekoppeld.

Voorbeelden van bijecties zijn het isomorfisme is in de algebra en het homeomorfisme in de topologie. Bijecties worden in wiskundige bewijzen geconstrueerd om uiteenlopende feiten aan te tonen. Een voorbeeld hiervan is het aantonen van de gelijkmachtigheid van twee verzamelingen. Twee verzamelingen zijn namelijk gelijkmachtig als er een bijectie tussen deze verzamelingen bestaat.

Operaties op tweeplaatsige relaties

Aangezien relaties in wezen verzamelingen zijn, laten operaties op verzamelingen zich op natuurlijke wijze uitbreiden tot relaties. Laat $R$ en $S$ tweeplaatsige relaties tussen $A$ en $B$ zijn.

Doorsnede en vereniging

Zie Doorsnede (verzamelingenleer) en Vereniging (verzamelingenleer) voor de hoofdartikelen over dit onderwerp.

Als $a\in A$ en $b\in B$ zowel in $R$ als in $S$ tot elkaar in relatie staan, ligt het voor de hand te zeggen dat zij tot elkaar in de doorsnede van de beide relaties staan. En omgekeerd zullen elementen die in de doornede tot elkaar in relatie staan, ook tot elkaar in de beide relaties afzonderlijk staan.

De doorsnede van $R$ en $S$ is de tweeplaatsige relatie $R\cap S$ tussen $A$ en $B$ waarvoor geldt:

$a(R\cap S)b\quad$ als $\quad aRb{\text{ en }}aSb$

Op analoge wijze is de vereniging van $R$ en $S$ de tweeplaatsige relatie $R\cup S$ tussen $A$ en $B$ waarvoor geldt:

$a(R\cup S)b\quad$ als $\quad aRb{\text{ of }}aSb$

Vat men een tweeplaatsige relatie op als een verzameling geordende paren, overeenkomend met de grafiek van de 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.

Complement

Zie Complement (verzamelingenleer) voor het hoofdartikel over dit onderwerp.

Het complement van $R$, genoteerd als $R^{c}$ of als ${\overline {R}}$, is de tweeplaatsige relatie tussen $A$ en $B$ waarvoor geldt:

$aR^{c}b\quad$ als $\quad {\text{niet }}aRb$

Voor alle tweeplaatsige relaties $R$ geldt:

$(R^{c})^{c}=R$

Compositie of samenstelling

Zie Samengestelde relatie voor het hoofdartikel over dit onderwerp.

Laat $R$ een tweeplaatsige relatie tussen $A$ en $B$ zijn, en $S$ een tweeplaatsige relatie tussen$B$ en $C$. De compositie of samenstelling van $R$ en $S$ is de tweeplaatsige relatie $R\circ S$ tussen $A$ en $C$ waarvoor geldt:

$a(R\circ S)c$ als er een $b\in B$ is waarvoor $aRb{\text{ en }}bSc$

Compositie is associatief:

$(R\circ S)\circ T=R\circ (S\circ T)$

Daarom wordt meestal alleen $R\circ S\circ T$ geschreven in plaats van $(R\circ S)\circ T$ of $R\circ (S\circ T)$.

Vaak wordt de compositie van $R$ en $S$ genoteerd als $S\circ R$ in plaats van $R\circ S$, zodat de notatie in overeenstemming is met de notatie voor functiecompositie. 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

Zie Inverse voor het hoofdartikel over dit onderwerp.

De inverse van $R$ is de tweeplaatsige relatie $R^{-1}$ tussen $B$ en $A$ waarvoor geldt:

$bR^{-1}a\quad$ als $\quad aRb$

Voor alle tweeplaatsige relaties $R$ geldt:

• $(R^{-1})^{-1}=R$
• Als $R$ links-volledig is, dan is $R^{-1}$ rechts-volledig.
• Als $R$ rechts-volledig is, dan is $R^{-1}$ links-volledig.
• Als $R$ links-definiet is, dan is $R^{-1}$ rechts-definiet.
• Als $R$ rechts-definiet is, dan is $R^{-1}$ links-definiet.
• Als $R$ bijectief is, dan is $R^{-1}$ dat ook.

Eigenschappen van deze operaties

Zij $R$ en $S$ tweeplaatsige relaties tussen $A$ en $B$, $T$ een tweeplaatsige relatie tussen $B$ en $C$, en $P$ een tweeplaatsige relatie tussen $X$ en $A$.

• De doorsnede van $R$ en het complement $R^{c}$ van $R$ is de lege relatie tussen $A$ en $B$:

$R\cap R^{c}=(\varnothing ,A,B)$

• De vereniging van $R$ en het complement $R^{c}$ van $R$ is de universele relatie tussen $A$ en $B$:

$R\cup R^{c}=(A\times B,A,B)$

• De inverse van het complement van $R$ is hetzelfde als het complement van de inverse van $R$:

$(R^{c})^{-1}=(R^{-1})^{c}$

• De inverse van de compositie van $R$ en $T$ is hetzelfde als de compositie van de inverse van $T$ en de inverse van $R$:

$(R\circ T)^{-1}=T^{-1}\circ R^{-1}$

• De inverse is distributief over zowel doorsnede als vereniging:

$(R\cap S)^{-1}=R^{-1}\cap S^{-1}$

$(R\cup S)^{-1}=R^{-1}\cup S^{-1}$

• De compositie is zowel links- als rechtsdistributief over de vereniging: (dit geldt niet voor de doorsnede).

$P\circ (R\cup S)=(P\circ R)\cup (P\circ S)$

$(R\cup S)\circ T=(R\circ T)\cup (S\circ T)$

Homogene tweeplaatsige relaties

Een homogene tweeplaatsige relatie of tweeplaatsige endorelatie is een tweeplaatsige relatie waarvan het domein en het codomein dezelfde verzameling zijn. Als $R$ een homogene tweeplaatsige relatie op $A$ is, wordt $R$ soms gedefinieerd als het 2-tupel of koppel $(G,A)$ in plaats van het 3-tupel $(G,A,A)$. Deze wijze van noteren is bijvoorbeeld gebruikelijk in de grafentheorie.

Eigenschappen van homogene tweeplaatsige relaties

Een homogene tweeplaatsige relatie $R$ op $A$ heet

• voortzettend: als voor alle $a\in A$ er een $b\in A$ is zodanig dat $aRb$.
• reflexief: als voor alle $a\in A$ geldt dat $aRa$.

alternatief: als voor de grafiek $G$ van $R$ en de identieke afbeelding $\mathrm {id} _{A}$ van $A$ geldt: $\mathrm {id} _{A}\subseteq G$.

• irreflexief: als er geen $a\in A$ is zodanig dat $aRa$.
• symmetrisch: als voor alle $a,b\in A$ geldt: als $aRb$, dan $bRa$.

alternatief: als voor de grafieken $G$ van $R$ en $G'$ van $R^{-1}$ geldt: $G'\subseteq G$

• asymmetrisch: als er geen paar $a,b\in A$ is met $aRb$ en $bRa$.
• antisymmetrisch: als voor alle $a,b\in A$ geldt: als $aRb$ en $bRa$, dan $a=b$.
• transitief: als voor alle $a,b,c\in A$ geldt: als $aRb$ en $bRc$, dan $aRc$.

alternatief: als voor de grafieken $G$ van $R$ en $G'$ van $R\circ R$ geldt: $G'\subseteq G$

• intransitief: als er geen $a,b,c\in A$ zijn zodanig dat $aRb,bRc$ en $aRc$.
• dicht: als voor alle $a,b\in A$ geldt: als $aRb$ dan is er een $c\in A$ zodanig dat $aRc$ en $cRb$.
• euclidisch: als voor alle $a,b,c\in A$ geldt: als $aRb$ en $aRc$, dan $bRc$.
• samenhangend: als voor alle $a,b,c\in A$ geldt: als $aRb$ en $aRc$, dan $bRc$ of $cRb$.
• totaal: als voor alle $a,b\in A$ geldt dat $aRb$ of $bRa$, of beide.
• connex: als voor alle $a,b\in A$ geldt dat $a=b$ of $aRb$ of $bRa$.
• trichotoom: als voor alle $a,b\in A$ precies een van de volgende uitspraken waar is: $aRb$, $bRa$ of $a=b$.
• deterministisch: als voor alle $a,b,c\in A$ geldt: als $aRb$ en $aRc$, dan $b=c$. Vergelijk het met de definities van rechts-definitiet en functioneel.
• convergent: als voor alle $a,b,c\in A$ geldt: als $aRb$ en $aRc$, dan is er een $d\in A$ zodanig dat $bRd$ en $cRd$.
• divergent: als voor alle $a,b,c\in A$ geldt: als $aRb$, $aRc$ en $b\neq c$ dan is er geen $d\in A$ zodanig dat $bRd$ en $cRd$.

Operaties op homogene tweeplaatsige relaties

Restrictie en extensie

Zie Restrictie (wiskunde) voor het hoofdartikel over dit onderwerp.

Zij $R$ een homogene tweeplaatsige relatie op $A$. Als $B\subseteq A$, dan is de restrictie van $R$ tot $B$ de homogene tweeplaatsige relatie $S$ op $B$ waarvoor geldt:

$a,b\in B$ dan $aSb\Longleftrightarrow aRb$.

Informeel gesproken is een restrictie van een homogene tweeplaatsige relatie het resultaat van het inperken van zijn domein.

Als $R$ een of meer van de eigenschappen reflexief, irreflexief, symmetrisch, asymmetrisch, antisymmetrisch, transitief, intransitief, euclidisch, totaal, trichotoom, deterministisch of divergent heeft, dan heeft iedere restrictie van $R$ dezelfde eigenschappen ook. Als gevolg is iedere restrictie van een equivalentierelatie ook een equivalentierelatie, iedere restrictie van een partiële orde ook een partiële orde, enzovoort.

Als $S$ een restrictie van $R$ is, dan heet $R$ een extensie van $S$.

Afsluiting en reductie

Zij $R$ een homogene tweeplaatsige relatie op $A$.

• De reflexieve afsluiting van $R$ is de tweeplaatsige relatie $R^{=}$ op $A$ waarvoor geldt:

$aR^{=}b\Longleftrightarrow aRb{\text{ of }}a=b$

• De reflexieve reductie van $R$ is de tweeplaatsige relatie $R^{\neq }$ op $A$ waarvoor geldt:

$aR^{=}b\Longleftrightarrow aRb{\text{ en }}a\neq b$

• De transitieve afsluiting van $R$ is de kleinste transitieve tweeplaatsige relatie $R^{+}$ op $A$ die $R$ omvat.
• De transitieve reductie van $R$ is de kleinste tweeplaatsige relatie $R^{-}$ op $A$ met dezelfde transitieve afsluiting als van $R$.
• De reflexief-transitieve afsluiting van $R$ is de relatie $R^{*}=(R^{+})^{=}=(R^{=})^{+}$.
• De transitief-reflexieve reductie van $R$ is de relatie $(R^{-})^{\neq }=(R^{\neq })^{-}$.

Equivalentierelaties

Zie Equivalentierelatie voor het hoofdartikel over dit onderwerp.

Equivalentierelatie. De verbindingen van punten met zichzelf zijn weggelaten.

Een equivalentierelatie is een homogene tweeplaatsige relatie die reflexief, symmetrisch en transitief is.

Voor een equivalentierelatie $\sim$ op $A$, is voor iedere $a\in A$ de equivalentieklasse $[a]$ van $a$ de verzameling van alle elementen waarmee $a$ in $\sim$-relatie staat:

$[a]=\{b\in A\mid b\sim a\}$

Equivalentieklassen hebben de volgende eigenschappen:

• Voor alle $a\in A$ geldt dat $a\in [a]$.
• Elke $a\in A$ behoort tot precies één equivalentieklasse.
• De equivalentieklassen vormen een partitie van $A$.
• Voor alle $a,b\in A$ geldt: $a\sim b\Longleftrightarrow [a]=[b],a$ en $b$ zitten in dezelfde equivalentieklasse.

De verzameling

$A/\sim \ =\{\,[a]\mid a\in A\,\}$

van alle equivalentieklassen van $a$ wordt de quotiëntverzameling van $A$ onder $\sim$ genoemd.

Quotiëntverzamelingen hebben de volgende eigenschappen:

• Iedere equivalentierelatie op $A$ levert een unieke quotiëntverzameling op. Er zijn, met andere woorden, geen twee verschillende equivalentierelaties op $A$ die dezelfde quotiëntverzameling van $A$ opleveren.
• $A/\sim$ is een partitie van $A$. Dat wil zeggen dat ieder element van $A$ in precies een van de equivalentieklassen $[a]\in A/\sim$ zit, de vereniging van alle equivalentieklassen $[a]\in A/\sim$ gelijk is aan $A$ en dat de lege verzameling geen element van $A/\sim$ is.

Iedere partitie van $A$ is dus een quotiëntverzameling van $A$ onder een zekere equivalentierelatie op $A$, anders gezegd is er een bijectie tussen alle mogelijke partities van $A$ en alle mogelijke equivalentierelaties op $A$.

Orderelaties

Zie Ordetheorie voor het hoofdartikel over dit onderwerp.

Een belangrijke toepassing van (homogene) tweeplaatsige relaties is het beschrijven van orde door middel van orderelaties. Soorten orderelatie zijn onder meer totale orde, partiële orde, totale preorde, preorde, strikte totale orde, strikte partiële orde en strikte zwakke orde.

Grafen

Een homogene tweeplaatsige relatie op een eindig domein kan ook geïnterpreteerd en weergegeven worden als een gerichte graaf met eventuele lussen (pijlen van een knoop naar zichzelf). De elementen uit het domein komen dan overeen met de knopen van de graaf en de elementen uit de grafiek met de zijden van de graaf.

In een context met alleen reflexieve relaties kan worden afgesproken dat de lussen niet weergegeven worden.

In een context met alleen transitieve relaties kan worden afgesproken dat met de weergegeven graaf de transitieve afsluiting ervan wordt bedoeld, en dat de relaties worden weergegeven met de graaf van de transitieve reductie, als deze bestaat, en anders de graaf wel "zoveel mogelijk" gereduceerd wordt. Dat hoeft dan niet een graaf met het absoluut minimale aantal pijlen te zijn, als duidelijk overbodige pijlen maar worden vermeden.

In een context met alleen partiële ordes kunnen beide vereenvoudigingen gecombineerd worden.

Voorbeelden van homogene tweeplaatsige relaties

Hier volgen drie voorbeelden uit de wiskunde.

• 'Is-groter-dan' is een bekend voorbeeld van een homogene tweeplaatsige relatie op getallen of, meer in het algemeen, op numerieke expressies. Het is een strikte totale orde.
• 'Is-gelijk-aan' is een voor de hand liggend voorbeeld van een equivalentierelatie. Het domein van de verzameling, waarop de relatie 'is-gelijk-aan' betrekking heeft, zou de verzameling van alle objecten moeten zijn, of ten minste de verzameling van alle wiskundige objecten, maar dat leidt tot de russellparadox. Om dit te omzeilen zouden er verschillende is-gelijk-aan-relaties gedefinieerd kunnen worden voor bijvoorbeeld getallen en meetkundige figuren.
• Omdat afbeeldingen ook tweeplaatsige relaties zijn, is iedere identieke afbeelding $\mathrm {id} _{A}$ een homogene tweeplaatsige relatie op $A$. De identieke afbeelding $\mathrm {id}$ op een verzameling $A$ is zowel een bijectie als een equivalentierelatie en het is de enige relatie op $A$ die zowel een bijectie als een equivalentierelatie is. Overigens is de identieke afbeelding van $A$ de kleinst mogelijke equivalentierelatie op $A$. De grootst mogelijke equivalentierelatie op $A$ is de universele tweeplaatsige relatie op $A$.

Aantal mogelijke homogene tweeplaatsige relaties

$R$ is een tweeplaatsige relatie en $n$ is het aantal elementen van de verzameling $A$, die het domein en het codomein van $R$ bepaalt.

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	partiële ordes bij ongelabelde elementen	equivalentierelaties bij ongelabelde elementen
0	1	1	1	1	1	1	1	1	1	1
1	2	1	2	1	1	1	1	1	1	1
2	16	4	13	4	3	3	2	2	2	2
3	512	64	171	29	19	13	6	5	5	3
4	65536	4096	3994	355	219	75	24	15	16	5
OEIS	A002416	A053763	A006905	A000798	A001035	A000670	A000142	A000110	A000112	A00041

• Het aantal relaties is $2^{(n^{2})}$. De universele relatie heeft $n^{2}$ elementen. Het totale aantal relaties komt overeen met het aantal elementen in de machtsverzameling van deze universele relatie, dus is $2^{(n^{2})}$.
• Het aantal reflexieve en het aantal irreflexieve relaties is $2^{n(n-1)}$. Voor de $n$ elementen $a\in A$ moet in een reflexieve relatie steeds gelden dat $(a,a)\in R$ en in een irreflexieve relatie dat $(a,a)\notin R$, dus blijven er in beide gevallen $n(n-1)$ geordende paren over, die al dan niet element van $R$ zijn. Het aantal elementen in de machtsverzameling van een relatie met $n(n-1)$ geordende paren is $2^{n(n-1)}$.
• Het aantal bijecties is gelijk aan het aantal totale ordes.
• Het aantal equivalentierelaties is gelijk aan het aantal partities van dezelfde verzameling.
• Het aantal strikte partiële ordes is gelijk aan het aantal partiële ordes.
• Het aantal strikte zwakke ordes is gelijk aan het aantal totale preordes. Aangezien strikte zwakke ordes strikte partiële ordes zijn, is het aantal totale preordes niet groter dan het aantal partiële ordes. Voor $n\geq 3$ is het aantal kleiner, en zijn er dus ook strikte partiële ordes die geen strikte zwakke orde zijn.
• Het aantal strikte totale ordes is gelijk aan het aantal totale ordes.

Voor elke $n$ is er precies één equivalentierelatie die tevens partiële orde is, 'is gelijk aan', genoteerd '='. Verder is er het complement ervan, de symmetrische irreflexieve relatie 'is niet gelijk aan', genoteerd '≠'. De lege relatie is irreflexief, transitief en symmetrisch, en is zowel de strikte partiële orde behorend bij '=', als de strikte zwakke orde behorend bij de totale preorde waarbij alle elementen equivalent zijn, de universele relatie. De universele relatie is een equivalentierelatie. Alle vier zijn ze dus symmetrisch. Voor $n\geq 2$ zijn het vier verschillende relaties, en is '≠' niet transitief. Het zijn de relaties die bij een permutatie van de elementen gelijk blijven, dus waarbij het gelden van $aRb$ hoogstens afhangt van het al of niet gelijk zijn van $a$ en $b$.

Geval n = 2

Er zijn twee totale ordes op $\{a,b\}$, een waarbij $a<b$ en een waarbij $b<a$. Voor beide geldt dat de inverse van het complement tevens de irreflexieve versie is, en dat dit een strikte totale orde is.

Er is één partiële orde op $\{a,b\}$ die geen totale orde is, namelijk die waarbij alleen $a\leq a$ en $b\leq b$ (de relatie '='). De elementen $a$ en $b$ worden onvergelijkbaar genoemd. Dat geeft samen drie partiële ordes. De irreflexieve versie is de lege relatie, de strikte partiële orde die geen strikte totale orde is. De inverse van het complement is geen preorde. Er is verder een strikte partiële orde die geen strikte totale orde is, namelijk de lege relatie, die tevens de strikte zwakke orde is die hoort bij de totale preorde die geen totale orde is.

Er is één totale preorde die geen totale orde is, namelijk die waarbij voor alle paren $(x,y)$ geldt $x\lesssim y$ (de universele relatie). Voor $\{a,b\}$ is dus $a\sim b$. $a$ en $b$ vormen samen een equivalentieklasse en worden equivalent, gelijkwaardig of indifferent genoemd. Dit geeft samen drie totale preordes. De inverse van het complement is de bijbehorende strikte zwakke orde '$<$', de lege relatie, de al genoemde strikte partiële orde die geen strikte totale orde is.

Dit geeft samen vier preordes. Er zijn geen preordes die noch partiële orde, noch totale preorde zijn.

Als preordes die alleen verschillen door een permutatie van de elementen als één (soort) preorde worden geteld, zijn er drie: totale orde, onvergelijkbaar en equivalent.

Geval n = 3

Er zijn 6 totale ordes, en nog 13 partiële ordes (de relatie '=', 6 partiële ordes met twee vergelijkbare elementen, en 6 met een element dat met de andere twee vergelijkbaar is) en 7 totale preordes die geen totale orde zijn (1 met één klasse, en 6 met twee klassen). Bijbehorend zijn er 6 strikte totale ordes, en nog 13 strikte partiële ordes. Van deze 13 zijn er 7 de strikte zwakke ordes die geen strikte totale orde zijn. De 6 strikte partiële ordes die geen strikte zwakke orde zijn, zijn die met precies één paar vergelijkbare elementen.

Er zijn ook 3 preordes die noch partiële orde, noch totale preorde zijn, namelijk die met twee equivalente elementen die beide met het derde element onvergelijkbaar zijn. Alle elementen zijn maximaal en minimaal element. Er zijn geen grootste of kleinste elementen. De "bijbehorende" strikte orde is steeds de lege relatie.

Als preordes die alleen verschillen door een permutatie van de elementen als één (soort) preorde worden geteld, zijn er 8: 1 totale orde, nog 4 partiële ordes, nog 2 totale preordes en nog een preorde. Merk op dat bij de niet-totale partiële ordes met een element dat met de andere twee vergelijkbaar is, onderscheiden moeten worden het geval dat er een grootste element is, en dat waarbij er een kleinste element is. Er is wel symmetrie, maar de ene gaat niet door een permutatie van de elementen over in de andere.

Er zijn 35 reflexieve relaties die geen preordes zijn omdat ze niet transitief zijn; hiertoe behoren er twee die de reflexieve afsluiting zijn van de relatie "wordt gevolgd door" bij een cyclus van de drie elementen, die overeenkomt met de opvolgersafbeelding.

Er zijn verder 6 strikte totale ordes, en nog 13 strikte partiële ordes, waaronder de lege relatie. Hiervan zijn er 7 tevens de strikte zwakke ordes die horen bij de totale preordes die geen totale orde zijn.

Geval n = 4

Er zijn 24 totale ordes, en nog 195 partiële ordes, in totaal dus 219 partiële ordes. Er zijn verder 24 strikte totale ordes, en nog 195 strikte partiële ordes, waaronder de lege relatie. Bij ongelabelde elementen zijn er in totaal ook 16 strikte partiële ordes.

Er zijn verder 75 totale preordes, waarvan 51 die geen totale orde zijn.

Er zijn ook nog 85 preordes die noch partiële orde, noch totale preorde zijn. Hiervan zijn er 78 die kunnen worden geconstrueerd als de partiële ordes die geen totale orde zijn (13 voor n = 3), toegepast op een combinatie van twee equivalente elementen en de twee andere, niet equivalente elementen. Verder zijn er 4 met drie equivalente elementen en een onvergelijkbare, en 3 met twee onvergelijkbare paren equivalente elementen.

Als preordes die alleen verschillen door een permutatie van de elementen als één (soort) preorde worden geteld, zijn er 1 totale orde, nog 15 partiële ordes, voor de partities '4', '3+1', '2+2' en '2+1+1' respectievelijk 1, 2, 1 en 3 totale preordes (samen 7) en een aantal preordes die noch partiële orde, noch totale preorde zijn.

Toepassingen buiten de wiskunde

In de economische wetenschap wordt het begrip voorkeur vaak gemodelleerd met een tweeplaatsige preferentierelatie, namelijk een totale preorde of de bijbehorende strikte zwakke orde.

voetnoten

literatuur

• (en) Bourbaki, Nicolas (1994), Elements of the History of Mathematics. Springer.
• (en) JR Lucas. Conceptual Roots of Mathematics, 1999.
• (en) Russell, Bertrand (1903/1938), The Principles of Mathematics, 2nd ed.. Cambridge University Press.
• (en) Hazewinkel, Michiel, Encyclopaedia of Mathematics. Springer-Verlag.

Dit artikel is op 2 april 2009 in deze versie opgenomen in de etalage.