द्वितीय-क्रम अंकगणित

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

दूसरे क्रम के अंकगणित का अग्रदूत जिसमें तीसरे क्रम के पैरामीटर सम्मिलित हैं, डेविड हिल्बर्ट और पॉल बर्नीस ने अपनी पुस्तक ग्रुंडलाजेन डेर मैथेमेटिक में प्रस्तुत किया था। दूसरे क्रम के अंकगणित के मानक स्वयंसिद्धीकरण को Z₂ द्वारा दर्शाया गया है।

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

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

दूसरे क्रम के अंकगणित का एक उपप्रणाली दूसरे क्रम के अंकगणित की भाषा में एक सिद्धांत है, जिसका प्रत्येक स्वयंसिद्ध पूर्ण दूसरे क्रम के अंकगणित (Z₂) का एक प्रमेय है। ऐसे उपप्रणालियाँ गणित को रिवर्स के लिए आवश्यक हैं, एक शोध कार्यक्रम यह जांच करता है, कि भिन्न-भिन्न ताकत के कुछ अस्थिर उपप्रणालियों में आधारित गणित का कितना भाग प्राप्त किया जा सकता है। इन अस्थिर उपप्रणालियों में अधिकांश मुख्य गणित को औपचारिक रूप दिया जा सकता है, जिनमें से कुछ को नीचे परिभाषित किया गया है। रिवर्स गणित यह भी स्पष्ट करता है, कि आधारित गणित किस सीमा और विधि से गैर-रचनात्मक है।

परिभाषा

सिंटेक्स

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

इंडिविजुअल पद स्थिरांक 0, यूनरी फलन एस (उत्तराधिकारी फलन ), और बाइनरी ऑपरेशन + और से बनते हैं, . (जोड़ और गुणा) उत्तराधिकारी फलन अपने इनपुट में 1 जोड़ता है। रिलेशन = (समानता) और < (प्राकृतिक संख्याओं की तुलना) दो इंडिविजुअल से रिलेशन हैं, जबकि रिलेशन ∈ (सदस्यता) एक इंडिविजुअल और एक समुच्चय (या वर्ग) से रिलेशन है। ${\mathcal {L}}=\{0,S,+,\cdot ,=,<,\in \}$ इस प्रकार अंकन में दूसरे क्रम के अंकगणित की भाषा हस्ताक्षर द्वारा दी जाती है।

उदाहरण के लिए, $\forall n(n\in X\rightarrow Sn\in X)$ दूसरे क्रम के अंकगणित का एक सुव्यवस्थित सूत्र है, जो अंकगणितीय है, इसमें एक मुक्त समुच्चय चर $\exists X\forall n(n\in X\leftrightarrow n<SSSSSS0\cdot SSSSSSS0)$

एक सुगठित सूत्र है, जो अंकगणितीय नहीं है, जिसमें एक बाध्य समुच्चय चर X और एक बाध्य इंडिविजुअल चर n है।

शब्दार्थ

क्वांटिफायर की कई भिन्न-भिन्न व्याख्याएँ संभव हैं। यदि दूसरे क्रम के तर्क के पूर्ण शब्दार्थ का उपयोग करके दूसरे क्रम के अंकगणित का अध्ययन किया जाता है, तो समुच्चय क्वांटिफायर इंडिविजुअल चर की सीमा के सभी सब समुच्चय होते हैं। यदि दूसरे क्रम के अंकगणित को प्रथम-क्रम तर्क (हेनकिन) के शब्दार्थ का उपयोग करके औपचारिक रूप दिया जाता है, तो किसी भी मॉडल में समुच्चय चर के लिए एक डोमेन सम्मिलित करना होता है, और यह डोमेन इंडिविजुअल चर के डोमेन के पूर्ण पॉवरसमुच्चय का (शापिरो 1991, पीपी 74-75) एक उचित उपसमुच्चय हो सकता है।

अभिगृहीत

बेसिक

निम्नलिखित स्वयंसिद्धों को मूल स्वयंसिद्धों या कभी-कभी रॉबिन्सन स्वयंसिद्धों के रूप में जाना जाता है। परिणामी प्रथम-क्रम सिद्धांत, जिसे रॉबिन्सन अंकगणित के रूप में जाना जाता है, अनिवार्य रूप से प्रेरण के बिना पीनो अंकगणित है। परिमाणित चरों के लिए प्रवचन का क्षेत्र प्राकृतिक संख्याएँ हैं, जिन्हें सामूहिक रूप से N द्वारा दर्शाया जाता है, और विशिष्ट सदस्य भी सम्मिलित करना हैं 0, जिसे "शून्य" कहा जाता है।

आदिम फलन एकात्मक उत्तराधिकारी फलन हैं, जो उपसर्ग द्वारा निरूपित होते हैं, एस, और दो बाइनरी ऑपरेशन, जोड़ और गुणा, इन्फ़िक्स ऑपरेटर "+" और द्वारा दर्शाया गया है। . क्रमशः ऑर्डर नामक एक आदिम बाइनरी रिलेशन भी है, जिसे इन्फ़िक्स ऑपरेटर "<" द्वारा दर्शाया गया है।

उत्तराधिकारी फलन और शून्य को नियंत्रित करने वाले सिद्धांत:

1. $\forall m[Sm=0\rightarrow \bot ].$ (प्राकृतिक संख्या का उत्तराधिकारी कभी शून्य नहीं होता है।)

2. $\forall m\forall n[Sm=Sn\rightarrow m=n].$ (उत्तराधिकारी फलन इंजेक्टिव है।)

3. $\forall n[0=n\lor \exists m[Sm=n]].$ (प्रत्येक प्राकृतिक संख्या शून्य या उत्तराधिकारी होती है।)

जोड़ पुनरावर्ती रूप से परिभाषित:

4. $\forall m[m+0=m]$

5. $\forall m\forall n[m+Sn=S(m+n)]$

गुणन को पुनरावर्ती रूप से परिभाषित किया गया:

6. $\forall m[m\cdot 0=0]$

7. $\forall m\forall n[m\cdot Sn=(m\cdot n)+m]$

आदेश रिलेशन "<" को नियंत्रित करने वाले अभिगृहीत:

8. $\forall m[m<0\rightarrow \bot ].$ (कोई भी प्राकृत संख्या शून्य से छोटी नहीं होती है।)

9. $\forall n\forall m[m<Sn\leftrightarrow (m<n\lor m=n)]$

10. $\forall n[0=n\lor 0<n].$ (प्रत्येक प्राकृतिक संख्या शून्य या शून्य से बड़ी होती है।)

11 $\forall m\forall n[(Sm<n\lor Sm=n)\leftrightarrow m<n]$

ये सभी स्वयंसिद्ध कथन प्रथम-क्रम के कथन हैं। अर्थात्, सभी चर प्राकृतिक संख्याओं पर आधारित में होते हैं, न कि उनके समुच्चयों के, यह तथ्य उनके अंकगणितीय होने से भी अधिक स्ट्रोंगर है। इसके अतिरिक्त, अभिगृहीत 3 में मात्र एक अस्तित्वगत परिमाणक है। अभिगृहीत 1 और 2, प्रेरण के एक अभिगृहीत स्कीमा के साथ मिलकर एन की सामान्य पीनो-डेडेकाइंड परिभाषा बनाते हैं। इन अभिगृहीतों में प्रेरण के किसी भी प्रकार के अभिगृहीत स्कीमा को जोड़ने से अभिगृहीत 3, 10, और 11 निरर्थक हो जाते हैं।

प्रेरण और समझ स्कीमा

यदि φ(n) एक मुक्त इंडिविजुअल चर n और संभवतः अन्य मुक्त इंडिविजुअल या समुच्चय चर (लिखित m₁,...,m_k and X₁,...,X_l) के साथ दूसरे क्रम के अंकगणित का एक सूत्र है, तो φ के लिए प्रेरण स्वयंसिद्ध करना होता है।

$\forall m_{1}\dots m_{k}\forall X_{1}\dots X_{l}((\varphi (0)\land \forall n(\varphi (n)\rightarrow \varphi (Sn)))\rightarrow \forall n\varphi (n))$

(पूर्ण) दूसरे क्रम की प्रेरण योजना में सभी दूसरे क्रम के सूत्रों पर, इस स्वयंसिद्ध के सभी उदाहरण सम्मिलित करना हैं।

प्रेरण योजना का एक विशेष रूप से महत्वपूर्ण उदाहरण है, जब φ सूत्र है $n\in X$ इस तथ्य को व्यक्त करता है, कि n, X का एक सदस्य है (X एक मुक्त समुच्चय चर है)। इस स्थितियाँ में, φ के लिए प्रेरण स्वयंसिद्ध करना होता है।

$\forall X((0\in X\land \forall n(n\in X\rightarrow Sn\in X))\rightarrow \forall n(n\in X))$

इस वाक्य को द्वितीय-क्रम प्रेरण स्वयंसिद्ध कहा जाता है।

यदि φ(n) एक मुक्त चर n और संभवतः अन्य मुक्त चर के साथ एक सूत्र है, लेकिन चर Z नहीं है, तो φ के लिए समझ स्वयंसिद्ध सूत्र है।

$\exists Z\forall n(n\in Z\leftrightarrow \varphi (n))$

यह स्वयंसिद्ध समुच्चय बनाना संभव बनाता है, $Z=\{n|\varphi (n)\}$ φ(n) को संतुष्ट करने वाली प्राकृतिक संख्याओं का एक तकनीकी प्रतिबंध है, कि सूत्र φ में चर Z सम्मिलित करना नहीं हो सकता है, अन्यथा सूत्र के लिए $n\not \in Z$ समझ के सिद्धांत की ओर ले जाएगा

$\exists Z\forall n(n\in Z\leftrightarrow n\not \in Z)$,

जो असंगत है, इस सम्मेलन को इस लेख के शेष भाग में माना गया है।

पूरा सिस्टम

दूसरे क्रम के अंकगणित के औपचारिक सिद्धांत (दूसरे क्रम के अंकगणित की भाषा में) में मूल स्वयंसिद्ध, प्रत्येक सूत्र φ (अंकगणित या अन्यथा) के लिए समझ स्वयंसिद्ध और दूसरे क्रम प्रेरण स्वयंसिद्ध सम्मिलित करना हैं। इस सिद्धांत को नीचे परिभाषित इसकी उपप्रणालियों से भिन्न करने के लिए कभी-कभी पूर्ण द्वितीय-क्रम अंकगणित भी कहा जाता है। चूँकि पूर्ण दूसरे क्रम के शब्दार्थ का अर्थ यह है, कि हर संभव समुच्चय उपस्थित है, जब पूर्ण दूसरे क्रम के शब्दार्थ को नियोजित किया जाता है, तो समझ के सिद्धांतों को निगमनात्मक प्रणाली का भाग माना जा सकता है (शापिरो 1991, पृष्ठ 66)।

मॉडल

यह खंड प्रथम-क्रम के शब्दार्थ के साथ दूसरे-क्रम के अंकगणित का वर्णन करता है। इस प्रकार एक मॉडल ${\mathcal {M}}$ दूसरे क्रम की अंकगणित की भाषा में एक समुच्चय एम (जो भिन्न-भिन्न चर की श्रेणी बनाता है) के साथ एक स्थिरांक 0 (एम का एक एलिमेंट), एम से एम तक एक फलन एस, दो बाइनरी ऑपरेशन + और · एम पर, एक बाइनरी रिलेशन < पर एम, और एम के उपसमुच्चय का एक संग्रह डी सम्मिलित करना होता है, जो समुच्चय चर की सीमा है। डी को छोड़ने से प्रथम-क्रम अंकगणित की भाषा का एक मॉडल तैयार होता है।

जब डी, मॉडल M का पूर्ण पावरसमुच्चय है, ${\mathcal {M}}$ को पूर्ण मॉडल कहा जाता है। पूर्ण दूसरे क्रम के शब्दार्थ का उपयोग दूसरे क्रम के अंकगणित के मॉडल को पूर्ण मॉडल तक सीमित करने के समतुल्य है। वास्तव में, दूसरे क्रम के अंकगणित के सिद्धांतों में मात्र एक पूर्ण मॉडल होता है। यह इस तथ्य से पता चलता है, कि दूसरे क्रम के प्रेरण स्वयंसिद्ध वाले पीनो सिद्धांतों में दूसरे क्रम के शब्दार्थ के अनुसार मात्र एक मॉडल होता है।

परिभाषित कार्य

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

अधिक प्रकार के मॉडल

जब दूसरे क्रम के अंकगणित की भाषा के एक मॉडल में कुछ गुण होते हैं, तो इसे इन अन्य नामों से भी कहा जा सकता है:

• जब एम अपने सामान्य संचालन के साथ प्राकृतिक संख्याओं का सामान्य समुच्चय है, ${\mathcal {M}}$ ω-मॉडल कहा जाता है। इस स्थितियाँ में, मॉडल की पहचान डी से की जा सकती है, जो प्राकृतिक के समुच्चय का संग्रह है, क्योंकि यह समुच्चय पूरी प्रकार से ω-मॉडल निर्धारित करने के लिए पर्याप्त है। अद्वितीय पूर्ण ω-मॉडल, जो अपनी सामान्य संरचना और उसके सभी उपसमुच्चयों के साथ प्राकृतिक संख्याओं का सामान्य समुच्चय है, दूसरे क्रम के अंकगणित का इच्छित या मानक मॉडल कहा जाता है।
• एक प्रतिमा ${\mathcal {M}}$ दूसरे क्रम के अंकगणित की भाषा को β-मॉडल कहा जाता है, यदि ${\mathcal {M}}\prec _{1}^{1}{\mathcal {P}}(\omega )$ अर्थात Σ¹₁-कथन पैरामीटर के साथ ${\mathcal {M}}$ जो इससे संतुष्ट हैं, ${\mathcal {M}}$ पूर्ण मॉडल से संतुष्ट लोगों के समान हैं। कुछ धारणाएँ जो β-मॉडल के रिलेशन में निरपेक्ष हैं, उनमें सम्मिलित करना हैं, $A\subseteq \omega \times \omega$ एक अच्छे क्रम को एन्कोड करता है, और $A\subseteq \omega \times \omega$ एक ट्री है। उपरोक्त परिणाम को βn-मॉडल की अवधारणा तक विस्तारित किया गया है, $n\in \mathbb {N}$ जिसकी परिभाषा उपरोक्त के समान ही है, $\prec _{1}^{1}$ द्वारा प्रतिस्थापित किया गया है, $\prec _{n}^{1}$ अर्थात $\Sigma _{1}^{1}$ द्वारा प्रतिस्थापित किया गया है, $\Sigma _{n}^{1}$ इस परिभाषा का उपयोग करना β₀-मॉडल ω-मॉडल के समान हैं।

उपप्रणाली

Main article: रिवर्स गणित

दूसरे क्रम के अंकगणित के कई नामित उप-प्रणालियां हैं।

सबसिस्टम के नाम में एक सबस्क्रिप्ट 0 इंगित करता है, कि इसमें पूर्ण द्वितीय-क्रम प्रेरण योजना (फ़्रीडमैन 1976) का मात्र एक प्रतिबंधित भाग सम्मिलित करना है। इस प्रकार का प्रतिबंध सिस्टम की प्रमाण-सैद्धांतिक ताकत को अधिक कम कर देता है। उदाहरण के लिए, नीचे वर्णित प्रणाली RCA 0 पीनो अंकगणित के समतुल्य है। रिलेशन सिद्धांत एसीए, जिसमें ए.सी.ए₀ प्लस पूर्ण द्वितीय-क्रम प्रेरण योजना सम्मिलित करना है, पीनो अंकगणित से अधिक स्ट्रोंगर है।

अंकगणितीय समझ

अच्छी प्रकार से अध्ययन किए गए कई उपप्रणालियाँ मॉडलों के समापन गुणों से रिलेशन हैं। उदाहरण के लिए, यह दिखाया जा सकता है, कि पूर्ण दूसरे क्रम के अंकगणित का प्रत्येक ω-मॉडल ट्यूरिंग जंप के अनुसार संवृत्त है, लेकिन ट्यूरिंग जंप के अनुसार संवृत्त किया गया, प्रत्येक ω-मॉडल पूर्ण दूसरे क्रम के अंकगणित का एक मॉडल नहीं है। सबसिस्टम ए.सी.ए₀ में ट्यूरिंग जंप के अनुसार संवृत्त होने की धारणा को पकड़ने के लिए पर्याप्त स्वयंसिद्ध सम्मिलित करना हैं।

ए.सी.ए₀ को मूल सिद्धांतों, अंकगणितीय समझ स्वयंसिद्ध योजना (दूसरे शब्दों में प्रत्येक अंकगणितीय सूत्र φ के लिए समझ स्वयंसिद्ध) और सामान्य दूसरे क्रम प्रेरण स्वयंसिद्ध से युक्त सिद्धांत के रूप में परिभाषित किया गया है। यह संपूर्ण अंकगणितीय प्रेरण अभिगृहीत योजना को भी सम्मिलित करनाकरने के समतुल्य होगा, दूसरे शब्दों में प्रत्येक अंकगणितीय सूत्र φ के लिए प्रेरण अभिगृहीत को सम्मिलित करना होता है।

यह दिखाया जा सकता है, कि यदि एस को ट्यूरिंग जंप, ट्यूरिंग रिड्यूसिबिलिटी और ट्यूरिंग जॉइन (सिम्पसन 2009, पीपी. 311-313) के अनुसार संवृत्त किया जाता है, तो एस के उपसमुच्चय का एक संग्रह ए.सी.ए₀ का एक Q-मॉडल निर्धारित करता है।

ए.सी.ए₀ में सबस्क्रिप्ट 0₀ इंगित करता है, कि इंडक्शन एक्सिओम योजना के प्रत्येक उदाहरण में यह सबसिस्टम सम्मिलित करना नहीं है। इससे ω-मॉडल के लिए कोई फर्क नहीं पड़ता है, जो स्वचालित रूप से प्रेरण सिद्धांत के प्रत्येक उदाहरण को संतुष्ट करता है। चूंकि, गैर-ω-मॉडल के अध्ययन में इसका महत्व है। सभी सूत्रों के लिए ए.सी.ए₀ प्लस इंडक्शन से युक्त प्रणाली को कभी-कभी बिना सबस्क्रिप्ट वाला एसीए कहा जाता है।

सिस्टम एसीए₀ प्रथम-क्रम अंकगणित (या प्रथम-क्रम पीनो स्वयंसिद्धों) का एक रूढ़िवादी विस्तार है, जिसे मूल स्वयंसिद्धों के रूप में परिभाषित किया गया है, साथ ही प्रथम-क्रम अंकगणित की भाषा में प्रथम-क्रम प्रेरण स्वयंसिद्ध योजना (सभी सूत्रों के लिए φ में कोई भी वर्ग चर सम्मिलित करना नहीं है, बाध्य या अन्यथा)। विशेष रूप से इसमें सीमित प्रेरण स्कीमा के कारण प्रथम-क्रम अंकगणित के समान प्रमाण-सैद्धांतिक क्रमसूचक ε0 है।

सूत्रों के लिए अंकगणितीय पदानुक्रम

Main article: अंकगणितीय पदानुक्रम

एक सूत्र को परिबद्ध अंकगणित या Δ⁰₀ कहा जाता है, जब इसके सभी परिमाणक ∀n<t या ∃n<t के रूप के होते हैं (जहाँ n इंडिविजुअल चर की मात्रा निर्धारित की जा रही है, और t एक इंडिविजुअल पद है), जहाँ

$\forall n<t(\cdots )$

के लिए खड़ा है

$\forall n(n<t\rightarrow \cdots )$

और

$\exists n<t(\cdots )$

के लिए खड़ा है

$\exists n(n<t\land \cdots )$.

एक सूत्र को क्रमशः Π⁰₁ (या कभी-कभी Π1) कहा जाता है, जब यह क्रमशः ∃mφ के रूप का होता है, क्रमशः ∀mφ जहां φ एक घिरा हुआ अंकगणितीय सूत्र है, और m एक इंडिविजुअल चर है (जो कि φ में मुफ़्त है)। अधिक सामान्यतः, एक सूत्र को क्रमशः Σ⁰_n, Π⁰_n कहा जाता है, जब इसे क्रमशः Π⁰_n−1, क्रमशः Σ⁰_n−1 सूत्र (और Σ⁰₀ और Π⁰₀ दोनों Δ⁰₀ के समतुल्य हैं) में अस्तित्वगत, क्रमशः सार्वभौमिक, इंडिविजुअल क्वांटिफायर जोड़कर प्राप्त किया जाता है। निर्माण के अनुसार, ये सभी सूत्र अंकगणितीय हैं, (कोई भी वर्ग चर कभी भी बाध्य नहीं होता है) और, वास्तव में, सूत्र को स्कोलेम प्रीनेक्स फॉर्म में डालकर कोई यह देख सकता है, कि प्रत्येक अंकगणितीय सूत्र तार्किक रूप से सभी बड़े पर्याप्त n के लिए Σ⁰_n या Π⁰_n सूत्र के समतुल्य है।

पुनरावर्ती समझ

सबसिस्टम RCA₀ ए.सी.ए₀ की तुलना में एक अस्थिर प्रणाली है, और इसे अधिकांशतः रिवर्स गणित में आधार प्रणाली के रूप में उपयोग किया जाता है। इसमें सम्मिलित करना हैं, मूल सिद्धांत, Σ⁰₁ प्रेरण योजना, और Δ⁰₁ समझ योजना, पूर्व शब्द स्पष्ट है, Σ प्रेरण योजना प्रत्येक Σ⁰₁ सूत्र φ के लिए प्रेरण सिद्धांत है। शब्द Δ⁰₁ समझ" अधिक समिश्रय है, क्योंकि Δ⁰₁ सूत्र जैसी कोई चीज़ नहीं है। इसके अतिरिक्त Δ⁰₁ समझ योजना प्रत्येक Σ⁰₁ सूत्र के लिए समझ सिद्धांत पर जोर देती है, जो तार्किक रूप से Π⁰₁ सूत्र के समतुल्य है। इस योजना में प्रत्येक Σ⁰₁ सूत्र φ और प्रत्येक Π⁰₁ सूत्र ψ के लिए अभिगृहीत सम्मिलित करना है।

$\forall m\forall X((\forall n(\varphi (n)\leftrightarrow \psi (n)))\rightarrow \exists Z\forall n(n\in Z\leftrightarrow \varphi (n)))$

RCA₀ के प्रथम-क्रम परिणामों का समुच्चय पीनो अंकगणित के सबसिस्टम IΣ1 के समान है, जिसमें प्रेरण Σ⁰₁ सूत्रों तक सीमित है। बदले में, IΣ1 आदिम पुनरावर्ती अंकगणित (पीआरए) पर रूढ़िवादी है, $\Pi _{2}^{0}$ इसके अतिरिक्त, प्रमाण-सैद्धांतिक क्रम RCA_{0 ω} ω है, जो पीआरए के समान है।

यह देखा जा सकता है, कि ω के सबसमुच्चय का एक संग्रह एस RCA₀ का एक ω-मॉडल निर्धारित करता है, यदि और मात्र यदि एस ट्यूरिंग रिड्यूसिबिलिटी और ट्यूरिंग जॉइन के अनुसार संवृत्त है। विशेष रूप से, ω के सभी गणना योग्य उपसमुच्चय का संग्रह RCA₀ का ω-मॉडल देता है। इस प्रणाली के नाम के पीछे यही प्रेरणा है, यदि RCA₀ का उपयोग करके किसी समुच्चय का अस्तित्व सिद्ध किया जा सकता है, तो समुच्चय पुनरावर्ती (अर्थात गणना योग्य) है।

अस्थिर सिस्टम

कभी-कभी RCA₀ से भी अस्थिर प्रणाली वांछित होती है। ऐसी एक प्रणाली को इस प्रकार परिभाषित किया गया है। किसी को पहले अंकगणित की भाषा को एक घातीय फलन प्रतीक के साथ बढ़ाना होगा (स्ट्रोंगर प्रणालियों में घातांक को सामान्य चाल द्वारा जोड़ और गुणा के संदर्भ में परिभाषित किया जा सकता है, लेकिन जब प्रणाली बहुत अस्थिर हो जाती है, तो यह संभव नहीं है) और स्पष्ट स्वयंसिद्धों द्वारा मूल सिद्धांतों को गुणन से प्रेरक रूप से घातांक को परिभाषित करना होगा; तब सिस्टम में (समृद्ध) बुनियादी सिद्धांत, प्लस Δ⁰₁ समझ, प्लस Δ⁰₀ प्रेरण सम्मिलित करना होते हैं।

स्ट्रोंगर सिस्टम

RCA₀ पर, दूसरे क्रम के अंकगणित का प्रत्येक सूत्र सभी बड़े पर्याप्त n के लिए Σ¹_n या Π¹_n सूत्र के समतुल्य है। प्रणाली Π¹₁-समझ एक ऐसी प्रणाली है, जिसमें बुनियादी सिद्धांतों के साथ-साथ सामान्य दूसरे क्रम के प्रेरण सिद्धांत और प्रत्येक (बोल्डफेस) Π¹_n सूत्र φ के लिए समझ सिद्धांत सम्मिलित करना है। यह Σ¹₁-समझदारी के समतुल्य है (दूसरी ओर, Δ¹₁-समझदारी, जिसे Δ⁰₁-समझदारी के अनुरूप परिभाषित किया गया है, अस्थिर है)।

प्रक्षेप्य नियति

Main article: प्रोजेक्टिव डिटर्मिनेसी का सिद्धांत

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

दूसरे क्रम के अंकगणित की भाषा में व्यक्त किए जाने वाले कई प्राकृतिक प्रस्ताव Z₂ और यहां तक कि जेडएफसी से स्वतंत्र हैं, लेकिन प्रक्षेप्य निर्धारण से सिद्ध करने योग्य हैं। उदाहरणों में सह-विश्लेषणात्मक पूर्ण उपसमुच्चय संपत्ति, मापनीयता और बेयर की संपत्ति सम्मिलित करना है, $\Sigma _{2}^{1}$ समुच्चय, $\Pi _{3}^{1}$ एकरूपता, आदि होता है, एक अस्थिर आधार सिद्धांत (जैसे कि RCA₀) पर, प्रक्षेप्य निर्धारण का तात्पर्य समझ से है, और दूसरे क्रम के अंकगणित का एक अनिवार्य रूप से पूर्ण सिद्धांत प्रदान करता है, Z₂ की भाषा में प्राकृतिक कथन जो प्रक्षेप्य निर्धारण के साथ Z₂ से स्वतंत्र हैं, उन्हें ढूंढना कठिन है।

ZFC + {वहां n वुडिन कार्डिनल हैं: n एक प्राकृतिक संख्या है} प्रक्षेप्य निर्धारण के साथ Z₂ पर रूढ़िवादी है, [उद्धरण वांछित], अर्थात दूसरे क्रम के अंकगणित की भाषा में एक बयान प्रक्षेप्य निर्धारण के साथ Z₂ में सिद्ध हो सकता है, यदि और मात्र यदि समुच्चय सिद्धांत की भाषा में इसका अनुवाद ZFC + में सिद्ध हो सकता है {n वुडिन कार्डिनल हैं: n∈N}।

कोडिंग गणित

दूसरे क्रम का अंकगणित सीधे प्राकृतिक संख्याओं और प्राकृतिक संख्याओं के समुच्चय को औपचारिक बनाता है। चूंकि, यह कोडिंग तकनीकों के माध्यम से अप्रत्यक्ष रूप से अन्य गणितीय वस्तुओं को औपचारिक रूप देने में सक्षम है, एक तथ्य जिसे सबसे पहले हरमन वेइल ने देखा था (सिम्पसन 2009, पृष्ठ 16)। पूर्णांक, तर्कसंगत संख्या और वास्तविक संख्याएं सभी को उपप्रणाली RCA₀ में औपचारिक रूप दिया जा सकता है, साथ ही उनके बीच पूर्ण वियोज्य मीट्रिक रिक्त स्थान और निरंतर कार्यों (सिम्पसन 2009, अध्याय II) के साथ है।

रिवर्स गणित का अनुसंधान कार्यक्रम गणितीय प्रमेयों को सिद्ध करने के लिए आवश्यक समुच्चय-अस्तित्व सिद्धांतों का अध्ययन करने के लिए दूसरे क्रम के अंकगणित में गणित की इन औपचारिकताओं का उपयोग करता है (सिम्पसन 2009, पृष्ठ 32)। उदाहरण के लिए, वास्तविक से वास्तविक तक के कार्यों के लिए मध्यवर्ती मूल्य प्रमेय RCA₀ (सिम्पसन 2009, पृष्ठ 87) में सिद्ध है, जबकि बोल्ज़ानो-वीयरस्ट्रैस प्रमेय RCA₀ (सिम्पसन 2009, पृष्ठ 34) के मुकाबले RCA₀ के समतुल्य है।

उपरोक्त कोडिंग निरंतर और कुल कार्यों के लिए अच्छी प्रकार से काम करती है, जैसा कि (कोहलेनबैक 2002, धारा 4) में दिखाया गया है, एक उच्च-क्रम आधार सिद्धांत और अस्थिर कोनिग लेम्मा को मानते है। जैसा कि संभवतः अपेक्षित था, टोपोलॉजी या माप सिद्धांत के स्थितियाँ में, कोडिंग समस्याओं के बिना नहीं है, जैसा कि उदाहरण में पता लगाया गया है। (हंटर, 2008) या (नॉर्मन एंड सैंडर्स, 2019)। चूंकि, यहां तक कि रीमैन अभिन्न फ़ंक्शंस को कोड करने से भी समस्याएं उत्पन्न होती हैं, जैसा कि (नॉर्मन एंड सैंडर्स, 2020) में दिखाया गया है, रीमैन इंटीग्रल के लिए आर्ज़ेला के अभिसरण प्रमेय को सिद्ध करने के लिए आवश्यक न्यूनतम (समझ) सिद्धांत बहुत भिन्न हैं, यह इस बात पर निर्भर करता है, कि कोई दूसरे-क्रम कोड या तीसरे-क्रम फ़ंक्शंस का उपयोग करता है, या नहीं करता है।

यह भी देखें

• पेरिस-हैरिंगटन प्रमेय
• प्रेस्बर्गर अंकगणित
• सच्चा अंकगणित

संदर्भ

• Burgess, J. P. (2005), Fixing Frege, Princeton University Press.
• Buss, S. R. (1998), Handbook of proof theory, Elsevier. ISBN 0-444-89840-9
• Friedman, H. (1976), "Systems of second order arithmetic with restricted induction," I, II (Abstracts). Journal of Symbolic Logic, v. 41, pp. 557– 559. JStor
• Hilbert, D. and Bernays, P. (1934), Grundlagen der Mathematik, Springer-Verlag. MR0237246
• Hunter, James, Higher order Reverse Topology, Dissertation, University of Madison-Wisconsin [1].
• Kohlenbach, U., Foundational and mathematical uses of higher types, Reflections on the foundations of mathematics, Lect. Notes Log., vol. 15, ASL, 2002, pp. 92–116.
• Shapiro, S. (1991), Foundations without foundationalism, Oxford University Press. ISBN 0-19-825029-0
• Simpson, S. G. (2009), Subsystems of second order arithmetic, 2nd edition, Perspectives in Logic, Cambridge University Press. ISBN 978-0-521-88439-6 MR2517689
• Takeuti, G. (1975) Proof theory ISBN 0-444-10492-5