Relation আর তার ধর্ম — reflexive, symmetric, transitive

১ · Relation কী — জোড়ার একটি সেট

দৈনন্দিন ভাষায় “সম্পর্ক” অনেক রকম: রহিম করিমের ভাই, ঢাকা খুলনার চেয়ে বড়, ১২ সংখ্যাটি ৩ দিয়ে বিভাজ্য, একটি অর্ডার একজন ক্রেতার। প্রতিটি ক্ষেত্রে দুটি বস্তু, আর তাদের মধ্যে কিছু একটা সত্য বা মিথ্যা। গণিত এই সব সম্পর্কের একটিই সাধারণ রূপ দেয়: কোন কোন জোড়া সম্পর্কে যুক্ত, তার তালিকা।

পর্ব ১৪ “সেট — সংজ্ঞা, subset, power set আর Cartesian product”-এ সংজ্ঞাটি সংক্ষেপে এসেছে। এখানে তাকে পূর্ণ রূপে লিখি।

এখানে A × B = {(a, b) : a ∈ A, b ∈ B}, সব ordered pair-এর সেট। “Binary” শব্দটির অর্থ জোড়ায় জোড়ায় দুটি করে বস্তু; তিন বা ততোধিক বস্তুর সম্পর্ক (n-ary relation) পর্ব ৫৩ “n-ary relation আর relational database-এর গণিত”-এর বিষয়। এই পর্বে “relation” মানেই binary relation.

বাজারঘরের উদাহরণ। ক্রেতা C = {রিনা, সজীব, তানিয়া} আর পণ্য P = {চাল, ডাল, চা, তেল}. “কিনেছেন” relation K = {(রিনা, চাল), (রিনা, ডাল), (সজীব, চা), (তানিয়া, চাল), (তানিয়া, তেল)}. C × P-এ 3 · 4 = 12টি জোড়া, তার মধ্যে ৫টি K-তে। প্রতিটি সম্ভাব্য খাতা C × P-এর একটি subset, তাই এমন খাতা মোট 2¹² = 4096টি সম্ভব।

একটি সেটের ওপর relation. অনেক গুরুত্বপূর্ণ relation একই সেটের দুটি উপাদানের মধ্যে: পূর্ণসংখ্যায় ≤, <, “a ∣ b” (a, b-কে নিঃশেষে ভাগ করে), “a ≡ b (mod 5)” (পর্ব ২২), বাজারঘরের পণ্যে “x-এর দাম y-এর চেয়ে কম”, অর্ডার-প্রক্রিয়ার কাজে “x শেষ না হলে y শুরু হয় না”। এই পর্বের ধর্মগুলো (reflexive, symmetric, transitive …) শুধু এই ধরনের relation-এর জন্যই অর্থবহ, কারণ সেখানে (a, b) আর (b, a) দুটিই একই সেটের জোড়া।

উদাহরণ: A = {1, 2, 3, 4}-এর ওপর “a ∣ b” relation হলো {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}, আটটি জোড়া। আর A-এর ওপর সম্ভাব্য relation |A × A| = 16টি জোড়ার যেকোনো subset, তাই 2¹⁶ = 65536টি। সাধারণভাবে n উপাদানের সেটে 2^n²টি relation; §৫-এ এদের মধ্যে কয়টির কোন ধর্ম আছে, তা গুনব।

ফাংশন একটি বিশেষ relation

পর্ব ১৬ “ফাংশন — one-to-one, onto, inverse আর composition”-এ f: A → B-কে নিয়ম হিসেবে দেখেছেন। জোড়ার ভাষায় একটি function হলো এমন একটি relation f ⊆ A × B, যাতে প্রতিটি a ∈ A-এর জন্য ঠিক একটি b ∈ B থাকে, যেখানে (a, b) ∈ f. তখনই আমরা লিখি f(a) = b. এই সেটটিকেই পর্ব ১৬-এ “ফাংশনের graph” বলা হয়েছিল। তাই প্রতিটি ফাংশন একটি relation, কিন্তু উল্টোটি সত্য নয়: “কিনেছেন” relation K-তে রিনার দুটি পণ্য আছে, তাই K কোনো ফাংশন নয়। দুটি শর্তের যেকোনোটি ভাঙলে ফাংশন থাকে না: কোনো a-এর কোনো জোড়া না থাকলে (তখন তা partial function), বা একাধিক জোড়া থাকলে।

২ · তিন রূপে relation — তালিকা, digraph আর 0-1 matrix

একটি সসীম relation তিনভাবে লেখা যায়, আর প্রতিটি রূপ ভিন্ন প্রশ্নের জন্য সুবিধাজনক। চলুন পুরো পর্বে একটি উদাহরণ ধরে রাখি: A = {1, 2, 3, 4}-এর ওপর

R = {(1,1), (2,2), (3,3), (1,2), (2,3), (1,3), (3,2)}

ধরুন 1, 2, 3, 4 হলো বাজারঘরের চারটি ডেলিভারি জোন, আর a R b মানে “জোন a-এর রাইডার জোন b-তে ডেলিভারি দিতে পারেন”। জোন ৪ নতুন, এখনো কোনো রাইডার নেই।

1. জোড়ার তালিকা (set of pairs): ওপরের মতো। কোডে সবচেয়ে সহজ: Python-এ set of tuple; “(a, b) আছে কি?” প্রশ্নের উত্তর এক ধাপে।
2. Directed graph (digraph) বা তীরচিত্র: প্রতিটি উপাদান একটি বিন্দু (vertex), আর প্রতিটি (a, b)-এর জন্য a থেকে b-তে একটি তীর। (a, a) মানে বিন্দু থেকে নিজের কাছে ফেরা একটি ছোট ফাঁস, যার নাম self-loop. A থেকে B-তে relation হলে দুই সারিতে দুটি সেট এঁকে বাঁ থেকে ডানে তীর দেওয়া হয় (arrow diagram), যেমনটি পর্ব ১৬-এ ফাংশনের জন্য দেখেছেন।
3. 0-1 matrix: A = {a₁, …, a_m}, B = {b₁, …, b_n} হলে M_R একটি m × n matrix, যার ঘর m_ij = 1 যদি (a_i, b_j) ∈ R, নইলে 0. পর্ব ১৯ “Discrete math-এ matrix — 0-1 matrix আর Boolean product”-এ এই matrix-এর অপারেশন শিখেছেন।

তিন রূপের মধ্যে অনুবাদ যান্ত্রিক: matrix-এর প্রতিটি 1 একটি জোড়া আর একটি তীর; matrix-এর কর্ণ (main diagonal, m₁₁, m₂₂, …) মানে self-loop-গুলো। কোন রূপ কখন ভালো? ছোট হাতের হিসাবে আর ধর্ম “দেখে” বুঝতে digraph; কম্পিউটারে দ্রুত গুণ আর তুলনায় matrix; আর বিরল (sparse) relation-এ, যেখানে সম্ভাব্য জোড়ার খুব কম অংশ আছে, জোড়ার তালিকা বা adjacency list জায়গা বাঁচায়। গ্রাফের representation-এর ব্যবহারিক দিক DSA কোর্সের পর্ব ৩৯ “গ্রাফ — উপস্থাপন আর পরিভাষা”-এ, আর গণিতের দিক এই কোর্সের পর্ব ৫৮ “গ্রাফের representation আর isomorphism”-এ।

৩ · ছয়টি ধর্ম — সংজ্ঞা, matrix আর digraph-এ চেহারা

এখন থেকে R হলো একটি সেট A-এর ওপর relation. প্রতিটি ধর্ম একটি quantifier-যুক্ত বাক্য (পর্ব ৪-এর predicate logic), আর তাদের ঠিকভাবে পড়তে পারাই এই পর্বের অর্ধেক কাজ।

সংজ্ঞাগুলোর quantifier-এ মনোযোগ দিন। Reflexive একটি “সব a-এর জন্য (a, a) আছে” দাবি, তাই একটিমাত্র অনুপস্থিত (a, a) দাবিটি ভাঙে। Symmetric, antisymmetric, asymmetric আর transitive হলো “যদি … তবে …” আকারের দাবি; শর্তটি কখনো সত্য না হলে দাবিটি শূন্যভাবে (vacuously) সত্য। তাই খালি relation ∅ symmetric, antisymmetric, asymmetric আর transitive, কিন্তু A ≠ ∅ হলে reflexive নয়।

Transitive-এর matrix-শর্তে M ⊙ M হলো Boolean product (পর্ব ১৯): ঘর (i, j)-এ 1 ঠিক তখন, যখন কোনো k-এর জন্য m_ik = m_kj = 1, অর্থাৎ i থেকে j-তে দুই ধাপের পথ আছে। “M ⊙ M ≤ M” মানে প্রতিটি দুই-ধাপ পথের জন্য সরাসরি জোড়াটিও আছে। এর প্রমাণ §৭-এর উপপাদ্য ৭.৪ থেকে আসবে।

এবার উদাহরণ R-কে ধর্ম ধরে পরীক্ষা করি, প্রতিটি ধর্মে কোন জোড়া দোষী তা খুঁজে।

1R-এ ৭টি জোড়া2reflexive: সব (a,a)?3irreflexive: কোনো (a,a) নয়?4symmetric: (a,b) → (b,a)?5antisymmetric: a≠b দুই দিকে?6asymmetric: কোনো উল্টো নেই?7transitive: ১৫টি দুই-ধাপ পথ8ফলাফল

৪ · ধর্মের মিশ্রণ — কোনটি কোনটিকে বোঝায়, কোনটি বোঝায় না

ছয়টি ধর্ম স্বাধীন নয়। কিছু সম্পর্ক প্রমাণ করা যায়, আর কিছু “স্বাভাবিক মনে হওয়া” সম্পর্ক আসলে মিথ্যা। দুটি উপপাদ্য দিয়ে শুরু করি।

1. (⇒) R asymmetric ধরুন। কোনো a-এর জন্য (a, a) ∈ R হলে asymmetry-তে b = a বসিয়ে (a, a) ∉ R, বিরোধ। তাই R irreflexive. — সংজ্ঞায় b = a বসানো
2. (⇒) Antisymmetric-এর শর্ত “(a, b) ∈ R ∧ (b, a) ∈ R” asymmetric R-এ কখনো সত্য হয় না, তাই implication-টি শূন্যভাবে সত্য। — vacuous truth, পর্ব ২
3. (⇐) R irreflexive আর antisymmetric ধরুন, আর ধরুন কোনো (a, b) ∈ R আর (b, a) ∈ R. Antisymmetry থেকে a = b, তাহলে (a, a) ∈ R, যা irreflexivity-র বিরোধী। — proof by contradiction, পর্ব ৮
4. তাই এমন জোড়া নেই: (a, b) ∈ R হলে (b, a) ∉ R, অর্থাৎ R asymmetric. ∎

1. (⇒) (a, b) ∈ R নিন। Symmetry থেকে (b, a) ∈ R; তখন antisymmetry থেকে a = b. তাই প্রতিটি জোড়া (a, a) আকারের, অর্থাৎ R ⊆ Δ_A. — দুই সংজ্ঞা পরপর
2. (⇐) R ⊆ Δ_A হলে প্রতিটি জোড়া (a, a), যার উল্টো সে নিজেই, তাই symmetric; আর (a, b), (b, a) দুটিই থাকলে দুটিই diagonal-এ, তাই a = b. ∎ — সংজ্ঞা যাচাই

তাই “symmetric” আর “antisymmetric” পরস্পরের উল্টো নয়: Δ_A আর ∅ দুটি ধর্মই রাখে, আর §৩-এর R কোনোটিই রাখে না। n উপাদানের সেটে দুটি ধর্মই আছে এমন relation ঠিক 2ⁿটি, Δ_A-এর subset-গুলো।

নিচের সারণিতে পরিচিত কিছু relation, প্রতিটি ধর্মসহ। “✓” = আছে, “✗” = নেই। সেটটি বলা না থাকলে ধনাত্মক পূর্ণসংখ্যা ℤ⁺.

কয়েকটি সারি নিয়ে ভাবুন। ℤ-এ ∣ antisymmetric নয়, কারণ 2 ∣ −2 আর −2 ∣ 2, অথচ 2 ≠ −2; তাই সারণিতে ℤ⁺ নেওয়া হয়েছে। |a − b| ≤ 1 (“দাম প্রায় সমান”) transitive নয়: 1 আর 2 কাছাকাছি, 2 আর 3 কাছাকাছি, কিন্তু 1 আর 3 নয়। বাস্তবে “প্রায় সমান” ধরনের সম্পর্ক প্রায়ই এই ফাঁদে পড়ে: দুই টাকা করে সরতে সরতে দশ টাকার পার্থক্য। ≡ (mod 3) reflexive, symmetric আর transitive তিনটিই; এই তিনটি একসঙ্গে থাকলে relation-টিকে বলে equivalence relation, যা পর্ব ৫৫ “Equivalence relation আর partition”-এর বিষয়। আর reflexive, antisymmetric আর transitive একসঙ্গে (≤, ∣, ⊆) হলো partial order, পর্ব ৫৬ “Partial order, Hasse diagram, topological sort আর lattice”-এর বিষয়। তাই এই পর্বের ছয়টি ধর্ম পুরো মডিউলের ইট।

নিচের ব্লক §৩-এর পরীক্ষাটি কোডে করে, আর প্রতিটি “না”-এর পাশে প্রথম দুটি দোষী জোড়া (বা দুই-ধাপ পথ) ছাপে। সঙ্গে বাজারঘরের চারটি পণ্যের দাম ধরে “সস্তা” আর “একই দাম” relation-ও পরীক্ষা করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে; পরের ব্লকগুলো দ্রুত চলে।

def check(R, A):
    """Return {property: None if it holds, else the pairs that break it}."""
    bad = {}
    bad["reflexive"] = [(a, a) for a in A if (a, a) not in R] or None
    bad["irreflexive"] = [(a, a) for a in A if (a, a) in R] or None
    bad["symmetric"] = [(a, b) for (a, b) in sorted(R)
                        if (b, a) not in R] or None
    bad["antisymmetric"] = [(a, b) for (a, b) in sorted(R)
                            if a < b and (b, a) in R] or None
    bad["asymmetric"] = [(a, b) for (a, b) in sorted(R)
                         if (b, a) in R and a <= b] or None
    bad["transitive"] = [((a, b), (b, d)) for (a, b) in sorted(R)
                         for (c, d) in sorted(R)
                         if b == c and (a, d) not in R] or None
    return bad

def report(name, R, A):
    print(name)
    for prop, why in check(R, A).items():
        print(f"  {prop:13}", "yes" if why is None else f"no  {why[:2]}")

A = [1, 2, 3, 4]
R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3), (1, 3), (3, 2)}
report("R on {1,2,3,4}", R, A)
# bazarghor: "costs less than" on four product prices (taka)
price = {1: 120, 2: 450, 3: 450, 4: 900}
L = {(a, b) for a in A for b in A if price[a] < price[b]}
report("cheaper-than", L, A)
E = {(a, b) for a in A for b in A if price[a] == price[b]}
report("same-price", E, A)

R on {1,2,3,4}
  reflexive     no  [(4, 4)]
  irreflexive   no  [(1, 1), (2, 2)]
  symmetric     no  [(1, 2), (1, 3)]
  antisymmetric no  [(2, 3)]
  asymmetric    no  [(1, 1), (2, 2)]
  transitive    yes
cheaper-than
  reflexive     no  [(1, 1), (2, 2)]
  irreflexive   yes
  symmetric     no  [(1, 2), (1, 3)]
  antisymmetric yes
  asymmetric    yes
  transitive    yes
same-price
  reflexive     yes
  irreflexive   no  [(1, 1), (2, 2)]
  symmetric     yes
  antisymmetric no  [(2, 3)]
  asymmetric    no  [(1, 1), (2, 2)]
  transitive    yes

৫ · Relation গোনা — সূত্র, প্রমাণ আর যেখানে সূত্র নেই

|A| = n হলে A × A-এর n² ঘরকে দুই দলে ভাগ করা যায়: n-টি কর্ণের ঘর (a, a), আর বাকি n² − n ঘর, যারা আবার C(n, 2) = n(n − 1)/2টি অক্রমিক জোড়া {a, b}-এ সাজানো, প্রতিটিতে দুটি ঘর: (a, b) আর (b, a) ঘর দুটি। প্রতিটি ধর্ম এই ঘরগুলোর ওপর একটি শর্ত, আর পর্ব ৩১-এর গুণের নিয়ম বাকি কাজ করে।

1. মোট: প্রতিটি relation n² ঘরের প্রতিটিতে 0 বা 1 বাছাই, তাই 2^n². — গুণের নিয়ম
2. Reflexive: n-টি কর্ণের ঘর বাধ্যতামূলক 1, বাকি n² − n = n(n − 1) ঘর স্বাধীন, তাই 2ⁿ⁽ⁿ⁻¹⁾. Irreflexive-এ কর্ণ বাধ্যতামূলক 0, বাকি একই। — গুণের নিয়ম
3. Symmetric: কর্ণের n ঘর স্বাধীন, তাই 2ⁿ উপায়। প্রতিটি অক্রমিক জোড়া {a, b}-তে (a, b) আর (b, a) একসঙ্গে থাকবে বা একসঙ্গে থাকবে না: ২টি পছন্দ, এমন জোড়া n(n − 1)/2টি। মোট 2ⁿ · 2^n(n−1)/2 = 2^n(n+1)/2. — সূচকের যোগ
4. Antisymmetric: কর্ণ স্বাধীন, তাই 2ⁿ উপায়। প্রতিটি {a, b}-তে “দুটিই” নিষিদ্ধ, তাই তিনটি পছন্দ: কোনোটি নয়, শুধু (a, b), শুধু (b, a). মোট 2ⁿ · 3^n(n−1)/2. — গুণের নিয়ম
5. Asymmetric: উপপাদ্য ৪.১ অনুযায়ী = irreflexive + antisymmetric: কর্ণ বাধ্যতামূলক 0, বাকি একই তিন পছন্দ, তাই 3^n(n−1)/2. — উপপাদ্য ৪.১
6. Reflexive আর symmetric: কর্ণ বাধ্যতামূলক 1, প্রতিটি {a, b}-তে ২টি পছন্দ: 2^n(n−1)/2. ∎ — ধাপ ২ আর ৩ মিলিয়ে

1৯টি ঘর = ৩ কর্ণ + ৩ জোড়া2কর্ণ (1,1),(2,2),(3,3): 2³3{1,2}: ৩ পছন্দ4{1,3}: ৩ পছন্দ5{2,3}: ৩ পছন্দ6মিলিয়ে দেখা

Transitive-এর সূত্র কেন নেই

ওপরের সব ধর্ম স্থানীয়: প্রতিটি শর্ত একটি ঘর বা একটি জোড়া {a, b}-এর কথা বলে, তাই ঘরগুলোর পছন্দ স্বাধীন আর গুণের নিয়ম খাটে। Transitivity তিনটি উপাদান a, b, c একসঙ্গে জড়ায়, আর একটি ঘরের পছন্দ অন্য অনেক ঘরকে বাধ্য করে: (1, 2) আর (2, 3) রাখলে (1, 3) রাখতেই হবে। পছন্দগুলো আর স্বাধীন নয়, আর n উপাদানের সেটে transitive relation-এর সংখ্যার কোনো সরল বদ্ধ সূত্র (closed form) জানা নেই। ছোট n-এ শুধু গুনে বের করা যায়: n = 1, 2, 3, 4-এ 2, 13, 171, 3994. Scratch-এ সারি ধরে backtracking দিয়ে n = 5-এ 154303 পাওয়া গেছে, যা OEIS-এর A006905 ক্রমের মানের সঙ্গে মেলে।

নিচের ব্লক n = 1, 2, 3-এ সব 2^n²টি relation তালিকা করে প্রতিটি ধর্ম গোনে আর সূত্রের সঙ্গে মেলায়। n = 4-এ ৬৫৫৩৬টি relation-এর transitive-গুলো গোনে bitmask দিয়ে: প্রতিটি সারি একটি ৪-bit সংখ্যা, আর “(i, j) ∈ R হলে সারি j-এর সব 1 সারি i-তেও আছে” শর্তটিই transitivity: (i, j) আর (j, k) থাকলে (i, k)-ও থাকতে হবে। n = 5-এ 2²⁵, অর্থাৎ তিন কোটিরও বেশি relation; এই সরল brute force সেখানে ব্রাউজারে অনেক সময় নেবে, তাই এখানে থামি।

from itertools import product

def count(n):                       # relation = n x n 0-1 matrix M
    c = dict(refl=0, sym=0, anti=0, asym=0, trans=0)
    cells = [(i, j) for i in range(n) for j in range(n)]
    for bits in product((0, 1), repeat=n * n):
        M = dict(zip(cells, bits))
        c["refl"] += all(M[i, i] for i in range(n))
        c["sym"] += all(M[i, j] == M[j, i] for i, j in cells)
        c["anti"] += all(not (M[i, j] and M[j, i]) for i, j in cells if i != j)
        c["asym"] += all(not (M[i, j] and M[j, i]) for i, j in cells)
        c["trans"] += all(M[i, k] for i, j in cells for k in range(n)
                          if M[i, j] and M[j, k])
    return c

def formula(n):
    return dict(refl=2 ** (n * (n - 1)), sym=2 ** (n * (n + 1) // 2),
                anti=2 ** n * 3 ** (n * (n - 1) // 2),
                asym=3 ** (n * (n - 1) // 2), trans="?")

for n in (1, 2, 3):
    print(f"n={n}  all={2 ** (n * n)}")
    print("  brute  ", count(n))
    print("  formula", formula(n))

def transitive_rows(rows):          # rows[i] = bitmask of j with (i, j) in R
    return all(rows[j] & ~rows[i] == 0
               for i in range(4) for j in range(4) if rows[i] >> j & 1)
t4 = sum(transitive_rows([(m >> 4 * i) & 15 for i in range(4)])
         for m in range(1 << 16))
print("transitive relations on 4 elements:", t4, "of", 1 << 16)

n=1  all=2
  brute   {'refl': 1, 'sym': 2, 'anti': 2, 'asym': 1, 'trans': 2}
  formula {'refl': 1, 'sym': 2, 'anti': 2, 'asym': 1, 'trans': '?'}
n=2  all=16
  brute   {'refl': 4, 'sym': 8, 'anti': 12, 'asym': 3, 'trans': 13}
  formula {'refl': 4, 'sym': 8, 'anti': 12, 'asym': 3, 'trans': '?'}
n=3  all=512
  brute   {'refl': 64, 'sym': 64, 'anti': 216, 'asym': 27, 'trans': 171}
  formula {'refl': 64, 'sym': 64, 'anti': 216, 'asym': 27, 'trans': '?'}
transitive relations on 4 elements: 3994 of 65536

৬ · Relation জোড়া দেওয়া — union, intersection, difference আর inverse

Relation যেহেতু সেট, পর্ব ১৫ “সেটের অপারেশন — union, intersection, Venn diagram আর identity”-এর সব অপারেশন সরাসরি খাটে। R আর S দুটিই A থেকে B-তে হলে R ∪ S, R ∩ S, R − S, R ⊕ S সবই A থেকে B-তে relation. Matrix-এ union হলো ঘরে ঘরে ∨ (join, M_R ∨ M_S), আর intersection হলো ঘরে ঘরে ∧, যার নাম meet.

বাজারঘরের উদাহরণ। জানুয়ারির “কিনেছেন” relation K₁ আর ফেব্রুয়ারির K₂ হলে K₁ ∪ K₂ = “দুই মাসের যেকোনোটিতে কিনেছেন”, K₁ ∩ K₂ = “দুই মাসেই কিনেছেন” (নিয়মিত ক্রেতা-পণ্য জোড়া), আর K₁ − K₂ = “জানুয়ারিতে কিনেছেন কিন্তু ফেব্রুয়ারিতে আর কেনেননি”, যা মার্কেটিং দলের জন্য একটি কাজের তালিকা।

“কিনেছেন”-এর inverse হলো “কেনা হয়েছে … দ্বারা”, আর ℤ-এ <-এর inverse হলো >. ফাংশনের ক্ষেত্রে inverse relation f⁻¹ সবসময় আছে, কিন্তু সেটি নিজে একটি ফাংশন হয় ঠিক তখন, যখন f bijection (পর্ব ১৬)। Inverse দিয়ে ধর্মগুলোর ছোট রূপ পাওয়া যায়: R symmetric ⇔ R = R⁻¹; R antisymmetric ⇔ R ∩ R⁻¹ ⊆ Δ_A; R asymmetric ⇔ R ∩ R⁻¹ = ∅. প্রতিটি সংজ্ঞা থেকে সরাসরি আসে।

কোন ধর্ম অপারেশনে টিকে থাকে

একটি স্বাভাবিক প্রশ্ন: R আর S দুটিরই একটি ধর্ম থাকলে R ∪ S বা R ∩ S-এর কি সেটি থাকে? Reflexive আর symmetric union আর intersection দুটিতেই টেকে (সংজ্ঞা থেকে সরাসরি)। কিন্তু transitive-এর গল্প আলাদা।

1. (a, b) ∈ R ∩ S আর (b, c) ∈ R ∩ S নিন। তাহলে (a, b), (b, c) ∈ R. — intersection-এর সংজ্ঞা
2. R transitive, তাই (a, c) ∈ R; একইভাবে (a, b), (b, c) ∈ S থেকে (a, c) ∈ S. — transitivity দুবার
3. তাই (a, c) ∈ R ∩ S, অর্থাৎ R ∩ S transitive. — intersection-এর সংজ্ঞা
4. Union-এর counterexample: A = {1, 2}-এ R = {(1, 2)} আর S = {(2, 1)}. প্রতিটি একটিমাত্র জোড়ার relation, তাই কোনো দুই-ধাপ পথ নেই আর দুটিই transitive. কিন্তু R ∪ S = {(1, 2), (2, 1)}-এ 1 → 2 → 1 পথ আছে, অথচ (1, 1) নেই। ∎

এই অসমতার একটি গভীর পরিণাম আছে: যেকোনো R-কে ধারণ করে এমন সব transitive relation-এর intersection আবার transitive, আর সেটিই R-কে ধারণকারী সবচেয়ে ছোট transitive relation, যার নাম transitive closure. পরের পর্ব ৫৪ “Relation-এর closure আর Warshall-এর algorithm”-এ এটিই মূল বিষয়।

৭ · Composition, power আর একটি মূল উপপাদ্য

বাজারঘরের তিনটি গুদাম W = {G1, G2, G3}, তিনটি বিতরণ hub H = {h1, h2, h3}, আর তিনটি জেলা D = {ঢাকা, খুলনা, সিলেট}. R ⊆ W × H বলে কোন গুদাম কোন hub-এ মাল পাঠায়, আর S ⊆ H × D বলে কোন hub কোন জেলায় দেয়। প্রশ্ন: কোন গুদামের মাল কোন জেলায় পৌঁছাতে পারে? উত্তর একটি নতুন relation, যা দুটি relation “জোড়া দিয়ে” পাওয়া।

লেখার ক্রমটি খেয়াল করুন: S∘R-এ R আগে প্রয়োগ হয়, যদিও ডানে লেখা। কারণ এটি ফাংশনের composition-এর সঙ্গে মিলিয়ে রাখা হয়েছে: f আর g ফাংশন হলে, relation হিসেবে g∘f ঠিক পর্ব ১৬-এর composition (g∘f)(a) = g(f(a)), যেখানে f আগে। কিছু বই (আর relational algebra) উল্টো ক্রমে R;S লেখে; বই পড়ার সময় কোন রীতি তা আগে দেখে নিন।

1. (M_R ⊙ M_S)_ij = ⋁_k (r_ik ∧ s_kj), অর্থাৎ 1 ঠিক তখন, যখন কোনো k-এর জন্য r_ik = 1 আর s_kj = 1. — Boolean product-এর সংজ্ঞা, পর্ব ১৯
2. r_ik = 1 মানে (a_i, b_k) ∈ R, আর s_kj = 1 মানে (b_k, c_j) ∈ S. — 0-1 matrix-এর সংজ্ঞা
3. তাই ঘরটি 1 ঠিক তখন, যখন কোনো b_k মধ্যবর্তী হিসেবে আছে, যা (a_i, c_j) ∈ S∘R-এর সংজ্ঞা। ∎ — সংজ্ঞা ৭.১

এখানেও ক্রম: matrix-এ R বাঁয়ে, composition-এর চিহ্নে R ডানে। এই অদলবদলটি পরীক্ষায় একটি প্রিয় ফাঁদ।

1R: গুদাম → hub2S: hub → জেলা3G1-এর সব পথ4G2-এর সব পথ5G3-এর সব পথ6M_R ⊙ M_S দিয়ে মেলানো

1. (a, d) ∈ T∘(S∘R) ⇔ কোনো c-এর জন্য (a, c) ∈ S∘R আর (c, d) ∈ T. — সংজ্ঞা ৭.১
2. ⇔ কোনো c আর কোনো b-এর জন্য (a, b) ∈ R, (b, c) ∈ S আর (c, d) ∈ T. — S∘R-এর সংজ্ঞা খুলে, ∃-গুলো সামনে আনা (পর্ব ৫)
3. ⇔ কোনো b-এর জন্য (a, b) ∈ R আর [কোনো c-এর জন্য (b, c) ∈ S, (c, d) ∈ T]. — একই ধরনের দুটি ∃-এর ক্রম বদলানো যায়
4. ⇔ কোনো b-এর জন্য (a, b) ∈ R আর (b, d) ∈ T∘S ⇔ (a, d) ∈ (T∘S)∘R. ∎ — সংজ্ঞা ৭.১ দুবার

দুই পাশই বলে একই কথা: “a থেকে R, S, T ধরে তিন ধাপে d-তে যাওয়া যায়”। কিন্তু composition commutative নয়: A = {1, 2, 3}-এ R = {(1, 2), (2, 3)} আর S = {(2, 1), (3, 3)} হলে S∘R = {(1, 1), (2, 3)}, অথচ R∘S = {(2, 2)}. ফাংশনের মতোই, আগে মোজা পরে জুতা আর আগে জুতা পরে মোজা এক নয়।

Power আর transitivity

উদাহরণ: {1, 2, 3}-এ R = {(1, 2), (2, 3), (3, 1)}, একটি তিন-জোনের চক্রাকার রুট। R² = {(1, 3), (2, 1), (3, 2)} (দুই ধাপ সামনে), আর R³ = {(1, 1), (2, 2), (3, 3)} = Δ: তিন ধাপে সবাই নিজের জায়গায় ফেরে। R² ⊄ R, আর এটিই বলে দেয় R transitive নয়, নিচের উপপাদ্য অনুযায়ী।

1. (⇐) n = 2 নিন: R² ⊆ R. এখন (a, b), (b, c) ∈ R হলে সংজ্ঞা অনুযায়ী (a, c) ∈ R∘R = R² ⊆ R. তাই R transitive. — সংজ্ঞা ৭.১ আর ৭.৪
2. (⇒) R transitive ধরুন। n-এর ওপর induction করি। ভিত্তি n = 1: R¹ = R ⊆ R. — পর্ব ১০
3. Inductive hypothesis: কোনো n ≥ 1-এর জন্য Rⁿ ⊆ R. — ধরে নেওয়া
4. (a, c) ∈ Rⁿ⁺¹ = Rⁿ∘R নিন। সংজ্ঞা অনুযায়ী কোনো b আছে, যাতে (a, b) ∈ R আর (b, c) ∈ Rⁿ. — সংজ্ঞা ৭.১
5. Hypothesis থেকে (b, c) ∈ R; তাই (a, b), (b, c) ∈ R, আর transitivity থেকে (a, c) ∈ R. অর্থাৎ Rⁿ⁺¹ ⊆ R. ∎ — transitivity

উপপাদ্যটির অর্থ সহজ: transitive relation-এ “যতো ধাপেই যাওয়া যাক, সরাসরি তীর আছে”। আর §৩-এর matrix-শর্ত “M ⊙ M ≤ M” হলো ধাপ ১-এর R² ⊆ R, উপপাদ্য ৭.২ দিয়ে matrix-এ লেখা। উপপাদ্যটি একটি algorithm-এর দিকেও ইঙ্গিত দেয়: R ∪ R² ∪ R³ ∪ ⋯ নিলে একটি transitive relation পাওয়া যায়, আর n উপাদানের সেটে Rⁿ-এর পর নতুন কিছু আসে না। এর প্রমাণ আর দ্রুত Warshall algorithm পর্ব ৫৪-এ।

নিচের প্রথম ব্লক stepper-এর composition জোড়ার সেট আর Boolean product দুই পথে বের করে মেলায়, তারপর নির্দিষ্ট seed-এ ১০০০টি এলোমেলো relation-ত্রয়ীতে উপপাদ্য ৭.২ আর ৭.৩ পরীক্ষা করে, আর গোনে কয়বার S∘R = R∘S হয়। দ্বিতীয় ব্লক {0, 1, 2}-এর সব ৫১২টি relation-এ উপপাদ্য ৭.৫ আর ৬.২ যাচাই করে।

import random
random.seed(52)

def compose(S, R):                  # S o R: first R, then S
    return {(a, c) for (a, b) in R for (b2, c) in S if b == b2}

def matrix(R, X, Y):
    return [[int((x, y) in R) for y in Y] for x in X]

def bool_product(P, Q):             # (P . Q)[i][j] = OR_k (P[i][k] AND Q[k][j])
    return [[int(any(P[i][k] and Q[k][j] for k in range(len(Q))))
             for j in range(len(Q[0]))] for i in range(len(P))]

W, H, D = ["G1", "G2", "G3"], ["h1", "h2", "h3"], ["Dhaka", "Khulna", "Sylhet"]
R = {("G1", "h1"), ("G1", "h2"), ("G2", "h3"), ("G3", "h2")}
S = {("h1", "Dhaka"), ("h2", "Khulna"), ("h2", "Sylhet"), ("h3", "Dhaka")}
SR = compose(S, R)
print("S o R =", sorted(SR))
print("M_R . M_S =", bool_product(matrix(R, W, H), matrix(S, H, D)))
print("M_(S o R) =", matrix(SR, W, D))

A = range(5)                        # random relations on a 5-element set
def rand_rel(p=0.3):
    return {(a, b) for a in A for b in A if random.random() < p}
same_matrix = assoc = commute = 0
for _ in range(1000):
    R1, R2, R3 = rand_rel(), rand_rel(), rand_rel()
    M = bool_product(matrix(R1, A, A), matrix(R2, A, A))
    same_matrix += M == matrix(compose(R2, R1), A, A)
    assoc += compose(R3, compose(R2, R1)) == compose(compose(R3, R2), R1)
    commute += compose(R2, R1) == compose(R1, R2)
print("matrix rule held:", same_matrix, "/ 1000")
print("associativity held:", assoc, "/ 1000")
print("S o R == R o S in:", commute, "/ 1000")

S o R = [('G1', 'Dhaka'), ('G1', 'Khulna'), ('G1', 'Sylhet'), ('G2', 'Dhaka'), ('G3', 'Khulna'), ('G3', 'Sylhet')]
M_R . M_S = [[1, 1, 1], [1, 0, 0], [0, 1, 1]]
M_(S o R) = [[1, 1, 1], [1, 0, 0], [0, 1, 1]]
matrix rule held: 1000 / 1000
associativity held: 1000 / 1000
S o R == R o S in: 1 / 1000

from itertools import product
A = range(3)
pairs = [(a, b) for a in A for b in A]
rels = [frozenset(p for p, x in zip(pairs, bits) if x)
        for bits in product((0, 1), repeat=9)]

def compose(S, R):
    return frozenset((a, c) for (a, b) in R for (b2, c) in S if b == b2)

def transitive(R):
    return compose(R, R) <= R

def powers_inside(R, upto=4):       # is R^n a subset of R for n = 1..upto?
    P = R
    for _ in range(upto - 1):
        P = compose(R, P)           # R^(n+1) = R o R^n
        if not P <= R:
            return False
    return True
agree = sum(transitive(R) == powers_inside(R) for R in rels)
print("transitive <=> R^n in R (n<=4):", agree, "of", len(rels))

T = [R for R in rels if transitive(R)]
print("transitive relations on 3 elements:", len(T))
inter = all(transitive(R & S) for R in T for S in T)
print("intersection of two transitive is transitive:", inter)
for R in T:                         # look for a union that breaks it
    S = next((S for S in T if not transitive(R | S)), None)
    if S and len(R) == len(S) == 1:
        print("union counterexample:", sorted(R), "+", sorted(S),
              "->", sorted(R | S))
        break
inv = all(frozenset((b, a) for a, b in R) in set(T) for R in T)
print("inverse of transitive is transitive:", inv)

transitive <=> R^n in R (n<=4): 512 of 512
transitive relations on 3 elements: 171
intersection of two transitive is transitive: True
union counterexample: [(2, 1)] + [(1, 2)] -> [(1, 2), (2, 1)]
inverse of transitive is transitive: True

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

অঙ্ক ১: ধর্ম মিলিয়ে গোনা

A = {1, 2, 3}-এর ওপর (ক) কয়টি relation reflexive আর symmetric দুটিই? (খ) কয়টি reflexive-ও নয়, irreflexive-ও নয়?

1. (ক) উপপাদ্য ৫.১: 2^n(n−1)/2 = 2³ = 8. কর্ণ বাধ্যতামূলক 1, আর তিনটি অক্রমিক জোড়ার প্রতিটি থাকবে বা থাকবে না।
2. (খ) মোট 512 থেকে reflexive 64 আর irreflexive 64 বাদ দিন। n ≥ 1-এ কোনো relation একসঙ্গে দুটিই হতে পারে না (কর্ণের একটি ঘর একসঙ্গে 0 আর 1 নয়), তাই পর্ব ৪৯-এর inclusion–exclusion-এ ছেদ 0. উত্তর 512 − 64 − 64 = 384 (scratch-এ brute force দিয়ে মেলানো)।

অঙ্ক ২: Power দিয়ে transitivity

{1, 2, 3}-এ R = {(1, 2), (2, 3), (3, 1)}. R² আর R³ বের করে বলুন R transitive কি না।

1. R²: 1 → 2 → 3 দেয় (1, 3); 2 → 3 → 1 দেয় (2, 1); 3 → 1 → 2 দেয় (3, 2). R² = {(1, 3), (2, 1), (3, 2)}.
2. R³ = R²∘R: 1 → 2, তারপর R²-এ 2 → 1, তাই (1, 1); একইভাবে (2, 2), (3, 3). R³ = Δ.
3. (1, 3) ∈ R² কিন্তু (1, 3) ∉ R, তাই R² ⊄ R, আর উপপাদ্য ৭.৫ অনুযায়ী R transitive নয়। সরাসরি দোষী: (1, 2), (2, 3) আছে কিন্তু (1, 3) নেই।

অঙ্ক ৩: বিভাজ্যতা relation

A = {1, 2, 3, 4, 6, 12}-এর ওপর “a ∣ b” relation-এ কয়টি জোড়া, আর কোন ধর্মগুলো আছে?

1. প্রতিটি a-এর জন্য A-তে তার গুণিতক গুনি: 1 → ৬টি; 2 → 2, 4, 6, 12 (৪টি); 3 → 3, 6, 12 (৩টি); 4 → 4, 12 (২টি); 6 → 6, 12 (২টি); 12 → ১টি। মোট 18টি জোড়া (scratch-এ গুনে মেলানো)।
2. Reflexive (a ∣ a), antisymmetric (ধনাত্মকে a ∣ b আর b ∣ a হলে a = b), transitive (a ∣ b, b ∣ c হলে c = b·k = a·j·k, তাই a ∣ c হয়)। Symmetric নয় (2 ∣ 4, 4 ∤ 2), irreflexive নয়, asymmetric নয়। তিনটি ধর্ম মিলে একটি partial order, যার ছবি (Hasse diagram) পর্ব ৫৬-এ আঁকা হবে।

প্রয়োগ: কোথায় এই ধর্মগুলো কাজে লাগে

ডেটাবেসে প্রতিটি টেবিল একটি relation; ধর্ম আর composition-এর ধারণা থেকেই join আর query-র বীজগণিত আসে (ডেটাবেস ও SQL কোর্সের পর্ব ০৫ “Relational model — relation, tuple, attribute আর domain”, আর গণিতের দিক পর্ব ৫৩-এ)। কোনো build system বা বাজারঘরের অর্ডার-প্রক্রিয়ায় “x-এর আগে y” relation-কে asymmetric রাখতে হয়, নইলে চক্র তৈরি হয় আর কাজ শুরুই হয় না; তার transitive রূপ দিয়ে সব পরোক্ষ নির্ভরতা পাওয়া যায় (DSA কোর্সের পর্ব ৪২ “Topological sort আর DAG” দেখুন)। আর হিসাবের সফটওয়্যারে একটি “সমান” তুলনা reflexive, symmetric আর transitive না হলে sorting আর hashing ভুল ফল দেয়; floating-point-এ “প্রায় সমান” তুলনা transitive নয়, ঠিক §৪-এর |a − b| ≤ 1-এর মতো।

যুক্তির ভুল ধরুন: “symmetric আর transitive হলে reflexive”

একজন লিখলেন: “দাবি: R symmetric আর transitive হলে R reflexive. প্রমাণ: যেকোনো a ∈ A নিন। ধরুন (a, b) ∈ R. Symmetry থেকে (b, a) ∈ R. তাহলে (a, b) আর (b, a) থেকে transitivity অনুযায়ী (a, a) ∈ R. তাই R reflexive. ∎”

ভুল কোথায়: “ধরুন (a, b) ∈ R” ধাপটি ধরে নেয় যে a-এর অন্তত একটি সঙ্গী b আছে। a যদি কারও সঙ্গেই যুক্ত না থাকে, তাহলে যুক্তিটি শুরুই হয় না। Counterexample: A = {1, 2}-এ R = {(1, 1)}. R symmetric (একমাত্র জোড়ার উল্টো সে নিজেই), transitive (একমাত্র দুই-ধাপ পথ 1 → 1 → 1, আর (1, 1) আছে), কিন্তু (2, 2) নেই, তাই reflexive নয়। খালি relation ∅ আরও সরল counterexample. সঠিক বক্তব্য যা প্রমাণটি আসলে দেখায়: symmetric আর transitive R-এ যে a কারও সঙ্গে যুক্ত, তার জন্য (a, a) ∈ R থাকে। এই ভুলটি পর্ব ৫৫-এ equivalence relation-এর আলোচনায় আবার কাজে লাগবে: তিনটি শর্তের কোনোটিই বাড়তি নয়।

৯ · AI-এর যুগে — relation-এর প্রশ্নে AI-এর উত্তর যাচাই

Relation-এর প্রশ্ন ছোট আর নিয়মমাফিক দেখায়, তাই AI সহকারীরা আত্মবিশ্বাসী উত্তর দেয়। কিন্তু ঠিক এই ধরনের প্রশ্নে কয়েকটি নিয়মিত ভুল দেখা যায়, যা একটি ছোট brute force দিয়েই ধরা পড়ে।

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

• প্রতিটি “না”-এর জন্য দোষী জোড়াটি relation-এ সত্যিই আছে কি না দেখেছি
• প্রতিটি “হ্যাঁ” নিজে অন্তত matrix দেখে মিলিয়েছি (কর্ণ, transpose, M ⊙ M)
• গণনার সূত্র n = 2 আর n = 3-এ brute force দিয়ে মিলিয়েছি
• Composition-এর ক্রম (কোনটি আগে) আর matrix-এর ক্রম আলাদা করে দেখেছি
• প্রমাণে প্রতিটি “ধরুন … আছে” ধাপের অস্তিত্ব নিশ্চিত করেছি
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

Relation-এর সৌন্দর্য হলো, ছোট সেটে সবকিছু সম্পূর্ণ তালিকা করা যায়: তিন উপাদানে মাত্র ৫১২টি relation, যা Python এক সেকেন্ডের কম সময়ে দেখে ফেলে। তাই AI যা-ই দাবি করুক, ছোট n-এ পূর্ণ গণনা একটি নিরপেক্ষ বিচারক। প্রমাণ বলে কেন সত্য, আর brute force বলে অন্তত ছোট ক্ষেত্রে মিথ্যা নয়; দুটি একসঙ্গে থাকলে তবেই ভরসা করুন।