Day 38 — Relations

Day 38 — Relations

Stage IV · concept day
Goal: Define binary relations; represent them as digraphs and matrices; check reflexive, symmetric, transitive, antisymmetric properties; understand reflexive/symmetric/transitive closures (paths for transitive); compose relations.

Why this matters

“Depends on,” “reaches,” “⊆,” “≡ mod \(n\),” “≤,” edges in graphs—all are relations. Properties classify them into equivalence relations (Day 39) and partial orders (Day 40). Transitive closure is “path exists”—the mathematical name for reachability in a digraph.

Theory

Binary relations

A binary relation on a set \(A\) is \(R \subseteq A\times A\).
(More generally from \(A\) to \(B\): \(R\subseteq A\times B\).)
Write \(a\,R\,b\) or \((a,b)\in R\).

Representations

Digraph: vertices \(A\); directed edge \(a\to b\) iff \(a\,R\,b\). Loops mean \(a\,R\,a\).

Boolean matrix: order \(A=\{a_1,\ldots,a_n\}\); \(M_{ij}=1\) iff \(a_i\,R\,a_j\).

Core properties (on \(A\))

Property	Definition
Reflexive	\(\forall a\in A,\; a\,R\,a\)
Symmetric	\(\forall a,b,\; a\,R\,b \Rightarrow b\,R\,a\)
Antisymmetric	\(\forall a,b,\; (a\,R\,b \wedge b\,R\,a) \Rightarrow a=b\)
Transitive	\(\forall a,b,c,\; (a\,R\,b \wedge b\,R\,c) \Rightarrow a\,R\,c\)
Irreflexive	\(\forall a,\; \neg(a\,R\,a)\)
Asymmetric	\(a\,R\,b \Rightarrow \neg(b\,R\,a)\) (implies irreflexive)

Note: Antisymmetric is not “not symmetric.” Equality is both symmetric and antisymmetric. \(<\) is antisymmetric? If \(a<b\) and \(b<a\) then false, so implication to \(a=b\) holds vacuously—actually strict orders are asymmetric. \(\le\) is antisymmetric and reflexive.

Closures (idea)

Given \(R\), the \(P\)-closure is the smallest relation containing \(R\) with property \(P\) (when it exists).

• Reflexive closure: \(R \cup \Delta_A\) where \(\Delta_A=\{(a,a):a\in A\}\).
  
• Symmetric closure: \(R \cup R^{-1}\) where \(R^{-1}=\{(b,a):(a,b)\in R\}\).
  
• Transitive closure: \(R^+\) (or \(R^*\) reflexive-transitive) — edges for paths of positive length;
  \[R^+ = \bigcup_{k\ge 1} R^k,\]
  where \(R^1=R\), \(R^{k+1}=R^k \circ R\) (composition).
  On finite digraphs: \((a,b)\) in transitive closure iff path from \(a\) to \(b\).

Composition of relations

For \(R\subseteq A\times B\), \(S\subseteq B\times C\),
\[S \circ R = \{ (a,c) : \exists b\in B\, (a\,R\,b \wedge b\,S\,c) \}.\]
(Order conventions vary: some write \(R\circ S\) for apply \(R\) first—fix left/right. We use “\(S\circ R\) means \(R\) first then \(S\)” like functions.)

Composition is associative; identity relation \(\Delta_A\) acts as unit for relations on \(A\).

Matrix view of composition

Boolean matrix product: \((MS)_{ik} = \bigvee_j (M_{ij} \wedge S_{jk})\). Transitive closure via repeated product / Warshall awareness.

Examples of relations

• \(=\) on any \(A\): reflexive, symmetric, transitive (equivalence).
  
• \(\le\) on \(\mathbb{R}\): reflexive, antisymmetric, transitive (partial/total order).
  
• \(<\) on \(\mathbb{R}\): irreflexive, transitive, asymmetric.
  
• “divides” on \(\mathbb{Z}^+\): partial order.
  
• “is a parent of”: neither symmetric nor transitive typically.
  
• empty relation: transitive, symmetric; reflexive only if \(A=\emptyset\).
  
• full relation \(A\times A\): reflexive, symmetric, transitive.

Checking properties algorithmically (finite)

• Reflexive: all diagonal matrix entries \(1\).
  
• Symmetric: matrix equals its transpose.
  
• Transitive: harder—check \(M\vee (M*M) = M\) boolean, or use closure and compare.

Worked examples

Example 1 — List pairs

\(A=\{1,2,3\}\), \(R=\{(1,1),(1,2),(2,2),(3,3)\}\).
Reflexive? Missing \((2?\) has \(2,2)\), has all diagonal—yes if only those… has \(1,1;2,2;3,3\) yes. Symmetric? \((1,2)\) without \((2,1)\)—no. Transitive? \((1,2)\) and … no further.

Example 2 — Divisibility

On \(\{1,2,3,4,6\}\), \(a\mid b\). Reflexive yes; transitive yes; antisymmetric yes (on positives).

Example 3 — Mod \(n\)

\(a \equiv b \pmod{n}\): equivalence (Day 39).

Example 4 — Symmetric closure

\(R=\{(1,2)\}\) on \(\{1,2\}\): add \((2,1)\).

Example 5 — Reflexive closure

Same \(R\): add \((1,1),(2,2)\).

Example 6 — Transitive closure / path

\(R=\{(a,b),(b,c)\}\): closure adds \((a,c)\).

Example 7 — Composition

\(R=\{(1,2)\}\), \(S=\{(2,3)\}\): \(S\circ R = \{(1,3)\}\).

Example 8 — Not transitive

“friend” on social graph often not transitive; transitive closure is “connected in friendship undirected” if symmetrized.

Example 9 — Matrix

\(A=\{1,2\}\), \(R=\{(1,1),(1,2)\}\): \(M = \begin{pmatrix}1&1\\0&0\end{pmatrix}\).

Example 10 — Antisymmetric vs asymmetric

\(\le\) antisymmetric not asymmetric (\(a\le a\)). \(<\) asymmetric.

Example 11 — Reachability

Web links: transitive closure ≈ can reach by following links.

Example 12 — \(R\circ R\)

\((a,c)\in R^2\) iff some mid \(b\) with two-step path.

Example 13 — Equality as \(\Delta\)

Smallest reflexive relation on \(A\).

Example 14 — Failure of symmetry + antisymmetry

If both, then \(a\,R\,b\) implies \(a=b\): relation \(\subseteq \Delta_A\).

Exercises

1. For \(A=\{1,2,3\}\) list a relation that is reflexive only among the four properties—or state which hold for \(R=\Delta_A\).
   
2. Check properties of \(<\) on \(\mathbb{Z}\).
   
3. Check properties of \(\mid\) on \(\mathbb{Z}^+\).
   
4. Give a relation that is symmetric but not transitive.
   
5. Give transitive but not symmetric.
   
6. Compute symmetric and reflexive closures of \(\{(1,2),(2,3)\}\) on \(\{1,2,3\}\).
   
7. Compute transitive closure of that same \(R\).
   
8. Compose \(R=\{(a,b),(b,b)\}\), \(S=\{(b,c)\}\) on \(\{a,b,c\}\).
   
9. Prove composition is associative (element chase with witnesses).
   
10. Prove \(R\) transitive iff \(R\circ R \subseteq R\).
    
11. Prove \(R\) reflexive iff \(\Delta_A \subseteq R\).
    
12. Matrix for “\(\le\)” on \(\{1,2,3\}\).
    
13. Is the empty relation on \(\{1,2\}\) transitive? Reflexive?
    
14. Prove: if \(R\) and \(S\) symmetric, \(R\cap S\) symmetric. What about \(R\cup S\)? \(R\circ S\)?
    
15. Find \(R\) with \(R\circ R = R\) (transitive and … idempotent under composition).
    
16. Digraph: draw transitive closure of a 4-edge example.
    
17. CS: model “package depends on” — which properties expected?
    
18. Antisymmetric: show \(\subseteq\) on \(\mathcal{P}(X)\) is antisymmetric.
    
19. Can a relation be both symmetric and asymmetric? Only empty on nonempty? Discuss.
    
20. Warshall awareness: one sentence what it computes.
    
21. Prove \(R^+\) is transitive.
    
22. Number of binary relations on a set of \(n\) elements: \(2^{n^2}\).
    
23. Number of reflexive relations on \(n\) elements.
    
24. If \(M\) is adjacency matrix, what does \(M^2\) count over integers vs boolean?
    
25. Give relation for “shares a class with” and discuss transitivity.

CS connection

• DAGs / dependency graphs: transitive closure = all transitive deps.
  
• RBAC: user–role–permission as composition of relations.
  
• SQL joins implement composition-like patterns.
  
• Union-find maintains equivalence closure (Day 39).
  
• Type subtyping as preorder (reflexive transitive).
  
• Adjacency matrices and reachability algorithms.

Common pitfalls

Pitfall	What to do instead
Antisymmetric = not symmetric	Different definitions
Forgetting loops for reflexive	Check diagonal
Transitive closure = one step	All path lengths
Composition order confusion	Fix a convention and stick to it
Assuming friend-of-friend is friend	Not without closure
Infinite \(A\) and “smallest” closure	Still defined as intersection of all super-relations with \(P\)

Checkpoint

• Define relation; digraph; matrix
  
• Test four main properties on examples
  
• Form reflexive/symmetric/transitive closures
  
• Compose two small relations
  
• State \(R\) transitive iff \(R\circ R\subseteq R\)
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — closures as operators

Let \(\mathrm{Ref}, \mathrm{Sym}, \mathrm{Trans}\) denote closure operators on relations on a fixed finite \(A\). Then:

• \(\mathrm{Ref}(R)=R\cup\Delta\)
  
• \(\mathrm{Sym}(R)=R\cup R^{-1}\)
  
• \(\mathrm{Trans}(R)=R^+\) path relation

Order of applying closures matters for intermediate results; the equivalence closure is the smallest equivalence containing \(R\) (reflexive-symmetric-transitive closure), computed e.g. by undirected connectivity if you first symmetrize.

Warshall / Floyd awareness

Warshall’s algorithm computes transitive closure in \(O(n^3)\) boolean operations on an \(n\)-vertex digraph—dynamic programming over intermediate vertices. Same skeleton as Floyd–Warshall for shortest paths with different “semiring.”

Preorders

Reflexive + transitive (not necessarily antisymmetric) = preorder.
Example: reachability with loops; “\(a\) maps to \(b\) under rewriting.”
Antisymmetrizing a preorder yields a partial order on equivalence classes.

More worked examples

Example 15 — Divisibility matrix
On \(\{1,2,3,4\}\), write \(0/1\) matrix for \(\mid\).

Example 16 — Composition count
\((a,c)\in R\circ R\) iff path length 2.

Example 17 — Smallest transitive containing a cycle
\(R=\{(1,2),(2,3),(3,1)\}\) ⇒ \(R^+\) is full \(A\times A\) on \(\{1,2,3\}\).

Example 18 — Antisymmetric failure
\(R=\{(1,2),(2,1)\}\) not antisymmetric on \(\{1,2\}\).

Additional exercises

26. Prove \(R\) symmetric iff \(R=R^{-1}\).
    
27. Compute equivalence closure of \(\{(1,2),(2,3)\}\) on \(\{1,2,3,4\}\).
    
28. Show intersection of transitive relations is transitive; union need not be.
    
29. Number of reflexive symmetric relations on \(n\) elements (undirected graphs with loops forced).
    
30. CS: model “imports” relation; what does transitive closure mean for build systems?

Extended practice workshop

Property checklist on standard relations

For each, mark R/S/T/A (antisym):

1. \(=\) on any \(A\).
   
2. \(\neq\) on a set with \(\ge 2\) elements.
   
3. \(\le\) on \(\mathbb{R}\).
   
4. \(<\) on \(\mathbb{R}\).
   
5. \(\mid\) on \(\mathbb{Z}^+\).
   
6. “is parent of” on people (assume no cycles).
   
7. Empty relation on \(\{1,2,3\}\).
   
8. Full relation \(A\times A\).

Closure computations

9. \(R=\{(1,2),(2,1),(2,3)\}\) on \(\{1,2,3\}\): Ref, Sym, Trans closures (separately).
   
10. Equivalence closure of \(R\) (combine).
    
11. Path interpretation of Trans\((R)\).

Composition

12. \(R=\{(a,b),(b,c),(c,c)\}\), compute \(R\circ R\) and \(R\circ R\circ R\).
    
13. Prove \(R\) transitive iff \(R\circ R\subseteq R\) (both directions).
    
14. Identity \(\Delta\) satisfies \(R\circ\Delta=R=\Delta\circ R\).

Matrix

15. Write boolean matrix for \(\le\) on \(\{1,2,3\}\).
    
16. Boolean square of that matrix—interpret.

CS scenarios

17. Package depends-on: expected properties?
    
18. Git “parent commit”: transitive closure = ancestor.
    
19. RBAC user→role→permission as composition.
    
20. Reachability in a call graph.

Property decision tree

Need ignore differences? → aim for equivalence (add SYM)
Need ranking/dependency? → aim for partial order (add ANTI, keep REF+TRANS)
Need reachability? → take TRANS closure of edge relation

Quick theorems to recite

1. \(R\) reflexive iff \(\Delta\subseteq R\).
   
2. \(R\) symmetric iff \(R=R^{-1}\).
   
3. \(R\) transitive iff \(R\circ R\subseteq R\).
   
4. Transitive closure ↔︎ paths of length \(\ge 1\).
   
5. Composition is associative; \(\Delta\) is unit.
   
6. Number of relations on \(n\) elements: \(2^{n^2}\).

Checkpoint recap (relations day)

• Test four properties on a 4-pair relation
  
• Form Ref/Sym/Trans closures
  
• Compose two relations
  
• Draw a digraph and its transitive closure
  
• Matrix for a small relation

Synthesis

A binary relation is “just” a set of pairs, but the named properties (REF, SYM, TRANS, ANTI) carve out the structures CS uses constantly: equivalence (clustering), partial order (dependencies), and reachability (transitive closure of edges). Composition is relational join; closures are the “least structure containing \(R\).”

Property checklist (run every example)

Property	Test	Closure idea
Reflexive	\(\Delta\subseteq R\)	Add all \((a,a)\)
Symmetric	\((a,b)\in R\Rightarrow(b,a)\in R\)	Add reverse edges
Transitive	paths of length \(2\) imply edge	Add all path pairs
Antisymmetric	\((a,b)\) and \((b,a)\) ⇒ \(a=b\)	Not a “closure” target usually

More worked examples

Example — Composition as path length 2.
If \(R\) is edges, \((a,c)\in R\circ R\) iff \(\exists b\,(aRb\wedge bRc)\). Transitivity says \(R\circ R\subseteq R\).

Example — Reflexive-transitive closure.
Reachability with self: \(R^*=\bigcup_{n\ge 0} R^n\) with \(R^0=\Delta\). In graphs: paths of any length including \(0\).

Example — “Depends on” for packages.
Typically not symmetric; should be acyclic for install order; transitive closure = full dependency set. Antisymmetry fails if mutual depends (cycle of equals)—real systems forbid or collapse.

Example — Matrix boolean square.
If \(M\) is the adjacency matrix (boolean), \(M\vee M^2\vee\cdots\) builds reachability (Warshall/Floyd–Warshall family). Hand-compute \(2\times 2\) or \(3\times 3\) examples.

Example — Counting.
On an \(n\)-element set there are \(2^{n^2}\) relations; \(2^{n(n-1)/2}\) undirected simple graphs if you force SYM and irreflexive—different counting conventions.

Extra exercises (synthesis)

31. For \(R=\{(1,2),(2,3)\}\) on \(\{1,2,3\}\), compute Ref, Sym, Trans closures separately and the equivalence closure.
    
32. Prove: \(R\) symmetric iff \(R=R^{-1}\).
    
33. Prove: \(R\) transitive iff \(R\circ R\subseteq R\).
    
34. Show composition is associative: \((T\circ S)\circ R = T\circ(S\circ R)\).
    
35. RBAC: users \(U\), roles \(S\), permissions \(P\); relations \(R_1\subseteq U\times S\), \(R_2\subseteq S\times P\); interpret \(R_2\circ R_1\).
    
36. Draw digraph of \(<\) on \(\{1,2,3,4\}\) and mark transitive edges not in the Hasse (cover) relation.

Map forward

• Equivalence = REF + SYM + TRANS → partitions (Day 39).
  
• Partial order = REF + ANTI + TRANS → Hasse, topo sort (Day 40).
  
• Functions = special relations: left-total and right-unique (Days 41–42).

Property tests are boolean; closures are constructive. Always compute on a \(3\)–\(4\) element set before claiming intuition.

Tomorrow

Day 39 — Equivalence relations. Partitions ↔︎ equivalences; classes; \(\mathbb{Z}/n\mathbb{Z}\); well-defined operations awareness; refining partitions.