The Lumenary · Grades 6–8

Relations, equivalence relations and partitions

Name: ______________________

Date: ______________________

You will learn to

Represent a relation on a finite set as a set of ordered pairs, a table and an arrow diagram
Test a relation for reflexivity, symmetry and transitivity, giving a counterexample whenever a property fails
Find the equivalence classes of an equivalence relation, and the equivalence relation that a partition defines
Prove that two equivalence classes are either equal or disjoint, and that the classes form a partition
Show that “same remainder on division by $n$ ” is an equivalence relation on $\Z$ with exactly $n$ classes

1.
On the set $\{0, 1, 2, \dots, 11\}$ , let $a \sim b$ mean that $a$ and $b$ have the same remainder on division by $4$ . List the elements of the class $[6]$ .
2.
Which properties does the relation $a \le b$ (“ $a$ is less than or equal to $b$ ”) on $\Z$ have? Choose all that apply.
- A.Reflexive
- B.Symmetric
- C.Transitive
3.
On $\Z$ , let $a \approx b$ mean that $a$ and $b$ differ by at most $2$ . This relation is not an equivalence relation. Which of these is a genuine counterexample?
- A. $0 \approx 2$ and $2 \approx 4$ , but $0 \not\approx 4$
- B. $3 \not\approx 3$
- C. $1 \approx 3$ but $3 \not\approx 1$
- D. $0 \approx 1$ and $1 \approx 2$ , and $0 \approx 2$
4.
On the whole numbers $0, 1, 2, 3, \dots$ , let $a \sim b$ mean “ $a$ and $b$ have the same last digit”. How many equivalence classes are there?
5.
The partition $\{\{a, b, c\}, \{d\}, \{e, f\}\}$ of $\{a, b, c, d, e, f\}$ defines the relation “lies in the same block as”. How many ordered pairs does this relation contain?
6.
Here is a “proof” that every symmetric, transitive relation is reflexive.

Let $a$ be any element. (1) Choose $b$ with $a \sim b$ . (2) By symmetry, $b \sim a$ . (3) By transitivity, from $a \sim b$ and $b \sim a$ we get $a \sim a$ .

What is wrong?
- A.Step (1): there might be no $b$ with $a \sim b$
- B.Step (2) uses symmetry the wrong way round
- C.Step (3): transitivity needs three different elements
- D.Nothing — the proof is correct
7.
Which of these is a partition of $\{1, 2, 3, 4, 5, 6\}$ ?
- A. $\{\{1, 2\}, \{3, 4\}, \{5, 6\}\}$
- B. $\{\{1, 2, 3\}, \{3, 4, 5, 6\}\}$
- C. $\{\{1, 2\}, \{4, 5, 6\}\}$
- D. $\{\{1, 2, 3, 4, 5, 6\}, \varnothing\}$
8.
How many different equivalence relations are there on the set $\{1, 2, 3, 4\}$ ? (Use Theorem 3: count the partitions instead.)
9.
In the Lean section, cls R a x means “ $x$ belongs to the class of $a$ ”. Which statement says that any two classes are equal or disjoint?
- A.cls R a = cls R b ∨ ∀ x, ¬ (cls R a x ∧ cls R b x)
- B.cls R a = cls R b ∧ ∀ x, ¬ (cls R a x ∧ cls R b x)
- C.∀ x, cls R a x → cls R b x
- D.cls R a ≠ cls R b → ∃ x, cls R a x ∧ cls R b x
10.
Write is_equivalence(elements, related), where elements is a list and related(a, b) returns True or False. It should return True exactly when the relation is reflexive, symmetric and transitive on elements. Python's all(...) is handy: all(related(a, a) for a in elements) tests reflexivity. What should your function return for an empty list, and why?
Computational — Practice

Answer key — Relations, equivalence relations and partitions

1.
$6$ leaves remainder $2$ on division by $4$ , so $[6]$ consists of the numbers in the set with remainder $2$ : $[6] = \{2, 6, 10\}$ . The same class could be called $[2]$ or $[10]$ .
2.
$\le$ is reflexive ( $a \le a$ ) and transitive ( $a \le b \le c$ gives $a \le c$ ), but not symmetric: $1 \le 2$ while $2 \not\le 1$ . So it is not an equivalence relation. (Compare $<$ , which is not even reflexive.)
3.
The relation is reflexive and symmetric, but small differences add up: $0 \approx 2$ and $2 \approx 4$ , while $0$ and $4$ differ by $4 > 2$ . So it is not transitive, and one such triple is enough to prove it.
4.
There is one class for each last digit $0, 1, \dots, 9$ , so there are $10$ classes. (This is “same remainder on division by $10$ ”, which has $10$ classes by Theorem 4.)
5.
Within a block of size $k$ , every element is related to every element, itself included, giving $k^2$ ordered pairs. So the total is $3^2 + 1^2 + 2^2 = 9 + 1 + 4 = 14$ .
6.
Step (1) assumes that $a$ is related to something. If it is not, the argument never starts. The correct statement is: a symmetric, transitive relation in which every element is related to at least one element is reflexive (this is refl_of_symm_trans in the Lean section). Counterexample to the false claim: $\{(0, 0)\}$ on $\{0, 1\}$ .
7.
Only $\{\{1, 2\}, \{3, 4\}, \{5, 6\}\}$ . The second option has overlapping blocks (both contain $3$ ), the third misses $3$ , and the fourth contains the empty set as a block.
8.
By Theorem 3, count partitions of $\{1, 2, 3, 4\}$ by block sizes:
- one block of $4$ : $1$ way;
- $3 + 1$ : choose the single element, $4$ ways;
- $2 + 2$ : the block containing $1$ has one more element, $3$ ways;
- $2 + 1 + 1$ : choose the pair, $6$ ways;
- $1 + 1 + 1 + 1$ : $1$ way.
Total $1 + 4 + 3 + 6 + 1 = 15$ , the Bell number $B_4$ . The experiment in the lesson confirms this by checking all $1024$ symmetric relations on four elements.
9.
The theorem cls_eq_or_disjoint states cls R a = cls R b ∨ ∀ x, ¬ (cls R a x ∧ cls R b x): either the classes are equal, or no element lies in both. The version with ∧ is never true, because classes are non-empty.

10.

def is_equivalence(elements, related):
    reflexive = all(related(a, a) for a in elements)
    symmetric = all(related(b, a)
                    for a in elements for b in elements if related(a, b))
    transitive = all(related(a, c)
                     for a in elements for b in elements for c in elements
                     if related(a, b) and related(b, c))
    return reflexive and symmetric and transitive

For an empty list every all(...) has nothing to check, and returns True: a statement about all elements of an empty set is true, because there is no element that could be a counterexample. So the empty relation on the empty set is an equivalence relation, with no classes — matching the empty partition.