Chapter 12: Relations

"The relational model is based on the mathematical theory of relations." — E. F. Codd, paraphrasing the premise of A Relational Model of Data for Large Shared Data Banks (1970)

Overview

Open any database you have ever used and you are looking at relations. The word is not a coincidence: a table of (user_id, email) pairs, a table of (student, course) enrollments, a follows table of (follower, followee) pairs — every one of them is, formally, a relation in the precise mathematical sense this chapter builds. When you write JOIN, WHERE, or GROUP BY, you are manipulating relations with operations that mathematicians described decades before SQL existed. Understanding relations as mathematical objects is what lets you reason about whether a query is correct, why a UNIQUE constraint behaves the way it does, and what it really means to say two rows are "the same" for some purpose.

But databases are only the most obvious payoff. Relations are everywhere a programmer looks once they know the shape. "Is reachable from" on a graph of web pages is a relation. "Has the same hash as" on a set of keys is a relation. "Must run before" on a set of build targets is a relation. "Is congruent to, modulo 12" on the hours of a clock is a relation. The moment you can classify which kind of relation you have — does it group things into clean buckets? does it impose an ordering? — you unlock a standard toolbox of facts and algorithms that apply to all of them at once. That is abstraction (theme three of this book) doing exactly what it is supposed to do: one set of ideas, paying off in a dozen places.

We will start with the most concrete possible description — a relation is just a set of pairs — and from there develop three ways to see a relation, four properties that classify it, and two structures (equivalence relations and closures) that turn the classification into something you can compute with.

In this chapter, you will learn to:

• See a relation three ways — as a set of ordered pairs, as a Boolean matrix, and as a directed graph — and move between the representations as the problem demands.
• Decide whether a relation is reflexive, symmetric, antisymmetric, or transitive, and prove your answer.
• Recognize equivalence relations, the relations that partition a set into "sameness" buckets, and work with their equivalence classes.
• Compute closures — the smallest way to add pairs until a relation gains a property it was missing — with transitive closure as the headline case.
• Read a database table as a relation and explain joins, keys, and selection in the language of this chapter.

Learning Paths

🏃 Fast Track: If you have seen relations before, skim 12.1–12.2 for our notation, then focus on 12.3 (the four properties — get fast at testing them), 12.4 (equivalence relations and the partition theorem), and 12.5 (transitive closure). Do the ⭐⭐ and ⭐⭐⭐ exercises.

📖 Standard Path: Read in order. Work every 🔄 Check Your Understanding before moving on, and try to classify each example relation yourself before reading our classification.

🔬 Deep Dive: After the chapter, prove the equivalence-relation/partition correspondence in both directions in full detail (we prove one carefully and sketch the other), and implement Warshall's algorithm for transitive closure, then compare it to the repeated-composition approach in 12.5.

12.1 Relations as sets of pairs

Start with a concrete table. Suppose a tiny course-enrollment system records who is enrolled in what:

What is this table, stripped of its formatting? It is a set of pairs. Each row pairs a student with a course, and the table is the collection of those pairs:

$$E = \{(\text{Ana}, \text{CS101}),\ (\text{Ana}, \text{MATH200}),\ (\text{Ben}, \text{CS101}),\ (\text{Cleo}, \text{PHIL150})\}.$$

The order inside each pair matters — (Ana, CS101) means "Ana is enrolled in CS101," which is not the same statement as (CS101, Ana). We are using ordered pairs, the construction from Chapter 8, and the table is a subset of all possible (student, course) pairs.

🔗 Connection. Recall from Chapter 8 (§8.4) that the Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ with $a \in A$ and $b \in B$. If $S$ is the set of students and $C$ the set of courses, then every conceivable enrollment lives in $S \times C$, and our actual table $E$ is just the subset that really happened. That single observation — a relation is a subset of a Cartesian product — is the entire definition.

Here is the definition, stated once and for all.

Definition (binary relation). Let $A$ and $B$ be sets. A binary relation from $A$ to $B$ is a subset $R \subseteq A \times B$. We write $a\,R\,b$ (read "$a$ is related to $b$") to mean $(a, b) \in R$, and $a \not\!R\, b$ to mean $(a, b) \notin R$. When $A = B$, we call $R$ a relation on $A$.

"Binary" here means the pairs have two slots; this whole chapter is about binary relations, and we will usually just say "relation." The set $A$ is the relation's domain side and $B$ its codomain side, but the heart of the idea is brutally simple: a relation is a set of ordered pairs. Everything else — matrices, graphs, equivalence classes, closures — is a way of organizing or visualizing that one set.

Some relations you already know, recast in this language:

• "Less than" on integers. $R = \{(a, b) \mid a < b\} \subseteq \mathbb{Z} \times \mathbb{Z}$. Here $3\,R\,5$ (because $3 < 5$) but not $5\,R\,3$. This relation is infinite.
• "Divides" on positive integers. $R = \{(a, b) \mid a \mid b\}$. So $3\,R\,12$ because $3 \mid 12$. (We met divisibility back in Chapter 4.)
• "Has the same remainder mod 3." On $\{0, 1, \dots, 8\}$, this relates $1$ and $4$ and $7$ to each other, $2$ and $5$ and $8$ to each other, and so on. We will return to this one constantly.

💡 Intuition: A function (Chapter 9) is a special kind of relation — one where every input appears in exactly one pair. A relation lifts that restriction: an input can relate to zero, one, or many outputs. "Ana" appears in two pairs of $E$; that is fine for a relation but would be illegal for a function. So "relation" is the more general concept, and "function" is the disciplined special case.

🔗 Connection. This is why Chapter 9 opened by calling a function "a relation with a rule." Now you can see the precise statement: a function $f\colon A \to B$ is a relation $R \subseteq A \times B$ with the extra property that for every $a \in A$ there is exactly one $b$ with $(a, b) \in R$. Relations are the genus; functions are one species.

A relation on a finite set is itself a finite set of pairs, so we can store and manipulate it directly in code. The most faithful representation is a Python set of tuples:

# "Divides" relation on {1, 2, 3, 4, 5, 6}, built from its definition.
domain = range(1, 7)
divides = {(a, b) for a in domain for b in domain if b % a == 0}
print((2, 6) in divides)   # 2 divides 6?
print((4, 6) in divides)   # 4 divides 6?
# Expected output:
# True
# False

We built divides exactly the way the definition reads: take all pairs $(a, b)$ from the Cartesian product and keep those satisfying the condition. Testing "$a\,R\,b$" is then just a membership check, (a, b) in divides, which is the $\in$ of the definition rendered in Python.

🔄 Check Your Understanding 1. The relation $E$ (enrollment) above has 4 pairs. If there are 3 students and 4 courses, how many pairs are in the full Cartesian product $S \times C$, and what fraction does $E$ occupy? 2. Is "is enrolled in" a function from students to courses? Why or why not? 3. Write the relation "$a + b = 4$" on the set $\{0, 1, 2, 3, 4\}$ as an explicit set of pairs.

Answers

1. $|S \times C| = 3 \times 4 = 12$ pairs; $E$ has 4 of them, so it occupies $4/12 = 1/3$.
2. No. A function requires each input to relate to exactly one output, but Ana is enrolled in two courses, so "is enrolled in" relates one input to two outputs — a relation, not a function.
3. $\{(0,4), (1,3), (2,2), (3,1), (4,0)\}$.

12.2 Representing relations: matrix and digraph

A set of pairs is faithful but hard to see. Two other representations make different facts jump out, and switching between them is a core skill — many proofs and algorithms are obvious in one representation and opaque in another.

The Boolean matrix

For a relation $R$ on a finite set $A = \{a_1, a_2, \dots, a_n\}$, fix an ordering of the elements and build an $n \times n$ grid of $0$s and $1$s. Put a $1$ in row $i$, column $j$ exactly when $a_i\,R\,a_j$:

$$M_{ij} = \begin{cases} 1 & \text{if } (a_i, a_j) \in R, \\ 0 & \text{otherwise.} \end{cases}$$

This is the adjacency matrix (or relation matrix) of $R$. For "divides" on $\{1, 2, 3, 4\}$, with the natural ordering $1, 2, 3, 4$:

$$M = \begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline 1 & 1 & 1 & 1 & 1 \\ 2 & 0 & 1 & 0 & 1 \\ 3 & 0 & 0 & 1 & 0 \\ 4 & 0 & 0 & 0 & 1 \end{array}$$

Read row 2: $2 \mid 2$ and $2 \mid 4$, so there are $1$s in columns 2 and 4. Read the diagonal: it is all $1$s, because every number divides itself. We will see in 12.3 that properties of $R$ show up as visible patterns in this matrix — the all-$1$s diagonal, for instance, is exactly what "reflexive" looks like.

💡 Intuition: The matrix is a complete lookup table. Question "$a_i\,R\,a_j$?" becomes "what is in cell $(i, j)$?" — a constant-time array access once the matrix is built. The cost is space: the matrix always has $n^2$ cells, even if the relation has only a handful of pairs. (This is precisely the dense vs. sparse trade-off you will meet again for graphs in Chapter 28.)

The directed graph

The third view turns each element into a dot and each pair into an arrow. Draw a node for every element of $A$; draw an arrow from $a$ to $b$ whenever $a\,R\,b$. A pair $(a, a)$ becomes a self-loop, an arrow from a node back to itself. This picture is a directed graph, and a relation's directed-graph picture is sometimes called its relation digraph.

🔗 Connection. We are using directed graphs informally here, as a way to draw a relation. The directed graph is itself one of the most important objects in computer science, and it gets a full formal treatment in Chapter 27 — where, fittingly, a graph is defined as a set together with a relation on it. A relation and a directed graph are, in a precise sense developed there, the same thing wearing different clothes. For now, treat the digraph as a sketch that makes a relation's shape visible.

Here is "divides" on $\{1, 2, 3, 4\}$ as a digraph, drawn in text (an arrow a -> b means $a \mid b$; self-loops are listed once at the end):

1 -> 2     1 -> 3     1 -> 4
2 -> 4
self-loops: 1, 2, 3, 4   (every number divides itself)

Notice how each representation makes a different question easy. Is the relation reflexive? The matrix answers instantly (look at the diagonal). Can I get from 1 to 4 by following arrows? The digraph answers instantly (follow 1 -> 2 -> 4). That second question — reachability by following arrows — is exactly the transitive closure of 12.5, and it is no accident that it is the digraph that makes it natural.

The three representations, side by side

Let's build the matrix in code from a set of pairs, since we will reuse the conversion:

def relation_matrix(pairs, elements):
    """Boolean adjacency matrix of a relation given as a set of pairs."""
    idx = {e: i for i, e in enumerate(elements)}     # element -> row/col index
    n = len(elements)
    M = [[0] * n for _ in range(n)]
    for (a, b) in pairs:
        M[idx[a]][idx[b]] = 1
    return M

rel = {(1, 1), (1, 2), (2, 2), (1, 3), (3, 3), (1, 4), (2, 4), (4, 4)}
for row in relation_matrix(rel, [1, 2, 3, 4]):
    print(row)
# Expected output:
# [1, 1, 1, 1]
# [0, 1, 0, 1]
# [0, 0, 1, 0]
# [0, 0, 0, 1]

The printed matrix matches the "divides on $\{1,2,3,4\}$" matrix above, row for row — a good sanity check that our conversion is faithful.

🔄 Check Your Understanding 1. In the adjacency matrix of a relation on an $n$-element set, what does an all-zero row tell you about the corresponding element? 2. A relation has a self-loop on every node of its digraph. What does its matrix look like along the main diagonal? 3. If a relation has $k$ pairs on a set of size $n$, how many $1$s and how many $0$s are in its matrix?

Answers

1. The element is related to nothing — it appears as the first coordinate of no pair. (For "divides" that never happens, since every number divides at least itself.)
2. The main diagonal is all $1$s.
3. Exactly $k$ ones (one per pair) and $n^2 - k$ zeros.

12.3 Properties of relations

This is the heart of the chapter. A relation is just a set of pairs, but the patterns in that set determine everything we can do with it. Four properties carve up the world of relations, and almost every named structure later in the book (orders, equivalences, graphs, congruences) is defined by some combination of them.

Throughout, let $R$ be a relation on a set $A$ (same set on both sides — that is the case where these properties make sense).

Reflexive

Definition (reflexive). $R$ is reflexive if every element is related to itself: $$\forall a \in A,\ (a, a) \in R.$$

"Divides" is reflexive on the positive integers, because $a \mid a$ for every $a$. "$\le$" is reflexive ($a \le a$). "$<$" is not reflexive — $a < a$ is never true. In the digraph, reflexive means every node has a self-loop; in the matrix, it means the main diagonal is all $1$s.

⚠️ Common Pitfall: Reflexivity requires the loop on every element, no exceptions. A relation with self-loops on some elements but not all is neither reflexive nor (necessarily) anything special — it is called non-reflexive, and the failure of even one $(a,a)$ is enough to disqualify it. Always check the universally-quantified statement, not a few examples.

Symmetric

Definition (symmetric). $R$ is symmetric if relatedness always runs both ways: $$\forall a, b \in A,\ (a, b) \in R \rightarrow (b, a) \in R.$$

"Has the same birthday as" is symmetric. "Is a sibling of" is symmetric. "Follows" on a social network is not symmetric in general — you can follow someone who does not follow you back. In the digraph, symmetric means every arrow has a matching arrow in the opposite direction (so you may as well draw undirected edges); in the matrix, it means $M_{ij} = M_{ji}$ for all $i, j$ — the matrix equals its own transpose, symmetric across the main diagonal.

Antisymmetric

Symmetry's opposite is subtler than "arrows never come in pairs." It says the only way to have arrows both ways is the trivial self-loop case.

Definition (antisymmetric). $R$ is antisymmetric if $$\forall a, b \in A,\ \big((a, b) \in R \ \land\ (b, a) \in R\big) \rightarrow a = b.$$

Equivalently: if $a \ne b$, you cannot have both $(a,b)$ and $(b,a)$. "Divides" on the positive integers is antisymmetric: if $a \mid b$ and $b \mid a$ then $a = b$. "$\le$" is antisymmetric ($a \le b$ and $b \le a$ force $a = b$). This property is what makes a relation behave like an ordering, and it is the linchpin of Chapter 13's partial orders.

⚠️ Common Pitfall: Antisymmetric is not the same as "not symmetric." They are different ideas living on different axes. A relation can be: - both symmetric and antisymmetric (e.g., the equality relation $\{(a,a) \mid a \in A\}$ — every arrow is a self-loop, so both conditions hold vacuously for distinct elements); - neither (e.g., $\{(1,2), (2,1), (2,3)\}$ on $\{1,2,3\}$ — the $(2,3)$ with no $(3,2)$ kills symmetry, and the $(1,2),(2,1)$ pair with $1 \ne 2$ kills antisymmetry); - exactly one of the two.

"Symmetric" and "antisymmetric" are not negations of each other. Read each definition literally.

Transitive

Definition (transitive). $R$ is transitive if relatedness chains: $$\forall a, b, c \in A,\ \big((a, b) \in R \ \land\ (b, c) \in R\big) \rightarrow (a, c) \in R.$$

"Divides" is transitive: if $a \mid b$ and $b \mid c$ then $a \mid c$. "$<$" is transitive. "Is an ancestor of" is transitive. "Is the parent of" is not transitive — your grandparent is not your parent. In the digraph, transitive means every two-step path has a one-step shortcut: whenever you can go $a \to b \to c$, there is already a direct arrow $a \to c$. That picture is exactly why "transitive closure" (12.5) means "add the shortcuts until no two-step path lacks one."

💡 Intuition: Three of the four properties are about a single missing arrow you can check for: reflexive (is the self-loop there?), symmetric (is the reverse arrow there?), transitive (is the shortcut there?). Antisymmetric is the odd one out — it forbids a configuration rather than requiring one. Keeping that asymmetry in mind stops you from conflating the four.

A worked classification

Let's classify a relation completely, stating the strategy before each verdict.

Claim. Let $R = \{(a, b) \mid a \equiv b \pmod 3\}$ on $A = \{0, 1, 2, 3, 4, 5\}$ — "$a$ and $b$ leave the same remainder when divided by 3." Then $R$ is reflexive, symmetric, and transitive, but not antisymmetric.

The strategy first. For each property we check its defining condition directly against the definition of congruence mod 3. Recall (from Chapter 4's divisibility groundwork) that $a \equiv b \pmod 3$ means $3 \mid (a - b)$; we will unpack that into "$a - b = 3k$ for some integer $k$" whenever we need to do algebra, exactly the unpack-do-algebra-repackage move from the proof chapters.

Reflexive. For any $a$, $a - a = 0 = 3 \cdot 0$, so $3 \mid (a - a)$, i.e. $a \equiv a \pmod 3$. Thus $(a, a) \in R$ for all $a$. Reflexive. ✓

Symmetric. Suppose $(a, b) \in R$, so $3 \mid (a - b)$, say $a - b = 3k$. Then $b - a = 3(-k)$, so $3 \mid (b - a)$ and $(b, a) \in R$. Symmetric. ✓

Transitive. Suppose $(a, b) \in R$ and $(b, c) \in R$, so $a - b = 3k$ and $b - c = 3m$ for integers $k, m$. Adding, $a - c = (a - b) + (b - c) = 3k + 3m = 3(k + m)$, so $3 \mid (a - c)$ and $(a, c) \in R$. Transitive. ✓

Antisymmetric? We look for a counterexample (Chapter 2's tool for killing a universal claim). Take $a = 0, b = 3$. Then $0 \equiv 3 \pmod 3$ and $3 \equiv 0 \pmod 3$, so both $(0, 3)$ and $(3, 0)$ are in $R$, yet $0 \ne 3$. The antisymmetry condition is violated. Not antisymmetric. ✗ $\blacksquare$

A relation that is reflexive, symmetric, and transitive — like this one — has a special name and is the subject of the next section. But first, let's automate the checking.

def is_reflexive(R, A):
    return all((a, a) in R for a in A)

def is_symmetric(R):
    return all((b, a) in R for (a, b) in R)

def is_transitive(R):
    return all((a, c) in R for (a, b) in R for (x, c) in R if b == x)

A = {0, 1, 2, 3, 4, 5}
R = {(a, b) for a in A for b in A if (a - b) % 3 == 0}
print(is_reflexive(R, A), is_symmetric(R), is_transitive(R))
# Expected output:
# True True True

Each function is a near-transcription of its definition. is_reflexive checks $(a,a) \in R$ for all $a$; is_symmetric checks the reverse pair exists for every pair; is_transitive checks the shortcut exists for every two-step chain (the if b == x finds the chains $a\,R\,b$ and $b\,R\,c$). This is theme four in miniature: the code tests the claim on a finite set, the proof above guarantees it for all of $\mathbb{Z}$.

🐛 Find the Error. A student writes a faster transitivity check: python def is_transitive_buggy(R): return all((a, c) in R for (a, b) in R for (b, c) in R) hoping the repeated name b will "match up" the two pairs. What does this actually compute, and why is it wrong?

Answer

In a Python generator, the inner (b, c) rebinds b — it does not constrain the inner loop to pairs whose first element equals the outer b. The code iterates over all pairs (a, b) and, for each, over all pairs (b, c) (with b overwritten), so it checks (a, c) in R for the outer a and the inner c across every combination — not the transitivity condition at all. The correct version must use two different names and an explicit if b == x guard (as in is_transitive above), or iterate with an explicit equality test. This is a genuinely common bug: a repeated comprehension variable shadows, it does not unify.

🔄 Check Your Understanding 1. Classify "$\le$" on $\mathbb{Z}$: which of the four properties does it have? 2. Classify "is a sibling of" (sharing at least one parent, and not counting yourself): reflexive? symmetric? transitive? 3. Give a relation on $\{1, 2, 3\}$ that is symmetric but not transitive.

Answers

1. Reflexive ($a \le a$), antisymmetric ($a \le b \land b \le a \Rightarrow a = b$), transitive ($a \le b \le c \Rightarrow a \le c$); not symmetric ($1 \le 2$ but $2 \not\le 1$). This combination — reflexive, antisymmetric, transitive — is a partial order (Chapter 13).
2. Not reflexive (you are not your own sibling, by the stipulation). Symmetric (if A is B's sibling, B is A's). Not transitive in general: half-siblings can break it — A and B share a mother, B and C share a father, but A and C may share no parent.
3. For example $\{(1,2), (2,1), (2,3), (3,2)\}$: symmetric (every arrow has its reverse) but not transitive ($(1,2)$ and $(2,3)$ but no $(1,3)$).

12.4 Equivalence relations and partitions

The congruence-mod-3 relation in 12.3 turned out to be reflexive, symmetric, and transitive. That trio is so important it gets its own name, because it captures the idea of sameness for some purpose.

Definition (equivalence relation). A relation $R$ on a set $A$ is an equivalence relation if it is reflexive, symmetric, and transitive.

Why those three and not others? Think about what "is the same as, for purposes of X" should mean:

• everything is the same as itself (reflexive),
• if $a$ is the same as $b$, then $b$ is the same as $a$ (symmetric),
• if $a$ is the same as $b$ and $b$ is the same as $c$, then $a$ is the same as $c$ (transitive).

Those are exactly the rules ordinary equality obeys. An equivalence relation is a generalized equality: it declares certain elements interchangeable for the purpose at hand, even when they are not literally identical. "Has the same remainder mod 12" makes 1 o'clock and 13 o'clock interchangeable on a clock face. "Has the same hash" makes two keys interchangeable for bucket selection. "Is anagram of" makes "listen" and "silent" interchangeable for a word puzzle.

Equivalence classes

Once you declare some elements interchangeable, they clump together. The clump containing a given element is its equivalence class.

Definition (equivalence class). Let $R$ be an equivalence relation on $A$ and let $a \in A$. The equivalence class of $a$ is the set of everything related to $a$: $$[a] = \{x \in A \mid (a, x) \in R\}.$$ Any element of a class is called a representative of that class.

For congruence mod 3 on $\{0, 1, 2, 3, 4, 5\}$:

$$[0] = \{0, 3\}, \quad [1] = \{1, 4\}, \quad [2] = \{2, 5\}.$$

And notice $[3] = \{0, 3\} = [0]$: the class of 3 is the same set as the class of 0, because 0 and 3 are related. Different representatives, same class. There are really only three distinct classes, and together they account for every element of $\{0,1,2,3,4,5\}$ with no overlaps. That "carve the set into non-overlapping, exhaustive clumps" behavior is the whole point, and it has a name.

Partitions

Definition (partition). A partition of a set $A$ is a collection of non-empty subsets of $A$ (called blocks or cells) that are pairwise disjoint (no two share an element) and whose union is all of $A$ (every element is in some block). Formally, a partition is a set ${B_1, B_2, \dots}$ of non-empty subsets with $B_i \cap B_j = \emptyset$ for $i \ne j$ and $\bigcup_i B_i = A$.

The classes $\{0,3\}, \{1,4\}, \{2,5\}$ form a partition of $\{0,1,2,3,4,5\}$: none is empty, no two overlap, and together they cover everything. This is not a coincidence — it is a theorem, and it is the most important structural fact in the chapter.

🚪 Threshold Concept: equivalence relations are partitions. These look like two different ideas — one is a set of pairs satisfying three axioms, the other is a way of slicing a set into blocks. They are secretly the same idea. Every equivalence relation chops its set into the partition of its classes; every partition arises from exactly one equivalence relation (relate two elements iff they share a block). Once you see this, you will start noticing equivalence relations as partitions everywhere: hash buckets, connected components of a graph (Chapter 28), strongly-connected components, "same type" in a type system, "same orbit" under a symmetry. Whenever you sort things into bins where bin-membership is "all or nothing," an equivalence relation is hiding underneath.

Let's prove the half that does the real work: an equivalence relation's classes form a partition.

The strategy first. A partition needs three things: blocks non-empty, blocks cover $A$, blocks pairwise disjoint. Non-emptiness and covering are quick — they fall straight out of reflexivity. The real content is disjointness, and the honest way to prove "disjoint" for equivalence classes is to prove the contrapositive-flavored statement: if two classes overlap at all, they are identical. That reduces "disjoint or equal" to a clean set-equality argument that leans on symmetry and transitivity.

Theorem. Let $R$ be an equivalence relation on a non-empty set $A$. Then the set of equivalence classes $\{[a] \mid a \in A\}$ is a partition of $A$.

Proof. We verify the three defining conditions of a partition.

Each class is non-empty, and the classes cover $A$. Fix any $a \in A$. By reflexivity $(a, a) \in R$, so $a \in [a]$. Thus every class contains its own representative (non-empty), and every element $a$ lies in some class, namely $[a]$ (covering). So $\bigcup_{a \in A} [a] = A$.

Any two classes are equal or disjoint. We show: for $a, b \in A$, if $[a] \cap [b] \ne \emptyset$ then $[a] = [b]$. Suppose the classes share an element $c$, so $c \in [a]$ and $c \in [b]$; that means $(a, c) \in R$ and $(b, c) \in R$. We prove $[a] = [b]$ by showing each is a subset of the other.

Take any $x \in [a]$, so $(a, x) \in R$. We have $(b, c) \in R$ and, by symmetry on $(a,c) \in R$, also $(c, a) \in R$. Chain them with transitivity: from $(b, c)$ and $(c, a)$ we get $(b, a) \in R$, and then from $(b, a)$ and $(a, x)$ we get $(b, x) \in R$. Hence $x \in [b]$. This shows $[a] \subseteq [b]$. The reverse inclusion $[b] \subseteq [a]$ is identical with the roles of $a$ and $b$ swapped. Therefore $[a] = [b]$.

So distinct classes cannot partially overlap: any two are either the same set or share nothing. Combined with non-emptiness and covering, the classes form a partition of $A$. $\blacksquare$

The converse — every partition defines an equivalence relation — is the easier direction, and we state it so you have the full correspondence.

Theorem (converse). Let $P = \{B_1, B_2, \dots\}$ be a partition of $A$. Define $R$ by $(a, b) \in R$ iff $a$ and $b$ lie in the same block. Then $R$ is an equivalence relation, and its classes are exactly the blocks of $P$.

The strategy first (sketch). Reflexive: every $a$ is in its own block with itself. Symmetric: "same block" does not care about order. Transitive: if $a, b$ share a block and $b, c$ share a block, then since blocks are disjoint that block is the same block, so $a, c$ share it. (Filling in this sketch is a Deep Dive exercise.)

Putting the two theorems together gives the threshold concept its precise form: there is a one-to-one correspondence (a bijection) between equivalence relations on $A$ and partitions of $A$. Choosing one is choosing the other.

Computing classes in code

Given an equivalence relation as a set of pairs, the classes are straightforward to recover: each class is the set of everything related to a chosen representative.

def equivalence_classes(R, A):
    """Distinct equivalence classes of an equivalence relation R on A."""
    seen, classes = set(), []
    for a in sorted(A):
        if a in seen:
            continue
        cls = {x for x in A if (a, x) in R}   # everything related to a
        classes.append(cls)
        seen |= cls
    return classes

A = {0, 1, 2, 3, 4, 5}
R = {(a, b) for a in A for b in A if (a - b) % 3 == 0}
print(equivalence_classes(R, A))
# Expected output:
# [{0, 3}, {1, 4}, {2, 5}]

We walk elements in order; the first time we meet an element not yet placed, we form its class $\{x \mid (a,x) \in R\}$ and mark all of them seen. Because the classes partition $A$ (the theorem we just proved!), this visits each class exactly once and never produces an overlap — the correctness of the code rests on the theorem.

🔄 Check Your Understanding 1. How many equivalence classes does "congruent mod $n$" have on the integers? Name them. 2. Is the relation "$a$ and $b$ differ by at most 1" (i.e. $|a - b| \le 1$) on $\{1,2,3,4\}$ an equivalence relation? If not, which property fails? 3. A partition of a 4-element set has blocks $\{1,2\}$ and $\{3,4\}$. Write the corresponding equivalence relation as a set of pairs.

Answers

1. Exactly $n$ classes, the residue classes $[0], [1], \dots, [n-1]$ — grouped by remainder on division by $n$. (These are the elements of $\mathbb{Z}_n$.)
2. No. It is reflexive and symmetric but not transitive: $1$ relates to $2$ and $2$ relates to $3$ (each differs by 1), but $1$ and $3$ differ by 2, so $(1,3)$ is missing.
3. $\{(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4)\}$ — within-block pairs only, both directions and self-loops included.

12.5 Closures: adding the minimum to gain a property

Often you have a relation and want it to have a property it currently lacks. You do not want to throw pairs away (that would lose information); you want to add the fewest pairs needed so the property holds. The result is a closure.

Definition (closure with respect to a property). Given a relation $R$ on $A$ and a property $\Pi$ (reflexive, symmetric, or transitive), the $\Pi$-closure of $R$ is the smallest relation $S$ such that $R \subseteq S$ and $S$ has property $\Pi$. "Smallest" means: $S$ has property $\Pi$, contains $R$, and is contained in every relation that has property $\Pi$ and contains $R$.

The three basic closures, from easiest to most interesting:

• Reflexive closure. Add every missing self-loop. Formally $S = R \cup \{(a, a) \mid a \in A\}$. You simply union in the diagonal.
• Symmetric closure. Add the reverse of every pair. Formally $S = R \cup {(b, a) \mid (a, b) \in R}$. You union in the transpose.
• Transitive closure. Add a shortcut for every multi-step path — and keep going, because adding shortcuts can create new multi-step paths that need their own shortcuts. This one is the headline.

Why transitive closure is the interesting one

Reflexive and symmetric closure each take a single pass: you know in advance exactly which pairs to add. Transitive closure is different because it can cascade. Consider the "parent of" relation $R = \{(a, b), (b, c), (c, d)\}$ — a chain $a \to b \to c \to d$. To make it transitive:

• The path $a \to b \to c$ demands $(a, c)$.
• The path $b \to c \to d$ demands $(b, d)$.
• Now $(a, c)$ and $(c, d)$ form a new path demanding $(a, d)$.

The transitive closure of "parent of" is "ancestor of": $a$ is an ancestor of everyone downstream, not just its child. In a graph, the transitive closure answers reachability: $(a, b)$ is in the transitive closure exactly when there is a path (of length $\ge 1$) from $a$ to $b$. That is why this operation matters far beyond relations: "can package A's build reach package B as a dependency?", "is node X reachable from node Y?", "does this import chain eventually pull in that module?" are all transitive-closure questions.

💡 Intuition: Picture the digraph. The transitive closure is the digraph you would draw if, for every place you can walk to by following arrows, you also drew a single direct arrow. Closures only ever add arrows; they never remove. And "smallest" means you add exactly the reachability arrows and nothing gratuitous.

Computing transitive closure

One clean way to compute it: keep adding shortcut pairs until a full pass adds nothing new. Each pass looks for a two-step path $a \to b \to c$ whose shortcut $(a, c)$ is missing, and adds it. Because the set of possible pairs is finite ($n^2$ of them), the process must stop.

def closure_transitive(R):
    """Smallest transitive relation containing R (reachability via paths)."""
    S = set(R)
    changed = True
    while changed:                      # repeat until a full pass adds nothing
        changed = False
        new = {(a, c) for (a, b) in S for (x, c) in S if b == x}
        if not new <= S:                # some shortcut is still missing
            S |= new
            changed = True
    return S

print(sorted(closure_transitive({(1, 2), (2, 3), (3, 4)})))
# Expected output:
# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

Trace the cascade by hand. We start with the chain $1 \to 2 \to 3 \to 4$. The first pass finds the two-step shortcuts $(1,3)$ and $(2,4)$ and adds them. Now $(1,3)$ and $(3,4)$ chain, so the second pass finds $(1,4)$ and adds it. The third pass finds nothing new, so we stop. The result is every pair $(i, j)$ with $i < j$ — exactly the reachability relation of the chain, all six pairs. The loop is doing, by brute force, what the cascade demands.

🔗 Connection. There is a famously elegant $O(n^3)$ algorithm for this — Warshall's algorithm — that fills in reachability with three nested loops over the adjacency matrix, and it is a close cousin of the all-pairs shortest-path algorithm you will meet in Chapter 29 (Floyd–Warshall). Our pass-until- stable version is simpler to understand and prove terminating; Warshall's is what you would use in production. Implementing and comparing them is a Deep Dive exercise.

⚠️ Common Pitfall: "Transitive closure" is not "make it an equivalence relation." Transitive closure adds only shortcuts; it does not add self-loops (reflexivity) or reverse arrows (symmetry). If you want the smallest equivalence relation containing $R$ — sometimes called the equivalence closure — you must take the reflexive, symmetric, and transitive closure together. Order matters less than you might fear, but you do need all three.

🔄 Check Your Understanding 1. What is the symmetric closure of the "follows" relation on a social network, in plain English? 2. The transitive closure of $\{(1,2),(2,1)\}$ on $\{1,2\}$ — what pairs does it contain, and is the result reflexive? 3. True or false: adding pairs to make a relation transitive can never break transitivity, so a single pass of "add all missing shortcuts" always suffices.

Answers

1. "Follows or is followed by" — the mutual-or-one-way connection relation; an arrow becomes an undirected link. (This is exactly how you would turn a directed follower graph into an undirected "connections" graph.)
2. $(1,2),(2,1)$ chain to give $(1,1)$, and $(2,1),(1,2)$ give $(2,2)$. So the closure is $\{(1,1),(1,2),(2,1),(2,2)\}$ — all four pairs. It is reflexive here, but only as a side effect of the back-and-forth arrows; transitive closure does not add self-loops in general.
3. False. As the chain example showed, adding shortcuts can create new two-step paths needing their own shortcuts, so one pass is not always enough — you must iterate until a pass adds nothing.

12.6 Relations in databases: the relational model

We opened with the claim that a database table is a relation. Now we can make that precise and see why the math pays rent. In 1970, E. F. Codd proposed organizing data not as linked records but as relations in the mathematical sense — and the entire relational-database industry (SQL, PostgreSQL, SQLite, every system with SELECT and JOIN) grew from that one abstraction. This is theme one of the book — discrete math is the language of CS — stated as plainly as it ever gets.

Tables as relations

A table with columns $C_1, C_2, \dots, C_k$ is a subset of the Cartesian product of the columns' domains:

$$T \subseteq D_1 \times D_2 \times \cdots \times D_k,$$

where $D_i$ is the set of allowed values for column $C_i$. Each row is a $k$-tuple, an element of that product; the table is the set of rows currently present. (Real SQL tables can contain duplicate rows and are technically multisets, and they fix a column order; the pure relational model uses true sets with named columns. The mathematical idealization is a relation, and it is close enough that the intuition transfers directly.)

So a two-column table is exactly a binary relation, and a $k$-column table is a $k$-ary relation — the same idea with $k$ slots instead of 2. Our enrollment table $E$ from 12.1 was a binary relation; add a grade column and it becomes a ternary relation $\subseteq S \times C \times G$.

Operations as set operations

Once tables are relations, the query operations are operations on sets — many of them ones you already know from Chapter 8:

A JOIN is the standout. To join enrollment $E(\text{student}, \text{course})$ with a course catalog $\text{Cat}(\text{course}, \text{title})$ on the shared course column, you conceptually form the Cartesian product $E \times \text{Cat}$ (all pairs of rows) and then select the combinations where the two course values agree. The result relates each student to the titles of their courses. Every join you have ever written is "Cartesian product, then keep the rows that match" — a product followed by a selection, both pure relation operations.

💡 Intuition: This is why a careless join "explodes." A CROSS JOIN of an $m$-row table and an $n$-row table has $m \times n$ rows — the literal size of the Cartesian product. A real join is that product filtered down by the ON condition. If your ON condition is missing or wrong, you get the raw product, which is why a forgotten join condition can turn two thousand-row tables into a million-row result. The Cartesian product is not an analogy here; it is what the engine computes.

Keys, in relational terms

A key of a table is a set of columns whose values uniquely identify a row — no two rows agree on all the key columns. In our terms, the key is the set of columns on which the "projection to those columns" is injective (Chapter 9): distinct rows project to distinct key-tuples. A UNIQUE or PRIMARY KEY constraint is the database enforcing that injectivity for you. When you puzzled over why a primary key forbids duplicates, the answer is: it is asserting that one specific projection of the relation is an injection.

🔗 Connection. Notice how much of this chapter and the last two just paid off at once: tables are subsets of Cartesian products (Chapter 8), rows are tuples (Chapter 8), keys are injective projections (Chapter 9), and the query algebra is set operations (Chapter 8) plus selection. The relational model is not "inspired by" discrete math — it is discrete math, deployed. That is the payoff abstraction promises.

Let's model a tiny join from scratch, to make the "product then select" story literal:

def join_on_course(enroll, catalog):
    """Inner join of enroll(student, course) and catalog(course, title) on course.
    Mirrors: take the Cartesian product, then SELECT the matching rows."""
    return {(s, c1, title)
            for (s, c1) in enroll          # each row of the left relation
            for (c2, title) in catalog      # paired with each row of the right (the product)
            if c1 == c2}                    # selection: keep where course columns agree

enroll = {("Ana", "CS101"), ("Ben", "CS101"), ("Cleo", "PHIL150")}
catalog = {("CS101", "Intro to CS"), ("PHIL150", "Logic")}
for row in sorted(join_on_course(enroll, catalog)):
    print(row)
# Expected output:
# ('Ana', 'CS101', 'Intro to CS')
# ('Ben', 'CS101', 'Intro to CS')
# ('Cleo', 'PHIL150', 'Logic')

The comprehension is the relational definition made executable: the two for clauses generate the Cartesian product of the two relations, and the if c1 == c2 is the selection that keeps only matching rows. Cleo's PHIL150 matched the Logic catalog row; everyone got their course title attached. That is a JOIN, and underneath SQL's syntax, that is what the database does.

🔄 Check Your Understanding 1. A table has columns (order_id, product, qty). Which single column is the natural key, and what does "it is a key" assert in the projection language? 2. In relational terms, what is the difference between SELECT name FROM users and SELECT * FROM users WHERE age > 18? 3. Two tables have 100 and 50 rows. What is the maximum possible number of rows in their join on a shared column, and when is that maximum reached?

Answers

1. order_id is the natural key; "it is a key" asserts that the projection of the table onto the order_id column is injective — distinct rows have distinct order_ids.
2. SELECT name is a projection (keep only the name column of every tuple); WHERE age > 18 is a selection (keep only the tuples satisfying the predicate, all columns intact). Projection cuts columns; selection cuts rows.
3. At most $100 \times 50 = 5000$ rows — the size of the full Cartesian product — reached only if every row of one matches every row of the other on the join column (e.g., they all share one value). A selective join condition yields far fewer.

Project Checkpoint: relations.py — equivalence testing and transitive closure

It is time to start the relations.py module of our dmtoolkit. This chapter contributes two of its three core functions; Chapter 13 will add topo_sort once we have partial orders to sort by. Per the Toolkit's frozen API, we add is_equivalence(rel, dom) and closure_transitive(rel).

Create dmtoolkit/relations.py and add:

def is_equivalence(rel, dom):
    """True iff rel is reflexive, symmetric, and transitive on domain dom.
    rel is a set of (a, b) tuples; dom is the underlying set of elements."""
    reflexive = all((a, a) in rel for a in dom)
    symmetric = all((b, a) in rel for (a, b) in rel)
    transitive = all((a, c) in rel
                     for (a, b) in rel for (x, c) in rel if b == x)
    return reflexive and symmetric and transitive


def closure_transitive(rel):
    """Smallest transitive relation containing rel (reachability via paths)."""
    S = set(rel)
    while True:
        new = {(a, c) for (a, b) in S for (x, c) in S if b == x}
        if new <= S:                 # a full pass added nothing -> stable
            return S
        S |= new


if __name__ == "__main__":
    dom = {0, 1, 2, 3, 4, 5}
    cong3 = {(a, b) for a in dom for b in dom if (a - b) % 3 == 0}
    print(is_equivalence(cong3, dom))                 # congruence mod 3
    print(is_equivalence({(0, 1)}, {0, 1}))           # missing reflexive/symmetric
    print(sorted(closure_transitive({(1, 2), (2, 3), (3, 4)})))
    # Expected output:
    # True
    # False
    # [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

Both functions are direct transcriptions of this chapter's definitions: is_equivalence checks the three axioms (using the two-name-plus-if b == x idiom that the Find-the-Error box warned us about), and closure_transitive iterates "add all missing shortcuts" until a pass is stable, which we argued must terminate because there are only $n^2$ possible pairs. The first call confirms congruence mod 3 is an equivalence relation; the second shows a relation that fails (it is neither reflexive nor symmetric on $\{0,1\}$); the third reproduces the chain-reachability cascade by hand-trace.

How this builds toward the capstone: transitive closure is reachability, and reachability is the backbone of the graph algorithms in Part V — connectivity, components, and the social-network analysis of capstone Track B all stand on it. is_equivalence underlies "same-bucket" reasoning (hashing, components, congruence classes) that recurs through number theory and graphs. Next chapter we complete the module with topo_sort, turning relations.py into a small but real foundation the later chapters build on directly.

Toolkit so far: logic.py (Ch. 1–3), recurrences.py begun (Ch. 6), sets.py (Ch. 8), and now relations.py with is_equivalence and closure_transitive. The package is starting to compose: the set operations from Chapter 8 are exactly what selection and join used above.

Summary

A relation from $A$ to $B$ is a subset $R \subseteq A \times B$; we write $a\,R\,b$ for $(a,b) \in R$. A relation on $A$ has $A$ on both sides. Functions are the special relations where every input appears in exactly one pair.

Three representations (convert freely):

Four properties of a relation on $A$ (all quantified over the whole set):

• Symmetric and antisymmetric are not opposites; a relation can be both, neither, or one.

Equivalence relations and partitions (the threshold concept):

• An equivalence relation is reflexive + symmetric + transitive — a generalized equality.
• The equivalence class $[a] = \{x \mid (a,x) \in R\}$; any element is a representative.
• Theorem: the classes of an equivalence relation form a partition (non-empty, disjoint, covering); conversely every partition defines an equivalence relation. The two notions are in bijection.

Closures (smallest superset with a property):

• Transitive closure $=$ reachability in the digraph. Compute by adding missing shortcuts until a pass changes nothing (terminates because only $n^2$ pairs exist). Warshall's algorithm does it in $O(n^3)$.

Relations in databases: a $k$-column table is a $k$-ary relation $\subseteq D_1 \times \cdots \times D_k$; `WHERE` is selection, `SELECT col` is projection, set operators are $\cup/\cap/\setminus$, and a JOIN is a Cartesian product followed by a selection. A key is a column set whose projection is injective.

Spaced Review

Retrieval keeps knowledge available. Answer from memory before checking.

1. (Ch. 8) A relation on a set $A$ is a subset of which set? State it using the Cartesian-product notation from Chapter 8, and say how many pairs are in that set when $|A| = n$.
2. (Ch. 8) Selection (WHERE) and the set operations UNION/INTERSECT/EXCEPT correspond to which Chapter 8 operations? Match each.
3. (Ch. 9) Every function is a relation, but not conversely. State the exact extra condition a relation $R \subseteq A \times B$ must satisfy to be a function $f\colon A \to B$.
4. (Ch. 9) A database key is a set of columns whose projection is injective. Recall the Chapter 9 definition of injective and explain why "no two rows share a key value" is the same statement.

Answers

1. A subset of the Cartesian product $A \times A$. Since $|A \times A| = n^2$, there are $n^2$ possible pairs (and so $2^{n^2}$ possible relations on $A$).
2. WHERE (selection) keeps a subset of rows; UNION $= \cup$, INTERSECT $= \cap$, EXCEPT $= \setminus$ (set difference) — all directly from Chapter 8 (§8.3).
3. For every $a \in A$ there is exactly one $b \in B$ with $(a, b) \in R$ (total and single-valued). Relations allow zero or many; functions demand exactly one.
4. Injective means distinct inputs map to distinct outputs: $x \ne y \Rightarrow f(x) \ne f(y)$. Reading "row" as input and "key value" as output, injectivity says distinct rows have distinct key values — i.e., no two rows share a key value. Same statement.

What's Next

We have met the four properties, but only one combination so far — reflexive + symmetric + transitive, the equivalence relations that slice a set into equal-rank buckets. Swap symmetry for antisymmetry and you get the other great family: reflexive + antisymmetric + transitive, the partial orders. Where equivalence relations say "these are the same," partial orders say "this comes before that" — and they model dependency, precedence, and hierarchy: which tasks must finish before which, which version supersedes which, how make decides build order. Chapter 13 develops partial orders and their Hasse diagrams, finds the special "all-pairs-comparable" total orders inside them, builds the lattices that sit underneath Boolean algebra and logic, and uses an order to topologically sort a dependency graph — the third function our relations.py module is waiting for.