L'insieme quoziente e le partizioni
L'insieme quoziente A/ρ è l'insieme di tutte le classi di equivalenza modulo ρ dell'insieme A.
Ad esempio, tutti gli elementi di A che appartengono alla classe di equivalenza [a] nell'insieme A/ρ sono indicati come un unico elemento [a]
Le classi di equivalenza modulo ρ dell'insieme A formano una partizione dell'insieme.
Cos'è una partizione? Una partizione è una collezione di sottoinsiemi non vuoti (parti) di un insieme tali che
[1] la somma delle parti è uguale all'insieme $$ U A_n = A $$
[2] l'intersezione tra le parti è nulla, ossia le parti sono disgiunte tra loro $$ A_a ⋂ A_b = Ø $$
Esempi
Esempio 1
L'insieme A contiene gli elementi {1,2,3,4}
L'insieme delle parti F contiene dei sottoinsiemi di A
$$ F = \{ \{1\} , \{ 3,4 \} \} $$
L'insieme F non è una partizione perché soddisfa due proprietà su tre:
- L'insieme F non è vuoto
- L'intersezione tra gli elementi di F è vuota.
Tuttavia, l'unione delle parti di F non è uguale all'insieme A perché manca il singleton {2}
Esempio 2
L'insieme A contiene gli elementi {1,2,3,4}
L'insieme delle parti F contiene dei sottoinsiemi di A
$$ F = \{ \{ 1 \} ,\{ 3,4 \}, \{ 2 \} \} $$
In questo caso si tratta di una partizione perché soddisfa tutte le tre proprietà.
A questo punto posso affermare il teorema fondamentale sulle relazioni di equivalenza
- Data una relazione di equivalenza ρ in A, le classi di equivalenza di A modulo ρ ( ossia l'insieme quoziente A/ρ) determinano una partizione di A
- Ogni partizione di A determina una relazione di equivalenza ρ in cui i sottoinsiemi della partizione sono le classi di equivalenza
Dimostrazione
La relazione di equivalenza aρa mette in relazione l'elemento a con se stesso.
La classe di equivalenza [a] è composta dall'elemento rappresentativo stesso {a}
Questo vale per ogni elemento x=b,c,d,... dell'insieme A.
Quindi, le classi di equivalenza sono disgiunte oppure coincidenti.
Se un elemento x appartiene a [a]⋂[b] e le classi [a] e [b] sono non disgiunte, allora x è in relazione con a e con b.
$$ xρa \\ xρb $$
Quindi, per simmetria e transitività anche a è in relazione con b.
$$ aρx ∧ xρb \Rightarrow aρb $$
Nel caso delle relazioni di equivalenza aρb equivale all'uguaglianza delle classi [a]=[b]
$$ aρb \Rightarrow [a]=[b] $$
Quindi se [a]⋂[b]≠Ø le due classi coincidono [a]=[b]
- Se sono disgiunte [a]⋂[b]=Ø, quindi [a]≠[b]
- Se sono non sono disgiunte [a]⋂[b]≠Ø, quindi [a]=[b]
Ho così dimostrato che le classi di equivalenza ρ di un insieme A rispondono a tutte le proprietà delle partizioni
- Le classi non sono mai vuote. Per definizione includono al minimo l'elemento rappresentativo della classe.
- L'unione delle classi A/ρ è uguale all'insieme delle partizioni di A. Unendo tutti gli elementi che compongono le classi ottengo esattamente l'insieme delle partizioni dell'insieme A .
- L'intersezione di due classi disgiunte è l'insieme vuoto Ø. Se l'intersezione tra le classi non è vuota [a]⋂[b]≠Ø allora le classi sono uguali [a]=[b]
Esempio
Sia A un insieme composto dagli elementi { 1, 2, 3, 4 }
$$ A = \{1, 2, 3, 4 \} $$
e sia F un insieme delle parti composto dai sottoinsiemi {1}, {2}, {3,4}
$$ F = \{ \{ 1 \} ,\{ 3,4 \}, \{ 2 \} \} $$
Ho una relazione di equivalenza ρ che mette in relazione gli elementi a,b dell'insieme A
$$ aρb $$
Questa relazione equivale a un sottoinsieme della partizione F che include gli elementi a e b.
$$ \forall a,b \in A , aρb \Leftrightarrow ∃ X \in F | {a,b} ⊆ X $$
Le coppie di elementi che soddisfano questa relazione sono le seguenti:
$$ ρ_F = \{ (1,1) , (2,2) , (3,3), (4,4), (3,4), (4,3) \} $$
Ora l'insieme quoziente A/ρ è composto dalle seguenti classi di equivalenza
$$ A/ρ = \{ [1], [2], [3], [4] \}$$
Dove ogni classe di equivalenza [x] contiene tutti gli elementi che sono in relazione con l'elemento x.
$$ [1] = \{ 1 \} \\ [2] = \{ 2 \} \\ [3] = \{ 3, 4 \} \\ [4] = \{ 3,4 \} $$
Nota. L'elemento 1 è in relazione solo con se stesso. Idem l'elemento 2. L'elemento 3 è invece in relazione sia con se stesso che con 4. Lo stesso vale per l'elemento 4.
Quindi, sostituendo le classi con gli elementi ottengo
$$ A/ρ = \{ \{ 1 \}, \{ 2 \}, \{ 3,4 \} \}$$
L'insieme quoziente A/ρ coincide con la partizione F.
E così via.
