Teoria degli insiemi

Definizione: teoria degli insiemi

La teoria degli insiemi è una branca della matematica che si occupa dello studio degli insiemi, cioè collezioni di oggetti distinti che possono essere definiti e manipolati secondo determinate regole. Si tratta di un argomento fondamentale, poiché costituisce la base della moderna matematica.

1 - Introduzione agli insiemi

Gli insiemi sono l’oggetto matematico su cui si fonda la teoria degli insiemi e vengono utilizzati per descrivere e analizzare gruppi di oggetti, numeri o concetti.

Definizione: insieme

Un insieme, denotato con le lettere latine maiuscole (es. $A$, $B$, $C$, ecc.), è una collezione ben definita di oggetti distinti, detti elementi dell’insieme, generalmente denotati con le lettere latine minuscole (es. $a$, $b$, $c$, ecc.).

Per affermare l’appartenenza di un dato elemento a un insieme si usa il simbolo $\in$¹, mentre per negarla si usa il simbolo $\notin$².

Osservazione: restrizioni sulla natura degli elementi di un insieme

Non c’è alcuna restrizione su quale sia la natura degli oggetti che possono appartenere a un insieme: essi possono essere sia oggetti “matematici” (come i numeri), ma non solo (es. l’insieme delle capitali dei Paesi nel mondo). Non è neanche detto che gli oggetti dell’insieme debbano avere una natura “omogenea” (es. può esistere un insieme che ha come elementi il numero 4, il nome del Rettore dell’Università di Torino e la Mole Antonelliana).

Osservazione: significato di "ben definita"

La richiesta che la collezione sia ben definita significa che non deve esserci alcuna ambiguità circa il fatto che un oggetto sia o meno un elemento di un dato insieme (es. l’insieme dei professori più bravi dell’Università di Torino non può essere un insieme perché non è possibile definire in modo oggettivo quali professori ne facciano parte e quali no).

Osservazione: insiemi come elementi di altri insiemi

Una volta definito correttamente un certo insieme, esso è certamente un oggetto matematico e, in quanto tale, può essere esso stesso elemento di un altro insieme: gli elementi di un insieme possono essere a loro volta insiemi (es. l’insieme $B$ può essere inteso come un elemento dell’insieme $A$).

Inoltre, dati un insieme $A$ e un suo elemento l’insieme $B\in A$, gli elementi di $B$ NON sono elementi di $A$ (es. se abbiamo $B=\{3,4\}$ e $A=\{0,1,2,\{3,4\}\}$, con $B\in A$ , gli elementi di $A$ sono 4, in quanto gli elementi $\{3,4\}$ di $B$ sono contati come un unico elemento in $A$).

Definizione: insieme universo

Un insieme universo (o universo di riferimento), solitamente denotato con "$\mathcal{U}$" è un insieme che comprende tutti gli insiemi/oggetti/enti pertinenti a un certo contesto o problema. Gli altri insiemi considerati sono tutti sottoinsiemi di questo insieme universo.

Esempio

Se si sta lavorando con un mazzo di carte da gioco francesi standard, che contiene 52 carte divise in 4 semi, l’insieme universo è l’insieme di tutte e 52 le carte del mazzo. Ogni altro insieme, per esempio quello delle 13 carte di cuori, sarà un sottoinsieme dell’insieme universo.

1.1 - Insieme vuoto

Definizione: insieme vuoto

L’insieme vuoto, denotato col simbolo "$\varnothing$", è l’insieme privo di elementi.

Osservazione: l'insieme $A=\{\varnothing \}$ non è vuoto

L’insieme $A=\{\varnothing \}$ non è un insieme vuoto: l’insieme vuoto è privo di elementi, mentre l’insieme $A$ ha un elemento, ossia l’elemento-insieme vuoto $\varnothing \in A$ (come già osservato, un insieme può avere come suoi elementi altri insiemi).

Osservazione: unicità dell'insieme vuoto

L’insieme vuoto è unico, ovvero: se $A$ e $B$ sono due insiemi che non contengono nessun elemento, allora, per il principio di estensionalità, si ha che:

$$A=B$$

Infatti $A$ e $B$, avendo gli stessi elementi (cioè nessuno), verificano la formula:

$$\forall x(x\in A⟺x\in B)$$

1.2 - Singoletti

Definizione: singoletto

Un singoletto o insieme unitario è un insieme formato da un solo elemento.

Esempio: $\{0\}$ e $\{\{1,2,3\}\}$ sono singoletti

Gli insiemi $\{0\}$ e $\{\{1,2,3\}\}$ sono singoletti: in particolare, il primo è formato unicamente dall’elemento $0$, mentre il secondo è formato dall’unico elemento $\{1,2,3\}$ che a sua volta è un insieme (quest’ultimo però non unitario).

1.3 - Cardinalità di un insieme

Definizione: cardinalità di un insieme

La cardinalità di un insieme $A$, denotata "$|A|$" oppure "$\#A$", è il numero degli elementi di $A$.

Se $A$ contiene un numero finito $n$ di elementi si denota "$|A|=n$" (es. $|\{0,1\}|=2$), mentre se $A$ contiene infiniti elementi (e cioè è un insieme infinito) si denota "$|A|=\infty$".

Esempio: $|\{\{0,1\},0,1\}|=3$

Dato un insieme $A=\{0,1\}$ e un insieme $B$ che ha come elementi l’insieme $A$ e i numeri $0$ e $1$, quindi $B=\{\{0,1\},0,1\}$, la sua cardinalità $|B|=|\{\{0,1\},0,1\}|$ è pari a $3$, in quanto l’insieme $A$ viene considerato come un unico elemento in $B$, mentre gli altri due numeri $0$ e $1$ vengono considerati ognuno come un elemento a sé stante.

Esempio: $|\{\{0,1\},0,1\}|=3$

Dato un insieme $A=\{0,1\}$ e un insieme $B$ che ha come elementi l’insieme $A$ e i numeri $0$ e $1$, quindi $B=\{\{0,1\},0,1\}$, la sua cardinalità $|B|=|\{\{0,1\},0,1\}|$ è pari a $3$, in quanto l’insieme $A$ viene considerato come un unico elemento in $B$, mentre gli altri due numeri $0$ e $1$ vengono considerati ognuno come un elemento a sé stante.

Esempio: $|\mathbb{N}|=\infty$

La cardinalità dell’insieme dei numeri naturali $\mathbb{N}$, quindi $|\mathbb{N}|$, è uguale a $\infty$, in quanto l’insieme $\mathbb{N}$ contiene infiniti elementi che vanno da $0$ a $+\infty$.

1.4 - Rappresentazioni di un insieme

1.4.2 - Rappresentazione per elencazione di un insieme

Rappresentazione per elencazione di un insieme

La rappresentazione per elencazione di un insieme prevede di indicare tutti gli elementi che appartengono ad un insieme semplicemente elencandoli uno ad uno, all’interno di parentesi graffe. Quando si rappresenta un insieme per elencazione, non ha mai importanza l’ordine con cui si scrivono gli elementi e, inoltre, tale metodo è pratico solo quando l’insieme in questione contiene pochi elementi.

Esempio: $A=\{1,2,3,4,5,6,7,8,9\}$ e $B=\{\text{Francia},\text{Germania},\text{Svizzera}\}$

La notazione $A=\{1,2,3,4,5,6,7,8,9\}$ definisce correttamente l’insieme $A$ come l’insieme dei numerali naturali compresi tra 1 e 9, mentre $B=\{\text{Francia},\text{Germania},\text{Svizzera}\}$ definisce correttamente l’insieme $B$ come un insieme contenente alcune nazioni europee.

Nel caso in cui ci siano invece più elementi che si vogliono omettere nella notazione (come anche nel caso di insiemi infiniti, in cui si vogliono esplicitare soltanto alcuni determinati elementi dell’insieme), si possono usare i puntini di sospensione "$\dots$" all’interno delle graffe.

Esempio: $\mathbb{N}=\{0,1,2,3,\dots \},\mathbb{Z}=\{\dots ,-2,-1,0,1,2,\dots \},\mathbb{R}=\{\dots ,3,\dots ,4,\dots \}$

Ognuno dei seguenti insiemi numerici usa i puntini di sospensione in modo diverso:

• L’insieme dei numeri naturali $\mathbb{N}$ può essere rappresentato con la notazione $\mathbb{N}=\{0,1,2,3,\dots \}$, in cui i puntini che seguono il $3$ indicano che ci sono infiniti numeri naturali dopo di esso.
• Allo stesso modo, per l’insieme dei numeri interi $\mathbb{Z}$, nella notazione $\mathbb{Z}=\{\dots ,-2,-1,0,1,2,\dots \}$ i primi puntini indicano che prima del $-2$ ci sono infiniti numeri interi.
• Anche per l’insieme dei numeri reali $\mathbb{R}$, nella notazione $\mathbb{R}=\{\dots ,3,\dots ,4,\dots \}$ i puntini tra il $3$ e il $4$ indicano che ci sono infiniti numeri reali tra i due.

1.4.2 - Rappresentazione per caratteristica di un insieme

Rappresentazione per caratteristica di un insieme

La rappresentazione per caratteristica di un insieme consiste nel dare una proprietà che risulti verificata da tutti gli elementi dell’insieme e solo da essi. Dunque, la forma generale della definizione di un insieme $X$ con questo metodo è del tipo

$$X=\{x\in \mathcal{U}\mid P(x)\}$$

oppure del tipo

$$X=\{x\mid x\in \mathcal{U},P(x)\}$$

(da leggersi ”$X$ è l’insieme degli elementi $x$ in $\mathcal{U}$ tali che $x$ soddisfa la proprietà $P$”) dove l’insieme universo $\mathcal{U}$, che può essere implicito o esplicito, è stato già definito precedentemente e funziona da ambito del discorso.

Esempio: $C=\{\text{cittadini italiani}\}$ e $D=\{x\in \mathbb{R}\mid x^2>1\}$

Le notazioni $C=\{\text{cittadini italiani}\}$ e $D=\{x\in \mathbb{R}\mid x^2>1\}$ definiscono correttamente due insiemi nonostante non siano elencati esplicitamente tutti i loro elementi, specialmente nel caso dell’insieme $D$ che sarebbe matematicamente impossibile, essendo questo insieme infinito.

In particolare, gli oggetti a cui applicare i due criteri sono presi a priori da un certo insieme di riferimento, esplicito nel caso di $D$ (l’insieme dei numeri reali $\mathbb{R}$) ed implicito nel caso di $C$ (avrebbe senso applicare il criterio su un insieme di esseri umani).

1.4.3 - Rappresentazione grafica di un insieme

Rappresentazione grafica di un insieme

La rappresentazione grafica di un insieme consiste nel rappresentarlo con una regione di piano limitata da una curva chiusa: gli elementi dell’insieme sono scritti all’interno della linea chiusa, mentre gli elementi che non appartengono all’insieme stanno all’esterno. Il nome dell’insieme, invece, viene posto all’esterno della linea chiusa vicino a essa. Forme grafiche di questo tipo sono generalmente denominate diagrammi di Eulero-Venn ed offrono un supporto intuitivo notevole nel rappresentare gli insiemi.

1.4.4 - Rappresentazione per intervalli di un insieme

Rappresentazione per intervalli di un insieme

La rappresentazione per intervalli di un insieme si può usare nel caso in cui l’insieme contiene tutti i numeri (generalmente in $\mathbb{R}$) compresi tra due valori detti estremi dell’intervallo, che possono essere compresi o meno nell’intervallo stesso. Per indicare l’intervallo, quindi, si racchiudono i due valori, separati da una virgola, in due parentesi che sono quadre se i valori sono compresi nell’intervallo o, altrimenti, tonde.

Osservazione: intervalli con un solo estremo incluso

Gli intervalli non devono necessariamente avere entrambi gli intervalli inclusi o esclusi: possono averne anche uno solo incluso e l’altro escluso.

Esempio: $A=\{x\in \mathbb{R}\mid x>-1\wedge x\le 4\}=(-1,4]$

Dato un insieme $A=\{x\in \mathbb{R}\mid x>-1\wedge x\le 4\}$, esso si può anche rappresentare come l’intervallo $(-1,4]$ dal momento che esso racchiude tutti i numeri $x\in \mathbb{R}$ compresi tra $-1$ escluso e $4$ incluso.

1.5 - Tuple

Definizione: tupla

Una tupla (o lista ordinata) è una collezione di oggetti disposti in un ordine specifico. A differenza di un insieme, l’ordine degli elementi in una tupla è significativo, e gli stessi elementi possono comparire più volte.

Una $n$-upla è una tupla di esattamente $n$ elementi, dove $n$ è un numero intero non-negativo e si denota similmente alla rappresentazione per elencazione di un insieme nei seguenti modi:

$$(a_1,a_2,\dots ,a_n)$$

oppure:

$$⟨a_1,a_2,\dots ,a_n⟩$$

Se la tupla è composta da solamente $2$ elementi $a$ e $b$, si parla di coppia ordinata e solitamente si denota solo con le parentesi tonde:

$$(a,b)$$

2 - Sottoinsiemi

Definizione: sottoinsieme

Dati due insiemi $A$ e $B$, $B$ si dice sottoinsieme di $A$ e si denota con "$B\subseteq A$" (”$B$ è incluso in $A$”) se ogni elemento di $B$ è anche un elemento di $A$:

$$B\subseteq A=\{b\in B\mid b\in A\}$$

Alternativamente, usando i connettivi logici, la definizione di sottoinsieme si può esprimere nel seguente modo:

$$B\subseteq A⟺\forall x(x\in B⟹x\in A)$$

Per indicare che $B$ non è un sottoinsieme di $A$ (e cioè che esiste almeno un elemento in $B$ che non è in $A$) si usa la notazione "$B⊈A$":

$$B⊈A⟺\exists x(x\in B⟹x\notin A)$$

Esempio: sottoinsiemi di $A=\{0,1,2,3,4\}$

Dato un insieme $A=\{0,1,2,3,4\}$, possibili sottoinsiemi di $A$ sono gli insiemi $B=\{0,1,2\}$ e $C=\{4\}$, in quanto gli elementi che contengono appartengono anche ad $A$:

$$B,C\subseteq A$$

Non è invece sottoinsieme di $A$ l’insieme $D=\{1,4,5\}$, perché l’elemento $5$ non è contenuto anche in $A$:

$$D⊈A$$

Osservazione: confusione sul termine "contenere"

In italiano, il termine “contenere” è ambiguo perché si utilizza:

• Sia nel senso di appartenenza (es. ”$\mathbb{N}$ contiene $1$”, inteso come ”$1$ è un elemento di $\mathbb{N}$” che si traduce in termini matematici con "$1\in \mathbb{N}$").
• Sia nel senso di inclusione (es. ”$\mathbb{N}$ contiene i numeri pari”, inteso come “l’insieme dei numeri pari è incluso in $\mathbb{N}$” che si traduce in termini matematici con "$\{x\in \mathbb{Z}\mid x=2k,k\in \mathbb{Z}\}\in \mathbb{N}$").

Per questo motivo, l’uso del termine “contenere” è sconsigliato in ambito insiemistico.

2.1 - Sottoinsiemi propri

Definizione: sottoinsieme proprio

Dati un insieme $A$ e un suo sottoinsieme $B$ con $B\ne A$ (cioè che almeno un elemento in $A$ non appartiene a $B$), $B$ è detto sottoinsieme proprio di $A$ e, per evidenziarne la disuguaglianza, si può indicare nel seguente modo:

$$B⊊A$$

Esempio: sottoinsiemi propri di $A=\{0,1,2,3,4\}$

Dato un insieme $A=\{0,1,2,3,4\}$, dei suoi possibili sottoinsiemi propri sono gli insiemi $B=\{1,3,4\}⊊A$ e $C=\{0,1,2,3\}⊊A$.

2.2 - Sottoinsiemi banali

Definizione: sottoinsiemi banali

Per ogni insieme $X$ si ha sempre che $\varnothing \subseteq X$ e $X\subseteq X$: questi sono detti sottoinsiemi banali di $X$.

Esempio: sottoinsiemi banali di $A=\{0,1,2,3,4\}$

Dato un insieme $A=\{0,1,2,3,4\}$, i suoi sottoinsiemi banali sono l’insieme vuoto $\varnothing$ e l’insieme $B=\{0,1,2,3,4\}$.

2.3 - Insieme delle parti

Definizione: insieme delle parti

Dato un insieme $A$, si definisce insieme delle parti o insieme potenza di $A$ e si denota "$\mathcal{P}(A)$" l’insieme i cui elementi sono tutti i possibili sottoinsiemi di $A$: $\mathcal{P}(A)=\{B\mid B\subseteq A\}$

Esempio di insieme delle parti

Dato un insieme $A=\{a,b,c\}$, si ha $\mathcal{P}(A)=\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\},\{b,c\},\{a,c\},A\}$.

Osservazione: insieme delle parti di un insieme vuoto

L’unico sottoinsieme di un insieme vuoto $\varnothing$ è $\{\varnothing \}$. Pertanto, il suo insieme delle parti è $\mathcal{P}(\varnothing )=\{\varnothing \}$ e, dunque, $\mathcal{P}(\varnothing )\ne \varnothing$.

Osservazione: insieme delle parti di un singoletto

Dato un singoletto $A=\{a\}$, gli suoi sottoinsiemi sono quelli banali, quindi il suo insieme delle parti è $\mathcal{P}(A)=\mathcal{P}(\{a\})=\{\varnothing ,\{a\}\}$.

Osservazione: insieme delle parti è sempre non vuoto

Per qualsiasi insieme $A$, vuoto o non vuoto, il suo insieme delle parti $\mathcal{P}(A)$ contiene sempre l’insieme vuoto $\varnothing$ e $A$ stesso come elementi (cioè i suoi sottoinsiemi banali), quindi è sempre non vuoto.

Osservazione: cardinalità di un insieme delle parti

Dato un insieme finito $A$ con $n$ elementi (quindi $|A|=n$), allora il suo insieme delle parti $\mathcal{P}(A)$ ha esattamente $2^n$ elementi, cioè $|\mathcal{P}(A)|=2^{|A|}$. Per esempio, dato un insieme $A$ con $3$ elementi, il suo insieme delle parti $\mathcal{P}(A)$ avrà $2^3=8$ elementi.

3 - Uguaglianza di due insiemi

L’uguaglianza di due insiemi viene verificata solo se viene rispettato il principio di estensionalità.

Principio di estensionalità

Due insiemi sono uguali se e solo se hanno gli stessi elementi, ovvero:

$$A=B⟺\forall x(x\in A⟺x\in B)$$

Osservazione: irrilevanza dell'ordine e unicità degli elementi

Dato un insieme $\{-1,2,3\}$, per il principio di estensionalità, si ha che:

$$\{-1,2,3\}=\{2,-1,3\}=\{-1,2,3,3\}$$

In altre parole: l’ordine in cui vengono elencati gli elementi di un insieme è irrilevante e le eventuali ripetizioni non contano, proprio perché per tutti e tre insiemi vale il principio di estensionalità e, quindi, sono in realtà tutti lo stesso insieme:

$$\{-1,2,3\}=\{2,-1,3\}=\{-1,2,3,3\}⟺\forall x(x\in \{-1,2,3\}⟺x\in \{2,-1,3\}⟺x\in \{-1,2,3,3\})$$

Al contrario, $\{3,-1,2\}\ne \{2,-1,2\}$ poiché $3$ appartiene al primo insieme ma non al secondo.

Dal principio di estensionalità si ottiene il teorema della doppia inclusione, usato spesso (in maniera implicita) per dimostrare l’uguaglianza di due insiemi.

Teorema della doppia inclusione

Dati due insiemi $A$ e $B$, essi sono uguali se e solo se ciascuno è un sottoinsieme dell’altro contemporaneamente:

$$A=B⟺A\subseteq B\wedge B\subseteq A$$

Dimostrazione

Avendo una bi-implicazione, si devono dimostrare entrambe le direzioni:

• Direzione dell’implicazione $⟹$: se $A=B$, allora $A$ e $B$ hanno esattamente gli stessi elementi, cioè ogni elemento di $A$ è anche un elemento di $B$ (e quindi $A\subseteq B$) e ogni elemento di $B$ è anche un elemento di $A$ (e quindi $B\subseteq A$).
• Direzione della conseguenza $⟸$: se $A\subseteq B$ e $B\subseteq A$, allora $A$ e $B$ devono contenere esattamente gli stessi elementi, perché l’esistenza di un $x\in A\mid x\notin B$ contraddice l’ipotesi $A\subseteq B$ e l’esistenza di un $y\in B\mid y\notin A$ contraddice l’ipotesi $B\subseteq A$.

$■$

4 - Operazioni sugli insiemi

4.1 - Intersezione di insiemi

Definizione: intersezione di due insiemi

Dati due insiemi $A$ e $B$, si dice intersezione di $A$ e $B$ e si denota "$A\cap B$" l’insieme che comprende gli elementi che appartengono contemporaneamente sia ad $A$ che a $B$:

$$A\cap B=\{x\mid x\in A\wedge x\in B\}$$

Due insiemi $A$ e $B$ si dicono disgiunti se non hanno elementi in comune:

$$A\cap B=\varnothing$$

Esempio: intersezione di due insiemi

Dati due insiemi:

$$\begin{array}{rl}& A=\{n\in \mathbb{N}\mid n\text{ eˋ pari}\}=\{0,2,4,6,\dots \}\\ & B=\{n\in \mathbb{N}\mid 10\le n^2\le 200\}=\{4,6,8,10,12,14\}\end{array}$$

la loro intersezione è: $A\cap B=\{4,6,8,10,12,14\}$

Esempio: intersezione di tre insiemi

Dati tre insiemi:

$$\begin{array}{rl}& A=\{a,b,c,d,e\}\\ & B=\{d,e,f,g\}\\ & C=\{g,h,i\}\end{array}$$

le combinazioni delle loro intersezioni sono:

$$\begin{array}{rl}A\cap B& =\{d,e\}\\ B\cap C& =\{g\}\\ A\cap C& =\varnothing \\ A\cap B\cap C& =\varnothing \end{array}$$

Esempio: intersezione di insiemi delle parti

Dato un insieme $X=\{a,b,c,d\}$ e dati due insiemi

$$\begin{array}{rl}& A=\{S\in \mathcal{P}(X)\mid |S|=2\}=\{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}\\ & B=\{S\in \mathcal{P}(X)\mid c\in S\}=\{\{c\},\{a,c\},\{b,c\},\{c,d\},\{a,b,c\},\{b,c,d\},\{a,c,d\},\{a,b,c,d\}\}\end{array}$$

allora

$$A\cap B=\{\{a,c\},\{b,c\},\{c,d\}\}$$

4.2 - Unione di insiemi

Definizione: unione di due insiemi

Dati due insiemi $A$ e $B$, si dice unione di $A$ e $B$ e si denota "$A\cup B$" l’insieme contenente tutti gli elementi di entrambi gli insiemi:

$$A\cup B=\{x\mid x\in A\vee x\in B\}$$

Gli elementi che si trovano sia in $A$ che in $B$ vengono presi in considerazione una volta sola perché, per l’unicità degli elementi, non ci possono essere elementi ripetuti in un insieme.

Esempio: unione di due insiemi

Dati due insiemi:

$$\begin{array}{rl}& A=\{0,1\}\\ & B=\{2,3,4\}\end{array}$$

la loro unione è

$$A\cup B=\{0,1,2,3,4\}$$

Esempio: unione di tre insiemi

Dati tre insiemi:

$$\begin{array}{rl}& A=\{a,b,c,d,e\}\\ & B=\{d,e,f,g\}\\ & C=\{g,h,i\}\end{array}$$

le combinazioni delle loro unioni sono:

$$\begin{array}{rl}A\cup B& =\{a,b,c,d,e,f,g\}\\ B\cup C& =\{d,e,f,g,h,i\}\\ A\cup C& =\{a,b,c,d,e,g,h,i\}\\ A\cup B\cup C& =\{a,b,c,d,e,f,g,h,i\}\end{array}$$

Esempio: unione degli insiemi dei numeri pari e dispari

Dati due insiemi:

$$\begin{array}{rl}& A=\{n\in \mathbb{N}\mid n\mathrm{mod}2=0\}\\ & B=\{n\in \mathbb{N}\mid n\mathrm{mod}2=1\}\end{array}$$

ossia rispettivamente gli insiemi dei numeri naturali pari e dispari, allora lo loro unione è l’insieme dei numeri naturali $\mathbb{N}$:

$$A\cup B=\mathbb{N}$$

4.3 - Differenza di insiemi

Definizione: differenza tra due insiemi

Dati due insiemi $A$ e $B$, si dice differenza tra $A$ e $B$ e si denota "$A\setminus B$" l’insieme degli elementi presenti in $A$ ma non in $B$:

$$A\setminus B=\{x\mid x\in A\wedge x\notin B\}$$

Esempio: differenza tra due insiemi

Dati due insiemi:

$$\begin{array}{rl}& A=\{0,1,2\}\\ & B=\{2\}\end{array}$$

la loro differenza è:

$$A\setminus B=\{0,1\}$$

4.4 - Differenza simmetrica di insiemi

Definizione: differenza simmetrica tra due insiemi

Dati due insiemi $A$ e $B$, si dice differenza simmetrica tra $A$ e $B$ e si denota "$A\Delta B$" l’insieme degli elementi presenti solamente in uno dei due insiemi:

$$A\Delta B=\{x\mid \forall x((x\in A\wedge x\notin B)\vee (x\in B\wedge x\notin A))\}$$

Esempio: differenza simmetrica di due insiemi

Dati due insiemi:

$$\begin{array}{r}A=\{1,4,6,23,57\}\\ B=\{2,4,6,8,10\}\end{array}$$

la loro differenza simmetrica è:

$$A\Delta B=\{1,2,8,10,23,57\}$$

4.5 - Complemento di un insieme

Definizione: complemento di un insieme

Dati un insieme universo $\mathcal{U}$ e un insieme $A\subseteq \mathcal{U}$, si dice complemento di $A$ e si denota "$A^{\complement }$" (ma anche "$A^{\prime }$", "$\overline{A}$", "${\complement }_{\mathcal{U}}(A)$" e "$\complement (A)$") la differenza $\mathcal{U}\setminus A$, cioè il sottoinsieme degli elementi di $\mathcal{U}$ non in $A$:

$$A^{\complement }=\mathcal{U}\setminus A=\{x\mid x\in \mathcal{U}\wedge x\notin A\}$$

Osservazione: $\mathbb{I}={\mathbb{Q}}^{\complement }$ con $\mathcal{U}=\mathbb{R}$

L’insieme dei numeri irrazionali $\mathbb{I}$ si può esprimere come complemento di $\mathbb{Q}$ se si considera come insieme universo $\mathbb{R}$:

$$\mathbb{I}={\mathbb{Q}}^{\complement }\text{ con }\mathcal{U}=\mathbb{R}$$

Proprietà del doppio complemento: $(A^{\complement }{)}^{\complement }=A$

Dati un insieme universo $\mathcal{U}$ e un insieme $A\subseteq \mathcal{U}$, il doppio complemento $(A^{\complement }{)}^{\complement }$ di $A$ in $\mathcal{U}$ è sempre uguale ad $A$:

$$(A^{\complement }{)}^{\complement }=A$$

Dimostrazione

Dobbiamo verificare che, qualunque sia $A$, valga la formula:

$$\forall x(x\in (A^{\complement }{)}^{\complement })⟺x\in A)$$

Fissiamo quindi un generico $x$. Sfruttando la corrispondenza tra operazioni insiemistiche e connettivi logici visti in precedenza, la formula:

$$x\in (A^{\complement }{)}^{\complement }⟺x\in A$$

diventa:

$$\neg (\neg (x\in A))⟺x\in A$$

Se ora nella formula sostituiamo l’affermazione "$x\in A$" con una corrispondente lettera proposizionale $P$ otteniamo la formula proposizionale:

$$\neg (\neg P)⟺P$$

In generale, il fatto che $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 (A^{\complement }{)}^{\complement }⟺x\in A$$

da cui $(A^{\complement }{)}^{\complement }=A$, come volevasi dimostrare.

$■$

4.5.1 - Leggi di De Morgan

Le leggi di De Morgan (o teoremi di De Morgan) sono due regole fondamentali usate sia in teoria degli insiemi che in logica proposizionale. Esse descrivono come negare combinazioni di proposizioni logiche o insiemi, permettendo di trasformare espressioni complesse in forme equivalenti.

In particolare, in teoria degli insiemi, le leggi di De Morgan descrivono la relazione tra intersezione, unione e complemento di due insiemi e si esprimono nei seguenti due teoremi.

Prima legge di De Morgan: $(A\cup B{)}^{\complement }=A^{\complement }\cap B^{\complement }$

Il complemento dell’insieme $A\cup B$, cioè l’insieme di tutti gli elementi che non appartengono né ad $A$ né a $B$, è uguale all’intersezione dei complementi di $A$ e $B$, ovvero l’insieme di tutti gli elementi che non appartengono a $A$ e, contemporaneamente, non appartengono a $B$:

$$(A\cup B{)}^{\complement }=A^{\complement }\cap B^{\complement }$$

Dimostrazione

Dobbiamo dimostrare che, per ogni $x$, vale la formula:

$$x\in (A\cup B{)}^{\complement }⟺x\in (A^{\complement }\cap B^{\complement })$$

Utilizzando la corrispondenza tra operazioni insiemistiche e connettivi, la formula precedente diventa:

$$\neg (x\in A\vee x\in B)⟺\neg (x\in A)\wedge \neg (x\in B)$$

Questa è una proposizione della forma:

$$\neg (P\vee Q)⟺\neg P\wedge \neg Q$$

dove $P$ e $Q$ sono, rispettivamente, "$x\in A$" e "$x\in B$".

Poiché tale proposizione è una tautologia, l’identità insiemistica è dimostrata.

$■$

Seconda legge di De Morgan: $(A\cap B{)}^{\complement }=A^{\complement }\cup B^{\complement }$

Il complemento dell’insieme $A\cap B$, cioè l’insieme di tutti gli elementi che appartengono contemporaneamente sia ad $A$ che a $B$, è uguale all’unione dei complementi di $A$ e $B$, ovvero l’insieme di tutti gli elementi che non appartengono ad $A$ oppure che non appartengono a $B$:

$$(A\cap B{)}^{\complement }=A^{\complement }\cup B^{\complement }$$

Dimostrazione

Dobbiamo dimostrare che, per ogni $x$, vale la formula:

$$x\in (A\cap B{)}^{\complement }⟺x\in (A^{\complement }\cup B^{\complement })$$

Utilizzando la corrispondenza tra operazioni insiemistiche e connettivi, la formula precedente diventa:

$$\neg (x\in A\wedge x\in B)⟺\neg (x\in A)\vee \neg (x\in B)$$

Questa è una proposizione della forma:

$$\neg (P\wedge Q)⟺\neg P\vee \neg Q$$

dove $P$ e $Q$ sono, rispettivamente, "$x\in A$" e "$x\in B$".

Poiché tale proposizione è una tautologia, l’identità insiemistica è dimostrata.

$■$

Dimostrazione alternativa

La stessa identità può anche essere dimostrata utilizzando ciò che abbiamo già dimostrato, ovvero che per tutti gli insiemi $X$ e $Y$ valgono $(X^{\complement }{)}^{\complement }=X$ per la proprietà del doppio complemento e $(X\cup Y{)}^{\complement }=X^{\complement }\cap Y^{\complement }$ per la prima legge di De Morgan.

Partendo da $(A\cap B{)}^{\complement }$, per la proprietà del doppio complemento abbiamo che:

$$(A\cap B{)}^{\complement }=(A^{\complement }{)}^{\complement }\cap (B^{\complement }{)}^{\complement }{)}^{\complement }$$

Per la prima legge di De Morgan, possiamo passare dall’intersezione all’unione:

$$((A^{\complement }{)}^{\complement }\cap (B^{\complement }{)}^{\complement }{)}^{\complement }=((A^{\complement }\cup B^{\complement }{)}^{\complement }{)}^{\complement }$$

Avendo dei doppi complementi, possiamo rimuoverli:

$$((A^{\complement }\cup B^{\complement }{)}^{\complement }{)}^{\complement }=A^{\complement }\cup B^{\complement }$$

Si ottiene così la formula desiderata.

$■$

4.6 - Prodotto cartesiano di insiemi

Definizione: prodotto cartesiano di due insiemi

Dati due insiemi $A$ e $B$, si definisce prodotto cartesiano di $A$ e $B$ e si denota "$A\times B$" l’insieme i cui elementi sono coppie ordinate di elementi con il primo elemento in $A$ e il secondo in $B$:

$$A\times B=\{(x,y)\mid x\in A\wedge y\in B\}$$

Quando $A$ e $B$ coincidono, quindi si ha un prodotto cartesiano $A\times A$, si può anche denotare come $A^2$ o, se $A$ è ripetuto $n$ volte (cioè come $\underset{n\text{volte}}{\underbrace{A\times A\times \dots \times A}}$), si può scrivere come $A^n$. Per convenzione, inoltre, si pone anche $A^0=\{\varnothing \}$.

Esempio: prodotto cartesiano di due insiemi

Dati due insiemi:

$$\begin{array}{rl}& A=\{1,2\}\\ & B=\{3,4,5\}\end{array}$$

il loro prodotto cartesiano è

$$A\times B=\{(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)\}$$

Osservazione: $A\times \varnothing =\varnothing$

Il prodotto cartesiano tra un insieme $A$ e l’insieme vuoto $\varnothing$ è sempre pari all’insieme vuoto $\varnothing$:

$$A\times \varnothing =\varnothing$$

Osservazione: $A\ne \varnothing \wedge B\ne \varnothing ⟹A\times B\ne \varnothing$

Il prodotto cartesiano tra due insiemi A e B non vuoti è sempre pari a un insieme non vuoto:

$$A\ne \varnothing \wedge B\ne \varnothing ⟹A\times B\ne \varnothing$$

Osservazione: valenza geometrica del prodotto cartesiano

Se si interpreta l’insieme $\mathbb{R}$ dei numeri reali come una retta, allora il prodotto cartesiano ${\mathbb{R}}^2=\mathbb{R}\times \mathbb{R}$ è l’insieme formato da tutte le coppie ordinate $(x,y)$ di numeri reali:

$${\mathbb{R}}^2=\{(x,y)\mid x\in \mathbb{R}\wedge y\in \mathbb{R}\}$$

In altre parole, ${\mathbb{R}}^2$ non è nient’altro che il piano cartesiano, in cui un elemento di ${\mathbb{R}}^2$ è un punto identificato dalla coppia $(x,y)$; stesso discorso si può fare per l’insieme ${\mathbb{R}}^3$, ossia l’insieme che rappresenta lo spazio cartesiano in cui i punti sono identificati dalle tre coordinate $(x,y,z)$.

Proposizione: cardinalità del prodotto cartesiano

Dati due insiemi finiti $A$ e $B$, con $|A|=m$ e $|B|=n$, allora la cardinalità del loro prodotto cartesiano $|A\times B|$ è uguale al prodotto delle loro cardinalità $m\cdot n$; se, invece, almeno uno tra $A$ e $B$ è infinito, allora anche $|A\times B|$ è infinito:

$$|A|=m,|B|=n⟹|A\times B|=\{\begin{array}{ll}m\cdot n& m,n\ne \infty \\ \infty & m,n=\infty \end{array}$$

Dimostrazione

Se $A$ e $B$ sono finiti con $|A|=m$ e $|B|=n$, si possono numerare ed elencare i loro elementi come $A=\{a_1,a_2,...,a_m\}$ e $B=\{b_1,b_2,...,b_n\}$ e si possono organizzare gli elementi di $A\times B$ in una tabella:

$$\begin{array}{cccc}(a_1,b_1)& (a_1,b_2)& \dots & (a_1,b_n)\\ (a_2,b_1)& (a_2,b_2)& \dots & (a_2,b_n)\\ ⋮& ⋮& \ddots & ⋮\\ (a_m,b_1)& (a_m,b_2)& \dots & (a_m,b_n)\end{array}$$

La tabella include chiaramente tutti gli elementi di $A\times B$ una volta sola e, quindi, devono essere $m\cdot n$ in totale, essendo $m$ in verticale ed $n$ in orizzontale. Il caso in cui uno degli insieme è infinito è chiaro, in quanto la tabella risulterà avere righe o colonne infinite.

$■$

5 - Famiglia di insiemi

Definizione: famiglia di insiemi

Un insieme è detto famiglia di insiemi se ognuno degli elementi è a sua volta un insieme e viene denotata come:

$$\{A_i{\}}_{i\in I}$$

dove l’insieme $I$ è chiamato insieme degli indici e ciascun $i\in I$ identifica univocamente un insieme $A_i$ della famiglia.

5.1 - Operazioni su famiglie di insiemi

Definizione: intersezione di una famiglia di insiemi

Data una famiglia di insiemi $\{A_i{\}}_{i\in I}$, l’intersezione degli $A_i$ è l’insieme degli elementi che appartengono a ogni $A_i$:

$$\bigcap _{i=1}^n{A}_i=\{x\mid \forall i\in I(x\in A_i)\}$$

Definizione: unione di una famiglia di insiemi

Data una famiglia di insiemi $\{A_i{\}}_{i\in I}$, l’unione degli $A_i$ è l’insieme degli elementi che appartengono ad almeno un $A_i$:

$$\bigcup _{i=1}^n{A}_i=\{x\mid \exists i\in I(x\in A_i)\}$$

Definizione: prodotto cartesiano di una famiglia di insiemi

Data una famiglia di insiemi $\{A_i{\}}_{i\in I}$, il prodotto cartesiano degli $A_i$ è l’insieme delle $n$-uple $(x_1,x_2,\dots ,x_n)$ con $x_i\in A_i$:

$$\prod _{i=1}^n{A}_i=\{(x_1,x_2,\dots ,x_n)\mid \forall i\in I(x_i\in A_i)\}$$

Fonti

• 🏫 Lezioni dei Prof. Chen Yu e Terracini Lea del corso di Matematica Discreta (canale C), Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2023-24.
• 🏫 Lezioni del Prof. Radeschi Marco del corso di Algebra Lineare (canale C), Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2023-24.
• 🏫 Lezioni e slide del Prof. Viale Matteo del corso di Logica Matematica (canale B), Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2024-25:
  • 2.1 - Insiemi_moodle.pdf

Footnotes

1. Si legge come “appartiene a” (es. $a\in A$ denota che l’elemento $a$ appartiene all’insieme $A$). ↩

2. Si legge come “non appartiene a” (es. "$b\notin B$" denota che l’elemento $b$ non appartiene all’insieme $B$). ↩