Esercizio 6

Testo (Lezione 6, esercizio 6 del foglio). Dimostrare per induzione che se $|A| = n$, con $n \ge 1$, allora $|\mathcal{P}(A)| = 2^n$.

Passo 0: capire cosa dobbiamo dimostrare

Servono il principio di induzioneSe $P(n_0)$ è vera e da $P(n)$ segue sempre $P(n+1)$, allora $P(n)$ vale per ogni $n \ge n_0$.Principio di induzione → e le nozioni di cardinalità, sottoinsieme, insieme delle parti e biiezione (vedi Insiemi e insieme delle partiCome si descrive un insieme, sottoinsiemi, uguaglianza, insieme delle parti e insiemi finiti e infiniti.Insiemi e insieme delle parti →): se non le conosci, leggi prima quelle due note.

Cosa significano i simboli.

• $|A| = n$: l'insieme $A$ ha $n$ elementi ("modulo" = cardinalitàIl numero di elementi di un insieme finito; si scrive $\lvert A \rvert$ e non ha nulla a che fare con il valore assoluto.Insiemi e insieme delle parti →).
• $\mathcal{P}(A)$: l'insieme delle partiCome si descrive un insieme, sottoinsiemi, uguaglianza, insieme delle parti e insiemi finiti e infiniti.Insiemi e insieme delle parti → di $A$, cioè l'insieme di tutti i sottoinsiemi di $A$ (compresi $\emptyset$L'insieme vuoto, che non ha elementi: è sottoinsieme di qualunque insieme.Insiemi e insieme delle parti → e $A$ stesso).
• $|\mathcal{P}(A)| = 2^n$: il numero di sottoinsiemi di $A$ è $2^n$.

Esempi per farsi un'idea.

Funziona nei primi casi, ma serve una dimostrazione per ogni $n \ge 1$, e quindi usiamo l'induzione.

Come si imposta l'induzione qui. L'affermazione $P(n)$ è:

"Per ogni insieme $A$ con $n$ elementi, $|\mathcal{P}(A)| = 2^n$."

Attenzione: nell'affermazione $P(n)$ c'è un "per ogni insieme con $n$ elementi". L'induzione è sul numero $n$, mentre l'insieme $A$ non è fisso: nel passo induttivo useremo l'ipotesi su un altro insieme (più piccolo di un elemento). Per questo l'ipotesi deve valere per tutti gli insiemi con $n$ elementi.

Passo 1: passo base ($n = 1$)

Dobbiamo verificare $P(1)$Passo base: si controlla l'affermazione sul primo valore richiesto, qui $n_0 = 1$ perché il testo chiede $n \ge 1$.Principio di induzione →: ogni insieme con $1$ elemento ha $2^1 = 2$ sottoinsiemi.

Sia $A = \{a\}$ un insieme con un solo elemento. Quali sono i suoi sottoinsiemi? Un sottoinsieme contiene alcuni (o nessuno) degli elementi di $A$, e $A$ ha un solo elemento $a$, quindi ci sono solo due possibilità:

• non contiene $a$: è l'insieme vuoto $\emptyset$;
• contiene $a$: è $\{a\}$.

Quindi $\mathcal{P}(A) = \{\emptyset, \{a\}\}$, che ha $2$ elementi. E $2^1 = 2$ ✓.

Il passo base è fatto.

Passo 2: passo induttivo

Dobbiamo dimostrare: per ogni $n \ge 1$, se $P(n)$ è vera allora $P(n+1)$ è vera.

Fissiamo $n \ge 1$.

Ipotesi induttivaSi suppone vera $P(n)$ per un $n$ fissato e la si usa per dedurre $P(n+1)$.Principio di induzione → $P(n)$: ogni insieme con $n$ elementi ha esattamente $2^n$ sottoinsiemi.

Tesi $P(n+1)$: ogni insieme con $n + 1$ elementi ha esattamente $2^{n+1}$ sottoinsiemi.

Dimostrazione della tesi

Sia $B$ un insieme qualsiasi con $n + 1$ elementi. Dobbiamo contare i suoi sottoinsiemi.

(a) Isolare un elemento. Poiché $n + 1 \ge 2 > 0$, $B$ ha almeno un elemento. Ne scegliamo uno e lo chiamiamo $b$. Sia $A = B \setminus \{b\}$Differenza di insiemi: gli elementi di $B$ che non stanno in $\{b\}$, cioè $B$ privato di $b$.Operazioni tra insiemi → ($B$ senza $b$). Allora $A$ ha $n$ elementi, quindi si può applicare l'ipotesi induttiva ad $A$:

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

(b) Dividere i sottoinsiemi di $B$ in due gruppi. Ogni sottoinsieme $Y \subseteq B$$Y$ è sottoinsieme di $B$: ogni elemento di $Y$ sta anche in $B$.Insiemi e insieme delle parti → appartiene a uno e uno solo di questi due gruppi, a seconda che contenga $b$ oppure no:

• Gruppo 1: i sottoinsiemi di $B$ che non contengono $b$.
• Gruppo 2: i sottoinsiemi di $B$ che contengono $b$.

I due gruppi sono disgiuntiDue insiemi sono disgiunti se la loro intersezione è vuota, cioè non hanno elementi in comune.Operazioni tra insiemi → (nessun sottoinsieme può contenere e non contenere $b$ contemporaneamente) e, uniti, danno tutti i sottoinsiemi di $B$ (ogni sottoinsieme o contiene $b$ o non lo contiene). Quindi, per la regola della somma per insiemi disgiuntiSe due insiemi finiti non hanno elementi in comune, la loro unione ha tanti elementi quanti il primo più quanti il secondo.Insiemi e insieme delle parti →:

$$|\mathcal{P}(B)| = |\text{Gruppo 1}| + |\text{Gruppo 2}|$$

(c) Contare il Gruppo 1. Un sottoinsieme di $B$ che non contiene $b$ ha tutti gli elementi in $B \setminus \{b\} = A$, cioè è un sottoinsieme di $A$. Viceversa, ogni sottoinsieme di $A$ è anche un sottoinsieme di $B$ che non contiene $b$. Quindi il Gruppo 1 è esattamente $\mathcal{P}(A)$, e per l'ipotesi induttiva:

$$|\text{Gruppo 1}| = |\mathcal{P}(A)| = 2^n$$

(d) Contare il Gruppo 2. Un sottoinsieme $Y$ di $B$ che contiene $b$ si ottiene prendendo un sottoinsieme $X$ di $A$ e aggiungendo $b$. Costruiamo una corrispondenza:

$$f : \mathcal{P}(A) \to \text{Gruppo 2}, \qquad f(X) = X \cup \{b\}$$

Mostriamo che è una biiezioneFunzione iniettiva e suriettiva: accoppia gli elementi dei due insiemi uno a uno, quindi questi hanno lo stesso numero di elementi.Funzioni iniettive, suriettive e inverse →, così il Gruppo 2 ha tanti elementi quanti $\mathcal{P}(A)$.

• Ben definitaLa regola $f$ produce davvero, per ogni $X$ di partenza, un elemento dell'insieme di arrivo dichiarato (qui il Gruppo 2).: se $X \subseteq A$, allora $X \cup \{b\} \subseteq B$ e contiene $b$, quindi appartiene al Gruppo 2 ✓.
• Iniettiva (insiemi diversi vanno in insiemi diversi): se $X \cup \{b\} = X' \cup \{b\}$ con $X, X' \subseteq A$, allora, togliendo $b$ da entrambi (e ricordando che $X$ e $X'$ non contengono $b$, perché sono sottoinsiemi di $A = B \setminus \{b\}$) si ottiene $X = X'$ ✓.
• Suriettiva (ogni elemento del Gruppo 2 è raggiunto): sia $Y$ nel Gruppo 2, cioè $Y \subseteq B$ con $b \in Y$. Poniamo $X = Y \setminus \{b\}$. Allora $X \subseteq B \setminus \{b\} = A$, e $f(X) = (Y \setminus \{b\}) \cup \{b\} = Y$ (perché $b \in Y$) ✓.

Quindi $f$ è una biiezione e

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

(e) Mettere insieme.

$$|\mathcal{P}(B)| = 2^n + 2^n = 2 \cdot 2^n = 2^{n+1}$$

(l'ultimo passaggio è la proprietà delle potenze$a^m \cdot a^n = a^{m+n}$: qui $2^1 \cdot 2^n = 2^{n+1}$.Funzioni potenza → $2 \cdot 2^n = 2^{n+1}$). Ed è la tesi ✓.

Il passo induttivo è fatto.

Verifica del passo con un esempio concreto

Prendiamo $n = 2$, quindi $B = \{1, 2, 3\}$ ($n + 1 = 3$ elementi). Scegliamo $b = 3$, e $A = \{1, 2\}$.

Il Gruppo 2 si ottiene dal Gruppo 1 aggiungendo $3$ a ciascun sottoinsieme: $\emptyset \to \{3\}$, $\{1\} \to \{1,3\}$, $\{2\} \to \{2,3\}$, $\{1,2\} \to \{1,2,3\}$. Totale $4 + 4 = 8 = 2^3$ ✓.

Passo 3: conclusione

Il passo base ha mostrato $P(1)$; il passo induttivo ha mostrato che $P(n)$ implica $P(n+1)$ per ogni $n \ge 1$. Per il principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →:

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

Osservazioni

• E se $n = 0$? Allora $A = \emptyset$ e $\mathcal{P}(\emptyset) = \{\emptyset\}$ ha $1$ elemento (l'unico sottoinsieme di $\emptyset$ è $\emptyset$ stesso). E $2^0 = 1$ ✓. La formula vale anche per $n = 0$, ma il testo chiede $n \ge 1$, quindi il passo base è $n = 1$.
• Perché serve il passo base $n = 1$ e non basta il passo induttivo. Il passo induttivo trasforma un caso in quello successivo, ma ha bisogno di partire da qualche caso vero.
• Interpretazione alternativa (utile per ricordare). Per costruire un sottoinsieme di un insieme con $n$ elementi, per ogni elemento si sceglie "dentro" o "fuori": $2$ scelte ciascuno, quindi $2^n$ in tutto. Il passo induttivo formalizza questo: l'elemento $b$ può stare "fuori" (Gruppo 1) o "dentro" (Gruppo 2).

Errori comuni

• Applicare l'ipotesi induttiva a $B$ invece che ad $A$. L'ipotesi vale per insiemi con $n$ elementi; $B$ ne ha $n + 1$. Bisogna togliere un elemento per ottenere $A$.
• Dire che l'ipotesi induttiva vale "per un certo insieme $A$ fissato" invece che "per ogni insieme con $n$ elementi". Nel passo induttivo serve usarla per l'insieme $A = B \setminus \{b\}$, che non è quello da cui siamo partiti.
• Dimenticare di mostrare che i due gruppi sono disgiunti e completi, cioè che nessun sottoinsieme sia contato due volte né dimenticato.
• Non giustificare che il Gruppo 2 ha tanti elementi quanto il Gruppo 1 (serve la biiezione "aggiungo $b$").
• Dimenticare $\emptyset$ e $A$ tra i sottoinsiemi quando si fanno gli esempi.

Riassunto