2.1 Binary Relations

A binary relation R from set A to set B is any subset of A × B: R ⊆ A × B. If (a, b) ∈ R we write a R b. A relation on A is a subset of A × A. Since |A × A| = n^2 when |A| = n, there are 2^(n^2) possible relations on A.

A relation on a finite set can be represented as:

• a zero-one matrix M where M[i][j] = 1 iff (a_i, a_j) ∈ R, or
• a directed graph (digraph) with an arrow from a to b for each pair (a, b) ∈ R.

2.2 Properties of Relations on a Set A

Caution: symmetric and antisymmetric are not opposites. The relation {(1,1), (2,2)} is both; the relation {(1,2), (2,1), (1,3)} is neither.

2.3 Equivalence Relations and Partitions

A relation that is reflexive, symmetric, and transitive is an equivalence relation. It partitions A into disjoint equivalence classes [a] = {x ∈ A | x R a}; conversely every partition of A defines an equivalence relation (this is the Fundamental Theorem of Equivalence Relations).

2.4 Worked Example 1 — Congruence Modulo 3

Claim: R on Z defined by a R b iff a ≡ b (mod 3), i.e., 3 | (a − b), is an equivalence relation.

1. Reflexive: a − a = 0 = 3·0, so 3 | (a − a). ✔
2. Symmetric: if 3 | (a − b), say a − b = 3k, then b − a = 3(−k), so 3 | (b − a). ✔
3. Transitive: if a − b = 3k and b − c = 3m, then a − c = (a − b) + (b − c) = 3(k + m). ✔

The equivalence classes are the three residue classes: [0] = {..., −3, 0, 3, 6, ...}, [1] = {..., −2, 1, 4, 7, ...}, [2] = {..., −1, 2, 5, 8, ...}. They are pairwise disjoint and their union is Z — a partition, exactly as the theorem promises. This is the mathematical basis of hash bucketing: h(k) = k mod m throws every key into one of m equivalence classes.

2.5 Partial Orders and Hasse Diagrams

A relation that is reflexive, antisymmetric, and transitive is a partial order; the pair (A, ⪯) is a poset. Elements a, b are comparable if a ⪯ b or b ⪯ a; a poset where every pair is comparable is a total order (e.g., (Z, ≤)).

A Hasse diagram draws a poset with all redundancy removed: omit loops (reflexivity), omit edges implied by transitivity, and draw the smaller element below the larger so arrowheads are unnecessary.

2.6 Worked Example 2 — Hasse Diagram of D12 = ({1,2,3,4,6,12}, |)

Divisibility is a partial order on the divisors of 12. Cover relations (a covered-by b with nothing in between): 1–2, 1–3, 2–4, 2–6, 3–6, 4–12, 6–12.

        12
       /  \
      4    6
       \  / \
        2    3
         \  /
          1

• Minimal & least element: 1 (divides everything).
• Maximal & greatest element: 12 (everything divides it).
• 4 and 6 are incomparable (4 ∤ 6 and 6 ∤ 4) — this is what makes the order partial.
• Every pair has a LUB (their lcm) and a GLB (their gcd), so D12 is a lattice: LUB(4, 6) = 12, GLB(4, 6) = 2.

2.7 Closures of a Relation

The closure of R with respect to a property P is the smallest relation containing R that has property P.

Example: R = {(1,2), (2,3)} on A = {1,2,3}:

• Reflexive closure = R ∪ {(1,1), (2,2), (3,3)}.
• Symmetric closure = R ∪ {(2,1), (3,2)}.
• Transitive closure = R ∪ {(1,3)} — computed in general by Warshall's algorithm in O(n^3), the same algorithm compilers use for reachability analysis.

2.8 CS Applications

Topological sorting of a task-dependency poset schedules builds (make, npm); equivalence classes drive union–find in Kruskal's algorithm; database normalization reasons over functional-dependency closures.

🎯 Exam Focus

1. Define reflexive, symmetric, antisymmetric, and transitive relations with one example and one counterexample each.
2. Prove that "a R b iff a ≡ b (mod 5)" is an equivalence relation on Z and list its equivalence classes.
3. Draw the Hasse diagram of ({1, 2, 3, 4, 6, 8, 12, 24}, |). Identify maximal, minimal, greatest, and least elements.
4. How many relations on a set of 3 elements are (a) possible, (b) reflexive? (Answer: 2^9 = 512 and 2^6 = 64 — justify.)
5. Find the transitive closure of R = {(1,2), (2,1), (2,3), (3,4)} on {1,2,3,4}.
6. Show that the intersection of two equivalence relations on A is an equivalence relation, but their union need not be.