Relations and Equivalence

Binary Relations

A binary relation $R$ on a set $A$ is a set of ordered pairs, recording which elements are connected. We write $a\, R\, b$ when $(a, b) \in R$. Relations generalize functions to model any pairwise connection.

Three fundamental properties classify relations:

A relation with all three is an equivalence relation, capturing sameness in some respect.

Structure & Pitfalls

An equivalence relation partitions set $A$ into disjoint equivalence classes of mutually related elements. For example, congruence mod 5 partitions integers into five remainder classes.

A different mix—reflexive, antisymmetric ($a\,R\,b$ and $b\,R\,a \Rightarrow a = b$), and transitive—forms a partial order like $\le$.

Common pitfall: Confusing symmetric with transitive. Symmetry reverses a single pair ($a\,R\,b \Rightarrow b\,R\,a$); transitivity chains two pairs ($a\,R\,b$ and $b\,R\,c \Rightarrow a\,R\,c$). "One step from" on a number line is symmetric but not transitive.