Exercises: Relations

DataField.Dev

Exercises: Relations

These build from mechanical warm-ups (convert a relation between representations, test a property) up to full proofs, code, modeling, and a conjecture you'll settle with both. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the daggered (†) and odd-numbered problems are in the appendix answers-to-selected.md — try them before you peek.

Throughout, "$R$ on $A$" means a relation with the same set on both sides, and we write $a\,R\,b$ for $(a, b) \in R$, exactly as in §12.1.

Part A — Warm-ups: represent and test (⭐)

12.1 † Write the relation "$a + b$ is even" on the set $A = \{1, 2, 3, 4\}$ as an explicit set of ordered pairs.

12.2 For the relation $R = \{(1,1),(1,2),(2,2),(2,3),(3,3)\}$ on $\{1,2,3\}$, draw the Boolean adjacency matrix (rows/columns in the order $1, 2, 3$).

12.3 † The matrix below is the adjacency matrix of a relation on $\{a, b, c\}$ (order $a, b, c$). Write the relation as a set of pairs. $$M = \begin{array}{c|ccc} & a & b & c \\ \hline a & 1 & 0 & 1 \\ b & 0 & 1 & 0 \\ c & 1 & 0 & 1 \end{array}$$

12.4 Let $A = \{1, 2, 3, 4, 5, 6\}$ and $R = \{(a,b) \mid a \mid b\}$ ("divides"). Without listing every pair, state (a) how many pairs $(a, a)$ are in $R$, and (b) every $b$ with $2\,R\,b$.

12.5 † For each property — reflexive, symmetric, antisymmetric, transitive — state in one sentence what it looks like in the digraph of a relation.

12.6 A relation on a set of size $n = 5$ has exactly $7$ pairs. How many $1$s and how many $0$s does its adjacency matrix contain?

Part B — Ordinary computation (⭐⭐)

12.7 † Classify the relation $R = \{(a, b) \mid a \equiv b \pmod 4\}$ on $A = \{0, 1, \dots, 7\}$ by which of the four properties it has, then list its equivalence classes (if it is an equivalence relation).

12.8 Classify "$\subseteq$" (the subset relation) on the power set $\mathcal{P}(\{1, 2\})$: which of the four properties hold? (List the four subsets first, then check.)

12.9 † Compute the reflexive closure, the symmetric closure, and the transitive closure of $R = \{(1,2),(2,3),(3,1)\}$ on $\{1, 2, 3\}$. Give each as an explicit set of pairs.

12.10 Let $R = \{(1,2),(2,4),(4,1),(3,3)\}$ on $\{1,2,3,4\}$. Compute the transitive closure by hand, showing each pass of "add all missing shortcuts" until a pass adds nothing.

12.11 † A partition of $A = \{1,2,3,4,5\}$ has blocks $\{1,3,5\}$ and $\{2,4\}$. Write the corresponding equivalence relation as a set of pairs, and state how many pairs it has. (Recall §12.4: the relation contains exactly the within-block pairs.)

12.12 "Has the same number of letters as" is an equivalence relation on the set of words $\{\text{cat}, \text{dog}, \text{tree}, \text{ant}, \text{four}\}$. List its equivalence classes.

Part C — Prove it (⭐⭐, one scaffolded)

12.13 † (Scaffolded — fill the missing steps.) Prove that the relation $R = {(a, b) \mid a \equiv b \pmod 5}$ on $\mathbb{Z}$ is **transitive**. Fill the blanks, using the definition $a \equiv b \pmod 5 \iff 5 \mid (a - b) \iff a - b = 5k$ for some integer $k$ (as in §12.3).

Setup. Suppose $(a, b) \in R$ and $(b, c) \in R$. By the definition of congruence, $a - b = 5k$ and $b - c = \underline{\hphantom{xxxx}}$ for some integers $k$ and $m$.
Combine. Add the two equations: $a - c = (a - b) + (b - c) = \underline{\hphantom{xxxxxx}} = 5(\underline{\hphantom{xx}})$.
Conclude. Since $k + m$ is an integer, $5 \mid (a - c)$, so $(a, c) \in \underline{\hphantom{xx}}$. Therefore $R$ is transitive. $\blacksquare$

12.14 Prove that the relation "$\le$" on $\mathbb{Z}$ is antisymmetric. (State the definition you are verifying, then give the two-line argument.)

12.15 † Let $R$ be a symmetric and transitive relation on $A$, and suppose that every element of $A$ appears in at least one pair of $R$ (i.e., for each $a$ there is some $b$ with $(a, b) \in R$). Prove that $R$ is reflexive — and therefore an equivalence relation. (This is a classic trap: people think symmetric + transitive "almost" gives reflexive for free. The extra hypothesis is exactly what's needed.)

12.16 Prove that if $R$ is an equivalence relation on $A$ and $a, b \in A$, then $[a] = [b]$ if and only if $(a, b) \in R$. (One direction is §12.4's overlap-implies-equal argument; the other uses reflexivity. This is the precise "representatives are interchangeable" statement.)

12.17 † Let $R$ be a relation on $A$. Prove that $R$ is symmetric if and only if its adjacency matrix $M$ equals its own transpose, $M = M^{\mathsf{T}}$ (that is, $M_{ij} = M_{ji}$ for all $i, j$). (Translate the definition of symmetric into a statement about matrix entries, both directions.)

Part D — Find the error (⭐⭐)

Each argument below is wrong. State precisely which step fails and why.

12.18 † Claim: every relation that is symmetric and transitive is reflexive. "Proof": Let $(a, b) \in R$. By symmetry, $(b, a) \in R$. By transitivity applied to $(a, b)$ and $(b, a)$, we get $(a, a) \in R$. Since $a$ was arbitrary, $R$ is reflexive. ∎ — Find the flaw. (Hint: which $a$ does the argument actually cover? Compare with Exercise 12.15.)

12.19 Claim: "Antisymmetric" means "not symmetric." "Proof": The two conditions are written with the same hypotheses but opposite conclusions, so a relation has one exactly when it lacks the other. ∎ — Explain why this is wrong, and give a single relation on $\{1, 2\}$ that is both symmetric and antisymmetric (showing they are not negations).

12.20 † Claim: the transitive closure of any relation can be computed in a single pass that, for every two-step path $a \to b \to c$, adds the shortcut $(a, c)$. "Proof": one pass adds every shortcut, and adding a pair can only help transitivity, so we're done. ∎ — Using $R = \{(1,2),(2,3),(3,4)\}$, exhibit a shortcut that a single pass misses, and explain the cascade the argument ignores (cf. §12.5).

12.21 A student writes this check for whether R is an equivalence relation on A:

def is_equivalence_buggy(R, A):
    reflexive = all((a, a) in R for a in R)        # <- bug is on this line
    symmetric = all((b, a) in R for (a, b) in R)
    transitive = all((a, c) in R for (a, b) in R for (x, c) in R if b == x)
    return reflexive and symmetric and transitive

The symmetric and transitive lines are correct. The reflexive line is subtly wrong. State what for a in R actually iterates over, and give a concrete R and A on which is_equivalence_buggy returns the wrong answer.

Part E — Implement it (⭐⭐)

Write Python for each. Do not run it — hand-trace and include an # Expected output: comment, matching the book's convention. Represent a relation as a set of tuples, as in the chapter.

12.22 † Write is_antisymmetric(R) that returns True iff the relation R (a set of pairs) is antisymmetric. Test it on {(1,2),(2,1)} (should be False) and on {(1,2),(1,1)} (should be True).

12.23 Write reflexive_closure(R, A) and symmetric_closure(R) that return the respective closures as new sets (do not mutate R). Demonstrate both on R = {(1,2),(2,3)} with A = {1,2,3}.

12.24 † Write is_partition(blocks, A) that takes a list of sets blocks and a set A, and returns True iff blocks is a partition of A (every block non-empty, blocks pairwise disjoint, union equals A). Test it on [{1,2},{3}] with A = {1,2,3} (True) and on [{1,2},{2,3}] with A = {1,2,3} (False — they overlap).

12.25 Write relation_from_partition(blocks) that, given a partition as a list of sets, returns the corresponding equivalence relation as a set of pairs (the within-block pairs, both directions, including self-loops — the construction of §12.4's converse theorem). Demonstrate it on [{0,3},{1,4},{2,5}].

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

12.26 † (Model it.) A build system has targets A, B, C, D, E. The rule "X must be built immediately before Y" (a direct dependency) is D = {(A,B),(A,C),(B,D),(C,D),(D,E)}. (a) Express "X must be built at some point before Y" as an operation on D from this chapter, and name it. (b) Is target A required (directly or indirectly) before E? Answer by referring to the closure you named. (c) Why would a self-loop appearing in that closure indicate a problem with the build (a notion Chapter 13 will name)?

12.27 (Model it.) You are designing the "blocked users" feature of a chat app. Model the relation B where $(u, v) \in B$ means "$u$ has blocked $v$." (a) Should B be symmetric? Justify in terms of product behavior, not opinion. (b) Now model "$u$ and $v$ cannot see each other's messages," and express it as a closure of B. Which closure, and why? (c) Is the result an equivalence relation? Which property (if any) is still missing, and what would it mean in the app to add it?

12.28 † (Conjecture and test, then prove.) Let $R$ be a relation on a finite set $A$ with $\lvert A \rvert = n$. Conjecture: the transitive closure of $R$ stabilizes after at most $n - 1$ passes of "add all missing shortcuts" (i.e., once no new pair appears, you've found every reachability pair, and that takes at most $n-1$ rounds). (a) Write code that computes the transitive closure while counting the passes, and run it in your head on the chain $\{(1,2),(2,3),(3,4),(4,5)\}$ ($n = 5$). How many passes? (b) Try the cycle $\{(1,2),(2,3),(3,1)\}$ ($n = 3$). (c) Argue (a short proof) why a new reachability pair $(a, b)$ found on pass $k$ corresponds to a shortest path of length $\ge k+1$, so passes cannot exceed $n - 1$ (the longest possible simple path in an $n$-node graph).

12.29 (Conjecture and test.) Conjecture: on an $n$-element set, the number of equivalence relations equals the number of partitions, and for $n = 1, 2, 3, 4$ these counts are $1, 2, 5, 15$. (These are the Bell numbers.) (a) Write code that generates all relations on $\{1, 2, 3\}$ that are equivalence relations (brute force over subsets of $A \times A$ is fine for $n = 3$) and counts them; predict the output. (b) Why does the equivalence-relation/partition bijection of §12.4 guarantee the two counts agree, with no computation needed? (You are not asked to derive the Bell-number formula — Part III does counting.)

Part G — Interleaved & Deep Dive

Mixing earlier chapters keeps them sharp.

12.30 † (Ch. 8 + 12.) A relation on $A$ is a subset of $A \times A$. Using the Cartesian-product count from Chapter 8, (a) how many pairs are in $A \times A$ when $\lvert A \rvert = n$? (b) How many relations on $A$ are there in total? (c) How many of them are reflexive? (Hint: a reflexive relation must contain all $n$ diagonal pairs and may contain any subset of the other pairs.)

12.31 (Ch. 9 + 12.) Every function $f\colon A \to B$ is a relation $R_f \subseteq A \times B$. (a) State the two conditions on $R_f$ (from §12.1) that make it a function. (b) Define a relation $\sim$ on $A$ by $x \sim y$ iff $f(x) = f(y)$ ("$x$ and $y$ have the same image"). Prove $\sim$ is an equivalence relation. (c) When $f$ is the "key projection" of a database table, describe the equivalence classes of $\sim$ in words, and say what they look like when $f$ is injective (the key constraint of §12.6).

12.32 (Ch. 4 + 12.) Using divisibility from Chapter 4, prove that "divides" ($a \mid b$) is a partial-order-flavored relation on the positive integers by proving it is reflexive, antisymmetric, and transitive. For antisymmetry, use the fact (Chapter 4) that if $a \mid b$ and $b \mid a$ with $a, b > 0$ then $a = b$. (This combination is exactly what Chapter 13 will call a partial order.)

12.33 (Ch. 6 + 12 — Deep Dive.) Prove by induction on $k \ge 1$ that if $M$ is the Boolean adjacency matrix of a relation $R$, then there is a path of length exactly $k$ from $a_i$ to $a_j$ in the digraph of $R$ if and only if the $(i, j)$ entry of the Boolean matrix power $M^{(k)}$ is $1$ (where Boolean matrix multiplication uses $\land$ for $\times$ and $\lor$ for $+$). Then explain in one sentence why $M^{(1)} \lor M^{(2)} \lor \dots \lor M^{(n)}$ is the adjacency matrix of the transitive closure.

12.34 (Deep Dive — the converse theorem.) §12.4 proved that the classes of an equivalence relation form a partition, and sketched the converse. Write the full converse proof: given a partition $P$ of $A$, define $(a, b) \in R$ iff $a, b$ lie in the same block, and prove $R$ is reflexive, symmetric, and transitive, then show its classes are exactly the blocks of $P$. (The transitive step is where disjointness of blocks does the work.)

12.35 (Deep Dive — Warshall's algorithm.) §12.5 mentioned Warshall's $O(n^3)$ algorithm for transitive closure. (a) Write it: three nested loops over the adjacency matrix where, for each "intermediate" vertex $k$, you set $M[i][j] = M[i][j] \lor (M[i][k] \land M[k][j])$. (b) Run it in your head on $\{(1,2),(2,3)\}$ over $\{1,2,3\}$ and give the final matrix. (c) Compare its cost to the pass-until-stable method of §12.5 and explain, in one sentence, why Warshall needs only one pass over $k$ where the naive method may need several passes.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: the property's definition stated explicitly, a correct use of the relevant assumption (congruence unpacked, blocks disjoint, etc.), and a clean conclusion. For each "implement it," the rubric rewards a faithful transcription of the definition and a correct hand-derived # Expected output:.