डेडेकाइंड-मैकनील समापन: Difference between revisions

Revision as of 00:48, 10 July 2023

आंशिक रूप से अनुक्रम किए गए समूह का हस्से आरेख (बाएं) और इसका डेडेकाइंड-मैकनील समापन (दाएं)।

गणित में, विशेष रूप से अनुक्रम सिद्धांत में, आंशिक रूप से अनुक्रम किए गए समूह को डेडेकाइंड-मैकनील समापन कहा जाता है। इसका नाम होलब्रुक मान मैकनील के नाम पर रखा गया था, जिनके 1937 के पेपर ने पहली बार इसे परिभाषित और निर्मित किया था, और यह तर्कसंगत संख्याओं से वास्तविक संख्याओं के निर्माण के लिए डेडेकाइंड द्वारा उपयोग किए गए डेडेकाइंड अलगाव को सामान्यीकृत करता है। इसे अलगाव द्वारा संपूर्णता या सामान्य संपूर्ण भी कहा जाता है।^[1] ka

अनुक्रम अंतर्निहित और नियम संपूर्णता

आंशिक रूप से अनुक्रम किए गए समूह (पोसमूह) में द्विआधारी संबंध के साथ तत्वों का एक समूह (गणित) होता है $x \leq y$ तत्वों के युग्मों पर जो कि प्रतिवर्ती संबंध है ( $x \leq x$ प्रत्येक x के लिए), सकर्मक संबंध (यदि $x \leq y$ और $y \leq z$ तब $x \leq z$ ), और प्रतिसममिति संबंध (यदि दोनों $x \leq y$ और $y \leq x$ फिर $x = y$ ). संपूर्णांकों या वास्तविक संख्याओं पर सामान्य संख्यात्मक क्रम इन गुणों को संतुष्ट करते है, चूँकि, संख्याओं पर क्रम के विपरीत, आंशिक क्रम में दो तत्व हो सकते है जो अतुलनीय होते है: $x \leq y$ और $y \leq x$ प्राप्त होता है। आंशिक क्रम का एक और परिचित उदाहरण समूह के जोड़ पर उपसमूह अनुक्रमित ⊆ है।^[2]

अगर $S$ आंशिक रूप से अनुक्रम किया गया समूह है, संपूर्णता $S$ का अर्थ है संपूर्ण नियम $L$ के अनुक्रम-अंतर्निहित के साथ $S$ में $L$ .^[3] संपूर्ण धारणा का अर्थ है कि तत्वों का प्रत्येक उपसमुच्चय $L$ में एक अनंत और सर्वोच्च है, यह वास्तविक संख्याओं के अनुरूप गुणों का सामान्यीकरण करता है। अनुक्रम-अंतर्निहित की धारणा उन आवश्यकताओं को लागू करता है जो इसके अलग-अलग तत्वों को लागू करते है $S$ को अलग-अलग तत्वों में अंकित किया जाता है $L$ , और वह तत्वों की प्रत्येक जोड़ $S$ में समान क्रम होता है $L$ जैसे $S$ . विस्तारित वास्तविक संख्या रेखा (+∞ और −∞ के साथ वास्तविक संख्याएं) तर्कसंगत संख्याओं के इस अर्थ में संपूर्ण है: तर्कसंगत संख्याओं का समूह {3, 3.1, 3.14, 3.141, 3.1415, 3.14159, ...} की कोई तर्कसंगत न्यूनतम ऊपरी सीमा नहीं होती है, लेकिन वास्तविक संख्याओं में इसकी सबसे कम ऊपरी सीमा होता है $π$ .^[4]

किसी दिए गए आंशिक रूप से अनुक्रम किए गए समूह में कई अलग-अलग संपूर्णताएँ हो सकती है। उदाहरण के लिए, किसी आंशिक रूप से अनुक्रम किए गए समूह का पूरा होना $S$ उपसमुच्चय द्वारा क्रमित इसके निचले समुच्चय का समुच्चय होता है। $S$ प्रत्येक तत्व को अंकित करके इस (संपूर्ण) नियम में अंतर्निहित होता है $x$ तत्वों के निचले समूह के लिए जो इससे कम या इसके बराबर होता है $x$ . परिणाम एक वितरणात्मक नियम होता है और इसका उपयोग बिरखॉफ के प्रतिनिधित्व प्रमेय में किया जाता है। चूँकि, इसमें संपूर्णता के लिए आवश्यकता से कहीं अधिक तत्व हो सकते है $S$ .^[5] सभी संभावित नियम संपूर्णताओं में से, डेडेकाइंड-मैकनील संपूर्णता सबसे छोटा संपूर्ण नियम है $S$ इसमें समाहित होते है।^[6]

परिभाषा

प्रत्येक उपसमुच्चय के लिए $A$ आंशिक रूप से अनुक्रम किए गए समूह का होता है $S$ , $A u$ की ऊपरी सीमा के समुच्चय को निरूपित करें $A$ , वह है, एक तत्व $x$ का $S$ से संबंधित $A u$ जब कभी भी $x$ प्रत्येक तत्व से बड़ा या उसके बराबर है $A$ . सममित रूप से, चलो $A l$ की निचली सीमाओं के समुच्चय को निरूपित करें $A$ , वे तत्व जो प्रत्येक तत्व से कम या उसके बराबर है $A$ . फिर डेडेकाइंड-मैकनील का समापन $S$ में सभी उपसमुच्चय शामिल है $A$ जिसके लिए

(A u) l = A

,

इसे शामिल करके आदेश दिया गया है: $A \leq B$ संपूर्णता में यदि और केवल यदि $A \subseteq B$ संपत्तियां।^[7]

तत्व $x$ का $S$ अपने आदर्श (आदेश सिद्धांत), समूह के रूप में संपूर्णता में एम्बेड करता है $↓ x$ से कम या उसके बराबर तत्वों का $x$ . तब $(↓ x) u$ से बड़े या उसके बराबर तत्वों का समूह है $x$ , और $((↓ x) u) l = ↓ x$ , वह दिखा रहा हूँ $↓ x$ वास्तव में संपूर्णता का सदस्य है। से अंकितिंग $x$ को $↓ x$ एक अनुक्रम-अंतर्निहित है।^[7] डेडेकाइंड-मैकनेइल संपूर्णता की एक वैकल्पिक परिभाषा जो डेडेकाइंड कट की परिभाषा से अधिक मिलती-जुलती है, कभी-कभी उपयोग की जाती है।^[8] आंशिक रूप से अनुक्रम किए गए समूह में $S$ , समूह की एक जोड़ी के रूप में कट को परिभाषित करें $(A, B)$ जिसके लिए $A u = B$ और $A = B l$ . अगर $(A, B)$ एक कट है तो A समीकरण को संतुष्ट करता है $(A u) l = A$ , और इसके विपरीत यदि $(A u) l = A$ तब $(A, A u)$ एक कट है. इसलिए, कट का समूह, आंशिक रूप से कट के निचले समूह (या ऊपरी समूह पर समावेशन संबंध के विपरीत) पर शामिल किए जाने के द्वारा आदेश दिया गया है, डेडेकाइंड-मैकनील संपूर्णता की एक समतुल्य परिभाषा देता है।^[9]

वैकल्पिक परिभाषा के साथ, संपूर्ण नियम के जुड़ने और मिलने के संचालन दोनों में सममित विवरण है: यदि $(A i, B i)$ कट्स के किसी भी परिवार में कट्स है, तो इन कट्स का मिलन कट है $(L, L u)$ कहाँ $L = \cap i A i$ , और जुड़ना ही कट है $(U l, U)$ कहाँ $U = \cap i B i$ .^[9]

उदाहरण

अगर $\mathbb {Q}$ तर्कसंगत संख्याओं का समूह है, जिसे सामान्य संख्यात्मक क्रम के साथ पूरी तरह से व्यवस्थित समूह के रूप में देखा जाता है, फिर डेडेकाइंड-मैकनील के प्रत्येक तत्व को पूरा किया जाता है $\mathbb {Q}$ इसे डेडेकाइंड कट और डेडेकाइंड-मैकनील के पूरा होने के रूप में देखा जा सकता है $\mathbb {Q}$ दो अतिरिक्त मानों के साथ वास्तविक संख्याओं पर कुल क्रम है $\pm \infty$ .^[10] अगर $S$ एक एंटीचेन है (तत्वों का एक समूह जिनमें से कोई भी दो तुलनीय नहीं है) तो डेडेकाइंड-मैकनील का समापन $S$ के होते है $S$ स्वयं दो अतिरिक्त तत्वों के साथ, एक निचला तत्व जो प्रत्येक तत्व के नीचे है $S$ और एक शीर्ष तत्व जो प्रत्येक तत्व के ऊपर है $S$ .^[11] अगर $O$ वस्तुओं का कोई भी सीमित समूह है, और $A$ वस्तुओं के लिए एकात्मक विशेषताओं का कोई सीमित समूह है $O$ , तो कोई ऊंचाई दो का आंशिक क्रम बना सकता है जिसमें आंशिक क्रम के तत्व वस्तुएं और विशेषताएं है, और जिसमें $x \leq y$ कब $x$ एक वस्तु है जिसमें विशेषता है $y$ . इस तरह से परिभाषित आंशिक आदेश के लिए, डेडेकाइंड-मैकनील का समापन $S$ को एक अवधारणा नियम के रूप में जाना जाता है, और यह औपचारिक अवधारणा विश्लेषण के क्षेत्र में एक केंद्रीय भूमिका निभाता है।^[12]

गुण

डेडेकाइंड-मैकनील आंशिक रूप से अनुक्रम किए गए समूह को पूरा करता है $S$ सबसे छोटी संपूर्ण नियम है $S$ इसमें सन्निहित है, इस अर्थ में कि, यदि $L$ किसी भी नियम का पूरा होना है $S$ , तो डेडेकाइंड-मैकनील संपूर्णता आंशिक रूप से अनुक्रम किया गया उपसमुच्चय है $L$ .^[6] कब $S$ परिमित है, इसकी संपूर्णता भी परिमित है, और सभी परिमित संपूर्ण नियमों में तत्वों की संख्या सबसे कम है $S$ .^[12]

आंशिक रूप से अनुक्रम किया गया समूह $S$ डेडेकाइंड-मैकनेइल संपूर्णता में जॉइन-डेंस और मीट-डेंस है, अर्थात्, संपूर्णता का प्रत्येक तत्व कुछ तत्वों के समूह का जोड़ है $S$ , और इसमें तत्वों के कुछ समूह का मिलन भी है $S$ .^[13] डेडेकाइंड-मैकनील संपूर्णता को संपूर्णताओं में से एक माना जाता है $S$ इस संपत्ति द्वारा.^[14]

बूलियन बीजगणित (संरचना) का डेडेकाइंड-मैकनील समापन एक संपूर्ण बूलियन बीजगणित है, इस परिणाम को वालेरी इवानोविच ग्लिवेंको और मार्शल स्टोन के बाद ग्लिवेंको-स्टोन प्रमेय के रूप में जाना जाता है।^[15] इसी प्रकार, एक अवशिष्ट नियम का डेडेकाइंड-मैकनील पूरा होना एक संपूर्ण अवशिष्ट नियम है।^[16] चूँकि, एक वितरणात्मक नियम का पूरा होना स्वयं वितरणात्मक नहीं होना चाहिए, और एक मॉड्यूलर नियम का पूरा होना मॉड्यूलर नहीं रह सकता है।^[17] डेडेकाइंड-मैकनील संपूर्णता स्व-दोहरी है: आंशिक क्रम के द्वैत (आदेश सिद्धांत) का पूरा होना संपूर्णता के दोहरे के समान है।^[18]

डेडेकाइंड-मैकनील का समापन $S$ का क्रम आयाम भी वैसा ही है $S$ अपने आप।^[19] आंशिक रूप से अनुक्रम किए गए समूहों और आंशिक रूप से अनुक्रम किए गए समूहों के बीच मोनोटोनिक कार्यों की श्रेणी (गणित) में, संपूर्ण नियम अनुक्रम-अंतर्निहित के लिए इंजेक्शन वस्तु बनाती है, और डेडेकाइंड-मैकनील पूरा करती है $S$ का इंजेक्शन पतवार है $S$ .^[20]

एल्गोरिदम

कई शोधकर्ताओं ने एक सीमित आंशिक रूप से अनुक्रम किए गए समूह को पूरा करने वाले डेडेकाइंड-मैकनील के निर्माण के लिए एल्गोरिदम की जांच की है। डेडेकाइंड-मैकनील संपूर्णता उस आंशिक क्रम से तेजी से बड़ी हो सकती है, जिससे यह आता है,^[12] और ऐसे एल्गोरिदम के लिए समय सीमा आम तौर पर आउटपुट-संवेदनशील एल्गोरिदम में बताई जाती है|आउटपुट-संवेदनशील तरीके से, संख्या पर निर्भर करता है $n$ इनपुट के तत्वों का आंशिक क्रम, और संख्या पर $c$ इसके संपूर्ण होने के तत्वों का.

अलगाव के समूह का निर्माण

Ganter & Kuznetsov (1998) एक वृद्धिशील एल्गोरिदम का वर्णन करें, जिसमें एक समय में एक तत्व जोड़कर इनपुट आंशिक क्रम बनाया जाता है, प्रत्येक चरण में, छोटे आंशिक क्रम की संपूर्णता को बड़े आंशिक क्रम की संपूर्णता के रूप में विस्तारित किया जाता है। उनकी पद्धति में, संपूर्णता को अलगाव की एक स्पष्ट सूची द्वारा दर्शाया जाता है। संवर्धित आंशिक क्रम का प्रत्येक कट, उस कट को छोड़कर जिसके दो समूह नए तत्व में प्रतिच्छेद करते है, या तो पिछले आंशिक क्रम से एक कट है या पिछले से कट के एक या दूसरे पक्ष में नया तत्व जोड़कर बनता है। आंशिक क्रम, इसलिए उनके एल्गोरिदम को यह निर्धारित करने के लिए कि कौन से कट है, केवल इस फॉर्म के समूह के जोड़े का परीक्षण करने की आवश्यकता है। आंशिक क्रम को पूरा करने के लिए एक तत्व जोड़ने के लिए उनकी विधि का उपयोग करने का समय है $O (cnw)$ कहाँ $w$ आंशिक क्रम की चौड़ाई है, यानी, इसके सबसे बड़े एंटीचेन का आकार। इसलिए, किसी दिए गए आंशिक आदेश के पूरा होने की गणना करने का समय है $O (cn 2 w) = O(cn 3)$ .^[12]

जैसा Jourdan, Rampon & Jard (1994) ध्यान दें, आंशिक रूप से अनुक्रम किए गए समूह में सभी कटों को सूचीबद्ध करने की समस्या को एक सरल समस्या के विशेष मामले के रूप में तैयार किया जा सकता है, सभी अधिकतम एंटीचेन को एक अलग आंशिक रूप से अनुक्रम किए गए समूह में सूचीबद्ध करने की। अगर $P$ कोई आंशिक रूप से अनुक्रम किया गया समूह है, मान लीजिए $Q$ एक आंशिक क्रम हो जिसके तत्वों की दो प्रतियां हों $P$ : प्रत्येक तत्व के लिए $x$ का $P$ , $Q$ में दो तत्व शामिल है $x 0$ और $x 1$ , साथ $x i < y j$ अगर और केवल अगर $x < y$ और $i < j$ . फिर अलगाव होती है $P$ अधिकतम एंटीचेन के साथ एक-के-लिए-एक से मेल खाता है $Q$ : कट के निचले समूह के तत्व एक एंटीचेन में सबस्क्रिप्ट 0 वाले तत्वों के अनुरूप होते है, और कट के ऊपरी समूह के तत्व एक एंटीचेन में सबस्क्रिप्ट 1 वाले तत्वों के अनुरूप होते है। जॉर्डन एट अल. अधिकतम एंटीचेन खोजने के लिए एक एल्गोरिदम का वर्णन करें, जिसे सभी कटों को सूचीबद्ध करने की समस्या पर लागू किया जाए $P$ , समय लेता है $O (c (nw + w 3))$ , के एल्गोरिदम में सुधार Ganter & Kuznetsov (1998) जब चौड़ाई $w$ छोटा है।^[21] वैकल्पिक रूप से, एक अधिकतम एंटीचेन $Q$ तुलनीयता ग्राफ़ में अधिकतम स्वतंत्र समूह के समान है $Q$ , या तुलनीयता ग्राफ के पूरक में एक अधिकतम क्लिक, इसलिए क्लिक समस्या या स्वतंत्र समूह समस्या के लिए एल्गोरिदम को डेडेकाइंड-मैकनेइल संपूर्णता समस्या के इस संस्करण पर भी लागू किया जा सकता है।^[22]

कवरिंग ग्राफ़ का निर्माण

डेडेकाइंड-मैकनील संपूर्णता का संक्रमणीय कमी या कवरिंग ग्राफ इसके तत्वों के बीच क्रम संबंध का संक्षिप्त तरीके से वर्णन करता है: कट के प्रत्येक पड़ोस (ग्राफ सिद्धांत) को कट के ऊपरी या निचले समूह से मूल आंशिक क्रम के एक तत्व को हटाना होगा, इसलिए प्रत्येक शीर्ष पर अधिकतम $n$ पड़ोसियों। इस प्रकार, कवरिंग ग्राफ़ है $c$ शीर्ष और अधिक से अधिक $cn /2$ पड़ोसियों, एक संख्या जो की तुलना में बहुत छोटी हो सकती है $c 2$ एक मैट्रिक्स में प्रविष्टियाँ जो तत्वों के बीच सभी जोड़ीवार तुलनाओं को निर्दिष्ट करती है। Nourine & Raynaud (1999)दिखाएं कि इस कवरिंग ग्राफ़ की कुशलतापूर्वक गणना कैसे करें, अधिक सामान्यतः, यदि $B$ समूह का कोई भी परिवार है, वे दिखाते है कि उपसमुच्चय के संघों की नियम के कवरिंग ग्राफ की गणना कैसे करें $B$ . डेडेकाइंड-मैकनील नियम के मामले में, $B$ को प्रमुख आदर्शों के पूरक समूहों के परिवार और के उपसमूहों के संघ के रूप में लिया जा सकता है $B$ कट्स के निचले समूह के पूरक है। उनके एल्गोरिदम का मुख्य विचार उपसमुच्चय के संघ उत्पन्न करना है $B$ वृद्धिशील रूप से (प्रत्येक समूह के लिए $B$ , पहले से उत्पन्न सभी यूनियनों के साथ अपना संघ बनाते हुए), एक त्रि में समूह के परिणामी परिवार का प्रतिनिधित्व करते है, और कवरिंग संबंध में आसन्नता के लिए समूह के कुछ उम्मीदवार जोड़े का परीक्षण करने के लिए त्रि प्रतिनिधित्व का उपयोग करते है, समय लगता है $O (cn 2)$ . बाद के काम में, उन्हीं लेखकों ने दिखाया कि एल्गोरिदम को समान कुल समय सीमा के साथ पूरी तरह से वृद्धिशील (एक समय में आंशिक क्रम में तत्वों को जोड़ने में सक्षम) बनाया जा सकता है।^[23]

↑ Davey & Priestley (2002, p. 166); Schröder (2003, p. 119).
↑ Roman (2007).
↑ Schröder (2003), definition 5.3.1, p. 119.
↑ O'Leary (2015).
↑ Carpineto, Claudio; Romano, Giovanni (2004), Concept data analysis: theory and applications, John Wiley and Sons, p. 10, ISBN 978-0-470-85055-8.
↑ ^6.0 ^6.1 Bishop (1978); Schröder (2003), Theorem 5.3.8, p. 121.
↑ ^7.0 ^7.1 MacNeille (1937), Lemma 11.8, p. 444; Davey & Priestley (2002), Lemma 3.9(i), p. 166.
↑ This is the definition originally used by MacNeille (1937), for instance.
↑ ^9.0 ^9.1 MacNeille (1937).
↑ Davey & Priestley (2002), Example 7.44(1), p. 168; Schröder (2003), Example 5.3.3(2), p. 120.
↑ Davey & Priestley (2002), Example 7.44(2), p. 168.
↑ ^12.0 ^12.1 ^12.2 ^12.3 Ganter & Kuznetsov (1998).
↑ Schröder (2003), Proposition 5.3.7, p. 121.
↑ Schmidt (1956).
↑ Birkhoff (1995), Theorem 27, p. 130.
↑ Gabbay, Shehtman & Skvortsov (2009).
↑ Cotlar (1944); Funayama (1944).
↑ Birkhoff (1995).
↑ This result is frequently attributed to an unpublished 1961 Harvard University honors thesis by K. A. Baker, "Dimension, join-independence and breadth in partially ordered sets". It was published by Novák (1969).
↑ Banaschewski & Bruns (1967).
↑ Jourdan, Rampon & Jard (1994).
↑ For the equivalence between algorithms for antichains in partial orders and for independent sets in comparability graphs, see Cameron (1985), p. 251.
↑ Nourine & Raynaud (2002).

संदर्भ

Banaschewski, B.; Bruns, G. (1967), "Categorical characterization of the MacNeille completion", Archiv der Mathematik, 18 (4): 369–377, doi:10.1007/BF01898828, MR 0221984, S2CID 121216988.
Birkhoff, Garrett (1995), "VI.9 Completion by Cuts", Lattice Theory, Colloquium Publications, vol. 25 (3rd ed.), American Mathematical Society, pp. 126–128, ISBN 978-0-8218-1025-5.
Bishop, Alan A. (1978), "A universal mapping characterization of the completion by cuts", Algebra Universalis, 8 (3): 349–353, doi:10.1007/bf02485405, MR 0469839, S2CID 121624631.
Cameron, Kathie (1985), "Antichain sequences", Order, 2 (3): 249–255, doi:10.1007/BF00333130, MR 0824698
Cotlar, Mischa (1944), "A method of construction of structures and its application to topological spaces and abstract arithmetic", Univ. Nac. Tucumán. Revista A., 4: 105–157, MR 0014062.
Davey, B. A.; Priestley, Hilary A. (2002), "7.38 The Dedekind–MacNeille completion", Introduction to Lattices and Order (2nd ed.), Cambridge University Press, p. 166, ISBN 978-0-521-78451-1, Zbl 1002.06001.
Funayama, Nenosuke (1944), "On the completion by cuts of distributive lattices", Proceedings of the Imperial Academy, Tokyo, 20: 1–2, doi:10.3792/pia/1195573210, MR 0014063, Zbl 0063.01484.
Gabbay, Dov M.; Shehtman, Valentin; Skvortsov, Dimitrij (2009), "3.4.12 The Dedekind–MacNeille completion of a residuated lattice", Quantification in Nonclassical Logic, Volume 1, Studies in logic and the foundations of mathematics, vol. 153, Elsevier, pp. 177–178, ISBN 978-0-444-52012-8, Zbl 1211.03002.
Ganter, Bernhard; Kuznetsov, Sergei O. (1998), "Stepwise construction of the Dedekind-MacNeille completion", Proc. 6th Int. Conf. Conceptual Structures: Theory, Tools and Applications (ICCS98), Lecture Notes in Computer Science, vol. 1453, Springer-Verlag, pp. 295–302, doi:10.1007/BFb0054922, MR 1673860, Zbl 0928.06004.
Jourdan, Guy-Vincent; Rampon, Jean-Xavier; Jard, Claude (1994), "Computing on-line the lattice of maximal antichains of posets" (PDF), Order, 11 (3): 197–210, doi:10.1007/BF02115811, MR 1308475, S2CID 120755660, Zbl 0814.06004.
MacNeille, H. M. (1937), "Partially ordered sets", Transactions of the American Mathematical Society, 42 (3): 416–460, doi:10.2307/1989739, JFM 63.0833.04, JSTOR 1989739, MR 1501929, Zbl 0017.33904.
Nourine, Lhouari; Raynaud, Olivier (1999), "A fast algorithm for building lattices", Information Processing Letters, 71 (5–6): 199–204, doi:10.1016/S0020-0190(99)00108-8, MR 1726978, Zbl 0998.06005.
Nourine, Lhouari; Raynaud, Olivier (2002), "A fast incremental algorithm for building lattices", Journal of Experimental and Theoretical Artificial Intelligence, 14 (2): 217–227, doi:10.1080/09528130210164152, S2CID 38160433, Zbl 1022.68027.
Novák, Vítězslav (1969), "Über eine Eigenschaft der Dedekind-MacNeilleschen Hülle", Mathematische Annalen, 179: 337–342, doi:10.1007/BF01350778, MR 0240010, S2CID 120963245.
O'Leary, Michael L. (2015), A First Course in Mathematical Logic and Set Theory, John Wiley & Sons, p. 276, ISBN 978-0-470-90588-3
Roman, Steven (2007), Advanced Linear Algebra, Graduate Texts in Mathematics, vol. 135 (3rd ed.), Springer, pp. 10–11, ISBN 978-0-387-72831-5
Schmidt, Jürgen (1956), "Zur Kennzeichnung der Dedekind-MacNeilleschen Hülle einer geordneten Hülle", Archiv der Mathematik (in Deutsch), 7: 241–249, doi:10.1007/BF01900297, MR 0084484
Schröder, Bernd S. W. (2003), "5.3 Embeddings/The Dedekind/MacNeille Completion", Ordered Sets: An Introduction, Birkhäuser, pp. 119–122, ISBN 978-1-4612-6591-7.

बाहरी संबंध

MacNeille completion in PlanetMath
MacNeille completion at the nLab

[1] Davey & Priestley (2002, p. 166); Schröder (2003, p. 119).

[FOOTNOTERoman2007-2] Roman (2007).

[3] Schröder (2003), definition 5.3.1, p. 119.

[FOOTNOTEO'Leary2015-4] O'Leary (2015).

[5] Carpineto, Claudio; Romano, Giovanni (2004), Concept data analysis: theory and applications, John Wiley and Sons, p. 10, ISBN 978-0-470-85055-8.

[smallest-completion-6] 6.0 ^6.1 Bishop (1978); Schröder (2003), Theorem 5.3.8, p. 121.

[def-7] 7.0 ^7.1 MacNeille (1937), Lemma 11.8, p. 444; Davey & Priestley (2002), Lemma 3.9(i), p. 166.

[8] This is the definition originally used by MacNeille (1937), for instance.

[FOOTNOTEMacNeille1937-9] 9.0 ^9.1 MacNeille (1937).

[10] Davey & Priestley (2002), Example 7.44(1), p. 168; Schröder (2003), Example 5.3.3(2), p. 120.

[11] Davey & Priestley (2002), Example 7.44(2), p. 168.

[FOOTNOTEGanterKuznetsov1998-12] 12.0 ^12.1 ^12.2 ^12.3 Ganter & Kuznetsov (1998).

[13] Schröder (2003), Proposition 5.3.7, p. 121.

[FOOTNOTESchmidt1956-14] Schmidt (1956).

[15] Birkhoff (1995), Theorem 27, p. 130.

[FOOTNOTEGabbayShehtmanSkvortsov2009-16] Gabbay, Shehtman & Skvortsov (2009).

[17] Cotlar (1944); Funayama (1944).

[FOOTNOTEBirkhoff1995-18] Birkhoff (1995).

[19] This result is frequently attributed to an unpublished 1961 Harvard University honors thesis by K. A. Baker, "Dimension, join-independence and breadth in partially ordered sets". It was published by Novák (1969).

[FOOTNOTEBanaschewskiBruns1967-20] Banaschewski & Bruns (1967).

[FOOTNOTEJourdanRamponJard1994-21] Jourdan, Rampon & Jard (1994).

[22] For the equivalence between algorithms for antichains in partial orders and for independent sets in comparability graphs, see Cameron (1985), p. 251.

[FOOTNOTENourineRaynaud2002-23] Nourine & Raynaud (2002).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

@@ Line 1: / Line 1: @@
 {{short description|Smallest complete lattice containing a partial order}}
-{{redirect|Dedekind completion|some other related concepts|Dedekind completeness}}
+{{redirect|डेडेकाइंड पूर्णता|कुछ अन्य संबंधित अवधारणाएँ|डेडेकाइंड पूर्णता}}
-[[File:Dedekind-Macneille completion.svg|thumb|240px|आंशिक रूप से ऑर्डर किए गए सेट का [[हस्से आरेख]] (बाएं) और इसका डेडेकाइंड-मैकनील समापन (दाएं)।]]गणित में, विशेष रूप से ऑर्डर सिद्धांत में, आंशिक रूप से ऑर्डर किए गए सेट का डेडेकाइंड-मैकनील समापन सबसे छोटा [[पूर्ण जाली]] है जिसमें यह शामिल है। इसका नाम [[होलब्रुक मान मैकनील]] के नाम पर रखा गया है, जिनके 1937 के पेपर ने पहली बार इसे परिभाषित और निर्मित किया था, और [[रिचर्ड डेडेकाइंड]] के नाम पर क्योंकि इसका निर्माण [[तर्कसंगत संख्या]]ओं से [[वास्तविक संख्या]]ओं के निर्माण के लिए डेडेकाइंड द्वारा उपयोग किए गए [[डेडेकाइंड कट]]ौती को सामान्यीकृत करता है। इसे कटौती द्वारा पूर्णता या सामान्य पूर्णता भी कहा जाता है।<ref>{{harvtxt|Davey| Priestley|2002|p=166}}; {{harvtxt|Schröder|2003|p=119}}.</ref>
+[[File:Dedekind-Macneille completion.svg|thumb|240px|आंशिक रूप से अनुक्रम किए गए समूह का [[हस्से आरेख]] (बाएं) और इसका डेडेकाइंड-मैकनील समापन (दाएं)।]]गणित में, विशेष रूप से अनुक्रम सिद्धांत में, आंशिक रूप से अनुक्रम किए गए समूह को डेडेकाइंड-मैकनील समापन कहा जाता है। इसका नाम [[होलब्रुक मान मैकनील]] के नाम पर रखा गया था, जिनके 1937 के पेपर ने पहली बार इसे परिभाषित और निर्मित किया था, और यह [[तर्कसंगत संख्या|तर्कसंगत संख्याओं]] से [[वास्तविक संख्या|वास्तविक संख्याओं]] के निर्माण के लिए डेडेकाइंड द्वारा उपयोग किए गए [[डेडेकाइंड कट|डेडेकाइंड अलगाव]] को सामान्यीकृत करता है। इसे अलगाव द्वारा संपूर्णता या सामान्य संपूर्ण भी कहा जाता है।<ref>{{harvtxt|Davey| Priestley|2002|p=166}}; {{harvtxt|Schröder|2003|p=119}}.</ref> ka
+==अनुक्रम अंतर्निहित और नियम संपूर्णता==
+आंशिक रूप से अनुक्रम किए गए समूह (पोसमूह) में द्विआधारी संबंध के साथ तत्वों का एक [[सेट (गणित)|समूह (गणित)]] होता है {{math|''x'' ≤ ''y''}} तत्वों के युग्मों पर जो कि [[प्रतिवर्ती संबंध]] है ({{math|''x'' ≤ ''x''}} प्रत्येक x के लिए), [[सकर्मक संबंध]] (यदि {{math|''x'' ≤ ''y''}} और {{math|''y'' ≤ ''z''}} तब {{math|''x'' ≤ ''z''}}), और [[एंटीसिमेट्रिक संबंध|प्रतिसममिति संबंध]] (यदि दोनों {{math|''x'' ≤ ''y''}} और {{math|''y'' ≤ ''x''}} फिर {{math|1=''x'' = ''y''}}). [[पूर्णांक|संपूर्णांकों]] या वास्तविक संख्याओं पर सामान्य संख्यात्मक क्रम इन गुणों को संतुष्ट करते है, चूँकि, संख्याओं पर क्रम के विपरीत, आंशिक क्रम में दो तत्व हो सकते है जो अतुलनीय होते है: {{math|''x'' ≤ ''y''}} और {{math|''y'' ≤ ''x''}} प्राप्त होता है। आंशिक क्रम का एक और परिचित उदाहरण समूह के जोड़ पर [[सबसेट|उपसमूह]] अनुक्रमित ⊆ है।{{sfnp|Roman|2007}}
-==ऑर्डर एम्बेडिंग और जाली पूर्णता==
-आंशिक रूप से ऑर्डर किए गए सेट (पोसेट) में बाइनरी संबंध के साथ तत्वों का एक [[सेट (गणित)]] होता है {{math|''x'' ≤ ''y''}}तत्वों के युग्मों पर जो कि [[प्रतिवर्ती संबंध]] है ({{math|''x'' ≤ ''x''}} प्रत्येक x के लिए), [[सकर्मक संबंध]] (यदि {{math|''x'' ≤ ''y''}} और {{math|''y'' ≤ ''z''}} तब {{math|''x'' ≤ ''z''}}), और [[एंटीसिमेट्रिक संबंध]] (यदि दोनों {{math|''x'' ≤ ''y''}} और {{math|''y'' ≤ ''x''}} फिर पकड़ो {{math|1=''x'' = ''y''}}). [[पूर्णांक]]ों या वास्तविक संख्याओं पर सामान्य संख्यात्मक क्रम इन गुणों को संतुष्ट करते हैं; हालाँकि, संख्याओं पर क्रम के विपरीत, आंशिक क्रम में दो तत्व हो सकते हैं जो अतुलनीय हैं: कोई भी नहीं {{math|''x'' ≤ ''y''}} और न {{math|''y'' ≤ ''x''}} धारण करता है। आंशिक क्रम का एक और परिचित उदाहरण सेट के जोड़े पर [[सबसेट]] ऑर्डरिंग ⊆ है।{{sfnp|Roman|2007}}
-अगर {{mvar|S}} आंशिक रूप से ऑर्डर किया गया सेट है, पूर्णता {{mvar|S}} का अर्थ है पूर्ण जाली {{mvar|L}} के [[ऑर्डर-एम्बेडिंग]] के साथ {{mvar|S}} में {{mvar|L}}.<ref>{{harvtxt|Schröder|2003}}, definition 5.3.1, p.&nbsp;119.</ref> पूर्ण जालक की धारणा का अर्थ है कि तत्वों का प्रत्येक उपसमुच्चय {{mvar|L}} में एक अनंत और सर्वोच्च है; यह वास्तविक संख्याओं के अनुरूप गुणों का सामान्यीकरण करता है। ऑर्डर-एम्बेडिंग की धारणा उन आवश्यकताओं को लागू करती है जो इसके अलग-अलग तत्वों को लागू करती हैं {{mvar|S}} को अलग-अलग तत्वों में मैप किया जाना चाहिए {{mvar|L}}, और वह तत्वों की प्रत्येक जोड़ी {{mvar|S}} में समान क्रम है {{mvar|L}} जैसा कि वे करते हैं {{mvar|S}}. [[विस्तारित वास्तविक संख्या रेखा]] (+∞ और −∞ के साथ वास्तविक संख्याएं) तर्कसंगत संख्याओं के इस अर्थ में एक पूर्णता है: तर्कसंगत संख्याओं का सेट {3, 3.1, 3.14, 3.141, 3.1415, 3.14159, ...} करता है इसकी कोई तर्कसंगत न्यूनतम ऊपरी सीमा नहीं है, लेकिन वास्तविक संख्याओं में इसकी सबसे कम ऊपरी सीमा है {{pi}}.{{sfnp|O'Leary|2015}}
-किसी दिए गए आंशिक रूप से ऑर्डर किए गए सेट में कई अलग-अलग पूर्णताएँ हो सकती हैं। उदाहरण के लिए, किसी आंशिक रूप से ऑर्डर किए गए सेट का एक पूरा होना {{mvar|S}} उपसमुच्चय द्वारा क्रमित इसके निचले समुच्चय का समुच्चय है। {{mvar|S}} प्रत्येक तत्व को मैप करके इस (पूर्ण) जाली में एम्बेडेड है {{mvar|x}}तत्वों के निचले समूह के लिए जो इससे कम या इसके बराबर हैं {{mvar|x}}. परिणाम एक [[वितरणात्मक जाली]] है और इसका उपयोग बिरखॉफ के प्रतिनिधित्व प्रमेय में किया जाता है। हालाँकि, इसमें पूर्णता के लिए आवश्यकता से कहीं अधिक तत्व हो सकते हैं {{mvar|S}}.<ref>{{citation|title=Concept data analysis: theory and applications|first1=Claudio|last1=Carpineto|first2=Giovanni|last2=Romano|publisher=John Wiley and Sons|year=2004|isbn=978-0-470-85055-8|page=10}}.</ref> सभी संभावित जाली पूर्णताओं में से, डेडेकाइंड-मैकनील पूर्णता सबसे छोटी पूर्ण जाली है {{mvar|S}} इसमें सन्निहित है।<ref name="smallest-completion"/>
+अगर {{mvar|S}} आंशिक रूप से अनुक्रम किया गया समूह है, संपूर्णता {{mvar|S}} का अर्थ है संपूर्ण नियम {{mvar|L}} के [[ऑर्डर-एम्बेडिंग|अनुक्रम-अंतर्निहित]] के साथ {{mvar|S}} में {{mvar|L}}.<ref>{{harvtxt|Schröder|2003}}, definition 5.3.1, p.&nbsp;119.</ref> संपूर्ण धारणा का अर्थ है कि तत्वों का प्रत्येक उपसमुच्चय {{mvar|L}} में एक अनंत और सर्वोच्च है, यह वास्तविक संख्याओं के अनुरूप गुणों का सामान्यीकरण करता है। अनुक्रम-अंतर्निहित की धारणा उन आवश्यकताओं को लागू करता है जो इसके अलग-अलग तत्वों को लागू करते है {{mvar|S}} को अलग-अलग तत्वों में अंकित किया जाता है {{mvar|L}}, और वह तत्वों की प्रत्येक जोड़ {{mvar|S}} में समान क्रम होता है {{mvar|L}} जैसे {{mvar|S}}. [[विस्तारित वास्तविक संख्या रेखा]] (+∞ और −∞ के साथ वास्तविक संख्याएं) तर्कसंगत संख्याओं के इस अर्थ में संपूर्ण है: तर्कसंगत संख्याओं का समूह {3, 3.1, 3.14, 3.141, 3.1415, 3.14159, ...} की कोई तर्कसंगत न्यूनतम ऊपरी सीमा नहीं होती है, लेकिन वास्तविक संख्याओं में इसकी सबसे कम ऊपरी सीमा होता है {{pi}}.{{sfnp|O'Leary|2015}}
+किसी दिए गए आंशिक रूप से अनुक्रम किए गए समूह में कई अलग-अलग संपूर्णताएँ हो सकती है। उदाहरण के लिए, किसी आंशिक रूप से अनुक्रम किए गए समूह का पूरा होना {{mvar|S}} उपसमुच्चय द्वारा क्रमित इसके निचले समुच्चय का समुच्चय होता है। {{mvar|S}} प्रत्येक तत्व को अंकित करके इस (संपूर्ण) नियम में अंतर्निहित होता है {{mvar|x}} तत्वों के निचले समूह के लिए जो इससे कम या इसके बराबर होता है {{mvar|x}}. परिणाम एक [[वितरणात्मक जाली|वितरणात्मक नियम]] होता है और इसका उपयोग बिरखॉफ के प्रतिनिधित्व प्रमेय में किया जाता है। चूँकि, इसमें संपूर्णता के लिए आवश्यकता से कहीं अधिक तत्व हो सकते है {{mvar|S}}.<ref>{{citation|title=Concept data analysis: theory and applications|first1=Claudio|last1=Carpineto|first2=Giovanni|last2=Romano|publisher=John Wiley and Sons|year=2004|isbn=978-0-470-85055-8|page=10}}.</ref> सभी संभावित नियम संपूर्णताओं में से, डेडेकाइंड-मैकनील संपूर्णता सबसे छोटा संपूर्ण नियम है {{mvar|S}} इसमें समाहित होते है।<ref name="smallest-completion"/>
 ==परिभाषा==
-प्रत्येक उपसमुच्चय के लिए {{mvar|A}} आंशिक रूप से ऑर्डर किए गए सेट का {{mvar|S}}, होने देना {{math|''A''<sup>u</sup>}} की [[ऊपरी सीमा]]ओं के समुच्चय को निरूपित करें {{mvar|A}}; वह है, एक तत्व {{mvar|x}} का {{mvar|S}} से संबंधित {{math|''A''<sup>u</sup>}} जब कभी भी {{mvar|x}} प्रत्येक तत्व से बड़ा या उसके बराबर है {{mvar|A}}. सममित रूप से, चलो {{math|''A''<sup>l</sup>}} की निचली सीमाओं के समुच्चय को निरूपित करें {{mvar|A}}, वे तत्व जो प्रत्येक तत्व से कम या उसके बराबर हैं {{mvar|A}}. फिर डेडेकाइंड-मैकनील का समापन {{mvar|S}} में सभी उपसमुच्चय शामिल हैं {{mvar|A}} जिसके लिए
+प्रत्येक उपसमुच्चय के लिए {{mvar|A}} आंशिक रूप से अनुक्रम किए गए समूह का होता है {{mvar|S}}, {{math|''A''<sup>u</sup>}} की [[ऊपरी सीमा]] के समुच्चय को निरूपित करें {{mvar|A}}, वह है, एक तत्व {{mvar|x}} का {{mvar|S}} से संबंधित {{math|''A''<sup>u</sup>}} जब कभी भी {{mvar|x}} प्रत्येक तत्व से बड़ा या उसके बराबर है {{mvar|A}}. सममित रूप से, चलो {{math|''A''<sup>l</sup>}} की निचली सीमाओं के समुच्चय को निरूपित करें {{mvar|A}}, वे तत्व जो प्रत्येक तत्व से कम या उसके बराबर है {{mvar|A}}. फिर डेडेकाइंड-मैकनील का समापन {{mvar|S}} में सभी उपसमुच्चय शामिल है {{mvar|A}} जिसके लिए
-:{{math|1=(''A''<sup>u</sup>)<sup>l</sup> = ''A''}};
+:{{math|1=(''A''<sup>u</sup>)<sup>l</sup> = ''A''}},
-इसे शामिल करके आदेश दिया गया है: {{math|''A'' ≤ ''B''}} पूर्णता में यदि और केवल यदि {{math|''A'' ⊆ ''B''}} संपत्तियां।<ref name=def/>
+इसे शामिल करके आदेश दिया गया है: {{math|''A'' ≤ ''B''}} संपूर्णता में यदि और केवल यदि {{math|''A'' ⊆ ''B''}} संपत्तियां।<ref name=def/>
-तत्व {{mvar|x}} का {{mvar|S}} अपने [[आदर्श (आदेश सिद्धांत)]], सेट के रूप में पूर्णता में एम्बेड करता है {{math|↓<sub>''x''</sub>}}से कम या उसके बराबर तत्वों का {{mvar|x}}. तब {{math|(↓<sub>''x''</sub>)<sup>u</sup>}} से बड़े या उसके बराबर तत्वों का समूह है {{mvar|x}}, और {{math|1=((↓<sub>''x''</sub>)<sup>u</sup>)<sup>l</sup> = ↓<sub>''x''</sub>}}, वह दिखा रहा हूँ {{math|↓<sub>''x''</sub>}} वास्तव में पूर्णता का सदस्य है। से मैपिंग {{mvar|x}} को {{math|↓<sub>''x''</sub>}} एक ऑर्डर-एम्बेडिंग है।<ref name=def>{{harvtxt|MacNeille|1937}}, Lemma 11.8, p.&nbsp; 444; {{harvtxt|Davey| Priestley|2002}}, Lemma 3.9(i), p.&nbsp;166.</ref>
+तत्व {{mvar|x}} का {{mvar|S}} अपने [[आदर्श (आदेश सिद्धांत)]], समूह के रूप में संपूर्णता में एम्बेड करता है {{math|↓<sub>''x''</sub>}}से कम या उसके बराबर तत्वों का {{mvar|x}}. तब {{math|(↓<sub>''x''</sub>)<sup>u</sup>}} से बड़े या उसके बराबर तत्वों का समूह है {{mvar|x}}, और {{math|1=((↓<sub>''x''</sub>)<sup>u</sup>)<sup>l</sup> = ↓<sub>''x''</sub>}}, वह दिखा रहा हूँ {{math|↓<sub>''x''</sub>}} वास्तव में संपूर्णता का सदस्य है। से अंकितिंग {{mvar|x}} को {{math|↓<sub>''x''</sub>}} एक अनुक्रम-अंतर्निहित है।<ref name=def>{{harvtxt|MacNeille|1937}}, Lemma 11.8, p.&nbsp; 444; {{harvtxt|Davey| Priestley|2002}}, Lemma 3.9(i), p.&nbsp;166.</ref>
-डेडेकाइंड-मैकनेइल पूर्णता की एक वैकल्पिक परिभाषा जो डेडेकाइंड कट की परिभाषा से अधिक मिलती-जुलती है, कभी-कभी उपयोग की जाती है।<ref>This is the definition originally used by {{harvtxt|MacNeille|1937}}, for instance.</ref> आंशिक रूप से ऑर्डर किए गए सेट में {{mvar|S}}, सेट की एक जोड़ी के रूप में कट को परिभाषित करें {{math|(''A'',''B'')}} जिसके लिए {{math|1=''A''<sup>u</sup> = ''B''}} और {{math|1=''A'' = ''B''<sup>l</sup>}}. अगर {{math|(''A'',''B'')}} एक कट है तो A समीकरण को संतुष्ट करता है {{math|1=(''A''<sup>u</sup>)<sup>l</sup> = ''A''}}, और इसके विपरीत यदि {{math|1=(''A''<sup>u</sup>)<sup>l</sup> = ''A''}} तब {{math|(''A'',''A''<sup>u</sup>)}} एक कट है. इसलिए, कट का सेट, आंशिक रूप से कट के निचले सेट (या ऊपरी सेट पर समावेशन संबंध के विपरीत) पर शामिल किए जाने के द्वारा आदेश दिया गया है, डेडेकाइंड-मैकनील पूर्णता की एक समतुल्य परिभाषा देता है।{{sfnp|MacNeille|1937}}
+डेडेकाइंड-मैकनेइल संपूर्णता की एक वैकल्पिक परिभाषा जो डेडेकाइंड कट की परिभाषा से अधिक मिलती-जुलती है, कभी-कभी उपयोग की जाती है।<ref>This is the definition originally used by {{harvtxt|MacNeille|1937}}, for instance.</ref> आंशिक रूप से अनुक्रम किए गए समूह में {{mvar|S}}, समूह की एक जोड़ी के रूप में कट को परिभाषित करें {{math|(''A'',''B'')}} जिसके लिए {{math|1=''A''<sup>u</sup> = ''B''}} और {{math|1=''A'' = ''B''<sup>l</sup>}}. अगर {{math|(''A'',''B'')}} एक कट है तो A समीकरण को संतुष्ट करता है {{math|1=(''A''<sup>u</sup>)<sup>l</sup> = ''A''}}, और इसके विपरीत यदि {{math|1=(''A''<sup>u</sup>)<sup>l</sup> = ''A''}} तब {{math|(''A'',''A''<sup>u</sup>)}} एक कट है. इसलिए, कट का समूह, आंशिक रूप से कट के निचले समूह (या ऊपरी समूह पर समावेशन संबंध के विपरीत) पर शामिल किए जाने के द्वारा आदेश दिया गया है, डेडेकाइंड-मैकनील संपूर्णता की एक समतुल्य परिभाषा देता है।{{sfnp|MacNeille|1937}}
-वैकल्पिक परिभाषा के साथ, पूर्ण जाली के जुड़ने और मिलने के संचालन दोनों में सममित विवरण हैं: यदि {{math|(''A<sub>i</sub>'',''B<sub>i</sub>'')}} कट्स के किसी भी परिवार में कट्स हैं, तो इन कट्स का मिलन कट है {{math|(''L'',''L''<sup>u</sup>)}} कहाँ {{math|1=''L'' = ∩<sub>''i''</sub>''A<sub>i</sub>''}}, और जुड़ना ही कट है {{math|(''U''<sup>l</sup>,''U'')}} कहाँ {{math|1=''U'' = ∩<sub>''i''</sub>''B<sub>i</sub>''}}.{{sfnp|MacNeille|1937}}
+वैकल्पिक परिभाषा के साथ, संपूर्ण नियम के जुड़ने और मिलने के संचालन दोनों में सममित विवरण है: यदि {{math|(''A<sub>i</sub>'',''B<sub>i</sub>'')}} कट्स के किसी भी परिवार में कट्स है, तो इन कट्स का मिलन कट है {{math|(''L'',''L''<sup>u</sup>)}} कहाँ {{math|1=''L'' = ∩<sub>''i''</sub>''A<sub>i</sub>''}}, और जुड़ना ही कट है {{math|(''U''<sup>l</sup>,''U'')}} कहाँ {{math|1=''U'' = ∩<sub>''i''</sub>''B<sub>i</sub>''}}.{{sfnp|MacNeille|1937}}
 ==उदाहरण==
-अगर <math>\Q</math> तर्कसंगत संख्याओं का सेट है, जिसे सामान्य संख्यात्मक क्रम के साथ पूरी तरह से व्यवस्थित सेट के रूप में देखा जाता है, फिर डेडेकाइंड-मैकनील के प्रत्येक तत्व को पूरा किया जाता है <math>\Q</math> इसे डेडेकाइंड कट और डेडेकाइंड-मैकनील के पूरा होने के रूप में देखा जा सकता है <math>\Q</math> दो अतिरिक्त मानों के साथ वास्तविक संख्याओं पर कुल क्रम है <math>\pm\infty</math>.<ref>{{harvtxt|Davey| Priestley|2002}}, Example 7.44(1), p.&nbsp;168; {{harvtxt|Schröder|2003}}, Example 5.3.3(2), p.&nbsp;120.</ref>
+अगर <math>\Q</math> तर्कसंगत संख्याओं का समूह है, जिसे सामान्य संख्यात्मक क्रम के साथ पूरी तरह से व्यवस्थित समूह के रूप में देखा जाता है, फिर डेडेकाइंड-मैकनील के प्रत्येक तत्व को पूरा किया जाता है <math>\Q</math> इसे डेडेकाइंड कट और डेडेकाइंड-मैकनील के पूरा होने के रूप में देखा जा सकता है <math>\Q</math> दो अतिरिक्त मानों के साथ वास्तविक संख्याओं पर कुल क्रम है <math>\pm\infty</math>.<ref>{{harvtxt|Davey| Priestley|2002}}, Example 7.44(1), p.&nbsp;168; {{harvtxt|Schröder|2003}}, Example 5.3.3(2), p.&nbsp;120.</ref>
-अगर {{mvar|S}} एक [[एंटीचेन]] है (तत्वों का एक सेट जिनमें से कोई भी दो तुलनीय नहीं हैं) तो डेडेकाइंड-मैकनील का समापन {{mvar|S}} के होते हैं {{mvar|S}} स्वयं दो अतिरिक्त तत्वों के साथ, एक निचला तत्व जो प्रत्येक तत्व के नीचे है {{mvar|S}} और एक शीर्ष तत्व जो प्रत्येक तत्व के ऊपर है {{mvar|S}}.<ref>{{harvtxt|Davey| Priestley|2002}}, Example 7.44(2), p.&nbsp;168.</ref>
+अगर {{mvar|S}} एक [[एंटीचेन]] है (तत्वों का एक समूह जिनमें से कोई भी दो तुलनीय नहीं है) तो डेडेकाइंड-मैकनील का समापन {{mvar|S}} के होते है {{mvar|S}} स्वयं दो अतिरिक्त तत्वों के साथ, एक निचला तत्व जो प्रत्येक तत्व के नीचे है {{mvar|S}} और एक शीर्ष तत्व जो प्रत्येक तत्व के ऊपर है {{mvar|S}}.<ref>{{harvtxt|Davey| Priestley|2002}}, Example 7.44(2), p.&nbsp;168.</ref>
-अगर {{mvar|O}} वस्तुओं का कोई भी सीमित सेट है, और {{mvar|A}} वस्तुओं के लिए एकात्मक विशेषताओं का कोई सीमित सेट है {{mvar|O}}, तो कोई ऊंचाई दो का आंशिक क्रम बना सकता है जिसमें आंशिक क्रम के तत्व वस्तुएं और विशेषताएं हैं, और जिसमें {{math|''x'' ≤ ''y''}} कब {{mvar|x}} एक वस्तु है जिसमें विशेषता है{{mvar|y}}. इस तरह से परिभाषित आंशिक आदेश के लिए, डेडेकाइंड-मैकनील का समापन {{mvar|S}} को एक अवधारणा जालक के रूप में जाना जाता है, और यह [[औपचारिक अवधारणा विश्लेषण]] के क्षेत्र में एक केंद्रीय भूमिका निभाता है।{{sfnp|Ganter|Kuznetsov|1998}}
+अगर {{mvar|O}} वस्तुओं का कोई भी सीमित समूह है, और {{mvar|A}} वस्तुओं के लिए एकात्मक विशेषताओं का कोई सीमित समूह है {{mvar|O}}, तो कोई ऊंचाई दो का आंशिक क्रम बना सकता है जिसमें आंशिक क्रम के तत्व वस्तुएं और विशेषताएं है, और जिसमें {{math|''x'' ≤ ''y''}} कब {{mvar|x}} एक वस्तु है जिसमें विशेषता है{{mvar|y}}. इस तरह से परिभाषित आंशिक आदेश के लिए, डेडेकाइंड-मैकनील का समापन {{mvar|S}} को एक अवधारणा नियम के रूप में जाना जाता है, और यह [[औपचारिक अवधारणा विश्लेषण]] के क्षेत्र में एक केंद्रीय भूमिका निभाता है।{{sfnp|Ganter|Kuznetsov|1998}}
 ==गुण==
-डेडेकाइंड-मैकनील आंशिक रूप से ऑर्डर किए गए सेट को पूरा करता है {{mvar|S}} सबसे छोटी पूर्ण जाली है {{mvar|S}} इसमें सन्निहित है, इस अर्थ में कि, यदि {{mvar|L}} किसी भी जाली का पूरा होना है {{mvar|S}}, तो डेडेकाइंड-मैकनील पूर्णता आंशिक रूप से ऑर्डर किया गया उपसमुच्चय है {{mvar|L}}.<ref name="smallest-completion">{{harvtxt|Bishop|1978}}; {{harvtxt|Schröder|2003}}, Theorem 5.3.8, p.&nbsp;121.</ref> कब {{mvar|S}} परिमित है, इसकी पूर्णता भी परिमित है, और सभी परिमित पूर्ण जालकों में तत्वों की संख्या सबसे कम है {{mvar|S}}.{{sfnp|Ganter|Kuznetsov|1998}}
+डेडेकाइंड-मैकनील आंशिक रूप से अनुक्रम किए गए समूह को पूरा करता है {{mvar|S}} सबसे छोटी संपूर्ण नियम है {{mvar|S}} इसमें सन्निहित है, इस अर्थ में कि, यदि {{mvar|L}} किसी भी नियम का पूरा होना है {{mvar|S}}, तो डेडेकाइंड-मैकनील संपूर्णता आंशिक रूप से अनुक्रम किया गया उपसमुच्चय है {{mvar|L}}.<ref name="smallest-completion">{{harvtxt|Bishop|1978}}; {{harvtxt|Schröder|2003}}, Theorem 5.3.8, p.&nbsp;121.</ref> कब {{mvar|S}} परिमित है, इसकी संपूर्णता भी परिमित है, और सभी परिमित संपूर्ण नियमों में तत्वों की संख्या सबसे कम है {{mvar|S}}.{{sfnp|Ganter|Kuznetsov|1998}}
-आंशिक रूप से ऑर्डर किया गया सेट {{mvar|S}} डेडेकाइंड-मैकनेइल पूर्णता में जॉइन-डेंस और मीट-डेंस है; अर्थात्, पूर्णता का प्रत्येक तत्व कुछ तत्वों के समूह का जोड़ है {{mvar|S}}, और इसमें तत्वों के कुछ सेट का मिलन भी है {{mvar|S}}.<ref>{{harvtxt|Schröder|2003}}, Proposition 5.3.7, p.&nbsp;121.</ref> डेडेकाइंड-मैकनील पूर्णता को पूर्णताओं में से एक माना जाता है {{mvar|S}} इस संपत्ति द्वारा.{{sfnp|Schmidt|1956}}
+आंशिक रूप से अनुक्रम किया गया समूह {{mvar|S}} डेडेकाइंड-मैकनेइल संपूर्णता में जॉइन-डेंस और मीट-डेंस है, अर्थात्, संपूर्णता का प्रत्येक तत्व कुछ तत्वों के समूह का जोड़ है {{mvar|S}}, और इसमें तत्वों के कुछ समूह का मिलन भी है {{mvar|S}}.<ref>{{harvtxt|Schröder|2003}}, Proposition 5.3.7, p.&nbsp;121.</ref> डेडेकाइंड-मैकनील संपूर्णता को संपूर्णताओं में से एक माना जाता है {{mvar|S}} इस संपत्ति द्वारा.{{sfnp|Schmidt|1956}}
-[[बूलियन बीजगणित (संरचना)]] का डेडेकाइंड-मैकनील समापन एक [[पूर्ण बूलियन बीजगणित]] है; इस परिणाम को [[ वालेरी इवानोविच ग्लिवेंको ]] और [[मार्शल स्टोन]] के बाद ग्लिवेंको-स्टोन प्रमेय के रूप में जाना जाता है।<ref>{{harvtxt|Birkhoff|1995}}, Theorem 27, p.&nbsp;130.</ref> इसी प्रकार, एक [[अवशिष्ट जाली]] का डेडेकाइंड-मैकनील पूरा होना एक पूर्ण अवशिष्ट जाली है।{{sfnp|Gabbay|Shehtman|Skvortsov|2009}} हालाँकि, एक वितरणात्मक जाली का पूरा होना स्वयं वितरणात्मक नहीं होना चाहिए, और एक [[मॉड्यूलर जाली]] का पूरा होना मॉड्यूलर नहीं रह सकता है।<ref>{{harvtxt|Cotlar|1944}}; {{harvtxt|Funayama|1944}}.</ref>
+[[बूलियन बीजगणित (संरचना)]] का डेडेकाइंड-मैकनील समापन एक [[पूर्ण बूलियन बीजगणित|संपूर्ण बूलियन बीजगणित]] है, इस परिणाम को [[ वालेरी इवानोविच ग्लिवेंको ]] और [[मार्शल स्टोन]] के बाद ग्लिवेंको-स्टोन प्रमेय के रूप में जाना जाता है।<ref>{{harvtxt|Birkhoff|1995}}, Theorem 27, p.&nbsp;130.</ref> इसी प्रकार, एक [[अवशिष्ट जाली|अवशिष्ट नियम]] का डेडेकाइंड-मैकनील पूरा होना एक संपूर्ण अवशिष्ट नियम है।{{sfnp|Gabbay|Shehtman|Skvortsov|2009}} चूँकि, एक वितरणात्मक नियम का पूरा होना स्वयं वितरणात्मक नहीं होना चाहिए, और एक [[मॉड्यूलर जाली|मॉड्यूलर नियम]] का पूरा होना मॉड्यूलर नहीं रह सकता है।<ref>{{harvtxt|Cotlar|1944}}; {{harvtxt|Funayama|1944}}.</ref>
-डेडेकाइंड-मैकनील पूर्णता स्व-दोहरी है: आंशिक क्रम के [[द्वैत (आदेश सिद्धांत)]] का पूरा होना पूर्णता के दोहरे के समान है।{{sfnp|Birkhoff|1995}}
+डेडेकाइंड-मैकनील संपूर्णता स्व-दोहरी है: आंशिक क्रम के [[द्वैत (आदेश सिद्धांत)]] का पूरा होना संपूर्णता के दोहरे के समान है।{{sfnp|Birkhoff|1995}}
 डेडेकाइंड-मैकनील का समापन {{mvar|S}} का क्रम आयाम भी वैसा ही है {{mvar|S}} अपने आप।<ref>This result is frequently attributed to an unpublished 1961 Harvard University honors thesis by K. A. Baker, "Dimension, join-independence and breadth in partially ordered sets". It was published by {{harvtxt|Novák|1969}}.</ref>
-आंशिक रूप से ऑर्डर किए गए सेटों और आंशिक रूप से ऑर्डर किए गए सेटों के बीच मोनोटोनिक कार्यों की [[श्रेणी (गणित)]] में, पूर्ण जाली ऑर्डर-एम्बेडिंग के लिए [[इंजेक्शन वस्तु]] बनाती है, और डेडेकाइंड-मैकनील पूरा करती है {{mvar|S}} का [[इंजेक्शन पतवार]] है{{mvar|S}}.{{sfnp|Banaschewski|Bruns|1967}}
+आंशिक रूप से अनुक्रम किए गए समूहों और आंशिक रूप से अनुक्रम किए गए समूहों के बीच मोनोटोनिक कार्यों की [[श्रेणी (गणित)]] में, संपूर्ण नियम अनुक्रम-अंतर्निहित के लिए [[इंजेक्शन वस्तु]] बनाती है, और डेडेकाइंड-मैकनील पूरा करती है {{mvar|S}} का [[इंजेक्शन पतवार]] है{{mvar|S}}.{{sfnp|Banaschewski|Bruns|1967}}
 ==एल्गोरिदम==
-कई शोधकर्ताओं ने एक सीमित आंशिक रूप से ऑर्डर किए गए सेट को पूरा करने वाले डेडेकाइंड-मैकनील के निर्माण के लिए एल्गोरिदम की जांच की है। डेडेकाइंड-मैकनील पूर्णता उस आंशिक क्रम से तेजी से बड़ी हो सकती है, जिससे यह आता है,{{sfnp|Ganter|Kuznetsov|1998}} और ऐसे एल्गोरिदम के लिए समय सीमा आम तौर पर [[आउटपुट-संवेदनशील एल्गोरिदम]] में बताई जाती है|आउटपुट-संवेदनशील तरीके से, संख्या पर निर्भर करता है {{mvar|n}} इनपुट के तत्वों का आंशिक क्रम, और संख्या पर {{mvar|c}} इसके पूर्ण होने के तत्वों का.
+कई शोधकर्ताओं ने एक सीमित आंशिक रूप से अनुक्रम किए गए समूह को पूरा करने वाले डेडेकाइंड-मैकनील के निर्माण के लिए एल्गोरिदम की जांच की है। डेडेकाइंड-मैकनील संपूर्णता उस आंशिक क्रम से तेजी से बड़ी हो सकती है, जिससे यह आता है,{{sfnp|Ganter|Kuznetsov|1998}} और ऐसे एल्गोरिदम के लिए समय सीमा आम तौर पर [[आउटपुट-संवेदनशील एल्गोरिदम]] में बताई जाती है|आउटपुट-संवेदनशील तरीके से, संख्या पर निर्भर करता है {{mvar|n}} इनपुट के तत्वों का आंशिक क्रम, और संख्या पर {{mvar|c}} इसके संपूर्ण होने के तत्वों का.
-===कटौती के सेट का निर्माण===
+===अलगाव के समूह का निर्माण===
-{{harvtxt|Ganter|Kuznetsov|1998}} एक वृद्धिशील एल्गोरिदम का वर्णन करें, जिसमें एक समय में एक तत्व जोड़कर इनपुट आंशिक क्रम बनाया जाता है; प्रत्येक चरण में, छोटे आंशिक क्रम की पूर्णता को बड़े आंशिक क्रम की पूर्णता के रूप में विस्तारित किया जाता है। उनकी पद्धति में, पूर्णता को कटौती की एक स्पष्ट सूची द्वारा दर्शाया जाता है। संवर्धित आंशिक क्रम का प्रत्येक कट, उस कट को छोड़कर जिसके दो सेट नए तत्व में प्रतिच्छेद करते हैं, या तो पिछले आंशिक क्रम से एक कट है या पिछले से कट के एक या दूसरे पक्ष में नया तत्व जोड़कर बनता है। आंशिक क्रम, इसलिए उनके एल्गोरिदम को यह निर्धारित करने के लिए कि कौन से कट हैं, केवल इस फॉर्म के सेट के जोड़े का परीक्षण करने की आवश्यकता है। आंशिक क्रम को पूरा करने के लिए एक तत्व जोड़ने के लिए उनकी विधि का उपयोग करने का समय है {{math|''O''(''cnw'')}} कहाँ {{mvar|w}} आंशिक क्रम की चौड़ाई है, यानी, इसके सबसे बड़े एंटीचेन का आकार। इसलिए, किसी दिए गए आंशिक आदेश के पूरा होने की गणना करने का समय है {{math|1=''O''(''cn''<sup>2</sup>''w'') = O(''cn''<sup>3</sup>)}}.{{sfnp|Ganter|Kuznetsov|1998}}
+{{harvtxt|Ganter|Kuznetsov|1998}} एक वृद्धिशील एल्गोरिदम का वर्णन करें, जिसमें एक समय में एक तत्व जोड़कर इनपुट आंशिक क्रम बनाया जाता है, प्रत्येक चरण में, छोटे आंशिक क्रम की संपूर्णता को बड़े आंशिक क्रम की संपूर्णता के रूप में विस्तारित किया जाता है। उनकी पद्धति में, संपूर्णता को अलगाव की एक स्पष्ट सूची द्वारा दर्शाया जाता है। संवर्धित आंशिक क्रम का प्रत्येक कट, उस कट को छोड़कर जिसके दो समूह नए तत्व में प्रतिच्छेद करते है, या तो पिछले आंशिक क्रम से एक कट है या पिछले से कट के एक या दूसरे पक्ष में नया तत्व जोड़कर बनता है। आंशिक क्रम, इसलिए उनके एल्गोरिदम को यह निर्धारित करने के लिए कि कौन से कट है, केवल इस फॉर्म के समूह के जोड़े का परीक्षण करने की आवश्यकता है। आंशिक क्रम को पूरा करने के लिए एक तत्व जोड़ने के लिए उनकी विधि का उपयोग करने का समय है {{math|''O''(''cnw'')}} कहाँ {{mvar|w}} आंशिक क्रम की चौड़ाई है, यानी, इसके सबसे बड़े एंटीचेन का आकार। इसलिए, किसी दिए गए आंशिक आदेश के पूरा होने की गणना करने का समय है {{math|1=''O''(''cn''<sup>2</sup>''w'') = O(''cn''<sup>3</sup>)}}.{{sfnp|Ganter|Kuznetsov|1998}}
-जैसा {{harvtxt|Jourdan|Rampon|Jard|1994}} ध्यान दें, आंशिक रूप से ऑर्डर किए गए सेट में सभी कटों को सूचीबद्ध करने की समस्या को एक सरल समस्या के विशेष मामले के रूप में तैयार किया जा सकता है, सभी अधिकतम एंटीचेन को एक अलग आंशिक रूप से ऑर्डर किए गए सेट में सूचीबद्ध करने की। अगर {{mvar|P}} कोई आंशिक रूप से ऑर्डर किया गया सेट है, मान लीजिए {{mvar|Q}} एक आंशिक क्रम हो जिसके तत्वों की दो प्रतियां हों {{mvar|P}}: प्रत्येक तत्व के लिए {{mvar|x}} का {{mvar|P}}, {{mvar|Q}} में दो तत्व शामिल हैं {{math|''x''<sub>0</sub>}} और {{math|''x''<sub>1</sub>}}, साथ {{math|''x<sub>i</sub>'' < ''y<sub>j</sub>''}} अगर और केवल अगर {{math|''x'' < ''y''}} और {{math|''i'' < ''j''}}. फिर कटौती होती है {{mvar|P}} अधिकतम एंटीचेन के साथ एक-के-लिए-एक से मेल खाता है {{mvar|Q}}: कट के निचले सेट के तत्व एक एंटीचेन में सबस्क्रिप्ट 0 वाले तत्वों के अनुरूप होते हैं, और कट के ऊपरी सेट के तत्व एक एंटीचेन में सबस्क्रिप्ट 1 वाले तत्वों के अनुरूप होते हैं। जॉर्डन एट अल. अधिकतम एंटीचेन खोजने के लिए एक एल्गोरिदम का वर्णन करें, जिसे सभी कटों को सूचीबद्ध करने की समस्या पर लागू किया जाए {{mvar|P}}, समय लेता है {{math|1=''O''(''c''(''nw'' + ''w''<sup>3</sup>))}}, के एल्गोरिदम में सुधार {{harvtxt|Ganter|Kuznetsov|1998}} जब चौड़ाई {{mvar|w}} छोटा है।{{sfnp|Jourdan|Rampon|Jard|1994}} वैकल्पिक रूप से, एक अधिकतम एंटीचेन {{mvar|Q}} [[तुलनीयता ग्राफ]]़ में [[अधिकतम स्वतंत्र सेट]] के समान है {{mvar|Q}}, या तुलनीयता ग्राफ के पूरक में एक [[अधिकतम क्लिक]], इसलिए क्लिक समस्या या स्वतंत्र सेट समस्या के लिए एल्गोरिदम को डेडेकाइंड-मैकनेइल पूर्णता समस्या के इस संस्करण पर भी लागू किया जा सकता है।<ref>For the equivalence between algorithms for antichains in partial orders and for independent sets in comparability graphs, see {{harvtxt|Cameron|1985}}, p. 251.</ref>
+जैसा {{harvtxt|Jourdan|Rampon|Jard|1994}} ध्यान दें, आंशिक रूप से अनुक्रम किए गए समूह में सभी कटों को सूचीबद्ध करने की समस्या को एक सरल समस्या के विशेष मामले के रूप में तैयार किया जा सकता है, सभी अधिकतम एंटीचेन को एक अलग आंशिक रूप से अनुक्रम किए गए समूह में सूचीबद्ध करने की। अगर {{mvar|P}} कोई आंशिक रूप से अनुक्रम किया गया समूह है, मान लीजिए {{mvar|Q}} एक आंशिक क्रम हो जिसके तत्वों की दो प्रतियां हों {{mvar|P}}: प्रत्येक तत्व के लिए {{mvar|x}} का {{mvar|P}}, {{mvar|Q}} में दो तत्व शामिल है {{math|''x''<sub>0</sub>}} और {{math|''x''<sub>1</sub>}}, साथ {{math|''x<sub>i</sub>'' < ''y<sub>j</sub>''}} अगर और केवल अगर {{math|''x'' < ''y''}} और {{math|''i'' < ''j''}}. फिर अलगाव होती है {{mvar|P}} अधिकतम एंटीचेन के साथ एक-के-लिए-एक से मेल खाता है {{mvar|Q}}: कट के निचले समूह के तत्व एक एंटीचेन में सबस्क्रिप्ट 0 वाले तत्वों के अनुरूप होते है, और कट के ऊपरी समूह के तत्व एक एंटीचेन में सबस्क्रिप्ट 1 वाले तत्वों के अनुरूप होते है। जॉर्डन एट अल. अधिकतम एंटीचेन खोजने के लिए एक एल्गोरिदम का वर्णन करें, जिसे सभी कटों को सूचीबद्ध करने की समस्या पर लागू किया जाए {{mvar|P}}, समय लेता है {{math|1=''O''(''c''(''nw'' + ''w''<sup>3</sup>))}}, के एल्गोरिदम में सुधार {{harvtxt|Ganter|Kuznetsov|1998}} जब चौड़ाई {{mvar|w}} छोटा है।{{sfnp|Jourdan|Rampon|Jard|1994}} वैकल्पिक रूप से, एक अधिकतम एंटीचेन {{mvar|Q}} [[तुलनीयता ग्राफ]]़ में [[अधिकतम स्वतंत्र सेट|अधिकतम स्वतंत्र समूह]] के समान है {{mvar|Q}}, या तुलनीयता ग्राफ के पूरक में एक [[अधिकतम क्लिक]], इसलिए क्लिक समस्या या स्वतंत्र समूह समस्या के लिए एल्गोरिदम को डेडेकाइंड-मैकनेइल संपूर्णता समस्या के इस संस्करण पर भी लागू किया जा सकता है।<ref>For the equivalence between algorithms for antichains in partial orders and for independent sets in comparability graphs, see {{harvtxt|Cameron|1985}}, p. 251.</ref>
 ===कवरिंग ग्राफ़ का निर्माण===
-डेडेकाइंड-मैकनील पूर्णता का संक्रमणीय कमी या कवरिंग ग्राफ इसके तत्वों के बीच क्रम संबंध का संक्षिप्त तरीके से वर्णन करता है:
+डेडेकाइंड-मैकनील संपूर्णता का संक्रमणीय कमी या कवरिंग ग्राफ इसके तत्वों के बीच क्रम संबंध का संक्षिप्त तरीके से वर्णन करता है:
-कट के प्रत्येक [[पड़ोस (ग्राफ सिद्धांत)]] को कट के ऊपरी या निचले सेट से मूल आंशिक क्रम के एक तत्व को हटाना होगा, इसलिए प्रत्येक शीर्ष पर अधिकतम {{mvar|n}} पड़ोसियों। इस प्रकार, कवरिंग ग्राफ़ है {{mvar|c}} शीर्ष और अधिक से अधिक {{mvar|''cn''/2}} पड़ोसियों, एक संख्या जो की तुलना में बहुत छोटी हो सकती है {{mvar|''c''<sup>2</sup>}} एक मैट्रिक्स में प्रविष्टियाँ जो तत्वों के बीच सभी जोड़ीवार तुलनाओं को निर्दिष्ट करती हैं। {{harvtxt|Nourine|Raynaud|1999}}दिखाएं कि इस कवरिंग ग्राफ़ की कुशलतापूर्वक गणना कैसे करें; अधिक सामान्यतः, यदि {{mvar|B}} सेट का कोई भी परिवार है, वे दिखाते हैं कि उपसमुच्चय के संघों की जाली के कवरिंग ग्राफ की गणना कैसे करें {{mvar|B}}. डेडेकाइंड-मैकनील जाली के मामले में, {{mvar|B}} को प्रमुख आदर्शों के [[पूरक सेट]]ों के परिवार और के उपसमूहों के संघ के रूप में लिया जा सकता है {{mvar|B}} कट्स के निचले सेट के पूरक हैं। उनके एल्गोरिदम का मुख्य विचार उपसमुच्चय के संघ उत्पन्न करना है {{mvar|B}} वृद्धिशील रूप से (प्रत्येक सेट के लिए {{mvar|B}}, पहले से उत्पन्न सभी यूनियनों के साथ अपना संघ बनाते हुए), एक त्रि में सेट के परिणामी परिवार का प्रतिनिधित्व करते हैं, और कवरिंग संबंध में आसन्नता के लिए सेट के कुछ उम्मीदवार जोड़े का परीक्षण करने के लिए त्रि प्रतिनिधित्व का उपयोग करते हैं; समय लगता है {{math|''O''(''cn''<sup>2</sup>)}}. बाद के काम में, उन्हीं लेखकों ने दिखाया कि एल्गोरिदम को समान कुल समय सीमा के साथ पूरी तरह से वृद्धिशील (एक समय में आंशिक क्रम में तत्वों को जोड़ने में सक्षम) बनाया जा सकता है।{{sfnp|Nourine|Raynaud|2002}}
+कट के प्रत्येक [[पड़ोस (ग्राफ सिद्धांत)]] को कट के ऊपरी या निचले समूह से मूल आंशिक क्रम के एक तत्व को हटाना होगा, इसलिए प्रत्येक शीर्ष पर अधिकतम {{mvar|n}} पड़ोसियों। इस प्रकार, कवरिंग ग्राफ़ है {{mvar|c}} शीर्ष और अधिक से अधिक {{mvar|''cn''/2}} पड़ोसियों, एक संख्या जो की तुलना में बहुत छोटी हो सकती है {{mvar|''c''<sup>2</sup>}} एक मैट्रिक्स में प्रविष्टियाँ जो तत्वों के बीच सभी जोड़ीवार तुलनाओं को निर्दिष्ट करती है। {{harvtxt|Nourine|Raynaud|1999}}दिखाएं कि इस कवरिंग ग्राफ़ की कुशलतापूर्वक गणना कैसे करें, अधिक सामान्यतः, यदि {{mvar|B}} समूह का कोई भी परिवार है, वे दिखाते है कि उपसमुच्चय के संघों की नियम के कवरिंग ग्राफ की गणना कैसे करें {{mvar|B}}. डेडेकाइंड-मैकनील नियम के मामले में, {{mvar|B}} को प्रमुख आदर्शों के [[पूरक सेट|पूरक समूह]]ों के परिवार और के उपसमूहों के संघ के रूप में लिया जा सकता है {{mvar|B}} कट्स के निचले समूह के पूरक है। उनके एल्गोरिदम का मुख्य विचार उपसमुच्चय के संघ उत्पन्न करना है {{mvar|B}} वृद्धिशील रूप से (प्रत्येक समूह के लिए {{mvar|B}}, पहले से उत्पन्न सभी यूनियनों के साथ अपना संघ बनाते हुए), एक त्रि में समूह के परिणामी परिवार का प्रतिनिधित्व करते है, और कवरिंग संबंध में आसन्नता के लिए समूह के कुछ उम्मीदवार जोड़े का परीक्षण करने के लिए त्रि प्रतिनिधित्व का उपयोग करते है, समय लगता है {{math|''O''(''cn''<sup>2</sup>)}}. बाद के काम में, उन्हीं लेखकों ने दिखाया कि एल्गोरिदम को समान कुल समय सीमा के साथ पूरी तरह से वृद्धिशील (एक समय में आंशिक क्रम में तत्वों को जोड़ने में सक्षम) बनाया जा सकता है।{{sfnp|Nourine|Raynaud|2002}}
 ==टिप्पणियाँ==

Anonymous

Search

डेडेकाइंड-मैकनील समापन: Difference between revisions

Namespaces

More

Page actions

Revision as of 00:48, 10 July 2023

Contents

अनुक्रम अंतर्निहित और नियम संपूर्णता

परिभाषा

उदाहरण

गुण

एल्गोरिदम

अलगाव के समूह का निर्माण

कवरिंग ग्राफ़ का निर्माण

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

डेडेकाइंड-मैकनील समापन: Difference between revisions

Revision as of 00:48, 10 July 2023

अनुक्रम अंतर्निहित और नियम संपूर्णता

परिभाषा

उदाहरण

गुण

एल्गोरिदम

अलगाव के समूह का निर्माण

कवरिंग ग्राफ़ का निर्माण

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories