Ekvivalenciareláció

Az ekvivalenciareláció halmazon értelmezett bináris reláció, amely reflexív, szimmetrikus és tranzitív.

Motiváció

Az ekvivalenciareláció az egyenlőség reláció valamiféle finomítása. Mindig eldönthetjük, hogy a halmaz két eleme azonos-e, vagyis hogy a = b. De néha hasznos tudni, hogy két elem csak hasonló-e, nem feltétlenül azonos. Más szóval – hogy van-e valamilyen lényeges közös tulajdonságuk. Például két könyvet hasonlónak tekinthetünk, ha azonos a műfajuk – vagy ekvivalenciával megfogalmazva: két könyv ekvivalens, ha azonos a műfajuk.

Mit várnánk egy ilyen ekvivalenciától? Vegyünk egy másik példát. Két szó hasonló/ekvivalens, ha egyforma hosszú.

Valószínűleg azt várnánk, hogy ha két azonos szó hasonlóságát mérjük, akkor azt kapjuk, hogy hasonlóak. Tehát minden szóra igaznak kell lennie, hogy önmagával hasonló/ekvivalens. A relációk nyelvén: az ekvivalenciarelációnak reflexívnek kell lennie.

Továbbá, ha a „patak” szó hasonló/ekvivalens a „Kinga” szóval, akkor természetesen azt várjuk, hogy a „Kinga” szó is ekvivalens a „patak” szóval. Más szóval a sorrend nem számít. A relációk nyelvén: az ekvivalenciarelációnak szimmetrikusnak kell lennie.

Végül, ha a „hold” szó hasonló/ekvivalens a „bika” szóval, a „bika” szó pedig ekvivalens a „kert” szóval, akkor azt várjuk, hogy a „hold” és a „kert” szópár is ekvivalens lesz. Az ekvivalenciarelációnak tehát tranzitívnak is kell lennie.

Ezen kívül semmi mást nem várunk az ekvivalenciától.

Példák

További példák ekvivalenciára:

• Ugyanabban a városban lakni. Gergő biztosan ugyanabban a városban lakik, mint Gergő (reflexivitás). Ha Gergő ugyanabban a városban lakik, mint Olivér, akkor Olivér is ugyanabban a városban lakik, mint Gergő (szimmetria). És ha Olivér ugyanabban a városban lakik, mint Martin, akkor Gergő is ugyanabban a városban lakik, mint Martin (tranzitivitás).
• Ugyanabban a hónapban születni. Anna biztosan ugyanabban a hónapban született, mint Anna (reflexivitás). Ha Anna és Bence ugyanabban a hónapban született, akkor Bence és Anna is ugyanabban a hónapban született (szimmetria). És ha Bence és Csaba ugyanabban a hónapban született, akkor Anna és Csaba is ugyanabban a hónapban született (tranzitivitás).
• (a; b) ∈ R akkor és csak akkor, ha a − b páros szám; a, b egész számok. Reflexivitás: a − a = 0, a nulla páros szám. Szimmetria: jelöljük c = a − b-vel. Ekkor b − a = −(a − b) = −c. Ha c páros, akkor −c is páros kell, hogy legyen. Tranzitivitás: jelöljük p = a − b-vel, továbbá q = b − c-vel. Tudjuk, hogy p és q is páros szám. Most azt kell bizonyítanunk, hogy a − c páros szám. Ebbe az egyenletbe c helyére behelyettesítjük a c = b − q kifejezést: a − (b − q), ami egyenlő a − b + q-val. A feltételekből tudjuk, hogy a − b páros szám. Ha páros számhoz hozzáadunk még egy páros számot, q-t, ismét páros számot kapunk.
• Egyenlőség. Az egyenlőség ekvivalencia, és egyben a legkisebb ekvivalencia bármely M halmazon.

Triviális ekvivalencia

Adott egy nemüres M halmaz. Mi a legkisebb lehetséges ekvivalencia R az M halmazon? Az M × M Descartes-szorzat legkisebb lehetséges részhalmaza az üres halmaz ∅. Teljesíti-e az üres halmaz az ekvivalencia feltételeit?

Biztosan szimmetrikus, mivel az R relációnak nincs egyetlen eleme sem, így a szimmetria feltétele automatikusan, triviálisan teljesül. Hasonlóan a tranzitivitás. A probléma a reflexivitással van. A definíció szerint az M halmaz minden x elemére igaz, hogy (x; x) ∈ R. Teljesül ez? Az M halmaz nemüres, tehát tartalmaz valamilyen elemet, például q-t. Benne van-e a (q; q) pár az R relációban? Nincs. Az R reláció tehát nem reflexív.

Mi a legkisebb reflexív reláció? Az egyenlőség reláció. Az R relációnak legalább az (x; x) párokat tartalmaznia kell az M minden elemére. Ez éppen az identitás reláció. Szimmetrikus-e egy ilyen reláció? Könnyen látható, hogy igen. Hasonlóan könnyen látható, hogy tranzitív is. Az M halmaz legkisebb ekvivalenciarelációja tehát az identitás reláció, jelölése id_M, és az (x; x) párokat tartalmazza minden x ∈ M-re.

Mi a legnagyobb lehetséges ekvivalencia az M halmazon? A legnagyobb részhalmaz maga az M × M. Teljesíti-e az ekvivalencia feltételeit? Talán triviálisan látszik, hogy igen.

Ekvivalenciaosztály

Minden ekvivalencia diszjunkt halmazok rendszerére osztja az M halmazt, ezeket nevezzük ekvivalenciaosztályoknak.

Legyen M az összes szó halmaza, R pedig az „egyforma hosszú szó” ekvivalencia. Vagyis (a; b) ∈ R akkor és csak akkor, ha az a és b szó hossza megegyezik. Ez az ekvivalencia a szavak halmazát több kisebb halmazra bontja, amelyek mindig azonos hosszúságú szavakat tartalmaznak. Az egyes ekvivalenciaosztályokat alsó indexszel különböztethetjük meg, amely egyben az adott halmazban lévő szavak hosszát is jelzi:

• M₁ = {a, e, s, …}
• M₂ = {az, és, ki, be, el, …}
• M₃ = {ház, kép, víz, nem, …}
• M₄ = {hold, park, tető, kert, …}
• …

Figyelj meg két dolgot: 1) az egyes halmazok egymással diszjunktak, nincs közös elemük. 2) az egyes halmazok minden eleme egymással ekvivalens. Az M₃ halmaz minden szava egymással ekvivalens, mert minden szó hossza három, tehát azonos, ez az ekvivalencia feltétele.

Minden elem egyértelműen meghatározza az ekvivalenciaosztályát. Ezt általában az M[x] jelöléssel írjuk, ahol x ∈ M. Ha azt írnánk, hogy M[ház], azzal egyértelműen meghatároznánk azt az ekvivalenciaosztályt, amelyet már M₃-mal jelöltünk.

Hogyan találjuk meg az ekvivalenciaosztályt, ha ismerünk valamilyen x ∈ M elemet? Végigmegyünk M összes elemén, és megnézzük, hogy ezek közül melyek ekvivalensek az x elemmel. Ezek lesznek az M[x] ekvivalenciaosztály elemei.

M[ház]-hoz végigmennénk M összes szaván, és az M₃-ban megtartanánk azokat, amelyek hossza három.

Az ekvivalenciaosztály definíciója és tulajdonságai

Az ekvivalenciaosztályt definiálhatjuk így. Legyen adott az M halmaz és rajta az R ekvivalencia. Ekkor az x ∈ M elemet tartalmazó osztályon a következőt értjük:

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

A definíció azt mondja, hogy ezek mind azok az y elemek, amelyek ekvivalensek az adott x elemmel. Mivel az ekvivalenciareláció reflexív, ilyen módon maga az x elem is bekerül – hiszen x ekvivalens önmagával.

Az ekvivalencia szerinti osztályozáson az összes ekvivalenciaosztály halmazát értjük. Az összes szó halmazának osztályozása tehát a {M₁, M₂, M₃, …} halmaz lenne.

Az ekvivalenciaosztályok alapvető tulajdonságai:

• (a; b) ∈ R akkor és csak akkor, ha M[a] = M[b]. Ha van két ekvivalens elemünk, a, b, akkor az ekvivalenciaosztályaiknak egyenlőnek kell lenniük.
• Fordítva, ha nem teljesül, hogy (a; b) ∈ R, akkor M[a] ≠ M[b] is igaz, pontosabban M[a] ∩ M[b] = ∅. Ha két elem nem ekvivalens, akkor osztályaik diszjunktak.
• Az összes ekvivalenciaosztály uniójának az eredeti M halmazt kell adnia: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Az előző felírás csak véges sok ekvivalenciaosztályra szól, de általában végtelen sok is lehet belőlük.)

Példák ekvivalencia szerinti osztályozásra

Az első példa, a páratlan és páros számok:

Legyen adott egy egyszerű R ekvivalencia a pozitív egész számokon, ℕ⁺-on. (a; b) ∈ R akkor és csak akkor, ha a és b is páratlan, vagy a és b is páros. Példák elemekre: (1; 7), (13; 9), (4; 6), (8; 136). Most meghatározzuk ennek az ekvivalenciának az ekvivalenciaosztályokra bontását.

Kezdjük sorban. Mivel lesz egyenlő az ℕ⁺[1] osztály? Meg kell találnunk az összes számot, amely ekvivalens az eggyel. Az ekvivalencia feltétele szerint ez az összes páratlan szám, tehát ℕ⁺[1] = {1, 3, 5, 7, 9, …}.

Mivel lesz egyenlő az ℕ⁺[2] osztály? Megkeressük az összes számot, amely ekvivalens a kettessel. Ez az összes páros szám: ℕ⁺[2] = {2, 4, 6, 8, 10, …}.

Most ℕ⁺[3]. Mely számok ekvivalensek a hármassal? Az összes páratlan szám. Így viszont az ℕ⁺[1] halmazt kapjuk, amelyet két bekezdéssel korábban kiszámoltunk. Hasonlóan ℕ⁺[4]-nél ismét a páros számok halmazát.

Látjuk, hogy a továbbiakban mindig ugyanazok a halmazok ismétlődnének. Ez abból is látszik, hogy bármelyik további n pozitív egész számot vesszük, az vagy n ∈ ℕ⁺[1], vagy n ∈ ℕ⁺[2]. Páratlan és páros számokon kívül nincsenek más pozitív egész számaink, így ez a két halmaz alkotja az ekvivalencia osztályozását.

Ez hasonló ahhoz, mintha az emberek halmazán olyan ekvivalenciát képzelnénk el, hogy a és b is férfi, vagy a és b is nő. Akkor osztályozásként a nők halmazát és a férfiak halmazát kapnánk.

A második példa, az abszolútérték:

Legyen R ekvivalencia az egész számok ℤ halmazán, definiálva így: (a; b) ∈ R akkor és csak akkor, ha |a| = |b|. (Azok a függőleges vonalak az abszolútértéket jelentik.) Ismét sorban haladunk:

• ℤ[0] = {0}. A nulla csak a nullával áll relációban.
• ℤ[1] = {−1, 1}. Az egyes az eggyel és a mínusz eggyel áll relációban, mert |1| = |−1|.
• ℤ[2] = {−2, 2}. A kettes a kettessel és a mínusz kettessel áll relációban.
• ℤ[3] = {−3, 3}.
• …

Talán világos, hogyan folytatódik. A teljes osztályozás tehát az osztályok halmaza:

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

(Vagyis az összes a, −a pár, ahol a nemnegatív egész szám.) Látod, hogy végtelen sok osztály van.