Indukcja matematyczna - zbiór n-elementowy ma 2ⁿ podzbiorów

Krok 1. Sprawdzenie dla n = 0 (baza). Zbiór pusty ma jeden podzbiór - samego siebie, a $2^0 = 1$. (Dla kontroli: zbiór $\{a\}$ ma podzbiory $\varnothing$ i $\{a\}$ - to $2 = 2^1$.)

Krok 2. Założenie i teza. Zakładamy, że każdy zbiór $k$-elementowy ($k \ge 0$) ma $2^k$ podzbiorów. Teza: każdy zbiór $(k + 1)$-elementowy ma $2^{k + 1}$ podzbiorów.

Krok 3. Dowód kroku. Niech $A$ będzie zbiorem $(k + 1)$-elementowym. Wybierzmy w nim jeden element $x$ i oznaczmy $B = A \setminus \{x\}$ - to zbiór $k$-elementowy. Podzbiory zbioru $A$ dzielą się na dwie rozłączne grupy:

• podzbiory bez $x$ - to dokładnie podzbiory zbioru $B$; z założenia jest ich $2^k$,
• podzbiory z $x$ - każdy z nich to $C \cup \{x\}$ dla jednego podzbioru $C$ zbioru $B$, więc też jest ich $2^k$.

Razem:

$2^k + 2^k = 2 \cdot 2^k = 2^{k + 1}.$

To jest teza.

Odpowiedź. Na mocy zasady indukcji matematycznej zbiór $n$-elementowy ma $2^n$ podzbiorów dla każdego $n \ge 0$ - np. zbiór $\{1, 2, 3\}$ ma ich $8$. Więcej o liczeniu podzbiorów: kombinatoryka.