পার্শিয়াল অর্ডার ও Hasse ডায়াগ্রাম

১ · পার্শিয়াল অর্ডারের সংজ্ঞা

একটি সেট $A$-এর উপর রিলেশন $\preceq$ কে পার্শিয়াল অর্ডার (Partial Order)Partial Orderএকটি রিলেশন যা একসাথে reflexive, antisymmetric ও transitive — L08-এর তিনটি নির্দিষ্ট বৈশিষ্ট্যের সমাহার। বলা হয় যদি এটি একসাথে reflexive, antisymmetric, ও transitive হয় (L08 দেখুন)। জোড়া $(A, \preceq)$-কে তখন একটি পোসেট (Poset)Poset"Partially Ordered Set"-এর সংক্ষিপ্ত রূপ — একটি সেট $A$ ও তার উপর একটি পার্শিয়াল অর্ডার $\preceq$ একসাথে। ("Partially Ordered Set") বলা হয়। L08-এ দেখেছি "divides" ও "$\leq$" উভয়ই পার্শিয়াল অর্ডার।

দুটি উপাদান $a, b \in A$ কে comparable বলা হয় যদি $a \preceq b$ অথবা $b \preceq a$ হয়। যদি কোনোটিই সত্য না হয়, তারা incomparable। যদি একটি পোসেটে প্রতিটি জোড়া উপাদান comparable হয়, তাকে বলা হয় total order (যেমন $\leq$ পূর্ণসংখ্যায়) — কিন্তু "divides" পোসেটে $2$ ও $3$ incomparable ($2 \nmid 3$ এবং $3 \nmid 2$), তাই এটি শুধু একটি পার্শিয়াল অর্ডার, total order নয়।

২ · Hasse ডায়াগ্রাম আঁকার নিয়ম

একটি পোসেটের সব রিলেশন ($a \preceq b$-এর সব জোড়া) আঁকলে ডায়াগ্রাম অপ্রয়োজনীয়ভাবে জটিল হয়ে যায় — reflexive loop ($a \preceq a$) ও transitive এজ (যেমন $1 \preceq 4$, যা $1 \preceq 2 \preceq 4$ থেকেই বোঝা যায়) বাদ দেওয়া যায়। একটি Hasse ডায়াগ্রামHasse Diagramএকটি পোসেটের শুধু "covering" রিলেশন দেখানো ডায়াগ্রাম — reflexive loop ও transitive এজ বাদ দিয়ে, নিচ থেকে উপরের দিকে ক্রম বাড়ে এমনভাবে আঁকা। শুধু covering সম্পর্ক দেখায়: $a$, $b$-এর একটি কভার (লেখা হয় $a \prec\!\cdot b$) যদি $a \prec b$ হয় এবং এমন কোনো $c$ না থাকে যেখানে $a \prec c \prec b$ (অর্থাৎ মাঝে কিছু নেই)। নিয়ম — বড় উপাদান উপরে আঁকা হয়, ছোট নিচে; এজে কোনো তীরচিহ্ন থাকে না, কারণ "উপরের দিক" নিজেই দিক নির্দেশ করে।

৩ · Worked উদাহরণ — divisibility পোসেট

$S = \{1,2,3,4,6,12\}$ সেটের উপর "divides" রিলেশন বিবেচনা করুন। কভারিং জোড়াগুলো হলো — $1$ কভার করে $2$ ও $3$ (কারণ মাঝে কিছু নেই); $2$ কভার করে $4$ ও $6$; $3$ কভার করে $6$; এবং $4$ ও $6$ উভয়ে কভার করে $12$। লক্ষ করুন $1 \mid 4$ সত্য হলেও এজ নেই, কারণ $1 \prec 2 \prec 4$ — এটি একটি transitive সম্পর্ক, covering নয়।

S = [1, 2, 3, 4, 6, 12]

def divides(a, b):
    return b % a == 0

covers = []
for a in S:
    for b in S:
        if a != b and divides(a, b):
            has_between = any(
                c != a and c != b and divides(a, c) and divides(c, b)
                for c in S
            )
            if not has_between:
                covers.append((a, b))

print("কভারিং এজ (Hasse ডায়াগ্রামের এজ):")
for a, b in sorted(covers):
    print(f"  {a} → {b}")
print("\nমোট এজ:", len(covers))

৪ · Maximal/minimal, bounds, ও join/meet

একটি উপাদান maximal যদি তার উপরে কেউ না থাকে (কোনো $b$ নেই যেখানে $a \prec b$); minimal হলে তার বিপরীত। যদি একটি একক উপাদান সবার চেয়ে বড় হয় (বাকি সবার সাথে comparable এবং বড়), তাকে বলা হয় greatest element (এবং দ্বৈতভাবে least element)। আমাদের উদাহরণে $1$ হলো least element (সবাইকে ভাগ করে) এবং $12$ হলো greatest element (সবার দ্বারা ভাগ হয়) — তাই এই পোসেটটি "bounded"।

একটি উপসেটের upper bound এমন একটি উপাদান যা উপসেটের প্রতিটি উপাদানের চেয়ে বড় বা সমান; lower bound এর বিপরীত। সবচেয়ে ছোট upper bound-কে বলা হয় join ($\vee$, least upper bound), সবচেয়ে বড় lower bound-কে বলা হয় meet ($\wedge$, greatest lower bound)। মজার ব্যাপার — divisibility পোসেটে join আসলে LCM এবং meet আসলে GCD! যেমন $\{2,3\}$-এর join $= \text{lcm}(2,3) = 6$, $\{4,6\}$-এর meet $= \gcd(4,6) = 2$। L25-এ GCD ও LCM-এর সম্পূর্ণ আলোচনা এই একই কাঠামোর গভীরতর রূপ।