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

From Vigyanwiki
No edit summary
No edit summary
Line 2: Line 2:
{{redirect|प्राथमिक पुनरावर्ती अंकगणित|अभिकलनात्मक सम्मिश्रता वर्ग|प्राथमिक}}
{{redirect|प्राथमिक पुनरावर्ती अंकगणित|अभिकलनात्मक सम्मिश्रता वर्ग|प्राथमिक}}


[[प्रमाण सिद्धांत]] में, [[गणितीय तर्क]] की एक शाखा, प्राथमिक फ़ंक्शन अंकगणित (ईएफए), जिसे प्राथमिक अंकगणित और घातीय फ़ंक्शन अंकगणित भी कहा जाता है,<ref>C. Smoryński, "Nonstandard Models and Related Developments" (p. 217). From ''Harvey Friedman's Research on the Foundations of Mathematics'' (1985), Studies in Logic and the Foundations of Mathematics vol. 117.</ref> 0, 1, +, ×, x<sup>y</sup> के सामान्य प्राथमिक गुणों के साथ अंकगणित की प्रणाली है, साथ में बंधे हुए क्वांटिफायर वाले सूत्रों के लिए [[गणितीय प्रेरण]] भी है।
[[प्रमाण सिद्धांत]] में, [[गणितीय तर्क]] की एक शाखा, प्राथमिक फ़ंक्शन अंकगणित (ईएफए), जिसे प्राथमिक अंकगणित और घातीय फ़ंक्शन अंकगणित भी कहा जाता है।<ref>C. Smoryński, "Nonstandard Models and Related Developments" (p. 217). From ''Harvey Friedman's Research on the Foundations of Mathematics'' (1985), Studies in Logic and the Foundations of Mathematics vol. 117.</ref> 0, 1, +, ×, x<sup>y</sup> के सामान्य प्राथमिक गुणों के साथ अंकगणित की प्रणाली है, साथ में बंधे हुए क्वांटिफायर वाले सूत्रों के लिए [[गणितीय प्रेरण]] भी है।


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


==परिभाषा==
==परिभाषा==


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


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


ईएफए के अभिगृहीत हैं,
ईएफए के अभिगृहीत हैं,
Line 26: Line 26:
[[फ्रीडमैन (1999)]] के अनुमान का मूल कथन है:
[[फ्रीडमैन (1999)]] के अनुमान का मूल कथन है:


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


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


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


कई संबंधित कम्प्यूटेशनल जटिलता वर्गों में ईएफए के समान गुण हैं:
कई संबंधित अभिकलनात्मक सम्मिश्रता वर्गों में ईएफए के समान गुण हैं:
* कोई भी भाषा से बाइनरी फ़ंक्शन प्रतीक ऍक्स्प को हटा सकता है, रॉबिन्सन अंकगणित को सभी सूत्रों के लिए बाध्य क्वांटिफायर और एक स्वयंसिद्ध के साथ प्रेरण के साथ ले कर, जो मोटे तौर पर बताता है कि घातांक हर जगह परिभाषित एक फ़ंक्शन है। यह ईएफए के समान है और इसमें समान प्रमाण सैद्धांतिक शक्ति है, लेकिन इसके साथ काम करना अधिक बोझिल है।
* कोई भी भाषा से बाइनरी फ़ंक्शन प्रतीक ऍक्स्प को हटा सकता है, रॉबिन्सन अंकगणित को सभी सूत्रों के लिए बाध्य क्वांटिफायर और एक स्वयंसिद्ध के साथ तथा प्रेरण के साथ ले कर, जो सामान्यतः बताता है कि घातांक हर जगह परिभाषित एक फ़ंक्शन है। यह ईएफए के समान है और इसमें समान प्रमाण सैद्धांतिक शक्ति है, लेकिन इसके साथ काम करना अधिक बोझिल है।
*दूसरे क्रम के अंकगणित के कमजोर टुकड़े हैं जिन्हें <math>\mathsf{RCA}_0^*</math> कहा जाता है और <math>\mathsf{WKL}_0^*</math> जो <math>\Pi_2^0</math> वाक्यों के लिए EFA पर रूढ़िवादी हैं (यानी कोई भी <math>\Pi_2^0</math> वाक्य जो डिस्प्लेस्टाइल <math>\mathsf{RCA}_0^*</math> या <math>\mathsf{WKL}_0^*</math> द्वारा सिद्ध हैं।)<ref>S. G. Simpson, R. L. Smith, "[https://www.sciencedirect.com/science/article/pii/0168007286900746 Factorization of polynomials and <math>\Sigma_1^0</math>-induction]" (1986). Annals of Pure and Applied Logic, vol. 31 (p.305)</ref> पहले से ही ईएफए  विशेष रूप से, वे निरंतरता कथनों के लिए रूढ़िवादी हैं। इन अंशों का कभी-कभी विपरीत गणित में ([[सिम्पसन 2009]]) अध्ययन किया जाता है।
*दूसरे क्रम के अंकगणित के कमजोर टुकड़े हैं जिन्हें <math>\mathsf{RCA}_0^*</math> कहा जाता है और <math>\mathsf{WKL}_0^*</math> जो <math>\Pi_2^0</math> वाक्यों के लिए ईएफए पर रूढ़िवादी हैं (यानी कोई भी <math>\Pi_2^0</math> वाक्य जो डिस्प्लेस्टाइल <math>\mathsf{RCA}_0^*</math> या <math>\mathsf{WKL}_0^*</math> द्वारा सिद्ध हैं।)<ref>S. G. Simpson, R. L. Smith, "[https://www.sciencedirect.com/science/article/pii/0168007286900746 Factorization of polynomials and <math>\Sigma_1^0</math>-induction]" (1986). Annals of Pure and Applied Logic, vol. 31 (p.305)</ref> पहले से ही ईएफए  विशेष रूप से, वे निरंतरता कथनों के लिए रूढ़िवादी हैं। इन अंशों का कभी-कभी विपरीत गणित में ([[सिम्पसन 2009]]) अध्ययन किया जाता है।
*प्राथमिक पुनरावर्ती अंकगणित (ईआरए) [[आदिम पुनरावर्ती अंकगणित]] (पीआरए) का एक उपप्रणाली है जिसमें पुनरावर्तन सीमित रकम और उत्पादों तक ही सीमित है। इसमें भी EFA के समान डिस्प्लेस्टाइल <math>\Pi_2^0</math> वाक्य हैं, इस अर्थ में कि जब भी EFA ∀x∃y P(x,y) को साबित करता है, P क्वांटिफायर-मुक्त के साथ, ERA ओपन फॉर्मूला P(x,T(x)) को साबित करता है, T के साथ ERA में एक शब्द परिभाषित होता है। पीआरए की तरह, ईआरए को पूरी तरह से तर्क-मुक्त तरीके से परिभाषित किया जा सकता है, केवल प्रतिस्थापन और प्रेरण के नियमों और सभी प्राथमिक पुनरावर्ती कार्यों के लिए समीकरणों को परिभाषित करने के साथ, हालांकि, पीआरए के विपरीत, प्राथमिक पुनरावर्ती कार्यों को आधार कार्यों की एक सीमित संख्या की संरचना और प्रक्षेपण के तहत बंद करने की विशेषता हो सकती है, और इस प्रकार केवल परिभाषित समीकरणों की एक सीमित संख्या की आवश्यकता होती है।
*प्राथमिक पुनरावर्ती अंकगणित (ईआरए) [[आदिम पुनरावर्ती अंकगणित]] (पीआरए) का एक उपप्रणाली है जिसमें पुनरावर्तन सीमित योगफल और गुणनफल तक ही सीमित है। इसमें भी ईएफए के समान डिस्प्लेस्टाइल <math>\Pi_2^0</math> वाक्य हैं, इस अर्थ में कि जब भी ईएफए ∀x∃y P(x,y) को सिद्ध करता है, P क्वांटिफायर-मुक्त के साथ, ईआरऐ संवृत सूत्र P(x,T(x)) को सिद्ध करता है, T के साथ ईआरऐ में एक शब्द परिभाषित होता है। पीआरए के जैसे, ईआरए को पूरे प्रकार से तर्क-मुक्त विधि से परिभाषित किया जा सकता है, केवल प्रतिस्थापन और प्रेरण के नियमों और सभी प्राथमिक पुनरावर्ती कार्यों के लिए समीकरणों को परिभाषित करने के साथ, चूंकि, पीआरए के विपरीत, प्राथमिक पुनरावर्ती कार्यों को आधार कार्यों की एक सीमित संख्या की संरचना और प्रक्षेपण के अनुसार विवृत करने की विशेषता हो सकती है, और इस प्रकार केवल परिभाषित समीकरणों की एक सीमित संख्या की आवश्यकता होती है।


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

Revision as of 22:24, 22 July 2023

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

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

परिभाषा

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

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

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

  1. C. Smoryński, "Nonstandard Models and Related Developments" (p. 217). From Harvey Friedman's Research on the Foundations of Mathematics (1985), Studies in Logic and the Foundations of Mathematics vol. 117.
  2. S. G. Simpson, R. L. Smith, "Factorization of polynomials and -induction" (1986). Annals of Pure and Applied Logic, vol. 31 (p.305)
  • 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