Binaire relatie

Een binaire relatie is een bijzonder type relatie met ariteit twee. Typische binaire relaties zijn bijvoorbeeld kleiner dan, gelijkheid, deelbaarheid, groter dan enzovoort.

Voorbeelden

Een binaire relatie is een van de typische en vaak voorkomende relaties. Ze heeft ook een paar interessante eigenschappen, die we hier beschrijven.

Voorbeelden van binaire relaties zijn: het verband “vader — zoon”, het paar “vervoermiddel — aantal wielen” of het algemenere “object — eigenschap van het object”. Het object kan een dier zijn en de eigenschap het aantal poten, de gemiddelde levensduur, het aantal haren op de kop enzovoort.

Een binaire relatie R tussen de verzamelingen M₁ en M₂ kunnen we zo definiëren: R ⊆ M₁ × M₂. Een binaire relatie is dus een verzameling van paren, waarbij die verzameling een deelverzameling is van het cartesisch product van de twee verzamelingen waartussen we de relatie invoeren. De relatie “vader — zoon” kan dus een relatie zijn tussen de verzamelingen van alle mensen, tussen de verzamelingen van alle mensen in Europa of in Utrecht. We kunnen de verzameling ook in een andere richting beperken: we kunnen zeggen dat we de relatie definiëren tussen de verzamelingen van alle mannen, niet van mensen in het algemeen.

Voor binaire relaties gebruiken we meestal een speciale notatie. In plaats van (a, b) ∈ R te schrijven, kunnen we aRb schrijven. In plaats van (3, 1) ∈ > kunnen we bijvoorbeeld 3 > 1 schrijven. Net zo voor de andere relaties. De notatie aSb is dus equivalent met de notatie (a, b) ∈ S.

Inverse relatie

De inverse relatie is de relatie die tegengesteld is aan de huidige relatie. (Let op, niet te verwarren met het complement van een relatie.) Wat is de tegengestelde relatie van de relatie kleiner dan? Groter dan. Als de relatie kleiner dan het element (4, 7) bevat, dus 4 < 7, dan is het inverse element het omgekeerde: 7 > 4, en in de inverse relatie zit het omgekeerde paar (7, 4).

Als we een relatie R ⊆ M₁ × M₂ hebben, construeren we de inverse relatie R⁻¹ door alle elementen (a, b) ∈ R te nemen en hun omgekeerde in R⁻¹ te zetten. Als de relatie R dus het element (a, b) bevat, moet de relatie R⁻¹ het element (b, a) bevatten. Het geldt ook omgekeerd: als R⁻¹ het element (b, a) bevat, dan moet de relatie R het element (a, b) bevatten.

Formeel gedefinieerd: de relatie R⁻¹ is de inverse van R precies dan als geldt:

$$\mathrm{\forall }a\in M_1\mathrm{\forall }b\in M_2:(a,b)\in R\iff (b,a)\in R^{-1}$$

Er geldt dus dat 6 < 8 precies dan als 8 > 6. Net zo voor andere paren.

Samenstelling van relaties

Binaire relaties kunnen we met elkaar samenstellen. We nemen twee relaties: de eerste, R, is “de vader van zijn zoon zijn” en de tweede, S, is “de broer van zijn zus zijn”. De relatie R bevat dus paren (vader, zoon), de tweede relatie bevat paren (broer, zus).

Nu proberen we de relaties samen te stellen. Er ontstaat een nieuwe relatie, die we R ∘ S noemen, en deze relatie bevat het element (a, c) precies dan als (a, b) ∈ R en tegelijk (b, c) ∈ S. Merk op dat b in beide elementen voorkomt, één keer op de tweede plaats en dan op de eerste plaats van het paar. Dat is een soort verbindingselement van de samenstelling.

Voorbeeld: R = {(Bram, Sem), (Lucas, Daan)} en S = {(Sem, Lotte), (Sem, Julia), (Daan, Emma)}. Bram is de vader van Sem, Lucas is de vader van Daan. Sem heeft de zussen Lotte en Julia en Daan heeft een zus Emma.

Nu stellen we de relaties samen: R ∘ S. We zoeken een paar uit R waarvan de zoon iemand is die in de relatie S als broer voorkomt. Bijvoorbeeld deze twee paren: (Bram, Sem) en (Sem, Lotte). Sem is het verbindingselement, dat hebben we verder niet nodig en van de overgebleven namen maken we een nieuw paar: (Bram, Lotte). De relatie R ∘ S bevat dus het paar (Bram, Lotte). Sem heeft nog een zus, Julia, die voegen we ook toe aan de samengestelde relatie: (Bram, Julia). Tot slot blijft zoon Daan over. Die heeft een zus Emma. We hebben dus twee paren: (Lucas, Daan) en (Daan, Emma). Daarmee maken we nog een element: (Lucas, Emma).

Het resultaat is de relatie: R ∘ S = {(Bram, Lotte), (Bram, Julia), (Lucas, Emma)}. Hoe zouden we deze relatie kunnen noemen? Waarschijnlijk “de vader van zijn dochter zijn”.

Nog een keer de hele definitie:

$$(a,c)\in (R\circ S)\iff \mathrm{\exists }b(a,b)\in R\wedge (b,c)\in S$$

Opmerking: soms wordt de omgekeerde notatie gebruikt, dat wil zeggen dat voor dezelfde definitie in plaats van R ∘ S de notatie S ∘ R zou worden gebruikt.