Corrispondenza biunivoca tra sottoinsiemi

Testo

Sia $A = \{a, b, c, d, e\}$. Poni $B = \{X \mid X \subseteq A \text{ e } e \notin X\}$ e $C = \{X \mid X \subseteq A \text{ e } e \in X\}$. Mostra che esiste una corrispondenza biunivoca tra $B$ e $C$, poi generalizza a un insieme di $n+1$ elementi.

Soluzione

Definiamo $\varphi : B \to C$ ponendo $\varphi(X) = X \cup \{e\}.$ È ben definita: se $X \subseteq A$ e $e \notin X$, allora $X \cup \{e\} \subseteq A$ e contiene $e$, quindi appartiene a $C$.

È una biiezione, con inversa $\psi : C \to B$ data da $\psi(Y) = Y \setminus \{e\}$:

• $\psi(\varphi(X)) = (X \cup \{e\}) \setminus \{e\} = X$ (perché $e \notin X$);
• $\varphi(\psi(Y)) = (Y \setminus \{e\}) \cup \{e\} = Y$ (perché $e \in Y$).

Quindi $B$ e $C$ hanno lo stesso numero di elementi.

Generalizzazione: per un insieme con $n+1$ elementi, “aggiungere l’elemento distinto $e$” mette in corrispondenza biunivoca i sottoinsiemi che non contengono $e$ con quelli che lo contengono. Ciascuna delle due famiglie ha $2^n$ elementi, e insieme danno i $2^{n+1}$ sottoinsiemi totali. $\blacksquare$

Collegamenti

Argomenti: Funzioni proprieta
Concetti: Funzione biiettiva · Insieme delle parti
Competenze: Dimostrare
Tipo di esercizio: Dimostrazione