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

"Elementary recursive arithmetic" redirects here. For the computational complexity class, see ELEMENTARY.

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

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

परिभाषा

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

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

'बाउंडेड क्वांटिफायर' फॉर्म के होते हैं ∀(x < y) और ∃(x < y) जो कि संक्षिप्ताक्षर हैं ∀ x (x < y) → ... और ∃x(x < y)∧... सामान्य तरीके से.

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

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

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

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

से अनुमान का मूल कथन Friedman (1999) है:

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

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

संबंधित सिस्टम

कई संबंधित कम्प्यूटेशनल जटिलता वर्गों में ईएफए के समान गुण हैं:

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