Relazione di equivalenza

La relazione di equivalenza è una relazione binaria su un insieme che è riflessiva, simmetrica e transitiva.

Motivazione

La relazione di equivalenza è una sorta di affinamento della relazione di uguaglianza. Possiamo sempre decidere se due elementi di un insieme sono uguali, cioè se a = b. A volte però ci è utile sapere se due elementi sono soltanto simili, non necessariamente uguali. In altre parole, se hanno in comune una certa proprietà fondamentale. Per esempio due libri possiamo considerarli simili se hanno lo stesso genere, oppure, con l’equivalenza: due libri sono equivalenti se hanno lo stesso genere.

Che cosa ci aspetteremmo da un’equivalenza di questo tipo? Prendiamo un altro esempio. Due parole sono simili/equivalenti se hanno la stessa lunghezza.

Probabilmente ci aspetteremmo che, misurando la somiglianza di due parole uguali, risultino simili. Quindi per ogni parola deve valere che è simile/equivalente a se stessa. Nel linguaggio delle relazioni: la relazione di equivalenza deve essere riflessiva.

Inoltre, se la parola «fiume» è simile/equivalente alla parola «Marco», allora ci aspettiamo certamente che anche la parola «Marco» sia equivalente alla parola «fiume». In altre parole, l’ordine non conta. Nel linguaggio delle relazioni: la relazione di equivalenza deve essere simmetrica.

Infine, se la parola «mare» è simile/equivalente alla parola «lupo» e la parola «lupo» è equivalente alla parola «naso», allora ci aspettiamo che anche la coppia di parole «mare» e «naso» sia equivalente. Quindi la relazione di equivalenza deve essere anche transitiva.

Dall’equivalenza non ci aspettiamo nient’altro.

Esempi

Altri esempi di equivalenze:

• Abitare nella stessa città. Luca abita sicuramente nella stessa città di Luca (riflessività). Se Luca abita nella stessa città di Matteo, anche Matteo abita nella stessa città di Luca (simmetria). E se Matteo abita nella stessa città di Marco, anche Luca abita nella stessa città di Marco (transitività).
• Brani dello stesso autore. Il brano «Brano 1» ha sicuramente lo stesso autore del brano «Brano 1» (riflessività). Se i brani «Brano 1» e «Brano 2» hanno lo stesso autore, anche «Brano 2» e «Brano 1» hanno lo stesso autore (simmetria). E se «Brano 2» e «Brano 3» hanno lo stesso autore, anche «Brano 1» e «Brano 3» hanno lo stesso autore (transitività).
• (a; b) ∈ R se e solo se a − b è un numero pari; a, b sono numeri interi. Riflessività: a − a = 0, zero è un numero pari. Simmetria: poniamo c = a − b. Allora b − a = −(a − b) = −c. Se c è pari, deve essere pari anche −c. Transitività: poniamo p = a − b e inoltre q = b − c. Sappiamo che sia p sia q sono numeri pari. Ora dobbiamo dimostrare che a − c è un numero pari. In questa uguaglianza al posto di c sostituiamo c = b − q: a − (b − q), che è uguale a a − b + q. Dalle ipotesi sappiamo che a − b è un numero pari. Se a un numero pari sommiamo un altro numero pari q, otteniamo di nuovo un numero pari.
• L’uguaglianza. L’uguaglianza è un’equivalenza, ed è anche la più piccola equivalenza su un qualsiasi insieme M.

Equivalenza banale

Abbiamo un insieme non vuoto M. Qual è la più piccola equivalenza possibile R sull’insieme M? Il più piccolo sottoinsieme possibile del prodotto cartesiano M × M è l’insieme vuoto ∅. L’insieme vuoto soddisfa le condizioni di un’equivalenza?

È sicuramente simmetrica: poiché la relazione R non ha elementi, la condizione di simmetria è soddisfatta automaticamente e in modo banale. Lo stesso vale per la transitività. Il problema è la riflessività. La definizione dice che per tutti gli elementi x dell’insieme M vale (x; x) ∈ R. È soddisfatta? L’insieme M è non vuoto, quindi contiene un elemento, per esempio q. La coppia (q; q) appartiene alla relazione R? No. La relazione R non è quindi riflessiva.

Qual è la più piccola relazione che soddisfa la riflessività? La relazione di uguaglianza. La relazione R deve contenere almeno le coppie (x; x) per tutti gli elementi di M. E questa è proprio la relazione identica. Una relazione di questo tipo è simmetrica? Si vede facilmente che lo è. Allo stesso modo si vede facilmente che è anche transitiva. La più piccola relazione di equivalenza sull’insieme M è quindi la relazione identica, che indichiamo con id_M, e contiene le coppie (x; x) per tutti gli x ∈ M.

Qual è la più grande equivalenza possibile sull’insieme M? Il sottoinsieme più grande è l’intero insieme M × M. Soddisfa le condizioni di un’equivalenza? Si vede facilmente di sì.

Classe di equivalenza

Ogni equivalenza divide l’insieme M in un sistema di insiemi disgiunti, che chiamiamo classi di equivalenza.

Sia M l’insieme di tutte le parole ed R l’equivalenza «parola della stessa lunghezza». Quindi (a; b) ∈ R se e solo se le parole a e b hanno la stessa lunghezza. Questa equivalenza divide l’insieme delle parole in alcuni insiemi più piccoli, che conterranno sempre parole della stessa lunghezza. Le singole classi di equivalenza possiamo distinguerle con un pedice, che indicherà anche la lunghezza delle parole nell’insieme considerato:

• M₁ = {a, e, i, o, …}
• M₂ = {di, da, in, su, mi, …}
• M₃ = {per, con, tre, mai, …}
• M₄ = {casa, mare, lupo, pane, …}
• …

Nota due cose: 1) i singoli insiemi sono a due a due disgiunti, non hanno alcun elemento in comune. 2) tutti gli elementi di ciascun insieme sono equivalenti tra loro. Tutte le parole dell’insieme M₃ sono equivalenti tra loro, perché tutte hanno lunghezza tre, cioè la stessa lunghezza, che è la condizione dell’equivalenza.

Inoltre ogni elemento definisce in modo univoco la propria classe di equivalenza. Di solito lo scriviamo con la notazione M[x], dove x ∈ M. Se scrivessimo M[per], definiremmo in modo univoco la classe di equivalenza che abbiamo già indicato con M₃.

Come troviamo la classe di equivalenza, se conosciamo un certo x ∈ M? Scorriamo tutti gli elementi di M e verifichiamo quali sono equivalenti all’elemento x. Saranno tutti gli elementi che fanno parte della classe di equivalenza M[x].

Per M[per] scorreremmo tutte le parole di M e terremmo in M₃ quelle di lunghezza tre.

Definizione e proprietà della classe di equivalenza

La classe di equivalenza possiamo definirla così. Sia M un insieme e R un’equivalenza definita su di esso. Per classe della partizione che contiene l’elemento x ∈ M intendiamo:

$$M[x]=\{y\in M;(x;y)\in R\}$$

La definizione dice che sono tutti gli y equivalenti all’elemento dato x. Poiché la relazione di equivalenza è riflessiva, in questo modo vi rientra anche l’elemento x stesso, perché x è equivalente a se stesso.

Per partizione di un’equivalenza intendiamo poi l’insieme di tutte le classi di equivalenza. La partizione dell’insieme di tutte le parole sarebbe quindi l’insieme {M₁, M₂, M₃, …}.

Proprietà fondamentali delle classi di equivalenza:

• (a; b) ∈ R se e solo se M[a] = M[b]. Se abbiamo due elementi a, b equivalenti, le loro classi di equivalenza devono essere uguali.
• Viceversa, se non vale (a; b) ∈ R, allora vale anche M[a] ≠ M[b], più precisamente M[a] ∩ M[b] = ∅. Se abbiamo due elementi non equivalenti, le loro classi della partizione sono disgiunte.
• L’unione di tutte le classi di equivalenza deve dare l’insieme originale M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (La scrittura precedente vale solo per un numero finito di classi di equivalenza, ma in generale ce ne possono essere infinite.)

Esempi di partizioni di un’equivalenza

Primo esempio, numeri dispari e pari:

Sia R una semplice equivalenza definita sui numeri naturali diversi da zero N. (a; b) ∈ R se e solo se a e b sono entrambi dispari oppure a e b sono entrambi pari. Esempi di elementi: (1; 7), (13; 9), (4; 6), (8; 136). Determiniamo ora la partizione di questa equivalenza in classi di equivalenza.

Procediamo per gradi. A che cosa sarà uguale la classe N[1]? Dobbiamo trovare tutti i numeri equivalenti al numero uno. Secondo la condizione di equivalenza sono tutti i numeri dispari, quindi N[1] = {1, 3, 5, 7, 9, …}.

A che cosa sarà uguale la classe N[2]? Troviamo tutti i numeri equivalenti al due. Sono tutti i numeri pari: N[2] = {2, 4, 6, 8, 10, …}.

Ora N[3]. Quali numeri sono equivalenti al tre? Tutti i numeri dispari. Otteniamo però l’insieme N[1], che abbiamo già calcolato due paragrafi fa. Lo stesso vale per N[4], dove otteniamo di nuovo l’insieme dei numeri pari.

Vediamo che proseguendo si ripeterebbero sempre gli stessi insiemi. Lo si vede anche dal fatto che, qualunque altro numero naturale n prendiamo, varrà n ∈ N[1] oppure n ∈ N[2]. Non abbiamo altri numeri naturali oltre ai dispari e ai pari, quindi questi due insiemi formano la partizione dell’equivalenza.

È simile a immaginare un’equivalenza sull’insieme delle persone: a e b sono entrambi uomini oppure a e b sono entrambe donne. Come partizione otterremmo l’insieme delle donne e l’insieme degli uomini.

Secondo esempio, valore assoluto:

Sia R un’equivalenza sull’insieme dei numeri interi Z definita così: (a; b) ∈ R se e solo se |a| = |b|. (Quelle barre verticali indicano il valore assoluto.) Procediamo di nuovo per gradi:

• Z[0] = {0}. Lo zero è in relazione soltanto con lo zero.
• Z[1] = {−1, 1}. L’uno è in relazione con l’uno e con il meno uno, perché |1| = |−1|.
• Z[2] = {−2, 2}. Il due è in relazione con il due e con il meno due.
• Z[3] = {−3, 3}.
• …

Probabilmente è chiaro come proseguirà. L’intera partizione sarebbe quindi l’insieme delle classi:

$$\{\{a,-a\};a\in {\mathbb{Z}}_0^{+}\}$$

(Cioè tutte le coppie a, −a, dove a è un numero intero non negativo.) Vedi che le classi sono infinite.