आंशिक क्रम और lattices
उद्देश्य, पूर्वज्ञान और प्रचलन
Partial order पहचानना, Hasse diagram पढ़ना, minimal और least में अंतर करना, subset के bounds निकालना और सीमित poset के lattice होने का निर्णय करना सीखें। पूर्वज्ञान: समुच्चय, फलन और relations के गुण। यह आधारभूत पाठ है, पूरा lattice theory नहीं; distributive, complemented और Boolean lattices के लिए आगे पढ़ना होगा।
Relation का underlying set प्रश्न का हिस्सा है। सभी हल किए उदाहरणों में सीमित गैर-रिक्त sets हैं। a≼b एक अमूर्त क्रम बताता है; इसका अर्थ आवश्यक रूप से संख्यात्मक a≤b नहीं। Divisibility वाले क्रम में a≼b का अर्थ a, b को विभाजित करता है, जिसे a|b लिखते हैं।
1. Partial order में तीन गुण साथ चाहिए
A पर relation ≼ partial order है यदि वह reflexive (a≼a), antisymmetric (a≼b और b≼a से a=b) तथा transitive (a≼b और b≼c से a≼c) हो। (A,≼) को partially ordered set या poset कहते हैं। Antisymmetry अलग तत्वों के बीच दोतरफ़ा क्रम रोकती है; diagonal pairs को नहीं रोकती।
a और b comparable हैं यदि a≼b या b≼a। Total order ऐसा partial order है जिसमें हर pair comparable हो। Partial order में हर pair की तुलना जरूरी नहीं। “Partial” का अर्थ अधूरी जानकारी नहीं; relation पूरी तरह ज्ञात होने पर भी कुछ तत्व incomparable हो सकते हैं।
पूर्णांकों पर सामान्य ≤ total order है। Power set पर inclusion ⊆ partial order है: a≠b हो तो {a} और {b} incomparable हैं। धनात्मक पूर्णांकों पर divisibility partial order है; 2 और 3 incomparable हैं। “धनात्मक” कहना जरूरी है: सभी गैर-शून्य signed integers लेने पर 2 और −2 एक-दूसरे को विभाजित करते हैं, लेकिन समान नहीं, इसलिए antisymmetry टूटती है।
2. Hasse diagram क्या नहीं दिखाता
सीमित poset में b, a को cover करता है यदि a≺b और उनके बीच कोई c न हो। यहाँ a≺b का अर्थ a≼b तथा a≠b है। Hasse diagram cover relations दिखाता है; प्रचलन के अनुसार बड़ा तत्व ऊपर रखते हैं। Self-loops और transitivity से मिलने वाले edges नहीं बनाते। पूरे order को समझते समय उन्हें वापस शामिल करें।
12 के धनात्मक divisors D={1,2,3,4,6,12} को divisibility से क्रम दें। इसके Hasse diagram का स्पष्ट पाठ्य विवरण है:
- सबसे नीचे: 1। सबसे ऊपर: 12।
- नीचे से ऊपर के cover pairs: (1,2), (1,3), (2,4), (2,6), (3,6), (4,12), (6,12)।
(1,12) cover pair नहीं है, फिर भी 1≼12 सत्य है: ऊपर जाते paths transitivity बताते हैं। Direct edge न होने से तत्व आवश्यक रूप से incomparable नहीं होते। इसके विपरीत, 4 से 6 या 6 से 4 का ऊपर जाता path नहीं, इसलिए वे incomparable हैं। केवल चित्र में ऊँचाई relation नहीं बनाती; paths या दी गई divisibility जाँचें।
3. Minimal और least अलग हैं
m, minimal है यदि उससे नीचे कोई अलग तत्व नहीं। वह least है यदि वह हर तत्व से नीचे या बराबर है। इसी तरह M, maximal है यदि उसके ऊपर कोई अलग तत्व नहीं; greatest है यदि हर तत्व उससे नीचे या बराबर हो। इन अर्थों को मिलाने से बचने के लिए यहाँ अंग्रेज़ी technical terms साथ रखे गए हैं।
कई minimal या maximal तत्व हो सकते हैं, लेकिन अधिकतम एक least और एक greatest तत्व। Least की uniqueness देखें: l और l′ दोनों least हों तो l≼l′ तथा l′≼l; antisymmetry से l=l′। Least तत्व minimal भी होता है; उलटी दिशा जरूरी नहीं।
हल किया उदाहरण: A={2,3,6} पर divisibility। 2 और 3 दोनों minimal हैं क्योंकि A में उनका कोई अलग divisor नहीं। Least तत्व नहीं: 2, 3 को और 3, 2 को विभाजित नहीं करता। 6, maximal और greatest दोनों है क्योंकि A का हर तत्व 6 को विभाजित करता है। Least के रूप में 1 न जोड़ें; वह A में नहीं है।
12 के सभी divisors D में least तत्व 1 और greatest तत्व 12 है। परिणाम underlying set पर निर्भर हैं, केवल relation के नाम पर नहीं।
4. Bounds, ambient poset के तत्व होते हैं
Poset A का subset S लें। S का lower bound l, A में होता है और हर s∈S के लिए l≼s पूरा करता है। Upper bound u, A में होता है और हर s∈S के लिए s≼u। Bound का स्वयं S में होना जरूरी नहीं।
Greatest lower bound या glb ऐसा lower bound है जो बाकी सभी lower bounds से ऊपर या बराबर हो। Least upper bound या lub ऐसा upper bound है जो बाकी सभी upper bounds से नीचे या बराबर हो। “Greatest lower” और “least upper” में poset का क्रम लागू होता है, labels का मनमाना संख्यात्मक आकार नहीं। इनके मौजूद होने पर antisymmetry से प्रत्येक unique होता है।
D के भीतर S={4,6} के lower bounds {1,2} हैं; glb=2। Upper bounds {12} हैं; lub=12। 2 और 12, S में नहीं हैं, और यह स्वीकार्य है। हर lower bound, greatest नहीं होता: 1 lower bound है लेकिन glb नहीं।
विपरीत उदाहरण: divisibility वाले A={1,2,3} में S={2,3} लें। glb=1 है, लेकिन A में कोई upper bound नहीं। पूर्णांक 6 common multiple है, फिर भी इस poset का bound नहीं हो सकता क्योंकि वह A का तत्व नहीं।
5. Lattice में हर pair की शर्त पूरी हो
Lattice ऐसा poset है जिसमें हर दो तत्वों का glb और lub दोनों हों। a,b के glb को meet, a∧b, और lub को join, a∨b कहते हैं। ये संकेत logical AND तथा OR जैसे दिखते हैं, लेकिन यहाँ दिए poset की operations हैं।
एक pair के लिए सफलता से पूरा poset lattice सिद्ध नहीं होता। Meet या join के बिना एक pair मिलने से उसे lattice न होना सिद्ध कर सकते हैं। Lattice का total order होना जरूरी नहीं। दूसरी ओर, हर totally ordered set lattice है: pair का छोटा तत्व meet और बड़ा तत्व join होता है।
12 के divisors D lattice हैं। दो divisors का gcd उनका meet और lcm उनका join है। दोनों 12 के divisors ही रहते हैं। 4 और 6 के लिए meet=2, join=12। 2 और 6 के लिए meet=2, join=6 क्योंकि दोनों comparable हैं।
Divisibility वाला {1,2,3} lattice नहीं: 2 और 3 का इस set में join नहीं। किसी मनमाने subset पर membership और bounds की परिभाषा जाँचे बिना gcd/lcm का shortcut न लगाएँ। एक निश्चित धनात्मक पूर्णांक के सभी धनात्मक divisors लेने पर यह shortcut सीधे काम करता है।
6. हल किया उदाहरण: power-set lattice
A={a,b} लें। इसका power set {∅,{a},{b},{a,b}} inclusion से क्रमित हो। Cover pairs हैं ∅<{a}, ∅<{b}, {a}<{a,b}, {b}<{a,b}। बीच के तत्व incomparable हैं, फिर भी हर pair का meet और join है।
A के किसी भी subsets X,Y का meet, X∩Y और join, X∪Y है। क्यों? हर common lower bound दोनों sets में शामिल होगा, इसलिए intersection में भी शामिल होगा। Intersection स्वयं common lower bound है, इसलिए greatest है। इसी तरह हर common upper bound में दोनों sets और इसलिए उनका union शामिल होगा; union सबसे छोटा ऐसा bound है।
इसलिए {a}∧{b}=∅ और {a}∨{b}={a,b}। यहाँ least तत्व ∅ और greatest तत्व A है। उदाहरण दिखाता है कि incomparable तत्वों का भी meet और join हो सकता है; केवल incomparability से lattice की शर्त गलत नहीं होती।
7. सीमित poset जाँचने की विश्वसनीय विधि
पहले underlying set और order स्पष्ट करें। Relation ordered pairs से दिया हो तो poset कहने से पहले सभी आवश्यक diagonal pairs, antisymmetry और transitivity जाँचें। Valid Hasse diagram दिया हो तो reachability जोड़कर संबंध पढ़ें, केवल बने edges को पूरा relation न मानें।
Minimal/maximal के लिए पूछें कि candidate से नीचे/ऊपर कोई अलग तत्व है या नहीं। Least/greatest के लिए candidate को हर तत्व से compare करें। S के bounds के लिए सभी ambient elements में आवश्यक तुलनाएँ जाँचें। फिर देखें कि कौन-सा lower bound बाकी lower bounds से ऊपर है या कौन-सा upper bound बाकी upper bounds से नीचे है।
सीमित poset को lattice सिद्ध करने के लिए हर unordered pair जाँचें या intersection/union जैसा सामान्य निर्माण दें। महत्वपूर्ण जाँच के लिए अलग तत्वों के pairs पर्याप्त हैं: किसी तत्व का स्वयं के साथ meet और join वही तत्व होता है। केवल चित्र देखकर निर्णय लेने के बजाय candidate को हर upper bound से compare करें। Upper bounds का set सीमित और गैर-रिक्त हो तथा उसमें वास्तव में एक ही minimal तत्व हो, तो वही least भी है: हर upper bound के नीचे कोई minimal upper bound होगा, जो वही unique तत्व होना चाहिए।
झटपट संदर्भ
- Poset: reflexive + antisymmetric + transitive।
- Total order: हर pair comparable भी हो।
- Hasse edges: covers, न कि हर सत्य ordered pair।
- Least ⇒ minimal; greatest ⇒ maximal; उलटी दिशाएँ गलत हो सकती हैं।
- Bounds, ambient set में होने चाहिए; bounded subset में होना जरूरी नहीं।
- Lattice: हर pair का meet और join हो।
- P(A) और inclusion में meet=intersection, join=union।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें। दिए domains और operations महत्वपूर्ण हैं।
C01. Set पर partial order किन तीन गुणों से परिभाषित होता है?
A. Reflexive, antisymmetric और transitive B. Reflexive, symmetric और transitive C. Irreflexive, symmetric और transitive D. Reflexive, symmetric और nontransitive
उत्तर: A
A: यही partial-order की शर्तें हैं; हर pair की comparability जरूरी नहीं।
B: ये equivalence relation के गुण हैं, सामान्य partial order की शर्तें नहीं।
C: Partial order reflexive है, irreflexive नहीं, और antisymmetry चाहिए।
D: Partial order में transitivity और antisymmetry चाहिए।
C02. Divisibility poset D={1,2,3,4,6,12} में 1 और 12 के बारे में क्या सही है?
A. Cover edge न होने से वे incomparable हैं। B. 1≼12 सत्य है, लेकिन 12, 1 को cover नहीं करता। C. 1, 12 को विभाजित करता है, इसलिए 12, 1 को cover करता है। D. Hasse diagram transitive pairs छोड़ता है, इसलिए 1≼12 असत्य है।
उत्तर: B
A: Comparability पूरे order या upward paths से तय है, केवल direct cover edge से नहीं।
B: 1, 12 को विभाजित करता है, लेकिन 1≺2≺12 जैसा बीच का तत्व है, इसलिए cover नहीं।
C: Divisibility से order मिलता है, लेकिन बीच के तत्व cover होने से रोकते हैं।
D: चित्र में edge न बनाने से underlying transitive relation मिटता नहीं।
C03. A={2,3,6} पर divisibility order में minimal तत्व और least तत्व कौन-से हैं?
A. Minimal {2}; least 2 B. Minimal {1}; least 1 C. Minimal {2,3}; least तत्व नहीं D. Minimal {6}; least 6
उत्तर: C
A: 3 भी minimal है और 2, 3 को विभाजित नहीं करता, इसलिए 2 least नहीं।
B: 1 underlying set में नहीं; वह उसका तत्व या bound नहीं हो सकता।
C: A में 2 और 3 के अलग predecessors नहीं और वे एक-दूसरे को विभाजित नहीं करते; दोनों से नीचे कोई तत्व नहीं।
D: 6 greatest और maximal है, minimal नहीं; 2 और 3 उससे नीचे हैं।
C04. Divisibility वाले 12 के सभी धनात्मक divisors के lattice में 4 और 6 का क्रमशः meet और join क्या है?
A. 1, 12 B. 4, 6 C. 12, 2 D. 2, 12
उत्तर: D
A: 1 lower bound है, लेकिन इस order में 2 उससे बड़ा common lower bound है।
B: 4 और 6 incomparable हैं; वे आवश्यक प्रकार के common bounds नहीं।
C: Meet और join उलट गए: 12 upper bound और 2 greatest lower bound है।
D: gcd=2 और lcm=12; दोनों divisor set में हैं।
C05. Divisibility से क्रमित {1,2,3} lattice क्यों नहीं है?
A. इस set पर divisibility transitive नहीं। B. 2 और 3 का set के भीतर कोई common upper bound नहीं। C. 2 और 3 का set के भीतर कोई lower bound नहीं। D. हर lattice का total order होना जरूरी है।
उत्तर: B
A: Divisibility transitive रहती है; समस्या poset की शर्त में नहीं।
B: 1,2,3 में कोई दोनों 2 और 3 से divisible नहीं, इसलिए pair का इस poset में join नहीं।
C: 1 common lower bound और उनका meet है।
D: Lattices में incomparable तत्व हो सकते हैं; समस्या missing join है, केवल incomparability नहीं।
C06. Inclusion से क्रमित P({a,b}) में {a} और {b} का meet और join क्या है?
A. ∅ और {a,b} B. {a,b} और ∅ C. {a} और {b} D. Incomparable होने के कारण दोनों मौजूद नहीं
उत्तर: A
A: Meet intersection और join union है: {a}∩{b}=∅ तथा {a}∪{b}={a,b}।
B: Intersection और union की भूमिकाएँ उलट गई हैं।
C: कोई singleton दोनों singletons का common lower या upper bound नहीं।
D: Incomparable होने से meet और join नहीं रुकते; ambient power set में दोनों हैं।
स्रोत और दायरा
यह मौलिक आधारभूत पाठ आधिकारिक GATE 2027 CS syllabus के Section 1 में Discrete Mathematics से जुड़ा है। यह पूरा विषय या पूरा syllabus नहीं। Syllabus प्रासंगिकता बताता है; NPTEL course आगे पढ़ने का मूल संस्थागत स्रोत है। उदाहरण और अभ्यास मौलिक हैं, परीक्षा से नकल किए प्रश्न नहीं।
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन