Molto spesso, in matematica come nel lavoro con i dati, si vuole trattare come «uguali» cose che uguali non sono: due indirizzi email che differiscono solo per le maiuscole, due frazioni come 1/2 e 2/4, due file con lo stesso contenuto ma nomi diversi. Le relazioni di equivalenza sono lo strumento che rende rigoroso questo «essere uguali da un certo punto di vista», e il loro risultato naturale è una partizione dell'insieme in gruppi.
Definizione
Una relazione ~ su un insieme A è una relazione di equivalenza se è:
- riflessiva: a ~ a per ogni a;
- simmetrica: se a ~ b allora b ~ a;
- transitiva: se a ~ b e b ~ c allora a ~ c.
Le tre proprietà catturano esattamente ciò che ci aspettiamo da una nozione di «uguaglianza»: ogni cosa è uguale a sé, l'uguaglianza non ha direzione e si propaga lungo le catene.
Esempi
- Stesso resto nella divisione per n: a ~ b se a e b danno lo stesso resto diviso per n. È la congruenza modulo n, base dell'aritmetica modulare.
- Stessa lunghezza: sulle stringhe, s ~ t se hanno lo stesso numero di caratteri.
- Stesso contenuto: sui file, f ~ g se il loro contenuto è identico byte per byte.
- Uguaglianza senza maiuscole: sulle stringhe, s ~ t se coincidono dopo averle convertite in minuscolo.
- Frazioni equivalenti: a/b ~ c/d se a · d = b · c.
Un controesempio istruttivo: «differiscono al più di 1», sui numeri interi, è riflessiva e simmetrica ma non transitiva (1 ~ 2 e 2 ~ 3, ma 1 e 3 differiscono di 2). Lo stesso problema si presenta con la «somiglianza» tra stringhe basata su una soglia: piccole differenze accumulate lungo una catena portano a due elementi molto diversi. Per questo una relazione di somiglianza non va trattata come un'equivalenza senza pensarci.
Classi di equivalenza
Data una relazione di equivalenza, la classe di equivalenza di un elemento a è l'insieme di tutti gli elementi equivalenti ad a:
[a] = {x ∈ A | x ~ a}
Con la congruenza modulo 3 sugli interi ci sono tre classi:
- [0] = {…, −3, 0, 3, 6, …}
- [1] = {…, −2, 1, 4, 7, …}
- [2] = {…, −1, 2, 5, 8, …}
Qualsiasi elemento della classe può fare da rappresentante: [1] = [4] = [−2]. L'insieme delle classi si chiama insieme quoziente e si scrive A/~. Nel caso della congruenza modulo n, il quoziente è indicato con ℤ/nℤ o ℤₙ, e ha n elementi.
Il teorema fondamentale: equivalenze e partizioni
Una partizione di A è una famiglia di sottoinsiemi non vuoti di A, a due a due disgiunti, la cui unione è A. Ogni elemento sta in uno e un solo blocco.
Il risultato centrale è che relazioni di equivalenza e partizioni sono la stessa cosa vista da due lati:
- Le classi di una relazione di equivalenza formano una partizione. Ogni a sta nella sua classe [a] per la riflessività; due classi sono o identiche o disgiunte, grazie a simmetria e transitività.
- Viceversa, ogni partizione definisce un'equivalenza: a ~ b se e solo se a e b stanno nello stesso blocco.
Questo spiega perché il raggruppamento è un'operazione così naturale. Un GROUP BY in SQL partiziona le righe in base al valore di una o più colonne; implicitamente usa la relazione di equivalenza «hanno gli stessi valori in quelle colonne».
Calcolare le classi in pratica
Quando l'equivalenza è data da una funzione chiave, come «convertire in minuscolo» o «calcolare l'hash», le classi si ottengono raggruppando per chiave:
from collections import defaultdict
def classi(elementi, chiave):
gruppi = defaultdict(list)
for e in elementi:
gruppi[chiave(e)].append(e)
return list(gruppi.values())
classi(["Mario@ditta", "mario@ditta", "anna@studio"], str.lower)
# [['Mario@ditta', 'mario@ditta'], ['anna@studio']]
Spesso però si conoscono solo alcune coppie equivalenti, e il resto deriva dalla transitività: «il record 1 è lo stesso cliente del record 7, il 7 dello stesso del 12». Per trovare le classi in questo caso si usa la struttura union-find (o insiemi disgiunti): ogni elemento parte da solo, ogni coppia nota fonde i due gruppi, e alla fine ogni gruppo è una classe. Con le ottimizzazioni di compressione dei cammini e unione per rango, le operazioni sono praticamente a tempo costante. Nella deduplicazione di anagrafiche e nell'aggregazione di indicatori raccolti da fonti diverse, è uno degli strumenti che uso più volentieri.
In sintesi
- Una relazione di equivalenza è riflessiva, simmetrica e transitiva.
- La classe [a] raccoglie gli elementi equivalenti ad a; l'insieme delle classi è il quoziente.
- Equivalenze e partizioni si corrispondono esattamente: ogni equivalenza raggruppa, ogni raggruppamento è un'equivalenza.
- Le relazioni di somiglianza con soglia di solito non sono transitive.
- Con una funzione chiave si raggruppa per chiave; con coppie sparse si usa union-find.
