La notazione è uno strumento che ci permette di esprimere idee e operazioni matematiche in modo sintetico e preciso. Una buona notazione può farci risparmiare tempo e fatica, e questo non è certo poco! Ma il suo vantaggio più importante è un altro: può rendere semplici e leggibili ragionamenti che, senza gli strumenti adeguati, diventerebbero lunghi e complicati.
Vediamo un esempio concreto: la dimostrazione della proprietà associativa della differenza simmetrica tra insiemi.
$$ (A \Delta B) \Delta C = A \Delta (B \Delta C) $$
L’obiettivo è dimostrare che il modo in cui raggruppiamo tre insiemi quando applichiamo la differenza simmetrica non cambia il risultato.
Prima di cominciare, fermiamoci un momento e rinfreschiamoci le idee sulle operazioni coinvolte. Ci serviranno alcuni strumenti di logica, un po’ di algebra degli insiemi e, soprattutto, una notazione che ci permetta di passare agevolmente da un linguaggio all’altro.
Insiemi e predicati
Stabiliamo un ambiente di lavoro, o insieme universo, che indicheremo con $U$.
Un insieme $A$ contenuto in $U$ può essere descritto mediante un predicato $P(x)$: una proprietà che può essere vera o falsa per ciascun elemento $x$ dell’universo.
Possiamo quindi definire l’insieme $A$ per comprensione:
$$ A = \{x \in U \mid P(x)\} $$
In altre parole, $A$ contiene esattamente gli elementi di $U$ per i quali $P(x)$ è vera.
Per definizione, dunque, possiamo scrivere:
$$ x \in A \iff P(x) $$
Il simbolo $\iff$ indica un’equivalenza logica: le due proposizioni sono vere e false esattamente negli stessi casi.
Possiamo anche caratterizzare un insieme mediante la sua stessa relazione di appartenenza:
$$ A = \{x \in U \mid x \in A\} $$
Può sembrare una definizione un po’ buffa, perché non ci sta dicendo nulla di nuovo su quali siano gli elementi di $A$. Tuttavia, mette in evidenza un punto fondamentale: un insieme può essere descritto attraverso il predicato che stabilisce se un elemento gli appartiene oppure no.
Questo ci permette di tradurre le operazioni tra insiemi in operazioni logiche sui predicati di appartenenza.
Ad esempio:
-
Unione:
$$ A \cup B = \{x \in U \mid x \in A \lor x \in B\} $$
-
Intersezione:
$$ A \cap B = \{x \in U \mid x \in A \land x \in B\} $$
-
Differenza:
$$ A \setminus B = \{x \in U \mid x \in A \land x \notin B\} $$
I simboli $\lor$ e $\land$ indicano rispettivamente la disgiunzione logica (OR) e la congiunzione logica (AND).
Per la negazione di una proposizione useremo il simbolo $\lnot$. In particolare, la negazione della proposizione $x \in B$ si scrive:
$$ \lnot(x \in B) \iff x \notin B $$
Questa equivalenza può sembrare banale, ma è proprio ciò che ci permette di trasformare le operazioni tra insiemi in formule logiche, manipolarle con le regole della logica e poi tornare agli insiemi.
Una prima dimostrazione: due modi di scrivere la differenza simmetrica
La differenza simmetrica tra due insiemi $A$ e $B$ è l’insieme degli elementi che appartengono a uno solo dei due insiemi.
La definiamo così:
$$ A \Delta B = (A \setminus B) \cup (B \setminus A) $$
Possiamo anche descriverla in un altro modo:
$$ A \Delta B = (A \cup B) \setminus (A \cap B) $$
La seconda espressione dice che prendiamo tutti gli elementi che appartengono ad almeno uno dei due insiemi ed eliminiamo quelli che appartengono a entrambi.
Dimostriamo che le due definizioni sono equivalenti. Per farlo, lavoriamo sui predicati di appartenenza.
$$ \begin{aligned} x \in (A \setminus B) \cup (B \setminus A) &\iff x \in (A \setminus B) \lor x \in (B \setminus A) \\ &\iff (x \in A \land x \notin B) \lor (x \in B \land x \notin A) \\ &\iff (x \in A \lor x \in B) \land \underset{Tautologia}{(x \in A \lor x \notin A)} \land \underset{Tautologia}{(x \notin B \lor x \in B)} \land (x \notin A \lor x \notin B) \\ &\iff (x \in A \lor x \in B) \land \lnot(x \in A \land x \in B) \\ &\iff x \in (A \cup B) \land x \notin (A \cap B) \\ &\iff x \in (A \cup B) \setminus (A \cap B) \end{aligned} $$
Abbiamo quindi dimostrato che un elemento appartiene al primo insieme se e solo se appartiene al secondo. Per estensionalità, i due insiemi sono uguali:
$$ (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B) $$
Il principio di estensionalità afferma proprio questo: due insiemi sono uguali se e solo se hanno gli stessi elementi.
Notiamo anche un piccolo vantaggio della notazione. Scrivere $\iff$ al posto di una semplice uguaglianza rende esplicito che stiamo confrontando proposizioni logiche, non insiemi. Non è un dettaglio puramente estetico: una notazione precisa ci aiuta a capire che tipo di oggetto stiamo manipolando in ogni passaggio.
La dimostrazione lunga: sviluppiamo le differenze
Ottimo, abbiamo ripassato gli strumenti che ci servono. Possiamo affrontare il problema iniziale:
$$ (A \Delta B) \Delta C = A \Delta (B \Delta C) $$
Cercheremo di sviluppare entrambi i membri fino a ottenere una stessa espressione.
Partiamo dal membro sinistro. Sostituiamo la definizione di differenza simmetrica:
$$ \begin{aligned} (A \Delta B) \Delta C &= ((A \setminus B) \cup (B \setminus A)) \Delta C \\ &= (((A \setminus B) \cup (B \setminus A)) \setminus C) \;\cup\; (C \setminus ((A \setminus B) \cup (B \setminus A))) \end{aligned} $$
La notazione comincia già a far girare la testa, ma noi procediamo imperterriti. Per rendere i passaggi più leggibili, studiamo prima due proprietà della differenza tra insiemi.
La differenza distribuisce sull’unione nel primo argomento
Consideriamo:
$$ (X \cup Y) \setminus C $$
Traduciamo il predicato di appartenenza:
$$ \begin{aligned} x \in (X \cup Y) \land x \notin C &\iff (x \in X \lor x \in Y) \land x \notin C \\ &\iff (x \in X \land x \notin C) \lor (x \in Y \land x \notin C) \end{aligned} $$
Ritornando agli insiemi, otteniamo:
$$ (X \cup Y) \setminus C = (X \setminus C) \cup (Y \setminus C) $$
La differenza si distribuisce quindi sull’unione quando l’unione compare nel primo argomento, cioè a sinistra del simbolo $\setminus$.
La differenza rispetto a un’unione nel secondo argomento
Che cosa succede, invece, quando l’unione compare nel secondo argomento?
$$ C \setminus (X \cup Y) $$
Traduciamo nuovamente il predicato:
$$ \begin{aligned} x \in C \land x \notin (X \cup Y) &\iff x \in C \land \lnot(x \in X \lor x \in Y) \\ &\iff x \in C \land (x \notin X \land x \notin Y) \\ &\iff (x \in C \land x \notin X) \land x \notin Y \end{aligned} $$
Otteniamo:
$$ C \setminus (X \cup Y) = (C \setminus X) \setminus Y $$
In questo caso non otteniamo un’unione di differenze, ma una differenza applicata due volte.
È importante non confondere i due risultati: la posizione dell’unione rispetto al simbolo $\setminus$ cambia la formula che possiamo utilizzare. Una buona notazione aiuta proprio a individuare queste differenze strutturali.
Torniamo al membro sinistro
Riprendiamo lo sviluppo di $(A \Delta B) \Delta C$ e applichiamo le proprietà appena dimostrate.
$$ \begin{aligned} (A \Delta B) \Delta C &= ((A \setminus B) \cup (B \setminus A)) \Delta C \\ &= (((A \setminus B) \cup (B \setminus A)) \setminus C) \;\cup\; (C \setminus ((A \setminus B) \cup (B \setminus A))) \\ &= ((A \setminus B) \setminus C) \;\cup\; ((B \setminus A) \setminus C) \;\cup\: (C \setminus ((A \setminus B) \cup (B \setminus A))) \\ &= (A \setminus (B \cup C)) \;\cup\; (B \setminus (A \cup C)) \;\cup\; (C \setminus ((A \setminus B) \cup (B \setminus A))) \end{aligned} $$
Nel passaggio finale abbiamo usato l’identità:
$$ (X \setminus Y) \setminus Z = X \setminus (Y \cup Z) $$
Ora dobbiamo semplificare il termine che contiene la differenza tra $C$ e un’unione.
$$ C \setminus ((A \setminus B) \cup (B \setminus A)) $$
Per farlo, usiamo ancora la proprietà appena dimostrata:
$$ \begin{aligned} C \setminus ((A \setminus B) \cup (B \setminus A)) &= (C \setminus (A \setminus B)) \setminus (B \setminus A) \\ &= ((C \setminus A) \cup (C \cap B)) \setminus (B \setminus A) \\ &= ((C \setminus A) \setminus (B \setminus A)) \cup ((C \cap B) \setminus (B \setminus A)) \\ &= (C \setminus (A \cup B)) \cup (A \cap B \cap C) \end{aligned} $$
Nel terzo passaggio abbiamo utilizzato l’identità:
$$ X \setminus (Y \setminus Z) = (X \setminus Y) \cup (X \cap Z) $$
L’ultimo passaggio si può verificare osservando che il primo termine contiene gli elementi di $C$ che non appartengono né ad $A$ né a $B$, mentre il secondo contiene gli elementi comuni ai tre insiemi.
Sostituendo il risultato, otteniamo:
$$ \begin{aligned} (A \Delta B) \Delta C &= (A \setminus (B \cup C)) \\ &\quad \cup (B \setminus (A \cup C)) \\ &\quad \cup (C \setminus (A \cup B)) \\ &\quad \cup (A \cap B \cap C) \end{aligned} $$
Abbiamo sviluppato il membro sinistro. Adesso dovremmo fare altrettanto con il membro destro:
$$ A \Delta (B \Delta C) $$
Il procedimento è analogo. Sostituendo la definizione di differenza simmetrica e applicando le stesse proprietà, arriviamo a:
$$ \begin{aligned} A \Delta (B \Delta C) &= (A \setminus (B \cup C)) \\ &\quad \cup (B \setminus (A \cup C)) \\ &\quad \cup (C \setminus (A \cup B)) \\ &\quad \cup (A \cap B \cap C) \end{aligned} $$
I due membri sono uguali alla stessa espressione. Perciò:
$$ \boxed{(A \Delta B) \Delta C = A \Delta (B \Delta C)} $$
La proprietà associativa è dimostrata.
Certo che lo sviluppo di tutti questi conti non è stato affatto agile! Siamo passati dalle operazioni tra insiemi ai predicati di appartenenza, abbiamo manipolato formule logiche e poi siamo tornati agli insiemi. La quantità di notazione e di trasformazioni rende la dimostrazione piuttosto faticosa.
Possiamo fare di meglio?
Introduciamo una nuova notazione: il complementare di un insieme rispetto all’universo $U$.
$$ A^c = \{x \in U \mid x \notin A\} $$
In altre parole, $A^c$ contiene tutti gli elementi dell’universo che non appartengono ad $A$.
Questa semplice definizione ci permette di riscrivere la differenza tra insiemi usando soltanto intersezioni e complementari:
$$ A \setminus B = A \cap B^c $$
La differenza simmetrica diventa quindi:
$$ \begin{aligned} A \Delta B &= (A \setminus B) \cup (B \setminus A) \\ &= (A \cap B^c) \cup (B \cap A^c) \end{aligned} $$
Possiamo anche esprimere le leggi di De Morgan in una forma particolarmente compatta:
$$ \begin{aligned} (A \cup B)^c &= A^c \cap B^c \\ (A \cap B)^c &= A^c \cup B^c \end{aligned} $$
La prima legge dice che non appartenere all’unione equivale a non appartenere a entrambi gli insiemi. La seconda dice che non appartenere all’intersezione equivale a non appartenere ad almeno uno dei due.
Abbiamo introdotto una nuova notazione, ma non una nuova operazione fondamentale: il complementare è definito attraverso l’appartenenza e la negazione. Il vantaggio è che possiamo riutilizzare le regole già conosciute, riducendo il numero di simboli e di trasformazioni da gestire.
La stessa dimostrazione, con una notazione più efficace
Torniamo alla proprietà associativa della differenza simmetrica. Questa volta utilizziamo il complementare e le leggi di De Morgan.
Partiamo dal membro sinistro:
$$ \begin{aligned} (A \Delta B) \Delta C &= ((A \cap B^c) \cup (B \cap A^c)) \Delta C \\ &= (((A \cap B^c) \cup (B \cap A^c)) \cap C^c) \cup (C \cap ((A \cap B^c) \cup (B \cap A^c))^c) \\ &= (A \cap B^c \cap C^c) \cup (B \cap A^c \cap C^c) \cup (C \cap ((A \cap B^c)^c \cap (B \cap A^c)^c)) \\ &= (A \cap B^c \cap C^c) \cup (B \cap A^c \cap C^c) \cup (C \cap ((A^c \cup B) \cap (B^c \cup A))) \\ &= (A \cap B^c \cap C^c) \cup (B \cap A^c \cap C^c) \cup (C \cap A^c \cap B^c) \cup (C \cap A \cap B) \end{aligned} $$
Nell’ultimo abbiamo usato la distributività e osservato che:
$$ A^c \cap A = \varnothing \qquad B^c \cap B = \varnothing $$
I termini che contengono queste intersezioni sono quindi vuoti e possono essere eliminati dall’unione.
Otteniamo così:
$$ \begin{aligned} (A \Delta B) \Delta C &= (A \cap B^c \cap C^c) \\ &\quad \cup (B \cap A^c \cap C^c) \\ &\quad \cup (C \cap A^c \cap B^c) \\ &\quad \cup (A \cap B \cap C) \end{aligned} $$
Sviluppando nello stesso modo il membro destro, si ottiene esattamente la medesima espressione:
$$ \begin{aligned} A \Delta (B \Delta C) &= (A \cap B^c \cap C^c) \\ &\quad \cup (B \cap A^c \cap C^c) \\ &\quad \cup (C \cap A^c \cap B^c) \\ &\quad \cup (A \cap B \cap C) \end{aligned} $$
Di conseguenza:
$$ \boxed{(A \Delta B) \Delta C = A \Delta (B \Delta C)} $$
La proprietà associativa è dimostrata anche con questo secondo metodo.
Non è soltanto una questione di abbreviare
Abbiamo ottenuto lo stesso risultato in entrambi i casi, ma con strumenti diversi.
La prima dimostrazione ha richiesto di manipolare ripetutamente le differenze tra insiemi, prestando attenzione alla posizione delle unioni e delle intersezioni. La seconda ha trasformato le differenze in intersezioni con complementari, consentendoci di applicare in modo sistematico le leggi di De Morgan e la distributività.
Non è soltanto una questione di fatica: una buona notazione mette in evidenza la struttura del problema e rende più facile riconoscere quali regole applicare.
La notazione del complementare, in questo caso, non ha semplicemente abbreviato le formule. Ha ricondotto il problema a un insieme di operazioni più uniforme, governato da regole che conosciamo bene.
Naturalmente, non esiste una notazione migliore in assoluto. Una notazione efficace dipende dal problema che vogliamo risolvere e dalle proprietà che desideriamo mettere in evidenza. Per questo, conoscere più modi di rappresentare lo stesso oggetto matematico è uno strumento importante per chi fa matematica.
La prossima volta che vi trovate davanti a una dimostrazione particolarmente laboriosa, provate a fermarvi e a chiedervi:
«Conosco abbastanza bene la notazione che sto usando? Esiste un modo diverso di rappresentare questo problema che renda più semplici i passaggi?»
A volte, la strada più breve per una dimostrazione non consiste nel fare meno calcoli, ma nel trovare il linguaggio giusto per farli.