La classe di equivalenza modulo r
Una classe di equivalenza modulo ρ dell'elemento β definita nell'insieme X è l'insieme [β] di tutti gli elementi x di X che sono in relazione con l'elemento βρx. $$ [β]_ρ = \{ x \in X \:\: | \:\: xρβ \} $$
L'elemento a è detto rappresentante della classe.
Ogni classe può essere composta al minimo da un elemento ossia dal rappresentante della classe stessa.
Esempio
La relazione di equivalenza ρ collega gli elementi a,b dell'insieme dei numeri interi Z che soddisfano la seguente relazione a2=b2.
$$ [a] = \{ b \in X \:\: | \:\: a^2 = b^2 \} $$
Ad esempio, una classe è la seguente:
$$ [a]= \{ +2, -2 \} $$
Perché sia +2 che -2 al quadrato restituiscono lo stesso risultato (4)
In generale, in questo esempio ogni classe di equivalenza [a] della relazione ρ è composta da due elementi
$$ [a]= \{ +a, -a \} $$
Fatta eccezione per l'elemento 0, la cui classe di equivalenza è composta da un solo elemento, lo zero.
$$ [0]= \{ 0 \} $$
Un esempio pratico di classe di equivalenza
L'insieme delle parti di A={1,2,3} è il seguente:
$$ P(A) = \{ Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} \} $$
Gli elementi dell'insieme delle parti sono sottoinsiemi di elementi.
Per ipotesi la relazione di equivalenza ρ individua gli elementi di P(A) che hanno la stessa cardinalità, ossia lo stesso numero di elementi.
Quindi, le classi di equivalenza sono determinate da
$$ [a]_ρ = \{ x \in A | xρa \} $$
In questo caso le classi di equivalenza sono le seguenti
La classe di equivalenza di a=Ø è l'insieme vuoto stesso
$$ [Ø]_ρ = \{ Ø \} $$
Attenzione. Non bisogna confondersi. Questo non vuol dire che la classe è vuota. La classe contiene un elemento ossia l'insieme vuoto {Ø} in quanto è un elemento di P(X). Come già detto, la classe di equivalenza contiene al minimo un elemento ossia l'elemento rappresentativo della classe.
La classe di equivalenza di a={1} è il sottoinsieme composto da tutti gli elementi di P(A) con cardinalità uguale a 1, ossia i singletons.
$$ [{1}]_ρ = \{ \{1\}, \{2\}, \{3\} \} $$
Allo stesso modo la classe di equivalenza degli elementi a={2} e a={3} è la stessa di a={1}
$$ [{2}]_ρ= \{ \{1\}, \{2\}, \{3\} \} $$
$$ [{3}]_ρ = \{ \{1\}, \{2\}, \{3\} \} $$
La classe di equivalenza dell'elemento a={1,2} è composta da tutti gli elementi di P(A) con cardinalità uguale a 2
$$ [{1,2}]_ρ = \{ \{1,2\}, \{1,3\}, \{2,3\} \} $$
Anche in questo caso, la classe di equivalenza di a={1,2} è uguale alle classi di equivalenza degli elementi a={1,3} e a={2,3}
$$ [{1,3}]_ρ = \{ \{1,2\}, \{1,3\}, \{2,3\} \} $$
$$ [{2,3}]_ρ = \{ \{1,2\}, \{1,3\}, \{2,3\} \} $$
Infine, la classe di equivalenza dell'elemento a={1,2,3} è il sottoinsieme di elementi di P(A) con cardinalità uguale a 3.
$$ [{1,2,3}]_ρ = \{ \{1,2,3\} \} $$
Nota. Come si può vedere in quest'ultimo caso, ogni classe di equivalenza è composta al minimo dall'elemento rappresentativo.
Le proprietà delle classi di equivalenza
Dato un insieme A, una relazione di equivalenza ρ definita in A e presi due elementi a,b di A, le classi di equivalenza hanno le seguenti proprietà
$$ [a] \ne Ø $$ $$ [a]=[b]_ρ \Leftrightarrow aρb $$ $$ [a] \ne [b]_ρ \Leftrightarrow [a]⋂[b]=Ø $$
Dimostrazione
Prima proprietà
Una classe di equivalenza non è mai vuota.
$$ [a] \ne Ø $$
La relazione di equivalenza è riflessiva.
Quindi, ogni elemento a di A è in relazione con se stesso.
$$ \forall a \in A (aρa) \Rightarrow \forall a \in A \:\:[a] \ne Ø $$
Pertanto, ogni classe di equivalenza contiene almeno un elemento, ossia l'elemento di rappresentanza, e non è vuota.
In conclusione, una classe di equivalenza non è mai vuota. Al minimo contiene l'elemento rappresentante della classe.
Seconda proprietà
Due classi di equivalenza sono uguali se i loro elementi rappresentativi sono in relazione tra loro.
$$ [a]=[b]_ρ \Leftrightarrow aρb $$
Essendo una doppia implicazione, devo dimostrare sia la condizione sufficiente e sia la condizione necessaria.
A] Condizione sufficiente
Se la classe di [a]=[b] allora gli elementi rappresentativi sono in relazione tra loro
$$ [a]=[b]_ρ \Rightarrow aρb $$
L'ipotesi di partenza è l'uguaglianza delle classi [a]=[b], devo dimostrare che aρb sono in relazione.
Secondo la proprietà riflessiva, ogni elemento dell'insieme A appartiene alla sua classe di equivalenza [a] perché ogni classe contiene il suo elemento rappresentativo.
$$ \forall a \in A \in [a] $$
Per ipotesi la classe [a] è uguale alla classe [b]
Quindi, esiste l'elemento a appartiene anche alla classe [b]
$$ [a]=[b] \Rightarrow a \in [b] $$
A sua volta la classe [b] contiene tutti gli elementi x in che soddisfano la relazione xρb
$$ [b]=\{ x \in A | xρb \} $$
Pertanto, l'elemento x=a è in relazione con [b]
$$ aρb $$
Questo dimostra la condizione
$$ [a]=[b] \Rightarrow aρb $$
La condizione sufficiente è dimostrata.
B] Condizione necessaria
Se i rappresentanti delle classi sono in relazione aρb, allora le rispettive classi sono uguali tra loro [a]=[b].
$$ aρb \Rightarrow [a]=[b]_ρ $$
Secondo la tesi la classe [a] è uguale alla classe [b]
Posso riscrivere l'uguaglianza con la doppia inclusione.
$$ [a]=[b] ⇔ [a] ⊆ [b] ∧ [b] ⊆ [a] $$
Secondo la prima inclusione
$$ [a] ⊆ [b] ⇔ \forall x \in [a], x \in [b] $$
Se x appartiene alla classe di a, allora x è in relazione con a.
$$ x \in [a] ==> xρa $$
Secondo l'ipotesi iniziale ho anche la relazione tra a e b
$$ aρb $$
Quindi
$$ xρa \\ aρb $$
Applicando la proprietà transitiva
$$ xρa ∧ aρb \Rightarrow xρb $$
Poiché per ipotesi aρb, allora tutti gli elementi in [a] appartengono anche a [b]
$$ aρb \Rightarrow \forall x \in [a] , x \in [b] \Rightarrow [a] ⊆ [b] $$
Ho così dimostrato che la classe [a] è inclusa nella classe [b]
Ora devo dimostrare la condizione opposta, ossia se anche la classe [b] è inclusa nella classe [a]
Secondo la seconda inclusione
$$ [b] ⊆ [a] ⇔ \forall x \in [b], x \in [a] $$
Se x appartiene alla classe di b, allora x è in relazione con b.
$$ x \in [b] ==> xρb $$
Secondo l'ipotesi iniziale ho anche la relazione tra a e b
$$ aρb $$
che per la proprietà di simmetria è uguale a
$$ bρa $$
Quindi
$$ xρb \\ bρa $$
Applicando la proprietà transitiva
$$ xρb ∧ bρa \Rightarrow xρa $$
Poiché per ipotesi aρb, allora tutti gli elementi in [a] appartengono anche a [b]
$$ aρb \Rightarrow \forall x \in [b] , x \in [a] \Rightarrow [b] ⊆ [a] $$
Ho così dimostrato che la classe [b] è inclusa nella classe [a]
Una volta dimostrata la doppia inclusione [b] ⊆ [a] e [a] ⊆ [b], ho dimostrato anche l'uguaglianza delle classi.
$$ [a] ⊆ [b] ∧ [b] ⊆ [a] \Rightarrow $$
Ho così dimostrato anche la condizione necessaria.
Terza proprietà
Due classi sono diverse se sono disgiunte, ossia se l'intersezione delle classi è uguale al vuoto.
$$ [a] \ne [b] \Leftrightarrow [a]⋂[b]=Ø $$
Essendo una doppia implicazione, devo dimostrare sia la condizione necessaria che sufficiente.
La condizione sufficiente
La dimostrazione è per assurdo
Se l'intersezione [a]⋂[b] è diversa dall'insieme vuoto, allora deve esistere un elemento.
$$ [a]⋂[b] \ne Ø \Rightarrow ∃ a \in [a]⋂[b] $$
Un elemento qualsiasi c dell'intersezione appartiene sia ad [a] che a [b]
Se c appartiene alla classe [a], allora c è in relazione con a e le classi [a] e [c] sono uguali
$$ c \in [a] \Rightarrow cρa \Rightarrow [c] = [a] $$
Se c appartiene alla classe [b], allora c è in relazione anche con b e le classi [b] e [c] sono uguali
$$ c \in [b] \Rightarrow cρb \Rightarrow [b] = [a] $$
Quindi, per transitività le classi [a] e [b] sono uguali
$$ [a]=[b]
Questo però nega l'ipotesi iniziale [a]≠[b].
Quindi, non può esserci nessun elemento nell'intersezione [a]⋂[b]=Ø.
La condizione necessaria
Ora dimostro che se l'intersezione [a]⋂[b] è nulla, allora le classi [a] e [b] sono diverse
$$ [a] ⋂ [b] = ø \Leftrightarrow [a] \ne [b] $$
La dimostrazione è sempre per assurdo.
Se per assurdo le classi sono uguali [a]=[b]
Allora l'intersezione [a]⋂[b] è uguale all'intersezione di [a] per se stessa [a]⋂[a].
Secondo la proprietà di idempotenza, l'intersezione di [a]⋂[a] è uguale ad [a].
$$ [a] ⋂ [a] = [a] $$
Quindi la classe [a] non è vuota
$$ [a] \ne Ø $$
Questo è però un assurdo perché è una negazione dell'ipotesi iniziale [a] ⋂ [b] = Ø.
