Insiemi, sottoinsiemi e insieme delle parti (da zero)

Esempio svolto: Esercizio 6 - numero di sottoinsiemi (insieme delle parti).

Insiemi ed elementi

Un insieme è una collezione di oggetti distinti, chiamati elementi. Si scrive tra parentesi graffe:

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

• Per dire che $2$ è un elemento di $A$ si scrive $2 \in A$. Per dire che $5$ non lo è: $5 \notin A$.
• Nell'insieme non conta l'ordine ($\{1,2,3\} = \{3,1,2\}$) e non contano le ripetizioni ($\{1,1,2\} = \{1,2\}$).
• L'insieme vuoto, scritto $\emptyset$ (o $\{\}$), è l'insieme che non ha nessun elemento.
• Convenzione: gli insiemi si indicano con lettere maiuscole ($A, B, X, Y$), gli elementi con lettere minuscole ($a, b, x, y$).

Le operazioni tra insiemi (unione, intersezione, complementare, prodotto cartesiano) sono in Operazioni tra insiemiUnione, intersezione, differenza, complementare e prodotto cartesiano, con le leggi di De Morgan e il legame con la logica.Operazioni tra insiemi →; gli insiemi di numeri $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}$ in Insiemi numerici (N, Z, Q, R)Naturali, interi, razionali e reali, perché la radice di 2 obbliga a passare da Q a R, e gli intervalli.Insiemi numerici (N, Z, Q, R) →.

Tre modi di descrivere un insieme

1. Per elencazione. Si scrivono tutti gli elementi tra graffe: $A = \{1, 2, 3\}$. Funziona bene per insiemi finiti (con un numero finito di elementi). Per insiemi infiniti si usano i puntini quando la regola è chiara: $\mathbb{N} = \{0, 1, 2, 3, \dots\}$.

2. Con un predicato (proprietà caratteristica). Si dice da quale insieme "grande" si pescano gli elementi e quale proprietà devono avere:

$$A = \{x \in \mathbb{N} : 1 \le x < 4\} = \{1, 2, 3\}$$

Si legge: "l'insieme degli $x$ naturali tali che $1 \le x < 4$". La proprietà dopo i due punti è un predicato $p(x)$ (vedi Logica e quantificatoriProposizioni, connettivi, predicati e quantificatori (per ogni, esiste), con le regole per negarli.Logica e quantificatori →): nell'insieme entrano esattamente gli $x$ per cui $p(x)$ è vera. È l'unico modo pratico per insiemi infiniti come

$$\{x \in \mathbb{R} : x^2 \le 4\} = \{x \in \mathbb{R} : -2 \le x \le 2\} = [-2, 2]$$

Qui si vede un fatto utile: predicati equivalenti descrivono lo stesso insieme ($x^2 \le 4$ e $-2 \le x \le 2$ sono veri per gli stessi $x$).

Attenzione all'insieme da cui si pesca. $\{x \in \mathbb{N} : x^2 \le 4\} = \{0, 1, 2\}$, mentre $\{x \in \mathbb{R} : x^2 \le 4\}$ è l'intero intervallo $[-2, 2]$. Stessa proprietà, insiemi diversissimi.

3. Graficamente (diagrammi di Venn). Si disegna l'insieme come una zona chiusa del piano e i suoi elementi come punti dentro la zona. Non serve per dimostrare, ma aiuta moltissimo a intuire le relazioni tra insiemi.

Cardinalità (il "modulo" di un insieme)

Il numero di elementi di un insieme finito $A$ si chiama cardinalità di $A$ e si scrive $|A|$ (le barre verticali si leggono "modulo" o "cardinalità"). Nel testo dell'esercizio "modulo di $A$ = $n$" significa semplicemente: $A$ ha $n$ elementi.

Esempi: $|\{1,2,3\}| = 3$; $|\{a\}| = 1$; $|\emptyset| = 0$.

Sottoinsiemi

$B$ è un sottoinsieme di $A$, e si scrive $B \subseteq A$, se ogni elemento di $B$ è anche elemento di $A$.

Esempi con $A = \{1, 2, 3\}$:

• $\{1, 3\} \subseteq A$ (sia $1$ sia $3$ stanno in $A$) ✓;
• $\{2\} \subseteq A$ ✓;
• $\{1, 5\} \not\subseteq A$, perché $5 \notin A$.

Due sottoinsiemi che esistono sempre, per qualsiasi insieme $A$:

• l'insieme vuoto $\emptyset$ (la condizione "ogni elemento di $\emptyset$ sta in $A$" è vera, perché $\emptyset$ non ha elementi da controllare);
• l'insieme $A$ stesso (ogni elemento di $A$ sta in $A$).

Si dice anche "$A$ è contenuto in $B$". In simboli: $A \subseteq B$ se $\forall a \in A : a \in B$. Nel diagramma di Venn, la zona di $A$ sta tutta dentro la zona di $B$. Se anche un solo elemento di $A$ sta fuori da $B$, allora $A \not\subseteq B$ (basta un controesempio per smentire un "per ogni").

Inclusione stretta (sottoinsieme proprio)

$A \subset B$ (oppure $A \subsetneq B$) se $A \subseteq B$ e inoltre $\exists\, b \in B$ con $b \notin A$. Cioè $A$ è contenuto in $B$ ma non è tutto $B$: in $B$ c'è almeno un elemento in più. Esempio: $\{1, 2\} \subset \{1, 2, 3\}$ (l'elemento in più è $3$), mentre $\{1, 2, 3\} \subseteq \{1, 2, 3\}$ ma non in senso stretto.

Uguaglianza di insiemi

$$A = B \quad \text{se} \quad A \subseteq B \ \text{ e } \ B \subseteq A$$

Due insiemi sono uguali quando hanno esattamente gli stessi elementi. Questa definizione dà anche il metodo per dimostrare che due insiemi sono uguali: si dimostrano le due inclusioni separatamente (ogni elemento del primo sta nel secondo, e viceversa).

Insieme delle parti

L'insieme delle parti di $A$, scritto $\mathcal{P}(A)$, è l'insieme di tutti i sottoinsiemi di $A$. I suoi elementi sono a loro volta insiemi.

Esempio con $A = \{a, b\}$. I sottoinsiemi sono: $\emptyset$, $\{a\}$, $\{b\}$, $\{a, b\}$. Quindi

$$\mathcal{P}(\{a, b\}) = \bigl\{\, \emptyset,\ \{a\},\ \{b\},\ \{a, b\} \,\bigr\}$$

e $|\mathcal{P}(A)| = 4$.

Esempio con $A = \{1, 2, 3\}$. I sottoinsiemi sono $8$:

Totale: $1 + 3 + 3 + 1 = 8 = 2^3$.

Attenzione a non confondere $a \in A$ (elemento) con $\{a\} \subseteq A$ (sottoinsieme con un solo elemento): $a$ è un oggetto, $\{a\}$ è un insieme che lo contiene. In $\mathcal{P}(A)$ ci sono i sottoinsiemi come $\{a\}$, non gli elementi come $a$.

Errori frequenti con $\in$ e $\subseteq$ (dalla lezione)

La regola: $\in$ collega un elemento a un insieme; $\subseteq$ collega un insieme a un insieme. Prima di scrivere uno dei due simboli, chiediti "cosa c'è a sinistra: un oggetto o un insieme? E di che insieme fa parte?".

L'ultima coppia è la più insidiosa: $\emptyset$ è sia elemento sia sottoinsieme di $\mathcal{P}(A)$, per due motivi diversi.

(Per la prof, se $A \ne \emptyset$, i sottoinsiemi diversi da $\emptyset$ e da $A$ si chiamano sottoinsiemi propri.)

Quanti sottoinsiemi ha un insieme?

Dagli esempi: $|A| = 2$ dà $4 = 2^2$ sottoinsiemi, $|A| = 3$ dà $8 = 2^3$. In generale

$$|A| = n \implies |\mathcal{P}(A)| = 2^n$$

Intuitivamente: per costruire un sottoinsieme si decide, per ciascuno degli $n$ elementi, "lo metto" oppure "non lo metto": $2$ scelte per ogni elemento, quindi $2 \cdot 2 \cdots 2 = 2^n$ possibilità. La dimostrazione rigorosa per induzione è nell'Esercizio 6 - numero di sottoinsiemi (insieme delle parti).

Due strumenti per contare

1. Somma per insiemi disgiunti. Due insiemi sono disgiunti se non hanno elementi in comune. Se $X$ e $Y$ sono disgiunti, allora il numero di elementi della loro unione è la somma:

$$|X \cup Y| = |X| + |Y|$$

(Se avessero elementi in comune, questi verrebbero contati due volte, ed è per questo che serve la disgiunzione.)

2. Corrispondenza uno a uno. Se si riesce ad abbinare gli elementi di due insiemi $X$ e $Y$ in modo che ogni elemento di $X$ abbia esattamente un partner in $Y$ e ogni elemento di $Y$ esattamente un partner in $X$, allora $|X| = |Y|$. Tale abbinamento si chiama biiezione (o corrispondenza biunivoca). È come far sedere gli invitati a un tavolo con tanti posti quanti gli invitati, senza posti liberi e senza persone in piedi: i due gruppi hanno lo stesso numero di elementi.

Per verificare che una regola $f : X \to Y$ è una biiezione bisogna controllare:

• ben definita: $f(x)$ appartiene davvero a $Y$ per ogni $x \in X$;
• iniettiva: elementi diversi di $X$ hanno immagini diverse (due elementi non finiscono sullo stesso partner);
• suriettiva: ogni elemento di $Y$ è l'immagine di qualche elemento di $X$ (nessun posto libero).

Un modo rapido per mostrare tutto insieme è esibire la regola inversa che riporta da $Y$ a $X$.

Insiemi finiti e infiniti (lezione 4)

Sia $E \ne \emptyset$.

• $E$ è finito se ha un numero finito di elementi: $|E| = n$ per qualche $n \in \mathbb{N}$.
• $E$ è infinito, e si scrive $|E| = +\infty$, se non è finito.

Questa è la definizione intuitiva. La prof dà anche una caratterizzazione analitica, che usa le biiezioni:

$E$ è infinito $\iff$ $E$ può essere messo in corrispondenza biunivoca con un suo sottoinsieme proprio (un sottoinsieme strettamente più piccolo).

Perché per gli insiemi finiti non succede. $E = \{1, 2, 3\}$ non può essere messo in corrispondenza biunivoca con un sottoinsieme proprio, per esempio $\{1, 2\}$: un sottoinsieme proprio ha meno elementi, e due insiemi finiti sono in biiezione solo se hanno lo stesso numero di elementi (qualcuno resterebbe "senza partner").

$\mathbb{N}$ è infinito. La regola $n \mapsto 2n$ mette in corrispondenza biunivoca $\mathbb{N}$ con l'insieme dei pari $\{0, 2, 4, \dots\} \subsetneq \mathbb{N}$:

Ogni naturale ha esattamente un partner pari, e ogni pari $m$ è il partner di esattamente un naturale, cioè $\frac{m}{2}$ (la regola inversa). Quindi c'è una biiezione tra $\mathbb{N}$ e una sua parte propria: $\mathbb{N}$ è infinito. (Curioso ma vero: "ci sono tanti pari quanti naturali".)

$[0, 1)$ è infinito. La regola $x \mapsto \frac{x}{2}$ manda $[0, 1)$ in $[0, \frac12) \subsetneq [0, 1)$ ed è biunivoca: la regola inversa è $y \mapsto 2y$ (ogni $y \in [0, \frac12)$ è l'immagine di esattamente un $x = 2y \in [0, 1)$).

Attenzione: infinito non vuol dire illimitato. $[0, 1)$ è infinito ma limitato (sta tutto tra $0$ e $1$): vedi Estremo superiore (sup)Maggioranti e minoranti, massimo e minimo, estremo superiore (il più piccolo dei maggioranti) e inferiore, con la caratterizzazione con epsilon.Estremo superiore (sup) →.

Operazioni che servono

Le operazioni sono spiegate per bene in Operazioni tra insiemiUnione, intersezione, differenza, complementare e prodotto cartesiano, con le leggi di De Morgan e il legame con la logica.Operazioni tra insiemi →; qui il minimo indispensabile per l'esercizio 6.

• Unione: $X \cup Y$ = elementi che stanno in $X$ o in $Y$.
• Aggiungere un elemento: $X \cup \{b\}$ = $X$ più l'elemento $b$.
• Togliere un elemento: $B \setminus \{b\}$ = $B$ senza l'elemento $b$.
• Se $|B| = n + 1$ e $b \in B$, allora $|B \setminus \{b\}| = n$.