Binära relationer

En binär relation är en speciell typ av relation med aritet två. Typiska binära relationer är till exempel mindre än, likhet, delbarhet, större än och liknande.

Exempel

Binära relationer hör till de typiska och vanligt förekommande relationerna. Samtidigt har de några intressanta egenskaper som vi beskriver här.

Exempel på binära relationer är sambandet ”pappa — son”, paret ”fordon — antal hjul” eller det mer allmänna ”objekt — objektets egenskap”. Objektet kan vara ett djur och egenskapen antal ben, medellivslängd, antal hårstrån på huvudet och liknande.

En binär relation R mellan mängderna M₁ och M₂ kan vi definiera så här: R ⊆ M₁ × M₂. En binär relation är alltså en mängd av par, där mängden är en delmängd av den kartesiska produkten av de två mängderna som vi inför relationen mellan. Relationen ”pappa — son” kan alltså vara en relation mellan mängden av alla människor, mellan mängden av alla människor i Europa eller i Stockholm. Vi kan också begränsa mängden åt ett annat håll, vi kan säga att vi definierar relationen mellan mängden av alla män, inte människor i allmänhet.

För binära relationer använder vi vanligen en särskild beteckning. I stället för att skriva (a, b) ∈ R kan vi skriva aRb. Till exempel kan vi i stället för (3, 1) ∈ > skriva 3 > 1. På samma sätt för andra relationer. Skrivsättet aSb är alltså ekvivalent med (a, b) ∈ S.

Invers relation

En invers relation är den relation som är motsatt till den givna relationen. (Obs, förväxla den inte med komplementet till en relation.) Vilken relation är motsatsen till relationen mindre än? Större än. Om relationen mindre än innehåller elementet (4, 7), alltså 4 < 7, så blir det inversa elementet det motsatta: 7 > 4, i den inversa relationen finns det inversa paret (7, 4).

Om vi har en relation R ⊆ M₁ × M₂, konstruerar vi den inversa relationen R⁻¹ genom att ta alla element (a, b) ∈ R och sätta in deras inverser i R⁻¹. Om relationen R alltså innehåller elementet (a, b) måste relationen R⁻¹ innehålla elementet (b, a). Det gäller även åt andra hållet, om R⁻¹ innehåller elementet (b, a) måste relationen R innehålla elementet (a, b).

Om vi skulle definiera det, är relationen R⁻¹ invers till R om och endast om det gäller att:

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

Det gäller alltså att 6 < 8 om och endast om 8 > 6. På samma sätt för andra par.

Sammansättning av relationer

Binära relationer kan vi sätta ihop med varandra. Vi har två relationer, den första, R, är ”vara pappa till sin son” och den andra, S, ”vara bror till sin syster”. Relationen R innehåller alltså par (pappa, son), den andra relationen innehåller par (bror, syster).

Nu försöker vi sätta ihop relationerna. Vi får en ny relation som vi kallar R ∘ S, och den relationen innehåller elementet (a, c) om och endast om (a, b) ∈ R och samtidigt (b, c) ∈ S. Lägg märke till att b förekommer i båda elementen, en gång på andra platsen och sedan på första platsen i paret. Det är ett slags sammanbindande element för sammansättningen.

Exempel: R = {(Anton, Markus), (Per, Jakob)} och S = {(Markus, Elsa), (Markus, Alice), (Jakob, Maja)}. Anton är pappa till Markus, Per är pappa till Jakob. Markus har systrarna Elsa och Alice och Jakob har systern Maja.

Nu sätter vi ihop relationerna: R ∘ S. Vi söker ett par ur R som på sonens plats har någon som står som bror i relationen S. Till exempel dessa två par: (Anton, Markus) och (Markus, Elsa). Markus är det sammanbindande elementet, det behöver vi inte längre, och av de återstående namnen bildar vi ett nytt par: (Anton, Elsa). Relationen R ∘ S innehåller alltså paret (Anton, Elsa). Markus har ytterligare en syster, Alice, henne lägger vi också till i den sammansatta relationen: (Anton, Alice). Till sist återstår sonen Jakob. Han har systern Maja. Vi har alltså två par: (Per, Jakob) och (Jakob, Maja). Av dem skapar vi ett nytt element: (Per, Maja).

Resultatet är relationen: R ∘ S = {(Anton, Elsa), (Anton, Alice), (Per, Maja)}. Hur skulle vi kunna döpa den relationen? Förmodligen ”vara pappa till sin dotter”.

Här är hela definitionen en gång till:

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

Anmärkning: ibland används den omvända skrivningen, det vill säga för samma definition skulle man i stället för R ∘ S använda S ∘ R.