Relations

Connecting Elements

A binary relation $R$ on a set is a collection of ordered pairs — it says which elements are "related." "Is less than," "is equal to," "divides," and "is a sibling of" are all relations. Formally, $R$ is a subset of the set of all pairs $(a, b)$, and we write $a\, R\, b$ when the pair is in $R$. Relations underlie ordering, equivalence, databases, and graphs.

Three properties classify relations:

• Reflexive — every element relates to itself: $a\, R\, a$ for all $a$.
• Symmetric — if $a\, R\, b$ then $b\, R\, a$.
• Transitive — if $a\, R\, b$ and $b\, R\, c$ then $a\, R\, c$.

Two combinations are especially important. An equivalence relation is reflexive, symmetric, and transitive — it behaves like "sameness" and partitions the set into disjoint equivalence classes (all elements equivalent to each other). "Has the same remainder mod 5" is an equivalence relation; its classes are the five remainder groups. A partial order is reflexive, antisymmetric (if $a\,R\,b$ and $b\,R\,a$ then $a = b$), and transitive — it captures "ordering" like $\le$ or "divides" or subset inclusion, where some elements may be incomparable.

The power of these properties is that they let us reason about a relation abstractly: knowing a relation is an equivalence relation immediately tells us it partitions the set, no matter what the relation actually is.

Common pitfall: confusing symmetric with transitive, or assuming a relation with one property has the others. Symmetry is about reversing a single pair ($a\,R\,b \Rightarrow b\,R\,a$); transitivity chains two pairs into a third ($a\,R\,b, b\,R\,c \Rightarrow a\,R\,c$). A relation can easily have one without the other — "is one mile from" is symmetric but not transitive.