Binære relasjoner på en mengde

Med en binær relasjon på en mengde mener vi en binær relasjon definert mellom to like mengder.

Eksempler

En binær relasjon på en mengde er en spesiell type binær relasjon der begge de underliggende mengdene er like. En binær relasjon på en mengde er altså en relasjon R slik at R ⊆ M × M.

Relasjonen «større enn» er en binær relasjon på en mengde, fordi vi jobber med tall på begge sider. Det gjelder altså at > ⊆ ℝ × ℝ. Relasjonen «far — antall barn» er ikke en binær relasjon på en mengde, fordi fedrene velges fra mengden av alle mennesker, mens antall barn velges fra en tallmengde.

Egenskaper

En binær relasjon R på en mengde M kan ha noen interessante egenskaper. Vi sier at relasjonen R er…

• refleksiv hvis det for alle a ∈ M gjelder at (a, a) ∈ R.
• symmetrisk hvis det for alle a, b ∈ M gjelder at hvis (a, b) ∈ R, så også (b, a) ∈ R.
• antisymmetrisk hvis det for alle a, b ∈ M gjelder at hvis (a, b) ∈ R og samtidig (b, a) ∈ R, så er a = b.
• transitiv hvis det for alle a, b, c ∈ M gjelder at hvis (a, b) ∈ R og samtidig (b, c) ∈ R, så er også (a, c) i R.

Eksempler på refleksivitet

Refleksivitet betyr at et element er i relasjon med seg selv. Et typisk eksempel er likhet. Hvis vi har definert likhet på de naturlige tallene, gjelder det sikkert for et hvilket som helst element a at a = a. Et annet eksempel kan være delelighet. Der gjelder det igjen at tallet a er delelig med seg selv, altså er paret (a, a) i delelighetsrelasjonen (sju går opp i sju).

Relasjonen mindre enn er derimot ikke refleksiv, for det gjelder ikke at a < a. Det er ikke mulig, sju kan ikke være mindre enn sju. På samme måte med relasjonen å være far til barnet sitt — jeg kan ikke være min egen far. Slike relasjoner er ikke refleksive.

Det er viktig at refleksivitet må gjelde for alle elementer, det er ikke nok å finne bare noen. Ta for eksempel relasjonen «å like noen». Jeg kan like andre, for eksempel billettkontrolløren, men jeg kan også like meg selv. Det finnes sikkert et menneske som liker seg selv. Men like sikkert finnes det et menneske som ikke liker seg selv. En slik relasjon er da ikke refleksiv — alle mennesker måtte ha likt seg selv.

Eksempler på symmetri

For en symmetrisk relasjon gjelder det at hvis et par er i relasjonen, så er også det inverse paret i relasjonen. For eksempel relasjonen å være søsken. Hvis Lukas er søsken til Nora, så er også Nora søsken til Lukas. Av tallrelasjoner kunne det være relasjonen «å være det motsatte tallet». Da mener jeg parene 2 og −2 eller −7 og 7. Det er slike to tall som har summen null. En slik relasjon er symmetrisk, fordi rekkefølgen rett og slett ikke spiller noen rolle: (2, −2) og (−2, 2) er fortsatt motsatte tall av hverandre og har summen null.

En relasjon som ikke er symmetrisk, er mindre enn (over de reelle tallene). Den har ikke et eneste symmetrisk element, for det kan aldri gjelde at a < b og samtidig b < a. Hvis 5 < 15, kan ikke 15 < 5 gjelde. Relasjonen «å være far til sønnen sin» er heller ikke symmetrisk. Du kan være far til sønnen din, men da kan ikke sønnen være far til faren sin.

Denne egenskapen må igjen gjelde i alle tilfeller. Hvis relasjonen «å like noen» (på mengden av alle mennesker) skal være symmetrisk, så må Ingrid, hvis jeg liker henne, samtidig like meg. Og siden hun ikke engang kjenner meg, kan jeg ikke si at hun liker meg, noe som er synd, og da er ikke relasjonen symmetrisk. Noe som også er synd.

Eksempler på antisymmetri

Et klassisk eksempel på en antisymmetrisk relasjon er mindre enn eller lik. Antisymmetri sier at hvis elementene (a, b) og (b, a) er i relasjonen, så må de være like, a = b. Relasjonen mindre enn eller lik oppfyller dette. Når gjelder a ≤ b og samtidig b ≤ a? Bare hvis a = b. Når vi setter inn tall: gjelder 3 ≤ 5 og samtidig 5 ≤ 3? Nei. Men 4 ≤ 4 og samtidig 4 ≤ 4 gjelder.

Et eksempel på en relasjon som ikke er antisymmetrisk, kan være par av ord som har samme lengde, for eksempel (lørdag, hammer). En slik relasjon er ikke antisymmetrisk, for vi finner et par av ord som er i relasjonen, det inverse elementet er også i relasjonen, og likevel er de to ordene ulike. Altså det nevnte elementet (lørdag, hammer) og inversen: (hammer, lørdag). Begge er tydeligvis i relasjonen vår, men samtidig er lørdag ≠ hammer, så relasjonen er ikke antisymmetrisk.

Eksempel på transitivitet

Relasjonen mindre enn er transitiv. Transitivitet sier at hvis 3 < 4 og samtidig 4 < 5, så må sikkert også 3 < 5 gjelde. For mange relasjoner er dette en ganske naturlig egenskap. På samme måte for eksempelet med ord av samme lengde. Hvis (hammer, lørdag) er i relasjonen og (lørdag, planke) er i relasjonen, så er også ordene (hammer, planke) i relasjonen.

Relasjonen å være far til en sønn er ikke transitiv. Hvis Henrik er far til Jakob og Jakob er far til Filip, så er ikke Henrik far til Filip, han er bestefaren hans. På samme måte er relasjonen å like noen ikke transitiv. Hvis jeg liker Nora og Nora liker mannen sin, betyr ikke det at jeg også liker mannen til Nora.

Transitivitet er også et tema for vanlige terninger. La oss anta relasjonen terning A er bedre enn terning B hvis det på terning A oftere (med større sannsynlighet) kommer et høyere tall enn på terning B. Er en slik relasjon transitiv? Det svarer artikkelen om ikke-transitive terninger på.

Ekvivalens og ordning

Noen spesielle typer binære relasjoner har egne navn:

• Ekvivalensrelasjon er en relasjon som er refleksiv, symmetrisk og transitiv.
• Ordningsrelasjon er en relasjon som er refleksiv, antisymmetrisk og transitiv.