गोडेल की अपूर्णता प्रमेय

"Bew" redirects here. For other uses, see Bew (disambiguation).

गोडेल की अपूर्णता प्रमेय गणितीय तर्क के दो प्रमेय हैं जो की सीमाओं से संबंधित हैं provability औपचारिक स्वयंसिद्ध सिद्धांतों में। 1931 में कर्ट गोडेल द्वारा प्रकाशित ये परिणाम गणितीय तर्क और गणित के दर्शन दोनों में महत्वपूर्ण हैं। प्रमेय व्यापक रूप से हैं, लेकिन सार्वभौमिक रूप से नहीं, यह दिखाते हुए कि हिल्बर्ट के कार्यक्रम को सभी गणित के लिए सिद्धांतों का एक पूर्ण और सुसंगत सेट खोजने के लिए असंभव है।

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

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

औपचारिक प्रणालियाँ: पूर्णता, निरंतरता और प्रभावी स्वयंसिद्धता

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

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

प्रभावी स्वयंसिद्धीकरण

एक औपचारिक प्रणाली को प्रभावी रूप से स्वयंसिद्ध कहा जाता है (जिसे प्रभावी रूप से उत्पन्न भी कहा जाता है) यदि इसके प्रमेयों का सेट पुनरावर्ती गणना योग्य सेट है (Franzén 2005, p. 112).

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

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

पूर्णता

स्वयंसिद्धों का एक सेट (वाक्यविन्यास, या निषेध-) पूर्ण सिद्धांत है, यदि स्वयंसिद्धों की भाषा में किसी भी कथन के लिए, वह कथन या उसका निषेध स्वयंसिद्धों से सिद्ध होता है (Smith 2007, p. 24). यह गोडेल की पहली अपूर्णता प्रमेय के लिए प्रासंगिक धारणा है। यह शब्दार्थ पूर्णता के साथ भ्रमित नहीं होना है, जिसका अर्थ है कि स्वयंसिद्धों का सेट दी गई भाषा के सभी शब्दार्थों को सिद्ध करता है। अपने गोडेल की पूर्णता प्रमेय में (यहाँ वर्णित अपूर्णता प्रमेय के साथ भ्रमित नहीं होना चाहिए), गोडेल ने सिद्ध किया कि प्रथम क्रम तर्क शब्दार्थ पूर्ण है। लेकिन यह वाक्यात्मक रूप से पूर्ण नहीं है, क्योंकि पहले क्रम के तर्क की भाषा में व्यक्त किए जाने वाले वाक्य हैं जो न तो केवल तर्क के स्वयंसिद्धों से सिद्ध किए जा सकते हैं और न ही अस्वीकृत किए जा सकते हैं।

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

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

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

संगति

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

Peano अंकगणित ZFC से काफी सुसंगत है, लेकिन अपने भीतर से नहीं। इसी तरह, ZFC अपने आप में सुसंगत नहीं है, लेकिन ZFC + एक दुर्गम कार्डिनल मौजूद है जो साबित करता है कि ZFC सुसंगत है क्योंकि यदि κ कम से कम ऐसा कार्डिनल है V_κ वॉन न्यूमैन ब्रह्मांड के अंदर बैठना ZFC का एक आंतरिक मॉडल है, और एक सिद्धांत संगत है अगर और केवल अगर इसका एक मॉडल है।

यदि कोई पीनो अंकगणित की भाषा में सभी कथनों को स्वयंसिद्धों के रूप में लेता है, तो यह सिद्धांत पूर्ण है, इसमें स्वयंसिद्धों का पुनरावर्ती गणनीय सेट है, और जोड़ और गुणा का वर्णन कर सकता है। हालाँकि, यह सुसंगत नहीं है।

असंगत सिद्धांतों के अतिरिक्त उदाहरण Naïve सेट सिद्धांत से उत्पन्न होते हैं # प्रारंभिक सेट सिद्धांत में विरोधाभास जिसका परिणाम तब होता है जब विनिर्देश के Axiom स्कीमा # अप्रतिबंधित समझ को सेट सिद्धांत में ग्रहण किया जाता है।

=== सिस्टम जिसमें अंकगणित === है

अपूर्णता प्रमेय केवल औपचारिक प्रणालियों पर लागू होते हैं जो प्राकृतिक संख्याओं के बारे में तथ्यों का पर्याप्त संग्रह साबित करने में सक्षम हैं। एक पर्याप्त संग्रह रॉबिन्सन अंकगणित के प्रमेयों का समुच्चय है Q. कुछ प्रणालियाँ, जैसे पीनो अंकगणित, प्राकृतिक संख्याओं के बारे में कथनों को प्रत्यक्ष रूप से व्यक्त कर सकती हैं। अन्य, जैसे ZFC सेट थ्योरी, अपनी भाषा में प्राकृतिक संख्याओं के बारे में बयानों की व्याख्या करने में सक्षम हैं। इनमें से कोई भी विकल्प अपूर्णता प्रमेय के लिए उपयुक्त है।

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

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

Dan Willard (2001) ने अंकगणित प्रणालियों के कुछ कमजोर परिवारों का अध्ययन किया है जो गोडेल नंबरिंग को औपचारिक रूप देने के लिए पर्याप्त अंकगणित को संबंध के रूप में अनुमति देते हैं, लेकिन जो एक कार्य के रूप में गुणा करने के लिए पर्याप्त मजबूत नहीं हैं, और इसलिए दूसरी अपूर्णता प्रमेय को साबित करने में विफल रहते हैं; कहने का तात्पर्य यह है कि ये प्रणालियाँ सुसंगत हैं और अपनी स्वयं की संगति साबित करने में सक्षम हैं (स्व-सत्यापन सिद्धांत देखें)।

परस्पर विरोधी लक्ष्य

स्वयंसिद्धों के एक सेट को चुनने में, एक लक्ष्य किसी भी गलत परिणाम को साबित किए बिना यथासंभव अधिक से अधिक सही परिणाम साबित करने में सक्षम होना है। उदाहरण के लिए, हम सच्चे स्वयंसिद्धों के एक सेट की कल्पना कर सकते हैं जो हमें प्राकृतिक संख्याओं के बारे में हर सच्चे अंकगणितीय दावे को सिद्ध करने की अनुमति देता है। (Smith 2007, p. 2). प्रथम-क्रम तर्क की मानक प्रणाली में, स्वयंसिद्धों का एक असंगत सेट प्रत्येक कथन को उसकी भाषा में सिद्ध करेगा (इसे कभी-कभी विस्फोट का सिद्धांत कहा जाता है), और इस प्रकार स्वचालित रूप से पूर्ण होता है। अभिगृहीतों का एक समुच्चय जो पूर्ण और सुसंगत दोनों है, तथापि, गैर-विरोधाभासी प्रमेयों का अधिकतम समुच्चय सिद्ध करता है।

पीनो अंकगणित, ZFC, और ZFC + के साथ पिछले अनुभागों में चित्रित पैटर्न में एक दुर्गम कार्डिनल मौजूद है जिसे आम तौर पर तोड़ा नहीं जा सकता है। यहाँ ZFC + मौजूद है एक दुर्गम कार्डिनल अपने आप से, सुसंगत साबित नहीं हो सकता। यह भी पूर्ण नहीं है, जैसा कि सातत्य परिकल्पना द्वारा चित्रित किया गया है, जो अनसुलझा है ZFC + में एक दुर्गम कार्डिनल मौजूद है।

पहली अपूर्णता प्रमेय से पता चलता है कि, औपचारिक प्रणालियों में जो मूल अंकगणित को व्यक्त कर सकते हैं, स्वयंसिद्धों की एक पूर्ण और सुसंगत परिमित सूची कभी नहीं बनाई जा सकती है: हर बार एक अतिरिक्त, सुसंगत कथन को एक अभिगृहीत के रूप में जोड़ा जाता है, ऐसे अन्य सत्य कथन होते हैं जो अभी भी नहीं हो सकते नए स्वयंसिद्ध के साथ भी सिद्ध हो। यदि कोई स्वयंसिद्ध जोड़ा जाता है जो सिस्टम को पूर्ण बनाता है, तो यह सिस्टम को असंगत बनाने की कीमत पर ऐसा करता है। स्वयंसिद्धों की एक अनंत सूची के लिए पूर्ण, सुसंगत और प्रभावी रूप से स्वयंसिद्ध होना भी संभव नहीं है।

पहला अपूर्णता प्रमेय

See also: Proof sketch for Gödel's first incompleteness theorem

गोडेल की पहली अपूर्णता प्रमेय पहली बार गोडेल के 1931 के पेपर प्रिंसिपिया मैथेमेटिका और संबंधित प्रणालियों के औपचारिक रूप से अनिर्णीत प्रस्तावों पर I में प्रमेय VI के रूप में दिखाई दिया। इसके बाद शीघ्र ही प्रमेय की परिकल्पना में सुधार किया गया J. Barkley Rosser (1936) रोसेर की चाल का उपयोग करना। परिणामी प्रमेय (रॉसर के सुधार को शामिल करते हुए) को अंग्रेजी में निम्नानुसार परिभाषित किया जा सकता है, जहां औपचारिक प्रणाली में यह धारणा शामिल है कि प्रणाली प्रभावी रूप से उत्पन्न होती है।

प्रथम अपूर्णता प्रमेय: कोई सुसंगत औपचारिक प्रणाली F जिसके भीतर एक निश्चित मात्रा में प्राथमिक अंकगणित किया जा सकता है, अधूरा है; यानी, की भाषा के बयान हैं F जिसे न तो सिद्ध किया जा सकता है और न ही असिद्ध किया जा सकता है F. (रातिकेनें 2020)</ब्लॉककोट>

अप्रमाणिक कथन {{math|G_F}प्रमेय द्वारा संदर्भित } को अक्सर सिस्टम के लिए गोडेल वाक्य के रूप में जाना जाता है F. सबूत सिस्टम के लिए एक विशेष गोडेल वाक्य बनाता है F, लेकिन सिस्टम की भाषा में असीम रूप से कई कथन हैं जो समान गुणों को साझा करते हैं, जैसे कि गोडेल वाक्य का संयोजन और तार्किक रूप से मान्य वाक्य।

प्रत्येक प्रभावी ढंग से उत्पन्न प्रणाली का अपना गोडेल वाक्य है। एक बड़ी प्रणाली को परिभाषित करना संभव है F' जिसमें संपूर्ण शामिल है F प्लस G_F एक अतिरिक्त स्वयंसिद्ध के रूप में। इसका परिणाम पूर्ण प्रणाली नहीं होगा, क्योंकि गोडेल का प्रमेय भी लागू होगा F', और इस तरह F' भी पूरा नहीं हो सकता। इस मामले में, G_F वास्तव में एक प्रमेय है F', क्योंकि यह एक स्वयंसिद्ध है। क्योंकि G_F केवल यह बताता है कि यह में साध्य नहीं है F, इसके भीतर इसकी उपयोगिता द्वारा कोई विरोधाभास प्रस्तुत नहीं किया गया है F'. हालाँकि, क्योंकि अपूर्णता प्रमेय लागू होता है F', एक नया गोडेल स्टेटमेंट होगा G_F' के लिए F', दिखा रहा है F' भी अधूरा है। G_F' से भिन्न होगा G_F के कारण से G_F' का उल्लेख करेंगे F', इसके बजायF.

गोडेल वाक्य का वाक्यात्मक रूप

गोडेल वाक्य को अप्रत्यक्ष रूप से खुद को संदर्भित करने के लिए डिज़ाइन किया गया है। वाक्य में कहा गया है कि, जब किसी अन्य वाक्य के निर्माण के लिए चरणों के एक विशेष क्रम का उपयोग किया जाता है, तो वह निर्मित वाक्य में सिद्ध नहीं होगा F. हालाँकि, चरणों का क्रम ऐसा है कि निर्मित वाक्य निकला G_F अपने आप। इस प्रकार, गोडेल वाक्य G_F परोक्ष रूप से भीतर अपनी स्वयं की अप्राप्यता बताता है F (Smith 2007, p. 135).

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

इस प्रकार, हालांकि गोडेल वाक्य अप्रत्यक्ष रूप से सिस्टम के वाक्यों को संदर्भित करता है F, जब एक अंकगणितीय कथन के रूप में पढ़ा जाता है तो गोडेल वाक्य सीधे केवल प्राकृतिक संख्याओं को संदर्भित करता है। यह दावा करता है कि किसी भी प्राकृतिक संख्या में कोई विशेष संपत्ति नहीं होती है, जहां वह संपत्ति आदिम पुनरावर्ती कार्य संबंध द्वारा दी जाती है (Smith 2007, p. 141). जैसे, गोडेल वाक्य को अंकगणित की भाषा में सरल वाक्य-विन्यास के रूप में लिखा जा सकता है। विशेष रूप से, इसे अंकगणित की भाषा में एक सूत्र के रूप में व्यक्त किया जा सकता है जिसमें कई प्रमुख सार्वभौमिक क्वांटिफायर होते हैं, जिसके बाद क्वांटिफायर-फ्री बॉडी होती है (ये सूत्र स्तर पर हैं) $\Pi _{1}^{0}$ अंकगणितीय पदानुक्रम का)। एमआरडीपी प्रमेय के माध्यम से, गोडेल वाक्य को एक बयान के रूप में फिर से लिखा जा सकता है कि पूर्णांक गुणांक वाले कई चर में एक विशेष बहुपद कभी भी मान शून्य नहीं लेता है जब पूर्णांक को उसके चर के लिए प्रतिस्थापित किया जाता है (Franzén 2005, p. 71).

गोडेल वाक्य का सत्य

प्रथम अपूर्णता प्रमेय से पता चलता है कि गोडेल वाक्य G_F एक उपयुक्त औपचारिक सिद्धांत का F में अप्राप्य है F. क्योंकि, जब अंकगणित के बारे में एक बयान के रूप में व्याख्या की जाती है, तो यह अप्राप्यता वास्तव में वाक्य (अप्रत्यक्ष रूप से) पर जोर देती है, गोडेल वाक्य वास्तव में सच है (Smoryński 1977, p. 825; यह भी देखें Franzén 2005, pp. 28–33). इस कारण यह वाक्य G_F को अक्सर सच कहा जाता है लेकिन इसे साबित नहीं किया जा सकता है। (Raatikainen 2020). हालाँकि, गोडेल वाक्य स्वयं औपचारिक रूप से अपनी इच्छित व्याख्या, वाक्य की सच्चाई को निर्दिष्ट नहीं कर सकता है G_F केवल सिस्टम के बाहर मेटा-विश्लेषण के माध्यम से पहुंचा जा सकता है। सामान्य तौर पर, यह मेटा-विश्लेषण कमजोर औपचारिक प्रणाली के भीतर किया जा सकता है जिसे आदिम पुनरावर्ती अंकगणित के रूप में जाना जाता है, जो निहितार्थ को सिद्ध करता है Con(F)→G_F, कहाँ Con(F) की निरंतरता पर जोर देने वाला एक विहित वाक्य है F (Smoryński 1977, p. 840, Kikuchi & Tanaka 1994, p. 403).

यद्यपि एक सुसंगत सिद्धांत का गोडेल वाक्य अंकगणित की इच्छित व्याख्या के बारे में एक बयान के रूप में सत्य है, गोडेल की पूर्णता प्रमेय के परिणामस्वरूप, गोडेल वाक्य कुछ पियानो स्वयंसिद्ध # गैर-मानक मॉडल में गलत होगा। (Franzén 2005, p. 135). उस प्रमेय से पता चलता है कि, जब एक वाक्य एक सिद्धांत से स्वतंत्र होता है, तो सिद्धांत में ऐसे मॉडल होंगे जिनमें वाक्य सत्य है और ऐसे मॉडल जिनमें वाक्य गलत है। जैसा कि पहले बताया गया है, सिस्टम का गोडेल वाक्य F एक अंकगणितीय कथन है जो दावा करता है कि किसी विशेष संपत्ति के साथ कोई संख्या मौजूद नहीं है। अपूर्णता प्रमेय दर्शाता है कि यह दावा प्रणाली से स्वतंत्र होगा F, और गोडेल वाक्य की सच्चाई इस तथ्य से अनुसरण करती है कि किसी भी मानक प्राकृतिक संख्या में संपत्ति का सवाल नहीं है। कोई भी मॉडल जिसमें गोडेल वाक्य गलत है, उसमें कुछ ऐसे तत्व होने चाहिए जो उस मॉडल के भीतर संपत्ति को संतुष्ट करते हों। ऐसा मॉडल गैर-मानक होना चाहिए - इसमें ऐसे तत्व होने चाहिए जो किसी भी मानक प्राकृतिक संख्या के अनुरूप न हों (Raatikainen 2020, Franzén 2005, p. 135).

झूठे विरोधाभास के साथ संबंध

गोडेल विशेष रूप से रिचर्ड के विरोधाभास और झूठा विरोधाभास को प्रिंसिपिया मैथमैटिका और संबंधित सिस्टम्स I में औपचारिक रूप से अनिर्णीत प्रस्ताव के परिचयात्मक खंड में उनके वाक्यात्मक अपूर्णता परिणाम के लिए सिमेंटिकल एनालॉग्स के रूप में उद्धृत करते हैं। झूठा विरोधाभास वाक्य है यह वाक्य झूठा है। झूठे वाक्य के विश्लेषण से पता चलता है कि यह सच नहीं हो सकता है (तब के लिए, जैसा कि यह दावा करता है, यह झूठा है), और न ही यह गलत हो सकता है (तब के लिए, यह सच है)। एक गोडेल वाक्य G सिस्टम के लिए F झूठा वाक्य के लिए एक समान दावा करता है, लेकिन सत्य के साथ प्रवीणता द्वारा प्रतिस्थापित किया जाता है: G कहते हैंG प्रणाली में साध्य नहीं है F. सच्चाई और साबित करने की क्षमता का विश्लेषण G झूठे वाक्य की सच्चाई के विश्लेषण का एक औपचारिक संस्करण है।

गोडेल वाक्य में असत्य के साथ सिद्ध नहीं होने को प्रतिस्थापित करना संभव नहीं है क्योंकि विधेयQ एक झूठे सूत्र की गोडेल संख्या है जिसे अंकगणित के सूत्र के रूप में प्रदर्शित नहीं किया जा सकता है। यह परिणाम, जिसे तर्स्की की अनिर्वचनीयता प्रमेय के रूप में जाना जाता है, गोडेल द्वारा स्वतंत्र रूप से खोजा गया था, जब वह अपूर्णता प्रमेय के प्रमाण पर काम कर रहे थे, और प्रमेय के नाम से, अल्फ्रेड टार्स्की द्वारा।

गोडेल के मूल परिणाम का विस्तार

गोडेल के 1931 के पेपर में बताए गए प्रमेयों की तुलना में, अपूर्णता प्रमेयों के कई समकालीन कथन दो तरह से अधिक सामान्य हैं। इन सामान्यीकृत बयानों को सिस्टम के व्यापक वर्ग पर लागू करने के लिए तैयार किया गया है, और उन्हें कमजोर स्थिरता मान्यताओं को शामिल करने के लिए तैयार किया गया है।

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

गोडेल के मूल कथन और अपूर्णता प्रमेय के प्रमाण के लिए इस धारणा की आवश्यकता है कि सिस्टम केवल संगत नहीं है बल्कि ओमेगा-संगत | ω-संगत है। एक प्रणाली 'ω-संगत' है यदि यह ω-असंगत नहीं है, और ω-असंगत है यदि कोई विधेय है P जैसे कि प्रत्येक विशिष्ट प्राकृतिक संख्या के लिए m सिस्टम साबित करता है ~P(m), और फिर भी सिस्टम यह भी साबित करता है कि एक प्राकृतिक संख्या मौजूद है n ऐसा है कि P(n). यानी, सिस्टम कहता है कि संपत्ति के साथ एक संख्या P इस बात से इनकार करते हुए मौजूद है कि इसका कोई विशिष्ट मूल्य है। एक प्रणाली की ω-संगति का तात्पर्य इसकी निरंतरता से है, लेकिन संगति का अर्थ ω-संगति नहीं है। J. Barkley Rosser (1936) ने अपूर्णता प्रमेय को सबूत (रॉसर की चाल) की भिन्नता को खोजने के द्वारा मजबूत किया, जिसके लिए सिस्टम को केवल ω-संगत होने के बजाय सुसंगत होने की आवश्यकता होती है। यह ज्यादातर तकनीकी रुचि का है, क्योंकि अंकगणित के सभी सच्चे औपचारिक सिद्धांत (सिद्धांत जिनके स्वयंसिद्ध प्राकृतिक संख्याओं के बारे में सभी सत्य कथन हैं) ω-संगत हैं, और इस प्रकार मूल रूप से कहा गया गोडेल का प्रमेय उन पर लागू होता है। अपूर्णता प्रमेय का मजबूत संस्करण जो केवल ω-संगति के बजाय स्थिरता मानता है, अब आमतौर पर गोडेल की अपूर्णता प्रमेय और गोडेल-रॉसर प्रमेय के रूप में जाना जाता है।

दूसरा अपूर्णता प्रमेय

प्रत्येक औपचारिक प्रणाली के लिए F मूल अंकगणित युक्त, कैनोनिक रूप से एक सूत्र को परिभाषित करना संभव है Cons(F) की निरंतरता व्यक्त करना F. यह सूत्र संपत्ति को व्यक्त करता है कि सिस्टम के भीतर एक औपचारिक व्युत्पत्ति कोडिंग करने वाली प्राकृतिक संख्या मौजूद नहीं है F जिसका निष्कर्ष एक वाक्यगत विरोधाभास है। वाक्यात्मक विरोधाभास को अक्सर 0=1 लिया जाता है, जिस स्थिति में Cons(F) बताता है कि कोई प्राकृतिक संख्या नहीं है जो '0 = 1' के स्वयंसिद्धों से व्युत्पत्ति को कोडित करती है F.

गोडेल की दूसरी अपूर्णता प्रमेय दिखाता है कि, सामान्य मान्यताओं के तहत, यह विहित संगति कथन Cons(F) में सिद्ध नहीं होगा F. प्रमेय पहली बार प्रमेय XI के रूप में गोडेल के 1931 के पेपर ऑन फॉर्मली अनडिसीडेबल प्रोपोज़िशन्स इन प्रिंसिपिया मैथेमेटिका एंड रिलेटेड सिस्टम्स I में दिखाई दिया। निम्नलिखित कथन में औपचारिक प्रणाली शब्द में एक धारणा भी शामिल है F प्रभावी रूप से स्वयंसिद्ध है।

दूसरा अधूरापन प्रमेय: किसी भी सुसंगत प्रणाली एफ के लिए जिसके भीतर एक निश्चित मात्रा में प्रारंभिक अंकगणित किया जा सकता है, एफ की संगति को एफ में ही सिद्ध नहीं किया जा सकता है। (Raatikainen 2020)

रूप में भी लिखा जा सकता है

मान लीजिए F एक सतत औपचारिक प्रणाली है जिसमें प्रारंभिक अंकगणित शामिल है। तब $F\not \vdash {\text{Cons}}(F)$. (Raatikainen 2020) (तब F, F की संगति सिद्ध नहीं करता है) </ब्लॉककोट>

यह प्रमेय पहले अपूर्णता प्रमेय से अधिक मजबूत है क्योंकि पहले अपूर्णता प्रमेय में निर्मित कथन प्रणाली की निरंतरता को सीधे व्यक्त नहीं करता है। सिस्टम के भीतर पहले अपूर्णता प्रमेय के प्रमाण को औपचारिक रूप देकर दूसरी अपूर्णता प्रमेय का प्रमाण प्राप्त किया जाता है F अपने आप।

निरंतरता व्यक्त करना

की संगति को व्यक्त करने की विधि के संबंध में दूसरे अपूर्णता प्रमेय में एक तकनीकी सूक्ष्मता है F की भाषा में एक सूत्र के रूप में F. एक प्रणाली की निरंतरता को व्यक्त करने के कई तरीके हैं, और उनमें से सभी एक ही परिणाम की ओर नहीं ले जाते हैं। सूत्र विपक्ष (F) दूसरी अपूर्णता प्रमेय से संगति की एक विशेष अभिव्यक्ति है।

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

हिल्बर्ट-बर्नेज़ की स्थिति

दूसरी अपूर्णता प्रमेय का मानक प्रमाण यह मानता है कि प्रवीणता विधेय है Prov_A(P) हिल्बर्ट-बर्नेज़ प्रोविबिलिटी शर्तों को संतुष्ट करता है। दे #(P) सूत्र के गोडेल संख्या का प्रतिनिधित्व करते हैं P, provability शर्तें कहती हैं:

1. अगर F साबित करता है P, तब F साबित करता है Prov_A(#(P)).
2. F 1 साबित करता है .; वह है, F साबित करता है Prov_A(#(P)) → Prov_A(#(Prov_A(#(P)))).
3. F साबित करता है Prov_A(#(P → Q)) ∧ Prov_A(#(P)) → Prov_A(#(Q))   (मूड सेट करना का एनालॉग)।

ऐसी प्रणालियाँ हैं, जैसे कि रॉबिन्सन अंकगणित, जो पहले अपूर्णता प्रमेय की मान्यताओं को पूरा करने के लिए पर्याप्त मजबूत हैं, लेकिन जो हिल्बर्ट-बर्नेज़ शर्तों को सिद्ध नहीं करती हैं। पीआनो अंकगणित, हालांकि, इन स्थितियों को सत्यापित करने के लिए काफी मजबूत है, जैसा कि सभी सिद्धांत पियानो अंकगणित से अधिक मजबूत हैं।

संगति प्रमाणों के लिए निहितार्थ

गोडेल की दूसरी अपूर्णता प्रमेय का अर्थ यह भी है कि एक प्रणाली F₁ ऊपर उल्लिखित तकनीकी शर्तों को पूरा करना किसी भी प्रणाली की निरंतरता को साबित नहीं कर सकता है F₂ की निरंतरता को सिद्ध करता है F₁. ऐसा इसलिए है क्योंकि ऐसी व्यवस्था है F₁ साबित कर सकता है कि अगर F₂ की निरंतरता सिद्ध करता है F₁, तब F₁ वास्तव में संगत है। उस दावे के लिए F₁ संगत है सभी नंबरों के लिए फॉर्म है n, n में विरोधाभास के सबूत के लिए कोड नहीं होने की निर्णायक संपत्ति है F₁ . अगर F₁ वास्तव में तब असंगत थे F₂ कुछ के लिए साबित होगा n वह n एक विरोधाभास का कोड है F₁. लेकिन अगर F₂ ने भी सिद्ध किया F₁ संगत है (अर्थात ऐसा नहीं है n), तो यह स्वयं असंगत होगा। इस तर्क को औपचारिक रूप दिया जा सकता है F₁ यह दिखाने के लिए कि अगर F₂ संगत है, तो F₁ संगत है। चूंकि, दूसरे अपूर्णता प्रमेय द्वारा, F₁ इसकी संगति सिद्ध नहीं करता, यह की संगति सिद्ध नहीं कर सकता F₂ दोनों में से एक।

दूसरे अपूर्णता प्रमेय के इस परिणाम से पता चलता है कि साबित करने की कोई उम्मीद नहीं है, उदाहरण के लिए, पीनो अंकगणित की निरंतरता किसी भी परिमित साधन का उपयोग करके जिसे एक प्रणाली में औपचारिक रूप दिया जा सकता है जिसकी स्थिरता पीनो अंकगणित (पीए) में सिद्ध होती है। उदाहरण के लिए, आदिम पुनरावर्ती अंकगणितीय (पीआरए) की प्रणाली, जिसे व्यापक रूप से परिमित गणित की सटीक औपचारिकता के रूप में स्वीकार किया जाता है, पीए में सिद्ध रूप से सुसंगत है। इस प्रकार पीआरए पीए की निरंतरता को सिद्ध नहीं कर सकता है। इस तथ्य को आम तौर पर यह माना जाता है कि हिल्बर्ट का कार्यक्रम, जिसका उद्देश्य वास्तविक (फिनिटिस्टिक) गणितीय बयानों के प्रमाणों में आदर्श (अनंतवादी) गणितीय सिद्धांतों के उपयोग को न्यायोचित ठहराना है, जो आदर्श सिद्धांतों के अनुरूप होने का अंतिम प्रमाण देता है, नहीं किया जा सकता (Franzén 2005, p. 106).

उपप्रमेय दूसरे अपूर्णता प्रमेय की ज्ञानमीमांसीय प्रासंगिकता को भी इंगित करता है। यह वास्तव में कोई रोचक जानकारी प्रदान नहीं करेगा यदि कोई सिस्टम F ने अपनी निरंतरता साबित की। ऐसा इसलिए है क्योंकि असंगत सिद्धांत सब कुछ साबित करते हैं, जिसमें उनकी निरंतरता भी शामिल है। इस प्रकार एक संगति प्रमाण F में F हमें इस बात का कोई सुराग नहीं देगा कि क्या F वास्तव में संगत है; की निरंतरता पर कोई संदेह नहीं है F इस तरह के एक संगति प्रमाण द्वारा हल किया जाएगा। संगति प्रमाणों में रुचि एक प्रणाली की संगति को सिद्ध करने की संभावना में निहित है F किसी प्रणाली में F' जो किसी मायने में कम संदिग्ध है F ही, उदाहरण के लिए से कमजोर F. कई स्वाभाविक रूप से होने वाले सिद्धांतों के लिए F और F', जैसे कि F = ज़र्मेलो-फ्रेंकेल सेट सिद्धांत और F' = आदिम पुनरावर्ती अंकगणित, की संगति F' में साध्य है F, और इस तरह F' की संगति सिद्ध नहीं कर सकता F दूसरे अपूर्णता प्रमेय के उपरोक्त परिणाम द्वारा।

दूसरा अपूर्णता प्रमेय किसी सिद्धांत की निरंतरता को साबित करने की संभावना को पूरी तरह से खारिज नहीं करता है T, केवल एक सिद्धांत में ऐसा करना T ही संगत सिद्ध हो सकता है। उदाहरण के लिए, गेरहार्ड जेंटजन ने एक अलग प्रणाली में पीनो अंकगणित की निरंतरता को सिद्ध किया जिसमें एक स्वयंसिद्ध शामिल है जो यह दावा करता है कि क्रमसूचक संख्या कहलाती है। ε₀ अच्छी तरह से स्थापित है; जेंटजन का कंसिस्टेंसी प्रूफ देखें। Gentzen के प्रमेय ने प्रमाण सिद्धांत में क्रमिक विश्लेषण के विकास को प्रेरित किया।

अनिर्णायक बयानों के उदाहरण

See also: List of statements independent of ZFC

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

अनिर्णीत शब्द के दो अर्थों के कारण, स्वतंत्रता (गणितीय तर्क) शब्द का प्रयोग कभी-कभी न तो सिद्ध करने योग्य और न ही खंडन योग्य अर्थों के लिए अनिर्णीत के बजाय किया जाता है।

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

गोडेल और पॉल कोहेन (गणितज्ञ) के संयुक्त कार्य ने अनिर्णीत कथनों के दो ठोस उदाहरण दिए हैं (शब्द के पहले अर्थ में): सातत्य परिकल्पना को ZFC में न तो सिद्ध किया जा सकता है और न ही उसका खंडन किया जा सकता है (सेट सिद्धांत का मानक स्वयंसिद्धीकरण), और पसंद के स्वयंसिद्ध को ZF में न तो सिद्ध किया जा सकता है और न ही खंडन किया जा सकता है (जो पसंद के स्वयंसिद्ध को छोड़कर सभी ZFC स्वयंसिद्ध हैं)। इन परिणामों के लिए अपूर्णता प्रमेय की आवश्यकता नहीं है। गोडेल ने 1940 में साबित किया कि इनमें से किसी भी कथन को ZF या ZFC सेट थ्योरी में अप्रमाणित नहीं किया जा सकता है। 1960 के दशक में, कोहेन ने साबित किया कि न तो ZF से सिद्ध किया जा सकता है, और निरंतर परिकल्पना को ZFC से सिद्ध नहीं किया जा सकता है।

1973 में, सहारों शेलाह ने दिखाया कि समूह सिद्धांत में व्हाइटहेड समस्या शब्द के पहले अर्थ में, मानक सेट सिद्धांत में अनिर्णीत है। ग्रेगरी चैतिन ने एल्गोरिथम सूचना सिद्धांत में अनिर्णायक बयान दिए और उस सेटिंग में एक और अपूर्णता प्रमेय साबित किया। चैटिन की अपूर्णता प्रमेय कहती है कि किसी भी प्रणाली के लिए जो पर्याप्त अंकगणित का प्रतिनिधित्व कर सकती है, एक ऊपरी सीमा होती है c जैसे कि कोलमोगोरोव जटिलता से अधिक होने के लिए उस प्रणाली में कोई विशिष्ट संख्या साबित नहीं की जा सकती c. जबकि गोडेल का प्रमेय झूठा विरोधाभास से संबंधित है, चैतिन का परिणाम बेरी के विरोधाभास से संबंधित है।

बड़ी प्रणालियों में सिद्ध होने वाले अनिर्णायक कथन

ये गोडेल के सच्चे लेकिन अनिर्णायक वाक्य के प्राकृतिक गणितीय समकक्ष हैं। उन्हें एक बड़ी प्रणाली में सिद्ध किया जा सकता है जिसे आम तौर पर तर्क के एक वैध रूप के रूप में स्वीकार किया जाता है, लेकिन पीनो अंकगणित जैसे अधिक सीमित प्रणाली में अपरिहार्य हैं।

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

क्रस्कल के पेड़ प्रमेय, जिसमें कंप्यूटर विज्ञान में अनुप्रयोग हैं, पीनो अंकगणित से भी अपरिहार्य है लेकिन सेट सिद्धांत में सिद्ध है। वास्तव में क्रुस्कल का वृक्ष प्रमेय (या इसका परिमित रूप) एक अधिक मजबूत प्रणाली एटीआर में अनिर्णीत है₀ गणित के एक दर्शन के आधार पर स्वीकार्य सिद्धांतों को संहिताबद्ध करना जिसे प्रतिरूपकता कहा जाता है। संबंधित लेकिन अधिक सामान्य ग्राफ मामूली प्रमेय (2003) में कम्प्यूटेशनल जटिलता सिद्धांत के परिणाम हैं।

कम्प्यूटेबिलिटी के साथ संबंध

See also: Halting problem § Gödel's incompleteness theorems

अपूर्णता प्रमेय पुनरावर्तन सिद्धांत में अनिर्णायक सेट के बारे में कई परिणामों से निकटता से संबंधित है।

Stephen Cole Kleene (1943) संगणनीयता सिद्धांत के बुनियादी परिणामों का उपयोग करते हुए गोडेल के अपूर्णता प्रमेय का प्रमाण प्रस्तुत किया। ऐसे ही एक परिणाम से पता चलता है कि रुकने की समस्या अनिर्णीत है: ऐसा कोई कंप्यूटर प्रोग्राम नहीं है जो किसी भी प्रोग्राम को सही ढंग से निर्धारित कर सके P इनपुट के रूप में, चाहे P किसी विशेष दिए गए इनपुट के साथ चलने पर अंततः रुक जाता है। क्लेन ने दिखाया कि कुछ स्थिरता गुणों के साथ अंकगणित की एक पूर्ण प्रभावी प्रणाली का अस्तित्व रुकने की समस्या को निर्णायक, एक विरोधाभासी होने के लिए मजबूर करेगा। प्रमाण की इस विधि द्वारा भी प्रस्तुत किया गया है Shoenfield (1967, p. 132); Charlesworth (1981); और Hopcroft & Ullman (1979).

Franzén (2005, p. 73) समझाता है कि मटियासेविच की प्रमेय | हिल्बर्ट की 10वीं समस्या के मटियासेविच के समाधान का उपयोग गोडेल की पहली अपूर्णता प्रमेय का प्रमाण प्राप्त करने के लिए किया जा सकता है। यूरी मटियासेविच ने साबित किया कि बहुभिन्नरूपी बहुपद दिए जाने पर कोई एल्गोरिद्म नहीं है p(x₁, x₂,...,x_k) पूर्णांक गुणांक के साथ, यह निर्धारित करता है कि समीकरण का पूर्णांक समाधान है या नहीं p = 0. क्योंकि पूर्णांक गुणांक वाले बहुपद, और स्वयं पूर्णांक, अंकगणित की भाषा में सीधे अभिव्यक्त होते हैं, यदि एक बहुभिन्नरूपी पूर्णांक बहुपद समीकरण p = 0 का पूर्णांकों में समाधान है तो अंकगणित की कोई भी पर्याप्त मजबूत प्रणाली T यह सिद्ध करेगा। इसके अलावा, यदि सिस्टम T ω-सुसंगत है, तो यह कभी भी सिद्ध नहीं होगा कि किसी विशेष बहुपद समीकरण का एक हल है जबकि वास्तव में पूर्णांकों में कोई हल नहीं है। इस प्रकार, यदि T पूर्ण और ω-सुसंगत थे, तो एल्गोरिथम से यह निर्धारित करना संभव होगा कि बहुपद समीकरण का समाधान केवल निम्न के प्रमाणों की गणना करके है या नहीं। T या तो तकp का समाधान है याp मटियासेविच के प्रमेय के विपरीत कोई समाधान नहीं मिला है। इसलिए यह इस प्रकार है T हो नहीं सकता w-संगत और पूर्ण। इसके अलावा, प्रत्येक सुसंगत प्रभावी रूप से उत्पन्न प्रणाली के लिए T, प्रभावी रूप से एक बहुभिन्नरूपी बहुपद उत्पन्न करना संभव है p पूर्णांकों पर जैसे कि समीकरण p = 0 का पूर्णांकों पर कोई हल नहीं है, लेकिन समाधान के अभाव को में सिद्ध नहीं किया जा सकता है T (Davis 2006, p. 416; Jones 1980).

Smoryński (1977, p. 842) दिखाता है कि पहले अपूर्णता प्रमेय को सिद्ध करने के लिए पुनरावर्ती अविभाज्य सेटों के अस्तित्व का उपयोग कैसे किया जा सकता है। यह सबूत अक्सर यह दिखाने के लिए बढ़ाया जाता है कि पियानो अंकगणित जैसी प्रणालियां अनिवार्य रूप से अनिर्णीत हैं (देखें Kleene 1967, p. 274).

कोल्मोगोरोव जटिलता के आधार पर, चैतिन की अपूर्णता प्रमेय स्वतंत्र वाक्यों के निर्माण की एक अलग विधि देती है। क्लेन द्वारा प्रस्तुत किए गए प्रमाण की तरह, जिसका उल्लेख ऊपर किया गया था, चैटिन की प्रमेय केवल उन सिद्धांतों पर लागू होती है जिनमें अतिरिक्त संपत्ति है कि उनके सभी स्वयंसिद्ध प्राकृतिक संख्याओं के मानक मॉडल में सत्य हैं। गोडेल की अपूर्णता प्रमेय को सुसंगत सिद्धांतों के लिए इसकी प्रयोज्यता से अलग किया जाता है, फिर भी मानक मॉडल में झूठे बयानों को शामिल किया जाता है; इन सिद्धांतों को ω-सुसंगत सिद्धांत|ω-असंगत के रूप में जाना जाता है।

पहले प्रमेय के लिए सबूत स्केच

Main article: Proof sketch for Gödel's first incompleteness theorem

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

1. सिस्टम में कथनों को प्राकृतिक संख्याओं (गोडेल संख्या के रूप में जाना जाता है) द्वारा दर्शाया जा सकता है। इसका महत्व यह है कि बयानों के गुण - जैसे उनकी सच्चाई और झूठ - यह निर्धारित करने के बराबर होंगे कि क्या उनके गोडेल नंबरों में कुछ गुण हैं, और इसलिए बयानों के गुणों को उनके गोडेल नंबरों की जांच करके प्रदर्शित किया जा सकता है। यह भाग उस कथन के विचार को व्यक्त करने वाले सूत्र के निर्माण में परिणत होता है S प्रणाली में साध्य है (जिसे किसी भी कथन पर लागू किया जा सकता हैS प्रणाली में)।
2. औपचारिक प्रणाली में एक संख्या का निर्माण करना संभव है जिसका मिलान कथन, जब व्याख्या की जाती है, स्वयं संदर्भ | स्व-संदर्भित होता है और अनिवार्य रूप से कहता है कि यह (अर्थात् स्वयं कथन) असाध्य है। यह विकर्ण लेम्मा नामक एक तकनीक का उपयोग करके किया जाता है (कैंटर के विकर्ण तर्क के रूप में इसकी उत्पत्ति के कारण तथाकथित)।
3. औपचारिक प्रणाली के भीतर यह कथन एक प्रदर्शन की अनुमति देता है कि यह सिस्टम में न तो साबित करने योग्य है और न ही अस्वीकार्य है, और इसलिए सिस्टम वास्तव में ω-संगत नहीं हो सकता है। इसलिए मूल धारणा कि प्रस्तावित प्रणाली मानदंडों को पूरा करती है, गलत है।

सिंटैक्स का अंकगणित

ऊपर वर्णित प्रमाण को स्पष्ट करने में मुख्य समस्या यह है कि पहली बार में ऐसा लगता है कि एक कथन का निर्माण करना है p के बराबर हैp सिद्ध नहीं किया जा सकता, p में किसी तरह का संदर्भ होना चाहिए p, जो आसानी से अनंत प्रतिगमन को जन्म दे सकता है। गोडेल की तकनीक यह दिखाने के लिए है कि बयानों को संख्याओं (अक्सर वाक्य - विन्यास के अंकगणित कहा जाता है) के साथ इस तरह से मिलान किया जा सकता है कि किसी कथन को साबित करने के लिए परीक्षण के साथ प्रतिस्थापित किया जा सकता है कि किसी संख्या में दी गई संपत्ति है या नहीं। यह एक स्व-संदर्भ सूत्र को इस तरह से निर्मित करने की अनुमति देता है जो परिभाषाओं के किसी भी अनंत प्रतिगमन से बचा जाता है। उसी तकनीक का बाद में एलन ट्यूरिंग ने Entscheidungsproblem पर अपने काम में उपयोग किया था।

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

• शब्द 'helloASCII में 104-101-108-108-111 के रूप में एन्कोड किया गया है, जिसे संख्या 104101108108111 में परिवर्तित किया जा सकता है।
• तार्किक कथनx=y => y=xASCII में 120-061-121-032-061-062-032-121-061-120 के रूप में एन्कोड किया गया है, जिसे संख्या 120061121032061062032121061120 में परिवर्तित किया जा सकता है।

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

प्रवीणता के बारे में एक बयान का निर्माण

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

एक सूत्र F(x) जिसमें ठीक एक मुक्त चर शामिल है x को स्टेटमेंट फॉर्म या क्लास-साइन कहा जाता है। अस सून अस x को एक विशिष्ट संख्या से बदल दिया जाता है, स्टेटमेंट फॉर्म एक सदाशयी स्टेटमेंट में बदल जाता है, और यह तब या तो सिस्टम में साबित होता है, या नहीं। कुछ सूत्रों के लिए कोई यह दिखा सकता है कि प्रत्येक प्राकृतिक संख्या के लिए n, $F(n)$ सच है अगर और केवल अगर यह साबित किया जा सकता है (मूल सबूत में सटीक आवश्यकता कमजोर है, लेकिन सबूत स्केच के लिए यह पर्याप्त होगा)। विशेष रूप से, यह प्राकृतिक संख्याओं की परिमित संख्या, जैसे 2 के बीच प्रत्येक विशिष्ट अंकगणितीय संक्रिया के लिए सत्य है × 3 = 6।

कथन प्रपत्र स्वयं कथन नहीं होते हैं और इसलिए इन्हें सिद्ध या अप्रमाणित नहीं किया जा सकता है। लेकिन हर कथन प्रपत्र F(x) द्वारा निरूपित एक गोडेल संख्या निर्दिष्ट की जा सकती है G(F). प्रपत्र में प्रयुक्त मुक्त चर का चुनाव F(x) गोडेल नंबर के असाइनमेंट के लिए प्रासंगिक नहीं है G(F).

साध्यता की धारणा को भी गोडेल नंबरों द्वारा निम्नलिखित तरीके से एन्कोड किया जा सकता है: चूँकि एक प्रमाण उन कथनों की एक सूची है जो कुछ नियमों का पालन करते हैं, एक प्रमाण के गोडेल नंबर को परिभाषित किया जा सकता है। अब, प्रत्येक कथन के लिए p, कोई पूछ सकता है कि क्या कोई संख्या है x इसके प्रमाण की गोडेल संख्या है। गोडेल संख्या के बीच संबंध p और x, इसके प्रमाण की संभावित गोडेल संख्या, दो संख्याओं के बीच अंकगणितीय संबंध है। इसलिए, एक कथन रूप है Bew(y) जो इस अंकगणितीय संबंध का उपयोग यह बताने के लिए करता है कि एक गोडेल संख्या का एक प्रमाण है y मौजूद:

Bew(y) = ∃ x (y सूत्र की गोडेल संख्या है और x कोडित सूत्र के प्रमाण की गोडेल संख्या है y).

Bew नाम beweisbar के लिए छोटा है, जो कि प्रूवेबल के लिए जर्मन शब्द है; यह नाम मूल रूप से गोडेल द्वारा प्रयोग किया गया था, जो अभी वर्णित सिद्धता सूत्र को दर्शाने के लिए किया गया था। ध्यान दें किBew(y) केवल एक संक्षिप्त नाम है जो मूल भाषा में एक विशेष, बहुत लंबे, सूत्र का प्रतिनिधित्व करता है T; डोरBew खुद इस भाषा का हिस्सा होने का दावा नहीं करता है।

सूत्र की एक महत्वपूर्ण विशेषता Bew(y) यह है कि अगर एक बयान p तब सिस्टम में साबित होता है Bew(G(p)) भी साध्य है। ऐसा इसलिए है क्योंकि कोई सबूत p का एक संगत गोडेल नंबर होगा, जिसके अस्तित्व का कारण बनता है Bew(G(p)) संतोष होना।

विकर्णकरण

सबूत में अगला कदम एक बयान प्राप्त करना है, जो अप्रत्यक्ष रूप से अपनी खुद की अप्राप्यता पर जोर देता है। हालांकि गोडेल ने सीधे तौर पर इस कथन का निर्माण किया, कम से कम एक ऐसे बयान का अस्तित्व विकर्ण लेम्मा से होता है, जो कहता है कि किसी भी पर्याप्त रूप से मजबूत औपचारिक प्रणाली और किसी भी बयान के लिए F एक कथन है p ऐसा कि सिस्टम साबित करता है

p ↔ F(G(p)).

जैसे भी हो F का निषेध हो Bew(x), हम प्रमेय प्राप्त करते हैं

p ↔ ~Bew(G(p))

और यह p इसके द्वारा परिभाषित मोटे तौर पर कहा गया है कि इसका अपना गोडेल नंबर एक अप्राप्य सूत्र का गोडेल नंबर है।

कथन p सचमुच के बराबर नहीं है ~Bew(G(p)); की अपेक्षा, p बताता है कि यदि एक निश्चित गणना की जाती है, तो परिणामी गोडेल संख्या एक अप्राप्य कथन की होगी। लेकिन जब यह गणना की जाती है, तो परिणामी गोडेल संख्या की गोडेल संख्या बन जाती है p अपने आप। यह अंग्रेजी में निम्नलिखित वाक्य के समान है:

, जब उद्धरणों में स्वयं से पहले, अप्राप्य है। , जब उद्धरणों में अपने आप से पहले आता है, तो यह असाध्य है।

यह वाक्य प्रत्यक्ष रूप से स्वयं को संदर्भित नहीं करता है, लेकिन जब कहा गया परिवर्तन किया जाता है तो परिणामस्वरूप मूल वाक्य प्राप्त होता है, और इस प्रकार यह वाक्य अप्रत्यक्ष रूप से अपनी स्वयं की अप्राप्यता का दावा करता है। विकर्ण लेम्मा का प्रमाण एक समान विधि का उपयोग करता है।

अब, मान लें कि अभिगृहीत प्रणाली ओमेगा-संगत | ω-संगत है, और चलो p पिछले अनुभाग में प्राप्त कथन हो।

अगर p साध्य थे, तब Bew(G(p)) सिद्ध होगा, जैसा कि ऊपर तर्क दिया गया है। लेकिन p की अस्वीकृति का दावा करता है Bew(G(p)). इस प्रकार प्रणाली असंगत होगी, एक बयान और इसकी अस्वीकृति दोनों को साबित करेगी। यह विरोधाभास दर्शाता है p साध्य नहीं हो सकता।

यदि का निषेध p साध्य थे, तब Bew(G(p)) साध्य होगा (क्योंकि p के नकार के बराबर होने के लिए बनाया गया था Bew(G(p))). हालांकि, प्रत्येक विशिष्ट संख्या के लिए x, x के प्रमाण का गोडेल नंबर नहीं हो सकता p, क्योंकि p साध्य नहीं है (पिछले पैराग्राफ से)। इस प्रकार एक तरफ सिस्टम साबित करता है कि एक निश्चित संपत्ति के साथ एक संख्या है (कि यह सबूत का गोडेल नंबर है) p), लेकिन दूसरी ओर, प्रत्येक विशिष्ट संख्या के लिए x, हम यह सिद्ध कर सकते हैं कि उसके पास यह गुण नहीं है। ω-संगत प्रणाली में यह असंभव है। इस प्रकार की अस्वीकृति p साध्य नहीं है।

इस प्रकार कथन p हमारी स्वयंसिद्ध प्रणाली में अनिर्णायक है: इसे न तो सिद्ध किया जा सकता है और न ही प्रणाली के भीतर अस्वीकृत किया जा सकता है।

दरअसल, यह दिखाने के लिए p साध्य नहीं है केवल इस धारणा की आवश्यकता है कि सिस्टम सुसंगत है। ω-संगति की प्रबल मान्यता यह दर्शाने के लिए आवश्यक है कि का निषेधन p साध्य नहीं है। इस प्रकार, यदि p एक विशेष प्रणाली के लिए बनाया गया है:

• यदि निकाय ω-सुसंगत है, तो यह न तो सिद्ध कर सकता है p और न ही इसकी अस्वीकृति, और इसी तरह p अनिर्णीत है।
• यदि व्यवस्था सुसंगत है, तो उसकी वही स्थिति हो सकती है, या वह नकारा साबित हो सकता है p. बाद के मामले में, हमारे पास एक बयान है (नहीं p ) जो झूठा है लेकिन साबित करने योग्य है, और सिस्टम ω-संगत नहीं है।

यदि सिस्टम की अपूर्णता से बचने के लिए कोई लापता स्वयंसिद्धों को जोड़ने का प्रयास करता है, तो उसे या तो जोड़ना होगा p या नहीं p स्वयंसिद्ध के रूप में। लेकिन तब किसी कथन के प्रमाण की गोडेल संख्या होने की परिभाषा बदल जाती है। जिसका अर्थ है कि सूत्र Bew(x) अब अलग है। इस प्रकार जब हम विकर्ण लेम्मा को इस नए Bew पर लागू करते हैं, तो हमें एक नया कथन प्राप्त होता है p, पिछले वाले से अलग है, जो कि ω-सुसंगत होने पर नई प्रणाली में अनिर्णीत होगा।

बेरी के विरोधाभास के माध्यम से सबूत

George Boolos (1989) पहले अपूर्णता प्रमेय के एक वैकल्पिक प्रमाण को रेखाचित्र बनाता है जो एक सच्चे लेकिन अप्राप्य सूत्र के निर्माण के लिए झूठा विरोधाभास के बजाय बेरी के विरोधाभास का उपयोग करता है। शाऊल क्रिपके द्वारा स्वतंत्र रूप से एक समान प्रमाण विधि की खोज की गई थी (Boolos 1998, p. 383). बूलोस का प्रमाण किसी भी संगणनीय गणना योग्य सेट के निर्माण के द्वारा आगे बढ़ता है S अंकगणित के सच्चे वाक्यों का, एक और वाक्य जो सत्य है लेकिन इसमें समाहित नहीं है S. यह प्रथम अपूर्णता प्रमेय को परिणाम के रूप में देता है। बूलोस के अनुसार, यह प्रमाण दिलचस्प है क्योंकि यह अंकगणित के प्रभावी, सुसंगत सिद्धांतों की अपूर्णता के लिए एक अलग प्रकार का कारण प्रदान करता है। (Boolos 1998, p. 388).

कंप्यूटर सत्यापित प्रमाण

See also: Automated theorem proving

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

नटराजन शंकर द्वारा Nqthm का उपयोग करते हुए 1986 में पहली अपूर्णता प्रमेय के संस्करणों के कंप्यूटर-सत्यापित प्रमाणों की घोषणा की गई थी। (Shankar 1994), रसेल ओ'कॉनर द्वारा 2003 में Coq का उपयोग करते हुए (O'Connor 2005) और जॉन हैरिसन द्वारा 2009 में एचओएल लाइट का उपयोग करते हुए (Harrison 2009). लॉरेंस पॉलसन द्वारा 2013 में इसाबेल प्रमेय कहावत का उपयोग करते हुए दोनों अपूर्णता प्रमेयों का एक कंप्यूटर-सत्यापित प्रमाण घोषित किया गया था (Paulson 2014).

दूसरे प्रमेय के लिए सबूत स्केच

See also: Hilbert–Bernays provability conditions

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

होने देना p ऊपर निर्मित अनिर्णायक वाक्य के लिए खड़ा है, और एक विरोधाभास प्राप्त करने के प्रयोजनों के लिए मान लें कि सिस्टम की स्थिरता S सिस्टम के भीतर से साबित किया जा सकता है S अपने आप। यह कथन प्रणाली को सिद्ध करने के बराबर है S संगत है । अब कथन पर विचार करें c, कहाँ c = यदि सिस्टम S संगत है, तो p साध्य नहीं है। वाक्य का प्रमाण c सिस्टम के भीतर औपचारिक रूप दिया जा सकता है S, और इसलिए बयान c,p साध्य नहीं है, (या समान रूप से, नहीं P(p) ) प्रणाली में सिद्ध किया जा सकता है S.

तो निरीक्षण करें, कि अगर हम साबित कर सकते हैं कि system S सुसंगत है (अर्थात की परिकल्पना में कथन c), तो हमने यह साबित कर दिया है p साध्य नहीं है। लेकिन यह एक विरोधाभास है क्योंकि प्रथम अपूर्णता प्रमेय के अनुसार, यह वाक्य (अर्थात् वाक्य में निहित है) c,p साध्य नहीं है ) वह है जिसे हम अप्राप्य बनाते हैं। ध्यान दें कि यही कारण है कि हमें पहले अपूर्णता प्रमेय को औपचारिक रूप देने की आवश्यकता है S: द्वितीय अपूर्णता प्रमेय को सिद्ध करने के लिए, हम प्रथम अपूर्णता प्रमेय के साथ एक विरोधाभास प्राप्त करते हैं जो केवल यह दिखा कर कर सकता है कि प्रमेय में निहित है S. इसलिए हम यह साबित नहीं कर सकते कि सिस्टम S संगत है। और दूसरा अपूर्णता प्रमेय कथन इस प्रकार है।

चर्चा और निहितार्थ

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

तर्कवाद के परिणाम और हिल्बर्ट की दूसरी समस्या

अपूर्णता प्रमेय को कभी-कभी भगवान फ्रीज का शुक्र है और बर्ट्रेंड रसेल द्वारा प्रस्तावित तार्किकता के कार्यक्रम के लिए गंभीर परिणाम माना जाता है, जिसका उद्देश्य तर्क के संदर्भ में प्राकृतिक संख्याओं को परिभाषित करना था। (Hellman 1981, pp. 451–468). बॉब हेल (दार्शनिक) और क्रिस्पिन राइट तर्क देते हैं कि तर्कवाद के लिए यह कोई समस्या नहीं है क्योंकि अपूर्णता प्रमेय पहले क्रम के तर्क पर समान रूप से लागू होते हैं जैसे वे अंकगणित पर लागू होते हैं। उनका तर्क है कि केवल उन लोगों को यह समस्या है जो मानते हैं कि प्राकृतिक संख्याओं को प्रथम क्रम तर्क के संदर्भ में परिभाषित किया जाना है।

कई तर्कशास्त्रियों का मानना ​​है कि गोडेल के अधूरे प्रमेय ने डेविड हिल्बर्ट की हिल्बर्ट की दूसरी समस्या के लिए एक घातक झटका मारा, जिसने गणित के लिए एक परिमित स्थिरता प्रमाण मांगा। दूसरी अपूर्णता प्रमेय, विशेष रूप से, अक्सर समस्या को असंभव बनाने के रूप में देखी जाती है। हालांकि, सभी गणितज्ञ इस विश्लेषण से सहमत नहीं हैं, और हिल्बर्ट की दूसरी समस्या की स्थिति अभी तक तय नहीं हुई है (देखें हिल्बर्ट की दूसरी समस्या #समस्या की स्थिति पर आधुनिक दृष्टिकोण)।

मन और मशीन

Main article: Mechanism (philosophy) § Gödelian arguments

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

Hilary Putnam (1960) ने सुझाव दिया कि गोडेल के प्रमेयों को मनुष्यों पर लागू नहीं किया जा सकता है, क्योंकि वे गलतियाँ करते हैं और इसलिए असंगत हैं, यह सामान्य रूप से विज्ञान या गणित के मानव संकाय पर लागू हो सकता है। यह मानते हुए कि यह सुसंगत है, या तो इसकी संगति सिद्ध नहीं की जा सकती है या इसे ट्यूरिंग मशीन द्वारा प्रदर्शित नहीं किया जा सकता है।

Avi Wigderson (2010) ने प्रस्तावित किया है कि गणितीय ज्ञान की अवधारणा तार्किक निर्णयनीयता के बजाय कम्प्यूटेशनल जटिलता सिद्धांत पर आधारित होनी चाहिए। वह लिखते हैं कि जब ज्ञान की व्याख्या आधुनिक मानकों द्वारा की जाती है, अर्थात् कम्प्यूटेशनल जटिलता के माध्यम से, गोडेल घटनाएं हमारे साथ बहुत अधिक हैं।

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

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

मन के मामले में, एक कहीं अधिक जटिल औपचारिक प्रणाली, हॉफस्टाटर के विचार में, यह अधोमुखी कारणता अनिर्वचनीय मानव प्रवृत्ति के रूप में प्रकट होती है कि हमारे मन की कार्य-कारण इच्छाओं, अवधारणाओं, व्यक्तित्वों, विचारों और विचारों के उच्च स्तर पर स्थित है, न्यूरॉन या यहां तक ​​कि मौलिक कणों के बीच बातचीत के निम्न स्तर पर होने के बजाय, भले ही भौतिकी के अनुसार बाद वाले में कारण शक्ति होती है।

इस प्रकार दुनिया को समझने के हमारे सामान्य मानवीय तरीके में एक अजीब उल्टापन है: हम "छोटे सामान" के बजाय "बड़े सामान" को देखने के लिए बने हैं, भले ही छोटे का डोमेन ऐसा लगता है जहां वास्तविक मोटर्स वास्तविकता चला रहे हैं रहते हैं। (आई एम अ स्ट्रेंज लूप।)

परासंगत तर्क

हालांकि गोडेल के प्रमेयों का आमतौर पर शास्त्रीय तर्क के संदर्भ में अध्ययन किया जाता है, लेकिन पैराकंसिस्टेंट लॉजिक और स्वाभाविक रूप से विरोधाभासी बयानों (भाषण ) के अध्ययन में भी उनकी भूमिका होती है। Graham Priest (1984, 2006) का तर्क है कि अनौपचारिक प्रमाण की सामान्य धारणा के साथ गोडेल के प्रमेय में औपचारिक प्रमाण की धारणा को बदलने के लिए इस्तेमाल किया जा सकता है, यह दिखाने के लिए कि भोली गणित असंगत है, और इसे डायलेथिज़्म के सबूत के रूप में उपयोग करती है। इस असंगति का कारण प्रणाली की भाषा के भीतर एक प्रणाली के लिए सत्य विधेय का समावेश है (Priest 2006, p. 47). Stewart Shapiro (2002) गोडेल के प्रमेयों के डायलेटिज्म के अनुप्रयोगों का अधिक मिश्रित मूल्यांकन देता है।

अन्य क्षेत्रों में अपूर्णता प्रमेयों के लिए अपील

गणित और तर्क से परे जाने वाले तर्कों के समर्थन में कभी-कभी अपूर्णता प्रमेयों की अपील और उपमाएँ की जाती हैं। कई लेखकों ने इस तरह के विस्तार और व्याख्याओं पर नकारात्मक टिप्पणी की है, जिसमें टोर्केल फ्रेंज़ेन (2005); पानू Raatikainen (2005); Alan Sokal and Jean Bricmont (1999); और Ophelia Benson and Jeremy Stangroom (2006). Sokal & Bricmont (1999), और Stangroom & Benson (2006, p. 10), उदाहरण के लिए, रेबेका गोल्डस्टीन की गोडेल के स्वीकृत गणितीय प्लैटोनिज्म और विरोधी-यथार्थवादी उपयोगों के बीच असमानता पर टिप्पणियों से उद्धरण, जिसमें उनके विचारों को कभी-कभी रखा जाता है। Sokal & Bricmont (1999, p. 187) समाजशास्त्र के संदर्भ में रेगिस डेब्रे के प्रमेय के आह्वान की आलोचना करें; डेब्रे ने इस प्रयोग को लाक्षणिक (ibid.) के रूप में बचाव किया है।

इतिहास

1929 में गोडेल ने अपने डॉक्टरेट थीसिस के रूप में पूर्णता प्रमेय के अपने प्रमाण को प्रकाशित करने के बाद, उन्होंने अपने आवास के लिए दूसरी समस्या की ओर रुख किया। उनका मूल लक्ष्य हिल्बर्ट की दूसरी समस्या का सकारात्मक समाधान प्राप्त करना था (Dawson 1997, p. 63). उस समय, दूसरे क्रम के अंकगणित के समान प्राकृतिक संख्याओं और वास्तविक संख्याओं के सिद्धांतों को विश्लेषण के रूप में जाना जाता था, जबकि अकेले प्राकृतिक संख्याओं के सिद्धांतों को अंकगणित के रूप में जाना जाता था।

गोडेल निरंतरता की समस्या पर काम करने वाले अकेले व्यक्ति नहीं थे। विल्हेम एकरमैन ने 1925 में विश्लेषण के लिए एक त्रुटिपूर्ण स्थिरता प्रमाण प्रकाशित किया था, जिसमें उन्होंने एप्सिलॉन कैलकुलस की विधि का उपयोग करने का प्रयास किया था|ε-प्रतिस्थापन मूल रूप से हिल्बर्ट द्वारा विकसित किया गया था। उस वर्ष बाद में, जॉन वॉन न्यूमैन आगमन के किसी भी स्वयंसिद्ध के बिना अंकगणित की एक प्रणाली के लिए प्रमाण को सही करने में सक्षम थे। 1928 तक, एकरमैन ने बर्नेज़ को एक संशोधित प्रमाण भेजा था; इस संशोधित प्रमाण ने हिल्बर्ट को 1929 में अपने विश्वास की घोषणा करने के लिए प्रेरित किया कि अंकगणित की निरंतरता का प्रदर्शन किया गया था और विश्लेषण का एक सुसंगत प्रमाण जल्द ही अनुसरण करेगा। अपूर्णता प्रमेय के प्रकाशन के बाद दिखाया गया कि एकरमैन का संशोधित प्रमाण गलत होना चाहिए, वॉन न्यूमैन ने एक ठोस उदाहरण पेश किया जिसमें दिखाया गया कि इसकी मुख्य तकनीक ठीक नहीं थी (Zach 2007, p. 418; Zach 2003, p. 33).

अपने शोध के दौरान, गोडेल ने पाया कि यद्यपि एक वाक्य जो अपनी स्वयं की असत्यता पर जोर देता है, विरोधाभास की ओर जाता है, एक वाक्य जो स्वयं की गैर-सिद्धता पर जोर देता है, नहीं करता है। विशेष रूप से, गोडेल उस परिणाम के बारे में जानते थे जिसे अब तर्स्की की अपरिभाष्यता प्रमेय कहा जाता है, हालांकि उन्होंने इसे कभी प्रकाशित नहीं किया। गोडेल ने 26 अगस्त, 1930 को कार्नाप, फीगेल और वैसमैन को अपनी पहली अपूर्णता प्रमेय की घोषणा की; ये चारों अगले सप्ताह कोनिग्सबर्ग में एक महत्वपूर्ण सम्मेलन, सटीक विज्ञान की ज्ञानमीमांसा पर दूसरे सम्मेलन में भाग लेंगे।

घोषणा

सटीक विज्ञान की ज्ञानमीमांसा पर 1930 का दूसरा सम्मेलन | कोनिग्सबर्ग सम्मेलन तीन शैक्षणिक समाजों की एक संयुक्त बैठक थी, जिसमें उस समय के कई प्रमुख तर्कशास्त्री उपस्थित थे। कार्नाप, हेटिंग और वॉन न्यूमैन ने क्रमशः तर्कवाद, अंतर्ज्ञानवाद और औपचारिकता के गणितीय दर्शन पर एक घंटे का भाषण दिया। (Dawson 1996, p. 69). सम्मेलन में हिल्बर्ट का सेवानिवृत्ति का पता भी शामिल था, क्योंकि वह गौटिंगेन विश्वविद्यालय में अपना पद छोड़ रहे थे। हिल्बर्ट ने भाषण का इस्तेमाल अपने विश्वास पर बहस करने के लिए किया कि सभी गणितीय समस्याओं को हल किया जा सकता है। उन्होंने यह कहते हुए अपना संबोधन समाप्त किया,

For the mathematician there is no Ignorabimus, and, in my opinion, not at all for natural science either. ... The true reason why [no one] has succeeded in finding an unsolvable problem is, in my opinion, that there is no unsolvable problem. In contrast to the foolish Ignorabimus, our credo avers: We must know. We shall know!

यह भाषण जल्द ही गणित पर हिल्बर्ट की मान्यताओं के सारांश के रूप में जाना जाने लगा (इसके अंतिम छह शब्द, Wir müssen Wissen। Wir Werden Wissen!, 1943 में हिल्बर्ट के समाधि-लेख के रूप में उपयोग किए गए थे)। हालांकि हिल्बर्ट के संबोधन के लिए गोडेल की उपस्थिति की संभावना थी, दोनों कभी आमने-सामने नहीं मिले (Dawson 1996, p. 72).

गोडेल ने सम्मेलन के तीसरे दिन एक गोलमेज चर्चा सत्र में अपनी पहली अपूर्णता प्रमेय की घोषणा की। घोषणा ने वॉन न्यूमैन के अलावा थोड़ा ध्यान आकर्षित किया, जिन्होंने बातचीत के लिए गोडेल को एक तरफ खींच लिया। उस वर्ष बाद में, पहली अपूर्णता प्रमेय के ज्ञान के साथ स्वतंत्र रूप से काम करते हुए, वॉन न्यूमैन ने दूसरी अपूर्णता प्रमेय का प्रमाण प्राप्त किया, जिसकी घोषणा उन्होंने 20 नवंबर, 1930 को एक पत्र में गोडेल को की। (Dawson 1996, p. 70). गोडेल ने स्वतंत्र रूप से दूसरी अपूर्णता प्रमेय प्राप्त की थी और इसे अपनी प्रस्तुत पांडुलिपि में शामिल किया था, जिसे 17 नवंबर, 1930 को मोनाशेफते फर मैथेमेटिक द्वारा प्राप्त किया गया था।

गोडेल का पेपर 1931 में Über फॉर्मल अनेंटशेडबारे सैत्जे डेर प्रिंसिपिया मैथेमेटिका एंड वर्वांडर सिस्टमे I (औपचारिक रूप से अनिर्णीत प्रस्तावों पर प्रिंसिपिया मैथेमेटिका और संबंधित सिस्टम I) शीर्षक के तहत प्रकाशित हुआ था। जैसा कि शीर्षक से पता चलता है, गोडेल ने मूल रूप से मोनाशेफ़्टे के अगले खंड में कागज के दूसरे भाग को प्रकाशित करने की योजना बनाई थी; पहले पेपर की तुरंत स्वीकृति एक कारण था जिससे उन्होंने अपनी योजनाओं को बदल दिया (van Heijenoort 1967, page 328, footnote 68a).

सामान्यीकरण और स्वीकृति

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

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

हिल्बर्ट के कार्यक्रम पर अपूर्णता प्रमेयों के प्रभाव को शीघ्र ही महसूस किया गया। बर्नेज़ ने ग्रंडलागेन डेर मैथेमेटिक (#) के दूसरे खंड में अपूर्णता प्रमेय का पूर्ण प्रमाण शामिल कियाCITEREFBernays1939), ε-प्रतिस्थापन विधि पर एकरमैन के अतिरिक्त परिणामों के साथ और Gentzen की अंकगणितीय स्थिरता प्रमाण। यह दूसरी अपूर्णता प्रमेय का पहला पूर्ण प्रकाशित प्रमाण था।

आलोचना

फिन्सलर

Paul Finsler (1926) ने एक ऐसी अभिव्यक्ति का निर्माण करने के लिए रिचर्ड के विरोधाभास के एक संस्करण का उपयोग किया जो गलत था लेकिन एक विशेष, अनौपचारिक ढांचे में जिसे उन्होंने विकसित किया था, असाध्य था। गोडेल इस पेपर से अनभिज्ञ थे जब उन्होंने अपूर्णता प्रमेयों को सिद्ध किया (कलेक्टेड वर्क्स खंड IV, पृ. 9)। फिन्सलर ने 1931 में गोडेल को इस पत्र के बारे में सूचित करने के लिए लिखा था, जिसे फिन्सलर ने अपूर्णता प्रमेय के लिए प्राथमिकता दी थी। फिन्सलर के तरीके औपचारिक रूप से सिद्ध होने पर निर्भर नहीं थे, और गोडेल के काम के लिए केवल एक सतही समानता थी (van Heijenoort 1967, p. 328). गोडेल ने पेपर पढ़ा, लेकिन इसे गंभीर रूप से त्रुटिपूर्ण पाया, और फिन्सलर को उनकी प्रतिक्रिया ने औपचारिकता की कमी के बारे में चिंता व्यक्त की (Dawson 1996, p. 89). फ़िंसलर ने अपने गणित के दर्शन के लिए तर्क देना जारी रखा, जिसने अपने करियर के शेष समय के लिए औपचारिकता को छोड़ दिया।

ज़र्मेलो

सितंबर 1931 में, अर्नेस्ट ज़र्मेलो ने गोडेल को यह घोषणा करने के लिए लिखा कि उन्होंने गोडेल के तर्क में एक आवश्यक अंतर के रूप में क्या वर्णित किया है (Dawson 1996, p. 76). अक्टूबर में, गोडेल ने 10 पन्नों के एक पत्र के साथ उत्तर दिया (Dawson 1996, p. 76, Grattan-Guinness 2005, pp. 512–513), जहां उन्होंने बताया कि ज़र्मेलो ने गलती से मान लिया था कि एक प्रणाली में सत्य की धारणा उस प्रणाली में निश्चित है (जो सामान्य रूप से टार्स्की की अपरिभाषितता प्रमेय द्वारा सत्य नहीं है)। लेकिन ज़र्मेलो ने भरोसा नहीं किया और अपनी आलोचनाओं को प्रिंट में प्रकाशित किया, जिसमें उनके युवा प्रतियोगी (Grattan-Guinness 2005, pp. 513). गोडेल ने फैसला किया कि मामले को आगे बढ़ाने का कोई मतलब नहीं है, और कार्नाप सहमत हो गए (Dawson 1996, p. 77). ज़र्मेलो के बाद के अधिकांश कार्य पहले क्रम के तर्क से अधिक मजबूत तर्कशास्त्र से संबंधित थे, जिसके साथ उन्होंने गणितीय सिद्धांतों की स्थिरता और श्रेणीबद्धता दोनों को दिखाने की आशा की थी।

विट्गेन्स्टाइन

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

कई टिप्पणीकारों ने विट्गेन्स्टाइन को गोडेल की गलतफहमी के रूप में पढ़ा है (Rodych 2003), हालांकि जूलियट फ्लॉयड और Hilary Putnam (2000), साथ ही Graham Priest (2004) ने यह तर्क देते हुए टेक्स्ट रीडिंग प्रदान की है कि अधिकांश कमेंटरी विट्गेन्स्टाइन को गलत समझती हैं। अपनी रिहाई पर, बर्नेज़, डमेट और क्रेसेल ने विट्गेन्स्टाइन की टिप्पणियों पर अलग-अलग समीक्षाएँ लिखीं, जिनमें से सभी बेहद नकारात्मक थीं। (Berto 2009, p. 208). इस आलोचना की एकमतता के कारण अपूर्णता प्रमेयों पर विट्गेन्स्टाइन की टिप्पणियों का तर्क समुदाय पर बहुत कम प्रभाव पड़ा। 1972 में, गोडेल ने कहा: क्या विट्गेन्स्टाइन ने अपना दिमाग खो दिया है? क्या वह इसका गंभीरता से मतलब है? वह जानबूझकर अनाप-शनाप बयानबाजी करते हैं (Wang 1996, p. 179), और कार्ल मेन्जर को लिखा कि विट्गेन्स्टाइन की टिप्पणियाँ अपूर्णता प्रमेयों के लेखन की गलतफहमी को प्रदर्शित करती हैं:

It is clear from the passages you cite that Wittgenstein did not understand [the first incompleteness theorem] (or pretended not to understand it). He interpreted it as a kind of logical paradox, while in fact is just the opposite, namely a mathematical theorem within an absolutely uncontroversial part of mathematics (finitary number theory or combinatorics). (Wang 1996, p. 179)

2000 में विट्गेन्स्टाइन के नचलास के प्रकाशन के बाद से, दर्शनशास्त्र में पत्रों की एक श्रृंखला ने मूल्यांकन करने की मांग की है कि क्या विट्गेन्स्टाइन की टिप्पणियों की मूल आलोचना उचित थी। Floyd & Putnam (2000) का तर्क है कि विट्गेन्स्टाइन को अपूर्णता प्रमेय के बारे में पहले की अपेक्षा अधिक पूर्ण समझ थी। वे विशेष रूप से एक ω-असंगत प्रणाली के लिए गोडेल वाक्य की व्याख्या से संबंधित हैं क्योंकि वास्तव में कह रहा है कि मैं साध्य नहीं हूं, क्योंकि सिस्टम में कोई मॉडल नहीं है जिसमें प्रवीणता विधेय वास्तविक सिद्धता से मेल खाती है। Rodych (2003) का तर्क है कि विट्गेन्स्टाइन की उनकी व्याख्या ऐतिहासिक रूप से उचित नहीं है। Berto (2009) विट्गेन्स्टाइन के लेखन और पैराकंसिस्टेंट लॉजिक के सिद्धांतों के बीच संबंधों की पड़ताल करता है।

यह भी देखें

• चैतिन की अपूर्णता प्रमेय
• गोडेल, एस्चर, बाख
• गोडेल मशीन
• गोडेल की पूर्णता प्रमेय
• गोडेल की स्पीड-अप प्रमेय
• लोब की प्रमेय
• दिमाग, मशीनें और गोडेल
• अंकगणित का गैर-मानक मॉडल
• सबूत सिद्धांत
• व्यवहार्यता तर्क
• क़ुइनिंग
• टार्स्की की अनिर्धारणीयता प्रमेय
• थ्योरी ऑफ एवरीथिंग # गोडेल का अधूरापन प्रमेय
• टंकण संख्या सिद्धांत

संदर्भ

उद्धरण

गोडेल द्वारा लेख

• कर्ट गोडेल, 1931, प्रिंसिपिया मैथेमेटिका और संबंधित प्रणालियों के औपचारिक रूप से अनिर्णीत प्रमेयों के बारे में, I, गणित और भौतिकी के लिए मासिक मुद्दे, वी। 38 एन. 1, पीपी. 173-198। doi:10.1007/BF01700692
• -, 1931, प्रिंसिपिया मैथेमेटिका और संबंधित प्रणालियों के औपचारिक रूप से अनिर्णीत प्रमेयों पर, मैं, सोलोमन फेफरमैन, संस्करण, 1986 में। कर्ट गोडेल कलेक्टेड वर्क्स, वॉल्यूम। I. ऑक्सफोर्ड यूनिवर्सिटी प्रेस, पीपी। 144-195। ISBN 978-0195147209. मूल जर्मन का सामना करने वाले अंग्रेजी अनुवाद के साथ, स्टीफन कोल क्लेन द्वारा एक परिचयात्मक नोट से पहले।
• - 1951, गणित की नींव और उनके निहितार्थ पर कुछ बुनियादी प्रमेय, सोलोमन फेफ़रमैन, संस्करण, 1995 में। कर्ट गोडेल कलेक्टेड वर्क्स, वॉल्यूम। III, ऑक्सफोर्ड यूनिवर्सिटी प्रेस, पीपी। 304–323। ISBN 978-0195147223.

अपने जीवनकाल के दौरान, गोडेल के पेपर का अंग्रेजी में अनुवाद

निम्नलिखित में से कोई भी सभी अनुवादित शब्दों और टाइपोग्राफी में सहमत नहीं है। टाइपोग्राफी एक गंभीर मामला है, क्योंकि गोडेल स्पष्ट रूप से उन मेटामैथमैटिकल धारणाओं पर जोर देना चाहते थे जिन्हें उनके सामान्य अर्थों में पहले परिभाषित किया गया था। . . (van Heijenoort 1967, p. 595). तीन अनुवाद मौजूद हैं। पहले जॉन डावसन का कहना है कि: मेल्टज़र अनुवाद गंभीर रूप से कम था और जर्नल ऑफ़ सिंबॉलिक लॉजिक में एक विनाशकारी समीक्षा प्राप्त हुई; गोडेल ने ब्रेथवेट की कमेंट्री की भी शिकायत की (Dawson 1997, p. 216). सौभाग्य से, मेल्टज़र अनुवाद को जल्द ही इलियट मेंडेलसन द्वारा मार्टिन डेविस के एंथोलॉजी द अनडेसिडेबल के लिए तैयार किए गए एक बेहतर अनुवाद द्वारा दबा दिया गया। . . उन्होंने अनुवाद को उतना अच्छा नहीं पाया जितना उन्होंने सोचा था। . . [लेकिन समय की कमी के कारण वह] इसके प्रकाशन के लिए सहमत हो गया (वही)। (एक फुटनोट में डावसन कहते हैं कि उन्हें अपने अनुपालन पर पछतावा होगा, क्योंकि प्रकाशित मात्रा पूरी तरह से गलत टाइपोग्राफी और कई गलत छापों से खराब हो गई थी (वही))। डावसन कहते हैं कि गोडेल ने जिस अनुवाद का समर्थन किया वह जीन वैन हेजेनूर्ट (वही) द्वारा किया गया था। गंभीर छात्रों के लिए 1934 के वसंत के दौरान इंस्टीट्यूट फॉर एडवांस्ड स्टडी में गोडेल द्वारा दिए गए व्याख्यानों के दौरान स्टीफन क्लेन और जे.बी. रोसेर द्वारा रिकॉर्ड किए गए व्याख्यान नोट्स के एक सेट के रूप में एक और संस्करण मौजूद है। Davis 1965, p. 39 और पी पर शुरू। 41); इस संस्करण का शीर्षक औपचारिक गणितीय प्रणालियों के अनिर्णायक प्रस्तावों पर है। उनके प्रकाशन के क्रम में:

• बी. मेल्टजर (अनुवाद) और आर.बी. ब्रेथवेट (परिचय), 1962. प्रिंसिपिया मैथेमेटिका और संबंधित प्रणालियों के औपचारिक रूप से अनिर्णीत प्रस्तावों पर, डोवर प्रकाशन, न्यूयॉर्क (डोवर संस्करण 1992), ISBN 0-486-66980-7 (pbk.) इसमें पीपी 33-34 पर गोडेल के जर्मन संक्षिप्ताक्षरों का एक उपयोगी अनुवाद शामिल है। जैसा कि ऊपर उल्लेख किया गया है, टाइपोग्राफी, अनुवाद और टिप्पणी संदिग्ध है। दुर्भाग्य से, इस अनुवाद को इसकी सभी संदिग्ध सामग्री के साथ पुनर्मुद्रित किया गया था

• स्टीफन हॉकिंग संपादक, 2005। ISBN 0-7624-1922-9. गोडेल का पेपर पी से शुरू होता है। 1097, हॉकिंग की टिप्पणी पी से शुरू होती है। 1089.

• मार्टिन डेविस (गणितज्ञ) संपादक, 1965। द अनडिसिडेबल: बेसिक पेपर्स ऑन अनडिसिडेबल प्रोपोजिशन्स, अनसॉल्वेबल प्रॉब्लम्स एंड कम्प्यूटेबल फंक्शंस, रेवेन प्रेस, न्यूयॉर्क, कोई आईएसबीएन नहीं। गोडेल का पेपर पृष्ठ 5 से शुरू होता है, जिसके पहले एक पृष्ठ की टिप्पणी है।
• जीन वैन हेयेनूर्ट संपादक, 1967, तीसरा संस्करण 1967। फ्रेज से गोडेल तक: गणितीय तर्क में एक स्रोत पुस्तक, 1879-1931, हार्वर्ड यूनिवर्सिटी प्रेस, कैम्ब्रिज मास। ISBN 0-674-32449-8 (पीबीके)। वैन हेजेनूर्ट ने अनुवाद किया। उनका कहना है कि प्रोफेसर गोडेल ने अनुवाद को मंजूरी दी, जो कई जगहों पर उनकी इच्छा के अनुरूप था। (पृष्ठ 595)। गोडेल का पेपर पी से शुरू होता है। 595; वैन हेजेनूर्ट की टिप्पणी पी पर शुरू होती है। 592.
• मार्टिन डेविस संपादक, 1965, उक्त। औपचारिक गणितीय प्रणालियों के अनिर्णीत प्रस्तावों पर। इरेटा के गोडेल के सुधार और गोडेल के जोड़े गए नोट्स के साथ एक प्रति पृष्ठ 41 पर शुरू होती है, जिसके पहले डेविस की टिप्पणी के दो पृष्ठ हैं। जब तक डेविस ने इसे अपनी मात्रा में शामिल नहीं किया, तब तक यह व्याख्यान केवल माइमोग्राफ किए गए नोटों के रूप में मौजूद था।

दूसरों के लेख

• जॉर्ज बूलोस, 1989, गोडेल इंकंप्लीटनेस प्रमेय का एक नया प्रमाण, अमेरिकन मैथमैटिकल सोसाइटी के नोटिस, वी, 36, पीपी। 388-390 और पी। 676, में पुनर्मुद्रित Boolos, George (1998). तर्क, तर्क और तर्क. Harvard University Press. ISBN 0-674-53766-1.
• बर्न्ड बुलड्ट, 2014, गोडेल की पहली अपूर्णता प्रमेय का दायरा Archived 2016-03-06 at the Wayback Machine, यूनिवर्सल लॉजिक, वी। 8, पीपी। 499–552। doi:10.1007/s11787-014-0107-3
• Charlesworth, Arthur (1981). "कंप्यूटर प्रोग्राम के संदर्भ में गोडेल के प्रमेय का प्रमाण". Mathematics Magazine. 54 (3): 109–121. doi:10.2307/2689794. JSTOR 2689794.
• Davis, Martin (1965). अनिर्णीत: अनिर्णीत प्रस्तावों, अघुलनशील समस्याओं और संगणनीय कार्यों पर मूल कागजात (in English). Raven Press. ISBN 978-0-911216-01-1.
• Davis, Martin (2006). "अपूर्णता प्रमेय" (PDF). Notices of the AMS. 53 (4): 414.
• Grattan-Guinness, Ivor, ed. (2005). पश्चिमी गणित में ऐतिहासिक लेखन 1640-1940. Elsevier. ISBN 9780444508713.
• van Heijenoort, Jean (1967). "Gödel's Theorem". In Edwards, Paul (ed.). Encyclopedia of Philosophy. Vol. 3. Macmillan. pp. 348–357.
• Hellman, Geoffrey (1981). "गोडेल ए फ्रेज-रसेल कैसे करें: गोडेल की अपूर्णता प्रमेय और तर्कवाद". Noûs. 15 (4 - Special Issue on Philosophy of Mathematics): 451–468. ISSN 0029-4624. JSTOR 2214847.
• डेविड हिल्बर्ट, 1900, गणितीय समस्याएं। पेरिस में गणितज्ञों की अंतर्राष्ट्रीय कांग्रेस से पहले दिए गए एक व्याख्यान का अंग्रेजी अनुवाद, जिसमें हिल्बर्ट का कथन है उनकी दूसरी समस्या।
• मार्टिन हिर्ज़ेल, 2000, औपचारिक रूप से अनिर्णायक प्रस्तावों पर प्रिंसिपिया मैथेमेटिका और संबंधित सिस्टम I।। गोडेल के पेपर का अंग्रेजी अनुवाद। मूल से संग्रहीत। 16 सितंबर, 2004।
• Kikuchi, Makoto; Tanaka, Kazuyuki (July 1994). "गोडेल के प्रमेयों के मॉडल-सैद्धांतिक प्रमाणों की औपचारिकता पर". Notre Dame Journal of Formal Logic. 35 (3): 403–412. doi:10.1305/ndjfl/1040511346. MR 1326122.
• स्टीफन कोल क्लेन, 1943, रिकर्सिव प्रेडीकेट्स एंड क्वांटिफायर्स, अमेरिकन मैथमैटिकल सोसाइटी के लेनदेन से पुनर्मुद्रित, वी। 53 एन। 1, पीपी। मार्टिन डेविस 1965 में 41-73, द अनडिसीडेबल (लोक। साइट।) पीपी। 255-287।
• Raatikainen, Panu (2020). "गोडेल की अपूर्णता प्रमेय". Stanford Encyclopedia of Philosophy. Retrieved November 7, 2022.
• Raatikainen, Panu (2005). "गोडेल के अपूर्णता प्रमेयों की दार्शनिक प्रासंगिकता पर". Revue Internationale de Philosophie. 59 (4): 513–534. doi:10.3917/rip.234.0513. S2CID 52083793.
• जॉन बार्कले रोसेर, 1936, गोडेल और चर्च के कुछ प्रमेय के विस्तार, जर्नल ऑफ़ सिंबॉलिक लॉजिक से पुनर्मुद्रित, v. 1 (1936) पीपी। . 230–235।
• -, 1939, गोडेल के प्रमेय और चर्च के प्रमेय के प्रमाणों की एक अनौपचारिक प्रदर्शनी, जर्नल ऑफ़ सिंबॉलिक लॉजिक से पुनर्मुद्रित, v. 4 (1939) पीपी। पीपी। 223–230
• Smoryński, C. (1977). "The incompleteness theorems". In Jon Barwise (ed.). गणितीय तर्क की पुस्तिका. Amsterdam: North-Holland Pub. Co. pp. 821–866. ISBN 978-0-444-86388-1.
• डैन ई. विलार्ड, 2001, स्व-सत्यापन स्वयंसिद्ध प्रणाली, अपूर्णता प्रमेय और संबंधित प्रतिबिंब सिद्धांत, प्रतीकात्मक तर्क का जर्नल, वी। 66 एन। 2, पीपी. 536–596. doi:10.2307/2695030 JSTOR 2695030
• Zach, Richard (2003). "फ़िनिटिज़्म का अभ्यास: हिल्बर्ट के कार्यक्रम में एप्सिलॉन कैलकुलस और संगति प्रमाण" (PDF). Synthese. Springer Science and Business Media LLC. 137 (1): 211–259. arXiv:math/0102189. doi:10.1023/a:1026247421383. ISSN 0039-7857. S2CID 16657040.
• Zach, Richard (2005). "Kurt Gödel, paper on the incompleteness theorems (1931)". In Grattan-Guinness, Ivor (ed.). पश्चिमी गणित में ऐतिहासिक लेखन 1640-1940. Elsevier. pp. 917–925. doi:10.1016/b978-044450871-3/50152-2. ISBN 9780444508713.

प्रमेयों के बारे में किताबें

• फ्रांसेस्को बेर्तो। गोडेल के बारे में कुछ है: अपूर्णता प्रमेय जॉन विली एंड संस के लिए पूर्ण मार्गदर्शिका। 2010.
• नॉर्बर्ट डोमिसन, 1990। बर्न: पीटर लैंग। 142 एस 1990। ISBN 3-261-04214-1. Zbl 0724.03003.
• Franzén, Torkel (2005). गोडेल की प्रमेय: इसके उपयोग और दुरुपयोग के लिए एक अधूरी मार्गदर्शिका. Wellesley, MA: A K Peters. ISBN 1-56881-238-8. MR 2146326.
• डगलस हॉफस्टाटर, 1979। गोडेल, एस्चर, बाख|गोडेल, एस्चर, बाख: एक शाश्वत गोल्डन चोटी। विंटेज किताबें। ISBN 0-465-02685-0. 1999 पुनर्मुद्रण: ISBN 0-465-02656-7. MR530196
• —, 2007. आई एम अ स्ट्रेंज लूप। बुनियादी पुस्तकें। ISBN 978-0-465-03078-1. ISBN 0-465-03078-5. MR2360307
• स्टेनली जाकी, OSB, 2005। मात्राओं का नाटक। रियल व्यू बुक्स।
• प्रति लिंडस्ट्रॉम, 1997। अपूर्णता के पहलू, तर्क वी। 10 में व्याख्यान नोट्स।
• जे.आर. लुकास, एफबीए, 1970। द फ्रीडम ऑफ द विल। क्लेरेंडन प्रेस, ऑक्सफोर्ड, 1970।
• अर्नेस्ट नागल, जेम्स आर. न्यूमैन, डगलस हॉफस्टाटर, 2002 (1958)। गोडेल का सबूत, संशोधित संस्करण। ISBN 0-8147-5816-9. MR1871678
• रूडी रूकर , 1995 (1982)। इन्फिनिटी एंड द माइंड: द साइंस एंड फिलॉसफी ऑफ द इनफिनिट। प्रिंसटन विश्वविद्यालय। प्रेस। MR658492
• Smith, Peter (2007). गोडेल के प्रमेयों का परिचय. Cambridge, U.K.: Cambridge University Press. ISBN 978-0-521-67453-9. MR 2384958.
• Shankar, N. (1994). मेटामैथमैटिक्स, मशीन और गोडेल का प्रमाण. Cambridge tracts in theoretical computer science. Vol. 38. Cambridge: Cambridge University Press. ISBN 0-521-58533-3.
• रेमंड स्मुलियन, 1987. हमेशा के लिए अनिर्णीत ISBN 0192801414 - औपचारिक प्रणालियों में अनिश्चयता पर आधारित पहेलियाँ
• —, 1991. गोडेल की अपूर्णता प्रमेय। ऑक्सफोर्ड यूनिवर्सिटी। प्रेस।
• -, 1994। विकर्णीकरण और आत्म-संदर्भ। ऑक्सफोर्ड यूनिवर्सिटी। प्रेस। MR1318913
• —, 2013. द गोडेलियन पहेली बुक: पहेलियाँ, विरोधाभास और सबूत। कूरियर निगम। ISBN 978-0-486-49705-1.
• Wang, Hao (1996). ए लॉजिकल जर्नी: फ्रॉम गोडेल टू फिलॉसफी. MIT Press. ISBN 0-262-23189-1. MR1433803

विविध संदर्भ

• Berto, Francesco (2009). "गोडेल विरोधाभास और विट्गेन्स्टाइन के कारण". Philosophia Mathematica. III (17).
• Dawson, John W. Jr. (1996). तार्किक दुविधाएं: कर्ट गोडेल का जीवन और कार्य. Taylor & Francis. ISBN 978-1-56881-025-6.
• Dawson, John W. Jr. (1997). तार्किक दुविधाएं: कर्ट गोडेल का जीवन और कार्य. Wellesley, Massachusetts: A. K. Peters. ISBN 978-1-56881-256-4. OCLC 36104240.
• रेबेका गोल्डस्टीन, 2005, अपूर्णता: कर्ट गोडेल, डब्ल्यू. डब्ल्यू. नॉर्टन एंड कंपनी का प्रमाण और विरोधाभास। ISBN 0-393-05169-2
• Floyd, Juliet; Putnam, Hilary (2000). "गोडेल प्रमेय के बारे में विट्गेन्स्टाइन के "कुख्यात पैराग्राफ" पर एक नोट". The Journal of Philosophy. JSTOR. 97 (11): 624–632. doi:10.2307/2678455. ISSN 0022-362X. JSTOR 2678455.
• Harrison, J. (2009). व्यावहारिक तर्क और स्वचालित तर्क की पुस्तिका. Cambridge: Cambridge University Press. ISBN 0521899575.
• डेविड हिल्बर्ट और पॉल बर्नेज़, फ़ाउंडेशन ऑफ़ मैथेमेटिक्स, स्प्रिंगर-वेरलाग।
• Hopcroft, John E.; Ullman, Jeffrey (1979). ऑटोमेटा सिद्धांत, भाषा और संगणना का परिचय. Reading, Mass.: Addison-Wesley. ISBN 0-201-02988-X.
• Jones, James P. (1980). "अनिर्णीत डायोफैंटाइन समीकरण" (PDF). Bulletin of the American Mathematical Society. 3 (2): 859–862.
• Kleene, Stephen Cole (1967). गणितीय तर्क. डोवर द्वारा पुनर्मुद्रित, 2002। ISBN 0-486-42533-9
• O'Connor, Russell (2005). "Coq द्वारा सत्यापित अंकगणित की आवश्यक अपूर्णता". Lecture Notes in Computer Science. 3603: 245–260.
• Paulson, Lawrence (2014). "आनुवंशिक रूप से परिमित सेट के सिद्धांत के लिए गोडेल की अपूर्णता प्रमेय का एक मशीन-सहायता प्रमाण". Review of Symbolic Logic. 7 (3): 484–498. doi:10.1017/S1755020314000112.
• ग्राहम पुजारी , 1984, लॉजिक ऑफ़ पैराडॉक्स रिविज़िटेड, जर्नल ऑफ़ फिलोसोफिकल लॉजिक, वी. 13,' एन। 2, पीपी. 153–179.
• —, 2004, मैक्स कोल्बेल में गोडेल के प्रमेय पर विट्जस्टीन की टिप्पणी, एड।, विट्गेन्स्टाइन का स्थायी महत्व, मनोविज्ञान प्रेस, पीपी। 207-227।
• Priest, Graham (2006). इन कॉन्ट्राडिक्शन: ए स्टडी ऑफ द ट्रांसकंसिस्टेंट. Oxford University Press. ISBN 0-19-926329-9.
• हिलेरी पटनम, 1960, माइंड्स एंड मशीन्स इन सिडनी हुक, एड., डायमेंशन्स ऑफ़ माइंड: ए सिम्पोसियम। न्यूयॉर्क यूनिवर्सिटी प्रेस। एंडरसन, ए.आर., संस्करण, 1964 में पुनर्मुद्रित। माइंड्स एंड मशीन्स। प्रेंटिस-हॉल: 77।
• वोल्फगैंग रौटेनबर्ग, 2010, गणितीय तर्क का एक संक्षिप्त परिचय, तीसरा। एड।, स्प्रिंगर, ISBN 978-1-4419-1220-6
• Rodych, Victor (2003). "गलतफहमी गोडेल: विट्गेन्स्टाइन के बारे में नए तर्क और विट्गेन्स्टाइन की नई टिप्पणी". Dialectica. 57 (3): 279–313. doi:10.1111/j.1746-8361.2003.tb00272.x
• स्टीवर्ट शापिरो, 2002, अपूर्णता और असंगतता, मन, वी. 111, पीपी 817-32। doi:10.1093/mind/111.444.817
• Sokal, Alan; Bricmont, Jean (1999). फैशनेबल नॉनसेंस: उत्तर आधुनिक बुद्धिजीवी 'विज्ञान का दुरुपयोग. Picador. ISBN 0-312-20407-8.
• Shoenfield, Joseph R. (1967). गणितीय तर्क. Natick, Mass.: Association for Symbolic Logic (published 2001). ISBN 978-1-56881-135-2.
• Stangroom, Jeremy; Benson, Ophelia (2006). सत्य क्यों मायने रखता है. Continuum. ISBN 0-8264-9528-1.
• जॉर्ज टूरलाकिस, लेक्चर्स इन लॉजिक एंड सेट थ्योरी, वॉल्यूम 1, मैथमेटिकल लॉजिक, कैम्ब्रिज यूनिवर्सिटी प्रेस, 2003। ISBN 978-0-521-75373-9
• एवी विगडरसन, 2010, द गोडेल फेनोमेना इन मैथमैटिक्स: ए मॉडर्न व्यू, कर्ट गोडेल एंड द फ़ाउंडेशन ऑफ़ मैथमैटिक्स: होराइज़न्स ऑफ़ ट्रुथ में , कैम्ब्रिज यूनिवर्सिटी प्रेस।
• हाओ वांग (अकादमिक), 1996, ए लॉजिकल जर्नी: फ्रॉम गोडेल टू फिलॉसफी, द एमआईटी प्रेस, कैम्ब्रिज एमए, ISBN 0-262-23189-1.
• Zach, Richard (2007). "Hilbert's Program Then and Now". In Jacquette, Dale (ed.). तर्कशास्त्र का दर्शन. Handbook of the Philosophy of Science. Vol. 5. Amsterdam: Elsevier. pp. 411–447. arXiv:math/0508572. doi:10.1016/b978-044451541-4/50014-2. ISBN 978-0-444-51541-4. OCLC 162131413. S2CID 291599.

बाहरी संबंध

• Godel's Incompleteness Theorems on In Our Time at the BBC
• "Kurt Gödel" entry by Juliette Kennedy in the Stanford Encyclopedia of Philosophy, July 5, 2011.
• "Gödel's Incompleteness Theorems" entry by Panu Raatikainen in the Stanford Encyclopedia of Philosophy, November 11, 2013.
• Paraconsistent Logic § Arithmetic and Gödel's Theorem entry in the Stanford Encyclopedia of Philosophy.
• MacTutor biographies:
  • Kurt Gödel. Archived 2005-10-13 at the Wayback Machine
  • Gerhard Gentzen.
• What is Mathematics:Gödel's Theorem and Around by Karlis Podnieks. An online free book.
• World's shortest explanation of Gödel's theorem using a printing machine as an example.
• October 2011 RadioLab episode about/including Gödel's Incompleteness theorem
• "Gödel incompleteness theorem", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• How Gödel's Proof Works by Natalie Wolchover, Quanta Magazine, July 14, 2020.
• [1] and [2] Gödel's incompleteness theorems formalised in Isabelle/HOL

`