Ekvivalensrelasjoner

En ekvivalensrelasjon er en binær relasjon på en mengde som er refleksiv, symmetrisk og transitiv.

Motivasjon

En ekvivalensrelasjon er en slags oppmykning av likhetsrelasjonen. Vi kan alltid avgjøre om to elementer i en mengde er like, altså om a = b. Men noen ganger er det nyttig å finne ut om to elementer bare ligner på hverandre, ikke nødvendigvis er like. Eller — om de har en viktig egenskap felles. For eksempel kan vi si at to bøker ligner på hverandre hvis de har samme sjanger — eller ved hjelp av ekvivalens: to bøker er ekvivalente hvis de har samme sjanger.

Hva ville vi forvente av en slik ekvivalens? La oss ta et annet eksempel. To ord er like/ekvivalente hvis de er like lange.

Vi ville vel forvente at hvis vi måler likheten mellom to identiske ord, kommer vi fram til at de er like. Altså må det for alle ord gjelde at de er like/ekvivalente med seg selv. På relasjonenes språk: en ekvivalensrelasjon må være refleksiv.

Videre, hvis ordet «bekk» er likt/ekvivalent med ordet «Nora», så forventer vi sikkert at ordet «Nora» også er ekvivalent med ordet «bekk». Med andre ord spiller rekkefølgen ingen rolle. På relasjonenes språk: en ekvivalensrelasjon må være symmetrisk.

Og til slutt, hvis ordet «tann» er likt/ekvivalent med ordet «fugl», og ordet «fugl» er ekvivalent med ordet «foss», så forventer vi at også ordene «tann» og «foss» er ekvivalente. Altså må en ekvivalensrelasjon også være transitiv.

Mer forventer vi ikke av en ekvivalens.

Eksempler

Flere eksempler på ekvivalenser:

• Å bo i samme by. Henrik bor sikkert i samme by som Henrik (refleksivitet). Hvis Henrik bor i samme by som Filip, så bor også Filip i samme by som Henrik (symmetri). Og hvis Filip bor i samme by som Lukas, så bor også Henrik i samme by som Lukas (transitivitet).
• Sanger med samme låtskriver. Sangen «Sol over fjorden» har sikkert samme låtskriver som sangen «Sol over fjorden» (refleksivitet). Hvis sangene «Sol over fjorden» og «Sang for vinden» har samme låtskriver, så har også «Sang for vinden» og «Sol over fjorden» samme låtskriver (symmetri). Og hvis «Sang for vinden» og «Reise mot nord» har samme låtskriver, så har også «Sol over fjorden» og «Reise mot nord» samme låtskriver (transitivitet).
• (a, b) ∈ R hvis og bare hvis a − b er et partall; a, b er hele tall. Refleksivitet: a − a = 0, null er et partall. Symmetri: la c = a − b. Da er b − a = −(a − b) = −c. Hvis c er et partall, må også −c være et partall. Transitivitet: la p = a − b, og videre q = b − c. Vi vet at både p og q er partall. Nå skal vi bevise at a − c er et partall. I denne likningen setter vi inn for c verdien c = b − q: a − (b − q), som er lik a − b + q. Fra forutsetningene vet vi at a − b er et partall. Hvis vi legger til enda et partall q til et partall, får vi igjen et partall.
• Likhet. Likhet er en ekvivalens, og det er samtidig den minste ekvivalensen på en vilkårlig mengde M.

Triviell ekvivalens

Vi har en ikke-tom mengde M. Hva er den minst mulige ekvivalensen R på mengden M? Den minst mulige delmengden av det kartesiske produktet M × M er den tomme mengden ∅. Oppfyller den tomme mengden betingelsene for en ekvivalens?

Den er sikkert symmetrisk, for siden relasjonen R ikke har noen elementer, er betingelsen for symmetri automatisk og trivielt oppfylt. På samme måte med transitivitet. Problemet er refleksiviteten. Definisjonen sier at det for alle elementer x i mengden M gjelder at (x, x) ∈ R. Er dette oppfylt? Mengden M er ikke tom, så den inneholder et element, for eksempel q. Er paret (q, q) i relasjonen R? Nei. Relasjonen R er altså ikke refleksiv.

Hva er den minste relasjonen som oppfyller refleksivitet? Likhetsrelasjonen. Relasjonen R må inneholde minst parene (x, x) for alle elementer i M. Det er nettopp identitetsrelasjonen. Er en slik relasjon symmetrisk? Det er lett å se at den er det. På samme måte er det lett å se at den også er transitiv. Den minste ekvivalensrelasjonen på mengden M er altså identitetsrelasjonen, som vi skriver id_M, og den inneholder parene (x, x) for alle x ∈ M.

Hva er den største mulige ekvivalensen på mengden M? Den største delmengden er hele mengden M × M. Oppfyller den betingelsene for en ekvivalens? Det er vel trivielt å se at den gjør det.

Ekvivalensklasse

Hver ekvivalens deler mengden M opp i et system av disjunkte mengder, som vi så kaller ekvivalensklasser.

La oss si at vi har mengden av alle ord M og ekvivalensen R like lange ord. Altså (a, b) ∈ R hvis og bare hvis ordene a og b har samme lengde. Denne ekvivalensen deler mengden av ord opp i flere mindre mengder, som alltid inneholder ord med samme lengde. De enkelte ekvivalensklassene kan vi skille med en senket indeks, som samtidig angir lengden på ordene i den aktuelle mengden:

• M₁ = {i, å, a, …}
• M₂ = {på, av, vi, du, de, …}
• M₃ = {men, for, den, hit, …}
• M₄ = {fisk, park, hest, vind, …}
• …

Legg merke til to ting: 1) de enkelte mengdene er disjunkte, de har ikke noe element felles. 2) alle elementene i hver enkelt mengde er ekvivalente med hverandre. Alle ordene i mengden M₃ er ekvivalente med hverandre, fordi alle ordene har lengde tre, altså samme lengde, og det er betingelsen for ekvivalens.

Hvert element bestemmer dessuten entydig sin ekvivalensklasse. Det skriver vi vanligvis med notasjonen M[x], der x ∈ M. Hvis vi skrev M[men], ville vi entydig bestemme ekvivalensklassen som vi allerede har kalt M₃.

Hvordan finner vi egentlig ekvivalensklassen hvis vi kjenner et x ∈ M? Vi går gjennom alle elementene i M og finner ut hvilke av dem som er ekvivalente med elementet x. Det blir alle elementene som er med i ekvivalensklassen M[x].

For M[men] ville vi gå gjennom alle ordene i M og beholde de ordene som har lengde tre i M₃.

Definisjon og egenskaper til ekvivalensklassen

Ekvivalensklassen kan vi definere slik. La oss si at vi har en mengde M og en ekvivalens R definert på den. Da mener vi med klassen i oppdelingen som inneholder elementet x ∈ M:

$$M[x]=\{y\in M;(x,y)\in R\}$$

Definisjonen sier at det er alle y som er ekvivalente med det oppgitte elementet x. Siden ekvivalensrelasjonen er refleksiv, kommer også selve elementet x med på denne måten — fordi x er ekvivalent med seg selv.

Med oppdelingen etter en ekvivalens mener vi mengden av alle ekvivalensklasser. Oppdelingen av mengden av alle ord ville altså være mengden {M₁, M₂, M₃, …}.

Grunnleggende egenskaper ved ekvivalensklasser:

• (a, b) ∈ R hvis og bare hvis M[a] = M[b]. Hvis vi har to elementer a, b som er ekvivalente, må ekvivalensklassene deres være like.
• Omvendt, hvis (a, b) ∈ R ikke gjelder, så er også M[a] ≠ M[b], mer presist M[a] ∩ M[b] = ∅. Hvis vi har to elementer som ikke er ekvivalente, er klassene deres i oppdelingen disjunkte.
• Unionen av alle ekvivalensklassene må gi den opprinnelige mengden M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Den foregående skrivemåten gjelder bare for et endelig antall ekvivalensklasser, men generelt kan det være uendelig mange.)

Eksempler på oppdelinger etter ekvivalens

Første eksempel, oddetall og partall:

La oss si at vi har en enkel ekvivalens R definert på de naturlige tallene N. (a, b) ∈ R hvis og bare hvis både a og b er oddetall eller både a og b er partall. Eksempler på elementer: (1, 7), (13, 9), (4, 6), (8, 136). Nå bestemmer vi oppdelingen av denne ekvivalensen i ekvivalensklasser.

Vi tar det steg for steg. Hva blir klassen N[1] lik? Vi må finne alle tall som er ekvivalente med tallet en. Ifølge betingelsen for ekvivalens er det alle oddetallene, så N[1] = {1, 3, 5, 7, 9, …}.

Hva blir klassen N[2] lik? Vi finner alle tall som er ekvivalente med to. Det er alle partallene: N[2] = {2, 4, 6, 8, 10, …}.

Nå N[3]. Hvilke tall er ekvivalente med tre? Alle oddetall. Men da får vi mengden N[1], som vi regnet ut for to avsnitt siden. På samme måte for N[4], der får vi igjen mengden av partall.

Vi ser at de samme mengdene bare ville gjentatt seg videre. Det ser vi også av at uansett hvilket annet naturlig tall n vi tar, vil det gjelde at n ∈ N[1] eller n ∈ N[2]. Vi har ingen andre naturlige tall enn oddetall og partall, så disse to mengdene utgjør oppdelingen etter ekvivalensen.

Det er som om vi tenkte oss en ekvivalens på mengden av mennesker, der både a og b er menn eller både a og b er kvinner. Da ville vi fått mengden av kvinner og mengden av menn som oppdeling.

Andre eksempel, absoluttverdi:

La oss si at vi har en ekvivalens R på mengden av de hele tallene Z definert slik: (a, b) ∈ R hvis og bare hvis |a| = |b|. (De loddrette strekene er absoluttverdi.) Igjen tar vi det steg for steg:

• Z[0] = {0}. Null er bare i relasjon med null.
• Z[1] = {−1, 1}. En er i relasjon med en og med minus en, fordi |1| = |−1|.
• Z[2] = {−2, 2}. To er i relasjon med to og med minus to.
• Z[3] = {−3, 3}.
• …

Det er sikkert klart hvordan dette fortsetter. Hele oppdelingen ville altså være mengden av klasser:

$$\{\{a,-a\};a\in {\mathbb{Z}}_0^{+}\}$$

(Altså alle par a, −a, der a er et ikke-negativt helt tall.) Du ser at det er uendelig mange klasser.