Ækvivalensrelation

En ækvivalensrelation er en binær relation på en mængde, som er refleksiv, symmetrisk og transitiv.

Motivation

En ækvivalensrelation er en slags forfinelse af relationen lighed. Vi kan altid afgøre, om to elementer i en mængde er ens, altså om a = b. Men nogle gange er det praktisk at finde ud af, om to elementer blot ligner hinanden, ikke nødvendigvis er ens. Eller — om de har samme afgørende egenskab. For eksempel kan vi anse to bøger for at ligne hinanden, hvis de har samme genre — eller ved hjælp af ækvivalens: to bøger er ækvivalente, hvis de har samme genre.

Hvad ville vi forvente af sådan en ækvivalens? Lad os tage et andet eksempel. To ord ligner hinanden/er ækvivalente, hvis de er lige lange.

Vi ville nok forvente, at hvis vi måler ligheden mellem to ens ord, så viser det sig, at de ligner hinanden. Altså skal det for alle ord gælde, at de ligner sig selv/er ækvivalente med sig selv. På relationernes sprog: en ækvivalensrelation skal være refleksiv.

Videre, hvis ordet »kaffe« ligner/er ækvivalent med ordet »Freja«, så forventer vi helt sikkert, at ordet »Freja« også er ækvivalent med ordet »kaffe«. Med andre ord er rækkefølgen ligegyldig. På relationernes sprog: en ækvivalensrelation skal være symmetrisk.

Og endelig, hvis ordet »kold« ligner/er ækvivalent med ordet »hånd«, og ordet »hånd« er ækvivalent med ordet »næse«, så forventer vi, at også parret af ordene »kold« og »næse« er ækvivalent. Altså skal en ækvivalensrelation også være transitiv.

Andet forventer vi ikke af en ækvivalens.

Eksempler

Flere eksempler på ækvivalenser:

• At bo i samme by. Mads bor helt sikkert i samme by som Mads (refleksivitet). Hvis Mads bor i samme by som Oscar, så bor Oscar også i samme by som Mads (symmetri). Og hvis Oscar bor i samme by som Martin, så bor Mads også i samme by som Martin (transitivitet).
• Bøger med samme forfatter. Bogen »Nattens ravne« har helt sikkert samme forfatter som bogen »Nattens ravne« (refleksivitet). Hvis bøgerne »Nattens ravne« og »Stormens sidste dag« har samme forfatter, så har også »Stormens sidste dag« og »Nattens ravne« samme forfatter (symmetri). Og hvis »Stormens sidste dag« og »Rejsen mod nord« har samme forfatter, så har også »Nattens ravne« og »Rejsen mod nord« samme forfatter (transitivitet).
• (a, b) ∈ R netop når a − b er et lige tal; a, b er hele tal. Refleksivitet: a − a = 0, nul er et lige tal. Symmetri: lad c = a − b. Så er b − a = −(a − b) = −c. Hvis c er lige, så skal også −c være lige. Transitivitet: lad p = a − b og videre q = b − c. Vi ved, at både p og q er lige tal. Nu skal vi bevise, at a − c er et lige tal. I denne ligning sætter vi c = b − q ind for c: a − (b − q), hvilket er lig med a − b + q. Af forudsætningerne ved vi, at a − b er et lige tal. Hvis vi lægger endnu et lige tal q til et lige tal, får vi igen et lige tal.
• Lighed. Lighed er en ækvivalens, og det er samtidig den mindste ækvivalens på en vilkårlig mængde M.

Triviel ækvivalens

Vi har en ikke-tom mængde M. Hvad er den mindst mulige ækvivalens R på mængden M? Den mindst mulige delmængde af mængdeproduktet M × M er den tomme mængde ∅. Opfylder den tomme mængde betingelserne for en ækvivalens?

Den er helt sikkert symmetrisk, for da relationen R ikke har nogen elementer, er betingelsen for symmetri automatisk og trivielt opfyldt. På samme måde transitivitet. Problemet er med refleksiviteten. Definitionen siger, at der for alle elementer x i mængden M gælder, at (x, x) ∈ R. Er dette opfyldt? Mængden M er ikke tom, så den indeholder et element, for eksempel q. Er parret (q, q) i relationen R? Nej. Relationen R er altså ikke refleksiv.

Hvad er den mindste relation, der opfylder refleksivitet? Relationen lighed. Relationen R skal mindst indeholde parrene (x, x) for alle elementer i M. Det er netop identitetsrelationen. Er en sådan relation symmetrisk? Det er let at se, at den er. På samme måde er det let at se, at den også er transitiv. Den mindste ækvivalensrelation på mængden M er altså identitetsrelationen, vi skriver den id_M, og den indeholder parrene (x, x) for alle x ∈ M.

Hvad er den størst mulige ækvivalens på mængden M? Den største delmængde er hele mængden M × M. Opfylder den betingelserne for en ækvivalens? Det er nok trivielt at se, at den gør.

Ækvivalensklasse

Hver ækvivalens deler mængden M op i et system af disjunkte mængder, som vi så kalder ækvivalensklasser.

Lad os have mængden af alle ord M og ækvivalensen R »lige lange ord«. Altså (a, b) ∈ R netop når ordene a og b har samme længde. Denne ækvivalens deler mængden af ord op i flere mindre mængder, som altid vil indeholde ord af samme længde. De enkelte ækvivalensklasser kan vi skelne ved hjælp af et sænket indeks, som samtidig angiver længden af ordene i den givne mængde:

• M₁ = {å, i, o, ø, …}
• M₂ = {af, at, du, på, …}
• M₃ = {men, for, den, her, …}
• M₄ = {kold, park, hest, dame, …}
• …

Læg mærke til to ting: 1) de enkelte mængder er indbyrdes disjunkte, de har ikke noget fælles element. 2) alle elementer i hver enkelt mængde er indbyrdes ækvivalente. Alle ord i mængden M₃ er indbyrdes ækvivalente, fordi alle ordene har længden tre, altså samme længde, hvilket er betingelsen for ækvivalens.

Hvert element definerer samtidig entydigt sin ækvivalensklasse. Det skriver vi sædvanligvis ved hjælp af notationen M[x], hvor x ∈ M. Hvis vi skriver M[men], definerer vi derved entydigt den ækvivalensklasse, som vi allerede har kaldt M₃.

Hvordan finder vi egentlig ækvivalensklassen, hvis vi kender et x ∈ M? Vi gennemgår alle elementer i M og finder ud af, hvilke af disse elementer der er ækvivalente med elementet x. Det bliver alle de elementer, som er en del af ækvivalensklassen M[x].

For M[men] ville vi gennemgå alle ord i M og i M₃ gemme sådanne ord, som har længden tre.

Definition og egenskaber ved ækvivalensklassen

Ækvivalensklassen kunne vi definere således. Lad os have en mængde M og en ækvivalens R defineret på den. Så forstår vi ved klassen i klasseinddelingen, der indeholder elementet x ∈ M:

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

Definitionen siger, at det er alle de y, som er ækvivalente med det givne element x. Fordi ækvivalensrelationen er refleksiv, kommer selve elementet x også med på denne måde — fordi x er ækvivalent med sig selv.

Ved klasseinddelingen hørende til en ækvivalens forstår vi så mængden af alle ækvivalensklasser. Klasseinddelingen af mængden af alle ord ville altså være mængden {M₁, M₂, M₃, …}.

Grundlæggende egenskaber ved ækvivalensklasser:

• (a, b) ∈ R netop når M[a] = M[b]. Hvis vi har to elementer a, b, som er ækvivalente, så skal deres ækvivalensklasser være ens.
• Omvendt, hvis (a, b) ∈ R ikke gælder, så er også M[a] ≠ M[b], mere præcist M[a] ∩ M[b] = ∅. Hvis vi har to elementer, som ikke er ækvivalente, så er deres klasser i klasseinddelingen disjunkte.
• Foreningsmængden af alle ækvivalensklasser skal give den oprindelige mængde M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Den foregående notation gælder kun for et endeligt antal ækvivalensklasser, men generelt kan der være uendeligt mange.)

Eksempler på klasseinddelinger efter ækvivalens

Første eksempel, ulige og lige tal:

Lad os have en enkel ækvivalens R defineret på de naturlige tal N. (a, b) ∈ R netop når både a og b er ulige, eller både a og b er lige. Eksempler på elementer: (1, 7), (13, 9), (4, 6), (8, 136). Nu bestemmer vi klasseinddelingen efter denne ækvivalens i ækvivalensklasser.

Vi begynder trin for trin. Hvad bliver klassen N[1] lig med? Vi skal finde alle tal, som er ækvivalente med tallet et. Ifølge betingelsen for ækvivalens er det alle de ulige tal, så N[1] = {1, 3, 5, 7, 9, …}.

Hvad bliver klassen N[2] lig med? Vi finder alle tal, som er ækvivalente med to. Det er alle de lige tal: N[2] = {2, 4, 6, 8, 10, …}.

Nu N[3]. Hvilke tal er ækvivalente med tre? Alle de ulige tal. Men derved får vi mængden N[1], som vi beregnede i næstsidste afsnit. På samme måde for N[4], her igen mængden af de lige tal.

Vi ser, at de samme mængder ville blive ved med at gentage sig. Det kan man også se af, at uanset hvilket andet naturligt tal n vi tager, vil det gælde, at n ∈ N[1] eller n ∈ N[2]. Andre naturlige tal end ulige og lige har vi ikke, så disse to mængder udgør klasseinddelingen efter ækvivalensen.

Det svarer til, at vi forestiller os en ækvivalens på en mængde af mennesker: både a og b er mænd, eller både a og b er kvinder. Så ville vi som klasseinddeling få mængden af kvinder og mængden af mænd.

Andet eksempel, numerisk værdi:

Lad os have ækvivalensen R på mængden af de hele tal Z defineret således: (a, b) ∈ R netop når |a| = |b|. (De lodrette streger er numerisk værdi.) Igen går vi trin for trin:

• Z[0] = {0}. Nul er kun i relation med nul.
• Z[1] = {−1, 1}. Et er i relation med et og med minus et, fordi |1| = |−1|.
• Z[2] = {−2, 2}. To er i relation med to og med minus to.
• Z[3] = {−3, 3}.
• …

Det er nok klart, hvordan det fortsætter. Hele klasseinddelingen ville altså være mængden af klasser:

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

(Altså alle par a, −a, hvor a er et helt ikke-negativt tal.) Du kan se, at der er uendeligt mange klasser.