Relations

Understanding Relations

A relation describes how elements of one set connect to elements of another (or the same) set, as a collection of ordered pairs. Beyond simple pairings, discrete math cares about three specific properties — reflexivity, symmetry, and transitivity — because together they determine whether a relation behaves like an equality (an equivalence relation) or like an ordering (a partial order), which shapes how we can group, sort, or compare the underlying elements.

Key Definitions & Formulas

• Reflexive: every element relates to itself, i.e. (a,a) is in R for all a.
• Symmetric: if (a,b) is in R, then (b,a) must be too.
• Transitive: if (a,b) and (b,c) are in R, then (a,c) must be too.
• Equivalence relation: reflexive, symmetric, and transitive all at once — it partitions the set into equivalence classes.
• Closure: the smallest relation containing R that also satisfies a given property (e.g. transitive closure).

Worked Example

Let A = {1,2,3} and R = {(1,1),(2,2),(3,3),(1,2),(2,1)}. R is reflexive (every (a,a) pair is present) and symmetric (1,2) and (2,1) both appear), and checking all chains confirms it's transitive too — so R is an equivalence relation that splits A into the classes {1,2} and {3}.

Where This Is Used

• Database normalization, where functional dependencies are relations with specific properties.
• Scheduling and task ordering, modeled with partial order relations.
• Grouping/clustering algorithms, which rely on equivalence-like relations.
• Graph theory, since every graph is fundamentally a relation on its vertex set.