More Operations on Sets

Two sets are easy; an infinite family of sets is where set theory earns its keep. Once you allow more than two sets at a time, the basic operations from §1.4 need to scale: indexed union generalizes $\cup$ to arbitrarily many sets, and indexed intersection generalizes $\cap$. Two further constructions — the power set, which collects every subset of a set into one giant new set, and the Cartesian product, which builds the set of ordered pairs — will be the foundation for relations (Chapter 4) and functions (Chapter 5). All four constructions are essentially shorthand for quantified statements you already know, which is why this section sits right after the quantifier negation rules.

Indexed unions and intersections

An indexed family of sets is a collection ${A_i}_{i \in I}$, where $I$ is some index set (often $\mathbb{N}$ or a finite list). The indexed union and indexed intersection are:

The union collects everything that lies in at least one $A_i$; the intersection keeps only what lies in every $A_i$. The quantifier $\exists$ powers the union; the quantifier $\forall$ powers the intersection. This is the deep reason the two are duals: De Morgan for quantifiers gives De Morgan for indexed sets.

For example, if $A_n = {1, 2, \ldots, n}$ for $n = 1, 2, 3$:

$\bigcup_{n=1}^{3} A_n = {1, 2, 3}$ (the largest $A_n$) and $\bigcap_{n=1}^{3} A_n = {1}$ (the smallest $A_n$).

The power set

The power set of $A$, written $\mathcal{P}(A)$ (also $2^A$), is the set of all subsets of $A$:

If $A$ has $n$ elements, $\mathcal{P}(A)$ has $2^n$ elements — one for each choice of "include or exclude" per element. For $A = {1, 2}$:

Notice the empty set $\emptyset$ is always a member of $\mathcal{P}(A)$ (the empty set is a subset of everything), and $A$ itself is always a member of $\mathcal{P}(A)$ (every set is a subset of itself).

Cartesian products

The Cartesian product of $A$ and $B$ is the set of ordered pairs

If $|A| = m$ and $|B| = n$, then $|A \times B| = mn$. The order in a pair matters: $(a, b) \neq (b, a)$ in general. Cartesian products are how we model planes ($\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$), strings ($\Sigma^*$), database joins (one row from each table), and — coming up in Chapter 4 — relations between sets.

Pause and think: Is ${1}$ an element of $\mathcal{P}({1, 2})$? Is $1$ an element of $\mathcal{P}({1, 2})$? What is the difference between $x \in \mathcal{P}(A)$ and $x \subseteq A$? (Hint: members of $\mathcal{P}(A)$ are SETS; the number $1$ is not a set.)

Try it

• Before listing: predict the size of $\mathcal{P}({a, b, c})$. Then list every element to verify your count of $2^3 = 8$.
• Predict first: which is bigger, $\bigcup_{i=1}^{3} {i}$ or $\bigcap_{i=1}^{3} {i}$? Compute both and explain.
• Let $A_n = [0, 1/n]$ for $n = 1, 2, 3, \ldots$. Predict $\bigcap_{n=1}^{\infty} A_n$ before computing. (Hint: $0$ is in every $A_n$; is any positive number in every $A_n$?)
• Compute ${0, 1} \times {0, 1} \times {0, 1}$ and count its elements. (You should see all binary strings of length $3$.)
• Is $\emptyset \in \mathcal{P}(A)$ for every set $A$? Is $A \in \mathcal{P}(A)$? Justify by recalling that elements of $\mathcal{P}(A)$ are exactly the subsets of $A$.

A trap to watch for

The single most common mistake is confusing membership with subsethood when working with $\mathcal{P}(A)$. For $A = {1, 2}$: ${1}$ is an element of $\mathcal{P}(A)$ because ${1}$ is a subset of $A$; but $1$ is not an element of $\mathcal{P}(A)$, because $1$ is not a set. The general rule: $x \in \mathcal{P}(A) \Leftrightarrow x \subseteq A$. Element-of $\mathcal{P}(A)$ means subset-of $A$. Spending sixty seconds with this rule now saves hours of confusion later when you start building relations on power sets and seeing nested set notation.

What you now know

You can build indexed unions and intersections, list power sets, and compute Cartesian products. Chapter 2 is now complete — you have a working vocabulary of propositional and predicate logic, plus the set-theoretic operations they describe. Chapter 3 leverages all of this into the art of writing proofs: direct, by contradiction, by contrapositive, and proofs that maneuver through quantifiers.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, ch. 2.
• Halmos, P. R. (1960). Naive Set Theory. Van Nostrand, §§6–7.
• Enderton, H. B. (1977). Elements of Set Theory. Academic Press, ch. 3.
• Kunen, K. (2009). The Foundations of Mathematics. College Publications, ch. 1.