Relations, equivalence classes and partitions
When a relation says which things count as “the same,” what are the groups it sorts a set into, and can we compute with a whole group as if it were a single object?
Where you are 15 in Sets
Why this exists
Mathematics often declares different things “the same for present purposes”: integers with the same remainder, the fractions \tfrac{1}{2} and \tfrac{3}{6}, seatings that differ by a turn of the table. The useful step is to collect everything that counts as the same into one group and treat the group as a single object. That needs a guarantee: the groups never overlap, and every element lands in one. Day 1 proves the guarantee for every equivalence relation. Day 2 uses it to build the integers modulo n, to test when arithmetic on groups makes sense, and to count objects up to a symmetry.
Definition
Day 1: classes and partitions
Recall from Relations and their properties: reflexive, symmetric, antisymmetric, transitive: a relation on a set A is a subset of A \times A, and an equivalence relation is one that is reflexive, symmetric and transitive. Write a \sim b when a is related to b.
Equivalence class. Let \sim be an equivalence relation on A and a \in A. The class of a is
Any member of a class is a representative of it. The set of all classes is written A / {\sim}, read “A modulo \sim.”
Partition. A partition of A is a collection of subsets of A, called blocks, such that every block is nonempty, any two different blocks are disjoint, and the union of all the blocks is A. Equivalently, every element of A lies in exactly one block. Given a partition P, write a \sim_P b when a and b lie in the same block.
Day 2: congruence classes and counting
Fix an integer n \ge 2. Congruence modulo n is an equivalence relation on \mathbb{Z} (Congruence modulo n and its arithmetic, Theorem 2), and its classes are the congruence classes (also called remainder or residue classes):
Their set is \mathbb{Z}_n, the integers modulo n; when n is clear, [a]_n is shortened to [a]. Classes are added and multiplied through representatives:
An operation defined through representatives is well defined when its result does not depend on which representatives are chosen. Until that is checked, a formula like the one above is only a hope.
Intuition
An equivalence relation says “same something”: same remainder, same size, same distance. Its classes are the sets of things sharing a value of that something. On the plane, let P \sim Q mean that P and Q are the same distance from the origin. The class of a point at distance r > 0 is the circle of radius r centered at the origin, and the origin is a class by itself. Each point of the plane lies on exactly one of these circles.
A partition is the same picture with the relation erased: boxes around the elements, each element in exactly one box. Day 1 shows the two pictures carry the same information: the relation determines the boxes, the boxes determine the relation, and each recovers the other.
Results
Throughout, \sim is an equivalence relation on a set A.
Theorem 1 (same class, same relation). For all a, b \in A, [a] = [b] if and only if a \sim b. Also a \in [a], so every class is nonempty.
Theorem 2 (equal or disjoint). For all a, b \in A, either [a] = [b] or [a] \cap [b] = \varnothing.
Theorem 3 (classes partition). The classes of \sim form a partition of A.
Theorem 4 (a partition gives a relation). For every partition P of A, the relation \sim_P is an equivalence relation, and its classes are exactly the blocks of P.
Theorem 5 (correspondence). Sending an equivalence relation to its set of classes, and a partition P to \sim_P, are inverse to each other. So they are bijections between the equivalence relations on A and the partitions of A.
Theorem 6 (same output). For every function f : A \to B, the relation “a \sim b when f(a) = f(b)” is an equivalence relation, whose classes are the sets \{x \in A : f(x) = y\} for y in the image of f. Every equivalence relation arises this way.
Theorem 7 (the integers modulo n). The classes [0], [1], \dots, [n - 1] are distinct and are all of \mathbb{Z}_n. So \mathbb{Z}_n has exactly n members.
Theorem 8 (well defined). If [a] = [a'] and [b] = [b'] in \mathbb{Z}_n, then [a + b] = [a' + b'] and [ab] = [a'b'].
Theorem 9 (counting by classes). If A is finite, |A| is the sum of the sizes of the classes. If every class has exactly k members and |A| = N, there are exactly N / k classes.
Why it is true
Proof of Theorem 1. Reflexivity gives a \sim a, so a \in [a]. Suppose a \sim b, and let x \in [a], so x \sim a. By transitivity x \sim b, so x \in [b]; thus [a] \subseteq [b]. By symmetry b \sim a, and the same argument gives [b] \subseteq [a], so [a] = [b] (Subsets, proper subsets and equal sets). Conversely, if [a] = [b], then a \in [a] = [b], so a \sim b. \square
Proof of Theorem 2. Suppose some c lies in [a] \cap [b]. Then c \sim a and c \sim b. By symmetry a \sim c, and by transitivity a \sim b. By Theorem 1, [a] = [b]. \square
Proof of Theorem 3. Each class is nonempty (Theorem 1), two different classes are disjoint (Theorem 2), and every a \in A lies in [a], so the classes cover A. \square
Proof of Theorem 4. Reflexive: every a lies in some block, together with itself. Symmetric: “in the same block” does not depend on order. Transitive: if a, b lie in block B_1 and b, c in block B_2, then b \in B_1 \cap B_2, and different blocks are disjoint, so B_1 = B_2. The class of a under \sim_P is the set of elements in a’s block, which is that block. \square
Proof of Theorem 5. Start from a partition P: by Theorem 4 the classes of \sim_P are the blocks of P, so the round trip returns P. Start from \sim, and let a \approx b mean that a and b lie in a common class [c]. If a \sim b, both lie in [b], so a \approx b. If a, b \in [c], then a \sim c and b \sim c, so a \sim b by symmetry and transitivity. Hence \approx is \sim. Two maps that undo each other in both orders are inverse bijections (Composing functions between sets, and when an inverse exists). \square
Proof of Theorem 6. The three properties are those of equality: f(a) = f(a); f(a) = f(b) gives f(b) = f(a); f(a) = f(b) and f(b) = f(c) give f(a) = f(c). The class of a is \{x : f(x) = f(a)\}. For the last sentence, given \sim take f : A \to A/{\sim} with f(a) = [a]; by Theorem 1, f(a) = f(b) exactly when a \sim b. \square
Proof of Theorem 7. Every integer a is congruent modulo n to exactly one r \in \{0, 1, \dots, n - 1\} (Congruence modulo n and its arithmetic, Theorem 1), so [a] = [r] by Theorem 1. Different remainders are not congruent, since each is its own remainder, so the n classes [r] are distinct. \square
Proof of Theorem 8. By Theorem 1, a \equiv a' and b \equiv b' \pmod{n}. The arithmetic rules of Congruence modulo n and its arithmetic (Theorem 3) give a + b \equiv a' + b' and ab \equiv a'b', and Theorem 1 turns these back into equal classes. \square
Proof of Theorem 9. Let the classes be C_1, \dots, C_m, pairwise disjoint with union A (Theorem 3). For disjoint finite sets |X \cup Y| = |X| + |Y| (Venn diagrams and counting a union with an empty overlap). Adding one class at a time, each new class is disjoint from the union of those before it, so by induction on m, |A| = |C_1| + \dots + |C_m|. If every |C_i| = k, this reads N = mk, so m = N / k. \square
Worked examples
Examples 1 to 3 go with day 1, examples 4 to 7 with day 2.
Classes from a function
On A = \{1, 2, \dots, 12\}, let a \sim b mean that a and b have the same largest odd divisor. Explain why \sim is an equivalence relation, and list its classes with a natural representative of each.
SolutionLet f(a) be the largest odd divisor of a. The relation is “f(a) = f(b),” so it is an equivalence relation by Theorem 6, with nothing to check by hand. Dividing out factors of 2: f is 1 at 1, 2, 4, 8; 3 at 3, 6, 12; 5 at 5, 10; and 7, 9, 11 are their own values. So there are six classes:
Each class contains exactly one odd number, f(a), a natural representative: [8] = [1] and [12] = [3]. The sizes add to 4 + 3 + 2 + 1 + 1 + 1 = 12 = |A|, as Theorem 9 requires. These classes, on \{1, \dots, 2n\}, are the boxes of an argument in The pigeonhole principle.
Real numbers that differ by an integer
On \mathbb{R}, let x \sim y mean x - y \in \mathbb{Z}. Prove that \sim is an equivalence relation and that every class contains exactly one number in [0, 1). Find that number for [2.75] and for [-3.4].
SolutionProof. Reflexive: x - x = 0 \in \mathbb{Z}. Symmetric: if x - y = k \in \mathbb{Z}, then y - x = -k \in \mathbb{Z}. Transitive: if x - y = k and y - z = j are integers, so is x - z = k + j.
Let \lfloor x \rfloor be the greatest integer at most x. Then t = x - \lfloor x \rfloor satisfies 0 \le t < 1, and x - t is an integer, so t \in [x]. If s, t \in [0, 1) both lie in [x], then s \sim t by Theorem 1, so s - t is an integer strictly between -1 and 1, which forces s = t. \square
For [2.75]: 2.75 - 2 = 0.75. For [-3.4]: \lfloor -3.4 \rfloor = -4 and -3.4 - (-4) = 0.6. So [2.75] = [0.75] and [-3.4] = [0.6].
From blocks to pairs
Let A = \{a, b, c, d, e, f, g\} with the partition P of Figure 2: blocks \{a, b, c, d\}, \{e\}, \{f, g\}. (a) Is a \sim_P e? Is f \sim_P g? (b) How many ordered pairs does \sim_P contain? (c) Which equivalence relations belong to the partition into seven one-element blocks, and to the partition with the single block A?
Solution(a) a and e are in different blocks, so a \not\sim_P e; f and g share a block, so f \sim_P g.
(b) A pair (x, y) is in \sim_P exactly when x, y share a block, so the pairs from a block B are those of B \times B, and different blocks give different pairs. The count is
(c) With one-element blocks, x \sim y only when x = y: the relation is equality, 7 pairs. With the single block, every two elements are related: all of A \times A, 7^2 = 49 pairs.
Arithmetic in the integers modulo 6
Compute [4] + [5], [4] \cdot [5] and [2] \cdot [3] in \mathbb{Z}_6. Then recompute the first two with the representatives -2 for [4] and 11 for [5].
SolutionBy definition [4] + [5] = [9], and 9 = 6 + 3, so [9] = [3]. Next [4] \cdot [5] = [20], and 20 = 3 \cdot 6 + 2, so [20] = [2]. Finally [2] \cdot [3] = [6] = [0]: a product of two classes other than [0] can be [0].
Now -2 \in [4] since 4 - (-2) = 6, and 11 \in [5] since 11 - 5 = 6. Then (-2) + 11 = 9 gives [3] again, and (-2) \cdot 11 = -22 = (-4) \cdot 6 + 2 gives [2] again, as Theorem 8 promises for every choice.
Operations that are not well defined
(a) On \mathbb{Z}_5, try to define [a] \star [b] = [\min(a, b)], the class of the smaller representative. (b) On \mathbb{Z}_3, try to define [a]^{[b]} = [a^b] for nonnegative representatives b. Show that neither is well defined.
SolutionIt is enough to find one class with two representatives that give different answers.
(a) With representatives 1 and 3, [1] \star [3] is [\min(1, 3)] = [1]. But [1] = [6] in \mathbb{Z}_5, and with 6 and 3, \min(6, 3) = 3 gives [3]. Since 3 - 1 = 2 is not a multiple of 5, [1] \neq [3], so \star is not an operation on classes.
(b) With exponent 1, [2]^{[1]} is [2^1] = [2]. But [1] = [4] in \mathbb{Z}_3, and 2^4 = 16 = 5 \cdot 3 + 1 gives [1] \neq [2]. The exponent cannot be a class. A fixed positive integer exponent, [a]^k = [a^k], is well defined, since it is repeated multiplication (Theorem 8).
Strings up to rotation
Thulani prints five-letter codes around the rim of a round token, using the letters a, b, c, read clockwise from any starting point. So two strings of length 5 give the same token when one is a rotation of the other, such as abcab and bcaba. How many different tokens are there?
SolutionLet S be the set of strings s = s_0 s_1 s_2 s_3 s_4 over \{a, b, c\}, so |S| = 3^5 = 243. Let \rho move the first letter to the end, so \rho(s) has letter s_{p + 1} in position p, positions read modulo 5. Say s \sim t when t = \rho^j(s) for some j \in \{0, 1, 2, 3, 4\}. Since \rho^5(s) = s, rotation amounts add like members of \mathbb{Z}_5: j = 0 gives reflexivity, \rho^{5 - j} undoes \rho^j (symmetry), and \rho^i after \rho^j is \rho^{i + j} (transitivity). The tokens are the classes, and [s] = \{s, \rho s, \rho^2 s, \rho^3 s, \rho^4 s\} has at most 5 members.
The constant strings aaaaa, bbbbb, ccccc are classes of size 1. Let s be nonconstant and suppose \rho^i s = \rho^j s with i < j. Applying \rho^{5 - j} gives \rho^m s = s with m = 5 - (j - i) \in \{1, 2, 3, 4\}, so s_p = s_{p + m} for every position p, and s_0 = s_m = s_{2m} = s_{3m} = s_{4m}. For each such m the positions 0, m, 2m, 3m, 4m modulo 5 are all five positions (for m = 2: 0, 2, 4, 1, 3; the others alike), so s is constant, a contradiction. Every nonconstant class has exactly 5 members.
Rotation keeps a string nonconstant, so the 243 - 3 = 240 nonconstant strings are a union of classes of size 5. By Theorem 9 they form 240 / 5 = 48 classes, and there are 48 + 3 = 51 tokens.
Every partition of a four-element set
List all partitions of \{1, 2, 3, 4\}. How many equivalence relations does \{1, 2, 3, 4\} have, and how many have exactly two classes?
SolutionWrite a partition by listing its blocks side by side, so \{1, 2\}\{3, 4\} has blocks \{1, 2\} and \{3, 4\}. Sort by block sizes.
| block sizes | how many | the partitions |
|---|---|---|
| 4 | 1 | \{1, 2, 3, 4\} |
| 3, 1 | 4 | \{1, 2, 3\}\{4\}, \{1, 2, 4\}\{3\}, \{1, 3, 4\}\{2\}, \{2, 3, 4\}\{1\} |
| 2, 2 | 3 | \{1, 2\}\{3, 4\}, \{1, 3\}\{2, 4\}, \{1, 4\}\{2, 3\} |
| 2, 1, 1 | 6 | \{1, 2\}\{3\}\{4\}, \{1, 3\}\{2\}\{4\}, \{1, 4\}\{2\}\{3\}, \{2, 3\}\{1\}\{4\}, \{2, 4\}\{1\}\{3\}, \{3, 4\}\{1\}\{2\} |
| 1, 1, 1, 1 | 1 | \{1\}\{2\}\{3\}\{4\} |
Each count has a reason: sizes 3, 1, choose the lone element; sizes 2, 2, the partner of 1 decides both blocks; sizes 2, 1, 1, choose the pair, \binom{4}{2} = 6 ways. The total is 1 + 4 + 3 + 6 + 1 = 15. By Theorem 5, \{1, 2, 3, 4\} has exactly 15 equivalence relations, out of 2^{16} relations in all, and those with exactly two classes number 4 + 3 = 7.
Boundaries
- All three properties are needed. On \{1, 2\} the relation \{(1, 1)\} is symmetric and transitive but not reflexive, and the “class” of 2 is empty, so the classes do not cover the set. Without transitivity, “classes” can overlap without being equal (exercise 8).
- A class is a set, and representatives are not unique. [3] in \mathbb{Z}_6 is an infinite set, not the number 3. A rule that reads off a representative must be checked to be well defined; Example 5 shows two that fail.
- Equal class sizes are a hypothesis. N / k needs every class to have k members. Strings of length 2 over \{0, 1\} up to rotation form 3 classes, \{00\}, \{11\}, \{01, 10\}, not 4 / 2 = 2. In general only the sum of the class sizes is N.
Where this goes next
Classes are how new number systems are built: a fraction is a class of pairs of integers, with \tfrac{a}{b} and \tfrac{c}{d} equivalent when ad = bc (Equivalent fractions), and \mathbb{Z}_n is a finite number system. Which classes of \mathbb{Z}_n can be divided by is Modular inverses and linear congruences, which leads on to Fermat's little theorem and the The Chinese remainder theorem. In counting, the round-table count (n - 1)! of Arrangements and factorials is Theorem 9 with N = n! and k = n, and Combinations with repetition: stars and bars counts strings up to rearrangement, where class sizes differ.
Exercises
Day 1: finding classes
- On \{-3, -2, -1, 0, 1, 2, 3\}, let x \sim y mean x^2 = y^2. List the classes.
- On the power set of \{1, 2, 3\}, let S \sim T mean |S| = |T|. List the classes and their sizes.
- On \mathbb{R} with x \sim y meaning x - y \in \mathbb{Z}, find the representative in [0, 1) of [7.3] and of [-4.15], and decide whether 2.7 \sim -1.3.
- On \{1, 2, 3, 4, 5\}, the relation R consists of the five pairs (x, x) and the four pairs (1, 4), (4, 1), (2, 5), (5, 2). Show that R is an equivalence relation by finding a partition P with R = {\sim_P}, and list its classes.
- Which of these are partitions of \{1, 2, 3, 4, 5, 6\}? (a) \{1, 3\}, \{2, 4, 6\}, \{5\} (b) \{1, 2, 3\}, \{3, 4, 5, 6\} (c) \{1, 2\}, \{4, 5\}, \{6\} (d) \{1, 2, 3, 4, 5, 6\}, \varnothing
Day 1: reasoning
- On the positive integers, let a \approx b mean a = 2^k b for some integer k, positive, negative or zero. Prove that \approx is an equivalence relation, and that each class contains exactly one odd number.
- Let f : A \to B and let a \sim b mean f(a) = f(b). Prove that [a] \mapsto f(a) is a well defined bijection from A / {\sim} onto the image of f.
- On \mathbb{R}, let x \bowtie y mean |x - y| \le 1, and let G(x) = \{y : y \bowtie x\}. Show that \bowtie is reflexive and symmetric but not transitive, and that G(0) and G(1) overlap without being equal.
Day 2: congruence classes
- List the members of [7]_9 between -30 and 30.
- Which of [-13], [22], [50], [-4] equal [5] in \mathbb{Z}_9?
- In \mathbb{Z}_8, compute [5] + [7], [5] \cdot [7], [6] \cdot [4] and [3] \cdot [3].
- Find every class x in \mathbb{Z}_{12} with x \cdot x = x.
- Decide which of these are well defined, with a reason or a failing pair of representatives. (a) f : \mathbb{Z}_{12} \to \mathbb{Z}_4, f([a]_{12}) = [a]_4 (b) g : \mathbb{Z}_4 \to \mathbb{Z}_{12}, g([a]_4) = [a]_{12} (c) h : \mathbb{Z}_7 \to \mathbb{Z}_7, h([a]) = [a^3 + 1] (d) on \mathbb{Z}_{10}, [a] \circ [b] = [|a - b|]
Day 2: counting
- How many strings of length 7 over \{0, 1\} are there up to rotation?
- List the classes of strings of length 4 over \{0, 1\} up to rotation. Why is the answer not 16 / 4?
- Two strings of length 3 over \{a, b, c\} are equivalent when one is a rearrangement of the letters of the other, such as abb and bab. How many classes are there, and of what sizes?
- List all partitions of \{p, q, r\}, and write the equivalence relation of \{p, q\}\{r\} as a set of pairs.
- How many equivalence relations on \{1, 2, 3, 4, 5\} have exactly two classes?
Day 2: reasoning
- Call [a]_n “even” when a is even. Show that this is well defined in \mathbb{Z}_6 but not in \mathbb{Z}_7.
- Prove that addition on \mathbb{Z}_n is commutative and associative, naming the property of integers each step uses.
- Let \sim be an equivalence relation on a finite set whose classes have sizes k_1, \dots, k_m. Prove that \sim, as a set of ordered pairs, has k_1^2 + \dots + k_m^2 members.
Answers
- \{0\}, \{-1, 1\}, \{-2, 2\}, \{-3, 3\}, the classes of f(x) = x^2 (Theorem 6).
- \{\varnothing\}; \{\{1\}, \{2\}, \{3\}\}; \{\{1, 2\}, \{1, 3\}, \{2, 3\}\}; \{\{1, 2, 3\}\}, of sizes 1, 3, 3, 1.
- 0.3, since 7.3 - 7 = 0.3; 0.85, since -4.15 - (-5) = 0.85. Yes: 2.7 - (-1.3) = 4 \in \mathbb{Z}.
- P: \{1, 4\}, \{2, 5\}, \{3\}. The pairs inside its blocks number 4 + 4 + 1 = 9 and are exactly the pairs of R, so by Theorem 4, R is an equivalence relation with classes \{1, 4\}, \{2, 5\}, \{3\}.
- Only (a). (b) puts 3 in two blocks; (c) misses 3; (d) has an empty block.
- Proof. Reflexive: a = 2^0 a. Symmetric: a = 2^k b gives b = 2^{-k} a. Transitive: a = 2^k b and b = 2^j c give a = 2^{k + j} c. Dividing out factors of 2 writes a = 2^e q with q odd, so a \approx q and each class has an odd member. If odd q, q' have q = 2^k q', then k > 0 makes q even and k < 0 makes q' = 2^{-k} q even; so k = 0 and q = q'. \square
- Proof. Well defined: [a] = [a'] gives a \sim a' (Theorem 1), that is, f(a) = f(a'). One to one: f(a) = f(b) gives a \sim b, so [a] = [b]. Onto the image: f(a) is the image of [a]. \square
- |x - x| = 0 \le 1 and |x - y| = |y - x|. Not transitive: 0 \bowtie 1 and 1 \bowtie 2, but |0 - 2| = 2. G(0) = [-1, 1] and G(1) = [0, 2] share [0, 1], yet -1 is in only the first.
- 7 + 9k for k = -4, \dots, 2: -29, -20, -11, -2, 7, 16, 25.
- [-13], [50] and [-4]: their differences from 5, namely -18, 45, -9, are multiples of 9, while 22 - 5 = 17 is not, and [22] = [4].
- [12] = [4]; [35] = [3]; [24] = [0]; [9] = [1].
- [0], [1], [4], [9]. Of r^2 - r for r = 0, \dots, 11, only these give a multiple of 12: for example 16 - 4 = 12 and 81 - 9 = 72, while 9 - 3 = 6 rules out [3].
- (a) Well defined: 12 \mid a - a' and 4 \mid 12 give 4 \mid a - a'. (b) Not: [0]_4 = [4]_4, but [0]_{12} \neq [4]_{12}. (c) Well defined, by Congruence modulo n and its arithmetic, Corollary 4. (d) Not: [1] = [11], but |1 - 3| = 2 and |11 - 3| = 8, and [2] \neq [8] in \mathbb{Z}_{10}.
- 20. The two constant strings are classes of size 1. Since 7 is prime, the argument of Example 6 gives every other class 7 members, so (128 - 2) / 7 + 2 = 18 + 2 = 20.
- \{0000\}, \{1111\}, \{0001, 0010, 0100, 1000\}, \{0011, 0110, 1100, 1001\}, \{0101, 1010\}, \{0111, 1110, 1101, 1011\}: six classes. Their sizes 1, 1, 4, 4, 2, 4 are not all 4, so Theorem 9 gives only the sum 16.
- 10 classes, one per multiset of 3 letters from 3 kinds, \binom{5}{3} = 10. Sizes: 1 for aaa, bbb, ccc; 3 for the six classes with two letters alike, like \{abb, bab, bba\}; 6 for the class of abc. Check: 3 + 18 + 6 = 27 = 3^3.
- \{p\}\{q\}\{r\}, \{p, q\}\{r\}, \{p, r\}\{q\}, \{q, r\}\{p\}, \{p, q, r\}: five. The relation of \{p, q\}\{r\} is the set of the five pairs (p, p), (q, q), (r, r), (p, q), (q, p).
- 15. By Theorem 5, count partitions into two blocks. The block containing 1 is \{1\} \cup S with S any subset of \{2, 3, 4, 5\} except the whole set, and it decides the other block: 2^4 - 1 = 15.
- In \mathbb{Z}_6: [a] = [a'] gives a - a' = 6k = 2(3k), even, so a and a' have the same parity. In \mathbb{Z}_7: [0] = [7], but 0 is even and 7 is odd.
- Proof. [a] + [b] = [a + b] = [b + a] = [b] + [a] by commutativity of integer addition, and ([a] + [b]) + [c] = [(a + b) + c] = [a + (b + c)] = [a] + ([b] + [c]) by associativity. Each use of the definition is valid by Theorem 8. \square
- Proof. (x, y) \in {\sim} exactly when x, y share a class C_i, that is, (x, y) \in C_i \times C_i. These products are pairwise disjoint, since a pair in two of them would put x in two classes (Theorem 2), and |C_i \times C_i| = k_i^2 (Cartesian product). Adding, as in the proof of Theorem 9, gives k_1^2 + \dots + k_m^2. \square