Tweeplaatsige relatie - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for Tweeplaatsige relatie.

Tweeplaatsige relatie

Uit Wikipedia, de vrije encyclopedie

Schematische weergave van een tweeplaatsige relatie. De punten in de cirkels geven objecten aan en de lijnen tussen de punten geven aan welke objecten met elkaar in relatie staan.
Schematische weergave van een tweeplaatsige relatie. De punten in de cirkels geven objecten aan en de lijnen tussen de punten geven aan welke objecten met elkaar in relatie staan.

In de wiskunde koppelt een tweeplaatsige relatie of binaire relatie tussen twee verzamelingen de elementen van de ene verzameling aan elementen van de andere. Een tweeplaatsige relatie is een specifiek geval van een relatie, namelijk een relatie met een plaatsigheid van twee. 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 alleen relatie genoemd. Historisch gezien werden met relaties oorspronkelijk 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.

Definitie

Een tweeplaatsige relatie tussen de verzamelingen en is een 3-tupel waarin

,

dus waarin een deelverzameling is van het cartesisch product van en . Alternatief wordt een tweeplaatsige relatie wel gedefinieerd als het 3-tupel in plaats van .

De tweeplaatsige relatie wordt soms eenvoudiger gedefinieerd als een verzameling geordende paren, overeenkomstig met de uit de eerste definitie. Uit welke verzamelingen de leden van de geordende paren komen, moet in dat geval expliciet worden genoemd 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.[1] De verzameling { (1, 2),  (2, 3) } is bijvoorbeeld wel een tweeplaatsige relatie op natuurlijke getallen, maar niet op de verzameling van alle meetkundige figuren. Een verzameling paren is, met andere woorden, niet een tweeplaatsige relatie zonder meer.

Het belangrijkste verschil tussen deze definities komt aan het licht wanneer tweeplaatsige relaties op gelijkheid getoetst worden. Neem de relaties en , waarbij . Het is evident dat in dit geval , hoewel de verzameling geordende paren in beide relaties hetzelfde is. Onder de tweede definitie zouden dezelfde relaties echter als volgt gedefinieerd worden: en , waaruit volgt dat .

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 wordt de grafiek van genoemd, het domein van en het codomein van . Men zegt ook dat een relatie over en is. Van een tweeplaatsige relatie , waarvan domein en codomein hetzelfde zijn, wordt gezegd dat een tweeplaatsige relatie over is of dat een tweeplaatsige relatie op is.

Van het geordende paar worden en argumenten van genoemd. Daarbij is een linker argument en een rechter argument. Verder zegt men in dit geval dat in -relatie staat tot . Als uit de context duidelijk is welke relatie wordt bedoeld zegt men ook dat in relatie tot staat. Wanneer de definitie gebruikt wordt waarbij een tweeplaatsige relatie een verzameling geordende paren is, zegt men dat in relatie tot staat als .

De lege relatie over en is de tweeplaatsige relatie over en waarvan de grafiek de lege verzameling is. Als de lege relatie over en is, dan geldt dat er geen en zijn zodanig dat in in relatie tot staat.

De universele relatie over en is de tweeplaatsige relatie waarvan de grafiek het cartesisch product van en is. Als de universele relatie over en is, geldt voor alle en dat in in relatie tot staat.

Notatie

De uitspraak ' staat in in relatie tot ' wordt op verschillende manieren genoteerd:

  • functienotatie ― 
  • infixnotatie ― 
  • Poolse notatie ― 

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

Voorbeelden

Een voorbeeld van een tweeplaatsige relatie over de verzameling van alle mensen is 'houden van'. Wanneer deze relatie wordt aangeduid met de letter L, van liefde, dan betekent L(Romeo, Julia) dat Romeo van Julia houdt. L(Julia, Romeo) zou betekenen dat Julia van Romeo houdt.

Voor een meer abstract voorbeeld worden eerst de verzamelingen waarvoor de relatie is gedefinieerd, beschreven.

= { Anna,  Boris,  Christine,  Dirk }

is een verzameling van vier willekeurige mensen en

= { Boek,  Bal,  Fiets,  Zon,  Maan }

is een verzameling van vijf objecten. Verder is

= { (Anna,  Bal),  (Christine,  Boek),  (Dirk,  Boek),  (Dirk,  Fiets) }.

Merk op dat alle linker leden van de paren in uit komen en alle rechter leden uit komen, waaruit volgt dat

.

is dus een tweeplaatsige relatie over en .

Als de relatie het begrip 'bezitten' beschrijft, dan betekent (Dirk, Fiets) dat Dirk de Fiets bezit en (Anna, Boek) dat Anna het Boek bezit. Het eerste is volgens de geconstrueerde relatie waar, het tweede is niet waar. Merk op dat volgens deze relatie niemand de Zon en de Maan bezit, dat het Boek in bezit is van zowel Christine als Dirk en dat Boris niets bezit.

Eigenschappen van tweeplaatsige relaties

Zij een tweeplaatsige relatie over en . De volgende eigenschappen[2] zijn nu gedefinieerd.

  • links-volledig ― Dat links-volledig is, betekent dat voor alle er een is, zodanig dat .
  • surjectief of rechts-volledig ― Dat of surjectief is, betekent dat voor alle er een is, zodanig dat .
  • injectief of links-definiet ― Dat injectief is, betekent dat geen twee verschillende linkerargumenten van in relatie staan tot hetzelfde rechterargument van . Dat wil zeggen dat voor alle en geldt: als en   dan .
  • rechts-definiet of functioneel ― Dat rechts-definiet is, betekent dat geen enkel linkerargument van in relatie staat tot twee verschillende rechter argumenten van . Een andere beschrijving van dezelfde eigenschap is dat ieder linkerargument van in relatie staat tot ten hoogste één rechterargument van . Beide omschrijvingen willen zeggen dat voor alle en geldt: als en dan .
  • bijectief of een-eenduidig ― Dat bijectief is, betekent dat links-volledig, rechts-volledig, links-definiet en rechts-definiet is.

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

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 ook als synoniem voor tweeplaatsige relatie gebruikt en het onderscheid tussen een-op-een-relatie en correspondentierelatie 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. Het verschil is dat in een bijectie de beide verzamelingen en 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 en kunnen voorkomen, die niet aan een element uit de andere verzameling zijn gekoppeld.

Het isomorfisme is in de algebra bijvoorbeeld een een-op-een-correspondentie en in de topologie is het homeomorfisme een een-op-een-correspondentie. Een-op-een-correspondenties 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 desda er een een-op-een-correspondentie tussen deze verzamelingen bestaat.

Operaties op tweeplaatsige relaties

Doorsnede en vereniging

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

Zij en tweeplaatsige relaties over en . De doorsnede van en , genoteerd als , is de tweeplaatsige relatie over en waarvoor geldt dat

voor alle en geldt: desda en .

De vereniging van en , genoteerd als , is de tweeplaatsige relatie over en waarvoor geldt dat

voor alle en geldt: desda of (of beide).

Wanneer de definitie van tweeplaatsige relatie wordt gebruikt 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.

Complement

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

Zij een tweeplaatsige relatie over en . Het complement van , genoteerd als of als , is de tweeplaatsige relatie over en waarvoor geldt dat

voor alle en geldt: desda niet .

Merk op dat voor alle tweeplaatsige relaties geldt dat

.

Compositie of samenstelling

Zie Samengestelde relatie voor het hoofdartikel over dit onderwerp.

Zij een tweeplaatsige relatie over en , en een tweeplaatsige relatie over en . De compositie of samenstelling van en , genoteerd als , is de tweeplaatsige relatie over en waarvoor geldt dat

voor alle en geldt: desda er een is zodanig dat en .

Alle tweeplaatsige relaties over en , over en , en over en zijn associativitief:

.

Daarom wordt meestal alleen geschreven in plaats van of .

Vaak wordt de compositie van en genoteerd als in plaats van , 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 of converse

Zie Inverse voor het hoofdartikel over dit onderwerp.

Zij een tweeplaatsige relatie over en . De inverse of converse van , genoteerd als  , is de tweeplaatsige relatie over en waarvoor geldt dat

voor alle en geldt: desda .

Merk op dat voor alle tweeplaatsige relaties het volgende geldt:

  • .
  • Als links-volledig is, dan is rechts-volledig.
  • Als rechts-volledig is, dan is links-volledig.
  • Als links-definiet is, dan is rechts-definiet.
  • Als rechts-definiet is, dan is links-definiet.
  • Als bijectief is, dan is ook bijectief.

Eigenschappen van deze operaties

Zij en tweeplaatsige relaties over en , een tweeplaatsige relatie over en , en een tweeplaatsige relatie over en .

  • De doorsnede van en het complement van is de lege relatie over en :
.
  • De vereniging van en het complement van is de universele relatie over en :
.
  • De inverse van het complement van is hetzelfde als het complement van de inverse van :
.
  • De inverse van de compositie van en is hetzelfde als de compositie van de inverse van en de inverse van :
.
  • De inverse is distributief over zowel doorsnede als vereniging:
,
.
  • Compositie is zowel links- als rechts-distributief over vereniging: (Merk op dat dit niet voor de doorsnede geldt.)
,
.

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 homogene tweeplaatsige relatie of tweeplaatsige endorelatie is dan ook een tweeplaatsige relatie waarvan het domein en het codomein dezelfde verzameling zijn. Als een homogene tweeplaatsige relatie op is, dan wordt soms gedefinieerd als het 2-tupel of koppel in plaats van het 3-tupel . Deze wijze van definiëren is bijvoorbeeld gebruikelijk in de grafentheorie.

Eigenschappen van homogene tweeplaatsige relaties

Zij een homogene tweeplaatsige relatie op .

  • voortzettend ― Dat voortzettend is, betekent dat voor alle er een is zodanig dat .
  • reflexief ― Dat reflexief is, betekent dat voor alle geldt dat .
alternatieve definitie ― betekent dat , waarbij de grafiek van is en de identieke afbeelding van .
  • irreflexief ― Dat irreflexief is, betekent dat er geen is zodanig dat .
  • symmetrisch ― Dat symmetrisch is, betekent dat voor alle geldt: als dan .
alternatieve definitie ― betekent dat , waarbij de grafiek van is en de grafiek van
  • asymmetrisch ― Dat asymmetrisch is, betekent dat er geen paar is met en .
  • antisymmetrisch ― Dat antisymmetrisch is, betekent dat voor alle geldt: als en , dan .
  • transitief ― Dat transitief is, betekent dat voor alle geldt: als en , dan .
alternatieve definitie ― betekent dat , waarbij de grafiek van is en de grafiek van .
  • intransitief ― Dat intransitief is, betekent dat er geen zijn zodanig dat , en .
  • dicht ― Dat dicht is, betekent dat voor alle geldt: als dan is er een zodanig dat en .
  • euclidisch ― Dat euclidisch is, betekent dat voor alle geldt: als en , dan .
  • samenhangend ― Dat samenhangend is, betekent dat voor alle geldt: als en , dan of .
  • totaal ― Dat totaal is, betekent dat voor alle geldt dat of , of beide.
  • trichotoom ― Dat trichotoom is, betekent dat voor alle precies een van de volgende uitspraken waar is: , of .
  • deterministisch ― Dat deterministisch is, betekent dat voor alle geldt: als en , dan . Vergelijk het met de definities van rechts-definitiet en functioneel.
  • convergent ― Dat convergent is, betekent dat voor alle geldt: als en , dan is er een zodanig dat  en .
  • divergent ― Dat divergent is, betekent dat voor alle geldt: als , en dan is er geen zodanig dat en  .

Operaties op homogene tweeplaatsige relaties

Restrictie en extensie

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

Zij een homogene tweeplaatsige relatie op . Als dan is de restrictie van tot de homogene tweeplaatsige relatie op waarvoor geldt dat

voor alle geldt: desda .

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

Als 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 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, enz.

Als een restrictie van is, dan heet een extensie van .

Afsluiting en reductie

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

Zij een homogene tweeplaatsige relatie op .

  • De reflexieve afsluiting van , genoteerd als , is de tweeplaatsige relatie op waarvoor geldt dat voor alle geldt dat desda of .
  • De reflexieve reductie van , genoteerd als , is de tweeplaatsige relatie op waarvoor geldt dat voor alle geldt dat desda en .
  • De transitieve afsluiting van , genoteerd als , is de kleinste transitieve tweeplaatsige relatie over waarvoor geldt: als dan .
  • De transitieve reductie van , genoteerd als , is de kleinste tweeplaatsige relatie over met dezelfde transitieve afsluiting als van .
  • De reflexief-transitieve afsluiting van , genoteerd als  , is de relatie .
  • De transitief-reflexieve reductie van is de relatie .

Equivalentierelaties

Zie Equivalentierelatie voor het hoofdartikel over dit onderwerp.
Schematische weergave van een equivalentierelatie. De lijnen die punten met zichzelf verbinden zijn omwille van eenvoud weggelaten.
Schematische weergave van een equivalentierelatie. De lijnen die punten met zichzelf verbinden zijn omwille van eenvoud weggelaten.

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

Gegeven een equivalentierelatie op , kan voor iedere de verzameling van alle elementen waarmee in -relatie staat, gedefinieerd worden:

.

Deze verzameling wordt de equivalentieklasse van genoemd, of een equivalentieklasse van .

Equivalentieklassen hebben de volgende eigenschappen:

  • Voor alle geldt dat .
  • Iedere zit in precies één equivalentieklasse van .
  • Voor alle geldt: desda en in dezelfde equivalentieklasse van zitten.

De verzameling

van alle equivalentieklassen van wordt de quotiëntverzameling van onder genoemd.

Quotiëntverzamelingen hebben de volgende eigenschappen:

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

Het blijkt bovendien dat iedere partitie van ook een quotiëntverzameling van is onder een zekere equivalentierelatie op . Hieruit volgt, samen met de bovenstaande eigenschappen, dat er een een-op-een-correspondentie is tussen alle mogelijke partities van en alle mogelijke equivalentierelaties op .

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. Vier basale soorten orderelaties zijn partiële ordes, totale ordes, preordes en strikte zwakke ordes. Daarnaast bestaan er nog andere soorten orderelaties.

Grafen

Zie Grafentheorie voor het hoofdartikel over dit onderwerp.

Een homogene tweeplaatsige relatie kan ook geïnterpreteerd worden als een graaf. 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.

Voorbeelden van homogene tweeplaatsige relaties

De al eerder genoemde relatie 'houden van' is een voorbeeld van een homogene tweeplaatsige relatie op de verzameling van alle mensen.[4] Voorbeelden uit de wiskunde zijn legio. Hier volgen er enkele.

  • Is-groter-dan is een overbekend voorbeeld van een homogene tweeplaatsige relatie op getallen of, meer in het algemeen, op numerieke expressies. Merk op dat is-groter-dan een strikte totale orde is.
  • Is-gelijk-aan is zonder twijfel het meest voorkomende voorbeeld van een homogene tweeplaatsige relatie. De relatie is-gelijk-aan is bovendien het meest voor de hand liggende voorbeeld van een equivalentierelatie. Naïef bezien zou het domein van deze relatie de verzameling van alle objecten moeten zijn, of ten minste de verzameling van alle wiskundige objecten. Dit leidt echter tot de Russell-paradox. Om dit te omzeilen zouden er verschillende is-gelijk-aan-relaties gedefinieerd kunnen worden voor verschillende domeinen: een is-gelijk-aan voor getallen, een is-gelijk-aan voor geometrische figuren, etc. Een andere oplossing is de (tweeplaatsige) relatie te herdefiniëren in termen van klassen in plaats van verzamelingen.
  • Omdat afbeeldingen ook tweeplaatsige relaties zijn, is iedere identiteitsafbeelding een homogene tweeplaatsige relatie op . Iedere identiteitsafbeelding is zowel een een-op-een-correspondentie als een equivalentierelatie. Bovendien is de identiteitsafbeelding van de enige relatie op die zowel een een-op-een-correspondentie als een equivalentierelatie is. Overigens is de identiteitsafbeelding van de kleinst mogelijke equivalentierelatie op . De grootst mogelijke equivalentierelatie op is de universele tweeplaatsige endorelatie op .

Het aantal mogelijke homogene tweeplaatsige relaties

Aantal mogelijke tweeplaatsige relaties op een verzameling met elementen
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
OEIS A002416 A053763 A006905 A000798 A001035 A000670 A000142 A000110
  • Het aantal irreflexieve relaties is gelijk aan het aantal reflexieve relaties.
  • Het aantal intransitieve relaties is gelijk aan het aantal transitieve relaties.
  • 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.
  • Het aantal strikte totale ordes is gelijk aan het aantal totale ordes.
  • Het aantal (homogene) een-op-een-correspondenties is gelijk aan het aantal totale ordes.
  • Het aantal equivalentierelaties is gelijk aan het aantal partities van dezelfde verzameling.

Toepassingen buiten de wiskunde

In de economische wetenschap wordt het begrip voorkeur vaak gemodelleerd met tweeplaatsige relaties, namelijk met strikte zwakke ordes.

Dit artikel is op 2 april 2009 in deze versie opgenomen in de etalage.
{{bottomLinkPreText}} {{bottomLinkText}}
Tweeplaatsige relatie
Listen to this article