Gli insiemi sono il linguaggio di base di quasi tutta la matematica discreta: relazioni, funzioni, grafi e probabilità si definiscono a partire da essi. Per chi lavora con i dati sono anche uno strumento quotidiano, perché confrontare due elenchi, trovare elementi in comune o mancanti è esattamente un'operazione tra insiemi.
Che cos'è un insieme
Un insieme è una collezione di oggetti distinti, chiamati elementi, in cui non contano né l'ordine né le ripetizioni. {1, 2, 3}, {3, 1, 2} e {1, 1, 2, 3} sono lo stesso insieme.
Un insieme si descrive in due modi:
- per elencazione: A = {rosso, verde, blu};
- per proprietà: B = {x ∈ ℤ | 0 < x < 10 e x è pari} = {2, 4, 6, 8}.
Il simbolo ∈ indica l'appartenenza: 4 ∈ B, mentre 5 ∉ B. L'insieme senza elementi è l'insieme vuoto, ∅. Il numero di elementi di un insieme finito si chiama cardinalità e si scrive |A|: qui |A| = 3.
Inclusione e uguaglianza
A è sottoinsieme di B (A ⊆ B) se ogni elemento di A appartiene anche a B. Due insiemi sono uguali se e solo se A ⊆ B e B ⊆ A: è proprio questo il metodo standard per dimostrare che due insiemi coincidono, mostrare le due inclusioni separatamente.
Alcuni fatti utili:
- ∅ è sottoinsieme di qualunque insieme (non ha elementi che possano violare la condizione).
- Ogni insieme è sottoinsieme di sé stesso.
- Se A ⊆ B e B ≠ A si dice che A è sottoinsieme proprio di B, e si scrive A ⊂ B.
Non confondete ∈ con ⊆: 1 ∈ {1, 2}, ma {1} ⊆ {1, 2}. E {1} ∈ {{1}, 2}, ma {1} non è sottoinsieme di {{1}, 2}, perché l'elemento 1 non compare in quest'ultimo.
Le operazioni fondamentali
Siano A e B sottoinsiemi di un universo U.
| Operazione | Simbolo | Elementi | Corrispondente logico |
|---|---|---|---|
| Unione | A ∪ B | in A o in B | ∨ |
| Intersezione | A ∩ B | in A e in B | ∧ |
| Differenza | A ∖ B | in A ma non in B | p ∧ ¬q |
| Differenza simmetrica | A △ B | in uno solo dei due | ⊕ (XOR) |
| Complemento | Aᶜ | in U ma non in A | ¬ |
L'ultima colonna non è una coincidenza. Ogni operazione tra insiemi corrisponde a un connettivo logico applicato alla condizione di appartenenza: x ∈ A ∩ B se e solo se x ∈ A ∧ x ∈ B. Per questo tutte le leggi della logica proposizionale hanno un equivalente insiemistico. Le leggi di De Morgan, per esempio, diventano:
- (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
- (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
Due insiemi si dicono disgiunti se A ∩ B = ∅.
Diagrammi di Venn
Un diagramma di Venn rappresenta ogni insieme come una regione chiusa dentro un rettangolo che rappresenta l'universo. Con due insiemi le regioni sono quattro: solo A, solo B, A e B insieme, nessuno dei due. Con tre insiemi diventano otto, una per ogni combinazione di «dentro» e «fuori».
I diagrammi aiutano a intuire un'uguaglianza, ma non la dimostrano in generale: la dimostrazione si fa con le inclusioni o con le leggi algebriche. Oltre tre o quattro insiemi diventano poco leggibili.
Un esempio pratico
Supponiamo di avere l'elenco degli account registrati su un sistema e quello degli account che hanno effettuato l'accesso negli ultimi 90 giorni. In Python:
registrati = {"anna", "bruno", "carla", "dario", "elena"}
attivi = {"anna", "carla", "elena", "fabio"}
registrati & attivi # {'anna', 'carla', 'elena'} accessi regolari
registrati - attivi # {'bruno', 'dario'} account dormienti
attivi - registrati # {'fabio'} anomalia da verificare
registrati ^ attivi # {'bruno', 'dario', 'fabio'} tutte le discrepanze
Le due differenze hanno significati ben diversi. Gli account dormienti sono candidati alla disattivazione; un accesso da un account non registrato è un'incoerenza che in un'analisi di sicurezza va spiegata. Confrontare insiemi in questo modo è uno dei controlli più semplici e più utili che conosco quando si verifica la coerenza tra due fonti di dati.
Gli insiemi di Python sono implementati con tabelle hash, quindi verificare l'appartenenza costa in media un tempo costante. Cercare un elemento in una lista, invece, richiede di scorrerla. Su elenchi lunghi la differenza è enorme.
Proprietà algebriche
Unione e intersezione sono commutative e associative, e ciascuna è distributiva rispetto all'altra:
- A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
- A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Valgono inoltre le leggi di assorbimento, A ∪ (A ∩ B) = A e A ∩ (A ∪ B) = A, e un'identità utile per le differenze: A ∖ B = A ∩ Bᶜ.
In sintesi
- Un insieme ignora ordine e ripetizioni; ∈ indica appartenenza, ⊆ inclusione.
- Per dimostrare A = B si mostrano le due inclusioni A ⊆ B e B ⊆ A.
- Unione, intersezione, differenza e complemento corrispondono a ∨, ∧, ∧¬ e ¬.
- Le leggi della logica, incluse quelle di De Morgan, valgono identiche per gli insiemi.
- Nel lavoro sui dati, intersezioni e differenze rivelano elementi comuni, mancanti e anomali.
