रॉबिन्सन अंकगणित

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

स्वसिद्धांत

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

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

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

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

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

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

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

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 का रूढ़िवादी विस्तार मिलता है) यह बर्गेस (2005, p. 56) जिसे Q* कहता है, उसके समतुल्य है। बर्गेस (2005, p. 230, fn. 24) भी देखें, किन्तु ध्यान दें कि उपरोक्त तीन सिद्धांतों में से दूसरे को "शुद्ध परिभाषा" से नहीं निकाला जा सकता है। Q का विस्तार" केवल स्वयंसिद्ध x < y ↔ ∃z (Sz + x = y) जोड़कर प्राप्त किया गया है।

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

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

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

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

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

Q की एक उल्लेखनीय विशेषता गणितीय प्रेरण की स्वयंसिद्ध योजना की अनुपस्थिति है। इसलिए Q में प्राकृतिक संख्याओं के बारे में किसी तथ्य के प्रत्येक विशिष्ट उदाहरण को सिद्ध करना अधिकांश संभव होता है, किन्तु संबंधित सामान्य प्रमेय को नहीं। उदाहरण के लिए, Q में 5 + 7 = 7 + 5 सिद्ध है, किन्तु सामान्य कथन x + y = y + x सिद्ध नहीं है। इसी प्रकार, कोई यह सिद्ध नहीं कर सकता कि Sx ≠ x हैं। Q का मॉडल जो कई मानक तथ्यों को विफल करता है, दो अलग-अलग नए तत्वों a और b को प्राकृतिक संख्याओं के मानक मॉडल से जोड़कर और Sa = a, Sb = b, x + a = b और x + b = a को परिभाषित करके प्राप्त किया जाता है। 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 हैं।

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

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

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

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

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

यह भी देखें

• जेंटज़ेन की संगति प्रमाण
• गोडेल की अपूर्णता प्रमेय
• प्रथम-क्रम सिद्धांतों की सूची
• पीनो स्वयंसिद्ध
• प्रेस्बर्गर अंकगणित
• स्कोलेम अंकगणित
• दूसरे क्रम का अंकगणित
• प्राकृतिक संख्याओं की सेट-सैद्धांतिक परिभाषा
• सामान्य समुच्चय सिद्धांत

ग्रन्थसूची

• 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.