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

"डेडेकाइंड पूर्णता" 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

कलन विधि

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

संख्याओं के समूह का निर्माण

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

आंशिक रूप से अनुक्रम किए गए समूह में सभी संख्याओंों को सूचीबद्ध करने की समस्या को एक सरल समस्या के विशेष स्थिति के रूप में तैयार किया जा सकता है, सभी अधिकतम श्रंखला को एक अलग आंशिक रूप से अनुक्रम किए गए समूह में सूचीबद्ध किया जाता है। यदि 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³))। वैकल्पिक रूप से, एक अधिकतम श्रंखला Q तुलनीयता आलेख में अधिकतम स्वतंत्र समूह के समान होता है Q, या तुलनीयता आलेख में एक पूरक होता है, इसलिए स्वतंत्र समूह समस्या के लिए कलन विधि को डेडेकाइंड-मैकनेइल संपूर्णता समस्या के इस संस्करण पर भी लागू किया जा सकता है।

आवरण आलेख का निर्माण

डेडेकाइंड-मैकनील संपूर्णता संक्रमणीय या आवरण आलेख के तत्वों के बीच क्रम संबंध का संक्षिप्त विधि का वर्णन करता है: संख्याओं के प्रत्येक आलेख सिद्धांत को संख्याओं के ऊपरी या निचले समूह से मूल आंशिक क्रम के तत्व को हटाना होता है, इसलिए प्रत्येक शीर्ष पर अधिकतम होता है n, इस प्रकार, आवरण आलेख होता है c शीर्ष और cn/2, एक संख्या जो की तुलना में बहुत छोटी हो सकती है c² एक आव्यूह में प्रविष्टियाँ जो तत्वों के बीच सभी जोड़ तुलनाओं को निर्दिष्ट करती है। नौरीन & रेनॉड (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