अभाज्य पुनरावर्ती अंकगणित

अभाज्य पुनरावर्ती अंकगणित (पीआरए) प्राकृतिक संख्याओं का एक परिमाणीकरण (तर्क)-मुक्त औपचारिकीकरण है। यह सबसे पहले नॉर्वेजियन गणितज्ञ स्कोलेम (1923) द्वारा प्रस्तावित किया गया था, अंकगणित की नींव की उनकी परिमितवादी अवधारणा को औपचारिक रूप देने के रूप में, और यह व्यापक रूप से सहमत है कि पीआरए के सभी तर्क परिमितवादी हैं। कई लोग यह भी मानते हैं कि सभी परिमितवाद को पीआरए द्वारा पकड़ लिया गया है, किन्तु दूसरों का मानना ​​है कि परिमितवाद को अभाज्य पुनरावर्तन से अधिक, ε₀ तक, पुनरावर्तन के रूपों तक बढ़ाया जा सकता है, जो पीनो अंकगणित का प्रमाण-सैद्धांतिक क्रमसूचक है। पीआरए का प्रमाण सिद्धांतिक क्रमसूचक ω^ω है, जहां ω सबसे छोटी अनंत संख्या है। पीआरए को कभी-कभी स्कोलेम अंकगणित भी कहा जाता है।

पीआरए की भाषा प्राकृतिक संख्याओं और किसी भी अभाज्य पुनरावर्ती फलन से जुड़े अंकगणितीय प्रस्तावों को व्यक्त कर सकती है, जिसमें जोड़, गुणा और घातांक के संचालन सम्मिलित हैं। पीआरए प्राकृतिक संख्याओं के क्षेत्र में स्पष्ट रूप से मात्रा निर्धारित नहीं कर सकता है। पीआरए को अधिकांश प्रमाण सिद्धांत के लिए मूल मेटामैथमैटिकल औपचारिक प्रणाली के रूप में लिया जाता है, विशेष रूप से स्थिरता प्रमाणों के लिए जैसे कि जेंटज़ेन के प्रथम-क्रम अंकगणित की स्थिरता प्रमाण के लिए।

भाषा और स्वयंसिद्ध

PRA की भाषा में सम्मिलित हैं:

• चर x, y, z,.... की गणनीय अनंत संख्या
• प्रस्तावित कलन तार्किक संयोजक;
• समानता प्रतीक =, स्थिर प्रतीक 0, और अभाज्य पुनरावर्ती फलन प्रतीक एस (अर्थात् जोड़ें);
• प्रत्येक अभाज्य पुनरावर्ती फलन के लिए प्रतीक।

PRA के तार्किक अभिगृहीत हैं:

• प्रस्तावित कलन की तनातनी (तर्क);
• समतुल्य संबंध के रूप में समानता (गणित) का सामान्य स्वयंसिद्धीकरण।

पीआरए के तार्किक नियम मूड सेट करना और प्रथम-क्रम तर्क#अनुमान के नियम हैं।
गैर-तार्किक स्वयंसिद्ध बातें, सबसे पहले हैं:

• $S(x)\neq 0$;
• $S(x)=S(y)\to x=y,$

कहाँ $x\neq y$ सदैव के निषेध को दर्शाता है $x=y$ ताकि, उदाहरण के लिए, $S(0)=0$ अस्वीकृत प्रस्ताव है.

इसके अलावा, प्रत्येक अभाज्य पुनरावर्ती फलन के लिए पुनरावर्ती परिभाषित समीकरणों को इच्छानुसार स्वयंसिद्धों के रूप में अपनाया जा सकता है। उदाहरण के लिए, अभाज्य पुनरावर्ती कार्यों का सबसे आम लक्षण वर्णन 0 स्थिरांक और उत्तराधिकारी फलन प्रक्षेपण, संरचना और अभाज्य पुनरावर्तन के तहत बंद है। तो (n+1)-स्थान फलन f के लिए, जिसे n-स्थान बेस फलन g और (n+2)-स्थान पुनरावृत्ति फलन h पर अभाज्य रिकर्सन द्वारा परिभाषित किया गया है, वहां परिभाषित समीकरण होंगे:

• $f(0,y_{1},\ldots ,y_{n})=g(y_{1},\ldots ,y_{n})$
• $f(S(x),y_{1},\ldots ,y_{n})=h(x,f(x,y_{1},\ldots ,y_{n}),y_{1},\ldots ,y_{n})$

विशेष रूप से:

• $x+0=x\$
• $x+S(y)=S(x+y)\$
• $x\cdot 0=0\$
• $x\cdot S(y)=x\cdot y+x\$
• ... और इसी तरह।

पीआरए प्रथम-क्रम अंकगणित के लिए गणितीय प्रेरण को (क्वांटिफ़ायर-मुक्त) प्रेरण के नियम से प्रतिस्थापित करता है:

• से $\varphi (0)$ और $\varphi (x)\to \varphi (S(x))$, निष्कर्ष निकालना $\varphi (y)$, किसी भी विधेय के लिए $\varphi .$

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

तर्क-मुक्त कलन

पीआरए को इस तरह से औपचारिक बनाना संभव है कि इसमें कोई तार्किक संयोजकता न हो - पीआरए का वाक्य सिर्फ दो शब्दों के बीच समीकरण है। इस सेटिंग में शब्द शून्य या अधिक चर का अभाज्य पुनरावर्ती कार्य है। Curry (1941) ने पहली ऐसी व्यवस्था दी। करी की प्रणाली में प्रेरण का नियम असामान्य था। द्वारा बाद में परिशोधन दिया गया Goodstein (1954). गुडस्टीन की प्रणाली में प्रेरण के अनुमान का नियम है:

${F(0)=G(0)\quad F(S(x))=H(x,F(x))\quad G(S(x))=H(x,G(x)) \over F(x)=G(x)}.$

यहां x वैरिएबल है, S उत्तराधिकारी ऑपरेशन है, और F, G, और H कोई अभाज्य पुनरावर्ती फलन हैं जिनमें दिखाए गए पैरामीटर के अलावा अन्य पैरामीटर भी हो सकते हैं। गुडस्टीन की प्रणाली के एकमात्र अन्य अनुमान नियम प्रतिस्थापन नियम हैं, जो इस प्रकार हैं:

${F(x)=G(x) \over F(A)=G(A)}\qquad {A=B \over F(A)=F(B)}\qquad {A=B\quad A=C \over B=C}.$

यहां ए, बी, और सी कोई भी पद हैं (शून्य या अधिक चर के अभाज्य पुनरावर्ती कार्य)। अंत में, किसी भी अभाज्य पुनरावर्ती कार्यों के लिए संबंधित परिभाषित समीकरणों के साथ प्रतीक हैं, जैसा कि ऊपर स्कोलेम की प्रणाली में है।

इस तरह प्रस्तावात्मक गणना को पूरी तरह से खारिज किया जा सकता है। तार्किक ऑपरेटरों को पूरी तरह से अंकगणितीय रूप से व्यक्त किया जा सकता है, उदाहरण के लिए, दो संख्याओं के अंतर का पूर्ण मूल्य अभाज्य पुनरावृत्ति द्वारा परिभाषित किया जा सकता है:

${\begin{aligned}P(0)=0\quad &\quad P(S(x))=x\\x{\dot {-}}0=x\quad &\quad x\mathrel {\dot {-}} S(y)=P(x\mathrel {\dot {-}} y)\\|x-y|=&(x\mathrel {\dot {-}} y)+(y\mathrel {\dot {-}} x).\\\end{aligned}}$

इस प्रकार, समीकरण x=y और $|x-y|=0$ समतुल्य हैं. इसलिए समीकरण $|x-y|+|u-v|=0$ और $|x-y|\cdot |u-v|=0$ समीकरण x=y और u=v के क्रमशः तार्किक संयोजन और वियोजन को व्यक्त करें। निषेध को इस प्रकार व्यक्त किया जा सकता है $1{\dot {-}}|x-y|=0$.

यह भी देखें

• प्राथमिक पुनरावर्ती अंकगणित
• परिमित-मूल्यवान तर्क
• हेटिंग अंकगणित
• पीनो अंकगणित
• अभाज्य पुनरावर्ती कार्य
• रॉबिन्सन अंकगणित
• दूसरे क्रम का अंकगणित
• स्कोलेम अंकगणित

संदर्भ

• Curry, Haskell B. (1941). "A formalization of recursive arithmetic". American Journal of Mathematics. 63: 263–282. doi:10.2307/2371522. MR 0004207.

• Goodstein, R. L. (1954). "Logic-free formalisations of recursive arithmetic". Mathematica Scandinavica. 2: 247–261. MR 0087614.

• van Heijenoort, Jean (1967). From Frege to Gödel. A source book in mathematical logic, 1879–1931. Cambridge, Mass.: Harvard University Press. pp. 302–333. MR 0209111.

• Kreisel, Georg (1960). "Ordinal logics and the characterization of informal concepts of proof" (PDF). Proceedings of the International Congress of Mathematicians, 1958. New York: Cambridge University Press. pp. 289–299. MR 0124194.

• Skolem, Thoralf (1923). "Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich" [The foundations of elementary arithmetic established by means of the recursive mode of thought without the use of apparent variables ranging over infinite domains] (PDF). Skrifter utgit av Videnskapsselskapet i Kristiania. I, Matematisk-naturvidenskabelig klasse (in German). 6: 1–38.{{cite journal}}: CS1 maint: unrecognized language (link)

• Tait, W.W. (1981). "Finitism". The Journal of Philosophy. 78: 524–546. doi:10.2307/2026089.

Additional reading

• Feferman, Solomon (1993). "What rests on what? The proof-theoretic analysis of mathematics" (PDF). Philosophy of Mathematics. J. Czermak (ed.): 1–147.

• Rose, H. E. (1961). "On the consistency and undecidability of recursive arithmetic". Zeitschrift für Mathematische Logik und Grundlagen der Mathematik. 7: 124–135. doi:10.1002/malq.19610070707. MR 0140413.