Relations & Equivalence

A relation is just a set of pairs

We built ordered pairs and the product $A \times A$ in the last node. Now cash it in. A relation on $A$ is simply a subset $R \subseteq A \times A$. The pairs in $R$ are the ones that are "related"; the pairs not in $R$ aren't. We write $a \mathbin{R} b$ (read "$a$ is related to $b$") as shorthand for $(a, b) \in R$.

That's the entire definition, and it's deflating in the best way — I love watching students realize it. The relation "$<$" on $\mathbb{R}$ is the set $\{(a, b) \mid a < b\}$. The relation "$=$" is the set $\{(a, a) \mid a \in A\}$ — the diagonal. "Divides" on $\mathbb{Z}$ is $\{(a, b) \mid a \text{ divides } b\}$. Every comparison you've ever made is secretly a subset of a Cartesian product you built two lessons ago. Relations aren't a new kind of thing; they're sets of ordered pairs with attitude.

Three properties to check

Relations come in flavors, and we classify them by three properties. Let $R$ be a relation on $A$.

• Reflexive: every element relates to itself. $\forall a \in A,\ a \mathbin{R} a$.
• Symmetric: the relation doesn't care about direction. $\forall a, b,\ a \mathbin{R} b \implies b \mathbin{R} a$.
• Transitive: relating chains through. $\forall a, b, c,\ (a \mathbin{R} b \land b \mathbin{R} c) \implies a \mathbin{R} c$.

Now drag the usual suspects through the checklist — this is how you build intuition, by interrogating each relation like a detective who won't be fooled by surface appearances:

Read that table like a detective who has seen this kind of thing before. $<$ flunks reflexivity and symmetry — utterly disqualified. $\le$ recovers reflexivity but still isn't symmetric. The two relations that pass all three — $=$ and "same parity" — are special. They have a name, and they run the rest of this lesson.

Equivalence relations: all three at once

A relation that is reflexive, symmetric, and transitive is called an equivalence relation. It's the mathematical formalization of "these things are the same in the way that matters," which is one of the most productive ideas in all of mathematics. Equality is the strictest one (same in every way), but the useful ones are looser: "same parity," "same remainder," "congruent triangles," "anagrams of each other." Different costumes, same equivalence class. You've seen this move before — it's the same spirit as "the squiggle is not the thing."

Given an equivalence relation $\sim$ on $A$, each element $a$ drags along its equivalence class — the set of everything related to it:

$[a] = \{\, x \in A \mid x \sim a \,\}.$

The class $[a]$ is the bag of all elements that are "the same as $a$" according to $\sim$. By reflexivity $a \in [a]$, so nobody's class is empty.

The headline example: congruence mod n

Fix a positive integer $n$. Say $a \equiv b \pmod{n}$ ("$a$ is congruent to $b$ mod $n$") when $n$ divides $a - b$ — equivalently, $a$ and $b$ leave the same remainder when divided by $n$. Let me prove this is an equivalence relation, because I refuse to claim something is true and then just wink at you. The proof is three lines. Watch.

• Reflexive: $n \mid (a - a) = 0$? Yes, $n \mid 0$ always. ✓
• Symmetric: if $n \mid (a - b)$, then $a - b = nk$ for some integer $k$, so $b - a = n(-k)$, so $n \mid (b - a)$. ✓
• Transitive: if $n \mid (a-b)$ and $n \mid (b-c)$, then $a - b = nk$ and $b - c = nm$; adding, $a - c = n(k + m)$, so $n \mid (a-c)$. ✓

All three hold, so congruence mod $n$ is an equivalence relation. Take $n = 3$. The classes are:

$[0] = \{\dots, -3, 0, 3, 6, \dots\}, \quad [1] = \{\dots, -2, 1, 4, 7, \dots\}, \quad [2] = \{\dots, -1, 2, 5, 8, \dots\}.$

Three classes, sorted by remainder $0, 1, 2$. Every integer lands in exactly one. These classes have a name you'll meet in algebra: $\mathbb{Z}/3\mathbb{Z}$, the integers mod $3$.

The fundamental theorem: equivalence relations ARE partitions

Now the punchline, and it's a genuine theorem. Recall partitions from the set-operations lesson: a partition of $A$ chops it into pairwise-disjoint, non-empty blocks that cover all of $A$. Here's the deep fact:

An equivalence relation on $A$ is the exact same data as a partition of $A$.

Two outfits, one body. Given an equivalence relation, its equivalence classes form a partition — and here's why, in two strokes. (1) They cover $A$: every $a$ sits in its own class $[a]$ (reflexivity). (2) They don't overlap: if two classes share even one element, they're identical. Suppose $x \in [a] \cap [b]$. Then $x \sim a$ and $x \sim b$; by symmetry $a \sim x$, and by transitivity $a \sim b$, which forces $[a] = [b]$ (everything related to $a$ is related to $b$ and vice versa). So distinct classes are disjoint. Cover plus disjoint equals partition. Conversely, any partition defines an equivalence relation: declare $a \sim b$ iff they're in the same block. Same data, two outfits.

For mod $3$: the three classes $[0], [1], [2]$ are disjoint and cover $\mathbb{Z}$ — a partition into three blocks. The theorem in the flesh.

The payoff: how mathematicians forge new objects

Here's the teaser that makes this lesson matter far beyond bookkeeping. The phrase "equal up to something" is how mathematicians build new objects — and this is the move that forges number systems. You declare an equivalence relation, then treat each class as a single new thing. It's one of the most audacious tricks in mathematics, and once you see it you'll never unsee it.

The cleanest case: fractions ARE equivalence classes. The fractions $\tfrac{1}{2}, \tfrac{2}{4}, \tfrac{3}{6}, \dots$ are different pairs of integers $(1,2), (2,4), (3,6)$, but they name the same rational number. Define $(a,b) \sim (c,d)$ when $ad = bc$ — that's an equivalence relation on pairs — and a rational number is literally an equivalence class of such pairs. Remember when we "invented fractions" to fix $\mathbb{N}$'s division defect? This is the forge that does it: glue together all the pairs that should be equal, and call each glued bundle a number. Equivalence relations are the forge. You'll see this exact move every time a new number system or quotient object gets built — file it away, because it pays off forever, and mathematicians who don't know it look like they're doing magic when they're just doing this.