Relations & Closures: Types, Properties, and Applications

1. Introduction to Relations

1.1 Definition and Representation

A relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A\times B$: $$R\subseteq A\times B$$

• If $(a,b)\in R$, we write $aRb$.
• Representation methods:
  • Roster form: List of ordered pairs (e.g., $R=\{(1,2),(2,3)\}$).
  • Matrix representation: Binary matrix $M$ where $M_{ij}=1$ if $(a_i,a_j)\in R$, else $0$.
  • Directed graph: Nodes = elements of $A$, edges = ordered pairs.

Example: Let $A=\{1,2,3\}$, $R=\{(1,2),(2,3),(3,1)\}$. Matrix:

   1  2  3
1 [0,1,0]
2 [0,0,1]
3 [1,0,0]

1.2 Types of Relations on a Set (Binary Relations)

For a relation $R$ on $A\times A$, key properties:

Worked Example: Check if $R=\{(1,2),(2,1),(2,3)\}$ on $\{1,2,3\}$ is:

• Not reflexive: Missing $(1,1),(3,3)$.
• Symmetric: $(1,2)$ has $(2,1)$, but $(2,3)$ lacks $(3,2)$. False.
• Transitive: $(1,2)$ and $(2,3)$ imply $(1,3)\notin R$. False.

---

2. Relation Closures

Closures extend a relation to satisfy a property with minimal additions.

2.1 Reflexive Closure

Definition: Smallest reflexive relation $R^{+}$ containing $R$. Method:

1. Add all pairs $(a,a)$ for $a\in A$ if missing.
2. Formula: $R^{+}=R\cup \{(a,a)\mid a\in A\}$.

Example: Let $A=\{1,2\}$, $R=\{(1,2)\}$. Reflexive closure: $R^{+}=\{(1,1),(2,2),(1,2)\}$.

2.2 Symmetric Closure

Definition: Smallest symmetric relation $R^{\ast }$ containing $R$. Method:

1. For every $(a,b)\in R$, add $(b,a)$ if not present.
2. Formula: $R^{\ast }=R\cup \{(b,a)\mid (a,b)\in R\}$.

Example: Let $R=\{(1,2),(2,3)\}$. Symmetric closure: $R^{\ast }=\{(1,2),(2,1),(2,3),(3,2)\}$.

2.3 Transitive Closure

Definition: Smallest transitive relation $R^{\tau }$ containing $R$. Methods:

1. Warshall’s Algorithm (for matrix representation):
   • Initialize $M=$ adjacency matrix of $R$.
   • For $k=1$ to $n$: $M[i][j]=M[i][j]\vee (M[i][k]\wedge M[k][j])$.
2. Graph-based: Add edges for all paths of length ≥2.

Example: Let $R=\{(1,2),(2,3)\}$ on $\{1,2,3\}$. Transitive closure: $R^{\tau }=\{(1,2),(2,3),(1,3)\}$.

Worked Example: Find transitive closure of $R=\{(1,2),(2,3),(3,4)\}$.

• Add $(1,3)$ (via $1\to 2\to 3$).
• Add $(1,4)$ (via $1\to 2\to 3\to 4$).
• Final: $R^{\tau }=\{(1,2),(2,3),(3,4),(1,3),(1,4),(2,4)\}$.

---

3. Equivalence Relations and Partitions

3.1 Equivalence Relations

A relation $R$ is equivalence if it is reflexive, symmetric, and transitive.

• Equivalence classes: For $a\in A$, $[a]=\{b\in A\mid aRb\}$.
• Partition: Set of disjoint equivalence classes covers $A$.

Example: Let $A=\{1,2,3,4\}$, $R=\{(1,1),(2,2),(3,3),(4,4),(1,3),(3,1),(2,4),(4,2)\}$.

• Equivalence classes: $[1]=\{1,3\}$, $[2]=\{2,4\}$.
• Partition: $\{\{1,3\},\{2,4\}\}$.

3.2 Partial Orders

A relation $\le$ is a partial order if:

1. Reflexive.
2. Antisymmetric.
3. Transitive.

• Hasse Diagram: Visual representation omitting reflexive/transitive edges.

Example: Let $A=\{1,2,5,8,16,32\}$, $R=$ "divides" relation.

• Hasse Diagram:

      32
      |
      16
     /  \
    8    5
    |
    2
    |
    1
  

• Elements:
  • Maximal: 32 (no element above it).
  • Minimal: 1 (no element below it).
  • Greatest: 32 (divides all others).
  • Least: 1 (divisible by all others).

---

4. Applications of Relations

---

5. Common Mistakes and Clarifications

1. Confusing Symmetric/Antisymmetric:

   • Symmetric: $(a,b)\in R⟹(b,a)\in R$.
   • Antisymmetric: $(a,b)\wedge (b,a)⟹a=b$.
   • Example: $R=\{(1,2),(2,1)\}$ is symmetric but not antisymmetric.

2. Transitive Closure Missteps:

   • Forgetting to add all implied pairs (e.g., missing $(1,4)$ in the earlier example).
   • Tip: Use Warshall’s algorithm for matrices to avoid omission.

3. Equivalence vs. Partial Order:

   • Equivalence relations partition sets; partial orders define hierarchies.
   • Example: "Divides" is a partial order, but "congruence modulo $n$" is an equivalence relation.

4. Hasse Diagrams:

   • Only draw edges for direct relations (omit transitive edges).
   • Example: In the "divides" relation, $2\to 8$ is omitted if $2\to 4\to 8$ exists.

---

Exam Tip

What Examiners Look For

1. Definitions:

   • Always state properties (reflexive/symmetric/transitive) before proving them.
   • Example: "To show $R$ is symmetric, we check: for all $(a,b)\in R$, $(b,a)\in R$."

2. Closure Problems:

   • Reflexive/Symmetric: List missing pairs explicitly.
   • Transitive: Use a table or graph to track implied pairs.
   • Example: For $R=\{(1,2),(2,3)\}$, write: "Since $(1,2)$ and $(2,3)$ are in $R$, by transitivity, $(1,3)$ must be added."

3. Equivalence Relations:

   • Partition the set and verify classes are disjoint and cover $A$.
   • Example: For $R=\{(1,1),(2,2),(1,2),(2,1)\}$, write: "The equivalence classes are $\{1,2\}$, which partitions $A=\{1,2\}$."

4. Hasse Diagrams:

   • Draw the diagram neatly and label maximal/minimal/greatest/least elements.
   • Example: For the "divides" relation, explicitly state: "32 is the greatest element as it is related to all others."

5. Recurrence Relations (from past papers):

   • Although this unit focuses on relations, recurrence relations (e.g., $a_n=6a_{n-1}-9a_{n-2}$) often appear in exams.
   • Solution Method:
     1. Find the characteristic equation (e.g., $r^2-6r+9=0$).
     2. Solve for roots: $r=3$ (double root).
     3. General solution: $a_n=(A+Bn)\cdot 3^n$.
     4. Use initial conditions to find $A$ and $B$.

6. Graph Theory Terms (Euler/Hamilton Paths):

   • Euler Path: Traverses every edge exactly once (exists if exactly 0 or 2 vertices have odd degree).
   • Hamilton Path: Visits every vertex exactly once (no simple degree condition; NP-hard to verify).
   • Example: In a cycle graph $C_n$ ($n\ge 3$), both Euler and Hamilton paths exist.

Mark Distribution Insights

• Definitions (20%): 1-2 marks per property (reflexive/symmetric/transitive).
• Proofs (30%): Structured steps (e.g., "Assume $(a,b)\in R$...").
• Closures (25%): Correctly identify missing pairs or use algorithms.
• Applications (15%): Relate to real-world scenarios (e.g., databases, networks).
• Diagrams (10%): Accuracy and clarity in Hasse diagrams.

Quick Revision Checklist

---