Hoofdmenu openen
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 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 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” genoemd. Historisch gezien werden met “relaties” oorspronkelijk ook enkel tweeplaatsige relaties aangeduid. Later is het begrip uitgebreid. Zie het artikel Relatie voor meer over de oorsprong en de geschiedenis van het begrip.

Inhoud

InleidingBewerken

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.

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   aan persoon   indien (en enkel indien) persoon   van persoon   houdt. Aldus wordt 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. 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, ten slotte, is iemand die aan zichzelf gekoppeld is.

In de wiskunde zijn tweeplaatsige relaties alomtegenwoordig. Ze worden gebruikt om is groter dan en is deelbaar door in de rekenkunde, is congruent aan in de meetkunde en vele andere begrippen mee te definiëren. Daarnaast wordt de functie, een van de belangrijkste begrippen in de wiskunde, meestal gedefinieerd als een speciaal geval van een tweeplaatsige relatie. Ook andere exacte wetenschappen passen tweeplaatsige relaties veelvuldig toe in uiteenlopende gebieden. In de informatica worden ze 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.

DefinitieBewerken

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  .

Soms wordt de tweeplaatsige relatie simpelweg 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 genoemd worden of uit de context blijken. Strikt genomen wordt in dit geval niet het begrip tweeplaatsige relatie gedefinieerd, maar het begrip tweeplaatsige relatie overen …, 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  , 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 Russell-paradox leidt.

TerminologieBewerken

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 koppel   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 bedoeld wordt, dan zegt men ook simpelweg 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  -relatie staat tot  .

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  -relatie staat tot  .

NotatieBewerken

De uitspraak “  staat in  -relatie tot  ” wordt op verschillende manieren genoteerd:

  • (functienotatie)  
  • (infixnotatie)  
  • (Poolse notatie)  

De functienotatie komt overeen met de karakteristieke functie van de grafiek van  .

VoorbeeldenBewerken

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.[2]

Voor een ander voorbeeld worden eerst de verzamelingen waarvoor de relatie gedefinieerd wordt, 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 helemaal niets (dat element is van  ) bezit.

Eigenschappen van tweeplaatsige relatiesBewerken

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

  • Dat   links-volledig is, betekent dat voor alle   er een   is, zodanig dat  .
  • Dat   rechts-volledig of surjectief is, betekent dat voor alle   er een   is, zodanig dat  .
  • Dat   links-definiet of 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  .
  • Dat   rechts-definiet of functioneel 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  .
  • Dat   bijectief is, betekent dat   links-volledig, rechts-volledig, links-definiet en rechts-definiet is.

Een functionele tweeplaatsige relatie wordt een afbeelding genoemd. Een afbeelding waarvan het het codomein een lichaam (ook wel veld) is, is een functie.[4]

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” echter als synoniem voor “(tweeplaatsige) 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 relatiesBewerken

Doorsnede en verenigingBewerken

  Zie Doorsnede en Vereniging voor de doorsnede en de vereniging van verzamelingen in plaats van relaties.

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 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.

ComplementBewerken

  Zie Complement voor het complement van verzamelingen in plaats van relaties.

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 samenstellingBewerken

  Zie ook: Samengestelde relatie

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  .

Voor alle tweeplaatsige relaties   over   en  ,   over   en  , en   over   en   geldt dat

(associativiteit)  .

Daarom wordt meestal simpelweg   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 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 converseBewerken

  Zie ook: Inverse

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 operatiesBewerken

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.)
 ,
 .

Een-op-een-correspondentiesBewerken

Een een-op-een-correspondentie of bijectie is een bijectieve tweeplaatsige relatie. De een-op-een-correspondentie is een veelgebruikte soort tweeplaatsige relatie. In de algebra is het isomorfisme bijvoorbeeld (een specifiek geval van) een een-op-een-correspondentie en in de topologie is het homeomorfisme (een specifiek geval van) een een-op-een-correspondentie.

In wiskundige bewijzen worden een-op-een-correspondenties 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.

Homogene tweeplaatsige relatiesBewerken

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 relatiesBewerken

Zij   een homogene tweeplaatsige relatie op  .

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

Operaties op homogene tweeplaatsige relatiesBewerken

Restrictie en extensieBewerken

  Zie Restrictie voor de restrictie van functies in plaats van relaties.

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 reductieBewerken

  Zie ook: Afsluiting

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  .

EquivalentierelatiesBewerken

  Zie ook: Equivalentierelatie
 
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:[5]

  • 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:[5]

  • 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  .

OrderelatiesBewerken

  Zie ook: Ordetheorie

Een belangrijke toepassing van (homogene) tweeplaatsige relaties is het beschrijven van orde door middel van orderelaties. Vier basale soorten orderelaties zijn partiële ordes, totale ordes, preordes en strikte zwakke ordes. Daarnaast bestaan er nog andere soorten orderelaties.

GrafenBewerken

  Zie ook: Grafentheorie

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 relatiesBewerken

De al eerder genoemde relatie houden van is een voorbeeld van een homogene tweeplaatsige relatie op de verzameling van alle mensen.[6] 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 relatiesBewerken

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 wiskundeBewerken

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

Zie ookBewerken

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