Relations & Partial Orders: Definitions, Properties & Applications

TAKEAWAYS:

• A relation is a subset of $A\times B$ that can be reflexive, symmetric, transitive, or an equivalence relation (partitioning sets into equivalence classes).
• Partial orders (like divisibility or subset relations) are reflexive, antisymmetric, and transitive, visualized via Hasse diagrams to show minimal/maximal elements.
• Equivalence relations partition sets into disjoint equivalence classes, used in hashing (e.g., modulo operations in Khalti’s transaction IDs).
• Closures (reflexive, symmetric, transitive) extend relations to satisfy properties, critical for designing error-free algorithms (e.g., Pathao’s route optimization).
• Applications: Social networks (friendship relations), databases (foreign keys), and scheduling (task dependencies) rely on these structures.
• Exam focus: Prove properties, draw Hasse diagrams, and compute closures—always justify steps with definitions.

---

1. Relations: Definitions and Properties

A relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A\times B$. If $(a,b)\in R$, we write $aRb$. Relations can be represented as:

• Directed graphs (nodes = elements, edges = relations),
• Matrices (rows/columns = elements, entries = 1 if related, 0 otherwise),
• Sets of ordered pairs (e.g., $R=\{(1,2),(2,3)\}$).

Key Properties of Relations

Relations on a set $A$ (i.e., $R\subseteq A\times A$) can have these properties:

Equivalence Relations

A relation that is reflexive, symmetric, and transitive is an equivalence relation. It partitions $A$ into equivalence classes (disjoint subsets where all elements are related).

Example: Let $A=\{1,2,3,4,5,6\}$ and $aRb$ if $a\equiv b(\mathrm{mod}3)$.

• Proof:
  1. Reflexive: $a\equiv a(\mathrm{mod}3)$ (always true).
  2. Symmetric: If $a\equiv b(\mathrm{mod}3)$, then $b\equiv a(\mathrm{mod}3)$.
  3. Transitive: If $a\equiv b$ and $b\equiv c$, then $a\equiv c$.
• Equivalence classes: $\{1,4\},\{2,5\},\{3,6\}$.

Real-world tie-in: Khalti assigns transaction IDs modulo 1000 to group similar transactions (e.g., all IDs ending with 001 are equivalent for fraud detection). This uses equivalence relations to cluster data efficiently.

---

2. Partial Orders and Hasse Diagrams

A partial order is a relation that is reflexive, antisymmetric, and transitive. Notation: $(A,\le )$ where $\le$ is the partial order.

Key Concepts

• Hasse Diagram: A simplified directed acyclic graph (DAG) where:
  • Nodes = elements of $A$,
  • Edges = relations $(a,b)$ if $a<b$ (no transitive edges or reflexive loops).
• Minimal/Maximal Elements:
  • Minimal: No element is related to it (except itself).
  • Least/Greatest: Unique minimal/maximal element related to all others.
• Chains/Antichains:
  • Chain: Totally ordered subset (e.g., $1<2<3$).
  • Antichain: No two elements are comparable (e.g., $\{2,3\}$ in divisibility order).

Example: Let $A=\{1,2,3,6\}$ with $a\le b$ if $a$ divides $b$.

• Hasse Diagram:

  graph TD
    A["1"] --> B["2"]
    A --> C["3"]
    B --> D["6"]
    C --> D

• Minimal element: 1 (divides all others).
• Maximal element: 6 (no element divides it except itself).
• Chains: $\{1,2,6\}$, $\{1,3,6\}$.
• Antichain: $\{2,3\}$ (neither divides the other).

Real-world tie-in: Daraz’s order processing uses partial orders to prioritize tasks:

• Orders are nodes, and "task A must complete before task B" defines edges.
• A Hasse diagram helps visualize dependencies (e.g., payment processing $\le$ inventory check $\le$ shipping).

---

3. Closures of Relations

Given a relation $R$, its closure is the smallest relation containing $R$ that satisfies a property (reflexive, symmetric, transitive).

Algorithm for Transitive Closure (Warshall’s):

1. Initialize $TC=R$.
2. For each $a,b,c\in A$:
   • If $(a,b)\in TC$ and $(b,c)\in TC$, add $(a,c)$ to $TC$.
3. Repeat until no new pairs are added.

Real-world tie-in: NTC’s network routing uses transitive closure to precompute all possible paths between nodes. If path $A\to B$ and $B\to C$ exist, the network knows $A\to C$ is possible without recalculating.

---

4. Applications in Computer Science

---

Exam Tip

1. Prove properties: For equivalence relations, explicitly check reflexivity, symmetry, and transitivity. Use bullet points or tables like above.
2. Draw Hasse diagrams: Always omit reflexive loops and transitive edges. Label minimal/maximal elements clearly.
3. Closures: Show step-by-step additions to the relation. For transitive closure, use Warshall’s algorithm or list all implied pairs.
4. Real-world links: In proofs, tie examples to systems like Khalti (equivalence), Daraz (partial orders), or NTC (transitive closure).
5. Common pitfalls:
   • Forgetting to include all elements in reflexive closure.
   • Misidentifying antisymmetry (e.g., confusing it with asymmetry).
   • Skipping the "disjoint" requirement for equivalence classes.

---

Worked Example (Exam Style): Question: Let $A=\{1,2,3,4\}$ and $R=\{(1,2),(2,4),(3,4)\}$. Is $R$ a partial order? If not, find its transitive closure.

Solution:

1. Check properties:
   • Reflexive: Fails (missing $(1,1),(2,2),(3,3),(4,4)$).
   • Antisymmetric: Passes (no pairs $(a,b)$ and $(b,a)$ with $a\ne b$).
   • Transitive: Fails (missing $(1,4)$ because $(1,2)$ and $(2,4)$ exist).
2. Transitive closure: Add $(1,4)$. Final $TC=\{(1,2),(1,4),(2,4),(3,4)\}$.
3. Hasse Diagram:

   graph TD
     A["1"] --> B["2"]
     A --> D["4"]
     C["3"] --> D

   • Minimal elements: 1, 3.
   • Maximal element: 4.

Why this matters: This mirrors how Pathao’s ride-matching algorithm ensures no circular dependencies in task scheduling (e.g., "pickup" must precede "drop-off"). The transitive closure guarantees all implied dependencies are accounted for.