Binære relasjoner

En binær relasjon er en spesiell type relasjon med aritet to. Typiske binære relasjoner er for eksempel mindre enn, likhet, delelighet, større enn og så videre.

Eksempler

Binære relasjoner er en av de typiske og vanligste relasjonene. De har også noen interessante egenskaper som vi skal beskrive her.

Et eksempel på en binær relasjon kan være forholdet «far — sønn», paret «transportmiddel — antall hjul» eller det mer generelle «objekt — egenskap ved objektet». Objektet kan være et dyr og egenskapen antall bein, gjennomsnittlig levealder, antall hår på hodet og lignende.

En binær relasjon R mellom mengdene M₁ og M₂ kan vi definere slik: R ⊆ M₁ × M₂. En binær relasjon er altså en mengde av par, og denne mengden er en delmengde av det kartesiske produktet av de to mengdene som vi innfører relasjonen mellom. Relasjonen «far — sønn» kan altså være en relasjon mellom mengden av alle mennesker, mellom mengden av alle mennesker i Europa eller i Oslo. Vi kan også begrense mengden i en annen retning, og si at vi definerer relasjonen mellom mengden av alle menn, ikke mennesker generelt.

For binære relasjoner bruker vi vanligvis en spesiell skrivemåte. I stedet for å skrive (a, b) ∈ R kan vi skrive aRb. For eksempel kan vi i stedet for (3, 1) ∈ > skrive 3 > 1. På samme måte for andre relasjoner. Skrivemåten aSb er altså ekvivalent med (a, b) ∈ S.

Invers relasjon

Den inverse relasjonen er den motsatte relasjonen til den relasjonen vi har. (Obs, ikke forveksle med komplementet til en relasjon.) Hva er den motsatte relasjonen til relasjonen mindre enn? Større enn. Hvis relasjonen mindre enn inneholder elementet (4, 7), altså 4 < 7, blir det inverse elementet det motsatte: 7 > 4, og i den inverse relasjonen er det det inverse paret (7, 4).

Hvis vi har en relasjon R ⊆ M₁ × M₂, lager vi den inverse relasjonen R⁻¹ ved å ta alle elementene (a, b) ∈ R og legge inversen av dem inn i R⁻¹. Altså: hvis relasjonen R inneholder elementet (a, b), må relasjonen R⁻¹ inneholde elementet (b, a). Det gjelder også omvendt: hvis R⁻¹ inneholder elementet (b, a), må relasjonen R inneholde elementet (a, b).

Definert formelt er relasjonen R⁻¹ invers til R hvis og bare hvis:

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

Det gjelder altså at 6 < 8 hvis og bare hvis 8 > 6. På samme måte for andre par.

Sammensetning av relasjoner

Binære relasjoner kan vi sette sammen med hverandre. La oss si at vi har to relasjoner, den første, R, er «å være far til sønnen sin», og den andre, S, er «å være bror til søsteren sin». Relasjonen R inneholder altså parene (far, sønn), og den andre relasjonen inneholder parene (bror, søster).

Nå prøver vi å sette relasjonene sammen. Vi får en ny relasjon, som vi kaller R ∘ S, og denne relasjonen inneholder elementet (a, c) hvis og bare hvis (a, b) ∈ R og samtidig (b, c) ∈ S. Legg merke til at b forekommer i begge parene, én gang på andre plass og én gang på første plass i paret. Det er det som knytter dem sammen i sammensetningen.

Eksempel: R = {(Henrik, Filip), (Jakob, Lukas)} og S = {(Filip, Nora), (Filip, Emma), (Lukas, Ingrid)}. Henrik er far til Filip, Jakob er far til Lukas. Filip har søstrene Nora og Emma, og Lukas har søsteren Ingrid.

Nå setter vi sammen relasjonene: R ∘ S. Vi leter etter et par fra R som på sønnens plass har en som er oppført som bror i relasjonen S. For eksempel disse to parene: (Henrik, Filip) og (Filip, Nora). Filip er det forbindende elementet, det trenger vi ikke videre, og av de resterende navnene lager vi et nytt par: (Henrik, Nora). Relasjonen R ∘ S inneholder altså paret (Henrik, Nora). Filip har én søster til, Emma, og henne tar vi også med i den sammensatte relasjonen: (Henrik, Emma). Til slutt gjenstår sønnen Lukas. Han har søsteren Ingrid. Så vi har to par: (Jakob, Lukas) og (Lukas, Ingrid). Dermed lager vi et nytt element: (Jakob, Ingrid).

Resultatet er relasjonen: R ∘ S = {(Henrik, Nora), (Henrik, Emma), (Jakob, Ingrid)}. Hva kunne vi kalle denne relasjonen? Sannsynligvis «å være far til datteren sin».

Her er hele definisjonen en gang til:

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

Merknad: noen ganger brukes den motsatte skrivemåten, det vil si at for den samme definisjonen ville man brukt S ∘ R i stedet for R ∘ S.