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

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$ पूर्ण (या निर्धारणीय) है यदि $T$ की भाषा में प्रत्येक वाक्य $S$ या तो सिद्ध करने योग्य ($T\vdash S$) या अस्वीकृत ($T\vdash \neg S$) है।

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

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

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

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

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

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

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

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

पूर्णता प्रमेय की प्रभावहीनता को व्युत्क्रमित गणित की प्रणाली पर मापा जा सकता है। जब एक गणनीय भाषा पर विचार किया जाता है तो पूर्णता और सघनता प्रमेय परस्पर समतुल्य होते हैं और चयन के एक अशक्त रूप के समान होते हैं, जिसे अशक्त कोनिग के लेम्मा के रूप में जाना जाता है, जो RCA₀ में समतुल्यता के साथ सिद्ध होता है (पीनो अंकगणित का एक दूसरे क्रम का संस्करण Σ⁰₁ सूत्रों पर प्रेरण तक सीमित है)। अशक्त कोनिग का लेम्मा 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."