ফাংশন — one-to-one, onto, inverse আর composition

১ · ফাংশন কী — domain, codomain আর image

বাজারঘরে প্রতিটি অর্ডারের একটি নম্বর আছে, আর প্রতিটি অর্ডার ঠিক একজন ক্রেতা দিয়েছেন। অর্ডার ১০১ রিনার, ১০২ সজীবের, ১০৩ আবার রিনার। “অর্ডার থেকে ক্রেতা” এই নিয়মটিই একটি ফাংশন। লক্ষ করুন দুটি জিনিস: কোনো অর্ডার ক্রেতাবিহীন নয়, আর কোনো অর্ডারের দুজন ক্রেতা নেই। অথচ একজন ক্রেতার একাধিক অর্ডার থাকতে পারে, আর কোনো নিবন্ধিত ক্রেতার একটিও অর্ডার না থাকতে পারে। ফাংশনের পুরো তত্ত্ব আসলে এই অসমতা নিয়েই: বাম দিকে নিয়ম কঠোর, ডান দিকে ঢিলা।

আগের দুটি পর্বে, পর্ব ১৪ “সেট — সংজ্ঞা, subset, power set আর Cartesian product” আর পর্ব ১৫ “সেটের অপারেশন — union, intersection, Venn diagram আর identity”, সেট আর তাদের অপারেশন এসেছে। ফাংশন হলো দুটি সেটের মধ্যে সংযোগ। Python-এ যে def দিয়ে ফাংশন লেখেন (Python কোর্সের পর্ব ১৩), তা এই গাণিতিক ধারণার একটি প্রয়োগ, তবে পুরোপুরি এক জিনিস নয়; পার্থক্যটা §৫-এ পরিষ্কার হবে।

সংজ্ঞাটি predicate logic-এ (পর্ব ০৪) লিখলে শর্ত দুটি স্পষ্ট হয়: ∀a ∈ A ∃b ∈ B (a-এর ছবি b), এবং সেই b অনন্য। এই “ঠিক একটি” হলো পর্ব ০৪-এর uniqueness quantifier ∃!. দুটি ফাংশন f, g সমান ধরা হয় ঠিক তখন, যখন তাদের domain এক, codomain এক, আর প্রতিটি a-তে f(a) = g(a). অর্থাৎ নিয়মের চেহারা আলাদা হলেও মান মিললে ফাংশন একই: ℤ-এর ওপর f(x) = (x + 1)² আর g(x) = x² + 2x + 1 একই ফাংশন।

Relation হিসেবে ফাংশন, আর ফাংশনের graph

“নিয়ম” শব্দটি একটু অস্পষ্ট। সেট তত্ত্বে একে নিখুঁত করা হয় ordered pair দিয়ে। Cartesian product A × B হলো সব (a, b) জোড়ার সেট; তার যেকোনো subset একটি relation (পর্ব ৫২ “Relation আর তার ধর্ম — reflexive, symmetric, transitive”-এ বিস্তারিত)। একটি ফাংশন হলো এমন relation R ⊆ A × B, যেখানে প্রতিটি a ∈ A-এর জন্য ঠিক একটি b আছে যাতে (a, b) ∈ R. এই জোড়াগুলোর সেটকেই বলে f-এর graph: {(a, f(a)) : a ∈ A}. স্কুলের xy-তলের লেখচিত্র আসলে এই সেটেরই ছবি, আর “উল্লম্ব রেখা পরীক্ষা” (প্রতিটি উল্লম্ব রেখা লেখচিত্রকে বড়জোর একবার ছোঁয়) সংজ্ঞার “ঠিক একটি”-রই চাক্ষুষ রূপ।

বাজারঘরের উদাহরণে: অর্ডার সেট O = {101, 102, 103, 104}, ক্রেতা সেট C = {রিনা, সজীব, তানিয়া, মাহিন}, আর f = {(101, রিনা), (102, সজীব), (103, রিনা), (104, তানিয়া)}. এখানে domain O, codomain C, কিন্তু image f(O) = {রিনা, সজীব, তানিয়া}: মাহিন codomain-এ আছেন, image-এ নেই। রিনার preimage দুটি: 101 আর 103. Codomain আর image-এর এই পার্থক্যই পরের অংশের onto ধারণার মূল।

যা ফাংশন নয়, তার উদাহরণ থেকেও শেখার আছে। ℝ থেকে ℝ-এ “x-এর বর্গমূল” ফাংশন নয়, দুই কারণে: ঋণাত্মক x-এর কোনো বাস্তব বর্গমূল নেই (প্রতিটি উপাদানের ছবি থাকার শর্ত ভাঙে), আর ধনাত্মক x-এর দুটি বর্গমূল ±√x (ঠিক একটি ছবির শর্ত ভাঙে)। তাই √x লিখলে আমরা বুঝি f: [0, ∞) → ℝ, যেখানে f(x) হলো অঋণাত্মক বর্গমূলটি: domain ছোট করে আর একটি মান বেছে নিয়ে ফাংশন বানানো হয়েছে।

২ · One-to-one, onto আর bijection — প্রমাণ আর খণ্ডনের ছক

প্রমাণ আর খণ্ডনের ছক

সংজ্ঞাগুলো quantifier দিয়ে লেখা, তাই প্রমাণের কাঠামোও quantifier থেকেই আসে। এটি মুখস্থ রাখার মতো চারটি ছক:

খেয়াল করুন onto-র সংজ্ঞায় quantifier-এর ক্রম ∀b ∃a: প্রতিটি b-এর জন্য a আলাদা হতে পারে। ক্রম উল্টে ∃a ∀b লিখলে দাঁড়ায় “একটি a সব b-তে যায়”, যা B-তে একাধিক উপাদান থাকলেই মিথ্যা; পর্ব ০৫-এর শিক্ষা এখানে সরাসরি খাটে। আর onto ছকের শেষ বাক্যটি (a সত্যিই A-তে আছে কি না) সবচেয়ে বেশি বাদ পড়ে: নিচের stepper-এর শেষ ধাপে দেখবেন, একই সূত্র ℝ-এ onto, ℤ-এ নয়।

1f: ℝ → ℝ, f(x) = 3x + 52one-to-one: f(a)=f(b) ⇒ a=b ?3onto: ∀y ∃x f(x) = y ?4inverse: (y − 5)/35g: ℤ → ℤ, একই সূত্র

খণ্ডনের উদাহরণ: x² কোথায় হোঁচট খায়

এবার উল্টো কাজ: একটি দাবি মিথ্যা দেখানো। f: ℤ → ℤ, f(x) = x². এখানে দুটি দাবিই ভাঙে, আর domain বা codomain বদলে তাদের কীভাবে সারানো যায়, তাও দেখব।

1f: ℤ → ℤ, f(x) = x²2x : −3 −2 −1 0 1 2 33x²:  9  4  1 0 1 4 94one-to-one? একটি জোড়া খুঁজি5onto? 2-এর preimage?6সারানো: ℕ → বর্গসংখ্যা

একটি সতর্কতা: ছোট মানের তালিকা দেখে খণ্ডন করা যায় (একটি উদাহরণই প্রমাণ), কিন্তু প্রমাণ করা যায় না। “x = −3 থেকে 3 পর্যন্ত 3x + 5-এর মানগুলো আলাদা, তাই one-to-one” ভুল যুক্তি; সসীম পরীক্ষা অসীম domain-এর জন্য কিছু প্রমাণ করে না। তবে domain নিজেই সসীম হলে সব মান দেখে নেওয়া পূর্ণ প্রমাণ (পর্ব ০৯-এর exhaustive proof). নিচের ব্লক ঠিক তাই করে: ছোট সসীম ফাংশনের পুরো টেবিল বানিয়ে image গুনে শ্রেণি ঠিক করে, আর one-to-one না হলে একটি সাক্ষী জোড়া, onto না হলে অপ্রাপ্য মানগুলো ছাপে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

def classify(name, rule, domain, codomain):
    f = {x: rule(x) for x in domain}              # the function as a table
    assert all(y in codomain for y in f.values()), "value outside codomain"
    image = set(f.values())
    one_to_one = len(image) == len(f)             # no two inputs share an output
    onto = image == set(codomain)                 # every codomain element is hit
    kind = ("bijection" if one_to_one and onto else
            "one-to-one only" if one_to_one else
            "onto only" if onto else "neither")
    print(f"{name:13} image={sorted(image)}  -> {kind}")
    if not one_to_one:                            # show a witness pair
        seen = {}
        for x, y in f.items():
            if y in seen:
                print(f"{'':13} witness: f({seen[y]}) = f({x}) = {y}")
                break
            seen[y] = x
    if not onto:
        print(f"{'':13} missed: {sorted(set(codomain) - image)}")

Z7 = range(7)
classify("(3x+5) mod 7", lambda x: (3 * x + 5) % 7, Z7, Z7)
classify("x*x mod 7", lambda x: x * x % 7, Z7, Z7)
classify("x // 2", lambda x: x // 2, range(10), range(5))
classify("2x", lambda x: 2 * x, range(5), range(10))
classify("x*x on -3..3", lambda x: x * x, range(-3, 4), range(10))

(3x+5) mod 7  image=[0, 1, 2, 3, 4, 5, 6]  -> bijection
x*x mod 7     image=[0, 1, 2, 4]  -> neither
              witness: f(3) = f(4) = 2
              missed: [3, 5, 6]
x // 2        image=[0, 1, 2, 3, 4]  -> onto only
              witness: f(0) = f(1) = 0
2x            image=[0, 2, 4, 6, 8]  -> one-to-one only
              missed: [1, 3, 5, 7, 9]
x*x on -3..3  image=[0, 1, 4, 9]  -> neither
              witness: f(-1) = f(1) = 1
              missed: [2, 3, 5, 6, 7, 8]

৩ · Inverse আর composition — উল্টো পথ আর পরপর দুই ধাপ

বাজারঘরের ডেলিভারি ব্যবস্থায় দুটি ধাপ। প্রথমে অর্ডারের ব্যাচ (1, 2, 3, 4) একজন courier-কে দেওয়া হয় (a, b, c, d), তারপর প্রতিটি courier তাঁর জেলার hub-এ যান (DHK ঢাকা, CTG চট্টগ্রাম, KHL খুলনা, RAJ রাজশাহী)। “ব্যাচ থেকে hub” জানতে দুটি ফাংশন পরপর লাগাতে হয়। আর কোনো hub-এ একটি ভুল পার্সেল পাওয়া গেলে উল্টো পথে “কোন ব্যাচের?” জানতে চাই। এই দুই কাজ composition আর inverse.

সাবধান: f⁻¹(b) লেখাটি দুই অর্থে চলে। inverse ফাংশন থাকলে এটি একটি উপাদান; কিন্তু অনেক বইয়ে যেকোনো f-এর জন্য f⁻¹(S) = {a : f(a) ∈ S} লেখা হয়, যা একটি সেট (S-এর preimage). আর 1/f(x) একেবারেই অন্য জিনিস; sin⁻¹ x মানে arcsin x, (sin x)⁻¹ নয়। প্রসঙ্গ দেখে অর্থ বুঝতে হয়।

প্রমাণ:

1. (⇐) ধরি f bijection. যেকোনো b ∈ B নিই। f onto, তাই কোনো a-তে f(a) = b; f one-to-one, তাই এমন a ঠিক একটি। এই a-কেই f⁻¹(b) সংজ্ঞায়িত করি: প্রতিটি b-এর ঠিক একটি ছবি, তাই এটি সত্যিই একটি ফাংশন। — onto দেয় অস্তিত্ব, one-to-one দেয় অনন্যতা
2. সংজ্ঞা থেকেই f(f⁻¹(b)) = b, আর f⁻¹(f(a)) = a, কারণ f(a)-এর অনন্য preimage a. — সংজ্ঞা
3. (⇒) ধরি g: B → A এমন যে g∘f = ι_A আর f∘g = ι_B. One-to-one: f(a₁) = f(a₂) হলে দুই পাশে g লাগিয়ে a₁ = g(f(a₁)) = g(f(a₂)) = a₂. — g∘f = ι_A
4. Onto: যেকোনো b ∈ B-এর জন্য a = g(b) নিলে f(a) = f(g(b)) = b. — f∘g = ι_B
5. অনন্যতা: g আর h দুটিই inverse হলে প্রতিটি b-তে g(b) = g(f(h(b))) = h(b). আর f⁻¹-এর inverse f নিজে, তাই f⁻¹-ও bijection. ∎

প্রমাণ:

1. (ক) দুই পাশের domain A, codomain D. যেকোনো a ∈ A-তে (h∘(g∘f))(a) = h((g∘f)(a)) = h(g(f(a))), আর ((h∘g)∘f)(a) = (h∘g)(f(a)) = h(g(f(a))). প্রতিটি a-তে মান সমান, তাই ফাংশন দুটি সমান। — composition-এর সংজ্ঞা, ফাংশনের সমতা
2. (খ) ধরি (g∘f)(a₁) = (g∘f)(a₂), অর্থাৎ g(f(a₁)) = g(f(a₂)). g one-to-one, তাই f(a₁) = f(a₂). f one-to-one, তাই a₁ = a₂. — দুবার one-to-one-এর সংজ্ঞা
3. (গ) যেকোনো c ∈ C নিই। g onto, তাই কোনো b ∈ B-তে g(b) = c. f onto, তাই কোনো a ∈ A-তে f(a) = b. তাহলে (g∘f)(a) = g(b) = c. — দুবার onto-র সংজ্ঞা
4. (ঘ) (খ) আর (গ) থেকে g∘f bijection. এখন (f⁻¹∘g⁻¹)∘(g∘f) = f⁻¹∘(g⁻¹∘g)∘f = f⁻¹∘ι_B∘f = f⁻¹∘f = ι_A, associativity (ক) দিয়ে বন্ধনী সরিয়ে; অন্য দিকও একইভাবে। উপপাদ্য ৩.২-এর অনন্যতায় এটিই (g∘f)⁻¹. ∎

(ঘ)-এর ক্রম উল্টে যাওয়া মনে রাখার একটি ঘরোয়া উপায়: আগে মোজা, পরে জুতা পরেন; খোলার সময় আগে জুতা, পরে মোজা। আর composition সাধারণত বিনিময়যোগ্য (commutative) নয়: ℝ-এ f(x) = x + 1, g(x) = 2x হলে (g∘f)(x) = 2x + 2, কিন্তু (f∘g)(x) = 2x + 1; x = 0-তেই 2 ≠ 1.

1f: 1→c  2→a  3→d  4→b2g: a→KHL b→DHK c→RAJ d→CTG3(g∘f)(x) = g(f(x))4(g∘f)⁻¹: সব তীর উল্টো5যাচাই: f⁻¹(g⁻¹(z))

৪ · Floor আর ceiling — পূর্ণসংখ্যায় নামানো আর ওঠানো

বাজারঘরের গুদামে ২৫০টি সাবান, একটি কার্টনে ধরে ২৪টি। কয়টি কার্টন লাগবে? 250/24 ≈ 10.42, কিন্তু 10.42টি কার্টন কেনা যায় না; লাগবে 11টি। আর কয়টি কার্টন পুরো ভরবে? 10টি। প্রথমটি ওপরের দিকে গোল করা, দ্বিতীয়টি নিচের দিকে। এই দুই কাজের নাম ceiling আর floor, আর কম্পিউটার বিজ্ঞানে এরা সর্বত্র: byte, পাতা, ব্লক, অ্যারের মাঝের index, গাছের উচ্চতা।

উদাহরণ: ⌊3.7⌋ = 3, ⌈3.7⌉ = 4, ⌊5⌋ = ⌈5⌉ = 5. ঋণাত্মকে সাবধান: ⌊−3.5⌋ = −4 (−3 নয়, কারণ −3 > −3.5), আর ⌈−3.5⌉ = −3. দুটিই onto (প্রতিটি পূর্ণসংখ্যা n নিজের ছবি) কিন্তু one-to-one নয় (⌊0.2⌋ = ⌊0.7⌋ = 0). এদের graph দেখতে সিঁড়ির মতো:

প্রমাণ:

1. (ক) m = ⌊x⌋ ধরি। সংজ্ঞা ৪.১ অনুযায়ী m ≤ x < m + 1. — floor-এর সংজ্ঞা
2. সব পাশে n যোগ করি: m + n ≤ x + n < (m + n) + 1. m + n একটি পূর্ণসংখ্যা। — অসমতায় যোগ, পূর্ণসংখ্যার closure
3. সংজ্ঞা ৪.১-এর “⇔” দিক থেকে ⌊x + n⌋ = m + n = ⌊x⌋ + n. — সংজ্ঞা
4. (খ) m = ⌊−x⌋ ধরি: m ≤ −x < m + 1. −1 দিয়ে গুণ করলে চিহ্ন উল্টায়: −m − 1 < x ≤ −m. এটি ঠিক ⌈x⌉ = −m-এর সংজ্ঞা, তাই ⌈x⌉ = −⌊−x⌋. — ceiling-এর সংজ্ঞা
5. (গ) দুই ক্ষেত্র (পর্ব ০৯-এর proof by cases). n = 2k জোড় হলে ⌊k⌋ + ⌈k⌉ = k + k = n. n = 2k + 1 বিজোড় হলে n/2 = k + 1/2, তাই ⌊n/2⌋ = k, ⌈n/2⌉ = k + 1, যোগফল 2k + 1 = n. ∎

(ক)-এর প্রমাণে n পূর্ণসংখ্যা হওয়াটাই আসল: n-এর জায়গায় বাস্তব y বসালে দাবিটি ভাঙে। x = y = 0.5 নিলে ⌊x + y⌋ = ⌊1⌋ = 1, কিন্তু ⌊x⌋ + ⌊y⌋ = 0 + 0 = 0. সঠিক কথা হলো ⌊x⌋ + ⌊y⌋ ≤ ⌊x + y⌋ ≤ ⌊x⌋ + ⌊y⌋ + 1 (অনুশীলন ৪ দেখুন)।

প্রয়োগ: বাক্স, পাতা আর byte

প্রতিটি বাক্সে k-টি করে n-টি জিনিস রাখতে সবচেয়ে কম ⌈n/k⌉টি বাক্স লাগে; কারণ b-টি বাক্সে বড়জোর bk-টি জিনিস ধরে, তাই bk ≥ n, অর্থাৎ b ≥ n/k, আর b পূর্ণসংখ্যা। এই এক নিয়ম থেকেই: ৪৭টি অর্ডার, প্রতি পাতায় ১০টি দেখালে ⌈47/10⌉ = 5 পাতা; 1001 bit রাখতে ⌈1001/8⌉ = 126 byte; একটি ধনাত্মক পূর্ণসংখ্যা n লিখতে ⌊log₂ n⌋ + 1টি binary অঙ্ক (n = 1000 হলে 10টি)। পর্ব ১৩-এর দ্রুত ঘাতের ঘোরার সংখ্যাও ঠিক এই রাশি। প্রোগ্রামে float ছাড়া ⌈n/k⌉ পেতে, k > 0 আর n ≥ 0 হলে, ⌊(n + k − 1)/k⌋ লেখা হয়; Python-এ (n + k - 1) // k বা -(-n // k), দ্বিতীয়টি আসলে (খ)-এর সূত্র।

Python-এর // সত্যিই floor: -7 // 2 হলো −4. কিন্তু int(-3.5) শূন্যের দিকে কাটে, ফল −3; C, Java-র পূর্ণসংখ্যা ভাগও শূন্যের দিকে কাটে। ধনাত্মক সংখ্যায় পার্থক্য নেই, ঋণাত্মকে আছে। নিচের ব্লক Fraction (নির্ভুল ভগ্নাংশ, float-এর গোলমাল ছাড়া) দিয়ে উপরের identity-গুলো হাজার হাজার মানে পরীক্ষা করে, আর একটি মিথ্যা দাবির counterexample খুঁজে দেয়।

from fractions import Fraction
from math import floor, ceil

xs = [Fraction(k, 12) for k in range(-60, 61)]    # exact rationals -5 .. 5
ns = range(-5, 6)

def test(name, claim, pairs):
    bad = next((p for p in pairs if not claim(*p)), None)
    verdict = "holds" if bad is None else f"FAILS at {tuple(str(v) for v in bad)}"
    print(f"{name:30} {len(pairs):6} cases: {verdict}")

test("floor(x+n) = floor(x)+n", lambda x, n: floor(x + n) == floor(x) + n,
     [(x, n) for x in xs for n in ns])
test("ceil(x) = -floor(-x)", lambda x: ceil(x) == -floor(-x), [(x,) for x in xs])
test("floor(x+y) = floor(x)+floor(y)", lambda x, y: floor(x + y) == floor(x) + floor(y),
     [(x, y) for x in xs for y in xs])
test("floor(2x) = floor(x)+floor(x+1/2)",
     lambda x: floor(2 * x) == floor(x) + floor(x + Fraction(1, 2)), [(x,) for x in xs])
test("n//2 + ceil(n/2) = n", lambda n: n // 2 + ceil(Fraction(n, 2)) == n,
     [(n,) for n in range(-100, 101)])
test("ceil(n/k) = (n+k-1)//k, k>0", lambda n, k: ceil(Fraction(n, k)) == (n + k - 1) // k,
     [(n, k) for n in range(0, 201) for k in range(1, 21)])

print("orders 47, 10 per page   -> pages:", -(-47 // 10))
print("items 250, 24 per box    -> boxes:", -(-250 // 24))
print("1001 bits                -> bytes:", -(-1001 // 8))
print("-7 // 2 =", -7 // 2, "  int(-3.5) =", int(-3.5), "  floor(-3.5) =", floor(-3.5))

floor(x+n) = floor(x)+n          1331 cases: holds
ceil(x) = -floor(-x)              121 cases: holds
floor(x+y) = floor(x)+floor(y)  14641 cases: FAILS at ('-59/12', '-49/12')
floor(2x) = floor(x)+floor(x+1/2)    121 cases: holds
n//2 + ceil(n/2) = n              201 cases: holds
ceil(n/k) = (n+k-1)//k, k>0      4020 cases: holds
orders 47, 10 per page   -> pages: 5
items 250, 24 per box    -> boxes: 11
1001 bits                -> bytes: 126
-7 // 2 = -4   int(-3.5) = -3   floor(-3.5) = -4

৫ · Partial function — যে প্রোগ্রাম সব ইনপুটে উত্তর দেয় না

সংজ্ঞা ১.১ কঠোর: domain-এর প্রতিটি উপাদানের ছবি থাকতে হবে। কিন্তু প্রোগ্রামিংয়ের ফাংশন প্রায়ই এই শর্ত ভাঙে। 1 / x x = 0-তে exception দেয়; একটি লুপ কিছু ইনপুটে কখনো থামে না। এদের জন্য গণিতে আলাদা নাম আছে।

উদাহরণ: f: ℤ → ℝ, f(n) = 1/n হলো partial, D = ℤ − {0}. g: ℝ → ℝ, g(x) = √x হলো partial, D = [0, ∞). আর পর্ব ১৩-এর একটি প্রোগ্রাম মনে করুন: while x != 0: x = x - 2, যা জোড় অঋণাত্মক x-এ থামে, বিজোড়ে চিরকাল চলে। “ইনপুট থেকে শেষ অবস্থা” ফাংশনটি ℤ থেকে ℤ-এ partial: এর সংজ্ঞার domain জোড় অঋণাত্মক সংখ্যা।

প্রতিটি প্রোগ্রাম আসলে একটি partial function গণনা করে: যে ইনপুটে থামে না, সেখানে ফল অসংজ্ঞায়িত। আর কোন ইনপুটে থামবে, অর্থাৎ D ঠিক কোনটি, তা সাধারণভাবে কোনো algorithm দিয়ে নির্ধারণ করা যায় না: এটিই halting problem, যার প্রমাণ আসবে পর্ব ৭৫ “Turing machine-এর পরিচয় — computability আর halting problem”-এ, আর তার পেছনের গণনা-তত্ত্ব আসবে পর্ব ১৮-এ। পরে একটি আলাদা Theory of Computation কোর্সেও এ বিষয়ে বিস্তারিত থাকবে।

প্রোগ্রামিংয়ে partial function-কে total বানানোর দুটি প্রচলিত কৌশল আছে, দুটিই গণিতের ভাষায় পরিষ্কার। এক, domain ছোট করা: precondition লেখা (“n ≠ 0 হলে ডাকুন”), যা পর্ব ১৩-এর Hoare logic. দুই, codomain বড় করা: B-এর সঙ্গে একটি বিশেষ মান যোগ করা, যেমন Python-এর None বা dict.get(key), যা চাবি না থাকলে None দেয়। তখন f: A → B ∪ {None} একটি total function. d[key] আর d.get(key)-এর পার্থক্য ঠিক partial আর total-এর পার্থক্য।

৬ · ফাংশন গোনা — n^m, n!/(n − m)! আর pigeonhole

বাজারঘরে ৩টি নতুন অর্ডার, আর ৪ জন courier. প্রতিটি অর্ডার একজনকে দিতে হবে। কত উপায়ে? আর যদি শর্ত থাকে একজন courier একটির বেশি অর্ডার পাবেন না? প্রথম প্রশ্নের উত্তর মোট ফাংশনের সংখ্যা, দ্বিতীয়টির one-to-one ফাংশনের সংখ্যা। গোনার নিয়মগুলো বিস্তারিত আসবে মডিউল ৬-এ (পর্ব ৩১ “গণনার মূল নিয়ম — যোগ, গুণ, বিয়োগ আর ভাগ”); এখানে শুধু গুণের নিয়ম লাগবে: পরপর স্বাধীন বাছাইয়ে মোট উপায় প্রতিটি ধাপের উপায়ের গুণফল।

প্রমাণ: A = {a₁, …, a_m} লিখি। একটি ফাংশন মানে ক্রমে f(a₁), …, f(a_m) বেছে নেওয়া।

1. (ক) প্রতিটি f(a_i)-এর জন্য n-টি পছন্দ, আর একটির বাছাই অন্যটিকে সীমিত করে না। গুণের নিয়মে n · n ⋯ n (m বার) = n^m. — গুণের নিয়ম
2. (খ) One-to-one হলে f(a₁)-এর n-টি পছন্দ, f(a₂)-এর n − 1টি (f(a₁) বাদ), …, f(a_m)-এর n − m + 1টি (আগের m − 1টি আলাদা মান বাদ)। গুণফল n!/(n − m)!. — গুণের নিয়ম
3. m > n হলে ধরি একটি one-to-one f আছে। তাহলে f(a₁), …, f(a_m) m-টি আলাদা উপাদান B-তে, অথচ B-তে মাত্র n < m-টি উপাদান: বিরোধ। — proof by contradiction
4. (গ) m = n বসালে n!/0! = n!. সসীম সেটে |A| = |B| হলে one-to-one ফাংশনের image-এ n-টি আলাদা উপাদান, অর্থাৎ পুরো B: তাই প্রতিটি one-to-one ফাংশনই onto, অর্থাৎ bijection. ∎

ধাপ ৩-এর যুক্তিটির একটি নিজস্ব নাম আছে: pigeonhole principle (কবুতরের খোপের নীতি)। ফাংশনের ভাষায়: |A| > |B| হলে A থেকে B-তে কোনো ফাংশন one-to-one নয়, অর্থাৎ অন্তত দুটি উপাদান একই ছবি পায়। পর্ব ৩২ “Pigeonhole principle — সহজ থেকে generalized”-এ এর শক্তিশালী রূপ আসবে। ধাপ ৪-এর শেষ বাক্যটিও গুরুত্বপূর্ণ: সমান আকারের সসীম সেটে one-to-one ⇔ onto. অসীম সেটে এটি মিথ্যা: f: ℕ → ℕ, f(n) = n + 1 one-to-one, কিন্তু 0 কারো ছবি নয়। এই পার্থক্যই পর্ব ১৮ “Cardinality — countable, uncountable আর Cantor-এর diagonal”-এর শুরু।

Onto ফাংশন গোনা কঠিনতর: কোনো লক্ষ্য খালি না থাকার শর্ত সরাসরি গুণের নিয়মে আসে না। উত্তর হলো

onto(m, n) = ∑_k=0ⁿ (−1)^k C(n, k) (n − k)^m

যেখানে C(n, k) হলো n-টি থেকে k-টি বাছাইয়ের উপায় (পর্ব ৩৩-এ)। সূত্রটির প্রমাণ inclusion–exclusion দিয়ে, পর্ব ৪৯ “Inclusion–exclusion আর derangement”-এ; এখানে আমরা শুধু brute force দিয়ে সংখ্যাগুলো মেলাব। নিচের ব্লক সব m-tuple বানিয়ে (প্রতিটি tuple একটি ফাংশন) image-এর আকার গোনে, আর তিনটি সূত্রের সঙ্গে তুলনা করে।

from itertools import product
from math import comb, factorial, perm
import time

def brute(m, n):                    # every function {0..m-1} -> {0..n-1} is an m-tuple
    total = inj = onto = 0
    for t in product(range(n), repeat=m):
        total += 1
        k = len(set(t))             # size of the image
        inj += (k == m)
        onto += (k == n)
    return total, inj, onto

def formulas(m, n):
    total = n ** m
    inj = perm(n, m)                # n!/(n-m)!, and 0 when m > n
    onto = sum((-1) ** k * comb(n, k) * (n - k) ** m for k in range(n + 1))
    return total, inj, onto

print(" m  n | brute (all, 1-1, onto) | formulas")
for m, n in [(2, 4), (3, 2), (3, 3), (3, 4), (4, 3), (4, 5), (5, 3)]:
    b, f = brute(m, n), formulas(m, n)
    print(f"{m:2} {n:2} | {str(b):22} | {f}  {'match' if b == f else 'MISMATCH'}")

t0 = time.perf_counter()
brute(7, 7)
print(f"brute(7, 7): 7**7 = {7**7} tuples in {time.perf_counter() - t0:.1f} s")
print("formulas(10, 10):", formulas(10, 10), " 10! =", factorial(10))

 m  n | brute (all, 1-1, onto) | formulas
 2  4 | (16, 12, 0)            | (16, 12, 0)  match
 3  2 | (8, 0, 6)              | (8, 0, 6)  match
 3  3 | (27, 6, 6)             | (27, 6, 6)  match
 3  4 | (64, 24, 0)            | (64, 24, 0)  match
 4  3 | (81, 0, 36)            | (81, 0, 36)  match
 4  5 | (625, 120, 0)          | (625, 120, 0)  match
 5  3 | (243, 0, 150)          | (243, 0, 150)  match
brute(7, 7): 7**7 = 823543 tuples in 0.2 s
formulas(10, 10): (10000000000, 3628800, 3628800)  10! = 3628800

৭ · Hash function — collision মানে one-to-one নয়

বাজারঘরের লাখ লাখ ক্রেতার id দ্রুত খুঁজতে একটি hash function h ব্যবহার হয়: প্রতিটি id-কে একটি ছোট সংখ্যায় (বাকেট নম্বর) পাঠায়, যেমন h(id) = id mod 7. গাণিতিকভাবে h: (সব সম্ভাব্য id) → {0, 1, …, 6} একটি ফাংশন, যার domain বিশাল আর codomain ছোট। দুটি আলাদা id একই বাকেটে পড়লে বলে collision, অর্থাৎ ঠিক “h one-to-one নয়”-এর সাক্ষী। উপপাদ্য ৬.১(খ)-এর m > n অংশ বলে: domain codomain-এর চেয়ে বড় হলে collision এড়ানো অসম্ভব, h যত চালাকি করেই বানানো হোক। Hash table কীভাবে collision সামলায় (chaining, probing, load factor), তা DSA কোর্সের পর্ব ৩২-এ।

তাহলে ভালো hash function-এর লক্ষ্য কী? One-to-one হওয়া নয় (অসম্ভব), বরং বাকেটগুলোতে id-গুলো প্রায় সমানভাবে ছড়ানো, অর্থাৎ প্রতিটি বাকেটের preimage প্রায় সমান আকারের। কাঠামোবদ্ধ ডেটায় দুর্বল h কী করে, নিচের ব্লকে দেখুন। সঙ্গে একটি dict-কে ফাংশন হিসেবে দেখা, আর mod গণিতে কোন সূত্র one-to-one তার পরীক্ষা।

from collections import defaultdict

# a dict is a finite function: each key has exactly one value
city = {"C101": "Dhaka", "C102": "Khulna", "C103": "Dhaka", "C104": "Sylhet"}
print("one-to-one?", len(set(city.values())) == len(city))
back = {v: k for k, v in city.items()}      # "inverting" a non-injective dict
print("naive inverse:", back)               # C101 has silently disappeared

# hashing customer ids into 7 buckets: h(id) = id mod 7
ids = [1009, 1016, 1023, 1500, 2024, 2600, 3301, 4150, 5005, 7777]
buckets = defaultdict(list)
for c in ids:
    buckets[c % 7].append(c)
print(f"{len(ids)} ids, 7 buckets, used {len(buckets)}:")
for b in sorted(buckets):
    print(f"  bucket {b}: {buckets[b]}")

def is_injective(h, dom):
    return len({h(x) for x in dom}) == len(dom)

Z11 = range(11)
print("(3x + 2) mod 11 one-to-one on Z11:", is_injective(lambda x: (3 * x + 2) % 11, Z11))
print("(4x + 2) mod 12 one-to-one on Z12:", is_injective(lambda x: (4 * x + 2) % 12, range(12)))
print("x*x mod 11 one-to-one on Z11:", is_injective(lambda x: x * x % 11, Z11))

one-to-one? False
naive inverse: {'Dhaka': 'C103', 'Khulna': 'C102', 'Sylhet': 'C104'}
10 ids, 7 buckets, used 6:
  bucket 0: [5005, 7777]
  bucket 1: [1009, 1016, 1023, 2024]
  bucket 2: [1500]
  bucket 3: [2600]
  bucket 4: [3301]
  bucket 6: [4150]
(3x + 2) mod 11 one-to-one on Z11: True
(4x + 2) mod 12 one-to-one on Z12: False
x*x mod 11 one-to-one on Z11: False

Cryptography-র hash function (যেমন SHA-256) একই গাণিতিক বাধার মধ্যে কাজ করে: যেকোনো দৈর্ঘ্যের বার্তা থেকে 256-bit মান, তাই বিপুল সংখ্যক collision আছেই। তার নিরাপত্তার দাবি হলো collision খুঁজে বের করা কার্যত অসম্ভব কঠিন, collision নেই এমন নয়। এর বাস্তব ব্যবহার সাইবার সিকিউরিটি কোর্সের পর্ব ৯-এ, আর কত id-এ collision-এর সম্ভাবনা ৫০% ছাড়ায় (birthday paradox), তা পর্ব ৪২ “Birthday paradox, hash collision আর balls-into-bins”-এ।

৮ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

এই অংশে বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় যে ধাঁচের অঙ্ক আসে, তার তিনটি পূর্ণ সমাধান, তারপর একটি ভুল প্রমাণ ধরার অনুশীলন।

অঙ্ক ১: প্রমাণ করুন, f: ℝ − {1} → ℝ − {2}, f(x) = 2x/(x − 1) একটি bijection, আর f⁻¹ বের করুন

1. ফাংশন কি না: x ≠ 1 হলে হর শূন্য নয়। আর f(x) = 2 হলে 2x = 2x − 2, অর্থাৎ 0 = −2, অসম্ভব; তাই প্রতিটি ছবি সত্যিই codomain ℝ − {2}-এ।
2. One-to-one: 2a/(a − 1) = 2b/(b − 1) ⇒ 2a(b − 1) = 2b(a − 1) ⇒ 2ab − 2a = 2ab − 2b ⇒ a = b.
3. Onto: y ≠ 2 নিই। 2x/(x − 1) = y ⇒ 2x = yx − y ⇒ x(y − 2) = y ⇒ x = y/(y − 2), যা y ≠ 2 বলে সংজ্ঞায়িত। এই x কি 1 হতে পারে? y/(y − 2) = 1 ⇒ y = y − 2, অসম্ভব; তাই x domain-এ আছে, আর f(x) = y.
4. উত্তর: f একটি bijection, f⁻¹(y) = y/(y − 2). যাচাই: f(3) = 6/2 = 3, আর f⁻¹(3) = 3/1 = 3; f(−1) = −2/−2 = 1, আর f⁻¹(1) = 1/(−1) = −1. ∎

লক্ষ করুন domain থেকে 1 আর codomain থেকে 2 বাদ দেওয়া কেন জরুরি: 1-এ f অসংজ্ঞায়িত (partial হয়ে যেত), আর 2 কারো ছবি নয় (onto হতো না)। পরীক্ষায় এই দুটি “বাদ” কোথা থেকে এল তা লিখলে পূর্ণ নম্বর।

অঙ্ক ২: A = {1, 2, 3, 4}, B = {a, b, c, d, e}

(ক) A থেকে B-তে কয়টি ফাংশন? 5⁴ = 625. (খ) কয়টি one-to-one? 5 · 4 · 3 · 2 = 120. (গ) কয়টি onto? 0, কারণ চারটি উপাদানের ছবি বড়জোর চারটি, B-তে পাঁচটি। (ঘ) B থেকে A-তে কয়টি one-to-one? 0, pigeonhole. (ঙ) A থেকে A-তে কয়টি bijection? 4! = 24. (ক)–(গ)-এর সংখ্যা §৬-এর ব্লকের (4, 5) সারির সঙ্গে মেলে।

অঙ্ক ৩: floor আর ceiling

(ক) ⌊−2.5⌋ + ⌈−2.5⌉ + ⌊2.5⌋ + ⌈2.5⌉ = −3 + (−2) + 2 + 3 = 0. (খ) বাজারঘর ১,০০০টি পার্সেল পাঠাবে, একটি ভ্যানে ধরে ৪৫টি: ⌈1000/45⌉ = 23টি ভ্যান (45 · 22 = 990 < 1000). (গ) ⌊x⌋ = 3 আর ⌈x⌉ = 4 হলে x সম্পর্কে কী বলা যায়? 3 ≤ x < 4 আর 3 < x ≤ 4, একসঙ্গে 3 < x < 4, অর্থাৎ x পূর্ণসংখ্যা নয় এবং 3 আর 4-এর মাঝে।

প্রমাণের ভুল ধরুন: “x² one-to-one”

একজন লিখলেন: “দাবি: f: ℝ → ℝ, f(x) = x² one-to-one. প্রমাণ: ধরি f(a) = f(b), অর্থাৎ a² = b². দুই পাশের বর্গমূল নিয়ে a = b. ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: √(a²) = |a|, a নয়। তাই সঠিক ধাপ হলো |a| = |b|, অর্থাৎ a = b অথবা a = −b; দ্বিতীয় সম্ভাবনাটি নিঃশব্দে বাদ পড়েছে। দাবিটিই মিথ্যা, a = −1, b = 1 counterexample. এটি একটি পরিচিত ধরন: এমন একটি ধাপ, যা সব সংখ্যায় উল্টো দিকে চলে না (a = b ⇒ a² = b² সত্য, কিন্তু উল্টোটা নয়)। প্রমাণে প্রতিটি “⇒” পড়ার সময় জিজ্ঞেস করুন, এটি কি আসলে “⇔”? domain [0, ∞) হলে |a| = a, আর তখন প্রমাণটি সঠিক হয়; তাই √ ফাংশনের domain [0, ∞)।

৯ · AI-এর যুগে — ফাংশনের প্রমাণ আর গোনা যাচাই

AI সহকারীকে “f কি bijection?” জিজ্ঞেস করলে সাধারণত আত্মবিশ্বাসী, পরিপাটি উত্তর আসে। কিন্তু এই পর্বের প্রায় প্রতিটি সূক্ষ্মতায় AI নিয়মিত ভুল করে:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• Domain আর codomain লেখা আছে, আর উত্তর সেগুলোর ওপরই নির্ভর করছে
• One-to-one প্রমাণ “f(a) = f(b) ধরি” থেকে a = b পর্যন্ত গেছে; কোনো ধাপ এক দিকের নয়
• Onto প্রমাণে যেকোনো y-এর জন্য x বের করে x ∈ domain যাচাই করা হয়েছে
• গোনার সূত্র ছোট m, n-এ brute force দিয়ে মিলিয়েছি
• Floor/ceiling-এর দাবি ঋণাত্মক আর ভগ্নাংশ মানে Fraction দিয়ে পরীক্ষা করেছি
• উল্লেখিত উপপাদ্যের শর্ত (সসীম সেট, পূর্ণসংখ্যা n, bijection) আর কোনো ইতিহাস বা বইয়ের নাম বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

সবচেয়ে সস্তা প্রথম পরীক্ষা: AI যে ফাংশনকে bijection বলছে, তাকে একটি ছোট সসীম domain-এ (বা mod n-এ) চালিয়ে image গুনুন। একবার collision পেলেই দাবি বাতিল; না পেলে তখন প্রমাণের প্রতিটি ধাপ নিজে পড়ুন।