डेडेकाइंड-मैकनील समापन

"डेडेकाइंड पूर्णता" redirects here. For कुछ अन्य संबंधित अवधारणाएँ, see डेडेकाइंड पूर्णता.

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

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

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

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

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

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

परिभाषा

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

(A^u)^l = A,

इसे शामिल करके आदेश दिया गया है: A ≤ B संपूर्णता में यदि और केवल यदि A ⊆ B संपत्तियां।

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

वैकल्पिक परिभाषा के साथ, संपूर्ण नियम के जुड़ने और मिलने के संचालन दोनों में सममित विवरण है: यदि (A_i,B_i) कट्स के किसी भी परिवार में कट्स है, तो इन कट्स का मिलन कट है (L,L^u) कहाँ L = ∩_iA_i, और जुड़ना ही कट है (U^l,U) कहाँ U = ∩_iB_i.

उदाहरण

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

गुण

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

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

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

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

एल्गोरिदम

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

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

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

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

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

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

संदर्भ

• 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