पूर्ण आंशिक क्रम

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

परिभाषाएँ

एक पूर्ण आंशिक क्रम, संक्षिप्त रूप में सीपीओ, संदर्भ के आधार पर निम्नलिखित में से किसी भी अवधारणा को संदर्भित कर सकता है।

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

• आंशिक रूप से ऑर्डर किया गया सेट एक इंगित निर्देशित-पूर्ण आंशिक ऑर्डर है यदि यह कम से कम तत्व वाला डीसीपीओ है। इन्हें कभी-कभी संक्षिप्त रूप में सीपीपीओ कहा जाता है।

• आंशिक रूप से ऑर्डर किया गया सेट एक ω-पूर्ण आंशिक ऑर्डर (ω-cpo) है यदि यह एक पॉसेट है जिसमें प्रत्येक ω-श्रृंखला (x) है₁ ≤ एक्स₂ ≤ एक्स₃ ≤ एक्स₄ ≤ ...) में एक सर्वोच्च है जो पोसेट से संबंधित है। प्रत्येक dcpo एक ω-cpo है, क्योंकि प्रत्येक ω-श्रृंखला एक निर्देशित सेट है, लेकिन इसका विपरीत (तर्क) सत्य नहीं है। हालाँकि, डोमेन सिद्धांत#डोमेन के आधार वाला प्रत्येक ω-cpo भी एक dcpo है (समान आधार के साथ)। आधार वाले ω-cpo (dcpo) को सतत ω-cpo (निरंतर dcpo) भी कहा जाता है।

ध्यान दें कि पूर्ण आंशिक क्रम का उपयोग कभी भी उस स्थिति के लिए नहीं किया जाता है जिसमें सभी उपसमुच्चय में सर्वोच्चता होती है; इस अवधारणा के लिए पूर्ण जाली शब्दावली का उपयोग किया जाता है।

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

निर्देशित-पूर्ण आंशिक क्रम की द्वैत (आदेश सिद्धांत) धारणा को फ़िल्टर्ड-पूर्ण आंशिक क्रम कहा जाता है। हालाँकि, यह अवधारणा व्यवहार में बहुत कम बार पाई जाती है, क्योंकि आमतौर पर कोई व्यक्ति स्पष्ट रूप से दोहरे क्रम पर काम कर सकता है।

उदाहरण

• प्रत्येक परिमित स्थिति पूर्ण निर्देशित होती है।
• सभी पूर्ण जालियों को भी पूर्ण निर्देशित किया जाता है।
• किसी भी पॉसेट के लिए, सभी गैर-रिक्त फ़िल्टर (गणित) का सेट, समावेशन (सेट सिद्धांत) द्वारा आदेशित, एक डीसीपीओ है। खाली फिल्टर के साथ-साथ यह नुकीला भी होता है। यदि ऑर्डर में बाइनरी शामिल हों और मिलें है, तो यह निर्माण (खाली फिल्टर सहित) वास्तव में एक पूर्ण जाली उत्पन्न करता है।
• प्रत्येक सेट एस को कम से कम तत्व ⊥ जोड़कर और एस में प्रत्येक एस के लिए ⊥ ≤ s और s ≤ s के साथ एक फ्लैट ऑर्डर पेश करके एक इंगित डीसीपीओ में बदल दिया जा सकता है और कोई अन्य ऑर्डर संबंध नहीं है।
• कुछ दिए गए सेट एस पर सभी आंशिक कार्यों के सेट को एफ ≤ जी को परिभाषित करके आदेश दिया जा सकता है यदि और केवल यदि जी एफ का विस्तार करता है, यानी यदि एफ के फ़ंक्शन का डोमेन जी के डोमेन का सबसेट है और एफ के मान हैं और जी उन सभी इनपुटों पर सहमत हैं जिनके लिए वे दोनों परिभाषित हैं। (समान रूप से, f ≤ g यदि और केवल यदि f ⊆ g जहां f और g को फ़ंक्शन के उनके संबंधित ग्राफ़ से पहचाना जाता है।) यह क्रम एक इंगित dcpo है, जहां सबसे कम तत्व कहीं भी परिभाषित आंशिक फ़ंक्शन नहीं है (खाली डोमेन के साथ) ). वास्तव में, ≤ भी पूर्ण परिबद्ध है। यह उदाहरण यह भी प्रदर्शित करता है कि हमेशा महानतम तत्व का होना स्वाभाविक क्यों नहीं है।
• किसी भी शांत स्थान का विशेषज्ञता क्रम एक डीसीपीओ है।
• आइए हम शब्द "निगमनात्मक प्रणाली " का उपयोग परिणाम के तहत बंद वाक्य (गणितीय तर्क) के एक सेट के रूप में करें (परिणाम की धारणा को परिभाषित करने के लिए, आइए उदाहरण के लिए अल्फ्रेड टार्स्की के बीजगणितीय दृष्टिकोण का उपयोग करें)). ऐसे दिलचस्प प्रमेय हैं जो निर्देशित-पूर्ण आंशिक क्रम वाले निगमनात्मक प्रणालियों के एक सेट से संबंधित हैं। इसके अलावा, निगमनात्मक प्रणालियों के एक सेट को प्राकृतिक तरीके से कम से कम तत्व के लिए चुना जा सकता है (ताकि यह एक इंगित डीसीपीओ भी हो सके), क्योंकि खाली सेट के सभी परिणामों का सेट (यानी "तार्किक रूप से साबित करने योग्य का सेट) /तार्किक रूप से मान्य वाक्य”) (1) एक निगमनात्मक प्रणाली है (2) सभी निगमनात्मक प्रणालियों में निहित है।

गुण

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

सतत कार्य और निश्चित-बिंदु

दो dcpos P और Q के बीच एक फ़ंक्शन (गणित) f को 'स्कॉट निरंतरता | (स्कॉट) निरंतर' कहा जाता है यदि यह उनके सर्वोच्चता को संरक्षित करते हुए निर्देशित सेटों को निर्देशित सेटों पर मैप करता है:

• $f(D)\subseteq Q$ प्रत्येक निर्देशित के लिए निर्देशित किया जाता है $D\subseteq P$.
• $f(\sup D)=\sup f(D)$ प्रत्येक निर्देशित के लिए $D\subseteq P$.

ध्यान दें कि dcpos के बीच प्रत्येक निरंतर फ़ंक्शन एक मोनोटोन फ़ंक्शन # ऑर्डर सिद्धांत में मोनोटोनिकिटी है। निरंतरता की यह धारणा स्कॉट टोपोलॉजी द्वारा प्रेरित टोपोलॉजिकल निरंतरता के बराबर है।

दो dcpos P और Q के बीच सभी निरंतर कार्यों के सेट को [P → Q] दर्शाया जाता है। बिंदुवार#बिंदुवार संबंधों से सुसज्जित, यह फिर से एक dcpo है, और जब भी Q एक cpo होता है तो एक cpo होता है। इस प्रकार स्कॉट-निरंतर मानचित्रों के साथ पूर्ण आंशिक आदेश एक कार्टेशियन बंद श्रेणी श्रेणी (गणित) बनाते हैं। सीपीओ (पी, ⊥) के प्रत्येक आदेश-संरक्षित स्व-मानचित्र एफ में कम से कम निश्चित बिंदु होता है। यदि f निरंतर है तो यह निश्चित-बिंदु पुनरावृत्त फ़ंक्शन के सर्वोच्च के बराबर है (⊥, f (⊥), f (f (⊥)), … fⁿ(⊥), …) of ⊥ (क्लेन निश्चित-बिंदु प्रमेय भी देखें)।

यह भी देखें

अकेले निर्देशित पूर्णता काफी बुनियादी संपत्ति है जो अक्सर अन्य ऑर्डर-सैद्धांतिक जांच में होती है, उदाहरण के लिए बीजगणितीय पॉसेट और स्कॉट टोपोलॉजी का उपयोग करते हुए।

निर्देशित पूर्णता अन्य पूर्णता (आदेश सिद्धांत) धारणाओं जैसे श्रृंखला पूर्णता से विभिन्न तरीकों से संबंधित है।

संदर्भ

• Davey, B.A.; Priestley, H. A. (2002). Introduction to Lattices and Order (Second ed.). Cambridge University Press. ISBN 0-521-78451-4.