COMP233 · Chapter 8 Interactive Companion

Relations

What a relation is and the three ways to picture it; the core properties (reflexive, symmetric, transitive); closures; and equivalence relations with their classes and partitions. Sections 8.1–8.3.
Back to COMP233

About this chapter

A relation records which things are connected to which. “Is less than”, “divides”, “has the same remainder as”, “is a friend of”, “is a prerequisite of” — each is simply a set of ordered pairs. It is the same raw material as Chapter 7: a function is a special relation (every input related to exactly one output), so here we drop that restriction and study connection in full generality. Relations are the backbone of databases, graphs, equality up to a rule, and modular arithmetic.

The thread. Section 8.1 defines a relation and gives three equivalent pictures — the arrow diagram, the 0/1 matrix, and the directed graph — plus domain, range, inverse and complement. Section 8.2 asks three yes/no questions about a relation on one set — reflexive, symmetric, transitive — shows what each looks like in the graph, and how to prove and disprove them; then it builds the smallest fix, the closure. Section 8.3 combines all three into an equivalence relation, the exact idea of “being the same in some respect”, which cuts a set cleanly into classes.

Section 8.1Relations on sets

Definition · relation
A relation R from a set A to a set B is a subset of the Cartesian product A × B. We write x R y (“x is related to y”) for (x, y) ∈ R, and x ⅀ y for (x, y) ∉ R. When B = A it is a relation on A.

That one line is the whole idea: a relation is a chosen set of ordered pairs. Chapter 6 built A × B (every possible pair); a relation simply selects the pairs you care about. Because it is a set, the language of sets — subset, union, intersection, complement — transfers to relations directly.

  • The domain of R is the set of x appearing as a first coordinate; the range is the set of y appearing as a second coordinate.
  • How big can a relation be? On a set of size n there are n² possible pairs, so there are 2n² different relations — one per subset of A × A.
  • A relation generalises a function. A function f : A → B is exactly a relation in which every x ∈ A appears as a first coordinate exactly once. Relations relax that: an x may relate to many elements, or to none.

8.1.1 The three pictures — arrow diagram, matrix, and the relation itself

A relation from A to B can be drawn as an arrow diagram (an arrow x → y for every pair) or written as a 0/1 matrix (a 1 in row x, column y exactly when x R y). Enter A, B and the pairs and watch all three update together. This is the picture behind Examples 8.1.1–8.1.2.
Arrow diagram — every related pair is an arrow from A to B.
Matrix — a 1 marks each related pair (green = related).

8.1.2 Directed graph of a relation on a set

When a relation is on one set, the sharpest picture is a directed graph: one node per element and an arrow x → y for each pair. A pair (x, x) is a self-loop; a mutual pair (x, y) and (y, x) shows as two arrows curving opposite ways. The three properties of Section 8.2 each have an obvious look here, which is why this picture is worth getting comfortable with now.
arrow x→y element of A a loop on a node is a pair (x, x)

8.1.3 Standard relations — see the famous ones

The relations you meet again and again are defined by a rule, not a list. Pick one on {1, …, n}; the tool generates its pairs, draws the graph, builds the matrix, and reports the three properties at a glance — so you can feel why “divides” is a partial order while “congruence” is an equivalence relation. (Examples 8.1.3–8.1.4 and the §8.2 examples.)
Directed graph (shown for n ≤ 8).
Matrix — the diagonal shows reflexivity at a glance.
Inverse, complement, and composition
INVERSE R⁻¹Reverse every arrow: R⁻¹ = {(y, x) : (x, y) ∈ R}. In the matrix this is the transpose. Inverse of < is >; inverse of “child of” is “parent of”.
COMPLEMENTThe pairs not in R: Rᶜ = (A × B) − R. Complement of ≤ is >; complement of = is ≠.
COMPOSITION S ∘ RChain two relations: x (S∘R) z iff there is a y with x R y and y S z — a two-step hop. This is exactly how transitivity is tested.

The 8.1.1 explorer prints R⁻¹ for whatever you type. A relation that satisfies R⁻¹ = R is precisely a symmetric one — the first hint that the next section’s properties are really statements about this algebra of relations.

Practice exercises · Section 8.1

Epp, 4th ed. §8.1: recommended 1, 2, 9, 10, 13, 15, 16. Try each on paper first, then reveal.
Exercise 8.1 A
Let A = {2, 3, 4}, B = {6, 8, 10}, and x R y ⇔ x | y. List R, give its domain and range, and write R⁻¹.
Test each pair: 2|6, 2|8, 2|10; 3|6; 4|8 — the rest fail. R = {(2,6),(2,8),(2,10),(3,6),(4,8)}. Domain = {2,3,4}, range = {6,8,10}. R⁻¹ = {(6,2),(8,2),(10,2),(6,3),(8,4)} — the relation “is a multiple of”, from B back to A.
Exercise 8.1 B
On A = {0,1,2,3} let x R y ⇔ 2 | (x + y). Find R and R⁻¹. What do you notice, and how many pairs would the relation have on {0,…,5}?
x+y is even iff x, y share parity. Evens {0,2}, odds {1,3}. R = all pairs inside {0,2} and inside {1,3} = {(0,0),(0,2),(2,0),(2,2),(1,1),(1,3),(3,1),(3,3)}. R⁻¹ = R — it is symmetric (in fact an equivalence relation, “same parity”). On {0,…,5} the blocks are {0,2,4} and {1,3,5}, giving 3² + 3² = 18 pairs.

Section 8.2Reflexivity, symmetry, and transitivity

For a relation on one set A, three properties come up everywhere. Each is a statement about all elements, so you prove it by arguing an arbitrary case and disprove it with a single counterexample. Crucially, each has a picture in the directed graph — learn the picture and the verdict becomes something you can see.

REFLEXIVE∀ x,   x R x
In the graph: a self-loop on every node. In the matrix: all-1 diagonal.
SYMMETRIC∀ x,y,   xRy ⇒ yRx
In the graph: every arrow has its reverse (all two-way). Matrix: symmetric across the diagonal.
TRANSITIVE∀ x,y,z,   xRy ∧ yRz ⇒ xRz
In the graph: every 2-step path has a 1-step shortcut.

The negations tell you exactly what a counterexample looks like — you only need one:

  • Not reflexive: some x with x ⅀ x (one missing self-loop).
  • Not symmetric: some x, y with x R y but y ⅀ x (a one-way arrow).
  • Not transitive: some x, y, z with x R y, y R z, but x ⅀ z (a broken shortcut).
Two traps worth naming
(1) Reflexive needs a loop on every element, not just somewhere. (2) The empty relation on a non-empty set is not reflexive (no loops), yet it is vacuously symmetric and transitive — there is no arrow to violate those. “No counterexample exists” counts as true.

8.2.1 Property checker — with the exact witness, drawn

Enter a relation on a set. The checker tests all three properties and, when one fails, names the witness and colours it on the graph: a node missing its self-loop turns red and dashed; a one-way arrow turns orange. Use the presets to see each shape, then edit freely.
normal arrow one-way (symmetry fails here) has self-loop missing self-loop
Presets: symmetric, not transitive · reflexive + transitive (≤) · transitive only (<) · equivalence relation
Proving and disproving — the templates
Template · prove transitive (congruence mod 3)
Claim: on Z, a R b ⇔ 3 | (a − b) is transitive.
Assume the hypotheses for arbitrary a, b, c: a R b and b R c. By definition a − b = 3s and b − c = 3t for some s, t ∈ Z.
Reach the conclusion: add them — a − c = 3s + 3t = 3(s + t) with s + t ∈ Z, so 3 | (a − c), i.e. a R c. ∎
Template · disprove with one counterexample
Claim to refute: “x R y ⇔ x | y on Z⁺ is symmetric.”
Exhibit one pair: 2 | 6 is true, but 6 | 2 is false. So 2 R 6 while 6 ⅀ 2 — symmetry fails. One witness is enough. ∎

The shape is always the same: to prove a “for all” property, start from an arbitrary case using the definition and derive the conclusion; to disprove it, produce a single concrete failure.

Two further properties (and where they lead)

Beyond the core three, two more properties are worth recognising — they are what turn “divides” and “≤” into orderings rather than equivalences:

ANTISYMMETRICx R y ∧ y R x ⇒ x = y
The only two-way links are self-loops. True of ≤ and |. (Not the opposite of symmetric.)
IRREFLEXIVE∀ x,   x ⅀ x
No self-loops at all. True of <. (Also not the opposite of reflexive — a relation can be neither.)

Reflexive + antisymmetric + transitive defines a partial order (Section 8.5); reflexive + symmetric + transitive defines an equivalence relation (Section 8.3, next). Same three slots, two famous combinations.

8.2.2 Closures — the smallest repair

The closure of R with respect to a property is the smallest relation containing R that has the property. Reflexive closure adds the missing self-loops; symmetric closure adds the missing reverse arrows; transitive closure keeps adding the missing shortcut (x, z) whenever x R y and y R z until nothing new appears (equivalently, x → … → z by some directed path). The tool lists exactly what each closure adds.

Practice exercises · Section 8.2

Epp, 4th ed. §8.2: recommended 2, 3, 10, 12, 13, 14, 15, 18. More in Taught solutions.
Exercise 8.2 A
On A = {1,2,3} let R = {(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)}. Which of reflexive / symmetric / transitive hold? Give a witness for any failure.
Reflexive: yes — all of (1,1),(2,2),(3,3) present. Symmetric: yes — (1,2)/(2,1) and (2,3)/(3,2) both appear. Transitive: no. (1,2) and (2,3) are present but (1,3) is missing. Witness x=1, y=2, z=3. (Paste it into 8.2.1 to see the broken shortcut.)
Exercise 8.2 B
Define R on Z by a R b ⇔ ab > 0. Decide reflexive / symmetric / transitive, watching the role of 0.
Reflexive: no — 0·0 = 0, not > 0, so 0 ⅀ 0. (It is reflexive on Z − {0}.) Symmetric: yes — ab > 0 ⇒ ba > 0. Transitive: yes — ab>0 means a,b share a sign; bc>0 means b,c share a sign; so a,c share a sign and ac>0. The domain decides the “reflexive” verdict.

Section 8.3Equivalence relations

Definition · equivalence relation & class
A relation on A is an equivalence relation if it is reflexive, symmetric, and transitive — all three at once. It formalises “the same in some respect”. For a ∈ A, the equivalence class of a is [a] = { x ∈ A : x R a } — everything related to a. Any member can name its class (a representative).

The reason equivalence relations matter so much is that they are exactly the tool for grouping: deduplicating records by a key, bucketing by a hash, identifying states in an automaton, reducing fractions (every fraction names one rational number, and “equals the same rational” is an equivalence relation). The grouping is never arbitrary — it is forced to be a clean split:

Theorem 8.3.1 / 8.3.4 · classes partition the set
If R is an equivalence relation on A, its distinct classes form a partition of A — every element lies in exactly one class. Conversely, any partition defines an equivalence relation (“in the same block”). So equivalence relations and partitions are the same data, seen two ways.
Why the classes partition — the three lemmas

The partition theorem rests on three short facts. They are worth seeing because they show where each of the three properties is used.

Lemma 1 · every element is in its own class
a ∈ [a], because a R a by reflexivity. So no class is empty, and the classes cover A.
Lemma 2 · related elements share a class
If a R b then [a] = [b]. Take x ∈ [a], so x R a; with a R b, transitivity gives x R b, i.e. x ∈ [b]. The reverse inclusion uses symmetry (b R a) the same way. Hence the two classes are equal.
Lemma 3 · classes are equal or disjoint
If [a] and [b] share any element x, then x R a and x R b, so (symmetry + transitivity) a R b, and by Lemma 2 [a] = [b]. So two classes never partly overlap — they coincide or miss entirely. ∎

Together: the classes are non-empty (Lemma 1), they cover A (Lemma 1), and any two are equal or disjoint (Lemma 3) — the definition of a partition.

8.3.1 Equivalence checker — classes colour-coded

Enter a relation on a set. The tool checks the three properties; if all hold, it is an equivalence relation and the tool computes the classes, colours them, and shows the partition — the same colours appear on the directed graph, so you can see each class as its own connected cluster. If a property fails, it names the witness instead.

8.3.2 Congruence mod n — the model example

The most important equivalence relation: a ≡ b (mod n) means n | (a − b), i.e. a and b leave the same remainder on division by n. It splits the integers into exactly n classes [0], …, [n−1]. The number line below is coloured by class, so the repeating pattern is visible; pick n and test any two integers.
Each colour is one residue class; the pattern repeats every n integers.

8.3.3 Partition ↔ relation — the two-way street

Enter a partition as blocks separated by |, each a space/comma list, e.g. 1 2 | 3 | 4 5. The tool builds the induced equivalence relation (“x ~ y iff same block”), colours the blocks, and confirms the three properties hold automatically — Theorem 8.3.4 made concrete.

Practice exercises · Section 8.3

Epp, 4th ed. §8.3: recommended 1, 9, 10, 15, 16, 24, 28, 30. More in Taught solutions.
Exercise 8.3 A
On A = {0,1,2,3,4,5} let a R b ⇔ 3 | (a − b). Show it is an equivalence relation and list the classes.
Reflexive: 3 | 0. Symmetric: 3 | (a−b) ⇒ 3 | (b−a). Transitive: add the multiples of 3 (template above). So it is an equivalence relation. Classes by remainder mod 3: [0]={0,3}, [1]={1,4}, [2]={2,5} — three blocks partitioning A.
Exercise 8.3 B
How many distinct classes does “a ≡ b (mod 5)” have on Z, and which integers form [2]?
Five, one per remainder: [0],[1],[2],[3],[4]. (More names exist — [5]=[0] — but five distinct classes.) [2] = { 5k + 2 : k ∈ Z } = {…,−8,−3,2,7,12,…}.

WorkedTaught solutions to recommended exercises

A selection from Epp’s recommended problems (4th ed.), solved in the style used in lecture. Attempt each on paper first.
§8.1 · a relation from its rule
On A = {1,2,3,4} define x R y ⇔ x + y is even. Write R and read off the three properties.
Same-parity pairs. Evens {2,4}, odds {1,3}: R = {(1,1),(1,3),(3,1),(3,3),(2,2),(2,4),(4,2),(4,4)}. Reflexive (a+a even), symmetric (x+y=y+x), transitive (same parity chains). An equivalence relation with classes {1,3} and {2,4}.
§8.2 · prove symmetric
On Z, a R b ⇔ 5 | (a − b). Prove symmetry.
Assume a R b: a − b = 5k, k ∈ Z. Then b − a = 5(−k) with −k ∈ Z, so 5 | (b − a), i.e. b R a. ∎
§8.2 · closure
On {a,b,c}, R = {(a,b),(b,c)}. Give the reflexive, symmetric, and transitive closures.
Reflexive closure: add (a,a),(b,b),(c,c). Symmetric closure: add (b,a),(c,b). Transitive closure: (a,b),(b,c) force (a,c); no further pair appears, so Rᵗ = {(a,b),(b,c),(a,c)}.
§8.3 · verify an equivalence relation
On all binary strings, s R t ⇔ same length. Show it is an equivalence relation and describe the classes.
This is “same value of the function length”. Reflexive / symmetric / transitive all hold because equality of lengths does. (In general, “f(x)=f(y)” for any function f is always an equivalence relation.) Classes: one per length — {ε}, {0,1}, {00,01,10,11}, …
§8.3 · classes of congruence
For congruence mod 4, list the four classes and decide whether −6 and 10 share a class.
[0]={…,−4,0,4,8,…}, [1], [2]={…,−2,2,6,10,…}, [3]. −6 = 4(−2)+2 and 10 = 4(2)+2 — both remainder 2, so same class [2]. Equivalently 4 | (10−(−6)) = 16. ✓
§8.3 · partition to relation
The partition of {1,2,3,4,5} into {1,4,5} and {2,3} induces which relation, and how many pairs?
“Same block” gives all ordered pairs within each block: 3² = 9 from {1,4,5} and 2² = 4 from {2,3}. Total 13 pairs. A block of size k always contributes k², and the result is automatically reflexive, symmetric, and transitive.
§8.2 · matrix view
How can you tell reflexive, symmetric, and transitive from the 0/1 matrix M of R?
Reflexive: the diagonal is all 1s. Symmetric: M equals its transpose (Mᵗ = M) — mirror image across the diagonal. Transitive: wherever M² (Boolean product) has a 1, M already has a 1 — a 2-step path implies a direct edge. The 8.1.1 and 8.1.3 tools draw M for you to inspect.

HarderChallenge problems — and how to crack them

Tougher problems that reward real understanding. Each solution shows the idea first, then the steps.
Challenge 1 the classic trap
A student “proves” symmetric + transitive ⇒ reflexive: “if x R y then by symmetry y R x, then by transitivity x R x.” Find the flaw and give a symmetric, transitive, but not reflexive relation.
The flaw: the chain needs an x related to some y to start. An element related to nothing never gets a self-loop forced on it. Counterexample: on {1,2} take R = {(1,1)}. Symmetric ✓, transitive ✓, but not reflexive ((2,2) missing — 2 is related to nothing). The empty relation on a non-empty set is the extreme case. Lesson: reflexivity is genuinely independent — 8.2.1 flags exactly the orphaned element.
Challenge 2 count the structures
How many equivalence relations are there on a 4-element set?
Idea: an equivalence relation is a partition (8.3.4), so count partitions of {1,2,3,4} by block-size shape. 4: 1 way. 3+1: C(4,3)=4. 2+2: C(4,2)/2 = 3. 2+1+1: C(4,2)=6. 1+1+1+1: 1. Total 1+4+3+6+1 = 15 — the Bell number B₄ (1,1,2,5,15,…). Chapter 9’s counting tools make this systematic.
Challenge 3 prove it carefully
On R define x R y ⇔ x − y ∈ Z. Prove it is an equivalence relation and describe [0] and [0.5].
Reflexive: x−x=0∈Z. Symmetric: x−y∈Z ⇒ y−x∈Z. Transitive: add two integer differences. ✓ Classes group reals by fractional part. [0] = Z; [0.5] = {n + 0.5 : n ∈ Z}. One class per value in [0,1) — the circle you get by gluing the line at every integer.
Challenge 4 build to order
On {1,2,3,4} build a reflexive, symmetric, non-transitive relation with as few pairs as possible, then take its transitive closure.
Idea: link 1–2 and 2–3 symmetrically but skip 1–3; add all self-loops. R = {(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(2,3),(3,2)}: reflexive ✓, symmetric ✓, not transitive ((1,2),(2,3) but no (1,3)). Transitive closure forces (1,3) and (by symmetry) (3,1), fusing {1,2,3}. The closure is the equivalence relation with classes {1,2,3} and {4} — closing a reflexive-symmetric relation transitively always yields an equivalence relation.
Challenge 5 count, with classes
For congruence mod n, how many integers from 1 to 1000 lie in class [0] when n = 7?
[0] mod 7 is the multiples of 7. Count them in [1,1000]: ⌊1000/7⌋ = 142. The classes are nearly balanced: most hold 143 and some hold 142, summing to 1000 — the partition splits the range as evenly as 7 allows. (This counting move is exactly §9.1.)

Chapter recap — relations, end to end

  • 8.1 — a relation is a subset of A × B; picture it as an arrow diagram, a 0/1 matrix, or a directed graph; know domain, range, inverse (reverse / transpose), complement, and composition. A function is the special case “each input exactly once”.
  • 8.2 — reflexive (loop on every node / all-1 diagonal), symmetric (every arrow two-way / M=Mᵗ), transitive (every 2-step path has a shortcut). Prove from the definition on an arbitrary case; disprove with one counterexample. Closures add the smallest fix; antisymmetric + irreflexive lead to orderings.
  • 8.3 — reflexive + symmetric + transitive = an equivalence relation; classes [a] partition the set (equal or disjoint), one fact per property. Partitions and equivalence relations are the same data. Congruence mod n is the model: n classes by remainder.
The link forward. Counting equivalence relations (Challenge 2) and counting a residue class (Challenge 5) both needed systematic counting — exactly the toolkit of Chapter 9 (Counting & Probability), where “how many?” becomes a method.