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 a²=b².

$$[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] = Ø.