Power Set of a Finite Set and Its Cardinality

Given a set $A$, the power set of $A$ — written $P(A)$ — is the set of all possible subsets of $A$, including $A$ itself and the empty set $\emptyset$. In symbols,

For example, if $A = \{p, q\}$, every possible subset of $A$ is: $\emptyset$, $\{p\}$, $\{q\}$, and $\{p, q\}$ itself — so

Notice two things that are true of every power set: $\emptyset \in P(A)$ always (this is exactly the theorem from the previous section, now put to direct use — the empty set is a subset of $A$, so it belongs to the collection of all subsets of $A$), and $A \in P(A)$ always (every set is a subset of itself).

How many subsets does a finite set have? For a set $A$ with $n(A) = n$ elements, each subset is formed by making an independent "include or exclude" decision for every one of the $n$ elements — 2 choices per element, made $n$ times, giving $2 \times 2 \times \cdots \times 2$ ($n$ times) subsets in total. This gives the key counting result for this chapter: