Mulțimi factor și partiții
Mulțimea factor A/ρ este alcătuită din toate clasele de echivalență ale mulțimii A, determinate de relația ρ.
Cu alte cuvinte, toate elementele lui A care aparțin aceleiași clase de echivalență [a] sunt reprezentate împreună prin elementul unic [a] din A/ρ.
Aceste clase de echivalență definesc ceea ce numim o partiție a mulțimii A.
Definiție - partiție: O partiție este o colecție de submulțimi nevidente (numite părți) care îndeplinesc simultan condițiile:
[1] Reuniunea tuturor părților coincide cu mulțimea inițială: $$ \bigcup A_n = A $$
[2] Părțile sunt două câte două disjuncte: $$ A_a \cap A_b = \emptyset \quad \text{pentru } a \ne b $$
Exemple
Exemplul 1
Fie A = {1, 2, 3, 4}
Considerăm colecția F de submulțimi:
$$ F = \{ \{1\}, \{3,4\} \} $$
F nu este o partiție, întrucât satisface doar două dintre condițiile cerute:
- Nu este vidă
- Submulțimile sunt disjuncte
Dar reuniunea lor nu acoperă întreaga mulțime A: elementul 2 lipsește.
Exemplul 2
Luăm din nou A = {1, 2, 3, 4}
și colecția F:
$$ F = \{ \{1\}, \{2\}, \{3,4\} \} $$
De această dată, F este o partiție validă, întrucât respectă toate condițiile.
Astfel putem formula teorema fundamentală a relațiilor de echivalență:
- Dacă ρ este o relație de echivalență pe o mulțime A, atunci clasele de echivalență (adică mulțimea factor A/ρ) determină o partiție a lui A.
- Reciproc, orice partiție a lui A induce o relație de echivalență ρ, pentru care fiecare parte a partiției corespunde unei clase de echivalență distincte.
Demonstrație
O relație de echivalență leagă fiecare element de el însuși: aρa.
Prin urmare, orice clasă de echivalență [a] conține cel puțin elementul a.
Acest lucru este valabil pentru orice element x = b, c, d, … din A.
Rezultă că două clase de echivalență sunt fie identice, fie disjuncte.
Dacă un element x aparține și lui [a], și lui [b], atunci:
$$ x \rho a \\ x \rho b $$
Prin simetrie și tranzitivitate deducem că a este în relație cu b:
$$ a \rho x \land x \rho b \Rightarrow a \rho b $$
Deci cele două clase coincid:
$$ a \rho b \Rightarrow [a] = [b] $$
În consecință: dacă două clase au un element comun, ele trebuie să fie identice. Dacă sunt distincte, atunci nu au elemente comune: [a] ⋂ [b] = ∅.
- Dacă [a] ⋂ [b] = ∅, atunci [a] și [b] sunt clase diferite.
- Dacă [a] ⋂ [b] ≠ ∅, atunci [a] = [b].
Prin urmare, clasele de echivalență definite de ρ pe A îndeplinesc exact condițiile unei partiții:
- Fiecare clasă este nevidă: prin definiție, conține cel puțin reprezentantul său.
- Reuniunea claselor este întreaga mulțime A: reunind toate clasele se recuperează A.
- Două clase distincte sunt disjuncte: dacă au un element comun, sunt de fapt aceeași clasă.
Exemplu
Fie A = {1, 2, 3, 4}
Fie F = { {1}, {2}, {3,4} }
Definim o relație de echivalență ρ pe A prin:
$$ a \rho b $$
dacă și numai dacă a și b aparțin aceleiași submulțimi din F:
$$ \forall a, b \in A,\quad a \rho b \Leftrightarrow \exists X \in F \text{ cu } \{a,b\} \subseteq X $$
Perechile care verifică relația sunt:
$$ \rho_F = \{ (1,1), (2,2), (3,3), (4,4), (3,4), (4,3) \} $$
Mulțimea factor A/ρ are următoarele clase de echivalență:
$$ A/\rho = \{ [1], [2], [3], [4] \} $$
iar fiecare clasă conține elementele în relație cu reprezentantul său:
$$ [1] = \{1\} \\ [2] = \{2\} \\ [3] = \{3, 4\} \\ [4] = \{3, 4\} $$
Observație: 1 este în relație doar cu el însuși. La fel și 2. În schimb, 3 și 4 sunt în relație unul cu celălalt.
Scris ca mulțime de submulțimi:
$$ A/\rho = \{ \{1\}, \{2\}, \{3,4\} \} $$
Această mulțime factor A/ρ coincide exact cu partiția F.
Și așa mai departe.
