Exercises: Sets

DataField.Dev

Exercises: Sets

These build from mechanical warm-ups through full proofs, code, modeling, and a conjecture you must test before you trust. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md — attempt them before you peek. A good set-identity proof, like a good induction proof, is graded on a clearly stated strategy, correct use of definitions, and a clean conclusion.

Part A — Warm-ups (⭐)

8.1 † Write each set in roster notation. (a) $\{ x \in \mathbb{Z} \mid -2 \le x < 3 \}$. (b) the set of perfect cubes strictly between $0$ and $70$. (c) $\{ n^2 \mid n \in \mathbb{N},\ n \le 4 \}$.

8.2 Let $A = \{1, 2, \{3\}, \emptyset\}$. Answer true or false, with a one-phrase reason for each: (a) $3 \in A$; (b) $\{3\} \in A$; (c) $\emptyset \in A$; (d) $\emptyset \subseteq A$; (e) $\lvert A \rvert = 4$.

8.3 † Compute the cardinality of each: (a) $\{a, b, a, c, b\}$; (b) $\emptyset$; (c) $\{\emptyset\}$; (d) $\{\emptyset, \{\emptyset\}\}$; (e) $\{1, \{1, 2\}, \{1, 2, 3\}\}$.

8.4 With $U = \{1, 2, \dots, 10\}$, $A = \{1, 2, 3, 4, 5\}$, and $B = \{2, 4, 6, 8\}$, compute $A \cup B$, $A \cap B$, $A \setminus B$, $B \setminus A$, $\overline{A}$, and the symmetric difference $A \triangle B$.

8.5 † List every element of $\mathcal{P}(\{a, b, c\})$. How many are there? How many contain the element $a$?

Part B — Prove it (⭐⭐)

8.6 † (Scaffolded — fill in the missing steps.) Prove the absorption law $A \cap (A \cup B) = A$ by the element method. Fill the blanks:

($\subseteq$). Let $x \in A \cap (A \cup B)$. By the definition of intersection, $x \in A$ and $x \in \underline{\hphantom{xxxxx}}$. In particular $x \in \underline{\hphantom{xx}}$, so $A \cap (A \cup B) \subseteq A$.
($\supseteq$). Let $x \in A$. Then $x \in A \cup B$ as well (because membership in $A$ makes the "or" in $\underline{\hphantom{xxxxxxx}}$ true). Since $x \in A$ and $x \in A \cup B$, we have $x \in \underline{\hphantom{xxxxxxx}}$, so $A \subseteq A \cap (A \cup B)$.
Both inclusions hold, therefore $\underline{\hphantom{xxxxxxx}}$. $\blacksquare$

8.7 Prove by the element method that $A \setminus B = A \cap \overline{B}$ for all sets $A, B$ in a universe $U$. (This is the identity that lets you rewrite every difference as an intersection.)

8.8 † Prove one direction of De Morgan's law: $\overline{A \cap B} = \overline{A} \cup \overline{B}$. Write it as a chain of iff steps, naming the definition or logical equivalence used at each line (mirror the proof of $\overline{A \cup B} = \overline{A} \cap \overline{B}$ from §8.5).

8.9 Prove that for all sets $A$ and $B$, $A \subseteq B$ if and only if $A \cup B = B$. (Prove both directions; this is a small "iff with sets on both sides," so you will prove two set-equalities or two implications.)

8.10 † Prove the distributive law $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ (the dual of the one proved in §8.5). State your strategy first, then give two inclusions.

8.11 Prove that for all sets $A, B$: $A \subseteq B$ implies $\mathcal{P}(A) \subseteq \mathcal{P}(B)$. (Hint: take an arbitrary element of $\mathcal{P}(A)$ — remember its elements are sets — and show it belongs to $\mathcal{P}(B)$.)

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. Reference solutions live in code/exercise-solutions.py.

8.12 † Write a function symmetric_difference(a, b) that returns $A \triangle B = (A \setminus B) \cup (B \setminus A)$ from scratch (do not use Python's ^). Transcribe the set-builder definition directly, and show its output on $A = \{1,2,3,4\}$, $B = \{3,4,5,6\}$.

8.13 Write is_subset(a, b) returning True iff $A \subseteq B$, without using Python's <= or .issubset. Your one-line core should read like the definition $\forall x\,(x \in A \rightarrow x \in B)$. Test it on ${1,2} \subseteq {1,2,3}$ and ${1,5} \subseteq {1,2,3}$.

8.14 † Using the Toolkit's cartesian(a, b) from this chapter's Project Checkpoint, write three lines that build $A \times B$ for $A = \{1, 2\}$, $B = \{x, y, z\}$ and confirm $\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert$. What single printed value confirms the count rule held?

8.15 Write power_set_size_check(s) that builds power_set(s) (the Toolkit function) and returns True iff its size equals 2 ** len(s). Explain in one comment why you must use frozenset for the inner subsets.

Part D — Find the error (⭐⭐)

Each argument below is wrong. State precisely which part fails and why; where asked, give the corrected statement.

8.16 † Claim: "$\emptyset = \{\emptyset\}$, because both are 'empty-ish' and have nothing useful inside." "Justification": "neither contains an ordinary number, so they must be the same set." — Find the flaw, and give the cardinality of each set.

8.17 Claim: $A \setminus (B \cup C) = (A \setminus B) \cup (A \setminus C)$. "Proof": "removing $B$ or $C$ from $A$ is the same as removing $B$ from $A$ or removing $C$ from $A$." Find a small counterexample (try three-element sets), then state the correct right-hand side and name the logical law behind it.

8.18 † Claim: "For all sets $A, B$: if $A \in B$ then $A \subseteq B$." "Proof": "if $A$ is in $B$, then everything about $A$ is in $B$ too." Find a one- or two-element counterexample, and explain the difference between $\in$ and $\subseteq$ that the argument confuses.

8.19 Claim: "$A \times (B \cup C) = (A \times B) \cup (A \times C)$ is false because Cartesian product is not commutative." A classmate rejects the (true!) identity using an irrelevant reason. Explain why non-commutativity has nothing to do with this identity, then verify the identity holds on $A = \{1\}$, $B = \{x\}$, $C = \{y\}$.

Part E — Model it & Conjecture and test (⭐⭐⭐)

8.20 † (Model it.) A web crawler keeps three collections: visited (URLs already fetched), frontier (discovered but not yet fetched), and seen = visited ∪ frontier. Translate each of these requirements into a precise statement about sets, then say which set operation enforces it: (a) "never fetch the same URL twice"; (b) "the next URL to fetch is something discovered but not yet visited"; (c) "a freshly discovered URL is only added to the frontier if we have never seen it before." Which property of sets (versus lists) makes requirement (a) automatic?

8.21 (Model it.) A relational database table Enrollment pairs each student with each course they take. Using $S$ for the set of students and $C$ for the set of courses, express the universe of all conceivable enrollments as a Cartesian product, explain why the actual table is a subset of it, and state the maximum possible number of rows in terms of $\lvert S \rvert$ and $\lvert C \rvert$. (Chapter 12 will define a relation as exactly such a subset — you are previewing it.)

8.22 † (Conjecture and test, then prove.) For finite sets, is it always true that $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert$? First test the conjecture in code on a few pairs you write out by hand (include at least one overlapping pair and one disjoint pair), report where it breaks, then conjecture the corrected formula and prove it by the element method or a counting argument. (This corrected formula is inclusion–exclusion, formalized in Chapter 15.)

8.23 (Conjecture and test, then prove or disprove.) Conjecture: "for all finite sets, $\lvert \mathcal{P}(A \cup B) \rvert = \lvert \mathcal{P}(A) \rvert \cdot \lvert \mathcal{P}(B) \rvert$." Test it in code on a disjoint pair and an overlapping pair. Decide whether it is true in general; if false, find the smallest counterexample and state the condition on $A, B$ under which it does hold. (Use $\lvert \mathcal{P}(S) \rvert = 2^{\lvert S \rvert}$ to reason about why.)

Part F — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

8.24 † (Ch. 1 + 8.) Build the truth table for $\neg(p \land q)$ versus $\neg p \lor \neg q$, then state which set identity their logical equivalence proves and write that identity in set notation.

8.25 (Ch. 2 + 8.) Write the statement "$A \subseteq B$" as a quantified predicate, then write its negation (push the $\neg$ inward). In one sentence, say in plain set language what the negation asserts and which set a witness to it lives in.

8.26 † (Ch. 2 + 8.) Set-builder notation uses a predicate as a filter. Express each set with a set-builder expression $\{x \in U \mid P(x)\}$ for an appropriate predicate: (a) the even integers; (b) the prime numbers; (c) the complement (within $U = \mathbb{Z}$) of the multiples of $3$.

8.27 (Ch. 6 + 8.) Prove $\lvert \mathcal{P}(S) \rvert = 2^{\lvert S \rvert}$ by induction on $n = \lvert S \rvert$. (Base case $n = 0$; in the step, peel off one element $x$ and pair each subset of the rest with its copy that also contains $x$ — the "in or out" doubling. This is the induction the chapter promised in the Deep Dive learning path.)

8.28 † (Ch. 6 + 8.) The Toolkit's power_set starts with {frozenset()} and doubles the collection once per element. State the loop invariant ("after processing the first $j$ elements, subsets contains exactly …") and explain how it proves the function returns $2^{\lvert s \rvert}$ subsets — connecting the algorithm to the theorem of 8.2.

8.29 (Deep Dive.) Look up Russell's paradox: there is no set $R = \{x \mid x \notin x\}$. Argue, in one paragraph, why assuming such a set exists leads to the contradiction "$R \in R$ if and only if $R \notin R$." Which proof technique from Part I is this (assume existence, derive a contradiction)?

8.30 (Deep Dive.) Prove that $\{0, 1\}^n$ (the set of length-$n$ bitstrings) is in one-to-one correspondence with $\mathcal{P}(S)$ for any $n$-element set $S$: describe the map that sends a subset to its indicator bitstring, and explain why it is a bijection. This is the "subset $\leftrightarrow$ bitstring" idea from §8.2 made precise — and a preview of how Chapter 9 defines bijections and Chapter 15 counts with them.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: a stated strategy, correct unfolding of the set definitions into logic, an explicit appeal to a named logical equivalence where one is used, and a clean two-inclusion (or iff-chain) conclusion.