पूर्ण आंशिक क्रम: Difference between revisions
No edit summary |
(→उदाहरण) |
||
| Line 24: | Line 24: | ||
* प्रत्येक समुच्चय एस को कम से कम तत्व ⊥ जोड़कर और एस में प्रत्येक एस के लिए ⊥ ≤ s और s ≤ s के साथ फ्लैट ऑर्डर पेश करके इंगित डीसीपीओ में बदल दिया जा सकता है और कोई अन्य ऑर्डर संबंध नहीं है। | * प्रत्येक समुच्चय एस को कम से कम तत्व ⊥ जोड़कर और एस में प्रत्येक एस के लिए ⊥ ≤ s और s ≤ s के साथ फ्लैट ऑर्डर पेश करके इंगित डीसीपीओ में बदल दिया जा सकता है और कोई अन्य ऑर्डर संबंध नहीं है। | ||
* कुछ दिए गए समुच्चय एस पर सभी [[आंशिक कार्य]] के समुच्चय को f ≤ g को परिभाषित करके आदेश दिया जा सकता है यदि और केवल यदि g f का विस्तार करता है, अर्थात यदि f के फलन का डोमेन g के डोमेन का सबसमुच्चय है और f के मान हैं और g उन सभी इनपुटों पर सहमत हैं जिनके लिए वे दोनों परिभाषित हैं। (समान रूप से, f ≤ g यदि और केवल यदि f ⊆ g जहां f और g को फलन के उनके संबंधित ग्राफ़ से पहचाना जाता है।) यह क्रम इंगित डीसीपीओ है, जहां सबसे कम तत्व कहीं भी परिभाषित आंशिक फलन नहीं है (खाली डोमेन के साथ) ). वास्तव में, ≤ भी पूर्ण परिबद्ध है। यह उदाहरण यह भी प्रदर्शित करता है कि सदैव महानतम तत्व का होना स्वाभाविक क्यों नहीं है। | * कुछ दिए गए समुच्चय एस पर सभी [[आंशिक कार्य]] के समुच्चय को f ≤ g को परिभाषित करके आदेश दिया जा सकता है यदि और केवल यदि g f का विस्तार करता है, अर्थात यदि f के फलन का डोमेन g के डोमेन का सबसमुच्चय है और f के मान हैं और g उन सभी इनपुटों पर सहमत हैं जिनके लिए वे दोनों परिभाषित हैं। (समान रूप से, f ≤ g यदि और केवल यदि f ⊆ g जहां f और g को फलन के उनके संबंधित ग्राफ़ से पहचाना जाता है।) यह क्रम इंगित डीसीपीओ है, जहां सबसे कम तत्व कहीं भी परिभाषित आंशिक फलन नहीं है (खाली डोमेन के साथ) ). वास्तव में, ≤ भी पूर्ण परिबद्ध है। यह उदाहरण यह भी प्रदर्शित करता है कि सदैव महानतम तत्व का होना स्वाभाविक क्यों नहीं है। | ||
* किसी भी | * किसी भी संयमित समष्टि का [[विशेषज्ञता क्रम]] डीसीपीओ है। | ||
* आइए हम शब्द "[[ निगमनात्मक प्रणाली ]]" का उपयोग परिणाम के अनुसार बंद [[वाक्य (गणितीय तर्क)]] के समुच्चय के रूप में करें (परिणाम की धारणा को परिभाषित करने के लिए, आइए उदाहरण के लिए [[अल्फ्रेड टार्स्की]] के बीजगणितीय दृष्टिकोण का उपयोग करें) <ref name=Tar-BizIg>Tarski, Alfred: Bizonyítás és igazság / Válogatott tanulmányok. Gondolat, Budapest, 1990. (Title means: Proof and truth / Selected papers.)</ref><ref name=BurSan-UnivAlg>[http://www.math.uwaterloo.ca/~snburris/index.html Stanley N. Burris] and H.P. Sankappanavar: [http://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html A Course in Universal Algebra]</ref>). ऐसे रोचक प्रमेय हैं जो निर्देशित-पूर्ण आंशिक क्रम वाले निगमनात्मक प्रणालियों के समुच्चय से संबंधित हैं।<ref name=seqdcpo>See online in p. 24 exercises 5–6 of §5 in [https://www.math.uwaterloo.ca/~snburris/htdocs/UALG/univ-algebra.pdf]. Or, on paper, see [[#_note-Tar-BizIg|Tar:BizIg]].</ref> इसके अतिरिक्त, निगमनात्मक प्रणालियों के समुच्चय को प्राकृतिक विधि से कम से कम तत्व के लिए चुना जा सकता है (जिससे यह इंगित डीसीपीओ भी हो सके), क्योंकि खाली समुच्चय के सभी परिणामों का समुच्चय (अर्थात "तार्किक रूप से सिद्ध करने योग्य का समुच्चय) /तार्किक रूप से मान्य वाक्य”) (1) निगमनात्मक प्रणाली है (2) सभी निगमनात्मक प्रणालियों में निहित है। | * आइए हम शब्द "[[ निगमनात्मक प्रणाली ]]" का उपयोग परिणाम के अनुसार बंद [[वाक्य (गणितीय तर्क)]] के समुच्चय के रूप में करें (परिणाम की धारणा को परिभाषित करने के लिए, आइए उदाहरण के लिए [[अल्फ्रेड टार्स्की]] के बीजगणितीय दृष्टिकोण का उपयोग करें) <ref name=Tar-BizIg>Tarski, Alfred: Bizonyítás és igazság / Válogatott tanulmányok. Gondolat, Budapest, 1990. (Title means: Proof and truth / Selected papers.)</ref><ref name=BurSan-UnivAlg>[http://www.math.uwaterloo.ca/~snburris/index.html Stanley N. Burris] and H.P. Sankappanavar: [http://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html A Course in Universal Algebra]</ref>). ऐसे रोचक प्रमेय हैं जो निर्देशित-पूर्ण आंशिक क्रम वाले निगमनात्मक प्रणालियों के समुच्चय से संबंधित हैं।<ref name=seqdcpo>See online in p. 24 exercises 5–6 of §5 in [https://www.math.uwaterloo.ca/~snburris/htdocs/UALG/univ-algebra.pdf]. Or, on paper, see [[#_note-Tar-BizIg|Tar:BizIg]].</ref> इसके अतिरिक्त, निगमनात्मक प्रणालियों के समुच्चय को प्राकृतिक विधि से कम से कम तत्व के लिए चुना जा सकता है (जिससे यह इंगित डीसीपीओ भी हो सके), क्योंकि खाली समुच्चय के सभी परिणामों का समुच्चय (अर्थात "तार्किक रूप से सिद्ध करने योग्य का समुच्चय) /तार्किक रूप से मान्य वाक्य”) (1) निगमनात्मक प्रणाली है (2) सभी निगमनात्मक प्रणालियों में निहित है। | ||
Latest revision as of 15:16, 28 August 2023
गणित में, पूर्ण आंशिक क्रम वाक्यांश का उपयोग कम से कम तीन समान, किन्तु विशिष्ट, आंशिक रूप से क्रमित समुच्चयों की कक्षाओं को संदर्भित करने के लिए किया जाता है, जो विशेष पूर्णता (आदेश सिद्धांत) द्वारा विशेषता होती हैं। पूर्ण आंशिक आदेश,सांकेतिक शब्दार्थ और डोमेन सिद्धांत में सैद्धांतिक कंप्यूटर विज्ञान में एक केंद्रीय भूमिका निभाते हैं।
परिभाषा
एक पूर्ण आंशिक क्रम, संक्षिप्त रूप में सीपीओ, संदर्भ के आधार पर निम्नलिखित में से किसी भी अवधारणा को संदर्भित कर सकता है।
- पूर्ण आंशिक क्रम समुच्चय निर्देशित-पूर्ण आंशिक ऑर्डर (डीसीपीओ) है यदि इसके प्रत्येक निर्देशित समुच्चय में सर्वोच्च है। आंशिक क्रम का उपसमुच्चय निर्देशित होता है यदि यह खाली समुच्चय है | गैर-रिक्त है और तत्वों की प्रत्येक जोड़ी में उपसमुच्चय में ऊपरी सीमा होती है। साहित्य में, डी.सी.पी.ओ.एस कभी-कभी अप-कम्प्लीट पॉसमुच्चय लेबल के अंतर्गत भी दिखाई देते हैं।
- पूर्ण आंशिक क्रम समुच्चय इंगित निर्देशित-पूर्ण आंशिक ऑर्डर है यदि यह कम से कम तत्व वाला डीसीपीओ है। इन्हें कभी-कभी संक्षिप्त रूप में सीपीपीओ कहा जाता है।
- पूर्ण आंशिक क्रम समुच्चय ω-पूर्ण आंशिक ऑर्डर (ω-सीपीओ) है यदि यह पॉसमुच्चय है जिसमें प्रत्येक ω-श्रृंखला (x1 ≤ x2 ≤ x3 ≤ x4 ≤ ...) है जिसमें वह सर्वोच्च है जो पोसमुच्चय से संबंधित है। प्रत्येक डीसीपीओ ω-सीपीओ है, क्योंकि प्रत्येक ω-श्रृंखला निर्देशित समुच्चय है, किन्तु इसका विपरीत (तर्क) सत्य नहीं है। चूँकि, डोमेन सिद्धांत डोमेन के आधार वाला प्रत्येक ω-सीपीओ भी डीसीपीओ है (समान आधार के साथ) [1] आधार वाले ω-सीपीओ (डीसीपीओ) को सतत ω-सीपीओ (निरंतर डीसीपीओ) भी कहा जाता है।
ध्यान दें कि पूर्ण आंशिक क्रम का उपयोग कभी भी उस स्थिति के लिए नहीं किया जाता है जिसमें सभी उपसमुच्चय में सर्वोच्चता होती है; इस अवधारणा के लिए पूर्ण जाली शब्दावली का उपयोग किया जाता है।
निर्देशित सुप्रीमा के अस्तित्व की आवश्यकता को निर्देशित समुच्चयों को सामान्यीकृत सन्निकटन अनुक्रमों के रूप में और सुप्रीमा को संबंधित (अनुमानित) संगणनाओं की सीमा के रूप में देखने से प्रेरित किया जा सकता है। यह अंतर्ज्ञान, सांकेतिक शब्दार्थ के संदर्भ में, डोमेन सिद्धांत के विकास के पीछे प्रेरणा थी।
निर्देशित-पूर्ण आंशिक क्रम की द्वैत (आदेश सिद्धांत) धारणा को फ़िल्टर्ड-पूर्ण आंशिक क्रम कहा जाता है। चूँकि, यह अवधारणा व्यवहार में बहुत कम बार पाई जाती है, क्योंकि सामान्यतः कोई व्यक्ति स्पष्ट रूप से दोहरे क्रम पर काम कर सकता है।
उदाहरण
- प्रत्येक परिमित स्थिति पूर्ण निर्देशित होती है।
- सभी पूर्ण जालियों को भी पूर्ण निर्देशित किया जाता है।
- किसी भी पॉसमुच्चय के लिए, सभी गैर-रिक्त फ़िल्टर (गणित) का समुच्चय, समावेशन (समुच्चय सिद्धांत) द्वारा आदेशित, डीसीपीओ है। खाली फिल्टर के साथ-साथ यह स्पष्ट भी होता है। यदि ऑर्डर में बाइनरी सम्मिलित हों और मिलें है, जिससे यह निर्माण (खाली फिल्टर सहित) वास्तव में पूर्ण जाली उत्पन्न करता है।
- प्रत्येक समुच्चय एस को कम से कम तत्व ⊥ जोड़कर और एस में प्रत्येक एस के लिए ⊥ ≤ s और s ≤ s के साथ फ्लैट ऑर्डर पेश करके इंगित डीसीपीओ में बदल दिया जा सकता है और कोई अन्य ऑर्डर संबंध नहीं है।
- कुछ दिए गए समुच्चय एस पर सभी आंशिक कार्य के समुच्चय को f ≤ g को परिभाषित करके आदेश दिया जा सकता है यदि और केवल यदि g f का विस्तार करता है, अर्थात यदि f के फलन का डोमेन g के डोमेन का सबसमुच्चय है और f के मान हैं और g उन सभी इनपुटों पर सहमत हैं जिनके लिए वे दोनों परिभाषित हैं। (समान रूप से, f ≤ g यदि और केवल यदि f ⊆ g जहां f और g को फलन के उनके संबंधित ग्राफ़ से पहचाना जाता है।) यह क्रम इंगित डीसीपीओ है, जहां सबसे कम तत्व कहीं भी परिभाषित आंशिक फलन नहीं है (खाली डोमेन के साथ) ). वास्तव में, ≤ भी पूर्ण परिबद्ध है। यह उदाहरण यह भी प्रदर्शित करता है कि सदैव महानतम तत्व का होना स्वाभाविक क्यों नहीं है।
- किसी भी संयमित समष्टि का विशेषज्ञता क्रम डीसीपीओ है।
- आइए हम शब्द "निगमनात्मक प्रणाली " का उपयोग परिणाम के अनुसार बंद वाक्य (गणितीय तर्क) के समुच्चय के रूप में करें (परिणाम की धारणा को परिभाषित करने के लिए, आइए उदाहरण के लिए अल्फ्रेड टार्स्की के बीजगणितीय दृष्टिकोण का उपयोग करें) [2][3]). ऐसे रोचक प्रमेय हैं जो निर्देशित-पूर्ण आंशिक क्रम वाले निगमनात्मक प्रणालियों के समुच्चय से संबंधित हैं।[4] इसके अतिरिक्त, निगमनात्मक प्रणालियों के समुच्चय को प्राकृतिक विधि से कम से कम तत्व के लिए चुना जा सकता है (जिससे यह इंगित डीसीपीओ भी हो सके), क्योंकि खाली समुच्चय के सभी परिणामों का समुच्चय (अर्थात "तार्किक रूप से सिद्ध करने योग्य का समुच्चय) /तार्किक रूप से मान्य वाक्य”) (1) निगमनात्मक प्रणाली है (2) सभी निगमनात्मक प्रणालियों में निहित है।
गुण
एक ऑर्डर किया गया समुच्चय P इंगित डीसीपीओ है यदि और केवल यदि प्रत्येक श्रृंखला (ऑर्डर सिद्धांत) में P में सर्वोच्च है, अर्थात, P चेन-पूर्ण आंशिक ऑर्डर है चेन-पूर्ण है।[5] वैकल्पिक रूप से, ऑर्डर किया गया समुच्चय P इंगित डीसीपीओ है यदि और केवल तभी जब P के प्रत्येक ऑर्डर-संरक्षित स्व-मैप में कम से कम फिक्सप्वाइंट होता है।
सतत कार्य और निश्चित-बिंदु
दो डी.सी.पी.ओ.एस P और Q के बीच फलन (गणित) f को 'स्कॉट निरंतरता कहा जाता है यदि यह उनके सर्वोच्चता को संरक्षित करते हुए निर्देशित समुच्चयों को निर्देशित समुच्चयों पर मैप करता है:
- प्रत्येक निर्देशित के लिए निर्देशित किया जाता है .
- प्रत्येक निर्देशित के लिए .
ध्यान दें कि डी.सी.पी.ओ.एस के बीच प्रत्येक निरंतर फलन मोनोटोन फलन ऑर्डर सिद्धांत में मोनोटोनिकिटी है। निरंतरता की यह धारणा स्कॉट टोपोलॉजी द्वारा प्रेरित टोपोलॉजिकल निरंतरता के सामान्य है।
दो डी.सी.पी.ओ.एस P और Q के बीच सभी निरंतर कार्यों के समुच्चय को [P → Q] दर्शाया जाता है। बिंदुवार संबंधों से सुसज्जित, यह फिर से डीसीपीओ है, और जब भी Q सीपीओ होता है तो सीपीओ होता है।
इस प्रकार स्कॉट-निरंतर मैपों के साथ पूर्ण आंशिक आदेश कार्टेशियन बंद श्रेणी श्रेणी (गणित) बनाते हैं।[6] सीपीओ (पी, ⊥) के प्रत्येक ऑर्डर-संरक्षण स्व-मानचित्र एफ में कम से कम निश्चित बिंदु होता है। [7] यदि f निरंतर है तो यह निश्चित-बिंदु ⊥ के पुनरावृत्त फलन (⊥, f (⊥), f (f (⊥)), … f n(⊥), …) के सर्वोच्च के सामान्य है (क्लेन निश्चित-बिंदु प्रमेय भी देखें)
यह भी देखें
केवल निर्देशित पूर्णता अधिक मूलभूत प्रोपर्टी है जो अधिकांशतः अन्य ऑर्डर-सैद्धांतिक जांच में होती है, उदाहरण के लिए बीजगणितीय पॉसमुच्चय और स्कॉट टोपोलॉजी का उपयोग करते हुए।
निर्देशित पूर्णता अन्य पूर्णता (आदेश सिद्धांत) धारणाओं जैसे श्रृंखला पूर्णता से विभिन्न विधियों से संबंधित है।
टिप्पणियाँ
- ↑ Abramsky S, Gabbay DM, Maibaum TS (1994). Handbook of Logic in Computer Science, volume 3. Oxford: Clarendon Press. Prop 2.2.14, pp. 20. ISBN 9780198537625.
- ↑ Tarski, Alfred: Bizonyítás és igazság / Válogatott tanulmányok. Gondolat, Budapest, 1990. (Title means: Proof and truth / Selected papers.)
- ↑ Stanley N. Burris and H.P. Sankappanavar: A Course in Universal Algebra
- ↑ See online in p. 24 exercises 5–6 of §5 in [1]. Or, on paper, see Tar:BizIg.
- ↑ Markowsky, George (1976), "Chain-complete posets and directed sets with applications", Algebra Universalis, 6 (1): 53–68, doi:10.1007/bf02485815, MR 0398913, S2CID 16718857.
- ↑ Barendregt, Henk, The lambda calculus, its syntax and semantics Archived 2004-08-23 at the Wayback Machine, North-Holland (1984)
- ↑ See Knaster–Tarski theorem; The foundations of program verification, 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, ISBN 0-471-91282-4, Chapter 4; the Knaster–Tarski theorem, formulated over cpo's, is given to prove as exercise 4.3-5 on page 90.
संदर्भ
- Davey, B.A.; Priestley, H. A. (2002). Introduction to Lattices and Order (Second ed.). Cambridge University Press. ISBN 0-521-78451-4.
