2 Insiemi: rappresentazioni e operazioni

[next] [prev] [prev-tail] [tail] [up]

Capitolo 2
Insiemi: rappresentazioni e operazioni

WEB (Materiali vari)

“

Studia questo capitolo con l’AI: quiz, esercizi e altro

Ripassa con le flashcard

Esercizi auto-generati

Sorgente di questo capitolo

Schede, test e video di matematika.it

Esercizi del prof. De Capoa

Presentazioni— slide NotebookLM (clic per aprire il PDF)

Teoria degli insiemi

Logica e insiemi

Audio overview— podcast NotebookLM (clic per ascoltare)

[IT] Insiemi e logica

Per insieme intendiamo ogni raccolta in un tutto $M$ di oggetti $m$ ben distinti della nostra intuizione o del nostro pensiero.”
— Georg Cantor (1895)

____________________________________________________________________________________

2.1 Introduzione motivazionale

quiz e materiali con l’AI

La parola insieme è probabilmente il termine più ricorrente in tutta la matematica. Quando diciamo “i numeri naturali”, “i punti di una retta”, “le soluzioni di un’equazione”, stiamo sempre indicando un insieme.

Capire bene il linguaggio degli insiemi non è un esercizio fine a se stesso: è il vocabolario che permetterà di parlare in modo preciso di tutto ciò che incontreremo. Dire “$\sqrt {2}$ non è razionale” significa esattamente “$\sqrt {2}\notin \mathbb{Q} $”; dire “ogni numero naturale è intero” significa $\mathbb{N} \subseteq \mathbb{Z} $. Senza un linguaggio comune e condiviso non c’è dimostrazione possibile.

In questo capitolo costruiamo, un mattone alla volta, questo vocabolario: che cos’è un insieme, come lo si rappresenta, quali operazioni si possono fare tra insiemi e quali proprietà soddisfano. Sono nozioni che riprenderai in tutti i capitoli successivi.

2.2 Concetto di insieme e appartenenza

quiz e materiali con l’AI

flashcard del paragrafo

Definizione 2.1 — Insieme, intuitivamente

Un insieme è una collezione di oggetti, detti elementi, percepiti come un tutto. Perché una collezione sia un insieme nel senso matematico è necessario che dato un qualsiasi oggetto si possa stabilire, senza ambiguità, se quell’oggetto appartiene o non appartiene alla collezione.

Indicheremo gli insiemi con lettere maiuscole ($A$, $B$, $X$, $\ldots $) e i loro elementi con lettere minuscole ($a$, $b$, $x$, $\ldots $). La relazione tra un elemento e l’insieme che lo contiene si scrive così:

\[ x\in A \quad \text {(``$x$ appartiene ad $A$'')}, \qquad x\notin A \quad \text {(``$x$ non appartiene ad $A$'').} \]

Esempio 2.1

Sia $A$ l’insieme delle vocali della parola “matematica”. Allora $a\in A$, $e\in A$, $i\in A$, mentre $b\notin A$ e $5\notin A$. L’insieme è “ben definito”: per ogni oggetto possiamo decidere se appartiene o no.

Attenzione!

Non tutte le collezioni del linguaggio comune sono insiemi in senso matematico. “L’insieme delle ragazze alte della classe” non è un insieme finché non fissiamo una soglia precisa: senza un criterio univoco di appartenenza, la collezione non è ben definita.

Nota

Due principi fondano la teoria degli insiemi:

1.: un elemento può appartenere o non appartenere a un insieme, ma non entrambe le cose;
2.: l’ordine in cui si elencano gli elementi non conta, e ogni elemento si conta una sola volta.

Quindi $\{1,2,3\}$, $\{3,2,1\}$ e $\{1,1,2,3,3\}$ rappresentano lo stesso insieme.

La cardinalità di un insieme finito $A$ è il numero dei suoi elementi e si indica con $|A|$. Se $A=\{a,e,i,o,u\}$, allora $|A|=5$.

2.3 Rappresentazioni: tabulare, caratteristica, Eulero-Venn

quiz e materiali con l’AI

flashcard del paragrafo

Un insieme può essere descritto in tre modi equivalenti.

Rappresentazione tabulare (per elencazione). Si elencano fra parentesi graffe tutti gli elementi, separati da virgola:

\[ V=\{a,e,i,o,u\},\qquad P_{10}=\{2,3,5,7\}. \]

È comoda quando gli elementi sono pochi. Per insiemi infiniti si usano i puntini di sospensione, purché la regola di formazione sia chiara:

\[ \mathbb{N} =\{0,1,2,3,4,\ldots \},\qquad \text {multipli di }3 = \{0,3,6,9,12,\ldots \}. \]

Rappresentazione caratteristica (per proprietà). Si scrive una proprietà $P(x)$ che gli elementi devono soddisfare:

\[ A=\{\,x\mid P(x)\,\} \]

e si legge “l’insieme degli $x$ tali che vale $P(x)$”. La barra verticale $\mid $ si pronuncia “tali che”. Esempio:

\[ P_{10}=\{\,x\in \mathbb{N} \mid x\text { è primo e } x<10\,\}. \]

Spesso si indica il dominio a sinistra della barra ($x\in \mathbb{N} $) e la condizione a destra.

Rappresentazione di Eulero-Venn (grafica). Si disegna l’insieme come una regione del piano (di solito un ovale) e si segnano al suo interno gli elementi. È utile per visualizzare relazioni tra più insiemi.

[Picture] — Figura 2.1: Diagramma di Eulero-Venn dell’insieme $V=\{a,e,i,o,u\}$ delle vocali. L’elemento $b$ è esterno ($b\notin V$).

Esempio 2.2 — Tre forme per lo stesso insieme

L’insieme dei divisori positivi di $12$ può essere scritto:

tabulare: $D_{12}=\{1,2,3,4,6,12\}$;
caratteristica: $D_{12}=\{\,x\in \mathbb{N} \mid x\text { divide }12\,\}$;
Eulero-Venn: un ovale contenente i sei punti $1,2,3,4,6,12$.

2.4 Sottoinsiemi e inclusione

quiz e materiali con l’AI

flashcard del paragrafo

Definizione 2.2 — Sottoinsieme

Dati due insiemi $A$ e $B$, diciamo che $A$ è sottoinsieme di $B$ (oppure: $A$ è incluso in $B$) se ogni elemento di $A$ appartiene anche a $B$. Si scrive

\[ A\subseteq B \quad \Longleftrightarrow \quad \forall x:\ x\in A \Rightarrow x\in B. \]

Se inoltre $A\neq B$ (cioè in $B$ c’è almeno un elemento che non sta in $A$), si dice che $A$ è sottoinsieme proprio di $B$ e si scrive $A\subset B$.

Esempio 2.3

$\{1,2\}\subseteq \{1,2,3\}$, anzi $\{1,2\}\subset \{1,2,3\}$ (sottoinsieme proprio). Si ha pure $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} $: ogni naturale è intero, ogni intero è razionale, ma esistono interi non naturali (ad esempio $-1$) e razionali non interi (ad esempio $\tfrac {1}{2}$).

Definizione 2.3 — Uguaglianza tra insiemi

$A=B$ se e solo se $A\subseteq B$ e $B\subseteq A$. In altre parole, due insiemi sono uguali quando hanno esattamente gli stessi elementi.

Nota — Doppia inclusione: una strategia di dimostrazione

Per dimostrare che due insiemi $A$ e $B$ sono uguali è quasi sempre conveniente provare separatamente le due inclusioni $A\subseteq B$ e $B\subseteq A$. Vedremo applicazioni concrete di questa tecnica nei capitoli sulle dimostrazioni.

Definizione 2.4 — Insieme vuoto

L’insieme vuoto è l’insieme privo di elementi e si indica con $\varnothing $ (oppure $\{\,\}$). Per convenzione, $\varnothing \subseteq A$ per ogni insieme $A$.

Attenzione!

Non confondere $\varnothing $ con $\{\varnothing \}$: il primo è l’insieme vuoto (cardinalità $0$), il secondo è un insieme che contiene un elemento (l’insieme vuoto stesso), quindi ha cardinalità $1$.

Definizione 2.5 — Insieme delle parti

L’insieme delle parti di $A$, denotato $\mathcal {P}(A)$, è l’insieme di tutti i sottoinsiemi di $A$ (compresi $\varnothing $ e $A$ stesso). Se $|A|=n$, allora $|\mathcal {P}(A)|=2^n$.

Esempio 2.4

Se $A=\{a,b\}$, allora $\mathcal {P}(A)=\{\,\varnothing ,\,\{a\},\,\{b\},\,\{a,b\}\,\}$ e $|\mathcal {P}(A)|=2^2=4$.

2.5 Unione e intersezione

quiz e materiali con l’AI

flashcard del paragrafo

Definizione 2.6 — Unione

L’unione di $A$ e $B$ è l’insieme degli elementi che appartengono ad $A$ o a $B$ (o a entrambi):

\[ A\cup B = \{\,x\mid x\in A \text { oppure } x\in B\,\}. \]

Definizione 2.7 — Intersezione

L’intersezione di $A$ e $B$ è l’insieme degli elementi che appartengono sia ad $A$ sia a $B$:

\[ A\cap B = \{\,x\mid x\in A \text { e } x\in B\,\}. \]

Se $A\cap B=\varnothing $, gli insiemi $A$ e $B$ si dicono disgiunti.

Teorema 2.1 — Proprietà di unione e intersezione

Per ogni $A$, $B$, $C$:

commutativa: $A\cup B = B\cup A$, $A\cap B = B\cap A$;
associativa: $(A\cup B)\cup C = A\cup (B\cup C)$, $(A\cap B)\cap C = A\cap (B\cap C)$;
distributiva: $A\cap (B\cup C) = (A\cap B)\cup (A\cap C)$, $A\cup (B\cap C) = (A\cup B)\cap (A\cup C)$;
idempotente: $A\cup A = A$, $A\cap A = A$;
assorbimento: $A\cup (A\cap B) = A$, $A\cap (A\cup B) = A$;
vuoto: $A\cup \varnothing = A$, $A\cap \varnothing = \varnothing $.

Dimostrazione. Mostriamo la commutatività dell’unione; le altre si provano in modo analogo. Sia $x\in A\cup B$. Per definizione $x\in A$ oppure $x\in B$, che è esattamente la condizione $x\in B$ oppure $x\in A$, ovvero $x\in B\cup A$. Quindi $A\cup B\subseteq B\cup A$. Scambiando i ruoli di $A$ e $B$ si ottiene l’inclusione opposta e quindi l’uguaglianza.

\[ |A\cup B| = |A| + |B| - |A\cap B| \]

Quest’ultima formula, detta principio di inclusione-esclusione, conta gli elementi dell’unione evitando di contare due volte quelli in comune.

2.6 Differenza e complemento

quiz e materiali con l’AI

flashcard del paragrafo

Definizione 2.8 — Differenza

La differenza di $A$ meno $B$ è l’insieme degli elementi che appartengono ad $A$ ma non a $B$:

\[ A\setminus B = \{\,x\mid x\in A \text { e } x\notin B\,\}. \]

Quando si lavora dentro un insieme di riferimento $U$ (chiamato insieme universo), si introduce una notazione abbreviata per la differenza rispetto a $U$.

Definizione 2.9 — Complemento

Fissato un insieme universo $U$, il complemento di $A\subseteq U$ è

\[ \overline {A} = U\setminus A = \{\,x\in U\mid x\notin A\,\}. \]

Esempio 2.5

Sia $U=\{1,2,3,\ldots ,10\}$ e $A=\{2,4,6,8,10\}$ l’insieme dei pari di $U$. Allora $\overline {A}=\{1,3,5,7,9\}$. Si verifica che $A\cup \overline {A}=U$ e $A\cap \overline {A}=\varnothing $.

Teorema 2.2 — Leggi di De Morgan

Per ogni $A,B\subseteq U$:

\[ \overline {A\cup B} = \overline {A}\cap \overline {B},\qquad \overline {A\cap B} = \overline {A}\cup \overline {B}. \]

Dimostrazione (della prima). Sia $x\in \overline {A\cup B}$. Allora $x\notin A\cup B$, dunque $x\notin A$ e $x\notin B$, cioè $x\in \overline {A}$ e $x\in \overline {B}$, ossia $x\in \overline {A}\cap \overline {B}$. Si ottiene $\overline {A\cup B}\subseteq \overline {A}\cap \overline {B}$. Ogni passaggio è reversibile, quindi vale anche l’inclusione opposta e dunque l’uguaglianza. (Per la seconda, ragionamento analogo.)

Nota

Le leggi di De Morgan ci dicono come “distribuire” un complemento su unione e intersezione: scambiando $\cup $ con $\cap $ e prendendo il complemento di ciascun insieme. Le rincontreremo in logica con i connettivi “e” e “o”.

2.7 Prodotto cartesiano

quiz e materiali con l’AI

flashcard del paragrafo

Definizione 2.10 — Coppia ordinata

Una coppia ordinata $(a,b)$ è un’entità in cui contano quali sono gli elementi e in che ordine compaiono. Due coppie sono uguali se e solo se:

\[ (a,b)=(c,d) \quad \Longleftrightarrow \quad a=c \text { e } b=d. \]

Attenzione!

Non confondere $(a,b)$ con $\{a,b\}$: l’insieme $\{a,b\}=\{b,a\}$, ma la coppia $(a,b)\neq (b,a)$ se $a\neq b$.

Definizione 2.11 — Prodotto cartesiano

Il prodotto cartesiano di $A$ e $B$ è l’insieme di tutte le coppie ordinate in cui il primo elemento appartiene ad $A$ e il secondo a $B$:

\[ A\times B = \{\,(a,b)\mid a\in A,\ b\in B\,\}. \]

Nota

Se $A$ e $B$ sono finiti, $|A\times B|=|A|\cdot |B|$. Nell’esempio in figura: $|A|=3$, $|B|=2$, dunque $|A\times B|=6$.

Il prodotto cartesiano è la struttura che sta dietro al piano cartesiano: i punti del piano sono coppie ordinate $(x,y)\in \mathbb{R} \times \mathbb{R} $. Lo riprenderemo nel capitolo di geometria analitica.

2.8 Esempi svolti

quiz e materiali con l’AI

Esempio 2.6 — Operazioni con insiemi finiti

Siano $A=\{1,2,3,4,5\}$ e $B=\{4,5,6,7\}$, contenuti nell’universo $U=\{1,2,\ldots ,10\}$. Calcoliamo le principali operazioni.

Soluzione. In termini algebrici, prima di sostituire i valori:

\begin{align*} A\cup B &= \{x\mid x\in A \lor x\in B\}, \\ A\cap B &= \{x\mid x\in A \land x\in B\}, \\ A\setminus B &= \{x\mid x\in A \land x\notin B\}, \\ \overline {A} &= U\setminus A. \end{align*}

Sostituendo:

\begin{align*} A\cup B &= \{1,2,3,4,5,6,7\}, \\ A\cap B &= \{4,5\}, \\ A\setminus B &= \{1,2,3\}, \\ \overline {A} &= \{6,7,8,9,10\}. \end{align*}

Verifica del principio di inclusione-esclusione:

\[ |A\cup B| = |A| + |B| - |A\cap B| = 5+4-2 = 7. \quad \checkmark \]

Esempio 2.7 — Insieme delle parti

Determinare $\mathcal {P}(A)$ per $A=\{x,y,z\}$.

Soluzione. Poiché $|A|=3$, ci aspettiamo $|\mathcal {P}(A)|=2^3=8$ sottoinsiemi. Li elenchiamo per cardinalità crescente:

\[ \mathcal {P}(A)=\{\,\varnothing ,\,\{x\},\{y\},\{z\},\,\{x,y\},\{x,z\},\{y,z\},\,\{x,y,z\}\,\}. \]

Esempio 2.8 — Verifica di una legge di De Morgan

Con $A=\{1,2,3,4\}$, $B=\{3,4,5,6\}$, $U=\{1,2,\ldots ,8\}$, verifichiamo $\overline {A\cup B}=\overline {A}\cap \overline {B}$.

Soluzione. A sinistra: $A\cup B=\{1,2,3,4,5,6\}$, dunque $\overline {A\cup B}=\{7,8\}$. A destra: $\overline {A}=\{5,6,7,8\}$, $\overline {B}=\{1,2,7,8\}$, dunque $\overline {A}\cap \overline {B}=\{7,8\}$. Le due espressioni coincidono. $\checkmark $

2.9 Esercizi proposti

quiz e materiali con l’AI

Esercizio 2.1

1.: Scrivi per elencazione l’insieme $A=\{\,x\in \mathbb{N} \mid x\text { è dispari e } x<12\,\}$.
2.: Indica con $\subseteq $, $\subset $ o $\not \subseteq $ la relazione corretta tra le seguenti coppie di insiemi: $\{1,2\}$ e $\{1,2,3\}$; $\mathbb{N} $ e $\mathbb{Z} $; $\{a,b\}$ e $\{a,c\}$; $\varnothing $ e $\{0\}$.
3.: Siano $A=\{1,2,3,4,5\}$ e $B=\{3,5,7,9\}$. Calcola $A\cup B$, $A\cap B$, $A\setminus B$ e $B\setminus A$. Verifica con i conti che $|A\cup B|=|A|+|B|-|A\cap B|$.
4.: Sia $U=\{1,2,\ldots ,12\}$ e $A=\{\,x\in U\mid x\text { è multiplo di }3\,\}$. Determina $\overline {A}$ e verifica che $A\cap \overline {A}=\varnothing $ e $A\cup \overline {A}=U$.
5.: Per gli stessi $A$ e $B$ dell’esercizio 3, verifica entrambe le leggi di De Morgan rispetto a un universo $U=\{1,2,\ldots ,10\}$.
6.: Determina $\mathcal {P}(B)$ per $B=\{1,2,3,4\}$ ed elenca quanti sottoinsiemi ha cardinalità $0,1,2,3,4$. Confronta con i coefficienti binomiali $\binom {4}{k}$.
7.: Siano $A=\{1,2,3\}$ e $B=\{a,b\}$. Scrivi tutte le coppie di $A\times B$ e di $B\times A$. È vero che $A\times B=B\times A$?
8.: (Discussione.) È vero o falso che, comunque presi $A$ e $B$, vale $A\setminus B = B\setminus A$? Trova un controesempio o dimostra l’uguaglianza.

2.10 Riepilogo del capitolo

quiz e materiali con l’AI

Riepilogo

Un insieme è una collezione di oggetti per i quali sia possibile decidere, senza ambiguità, l’appartenenza. Si scrive $x\in A$ o $x\notin A$.
Tre rappresentazioni equivalenti: tabulare ($A=\{a,e,i,o,u\}$), caratteristica ($A=\{x\mid P(x)\}$), Eulero-Venn (grafica).
$A\subseteq B$ significa: ogni elemento di $A$ appartiene a $B$. Si ha $A=B$ se e solo se $A\subseteq B$ e $B\subseteq A$.
$\varnothing $ è l’insieme vuoto e $\varnothing \subseteq A$ per ogni $A$. $\mathcal {P}(A)$ è l’insieme dei sottoinsiemi di $A$ e $|\mathcal {P}(A)|=2^{|A|}$.
Operazioni fondamentali: $A\cup B$ (unione), $A\cap B$ (intersezione), $A\setminus B$ (differenza), $\overline {A}=U\setminus A$ (complemento rispetto all’universo $U$).
Principio di inclusione-esclusione: $|A\cup B|=|A|+|B|-|A\cap B|$.
Leggi di De Morgan: $\overline {A\cup B}=\overline {A}\cap \overline {B}$, $\overline {A\cap B}=\overline {A}\cup \overline {B}$.
$A\times B$ è l’insieme delle coppie ordinate $(a,b)$ con $a\in A$, $b\in B$; per insiemi finiti $|A\times B|=|A|\cdot |B|$.