Key Takeaways: Relations

A one-page reference card. Reread it before an exam or before classifying your next relation.

Core definition

A binary relation from $A$ to $B$ is a subset $R \subseteq A \times B$. Write $a\,R\,b$ for $(a,b) \in R$. A relation on $A$ has $A$ on both sides. On an $n$-element set there are $n^2$ possible pairs and $2^{n^2}$ possible relations. A function is the special relation where every input appears in exactly one pair.

Three representations (interconvertible)

Representation Form Best for Cost
Set of pairs $\{(a,b) \mid a\,R\,b\}$ definition, membership tests, sparse data $O(\lvert R\rvert)$
Boolean matrix $M_{ij}=1 \iff (a_i,a_j)\in R$ properties as patterns, $O(1)$ lookup $O(n^2)$ always
Directed graph node/element, arrow/pair paths, reachability varies

The four properties (all quantified over the whole set $A$)

Property Condition Digraph Matrix
Reflexive $\forall a,\ (a,a)\in R$ self-loop on every node diagonal all $1$s
Symmetric $(a,b)\in R \rightarrow (b,a)\in R$ every arrow has its reverse $M = M^{\mathsf{T}}$
Antisymmetric $(a,b),(b,a)\in R \rightarrow a=b$ no 2-cycle between distinct nodes $M_{ij}\land M_{ji}\Rightarrow i=j$
Transitive $(a,b),(b,c)\in R \rightarrow (a,c)\in R$ every 2-step path has a shortcut no length-2 path lacks an edge

Trap: symmetric and antisymmetric are NOT opposites. A relation can be both (equality), neither, or exactly one. Read each definition literally.

Quick mental model: three properties demand a missing arrow (self-loop / reverse / shortcut); antisymmetric forbids a configuration instead.

Named combinations

Reflexive Symmetric Antisymmetric Transitive Name Chapter
✓ ✓ — ✓ equivalence relation 12
✓ — ✓ ✓ partial order 13

Equivalence relations ↔ partitions (the key theorem)

  • Equivalence relation = reflexive + symmetric + transitive (a generalized equality).
  • Equivalence class: $[a] = \{x \in A \mid (a,x)\in R\}$. Any member is a representative; $[a]=[b] \iff (a,b)\in R$.
  • Partition: non-empty blocks, pairwise disjoint, union $=A$.
  • Theorem (bijection): the classes of an equivalence relation form a partition; every partition comes from exactly one equivalence relation. Choosing one is choosing the other.
  • Proof skeleton (classes form a partition): non-empty + covering from reflexivity; "overlap $\Rightarrow$ equal" from symmetry + transitivity.
  • Examples: congruent mod $n$ → $n$ residue classes; "same hash" → buckets; connected components (Ch. 28).

Closures (smallest superset gaining a property)

Closure What to add Passes
Reflexive the diagonal $\{(a,a)\}$ one
Symmetric the transpose $\{(b,a)\mid (a,b)\in R\}$ one
Transitive a shortcut for every path (= reachability) iterate until stable
  • Transitive closure $(a,b)$ holds $\iff$ there is a path $a\to\cdots\to b$ (length $\ge 1$).
  • Why iterate: a new shortcut can create a new 2-step path needing its own shortcut (cascade). Terminates because only $n^2$ pairs exist.
  • $O(n^3)$ in practice via Warshall's algorithm (cousin of Floyd–Warshall, Ch. 29).
  • Trap: transitive closure $\ne$ equivalence closure. For the smallest equivalence relation containing $R$, take reflexive and symmetric and transitive closure.

Relations in databases (the relational model)

A $k$-column table is a $k$-ary relation $\subseteq D_1 \times \cdots \times D_k$; each row is a tuple.

SQL Relational operation In our terms
WHERE selection $\sigma$ keep rows satisfying a predicate (a subset)
SELECT col projection $\pi$ keep only some columns (sub-tuples)
UNION/INTERSECT/EXCEPT $\cup$ / $\cap$ / $\setminus$ Chapter 8 set operations
CROSS JOIN Cartesian product $\times$ all row combinations ($m\times n$ rows)
JOIN ... ON product then selection combine, keep rows agreeing on the key
  • A key = column set whose projection is injective (Ch. 9): distinct rows → distinct key tuples. PRIMARY KEY/UNIQUE enforces that injectivity.
  • A forgotten ON condition $\Rightarrow$ the raw Cartesian product $\Rightarrow$ row explosion.

Decision aid: "what kind of relation is this?"

Reflexive + symmetric + transitive?      -> equivalence relation -> think PARTITION / buckets
Reflexive + antisymmetric + transitive?  -> partial order (Ch. 13) -> think ORDERING / precedence
Need "everything reachable from a"?       -> TRANSITIVE CLOSURE
Two-column table / who-relates-to-whom?   -> binary relation; store as set of pairs or matrix

Common pitfalls

  • Checking a property on a few examples instead of the universal statement.
  • Confusing antisymmetric with "not symmetric."
  • Expecting one pass to compute transitive closure (it cascades — iterate).
  • Conflating transitive closure with making a relation an equivalence relation.
  • In code: a repeated comprehension variable shadows, it does not unify — use two names + if b==x.

Toolkit additions (relations.py)

  • is_equivalence(rel, dom) — True iff rel is reflexive, symmetric, transitive on dom.
  • closure_transitive(rel) — smallest transitive relation containing rel (reachability).
  • (topo_sort(dag) arrives in Chapter 13, once partial orders are defined.)