निर्णायकता (तर्क)
तर्क में, सही/गलत निर्णय समस्या निर्णायक होती है यदि सही उत्तर प्राप्त करने के लिए कोई प्रभावी तरीका सम्मिलित हो। शून्य-क्रम तर्क (प्रस्तावात्मक तर्क) निर्णायक है, जबकि प्रथम-क्रम और उच्च-क्रम तर्क नहीं हैं। तार्किक रूप से मान्य सूत्रों (या प्रमेय) के उनके समुच्चय में सदस्यता प्रभावी रूप से निर्धारित की जा सकती है, तो तार्किक प्रणालियां निर्णायक हैं। औपचारिक प्रणालियाँ निर्णायक होती हैं यदि उनकी वैधता (तर्क) सूत्रों (या प्रमेय) के समुच्चय में सदस्यता प्रभावी रूप से निर्धारित की जा सकती है। निश्चित तार्किक प्रणाली में सिद्धांत (तार्किक परिणाम के अंतर्गत संवृत्त किए गए कथनों का समुच्चय) निर्णायक होता है यदि यह निर्धारित करने के लिए एक प्रभावी तरीका है कि सिद्धांत में एकपक्षीय सूत्र सम्मिलित हैं या नहीं है। कई महत्वपूर्ण समस्याएं अनिर्णीत हैं, अर्थात्, यह प्रमाणित हो गया है कि सदस्यता निर्धारित करने के लिए कोई प्रभावी तरीका नहीं है (परिमित के बाद एक सही उत्तर देना, हालांकि संभवतः बहुत लंबा, सभी स्थितियों में समय) उनके लिए सम्मिलित हो सकता है।
तार्किक प्रणाली की निर्णायकता
प्रत्येक तार्किक प्रणाली एक सिंटैक्टिक घटक के साथ आती है, जो अन्य वस्तुओ के साथ-साथ प्रवीणता की धारणा को निर्धारित करती है, और सिमेंटिक घटक, जो तार्किक वैधता की धारणा को निर्धारित करता है। एक प्रणाली के तार्किक रूप से मान्य सूत्रों को कभी-कभी प्रणाली के प्रमेय कहा जाता है, विशेष रूप से प्रथम-क्रम तर्क के संदर्भ में जहां गोडेल की पूर्णता प्रमेय सिमैन्टिक और सिंटैक्टिक परिणाम की समानता स्थापित करता है। अन्य स्थितियों में, जैसे रैखिक तर्क, सिंटैक्टिक परिणाम (प्रिवेबिलिटी) संबंध का उपयोग सिस्टम के प्रमेयों को परिभाषित करने के लिए किया जा सकता है।
तार्किक प्रणाली निर्णायक होती है यदि यह निर्धारित करने के लिए एक प्रभावी तरीका है कि क्या स्वैच्छिक सूत्र तार्किक प्रणाली के प्रमेय हैं। उदाहरण के लिए, प्रस्तावपरक तर्क निर्णायक है, क्योंकि सत्य-सारणी पद्धति का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि क्या एक एकपक्षीय तर्कवाक्य सूत्र तार्किक रूप से मान्य है।
प्रथम-क्रम तर्क सामान्य रूप से निर्णायक नहीं होता है; विशेष रूप से, किसी भी संकेत (तर्क) में तार्किक वैधताओं का समुच्चय जिसमें समानता सम्मिलित है और दो या अधिक तर्कों के साथ कम से कम एक अन्य निर्धारक निर्णायक नहीं है।[1] प्रथम-क्रम तर्क को विस्तारित करने वाली तार्किक प्रणालियाँ, जैसे कि द्वितीय-क्रम तर्क और प्रकार सिद्धांत, भी अनिर्णीत हैं।
पहचान के साथ एकपदीय निर्धारक कलन की वैधता, हालांकि, निर्णायक हैं। यह प्रणाली प्रथम-क्रम तर्क है जो उन संकेतों तक सीमित है जिनके पास कोई फ़ंक्शन प्रतीक नहीं है और समानता के अतिरिक्त जिनके संबंध प्रतीक कभी भी एक से अधिक तर्क नहीं लेते हैं।
कुछ तार्किक प्रणालियाँ केवल प्रमेयों के समुच्चय द्वारा ही पर्याप्त रूप से प्रदर्शित नहीं होती हैं। (उदाहरण के लिए, क्लेन के तर्क में कोई भी प्रमेय नहीं है।) ऐसे स्थितियों में, तार्किक प्रणाली की निर्णायकता की वैकल्पिक परिभाषाओं का प्रायः उपयोग किया जाता है, जो सूत्रों की वैधता की तुलना में कुछ अधिक सामान्य निर्धारित करने के लिए एक प्रभावी विधि की मांग करती हैं; इंस्टेंस के लिए, अनुक्रमों की वैधता, या या परिणाम संबंध {(Г, A) | Г ⊧ A} तार्किक है।
सिद्धांत की निर्णायकता
सिद्धांत (गणितीय तर्क) सूत्रों का एक समुच्चय है, जिसे प्रायः तार्किक परिणाम के अंतर्गत संवृत माना जाता है। सिद्धांत के लिए निर्णायकता इस बात से संबंधित है कि क्या कोई प्रभावी प्रक्रिया है जो यह निर्धारित करती है कि सूत्र सिद्धांत का सदस्य है या नहीं, सिद्धांत के संकेत में एक एकपक्षीय सूत्र दिया गया है। निर्णायकता की समस्या स्वाभाविक रूप से तब उत्पन्न होती है जब सिद्धांत को सिद्धांतों के एक निश्चित समुच्चय के तार्किक परिणामों के समुच्चय के रूप में परिभाषित किया जाता है।
सिद्धांतों की निर्णायकता के बारे में कई आधारभूत परिणाम हैं। प्रत्येक (गैर-परासंगत तर्क ) असंगत सिद्धांत निर्णायक है, क्योंकि सिद्धांत के संकेत में प्रत्येक सूत्र एक तार्किक परिणाम होगा, और इस प्रकार सिद्धांत का एक सदस्य होगा। प्रत्येक पूर्ण सिद्धांत पुनरावर्ती गणना योग्य प्रथम-क्रम सिद्धांत निर्णायक है। निर्णायक सिद्धांत का विस्तार निर्णायक नहीं हो सकता है। उदाहरण के लिए, प्रस्तावपरक तर्क में अनिर्णीत सिद्धांत हैं, हालांकि वैधताओं का समुच्चय (सबसे छोटा सिद्धांत) निर्णायक है।
सुसंगत सिद्धांत जिसमें गुण है कि प्रत्येक सुसंगत विस्तार अनिर्णीत है, अनिवार्य रूप से अनिर्णीत कहा जाता है। वास्तव में, प्रत्येक सुसंगत विस्तार अनिवार्य रूप से अनिर्णीत होगा। क्षेत्रों का सिद्धांत अनिर्णीत है लेकिन अनिवार्य रूप से अनिर्णीत नहीं है। रॉबिन्सन अंकगणित अनिवार्य रूप से अनिर्णीत होने के लिए जाना जाता है, और इस प्रकार प्रत्येक सुसंगत सिद्धांत जिसमें रॉबिन्सन अंकगणित सम्मिलित है या व्याख्या करता है, वह भी (अनिवार्य रूप से) अनिर्णीत है।
निर्णायक प्रथम-क्रम के सिद्धांतों के उदाहरणों में वास्तविक संवृत क्षेत्रो का सिद्धांत और प्रेस्बर्गर अंकगणित सम्मिलित हैं, जबकि समुच्चय का सिद्धांत (गणित) और रॉबिन्सन अंकगणित अनिर्णीत सिद्धांतों के उदाहरण हैं।
कुछ निर्णायक सिद्धांत
कुछ निर्णायक सिद्धांतों में सम्मिलित (मोंक 1976, पेज 234) हैं:[2]
- 1915 में लियोपोल्ड लोवेनहेम द्वारा स्थापित केवल समानता के साथ संकेत में प्रथम-क्रम तार्किक वैधता का समुच्चय।
- 1959 में एरेनफ्यूच्ट द्वारा स्थापित समानता और एकल फलन के साथ संकेत में प्रथम-क्रम तार्किक वैधता का समुच्चय।
- समानता और जोड़ के साथ संकेत में प्राकृतिक संख्याओं का प्रथम-क्रम सिद्धांत, जिसे प्रेस्बर्गर अंकगणित भी कहा जाता है। पूर्णता 1929 में मोजेज़ प्रेस्बर्गर द्वारा स्थापित की गई थी।
- समानता और गुणन के साथ संकेत में प्राकृतिक संख्याओं का प्रथम-क्रम सिद्धांत, जिसे स्कोलेम अंकगणित भी कहा जाता है।
- 1940 में अल्फ्रेड टार्स्की द्वारा स्थापित बूलियन बीजगणित के पहले क्रम के सिद्धांत को विहित रूप से परिभाषित किया गया (1940 में पाया गया लेकिन 1949 में घोषित किया गया)।
- टारस्की द्वारा 1949 में स्थापित दी गई विशेषता (बीजगणित) के बीजगणितीय रूप से संवृत क्षेत्रों का पहला क्रम सिद्धांत।
- 1949 में टार्स्की द्वारा स्थापित वास्तविक-संवृत क्रमित क्षेत्रों का प्रथम-क्रम सिद्धांत (टार्स्की की घातीय फलन समस्या भी देखें)।
- 1949 में टार्स्की द्वारा स्थापित यूक्लिडियन ज्यामिति का प्रथम-क्रम सिद्धांत।
- एबेलियन समुच्चयो का प्रथम-क्रम सिद्धांत, 1955 में स्ज़मील्यू द्वारा स्थापित किया गया।
- 1959 में श्वाभौसर द्वारा स्थापित अतिपरवलयिक ज्यामिति का प्रथम-क्रम सिद्धांत।
- 1980 के दशक से लेकर आज तक समुच्चय सिद्धांत की विशिष्ट निर्णायक उपभाषाओं की जांच की गई। (कैंटोन एट अल, 2001)
- ट्री का एकपदीय द्वित्तीय क्रम सिद्धांत (ग्राफ़ सिद्धांत) (S2S (गणित) देखें)।
निर्णायकता स्थापित करने के लिए उपयोग की जाने वाली विधियों में परिमाणक उन्मूलन, मॉडल पूर्णता और लोश-वॉच परीक्षण सम्मिलित हैं।
कुछ अनिर्णीत सिद्धांत
कुछ अनिर्णीत सिद्धांतों में सम्मिलित हैं (मोंक 1976, पृष्ठ 279):[2]
- समानता के साथ किसी भी पहले-क्रम के संकेत में तार्किक वैधताओं का समुच्चय और या तो: 2 से कम नहीं, या दो एकल फलन प्रतीकों, या 2 से कम नहीं, 1953 में बोरिस ट्रेचटेनब्रॉट द्वारा स्थापित एरिटी का एक फलन प्रतीक है।
- 1949 में टार्स्की और आंद्रेज मोस्टोव्स्की द्वारा स्थापित योग, गुणन और समानता के साथ प्राकृतिक संख्याओं का पहला क्रम सिद्धांत।
- 1949 में जूलिया रॉबिन्सन द्वारा स्थापित जोड़, गुणा और समानता के साथ परिमेय संख्याओं का प्रथम-क्रम सिद्धांत।
- 1953 में अल्फ्रेड टार्स्की द्वारा स्थापित समुच्चयों का पहला क्रम सिद्धांत[3] उल्लेखनीय रूप से, न केवल समुच्चयों का सामान्य सिद्धांत अनिर्णीत है, बल्कि कई और विशिष्ट सिद्धांत भी हैं, उदाहरण के लिए (जैसा कि माल्सेव 1961 द्वारा स्थापित) परिमित समुच्चयों का सिद्धांत है। मालसेव ने यह भी स्थापित किया कि अर्धसमुच्चयों का सिद्धांत और वलयों का सिद्धांत अनिर्णीत हैं। रॉबिन्सन ने 1949 में स्थापित किया कि क्षेत्रों का सिद्धांत अनिर्णीत है।
- रॉबिन्सन अंकगणित (और इसलिए कोई भी सुसंगत विस्तार, जैसे पियानों अंकगणित) अनिवार्य रूप से अनिर्णीत है, जैसा कि 1950 में राफेल रॉबिन्सन द्वारा स्थापित किया गया था।
- समानता और दो फलन प्रतीकों के साथ प्रथम-क्रम सिद्धांत है।[4]
व्याख्यात्मकता पद्धति का उपयोग प्रायः सिद्धांतों की अनिश्चितता को स्थापित करने के लिए किया जाता है। यदि एक अनिवार्य रूप से अनिर्णीत सिद्धांत T एक सुसंगत सिद्धांत S में व्याख्या योग्य है, तो S भी अनिवार्य रूप से अनिर्णीत है। यह संगणनीयता सिद्धांत में कई लघुकरण की अवधारणा से निकटता से संबंधित है।
अर्धनिर्णायकता
सिद्धांत या तार्किक प्रणाली का गुण जो निर्णायकता से दुर्बल है, और अर्ध-निर्णायकता है। एक सिद्धांत अर्धनिर्णीत होता है यदि कोई प्रभावी तरीका है, जो एकपक्षीय सूत्र दिया जाता है, हमेशा सिद्धांत में सूत्र होने पर सही रूप से बताएगा, लेकिन सिद्धांत में सूत्र नहीं होने पर या तो ऋणात्मक उत्तर दे सकता है या कोई उत्तर नहीं दे सकता है। यदि प्रमेय (और केवल प्रमेय) उत्पन्न करने के लिए एक प्रभावी विधि है, तो प्रत्येक प्रमेय अंततः उत्पन्न होगा, तो एक तार्किक प्रणाली अर्ध-निर्णायक है। यह निर्णायकता से अलग है क्योंकि एक अर्धनिर्णायक प्रणाली में यह जाँचने के लिए कोई प्रभावी प्रक्रिया नहीं हो सकती है कि कोई सूत्र नहीं एक प्रमेय है।
प्रत्येक निर्णायक सिद्धांत या तार्किक प्रणाली अर्ध-निर्णायक होती है, लेकिन सामान्य रूप से इसका उत्क्रम सत्य नहीं होता है; एक सिद्धांत निर्णायक है यदि और केवल यदि यह और इसके पूरक दोनों अर्ध-निर्णायक हैं। उदाहरण के लिए, पहले क्रम के तर्क की तार्किक वैधता का समुच्चय V अर्ध-निर्णायक है, लेकिन निर्णायक नहीं है। इस स्थिति में, ऐसा इसलिए है क्योंकि एकपक्षीय सूत्र A के निर्धारण के लिए कोई प्रभावी तरीका नहीं है कि क्या A, V में नहीं है। इसी तरह, प्रथम-क्रम के स्वयंसिद्धों के किसी भी पुनरावर्ती गणना योग्य समुच्चय के तार्किक परिणामों का समुच्चय अर्ध-निर्णायक है। ऊपर दिए गए अनिर्णीत प्रथम-क्रम सिद्धांतों के कई उदाहरण इस रूप के हैं।
पूर्णता से संबंध
निर्णायकता को पूर्ण सिद्धांत के साथ भ्रमित नहीं होना चाहिए। उदाहरण के लिए, बीजगणितीय रूप से संवृत क्षेत्रों का सिद्धांत निर्णायक है, लेकिन अधूरा है, जबकि + और × वाली भाषा में गैर-ऋणात्मक पूर्णांकों के बारे में सभी सत्य प्रथम-क्रम कथनों का समुच्चय पूर्ण है लेकिन अनिर्णीत है। दुर्भाग्य से, एक पारिभाषिक अस्पष्टता के रूप में, अनिश्चित कथन पद को कभी-कभी स्वतंत्र कथन (गणितीय तर्क) के उपपद के रूप में प्रयोग किया जाता है।
संगणनीयता से संबंध
निर्णायक समुच्चय की अवधारणा के साथ, निर्णायक सिद्धांत या तार्किक प्रणाली की परिभाषा या तो प्रभावी तरीकों या गणना योग्य फलनों के संदर्भ में दी जा सकती है। इन्हें सामान्य रूप से प्रति चर्च की थीसिस के समान माना जाता है। वास्तव में, प्रमाण है कि एक तार्किक प्रणाली या सिद्धांत अनिर्णीत है, कम्प्यूटेबिलिटी (संगणनीयता) की औपचारिक परिभाषा का उपयोग यह दिखाने के लिए करेगा कि एक उपयुक्त समुच्चय एक निर्णायक समुच्चय नहीं है, और फिर चर्च की थीसिस को यह दिखाने के लिए उपयोग करें कि सिद्धांत या तार्किक प्रणाली किसी भी प्रभावी विधि (एंडर्टन 2001, पीपी 206ff) द्वारा निर्णायक नहीं है।
खेलों के संदर्भ में
कुछ खेलों को उनकी निर्णायकता के अनुसार वर्गीकृत किया गया है:
- शतरंज निर्णायक है।[5][6] परिशुद्ध जानकारी वाले अन्य सभी परिमित दो-खिलाड़ी खेलों के लिए भी यही प्रयुक्त होता है।
- अनंत शतरंज में n में सहायक (नियमों और गेमपीस पर सीमाओं के साथ) निर्णायक है।[7][8] हालांकि, ऐसी स्थितियाँ हैं (अंततः कई भागों के साथ) जो जीतने के लिए प्रणोदित हैं, लेकिन किसी सीमित n के लिए n में सहायक नहीं हैं।[9]
- सीमित बोर्ड (लेकिन असीमित समय के साथ) पर अपूर्ण जानकारी वाले कुछ समूह खेल अनिर्णीत हैं।[10]
यह भी देखें
संदर्भ
टिप्पणियाँ
- ↑ Trakhtenbrot, 1953 .
- ↑ 2.0 2.1 Monk, Donald (1976). गणितीय तर्क. Springer. ISBN 9780387901701.
- ↑ Tarski, A.; Mostovski, A.; Robinson, R. (1953), Undecidable Theories, Studies in Logic and the Foundation of Mathematics, North-Holland, Amsterdam, ISBN 9780444533784
- ↑ Gurevich, Yuri (1976). "मानक कक्षाओं के लिए निर्णय समस्या". J. Symb. Log. 41 (2): 460–464. CiteSeerX 10.1.1.360.1517. doi:10.1017/S0022481200051513. S2CID 798307. Retrieved 5 August 2014.
- ↑ Stack Exchange Computer Science. "Is chess game movement TM decidable?"
- ↑ Undecidable Chess Problem?
- ↑ Mathoverflow.net/Decidability-of-chess-on-an-infinite-board Decidability-of-chess-on-an-infinite-board
- ↑ Brumleve, Dan; Hamkins, Joel David; Schlicht, Philipp (2012). "The Mate-in-n Problem of Infinite Chess Is Decidable". यूरोप में कम्प्यूटेबिलिटी पर सम्मेलन. Lecture Notes in Computer Science. Vol. 7318. Springer. pp. 78–88. arXiv:1201.5597. doi:10.1007/978-3-642-30870-3_9. ISBN 978-3-642-30870-3. S2CID 8998263.
- ↑ "Lo.logic – Checkmate in $\omega$ moves?".
- ↑ Poonen, Bjorn (2014). "10. Undecidable Problems: A Sampler: §14.1 Abstract Games". In Kennedy, Juliette (ed.). Interpreting Gödel: Critical Essays. Cambridge University Press. pp. 211–241 See p. 239. arXiv:1204.0299. CiteSeerX 10.1.1.679.3322. ISBN 9781107002661.}
ग्रन्थसूची
- Barwise, Jon (1982), "Introduction to first-order logic", in Barwise, Jon (ed.), Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN 978-0-444-86388-1
- Cantone, D.; Omodeo, E. G.; Policriti, A. (2013) [2001], Set Theory for Computing. From Decision Procedures to Logic Programming with Sets, Monographs in Computer Science, Springer, ISBN 9781475734522
- Chagrov, Alexander; Zakharyaschev, Michael (1997), Modal logic, Oxford Logic Guides, vol. 35, Oxford University Press, ISBN 978-0-19-853779-3, MR 1464942
- Davis, Martin (2013) [1958], Computability and Unsolvability, Dover, ISBN 9780486151069
- Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Academic Press, ISBN 978-0-12-238452-3
- Keisler, H. J. (1982), "Fundamentals of model theory", in Barwise, Jon (ed.), Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN 978-0-444-86388-1
- Monk, J. Donald (2012) [1976], Mathematical Logic, Springer-Verlag, ISBN 9781468494525
