Partial order, Hasse diagram, topological sort আর lattice

১ · ক্রম কী — partial order আর poset

পর্ব ৫২ “Relation আর তার ধর্ম — reflexive, symmetric, transitive”-এ relation দেখেছেন একটি সেট হিসেবে: R ⊆ A × A, অর্থাৎ পর্ব ১৪-এর Cartesian product-এর একটি subset. পর্ব ৫৫ “Equivalence relation আর partition”-এ reflexive, symmetric আর transitive relation বস্তুগুলোকে “একই রকম” দলে ভাগ করেছে। এই পর্বে symmetric-এর জায়গায় উল্টো ধর্মটি বসবে, আর তাতে পাওয়া যাবে “আগে-পরে” বা “ছোট-বড়”-র গণিত।

খেয়াল করুন, antisymmetric মানে “symmetric নয়” নয়। Antisymmetric বলে দুটি আলাদা উপাদান একে অন্যের দিকে দুই দিক থেকে যুক্ত হতে পারে না; কোনো relation একসঙ্গে symmetric আর antisymmetric দুটিই হতে পারে (যেমন শুধু সমতা, {(a, a)}), আবার দুটির কোনোটিই না-ও হতে পারে। তিনটি মূল উদাহরণ:

• (ℤ, ≤): সাধারণ ছোট-বড়। একমাত্র “পূর্ণ” উদাহরণ এই তালিকায়: যেকোনো দুটি সংখ্যা তুলনীয়।
• (ℤ⁺, ∣): a ∣ b মানে a, b-কে ভাগ করে। 2 ∣ 6, কিন্তু 4 আর 6-এর কেউ কাউকে ভাগ করে না।
• (P(S), ⊆): একটি সেটের power set, subset সম্পর্ক নিয়ে। {a} আর {b} তুলনীয় নয়।

1. Reflexive: a = 1 · a, তাই a ∣ a. — বিভাজ্যতার সংজ্ঞা
2. Antisymmetric: a ∣ b আর b ∣ a হলে b = ka, a = lb কোনো ধনাত্মক পূর্ণসংখ্যা k, l-এর জন্য। তাই a = lka, অর্থাৎ lk = 1, আর ধনাত্মক পূর্ণসংখ্যায় তা কেবল l = k = 1-এ হয়; তাই a = b. — a > 0 দিয়ে ভাগ
3. Transitive: b = ka আর c = lb হলে c = (lk)a, তাই a ∣ c. ∎ — গুণের সংযোজন

ধাপ ২-এ “ধনাত্মক” শর্তটি জরুরি। পুরো ℤ-এ 2 ∣ −2 আর −2 ∣ 2, অথচ 2 ≠ −2; তাই ℤ-এ ∣ antisymmetric নয়, partial order-ও নয়। একটি উপপাদ্যের শর্ত বাদ দিলে কী হয়, তার এটি ছোট কিন্তু সুন্দর উদাহরণ।

আরেকটি প্রশ্ন: ≤-এর বদলে < নিলে কী হয়? < reflexive নয় (3 < 3 মিথ্যা), তাই partial order নয়। এমন irreflexive, transitive relation-কে বলে strict order, আর দুটি ধারণা পরস্পরে বদলানো যায়: a ≺ b মানে a ≼ b আর a ≠ b, উল্টো দিকে a ≼ b মানে a ≺ b বা a = b. এই পর্বে ≼ বলতে সবসময় reflexive রূপটি বোঝাবে।

২ · তুলনীয়তা, total order আর lexicographic order

(ℤ, ≤) total; (ℤ⁺, ∣) আর (P(S), ⊆) total নয় (|S| ≥ 2 হলে)। কয়েকটি ছোট সেটে কতগুলো partial order আর কতগুলো total order আছে, scratch-এ সব relation পরীক্ষা করে গোনা হয়েছে: n = 1, 2, 3, 4 উপাদানে partial order যথাক্রমে 1, 3, 19, 219টি, আর total order 1, 2, 6, 24টি, অর্থাৎ n!. Total order মানে একটি সারি, আর n-টি উপাদানের সারি n!টি।

Total order বানানোর একটি স্বাভাবিক উপায় অভিধানের ক্রম। পর্ব ৩৬ “Permutation আর combination তৈরি — lexicographic order আর backtracking”-এ এই ক্রমে permutation তৈরি করেছেন; এখানে তার গাণিতিক ভিত।

1. Reflexive: a = a আর b ≼₂ b, তাই (a, b) ≼ (a, b). — দ্বিতীয় শর্ত
2. Antisymmetric: ধরুন (a, b) ≼ (a′, b′) আর (a′, b′) ≼ (a, b). যদি a ≠ a′ হতো, তাহলে দুই দিক থেকে a ≺₁ a′ আর a′ ≺₁ a, আর transitivity দিয়ে a ≺₁ a, যা অসম্ভব। তাই a = a′, আর তখন b ≼₂ b′, b′ ≼₂ b থেকে b = b′. — ≼₁, ≼₂-এর antisymmetry
3. Transitive: (a, b) ≼ (a′, b′) ≼ (a″, b″). প্রথম স্থানাঙ্কে a ≼₁ a′ ≼₁ a″. কোথাও কঠোরভাবে ছোট হলে a ≺₁ a″; দুই জায়গাতেই সমান হলে a = a″ আর b ≼₂ b′ ≼₂ b″. — ঘটনা ভাগ, পর্ব ৯
4. Total: দুই জোড়ার প্রথম স্থানাঙ্ক আলাদা হলে ≼₁ total বলে একটি ছোট; সমান হলে ≼₂ total বলে দ্বিতীয় স্থানাঙ্ক তুলনীয়। ∎ — total-এর সংজ্ঞা

উদাহরণ: ℤ × ℤ-এ (3, 9) ≺ (4, 1), কারণ প্রথম স্থানাঙ্কে 3 < 4, দ্বিতীয়টি দেখাই লাগে না; আর (4, 1) ≺ (4, 7). String-এ একই নিয়ম অক্ষর ধরে ধরে চলে, আর একটি string অন্যটির শুরুর অংশ হলে ছোটটি আগে: “bat” ≺ “bath” ≺ “bed”. বাজারঘরের অর্ডার-তালিকায় (তারিখ, অর্ডার নম্বর) জোড়া এই ক্রমে সাজালে আগে তারিখ, একই তারিখে অর্ডার নম্বর অনুযায়ী সারি হয়।

৩ · Hasse diagram — শুধু “ঠিক ওপরের” সম্পর্ক

একটি poset-কে পর্ব ১৯-এর zero-one matrix বা একটি directed graph হিসেবে আঁকা যায়, কিন্তু তাতে অনেক অপ্রয়োজনীয় রেখা থাকে। ৬০-এর উৎপাদকে ১২টি উপাদান, আর a ∣ b এমন জোড়া ৫৪টি, যার ১২টি loop (a ∣ a). বাকি ৪২টির বেশিরভাগ transitivity থেকে আপনিই বোঝা যায়: 2 ∣ 4 আর 4 ∣ 12 জানলে 2 ∣ 12 আঁকার দরকার নেই।

Hasse diagram থেকে পুরো order ফিরে পাওয়া যায়: a ≼ b ঠিক তখন, যখন a থেকে রেখা ধরে শুধু ওপরের দিকে উঠে b-তে পৌঁছানো যায় (শূন্য ধাপও চলে)। এর কারণ, সসীম poset-এ a ≺ b হলে a আর b-এর মাঝে একটি দীর্ঘতম chain নিলে তার পাশাপাশি প্রতিটি জোড়া একটি cover. অর্থাৎ ≼ হলো cover relation-এর reflexive-transitive closure, যা পর্ব ৫৪ “Relation-এর closure আর Warshall-এর algorithm”-এর ভাষা।

Hasse diagram বানানোর হাতের নিয়ম তিন ধাপের: সব জোড়া লিখুন, loop মুছুন, তারপর যে জোড়া মাঝের কোনো উপাদান দিয়ে “ঘুরে” পাওয়া যায় তা মুছুন। ১২-র উৎপাদকে ধাপগুলো দেখুন।

1S = {1, 2, 3, 4, 6, 12}2সব জোড়া a ∣ b3loop মোছা41-এর ঘুরপথ মোছা5বাকি ঘুরপথ মোছা6সারিতে সাজানো

নিচের ব্লক এই কাজটি যেকোনো সসীম poset-এ করে: প্রথমে তিনটি ধর্ম সব জোড়া আর ত্রয়ীতে পরীক্ষা করে, তারপর cover জোড়া বের করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে; পরের ব্লকগুলো দ্রুত চলে।

from itertools import combinations

def divisors(n):
    return [d for d in range(1, n + 1) if n % d == 0]

def is_partial_order(X, le):
    refl = all(le(x, x) for x in X)
    anti = all(not (le(a, b) and le(b, a)) for a, b in combinations(X, 2))
    trans = all(le(a, c) for a in X for b in X for c in X
                if le(a, b) and le(b, c))
    return refl, anti, trans

def covers(X, le):          # b covers a: a < b, nothing strictly between
    return [(a, b) for a in X for b in X
            if a != b and le(a, b)
            and not any(c != a and c != b and le(a, c) and le(c, b)
                        for c in X)]

divides = lambda a, b: b % a == 0
for n in (12, 60):
    X = divisors(n)
    pairs = sum(divides(a, b) for a in X for b in X)
    E = covers(X, divides)
    print(f"n={n}: {len(X)} divisors, {pairs} pairs, "
          f"{len(E)} Hasse edges, PO={is_partial_order(X, divides)}")
print("D12 Hasse edges:", covers(divisors(12), divides))

S = [frozenset(c) for r in range(4) for c in combinations("abc", r)]
subset = lambda A, B: A <= B
print("P({a,b,c}):", len(S), "sets,", len(covers(S, subset)),
      "Hasse edges, PO =", is_partial_order(S, subset))
print("< on 1..4:", is_partial_order(range(1, 5), lambda a, b: a < b))

n=12: 6 divisors, 18 pairs, 7 Hasse edges, PO=(True, True, True)
n=60: 12 divisors, 54 pairs, 20 Hasse edges, PO=(True, True, True)
D12 Hasse edges: [(1, 2), (1, 3), (2, 4), (2, 6), (3, 6), (4, 12), (6, 12)]
P({a,b,c}): 8 sets, 12 Hasse edges, PO = (True, True, True)
< on 1..4: (False, True, True)

৪ · Maximal, minimal, greatest আর least

ক্রিকেট দলের নির্বাচনে ভাবুন: “এমন কোনো খেলোয়াড় নেই যে তার চেয়ে সব দিক থেকে ভালো” আর “সে সবার চেয়ে সব দিক থেকে ভালো” দুটি আলাদা কথা। প্রথমটি অনেকের জন্য সত্য হতে পারে, দ্বিতীয়টি বড়জোর একজনের জন্য। Poset-এ এই পার্থক্যটিই maximal আর greatest-এর পার্থক্য।

উদাহরণ: S = {2, 3, 4, 6, 9, 12}, ∣ নিয়ে। Minimal: 2 আর 3 (এদের কোনো উৎপাদক S-এ নেই)। Maximal: 9 আর 12 (এদের কোনো গুণিতক S-এ নেই)। Greatest নেই, কারণ 9 ∤ 12 আর 12 ∤ 9; least-ও নেই। কিন্তু ৬০-এর উৎপাদকে 1 least আর 60 greatest. (ℤ, ≤)-এ কোনোটিই নেই: সেট অসীম, আর প্রতিটি সংখ্যার চেয়ে বড় ও ছোট সংখ্যা আছে।

1. ধরুন g আর g′ দুটিই greatest. g greatest বলে g′ ≼ g; g′ greatest বলে g ≼ g′. — সংজ্ঞা ৪.১
2. Antisymmetry থেকে g = g′; তাই greatest অনন্য। — partial order-এর ধর্ম
3. g maximal: g ≺ b হলে b ≼ g-ও সত্য (g greatest), তাই antisymmetry দিয়ে b = g, যা g ≺ b-এর বিরোধী। — contradiction, পর্ব ৮
4. অন্য কোনো maximal m থাকলে m ≼ g; m maximal বলে m ≺ g হতে পারে না, তাই m = g. ∎ — maximal-এর সংজ্ঞা

1. যেকোনো a₁ ∈ S নিন। a₁ minimal হলে শেষ; না হলে কোনো a₂ ≺ a₁ আছে। — minimal-এর সংজ্ঞার নেতিবাচক রূপ
2. এভাবে চালালে … ≺ a₃ ≺ a₂ ≺ a₁ পাওয়া যায়। Transitivity দিয়ে i > j হলে a_i ≺ a_j, তাই সব a_i আলাদা (সমান হলে a ≺ a, যা antisymmetry আর ≠-এর বিরোধী)। — transitivity
3. S-এ মাত্র |S|-টি উপাদান, তাই এই শিকল |S| ধাপের মধ্যে থামে, আর যেখানে থামে সেটি minimal. ∎ — pigeonhole, পর্ব ৩২

“সসীম” শর্তটি বাদ দেওয়া যায় না: (ℤ, ≤)-এ কোনো minimal নেই। আর আরেকটি সূক্ষ্ম কথা: সসীম poset-এ maximal উপাদান একটিই থাকলে তা greatest (প্রমাণ: যেকোনো b থেকে ওপরে উঠতে থাকলে উপপাদ্য ৪.৩-এর মতো কোনো maximal-এ থামে, আর সেটি একমাত্রটি)। অসীম poset-এ এই শেষ কথাটি মিথ্যা হতে পারে, যা §৯-এর ভুল-ধরা প্রশ্নের বিষয়।

৫ · Well-ordered সেট — অসীম নিচে নামা যায় না

(ℕ, ≤) well-ordered, আর এটিই পর্ব ১১ “Strong induction আর well-ordering”-এর well-ordering principle. (ℤ, ≤) নয় (পুরো ℤ-এর least নেই), আর ধনাত্মক মূলদ সংখ্যাও নয় ({1/n}-এর least নেই)। একটি সমতুল্য রূপ: well-ordered সেটে কোনো অসীম কঠোরভাবে নামতে থাকা ধারা x₁ ≻ x₂ ≻ x₃ ≻ ⋯ নেই, কারণ এমন ধারার মানগুলোর সেটের least থাকত না।

এই কারণেই well-ordering প্রোগ্রাম থামার প্রমাণে কাজে লাগে। পর্ব ১২-এর Ackermann ফাংশনের প্রতিটি recursive call-এ যুক্তির জোড়া (m, n) ℕ × ℕ-এর lexicographic order-এ কমে। ℕ × ℕ lexicographic order-এ well-ordered: একটি অশূন্য subset T-এ প্রথম স্থানাঙ্কের least m₀ নিন (ℕ well-ordered), তারপর m₀ দিয়ে শুরু হওয়া জোড়াগুলোর দ্বিতীয় স্থানাঙ্কের least n₀; (m₀, n₀) T-এর least. তাই কমতে থাকা call-ধারা অসীম হতে পারে না, আর ফাংশনটি সবসময় থামে।

৬ · Topological sort — প্রতিটি সসীম poset-কে একটি সারিতে সাজানো

বাজারঘরের ছয়টি কাজে ফিরি: A অর্ডার গ্রহণ, B পেমেন্ট যাচাই, C স্টক যাচাই, D ইনভয়েস, E প্যাকিং, F ডেলিভারি। নির্ভরতা: A → B, A → C, B → D, B → E, C → E, D → F, E → F, যেখানে u → v মানে “v-র আগে u”. একজন কর্মী একবারে একটি কাজ করেন; তাকে এমন একটি সারি দিতে হবে যা সব নির্ভরতা মানে। এই নির্ভরতার reflexive-transitive closure একটি partial order, আর প্রশ্নটি হলো এটিকে বাড়িয়ে একটি total order বানানো।

1. |S|-এর ওপর induction. |S| = 1 হলে একমাত্র উপাদানটিই সারি। — basis, পর্ব ১০
2. |S| = n + 1 হলে উপপাদ্য ৪.৩ দিয়ে একটি minimal উপাদান m নিন, আর তাকে সারির প্রথমে বসান। — সসীম poset-এ minimal আছে
3. S − {m}, একই ≼ নিয়ে, একটি n-উপাদানের poset (তিনটি ধর্ম subset-এ বজায় থাকে)। Induction hypothesis দিয়ে এর একটি linear extension b₁, …, b_n আছে; সারি m, b₁, …, b_n. — inductive hypothesis
4. এই সারি ≼ মানে কি? b_i ≼ b_j জোড়াগুলো hypothesis-এ মানা হয়েছে। m-যুক্ত জোড়ায় b ≼ m হতে পারে শুধু b = m হলে, কারণ m minimal; তাই m-এর আগে কারও আসার দরকার নেই, আর m ≼ b-গুলো m প্রথমে বলে মানা হয়। ∎ — minimal-এর সংজ্ঞা

এই প্রমাণই একটি algorithm: বারবার একটি minimal উপাদান তুলে নিন। Graph-এর ভাষায় নির্ভরতার রেখাগুলো একটি DAG (directed acyclic graph), minimal উপাদান মানে যে vertex-এ কোনো রেখা ঢোকে না (in-degree 0). A. B. Kahn ১৯৬২ সালে এই পদ্ধতি প্রকাশ করেন বলে সাধারণত উল্লেখ করা হয়; তাই এর নাম Kahn-এর algorithm. প্রতিটি vertex-এর in-degree গুনে রাখুন; in-degree 0 এমনগুলো একটি “প্রস্তুত” তালিকায়; প্রতিবার একটি বের করে সারিতে লিখুন আর তার পরের vertex-গুলোর in-degree এক কমান। এখানে প্রস্তুত তালিকা থেকে বর্ণক্রমে সবচেয়ে ছোটটি নেওয়া হলো।

1in-degree গোনা2A নেওয়া3B নেওয়া4C নেওয়া5D নেওয়া6E নেওয়া7F নেওয়া

1. Invariant: যেকোনো মুহূর্তে একটি vertex-এর রাখা in-degree = এখনো বের না হওয়া vertex থেকে তাতে ঢোকা রেখার সংখ্যা। শুরুতে সত্য, আর প্রতিবার x বের হলে x থেকে বের হওয়া রেখার শেষ vertex-গুলোতে ঠিক এক করে কমে। — loop invariant, পর্ব ১৩
2. তাই x বের হওয়ার সময় তার in-degree 0, অর্থাৎ x-এ ঢোকা প্রতিটি রেখা u → x-এর u আগেই বেরিয়েছে: ক্রমটি প্রতিটি নির্ভরতা মানে। — invariant থেকে
3. Cycle থাকলে তার কোনো vertex প্রথম বের হতে পারে না: cycle-এ তার আগের vertex তখনো ভেতরে, তাই in-degree অন্তত 1. তাই cycle-এর কোনো vertex বের হয় না, আর মোট বের হয় n-এর কম। — contradiction
4. Cycle না থাকলে, ধরুন algorithm কিছু vertex বাকি রেখে থামল। বাকিগুলো একটি সসীম poset (cycle নেই বলে closure antisymmetric), তাই উপপাদ্য ৪.৩ দিয়ে একটি minimal আছে, যার বাকিদের মধ্যে কোনো পূর্বসূরি নেই, অর্থাৎ in-degree 0, তাই প্রস্তুত তালিকা খালি ছিল না, বিরোধ। ∎ — উপপাদ্য ৪.৩

প্রতিটি রেখা একবার আর প্রতিটি vertex একবার ধরা হয়, তাই adjacency list দিয়ে লিখলে কাজ O(V + E). Queue, adjacency list আর DFS-ভিত্তিক বিকল্প পদ্ধতির কোড DSA কোর্সের পর্ব ৪২ “Topological sort আর DAG”-এ আছে; এখানে আমাদের লক্ষ্য প্রমাণ। নিচের ব্লক Kahn চালায়, তারপর ৬! = 720টি সারির প্রতিটি পরীক্ষা করে মোট কয়টি বৈধ সারি আছে তা গোনে, আর একটি cycle যোগ করে দেখে algorithm তা ধরে কি না।

from itertools import permutations

tasks = {"A": "order received", "B": "payment check",
         "C": "stock check", "D": "invoice",
         "E": "packing", "F": "delivery"}
deps = [("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"),
        ("C", "E"), ("D", "F"), ("E", "F")]

def kahn(V, E):
    indeg = {v: 0 for v in V}
    for a, b in E:
        indeg[b] += 1
    ready = sorted(v for v in V if indeg[v] == 0)
    order = []
    while ready:
        x = ready.pop(0)            # smallest label first
        order.append(x)
        for a, b in E:
            if a == x:
                indeg[b] -= 1
                if indeg[b] == 0:
                    ready = sorted(ready + [b])
    return order if len(order) == len(V) else None   # None = cycle

order = kahn(tasks, deps)
print("Kahn order:", " -> ".join(order))
print("           ", " -> ".join(tasks[t] for t in order))

ok = [p for p in permutations(tasks)
      if all(p.index(a) < p.index(b) for a, b in deps)]
print("all 720 orders checked, valid:", len(ok))
for p in ok:
    print("  ", "".join(p))
print("with E -> A added:", kahn(tasks, deps + [("E", "A")]))

Kahn order: A -> B -> C -> D -> E -> F
            order received -> payment check -> stock check -> invoice -> packing -> delivery
all 720 orders checked, valid: 5
   ABCDEF
   ABCEDF
   ABDCEF
   ACBDEF
   ACBEDF
with E -> A added: None

৭ · Chain, antichain — Mirsky আর Dilworth

কাজের ভাষায়: chain হলো এমন কাজের দল যেগুলো একটির পর একটি করতেই হবে, আর antichain হলো এমন কাজের দল যেগুলো একসঙ্গে, আলাদা কর্মী দিয়ে করা যায়। বাজারঘরের ছয় কাজে A, B, E, F একটি chain (height ৪), আর {B, C} বা {D, E} একটি antichain. একটি chain আর একটি antichain-এর সাধারণ উপাদান বড়জোর একটি, কারণ দুটি সাধারণ উপাদান হলে তারা একসঙ্গে তুলনীয় আর অতুলনীয় হতো। এই সরল পর্যবেক্ষণ থেকেই দুটি সুন্দর উপপাদ্য আসে।

1. h-এর কম অসম্ভব: h আকারের একটি chain-এর প্রতিটি উপাদান আলাদা antichain-এ পড়তে হবে, কারণ একটি antichain chain-এর বড়জোর একটি উপাদান নেয়। — pigeonhole
2. প্রতিটি x-এর জন্য level(x) = x-এ শেষ হওয়া দীর্ঘতম chain-এর আকার। 1 ≤ level(x) ≤ h. — সংজ্ঞা
3. A_k = {x : level(x) = k} নিন। x ≺ y হলে x-এ শেষ হওয়া দীর্ঘতম chain-এর পরে y যোগ করা যায়, তাই level(y) ≥ level(x) + 1 > level(x). — chain বাড়ানো
4. তাই একই level-এর দুটি উপাদান তুলনীয় হতে পারে না: প্রতিটি A_k একটি antichain, আর A₁, …, A_h মিলে S-এর একটি partition. ∎ — ধাপ ১ আর ৪ মিলিয়ে সমতা

“কম হয় না” অংশটি আগের মতোই সহজ: w আকারের antichain-এর প্রতিটি উপাদান আলাদা chain-এ পড়ে। “ঠিক w-টি chain যথেষ্ট” অংশটি কঠিনতর; Robert P. Dilworth ১৯৫০ সালে এটি প্রকাশ করেন বলে উল্লেখ করা হয়, আর Leon Mirsky ১৯৭১ সালে তার “dual” হিসেবে ওপরের সহজ উপপাদ্যটি দেন। Dilworth-এর একটি পরিচিত প্রমাণ bipartite matching দিয়ে চলে, যা পর্ব ৬৪ “Matching — bipartite graph, Hall-এর উপপাদ্য আর stable matching”-এর বিষয়; সেখানে §৫-এ König-এর উপপাদ্য থেকে পুরো প্রমাণটি দেওয়া আছে।

একটি প্রয়োগ: পর্ব ৩২-এর Erdős–Szekeres উপপাদ্য (n² + 1টি আলাদা সংখ্যার যেকোনো ধারায় দৈর্ঘ্য n + 1-এর একটি বাড়তে থাকা বা কমতে থাকা subsequence আছে) Mirsky দিয়ে দুই লাইনে আসে। অবস্থান i-তে মান x_i হলে i ≼ j বলুন যদি i ≤ j আর x_i ≤ x_j. এখানে chain মানে বাড়তে থাকা subsequence, আর antichain মানে কমতে থাকা। সবচেয়ে লম্বা বাড়তি অংশ n বা কম হলে Mirsky অনুযায়ী n² + 1টি উপাদান বড়জোর n-টি antichain-এ ভাগ হয়, তাই pigeonhole দিয়ে একটি antichain-এ অন্তত n + 1টি: দৈর্ঘ্য n + 1-এর কমতে থাকা subsequence.

নিচের ব্লক ৬০-এর উৎপাদকে Mirsky-এর level হিসাব করে, ৪০৯৬টি subset পরীক্ষা করে width বের করে, ৪টি chain-এর একটি ভাগ যাচাই করে (Dilworth-এর সংখ্যা), আর linear extension গোনে।

from itertools import combinations
from functools import lru_cache

X = [d for d in range(1, 61) if 60 % d == 0]
le = lambda a, b: b % a == 0

level = {}                 # Mirsky: longest chain ending at x
for x in X:                # X is increasing, so smaller divisors come first
    level[x] = 1 + max((level[y] for y in level if le(y, x)), default=0)
h = max(level.values())
print("height (longest chain):", h)
for k in range(1, h + 1):
    print(f"  level {k}: {[x for x in X if level[x] == k]}")

def antichain(c):
    return all(not le(a, b) and not le(b, a) for a, b in combinations(c, 2))
w = max(len(c) for r in range(1, len(X) + 1)
        for c in combinations(X, r) if antichain(c))
print("width (largest antichain), brute force over 4096 subsets:", w)

chains = [[1, 2, 4, 12, 60], [3, 6, 30], [5, 10, 20], [15]]
print("4 chains cover all:", sorted(sum(chains, [])) == X,
      "each a chain:", all(le(a, b) for c in chains for a, b in zip(c, c[1:])))

@lru_cache(None)
def linear_extensions(rest):
    if not rest:
        return 1
    return sum(linear_extensions(rest - {x}) for x in rest
               if not any(y != x and le(y, x) for y in rest))
print("linear extensions of D60:", linear_extensions(frozenset(X)))
print("linear extensions of D12:",
      linear_extensions(frozenset(d for d in X if 12 % d == 0)))

height (longest chain): 5
  level 1: [1]
  level 2: [2, 3, 5]
  level 3: [4, 6, 10, 15]
  level 4: [12, 20, 30]
  level 5: [60]
width (largest antichain), brute force over 4096 subsets: 4
4 chains cover all: True each a chain: True
linear extensions of D60: 2452
linear extensions of D12: 5

৮ · Upper bound, lub, glb আর lattice

ভাগ করা সম্পর্কে a আর b-এর upper bound মানে উভয়ের সাধারণ গুণিতক, আর lub মানে সেই সাধারণ গুণিতক যা অন্য সব সাধারণ গুণিতককে ভাগ করে। এটিই পর্ব ২১-এর lcm; একইভাবে glb হলো gcd. খেয়াল করুন, এখানে “ছোট” মানে ≤ নয়, ∣. ৬০-এর উৎপাদকে কয়েকটি জোড়া দেখুন।

14 আর 6: upper bound24 আর 6: lower bound310 আর 1244 আর 5520 আর 306সাধারণ নিয়ম

1. a, b ∈ D_n হলে a ∣ n আর b ∣ n, তাই n একটি সাধারণ গুণিতক, আর lcm(a, b) ∣ n; অর্থাৎ lcm(a, b) ∈ D_n. — lcm প্রতিটি সাধারণ গুণিতককে ভাগ করে, পর্ব ২১
2. lcm(a, b) একটি upper bound, আর যেকোনো upper bound u (a ∣ u, b ∣ u) হলে lcm(a, b) ∣ u. তাই এটি upper bound-গুলোর least. — lub-এর সংজ্ঞা
3. gcd(a, b) ∣ a ∣ n, তাই gcd ∈ D_n; আর যেকোনো সাধারণ উৎপাদক c-এর জন্য c ∣ gcd(a, b). তাই gcd হলো glb. ∎ — Bézout-ভিত্তিক gcd-এর ধর্ম, পর্ব ২১

আরেকটি মৌলিক উদাহরণ (P(S), ⊆): A ∨ B = A ∪ B আর A ∧ B = A ∩ B, কারণ A আর B দুটিকেই ধারণ করে এমন সবচেয়ে ছোট সেট A ∪ B (পর্ব ১৫)। (ℤ, ≤)-ও lattice, max আর min নিয়ে; প্রতিটি total order-ই lattice.

Lattice নয় এমন উদাহরণ: S = {1, 2, 3, 12, 18, 36}, ∣ নিয়ে। 2 আর 3-এর upper bound 12, 18, 36; কিন্তু 12 আর 18 কেউ কাউকে ভাগ করে না, তাই upper bound-গুলোর least নেই, অর্থাৎ lub(2, 3) নেই। (S-এ 6 থাকলে তা-ই হতো lub.) একইভাবে 12 আর 18-এর lower bound 1, 2, 3, যাদের greatest নেই। নিচের ব্লক সব জোড়া পরীক্ষা করে এটি নিশ্চিত করে, আর D_n-এ lub আর glb যে সত্যিই lcm আর gcd, তা-ও মেলায়।

from math import gcd

def least(cands, le):       # the element below all others, or None
    best = [c for c in cands if all(le(c, d) for d in cands)]
    return best[0] if best else None

def lattice_report(X, name):
    le = lambda a, b: b % a == 0
    ge = lambda a, b: a % b == 0
    bad = []
    for i, a in enumerate(X):
        for b in X[i + 1:]:
            ub = [c for c in X if le(a, c) and le(b, c)]
            lb = [c for c in X if le(c, a) and le(c, b)]
            lub, glb = least(ub, le), least(lb, ge)
            if lub is None or glb is None:
                bad.append((a, b, ub, lb))
            elif lub != a * b // gcd(a, b) or glb != gcd(a, b):
                bad.append((a, b, "differs from lcm/gcd"))
    print(f"{name}: {len(X)} elements, lattice = {not bad}")
    for row in bad[:3]:
        print("   no lub or glb:", row)

D60 = [d for d in range(1, 61) if 60 % d == 0]
lattice_report(D60, "D60")
lattice_report([1, 2, 3, 12, 18, 36], "S")
for n in (12, 36, 210):
    lattice_report([d for d in range(1, n + 1) if n % d == 0], f"D{n}")

D60: 12 elements, lattice = True
S: 6 elements, lattice = False
   no lub or glb: (2, 3, [12, 18, 36], [1])
   no lub or glb: (12, 18, [36], [1, 2, 3])
D12: 6 elements, lattice = True
D36: 9 elements, lattice = True
D210: 16 elements, lattice = True

শেষ পর্যবেক্ষণটি একটি বড় ধারণার দরজা। n squarefree হলে (কোনো মৌলিকের বর্গ n-কে ভাগ করে না) D_n আর P(মৌলিক উৎপাদকের সেট) একই গঠনের: D₃₀-এর Hasse diagram P({a, b, c})-এর মতো একটি ঘনক, আর দুটিরই linear extension ৪৮টি (scratch-এ গোনা)। এমন lattice-এ প্রতিটি উপাদানের একটি “পরিপূরক” আছে (30-এ 2-এর পরিপূরক 15), আর এই গঠনই Boolean algebra. পর্ব ৬৯ “Boolean algebra-র গণিত — function, identity আর minimization”-এ এই গঠন বীজগণিত হিসেবে আসবে।

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

অঙ্ক ১. S = {1, 2, 3, 4, 5, 6, 8, 12}, ∣ নিয়ে। Maximal, minimal, greatest, least বের করুন, আর {2, 3}-এর lub খুঁজুন। সমাধান: minimal শুধু 1, আর 1 সবাইকে ভাগ করে, তাই least 1. Maximal: 5, 8, 12 (এদের কোনো গুণিতক S-এ নেই)। তিনটি maximal, তাই greatest নেই (উপপাদ্য ৪.২)। {2, 3}-এর upper bound 6, 12; 6 ∣ 12, তাই lub 6.

অঙ্ক ২. P({a, b, c})-এর Hasse diagram-এ কয়টি রেখা, height আর width কত? সমাধান: প্রতিটি সেট থেকে একটি অনুপস্থিত অক্ষর যোগ করলে cover; ৮টি সেটে মোট অনুপস্থিত অক্ষর 3 · 4 = 12 (প্রতিটি অক্ষর ৪টি সেটে নেই), তাই ১২টি রেখা। Height ৪ (∅ ⊂ {a} ⊂ {a, b} ⊂ {a, b, c}); width ৩ ({a}, {b}, {c}), আর Mirsky-এর ৪টি antichain হলো আকার অনুযায়ী সারি: ১, ৩, ৩, ১।

অঙ্ক ৩. ℤ × ℤ-এর lexicographic order-এ (2, 5), (1, 9) আর (2, −1)-কে ছোট থেকে বড় সাজান। সমাধান: (1, 9) ≺ (2, −1) ≺ (2, 5); প্রথম স্থানাঙ্ক আগে দেখা হয়, তাই 9 বড় হলেও (1, 9) সবার আগে।

ভুল প্রমাণ ধরুন। দাবি: “যে poset-এ ঠিক একটি maximal উপাদান m, সেখানে m greatest.” প্রমাণ: “যেকোনো b নিন। b = m হলে শেষ। না হলে b maximal নয় (maximal একটিই), তাই b ≺ b₁ কোনো b₁-এর জন্য। b₁ = m হলে শেষ, না হলে b₁ ≺ b₂, এভাবে চলতে থাকে, আর শেষে m-এ পৌঁছায়। তাই b ≼ m.”

ভুল কোথায়: “শেষে m-এ পৌঁছায়” কথাটির কোনো যুক্তি নেই; শিকলটি অসীম হতে পারে। Counterexample: S = ℕ ∪ {m}, যেখানে ℕ-এ সাধারণ ≤ আর m কোনো সংখ্যার সঙ্গে তুলনীয় নয়। ℕ-এ কোনো maximal নেই (প্রতিটির পরে বড় সংখ্যা), তাই m একমাত্র maximal; কিন্তু 0 ⋠ m, তাই m greatest নয়। প্রমাণটি সঠিক হয় S সসীম হলে, কারণ তখন উপপাদ্য ৪.৩-এর মতো শিকল |S| ধাপের মধ্যে থামে। এটি একটি পরিচিত ধাঁচ: অসীম সেটে “এভাবে চলতে থাকলে শেষে” কথাটি well-ordering বা finiteness ছাড়া অর্থহীন।

১০ · AI-এর যুগে — ক্রম আর lattice-এর উত্তর যাচাই

Partial order-এর প্রশ্নে AI সহকারী প্রায়ই সংজ্ঞা ঠিক বলে, কিন্তু উদাহরণে ভুল করে, আর তা আত্মবিশ্বাসী ভাষায় আসে। কয়েকটি নিয়মিত ভুল:

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

• তিনটি ধর্ম ছোট উদাহরণে নিজে বা brute force দিয়ে পরীক্ষা করেছি
• Hasse diagram-এর প্রতিটি রেখা সত্যিই cover কি না দেখেছি
• Greatest বা least দাবি সব উপাদানের সঙ্গে মিলিয়েছি
• lub আর glb-এ “সংখ্যায় বড়” নয়, poset-এর ক্রম ব্যবহার হয়েছে কি না দেখেছি
• ব্যবহৃত প্রতিটি উপপাদ্যের শর্ত (বিশেষ করে সসীমতা) প্রশ্নে খাটে কি না দেখেছি
• নাম, সাল আর উৎস বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

Poset-এর প্রায় প্রতিটি দাবি ছোট উদাহরণে যন্ত্রের মতো যাচাই করা যায়: সব জোড়া, সব ত্রয়ী, সব subset, সব permutation. এই পর্বের চারটি ছোট Python ব্লকে প্রায় সব সংজ্ঞা এভাবেই পরীক্ষা হয়েছে। AI-এর উত্তরকে তালিকায় ভেঙে নিন, আর একটি স্বাধীন brute force চালিয়ে মিলিয়ে তবেই ভরসা করুন।