Binary Relations
A binary relation is a subset of ordered pairs from a set, written to show elements are "related." They underlie databases, graphs, and ordering.
Three core properties classify relations:
| Property | Definition | Example |
|---|---|---|
| Reflexive | for all | "is equal to" |
| Symmetric | If , then | "is a sibling of" |
| Transitive | If and , then | "is less than" |
Common pitfall: Do not confuse symmetric with transitive. Symmetry reverses a single pair, while transitivity chains two pairs. "Is one mile from" is symmetric, but walking one mile twice doesn't put you two miles away from the start.
Special Relations
Abstract properties let us reason without knowing the specific items. Two combinations matter most:
- Equivalence relation: Reflexive, symmetric, and transitive. It behaves like "sameness" and partitions the set into disjoint equivalence classes of mutually related elements. Example: "same remainder mod 5."
- Partial order: Reflexive, transitive, and antisymmetric (if and , then ). It captures "ordering" like or subset inclusion, where some elements are incomparable.
Pitfall: A relation can easily possess one property without the others. Never assume a reflexive relation is also symmetric or transitive.