Sort the integers from 1 to 12 by how many positive divisors they have:
| Number of divisors | Integers from 1 to 12 |
|---|---|
| 1 | 1 |
| 2 | 2, 3, 5, 7, 11 |
| 3 | 4, 9 |
| 4 | 6, 8, 10 |
| 6 | 12 |
Every integer lands in exactly one row, and no row is empty. Within a row the integers are "the same" for the purpose at hand, although they are different integers: the rows with 2 divisors hold the primes, and the row with 3 holds the squares of primes. Which rules for "the same" always sort a set this cleanly, and when can we compute with the rows as if each were a single object?
Mathematics does this kind of sorting constantly. The fractions $\frac{1}{2}$ and $\frac{3}{6}$ are different expressions for the same number, angles of $30^\circ$ and $390^\circ$ point the same way, and integers that leave the same remainder on division by 7 name the same weekday when they count days. An equivalence relation is the precise version of "the same for this purpose". It always produces a sorting like the table above, called a partition, and every partition comes from one.
First we define the three properties of an equivalence relation and see that none follows from the other two. Then we prove that the classes partition the set, and that every partition comes from exactly one equivalence relation. Next we build the rational numbers as classes of pairs of integers. Finally we ask when a rule defined on classes is well defined, the question on which the rest of the unit depends.
This is the first article of Congruence and Modular Arithmetic, the second unit of the course notes for MTH 532, and later articles build on it: congruence modulo $n$, the integers modulo $n$, quotient rings and cosets all use its results. The course text proves the three properties for congruence and then uses only those properties when it works with congruence classes (Hungerford, 2014, §2.1). This article develops that pattern for relations in general, as in Judson (2026, §1.2.3).
Relations
A relation on a set $S$ is a rule that, for each ordered pair $(a, b)$ of elements of $S$, says either that $a$ is related to $b$ or that it is not. Formally, a relation is a subset $R$ of the Cartesian product $S \times S$, the set of all ordered pairs. "$a$ is related to $b$" means $(a, b) \in R$. We write $a \sim b$ for this, and $a \not\sim b$ when it fails.
Familiar relations on the integers include $a = b$, $a \le b$, $a \mid b$ (for nonzero $a$), and "$a$ and $b$ have the same number of positive divisors". The definition allows any subset of $S \times S$, so relations need not have a pattern at all. The useful ones do. Which patterns make a relation behave like equality?
Three properties
Definition. A relation $\sim$ on a set $S$ is an equivalence relation if it has the following three properties.
- Reflexive: $a \sim a$ for every $a \in S$.
- Symmetric: for all $a, b \in S$, if $a \sim b$ then $b \sim a$.
- Transitive: for all $a, b, c \in S$, if $a \sim b$ and $b \sim c$ then $a \sim c$.
Equality is the model. Everything equals itself, equality reads the same in both directions, and two things equal to a third are equal to each other. An equivalence relation keeps these three features of equality while allowing distinct elements to be related.
Example (a function sorts its domain). Let $f$ be any function from $S$ to a set $T$, and define $a \sim b$ to mean $f(a) = f(b)$. Then $\sim$ is an equivalence relation, because each property of $\sim$ is the same property of equality in $T$:
- $f(a) = f(a)$;
- if $f(a) = f(b)$ then $f(b) = f(a)$;
- if $f(a) = f(b)$ and $f(b) = f(c)$ then $f(a) = f(c)$.
The opening table is this example with $S = \{1, \ldots, 12\}$ and $f(n)$ the number of positive divisors of $n$. Sorting the integers by their remainder on division by 7 is another, with $f(a)$ the remainder. That relation is congruence modulo 7.
Many relations that look different are of this kind once the right function is found. Two angles, measured in degrees, are equivalent when they differ by a multiple of $360$. That happens exactly when they have the same cosine and the same sine, so the function is "the point on the unit circle".
Relations with two of the three properties
Does any one of the three properties follow from the other two? None does. Each relation below, on the integers, has exactly two of them, as the script for this article confirms on the integers from $-5$ to $5$.
| Relation | Reflexive | Symmetric | Transitive | Where it fails |
|---|---|---|---|---|
| $a \le b$ | yes | no | yes | $1 \le 2$ but $2 \not\le 1$ |
| $\lvert a - b \rvert \le 1$ | yes | yes | no | $0 \sim 1$ and $1 \sim 2$, but $\lvert 0 - 2 \rvert = 2$ |
| $ab > 0$ | no | yes | yes | $0 \cdot 0 = 0$, so $0 \not\sim 0$ |
The second row is the reason that "close to" is never an equivalence relation. Closeness does not accumulate, and a chain of small steps can travel any distance.
The third row answers a tempting argument: "symmetry and transitivity give reflexivity for free." If $a \sim b$, then $b \sim a$ by symmetry, and transitivity applied to $a \sim b$ and $b \sim a$ gives $a \sim a$. The argument is correct, but it needs some $b$ with $a \sim b$ to start. Under $ab > 0$, the integer $0$ is related to nothing at all. So the argument never begins, and reflexivity fails exactly there.
Check your understanding. On the integers from 2 upward, call $a$ and $b$ related when they share a prime factor. Which of the three properties hold? Try the running pair 1729 and 1001 together with 38.
Reflexivity and symmetry hold, but transitivity fails: 1001 and 1729 share 7 and 13, and 1729 and $38 = 2 \cdot 19$ share 19, yet $1001 = 7 \cdot 11 \cdot 13$ and 38 share no prime. Like closeness, sharing a factor does not accumulate along a chain.
Equivalence classes
Once a relation is known to be an equivalence relation, we can collect everything related to a given element.
Definition. Let $\sim$ be an equivalence relation on $S$ and let $a \in S$. The equivalence class of $a$ is the set of all elements related to $a$:
$$[a] = \{\, x \in S : x \sim a \,\}.$$
Any element of a class is called a representative of it. In the opening example, $[5] = \{2, 3, 5, 7, 11\} = [11]$. The class is one set, and 5 and 11 are two of its representatives.
The basic facts about classes all follow from the three properties.
Lemma. Let $\sim$ be an equivalence relation on $S$. For every $a \in S$, $a \in [a]$; in particular every class is nonempty.
Proof. $a \sim a$ by reflexivity, which is the condition for $a \in [a]$. $\blacksquare$
Theorem. Let $\sim$ be an equivalence relation on $S$, and let $a, b \in S$. Then
$$a \sim b \quad \text{if and only if} \quad [a] = [b].$$
Here is the idea. If $a \sim b$, anything related to one of them is related to the other, by chaining through the link between $a$ and $b$ in whichever direction is needed. Conversely, $a$ lies in its own class, so equal classes put $a$ in the class of $b$.
Proof. Suppose $a \sim b$. To show $[a] \subseteq [b]$, let $x \in [a]$, so $x \sim a$. With $a \sim b$, transitivity gives $x \sim b$, so $x \in [b]$. For the reverse inclusion, let $x \in [b]$, so $x \sim b$. By symmetry $b \sim a$, and transitivity gives $x \sim a$, so $x \in [a]$. Hence $[a] = [b]$.
Conversely, suppose $[a] = [b]$. By the lemma $a \in [a]$, so $a \in [b]$, which by the definition of $[b]$ means $a \sim b$. $\blacksquare$
The theorem converts statements about the relation into statements of equality between sets. That is how the classes come to behave as single objects. Its first half used transitivity and symmetry, its second half reflexivity, so all three properties are needed.
Corollary. Two equivalence classes are either equal or disjoint.
Proof. Suppose $[a]$ and $[b]$ have an element $x$ in common. Then $x \sim a$ and $x \sim b$. By symmetry $a \sim x$, and transitivity applied to $a \sim x$ and $x \sim b$ gives $a \sim b$. By the theorem, $[a] = [b]$. So two classes that are not disjoint are equal. $\blacksquare$
Check your understanding. Extend the opening sort to all positive integers. Are 1729 and 1001 in the same class?
They are. By the fundamental theorem of arithmetic, $1729 = 7 \cdot 13 \cdot 19$ and $1001 = 7 \cdot 11 \cdot 13$ are each a product of three distinct primes, so each has $2^3 = 8$ divisors, one for each subset of its primes, as the script confirms. By the theorem, $[1729] = [1001]$: the class records only the count, not the primes.
Partitions
The corollary says that the classes do not overlap. Together with the lemma, that is almost the definition of a sorting like the opening table.
Definition. A partition of a set $S$ is a collection of subsets of $S$, called its blocks, such that
- every block is nonempty,
- the blocks are pairwise disjoint, and
- every element of $S$ lies in some block.
Equivalently, each element of $S$ lies in exactly one block.
Theorem (equivalence relations and partitions). Let $S$ be a set.
- If $\sim$ is an equivalence relation on $S$, its distinct equivalence classes form a partition of $S$.
- If $\mathcal{P}$ is a partition of $S$, the relation "$a$ and $b$ lie in the same block of $\mathcal{P}$" is an equivalence relation on $S$, and its equivalence classes are exactly the blocks of $\mathcal{P}$.
- The two constructions undo each other. Starting from an equivalence relation, forming its partition and then the relation of part 2 returns the original relation. Starting from a partition, forming its relation and then the classes of part 1 returns the original partition.
Here is the plan: part 1 is the lemma and the corollary, part 2 reads the three properties off the blocks, and part 3 checks that each round trip changes nothing.
Proof. (1) Each class is nonempty by the lemma. Distinct classes are disjoint by the corollary. Every $a \in S$ lies in a class, namely $[a]$.
(2) Every element lies in some block, so it lies in the same block as itself: the relation is reflexive. "Same block" reads the same in both directions, so it is symmetric. For transitivity, suppose $a$ and $b$ lie in a block $B$, and $b$ and $c$ lie in a block $B'$. Then $b \in B \cap B'$, and since distinct blocks are disjoint, $B = B'$. So $a$ and $c$ lie in the same block. Finally, if $B$ is the block containing $a$, then the class of $a$ is the set of elements in the same block as $a$, which is $B$.
(3) Under the relation of part 2 built from the classes of $\sim$, $a$ is related to $b$ when they lie in a common class. By the theorem on classes, that happens exactly when $a \sim b$. In the other direction, part 2 already showed that the classes of the "same block" relation are the blocks. $\blacksquare$
So equivalence relations and partitions are two descriptions of one thing. Sometimes the relation is easier to state, as with "differ by a multiple of 7". Sometimes the blocks are, as with the table at the top of the article.
Counting them
On a finite set the correspondence can be checked by brute force. A relation on $S = \{1, 2, 3, 4\}$ is any subset of the 16 ordered pairs, so there are $2^{16} = 65{,}536$ relations. The script for this article tests every one of them:
- 4,096 are reflexive;
- 1,024 are symmetric;
- 3,994 are transitive;
- only 15 have all three properties.
The script also lists the partitions of $\{1, 2, 3, 4\}$ directly and finds 15 of them, matching the theorem:
| Number of blocks | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Partitions of $\{1, 2, 3, 4\}$ | 1 | 7 | 6 | 1 |
The two-block partitions are the four of the form $\{\{a\}, \text{the other three}\}$ and the three that split the set into two pairs. The three-block partitions put one pair together and leave two singletons, and there are $\binom{4}{2} = 6$ pairs to choose. The number of partitions of an $n$-element set is called the $n$th Bell number. For $n = 0, 1, \ldots, 8$ the values are 1, 1, 2, 5, 15, 52, 203, 877 and 4,140, computed in the script from a recurrence and, for $n \le 6$, by listing.
The quotient set
A partition is a set of blocks. Treating each block as a single element gives a new set.
Definition. Let $\sim$ be an equivalence relation on $S$. The set of all equivalence classes,
$$S/{\sim} \; = \; \{\, [a] : a \in S \,\},$$
is the quotient set of $S$ by $\sim$, and the function $\pi : S \to S/{\sim}$ given by $\pi(a) = [a]$ is the quotient map.
The quotient set has one element for each block of the partition, not one for each element of $S$. In the opening example $S$ has 12 elements and $S/{\sim}$ has 5. The quotient map is onto, since every class is the class of each of its representatives. It is one-to-one only when every class has a single element, which happens only for equality. Its whole purpose is to send distinct but equivalent elements to the same place.
The quotient map also shows that the example of a function sorting its domain was the general case. For any equivalence relation, $a \sim b$ holds exactly when $[a] = [b]$, that is, when $\pi(a) = \pi(b)$. So every equivalence relation is "having the same value under some function", with the quotient map as the function.
Fractions as classes
The rational numbers give the classic use of a quotient set. A fraction is written with a pair of integers, but different pairs name the same number: $\frac{1}{2} = \frac{2}{4} = \frac{-3}{-6}$. How can this be said without already having the rational numbers? Through cross-multiplication.
Let $S$ be the set of pairs $(a, b)$ of integers with $b \neq 0$, and define
$$(a, b) \sim (c, d) \quad \text{if} \quad ad = bc.$$
Proposition. This relation is an equivalence relation on $S$.
The first two properties are immediate. For transitivity, the idea is to chain the two cross-multiplications through the middle pair and then cancel the middle denominator $d$.
Proof. Reflexive: $ab = ba$. Symmetric: if $ad = bc$ then $cb = da$, which is the condition for $(c, d) \sim (a, b)$.
Transitive: suppose $(a, b) \sim (c, d)$ and $(c, d) \sim (e, f)$, so $ad = bc$ and $cf = de$. Multiplying the first equation by $f$ and the second by $b$,
$$adf = bcf = bde.$$
So $d(af - be) = 0$. Since $d \neq 0$, and a product of two integers is zero only if one factor is zero, $af - be = 0$. That is, $af = be$, which says $(a, b) \sim (e, f)$. $\blacksquare$
The transitivity step canceled the factor $d$, and that is where the condition on denominators matters. Suppose pairs with second entry 0 were allowed. Then $(1, 0) \sim (0, 0)$, since $1 \cdot 0 = 0 \cdot 0$, and $(0, 0) \sim (0, 1)$, since $0 \cdot 1 = 0 \cdot 0$. But $(1, 0) \not\sim (0, 1)$, since $1 \cdot 1 \neq 0 \cdot 0$. The single pair $(0, 0)$ would link every class to every other.
The step also used the fact that two nonzero integers never have product zero. Number systems in which that fails, such as the integers modulo 21, are met in Units and Zero Divisors in the Integers Modulo n. There the same cross-multiplication rule would not be transitive.
The rational number $\frac{a}{b}$ is defined to be the class $[(a, b)]$, and $\mathbb{Q}$ is the quotient set $S/{\sim}$. Geometrically, $(a, b) \sim (c, d)$ says that the points $(a, b)$ and $(c, d)$ of the plane lie on the same line through the origin. So each class is the set of lattice points, other than the origin, on one such line.
Among the 78 pairs in the figure there are 47 distinct classes, and exactly 47 of the pairs are in lowest terms with positive denominator. That is no coincidence.
Proposition. Each class contains exactly one pair $(a, b)$ with $b > 0$ and $\gcd(a, b) = 1$.
Here is the idea. Any pair can be reduced to lowest terms, which gives existence. Two reduced pairs in one class must have denominators that divide each other, which gives uniqueness.
Proof. Existence: given $(c, d)$ in the class, replace it by $(-c, -d)$ if $d < 0$, which is an equivalent pair. Then divide both entries by $g = \gcd(c, d)$. The pair $(c/g, d/g)$ has positive second entry and relatively prime entries. It is equivalent to $(c, d)$ because $c \cdot (d/g) = d \cdot (c/g)$.
Uniqueness: suppose $(a, b) \sim (c, d)$ with $b, d > 0$ and $\gcd(a, b) = \gcd(c, d) = 1$. Then $ad = bc$, so $b \mid ad$. Since $\gcd(a, b) = 1$, the cancellation theorem of the previous unit gives $b \mid d$. The same argument with the roles exchanged gives $d \mid b$. Two positive integers that divide each other are equal, so $b = d$, and then $ad = bc$ gives $a = c$. $\blacksquare$
Well-defined definitions
Now the classes are objects. Can we compute with them? To define something about a class, one chooses a representative and computes with it. This is legitimate only when the answer does not depend on which representative was chosen. A rule with that property is called well defined.
The class of $\frac{2}{3}$ has representatives $(2, 3)$, $(4, 6)$ and $(-6, -9)$, among infinitely many others. Three attempted definitions:
| Rule applied to $(a, b)$ | $(2, 3)$ | $(4, 6)$ | $(-6, -9)$ | Well defined? |
|---|---|---|---|---|
| the numerator $a$ | 2 | 4 | $-6$ | no |
| $a^2 + b^2$ | 13 | 52 | 117 | no |
| the sign of $ab$ | $+1$ | $+1$ | $+1$ | yes |
"The numerator of a fraction" makes sense only after a representative is fixed, such as the one in lowest terms. As a function of the class it is not defined.
A common slip is to treat agreement on a few representatives as proof. The sign of $ab$ is well defined, but checking three representatives does not show it. A proof does: if $ad = bc$, multiply both sides by $bd$ to get $ab \cdot d^2 = cd \cdot b^2$. Since $b^2$ and $d^2$ are positive, $ab$ and $cd$ have the same sign. This is the sign of the rational number.
Arithmetic on fractions faces the same question. Multiplication is defined by $[(a, b)] \cdot [(c, d)] = [(ac, bd)]$. Before this can be called a definition, it must be checked that equivalent inputs give equivalent outputs. The idea is to rearrange the products so that each cross-multiplication hypothesis can be substituted in turn. Suppose $(a, b) \sim (a', b')$ and $(c, d) \sim (c', d')$, so $ab' = ba'$ and $cd' = dc'$. Then
$$(ac)(b'd') = (ab')(cd') = (ba')(dc') = (bd)(a'c'),$$
which says $(ac, bd) \sim (a'c', b'd')$. Addition, $[(a, b)] + [(c, d)] = [(ad + bc, bd)]$, passes the same test:
$$(ad + bc)\, b'd' = (ab')\, dd' + (cd')\, bb' = (ba')\, dd' + (dc')\, bb' = (a'd' + b'c')\, bd.$$
Both operations are well defined, and the rational numbers with these operations are the familiar ones. The same check, with "differ by a multiple of $n$" in place of cross-multiplication, is the central step in building the integers modulo $n$.
Check your understanding. Is the rule $[(a, b)] \mapsto a + b$ well defined on fractions? What about the reciprocal, $[(a, b)] \mapsto [(b, a)]$?
The sum is not: $(1, 2)$ and $(2, 4)$ name the same fraction but give 3 and 6. The reciprocal is well defined for $a \neq 0$, because the condition $ad = bc$ for $(a, b) \sim (c, d)$ is also the condition for $(b, a) \sim (d, c)$ (and $c \neq 0$, since $bc = ad \neq 0$). For $a = 0$ the pair $(b, 0)$ is not in $S$, which is why 0 has no reciprocal.
Where it leads
Quotient sets appear throughout the course, and each time the work is the same: an equivalence relation, its classes, and a proof that operations on the classes are well defined.
- Congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$ with $n$ classes (Congruence Modulo n), and the quotient set with its operations is $\mathbb{Z}_n$ (The Integers Modulo n).
- Congruence modulo a polynomial gives the rings in which new fields are built (Congruence Modulo a Polynomial), and congruence modulo an ideal gives quotient rings in general (Congruence Modulo an Ideal and Quotient Rings).
- In group theory, the cosets of a subgroup are the classes of an equivalence relation. The fact that they partition the group is the heart of Lagrange's theorem.
What we have learned
An equivalence relation is reflexive, symmetric and transitive, and none of the three can be dropped. Its classes partition the set, every partition arises this way, and two elements are related exactly when their classes are equal. The quotient set treats each class as a single element, and a rule on the classes is a definition only if it is well defined, as the arithmetic of fractions is and "the numerator" is not.
Back to the weekdays, which suggest the relation "differ by a multiple of 7". The next article, Congruence Modulo n, proves that differing by a multiple of $n$ is an equivalence relation with exactly $n$ classes, and works out which rules of arithmetic it respects.
References
- Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), §2.1. Brooks/Cole, Cengage Learning. The course text: congruence is shown to be reflexive, symmetric and transitive (Theorem 2.1), and the results on congruence classes (Theorem 2.3, Corollary 2.4) are proved from those three properties alone. record · 44 pages
- Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), §1.2.3, Equivalence Relations and Partitions. Free online at judsonbooks.org. The definition, the theorem that the classes of an equivalence relation form a partition and conversely (Theorem 1.2.25, Corollary 1.2.26), and fractions as an equivalence relation (Example 1.2.21). record · 44 pages