[proofplan]
Choose an enumeration of the finite [set](/page/Set) $A$ and encode each subset by its indicator values along that enumeration. This gives a bijection from $\mathcal{P}(A)$ to the set of binary strings indexed by the enumeration. We then count those binary strings by choosing one of two values independently at each of the $n$ positions.
[/proofplan]
[step:Choose an enumeration of the finite set $A$]
For each integer $n \geq 0$, define the index set $I_n := \{k \in \mathbb{Z} : 1 \leq k \leq n\}$, so $I_0 = \varnothing$. Since $A$ is finite and $|A| = n$, there exists a bijection
\begin{align*}
e: I_n &\to A.
\end{align*}
This bijection is an enumeration of the elements of $A$.
[/step]
[step:Encode each subset of $A$ by a binary string]
Define the encoding map
\begin{align*}
\Phi: \mathcal{P}(A) &\to \{0,1\}^{I_n} \\
S &\mapsto b_S,
\end{align*}
where $b_S: I_n \to \{0,1\}$ is the [function](/page/Function) defined by
\begin{align*}
b_S(k) =
\begin{cases}
1, & e(k) \in S, \\
0, & e(k) \notin S.
\end{cases}
\end{align*}
Thus $\Phi(S)$ records, for each position $k \in I_n$, whether the enumerated element $e(k)$ belongs to $S$.
[guided]
We want to compare subsets of $A$ with binary choices. The enumeration $e: I_n \to A$ lets us inspect the elements of $A$ in the indexed order $e(1), \dots, e(n)$. For a subset $S \subset A$, define a function $b_S: I_n \to \{0,1\}$ by
\begin{align*}
b_S(k) =
\begin{cases}
1, & e(k) \in S, \\
0, & e(k) \notin S.
\end{cases}
\end{align*}
This function is well-defined because for each $k \in I_n$, the element $e(k)$ lies in $A$, and since $S$ is a subset of $A$, exactly one of the two alternatives $e(k) \in S$ or $e(k) \notin S$ holds. Therefore the rule
\begin{align*}
\Phi: \mathcal{P}(A) &\to \{0,1\}^{I_n} \\
S &\mapsto b_S
\end{align*}
defines a function from the power set of $A$ to the set of all functions from $I_n$ to $\{0,1\}$.
[/guided]
[/step]
[step:Prove that the encoding map is injective]
Let $S,T \in \mathcal{P}(A)$ and assume $\Phi(S) = \Phi(T)$. Then $b_S(k) = b_T(k)$ for every $k \in I_n$. For any $a \in A$, surjectivity of $e$ gives some $k \in I_n$ with $e(k) = a$. Hence
\begin{align*}
a \in S \iff b_S(k) = 1 \iff b_T(k) = 1 \iff a \in T.
\end{align*}
Thus $S = T$, so $\Phi$ is injective.
[guided]
To prove injectivity, we must show that two subsets with the same binary encoding are the same subset. Let $S,T \in \mathcal{P}(A)$ and assume $\Phi(S) = \Phi(T)$. By definition of equality in $\{0,1\}^{I_n}$, this means
\begin{align*}
b_S(k) = b_T(k)
\end{align*}
for every $k \in I_n$.
Now take an arbitrary element $a \in A$. Since $e: I_n \to A$ is surjective, there exists $k \in I_n$ such that $e(k) = a$. The definition of $b_S$ gives $a \in S \iff b_S(k) = 1$, and the definition of $b_T$ gives $b_T(k) = 1 \iff a \in T$. Since $b_S(k) = b_T(k)$, we obtain
\begin{align*}
a \in S \iff b_S(k) = 1 \iff b_T(k) = 1 \iff a \in T.
\end{align*}
Because this equivalence holds for every $a \in A$, the subsets $S$ and $T$ have exactly the same elements. Therefore $S = T$, and $\Phi$ is injective.
[/guided]
[/step]
[step:Prove that the encoding map is surjective]
Let $b \in \{0,1\}^{I_n}$. Define
\begin{align*}
S_b := \{e(k) \in A : k \in I_n \text{ and } b(k) = 1\}.
\end{align*}
Then $S_b \subset A$, so $S_b \in \mathcal{P}(A)$. For each $k \in I_n$, the definition of $S_b$ gives
\begin{align*}
e(k) \in S_b \iff b(k) = 1.
\end{align*}
Therefore $b_{S_b}(k) = b(k)$ for every $k \in I_n$, so $\Phi(S_b) = b$. Hence $\Phi$ is surjective.
[/step]
[step:Count the binary strings and transfer the count through the bijection]
The set $\{0,1\}^{I_n}$ consists of all functions from the $n$-element set $I_n$ to the $2$-element set $\{0,1\}$. By the multiplication principle,
\begin{align*}
|\{0,1\}^{I_n}| = 2^n.
\end{align*}
Since $\Phi: \mathcal{P}(A) \to \{0,1\}^{I_n}$ is both injective and surjective, it is a bijection. Bijections preserve cardinality of finite sets, so
\begin{align*}
|\mathcal{P}(A)| = |\{0,1\}^{I_n}| = 2^n.
\end{align*}
This proves that a finite set of size $n$ has exactly $2^n$ subsets.
[/step]
