Chapter 8: Sets

"A set is a Many that allows itself to be thought of as a One." — Georg Cantor

Overview

Open almost any program you have written and you will find sets hiding in it, usually under another name. The collection of usernames already taken. The distinct words in a document. The tags on a post, where duplicates make no sense and order does not matter. The set of pages a web crawler has already visited, so it does not visit them twice. Every one of these is a set — an unordered collection of distinct things — and the moment you name the concept, a whole vocabulary and a whole algebra come with it for free.

Here is the practical problem sets solve. Suppose you have a list of ten million email addresses with an unknown number of duplicates, and you need three things: the distinct addresses, a way to ask "is alice@example.com in here?" in essentially constant time, and the addresses that appear in this list but not in your unsubscribe list. With a plain list, the first costs a nested scan, the second is a linear search, and the third is a double loop — all painfully slow. With the right data type, all three are one line each and run in near-linear total time. That data type is the set, and it is a direct implementation of the mathematics in this chapter.

Sets are also the foundation the rest of this book is built on. A relation (Chapter 12) is a set of pairs. A function (Chapter 9) is a special kind of relation. A graph (Chapter 27) is a set of vertices together with a set of edges. A probability event, later in the book, is a subset of a sample space. When we prove things about any of those later, we will be doing set algebra. Learn it cleanly now and the later chapters become much easier.

In this chapter you will learn to:

• Write collections precisely using roster and set-builder notation, and test membership.
• Decide and prove subset, proper-subset, and equality relationships between sets.
• Build the power set of a set and the Cartesian product of two sets, and count both.
• Combine sets with union, intersection, difference, and complement, and picture the result with a Venn diagram.
• Prove set identities two ways — by chasing a single element through the definitions, and by translating to the logic of Chapter 1.
• Reach for Python's set and frozenset deliberately, knowing exactly what mathematical guarantee each one gives you.

Learning Paths

🏃 Fast Track: If sets are review, skim 8.1–8.4 for the notation and Python conventions this book uses, then study 8.5 carefully — proving set identities by the element method is the genuinely new skill and it pays off in every later chapter. Do the ⭐⭐ and ⭐⭐⭐ exercises.

📖 Standard Path: Read in order. Work every 🔄 Check Your Understanding before continuing, and attempt the set-identity proofs in 8.5 yourself before reading ours. This is the chapter where the proof skills of Part I meet the structures of Part II.

🔬 Deep Dive: After the chapter, look up Russell's paradox (why "the set of all sets that do not contain themselves" is incoherent) and read how the axioms of set theory respond to it. Then prove the general formula $\lvert \mathcal{P}(S) \rvert = 2^{\lvert S \rvert}$ by induction — it is a clean application of Chapter 6.

8.1 Sets and membership

Start with the most concrete thing imaginable: a guest list. You are throwing a party, and you write down who is invited — Ana, Ben, Chen. That list of names, considered as a single collection, is a set. Two features of it are worth noticing immediately, because they are exactly what distinguishes a set from a list in code.

First, duplicates do not count. If you accidentally write "Ana" twice, Ana is still just one guest. The collection $\{\text{Ana}, \text{Ben}, \text{Ana}\}$ is the same collection as $\{\text{Ana}, \text{Ben}\}$. Second, order does not matter. "Ana, Ben, Chen" and "Chen, Ana, Ben" are the same guest list. A set is defined entirely by which things are in it, nothing more.

💡 Intuition: A set answers exactly one kind of question about each thing in the universe: "are you in, or out?" It does not record how many times you are in (you are simply in), and it does not record where you sit (there is no order). If you have ever called list(set(items)) to remove duplicates, you have used precisely this "in or out, once" behavior.

Now the definitions.

A set is an unordered collection of distinct objects. The objects in a set are called its elements (or members). We write sets with curly braces, listing the elements — this is called roster notation: $$A = \{1, 2, 3, 4\}.$$

To say that an object $x$ is an element of a set $A$, we write $x \in A$ (read "$x$ is in $A$" or "$x$ is a member of $A$"). To say it is not, we write $x \notin A$. For the set above, $2 \in A$ but $7 \notin A$. The symbol $\in$ is the membership relation, and it is the single most fundamental relation in all of mathematics: virtually every other idea in this book is built on top of it.

Some sets are too large or too patterned to list. For those we use set-builder notation, which describes a set by a property its elements satisfy: $$E = \{ x \mid x \text{ is an even integer} \}.$$ Read the vertical bar as "such that": "$E$ is the set of all $x$ such that $x$ is an even integer." Often we restrict the variable to a known set first, which is cleaner: $$E = \{ x \in \mathbb{Z} \mid x \text{ is even} \}, \qquad S = \{ n^2 \mid n \in \mathbb{N} \}.$$ The second reads "the set of $n^2$ as $n$ ranges over the naturals" — that is, ${0, 1, 4, 9, 16, \dots}$.

🔗 Connection. Set-builder notation is exactly a predicate from Chapter 2 used as a filter. The set $\{x \mid P(x)\}$ collects precisely the objects that make the predicate $P(x)$ true. In Python this is not an analogy but a literal feature: the set comprehension {x for x in domain if P(x)} builds the same set, with P(x) as the if clause. Quantifiers, predicates, and sets are three views of one idea.

We will use several standard sets so often that they get permanent names (these are the number systems from Chapter 2's examples):

One special set deserves immediate attention: the set with no elements at all. The empty set is written $\emptyset$ or $\{\}$. It is not "nothing" — it is a perfectly good set that happens to contain nothing, the way an empty box is still a box. The empty set turns up constantly (the set of solutions to $x^2 = -1$ over the reals; the set of users currently online at 3 a.m.), and getting comfortable with it now prevents a lot of confusion later.

⚠️ Common Pitfall: $\emptyset$, $\{\emptyset\}$, and $\{0\}$ are three different sets. $\emptyset$ is empty: it has zero elements. $\{\emptyset\}$ has one element, and that element is itself the empty set (think of a box containing one empty box). $\{0\}$ has one element, the number zero. Confusing "the empty set" with "a set containing the empty set" is one of the most common beginner errors, and it matters enormously when we build power sets in 8.2.

The number of elements in a finite set $S$ is its cardinality, written $\lvert S \rvert$. For $A = {1, 2, 3, 4}$ we have $\lvert A \rvert = 4$; and $\lvert \emptyset \rvert = 0$. Cardinality counts distinct elements, so $\lvert \{1, 1, 2\} \rvert = 2$ — the repeated $1$ is counted once, because a set has no repeats in the first place. (The cardinality of infinite sets is a subtler and genuinely surprising story — some infinities turn out to be bigger than others — which we postpone to a later chapter where it becomes a threshold idea.)

Let's see all of this in Python, where the correspondence is unusually faithful.

A = {1, 2, 3, 4}          # roster notation, almost verbatim
evens = {x for x in range(10) if x % 2 == 0}   # set-builder / comprehension
print(2 in A, 7 in A)     # the membership relation x in A
print(len(A))             # cardinality |A|
print({1, 1, 2})          # duplicates collapse automatically
# Expected output:
# True False
# 4
# {1, 2}

Notice that {1, 1, 2} printed as {1, 2}: Python enforces the "distinct" rule for you, exactly as the mathematics demands. (The output order is not guaranteed to be sorted — Python sets are unordered, faithful to the "order does not matter" rule. We will return to this in 8.6.)

🔄 Check Your Understanding 1. Write the set of perfect squares strictly between 1 and 30 in roster notation, then in set-builder notation. 2. What is $\lvert \{ \emptyset, \{\emptyset\}, \{1,2,3\} \} \rvert$? 3. True or false: $\{1, 2, 3\} = \{3, 2, 1, 1, 2\}$. Justify in one sentence.

Answers

1. Roster: $\{4, 9, 16, 25\}$. Set-builder: $\{ n^2 \mid n \in \mathbb{Z},\ 1 < n^2 < 30 \}$ (or equivalently $\{ n^2 \mid n \in \{2,3,4,5\} \}$). 2. Three — its elements are the empty set, the set containing the empty set, and the set $\{1,2,3\}$; these are three distinct objects, so cardinality is 3 (the fact that one element is itself a 3-element set is irrelevant to the outer count). 3. True — both describe the same collection $\{1,2,3\}$; order and repetition do not affect a set's identity.

8.2 Subsets, equality, and power sets

Two collections rarely live in isolation; we want to compare them. The most basic comparison is containment. Consider the set of all employees, and within it the set of all managers. Every manager is an employee, but not conversely. We say managers are a subset of employees.

A set $A$ is a subset of a set $B$, written $A \subseteq B$, if every element of $A$ is also an element of $B$. Formally — and notice this is just a universally quantified implication, straight from Chapter 2 — $$A \subseteq B \quad \text{means} \quad \forall x\, (x \in A \rightarrow x \in B).$$ If additionally $A \ne B$ (that is, $B$ has at least one element that $A$ lacks), we call $A$ a proper subset and write $A \subset B$. So $\{1,2\} \subseteq \{1,2,3\}$ and in fact ${1,2} \subset {1,2,3}$, while ${1,2,3} \subseteq {1,2,3}$ is true but ${1,2,3} \subset {1,2,3}$ is false.

💡 Intuition: "$A \subseteq B$" is a promise: pick any element of $A$ you like, and I guarantee it is also in $B$. To verify the promise you check an arbitrary element; to break it you need just one element of $A$ that is missing from $B$ — a counterexample, exactly the disproof move from Chapter 2.

Two facts about subsets surprise people the first time, and both follow directly from the definition being a universal implication:

Theorem (the empty set is a subset of everything). For every set $B$, $\emptyset \subseteq B$.

The strategy first. We must show $\forall x\, (x \in \emptyset \rightarrow x \in B)$. The hypothesis "$x \in \emptyset$" is never true, so the implication is vacuously true for every $x$ — there is no $x$ that could falsify it. This is the vacuous proof from Chapter 4 in its most useful form.

Proof. Let $x$ be arbitrary. The statement $x \in \emptyset$ is false (the empty set has no elements), so the implication $x \in \emptyset \rightarrow x \in B$ is true regardless of $B$ (a conditional with a false hypothesis is true). Since $x$ was arbitrary, $\forall x\,(x \in \emptyset \rightarrow x \in B)$ holds, which is exactly $\emptyset \subseteq B$. $\blacksquare$

Theorem (every set contains itself). For every set $A$, $A \subseteq A$.

Proof. For arbitrary $x$, the implication $x \in A \rightarrow x \in A$ is true (anything implies itself). Hence $A \subseteq A$. $\blacksquare$

Now we can say precisely what it means for two sets to be the same. We have been using "$=$" informally; here is the definition the rest of the book relies on.

Two sets $A$ and $B$ are equal, written $A = B$, if they have exactly the same elements. The single most important consequence is the way we prove equality: $$A = B \quad \text{if and only if} \quad A \subseteq B \text{ and } B \subseteq A.$$ This is called proving equality by mutual inclusion (or "double containment"), and it is the workhorse of 8.5. It mirrors a fact you already know from logic: $p \leftrightarrow q$ is equivalent to $(p \rightarrow q) \land (q \rightarrow p)$. To prove two sets equal, prove each is a subset of the other.

🔗 Connection. Set equality is extensional: a set is determined solely by what is in it, not by how it is described. The sets $\{x \in \mathbb{Z} \mid x^2 = 4\}$ and $\{-2, 2\}$ are equal even though one is a property and the other a list. This is the same principle as "two functions are equal if they agree on every input" (Chapter 9) — identity by behavior, not by name.

The power set

Here is a question that sounds abstract but is the heart of counting subsets, search spaces, and feature combinations: given a set, how many subsets does it have, and what are they? Collecting them all gives a new set — a set whose elements are themselves sets.

The power set of a set $S$, written $\mathcal{P}(S)$, is the set of all subsets of $S$: $$\mathcal{P}(S) = \{ A \mid A \subseteq S \}.$$ For example, with $S = \{a, b\}$: $$\mathcal{P}(\{a, b\}) = \big\{\ \emptyset,\ \{a\},\ \{b\},\ \{a, b\}\ \big\}.$$ Two subsets are easy to forget: the empty set $\emptyset$ (a subset of everything, by the theorem above) and the whole set $S$ itself (a subset of itself). Both always belong to $\mathcal{P}(S)$.

⚠️ Common Pitfall: The elements of a power set are sets, not the original elements. In $\mathcal{P}(\{a,b\})$, the object $a$ is not an element — but $\{a\}$ is. So $a \notin \mathcal{P}({a,b})$ while ${a} \in \mathcal{P}({a,b})$. Keeping the "level" straight (element vs. set-of-elements) is the whole game with power sets.

How big is a power set? Count for small cases: $\lvert \mathcal{P}(\emptyset) \rvert = 1$ (just $\emptyset$ itself), $\lvert \mathcal{P}(\{a\}) \rvert = 2$, $\lvert \mathcal{P}(\{a,b\}) \rvert = 4$, and you can check $\lvert \mathcal{P}(\{a,b,c\}) \rvert = 8$. The pattern is powers of two.

Theorem. If $\lvert S \rvert = n$, then $\lvert \mathcal{P}(S) \rvert = 2^n$.

The strategy first. We give the combinatorial argument, because it explains the "2" and previews Chapter 15. Building a subset of $S$ means making one independent yes/no decision per element: include it, or don't. With $n$ elements and 2 choices each, the product rule gives $2^n$ distinct subsets. (An induction proof is also clean — peel off one element, note that each subset either contains it or not, doubling the count each time — and you will write it in the exercises.)

Proof. A subset $A \subseteq S$ is completely determined by, for each element $x \in S$, the binary choice "$x \in A$?" There are $n$ elements, the choices are independent, and each has exactly 2 outcomes. By the product rule (developed in Chapter 15), the number of distinct subsets is $\underbrace{2 \cdot 2 \cdots 2}_{n} = 2^n$. Distinct choice-vectors give distinct subsets and every subset arises from one, so $\lvert \mathcal{P}(S) \rvert = 2^n$. $\blacksquare$

That binary correspondence — subset $\leftrightarrow$ bitstring of length $n$ — is not just a proof trick; it is how power sets are generated in code, as we will see in the Project Checkpoint.

🔄 Check Your Understanding 1. List all elements of $\mathcal{P}(\{1, 2, 3\})$. How many are there, and how many contain the element $2$? 2. Is $\emptyset \in \mathcal{P}(S)$ for every set $S$? Is $\emptyset \subseteq \mathcal{P}(S)$ for every set $S$? (Both are true — explain why each holds for a different reason.) 3. Explain in one sentence why $\lvert \mathcal{P}(S) \rvert = 2^{\lvert S \rvert}$ means a feature flag system with 20 independent flags has over a million configurations.

Answers

1. The eight subsets are $\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}$; there are $2^3 = 8$, and exactly half — four of them — contain $2$ (fix $2$ as "in," then freely choose the other two elements: $2^2 = 4$). 2. $\emptyset \in \mathcal{P}(S)$ because $\emptyset$ is a subset of $S$, and power-set elements are exactly the subsets. $\emptyset \subseteq \mathcal{P}(S)$ because the empty set is a subset of every set. The first is about membership, the second is the universal "empty set is a subset of anything" fact. 3. Each flag is an independent yes/no choice, so the configurations correspond to subsets of a 20-element set: $2^{20} = 1{,}048{,}576 > 10^6$.

8.3 Set operations and Venn diagrams

Sets become powerful when we combine them. Three or four operations do almost all the work, and each one corresponds — not by coincidence — to a logical connective from Chapter 1. That correspondence is the single most useful thing in this chapter, so we will make it explicit at every step.

Throughout, picture a universe $U$: the set of all objects currently under discussion (all integers, all users, all pixels — whatever the problem is about). Every set we talk about is a subset of $U$.

Union. The union of $A$ and $B$, written $A \cup B$, is the set of elements in $A$ or $B$ (or both): $$A \cup B = \{ x \mid x \in A \lor x \in B \}.$$ The "or" here is the inclusive or ($\lor$) from logic — an element in both sets is still in the union, counted once. Example: $\{1, 2, 3\} \cup \{3, 4\} = \{1, 2, 3, 4\}$.

Intersection. The intersection of $A$ and $B$, written $A \cap B$, is the set of elements in $A$ and $B$: $$A \cap B = \{ x \mid x \in A \land x \in B \}.$$ Example: $\{1, 2, 3\} \cap \{3, 4\} = \{3\}$. When $A \cap B = \emptyset$ — they share nothing — we say $A$ and $B$ are disjoint.

Difference. The difference $A \setminus B$ (read "$A$ minus $B$") is the set of elements in $A$ but not in $B$: $$A \setminus B = \{ x \mid x \in A \land x \notin B \}.$$ Example: $\{1, 2, 3\} \setminus \{3, 4\} = \{1, 2\}$. Note $A \setminus B$ and $B \setminus A$ are different in general; here $\{3,4\} \setminus \{1,2,3\} = \{4\}$. This is the operation behind "in my list but not on the unsubscribe list" from the overview.

Complement. The complement of $A$ (relative to the universe $U$), written $\overline{A}$, is everything in $U$ that is not in $A$: $$\overline{A} = \{ x \in U \mid x \notin A \} = U \setminus A.$$ Complement is just difference from the universe, and it corresponds to logical negation $\neg$. It only makes sense once a universe is fixed: the complement of "even numbers" is "odd numbers" if the universe is the integers, but something else entirely if the universe is all real numbers.

Here is the correspondence, all in one place. It is worth memorizing, because it lets you transfer every logical equivalence you proved in Chapter 1 into a set identity for free (we will exploit this in 8.5):

🚪 Threshold Concept. Set theory is logic with a universe attached. Every set operation is a logical connective applied to membership statements, and every set identity is a logical equivalence wearing different clothes. Once you see this, you stop memorizing set laws as a separate list: De Morgan's laws for sets ($\overline{A \cup B} = \overline{A} \cap \overline{B}$) are literally De Morgan's laws for logic ($\neg(p \lor q) \equiv \neg p \land \neg q$) with $p := (x \in A)$ and $q := (x \in B)$. This single insight collapses two chapters into one and is the reason Part I came before Part II.

Venn diagrams

A Venn diagram draws each set as a region (usually a circle) inside a rectangle representing the universe $U$; overlaps show shared elements. They are not proofs — a picture with two circles cannot, by itself, establish a fact about all sets — but they are an excellent way to see what an operation does and to guess an identity before proving it. Here is the standard two-set picture, with the four regions labeled by which of $A$, $B$ an element belongs to:

        U  (everything in the rectangle)
   +-----------------------------------+
   |        ___________                |
   |       /  A        \               |
   |      /     ___________            |
   |     |  1  / 2   \  3  |           |   region 1: in A only        = A \ B
   |     |     |  A∩B |    |           |   region 2: in A and B       = A ∩ B
   |      \     \_____/    /            |   region 3: in B only        = B \ A
   |       \___________   |  B         |   region 4: outside both     = complement of A∪B
   |              4        |           |
   |                       |__________/ |
   +-----------------------------------+

The whole shaded area of both circles is $A \cup B$ (regions 1, 2, 3); the lens in the middle is $A \cap B$ (region 2); the part of $A$ outside $B$ is $A \setminus B$ (region 1); and the corner outside both circles is $\overline{A \cup B}$ (region 4). Reading an identity off the diagram and then proving it is exactly the "compute to conjecture, prove to be sure" rhythm of theme four.

Let's compute every operation in Python and check the results against the definitions by hand.

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print(A | B)        # union:        in A or B
print(A & B)        # intersection: in A and B
print(A - B)        # difference:   in A but not B
print(A ^ B)        # symmetric difference: in exactly one
print(A.isdisjoint({7, 8}))   # share nothing?
# Expected output:
# {1, 2, 3, 4, 5, 6}
# {3, 4}
# {1, 2}
# {1, 2, 5, 6}
# True

Python uses the bitwise-looking operators |, &, -, ^ for union, intersection, difference, and symmetric difference respectively. Symmetric difference, $A \triangle B = (A \setminus B) \cup (B \setminus A)$, is "in exactly one of the two" — elements 3 and 4 are in both, so they drop out, leaving $\{1,2,5,6\}$. The operators are chosen to mirror the logic: | is or, & is and, exactly as for booleans.

🔄 Check Your Understanding 1. With $U = \{1,2,\dots,10\}$, $A = \{2,4,6,8,10\}$, $B = \{1,2,3,4,5\}$, compute $A \cap B$, $A \cup B$, $A \setminus B$, and $\overline{A}$. 2. Translate $\overline{A \cap B}$ into a statement about membership using a logical connective, then say in words what set it describes. 3. Why is a Venn diagram good for finding an identity but not for proving one in general?

Answers

1. $A \cap B = \{2,4\}$; $A \cup B = \{1,2,3,4,5,6,8,10\}$; $A \setminus B = \{6,8,10\}$; $\overline{A} = \{1,3,5,7,9\}$. 2. $x \in \overline{A \cap B}$ means $\neg(x \in A \land x \in B)$, i.e. $x$ is not in both — equivalently (De Morgan) $x \notin A$ or $x \notin B$. It is the set of elements missing from at least one of $A, B$. 3. A specific diagram shows specific circles in "general position"; it cannot rule out special cases (e.g., $A \subseteq B$, or $A$ empty) and a universal claim must cover all of them. The diagram suggests the truth; the element method (8.5) establishes it for every case at once.

8.4 Cartesian products and ordered pairs

So far order has never mattered — that is the defining feature of a set. But constantly we need the opposite: a pairing where order does matter. The point $(3, 5)$ on a grid is not the point $(5, 3)$. A row in a database table is an ordered tuple of fields. A move in chess is a from-square paired with a to-square. To capture "order matters," we need a new object built from sets.

An ordered pair $(a, b)$ is a pairing of two objects in which $a$ is the first coordinate and $b$ is the second. Its defining property is exactly what distinguishes it from the set $\{a, b\}$: $$(a, b) = (c, d) \quad \text{if and only if} \quad a = c \text{ and } b = d.$$ So $(3, 5) \ne (5, 3)$ (different first coordinates), whereas as sets $\{3, 5\} = \{5, 3\}$. Order and repetition matter in a pair: $(3, 3)$ is a perfectly good ordered pair, while $\{3, 3\} = \{3\}$ collapses.

💡 Intuition: A set is a bag — you can only ask "is this in the bag?" An ordered pair is a labeled slot machine with two windows, "first" and "second." The pair remembers positions; the set forgets them. Tuples in Python ((3, 5)) are ordered pairs; sets ({3, 5}) are sets — and Python will not let you confuse them.

Now we build a set out of ordered pairs. Given two sets, the Cartesian product $A \times B$ is the set of all ordered pairs whose first coordinate comes from $A$ and second from $B$: $$A \times B = \{ (a, b) \mid a \in A \text{ and } b \in B \}.$$ (The name honors Descartes, whose coordinate plane is exactly $\mathbb{R} \times \mathbb{R}$, written $\mathbb{R}^2$.) For example, $$\{1, 2\} \times \{x, y, z\} = \{(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)\}.$$ Every element of the first set is paired with every element of the second — a grid. Counting that grid gives a rule you will use constantly: $$\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert.$$ Above, $2 \times 3 = 6$ pairs, which matches. This is the product rule again (Chapter 15): to build a pair you choose a first coordinate ($\lvert A \rvert$ ways) and a second ($\lvert B \rvert$ ways).

⚠️ Common Pitfall: The Cartesian product is not commutative: $A \times B \ne B \times A$ in general, because $(a,b) \ne (b,a)$. With $A = \{1\}$ and $B = \{x\}$, $A \times B = \{(1,x)\}$ but $B \times A = {(x,1)}$ — different pairs. (The two products always have the same cardinality, but they are not the same set.) Likewise $A \times \emptyset = \emptyset$: there are no second coordinates to choose, so no pairs exist.

The construction extends to more than two sets: $A \times B \times C$ is the set of ordered triples $(a, b, c)$, and $A^n = A \times A \times \cdots \times A$ ($n$ times) is the set of $n$-tuples from $A$. The set $\{0, 1\}^n$ — all length-$n$ bitstrings — has $2^n$ elements, which is why it is the natural index set for the power set, and why an 8-bit byte has exactly $2^8 = 256$ values.

🔗 Connection. Cartesian products are the mathematical backbone of relational databases: a table with columns of types $T_1, T_2, \dots, T_k$ is a subset of $T_1 \times T_2 \times \cdots \times T_k$ — each row is one tuple, and the table is the set of allowed rows. We make this precise in Chapter 12, where a relation is defined as a subset of a Cartesian product. The ordered pair you just met is the atom of every relation and every graph edge (Chapter 27) in the rest of the book.

Here is the product in Python. We will build it from scratch (with a comprehension that reads almost exactly like the set-builder definition) and then note the library shortcut.

A = {1, 2}
B = {"x", "y", "z"}
product = {(a, b) for a in A for b in B}   # mirrors {(a,b) | a in A, b in B}
print(len(product))          # |A x B| = |A| * |B| = 2 * 3
print((1, "x") in product)   # is this pair in the product?
print((1, "x") == ("x", 1))  # ordered pairs: order matters
# Expected output:
# 6
# True
# False

The comprehension {(a, b) for a in A for b in B} is the Cartesian product written almost verbatim from its definition — two nested "for" clauses, one per coordinate. (Python's standard library also offers itertools.product(A, B), which we will use later once the concept is solid.)

🔄 Check Your Understanding 1. Let $A = \{1, 2, 3\}$ and $B = \{a, b\}$. What is $\lvert A \times B \rvert$? Write three of its elements. 2. Is $(2, 2) \in A \times A$ for $A = \{1, 2\}$? Is $\{2, 2\}$ a two-element set? 3. A password is 4 characters, each a lowercase letter (26 options). Express the set of all such passwords as a Cartesian power, and give its cardinality.

Answers

1. $\lvert A \times B \rvert = 3 \cdot 2 = 6$; sample elements: $(1,a), (2,b), (3,a)$. 2. Yes — $(2,2)$ is a valid ordered pair with both coordinates in $A$, so it is in $A \times A$. But ${2, 2} = {2}$ is a one-element set; repetition collapses in sets but not in pairs. 3. The set is $L^4 = L \times L \times L \times L$ where $L$ is the 26-letter alphabet; its cardinality is $26^4 = 456{,}976$.

8.5 Proving set identities

This is the section the chapter has been building toward. A set identity is an equation between set expressions that holds for all sets — for example, $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$, the distributive law. Because it must hold for all sets, you cannot verify it by trying one example (that only checks one case, and a Venn diagram only checks "generic" cases). You need a proof. There are two standard methods, and a fluent reader knows both.

Method 1: the element method (mutual inclusion)

The element method is the direct application of "equal means mutual inclusion" from 8.2. To prove $A = B$, prove $A \subseteq B$ and $B \subseteq A$, each by taking an arbitrary element and chasing it through the definitions. Often the two directions combine into one chain of if and only if steps.

Let's prove one of De Morgan's laws for sets — the result we previewed as a threshold idea.

De Morgan's Law for sets. For all sets $A, B$ (in a universe $U$), $\overline{A \cup B} = \overline{A} \cap \overline{B}$.

The strategy first. We show the two sets have exactly the same members by following one arbitrary element $x$ through the definitions. The pivot is a logical equivalence you proved in Chapter 1: $\neg (p \lor q) \equiv \neg p \land \neg q$. Every step is "unfold a definition" or "apply that equivalence," so the proof is mechanical once you set it up. We will write it as a chain of iff's, which proves both inclusions at once.

Proof. Let $x \in U$ be arbitrary. Then $$ > \begin{aligned} > x \in \overline{A \cup B} > &\iff x \notin A \cup B && \text{(definition of complement)} \\ > &\iff \neg\,(x \in A \lor x \in B) && \text{(definition of union)} \\ > &\iff (x \notin A) \land (x \notin B) && \text{(De Morgan's law, Chapter 1)} \\ > &\iff (x \in \overline{A}) \land (x \in \overline{B}) && \text{(definition of complement, twice)} \\ > &\iff x \in \overline{A} \cap \overline{B} && \text{(definition of intersection).} > \end{aligned} > $$ Since $x \in \overline{A \cup B} \iff x \in \overline{A} \cap \overline{B}$ for every $x$, the two sets have the same elements, so $\overline{A \cup B} = \overline{A} \cap \overline{B}$. $\blacksquare$

Read that proof again and notice what actually happened: the entire mathematical content is the one line "De Morgan's law, Chapter 1." Everything else is bookkeeping — unfolding the definition of each set operation into its logical connective, applying a known logical equivalence, and folding back up. This is the engine of every set-identity proof by the element method: translate membership into logic, apply a logical law, translate back. The threshold insight from 8.3 is what makes it work.

Sometimes a chain of iff's is awkward (for example, when one direction needs a case split), and you prove the two inclusions separately. Here is that style on the distributive law.

Distributive law. For all sets $A, B, C$: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.

The strategy first. Two inclusions. For "$\subseteq$": take $x$ in the left side, unpack it, and show it lands in the right side. For "$\supseteq$": the reverse. Each direction is just the distributive law of logic ($p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$) applied to the membership conditions — but writing it as two inclusions shows the technique when the iff-chain feels too slick.

Proof. ($\subseteq$) Let $x \in A \cap (B \cup C)$. Then $x \in A$, and $x \in B \cup C$, so $x \in B$ or $x \in C$. - If $x \in B$: then $x \in A$ and $x \in B$, so $x \in A \cap B$, hence $x \in (A \cap B) \cup (A \cap C)$. - If $x \in C$: then $x \in A$ and $x \in C$, so $x \in A \cap C$, hence $x \in (A \cap B) \cup (A \cap C)$.

Either way $x \in (A \cap B) \cup (A \cap C)$. So $A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$.

($\supseteq$) Let $x \in (A \cap B) \cup (A \cap C)$. Then $x \in A \cap B$ or $x \in A \cap C$. In the first case $x \in A$ and $x \in B$; in the second $x \in A$ and $x \in C$. In both cases $x \in A$, and in both cases $x \in B$ or $x \in C$, i.e. $x \in B \cup C$. Hence $x \in A \cap (B \cup C)$. So $(A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)$.

Both inclusions hold, so the two sets are equal. $\blacksquare$

💡 Intuition: The case split "if $x \in B$ … if $x \in C$ …" is the logical fact that $q \lor r$ means at least one of $q, r$ holds, so you must handle each possibility. Proof by cases (Chapter 5) and the connective $\lor$ are the same structure seen from two directions.

Method 2: set-builder algebra

Once you trust the translation, you can skip the element-chasing prose and manipulate set-builder expressions directly, citing logical equivalences as the justification. This is faster for experienced readers. Reproving De Morgan this way: $$ \overline{A \cup B} = \{x \mid \neg(x \in A \lor x \in B)\} = \{x \mid x \notin A \land x \notin B\} = \{x \mid x \in \overline{A}\} \cap \{x \mid x \in \overline{B}\} = \overline{A} \cap \overline{B}. $$ It is the same proof, compressed. Use whichever style your reader will find clearest; the element method is safer when you are learning, because every step names a definition.

For reference, here are the core set identities. Each is a logical equivalence in disguise, and each can be proved by the element method as a drill.

🐛 Find the Error. A student "proves" $A \setminus (B \cap C) = (A \setminus B) \cap (A \setminus C)$ by drawing one Venn diagram, shading both sides, and observing the shadings look the same. The identity is actually false. Find a tiny counterexample, then say what the correct right-hand side should be.

Answer

Take $A = \{1, 2\}$, $B = \{1\}$, $C = \{2\}$. Then $B \cap C = \emptyset$, so $A \setminus (B \cap C) = A = {1, 2}$. But $A \setminus B = {2}$ and $A \setminus C = {1}$, so $(A \setminus B) \cap (A \setminus C) = \emptyset \ne {1,2}$. The student's diagram silently assumed $B$ and $C$ overlap inside $A$; the correct identity is De Morgan-flavored: $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$ — difference turns the inner $\cap$ into a $\cup$, exactly as negation turns $\land$ into $\lor$. This is why a single picture is not a proof.

🔄 Check Your Understanding 1. In the De Morgan proof, which single step carried all the mathematical content, and which steps were "bookkeeping"? 2. Prove the absorption law $A \cup (A \cap B) = A$ by the element method (sketch both inclusions). 3. State the dual of De Morgan's law (swap $\cup \leftrightarrow \cap$). What logical equivalence justifies it?

Answers

1. The step "De Morgan's law, Chapter 1" ($\neg(p \lor q) \equiv \neg p \land \neg q$) is the content; unfolding/folding the definitions of complement, union, and intersection is bookkeeping.
2. ($\subseteq$) If $x \in A \cup (A \cap B)$ then $x \in A$ or $x \in A \cap B$; in either case $x \in A$ (the second case gives $x \in A$ directly). ($\supseteq$) If $x \in A$ then certainly $x \in A \cup (\text{anything})$. So both sides are equal to $A$. 3. The dual is $\overline{A \cap B} = \overline{A} \cup \overline{B}$, justified by $\neg(p \land q) \equiv \neg p \lor \neg q$.

8.6 Sets in code: set, frozenset, and when to use them

The mathematics is now a data structure. Python's built-in set is a direct, fast implementation of a finite set, and understanding the correspondence tells you exactly when to reach for it.

A set literally enforces the two defining properties from 8.1: distinctness (adding an element already present is a no-op) and unorderedness (there is no indexing, no guaranteed iteration order). What you gain in exchange for giving up order is speed: membership testing (x in s) is average-case $O(1)$, because a set is implemented as a hash table — a structure we study in depth later in the book. Contrast a list, where x in lst is $O(n)$ because it scans.

seen = set()                 # the empty set; NOT {} which is an empty dict!
for item in [3, 1, 3, 2, 1]:
    seen.add(item)           # adding a duplicate does nothing
print(len(seen))             # cardinality: distinct items only
print(2 in seen)             # O(1) average membership test
words = ["to", "be", "or", "not", "to", "be"]
print(len(set(words)))       # distinct-word count in one expression
# Expected output:
# 3
# True
# 4

That last line is the deduplication payoff from the overview: set(words) removes repeats and len counts the survivors, all in near-linear time. The crawler's "already visited" set, the "usernames taken" set, and the "distinct words" set are all this pattern.

⚠️ Common Pitfall: {} is an empty dictionary, not an empty set — a genuine Python gotcha that bites everyone once. The empty set is set(). (Non-empty set literals like {1, 2} are sets, because there are no key-value colons; only the empty braces are ambiguous, and Python resolves them as a dict.)

There is one constraint the mathematics does not obviously predict but the implementation forces: a set's elements must be hashable, which in practice means immutable. You cannot put a list or a set inside a set, because they can change and would corrupt the hash table. This matters the moment you want a set of sets — for instance, a power set, whose elements are themselves sets. The fix is frozenset: an immutable set that is hashable and so can be an element of another set.

# A power set is a set whose ELEMENTS are sets -> use frozenset for the inner sets.
S = {1, 2}
empty   = frozenset()
just1   = frozenset({1})
just2   = frozenset({2})
both    = frozenset({1, 2})
powerset = {empty, just1, just2, both}    # a set of frozensets
print(len(powerset))                       # should be 2^|S| = 4
print(frozenset({2, 1}) in powerset)       # order-insensitive membership
# Expected output:
# 4
# True

Notice frozenset({2, 1}) was found even though we inserted frozenset({1, 2}) — frozensets are still unordered, so the two are equal, and equality is what membership uses. This is set equality (8.2) doing exactly its job at the level of code.

When should you choose a set over a list? A compact decision rule:

🔗 Connection. The "$O(1)$ membership" guarantee is not magic — it rests on hashing, which in turn rests on the pigeonhole principle (many keys, few buckets, so collisions are inevitable) and on modular arithmetic. We build hash functions and the counting behind collisions properly in later chapters. For now, treat "set = fast membership, no duplicates, no order" as a contract you can rely on — and remember it is your mathematics, compiled.

🔄 Check Your Understanding 1. Why can't you write { {1}, {2} } directly as a set of sets in Python, and what is the fix? 2. You must keep, for each of 10 million log lines, whether you have seen that line's hash before. Set or list? Why, in one sentence about complexity? 3. What does set([3, 3, 1]) == set([1, 3]) evaluate to, and which set property guarantees it?

Answers

1. The inner {1} and {2} are mutable set objects, which are unhashable and cannot be elements of a set; replace them with frozenset({1}) and frozenset({2}). 2. A set — membership is $O(1)$ average versus $O(n)$ for a list, so checking "seen before?" ten million times is near-linear instead of quadratic. 3. True — duplicates collapse and order is irrelevant, so both expressions denote the set $\{1, 3\}$; set equality is by elements only.

Project Checkpoint: building sets.py for the Toolkit

Time to add the second module to your growing dmtoolkit. In Chapter 6 you began recurrences.py; now we build sets.py, implementing the four core set operations and the power set from scratch over an explicit universe — not by calling Python's built-ins, but by writing the definitions from 8.3 and 8.4 directly as code. Implementing them yourself is how the definitions become permanent.

The point of "from scratch" is fidelity to the math: each function is a one-line transcription of a set-builder definition. We use frozenset for the elements of a power set (per 8.6) so the result is a genuine set of sets.

Create dmtoolkit/sets.py and add:

def union(a, b):
    """{ x | x in a or x in b }"""
    return {x for x in a} | {x for x in b}

def intersection(a, b):
    """{ x | x in a and x in b }"""
    return {x for x in a if x in b}

def difference(a, b):
    """{ x | x in a and x not in b }"""
    return {x for x in a if x not in b}

def cartesian(a, b):
    """{ (x, y) | x in a and y in b }"""
    return {(x, y) for x in a for y in b}

def power_set(s):
    """{ A | A subseteq s }, as a set of frozensets. |power_set(s)| == 2 ** |s|."""
    elems = list(s)
    subsets = {frozenset()}                      # start with the empty set
    for x in elems:                              # peel off one element at a time
        subsets |= {sub | {x} for sub in subsets}   # double: each subset, with and without x
    return subsets

if __name__ == "__main__":
    A, B = {1, 2, 3}, {3, 4}
    print(sorted(union(A, B)))
    print(sorted(intersection(A, B)))
    print(sorted(difference(A, B)))
    print(len(power_set({1, 2, 3})))      # 2 ** 3
    print(len(cartesian({1, 2}, {"x", "y", "z"})))   # 2 * 3
# Expected output:
# [1, 2, 3, 4]
# [3]
# [1, 2]
# 8
# 6

The power_set function deserves a second look, because it is the $2^n$ proof from 8.2 turned into an algorithm. It starts with {∅} and processes one element $x$ at a time; at each step it keeps every subset built so far and adds a copy of each with $x$ included — doubling the collection each pass. After processing $n$ elements, the count has doubled $n$ times: $2^n$ subsets, exactly the theorem. The "with $x$ / without $x$" branch is the binary choice from the combinatorial proof, running in code.

Toolkit so far: logic.py (Chapters 1–3), recurrences.py (begun Chapter 6), and now sets.py. These set operations are not throwaway: in Chapter 12 your relations.py will represent a relation as a set of pairs built with cartesian, and in Part V graphs.py will store a graph's edges as a set. Every later structure is assembled from the operations you just wrote.

Summary

A set is an unordered collection of distinct elements, defined entirely by which objects it contains. This chapter's results, reference-grade:

Core objects and notation

Operations (each = a logical connective on membership)

Key facts

• $\emptyset \subseteq B$ for every set $B$ (vacuously true); $A \subseteq A$ always.
• Proving a set identity = translate membership to logic, apply a logical equivalence, translate back.
• De Morgan for sets is De Morgan for logic: $\overline{A \cup B} = \overline{A} \cap \overline{B}$, $\overline{A \cap B} = \overline{A} \cup \overline{B}$.
• A Venn diagram can suggest an identity but cannot prove one (it misses special cases).

In code: set = fast ($O(1)$) membership, no duplicates, no order, elements must be hashable; frozenset = immutable set, hashable, usable as an element of another set (needed for sets of sets). Beware: {} is an empty dict; the empty set is set().

Spaced Review

Retrieval keeps knowledge available. Answer from memory before checking.

1. (Ch. 2) Set-builder notation $\{x \mid P(x)\}$ uses a predicate as a filter. Write the negation of the statement "$\forall x\,(x \in A \rightarrow x \in B)$" and say in set language what that negation asserts.
2. (Ch. 2) Translate "every prime greater than 2 is odd" into a quantified statement, and express the set of counterexamples (which is empty) in set-builder notation.
3. (Ch. 1) Which logical equivalence is the De Morgan law for sets $\overline{A \cap B} = \overline{A} \cup \overline{B}$ secretly using?
4. (Ch. 1) Build the truth table for $p \land (q \lor r)$ versus $(p \land q) \lor (p \land r)$ and say which set identity their equivalence proves.

Answers

1. The negation is $\exists x\,(x \in A \land x \notin B)$ — there exists an element of $A$ that is not in $B$. In set language: $A \not\subseteq B$, witnessed by an element of $A \setminus B$. 2. $\forall p\,\big((p \text{ prime} \land p > 2) \rightarrow p \text{ odd}\big)$; the counterexample set $\{ p \mid p \text{ prime} \land p > 2 \land p \text{ even} \} = \emptyset$. 3. $\neg(p \land q) \equiv \neg p \lor \neg q$. 4. Both columns of the truth table agree on all 8 rows, so $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$; this proves the distributive law $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.

What's Next

You now have the static objects of discrete math — collections and the operations on them. The natural next question is dynamic: how do the elements of one set correspond to those of another? A rule that assigns to each input exactly one output is a function, and it turns out to be a special kind of set — a set of ordered pairs (the very pairs you built with the Cartesian product). In Chapter 9 we define functions formally, classify them as injective, surjective, or bijective, and discover that bijections are how we compare the sizes of sets — the idea that, a couple of chapters later, will let us prove the startling fact that some infinities are bigger than others. The membership relation you mastered here is the atom; functions are the first molecule.