Category theory के चित्रों से समझा गया order

• जब किसी element set पर एक binary relation reflexivity·transitivity·antisymmetry जैसे नियमों को संतुष्ट करती है, तब एक order structure बनती है
• Linear order वह संरचना है जिसमें हर दो elements आपस में comparable होते हैं, और totality को हटाने पर partial order मिलता है
• Partial order में chain, greatest element·least element, join·meet, और Hasse diagram के ज़रिए संरचना को समझा जा सकता है
• Color mixing, divisibility, और set inclusion partial order के उदाहरण हैं, और जब join तथा meet दोनों मौजूद हों तो lattice बनती है
• Preorder वह संरचना है जिसमें केवल reflexivity और transitivity होती है, और हर preorder को ऐसे category के रूप में समझा जा सकता है जिसमें किसी भी दो objects के बीच अधिकतम एक ही morphism हो

---

Order

• Order एक element set और उस पर परिभाषित binary relation से मिलकर बनता है, और जब यह कुछ निश्चित नियमों को पूरा करे तब एक गणितीय संरचना बनती है
  • Order का मापदंड क्या है, इससे अधिक महत्वपूर्ण यह है कि elements के बीच का relation कौन-से गुण रखता है
  • Binary relation किसी set के दो elements के बीच का संबंध है, और इसे arrow से भी दिखाया जा सकता है
• Set theory में order को मूल set के अपने ही Cartesian product के subset के रूप में, और programming में दो objects की तुलना करने वाले function के रूप में व्यक्त किया जा सकता है
  • लेकिन हर comparison function या element-pairs का set order को define नहीं करता; शुरुआती arrangement से स्वतंत्र होकर सुसंगत परिणाम देने के लिए कुछ नियम ज़रूरी होते हैं

Linear order

• Linear order** ऐसा order है जिसमें सभी elements एक-दूसरे के सापेक्ष किसी न किसी स्थान पर होते हैं, और कौन-सा element किससे पहले है यह**अस्पष्ट नहीं होता

  • उदाहरण के रूप में प्रकाश की wavelength या rainbow में रंगों के क्रम का उल्लेख किया गया है
  • Linear order को ऐसी binary relation के रूप में define किया जाता है जो reflexivity, transitivity, antisymmetry, और totality को संतुष्ट करे
  • यही चार नियम order relation बनने की शर्त हैं

• Reflexivity

  • हर element अपने ही बराबर या उससे बड़ा होना चाहिए, अर्थात हर $a$ के लिए $a \le a$ सत्य है
  • यह base case को संभालने वाला नियम है; इसके विपरीत यदि किसी element को स्वयं से related न माना जाए, तो strict order जैसा अलग प्रकार बनता है

• Transitivity

  • यदि $a \le b$ और $b \le c$ हो, तो $a \le c$ भी होना चाहिए
  • यह order का एक केंद्रीय नियम है

• Antisymmetry

  • यह विरोधाभासी comparison को रोकने वाला नियम है; यदि $x \le y$ और $y \le x$ हो, तो यह केवल $x = y$ होने पर ही स्वीकार्य है
  • इसे इस तरह भी कहा गया है कि अलग-अलग elements के बीच tie स्वीकार्य नहीं है

• Totality

  • हर दो elements का comparable होना अनिवार्य है, अर्थात किसी भी दो elements के लिए $a \le b \lor b \le a$ सत्य होगा
  • यानी किसी भी दो elements में एक न एक दूसरे से बड़ा या बराबर होगा
  • Totality में $a$ और $b$ के समान होने की स्थिति भी शामिल है, इसलिए reflexivity इसका special case बन जाती है
  • Totality हटाने पर partial order मिलता है, और linear order को total order भी कहा जाता है

• Natural numbers का order

  • Natural numbers, greater than or equal to relation के तहत linear order बनाते हैं
  • हर finite linear order, पहले element को 1, दूसरे को 2 आदि से मिलाकर natural numbers के किसी subset के साथ isomorphic होता है
  • इसलिए समान आकार वाले सभी finite linear orders आपस में isomorphic होते हैं
  • Category theory के नज़रिए से यह भी कहा गया है कि सभी finite linear orders और अधिकांश infinite linear orders के diagrams एक जैसे दिखते हैं

Partial order

• Partial order linear order से totality हटाकर मिलने वाली संरचना है, जिसमें केवल reflexivity, transitivity, और antisymmetry बचते हैं
  • इसे partially-ordered set, या poset, भी कहा जाता है
• हर linear order, partial order है, लेकिन हर partial order linear order नहीं होता
• Partial order का संबंध equivalence relation से भी है; यह वह संरचना है जिसमें equivalence relation की symmetry की जगह antisymmetry आती है
• Football skill comparison के उदाहरण में, यदि कुछ लोगों की तुलना सीधे या परोक्ष रूप से की जा सके तो linear order बन सकता है; लेकिन यदि ऐसे लोग भी हों जिन्होंने कभी एक-दूसरे के खिलाफ खेला ही न हो, तो non-linear structure बनती है और partial order बनता है
  • Partial order हमेशा यह तय नहीं कर पाता कि कौन बेहतर है

• Chain

  • Partial order कई linear subsets से बना हो सकता है, और ऐसे linear subset को chain कहा जाता है
  • उदाहरण के रूप में $m \to g \to f$ और $d \to o$ दो chains दी गई हैं
  • Chains का पूरी तरह अलग-अलग होना ज़रूरी नहीं; जब तक सभी connections एक-से-एक जुड़कर एक ही chain न बन जाएँ, partial order बना रहता है
  • उदाहरण में $d \le g$ और $f \le g$ पता है, लेकिन $d$ और $f$ के बीच relation अनिश्चित है

• Greatest element और least element

  • यदि कोई element $a$ हर दूसरे element $x$ के लिए $x \le a$ को संतुष्ट करे, तो वह greatest element है
  • कुछ partial orders में ऐसा element होता है; उदाहरण diagram में $m$ greatest element है
  • यदि कई elements बाकी सब से बड़े हों लेकिन आपस में समान न हों, तो greatest element मौजूद नहीं माना जाएगा
  • इसी तरह least element define किया जाता है

• Join

  • जुड़े हुए दो elements के least upper bound को join कहा जाता है
  • इसकी दो शर्तें हैं
    • $A \le G$ और $B \le G$ होना चाहिए
    • और किसी भी ऐसे element $P$ के लिए जो $A$ और $B$ दोनों से बड़ा हो, $G \le P$ होना चाहिए
  • यदि एक element दूसरे से बड़ा हो, तो join वही बड़ा element होता है
  • Linear order में किसी भी दो elements का join बस बड़ा element होता है
  • यदि समान स्तर के कई upper bounds हों, तो join मौजूद नहीं होता; join unique होना चाहिए

• Meet

  • दो elements से छोटे या बराबर सभी elements में सबसे बड़े element को meet कहा जाता है
  • Join वाले ही नियम उल्टी दिशा में लागू होते हैं

• Hasse diagram

  • इस section में इस्तेमाल किए गए diagrams Hasse diagrams हैं
  • इनमें बड़ा element हमेशा ऊपर रखा जाता है
  • यदि arrow हो, तो arrow जिस बिंदु की ओर जाता है वह हमेशा ऊपर होगा
  • इस arrangement से केवल ऊपर-नीचे देखकर तुलना की जा सकती है, और join भी उन common connected elements में सबसे नीचे वाले को ढूँढकर पहचाना जा सकता है

• Color-mixing partial order

  • एक color-mixing partial order दिया गया है, जिसमें हर रंग उस रंग की ओर जाता है जिसमें वह शामिल है
  • किसी भी दो रंगों का join वह रंग है जो उन्हें मिलाने पर बनता है

• Divisibility के अनुसार संख्याओं का partial order

  • यदि संख्याओं को आकार से नहीं बल्कि divisibility से व्यवस्थित किया जाए, तो partial order बनता है
  • यदि $a$, $b$ को divide करता है, तो $a$, $b$ से पहले माना जाता है
  • उदाहरण के लिए $2 \times 5 = 10$ होने से 2 और 5, 10 से पहले हैं, लेकिन 3, 10 से पहले नहीं है
  • इस order में join LCM है और meet GCD

• Inclusion partial order

  • यदि कई sets में कुछ common elements शामिल हों, तो inclusion order define किया जा सकता है
  • यदि set $a$, $b$ को include करता है, या दूसरे शब्दों में $b$, $a$ का subset है, तो $a$, $b$ से पहले आता है
  • इस स्थिति में join union है और meet intersection
  • हर set में शामिल रंगों को मिलाने पर पहले देखा गया color-mixing partial order जैसा ही structure बनता है
  • संख्याओं का divisibility order, repetition की अनुमति देने वाले prime sets या prime powers के inclusion order के साथ isomorphic है
  • यह arithmetic के fundamental theorem से स्पष्ट होता है, जिसके अनुसार हर संख्या primes के गुणनफल के रूप में ठीक एक ही तरीके से व्यक्त होती है

Birkhoff का representation theorem

• Color mixing और संख्याओं का divisibility partial order, दोनों को कुछ basic elements के संभावित set combinations पर बने inclusion order के रूप में व्यक्त किया जा सकता है
  • पहले मामले में basic elements primary colors हैं, और दूसरे में primes या prime powers
• कौन-सा finite partial order इस तरह व्यक्त किया जा सकता है, यह Birkhoff’s representation theorem बताता है
  • इसकी दो शर्तें हैं
    • हर element pair के लिए join और meet मौजूद हों
    • Join और meet एक-दूसरे के सापेक्ष distributive हों। प्रतीक $∨$, $∧$ में यह $x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)$ है
• हर वह partial order जिसमें सभी elements के लिए join और meet हों, lattice कहलाता है
• और यदि ये operations distributive हों, तो वह distributive lattice है
• Inclusion order बनाने वाले “prime-like” elements वे हैं जिन्हें दूसरे elements के join के रूप में व्यक्त नहीं किया जा सकता; इन्हें join-irreducible elements कहा जाता है
• इस theorem को इस रूप में भी कहा जा सकता है कि हर distributive lattice अपने join-irreducible elements के inclusion order के साथ isomorphic होती है
• जो partial orders distributive lattice नहीं हैं, वे भी inclusion order के साथ isomorphic हो सकते हैं, लेकिन उस स्थिति में वे ऐसे inclusion orders से मेल खाते हैं जो सभी संभावित combinations को शामिल नहीं करते

Lattice

• Lattice वह partial order है जिसमें हर दो elements के लिए join और meet मौजूद हों
  • हर lattice एक partial order है, लेकिन हर partial order lattice नहीं है
• किसी नियम से उत्पन्न कई partial orders distributive lattice होते हैं, और पिछले section के examples भी यदि पूरी तरह draw किए जाएँ तो distributive lattice बनते हैं
• Color mixing example में ऊपर एक black ball और नीचे एक white ball जोड़ी जाती है
  • ऐसा न करने पर ऊपर के तीन elements का join नहीं होगा, और नीचे के तीन elements का meet नहीं होगा

• Bounded lattice

  • जिस lattice में greatest element और least element दोनों हों, उसे bounded lattice कहा जाता है
  • Color mixing lattice में black ball greatest element है और white ball least element
  • यह भी कहा गया है कि हर finite lattice bounded होती है

Order isomorphism

• Order isomorphism दो orders के underlying sets के बीच एक invertible function होती है, जो order arrows को preserve करती है
• संख्याओं के divisibility order और prime inclusion order के उदाहरण में यह दो functions से बनती है
  • Prime inclusion order से numbers के order की ओर जाने वाला function set elements का multiplication है
  • Numbers के order से prime inclusion order की ओर जाने वाला function संख्या को product में तोड़ने वाला prime factorization है
• Order isomorphism की मुख्य शर्त यह है कि किसी भी दो elements $a$, $b$ के लिए $a \le b$ तब और केवल तब जब $F(a) \le F(b)$
• ऐसे function को order-preserving function कहा जाता है

Preorder

• Preorder वह संरचना है जो linear order से antisymmetry हटाने पर मिलती है, और जिसमें केवल reflexivity और transitivity बचते हैं
• Comparability के आधार पर देखें तो
  • Linear order में $a \le b$ या $b \le a$
  • Partial order में इनमें से एक सत्य हो सकता है, या दोनों ही असत्य हो सकते हैं
  • Preorder में इनमें से एक, दोनों असत्य, या दोनों सत्य भी संभव हैं
• Preorder रोज़मर्रा के अर्थ में order जैसा नहीं है; इसमें किसी भी बिंदु से किसी दूसरे बिंदु तक arrow जा सकता है
  • उदाहरण के रूप में football में “किसने किसे हराया” को direct या indirect wins सहित model किया गया है
• Transitivity के कारण indirect wins भी direct relation की तरह जुड़ जाती हैं, और इससे यदि cyclic relation हो तो कई objects आपस में पूरी तरह जुड़े हुए structure बना लेते हैं

• Preorder और equivalence relation

  • Preorder, partial order और equivalence relation के बीच की संरचना है
  • क्योंकि इन दोनों में फर्क करने वाला बिंदु (anti)symmetry ही है
  • Preorder के भीतर जो elements दोनों दिशाओं में जुड़े हों, वे symmetry को संतुष्ट करते हैं और equivalence relation बनाते हैं
  • ऐसे elements को समूहित करने पर preorder की equivalence classes बनती हैं
  • फिर यदि केवल इन equivalence classes के बीच के connections को लिया जाए, तो वे antisymmetry को संतुष्ट करते हैं और partial order बनाते हैं
  • इसलिए हर preorder के लिए उसकी equivalence classes पर partial order define किया जा सकता है

Preorder और category

• Preorder की transitivity वह नियम है जिसमें $a \le b$ और $b \le c$ होने पर $a \le c$ बनता है; इसे relation की composition के रूप में समझा जा सकता है
• Category की परिभाषा में निम्न दो शर्तें शामिल हैं
  • हर object के लिए identity morphism होना
  • उपयुक्त दो morphisms को compose किया जा सके, और यह composition associative हो
• Preorder में transitivity composition का काम करती है, और reflexivity identity morphism की भूमिका निभाती है
• इसलिए हर preorder एक category है
• सामान्य category में दो objects के बीच कई morphisms हो सकते हैं, लेकिन preorder में किसी भी दो objects के बीच अधिकतम एक morphism होता है
  • या तो $a \le b$ है, या नहीं है
• जैसे monoid एक object वाली category है, वैसे ही order को ऐसी category के रूप में समझा जा सकता है जिसमें किसी भी दो objects के बीच अधिकतम एक morphism हो
• इसी गुण के कारण preorder में हर diagram commutative होता है

• Partial order और preorder के categorical गुण

  • Partial order और preorder, दोनों preorder के विशेष मामले हैं, इसलिए वे category भी हैं
  • Category theory में preorder को skeletal categories के रूप में भी संदर्भित किया जाता है, जहाँ isomorphic objects अलग-अलग रहते हुए साथ मौजूद नहीं होते

• Product और coproduct

  • Category का coproduct दो morphisms $A \to A + B$, $B \to A + B$ और एक universal property से define होता है
  • यह order में join की परिभाषा के ठीक समान रूप है
  • Order में हर morphism unique होता है, इसलिए “बड़ा होना” का अर्थ “एक unique morphism का अस्तित्व” बन जाता है
  • इसलिए preorder की category में categorical coproduct, join के बराबर है
  • Duality के अनुसार product, meet के अनुरूप है

• Formal definition

  • Category theory में ऐसी categories जिनमें किसी भी दो objects के बीच अधिकतम एक morphism हो, thin categories कहलाती हैं
  • हर preorder को ऐसी thin category के रूप में देखा जा सकता है, और उल्टा भी ऐसी category को preorder की तरह समझा जा सकता है
  • Thin category, सामान्य category की तुलना में अधिक सरल संदर्भ में category की अवधारणा समझने के काम आती है
  • Meet और join को समझना, अधिक सामान्य categorical concepts जैसे product और coproduct को समझने में भी सहायक है
  • और जब objects के बीच कई morphisms के फर्क में रुचि न हो, केवल सरल संरचना चाहिए हो, तब यह एक उपयोगी ढाँचा है