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

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

दूसरे क्रम के अंकगणित का अग्रदूत जिसमें तीसरे क्रम के पैरामीटर सम्मिलित करनाहैं, डेविड हिल्बर्ट और पॉल बर्नीस ने अपनी पुस्तक ग्रुंडलाजेन डेर मैथेमेटिक में प्रस्तुत किया था। दूसरे क्रम के अंकगणित के मानक स्वयंसिद्धीकरण को 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, प्रेरण के एक अभिगृहीत स्कीमा के साथ मिलकर N की सामान्य पीनो-डेडेकाइंड परिभाषा बनाते हैं। इन अभिगृहीतों में प्रेरण के किसी भी प्रकार के अभिगृहीत स्कीमा को जोड़ने से अभिगृहीत 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}}$ को पूर्ण मॉडल कहा जाता है। पूर्ण दूसरे क्रम के शब्दार्थ का उपयोग दूसरे क्रम के अंकगणित के मॉडल को पूर्ण मॉडल तक सीमित करने के समतुल्य है। वास्तव में, दूसरे क्रम के अंकगणित के सिद्धांतों में मात्र एक पूर्ण मॉडल होता है। यह इस तथ्य से पता चलता है, कि दूसरे क्रम के प्रेरण स्वयंसिद्ध वाले पीनो सिद्धांतों में दूसरे क्रम के शब्दार्थ के अनुसार मात्र एक मॉडल होता है।

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

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

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

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

• जब एम अपने सामान्य संचालन के साथ प्राकृतिक संख्याओं का सामान्य समूह है, ${\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) का मात्र एक प्रतिबंधित भाग सम्मिलित करना है। इस प्रकार का प्रतिबंध सिस्टम की प्रमाण-सैद्धांतिक ताकत को अधिक कम कर देता है। उदाहरण के लिए, नीचे वर्णित प्रणाली आरसीए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 सूत्र के समतुल्य है।

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

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

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

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

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

कमजोर सिस्टम

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

मजबूत सिस्टम

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

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

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

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

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

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

कोडिंग गणित

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

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

उपरोक्त कोडिंग निरंतर और कुल कार्यों के लिए अच्छी प्रकार से काम करती है, जैसा कि (कोहलेनबैक 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