रॉबिन्सन अंकगणित: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{short description|Axiomatic logical system}}
{{short description|Axiomatic logical system}}
गणित में, रॉबिन्सन अंकगणित प्रथम-क्रम [[पीनो अंकगणित]] (पीए) का सूक्ष्म रूप से स्वयंसिद्ध टुकड़ा है, जिसे पहली बार 1950 में आर. एम. रॉबिन्सन द्वारा निर्धारित किया गया था।{{sfn|Robinson|1950}} इसे आमतौर पर Q से दर्शाया जाता है। Q लगभग है{{clarification needed|date=January 2023|reason=Authors tend to use slightly different but closely related versions of Q, so it would be helpful to explain more clearly the claim that the finite fragment of PA formed from PA with the induction schema removed is not the same as Q (in the sense intended in this article).}} [[गणितीय प्रेरण]] की स्वयंसिद्ध स्कीमा के बिना पीए। Q, PA से कमज़ोर है लेकिन इसकी भाषा ही है, और दोनों सिद्धांत पूर्ण सिद्धांत हैं। क्यू महत्वपूर्ण और दिलचस्प है क्योंकि यह पीए का सूक्ष्म रूप से स्वयंसिद्ध टुकड़ा है जो पुनरावर्ती रूप से अपूर्ण है और Decidability_(logic)#Decidability_of_a_theory है।
गणित में, रॉबिन्सन अंकगणित प्रथम-क्रम [[पीनो अंकगणित]] (पीए) का एक सूक्ष्म रूप से स्वयंसिद्ध भाग है, जिसे पहली बार 1950 में आर. एम. रॉबिन्सन द्वारा निर्धारित किया गया था।{{sfn|Robinson|1950}} इसे सामान्यतः '''Q''' से दर्शाया जाता है। '''Q''' [[गणितीय प्रेरण]] की स्वयंसिद्ध स्कीमा के बिना लगभग PA है। '''Q''', PA से कमज़ोर है किन्तु इसकी भाषा समान है, और दोनों सिद्धांत अपूर्ण हैं। '''Q''', महत्वपूर्ण और रोचक है क्योंकि यह PA का एक सूक्ष्म रूप से स्वयंसिद्ध भाग है जो पुनरावर्ती रूप से अपूर्ण और अनिवार्य रूप से अनिर्णीत है।


==स्वसिद्धांत==
==स्वसिद्धांत==
Q का फॉर्मल_सिस्टम#लॉजिकल_सिस्टम प्रथम-क्रम तर्क#समानता और उसके सिद्धांत|पहचान के साथ प्रथम-क्रम तर्क है, जिसे infix '=' द्वारा दर्शाया गया है। व्यक्ति, जिन्हें [[प्राकृतिक संख्या]]एँ कहा जाता है, समुच्चय (गणित) के सदस्य हैं जिन्हें N कहा जाता है और विशिष्ट सदस्य 0 है, जिसे [[शून्य]] कहा जाता है। N पर तीन [[ऑपरेशन (गणित)]] हैं:
'''Q''' का पृष्ठभूमि तर्क पहचान के साथ प्रथम-क्रम तर्क है, जिसे infix '=' द्वारा दर्शाया गया है। व्यक्ति, जिन्हें [[प्राकृतिक संख्या|प्राकृतिक संख्याएँ]] कहा जाता है, एक विशिष्ट सदस्य '''0''' के साथ '''N''' नामक समुच्चय के सदस्य हैं, जिसे शून्य कहा जाता है। '''N''' पर तीन [[ऑपरेशन (गणित)]] हैं:


*[[यूनरी ऑपरेशन]] जिसे [[उत्तराधिकारी कार्य]] कहा जाता है और [[उपसर्ग संकेतन]] ''एस'' द्वारा दर्शाया जाता है;
*[[यूनरी ऑपरेशन]] जिसे [[उत्तराधिकारी कार्य|उत्तराधिकारी फलन]] कहा जाता है और [[उपसर्ग संकेतन]] ''S'' द्वारा दर्शाया जाता है;
*दो [[बाइनरी ऑपरेशन]], जोड़ और [[गुणा]], क्रमशः इनफ़िक्स + और · द्वारा दर्शाए गए।
*दो [[बाइनरी ऑपरेशन]] जोड़ और [[गुणा]] क्रमशः इन्फ़िक्स '''+''' और '''·''' द्वारा दर्शायी जाती हैं।


Q के लिए निम्नलिखित अभिगृहीत Q1-Q7 हैं {{harvtxt|Burgess|2005|p=42}} (cf. [[प्रथम-क्रम अंकगणित]] के स्वयंसिद्ध भी)। वेरिएबल (गणित) जो [[अस्तित्वगत परिमाणक]] से बंधे नहीं हैं, अंतर्निहित [[सार्वभौमिक परिमाणक]] से बंधे हैं।
{{harvtxt|बर्गेस||p=}} (2005, पृष्ठ 42) में '''Q''' के लिए निम्नलिखित स्वयंसिद्ध कथन Q1-Q7 हैं (cf. [[प्रथम-क्रम अंकगणित]] के स्वयंसिद्ध भी हैं)। वे वेरिएबल जो [[अस्तित्वगत परिमाणक]] से बंधे नहीं हैं वे एक अंतर्निहित [[सार्वभौमिक परिमाणक]] से बंधे हैं।


# एसएक्स ≠ '0'
# ''Sx'' ≠ '''0'''
#
#*'0' किसी भी संख्या का उत्तराधिकारी नहीं है.
#*'0' किसी भी संख्या का उत्तराधिकारी नहीं है.
# (Sx = Sy) → x = y
# (Sx = Sy) → x = y
#* यदि x का उत्तराधिकारी, y के उत्तराधिकारी के समान है, तो x और y समान हैं। (1) और (2) 'एन' (यह '0' से घिरा [[अनंत सेट]] है) और एस (यह [[इंजेक्शन समारोह]] है जिसका फ़ंक्शन का डोमेन 'एन' है) के बारे में न्यूनतम तथ्य प्राप्त करते हैं जो गैर- के लिए आवश्यक हैं। तुच्छता. (2) का [[रूपांतरण (तर्क)]] पहचान के गुणों से होता है।
#*यदि x का उत्तराधिकारी, y के उत्तराधिकारी के समान है, तो x और y समान हैं। (1) और (2) '<nowiki/>'''N'''<nowiki/>' (यह '<nowiki/>'''0'''<nowiki/>' से घिरा [[अनंत सेट]] है) और S (यह [[इंजेक्शन समारोह|इन्जेक्टिव फलन]] है जिसका फलन का डोमेन ''''N'''<nowiki/>' है) के बारे में गैर-तुच्छता के लिए आवश्यक न्यूनतम तथ्य प्राप्त करते हैं। (2) का [[रूपांतरण (तर्क)|व्युत्क्रम (तर्क)]] सर्वसमिका के गुणों से आता है।
# y='0' ∨ ∃x (Sx = y)
# y=''''0'''<nowiki/>' ∨ ∃x (Sx = y)
#* प्रत्येक संख्या या तो '0' है या किसी संख्या का उत्तराधिकारी है। अंकगणित में मौजूद गणितीय प्रेरण की स्वयंसिद्ध स्कीमा 'क्यू' से अधिक मजबूत है जो इस स्वयंसिद्ध को प्रमेय में बदल देती है।
#* प्रत्येक संख्या या तो ''''0'''<nowiki/>' है या किसी संख्या का उत्तराधिकारी है। अंकगणित में उपस्थित गणितीय प्रेरण की स्वयंसिद्ध स्कीमा ''''Q'''<nowiki/>' से अधिक मजबूत है जो इस स्वयंसिद्ध को प्रमेय में बदल देती है।
# x + '0' = x
# x + ''''0'''<nowiki/>' = x
# x + Sy = S(x + y)
# x + Sy = S(x + y)
#* (4) और (5) जोड़ की [[पुनरावर्ती परिभाषा]] हैं।
#* (4) और (5) जोड़ की [[पुनरावर्ती परिभाषा]] हैं।
# x·'0' = '0'
# x·''''0'''<nowiki/>' = ''''0'''<nowiki/>'
# x·Sy = (x·y) + x
# x·Sy = (x·y) + x
#* (6) और (7) गुणन की पुनरावर्ती परिभाषा हैं।
#* (6) और (7) गुणन की पुनरावर्ती परिभाषा हैं।
Line 34: Line 35:
* ''x'' < ''y'' ∨ ''x'' = ''y'' ∨ ''y'' < ''x''
* ''x'' < ''y'' ∨ ''x'' = ''y'' ∨ ''y'' < ''x''


Q+ अभी भी Q का रूढ़िवादी विस्तार है, इस अर्थ में कि Q+ में सिद्ध होने वाला कोई भी सूत्र जिसमें <प्रतीक नहीं है, Q में पहले से ही सिद्ध है। (उपरोक्त तीन सिद्धांतों में से केवल पहले दो को Q में जोड़ने से Q का रूढ़िवादी विस्तार मिलता है) किस के बराबर {{harvtxt|Burgess|2005|p=56}} Q* को कॉल करता है। यह सभी देखें {{harvtxt|Burgess|2005|p=230|loc=fn. 24}}, लेकिन ध्यान दें कि उपरोक्त तीन स्वयंसिद्धों में से दूसरे को केवल स्वयंसिद्ध जोड़कर प्राप्त क्यू के शुद्ध परिभाषा विस्तार से नहीं निकाला जा सकता है {{nowrap|1=''x'' < ''y'' ↔ ∃''z'' (''Sz'' + ''x'' = ''y'')}}.)
Q+ अभी भी Q का रूढ़िवादी विस्तार है, इस अर्थ में कि Q+ में सिद्ध होने वाला कोई भी सूत्र जिसमें <प्रतीक नहीं है, Q में पहले से ही सिद्ध है। (उपरोक्त तीन सिद्धांतों में से केवल पहले दो को Q में जोड़ने से Q का रूढ़िवादी विस्तार मिलता है) किस के बराबर {{harvtxt|Burgess|2005|p=56}} Q* को कॉल करता है। यह सभी देखें {{harvtxt|Burgess|2005|p=230|loc=fn. 24}}, किन्तु ध्यान दें कि उपरोक्त तीन स्वयंसिद्धों में से दूसरे को केवल स्वयंसिद्ध जोड़कर प्राप्त क्यू के शुद्ध परिभाषा विस्तार से नहीं निकाला जा सकता है {{nowrap|1=''x'' < ''y'' ↔ ∃''z'' (''Sz'' + ''x'' = ''y'')}}.)


Q के अभिगृहीतों (1)-(7) के बीच, अभिगृहीत (3) को आंतरिक अस्तित्वगत परिमाणक की आवश्यकता है। {{harvtxt|Shoenfield|1967|p=22}} स्वयंसिद्धीकरण देता है जिसमें केवल (अंतर्निहित) बाहरी सार्वभौमिक परिमाणक होते हैं, क्यू के स्वयंसिद्ध (3) को छोड़कर लेकिन उपरोक्त तीन स्वयंसिद्धों को < के साथ आदिम के रूप में जोड़कर। अर्थात्, शॉनफील्ड की प्रणाली Q+ शून्य अभिगृहीत (3) है, और Q+ से सख्ती से कमजोर है, क्योंकि अभिगृहीत (3) अन्य अभिगृहीतों से स्वतंत्र है (उदाहरण के लिए, से कम क्रमसूचक) <math>\omega^\omega</math> (3) को छोड़कर सभी स्वयंसिद्धों के लिए मॉडल बनाता है जब Sv की व्याख्या v + 1 के रूप में की जाती है। शॉनफ़ील्ड की प्रणाली भी इसमें दिखाई देती है {{harvtxt|Boolos|Burgess|Jeffrey|2002|loc=Sec 16.2}}, जहां इसे न्यूनतम अंकगणित कहा जाता है ('क्यू' द्वारा भी दर्शाया जाता है)। निकट से संबंधित स्वयंसिद्धीकरण, जो < के बजाय ≤ का उपयोग करता है, पाया जा सकता है {{harvtxt|Machover|1996|pp=256–257}}.
Q के अभिगृहीतों (1)-(7) के बीच, अभिगृहीत (3) को आंतरिक अस्तित्वगत परिमाणक की आवश्यकता है। {{harvtxt|Shoenfield|1967|p=22}} स्वयंसिद्धीकरण देता है जिसमें केवल (अंतर्निहित) बाहरी सार्वभौमिक परिमाणक होते हैं, क्यू के स्वयंसिद्ध (3) को छोड़कर किन्तु उपरोक्त तीन स्वयंसिद्धों को < के साथ आदिम के रूप में जोड़कर। अर्थात्, शॉनफील्ड की प्रणाली Q+ शून्य अभिगृहीत (3) है, और Q+ से सख्ती से कमजोर है, क्योंकि अभिगृहीत (3) अन्य अभिगृहीतों से स्वतंत्र है (उदाहरण के लिए, से कम क्रमसूचक) <math>\omega^\omega</math> (3) को छोड़कर सभी स्वयंसिद्धों के लिए मॉडल बनाता है जब Sv की व्याख्या v + 1 के रूप में की जाती है। शॉनफ़ील्ड की प्रणाली भी इसमें दिखाई देती है {{harvtxt|Boolos|Burgess|Jeffrey|2002|loc=Sec 16.2}}, जहां इसे न्यूनतम अंकगणित कहा जाता है ('क्यू' द्वारा भी दर्शाया जाता है)। निकट से संबंधित स्वयंसिद्धीकरण, जो < के बजाय ≤ का उपयोग करता है, पाया जा सकता है {{harvtxt|Machover|1996|pp=256–257}}.


==मेटामैथेमेटिक्स==
==मेटामैथेमेटिक्स==
Line 45: Line 46:
क्यू, पीनो अंकगणित की तरह, सभी अनंत [[प्रमुखता]] के [[अंकगणित का गैर-मानक मॉडल]] है। हालाँकि, पीनो अंकगणित के विपरीत, टेनेनबाम का प्रमेय Q पर लागू नहीं होता है, और इसमें गणना योग्य गैर-मानक मॉडल हैं। उदाहरण के लिए, क्यू का गणना योग्य मॉडल है जिसमें सकारात्मक अग्रणी गुणांक के साथ पूर्णांक-गुणांक बहुपद, साथ ही शून्य बहुपद, उनके सामान्य अंकगणित के साथ शामिल है।
क्यू, पीनो अंकगणित की तरह, सभी अनंत [[प्रमुखता]] के [[अंकगणित का गैर-मानक मॉडल]] है। हालाँकि, पीनो अंकगणित के विपरीत, टेनेनबाम का प्रमेय Q पर लागू नहीं होता है, और इसमें गणना योग्य गैर-मानक मॉडल हैं। उदाहरण के लिए, क्यू का गणना योग्य मॉडल है जिसमें सकारात्मक अग्रणी गुणांक के साथ पूर्णांक-गुणांक बहुपद, साथ ही शून्य बहुपद, उनके सामान्य अंकगणित के साथ शामिल है।


क्यू की उल्लेखनीय विशेषता गणितीय प्रेरण की स्वयंसिद्ध योजना की अनुपस्थिति है। इसलिए क्यू में प्राकृतिक संख्याओं के बारे में किसी तथ्य के प्रत्येक विशिष्ट उदाहरण को साबित करना अक्सर संभव होता है, लेकिन संबंधित सामान्य प्रमेय को नहीं। उदाहरण के लिए, Q में 5 + 7 = 7 + 5 सिद्ध है, लेकिन सामान्य कथन ''x'' + ''y'' = ''y'' + ''x'' सिद्ध नहीं है। इसी तरह, कोई यह साबित नहीं कर सकता कि ''Sx'' ≠ ''x''। {{sfn|Burgess|2005|p=56}} क्यू का मॉडल जो कई मानक तथ्यों को विफल करता है, दो अलग-अलग नए तत्वों ए और बी को प्राकृतिक संख्याओं के मानक मॉडल से जोड़कर और सा = ए, एसबी = बी, एक्स + ए = बी और एक्स + बी = को परिभाषित करके प्राप्त किया जाता है। a सभी x के लिए, a + n = a और b + n = b यदि n मानक प्राकृतिक संख्या है, x·0 = 0 सभी x के लिए, a·n = b और b·n = a यदि n गैर- है शून्य मानक प्राकृतिक संख्या, x = a को छोड़कर सभी x के लिए x·a = a, x = b को छोड़कर सभी x के लिए x·b = b, a·a = b, और b·b = a।{{sfn|Boolos|Burgess|Jeffrey|2002|loc=Sec 16.4}}
क्यू की उल्लेखनीय विशेषता गणितीय प्रेरण की स्वयंसिद्ध योजना की अनुपस्थिति है। इसलिए क्यू में प्राकृतिक संख्याओं के बारे में किसी तथ्य के प्रत्येक विशिष्ट उदाहरण को साबित करना अक्सर संभव होता है, किन्तु संबंधित सामान्य प्रमेय को नहीं। उदाहरण के लिए, Q में 5 + 7 = 7 + 5 सिद्ध है, किन्तु सामान्य कथन ''x'' + ''y'' = ''y'' + ''x'' सिद्ध नहीं है। इसी तरह, कोई यह साबित नहीं कर सकता कि ''Sx'' ≠ ''x''। {{sfn|Burgess|2005|p=56}} क्यू का मॉडल जो कई मानक तथ्यों को विफल करता है, दो अलग-अलग नए तत्वों ए और बी को प्राकृतिक संख्याओं के मानक मॉडल से जोड़कर और सा = ए, एसबी = बी, एक्स + ए = बी और एक्स + बी = को परिभाषित करके प्राप्त किया जाता है। a सभी x के लिए, a + n = a और b + n = b यदि n मानक प्राकृतिक संख्या है, x·0 = 0 सभी x के लिए, a·n = b और b·n = a यदि n गैर- है शून्य मानक प्राकृतिक संख्या, x = a को छोड़कर सभी x के लिए x·a = a, x = b को छोड़कर सभी x के लिए x·b = b, a·a = b, और b·b = a।{{sfn|Boolos|Burgess|Jeffrey|2002|loc=Sec 16.4}}


क्यू की व्याख्या ज़र्मेलो सेट सिद्धांत के टुकड़े में की जा सकती है | ज़र्मेलो का स्वयंसिद्ध सेट सिद्धांत, जिसमें विस्तारशीलता, [[खाली सेट]] का अस्तित्व और युग्म का स्वयंसिद्ध शामिल है। यह सिद्धांत S' में है {{harvtxt|Tarski|Mostowski|Robinson|1953|p=34}} और एसटी में {{harvtxt|Burgess|2005|pp=90-91,223}}. अधिक विवरण के लिए [[सामान्य समुच्चय सिद्धांत]] देखें।
क्यू की व्याख्या ज़र्मेलो सेट सिद्धांत के टुकड़े में की जा सकती है | ज़र्मेलो का स्वयंसिद्ध सेट सिद्धांत, जिसमें विस्तारशीलता, [[खाली सेट]] का अस्तित्व और युग्म का स्वयंसिद्ध शामिल है। यह सिद्धांत S' में है {{harvtxt|Tarski|Mostowski|Robinson|1953|p=34}} और एसटी में {{harvtxt|Burgess|2005|pp=90-91,223}}. अधिक विवरण के लिए [[सामान्य समुच्चय सिद्धांत]] देखें।


क्यू प्रथम-क्रम सिद्धांतों की सूक्ष्म रूप से स्वयंसिद्ध सूची है | प्रथम-क्रम सिद्धांत जो कि पीनो अंकगणित (पीए) से काफी कमजोर है, और जिसके सिद्धांतों में केवल अस्तित्वगत परिमाणक होता है। फिर भी पीए की तरह यह गोडेल की अपूर्णता प्रमेयों के अर्थ में अपूर्ण और अपूर्ण है, और अनिवार्य रूप से अनिर्णीत है। {{harvtxt|Robinson|1950}} ऊपर दिए गए Q अभिगृहीतों (1)-(7) को इस बात पर ध्यान देकर व्युत्पन्न किया गया है कि पीए अभिगृहीतों की क्या आवश्यकता है {{sfn|Mendelson|2015|loc=Proposition 3.24|p=188}} यह साबित करने के लिए कि प्रत्येक गणना योग्य फ़ंक्शन पीए में प्रतिनिधित्व योग्य है।<ref>A function <math>f</math> is said to be ''representable'' in <math>\operatorname{PA}</math> if there is a formula <math>\phi</math> such that for all <math>x_1, \cdots, x_k, y</math>
क्यू प्रथम-क्रम सिद्धांतों की सूक्ष्म रूप से स्वयंसिद्ध सूची है | प्रथम-क्रम सिद्धांत जो कि पीनो अंकगणित (पीए) से काफी कमजोर है, और जिसके सिद्धांतों में केवल अस्तित्वगत परिमाणक होता है। फिर भी पीए की तरह यह गोडेल की अपूर्णता प्रमेयों के अर्थ में अपूर्ण और अपूर्ण है, और अनिवार्य रूप से अनिर्णीत है। {{harvtxt|Robinson|1950}} ऊपर दिए गए Q अभिगृहीतों (1)-(7) को इस बात पर ध्यान देकर व्युत्पन्न किया गया है कि पीए अभिगृहीतों की क्या आवश्यकता है {{sfn|Mendelson|2015|loc=Proposition 3.24|p=188}} यह साबित करने के लिए कि प्रत्येक गणना योग्य फलन पीए में प्रतिनिधित्व योग्य है।<ref>A function <math>f</math> is said to be ''representable'' in <math>\operatorname{PA}</math> if there is a formula <math>\phi</math> such that for all <math>x_1, \cdots, x_k, y</math>
:<math>f(\vec{x}) = y \Longleftrightarrow \operatorname{PA} \vdash \phi(\vec{x}, y),</math>
:<math>f(\vec{x}) = y \Longleftrightarrow \operatorname{PA} \vdash \phi(\vec{x}, y),</math>
:<math>f(\vec{x}) \neq y \Longleftrightarrow \operatorname{PA} \vdash \lnot \phi(\vec{x}, y).</math>
:<math>f(\vec{x}) \neq y \Longleftrightarrow \operatorname{PA} \vdash \lnot \phi(\vec{x}, y).</math>
Line 57: Line 58:
पहला अपूर्णता प्रमेय केवल स्वयंसिद्ध प्रणालियों पर लागू होता है जो आवश्यक कोडिंग निर्माणों को पूरा करने के लिए पर्याप्त अंकगणित को परिभाषित करता है (जिसमें गोडेल नंबरिंग हिस्सा है)। क्यू के सिद्धांतों को विशेष रूप से यह सुनिश्चित करने के लिए चुना गया था कि वे इस उद्देश्य के लिए पर्याप्त मजबूत हैं। इस प्रकार पहले अपूर्णता प्रमेय के सामान्य प्रमाण का उपयोग यह दिखाने के लिए किया जा सकता है कि Q अधूरा और अनिर्णीत है। यह इंगित करता है कि पीए की अपूर्णता और अनिर्णयता को पीए के एकमात्र पहलू पर दोष नहीं दिया जा सकता है जो इसे क्यू से अलग करता है, अर्थात् गणितीय प्रेरण की स्वयंसिद्ध स्कीमा।
पहला अपूर्णता प्रमेय केवल स्वयंसिद्ध प्रणालियों पर लागू होता है जो आवश्यक कोडिंग निर्माणों को पूरा करने के लिए पर्याप्त अंकगणित को परिभाषित करता है (जिसमें गोडेल नंबरिंग हिस्सा है)। क्यू के सिद्धांतों को विशेष रूप से यह सुनिश्चित करने के लिए चुना गया था कि वे इस उद्देश्य के लिए पर्याप्त मजबूत हैं। इस प्रकार पहले अपूर्णता प्रमेय के सामान्य प्रमाण का उपयोग यह दिखाने के लिए किया जा सकता है कि Q अधूरा और अनिर्णीत है। यह इंगित करता है कि पीए की अपूर्णता और अनिर्णयता को पीए के एकमात्र पहलू पर दोष नहीं दिया जा सकता है जो इसे क्यू से अलग करता है, अर्थात् गणितीय प्रेरण की स्वयंसिद्ध स्कीमा।


जब उपरोक्त सात सिद्धांतों में से किसी को हटा दिया जाता है तो गोडेल के प्रमेय मान्य नहीं होते हैं। क्यू के ये टुकड़े अनिर्णीत बने हुए हैं, लेकिन वे अब अनिवार्य रूप से अनिर्णीत नहीं हैं: उनके पास लगातार निर्णय लेने योग्य विस्तार हैं, साथ ही साथ अरुचिकर मॉडल भी हैं (यानी, मॉडल जो मानक प्राकृतिक संख्याओं के अंतिम-विस्तार नहीं हैं)।{{Citation needed|date=November 2022}}
जब उपरोक्त सात सिद्धांतों में से किसी को हटा दिया जाता है तो गोडेल के प्रमेय मान्य नहीं होते हैं। क्यू के ये टुकड़े अनिर्णीत बने हुए हैं, किन्तु वे अब अनिवार्य रूप से अनिर्णीत नहीं हैं: उनके पास लगातार निर्णय लेने योग्य विस्तार हैं, साथ ही साथ अरुचिकर मॉडल भी हैं (यानी, मॉडल जो मानक प्राकृतिक संख्याओं के अंतिम-विस्तार नहीं हैं)।{{Citation needed|date=November 2022}}


==यह भी देखें==
==यह भी देखें==

Revision as of 14:13, 15 July 2023

गणित में, रॉबिन्सन अंकगणित प्रथम-क्रम पीनो अंकगणित (पीए) का एक सूक्ष्म रूप से स्वयंसिद्ध भाग है, जिसे पहली बार 1950 में आर. एम. रॉबिन्सन द्वारा निर्धारित किया गया था।[1] इसे सामान्यतः Q से दर्शाया जाता है। Q गणितीय प्रेरण की स्वयंसिद्ध स्कीमा के बिना लगभग PA है। Q, PA से कमज़ोर है किन्तु इसकी भाषा समान है, और दोनों सिद्धांत अपूर्ण हैं। Q, महत्वपूर्ण और रोचक है क्योंकि यह PA का एक सूक्ष्म रूप से स्वयंसिद्ध भाग है जो पुनरावर्ती रूप से अपूर्ण और अनिवार्य रूप से अनिर्णीत है।

स्वसिद्धांत

Q का पृष्ठभूमि तर्क पहचान के साथ प्रथम-क्रम तर्क है, जिसे infix '=' द्वारा दर्शाया गया है। व्यक्ति, जिन्हें प्राकृतिक संख्याएँ कहा जाता है, एक विशिष्ट सदस्य 0 के साथ N नामक समुच्चय के सदस्य हैं, जिसे शून्य कहा जाता है। N पर तीन ऑपरेशन (गणित) हैं:

बर्गेस (2005, पृष्ठ 42) में Q के लिए निम्नलिखित स्वयंसिद्ध कथन Q1-Q7 हैं (cf. प्रथम-क्रम अंकगणित के स्वयंसिद्ध भी हैं)। वे वेरिएबल जो अस्तित्वगत परिमाणक से बंधे नहीं हैं वे एक अंतर्निहित सार्वभौमिक परिमाणक से बंधे हैं।

  1. Sx ≠ 0
    • '0' किसी भी संख्या का उत्तराधिकारी नहीं है.
  3. (Sx = Sy) → x = y
    • यदि x का उत्तराधिकारी, y के उत्तराधिकारी के समान है, तो x और y समान हैं। (1) और (2) 'N' (यह '0' से घिरा अनंत सेट है) और S (यह इन्जेक्टिव फलन है जिसका फलन का डोमेन 'N' है) के बारे में गैर-तुच्छता के लिए आवश्यक न्यूनतम तथ्य प्राप्त करते हैं। (2) का व्युत्क्रम (तर्क) सर्वसमिका के गुणों से आता है।
  4. y='0' ∨ ∃x (Sx = y)
    • प्रत्येक संख्या या तो '0' है या किसी संख्या का उत्तराधिकारी है। अंकगणित में उपस्थित गणितीय प्रेरण की स्वयंसिद्ध स्कीमा 'Q' से अधिक मजबूत है जो इस स्वयंसिद्ध को प्रमेय में बदल देती है।
  5. x + '0' = x
  6. x + Sy = S(x + y)
  7. x·'0' = '0'
  8. x·Sy = (x·y) + x
    • (6) और (7) गुणन की पुनरावर्ती परिभाषा हैं।

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

में स्वयंसिद्ध Robinson (1950) (1)–(13) में हैं Mendelson (2015, pp. 202–203). रॉबिन्सन के 13 सिद्धांतों में से पहले 6 की आवश्यकता केवल तभी होती है, जब यहां के विपरीत, पृष्ठभूमि तर्क में पहचान शामिल नहीं होती है।

एन पर सामान्य सख्त कुल क्रम, (< द्वारा दर्शाया गया) से कम, नियम के माध्यम से जोड़ के संदर्भ में परिभाषित किया जा सकता है x < y ↔ ∃z (Sz + x = y). समान रूप से, हम < को आदिम के रूप में लेकर और इस नियम को आठवें स्वयंसिद्ध के रूप में जोड़कर Q का निश्चित रूढ़िवादी विस्तार प्राप्त करते हैं; इस प्रणाली को रॉबिन्सन अंकगणित आर इन कहा जाता है Boolos, Burgess & Jeffrey (2002, Sec 16.4).

Q का अलग विस्तार, जिसे हम अस्थायी रूप से Q+ कहते हैं, प्राप्त होता है यदि हम < को आदिम के रूप में लेते हैं और (अंतिम परिभाषा स्वयंसिद्ध के बजाय) निम्नलिखित तीन स्वयंसिद्धों को Q के अभिगृहीत (1)-(7) में जोड़ते हैं:

  • ¬(x < 0)
  • x < Sy ↔ (x < y ∨ x = y)
  • x < y ∨ x = y ∨ y < x

Q+ अभी भी Q का रूढ़िवादी विस्तार है, इस अर्थ में कि Q+ में सिद्ध होने वाला कोई भी सूत्र जिसमें <प्रतीक नहीं है, Q में पहले से ही सिद्ध है। (उपरोक्त तीन सिद्धांतों में से केवल पहले दो को Q में जोड़ने से Q का रूढ़िवादी विस्तार मिलता है) किस के बराबर Burgess (2005, p. 56) Q* को कॉल करता है। यह सभी देखें Burgess (2005, p. 230, fn. 24), किन्तु ध्यान दें कि उपरोक्त तीन स्वयंसिद्धों में से दूसरे को केवल स्वयंसिद्ध जोड़कर प्राप्त क्यू के शुद्ध परिभाषा विस्तार से नहीं निकाला जा सकता है x < y ↔ ∃z (Sz + x = y).)

Q के अभिगृहीतों (1)-(7) के बीच, अभिगृहीत (3) को आंतरिक अस्तित्वगत परिमाणक की आवश्यकता है। Shoenfield (1967, p. 22) स्वयंसिद्धीकरण देता है जिसमें केवल (अंतर्निहित) बाहरी सार्वभौमिक परिमाणक होते हैं, क्यू के स्वयंसिद्ध (3) को छोड़कर किन्तु उपरोक्त तीन स्वयंसिद्धों को < के साथ आदिम के रूप में जोड़कर। अर्थात्, शॉनफील्ड की प्रणाली Q+ शून्य अभिगृहीत (3) है, और Q+ से सख्ती से कमजोर है, क्योंकि अभिगृहीत (3) अन्य अभिगृहीतों से स्वतंत्र है (उदाहरण के लिए, से कम क्रमसूचक) (3) को छोड़कर सभी स्वयंसिद्धों के लिए मॉडल बनाता है जब Sv की व्याख्या v + 1 के रूप में की जाती है। शॉनफ़ील्ड की प्रणाली भी इसमें दिखाई देती है Boolos, Burgess & Jeffrey (2002, Sec 16.2), जहां इसे न्यूनतम अंकगणित कहा जाता है ('क्यू' द्वारा भी दर्शाया जाता है)। निकट से संबंधित स्वयंसिद्धीकरण, जो < के बजाय ≤ का उपयोग करता है, पाया जा सकता है Machover (1996, pp. 256–257).

मेटामैथेमेटिक्स

Q के मेटामैथमैटिक्स पर देखें Boolos, Burgess & Jeffrey (2002, chpt. 16), Tarski, Mostowski & Robinson (1953), Smullyan (1991), Mendelson (2015, pp. 202–203) और Burgess (2005, §§1.5a, 2.2). क्यू की इच्छित व्याख्या प्राकृतिक संख्याएं और उनका सामान्य अंकगणित है जिसमें जोड़ और गुणा का अपना पारंपरिक अर्थ होता है, पहचान समानता (गणित) है, Sx = x + 1, तथा 0 प्राकृत संख्या 0 (संख्या) है।

कोई भी मॉडल (संरचना) जो संभवतः स्वयंसिद्ध (3) को छोड़कर क्यू के सभी स्वयंसिद्धों को संतुष्ट करता है, उसका अद्वितीय उपमॉडल (मानक भाग) मानक प्राकृतिक संख्याओं के समरूपी होता है। (N, +, ·, S, 0). (अभिगृहीत (3) को संतुष्ट करने की आवश्यकता नहीं है; उदाहरण के लिए गैर-ऋणात्मक पूर्णांक गुणांक वाले बहुपद मॉडल बनाते हैं जो (3) को छोड़कर सभी स्वयंसिद्धों को संतुष्ट करता है।)

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

क्यू की उल्लेखनीय विशेषता गणितीय प्रेरण की स्वयंसिद्ध योजना की अनुपस्थिति है। इसलिए क्यू में प्राकृतिक संख्याओं के बारे में किसी तथ्य के प्रत्येक विशिष्ट उदाहरण को साबित करना अक्सर संभव होता है, किन्तु संबंधित सामान्य प्रमेय को नहीं। उदाहरण के लिए, Q में 5 + 7 = 7 + 5 सिद्ध है, किन्तु सामान्य कथन x + y = y + x सिद्ध नहीं है। इसी तरह, कोई यह साबित नहीं कर सकता कि Sx ≠ x। [2] क्यू का मॉडल जो कई मानक तथ्यों को विफल करता है, दो अलग-अलग नए तत्वों ए और बी को प्राकृतिक संख्याओं के मानक मॉडल से जोड़कर और सा = ए, एसबी = बी, एक्स + ए = बी और एक्स + बी = को परिभाषित करके प्राप्त किया जाता है। a सभी x के लिए, a + n = a और b + n = b यदि n मानक प्राकृतिक संख्या है, x·0 = 0 सभी x के लिए, a·n = b और b·n = a यदि n गैर- है शून्य मानक प्राकृतिक संख्या, x = a को छोड़कर सभी x के लिए x·a = a, x = b को छोड़कर सभी x के लिए x·b = b, a·a = b, और b·b = a।[3]

क्यू की व्याख्या ज़र्मेलो सेट सिद्धांत के टुकड़े में की जा सकती है | ज़र्मेलो का स्वयंसिद्ध सेट सिद्धांत, जिसमें विस्तारशीलता, खाली सेट का अस्तित्व और युग्म का स्वयंसिद्ध शामिल है। यह सिद्धांत S' में है Tarski, Mostowski & Robinson (1953, p. 34) और एसटी में Burgess (2005, pp. 90–91, 223). अधिक विवरण के लिए सामान्य समुच्चय सिद्धांत देखें।

क्यू प्रथम-क्रम सिद्धांतों की सूक्ष्म रूप से स्वयंसिद्ध सूची है | प्रथम-क्रम सिद्धांत जो कि पीनो अंकगणित (पीए) से काफी कमजोर है, और जिसके सिद्धांतों में केवल अस्तित्वगत परिमाणक होता है। फिर भी पीए की तरह यह गोडेल की अपूर्णता प्रमेयों के अर्थ में अपूर्ण और अपूर्ण है, और अनिवार्य रूप से अनिर्णीत है। Robinson (1950) ऊपर दिए गए Q अभिगृहीतों (1)-(7) को इस बात पर ध्यान देकर व्युत्पन्न किया गया है कि पीए अभिगृहीतों की क्या आवश्यकता है [4] यह साबित करने के लिए कि प्रत्येक गणना योग्य फलन पीए में प्रतिनिधित्व योग्य है।[5] गणितीय प्रेरण के पीए स्वयंसिद्ध स्कीमा के इस प्रमाण का एकमात्र उपयोग कथन को साबित करना है जो उपरोक्त स्वयंसिद्ध (3) है, और इसलिए, सभी गणना योग्य कार्य Q में दर्शाए जा सकते हैं। [6][7][8] गोडेल के दूसरे अपूर्णता प्रमेय का निष्कर्ष Q के लिए भी लागू होता है: Q का कोई भी सुसंगत पुनरावर्ती स्वयंसिद्ध विस्तार अपनी स्वयं की स्थिरता साबित नहीं कर सकता है, भले ही हम गोडेल के प्रमाणों की संख्या को निश्चित कटौती तक सीमित कर दें।[9][10][11]

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

जब उपरोक्त सात सिद्धांतों में से किसी को हटा दिया जाता है तो गोडेल के प्रमेय मान्य नहीं होते हैं। क्यू के ये टुकड़े अनिर्णीत बने हुए हैं, किन्तु वे अब अनिवार्य रूप से अनिर्णीत नहीं हैं: उनके पास लगातार निर्णय लेने योग्य विस्तार हैं, साथ ही साथ अरुचिकर मॉडल भी हैं (यानी, मॉडल जो मानक प्राकृतिक संख्याओं के अंतिम-विस्तार नहीं हैं)।[citation needed]

यह भी देखें

संदर्भ

  1. ↑ Robinson 1950.
  2. ↑ Burgess 2005, p. 56.
  3. ↑ Boolos, Burgess & Jeffrey 2002, Sec 16.4.
  4. ↑ Mendelson 2015, p. 188, Proposition 3.24.
  5. ↑ A function is said to be representable in if there is a formula such that for all
  6. ↑ Odifreddi 1989.
  7. ↑ Mendelson 2015, p. 203, Proposition 3.33.
  8. ↑ Rautenberg 2010, p. 246.
  9. ↑ Bezboruah & Shepherdson 1976.
  10. ↑ Pudlák 1985.
  11. ↑ Hájek & Pudlák 1993, p. 387.


ग्रन्थसूची

  • Bezboruah, A.; Shepherdson, John C. (June 1976). "Gödel's Second Incompleteness Theorem for Q". Journal of Symbolic Logic. 41 (2): 503–512. doi:10.2307/2272251.
  • Boolos, George; Burgess, John P.; Jeffrey, Richard (2002). Computability and Logic (4th ed.). Cambridge University Press. ISBN 0-521-00758-5.
  • Burgess, John P. (July 2005). Fixing Frege. Princeton University Press. ISBN 978-0691122311.
  • Hájek, Petr; Pudlák, Pavel (1993). Metamathematics of first-order arithmetic (2nd ed.). Springer-Verlag.
  • Jones, James P.; Shepherdson, John C. (1983). "Variants of Robinson's essentially undecidable theoryR". Archiv für mathematische Logik und Grundlagenforschung. 23: 61–64. doi:10.1007/BF02023013.
  • Lucas, John R. Conceptual Roots of Mathematics. Routledge.
  • Machover, Moshé (1996). Set Theory, Logic, and Their Limitation. Cambridge University Press.
  • Mendelson, Elliott (2015). Introduction to Mathematical Logic (6th ed.). Chapman & Hall. ISBN 9781482237726.
  • Odifreddi, Piergiorgio (1989). Classical recursion theory, Vol. 1 (The Theory of Functions and Sets of Natural Numbers). ISBN 9780444894830. {{cite book}}: |journal= ignored (help)
  • Pudlák, Pavel (June 1985). "Cuts, consistency statements and interpretations". Journal of Symbolic Logic. 50 (2): 423–441. doi:10.2307/2274231.
  • Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic (3rd ed.). New York: Springer Science+Business Media. doi:10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6..
  • Robinson, R. M. (1950). "An Essentially Undecidable Axiom System". Proceedings of the International Congress of Mathematics: 729–730.
  • Shoenfield, Joseph R. (1967). Mathematical logic. Addison Wesley. (Reprinted by Association for Symbolic Logic and A K Peters in 2000).
  • Smullyan, Raymond (1991). Gödel's Incompleteness Theorems. Oxford University Press.
  • Tarski, Alfred; Mostowski, A.; Robinson, R. M. (1953). Undecidable theories. North Holland.
  • Vaught, Robert L. (1966). "On a Theorem of Cobham Concerning Undecidable Theories". Studies in Logic and the Foundations of Mathematics. 44: 14–25. doi:10.1016/S0049-237X(09)70566-X.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=रॉबिन्सन_अंकगणित&oldid=223215’