Equivalence relation আর partition

১ · “একই রকম” বলার গণিত — equivalence relation-এর সংজ্ঞা

আমরা প্রতিদিন জিনিসকে দলে ভাগ করি: একই ক্লাসের ছাত্র, একই রুটের রিকশা, একই মাসে জন্ম। প্রতিটি ক্ষেত্রে দুটি বস্তু “কোনো একটি দিক থেকে একই”, যদিও তারা হুবহু এক নয়। এই পর্বের প্রশ্ন: কোন ধরনের “একই” বললে দলগুলো পরিষ্কারভাবে ভাগ হয়, কেউ দুই দলে পড়ে না, আর কেউ বাদ যায় না?

পর্ব ৫২ “Relation আর তার ধর্ম — reflexive, symmetric, transitive”-এ relation-কে একটি সেট হিসেবে দেখা হয়েছে: সেট A-এর ওপর একটি relation R মানে A × A-এর একটি subset (পর্ব ১৪-এর Cartesian product). (a, b) ∈ R হলে লিখি a R b, আর এই পর্বে বিশেষ relation-এর জন্য চিহ্ন a ~ b (পড়ুন “a, b-এর সমতুল্য”)। এখানে সংজ্ঞাগুলো আবার নির্ভুলভাবে লিখে রাখি।

লক্ষ করুন, reflexive শর্তটি “প্রতিটি a-এর জন্য”, অর্থাৎ এটি সেট A-এর ওপর নির্ভর করে; বাকি দুটি শর্ত “যদি … তবে” ধরনের। এই সূক্ষ্ম পার্থক্যটি §৯-এর ভুল প্রমাণের মূলে।

উদাহরণ (সবগুলো equivalence):

• Congruence mod m: ℤ-এ a ≡ b (mod m) মানে m ∣ a − b. তিনটি ধর্মের প্রমাণ পর্ব ২২ “Modular arithmetic”-এ আছে (a − a = 0; a − b = km হলে b − a = (−k)m; দুটি সমীকরণ যোগ)। এটিই সব equivalence-এর আদর্শ নমুনা।
• একই জেলা: গ্রাহকের সেটে a ~ b মানে দুজনের ডেলিভারি জেলা এক।
• একই দৈর্ঘ্যের string: সব bit string-এর সেটে s ~ t মানে |s| = |t|.
• একই hash মান: একটি hash function h-এর জন্য x ~ y মানে h(x) = h(y) (পর্ব ২৬ আর পর্ব ৪২-এর hash table-এর একই bucket).
• Graph isomorphism: দুটি graph-এর vertex-এর নাম বদলে একটিকে অন্যটি বানানো গেলে তারা isomorphic; এটিও একটি equivalence, বিস্তারিত পর্ব ৫৮ “গ্রাফের representation আর isomorphism”-এ।

পাল্টা-উদাহরণ (প্রতিটিতে একটি ধর্ম ভাঙে):

শেষের আগের সারিটি মনে রাখার মতো: ℤ-এ “ab > 0” (একই চিহ্নের, শূন্য বাদে) symmetric আর transitive, কিন্তু reflexive নয়, কারণ 0 নিজের সঙ্গেও সম্পর্কিত নয়। “কাছাকাছি” ধরনের সম্পর্ক (দূরত্ব ১-এর মধ্যে, দামের পার্থক্য ১০ টাকার মধ্যে) প্রায় কখনো transitive নয়; ছোট ছোট ধাপ জমে বড় পার্থক্য হয়।

২ · Equivalence class — প্রতিটি উপাদানের দল

Congruence mod m-এর class হলো পর্ব ২২-এর congruence class [a]_m. নিচের stepper-এ {0, 1, …, 11} সেটে mod 4-এর class একে একে বের করা হয়েছে: একটি এখনো-না-দেখা সংখ্যা নিন, তার সমতুল্য সবাইকে তুলে নিন, তারপর পরের না-দেখা সংখ্যায় যান।

1a ~ b ⇔ 4 ∣ a − b2[0] = {0, 4, 8}3[1] = {1, 5, 9}4[2] = {2, 6, 10}5[3] = {3, 7, 11}6[4] = [8] = [0], …

Stepper-এর শেষ ধাপের পর্যবেক্ষণ (“[4] = [0]”) আর “কেউ দুই class-এ পড়ে না” সাধারণভাবে সত্য। পরের lemma-টি এই পর্বের প্রায় সব প্রমাণের ভিত্তি।

1. (ক) ⇒ (খ): ধরুন a ~ b. x ∈ [a] নিলে x ~ a, আর a ~ b, তাই transitive ধর্মে x ~ b, অর্থাৎ x ∈ [b]. তাই [a] ⊆ [b]. — transitive
2. symmetric ধর্মে b ~ a, তাই একই যুক্তিতে [b] ⊆ [a]; দুই দিকের অন্তর্ভুক্তি থেকে [a] = [b]. — symmetric, পর্ব ১৪-এর double inclusion
3. (খ) ⇒ (গ): reflexive ধর্মে a ~ a, তাই a ∈ [a] = [b], আর ছেদ খালি নয়। — reflexive
4. (গ) ⇒ (ক): c ∈ [a] ∩ [b] নিন। তাহলে c ~ a আর c ~ b. symmetric ধর্মে a ~ c, তারপর transitive ধর্মে a ~ b. ∎ — symmetric, transitive

প্রমাণে তিনটি ধর্মের প্রতিটি ঠিক এক জায়গায় লেগেছে। ফলাফলটি এক বাক্যে: দুটি class হয় হুবহু সমান, নয়তো একেবারে আলাদা; আংশিক মিল বলে কিছু নেই।

৩ · মৌলিক উপপাদ্য — equivalence relation আর partition একই জিনিস

সেট A-এর একটি partition (দলভাগ) হলো A-এর খালি-নয় এমন কয়েকটি subset-এর একটি সংগ্রহ, যাদের বলে block, যাতে প্রতিটি উপাদান ঠিক একটি block-এ পড়ে। অর্থাৎ block-গুলো খালি নয়, দুটি-দুটি করে পরস্পর বিচ্ছিন্ন, আর সবগুলোর union পুরো A. এই ধারণাটি পর্ব ৩৯-এ sample space ভাগ করতে আর পর্ব ৫০-এ গোনার জন্য এসেছে।

(ক)-এর প্রমাণ।

1. প্রতিটি class খালি নয়: a ∈ [a]. — reflexive
2. class-গুলোর union পুরো A: যেকোনো a ∈ A নিজের class [a]-তে আছে। — ধাপ ১
3. দুটি আলাদা class বিচ্ছিন্ন: [a] ≠ [b] হলে lemma ২.২-এর (খ) ⇔ (গ) অনুযায়ী [a] ∩ [b] = ∅. ∎ — lemma ২.২

(খ)-এর প্রমাণ। প্রতিটি a-এর জন্য B(a) দিয়ে বোঝাই a যে একমাত্র block-এ আছে।

1. Reflexive: a আর a একই block B(a)-তে। — partition-এ প্রতিটি উপাদান কোনো block-এ
2. Symmetric: a আর b একই block-এ থাকলে b আর a-ও একই block-এ। — “একই block” কথাটি দুই দিকে একই
3. Transitive: a, b একই block-এ আর b, c একই block-এ। b ঠিক একটি block-এ আছে, তাই দুটি block একই, B(a) = B(b) = B(c), আর a ~_P c. — block-গুলো বিচ্ছিন্ন
4. a-এর class = {x : x আর a একই block-এ} = B(a), তাই class-গুলো ঠিক P-এর block. ∎ — class-এর সংজ্ঞা

(গ)-এর প্রমাণ। ~ থেকে partition বানিয়ে আবার relation বানালে পাই “a আর b একই class-এ”, যা lemma ২.২ অনুযায়ী ঠিক a ~ b. আর P থেকে relation বানিয়ে আবার class নিলে (খ)-এর ধাপ ৪ অনুযায়ী P-ই ফিরে আসে। দুই দিকের composition identity, তাই দুটি রূপান্তর পরস্পরের উল্টো, আর পর্ব ১৬ অনুযায়ী দুটিই bijection. ∎

ছবিতে কথাটি এরকম: এক দিকে দলভাগ, অন্য দিকে zero-one matrix (পর্ব ১৯)। Row আর column একই দলের সদস্যদের পাশাপাশি রেখে সাজালে matrix-এর 1-গুলো কর্ণ বরাবর কয়েকটি বর্গাকার block-এ জমে, আর বাকি সব 0.

ছবির শেষ লাইনটি একটি দরকারি সূত্র: block-গুলোর আকার s₁, s₂, …, s_k হলে relation-এ ঠিক s₁² + s₂² + ⋯ + s_k²টি ক্রমজোড়া, কারণ একটি block-এর ভেতরে যেকোনো দুজন (নিজেকে নিজের সঙ্গেসহ) সম্পর্কিত। নিচের stepper দুই দিকের রূপান্তর হাতে করে দেখায়।

1P = {{1,3}, {2,5}, {4}}2block {1,3} → জোড়া3block {2,5} → জোড়া4block {4} → জোড়া5উল্টো: matrix-এর সারি 1, 26সারি 3, 4, 5 → partition

৪ · কয়টি equivalence relation — Bell আর Stirling সংখ্যা

মৌলিক উপপাদ্যের সবচেয়ে সরাসরি লাভ গণনায়। n-উপাদানের সেটে relation আছে 2^n²টি (n × n matrix-এর প্রতিটি ঘর 0 বা 1). তাদের মধ্যে কয়টি equivalence? প্রশ্নটি কঠিন শোনায়, কিন্তু উপপাদ্য ৩.১(গ)-এর bijection অনুযায়ী উত্তর = n-উপাদানের সেটের partition-এর সংখ্যা, যা পর্ব ৫০ “বিশেষ সংখ্যা — Catalan, Stirling আর partition”-এর Bell সংখ্যা B_n.

প্রমাণ: bijection একটি সেটের আকার অন্য সেটে বহন করে (পর্ব ৩৭-এর bijective গণনা), আর k-টি class মানে k-টি block. Bell-এর recurrence-এর প্রমাণ পর্ব ৫০-এ আছে: n + 1তম উপাদানের block-এ আর কোন কোন উপাদান থাকবে, তা বাছাই করে বাকিদের ভাগ করা। ∎

B_n-এর শুরু: 1, 1, 2, 5, 15, 52, 203, 877, 4140 (n = 0 থেকে 8). তুলনায় relation-এর সংখ্যা n = 3-এ 512, n = 6-এ 2³⁶ ≈ ৬,৮৭২ কোটি। নিচের ব্লক দাবিটি দুইভাবে যাচাই করে। n ≤ 3-এ সব relation তালিকা করে তিনটি ধর্ম পরীক্ষা করে। বড় n-এ সব relation দেখা অসম্ভব, তাই কেবল reflexive আর symmetric relation-গুলো দেখে (প্রতিটি অ-কর্ণ জোড়া {a, b} থাকবে কি না, 2^C(n,2)টি; n = 6-এ 32768), আর transitive কি না পরীক্ষা করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে; পরের ব্লকগুলো দ্রুত চলে।

from itertools import combinations, product
from math import comb
from collections import Counter
def is_equivalence(n, R):              # R = set of pairs (a, b)
    refl = all((a, a) in R for a in range(n))
    sym = all((b, a) in R for a, b in R)
    trans = all((a, d) in R for a, b in R for c, d in R if b == c)
    return refl and sym and trans
# n <= 3: try every one of the 2^(n*n) relations
for n in range(1, 4):
    cells = list(product(range(n), repeat=2))
    hits = sum(is_equivalence(n, {p for p, x in zip(cells, bits) if x})
               for bits in product((0, 1), repeat=n * n))
    print(f"n={n}: {2 ** (n * n):3} relations, {hits} equivalences")
def count_classes(n):                  # only reflexive + symmetric candidates
    edges = list(combinations(range(n), 2))
    by_k = Counter()
    for bits in product((0, 1), repeat=len(edges)):
        nb = [{a} for a in range(n)]   # nb[a] = everything related to a
        for (a, b), x in zip(edges, bits):
            if x:
                nb[a].add(b); nb[b].add(a)
        # transitive <=> related elements have identical neighbour sets
        if all(nb[a] == nb[b] for a in range(n) for b in nb[a]):
            by_k[len({frozenset(s) for s in nb})] += 1
    return by_k
bell = [1]
for m in range(6):                     # B(m+1) = sum C(m, k) B(k)
    bell.append(sum(comb(m, k) * bell[k] for k in range(m + 1)))
for n in range(1, 7):
    by_k = count_classes(n)
    print(f"n={n}: brute {sum(by_k.values()):3}  Bell {bell[n]:3}"
          f"  by #classes {[by_k[k] for k in range(1, n + 1)]}")

n=1:   2 relations, 1 equivalences
n=2:  16 relations, 2 equivalences
n=3: 512 relations, 5 equivalences
n=1: brute   1  Bell   1  by #classes [1]
n=2: brute   2  Bell   2  by #classes [1, 1]
n=3: brute   5  Bell   5  by #classes [1, 3, 1]
n=4: brute  15  Bell  15  by #classes [1, 7, 6, 1]
n=5: brute  52  Bell  52  by #classes [1, 15, 25, 10, 1]
n=6: brute 203  Bell 203  by #classes [1, 31, 90, 65, 15, 1]

একটি কাজের কৌশল। “1 আর 2 একই class-এ” এমন equivalence কয়টি, n-উপাদানের সেটে? 1 আর 2-কে একটি উপাদান হিসেবে জুড়ে দিলে বাকি থাকে n − 1টি “উপাদান”, আর যেকোনো partition-এ জোড়টি একসঙ্গে থাকে। তাই উত্তর B_n−1; n = 5-এ B₄ = 15 (scratch-এ সব partition তালিকা করে মেলানো)।

৫ · Quotient set আর well-defined অপারেশন

Equivalence-এর সবচেয়ে শক্তিশালী ব্যবহার হলো class-গুলোকে নতুন বস্তু হিসেবে দেখা। প্রতিটি class একটি “উপাদান” হয়ে যায়, আর তার ভেতরের পার্থক্য ভুলে যাওয়া হয়।

ℤ/≡_m হলো পর্ব ২২-এর ℤ_m = {[0], [1], …, [m − 1]}. π একটি surjection (প্রতিটি class কোনো না কোনো উপাদানের class), কিন্তু সাধারণত one-to-one নয়: π(1) = π(5) = [1] mod 4-এ। পর্ব ১৮-এর ভাষায়, সসীম A-এর জন্য |A/~| ≤ |A|, সমতা শুধু তখন যখন প্রতিটি class এক-সদস্যের।

এখন আসল প্রশ্ন। ℤ_m-এ যোগ সংজ্ঞায়িত হয় [a] + [b] = [a + b] দিয়ে। কিন্তু ডান পাশের সূত্রটি প্রতিনিধি a আর b ব্যবহার করে, আর একটি class-এর প্রতিনিধি অনেক। ফল যদি প্রতিনিধি বাছাইয়ের ওপর নির্ভর করত, তবে “[a] + [b]” কোনো নির্দিষ্ট class বোঝাত না।

উদাহরণ ১ (well-defined): mod m-এ যোগ। a ≡ a′ আর b ≡ b′ (mod m) হলে a − a′ = km আর b − b′ = lm, তাই (a + b) − (a′ + b′) = (k + l)m, অর্থাৎ [a + b] = [a′ + b′]. গুণেও একই (পর্ব ২২-এর উপপাদ্য ৩.১)। এভাবেই পর্ব ২২-এর হিসাব “শুধু ভাগশেষ নিয়ে কাজ” করা বৈধ হয়েছিল।

উদাহরণ ২ (well-defined নয়): mod 5-এ ঘাত। [a]^[b] = [a^b] নিয়মটি নিন। 1 ≡ 6 (mod 5), অথচ 2¹ = 2 আর 2⁶ = 64 ≡ 4 (mod 5). একই class [1] = [6] থেকে দুটি আলাদা ফল, তাই ঘাতে class বসানো যায় না। (ঘাত কোন modulus-এ কমানো যায়, তা পর্ব ২৪-এর Euler-এর উপপাদ্য বলে: সূচক mod φ(m), শর্তসাপেক্ষে।)

1. ধরুন n ∣ m. a ≡ a′ (mod m) হলে m ∣ a − a′, আর n ∣ m বলে n ∣ a − a′, অর্থাৎ [a]_n = [a′]_n. — বিভাজ্যতার transitive ধর্ম
2. উল্টো দিকে ধরুন F well-defined. 0 ≡ m (mod m), তাই [0]_n = [m]_n, অর্থাৎ n ∣ m − 0 = m. ∎ — একটি নির্দিষ্ট জোড়া পরীক্ষা

যেমন ঘড়ির ঘণ্টা (mod 12) থেকে “সকাল-সন্ধ্যার চার প্রহরের কোনটি” (mod 4) বের করা চলে, কারণ 4 ∣ 12; কিন্তু mod 6 থেকে mod 4 চলে না: [0]₆ = [6]₆, অথচ [0]₄ ≠ [6]₄ = [2]₄.

৬ · Kernel — প্রতিটি equivalence একটি ফাংশনের “একই মান”

“একই জেলা”, “একই দৈর্ঘ্য”, “একই hash”, “একই ভাগশেষ”: প্রতিটি উদাহরণে একটি ফাংশন লুকিয়ে আছে (জেলা, দৈর্ঘ্য, hash, mod m), আর সম্পর্কটি হলো “ফাংশনের মান সমান”। এটি কাকতালীয় নয়।

1. f(x) = f(x); f(x) = f(y) হলে f(y) = f(x); f(x) = f(y) আর f(y) = f(z) হলে f(x) = f(z). তাই ~_f একটি equivalence. — সমান চিহ্ন “=” নিজেই একটি equivalence
2. π(x) = π(y) ⇔ [x] = [y] ⇔ x ~ y. ∎ — lemma ২.২

এর ব্যবহারিক অর্থ বড়: আপনি যদি দুটি বস্তুর তুলনা লেখেন key(x) == key(y) আকারে (যেমন email-কে ছোট হাতের অক্ষরে রূপান্তর করে তুলনা), তবে তিনটি ধর্ম আপনাআপনি সত্য, আলাদা করে প্রমাণ করতে হয় না। কিন্তু “দূরত্ব ১-এর কম” ধরনের তুলনা এই আকারে লেখা যায় না, আর সেজন্যই তা transitive নয়।

Kernel-এর ভাষায় প্রতিটি ফাংশনকে তিন টুকরোয় ভাঙা যায়: প্রথমে দলে ভাগ করা, তারপর দল থেকে মানে যাওয়া, শেষে মানটিকে বড় সেটে বসানো।

1. Well-defined: a ~ a′ মানে ker f-এর সংজ্ঞায় f(a) = f(a′), তাই f̄([a]) প্রতিনিধির ওপর নির্ভর করে না। — সংজ্ঞা ৫.২
2. One-to-one: f̄([a]) = f̄([b]) হলে f(a) = f(b), অর্থাৎ a ~ b, আর lemma ২.২ অনুযায়ী [a] = [b]. — kernel-এর সংজ্ঞা
3. Onto: f(A)-এর প্রতিটি মান কোনো f(a), যা f̄([a]). — image-এর সংজ্ঞা
4. যেকোনো a-তে (ι ∘ f̄ ∘ π)(a) = ι(f̄([a])) = f(a). ∎ — পর্ব ১৬-এর composition

বাজারঘরের উদাহরণে: f = “গ্রাহকের জেলা”, A/~ = গ্রাহকদের জেলাভিত্তিক দল, আর f̄ প্রতিটি দলকে তার জেলার নাম দেয়, এক দলের এক নাম। ফলাফল হিসেবে একটি গণনা পাওয়া যায়: |A/ker f| = |f(A)|, অর্থাৎ class-এর সংখ্যা = আলাদা মানের সংখ্যা। Hash-এর ভাষায়: যতগুলো আলাদা hash মান আসলে ব্যবহৃত হয়েছে, ঠিক ততগুলো bucket-এ ডেটা আছে।

৭ · Refinement, intersection, union আর সবচেয়ে ছোট equivalence

একই সেটে অনেক equivalence থাকতে পারে, কোনোটি সূক্ষ্ম, কোনোটি মোটা দাগের। “একই থানা” “একই জেলা”-র চেয়ে সূক্ষ্ম: একই থানার দুজন সবসময় একই জেলার।

সবচেয়ে সূক্ষ্ম partition-এ প্রতিটি block এক-সদস্যের (relation শুধু কর্ণ Δ = {(a, a)}), আর সবচেয়ে মোটায় একটিই block (relation পুরো A × A). Congruence-এ: mod 4, mod 2-এর refinement, কারণ 4 ∣ a − b হলে 2 ∣ a − b. সাধারণভাবে mod a, mod b-এর refinement যদি এবং কেবল যদি b ∣ a (উপপাদ্য ৫.৩-এর একই যুক্তি; scratch-এ 1 ≤ a, b ≤ 8 সব জোড়ায় মেলানো)। Partition-গুলো refinement অনুযায়ী একটি “partial order” তৈরি করে, যার আলোচনা পর্ব ৫৬ “Partial order, Hasse diagram, topological sort আর lattice”-এ।

1. (ক) প্রতিটি ~_i-তে (a, a) আছে, তাই intersection-এও। (a, b) সবগুলোতে থাকলে প্রতিটি symmetric বলে (b, a)-ও সবগুলোতে। (a, b), (b, c) সবগুলোতে থাকলে প্রতিটি transitive বলে (a, c)-ও সবগুলোতে। — প্রতিটি ধর্ম “সবগুলোতে” কথার সঙ্গে খাপ খায়
2. (খ) reflexive আর symmetric একইভাবে টিকে যায়। Transitive ভাঙার উদাহরণ: {0, …, 5}-এ R₂ = “একই parity”, R₃ = “mod 3-এ সমান”। 0 R₂ 2 আর 2 R₃ 5, তাই union-এ 0 ~ 2, 2 ~ 5; কিন্তু 0 − 5 = −5, যা ২ বা ৩ কোনোটি দিয়েই বিভাজ্য নয়। ∎ — পাল্টা-উদাহরণ

Intersection-এর class হলো দুই partition-এর block-গুলোর ছেদ, অর্থাৎ দুটির সবচেয়ে মোটা সাধারণ refinement; congruence-এ ≡_a ∩ ≡_b = ≡_{lcm(a, b)} (পর্ব ২১-এর lcm). Union equivalence না হলে স্বাভাবিক প্রশ্ন: R-কে ধারণ করে এমন সবচেয়ে ছোট equivalence কোনটি?

1. A × A নিজেই R-কে ধারণকারী একটি equivalence, তাই সংগ্রহটি খালি নয়; উপপাদ্য ৭.২(ক) অনুযায়ী intersection E(R) একটি equivalence, আর সংজ্ঞা অনুযায়ী R-কে ধারণকারী প্রতিটি equivalence-এর ভেতরে। — intersection
2. S = R ∪ Δ ∪ R⁻¹ reflexive আর symmetric. S^* (S-এর জোড়া ধরে পথ) transitive, আর reflexive থাকে কারণ S ⊆ S^*. — transitive closure-এর সংজ্ঞা
3. S^* symmetric: x থেকে y-তে S-এর পথ x = v₀, v₁, …, v_k = y থাকলে, S symmetric বলে প্রতিটি ধাপ উল্টানো যায়, তাই y থেকে x-এ উল্টো পথ। সুতরাং S^* একটি equivalence যা R-কে ধারণ করে, আর E(R) ⊆ S^*. — পথ উল্টানো
4. উল্টো দিকে, R-কে ধারণকারী যেকোনো equivalence ~ নিজে reflexive আর symmetric, তাই S ⊆ ~; আর transitive বলে S-এর প্রতিটি পথের দুই প্রান্ত ~-এ সম্পর্কিত, অর্থাৎ S^* ⊆ ~. তাই S^* ⊆ E(R). ∎ — induction, পথের দৈর্ঘ্যে

Closure-এর সাধারণ তত্ত্ব আর Warshall-এর algorithm পর্ব ৫৪ “Relation-এর closure আর Warshall-এর algorithm”-এ আসছে। এখানে লক্ষ করার বিষয় ক্রম: transitive closure শেষে। আগে transitive, পরে symmetric নিলে ফল transitive না-ও হতে পারে (অনুশীলন ৪)। নিচের ব্লক জোড়ার তালিকা থেকে class বের করে, আর উপপাদ্য ৭.২-এর পাল্টা-উদাহরণ যাচাই করে।

def eq_closure(n, pairs):             # smallest equivalence containing pairs
    M = [[i == j for j in range(n)] for i in range(n)]      # reflexive
    for a, b in pairs:
        M[a][b] = M[b][a] = True                            # symmetric
    for k in range(n):                                      # Warshall
        for i in range(n):
            if M[i][k]:
                for j in range(n):
                    M[i][j] = M[i][j] or M[k][j]
    return M

def classes(M):                       # equal rows = one class
    rows = {tuple(j for j, x in enumerate(r) if x) for r in M}
    return sorted(rows)

# same product listed twice: (0,4), (4,7), (2,9), (5,6), (6,2)
M = eq_closure(10, [(0, 4), (4, 7), (2, 9), (5, 6), (6, 2)])
print("product classes:", classes(M))

n = 6                                 # R2 = same parity, R3 = same mod 3
R2 = {(a, b) for a in range(n) for b in range(n) if (a - b) % 2 == 0}
R3 = {(a, b) for a in range(n) for b in range(n) if (a - b) % 3 == 0}
U = R2 | R3
bad = [(a, b, c) for a, b in U for b2, c in U
       if b == b2 and (a, c) not in U]
print("union transitive?", not bad, " first break:", min(bad))
print("intersection = same mod 6?",
      R2 & R3 == {(a, a) for a in range(n)})
print("closure of the union:", classes(eq_closure(n, U)))

product classes: [(0, 4, 7), (1,), (2, 5, 6, 9), (3,), (8,)]
union transitive? False  first break: (0, 2, 5)
intersection = same mod 6? True
closure of the union: [(0, 1, 2, 3, 4, 5)]

৮ · Union-find — দল জোড়া লাগার সময় class রাখা

Closure-এর matrix পদ্ধতি n² জায়গা আর প্রায় n³ কাজ নেয়, আর জোড়া একটি একটি করে আসতে থাকলে প্রতিবার আবার হিসাব করতে হয়। বাজারঘরের বাস্তব সমস্যা ঠিক এমন: নতুন অ্যাকাউন্ট খুললেই দেখতে হয়, একই ফোন নম্বর বা email আগে কোনো অ্যাকাউন্টে ছিল কি না; থাকলে দুটি অ্যাকাউন্ট “একই গ্রাহক”। এই সম্পর্কটি জোড়ার equivalence closure, কারণ A1 আর A2-এর email এক, A2 আর A3-এর ফোন এক হলে A1 আর A3-ও একই গ্রাহক, যদিও তাদের কোনো তথ্য সরাসরি মেলে না।

এর জন্য তৈরি ডেটা স্ট্রাকচার union-find (disjoint set union). কোড আর জটিলতার পূর্ণ আলোচনা DSA কোর্সের পর্ব ৩৩ “Disjoint set union (union-find)”-এ; এখানে শুধু গণিত: এটি কী রাখে, আর কেন সঠিক।

• প্রতিটি উপাদান x-এর একটি parent[x]; parent ধরে উঠতে থাকলে শেষে একটি root পাওয়া যায়, যার parent সে নিজে। find(x) সেই root ফেরত দেয়: এটিই x-এর class-এর প্রতিনিধি।
• union(a, b): find(a) আর find(b) আলাদা হলে একটি root-কে অন্যটির নিচে বসানো। নিচের stepper-এ ছোট দলের root বড় দলের root-এর নিচে যায়, সমান হলে প্রথম যুক্তির root ওপরে থাকে (union by size).
• Path compression: find(x) চলার পথে যত node পাওয়া যায়, সবার parent সরাসরি root করে দেওয়া, যাতে পরের বার এক লাফে পৌঁছানো যায়।

1শুরু: parent[x] = x2union(0,1); union(2,3)3union(0,2)4union(4,5); union(6,7)5union(4,6)6union(3,7)7find(5)8find(7)

1. Invariant ধরুন: “একই root” relation, যাকে ~_root বলি, সবসময় E-এর সমান। ~_root একটি ফাংশনের (find-এর) kernel, তাই সবসময় একটি equivalence. — উপপাদ্য ৬.২
2. Base: শুরুতে root সবার আলাদা, তাই ~_root = Δ, আর কোনো জোড়া না আসায় E = Δ. — induction-এর ভিত্তি
3. find-এর path compression শুধু এমন node-এর parent বদলায় যাদের root আগে থেকেই r, আর নতুন parent সেই r; তাই কারও root বদলায় না, ~_root অপরিবর্তিত। — invariant রক্ষা
4. union(a, b): root r_a ≠ r_b হলে একটিকে অন্যটির নিচে বসালে ঠিক দুটি class এক হয়, বাকিরা যেমন ছিল। আর E-তে (a, b) যোগ করলে নতুন closure-এও ঠিক [a] আর [b] এক হয়, কারণ নতুন পথ শুধু ওই জোড়া দিয়ে যায়। r_a = r_b হলে দুই দিকেই কিছু বদলায় না। ∎ — induction-এর ধাপ, উপপাদ্য ৭.৩

এই প্রমাণে union by size বা path compression কোনোটিই সঠিকতার জন্য লাগেনি; ওরা শুধু গতি দেয়। দুটি একসঙ্গে থাকলে m-টি কাজের মোট সময় O(m α(n)), যেখানে α(n) অবিশ্বাস্য ধীরে বাড়া inverse Ackermann ফাংশন। এই সীমা Robert Tarjan ১৯৭৫ সালে প্রমাণ করেন বলে সাধারণত উল্লেখ করা হয়; প্রমাণটি এই কোর্সের বাইরে।

নিচের ব্লক বাজারঘরের ৭টি অ্যাকাউন্টে কাজটি করে, তারপর ২০০টি এলোমেলো জোড়ার তালিকায় union-find আর closure-এর উত্তর মেলায়। এখানে find path compression করে, আর union সরল (b-এর root যায় a-এর root-এর নিচে)।

import random
parent = {}
def find(x):                          # root, with path compression
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root
def union(a, b): parent[find(b)] = find(a)
accounts = {"A1": ("017-01", "rina@x"), "A2": ("018-02", "rina@x"),
            "A3": ("018-02", "rk@y"), "A4": ("019-04", "sumon@x"),
            "A5": ("016-05", "joy@y"), "A6": ("019-04", "joy@y"),
            "A7": ("015-07", "nila@x")}
parent.update({a: a for a in accounts})
owner = {}                            # first account seen with a phone/email
for acc, keys in accounts.items():
    for key in keys:
        union(owner.setdefault(key, acc), acc)
print("same customer:", sorted({tuple(a for a in accounts
                                 if find(a) == find(r)) for r in accounts}))
random.seed(55)                       # check against the closure method
for trial in range(200):
    n = random.randint(2, 12)
    pairs = [(random.randrange(n), random.randrange(n)) for _ in range(n)]
    parent.clear(); parent.update({i: i for i in range(n)})
    nb = {i: {i} for i in range(n)}   # closure: grow until nothing changes
    for a, b in pairs:
        union(a, b)
    for _ in range(n):
        for a, b in pairs + [(b, a) for a, b in pairs]:
            nb[a] |= nb[b]
    assert all((find(i) == find(j)) == (j in nb[i])
               for i in range(n) for j in range(n))
print("200 random tests: union-find == closure")

same customer: [('A1', 'A2', 'A3'), ('A4', 'A5', 'A6'), ('A7',)]
200 random tests: union-find == closure

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

Orbit: symmetry থেকে আসা equivalence

পর্ব ৫১ “Symmetry দিয়ে গণনা — Burnside-এর lemma আর Pólya”-এ একটি group action-এর জন্য x ~ y ⇔ “কোনো g-এর জন্য g·x = y” সম্পর্কটি equivalence বলে প্রমাণ হয়েছে (identity থেকে reflexive, উল্টো উপাদান থেকে symmetric, composition থেকে transitive). তার class-ই orbit, আর মৌলিক উপপাদ্য অনুযায়ী orbit-গুলো সেটটিকে ভাগ করে। তাই Burnside-এর lemma আসলে একটি নির্দিষ্ট equivalence-এর class গোনার সূত্র: |X/~| = (1/|G|)∑|Fix(g)|. একই ধাঁচে isomorphism-এর class-ও orbit (vertex-এর নাম বদলানোর group), যা পর্ব ৫৮-এ আসবে।

অঙ্ক ১: Equivalence কি না, আর class

A = {1, 2, 3, 4, 5, 6}-এ a R b ⇔ a + b জোড়। R কি equivalence? class আর জোড়ার সংখ্যা কত?

1. a + a = 2a জোড়, তাই reflexive. a + b জোড় হলে b + a-ও একই সংখ্যা, তাই symmetric.
2. a + b আর b + c জোড় হলে (a + b) + (b + c) = a + c + 2b জোড়, তাই a + c জোড়: transitive. সুতরাং equivalence (আসলে a R b ⇔ a ≡ b (mod 2), parity-ফাংশনের kernel).
3. class: {1, 3, 5} আর {2, 4, 6}; জোড়া 3² + 3² = 18 (scratch-এ গুনে মেলানো)।

অঙ্ক ২: সবচেয়ে ছোট equivalence

A = {1, 2, 3, 4}-এ R = Δ ∪ {(1,2), (2,1), (2,3), (3,2)}. R কি equivalence? না হলে R-কে ধারণকারী সবচেয়ে ছোট equivalence কোনটি?

1. R reflexive আর symmetric, কিন্তু 1 R 2, 2 R 3 অথচ (1, 3) ∉ R: transitive নয়।
2. উপপাদ্য ৭.৩: পথ ধরে 1, 2, 3 যুক্ত, 4 একা। তাই class {1, 2, 3} আর {4}; যোগ করতে হয় শুধু (1,3) আর (3,1).
3. উত্তর: 3² + 1² = 10টি জোড়ার relation (R-এর ৮টি + ২টি)।

অঙ্ক ৩: গোনা

{a, b, c, d}-এ কয়টি equivalence relation? ঠিক দুটি class-যুক্ত কয়টি? উত্তর: B₄ = 15; class-এর সংখ্যা অনুযায়ী 1 + 7 + 6 + 1. দুটি class: আকার ৩ + ১ হলে একা উপাদানটি বাছার ৪ উপায়, আর ২ + ২ হলে C(4, 2)/2 = 3 উপায় (দুটি block নামহীন বলে ২ দিয়ে ভাগ), মোট S(4, 2) = 7 (প্রথম Python ব্লকে মেলানো)।

প্রমাণের ভুল ধরুন: “symmetric + transitive ⇒ reflexive”

একজন লিখলেন: “R symmetric আর transitive হলে reflexive-ও। প্রমাণ: যেকোনো a নিন। a R b হলে symmetric ধর্মে b R a. এখন a R b আর b R a থেকে transitive ধর্মে a R a. তাই R reflexive, আর সংজ্ঞা থেকে reflexive শর্তটি বাদ দেওয়া যায়।”

ভুল কোথায়: প্রমাণটি ধরে নিয়েছে যে প্রতিটি a-এর জন্য এমন কোনো b আছে যাতে a R b. সেই b না থাকলে symmetric আর transitive শর্ত দুটি “যদি … তবে” বলে কিছুই দাবি করে না, আর a R a প্রমাণ হয় না। সবচেয়ে ছোট পাল্টা-উদাহরণ: A = {1}-এ খালি relation ∅, যা শূন্যভাবে (vacuously) symmetric আর transitive, কিন্তু 1 R 1 নয়। §১-এর সারণির “ab > 0” আরেকটি: 0-এর কোনো সঙ্গী নেই। সঠিক কথা: symmetric আর transitive R-এ “যার অন্তত একটি সঙ্গী আছে” এমন প্রতিটি a-এর জন্য a R a. নিচের ব্লক ছোট সেটে এমন relation সব গুনে দেখায় যে তারা আসলে বিরল নয়।

from itertools import product
from math import comb

def props(n, R):
    refl = all((a, a) in R for a in range(n))
    sym = all((b, a) in R for a, b in R)
    trans = all((a, d) in R for a, b in R for c, d in R if b == c)
    return refl, sym, trans

bell = [1]
for m in range(5):                    # B(m+1) = sum C(m, k) B(k)
    bell.append(sum(comb(m, k) * bell[k] for k in range(m + 1)))

for n in range(1, 5):
    cells = [(a, b) for a in range(n) for b in range(a, n)]
    st = not_refl = 0                 # symmetric: choose cells with a <= b
    example = None
    for bits in product((0, 1), repeat=len(cells)):
        R = set()
        for (a, b), x in zip(cells, bits):
            if x:
                R |= {(a, b), (b, a)}
        refl, sym, trans = props(n, R)
        if sym and trans:
            st += 1
            if not refl:
                not_refl += 1
                if example is None or len(R) > len(example):
                    example = R
    print(f"n={n}: symmetric+transitive {st:2} (Bell(n+1) = {bell[n + 1]:2}),"
          f" not reflexive {not_refl:2}")
print("largest counterexample for n=4:", sorted(example))

n=1: symmetric+transitive  2 (Bell(n+1) =  2), not reflexive  1
n=2: symmetric+transitive  5 (Bell(n+1) =  5), not reflexive  3
n=3: symmetric+transitive 15 (Bell(n+1) = 15), not reflexive 10
n=4: symmetric+transitive 52 (Bell(n+1) = 52), not reflexive 37
largest counterexample for n=4: [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

১০ · AI-এর যুগে — equivalence-এর প্রমাণ আর গণনা যাচাই

Relation-এর প্রশ্নে AI সহকারী প্রায়ই সংজ্ঞা নির্ভুল লেখে, কিন্তু প্রয়োগে আত্মবিশ্বাসী ভুল করে। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

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

• তিনটি ধর্মের প্রতিটির আলাদা প্রমাণ আছে, আর reflexive অংশটি “প্রতিটি a”-এর জন্য
• প্রতিটি cancel বা ভাগের পাশে শূন্য নয় এমন শর্ত লেখা আছে
• ছোট একটি সসীম অংশে brute force দিয়ে তিনটি ধর্ম পরীক্ষা করেছি
• গণনার উত্তর n = 3 বা 4-এ সব relation তালিকা করে মিলিয়েছি
• Quotient-এর অপারেশনে একই class-এর দুটি প্রতিনিধি বসিয়ে দেখেছি
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

Equivalence-এর প্রশ্নের সুবিধা হলো সসীম অংশে সবকিছু পরীক্ষা করা যায়: ৫ বা ৬টি উপাদানে তিনটি ধর্ম এক মুহূর্তে যাচাই হয়। প্রমাণ সাধারণ ক্ষেত্রে কাজ করে কি না, তা ছোট ক্ষেত্রের পরীক্ষা বলতে পারে না; কিন্তু ভুল প্রমাণ সাধারণত ছোট ক্ষেত্রেই ধরা পড়ে। তাই আগে পাল্টা-উদাহরণ খুঁজুন, তারপর প্রমাণে ভরসা করুন।