Induzione il numero di sottoinsiemi è 2 alla n

Testo

Dimostra per induzione su $n$ che ogni insieme con $n$ elementi ha esattamente $2^n$ sottoinsiemi.

Soluzione

Base ($n=0$): l’unico insieme con $0$ elementi è $\varnothing$, che ha un solo sottoinsieme (sé stesso), e $2^0 = 1$. Vero.

Passo induttivo: supponiamo che ogni insieme con $k$ elementi abbia $2^k$ sottoinsiemi. Sia $S$ un insieme con $k+1$ elementi; fissiamo un elemento $e \in S$ e poniamo $S' = S \setminus \{e\}$, che ha $k$ elementi.

I sottoinsiemi di $S$ si dividono in due gruppi:

• quelli che non contengono $e$: sono esattamente i sottoinsiemi di $S'$, cioè $2^k$;
• quelli che contengono $e$: si ottengono aggiungendo $e$ a un sottoinsieme di $S'$, quindi sono anch’essi $2^k$.

In totale $2^k + 2^k = 2 \cdot 2^k = 2^{k+1}$ sottoinsiemi. Per il principio di induzione la tesi vale per ogni $n$. $\blacksquare$

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Insieme delle parti · Principio di induzione
Metodi: Induzione
Competenze: Dimostrare
Tipo di esercizio: Dimostrazione