Clase de echivalență modulo ρ
Fie X o mulțime și ρ o relație de echivalență pe X. Clasa de echivalență a unui element β este mulțimea [β] alcătuită din toate elementele x din X aflate în relație cu β prin ρ: $$ [\beta]_\rho = \{ x \in X \:\: | \:\: x\rho\beta \} $$
Elementul a poartă numele de reprezentant al clasei.
Orice clasă de echivalență conține cel puțin un element: reprezentantul său.
Exemplu
Considerăm relația de echivalență ρ definită pe mulțimea numerelor întregi ℤ, unde două elemente a și b sunt în relație dacă și numai dacă \( a^2 = b^2 \).
$$ [a] = \{ b \in X \:\: | \:\: a^2 = b^2 \} $$
De exemplu, o clasă de echivalență este:
$$ [a] = \{ +2, -2 \} $$
întrucât atât +2, cât și -2 au același pătrat: 4.
În general, sub această relație, fiecare clasă [a] este alcătuită din două elemente:
$$ [a] = \{ +a, -a \} $$
cu excepția cazului a = 0, a cărui clasă conține un singur element:
$$ [0] = \{ 0 \} $$
Exemplu concret de clasă de echivalență
Să considerăm mulțimea putere a lui A = {1, 2, 3}:
$$ P(A) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \} $$
Elementele lui P(A) sunt toate submulțimile lui A.
Definim o relație de echivalență ρ pe P(A) astfel încât două submulțimi sunt echivalente dacă au aceeași cardinalitate, adică același număr de elemente.
Clasa de echivalență a unui element a se notează:
$$ [a]_\rho = \{ x \in P(A) \ | \ x\rho a \} $$
În acest context, clasele de echivalență sunt următoarele:
Clasa lui a = ∅ este mulțimea unitate formată doar din mulțimea vidă:
$$ [\emptyset]_\rho = \{ \emptyset \} $$
Observație: Aceasta nu înseamnă că clasa este vidă. Ea conține exact un element - mulțimea vidă - , care aparține lui P(A). După cum am menționat, orice clasă de echivalență conține cel puțin reprezentantul său.
Clasa lui a = {1} include toate submulțimile unitare ale lui A:
$$ [{1}]_\rho = \{ \{1\}, \{2\}, \{3\} \} $$
Analog, clasele de echivalență ale lui {2} și {3} coincid:
$$ [{2}]_\rho = \{ \{1\}, \{2\}, \{3\} \} $$
$$ [{3}]_\rho = \{ \{1\}, \{2\}, \{3\} \} $$
Clasa lui {1,2} reunește toate submulțimile cu două elemente:
$$ [{1,2}]_\rho = \{ \{1,2\}, \{1,3\}, \{2,3\} \} $$
Același lucru este valabil și pentru clasele lui {1,3} și {2,3}:
$$ [{1,3}]_\rho = \{ \{1,2\}, \{1,3\}, \{2,3\} \} $$
$$ [{2,3}]_\rho = \{ \{1,2\}, \{1,3\}, \{2,3\} \} $$
În sfârșit, clasa lui {1,2,3} conține un singur element, ea însăși:
$$ [{1,2,3}]_\rho = \{ \{1,2,3\} \} $$
Observație: Și în acest caz vedem că orice clasă de echivalență conține cel puțin un element: reprezentantul său.
Proprietățile claselor de echivalență
Fie A o mulțime și ρ o relație de echivalență definită pe A. Pentru orice a, b ∈ A se verifică următoarele proprietăți:
$$ [a] \ne \emptyset $$ $$ [a] = [b]_\rho \Leftrightarrow a\rho b $$ $$ [a] \ne [b]_\rho \Leftrightarrow [a] \cap [b] = \emptyset $$
Demonstrație
1. Prima proprietate
Nicio clasă de echivalență nu este vidă.
$$ [a] \ne \emptyset $$
Rezultatul decurge direct din reflexivitatea relației: orice element \( a \in A \) este în relație cu el însuși.
$$ \forall a \in A,\ (a\rho a) \Rightarrow [a] \ne \emptyset $$
Prin urmare, fiecare clasă de echivalență conține cel puțin reprezentantul său.
2. A doua proprietate
Două clase de echivalență coincid dacă și numai dacă reprezentanții lor sunt în relație:
$$ [a] = [b]_\rho \Leftrightarrow a\rho b $$
Fiind o bicondițională, trebuie demonstrată în ambele sensuri.
A] Sens direct (suficiență)
Dacă \( [a] = [b] \), atunci, întrucât \( a \in [a] \), urmează că \( a \in [b] \). Conform definiției, aceasta implică \( a\rho b \).
B] Sens invers (necesitate)
Presupunem că \( a\rho b \). Pentru a arăta că \( [a] = [b] \), este suficient să verificăm dubla incluziune:
$$ [a] \subseteq [b] \quad \text{și} \quad [b] \subseteq [a] $$
Prima incluziune: Fie \( x \in [a] \), adică \( x\rho a \). Cum \( a\rho b \), prin tranzitivitate rezultă \( x\rho b \), deci \( x \in [b] \).
A doua incluziune: Fie \( x \in [b] \), adică \( x\rho b \). Din \( a\rho b \) avem \( b\rho a \) prin simetrie. Aplicând tranzitivitatea obținem \( x\rho a \), deci \( x \in [a] \).
Prin urmare:
$$ [a] = [b] $$
3. A treia proprietate
Două clase de echivalență distincte sunt disjuncte:
$$ [a] \ne [b] \Leftrightarrow [a] \cap [b] = \emptyset $$
Sens direct: Să presupunem că \( [a] \cap [b] \ne \emptyset \), deci există \( c \in [a] \cap [b] \). Atunci \( c\rho a \) și \( c\rho b \), ceea ce implică \( [a] = [c] = [b] \), în contradicție cu ipoteza. Rezultă deci:
$$ [a] \ne [b] \Rightarrow [a] \cap [b] = \emptyset $$
Sens invers: Dacă presupunem că \( [a] = [b] \), atunci:
$$ [a] \cap [b] = [a] \cap [a] = [a] \ne \emptyset $$
ceea ce contrazice ipoteza că \( [a] \cap [b] = \emptyset \). Prin urmare:
$$ [a] \cap [b] = \emptyset \Rightarrow [a] \ne [b] $$
