Proof of the number of subsets of a finite set by indicator functions

Proof

We build a bijection from the power set to a set of functions.

1. Let $F = \set{0, 1}^X$ be the set of all functions from $X$ to $\set{0, 1}$.
2. Define $\Phi : \mathcal{P}(X) \to F$ by $\Phi(S) = 1_S$, the indicator function of $S$. So $1_S(x) = 1$ for $x \in S$ and $1_S(x) = 0$ for $x \in X \setminus S$.
3. Define $\Psi : F \to \mathcal{P}(X)$ by $\Psi(\varphi) = \set{x \in X : \varphi(x) = 1}$.
4. For $S \subseteq X$, the set $\Psi(\Phi(S))$ is the set of $x$ with $1_S(x) = 1$. This is $S$.
5. For $\varphi \in F$, let $T = \Psi(\varphi)$. Then $1_T(x) = 1 = \varphi(x)$ for $x \in T$.
6. For $x \notin T$ we have $\varphi(x) \ne 1$. Since $\varphi$ takes values in $\set{0, 1}$, this gives $\varphi(x) = 0 = 1_T(x)$. So $\Phi(\Psi(\varphi)) = \varphi$.
7. Thus $\Phi$ has a two-sided inverse, so it is a bijection by the inverse criterion.
8. By the number of functions between finite sets, $F$ is finite and $|F| = 2^n$.
9. A numbering of $F$ composed with $\Psi$ numbers $\mathcal{P}(X)$. So $\mathcal{P}(X)$ is finite, and the bijection principle gives $|\mathcal{P}(X)| = |F| = 2^n$.