Per indicare che un elemento \(x\) appartiene ad un insieme \(A\) scriviamo \[x \in A .\] Se invece \(x\) non appartiene ad \(A\) scriviamo \[x \notin A.\]
Un insieme è completamente determinato dai suoi elementi:
Due insiemi coincidono se e solo se hanno gli stessi elementi, ovvero
\(A\) \(=\) \(B\) se e solo se \(\forall x (x \in A \leftrightarrow x \in B)\).
\[\]
Insiemi L’insieme formato dagli elementi \(x_{1} , \dots , x_{n}\) si indica con \[\left \{ { x_{1} , \dots , x_{n}} \right \} .\]
L’insieme delle soluzioni dell’equazione \(x^3 - 4 x^2 + x + 6=0\) è \(\left \{ {-1 , 2 , 3} \right \}\).
Per il principio di estensionalità \[\left \{ {-1 , 2 , 3} \right \} = \left \{ {2 , -1 , 3} \right \} = \left \{ {3 , 2 , 3, -1} \right \}.\] In altre parole: l’ordine in cui vengono elencati gli elementi di un insieme è irrilevante, e le eventuali ripetizioni non contano.
L’insieme di tutti gli \(x\) che godono della proprietà \(P\) è indicato con
\(\left \{x \boldsymbol\mid P ( x ) \right\}\) oppure \(\left \{ x : P ( x ) \right\}\).
L’insieme degli \(x\) in \(A\) che soddisfano la proprietà \(P\) è indicato invece con
\(\left \{x \boldsymbol\mid x\in A \text{ e } P ( x ) \right\}\) oppure \(\left \{ x\in A \mid P ( x ) \right\}\).
Consideriamo la proprietà \(P(x)\) data da \[x^3 - 4 x^2 + x + 6=0 .\] Allora l’insieme di tutti i numeri interi che godono della proprietà \(P(x)\) è \[\left \{ x\in \mathbb{Z} \mid x^3 - 4 x^2 + x + 6=0 \right\}.\] Se invece \(P(x)\) è la proprietà “essere un numero pari” possiamo scrivere \[\left\{ x \in \mathbb{Z} \mid x \text{ è pari} \right\}.\]
Osservazione Consideriamo i due insiemi visti prima
\(\{-1,2,3\}\) e \(\left \{ x\in \mathbb{Z} \mid x^3 - 4 x^2 + x + 6=0 \right\}\).
La descrizione dell’insieme a sinistra è data attraverso una lista esplicita dei suoi elementi, mentre la descrizione di quello a destra è data attraverso una proprietà \(P(x)\) (essere soluzione dell’equazione \(x^3 - 4 x^2 + x + 6 = 0\)) che caratterizza quali numeri interi fanno parte dell’insieme.
Anche se le due descrizioni sono diverse, per il principio di estensionalità i due insiemi coincidono:
\(\{-1,2,3\} = \left \{ x\in \mathbb{Z} \mid x^3 - 4 x^2 + x + 6=0 \right\}\).
Per definizione, un insieme è vuoto se non contiene elementi.
Osservazione L’insieme vuoto è unico, ovvero: se \(A\) e \(B\) sono due insiemi che non contengono nessun elemento, allora per il principio di estensionalità \[A = B .\] Infatti, \(A\) e \(B\) hanno gli stessi elementi (cioè nessuno), ovvero \(A\) e \(B\) verificano la formula \[\forall x (x \in A \leftrightarrow x \in B).\]
L’(unico!) insieme vuoto si indica con \(\emptyset\).
Un insieme \(A\) è contenuto o incluso in un insieme \(B\) se ogni elemento di \(A\) è anche un elemento di \(B\): in simboli, \(A \subseteq B\). Quindi
\(A \subseteq B\) se e solo se \(\forall x (x \in A \rightarrow x \in B)\).
In questo caso, diciamo che \(A\) è un sottoinsieme di \(B\), oppure che \(B\) è un sovrainsieme di \(A\).
Attenzione! Non confondere \(\in\) con \(\subseteq\). In italiano, il termine “contenere” è ambiguo perché si utilizza sia nel senso di appartenenza (“\(\mathbb{N}\) contiene \(1\)”, inteso come “\(1\) è un elemento di \(\mathbb{N}\)”), sia nel senso di inclusione (“\(\mathbb{N}\) contiene i numeri pari”, inteso come “l’insieme dei numeri pari è incluso in \(\mathbb{N}\)”).
Chiaramente per ogni insieme \(A\) si ha che \(A \subseteq A\) e, poiché \(\emptyset\) non ha elementi, anche \(\emptyset \subseteq A\).
\(A \subset B\) (oppure \(A \subsetneq B\)) significa che \(A\) è un sottoinsieme proprio di \(B\), ovvero \(A \subseteq B\) ma \(A \neq B\).
Osservazione: Per verificare che \(A \nsubseteq B\) (ovvero che \(A\) non è un sottoinsieme di \(B\)) è sufficiente trovare un elemento \(x \in A\) che non appartenga a \(B\):
Dal principio di estensionalità si ottiene il
Dati due insiemi \(A\) e \(B\), si ha che \(A = B\) se e solo se \(A \subseteq B \wedge B \subseteq A\).
Descrizione informale dei principali insiemi numerici
L’insieme dei numeri naturali è \[\mathbb{N} = \left \{ {0 , 1 , 2 , \dots } \right \}\]
\(\mathbb{N}\) è contenuto propriamente nell’insieme dei numeri interi \[\mathbb{Z} = \left \{ { \dots , -2 , -1 , 0 , 1 , 2 , \dots} \right \}\]
Osservazione Qui sopra stiamo estendendo la notazione che abbiamo introdotto per insiemi finiti \(\{ x_{0}, x_{1}, \dotsc, x_{n} \}\) ad insiemi infiniti. I puntini indicano che l’elenco degli elementi prosegue indefinitamente in maniera “naturale”. Ad esempio, possiamo indicare l’insieme dei numeri naturali pari con \[\{ 0, 2, 4, 6, \dotsc \}.\]
Descrizione informale dei principali insiemi numerici
L’insieme \(\mathbb{Q}\) dei numeri razionali è l’insieme di tutti i numeri della forma \[\frac{n}{m}\] con \(n , m \in \mathbb{Z}\) e \(m \neq 0\). Ogni \(k \in \mathbb{Z}\) può essere scritto come \(\frac{k}{1}\) quindi \(\mathbb{Z} \subseteq \mathbb{Q}\) e poiché ci sono razionali che non sono interi (ad esempio \(\frac{1}{2}\)), l’inclusione è propria, cioè \(\mathbb{Z} \subset \mathbb{Q}\).
Descrizione informale dei principali insiemi numerici
Un razionale ha un’espansione decimale finita (per esempio \(\frac{1}{2}= 0,5\)) oppure un’espansione periodica (per esempio \(\frac{1}{3} = 0,33333\dots\)). I numeri la cui espansione decimale è arbitraria (cioè finita, periodica o aperiodica) si dicono numeri reali e l’insieme dei numeri reali si denota con \(\mathbb{R}\).
Chiaramente \(\mathbb{Q} \subseteq \mathbb{R}\) e l’inclusione è stretta (ovvero \(\mathbb{Q} \subset \mathbb{R}\)) poiché, ad esempio, \(\sqrt{2} \in \mathbb{R} \setminus \mathbb{Q}\).
Attenzione! Alcuni numeri ammettono due espansioni decimali diverse: ad esempio \(0,99999\dotsc\) e \(1\) indicano lo stesso numero reale.
L’insieme delle parti \(\mathscr{P}(A)\) di un insieme \(A\) (detto anche insieme potenza di \(A\)) è l’insieme di tutti i suoi sottoinsiemi: \[\mathscr{P}( A ) = \left \{B \boldsymbol\mid B \subseteq A \right\}.\]
\(\mathscr{P}(A)\) è un insieme i cui elementi sono a loro volta insiemi!
Osservazioni: \(\mathscr{P}(A)\) contiene sempre \(\emptyset\) e \(A\) come elementi, quindi è sempre non vuoto. Inoltre, se \(A\) è un insieme finito con \(n\) elementi, allora \(\mathscr{P}(A)\) ha esattamente \(2^n\) elementi.
Esercizi
Descrivere \(\mathscr{P}(A)\) dove \(A = \{ 0,1,2 \}\) \(\mathscr{P}(A)\) = { \(\emptyset\), \(\{ 0 \}\), \(\{ 1 \}\), \(\{ 2 \}\), \(\{ 0,1 \}\), \(\{ 0,2 \}\), \(\{ 1,2 \}\), \(\{ 0,1,2 \}\) }.
Descrivere \(\mathscr{P}(\mathscr{P}(A))\) con \(A = \{ 1 \}\) Si ha \(\mathscr{P}(A) = \{ \emptyset, A \}\), e quindi \(\mathscr{P}(\mathscr{P}(A)) = \{ \emptyset, \{ \emptyset \}, \{ A \}, \{ \emptyset,A \} \}\).
Esercizi
Inserire \(\in\) oppure \(\subseteq\) al posto dei puntini
| \[\emptyset \dotsc \mathbb{N}\] | \[\{ 5 \} \dotsc \mathbb{N}\] | \[5 \dotsc \mathbb{N}\] | \[\{ 5 \} \dotsc \mathscr{P}(\mathbb{N})\] |
|---|---|---|---|
| \[\mathbb{N} \dotsc \mathbb{Z}\] | \[\mathbb{N} \dotsc \mathscr{P}(\mathbb{Z})\] | \[\mathscr{P}(\mathbb{N}) \dotsc \mathscr{P}(\mathbb{Z})\] |
\(\{ n \in \mathbb{N} \mid n =4k \text{ per qualche } k \} \dotsc \{ n \in \mathbb{N} \mid n =2k \text{ per qualche } k \}\)
Risposta
Inserire \(\in\) oppure \(\subseteq\) al posto dei puntini
| \[\emptyset \subseteq \mathbb{N}\] | \[\{ 5 \} \subseteq \mathbb{N}\] | \[5 \in \mathbb{N}\] | \[\{ 5 \} \in \mathscr{P}(\mathbb{N})\] |
|---|---|---|---|
| \[\mathbb{N} \subseteq \mathbb{Z}\] | \[\mathbb{N} \in \mathscr{P}(\mathbb{Z})\] | \[\mathscr{P}(\mathbb{N}) \subseteq \mathscr{P}(\mathbb{Z})\] |
\(\{ n \in \mathbb{N} \mid n =4k \text{ per qualche } k \} \subseteq \{ n \in \mathbb{N} \mid n =2k \text{ per qualche } k \}\)
Esercizi
Quale delle seguenti affermazioni sono corrette?
\(\emptyset \in A\) per ogni insieme \(A\) FALSO
\(\emptyset \in \mathscr{P}(A)\) per ogni insieme \(A\) VERO
\(a \in \{ \{ a \} \}\) FALSO
\(\{ a \} \subseteq \{ \{ a \} \}\) FALSO
\(\{ a \} \in \{ \{ a \} \}\) VERO
\(\{ a \} \in \{ a , \{ a \} \}\) VERO
\(\{ a \} \subseteq \{ a , \{ a \} \}\) VERO
\(\{ 0,1,2 \} \subseteq \mathscr{P}(\mathbb{N})\) FALSO
L’intersezione di \(A\) e \(B\), in simboli \(A \cap B\), è l’insieme di tutti gli elementi che stanno sia in \(A\) che in \(B\), cioè
Due insiemi \(A\) e \(B\) si dicono disgiunti se non hanno alcun elemento in comune, ovvero se \(A \cap B = \emptyset\).
Le operazioni di unione e intersezione si possono generalizzare a famiglie di insiemi arbitrarie come segue.
Una famiglia arbitraria di insiemi è denotata da \(\left \{A_{i} \boldsymbol\mid i \in I \right\}\) — ad ogni indice \(i \in I\) corrisponde un insieme \(A_{i}\).
L’unione degli \(A_{i}\) è l’insieme degli enti che appartengono a qualche \(A_{i}\) \[\textstyle \bigcup_{i\in I} A_{i} = \left \{x \boldsymbol\mid \exists{i \in I} \left (x \in A_{i} \right ) \right\}\] mentre l’intersezione degli \(A_{i}\) è l’insieme degli enti che appartengono ad ogni \(A_{i}\) \[\textstyle\bigcap_{i\in I} A_{i} = \left \{x \boldsymbol\mid \forall{i \in I} \left ( x \in A_{i} \right ) \right\}.\]
Chiaramente \(\bigcup_{i \in I} A_{i}\) contiene ogni \(A_{j}\), mentre \(\bigcap_{i\in I} A_{i}\) è contenuta in ogni \(A_{j}\).
Consideriamo la famiglia \(\left \{A_{n} \boldsymbol\mid \in \mathbb{N} \right\}\) di intervalli di \(\mathbb{R}\) dove \(A_{n} = [ -1 ; 1 - 2^{-n}] \stackrel{\text{def}}{=}\left \{x \in \mathbb{R} \boldsymbol\mid -1 \leq x \leq 1-2^{-n} \right\}\). Allora
\(\bigcup\nolimits_{n \in \mathbb{N}} A_{n} = [-1;1) \stackrel{\text{def}}{=}\left \{x \in \mathbb{R} \boldsymbol\mid -1 \leq x < 1 \right\}\)
e
\(\bigcap\nolimits_{n \in \mathbb{N}} A_{n} = [-1 ; 0 ] \stackrel{\text{def}}{=}\left \{x \in \mathbb{R} \boldsymbol\mid -1 \leq x \leq 0=A_{0} \right\}\)
Poniamo ora \(A_{n} = [ - 1 ; 2^{-n} ] \stackrel{\text{def}}{=}\left \{x \in \mathbb{R} \boldsymbol\mid -1 \leq x \leq 2^{-n} \right\}\).
Allora
\(\bigcup\nolimits_{n \in \mathbb{N}} A_{n} = [-1 ; 1 ] \stackrel{\text{def}}{=}\left \{x \in \mathbb{R} \boldsymbol\mid -1 \leq x \leq 1=A_{0} \right\}\)
e
\(\bigcap\nolimits_{n \in \mathbb{N}} A_{n} = [-1 ; 0 ] \stackrel{\text{def}}{=}\left \{x \in \mathbb{R} \boldsymbol\mid -1 \leq x \leq 0 \right\}\).
La differenza tra \(A\) e \(B\), in simboli \(A \setminus B\), è l’insieme di tutti gli enti che stanno in \(A\) ma non in \(B\), cioè
La differenza simmetrica tra \(A\) e \(B\), in simboli \(A \mathop{\triangle} B\), è l’insieme di tutti gli enti che stanno in uno dei due insiemi ma non nell’altro, cioè
\[\forall {x} \left ( x \in A \mathop{\triangle} B \leftrightarrow ( (x \in A \wedge x \notin B) \vee (x \in B \wedge x \notin A) ) \right ) .\] Inoltre, \[A \mathop{\triangle} B = \left (A \cup B \right ) \setminus \left ( A \cap B \right )\]
Spesso è conveniente assumere che tutti gli insiemi/oggetti/enti di cui ci stiamo occupando siano contenuti in un insieme universale \(\mathcal{U}\), detto appunto universo.
Fissiamo ora un universo \(\mathcal{U}\). La differenza \(\mathcal{U} \setminus A\) si dice complementare (o, più semplicemente, complemento) di \(A\) e lo si indica con \(\complement A\).
Quindi \[\complement A = \left \{x \boldsymbol\mid x \notin A \right\} .\]
La logica proposizionale può essere utilizzata in maniera sistematica per verificare identità o inclusioni tra insiemi costruiti utilizzando le operazioni insiemistiche (finitarie) che abbiamo visto.
Dimostriamo che \(\complement \complement A = A\)
Dobbiamo verificare che, qualunqua sia \(A\), valga la formula \[\forall x (x \in \complement \complement A \leftrightarrow x\in A).\] Fissiamo quindi un generico \(x\). Sfruttando la corrispondenza tra operazioni insiemistiche e connettivi logici visti in precedenza, la formula \[x \in \complement \complement A \leftrightarrow x \in A\] diventa
\(\neg\) ( \(\neg\) ( \(x \in\) \(A\))) \(\leftrightarrow x \in A\).
Se ora nella formula \[\neg(\neg(x \in A) ) \leftrightarrow x \in A\] sostituiamo l’affermazione “\(x \in A\)” con una corrispondente lettera proposizionale \(\mathrm{P}\) otteniamo la formula proposizionale \[\neg(\neg \mathrm{P}) \leftrightarrow \mathrm{P}.\] In generale, il fatto che \(\mathrm{P}\) sia vera o meno dipenderà naturalmente dalla scelta di \(A\) e \(x\): ma noi vogliamo proprio dimostrare che l’equivalenza è vera in ogni caso (cioè comunque vengano presi \(A\) e \(x\)), ovvero che la proposizione precedente è una tautologia. Utilizzando le tavole di verità si verifica facilmente che questo è vero (legge della doppia negazione), quindi comunque siano presi \(A\) e \(x\) avremo che \[x \in \complement \complement A \leftrightarrow x \in A,\] da cui \(\complement \complement A = A\), come desiderato.
Dimostriamo che
Dobbiamo dimostrare che per ogni \(x\) \[x \in \complement ( A \cup B ) \leftrightarrow x \in \complement A \cap \complement B .\] Utilizzando la corrispondenza tra operazioni insiemistiche e connettivi che abbiamo visto, la formula precedente diventa
\(x \in\) \(A\) \(B\) \(\leftrightarrow\) \(x \in\) \(A\) \(B\) .
Dimostriamo che \(\complement ( A \cap B ) = \complement A \cup \complement B\)
Dobbiamo dimostrare che per ogni \(x\) \[x \in \complement ( A \cap B ) \leftrightarrow x \in \complement A \cup \complement B,\] ovvero che \[\neg (x \in A \wedge x \in B) \leftrightarrow \neg (x \in A ) \vee \neg(x \in B).\] Questa è una proposizione della forma \[\neg(\mathrm{P} \wedge \mathrm{Q}) \leftrightarrow \neg \mathrm{P} \vee \neg \mathrm{Q},\] dove \(\mathrm{P}\) e \(\mathrm{Q}\) sono, rispettivamente, “\(x \in A\)” e “\(x \in B\)”. Poiché tale proposizione è una tautologia (leggi di De Morgan), l’identità insiemistica iniziale è dimostrata.
\(\complement ( A \cap B ) = \complement A \cup \complement B\)
La stessa identità può anche essere dimostrata utilizzando ciò che abbiamo già dimostrato, ovvero che per tutti gli insiemi \(X\) e \(Y\) valgono \(\complement \complement X = X\) e \(\complement (X \cup Y) = \complement X \cap \complement Y\) .
| \[\complement ( A \cap B )\] | \[=\] | \[\complement (\complement\complement A \cap \complement\complement B)\] |
|---|---|---|
| \[\] | \[=\] | \[\complement \left ( \complement \left ( \complement A \cup \complement B\right ) \right )\] |
| \[\] | \[=\] | \[\complement \complement \left ( \complement A \cup \complement B\right )\] |
| \[\] | \[=\] | \[\complement A \cup \complement B\] |
Dimostrare che \(A\cap ( B \cup C ) = ( A \cap B ) \cup ( A \cap C )\)
Dobbiamo dimostrare che per ogni \(x\)
\(x\in A\cap ( B \cup C ) \leftrightarrow x \in ( A \cap B ) \cup ( A \cap C )\) ,
ovvero \[x \in A \wedge ( x \in B \vee x \in C ) \leftrightarrow ( x\in A \wedge x \in B ) \vee ( x\in A \wedge x \in C ) .\] Questa è una proposizione della forma \[\mathrm{P} \wedge ( \mathrm{Q} \vee \mathrm{R} ) \leftrightarrow ( \mathrm{P} \wedge \mathrm{Q} ) \vee ( \mathrm{P} \wedge \mathrm{R} ),\] dove \(\mathrm{P}\), \(\mathrm{Q}\) e \(\mathrm{R}\) sono, rispettivamente, “\(x\in A\)”, “\(x \in B\)” e “\(x \in C\)”. Poiché la proposizione precedente è una tautologia (come si può verificare facilmente con le tavole di verità), l’equivalenza è dimostrata.
Dimostrare che \(\complement \left (\bigcup_{{i\in I}} A_{i} \right ) = \bigcap_{{i\in I}} \complement A_{i}\) In questo caso non possiamo ricondurci alla logica proposizionale (a meno che \(I\) non sia finito) perché le operazioni \(\bigcup_{{i \in I}}\) e \(\bigcap_{{i \in I }}\) sono operazioni infinitarie (coinvolgono infiniti insiemi) mentre i connettivi sono operatori finitari (unari o binari). Dobbiamo quindi procedere con una dimostrazione ad hoc.
Dobbiamo dimostrare che per ogni \(x\) \[x \in \complement \left (\bigcup\nolimits_{i\in I} A_{i} \right ) \leftrightarrow x\in \bigcap\nolimits_{i\in I} \complement A_{i} .\] In effetti \(x \in \complement \left (\bigcup_{{i\in I}} A_{i} \right )\) \(\leftrightarrow \neg \left (x \in \bigcup_{{i\in I}} A_{i} \right )\) \(\leftrightarrow \neg ( \exists {i \in I} \left ( x \in A_{i} \right ) )\) \(\leftrightarrow \forall {i \in I} \neg \left ( x \in A_{i} \right )\) \(\leftrightarrow \forall {i \in I} \left ( x \notin A_{i} \right )\) \(\leftrightarrow \forall {i \in I} \left ( x \in \complement A_{i} \right )\) \(\leftrightarrow x \in \bigcap_{{i\in I}} \complement A_{i} .\)
Attenzione! La negazione di \(\exists {i \in I} (\dotsc)\), ovvero \(\neg ( \exists {i \in I} (\dotsc))\), è equivalente a \(\forall {i \in I} \neg (\dotsc)\).Viceversa, \(\neg ( \forall {i \in I} (\dotsc))\) è equivalente a \(\exists {i \in I} \neg (\dotsc)\).
Dimostrare che \(( A \cup B ) \setminus ( A \cap B ) = ( A \setminus B ) \cup ( B \setminus A )\)
Poiché \(X \setminus Y = X \cap \complement Y\), l’identità può essere riscritta come \[( A \cup B ) \cap \complement ( A \cap B ) = ( A \cap \complement B ) \cup ( B \cap \complement A ) .\] Quindi dobbiamo dimostrare che per ogni \(x\) \[x \in ( A \cup B ) \cap \complement ( A \cap B ) \leftrightarrow x \in ( A \cap \complement B ) \cup ( B \cap \complement A ) ,\] ovvero \[\begin{gathered} (x \in A \vee x \in B) \wedge \neg (x \in A \wedge x \in B) \leftrightarrow \\ (x \in A \wedge \neg(x \in B)) \vee (x \in B \wedge \neg(x \in A)). \end{gathered}\] Questa è una proposizione del tipo \[(\mathrm{P} \vee \mathrm{Q}) \wedge \neg (\mathrm{P} \wedge \mathrm{Q}) \leftrightarrow (\mathrm{P} \wedge \neg \mathrm{Q}) \vee (\mathrm{Q} \wedge \neg \mathrm{P}).\] Usando le tavole di verità si verifica che tale proposizione è una tautologia, quindi l’identità insiemistica proposta è corretta.
Lo stesso metodo può essere utilizzato anche per trovare controesempi quando una certa identità booleana non è valida.
Dimostrare (trovando un controesempio) che non vale l’identità \(A \cap (B \cup C) = A \cup (B \cap C)\)
Dato un generico \(x\), dobbiamo verificare che non è vero in generale che \[x \in A \cap (B \cup C) \leftrightarrow x \in A \cup (B \cap C),\] ovvero \[x \in A \wedge (x \in B \vee x \in C) \leftrightarrow x \in A \vee (x \in B \wedge x \in C).\] Questa è una proposizione del tipo \[\mathrm{P} \wedge (\mathrm{Q} \vee \mathrm{R}) \leftrightarrow \mathrm{P} \vee (\mathrm{Q} \wedge \mathrm{R}),\] dove \(\mathrm{P}\), \(\mathrm{Q}\) e \(\mathrm{R}\) sono, rispettivamente, “\(x \in A\)”, “\(x \in B\)” e “\(x \in C\)”.
La tavola di verità di tale proposizione è
| \(P\) | \(Q\) | \(R\) | \(P \wedge (Q \vee R)\) | \(P \vee (Q \wedge R)\) | \(P \wedge (Q \vee R) \leftrightarrow \mathrm{P} \vee (R \wedge R)\) |
|---|---|---|---|---|---|
| \(V\) | \(V\) | \(V\) | \(V\) | \(V\) | \(V\) |
| \(V\) | \(V\) | \(F\) | \(V\) | \(V\) | \(V\) |
| \(V\) | \(F\) | \(V\) | \(V\) | \(V\) | \(V\) |
| \(V\) | \(F\) | \(F\) | \(F\) | \(V\) | \(F\) |
| \(F\) | \(V\) | \(V\) | \(F\) | \(V\) | \(F\) |
| \(F\) | \(V\) | \(F\) | \(F\) | \(F\) | \(V\) |
| \(F\) | \(F\) | \(V\) | \(F\) | \(F\) | \(V\) |
| \(F\) | \(F\) | \(F\) | \(F\) | \(F\) | \(V\) |
Poiché la proposizione non è una tautologia, l’identità non è valida. Ad esempio, l’identità risulta falsa quando ci troviamo nella situazione descritta dalla quarta riga. Dunque un controesempio può essere costruito considerando un \(A\) che contenga almeno un elemento \(x\) che non compare né in \(B\) né in \(C\): in tale situazione si avrà infatti \(x \in A \cup ( B \cap C )\) ma \(x \notin A \cap (B \cup C)\), da cui \(A \cap (B \cup C) \neq A \cup (B \cap C)\). In maniera analoga si può ottenere un (diverso) controesempio dalla quinta riga.
Il prodotto cartesiano di \(A\) e \(B\), in simboli \(A \times B\), è l’insieme di tutte le coppie ordinate \(( x , y )\) dove \(x \in A\) e \(y \in B\), cioè \[A \times B = \left \{( x , y) \boldsymbol\mid x \in A \text{ e } y\in B \right\}.\]
Osserviamo che, a differenza degli insiemi, nelle coppie ordinate l’ordine è fondamentale, cioè \(( x , y )\) è un oggetto diverso da \(( y , x )\), a meno che \(x\) non sia \(y\).
Quindi \(A \times B\) è distinto da \(B \times A\) se \(A \neq B\). Se invece \(A = B\), allora \(A \times B = B \times A\): in questo caso, tale prodotto cartesiano viene indicato con \(A ^2\).
L’insieme \(\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}\) è l’usuale piano cartesiano, i cui elementi sono identificati da coppie ordinate di numeri reali (le coordinate).
Più in generale, se \(n \geq 1\) \[( x_{0} , x_{1} , \dots , x_{{n-1}} )\] indica la \(n\)-upla ordinata costituita dagli elementi \(x_{0} , x_{1} , \dots , x_{{n-1}}\).
Attenzione! A differenza di quel che accade per gli insiemi, nelle \(n\)-uple ordinate contano sia l’ordine che eventuali ripetizioni.
Il prodotto cartesiano degli insiemi \(A_{0}, \dotsc, A_{{n-1}}\), denotato con \[A_{0} \times A_{1} \times \dotsc \times A_{{n-1}} ,\] è l’insieme delle \(n\)-uple \((x_{0}, x_{1}, \dotsc, x_{{n-1}})\) tali che \(x_{i} \in A_{i}\) per ogni \(0 \leq i < n\).
Il prodotto cartesiano \(\underbrace{A \times \dots \times A}_{n}\) di \(n\) copie dell’insieme \(A\), ovvero l’insieme delle \(n\)-uple \((x_{0}, \dotsc, x_{{n-1}})\) tali che \(x_{i} \in A\) per ogni \(0 \leq i < n\), si indica più brevemente con \(A^n\) e viene detto potenza \(n\)-esima di \(A\). Per convenzione, si pone anche \(A^0 = \{ \emptyset \}\).