Two ways of building new sets come up constantly in counting and in the study of relations. Both start from the set operations you know, and both have sizes you can find without listing.
Key idea
The power set $\mathcal{P}(A)$ is the set of all subsets of $A$; if $|A| = n$, then $|\mathcal{P}(A)| = 2^{n}$. The Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ with $a \in A$ and $b \in B$; $|A \times B| = |A| \cdot |B|$.
Why it works
To build a subset of $A$, go through the elements one at a time and decide "in" or "out." That is $n$ independent two-way choices, so $2^{n}$ subsets, and the choices "all out" and "all in" give $\varnothing$ and $A$ itself. To build a pair, choose the first entry ($|A|$ ways) and then the second ($|B|$ ways). Order matters in a pair: $(1, 2) \ne (2, 1)$, while $\{1, 2\} = \{2, 1\}$. That is the whole point of a pair: it records which entry came first.
Worked examples
Worked example: Listing a power set
List $\mathcal{P}(\{a, b, c\})$.
- Size $0$: $\varnothing$. Size $1$: $\{a\}, \{b\}, \{c\}$.
- Size $2$: $\{a, b\}, \{a, c\}, \{b, c\}$. Size $3$: $\{a, b, c\}$.
- That is $1 + 3 + 3 + 1 = 8 = 2^{3}$ subsets, as promised.
Answer: $\varnothing, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}$
Worked example: Products in both orders
Let $A = \{1, 2\}$ and $B = \{x, y, z\}$. List $A \times B$. Is $A \times B = B \times A$?
- $$A \times B = \{(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)\},$$ which has $2 \cdot 3 = 6$ pairs.
- $B \times A$ contains $(x, 1)$, whose first entry comes from $B$. That pair is not in $A \times B$.
- So $A \times B \ne B \times A$, even though both have $6$ elements.
Answer: $6$ pairs; no
Worked example: Counting subsets with a condition
How many subsets of $\{1, 2, 3, 4, 5, 6\}$ contain $1$ but not $2$?
- The decisions for $1$ and $2$ are forced: $1$ in, $2$ out.
- The other $4$ elements are free: $2^{4} = 16$ subsets.
Answer: $16$
Common mistake
Leaving out $\varnothing$ and the whole set, or treating a pair as a set. A list of the subsets of $\{a, b\}$ that has only $\{a\}$ and $\{b\}$ is missing two: $\varnothing$ and $\{a, b\}$. And $(a, b)$ is not $\{a, b\}$: the pair $(3, 3)$ is fine, but the set $\{3, 3\}$ is just $\{3\}$. Check: your count of subsets must be $2^{n}$, and your count of pairs $|A| \cdot |B|$.