Binaire relatie op een verzameling

Onder een binaire relatie op een verzameling verstaan we een binaire relatie die is gedefinieerd tussen een verzameling en diezelfde verzameling.

Voorbeelden

Een binaire relatie op een verzameling is een bijzonder type binaire relatie, waarbij beide onderliggende verzamelingen dezelfde zijn. Een binaire relatie op een verzameling is dus een relatie R zodat R ⊆ M × M.

De relatie “groter dan” is een binaire relatie op een verzameling, omdat we aan beide kanten met getallen werken. Er geldt dus > ⊆ ℝ × ℝ. De relatie “vader — aantal kinderen” is geen binaire relatie op een verzameling, omdat we de vader kiezen uit de verzameling van alle mensen, terwijl we het aantal kinderen kiezen uit een of andere getalverzameling.

Eigenschappen

Een binaire relatie R op een verzameling M kan een paar interessante eigenschappen hebben. We zeggen dat de relatie R…

• reflexief is als voor alle a ∈ M geldt dat (a, a) ∈ R.
• symmetrisch is als voor alle a, b ∈ M geldt dat als (a, b) ∈ R, dan ook (b, a) ∈ R.
• antisymmetrisch is als voor alle a, b ∈ M geldt dat als (a, b) ∈ R en tegelijk ook (b, a) ∈ R, dan a = b.
• transitief is als voor alle a, b, c ∈ M geldt dat als (a, b) ∈ R en tegelijk (b, c) ∈ R, dan ook (a, c) in R zit.

Voorbeelden van reflexiviteit

Reflexiviteit betekent dat een element in relatie staat met zichzelf. Een typisch voorbeeld is gelijkheid. Als we gelijkheid op de natuurlijke getallen hebben gedefinieerd, dan geldt zeker voor elk element a: a = a. Een ander voorbeeld is deelbaarheid. Daar geldt weer dat het getal a deelbaar is door zichzelf, dus het paar (a, a) zit in de deelbaarheidsrelatie (zeven deelt zeven).

De relatie kleiner dan is echter niet reflexief, want het is niet zo dat a < a. Dat kan niet, zeven kan niet kleiner zijn dan zeven. Net zo de relatie de vader van zijn kind zijn — ik kan niet mijn eigen vader zijn. Zulke relaties zijn niet reflexief.

Het is belangrijk dat reflexiviteit voor alle elementen moet gelden, het is niet genoeg om er maar een paar te vinden. Neem bijvoorbeeld de relatie “iemand aardig vinden”. Ik kan iemand aardig vinden, bijvoorbeeld de conducteur, maar ik kan ook mezelf aardig vinden. Er is vast iemand die zichzelf aardig vindt. Maar er is net zo goed iemand die zichzelf niet aardig vindt. Zo'n relatie is dan niet reflexief — alle mensen zouden zichzelf aardig moeten vinden.

Voorbeelden van symmetrie

Bij een symmetrische relatie geldt dat als een paar in de relatie zit, ook het omgekeerde paar in de relatie zit. Bijvoorbeeld de relatie broer of zus zijn. Als Daan een broer of zus is van Lotte, dan is Lotte ook een broer of zus van Daan. Uit de getalrelaties zou het de relatie “tegengesteld getal zijn” kunnen zijn. Daarmee bedoel ik de paren 2 en −2 of −7 en 7. Het zijn twee getallen waarvan de som nul is. Zo'n relatie is symmetrisch, want de volgorde doet er gewoon niet toe: (2, −2) en (−2, 2) zijn nog steeds elkaars tegengestelde en hun som is nul.

Een relatie die niet symmetrisch is, is kleiner dan (over de reële getallen). Die heeft geen enkel symmetrisch element, want er kan nooit gelden a < b en tegelijk b < a. Als 5 < 15, dan kan niet gelden 15 < 5. Verder is ook de relatie “de vader van zijn zoon zijn” niet symmetrisch. Je kunt de vader van je zoon zijn, maar dan kan de zoon niet de vader van zijn vader zijn.

Ook deze eigenschap moet weer in alle gevallen gelden. Als de relatie “iemand aardig vinden” (op de verzameling van alle mensen) symmetrisch zou moeten zijn, dan zou, als ik Sophie aardig vind, Sophie mij tegelijk ook aardig moeten vinden. En omdat ze mij niet eens kent, kan ik niet zeggen dat ze mij aardig vindt, wat jammer is, en de relatie is niet symmetrisch. Wat ook jammer is.

Voorbeelden van antisymmetrie

Een klassiek voorbeeld van een antisymmetrische relatie is kleiner dan of gelijk aan. Antisymmetrie zegt ons dat als de elementen (a, b) en (b, a) in de relatie zitten, dat alleen kan als ze aan elkaar gelijk zijn, a = b. De relatie kleiner dan of gelijk aan voldoet daaraan. Wanneer geldt a ≤ b en tegelijk b ≤ a? Alleen als a = b. Als we invullen: geldt 3 ≤ 5 en tegelijk 5 ≤ 3? Nee. Maar 4 ≤ 4 en tegelijk 4 ≤ 4 geldt wel.

Een voorbeeld van een relatie die niet antisymmetrisch is, kunnen paren woorden zijn die even lang zijn, bijvoorbeeld (zaterdag, houtbijl). Zo'n relatie is niet antisymmetrisch, want we vinden een paar woorden dat in de relatie zit, het omgekeerde element zit ook in de relatie en toch zijn de twee woorden verschillend. Neem het genoemde element (zaterdag, houtbijl) en zijn omgekeerde: (houtbijl, zaterdag). Beide zitten duidelijk in onze relatie, maar toch is zaterdag ≠ houtbijl, dus de relatie is niet antisymmetrisch.

Voorbeeld van transitiviteit

Transitief is de relatie kleiner dan. Transitiviteit zegt ons dat als 3 < 4 en tegelijk 4 < 5, dan zeker ook moet gelden 3 < 5. Voor veel relaties is dat een vrij natuurlijke eigenschap. Net zo bij het voorbeeld met woorden van dezelfde lengte. Als (houtbijl, zaterdag) in de relatie zit en (zaterdag, houtblok) in de relatie zit, dan zit ook het paar woorden (houtbijl, houtblok) in de relatie.

Niet transitief is de relatie de vader van een zoon zijn. Als Bram de vader van Sem is en Sem de vader van Lucas, dan is Bram niet de vader van Lucas, maar zijn grootvader. Net zo is de relatie iemand aardig vinden niet transitief. Als ik Sophie aardig vind en Sophie vindt haar man aardig, dan betekent dat niet dat ik ook de man van Sophie aardig vind.

Over transitiviteit gaat het ook bij klassieke dobbelstenen. Neem de relatie dobbelsteen A is beter dan dobbelsteen B als bij dobbelsteen A vaker (met grotere kans) een hoger getal valt dan bij dobbelsteen B. Is zo'n relatie transitief? Daar geeft het artikel niet-transitieve dobbelstenen antwoord op.

Equivalentie en ordening

Sommige bijzondere typen binaire relaties hebben ook een eigen naam:

• Een equivalentierelatie is een relatie die reflexief, symmetrisch en transitief is.
• Een ordening is een relatie die reflexief, antisymmetrisch en transitief is.