Ekvivalensrelation

En ekvivalensrelation är en binär relation på en mängd som är reflexiv, symmetrisk och transitiv.

Motivering

En ekvivalensrelation är ett slags förfining av likhetsrelationen. Vi kan alltid avgöra om två element i en mängd är lika, alltså om a = b. Men ibland är det praktiskt att avgöra om två element bara är likartade, inte nödvändigtvis lika. Eller med andra ord — om de har samma avgörande egenskap. Till exempel kan vi anse att två böcker är likartade om de har samma genre — eller med hjälp av ekvivalens: två böcker är ekvivalenta om de har samma genre.

Vad skulle vi förvänta oss av en sådan ekvivalens? Vi tar ett annat exempel. Två ord är likartade/ekvivalenta om de är lika långa.

Vi skulle nog förvänta oss att om vi mäter likheten mellan två identiska ord, så blir resultatet att de är likartade. Alltså måste det för alla ord gälla att de är likartade/ekvivalenta med sig själva. På relationernas språk: en ekvivalensrelation måste vara reflexiv.

Vidare, om ordet ”bäck” är likartat/ekvivalent med ordet ”Maja”, så förväntar vi oss förstås att även ordet ”Maja” är ekvivalent med ordet ”bäck”. Med andra ord spelar ordningen ingen roll. På relationernas språk: en ekvivalensrelation måste vara symmetrisk.

Och slutligen, om ordet ”mörk” är likartat/ekvivalent med ordet ”näsa” och ordet ”näsa” är ekvivalent med ordet ”fisk”, så förväntar vi oss att även orden ”mörk” och ”fisk” är ekvivalenta. Alltså måste en ekvivalensrelation också vara transitiv.

Något mer förväntar vi oss inte av en ekvivalens.

Exempel

Fler exempel på ekvivalenser:

• Att bo i samma stad. Oscar bor förstås i samma stad som Oscar (reflexivitet). Om Oscar bor i samma stad som William, så bor också William i samma stad som Oscar (symmetri). Och om William bor i samma stad som Lucas, så bor också Oscar i samma stad som Lucas (transitivitet).
• Låtar med samma upphovsperson. Låten ”Vinterdröm” har förstås samma upphovsperson som låten ”Vinterdröm” (reflexivitet). Om låtarna ”Vinterdröm” och ”Havets sång” har samma upphovsperson, så har också ”Havets sång” och ”Vinterdröm” samma upphovsperson (symmetri). Och om ”Havets sång” och ”Skogsstigen” har samma upphovsperson, så har också ”Vinterdröm” och ”Skogsstigen” samma upphovsperson (transitivitet).
• (a, b) ∈ R om och endast om a − b är ett jämnt tal; a, b är heltal. Reflexivitet: a − a = 0, noll är ett jämnt tal. Symmetri: låt c = a − b. Då är b − a = −(a − b) = −c. Om c är jämnt, så måste också −c vara jämnt. Transitivitet: låt p = a − b och q = b − c. Vi vet att både p och q är jämna tal. Nu ska vi bevisa att a − c är ett jämnt tal. I den här likheten sätter vi in c = b − q för c: a − (b − q), vilket är lika med a − b + q. Av förutsättningarna vet vi att a − b är ett jämnt tal. Om vi lägger till ett annat jämnt tal q till ett jämnt tal, får vi åter ett jämnt tal.
• Likhet. Likhet är en ekvivalens, och det är dessutom den minsta ekvivalensen på en godtycklig mängd M.

Trivial ekvivalens

Vi har en icke-tom mängd M. Vilken är den minsta möjliga ekvivalensen R på mängden M? Den minsta möjliga delmängden av den kartesiska produkten M × M är den tomma mängden ∅. Uppfyller den tomma mängden villkoren för en ekvivalens?

Den är säkert symmetrisk: relationen R har inga element, så villkoret för symmetri är automatiskt och trivialt uppfyllt. Detsamma gäller transitiviteten. Problemet är reflexiviteten. Definitionen säger att det för alla element x i mängden M gäller att (x, x) ∈ R. Är det uppfyllt? Mängden M är icke-tom, så den innehåller något element, till exempel q. Ligger paret (q, q) i relationen R? Nej. Relationen R är alltså inte reflexiv.

Vilken är den minsta relationen som uppfyller reflexivitet? Likhetsrelationen. Relationen R måste innehålla åtminstone paren (x, x) för alla element i M. Det är just identitetsrelationen. Är en sådan relation symmetrisk? Det är lätt att se att den är det. På samma sätt är det lätt att se att den också är transitiv. Den minsta ekvivalensrelationen på mängden M är alltså identitetsrelationen, som vi betecknar id_M och som innehåller paren (x, x) för alla x ∈ M.

Vilken är den största möjliga ekvivalensen på mängden M? Den största delmängden är hela mängden M × M. Uppfyller den villkoren för en ekvivalens? Det är väl ganska uppenbart att den gör det.

Ekvivalensklass

Varje ekvivalens delar upp mängden M i ett system av disjunkta mängder, som vi kallar ekvivalensklasser.

Låt M vara mängden av alla ord och R ekvivalensen ”att vara lika långa ord”. Alltså (a, b) ∈ R om och endast om orden a och b är lika långa. Den här ekvivalensen delar upp mängden av ord i flera mindre mängder, som alltid innehåller ord av samma längd. De enskilda ekvivalensklasserna kan vi skilja åt med ett nedsänkt index, som samtidigt anger längden på orden i mängden:

• M₁ = {å, i, ö, …}
• M₂ = {på, av, du, vi, …}
• M₃ = {men, med, den, dig, …}
• M₄ = {park, vind, hund, bord, …}
• …

Lägg märke till två saker: 1) de enskilda mängderna är disjunkta, de har inget gemensamt element. 2) alla element i varje enskild mängd är ekvivalenta med varandra. Alla ord i mängden M₃ är ekvivalenta med varandra, eftersom alla orden har längden tre, alltså samma längd, vilket är villkoret för ekvivalens.

Varje element bestämmer entydigt sin ekvivalensklass. Det brukar vi skriva med beteckningen M[x], där x ∈ M. Om vi skriver M[men], så bestämmer vi entydigt den ekvivalensklass som vi redan har kallat M₃.

Hur hittar vi då en ekvivalensklass om vi känner något x ∈ M? Vi går igenom alla element i M och undersöker vilka av dem som är ekvivalenta med elementet x. Det blir alla element som ingår i ekvivalensklassen M[x].

För M[men] skulle vi gå igenom alla ord i M och spara i M₃ de ord som har längden tre.

Definition och egenskaper hos ekvivalensklassen

Vi kan definiera ekvivalensklassen så här. Låt M vara en mängd och R en ekvivalens definierad på den. Med den klass i partitionen som innehåller elementet x ∈ M menar vi då:

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

Definitionen säger att det är alla y som är ekvivalenta med det givna elementet x. Eftersom ekvivalensrelationen är reflexiv, så kommer även elementet x självt med på detta sätt — eftersom x är ekvivalent med sig självt.

Med partitionen som hör till ekvivalensen menar vi sedan mängden av alla ekvivalensklasser. Partitionen av mängden av alla ord skulle alltså vara mängden {M₁, M₂, M₃, …}.

Grundläggande egenskaper hos ekvivalensklasser:

• (a, b) ∈ R om och endast om M[a] = M[b]. Om vi har två element a, b som är ekvivalenta, så måste deras ekvivalensklasser vara lika.
• Omvänt, om (a, b) ∈ R inte gäller, så gäller också M[a] ≠ M[b], mer exakt M[a] ∩ M[b] = ∅. Om vi har två element som inte är ekvivalenta, så är deras klasser i partitionen disjunkta.
• Unionen av alla ekvivalensklasser måste ge den ursprungliga mängden M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Den föregående skrivningen gäller bara för ett ändligt antal ekvivalensklasser, men i allmänhet kan de vara oändligt många.)

Exempel på partitioner av ekvivalenser

Första exemplet, udda och jämna tal:

Låt R vara en enkel ekvivalens definierad på de positiva heltalen N. (a, b) ∈ R om och endast om både a och b är udda eller både a och b är jämna. Exempel på element: (1, 7), (13, 9), (4, 6), (8, 136). Nu bestämmer vi partitionen för den här ekvivalensen i ekvivalensklasser.

Vi börjar steg för steg. Vad blir klassen N[1] lika med? Vi måste hitta alla tal som är ekvivalenta med talet ett. Enligt villkoret för ekvivalens är det alla udda tal, så N[1] = {1, 3, 5, 7, 9, …}.

Vad blir klassen N[2] lika med? Vi hittar alla tal som är ekvivalenta med tvåan. Det är alla jämna tal: N[2] = {2, 4, 6, 8, 10, …}.

Nu N[3]. Vilka tal är ekvivalenta med trean? Alla udda tal. Men då får vi mängden N[1], som vi räknade ut två stycken tidigare. På samma sätt för N[4], där får vi återigen mängden av de jämna talen.

Vi ser att det härifrån bara skulle upprepas samma mängder. Det syns också av att vilket annat positivt heltal n vi än tar, så gäller det att n ∈ N[1] eller n ∈ N[2]. Några andra positiva heltal än udda och jämna har vi inte, så dessa två mängder utgör partitionen för ekvivalensen.

Det är som om vi tänkte oss en ekvivalens på mängden av människor, där a och b båda är män eller a och b båda är kvinnor. Då skulle vi som partition få mängden av kvinnor och mängden av män.

Andra exemplet, absolutbelopp:

Låt R vara en ekvivalens på mängden av heltal Z definierad så här: (a, b) ∈ R om och endast om |a| = |b|. (De där lodräta strecken är absolutbelopp.) Återigen går vi steg för steg:

• Z[0] = {0}. Noll står bara i relation till noll.
• Z[1] = {−1, 1}. Ett står i relation till ett och till minus ett, eftersom |1| = |−1|.
• Z[2] = {−2, 2}. Tvåan står i relation till tvåan och till minus två.
• Z[3] = {−3, 3}.
• …

Det är nog klart hur det fortsätter. Hela partitionen skulle alltså vara mängden av klasser:

$$\{\{a,-a\}\mid a\in \mathbb{N}\}$$

(Alltså alla par a, −a, där a är ett icke-negativt heltal.) Du ser att det finns oändligt många klasser.