Appendix C — Insiemi

Un insieme (o collezione, classe, gruppo, …) è un concetto primitivo, ovvero è un concetto che già possediamo. Georg Cantor l’ha definito nel modo seguente: un insieme è una collezione di oggetti, determinati e distinti, della nostra percezione o del nostro pensiero, concepiti come un tutto unico; tali oggetti si dicono elementi dell’insieme.

Mentre non è rilevante la natura degli oggetti che costituiscono l’insieme, ciò che importa è distinguere se un dato oggetto appartenga o meno ad un insieme. Deve essere vera una delle due possibilità: il dato oggetto è un elemento dell’insieme considerato oppure non è elemento dell’insieme considerato. Due insiemi $A$ e $B$ si dicono uguali se sono formati dagli stessi elementi, anche se disposti in ordine diverso: $A=B$. Due insiemi $A$ e $B$ si dicono diversi se non contengono gli stessi elementi: $A \neq B$. Ad esempio, i seguenti insiemi sono uguali:

\[ \{1, 2, 3\} = \{3, 1, 2\} = \{1, 3, 2\}= \{1, 1, 1, 2, 3, 3, 3\}. \]

Gli insiemi sono denotati da una lettera maiuscola, mentre le lettere minuscole, di solito, designano gli elementi di un insieme. Per esempio, un generico insieme $A$ si indica con

\[ A = \{a_1, a_2, \dots, a_n\}, \quad \text{con~} n > 0. \]

La scrittura $a \in A$ dice che $a$ è un elemento di $A$. Per dire che $b$ non è un elemento di $A$ si scrive $b \notin A.$

Per quegli insiemi i cui elementi soddisfano una certa proprietà che li caratterizza, tale proprietà può essere usata per descrivere più sinteticamente l’insieme:

\[ A = \{x ~\vert~ \text{proprietà posseduta da~} x\}, \]

che si legge come “$A$ è l’insieme degli elementi $x$ per cui è vera la proprietà indicata.” Per esempio, per indicare l’insieme $A$ delle coppie di numeri reali $(x,y)$ che appartengono alla parabola $y = x^2 + 1$ si può scrivere:

\[ A = \{(x,y) ~\vert~ y = x^2 + 1\}. \]

Dati due insiemi $A$ e $B$, diremo che $A$ è un sottoinsieme di $B$ se e solo se tutti gli elementi di $A$ sono anche elementi di $B$:

\[ A \subseteq B \iff (\forall x \in A \Rightarrow x \in B). \]

Se esiste almeno un elemento di $B$ che non appartiene ad $A$ allora diremo che $A$ è un sottoinsieme proprio di $B$:

\[ A \subset B \iff (A \subseteq B, \exists~ x \in B ~\vert~ x \notin A). \]

Un altro insieme, detto insieme delle parti, o insieme potenza, che si associa all’insieme $A$ è l’insieme di tutti i sottoinsiemi di $A$, inclusi l’insieme vuoto e $A$ stesso. Per esempio, per l’insieme $A = \{a, b, c\}$, l’insieme delle parti è:

\[ \mathcal{P}(A) = \{ \emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{c, b\}, \{a, b, c\} \}. \]

C.1 Operazioni tra insiemi

Si definisce intersezione di $A$ e $B$ l’insieme $A \cap B$ di tutti gli elementi $x$ che appartengono ad $A$ e contemporaneamente a $B$:

\[ A \cap B = \{x ~\vert~ x \in A \land x \in B\}. \]

Si definisce unione di $A$ e $B$ l’insieme $A \cup B$ di tutti gli elementi $x$ che appartengono ad $A$ o a $B$, cioè

\[ A \cup B = \{x ~\vert~ x \in A \lor x \in B\}. \]

Differenza. Si indica con $A \setminus B$ l’insieme degli elementi di $A$ che non appartengono a $B$:

\[ A \setminus B = \{x ~\vert~ x \in A \land x \notin B\}. \]

Insieme complementare. Nel caso che sia $B \subseteq A$, l’insieme differenza $A \setminus B$ è detto insieme complementare di $B$ in $A$ e si indica con $B^C$.

Dato un insieme $S$, una partizione di $S$ è una collezione di sottoinsiemi di $S$, $S_1, \dots, S_k$, tali che

\[ S = S_1 \cup S_2 \cup \dots S_k \]

\[ S_i \cap S_j, \quad \text{con~} i \neq j. \]

La relazione tra unione, intersezione e insieme complementare è data dalle leggi di DeMorgan:

\[ (A \cup B)^c = A^c \cap B^c, \] \[ (A \cap B)^c = A^c \cup B^c. \]

C.2 Diagrammi di Eulero-Venn

In molte situazioni è utile servirsi dei cosiddetti diagrammi di Eulero-Venn per rappresentare gli insiemi e verificare le proprietà delle operazioni tra insiemi (si veda la figura @ref(fig:sets-venn-diagrams). I diagrammi di Venn sono così nominati in onore del matematico inglese del diciannovesimo secolo John Venn anche se Leibnitz e Eulero avevano già in precedenza utilizzato rappresentazioni simili. In tale rappresentazione, gli insiemi sono individuati da regioni del piano delimitate da una curva chiusa. Nel caso di insiemi finiti, è possibile evidenziare esplicitamente alcuni elementi di un insieme mediante punti, quando si possono anche evidenziare tutti gli elementi degli insiemi considerati.

In tutte le figure $S$ è la regione delimitata dal rettangolo, $L$ è la regione all’interno del cerchio di sinistra e $R$ è la regione all’interno del cerchio di destra. La regione evidenziata mostra l’insieme indicato sotto ciascuna figura.

I diagrammi di Eulero-Venn che forniscono una dimostrazione delle leggi di DeMorgan sono forniti nella figura @ref(fig:demorgan).

Dimostrazione delle leggi di DeMorgan.

C.3 Coppie ordinate e prodotto cartesiano

Una coppia ordinata $(x,y)$ è l’insieme i cui elementi sono $x \in A$ e $y \in B$ e nella quale $x$ è la prima componente (o prima coordinata), $y$ la seconda. L’insieme di tutte le coppie ordinate costruite a partire dagli insiemi $A$ e $B$ viene detto prodotto cartesiano:

\[ A \times B = \{(x, y) ~\vert~ x \in A \land y \in B\}. \]

Ad esempio, sia $A = \{1, 2, 3\}$ e $B = \{a, b\}$. Allora,

\[ \{1, 2\} \times \{a, b, c\} = \{(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)\}. \]

C.4 Cardinalità

Si definisce cardinalità (o potenza) di un insieme finito il numero degli elementi dell’insieme. Viene indicata con $\vert A\vert, \#(A)$ o $\text{c}(A)$.

# Insiemi {#sec-appendix-sets} Un insieme (o collezione, classe, gruppo, ...) è un concetto primitivo, ovvero è un concetto che già possediamo. Georg Cantor l'ha definito nel modo seguente: *un insieme è una collezione di oggetti, determinati e distinti, della nostra percezione o del nostro pensiero, concepiti come un tutto unico; tali oggetti si dicono elementi dell'insieme.* Mentre non è rilevante la natura degli oggetti che costituiscono l'insieme, ciò che importa è distinguere se un dato oggetto appartenga o meno ad un insieme. Deve essere vera una delle due possibilità: il dato oggetto è un elemento dell'insieme considerato oppure non è elemento dell'insieme considerato. Due insiemi $A$ e $B$ si dicono uguali se sono formati dagli stessi elementi, anche se disposti in ordine diverso: $A=B$. Due insiemi $A$ e $B$ si dicono diversi se non contengono gli stessi elementi: $A \neq B$. Ad esempio, i seguenti insiemi sono uguali: $$ \{1, 2, 3\} = \{3, 1, 2\} = \{1, 3, 2\}= \{1, 1, 1, 2, 3, 3, 3\}. $$ Gli insiemi sono denotati da una lettera maiuscola, mentre le lettere minuscole, di solito, designano gli elementi di un insieme. Per esempio, un generico insieme $A$ si indica con $$ A = \{a_1, a_2, \dots, a_n\}, \quad \text{con~} n > 0. $$ La scrittura $a \in A$ dice che $a$ è un elemento di $A$. Per dire che $b$ non è un elemento di $A$ si scrive $b \notin A.$ Per quegli insiemi i cui elementi soddisfano una certa proprietà che li caratterizza, tale proprietà può essere usata per descrivere più sinteticamente l'insieme: $$ A = \{x ~\vert~ \text{proprietà posseduta da~} x\}, $$ che si legge come "$A$ è l'insieme degli elementi $x$ per cui è vera la proprietà indicata." Per esempio, per indicare l'insieme $A$ delle coppie di numeri reali $(x,y)$ che appartengono alla parabola $y = x^2 + 1$ si può scrivere: $$ A = \{(x,y) ~\vert~ y = x^2 + 1\}. $$ Dati due insiemi $A$ e $B$, diremo che $A$ è un *sottoinsieme* di $B$ se e solo se tutti gli elementi di $A$ sono anche elementi di $B$: $$ A \subseteq B \iff (\forall x \in A \Rightarrow x \in B). $$ Se esiste almeno un elemento di $B$ che non appartiene ad $A$ allora diremo che $A$ è un *sottoinsieme proprio* di $B$: $$ A \subset B \iff (A \subseteq B, \exists~ x \in B ~\vert~ x \notin A). $$ Un altro insieme, detto *insieme delle parti*, o insieme potenza, che si associa all'insieme $A$ è l'insieme di tutti i sottoinsiemi di $A$, inclusi l'insieme vuoto e $A$ stesso. Per esempio, per l'insieme $A = \{a, b, c\}$, l'insieme delle parti è: $$ \mathcal{P}(A) = \{ \emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{c, b\}, \{a, b, c\} \}. $$ ## Operazioni tra insiemi Si definisce *intersezione* di $A$ e $B$ l'insieme $A \cap B$ di tutti gli elementi $x$ che appartengono ad $A$ e contemporaneamente a $B$: $$ A \cap B = \{x ~\vert~ x \in A \land x \in B\}. $$ Si definisce *unione* di $A$ e $B$ l'insieme $A \cup B$ di tutti gli elementi $x$ che appartengono ad $A$ o a $B$, cioè $$ A \cup B = \{x ~\vert~ x \in A \lor x \in B\}. $$ *Differenza*. Si indica con $A \setminus B$ l'insieme degli elementi di $A$ che non appartengono a $B$: $$ A \setminus B = \{x ~\vert~ x \in A \land x \notin B\}. $$ *Insieme complementare*. Nel caso che sia $B \subseteq A$, l'insieme differenza $A \setminus B$ è detto insieme complementare di $B$ in $A$ e si indica con $B^C$. Dato un insieme $S$, una *partizione* di $S$ è una collezione di sottoinsiemi di $S$, $S_1, \dots, S_k$, tali che $$ S = S_1 \cup S_2 \cup \dots S_k $$ e $$ S_i \cap S_j, \quad \text{con~} i \neq j. $$ La relazione tra unione, intersezione e insieme complementare è data dalle leggi di DeMorgan: $$ (A \cup B)^c = A^c \cap B^c, $$ $$ (A \cap B)^c = A^c \cup B^c. $$ ## Diagrammi di Eulero-Venn In molte situazioni è utile servirsi dei cosiddetti diagrammi di Eulero-Venn per rappresentare gli insiemi e verificare le proprietà delle operazioni tra insiemi (si veda la figura \@ref(fig:sets-venn-diagrams). I diagrammi di Venn sono così nominati in onore del matematico inglese del diciannovesimo secolo John Venn anche se Leibnitz e Eulero avevano già in precedenza utilizzato rappresentazioni simili. In tale rappresentazione, gli insiemi sono individuati da regioni del piano delimitate da una curva chiusa. Nel caso di insiemi finiti, è possibile evidenziare esplicitamente alcuni elementi di un insieme mediante punti, quando si possono anche evidenziare tutti gli elementi degli insiemi considerati. ```{r sets-venn-diagrams, out.width='100%', echo=FALSE, fig.cap="In tutte le figure $S$ è la regione delimitata dal rettangolo, $L$ è la regione all'interno del cerchio di sinistra e $R$ è la regione all'interno del cerchio di destra. La regione evidenziata mostra l'insieme indicato sotto ciascuna figura."} knitr::include_graphics('images/sets-venn-diagrams.pdf') ``` I diagrammi di Eulero-Venn che forniscono una dimostrazione delle leggi di DeMorgan sono forniti nella figura \@ref(fig:demorgan). ```{r demorgan, out.width='100%', echo=FALSE, fig.cap="Dimostrazione delle leggi di DeMorgan."} knitr::include_graphics('images/demorgan.pdf') ``` ## Coppie ordinate e prodotto cartesiano Una coppia ordinata $(x,y)$ è l'insieme i cui elementi sono $x \in A$ e $y \in B$ e nella quale $x$ è la prima componente (o prima coordinata), $y$ la seconda. L'insieme di tutte le coppie ordinate costruite a partire dagli insiemi $A$ e $B$ viene detto **prodotto cartesiano**: $$ A \times B = \{(x, y) ~\vert~ x \in A \land y \in B\}. $$ Ad esempio, sia $A = \{1, 2, 3\}$ e $B = \{a, b\}$. Allora, $$ \{1, 2\} \times \{a, b, c\} = \{(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)\}. $$ ## Cardinalità Si definisce *cardinalità* (o potenza) di un insieme finito il numero degli elementi dell'insieme. Viene indicata con $\vert A\vert, \#(A)$ o $\text{c}(A)$.