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

तो क्या? नीचे मैं इसके बारे में बात करने के लिए "उंगलियों पर" करने की कोशिश करूंगा। बेशक, मेरी व्याख्या कठोर और सहज नहीं होगी, लेकिन मैं गणितज्ञों से कहूंगा कि वे मुझे सख्ती से न आंकें। यह संभव है कि गैर-गणितज्ञों (जो वास्तव में, मैं भी संबंधित हूं) के लिए, नीचे बताई गई बातों में कुछ नया और उपयोगी होगा।

गणितीय तर्क वास्तव में एक जटिल विज्ञान है, और सबसे महत्वपूर्ण बात, बहुत परिचित नहीं है। इसके लिए सावधानीपूर्वक और सख्त युद्धाभ्यास की आवश्यकता होती है, जिसमें यह महत्वपूर्ण है कि वास्तव में सिद्ध को इस तथ्य से भ्रमित न करें कि "यह पहले से ही स्पष्ट है।" हालाँकि, मुझे आशा है कि निम्नलिखित "टीजीएन के प्रमाण की रूपरेखा" को समझने के लिए, पाठक को केवल स्कूली गणित / कंप्यूटर विज्ञान, तार्किक सोच कौशल और 15-20 मिनट के समय के ज्ञान की आवश्यकता होगी।

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

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

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

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

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

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

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

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

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

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

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

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

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

औपचारिक अंकगणितीय कथनों के उदाहरण:

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

आदि। दूसरे शब्दों में, एफएसपी एक बूलियन मान के साथ एक प्राकृतिक तर्क के कार्यों के बराबर हैं।

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

आइए अब हम निम्नलिखित सूत्रीकरण में टीजीएन के प्रमाण के एक रेखाचित्र की ओर मुड़ें:

• औपचारिक अंकगणित की प्रस्तावित भाषा के लिए, कोई पूर्ण सुसंगत कटौती नहीं है।

हम विरोधाभास से साबित करेंगे।

तो चलिए मान लेते हैं कि ऐसा डिडक्टिव मौजूद है। आइए निम्नलिखित सहायक एल्गोरिथम का वर्णन करें जो एक प्राकृतिक संख्या के लिए एक बूलियन मान निर्दिष्ट करता है:

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

यहां हम एकमात्र स्थान पर आते हैं जहां मैं पाठक से इसके लिए अपना शब्द लेने के लिए कहूंगा।

जाहिर है, उपरोक्त धारणा के तहत, किसी भी एफएसपी को इनपुट पर एक प्राकृतिक संख्या और आउटपुट पर एक बूलियन मान वाले एल्गोरिदम से जोड़ा जा सकता है। कम स्पष्ट विपरीत है:

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

इस फिसलन भरी जगह से गुजरने के बाद हम जल्दी से अंत तक पहुंच जाते हैं।

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

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

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

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

• "चीनी भाषा में कोई भी वाक्यांश एक सच्चा कथन है यदि यह कॉमरेड माओ त्से तुंग की उद्धरण पुस्तक में निहित है, और यदि यह निहित नहीं है तो गलत है।"

फिर संबंधित पूर्ण और सुसंगत सिद्ध एल्गोरिथ्म (इसे "हठधर्मी निगमनात्मक" कहा जा सकता है) कुछ इस तरह दिखता है:

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

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

सबूत का विचार एक अभिव्यक्ति का निर्माण करना है जो इसकी गवाही देगा

खुद की अप्रमाणिकता। यह निर्माण तीन चरणों में किया जा सकता है:

पहला चरण औपचारिक अंकगणित और पूर्णांकों के सेट (gedelization) के बीच एक पत्राचार की स्थापना है;

दूसरा चरण कुछ विशेष संपत्ति का निर्माण है जिसके बारे में यह ज्ञात नहीं है कि यह औपचारिक अंकगणित का प्रमेय है या नहीं;

तीसरा चरण स्वयं से जुड़े एक निश्चित पूर्णांक के x के बजाय प्रतिस्थापन है, यानी सभी की इन संख्याओं द्वारा प्रतिस्थापन

प्रथम चरण। औपचारिक अंकगणित का ईश्वरीकरण

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

इस प्रकार, हम यह निष्कर्ष निकाल सकते हैं कि औपचारिक अंकगणित की प्रणाली का अपना मेटासिस्टम भी होता है।

अब हम अपने परिणामों को अधिक ठोस और विस्तार से प्रस्तुत करते हैं।

सबसे पहले, हम प्रत्येक प्रतीक और औपचारिक अंकगणित के साथ एक विशेष कोड पदनाम जोड़ सकते हैं, जिसे इस मामले में गोडेल नंबर कहा जाता है

दूसरे, हम कुछ रचना फ़ंक्शन का उपयोग करके वर्णों के प्रत्येक अनुक्रम को एक ही गोडेल संख्या प्रदान करते हैं। चलो वर्णों के अनुक्रम कहां हैं जो बनाते हैं

तीसरा (और यह आवश्यक है), स्वयंसिद्धों और प्रतिस्थापन नियमों (या प्रतिस्थापन नियमों) के अनुक्रम के प्रत्येक प्रमाण को एक संख्या सौंपी जाती है जहां सबूत में प्रयुक्त प्रमेयों के अनुक्रम को दर्शाता है

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

तो, आप प्रतीकों, प्रमेयों, प्रमाणों में हेरफेर करने के बजाय, उपयोग कर सकते हैं

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

आइए हम निम्नलिखित प्रस्ताव तैयार करें।

औपचारिक मेटारिदमेटिक प्राकृतिक संख्याओं के सेट में निहित है, और यह स्वयं औपचारिक अंकगणित की व्याख्या में निहित है।

औपचारिक अंकगणित के साथ यह स्थिति प्राकृतिक भाषा की स्थिति से मिलती-जुलती है: आखिरकार, कुछ भी हमें इसकी मूल अवधारणाओं और नियमों को तैयार करने के लिए इसका उपयोग करने से नहीं रोकता है।

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

तालिका 3.2

प्रत्येक सूत्र (1 से बारी-बारी से भिन्न प्रतीकों से मिलकर एक अनुक्रम द्वारा एन्कोड किया जाता है जिसमें पहली अभाज्य संख्याएँ होती हैं, अर्थात संख्या

एक अभाज्य संख्या कहाँ है।

बदले में, प्रमाण, यानी, सूत्रों के अनुक्रम को इसी तरह से संख्या . द्वारा एन्कोड किया जाएगा

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

ताकि उनके साथ छेड़छाड़ की जा सके। हालांकि, यह ध्यान दिया जाना चाहिए कि इस ऑपरेशन की मौलिक संभावना आवश्यक है।

उदाहरण। मान लीजिए कि संख्या T दी गई है, जो किसी प्रमाण के अनुरूप है और अभाज्य संख्याओं के गुणनफल को निरूपित करती है:

इस अपघटन का अर्थ है कि प्रमेय के प्रमाण में दो चरण होते हैं: एक संख्या 1981027125 253 से मेल खाती है, और दूसरी संख्या 1981027125 211 से मेल खाती है। इनमें से प्रत्येक संख्या को फिर से अभाज्य गुणनखंडों में विघटित करने पर, हम प्राप्त करते हैं

औपचारिक अंकगणितीय वर्णमाला कोडिंग तालिका (तालिका 3.2) से हम पाते हैं कि इन दो संख्याओं के लिए हमारे गोडेल नंबर

निम्नलिखित प्रमाण से मेल खाएगा:

सूत्र सूत्र से निम्नानुसार है

इस प्रकार, मेटारिदमेटिक में, मूल संख्या का मान औपचारिक अंकगणित से प्राप्त किया जाता है।

दूसरा चरण। गोडेल का लेम्मा

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

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

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

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

तीसरा चरण। अंतिम प्रतिस्थापन

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

हम इस दूसरे व्यंजक को a से और इसकी गोडेल संख्या को E से निरूपित करते हैं। आइए हम व्यंजक e की व्याख्या करें।

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

दूसरी व्याख्या। प्रमेय का कोई अंकगणितीय प्रमाण T नहीं है जो कि E का -प्रतिस्थापन होगा। इसलिए, यदि कोई प्रमाण नहीं है, तो ऐसा इसलिए है क्योंकि यह अपने आप में एक प्रमेय नहीं है। यह तीसरी व्याख्या की ओर ले जाता है।

तीसरी व्याख्या। एक व्यंजक जिसके लिए गोडेल संख्या E का -प्रतिस्थापन है, अंकगणित औपचारिक अंकगणित में एक प्रमेय नहीं है। लेकिन यह वह जगह है जहां विरोधाभास निहित है, क्योंकि निर्माण द्वारा यह स्वयं ई का एक प्रतिस्थापन है, और संख्या निर्माण द्वारा संख्या ई के अलावा कुछ भी नहीं है। इसका मतलब ई की अंतिम व्याख्या है।

09सेन

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

1900 में, पेरिस में गणितज्ञों का विश्व सम्मेलन आयोजित किया गया, जहाँ डेविड गिल्बर्ट(डेविड हिल्बर्ट, 1862-1943) ने उनके विचार में 23 सबसे महत्वपूर्ण कार्यों की रूपरेखा तैयार की, जिन्हें आने वाली बीसवीं सदी के सिद्धांतकारों को हल करना था। उनकी सूची में नंबर दो उन साधारण समस्याओं में से एक थी जो तब तक स्पष्ट प्रतीत होती हैं जब तक आप थोड़ा गहरा खुदाई नहीं करते। आधुनिक शब्दों में, यह प्रश्न था: क्या गणित अपने आप में पर्याप्त है? हिल्बर्ट के दूसरे कार्य को कड़ाई से साबित करने की आवश्यकता के लिए कम कर दिया गया था कि सिद्धांतों की प्रणाली - बिना सबूत के आधार के रूप में गणित में लिए गए बुनियादी बयान - सही और पूर्ण है, यानी यह मौजूद हर चीज के गणितीय विवरण की अनुमति देता है। यह साबित करना आवश्यक था कि स्वयंसिद्धों की ऐसी प्रणाली स्थापित करना संभव है कि, सबसे पहले, वे परस्पर सुसंगत होंगे, और दूसरी बात, किसी भी कथन की सच्चाई या असत्य के संबंध में कोई उनसे निष्कर्ष निकाल सकता है।

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

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

"यदि एक कथन A को सिद्ध किया जा सकता है, तो एक गैर-A कथन को सिद्ध किया जा सकता है।"

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

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

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

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

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

1900 में, पेरिस में गणितज्ञों का विश्व सम्मेलन आयोजित किया गया था, जिसमें डेविड हिल्बर्ट (1862-1943) ने अमूर्त के रूप में 23 सबसे महत्वपूर्ण, उनकी राय में, उनके द्वारा तैयार की गई समस्याओं को प्रस्तुत किया, जिन्हें सैद्धांतिक वैज्ञानिकों द्वारा हल किया जाना था। आने वाली बीसवीं सदी के। उनकी सूची में नंबर दो उन साधारण समस्याओं में से एक थी जो तब तक स्पष्ट प्रतीत होती हैं जब तक आप थोड़ा गहरा खुदाई नहीं करते। आधुनिक शब्दों में, यह प्रश्न था: क्या गणित अपने आप में पर्याप्त है? हिल्बर्ट की दूसरी समस्या यह साबित करना था कि सिस्टम सूक्तियों- बिना प्रमाण के आधार के रूप में गणित में लिए गए मूल कथन - पूर्ण और पूर्ण हैं, अर्थात यह आपको गणितीय रूप से हर उस चीज़ का वर्णन करने की अनुमति देता है जो मौजूद है। यह साबित करना आवश्यक था कि स्वयंसिद्धों की ऐसी प्रणाली स्थापित करना संभव है कि, सबसे पहले, वे परस्पर सुसंगत होंगे, और दूसरी बात, किसी भी कथन की सच्चाई या असत्य के संबंध में कोई उनसे निष्कर्ष निकाल सकता है।

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

और फिर 1931 में, कुछ विनीज़ चश्मे वाले गणितज्ञ कर्ट गोडेल ने एक छोटा लेख लिया और प्रकाशित किया जिसने तथाकथित "गणितीय तर्क" की पूरी दुनिया को उलट दिया। लंबी और जटिल गणितीय और सैद्धांतिक प्रस्तावनाओं के बाद, उन्होंने सचमुच निम्नलिखित की स्थापना की। आइए कोई भी कथन लें जैसे: "धारणा # 247 इस प्रणाली के स्वयंसिद्धों में तार्किक रूप से अप्राप्य है" और इसे "कथन ए" कहते हैं। तो गोडेल ने बस निम्नलिखित अद्भुत संपत्ति साबित की कोई भीस्वयंसिद्ध प्रणाली:

"यदि एक कथन A को सिद्ध किया जा सकता है, तो एक गैर-A कथन को सिद्ध किया जा सकता है।"

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

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

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

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

मुझे आश्चर्य है कि क्या हिल्बर्ट को पता था कि उनके प्रश्न हमें कितनी दूर ले जाएंगे?

कर्ट गोडेल, 1906-78

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

उसपेन्स्की वी.ए.

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

सैद्धांतिक कंप्यूटर विज्ञान 130,1994, पीपी.273-238।

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

सत्य के सार्वभौमिक मानदंड की असंभवता के बारे में निष्कर्ष है

संयोजन द्वारा टार्स्की द्वारा प्राप्त परिणाम का प्रत्यक्ष परिणाम

सत्य के अपने सिद्धांत के साथ गोडेल की अनिर्णयता प्रमेय, के अनुसार

जो अपेक्षाकृत के लिए भी सत्य का कोई सार्वभौमिक मानदंड नहीं हो सकता है

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

अंकगणित। स्वाभाविक रूप से, यह परिणाम सत्य की अवधारणा के लिए एक फोर्टियोरी लागू होता है

ज्ञान के किसी भी गैर-गणितीय क्षेत्र में जिसमें यह व्यापक रूप से है

अंकगणित का प्रयोग किया जाता है।

कार्ल पॉपर

उसपेन्स्की व्लादिमीर एंड्रीविच का जन्म 27 नवंबर, 1930 को मास्को में हुआ था। मॉस्को स्टेट यूनिवर्सिटी (1952) के यांत्रिकी और गणित संकाय से स्नातक किया। डॉक्टर ऑफ फिजिकल एंड मैथमैटिकल साइंसेज (1964)। प्रोफेसर, यांत्रिकी और गणित संकाय के गणितीय तर्क और एल्गोरिदम के सिद्धांत विभाग के प्रमुख (1966)। व्याख्यान के पाठ्यक्रम पढ़ता है "गणितीय तर्क का परिचय", "कम्प्यूटेबल फ़ंक्शंस", "गोडेल की पूर्णता प्रमेय"। तैयार किए 25 अभ्यर्थी व विज्ञान के 2 डॉक्टर

1. समस्या का विवरण

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

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

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

1.1.1. वर्णमाला

वर्णमाला से हमारा तात्पर्य प्राथमिक संकेतों के एक सीमित समूह से है (अर्थात, ऐसी चीजें जिन्हें घटक भागों में विभाजित नहीं किया जा सकता है)। इन वर्णों को वर्णमाला के अक्षर कहते हैं। वर्णमाला के एक शब्द से हमारा तात्पर्य अक्षरों के परिमित अनुक्रम से है। उदाहरण के लिए, अंग्रेजी में सामान्य शब्द (उचित नामों सहित) 54-अक्षर वाले वर्णमाला (26 छोटे अक्षर, 26 बड़े अक्षर, एक डैश और एक अक्षर) के शब्द हैं। एक अन्य उदाहरण - दशमलव अंकन में प्राकृतिक संख्याएं 10-अक्षर वाले वर्णमाला के शब्द हैं, जिनके अक्षर संकेत हैं: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9। हम साधारण बड़े अक्षरों का उपयोग निरूपित करने के लिए करेंगे। अक्षर। यदि L एक अक्षर है, तो L? अक्षर L के सभी शब्दों के समुच्चय को निरूपित करेगा, - इसके अक्षरों से बनने वाले शब्द। हम मान लेंगे कि किसी भी भाषा की अपनी वर्णमाला होती है, इसलिए इस भाषा के सभी भाव (यानी - विभिन्न वस्तुओं के नाम, इन वस्तुओं के बारे में कथन आदि) इस वर्णमाला के शब्द हैं। उदाहरण के लिए, अंग्रेजी भाषा में किसी भी वाक्य के साथ-साथ अंग्रेजी में लिखे गए किसी भी पाठ को विस्तारित 54-अक्षर वर्णमाला के शब्द के रूप में माना जा सकता है, जिसमें विराम चिह्न, इंटरवर्ड स्पेस, एक लाल रेखा वर्ण, और संभवतः कुछ शामिल हैं। अन्य उपयोगी पात्र। यह मानते हुए कि भाषा के भाव कुछ वर्णमाला के शब्द हैं, हम इस प्रकार ???f(x)dx जैसे "बहुपरत" अभिव्यक्तियों पर विचार नहीं करते हैं। हालांकि, यह सीमा बहुत महत्वपूर्ण नहीं है, क्योंकि उपयुक्त सम्मेलनों का उपयोग करके ऐसी किसी भी अभिव्यक्ति को रैखिक रूप में "विस्तारित" किया जा सकता है। एल में निहित कोई भी सेट एम? अक्षर L का शब्द समुच्चय कहलाता है। यदि हम केवल यह कहें कि M एक शब्द समुच्चय है, तो हमारा अर्थ है कि यह किसी वर्णमाला का शब्द है। अब ऊपर दी गई भाषा की धारणा को निम्नानुसार दोहराया जा सकता है: किसी भी भाषा में, अभिव्यक्तियों का कोई भी सेट एक शब्द सेट होता है।

1.1.2 बहुत सारे सच्चे दावे

हम मानते हैं कि हमें समुच्चय L का उपसमुच्चय T दिया गया है? (जहां एल किसी भाषा की वर्णमाला है जिस पर हम विचार कर रहे हैं), जिसे "सच्चे बयान" (या बस "सत्य") का सेट कहा जाता है। उपसमुच्चय T में सीधे पास करते हुए, हम तर्क के निम्नलिखित मध्यवर्ती चरणों को छोड़ देते हैं: सबसे पहले, वर्णमाला L के कौन से शब्द भाषा के सुगठित भाव हैं, अर्थात, इस भाषा की हमारी व्याख्या में उनका एक निश्चित अर्थ है (उदाहरण के लिए) , 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 सुगठित व्यंजक हैं, जबकि +=x जैसे व्यंजक नहीं हैं); दूसरे, कौन से व्यंजक सूत्र हैं, अर्थात्। एक पैरामीटर पर निर्भर हो सकता है (जैसे, x=3, x=y, 2=3, 2=2); तीसरा, कौन से सूत्र बंद सूत्र हैं, अर्थात। बयान जो मापदंडों पर निर्भर नहीं करते हैं (उदाहरण के लिए, 2=3, 2=2); और अंत में, कौन से बंद सूत्र सत्य कथन हैं (उदाहरण के लिए, 2=2)।

1.1.3. मौलिक भाषा जोड़ी

1.2. "अप्रमाणित"

"अप्रमाणित" का अर्थ है कोई सबूत नहीं होना।

1.3. प्रमाण

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

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

इस प्रकार, परिभाषा का हमारा अंतिम शब्द इस प्रकार है:

(1) हमारे पास वर्णमाला एल (भाषा की वर्णमाला) और वर्णमाला पी (प्रमाण का वर्णमाला) है।

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

(3) इसके अलावा हमारे पास एक कार्य है? (वास्तव में क्या सिद्ध किया गया है) खोजने के लिए, किसका डोमेन है? पी?पी? की स्थिति को संतुष्ट करता है, और किसकी सीमा पी में है? हम मानते हैं कि हमारे पास एक एल्गोरिथ्म है जो इस फ़ंक्शन की गणना करता है ("एल्गोरिदम एक फ़ंक्शन की गणना करता है" शब्दों का सटीक अर्थ निम्नलिखित है: इस एल्गोरिथ्म का उपयोग करके फ़ंक्शन मान प्राप्त किए जाते हैं - विशेष परिवर्तन नियमों का एक सेट)। हम कहेंगे कि तत्व p? P शब्द का प्रमाण है?(p) अक्षर L का।

एक ट्रिपल जो शर्तों को संतुष्ट करता है (1) - (3) को वर्णमाला एल पर एक निगमन प्रणाली कहा जाता है।

"स्वयंसिद्ध" और "अनुमान के नियम" के संदर्भ में "प्रमाण" को परिभाषित करने के सामान्य तरीके से परिचित पाठक के लिए, अब हम बताएंगे कि इस पद्धति को खंड 1.3.2 में दी गई परिभाषा के एक विशेष मामले के रूप में कैसे माना जा सकता है। यही है, एक सबूत को आमतौर पर ऐसी भाषा अभिव्यक्तियों के अनुक्रम के रूप में परिभाषित किया जाता है, जिनमें से प्रत्येक या तो एक स्वयंसिद्ध है या पहले से मौजूद बयानों में से किसी एक अनुमान नियमों का उपयोग करके प्राप्त किया गया है। यदि हम अपनी भाषा के वर्णमाला में एक नया शब्द * जोड़ते हैं, तो हम परिणामी वर्णमाला का उपयोग करके बनाए गए शब्द के रूप में ऐसा प्रमाण लिख सकते हैं: अभिव्यक्तियों का क्रम C1*C2*...*Cn शब्द बन जाता है। इस मामले में, फ़ंक्शन जो यह निर्धारित करता है कि वास्तव में क्या साबित हुआ है, इस शब्द के उस हिस्से में इसका मूल्य है जो अनुक्रम में अंतिम अक्षर * के तुरंत बाद है। एल्गोरिथम जिसका अस्तित्व खंड 1.3.2 में आवश्यक है। एक बार जब हम "स्वयंसिद्ध" और "अनुमान का नियम" शब्दों के किसी भी स्वीकृत अर्थ को ठीक से परिभाषित कर लेते हैं, तो परिभाषाएँ आसानी से बनाई जा सकती हैं।

1.4. अपूर्णता प्रमेय को सटीक रूप से तैयार करने का प्रयास

1.4.1. पहली कोशिश

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

1.4.2. दूसरा प्रयास

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

"मूल जोड़ी के संबंध में कुछ शर्तों के तहत, ऐसी कोई निगमन प्रणाली नहीं है जिसमें T के प्रत्येक शब्द का एक प्रमाण होगा।"

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

1.5. संगतता

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

1.6. संपूर्णता

ऐसा कहा जाता है कि एक मौलिक जोड़ी के संबंध में एक निगमन प्रणाली पूर्ण है, बशर्ते कि? (पी)? टी। तब अपूर्णता प्रमेय का हमारा सूत्रीकरण निम्नलिखित रूप लेता है:

मौलिक जोड़ी के संबंध में कुछ शर्तों के तहत, एल पर कोई कटौती प्रणाली नहीं है जो पूर्ण और अपेक्षाकृत सुसंगत दोनों है।