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

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

यह भी देखें

• 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