Relations and Equivalence

Structured Connections

A binary relation $R$ on a set $A$ is a set of ordered pairs from $A$ — it records which elements are "related." We write $a\, R\, b$ when $(a, b) \in R$. "Equals," "is less than," "divides," and "is congruent to mod $n$" are all relations. A function is a special relation; more generally, relations model any pairwise connection.

Three properties classify relations:

• Reflexive — $a\, R\, a$ for every $a$ (each element relates to itself).
• Symmetric — $a\, R\, b \Rightarrow b\, R\, a$ (relatedness is mutual).
• Transitive — $a\, R\, b$ and $b\, R\, c \Rightarrow a\, R\, c$ (relatedness chains).

A relation with all three properties is an equivalence relation. Equivalence relations behave like "sameness in some respect" and have a beautiful structure: each partitions the set $A$ into disjoint equivalence classes — maximal groups of mutually related elements — that together cover all of $A$. "Congruent mod $5$" partitions the integers into the five remainder classes $\{0, 5, 10, \dots\}, \{1, 6, 11, \dots\}, \dots$. Conversely, every partition arises from an equivalence relation, so equivalence relations and partitions are two views of the same idea.

A different combination — reflexive, antisymmetric ($a\,R\,b$ and $b\,R\,a \Rightarrow a = b$), and transitive — is a partial order, capturing "ordering" like $\le$ or subset inclusion, where some elements may be incomparable. Recognizing which properties a relation has tells you its structure immediately, without examining every pair.

Common pitfall: confusing symmetric with transitive, or assuming a relation with one property has the others. Symmetry reverses a single pair ($a\,R\,b \Rightarrow b\,R\,a$); transitivity chains two pairs into a third. A relation can have one without the other — "is one step from" (on a number line) is symmetric but not transitive. Only relations with all three of reflexive, symmetric, and transitive are equivalence relations.