Lesson 7 — Intermediate

Functions (Injective, Surjective, Bijective)

Function relation ka sabse useful special case hai — jahan har input ka sirf ek output ho. Is lesson mein seekhenge injective (one-one), surjective (onto), bijection, composition, inverse — aur counting: A se B tak kitne functions ban sakte hain.

Function kya hai

Range = codomain ka wo hissa jo actually images hai. Relation aur function ka fark: relation mein kisi element ka image ho bhi sakta hai aur na bhi, par function mein domain ke har element ka ek image zaroori hai.

Injective, Surjective, Bijective

INJECTIVE (one-one): do alag inputs ka alag output
  f(a) = f(b) → a = b
  Condition: |A| ≤ |B| (warna pigeonhole se clash)

SURJECTIVE (onto): codomain ka HAR element image ho
  range = codomain
  Condition: |A| ≥ |B| (koi element bacha na)

BIJECTIVE: injective + surjective dono
  Perfect 1-to-1 pairing → |A| = |B|
  Inverse function tabhi banta hai

Example: A = {1,2,3}, B = {p,q,r}
f = {(1,p), (2,q), (3,r)} → bijection ✓
g = {(1,p), (2,p), (3,q)} → na injective (1,2 clash),
                             na surjective (r bacha)

Composition aur inverse

Functions ko jodte hain (composition) aur ulta bhi kar sakte hain (inverse) — par inverse sirf bijection par banta hai:

Composition: (g ∘ f)(x) = g(f(x))
  f: A → B, g: B → C  ⇒  g ∘ f: A → C
  Order MATTERS : g ∘ f aur f ∘ g alag hote hain
                  (dono defined bhi nahi hote hamesha)

Inverse: f⁻¹: B → A  jab f BIJECTIVE hai
  f = {(1,p), (2,q), (3,r)}
  → f⁻¹ = {(p,1), (q,2), (r,3)}
  Surjective hona zaroori: har b ka preimage mile
  Injective hona zaroori: preimage unique ho

Properties:
  (h ∘ g) ∘ f = h ∘ (g ∘ f)    [associative]
  f ∘ f⁻¹ = identity (B par)
  f⁻¹ ∘ f = identity (A par)

Yaad rakho: composition associative hota hai, par commutative NAHI — g ∘ f aur f ∘ g aam taur par alag hain (aur defined bhi dono nahi hote).

Function counting — worked examples

Worked examples (|A| = m, |B| = n):

1) m = 3, n = 4 : total functions = 4³ = 64
   (har element ko 4 choices)

2) m = 3, n = 4 : injective = 4 × 3 × 2 = 24
   (pehle ko 4, doosre ko bacha 3, teesre ko 2)

3) m = 3, n = 3 : bijections = 3! = 6

4) m = 4, n = 3 : surjective = 3⁴ − C(3,1)2⁴ + C(3,2)1⁴
   = 81 − 48 + 3 = 36  (inclusion-exclusion)

5) Constant functions (sab ek hi image) = n

Hamesha order mein socho: pehle function hai ya nahi (har input ek hi output), phir type (injective/onto), phir counting. Ye 3-step soch GATE ke numericals mein kaam aati hai.

Exercise

Common mistakes

• Kisi element ki do images: Agar ek input ke do output hain — wo function hi nahi hai. Pehla check yahi hona chahiye, baaki sab baad mein.
• Injective aur surjective ulta: Injective = alag inputs ka alag output (one-one). Surjective = codomain ka har element covered (onto). Ek line mein difference yaad rakho.
• Har function ka inverse: Inverse sirf BIJECTIVE function ka banta hai. Surjective alone ka inverse nahi (do inputs ek output pe), injective alone ka bhi nahi (kuch codomain elements khaali).

Rule: har player ko EK hi number (function ka niyam)
Do alag players ka number alag = injective
Pool ka har number kisi na kisi player pe = surjective
Dono saath = bijection, inverse bhi banega (reverse map)