title: "Power Set"

Power Set

Definition. The power set $\mathcal{P}(A)$ of a set $A$ is the set of all subsets of $A$.

A set with $n$ elements has exactly $2^n$ subsets (Lecture 2, Example 9), and $\mathcal{P}(\mathbb{Z}^+)$ is uncountable (Lecture 2, Exercise 7). The exponent returns in the subset construction of Lecture 3, which builds one state per subset.