Power set and universal set

We now meet two ideas that elevate set theory from a notation to a structure. The power set lets us treat the subsets of a set as elements of a new set. The universal set gives a fixed background against which complements and Venn diagrams make sense.

Definitions

Let $A$ be a set. The power set of $A$, written $P(A)$ (or $\mathcal{P}(A)$, or sometimes $2^A$), is the set whose elements are all subsets of $A$: $P(A) = \{S : S \subseteq A\}.$

A universal set, usually denoted $U$, is a set chosen for a discussion so that every set under consideration is a subset of $U$.

Power set examples

• If $A = \varnothing$, then $P(A) = \{\varnothing\}$. One element: the empty subset.
• If $A = \{a\}$, then $P(A) = \{\varnothing, \{a\}\}$. Two elements.
• If $A = \{a, b\}$, then $P(A) = \{\varnothing, \{a\}, \{b\}, \{a, b\}\}$. Four elements.
• If $A = \{1, 2, 3\}$, then $P(A)$ has $\varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}$. Eight elements.

The pattern is unmistakable: a set with $n$ elements has $2^n$ subsets.

Theorem: $|P(A)| = 2^{|A|}$

Claim. If $A$ is a finite set with $|A| = n$, then $|P(A)| = 2^n$.

Proof (counting argument). A subset $S$ of $A$ is determined by deciding, for each of the $n$ elements of $A$, whether or not it belongs to $S$. Each element has $2$ independent choices: in or out. By the multiplication principle, the total number of subsets is $\underbrace{2 \times 2 \times \cdots \times 2}_{n\text{ times}} = 2^n. \qed$

Alternative proof (induction). Base case $n = 0$: $A = \varnothing$, $|P(\varnothing)| = 1 = 2^0$. Inductive step: assume $|P(A)| = 2^n$ for every $n$-element set. Take an $(n+1)$-element set $A \cup \{x\}$ where $x \notin A$. Every subset of $A \cup \{x\}$ either omits $x$ (and is a subset of $A$) or contains $x$ (and is $S \cup \{x\}$ for some subset $S \subseteq A$). These two families are disjoint and each has $|P(A)| = 2^n$ elements. So $|P(A \cup \{x\})| = 2 \cdot 2^n = 2^{n+1}$.

This is your first encounter with exponential growth in this course: doubling the size of $A$ does not double the size of $P(A)$ , it squares it.

Universal set

In any problem we usually have a "world" of objects in mind. The set of all such objects for the problem is called the universal set. For example:

• For divisibility problems: $U = \mathbb{Z}$ or $U = \mathbb{N}$.
• For trigonometric problems: $U = \mathbb{R}$.
• For class-attendance data: $U =$ all students in the class.

The choice of $U$ depends on context. Once $U$ is fixed, every set in the discussion is a subset of $U$, and the complement of a set (next subtopic) becomes meaningful.

Why these matter

Power sets appear whenever we want to count subsets: in probability, an event is a subset of the sample space, so events are elements of $P(S)$ where $S$ is the sample space; in combinatorics, choosing a committee is choosing a subset, and so on.

The universal set is what makes the diagram of a set finite to draw. Without specifying $U$, the complement of $\{1, 2, 3\}$ is hopelessly ambiguous: complement in $\mathbb{N}$? in $\mathbb{Z}$? in $\mathbb{R}$? The universal set settles the question.

Worked examples

Example 1. List $P(\{x, y, z\})$.

Eight subsets: $\varnothing,\ \{x\},\ \{y\},\ \{z\},\ \{x, y\},\ \{x, z\},\ \{y, z\},\ \{x, y, z\}$.

Example 2. If $|A| = 5$, how many subsets does $A$ have? How many of them have exactly $3$ elements?

Total subsets: $2^5 = 32$. Subsets of size $3$: $\binom{5}{3} = 10$ (revisited in Chapter 6).

Example 3. If $|P(A)| = 32$, find $|A|$.

$2^n = 32 \Rightarrow n = 5$. So $|A| = 5$.

Example 4. Take $U = \{1, 2, \dots, 10\}$, $A = \{2, 4, 6, 8, 10\}$. List the smallest universal set in which both $A$ and $B = \{3, 6, 9\}$ are subsets, and verify that $U$ suffices.

$A \cup B = \{2, 3, 4, 6, 8, 9, 10\}$. The smallest such universal set is $A \cup B$ itself. But the given $U = \{1, \dots, 10\}$ also contains all of these, so $U$ suffices.

Example 5 (harder). Prove: if $A \subseteq B$, then $P(A) \subseteq P(B)$.

Let $S \in P(A)$. Then $S \subseteq A$. By transitivity (since $A \subseteq B$), $S \subseteq B$, so $S \in P(B)$. Hence $P(A) \subseteq P(B)$.

Try it yourself

1. List all elements of $P(\{1, 2\})$.
2. How many subsets does a set with $8$ elements have?
3. If $P(A)$ has $128$ elements, find $|A|$.
4. Write all subsets of $\{a, b, c, d\}$ that have exactly two elements.
5. If $A = \{1, 2, \{3, 4\}\}$, find $|A|$ and $|P(A)|$.
6. Is $\{1, 2\} \in P(\{1, 2, 3\})$? Is $\{1, 2\} \subseteq P(\{1, 2, 3\})$?
7. Show that $P(\varnothing) = \{\varnothing\}$ and $P(\{\varnothing\}) = \{\varnothing, \{\varnothing\}\}$.
8. Choose a sensible universal set for: (a) "the set of vowels"; (b) "rational solutions of a quadratic"; (c) "students who play football".
9. Prove or disprove: $P(A \cap B) = P(A) \cap P(B)$.
10. Prove or disprove: $P(A \cup B) = P(A) \cup P(B)$.
11. If $|A| = n$, how many subsets of $A$ have an even number of elements? (Hint: split by including/excluding a fixed element.)
12. Why is "$U =$ the set of all sets" not a legal universal set? (Hint: it leads to Russell's paradox; this is taken on faith for now.)

Pitfalls / Tricks

• $\varnothing \in P(A)$ and $A \in P(A)$ for every set $A$. Both the empty subset and $A$ itself are subsets of $A$.
• $\{1\} \in P(\{1, 2\})$ (true) is not the same as $1 \in P(\{1, 2\})$ (false , $1$ is not a subset of $\{1, 2\}$).
• The universal set is a choice. The same set $A$ may have very different complements in different universes.
• Insight. The map $A \mapsto P(A)$ takes $n$ to $2^n$. It is the prototype of exponential blow-up , and the reason why brute-force search over subsets becomes infeasible quickly.