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

Not to be confused with गोडेल की अपूर्णता प्रमेय.

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

गोडेल की पूर्णता प्रमेय गणितीय तर्क में एक मौलिक प्रमेय है जो प्रथम-कोटि तर्क में अर्थगत सत्य और वाक्यात्मक प्रायिकता के मध्य एक समतुल्यता स्थापित करता है।

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

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

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

प्रारंभिक

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

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

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

कथन

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

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

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

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

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

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

यदि $T\models s$, तब $T\vdash s$.

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

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

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

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

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

यदि $T$ वाक्यात्मक रूप से सुसंगत है तो $T$ के पास एक मॉडल है।

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

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

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

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

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

परिणाम

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

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

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

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

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

प्रथम अपूर्णता प्रमेय बताता है कि कोई भी $T$ जो निरंतर प्रभावी है तथा जिसमें रॉबिन्सन अंकगणित ( Q ) सम्मिलित है, उसे स्पष्ट रूप से एक वाक्य $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."