वितरण जाली

गणित में, एक वितरण नियम एक नियम (क्रम) होता है जिसमें एक दूसरे के ऊपर वितरण को मिलाने और मिलने की संक्रियाएँ होती हैं। ऐसी संरचनाओं के प्रोटोटाइपिकल उदाहरण समुच्चय का संग्रह हैं जिसके लिए समुच्चय यूनियन (समुच्चय सिद्धांत) और प्रतिच्छेदन (समुच्चय सिद्धांत) द्वारा लैटिस संचालन दिया जा सकता है। वास्तव में, समुच्चय के ये नियम पूरी तरह से दृश्यावली का वर्णन करते हैं: प्रत्येक वितरणात्मक जालक-समरूपता के क्रम तक- समुच्चय के ऐसे नियम के रूप में दिया जाता है।

परिभाषा

स्वच्छंद लैटिस के मामले में, कोई भी वितरणात्मक लैटिस एल पर विचार करना चुन सकता है या तो आदेश सिद्धांत या सार्वभौमिक बीजगणित की संरचना के रूप में। लैटिस (आदेश) पर लेख में दोनों विचारों और उनके पारस्परिक पत्राचार पर चर्चा की गई है। वर्तमान स्थिति में बीजगणितीय विवरण अधिक सुविधाजनक प्रतीत होता है।

एक लैटिस (एल, ∨, ∧) 'वितरण' है यदि निम्नलिखित अतिरिक्त पहचान एल में सभी एक्स, वाई, और जेड के लिए रखती है:

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)।

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

x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) एल में सभी x, y, और z के लिए।

प्रत्येक लैटिस में, p≤q को हमेशा की तरह p∧q=p, असमानता x ∧ (y ∨ z) ≥ (x ∧ y) ∨ (x ∧ z) के साथ-साथ इसकी दोहरी असमानता x ∨ (y) को परिभाषित करता है। ∧ z) ≤ (x ∨ y) ∧ (x ∨ z)। एक नियम वितरणात्मक होता है यदि विपरीत असमानताओं में से एक भी धारण करता है।

आदेश सिद्धांत की अन्य वितरण स्थितियों के लिए इस स्थिति के संबंध के बारे में अधिक जानकारी वितरण पर लेख (आदेश सिद्धांत) में पाई जा सकती है।

आकारिता

वितरणात्मक लैटिस का एक रूपवाद सिर्फ एक लैटिस समरूपता है जैसा कि लैटिस (आदेश) पर लेख में दिया गया है, अर्थात एक ऐसा कार्य जो दो लैटिस संचालन के साथ संगत है। क्योंकि लैटिस का ऐसा रूपवाद लैटिस संरचना को संरक्षित करता है, इसके परिणामस्वरूप यह वितरण को भी संरक्षित करेगा (और इस प्रकार वितरणात्मक लैटिस का एक रूपवाद होगा)।

उदाहरण

Error creating thumbnail:

यंग की जाली

वितरणात्मक लैटिस सर्वव्यापी हैं, बल्कि विशिष्ट संरचनाएं भी हैं। जैसा कि पहले ही उल्लेख किया गया है कि वितरणात्मक लैटिस के लिए मुख्य उदाहरण समुच्चय के लैटिस हैं, जहां सामान्य समुच्चय सिद्धांतपरक संचालन द्वारा सम्मिलित होना और मिलना दिया जाता है। और उदाहरणों में सम्मिलित हैं:

• अधिकांश लॉजिक्स का लिंडेनबाउम-टार्स्की बीजगणित जो तार्किक संयोजन और तार्किक संयोजन का समर्थन करता है, एक वितरणात्मक लैटिस है, अर्थात और या इसके विपरीत वितरित करता है।
• प्रत्येक बूलियन बीजगणित (संरचना) एक वितरणात्मक लैटिस है।
• हर हेटिंग बीजगणित एक वितरण नियम है। विशेष रूप से इसमें सभी पूर्ण हेटिंग बीजगणित सम्मिलित हैं और इसलिए टोपोलॉजिकल स्पेस स्थान के सभी खुले समुच्चय लैटिस सम्मिलित हैं। यह भी ध्यान दें कि हेटिंग बीजगणित को अंतर्ज्ञानवादी तर्क के लिंडेनबाम बीजगणित के रूप में देखा जा सकता है, जो उन्हें पहले उदाहरण का एक विशेष मामला बनाता है।
• हर कुल आदेश एक वितरण पॉलीटॉप है जिसमें ज्वाइन के रूप में मैक्सिमम और मीट के रूप में मिन है।
• प्राकृतिक संख्या एक (सशर्त रूप से पूर्ण) वितरण लैटिस बनाती है, जो सबसे बड़े सामान्य विभाजक को पूरा करती है और कम से कम सामान्य गुणक को जोड़ती है। इस लैटिस में एक न्यूनतम तत्व भी है, जिसका नाम 1 है, जो जुड़ने के लिए पहचान तत्व के रूप में कार्य करता है।
• एक धनात्मक पूर्णांक n को देखते हुए, n के सभी धनात्मक विभाजकों का समुच्चय एक वितरण नियम बनाता है, जिसमें सबसे बड़ा समापवर्तक मिलता है और लघुतम समापवर्त्य जुड़ता है। यह एक बूलियन बीजगणित है यदि और केवल यदि n वर्ग-मुक्त पूर्णांक वर्ग-मुक्त है।
• एक रिज स्पेस लैटिस-ऑर्डर्ड वेक्टर स्पेस एक वितरक लैटिस है।
• युवा आरेख के समावेशन क्रम द्वारा दिया गया यंग का नियम विभाजन (संख्या सिद्धांत) का प्रतिनिधित्व करने वाले आरेख एक वितरणात्मक लैटिस है।
• एक वितरण पॉलीटोप के बिंदु (एक उत्तल पॉलीटोप को समन्वयित न्यूनतम और समन्वयित अधिकतम संचालन के तहत बंद किया जाता है), इन दो कार्यों के साथ लैटिस के संचालन में सम्मिलित होने और मिलने के रूप में।

जालक सिद्धांत के विकास के आरंभ में चार्ल्स एस. पियर्स का मानना ​​था कि सभी जालक वितरणात्मक होते हैं, अर्थात वितरण शेष जाली अभिगृहीतों से होता है। [4] [5] हालांकि, श्रोडर, वोइग्ट, (डी) लुरोथ, कोर्सेल्ट, [6] और डेडेकाइंड द्वारा स्वतंत्रता के प्रमाण दिए गए थे। [4]

विशेषता गुण

उपरोक्त परिभाषा के विभिन्न समतुल्य योग उपस्थित हैं। उदाहरण के लिए, L वितरणात्मक है यदि और केवल यदि निम्नलिखित L में सभी तत्वों x, y, z के लिए है:

(x$\wedge$y)$\vee$(y$\wedge$z)$\vee$(z$\wedge$x) = (x$\vee$y)$\wedge$(y$\vee$z)$\wedge$(z$\vee$x).

इसी प्रकार, L वितरणात्मक है यदि और केवल यदि

x$\wedge$z = y$\wedge$z and x$\vee$z = y$\vee$z हमेशा x = y इंगित करता है।

• Hasse diagrams of the two prototypical non-distributive lattices
• M3 1xyz0.svg

  The diamond lattice M₃ is non-distributive: x ∧ (y ∨ z) = x ∧ 1 = x ≠ 0 = 0 ∨ 0 = (x ∧ y) ∨ (x ∧ z).

• N5 1xyz0.svg

  The pentagon lattice N₅ is non-distributive: x ∧ (y ∨ z) = x ∧ 1 = x ≠ z = 0 ∨ z = (x ∧ y) ∨ (x ∧ z).

File:Non-dstrbtive lattices-warning.png

वितरणात्मक लैटिस जिसमें N5 (ठोस रेखाएँ, बाएँ) और M3 (दाएँ) सबसेट के रूप में होते हैं, लेकिन उप-वर्ग के रूप में नहीं

सरलतम अवितरणीय नियम M हैं₃, हीरा जाली, और एन₅, पेंटागन जाली। एक लैटिस वितरण योग्य है अगर और केवल अगर इसकी कोई भी सबलेटिस एम के लिए आइसोमोर्फिक नहीं है₃ या एन₅; एक सबलेटिस एक उपसमुच्चय है जो मिलने के तहत बंद हो जाता है और मूल लैटिस के संचालन में सम्मिलित हो जाता है। ध्यान दें कि यह उपसमुच्चय के समान नहीं है जो मूल क्रम के तहत एक लैटिस है (लेकिन संभवतः अलग-अलग जुड़ने और मिलने के संचालन के साथ)। आगे के लक्षण अगले भाग में प्रतिनिधित्व सिद्धांत से प्राप्त होते हैं।

एक ही तथ्य को कहने का एक वैकल्पिक तरीका यह है कि प्रत्येक वितरण लैटिस दो-तत्व बूलियन बीजगणित की प्रतियों का एक उप-प्रत्यक्ष उत्पाद है। तत्व श्रृंखला परिणाम के रूप में, प्रत्येक बूलियन बीजगणित (संरचना) में यह गुण भी होता है।

अंत में वितरण में कई अन्य सुखद गुण सम्मिलित हैं। उदाहरण के लिए, एक वितरणात्मक नियम का एक तत्व है नियम (आदेश)

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

इसके अतिरिक्त, प्रत्येक वितरण लैटिस भी मॉड्यूलर लैटिस है।

प्रतिनिधित्व सिद्धांत

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

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

एक अन्य प्रारंभिक प्रतिनिधित्व प्रमेय को अब वितरणात्मक लैटिस के लिए स्टोन के प्रतिनिधित्व प्रमेय के रूप में जाना जाता है (नाम मार्शल हार्वे स्टोन का सम्मान करता है, जिन्होंने इसे पहली बार साबित किया था)। यह कुछ टोपोलॉजिकल स्पेस के कॉम्पैक्ट जगह ओपन समुच्चय समुच्चय के लैटिस के रूप में वितरक लैटिस को दर्शाता है। इस परिणाम को बूलियन बीजगणित के लिए स्टोन के प्रसिद्ध स्टोन के प्रतिनिधित्व प्रमेय के सामान्यीकरण और स्टोन द्वैत की सामान्य सेटिंग की विशेषज्ञता के रूप में देखा जा सकता है।

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

स्टोन और प्रिस्टले के प्रमेयों के परिणामस्वरूप, कोई भी आसानी से देखता है कि कोई वितरण लैटिस वास्तव में सेटों की लैटिस के लिए आइसोमोर्फिक है। हालांकि, दोनों बयानों के प्रमाण के लिए बूलियन प्रधान आदर्श प्रमेय की आवश्यकता होती है, जो पसंद के स्वयंसिद्ध का एक कमजोर रूप है।

मुक्त वितरण नियम

File:Monotone Boolean functions.svg

शून्य, एक, दो और तीन जनरेटर पर मुफ्त वितरण जाली। 0 और 1 लेबल वाले तत्व खाली सम्मिलित होते हैं और मिलते हैं, और तत्व लेबल वाला बहुमत है (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) ∧ ( वाई ∨ जेड)।

जेनरेटर जी के एक समुच्चय पर मुक्त वस्तु वितरण लैटिस सामान्य मुक्त लैटिस से अधिक आसानी से बनाई जा सकती है। पहला अवलोकन यह है कि, वितरण के नियमों का उपयोग करते हुए, प्रत्येक शब्द द्विआधारी संक्रियाओं द्वारा गठित होता है $\lor$ और $\land$ जनरेटर के एक समुच्चय पर निम्नलिखित समतुल्य सामान्य रूप में परिवर्तित किया जा सकता है:

$M_{1}\lor M_{2}\lor \cdots \lor M_{n},$

कहाँ $M_{i}$ जी के तत्वों के परिमित मिलन हैं। इसके अतिरिक्त, चूंकि दोनों मिलते हैं और जुड़ते हैं साहचर्य, क्रमविनिमेयता और निःशक्तता, कोई डुप्लिकेट और ऑर्डर को अनदेखा कर सकता है, और समुच्चय के एक समुच्चय के रूप में उपरोक्त की तरह मिलने का प्रतिनिधित्व कर सकता है:

$\{N_{1},N_{2},\ldots ,N_{n}\},$

जहां $N_{i}$ G के परिमित उपसमुच्चय हैं। हालाँकि, यह अभी भी संभव है कि दो ऐसे शब्द वितरणात्मक लैटिस के समान तत्व को दर्शाते हैं। यह तब होता है जब सूचकांक जे और के ऐसे होते हैं $N_{j}$ का उपसमुच्चय है $N_{k}.$ इस मामले में मुलाकात की $N_{k}$ के नीचे होगा $N_{j},$ और इसलिए अनावश्यक समुच्चय को सुरक्षित रूप से हटाया जा सकता है $N_{k}$ पूरे शब्द की व्याख्या को बदले बिना। नतीजतन, जी के परिमित उपसमुच्चय का एक समुच्चय जब भी इसके सभी तत्वों को बेमतलब कहा जाएगा $N_{i}$ पारस्परिक रूप से अतुलनीय हैं (सबसेट ऑर्डरिंग के संबंध में); अर्थात जब यह एक स्पर्नर परिवार बनाता है।

अब जनरेटर G के एक समुच्चय पर मुक्त वितरण लैटिस को G के परिमित उपसमुच्चय के सभी परिमित अप्रासंगिक सेटों के समुच्चय पर परिभाषित किया गया है। दो परिमित अप्रासंगिक सेटों का जुड़ाव सभी निरर्थक सेटों को हटाकर उनके मिलन से प्राप्त किया जाता है। इसी तरह दो समुच्चय एस और टी का मिलन इसका बेतुका संस्करण है $\{N\cup M\mid N\in S,M\in T\}.$ सत्यापन कि यह संरचना आवश्यक सार्वभौमिक संपत्ति के साथ एक वितरण लैटिस है, नियमित है।

एन जनरेटर के साथ मुक्त वितरण नियम में तत्वों की संख्या डेडेकिंड संख्या द्वारा दी गई है। ये संख्याएँ तेजी से बढ़ती हैं, और केवल n ≤ 8 के लिए जानी जाती हैं; वे हैं

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sequence A000372 in the OEIS).

ऊपर दी गई संख्या मुक्त वितरण लैटिस में तत्वों की संख्या की गणना करती है जिसमें लैटिस संचालन सम्मिलित होते हैं और तत्वों के परिमित सेटों से मिलते हैं, जिसमें खाली समुच्चय भी सम्मिलित है। यदि खाली जोड़ और खाली मिलने की अनुमति नहीं है, तो परिणामी मुक्त वितरण लैटिस में दो कम तत्व होते हैं; उनके तत्वों की संख्या अनुक्रम बनाती है

0, 1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786 (sequence A007153 in the OEIS).

यह भी देखें

• पूरी तरह से वितरित लैटिस - एक लैटिस जिसमें अनंत जोड़ अनंत मिलते हैं
• वितरणात्मक लैटिस के लिए द्वैत सिद्धांत
• वर्णक्रमीय स्थान

अग्रिम पठन

• Burris, Stanley N.; Sankappanavar, H.P. (1981). A Course in Universal Algebra. Springer-Verlag. ISBN 3-540-90578-2.
• OEIS sequence A006982 (Number of unlabeled distributive lattices with n elements)