प्राथमिक फलन अंकगणित

"प्राथमिक पुनरावर्ती अंकगणित" redirects here. For अभिकलनात्मक सम्मिश्रता वर्ग, see प्राथमिक.

प्रमाण सिद्धांत में, गणितीय तर्क की एक शाखा, प्राथमिक फ़ंक्शन अंकगणित (ईएफए), जिसे प्राथमिक अंकगणित और घातीय फ़ंक्शन अंकगणित भी कहा जाता है। 0, 1, +, ×, x^y के सामान्य प्राथमिक गुणों के साथ अंकगणित की प्रणाली है, साथ में बंधे हुए क्वांटिफायर वाले सूत्रों के लिए गणितीय प्रेरण भी है।

ईएफए एक बहुत ही कमजोर तार्किक प्रणाली है, जिसका प्रमाण सैद्धांतिक क्रमसूचक ω³ है, लेकिन फिर भी यह सामान्य गणित को सिद्ध करने में सक्षम लगता है, जिसे पीनो अभिगृहीत प्रथम-क्रम अंकगणित की भाषा में कहा जा सकता है।

परिभाषा

ईएफए प्रथम क्रम तर्क (समानता के साथ) में एक प्रणाली है। इसकी भाषा में सम्मिलित हैं:

• दो स्थिरांक 0, 1,
• तीन बाइनरी ऑपरेशन +, ×, exp, exp(x,y) के साथ सामान्यतः x^y के रूप में लिखा जाता है।
• एक द्विआधारी संबंध प्रतीक < (यह वास्तव में आवश्यक नहीं है क्योंकि इसे अन्य परिचालनों के संदर्भ में लिखा जा सकता है और कभी-कभी छोड़ा जाता है, लेकिन बंधे हुए क्वांटिफायर को परिभाषित करने के लिए सुविधाजनक है)।

परिबद्ध परिमाणक ∀(x < y) और ∃(x < y) के रूप में होते हैं, जो सामान्य विधि से ∀ x (x < y) → ... और ∃x(x < y)∧... के संक्षिप्त रूप होते हैं।

ईएफए के अभिगृहीत हैं,

• 0, 1, +, ×, < के लिए रॉबिन्सन अंकगणित के अभिगृहीत
• घातांक के लिए अभिगृहीत: x⁰ = 1, x^y+1 = x^y × x.
• उन सूत्रों के लिए प्रेरण जिनके सभी परिमाणक परिबद्ध हैं (लेकिन जिनमें मुक्त चर हो सकते हैं)।

फ़्रीडमैन का भव्य अनुमान

हार्वे फ्रीडमैन के भव्य अनुमान का तात्पर्य है कि कई गणितीय प्रमेय, जैसे कि फ़र्मेट के अंतिम प्रमेय, को ईएफए जैसी बहुत कमजोर प्रणालियों में सिद्ध किया जा सकता है।

फ्रीडमैन (1999) के अनुमान का मूल कथन है:

"गणित के इतिहास में प्रकाशित प्रत्येक प्रमेय जिसके कथन में केवल अंतिम गणितीय वस्तुएं सम्मिलित हैं (यानी, जिसे तर्कमौलिक अंकगणितीय कथन कहते हैं) जिसको ईएफए में सिद्ध किया जा सकता है। ईएफए पीनो अंकगणित 0, 1, +, ×, ऍक्स्प के लिए सामान्य क्वांटिफायर-मुक्त सिद्धांतों के आधार पर पीनो अंकगणित का कमजोर टुकड़ा है, साथ ही भाषा में सभी सूत्रों के लिए प्रेरण की योजना के साथ जिनके सभी क्वांटिफायर बंधे हुए हैं।"

जबकि कृत्रिम अंकगणितीय कथनों का निर्माण करना सरल है जो सत्य हैं लेकिन ईएफए में सिद्ध नहीं हैं, फ्रीडमैन के अनुमान का मुद्दा यह है कि गणित में ऐसे कथनों के प्राकृतिक उदाहरण दुर्लभ प्रतीत होते हैं। कुछ प्राकृतिक उदाहरणों में तर्क से संगति कथन, रैमसे सिद्धांत से संबंधित कई कथन जैसे ज़ेमेरीडी नियमितता लेम्मा और ग्राफ लघु प्रमेय सम्मिलित हैं।

संबंधित प्रणाली

कई संबंधित अभिकलनात्मक सम्मिश्रता वर्गों में ईएफए के समान गुण हैं:

• कोई भी भाषा से बाइनरी फ़ंक्शन प्रतीक ऍक्स्प को हटा सकता है, रॉबिन्सन अंकगणित को सभी सूत्रों के लिए बाध्य क्वांटिफायर और एक स्वयंसिद्ध के साथ तथा प्रेरण के साथ ले कर, जो सामान्यतः बताता है कि घातांक हर जगह परिभाषित एक फ़ंक्शन है। यह ईएफए के समान है और इसमें समान प्रमाण सैद्धांतिक शक्ति है, लेकिन इसके साथ काम करना अधिक बोझिल है।
• दूसरे क्रम के अंकगणित के कमजोर टुकड़े हैं जिन्हें ${\mathsf {RCA}}_{0}^{*}$ कहा जाता है और ${\mathsf {WKL}}_{0}^{*}$ जो $\Pi _{2}^{0}$ वाक्यों के लिए ईएफए पर रूढ़िवादी हैं (यानी कोई भी $\Pi _{2}^{0}$ वाक्य जो डिस्प्लेस्टाइल ${\mathsf {RCA}}_{0}^{*}$ या ${\mathsf {WKL}}_{0}^{*}$ द्वारा सिद्ध हैं।) पहले से ही ईएफए विशेष रूप से, वे निरंतरता कथनों के लिए रूढ़िवादी हैं। इन अंशों का कभी-कभी विपरीत गणित में (सिम्पसन 2009) अध्ययन किया जाता है।
• प्राथमिक पुनरावर्ती अंकगणित (ईआरए) आदिम पुनरावर्ती अंकगणित (पीआरए) का एक उपप्रणाली है जिसमें पुनरावर्तन सीमित योगफल और गुणनफल तक ही सीमित है। इसमें भी ईएफए के समान डिस्प्लेस्टाइल $\Pi _{2}^{0}$ वाक्य हैं, इस अर्थ में कि जब भी ईएफए ∀x∃y P(x,y) को सिद्ध करता है, P क्वांटिफायर-मुक्त के साथ, ईआरऐ संवृत सूत्र P(x,T(x)) को सिद्ध करता है, T के साथ ईआरऐ में एक शब्द परिभाषित होता है। पीआरए के जैसे, ईआरए को पूरे प्रकार से तर्क-मुक्त विधि से परिभाषित किया जा सकता है, केवल प्रतिस्थापन और प्रेरण के नियमों और सभी प्राथमिक पुनरावर्ती कार्यों के लिए समीकरणों को परिभाषित करने के साथ, चूंकि, पीआरए के विपरीत, प्राथमिक पुनरावर्ती कार्यों को आधार कार्यों की एक सीमित संख्या की संरचना और प्रक्षेपण के अनुसार विवृत करने की विशेषता हो सकती है, और इस प्रकार केवल परिभाषित समीकरणों की एक सीमित संख्या की आवश्यकता होती है।

यह भी देखें

• Elementary function
• Grzegorczyk hierarchy
• Reverse mathematics
• Ordinal analysis
• Tarski's high school algebra problem

संदर्भ

• Avigad, Jeremy (2003), "Number theory and elementary arithmetic", Philosophia Mathematica, Series III, 11 (3): 257–284, doi:10.1093/philmat/11.3.257, ISSN 0031-8019, MR 2006194
• Friedman, Harvey (1999), grand conjectures
• Simpson, Stephen G. (2009), Subsystems of second order arithmetic, Perspectives in Logic (2nd ed.), Cambridge University Press, ISBN 978-0-521-88439-6, MR 1723993