Relations & Functions: Types, Representations & Applications

TAKEAWAYS:

• Relations are defined by ordered pairs and classified by properties (reflexive/symmetric/transitive); equivalence relations partition sets into disjoint subsets.
• Functions map inputs to outputs uniquely and are categorized by injectivity (one-to-one), surjectivity (onto), and bijectivity (both).
• Matrix representation of relations uses binary entries (1/0) to encode membership in $R\subseteq A\times B$.
• Graph representation visualizes relations as directed edges between nodes, critical for pathfinding (e.g., NTC’s network routing).
• Recursive functions (e.g., Fibonacci) define outputs based on prior values; mathematical induction proves their correctness.
• Real-world ties: Khalti’s transaction validation uses injective functions; Pathao’s ride-matching relies on bipartite graphs (relations between drivers and passengers).

1. Relations: Definitions and Properties

A relation $R$ from set $A$ to set $B$ is a subset of $A\times B$. If $(a,b)\in R$, we write $aRb$.

Key Properties of Relations

A relation $R$ on a set $A$ can have these properties:

Equivalence Relations and Partitions

An equivalence relation partitions $A$ into equivalence classes $[a]=\{x\in A\mid xRa\}$.

Example (Nepali Voting Districts): Let $A=\{\text{Kathmandu},\text{Lalitpur},\text{Bhaktapur}\}$ and $R=\{\text{cities in the same valley}\}$. Then:

• $[Kathmandu]=\{Kathmandu,Lalitpur,Bhaktapur\}$ (all in Kathmandu Valley).
• This is an equivalence relation because it is reflexive, symmetric, and transitive.

graph TD
    A["Kathmandu"] --> B["Lalitpur"]
    B --> A
    A --> C["Bhaktapur"]
    C --> A

2. Functions: Types and Representations

A function $f:A\to B$ assigns exactly one output $b\in B$ to each input $a\in A$.

Types of Functions

Visualizing Injectivity/Surjectivity:

Matrix Representation of Relations

For $A=\{a_1,a_2,a_3\}$ and $B=\{b_1,b_2\}$, the relation matrix $M_R$ is: $$M_R[i][j]=\{\begin{array}{ll}1& \text{if }(a_i,b_j)\in R,\\ 0& \text{otherwise}.\end{array}$$

Example (Past Exam Question): Given $A=\{1,2,3\}$, $B=\{1,2\}$, and $R=\{(a,b)\mid a>b\}$, the matrix is: $$\left[\begin{array}{cc}0& 1\\ 0& 1\\ 0& 1\end{array}\right]$$ Explanation:

• $1>1$? No → $M[1][1]=0$.
• $1>2$? No → $M[1][2]=0$ (but wait: the relation is $a>b$, so for $a=1$ and $b=2$, $1>2$ is false → $M[1][2]=0$. Correction: The relation is $a>b$, so:
  • $1>1$? No → $M[1][1]=0$
  • $1>2$? No → $M[1][2]=0$
  • $2>1$? Yes → $M[2][1]=1$
  • $2>2$? No → $M[2][2]=0$
  • $3>1$? Yes → $M[3][1]=1$
  • $3>2$? Yes → $M[3][2]=1$

Corrected Matrix: $$\left[\begin{array}{cc}0& 0\\ 1& 0\\ 1& 1\end{array}\right]$$

3. Graph Representation of Relations

Relations can be visualized as directed graphs where nodes are elements and edges represent $(a,b)\in R$.

Example (Friendship Relation): Let $A=\{\text{Ashish},\text{Bikram},\text{Chetan}\}$ and $R=\{\text{is friends with}\}$. If Ashish is friends with Bikram and Chetan, but Bikram and Chetan are not friends:

graph TD
    A["Ashish"] --> B["Bikram"]
    A --> C["Chetan"]

4. Recursive Functions and Induction

A recursive function defines $f(n)$ in terms of $f(k)$ for $k<n$.

Example (Fibonacci): $$f(0)=0,f(1)=1,f(n)=f(n-1)+f(n-2)\text{ for }n\ge 2.$$ Trace for $f(4)$: $$\begin{array}{rl}f(4)& =f(3)+f(2)\\ & =(f(2)+f(1))+(f(1)+f(0))\\ & =(f(1)+f(0))+f(1)+f(0)\\ & =(1+0)+1+0=3.\end{array}$$

Proof by Induction (Example): Claim: $f(n)=\frac{{\varphi }^n-{\psi }^n}{\sqrt{5}}$, where $\varphi =\frac{1+\sqrt{5}}{2}$ and $\psi =\frac{1-\sqrt{5}}{2}$. Base Cases:

• $n=0$: $\frac{1-1}{\sqrt{5}}=0=f(0)$.
• $n=1$: $\frac{\varphi -\psi }{\sqrt{5}}=1=f(1)$.

Inductive Step: Assume true for $n=k$ and $n=k-1$. Show for $n=k+1$: $$f(k+1)=f(k)+f(k-1)=\frac{{\varphi }^k-{\psi }^k}{\sqrt{5}}+\frac{{\varphi }^{k-1}-{\psi }^{k-1}}{\sqrt{5}}=\frac{{\varphi }^{k+1}-{\psi }^{k+1}}{\sqrt{5}}.$$

5. Real-World Applications

1. Khalti’s Transaction Validation (Injective Functions)

Khalti uses injective functions to assign unique transaction IDs. If two transactions had the same ID, the system would fail to distinguish them. For example:

• Input: user_id + amount + timestamp.
• Output: A 64-bit hash (e.g., SHA-256).
• Why injective? No two distinct inputs produce the same hash (collision-resistant).

2. Pathao’s Ride-Matching (Bipartite Graphs)

Pathao’s algorithm matches drivers to passengers using a bipartite graph:

• Left nodes: Drivers (with location, vehicle type).
• Right nodes: Passengers (with pickup/drop locations).
• Edges: Possible matches (e.g., driver’s location ≤ 500m from passenger).

graph LR
    D1["Driver 1"] -- "Distance ≤ 500m" --> P1["Passenger 1"]
    D1 -- "Distance ≤ 500m" --> P2["Passenger 2"]
    D2["Driver 2"] -- "Distance ≤ 500m" --> P2

Pathao’s algorithm finds a maximum matching in this graph to minimize wait times.

3. NTC’s Network Routing (Transitive Closure)

The Nepal Telecommunications Company (NTC) uses transitive closure to determine if two cities are connected via fiber optics. For example:

• Let $A=\{\text{Kathmandu},\text{Pokhara},\text{Biratnagar}\}$ and $R=\{\text{has direct fiber link}\}$.
• If $R=\{(\text{Kathmandu},\text{Pokhara}),(\text{Pokhara},\text{Biratnagar})\}$, then the transitive closure adds $(\text{Kathmandu},\text{Biratnagar})$.

Matrix for Transitive Closure: Original $M_R$: $$\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}\right]$$ Transitive closure $M_R^{+}$: $$\left[\begin{array}{ccc}0& 1& 1\\ 0& 0& 1\\ 0& 0& 0\end{array}\right]$$

6. Exam Tips

1. For relations:

   • Always check all three properties (reflexive/symmetric/transitive) for equivalence relations.
   • Matrix questions: Label rows/columns clearly (e.g., $a_1,a_2,\dots$) and fill 1/0 correctly.
   • Graph questions: Draw directed edges and label them with the relation (e.g., "is parent of").

2. For functions:

   • Injective? Use the "horizontal line test" (no two inputs share an output).
   • Surjective? Ensure every element in $B$ is covered.
   • Bijective? Both injective and surjective.
   • Identity function: Always maps $x\to x$.

3. Recursive functions:

   • Trace step-by-step for small values (e.g., $f(0)$ to $f(3)$).
   • Induction proofs: Show base case(s) and assume the inductive hypothesis for the step.

4. Common pitfalls:

   • Off-by-one errors in recursive definitions (e.g., $f(n)=f(n-1)+1$ vs. $f(n)=f(n+1)-1$).
   • Confusing symmetric/transitive: Symmetric requires $(a,b)⟹(b,a)$; transitive requires chaining $(a,b)$ and $(b,c)$ to $(a,c)$.
   • Matrix dimensions: If $A$ has $m$ elements and $B$ has $n$ elements, the matrix is $m\times n$.