Operasjoner på relasjoner

Siden relasjoner i virkeligheten er mengder, kan vi utføre de vanlige mengdeoperasjonene på dem.

Mengdeoperasjoner

I den forrige artikkelen definerte vi relasjoner som mengder. Med mengder kan vi utføre operasjoner som union, snitt eller differanse. La oss se på hva det betyr for relasjoner.

Først må vi innføre en betingelse, for vi kan ikke utføre disse operasjonene mellom hvilke som helst relasjoner. Hvis vi har relasjonene «mindre enn» og «å være et partall», gir ikke disse operasjonene mening, for den første relasjonen er binær, mens den andre er unær. For at vi skal få en relasjon igjen etter en mengdeoperasjon, må alle relasjonene som er med, ha samme aritet, altså må alle være n-ære for samme n.

Union

La oss si at vi har relasjonene «mindre enn» og «likhet». Hva skjer hvis vi tar unionen av disse relasjonene? I relasjonen mindre enn har vi alle par (a, b) der a < b. I likhetsrelasjonen har vi alle par (a, b) der a = b. I relasjonen < ∪ = er det altså alle par (a, b) der a < b eller a = b. Tallet a er enten mindre enn tallet b eller lik det. En slik relasjon kjenner vi, og vi kaller den «mindre enn eller lik» og skriver den ≤.

Hvis vi har relasjonene R₁ og R₂, blir unionen relasjonen R = R₁ ∪ R₂, og for den gjelder: elementet r er i relasjonen R hvis det er i relasjonen R₁ eller i relasjonen R₂. Med andre ord er det med i den resulterende relasjonen hvis det var med i minst en av relasjonene vi tok unionen av.

Snitt

Ved unionen fikk vi en ny relasjon der elementene var elementer i minst en av relasjonene. For snittet er det likt, bare at elementene må være med i begge relasjonene.

Hvis vi igjen tar relasjonene mindre enn og likhet (over de reelle tallene) og lager snittet av dem — hva får vi? Vi skulle få elementene som er i relasjonen mindre enn og samtidig er like. Men et slikt tilfelle kan ikke oppstå, for hvis a < b, gjelder aldri a = b. Vi ville fått den tomme relasjonen.

La oss si at vi har disse to relasjonene: «delelighet uten rest» og en binær relasjon som inneholder par av elementer (a, b) der a er et oddetall og b er et partall. La oss jobbe over de naturlige tallene. I den første relasjonen ville det vært tallpar som (5, 15), (6, 30), (3, 123) — det andre tallet må alltid være delelig med det første tallet. I den andre relasjonen er det slike tallpar der det første tallet er et oddetall og det andre et partall: (1, 4), (5, 14), (3, 24) osv. Snittet av disse relasjonene blir en ny relasjon R, og den inneholder slike par (a, b) der b er delelig med a og samtidig a er et oddetall og b er et partall. For eksempel: (5, 30) eller (3, 24).

Differanse

Hvis vi har to relasjoner R₁ og R₂, blir differansen R₁ − R₂ en ny relasjon som består av elementene som er i R₁, men ikke i R₂. Vi kan igjen gå tilbake til relasjonene mindre enn eller lik og likhet. Hvis relasjonen R₁ er mindre enn eller lik og relasjonen R₂ er likhet, får vi med differansen R₁ − R₂ elementene som er i relasjonen mindre enn eller lik, men ikke i likhetsrelasjonen. Vi får altså parene (a, b) der a ≤ b og samtidig ikke a = b. Med andre ord får vi relasjonen mindre enn: <.

Komplement til en relasjon

Til hver relasjon kan vi finne komplementet til relasjonen. Elementene i komplementet til relasjonen R er alle elementer som ikke hører til den opprinnelige relasjonen R. For eksempel er komplementet til likhetsrelasjonen (altså =) ulikhetsrelasjonen. I den første relasjonen har vi alle par av elementer som er like (for eksempel 5 = 5), og i komplementet har vi alle par av tall som ikke er like (for eksempel 5 ≠ 6).

Det eneste du må passe på når du bestemmer komplementet til en relasjon, er den underliggende mengden — mengden som relasjonen hører til. Likhetsrelasjonen kan vi definere på de naturlige tallene, de hele tallene, de reelle tallene, men gjerne også på mengden av alle mennesker på jorden.

Hvis vi har en binær relasjon R fra mengdene M₁ og M₂: R ⊆ M₁ × M₂, gjelder det at komplementet til relasjonen, la oss kalle det S, er lik S = (M₁ × M₂) ∖ R: det er de elementene som er i det kartesiske produktet av de underliggende mengdene, men ikke i relasjonen R. På tilsvarende måte for relasjoner med andre ariteter.