One-to-one correspondence between subsets

Statement

Let $A = \{a, b, c, d, e\}$. Set $B = \{X \mid X \subseteq A \text{ and } e \notin X\}$ and $C = \{X \mid X \subseteq A \text{ and } e \in X\}$. Show that there is a one-to-one correspondence between $B$ and $C$, then generalize to a set with $n+1$ elements.

Solution

Define $\varphi : B \to C$ by $\varphi(X) = X \cup \{e\}.$ It is well defined: if $X \subseteq A$ and $e \notin X$, then $X \cup \{e\} \subseteq A$ and contains $e$, so it belongs to $C$.

It is a bijection, with inverse $\psi : C \to B$ given by $\psi(Y) = Y \setminus \{e\}$:

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

Hence $B$ and $C$ have the same number of elements.

Generalization: for a set with $n+1$ elements, “adding the distinguished element $e$” puts the subsets not containing $e$ in one-to-one correspondence with those containing it. Each family has $2^n$ elements, and together they give the $2^{n+1}$ total subsets. $\blacksquare$