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

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

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

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

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

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

परिभाषा

सिंटेक्स

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

व्यष्टिगत पद स्थिरांक 0, एकात्मक फलन S (परवर्ती फलन), और द्विआधारी संक्रियाएँ + और ⋅ (जोड़ और गुणा) से बनते हैं। परवर्ती फलन अपने इनपुट में 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, जिसे "शून्य" कहा जाता है।

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

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

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) को संतुष्ट करने वाली प्राकृतिक संख्याओं का एक तकनीकी प्रतिबंध है, अन्यथा सूत्र φ में चर जेड सम्मिलित करना नहीं हो सकता है, अन्यथा सूत्र के लिए $n\not \in Z$ अभिबोध के सिद्धांत की ओर ले जाएगा

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

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

सम्पूर्ण पद्धति

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

मॉडल

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

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

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

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

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

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

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

अंकगणितीय अभिबोध

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

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

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

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

पद्धति ACA₀ प्रथम-क्रम अंकगणित (या प्रथम-क्रम पीनो अभिगृहीतों) का एक रूढ़िवादी विस्तार है, जिसे मूल अभिगृहीतों के रूप में परिभाषित किया गया है, साथ ही प्रथम-क्रम अंकगणित की भाषा में प्रथम-क्रम प्रेरण अभिगृहीत योजना सभी सूत्रों के लिए φ में कोई भी वर्ग चर सम्मिलित करना बाध्य नहीं है, या अन्यथा विशेष रूप से इसमें सीमित प्रेरण स्कीमा के कारण प्रथम-क्रम अंकगणित के समान प्रमाण-सैद्धांतिक क्रमसूचक ε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₀ तथा ACA₀ की तुलना में एक वीक़ प्रणाली है, और इसे अधिकांशतः प्रत्यावर्ती गणित में आधार प्रणाली के रूप में उपयोग किया जाता है। इसमें मूल सिद्धांत सम्मिलित करना हैं, Σ⁰₁ प्रेरण योजना, और Δ⁰₁ अभिबोध योजना, पूर्व शब्द स्पष्ट है, Σ प्रेरण योजना प्रत्येक Σ⁰₁ सूत्र φ के लिए प्रेरण सिद्धांत है। शब्द Δ⁰₁ अभिबोध" अधिक समिश्रय है, क्योंकि Δ⁰₁ सूत्र जैसी कोई चीज़ नहीं है। इसके अतिरिक्त Δ⁰₁ अभिबोध योजना प्रत्येक Σ⁰₁ सूत्र के लिए अभिबोध सिद्धांत पर जोर देती है, जो तार्किक रूप से Π⁰₁ सूत्र के समतुल्य है। इस योजना में प्रत्येक Σ⁰₁ सूत्र φ और प्रत्येक Π⁰₁ सूत्र ψ के लिए अभिगृहीत सम्मिलित करना है।

$\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