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

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

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

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

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.