Lesson 6 — Intermediate

Relations & their Types

Relation do sets ke beech ka link hai — "kaun kis se juda hai". Is lesson mein seekhenge relation kaise banta hai (cartesian product se), kis-kis type ka hota hai (reflexive, symmetric, transitive), aur equivalence relation kya hota hai. Ye GATE ka har saal aane wala topic hai.

Relation kya hai

A × B ka cartesian product hai, jiska size |A| × |B| hota hai. Relation usi product ka koi bhi subset ho sakta hai — isliye 4 pairs wale product par 2^4 = 16 relations ban sakte hain.

Relation ki representation aur ginti

A = {1, 2}, B = {x, y}
A × B = {(1,x), (1,y), (2,x), (2,y)} |A×B| = 2 × 2 = 4
R = {(1,x), (2,y)} → R ⊆ A × B, ye ek relation hai

Representation ke tarike:
1. Ordered pairs : R = {(1,1), (1,2), (2,2)}
2. Arrow diagram : har pair ka arrow
3. Matrix (0/1)  : R[i][j] = 1 agar (i,j) ∈ R

Relations ki ginti: A mein m, B mein n elements ho toh
|A × B| = mn → 2^(mn) relations ban sakte hain

Matrix representation se types check karna sabse fast hai — diagonal mein har jagah 1 = reflexive, matrix ka symmetric hona = symmetric relation. Ye practical trick exam mein time bachati hai.

Relation ke types (reflexive, symmetric, antisymmetric, transitive)

A = {1, 2, 3} par R check karo

REFLEXIVE    : har a ke liye (a, a) ∈ R
               (1,1), (2,2), (3,3) teeno chahiye
SYMMETRIC    : (a,b) ∈ R → (b,a) ∈ R
               (1,2) hai toh (2,1) bhi chahiye
ANTISYMMETRIC: (a,b) ∈ R ∧ (b,a) ∈ R → a = b
               (1,2) aur (2,1) dono hain toh 1 = 2 —
               matlab aise do alag elements nahi ho sakte
TRANSITIVE   : (a,b) ∈ R ∧ (b,c) ∈ R → (a,c) ∈ R
               (1,2), (2,3) hain toh (1,3) bhi chahiye

Example: R = {(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)}
→ Reflexive ✓  Antisymmetric ✓  Transitive ✓ (partial order)
→ Symmetric ✗  ((1,2) hai par (2,1) nahi)

Equivalence relations, partial order, composition

EQUIVALENCE RELATION = reflexive + symmetric + transitive
  Example: "same class mein hona" (students par)
  A ke saath A same class ✓, A-B same toh B-A bhi ✓,
  A-B aur B-C same toh A-C bhi ✓
  Equivalence relation PARTITION banata hai (groups)

PARTIAL ORDER = reflexive + antisymmetric + transitive
  Example: ≤ (less than or equal) — 3 ≤ 5, par 5 ≤ 3 nahi

Composition (S ke baad R):
  (a,c) tab jab koi b ho jisme (a,b) ∈ S, (b,c) ∈ R
Inverse:
  R⁻¹ = {(b, a) : (a, b) ∈ R}

• Reflexive check: har element ka (a,a) pair dekho — ek miss hote hi fail.
• Symmetric check: har pair ka ULTA pair dhoondho.
• Transitive check: chains dhoondho — (a,b) + (b,c) ke liye (a,c) chahiye.
• GATE tip: n-element set par reflexive relations = 2^(n²−n) — n=4 par 2^12 = 4096.

Exercise

Common mistakes

• Antisymmetric ko "not symmetric" samajhna: Antisymmetric ka matlab (a,b)+(b,a) → a=b. Not symmetric ka matlab (a,b) ho par (b,a) na ho. Dono alag definitions hain.
• Reflexive ke liye galat set dekhna: R ⊆ A×A par hi (a,a) check hota hai — B ke elements ke liye nahi. Domain set ke har element ka pair chahiye.
• Transitive check mein chains chhod dena: Ek bhi missing (a,c) relation ko transitive nahi banne deta. Har (a,b)+(b,c) wali chain check karo — sabse zyada mistakes yahin hoti hain.

Tum → A : friend?  symmetric NAHI (A ne add nahi kiya)
A ↔ B   : sibling   symmetric (rishta dono taraf)
Follower: A B ko follow kare toh B A ko bhi —
          dono pairs allowed (antisymmetric bhi nahi)
Trick: har pair ka ulta pair check = symmetry pakdi jaati hai