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

Not to be confused with Gödel's incompleteness theorems.

∃y. R(x,y)) सभी संरचनाओं (गणितीय तर्क) में लागू होता है (केवल सबसे सरल 8 दिखाए गए हैं) बाएं)। गोडेल के पूर्णता परिणाम के अनुसार, इसमें प्राकृतिक कटौती प्रमाण होना चाहिए (दाएं दिखाया गया है)।

गोडेल की पूर्णता प्रमेय गणितीय तर्क में एक मौलिक प्रमेय है जो प्रथम-क्रम तर्क में शब्दार्थ सत्य और वाक्यविन्यास संभाव्यता तर्क के बीच एक पत्राचार स्थापित करता है।

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

इसे पहली बार 1929 में कर्ट गोडेल ने सिद्ध किया था। इसे तब सरल बनाया गया जब एह रिफंड पर ने अपनी पीएच.डी. में अवलोकन किया। थीसिस कि प्रमाण के कठिन भाग को मॉडल अस्तित्व प्रमेय (1949 में प्रकाशित) के रूप में प्रस्तुत किया जा सकता है। हेनकिन के प्रमाण को 1953 में गिस्बर्ट हसनजेगर द्वारा सरल बनाया गया था।

प्रारंभिक

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

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

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

कथन

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

गोडेल का मूल सूत्रीकरण

पूर्णता प्रमेय कहता है कि यदि कोई सूत्र तार्किक रूप से मान्य है तो सूत्र की एक सीमित कटौती (एक औपचारिक प्रमाण) होती है।

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

अधिक सामान्य रूप

प्रमेय को तार्किक परिणाम के संदर्भ में अधिक सामान्यतः व्यक्त किया जा सकता है। हम कहते हैं कि एक वाक्य s, निरूपित सिद्धांत T का एक वाक्यात्मक परिणाम है $T\vdash s$, यदि हमारी निगमन प्रणाली में टी से s सिद्ध है। हम कहते हैं कि s निरूपित T का शब्दार्थ परिणाम है $T\models s$, यदि s, T के प्रत्येक मॉडल (गणितीय तर्क) में है। पूर्णता प्रमेय तब कहता है कि किसी भी प्रथम-क्रम सिद्धांत T के लिए एक सुव्यवस्थित भाषा और T की भाषा में कोई भी वाक्य,

if $T\models s$, then $T\vdash s$.

चूँकि व्युत्क्रम (ध्वनि) भी कायम है, यह उसी का अनुसरण करता है $T\models s$ अगर और केवल अगर $T\vdash s$, और इस प्रकार वाक्यविन्यास और अर्थ संबंधी परिणाम प्रथम-क्रम तर्क के लिए समतुल्य हैं।

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

गोडेल का मूल सूत्रीकरण बिना किसी स्वयंसिद्ध सिद्धांत के विशेष मामले को लेकर किया गया है।

मॉडल अस्तित्व प्रमेय

हेनकिन की संगति#हेनकिन के प्रमेय के परिणामस्वरूप, पूर्णता प्रमेय को स्थिरता के संदर्भ में भी समझा जा सकता है। हम कहते हैं कि एक सिद्धांत T वाक्यात्मक रूप से सुसंगत है यदि कोई वाक्य ऐसा नहीं है कि हमारे निगमनात्मक प्रणाली में s और उसके निषेधन ¬s दोनों को T से सिद्ध किया जा सके। मॉडल अस्तित्व प्रमेय कहता है कि किसी भी प्रथम-क्रम सिद्धांत टी के लिए एक सुव्यवस्थित भाषा के साथ,

if $T$ is syntactically consistent, then $T$ has a model.

लोवेनहेम-स्कोलेम प्रमेय के संबंध में एक अन्य संस्करण कहता है:

Every syntactically consistent, countable first-order theory has a finite or countable model.

हेनकिन के प्रमेय को देखते हुए, पूर्णता प्रमेय को इस प्रकार सिद्ध किया जा सकता है: यदि $T\models s$, तब $T\cup \lnot s$ मॉडल नहीं है. फिर, हेनकिन के प्रमेय के प्रतिधनात्मक द्वारा $T\cup \lnot s$ वाक्य रचना की दृष्टि से असंगत है। तो एक विरोधाभास ($\bot$) से सिद्ध होता है $T\cup \lnot s$ निगमनात्मक प्रणाली में. इस तरह $(T\cup \lnot s)\vdash \bot$, और फिर निगमनात्मक प्रणाली के गुणों द्वारा, $T\vdash s$.

अंकगणित के एक प्रमेय के रूप में

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

परिणाम

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

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

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

अपूर्णता प्रमेयों से संबंध

गोडेल के अपूर्णता प्रमेय दर्शाते हैं कि गणित में किसी भी प्रथम-क्रम सिद्धांत के भीतर जो सिद्ध किया जा सकता है, उसकी अंतर्निहित सीमाएँ हैं। उनके नाम में अपूर्णता पूर्ण के दूसरे अर्थ को संदर्भित करती है (देखें मॉडल सिद्धांत#कॉम्पैक्टनेस और पूर्णता प्रमेयों का उपयोग|मॉडल सिद्धांत - कॉम्पैक्टनेस और पूर्णता प्रमेयों का उपयोग करना): एक सिद्धांत $T$ यदि प्रत्येक वाक्य पूर्ण (या निर्णय योग्य) है $S$ की भाषा में $T$ या तो सिद्ध है ($T\vdash S$) या अस्वीकृत ($T\vdash \neg S$).

पहला अपूर्णता प्रमेय बताता है कि कोई भी $T$ जो सुसंगत, प्रभावी रूप से गणना योग्य है और इसमें रॉबिन्सन अंकगणित शामिल है ( क्यू ) स्पष्ट रूप से एक वाक्य का निर्माण करके, इस अर्थ में अधूरा होना चाहिए $S_{T}$ जो स्पष्ट रूप से न तो साबित करने योग्य है और न ही अस्वीकार्य है $T$. दूसरा अपूर्णता प्रमेय यह दिखाकर इस परिणाम का विस्तार करता है $S_{T}$ चुना जा सकता है ताकि यह की स्थिरता को व्यक्त कर सके $T$ अपने आप।

तब से $S_{T}$ में सिद्ध नहीं किया जा सकता $T$, पूर्णता प्रमेय का तात्पर्य एक मॉडल के अस्तित्व से है $T$ जिसमें $S_{T}$ गलत है। वास्तव में, $S_{T}$ एक अंकगणितीय पदानुक्रम है|Π₁ वाक्य, यानी यह बताता है कि कुछ परिमित संपत्ति सभी प्राकृतिक संख्याओं के लिए सत्य है; इसलिए यदि यह गलत है, तो कुछ प्राकृत संख्या एक प्रतिउदाहरण है। यदि यह प्रतिउदाहरण मानक प्राकृतिक संख्याओं के भीतर मौजूद होता, तो इसका अस्तित्व अस्वीकृत हो जाता $S_{T}$ अंदर $T$; लेकिन अपूर्णता प्रमेय ने इसे असंभव दिखाया, इसलिए प्रतिउदाहरण एक मानक संख्या नहीं होना चाहिए, और इस प्रकार कोई भी मॉडल नहीं होना चाहिए $T$ जिसमें $S_{T}$ गलत है इसमें अंकगणित का गैर-मानक मॉडल शामिल होना चाहिए|गैर-मानक संख्याएँ।

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

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

कॉम्पैक्टनेस प्रमेय से संबंध

पूर्णता प्रमेय और सघनता प्रमेय प्रथम-क्रम तर्क की दो आधारशिलाएँ हैं। हालाँकि इनमें से कोई भी प्रमेय पूरी तरह से प्रभावी ढंग से गणना योग्य तरीके से सिद्ध नहीं किया जा सकता है, प्रत्येक को दूसरे से प्रभावी ढंग से प्राप्त किया जा सकता है।

सघनता प्रमेय कहता है कि यदि कोई सूत्र φ, सूत्रों के (संभवतः अनंत) सेट का तार्किक परिणाम है तो यह Γ के एक परिमित उपसमुच्चय का तार्किक परिणाम है। यह पूर्णता प्रमेय का एक तात्कालिक परिणाम है, क्योंकि φ की औपचारिक कटौती में Γ से केवल एक सीमित संख्या में स्वयंसिद्धों का उल्लेख किया जा सकता है, और निगमन प्रणाली की सुदृढ़ता का अर्थ है कि φ इस परिमित सेट का एक तार्किक परिणाम है। सघनता प्रमेय का यह प्रमाण मूल रूप से गोडेल के कारण है।

इसके विपरीत, कई निगमनात्मक प्रणालियों के लिए, सघनता प्रमेय के प्रभावी परिणाम के रूप में पूर्णता प्रमेय को सिद्ध करना संभव है।

पूर्णता प्रमेय की अप्रभावीता को विपरीत गणित की तर्ज पर मापा जा सकता है। जब एक गणनीय भाषा पर विचार किया जाता है, तो पूर्णता और सघनता प्रमेय एक दूसरे के समतुल्य होते हैं और पसंद के एक कमजोर रूप के समतुल्य होते हैं, जिसे कमजोर कोनिग लेम्मा के रूप में जाना जाता है, समतुल्यता आरसीए में सिद्ध होती है।₀ (पीनो अंकगणित का दूसरा क्रम संस्करण Σ से अधिक प्रेरण तक सीमित है⁰₁ सूत्र)। कमजोर कोनिग का लेम्मा ZF में सिद्ध करने योग्य है, ज़र्मेलो-फ्रेंकेल सेट सिद्धांत की प्रणाली बिना पसंद के सिद्धांत के, और इस प्रकार गणनीय भाषाओं के लिए पूर्णता और कॉम्पैक्टनेस प्रमेय ZF में सिद्ध हैं। हालाँकि स्थिति तब भिन्न होती है जब भाषा तब से मनमाने ढंग से बड़ी कार्डिनैलिटी की होती है, हालाँकि ZF में पूर्णता और सघनता प्रमेय एक-दूसरे के बराबर साबित होते हैं, वे बूलियन प्राइम आदर्श के रूप में जाने जाने वाले पसंद के स्वयंसिद्ध के एक कमजोर रूप के भी साबित होते हैं। प्रमेय#अल्ट्राफ़िल्टर लेम्मा। विशेष रूप से, ZF का विस्तार करने वाला कोई भी सिद्धांत समान कार्डिनलिटी के सेट पर अल्ट्राफिल्टर लेम्मा को साबित किए बिना मनमानी (संभवतः बेशुमार) भाषाओं पर पूर्णता या कॉम्पैक्टनेस प्रमेय साबित नहीं कर सकता है।

अन्य तर्कों में पूर्णता

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

लिंडस्ट्रॉम के प्रमेय में कहा गया है कि प्रथम-क्रम तर्क सबसे मजबूत (कुछ बाधाओं के अधीन) तर्क है जो कॉम्पैक्टनेस और पूर्णता दोनों को संतुष्ट करता है।

क्रिपके शब्दार्थ के संबंध में मोडल तर्क या अंतर्ज्ञानवादी तर्क के लिए एक पूर्णता प्रमेय सिद्ध किया जा सकता है।

प्रमाण

गोडेल की पूर्णता प्रमेय का मूल प्रमाण समस्या को एक निश्चित वाक्यात्मक रूप में सूत्रों के लिए एक विशेष मामले में कम करके और फिर इस रूप को एक तदर्थ तर्क के साथ संभालकर आगे बढ़ा।

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

यह भी देखें

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

अग्रिम पठन

• Gödel, K (1929). Über die Vollständigkeit des Logikkalküls (Thesis). Doctoral dissertation. University Of Vienna. The first proof of the completeness theorem.
• Gödel, K (1930). "Die Vollständigkeit der Axiome des logischen Funktionenkalküls". Monatshefte für Mathematik (in Deutsch). 37 (1): 349–360. doi:10.1007/BF01696781. JFM 56.0046.04. S2CID 123343522. The same material as the dissertation, except with briefer proofs, more succinct explanations, and omitting the lengthy introduction.
• Hans Hermes (1973). Introduction to Mathematical Logic. Hochschultext (Springer-Verlag). London: Springer. ISBN 3540058192. ISSN 1431-4657. Chapter 5: "Gödel's completeness theorem".

बाहरी संबंध

• Stanford Encyclopedia of Philosophy: "Kurt Gödel"—by Juliette Kennedy.
• MacTutor biography: Kurt Gödel. Archived 2005-10-13 at the Wayback Machine
• Detlovs, Vilnis, and Podnieks, Karlis, "Introduction to mathematical logic."