Relații de echivalență

Relația de echivalență este o relație binară pe o mulțime care este reflexivă, simetrică și tranzitivă.

Motivație

Relația de echivalență este un fel de rafinare a relației de egalitate. Putem decide oricând dacă două elemente ale unei mulțimi sunt la fel, adică dacă a = b. Dar uneori ne este util să aflăm dacă două elemente sunt doar asemănătoare, nu neapărat la fel. Cu alte cuvinte – dacă au aceeași proprietate esențială. De exemplu, două cărți le putem considera asemănătoare dacă au același gen – sau, cu ajutorul echivalenței: două cărți sunt echivalente dacă au același gen.

Ce ne-am aștepta de la o astfel de echivalență? Să luăm alt exemplu. Două cuvinte sunt asemănătoare/echivalente dacă au aceeași lungime.

Probabil ne-am aștepta ca, măsurând asemănarea a două cuvinte identice, să rezulte că sunt asemănătoare. Deci orice cuvânt trebuie să fie asemănător/echivalent cu el însuși. În limbajul relațiilor: relația de echivalență trebuie să fie reflexivă.

Mai departe, dacă cuvântul „vară” este asemănător/echivalent cu cuvântul „lună”, atunci ne așteptăm sigur ca și cuvântul „lună” să fie echivalent cu cuvântul „vară”. Cu alte cuvinte, ordinea nu contează. În limbajul relațiilor: relația de echivalență trebuie să fie simetrică.

Și, în sfârșit, dacă cuvântul „vară” este asemănător/echivalent cu cuvântul „lună”, iar cuvântul „lună” este echivalent cu cuvântul „mână”, atunci ne așteptăm ca și cuvintele „vară” și „mână” să fie echivalente. Deci relația de echivalență trebuie să fie și tranzitivă.

Nu ne așteptăm la nimic altceva de la o echivalență.

Exemple

Alte exemple de echivalențe:

• A locui în același oraș. Vlad locuiește sigur în același oraș cu Vlad (reflexivitate). Dacă Vlad locuiește în același oraș cu Andrei, atunci și Andrei locuiește în același oraș cu Vlad (simetrie). Iar dacă Andrei locuiește în același oraș cu Marius, atunci și Vlad locuiește în același oraș cu Marius (tranzitivitate).
• Cântece cu același autor. Cântecul „Ploaia de seară” are sigur același autor ca cântecul „Ploaia de seară” (reflexivitate). Dacă cântecele „Ploaia de seară” și „Drumul spre mare” au același autor, atunci și „Drumul spre mare” și „Ploaia de seară” au același autor (simetrie). Iar dacă „Drumul spre mare” și „Cântec de iarnă” au același autor, atunci și „Ploaia de seară” și „Cântec de iarnă” au același autor (tranzitivitate).
• (a, b) ∈ R dacă și numai dacă a − b este număr par; a, b sunt numere întregi. Reflexivitate: a − a = 0, iar zero este număr par. Simetrie: notăm c = a − b. Atunci b − a = −(a − b) = −c. Dacă c este par, atunci și −c trebuie să fie par. Tranzitivitate: notăm p = a − b și q = b − c. Știm că atât p, cât și q sunt numere pare. Acum trebuie să demonstrăm că a − c este număr par. În această expresie îl înlocuim pe c conform relației c = b − q: a − (b − q), ceea ce este egal cu a − b + q. Din ipoteze știm că a − b este număr par. Dacă la un număr par adunăm un alt număr par q, obținem din nou un număr par.
• Egalitatea. Egalitatea este o echivalență, și în același timp cea mai mică echivalență pe orice mulțime M.

Echivalențe triviale

Avem o mulțime nevidă M. Care este cea mai mică echivalență posibilă R pe mulțimea M? Cea mai mică submulțime posibilă a produsului cartezian M × M este mulțimea vidă ∅. Îndeplinește mulțimea vidă condițiile echivalenței?

Sigur este simetrică: deoarece relația R nu are elemente, condiția de simetrie este îndeplinită automat și trivial. La fel tranzitivitatea. Problema este reflexivitatea. Definiția spune că pentru toate elementele x ale mulțimii M avem (x, x) ∈ R. Este aceasta îndeplinită? Mulțimea M este nevidă, deci conține un element, de exemplu q. Se află perechea (q, q) în relația R? Nu. Relația R nu este deci reflexivă.

Care este cea mai mică relație care îndeplinește reflexivitatea? Relația de egalitate. Relația R trebuie să conțină cel puțin perechile (x, x) pentru toate elementele lui M. Asta este exact relația identitate. Este o astfel de relație simetrică? Se vede ușor că da. La fel, se vede ușor că este și tranzitivă. Cea mai mică relație de echivalență pe mulțimea M este deci relația identitate, notată id_M, care conține perechile (x, x) pentru toți x ∈ M.

Care este cea mai mare echivalență posibilă pe mulțimea M? Cea mai mare submulțime este întreaga mulțime M × M. Îndeplinește condițiile echivalenței? Probabil se vede imediat că da.

Clasa de echivalență

Orice echivalență împarte mulțimea M într-un sistem de mulțimi disjuncte, pe care le numim clase de echivalență.

Fie mulțimea tuturor cuvintelor M și echivalența R „cuvinte de aceeași lungime”. Deci (a, b) ∈ R dacă și numai dacă cuvintele a și b au aceeași lungime. Această echivalență împarte mulțimea cuvintelor în mai multe mulțimi mai mici, care vor conține întotdeauna cuvinte de aceeași lungime. Clasele de echivalență le putem deosebi printr-un indice inferior, care va indica în același timp lungimea cuvintelor din mulțimea respectivă:

• M₁ = {a, e, i, o, …}
• M₂ = {la, de, cu, un, eu, …}
• M₃ = {dar, azi, mic, tot, …}
• M₄ = {casă, masă, vară, pace, …}
• …

Observă două lucruri: 1) mulțimile sunt disjuncte între ele, nu au niciun element comun. 2) toate elementele fiecărei mulțimi sunt echivalente între ele. Toate cuvintele din mulțimea M₃ sunt echivalente între ele, pentru că toate au lungimea trei, deci aceeași lungime, ceea ce este condiția echivalenței.

Fiecare element își determină în mod unic clasa de echivalență. Aceasta o scriem de obicei cu notația M[x], unde x ∈ M. Dacă scriem M[dar], definim în mod unic clasa de echivalență pe care am notat-o deja M₃.

Cum găsim, de fapt, clasa de echivalență dacă cunoaștem un x ∈ M? Parcurgem toate elementele din M și vedem care dintre ele sunt echivalente cu elementul x. Acestea vor fi toate elementele care fac parte din clasa de echivalență M[x].

Pentru M[dar] am parcurge toate cuvintele din M și am păstra în M₃ cuvintele care au lungimea trei.

Definiția și proprietățile clasei de echivalență

Clasa de echivalență o putem defini astfel. Fie o mulțime M și o echivalență R definită pe ea. Atunci prin clasa partiției care conține elementul x ∈ M înțelegem:

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

Definiția spune că acestea sunt toate elementele y care sunt echivalente cu elementul dat x. Deoarece relația de echivalență este reflexivă, în acest fel ajunge în clasă și elementul x însuși – pentru că x este echivalent cu el însuși.

Prin partiția determinată de echivalență înțelegem apoi mulțimea tuturor claselor de echivalență. Deci partiția mulțimii tuturor cuvintelor ar fi mulțimea {M₁, M₂, M₃, …}.

Proprietățile de bază ale claselor de echivalență:

• (a, b) ∈ R dacă și numai dacă M[a] = M[b]. Dacă avem două elemente a, b echivalente, atunci clasele lor de echivalență trebuie să fie egale.
• Invers, dacă nu este adevărat că (a, b) ∈ R, atunci avem și M[a] ≠ M[b], mai exact M[a] ∩ M[b] = ∅. Dacă avem două elemente care nu sunt echivalente, atunci clasele lor din partiție sunt disjuncte.
• Reuniunea tuturor claselor de echivalență trebuie să dea mulțimea inițială M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (Scrierea de mai sus este valabilă doar pentru un număr finit de clase de echivalență, dar în general pot fi infinit de multe.)

Exemple de partiții ale unei echivalențe

Primul exemplu, numerele impare și pare:

Fie o echivalență simplă R definită pe numerele naturale ℕ. (a, b) ∈ R dacă și numai dacă a și b sunt amândouă impare sau a și b sunt amândouă pare. Exemple de elemente: (1, 7), (13, 9), (4, 6), (8, 136). Determinăm acum partiția acestei echivalențe în clase de echivalență.

Începem pe rând. Cu ce va fi egală clasa ℕ[1]? Trebuie să găsim toate numerele echivalente cu numărul unu. Conform condiției echivalenței, acestea sunt toate numerele impare, deci ℕ[1] = {1, 3, 5, 7, 9, …}.

Cu ce va fi egală clasa ℕ[2]? Găsim toate numerele echivalente cu doi. Acestea sunt toate numerele pare, iar printre numerele naturale se află și zero, care este par: ℕ[2] = {0, 2, 4, 6, 8, 10, …}.

Acum ℕ[3]. Ce numere sunt echivalente cu trei? Toate numerele impare. Dar astfel obținem mulțimea ℕ[1], pe care am calculat-o în paragraful de mai sus. La fel pentru ℕ[4], unde obținem din nou mulțimea numerelor pare.

Vedem că mai departe s-ar repeta mereu aceleași mulțimi. Se vede și din faptul că, oricare alt număr natural n am lua, va fi adevărat că n ∈ ℕ[1] sau n ∈ ℕ[2]. Alte numere naturale decât cele impare și pare nu avem, deci aceste două mulțimi formează partiția echivalenței.

Este asemănător cu a ne imagina o echivalență pe mulțimea oamenilor: a și b sunt amândoi bărbați sau a și b sunt amândouă femei. Atunci am obține ca partiție mulțimea femeilor și mulțimea bărbaților.

Al doilea exemplu, valoarea absolută:

Fie echivalența R pe mulțimea numerelor întregi ℤ definită astfel: (a, b) ∈ R dacă și numai dacă |a| = |b|. (Acele linii verticale reprezintă valoarea absolută.) Din nou mergem pe rând:

• ℤ[0] = {0}. Zero este în relație doar cu zero.
• ℤ[1] = {−1, 1}. Unu este în relație cu unu și cu minus unu, pentru că |1| = |−1|.
• ℤ[2] = {−2, 2}. Doi este în relație cu doi și cu minus doi.
• ℤ[3] = {−3, 3}.
• …

Probabil este clar cum va continua. Întreaga partiție ar fi deci mulțimea claselor:

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

(Adică toate perechile a, −a, unde a este un număr întreg nenegativ.) Vezi că există infinit de multe clase.