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

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

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

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

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

परिभाषा

सिंटेक्स

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

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

अभिगृहीत

बुनियादी

निम्नलिखित स्वयंसिद्धों को मूल स्वयंसिद्धों या कभी-कभी रॉबिन्सन स्वयंसिद्धों के रूप में जाना जाता है। परिणामी प्रथम-क्रम सिद्धांत, जिसे रॉबिन्सन अंकगणित के रूप में जाना जाता है, अनिवार्य रूप से बिना प्रेरण के Peano_axioms#Peano_arithmetic_as_first-order_theory है। क्वांटिफिकेशन (तर्क) के लिए प्रवचन का क्षेत्र प्राकृतिक संख्याएं हैं, जिन्हें सामूहिक रूप से 'एन' द्वारा दर्शाया जाता है, और विशिष्ट सदस्य भी शामिल हैं $0$, शून्य कहा जाता है।

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

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

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].$

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

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

यदि φ(n) एक मुक्त व्यक्तिगत चर n और संभवतः अन्य मुक्त व्यक्तिगत या सेट चर (लिखित m) के साथ दूसरे क्रम के अंकगणित का एक सूत्र है₁,...,एम_k और एक्स₁,...,एक्स_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 (एम का एक तत्व), एम से एम तक एक फ़ंक्शन एस, दो बाइनरी ऑपरेशन + और · एम पर होता है। , एम पर एक द्विआधारी संबंध <, और एम के सबसेट का एक संग्रह डी, जो सेट चर की सीमा है। डी को छोड़ने से प्रथम-क्रम अंकगणित की भाषा का एक मॉडल तैयार होता है।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Main article: Arithmetical hierarchy

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

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

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

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

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

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

कमजोर सिस्टम

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

मजबूत सिस्टम

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

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

Main article: Axiom of projective determinacy

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

दूसरे क्रम के अंकगणित की भाषा में अभिव्यक्त होने वाले कई प्राकृतिक प्रस्ताव Z से स्वतंत्र हैं₂ और यहां तक ​​कि ZFC भी लेकिन प्रक्षेप्य निर्धारण से सिद्ध करने योग्य हैं। उदाहरणों में सह-विश्लेषणात्मक परफेक्ट सेट संपत्ति, मापनीयता और बेयर की संपत्ति शामिल है $\Sigma _{2}^{1}$ सेट, $\Pi _{3}^{1}$ कमजोर आधार सिद्धांत (जैसे आरसीए) पर एकरूपता (सेट सिद्धांत), आदि₀), प्रक्षेप्य निर्धारण का तात्पर्य समझ से है और दूसरे क्रम के अंकगणित का एक अनिवार्य रूप से पूर्ण सिद्धांत प्रदान करता है - 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