वृहद गणनीय क्रमसूचक

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

चूंकि केवल अधिक से अंकन हैं, अंकन वाले सभी क्रमांक पूर्व अनगिनत क्रमसूचक ω₁ से अधिक नीचे समाप्त हो जाते हैं, उनके सर्वोच्च को चर्च-क्लीन ω₁ या ω^CK
₁ कहा जाता है, (पूर्व अनगिनत क्रमसूचक के साथ भ्रमित नहीं होना चाहिए, ω₁)। ω^CK
₁ के नीचे की क्रमवाचक संख्याएँ पुनरावर्ती क्रमसूचक्स हैं। इससे बड़े संगणनीय क्रमसूचक को अभी भी परिभाषित किया जा सकता है, किन्तु अंकन नहीं हैं।

गणनीय क्रमसूचकों पर ध्यान केंद्रित करने के कारण, क्रमिक अंकगणित का उपयोग किया जाता है। यहां वर्णित क्रमसूचक बड़े कार्डिनल में वर्णित जितने बड़े नहीं हैं, किन्तु वे उन लोगों में बड़े हैं जिनके पास रचनात्मक अंकन (विवरण) हैं। बड़े क्रमसूचकों को परिभाषित किया जा सकता है, किन्तु उनका वर्णन करना कठिन होता जा रहा है।

पुनरावर्ती क्रमसूचकों पर सामान्यता

Main article: पुनरावर्ती क्रमसूचक

क्रमसूचक संकेतन

Main article: क्रमसूचक संकेतन

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

भिन्न परिभाषा स्टीफन कोल क्लेन की क्रमसूचक संकेतन प्रणाली का उपयोग करती है। संक्षेप में, क्रमिक संकेतन या तो नाम शून्य है (क्रमिक 0 का वर्णन), या क्रमसूचक संकेतन का उत्तराधिकारी (उस संकेतन द्वारा वर्णित क्रमसूचक के उत्तराधिकारी का वर्णन), या ट्यूरिंग मशीन (गणना योग्य कार्य) जो बढ़ते क्रम का उत्पादन करती है क्रमसूचक संकेतन (जो क्रमसूचक का वर्णन करते हैं जो अनुक्रम की सीमा है), और क्रमसूचक संकेतन आदेशित करता हैं, जिससे o के उत्तराधिकारी को o से बड़ा बनाया जा सके और सीमा को अनुक्रम के किसी भी पद से अधिक बनाया जा सके (यह क्रम संगणनीय है; चूंकि, क्रमसूचक संकेतन का समुच्चय 'O' स्वयं अत्यधिक गैर-पुनरावर्ती है, यह निर्धारित करने की असंभवता के कारण कि क्या दी गई ट्यूरिंग मशीन वास्तव में संकेतन के अनुक्रम का उत्पादन करती है); पुनरावर्ती क्रमसूचक तब क्रमसूचक होता है जिसे कुछ क्रमसूचक संकेतन द्वारा वर्णित किया जाता है।

पुनरावर्ती क्रमसूचक से अल्प कोई भी क्रमसूचक स्वयं ही पुनरावर्ती होता है, इसलिए सभी पुनरावर्ती क्रमसूचक का समुच्चय निश्चित (काउंटेबल) क्रमसूचक, चर्च-क्लीन क्रमसूचक (नीचे देखें) बनाता है।

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

अंकगणित की प्रणालियों से संबंध

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

कुछ संगणनीय क्रमांक इतने बड़े होते हैं कि जब वे निश्चित क्रमिक संकेतन O द्वारा दिए जा सकते हैं, तो दी गई औपचारिक प्रणाली यह दिखाने के लिए पर्याप्त शक्तिशाली नहीं हो सकती है कि O, वास्तव में, क्रमसूचक संकेतन है: प्रणाली इतने बड़े के लिए परिमित प्रवेश नहीं दिखाती है।

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

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

विशिष्ट पुनरावर्ती क्रमसूचक

विधेयात्मक परिभाषाएँ और वेब्लेन पदानुक्रम

Main article: वेब्लेन फंक्शन

हमने उल्लेख किया है (कैंटोर सामान्य रूप देखें) ε₀, जो समीकरण को संतुष्ट करने वाला सबसे अल्प है $\omega ^{\alpha }=\alpha$, तो यह अनुक्रम 0, 1 की सीमा है, $\omega$, $\omega ^{\omega }$, $\omega ^{\omega ^{\omega }}$, ... इस समीकरण को संतुष्ट करने वाले क्रमिक को ε₁ कहा जाता है। यह अनुक्रम की सीमा है,

$\varepsilon _{0}+1,\qquad \omega ^{\varepsilon _{0}+1}=\varepsilon _{0}\cdot \omega ,\qquad \omega ^{\omega ^{\varepsilon _{0}+1}}=(\varepsilon _{0})^{\omega },\qquad {\text{etc.}}$

अधिक सामान्यतः, $\iota$-वाँ क्रमवाचक है, जिसे $\omega ^{\alpha }=\alpha$ कहा जाता है, $\varepsilon _{\iota }$ को हम परिभाषित कर सकते हैं $\zeta _{0}$ सबसे अल्प क्रमसूचक के रूप में $\varepsilon _{\alpha }=\alpha$, किन्तु चूंकि ग्रीक वर्णमाला में कई अक्षर नहीं हैं, इसलिए अधिक ठोस संकेतन का उपयोग करना उत्तम है: $\varphi _{\gamma }(\beta )$ क्रमांक को परिभाषित करें, परिमित प्रवेश $\varphi _{0}(\beta )=\omega ^{\beta }$ द्वारा इस प्रकार है: $\varphi _{\gamma +1}(\beta )$ हो $\beta$-वाँ निश्चित बिंदु $\varphi _{\gamma }$ (अर्थात, $\beta$-वाँ क्रमवाचक ऐसा है $\varphi _{\gamma }(\alpha )=\alpha$; तो उदाहरण के लिए, $\varphi _{1}(\beta )=\varepsilon _{\beta }$), और जब $\delta$ सीमा क्रमसूचक है, परिभाषित करें $\varphi _{\delta }(\alpha )$ के रूप में $\alpha$-वाँ सरल निश्चित बिंदु $\varphi _{\gamma }$ सभी के लिए $\gamma <\delta$. फलन के इस क्रम को वेब्लेन पदानुक्रम के रूप में जाना जाता है (परिभाषा में अनावश्यक भिन्नताएं हैं, को $\delta$ अनुमति देना, $\varphi _{\delta }(\alpha )$ सीमा क्रमसूचक $\varphi _{\gamma }(\alpha )$ की सीमा हो, $\gamma <\delta$ के लिए यह अनिवार्य रूप से केवल सूचकांकों को 1 से परिवर्तित करता है, जो हानिरहित है)। वेब्लेन फलन (आधार के लिए $\omega$) $\varphi _{\gamma }$ $\gamma ^{th}$ कहलाती है।

क्रमसूचक: $\varphi _{\alpha }(\beta )<\varphi _{\gamma }(\delta )$ यदि केवल या तो ($\alpha =\gamma$ और $\beta <\delta$) या ($\alpha <\gamma$ और $\beta <\varphi _{\gamma }(\delta )$) या ($\alpha >\gamma$ और $\varphi _{\alpha }(\beta )<\delta$).

फेफ़रमैन-शुट्टे क्रमसूचक

सबसे अल्प क्रमसूचक ऐसा $\varphi _{\alpha }(0)=\alpha$ फ़ेफ़रमैन-शुट्टे क्रमसूचक के रूप में जाना जाता है और सामान्यतः $\Gamma _{0}$ लिखा जाता है। इसे सभी क्रमसूचकों के समुच्चय के रूप में वर्णित किया जा सकता है, जिसे केवल वेब्लेन पदानुक्रम और जोड़ का उपयोग करके, शून्य से प्रारम्भ करके, परिमित भाव के रूप में लिखा जा सकता है। फ़ेफ़रमैन-शुट्टे क्रमसूचक महत्वपूर्ण है क्योंकि, अर्थ में जो स्थिर बनाने के लिए जटिल है, यह सबसे अल्प (अनंत) क्रमसूचक है जिसे अल्प क्रमवाचक संख्या का उपयोग करके वर्णित नहीं किया जा सकता है। यह "अंकगणितीय परिमित प्रत्यावर्तन जैसी प्रणालियों की शक्ति को मापता है।

अधिक सामान्यतः, Γ_α उन क्रमसूचक्स की गणना करता है जिन्हें अतिरिक्त और वेब्लेन फलन का उपयोग करके अल्प क्रमसूचक्स से प्राप्त नहीं किया जा सकता है।

यह निश्चित रूप से, फेफर्मन-शुट्टे क्रमसूचक से भिन्न क्रमसूचकों का वर्णन करना संभव है। अधिक जटिल प्रविधि से निश्चित बिंदुओं का शोध निरंत रख सकता है: $\alpha \mapsto \Gamma _{\alpha }$ के निश्चित बिंदुओं की गणना करें , तत्पश्चात उसके निश्चित बिंदुओं की गणना करें, और इसी प्रकार, और प्रथम क्रमिक α का शोध करें जैसे कि α इस प्रक्रिया के α चरणों में प्राप्त होता है, और इस तदर्थ प्रविधि से विकर्ण करना निरंतर रखता है। यह अल्प वेब्लेन क्रमसूचक और बड़े वेब्लेन क्रमसूचक की परिभाषा की ओर जाता है।

अभेद्य क्रमसूचक

Main article: ऑर्डिनल कोलापसिंग फंक्शन

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

• ψ(α) को सबसे अल्प क्रमसूचक के रूप में परिभाषित किया गया है जिसे 0, 1, ω और Ω से प्रारम्भ करके और बार-बार जोड़, गुणा और घातांक प्रारम्भ करके और ψ को पूर्व से बनाए गए क्रमसूचकों को त्यागकर नहीं बनाया जा सकता है (अतिरिक्त इसके कि ψ केवल प्रारम्भ किया जा सकता है) α से कम नियमों के लिए, यह सुनिश्चित करने के लिए कि यह उचित रूप से परिभाषित है)।

जहाँ Ω = ω₁ प्रथम अनगिनत क्रमसूचक है। इसे इसलिए रखा गया है क्योंकि अन्यथा फलन ψ सबसे अल्प क्रमिक σ पर रुक जाता है जैसे कि ε_σ=σ: विशेष रूप से ψ(α)=σ किसी भी क्रमिक α संतोषजनक σ≤α≤Ω के लिए, चूंकि तथ्य यह है कि हमने Ω को सम्मिलित किया है, हमें इस बिंदु को ज्ञात करने की अनुमति देता है: ψ(Ω+1) σ से बड़ा है। Ω की मुख्य संपत्ति जिसका उपयोग किया है वह यह है कि ψ द्वारा उत्पादित किसी भी क्रमसूचक से अधिक है।

अभी भी बड़े क्रमसूचकों का निर्माण करने के लिए, हम अनगिनत क्रमसूचकों के निर्माण के उपायों को त्यागकर ψ की परिभाषा का विस्तार कर सकते हैं। ऐसा करने के कई प्रविधि हैं, जिनका वर्णन क्रमसूचक कोलैप्सिंग फलन पर लेख में कुछ सीमा तक किया गया है।

'बैचमैन-हावर्ड क्रमसूचक' (कभी-कभी इसे 'हावर्ड क्रमसूचक' ψ₀(ε_Ω+1) भी कहा जाता है, उपरोक्त संकेतन के साथ) महत्वपूर्ण है, क्योंकि यह क्रिप्के-प्लेटेक समुच्चय सिद्धांत के प्रमाण-सैद्धांतिक शक्ति का वर्णन करता है। वास्तव में, इन बड़े क्रमसूचकों का मुख्य महत्व, और उनका वर्णन करने का कारण, कुछ औपचारिक प्रणालियों से उनका संबंध है जैसा कि ऊपर बताया गया है। चूंकि, पूर्ण द्वितीय क्रम अंकगणित के रूप में इस प्रकार की शक्तिशाली औपचारिक प्रणालियां, जर्मेलो-फ्रेंकेल समुच्चय सिद्धांत को अकेले त्याग दें, इस समय पहुंच से भिन्न प्रतीत होती हैं।

इसके अतिरिक्त, कई पुनरावर्ती क्रमसूचक हैं जो पूर्व वाले के रूप में उचित प्रकार से ज्ञात नहीं हैं। बुखोल्ज़ का क्रमसूचक है, जिसे इस रूप में परिभाषित किया गया है $\psi _{0}(\Omega _{\omega })$, संक्षिप्त रूप में केवल $\psi (\Omega _{\omega })$, पूर्व अंकन का उपयोग करना, का प्रमाण-सैद्धांतिक क्रमसूचक $\Pi _{1}^{1}-CA_{0}$ है , अंकगणित का प्रथम-क्रम सिद्धांत प्राकृतिक संख्याओं के साथ-साथ प्राकृतिक संख्याओं के समुच्चय पर परिमाणीकरण की अनुमति देता है, और $ID_{<\omega }$, परिमित रूप से पुनरावृत्त आगमनात्मक परिभाषाओं का औपचारिक सिद्धांत हैं। इसके पश्चात टेकुटी-फेफरमैन-बुखोल्ज़ क्रमसूचक $\Pi _{1}^{1}-CA+BI$ है। और दूसरे क्रम के अंकगणित का उपसमुच्चय $\Pi _{1}^{1}$ - विचार + परिमित प्रवेश, और $ID_{\omega }$, का औपचारिक सिद्धांत $\omega$ है। अंकन में, इसे इस $\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$ रूप में परिभाषित किया गया है, यह बुखोल्ज़ के साई फलन की श्रेणी का सर्वोच्च है। इसका नाम सर्वप्रथम डेविड मैडोर ने रखा था।

आगामी क्रमसूचक का उल्लेख कोड के भाग में किया गया है,एजीडीए में बड़े गणनीय क्रमसूचक और संख्या का वर्णन करने वाले और आंद्रस कोवाक्स द्वारा $\psi _{0}(\Omega _{\omega +1}\cdot \varepsilon _{0})$ परिभाषित किया गया है।

आगामी क्रमसूचक का उल्लेख पूर्व के जैसे ही कोड के उसी भाग में किया गया है, और $\psi _{0}(\Omega _{\omega ^{\omega }})$ इसे परिभाषित किया गया है। यह आगामी क्रमसूचक, तत्पश्चात, कोड के इसी भाग में उल्लिखित है, जिसे परिभाषित किया गया है $\psi _{0}(\Omega _{\omega ^{\omega }})$ का प्रमाण-सैद्धांतिक क्रमसूचक है, $ID_{<\omega ^{\omega }}$ सामान्यतः $\psi _{0}(\Omega _{\varepsilon _{0}})$ का प्रमाण-सैद्धांतिक क्रमसूचक $ID_{<\varepsilon _{0}}$.$ID_{<\nu }$ के समान है, ध्यान दें कि इस निश्चित उदाहरण में, $\psi _{0}(\Omega _{\nu })$ का प्रतिनिधित्व प्रथम क्रमसूचक अशून्य $\Omega _{0}$ करता है ।

इस बिंदु तक के अधिकांश क्रमसूचकों को बुखोल्ज़ हाइड्रा (उदा. $\psi (\Omega _{\omega })=+(0(\omega ))$)

अनाम क्रमसूचक है, जिसे डेविड मैडोर ने गणनीय समाप्ति $\varepsilon _{I+1}$ के रूप में संदर्भित किया है,जहाँ $I$ प्रथम अप्राप्य है (=$\Pi _{0}^{1}$-अवर्णनीय) कार्डिनल,यह क्रिप्के-प्लेटक समुच्चय सिद्धांत का प्रमाण-सैद्धांतिक क्रमसूचक क्रमांक है। क्रिपके-प्लेटेक समुच्चय सिद्धांत क्रमसूचक (KPआई) के वर्ग की पुनरावर्ती दुर्गमता द्वारा संवर्धित, या, अंकगणितीय पक्ष पर, $\Delta _{2}^{1}$ -विचार + परिमित प्रवेश, इसका मूल्य $\psi (\varepsilon _{I+1})$ अज्ञात फलन को उपयोग करने समान है।

अनाम क्रमसूचक है, जिसे डेविड मैडोर ने गणनीय समाप्ति $\varepsilon _{M+1}$ के रूप में संदर्भित किया है ,जहाँ $M$ प्रथम महलो कार्डिनल है। यह KPएम का सिद्धांत का प्रमाण-सैद्धांतिक क्रमसूचक है, क्रिप्के-प्लेटेक समुच्चय सिद्धांत का विस्तार है। कृपके-प्लेटेक समुच्चय सिद्धांत महलो कार्डिनल पर आधारित है। इसका मूल्य $\psi (\varepsilon _{M+1})$ के समान है, बुखोल्ज़ के विभिन्न साई फलन में से उपयोग करना।अनाम क्रमसूचक है, जिसे डेविड मैडोर ने गणनीय समाप्ति $\varepsilon _{K+1}$ के रूप में संदर्भित किया है ,जहाँ $K$ प्रथम शक्तिहीन कॉम्पैक्ट है (=$\Pi _{1}^{1}$-अवर्णनीय) कार्डिनल, यह क्रिप्के-प्लेटेक समुच्चय सिद्धांत का प्रमाण-सैद्धांतिक क्रम है। क्रिप्के-प्लेटेक समुच्चय सिद्धांत + Π3 - Ref। इसका मूल्य $\Psi (\varepsilon _{K+1})$ के समान है राथजेन के साई फलन का उपयोग करना। अनाम क्रमसूचक है, जिसे डेविड मैडोर ने गणनीय समाप्ति $\varepsilon _{\Xi +1}$के रूप में संदर्भित किया है ,जहाँ $\Xi$ प्रथम $\Pi _{0}^{2}$ है -अवर्णनीय कार्डिनल, यह क्रिप्के-प्लेटक समुच्चय सिद्धांत का प्रमाण-सैद्धांतिक क्रम है। क्रिप्के-प्लेटक समुच्चय सिद्धांत + Πω-Ref।,इसका मूल्य $\Psi _{X}^{\varepsilon _{\Xi +1}}$ समान है, स्टीगर्ट के साई फलन का उपयोग करते हुए, जहां $X$ = ($\omega ^{+}$; $P_{0}$; $\epsilon$, $\epsilon$, 0). अंतिम अनाम क्रमसूचक है, जिसे डेविड मैडोर द्वारा स्थिरता के प्रमाण-सैद्धांतिक क्रमसूचक के रूप में संदर्भित किया गया है।यह स्थिरता का प्रमा-सैद्धांतिक क्रमसूचक है, क्रिप्के-प्लेटक समुच्चय सिद्धांत का विस्तार है। इसका मूल्य $\Psi _{X}^{\varepsilon _{Y+1}}$ के समान है, स्टीगर्ट के साई फलन का उपयोग करते हुए, जहां $X$ = ($\omega ^{+}$; $P_{0}$; $\epsilon$, $\epsilon$, 0), क्रमसूचकों का समूह है जिसके विषय में अधिक जानकारी नहीं है, किन्तु अभी भी अधिक महत्वपूर्ण हैं (आरोही क्रम में)।

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

अपरिवर्तनीय पुनरावर्ती क्रमसूचक

ठोस विवरण होने की आवश्यकता को त्याग कर, बड़े पुनरावर्ती गणनीय क्रमसूचकों को विभिन्न ठोस सिद्धांतों की शक्ति को मापने वाले क्रमसूचकों के रूप में प्राप्त किया जा सकता है; सामान्यतः कहा जाए तो, ये क्रमसूचक सबसे अल्प क्रमसूचक हैं जो सिद्धांत प्रमाणित नहीं कर सकते कि वे उचित प्रकार से क्रमिक हैं। दूसरे क्रम के अंकगणित, ज़र्मेलो समुच्चय सिद्धांत , या ज़र्मेलो-फ्रेंकेल समुच्चय सिद्धांत जैसे विभिन्न बड़े क्रमसूचक स्वयंसिद्धों के साथ ठोस सिद्धांत लेने से, कुछ अधिक बड़े पुनरावर्ती क्रमसूचक मिलते हैं। (कठोरता से यह ज्ञात नहीं है कि ये सभी वास्तव में क्रमसूचक हैं: निर्माण द्वारा, किसी सिद्धांत की क्रमिक शक्ति को केवल ठोस सिद्धांत से ही क्रमसूचक प्रमाणित किया जा सकता है। इसलिए बड़े कार्डिनल स्वयंसिद्धों के लिए यह अधिक अस्पष्ट हो जाता है।)

पुनरावर्ती क्रमसूचकों से भिन्न

चर्च-क्लीन क्रमसूचक

पुनरावर्ती क्रमसूचक के समुच्चय का सर्वोच्च सबसे अल्प क्रमसूचक है जिसे पुनरावर्ती प्रविधि से वर्णित नहीं किया जा सकता है। (यह पूर्णांकों के किसी भी पुनरावर्ती सुव्यवस्थित क्रम का क्रम प्रकार नहीं है।) वह क्रमसूचक गणनीय क्रमसूचक है जिसे चर्च-क्लीन क्रमसूचक $\omega _{1}^{\mathrm {CK} }$ कहा जाता है। इस प्रकार, $\omega _{1}^{\mathrm {CK} }$ सबसे अल्प गैर-पुनरावर्ती क्रमसूचक है, और इस बिंदु से किसी भी क्रमसूचक का उचित वर्णन करने की कोई अपेक्षा नहीं है - हम केवल उन्हें परिभाषित कर सकते हैं। किन्तु यह अभी भी पूर्व अनगिनत क्रमसूचक $\omega _{1}$ से अधिक कम है, चूंकि जैसा कि इसके प्रतीक से ज्ञात हुआ है, यह कई प्रकार से व्यवहार करता है, जैसे कि $\omega _{1}$ के अतिरिक्त उदाहरण के लिए, $\omega _{1}$ कोई कोलेम्ब फलनो को $\omega _{1}^{\mathrm {CK} }$ परिभाषित कर सकता है।

स्वीकार्य क्रमसूचक

Main article: स्वीकार्य अध्यादेश

चर्च-क्लेन क्रमसूचक क्रिपके-प्लेटक समुच्चय सिद्धांत से संबंधित है, किन्तु अब भिन्न प्रविधि से, जबकि बाचमैन-हावर्ड क्रमसूचक सबसे अल्प क्रमसूचक था जिसके लिए KP परिमित प्रवेश प्रमाणित नहीं करता है, चर्च- क्लेन क्रमसूचक सबसे अल्प α है जैसे कि रचनात्मक ब्रह्मांड का निर्माण गोडेल ब्रह्मांड, L, चरण α तक, KP का मॉडल $L_{\alpha }$ उत्पन्न करता है। इस प्रकार के क्रमसूचकों को स्वीकार्य $\omega _{1}^{\mathrm {CK} }$ कहा जाता है, सबसे अल्प स्वीकार्य क्रमिक (KP में अनंतता के स्वयंसिद्ध को सम्मिलित नहीं किए जाने की स्थिति में ω से भिन्न) है।

गेराल्ड सैक्स के प्रमेय के अनुसार, गणनीय स्वीकार्य क्रमसूचक वास्तव में चर्च-क्लेन क्रमसूचक के समान प्रविधि से निर्मित होते हैं किन्तु ओरेकल के साथ ट्यूरिंग मशीनों के लिए कोई कभी-कभी $\omega _{\alpha }^{\mathrm {CK} }$ लिखता है $\alpha$-वाँ क्रमिक के लिए, जो या तो स्वीकार्य है या अल्प स्वीकार्य की सीमा है।

स्वीकार्य क्रमसूचकों से भिन्न $\omega _{\omega }^{\mathrm {CK} }$ स्वीकार्य क्रमसूचकों की सबसे अल्प सीमा है (पश्चात में उल्लेख किया गया है), तत्पश्चात क्रमसूचक स्वयं स्वीकार्य नहीं है। यह सबसे अल्प भी है, यह $\alpha$ ऐसा है कि $L_{\alpha }\cap P(\omega )$ का मॉडल $\Pi _{1}^{1}$ है, क्रम जो स्वीकार्य $\alpha$ और $\alpha$ स्वीकार्य दोनों की सीमा है, या समकक्ष ऐसा है, वें स्वीकार्य क्रमिक, को पुनरावर्ती दुर्गम कहा जाता है, और कम से कम पुनरावर्ती दुर्गम को $\omega _{1}^{E_{1}}$ निरूपित किया जा सकता है। क्रमसूचक जो पुनरावर्ती रूप से अप्राप्य दोनों है और पुनरावर्ती रूप से दुर्गम की सीमा को पुनरावर्ती रूप से अति दुर्गम कहा जाता है।इस प्रकार से बड़े क्रमसूचकों का सिद्धांत उपस्थित है जो कि (अल्प) बड़े कार्डिनल संपत्ति के समानांतर है। उदाहरण के लिए, हम पुनरावर्ती महलो क्रमसूचक परिभाषित कर सकते हैं, ये $\alpha$ ऐसा है कि प्रत्येक $\alpha$-पुनरावर्ती संवृत असीमित उप $\alpha$ स्वीकार्य क्रमसूचक ( कार्डिनल आंखें की परिभाषा का पुनरावर्ती एनालॉग) सम्मिलित है। किन्तु ध्यान दें कि अभी भी यहां संभवतः गणनीय क्रमसूचकों के विषय में वर्णन कर रहे हैं।

प्रतिबिंब

सूत्रों के समुच्चय के लिए $\Gamma$, सीमा क्रमसूचक $\alpha$ कहा जाता है $\Gamma$-प्रतिबिंबित यदि श्रेणी $L_{\alpha }$ प्रत्येक के लिए निश्चित प्रतिबिंब $\Gamma$-सूत्र $\phi$ संपत्ति को संतुष्ट करता है। ये क्रमसूचक KP+Π₃- जैसे सिद्धांतों के क्रमिक विश्लेषण में प्रकट होते हैं, कृपके-प्लेटक समुच्चय सिद्धांत को बढ़ाता है। a $\Pi _{3}$-प्रतिबिंब स्कीमा, उन्हें कुछ अनगिनत कार्डिनल्स जैसे शक्तिहीन रूप से कॉम्पैक्ट कार्डिनल और अवर्णनीय कार्डिनल के पुनरावर्ती एनालॉग भी माना जा सकता है। उदाहरण के लिए, क्रमसूचक जो $\Pi _{3}$-प्रतिबिंबित करने को पुनरावर्ती शक्तिहीन रूप से कॉम्पैक्ट कहा जाता है। परिमित के लिए $n$, कम से कम $\Pi _{n}$-क्रमसूचक को प्रतिबिंबित करना भी मोनोटोनिक आगमनात्मक परिभाषाओं के क्लोजर क्रमसूचक का सर्वोच्च है, जिनके ग्राफ अंकगणितीय पदानुक्रम Π_m+1^{0 हैं। विशेष रूप से, $\Pi _{3}$-प्रतिबिंबित क्रमसूचकों में उच्च-क्रम फलन का उपयोग करके लक्षण वर्णन भी होता है। क्रमसूचक फलन पर उच्च-प्रकार के कार्यात्मक, उन्हें 2-स्वीकार्य क्रमसूचकों का नाम दिया जाता है। सोलोमन फेफरमैन द्वारा अप्रकाशित पेपर प्रत्येक परिमित के लिए आपूर्ति करता है, $n$ समान संपत्ति के अनुरूप $\Pi _{n}$-प्रतिबिंब होता है।}

असंभाव्यता

स्वीकार्य क्रमसूचक $\alpha$ कुल नहीं होने पर गैर-प्रक्षेप्य कहा जाता है $\alpha$-पुनरावर्ती एकाकी फलन मैपिंग $\alpha$ अल्प क्रम में, (यह नियमित कार्डिनल्स के लिए से सत्य है; चूंकि, मुख्य रूप से संगणनीय क्रमसूचक में रुचि रखते हैं।) स्वीकार्य, पुनरावर्ती दुर्गम, या यहाँ तक कि पुनरावर्ती रूप से महलो होने की तुलना में गैर-प्रक्षेप्य होना अत्यधिक ठोस स्थिति है।जेन्सेन की परियोजना की विधि द्वारा, यह इस कथन के समतुल्य है कि रचनात्मक ब्रह्मांड गोडेल ब्रह्मांड, एल, चरण α तक, मॉडल $L_{\alpha }$ KP + का $\Sigma _{1}$-भिन्नाव उत्पन्न करता है, चूंकि, $\Sigma _{1}$-स्वयं बल के पर (की उपस्थिति में नहीं $V=L$) असंभाव्यता को प्रदर्शित करने के लिए ठोस पर्याप्त स्वयंसिद्ध स्कीमा नहीं है, वास्तव में इसके सकर्मक मॉडल $KP$+$\Sigma _{1}$ हैं किसी भी गणनीय स्वीकार्य ऊंचाई का पृथक्करण $>\omega$ है। अप्रक्षेप्य क्रमसूचक्स रोनाल्ड ब्योर्न जेन्सेन से जुड़े हुए हैं, परियोजना पर जेन्सेन का कार्य करता है।

अप्राप्य क्रमसूचक

See also: न्यूनतम मॉडल (सेट सिद्धांत)

हम और भी बड़े क्रमसूचकों की कल्पना कर सकते हैं जो अभी भी गणनीय हैं। उदाहरण के लिए, यदि ज़र्मेलो-फ्रेंकेल समुच्चय सिद्धांत में सकर्मक मॉडल है (संगतता की मात्र परिकल्पना से ठोस परिकल्पना और दुर्गम कार्डिनल के अस्तित्व से निहित), तो वहाँ गणनीय उपस्थित $\alpha$ है $L_{\alpha }$ ऐसा है कि जेडएफसी का मॉडल है। इस प्रकार के क्रमसूचक्स जेडएफसी की शक्ति से इस अभिप्राय में भिन्न हैं कि यह (निर्माण द्वारा) उनके अस्तित्व को प्रमाणित नहीं कर सकता है।

यदि $T$ पुनरावर्ती गणनीय समुच्चय सिद्धांत है जो निर्माण की स्वयंसिद्धता के साथ संगत है | V=L, सबसे कम $\alpha$ ऐसा है कि $(L_{\alpha },\in )\vDash T$ कम से कम स्थिर क्रमसूचक से कम है, जो इस प्रकार है।

स्थिर क्रमसूचक

यहां तक ​​​​कि बड़े गणनीय क्रमसूचक, जिन्हें स्थिर क्रमसूचक कहा जाता है, को अवर्णनीयता की स्थिति या उन के रूप में परिभाषित किया जा सकता है $\alpha$ ऐसा है कि $L_{\alpha }$ का Σ₁ प्रारंभिक तुल्यता है, L का प्राथमिक उपमॉडल; जेडएफसी में इन क्रमसूचकों के अस्तित्व को सिद्ध किया जा सकता है, और वे मॉडल-सैद्धांतिक दृष्टिकोण से से गैर-प्रक्षेप्य क्रमसूचकों के निकटता से संबंधित हैं। गणनीय $\alpha$ के लिए $\alpha$ की स्थिरता के समान $L_{\alpha }\prec _{\Sigma _{1}}L_{\omega _{1}}$ है।

स्थिर क्रमसूचकों के प्रकार

ये स्थिर क्रमसूचकों के शक्तिहीन रूप हैं। उपरोक्त कम से कम अप्रक्षेप्य क्रमसूचक से अल्प इन गुणों वाले क्रमसूचक हैं,उदाहरण के लिए क्रमसूचक है $(+1)$-स्थिर यदि ऐसा $\Pi _{n}^{0}$-है सभी प्राकृतिक के लिए प्रतिबिंबित $n$.* गणनीय क्रमसूचक $\alpha$ कहा जाता है $(+\beta )$-स्थिर यदि केवल $L_{\alpha }\prec _{\Sigma _{1}}L_{\alpha +\beta }$होता है।

• गणनीय क्रमसूचक $\alpha$ कहा जाता है $(^{+})$-स्थिर यदि केवल $L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }$, जहाँ $\beta$ कम से कम स्वीकार्य क्रमिक से $\alpha$ बड़ा है।
• गणनीय क्रमसूचक $\alpha$ कहा जाता है $(^{++})$-स्थिर यदि केवल $L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }$, जहाँ $\beta$ कम से कम स्वीकार्य क्रमसूचक से बड़ा $\alpha$ है, गणनीय क्रमसूचक $\alpha$ को दुर्गम-स्थिर कहा जाता है यदि केवल $L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }$, जहाँ $\beta$ कम से कम पुनरावर्ती दुर्गम क्रमसूचक से $\alpha$ बड़ा है। गणनीय क्रमसूचक $\alpha$ महलो-स्थिर कहा जाता है यदि केवल $L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }$, जहाँ $\beta$ कम से कम पुनरावर्ती महलो क्रमसूचक से $\alpha$ बड़ा है।
• गणनीय क्रमसूचक $\alpha$ दुगना कहा जाता है $(+1)$-स्थिर यदि केवल $(+1)$ है -स्थिर क्रमसूचक $\beta >\alpha$ ऐसा है कि $L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }$.दूसरे क्रम के अंकगणित के उप-प्रणालियों के विश्लेषण सहित प्रमाण-सैद्धांतिक प्रकाशनों में स्थिरता की ठोस स्थिरता सामने आई हैं।

छद्म सुव्यवस्थित

क्लेन के अंकन की योजना के अंदर कुछ क्रमसूचकों का प्रतिनिधित्व करते हैं और कुछ नहीं करते हैं। पुनरावर्ती कुल क्रम को परिभाषित कर सकता है जो कि क्लेन अंकन का उपसमुच्चय है और प्रारंभिक खंड है जो क्रम-प्रकार के साथ $\omega _{1}^{\mathrm {CK} }$ सुव्यवस्थित है, इस कुल आदेश के क्रम प्रत्येक पुनरावर्ती गणना योग्य (या यहां तक ​​​​कि अतिगणतीय) गैर-रिक्त उपसमुच्चय में कम से कम तत्व होता है। तो यह कुछ अभिप्राय में सुव्यवस्थित जैसा दिखता है। उदाहरण के लिए, कोई इस पर अंकगणितीय संक्रियाओं को परिभाषित कर सकता है। तत्पश्चात यह प्रभावी रूप से निर्धारित करना संभव नहीं है कि प्रारंभिक सुव्यवस्थित भाग कहाँ समाप्त होता है और कम से कम तत्व की कमी वाला भाग प्रारम्भ होता है।

पुनरावर्ती स्यूडो-वेल-क्रमसूचक के उदाहरण के लिए, S को ATR₀ या अन्य पुनरावर्ती स्वयंसिद्ध सिद्धांत होने दें, जिसमें ω-मॉडल है किन्तु कोई अतिगणतीयल ω-मॉडल नहीं है, और (यदि आवश्यक हो) स्कोलेम फलन के रूप में S का विस्तार करता है। मान लीजिए कि T, S के (अनिवार्य रूप से) परिमित आंशिक ω-मॉडल का वृक्ष है: प्राकृतिक संख्याओं का क्रम $x_{1},x_{2},...,x_{n}$ T में है iff S प्लस ∃m φ(m) ⇒ φ(x_⌈φ⌉) (प्रथम n सूत्रों के लिए φ संख्यात्मक मुक्त चर के साथ; ⌈φ⌉ गोडेल संख्या है) n से अल्प कोई असंगति प्रमाण नहीं है। तत्पश्चात T का क्लेन-ब्राउवर क्रम पुनरावर्ती छद्मवेल क्रमसूचक है।

ऐसे किसी भी निर्माण में क्रमसूचक होना चाहिए, $\omega _{1}^{CK}\times (1+\eta )+\rho$, जहाँ $\eta$ का आदेश प्रकार है $(\mathbb {Q} ,<)$, और $\rho$ पुनरावर्ती क्रमसूचक है।

संदर्भ

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

पुनरावर्ती क्रमसूचकों पर

• वोल्फ्राम पोहलर्स, प्रमाण सिद्धांत, स्प्रिंगर 1989 ISBN 0-387-51842-8 (वेब्लेन पदानुक्रम और कुछ अप्रतिबंधित क्रमसूचकों के लिए)। यह बड़े गणनीय क्रमसूचकों पर सबसे अधिक पठनीय पुस्तक है।
• गेसी टेकुटी, प्रमाण सिद्धांत, दूसरा संस्करण 1987 ISBN 0-444-10492-5 (क्रमिक आरेखों के लिए)
• कर्ट शुट्टे, प्रमाण सिद्धांत, स्प्रिंगर 1977 ISBN 0-387-07911-4 (वेब्लेन पदानुक्रम और कुछ प्रतिकूल क्रमसूचकों के लिए)
• क्रेग स्मोरिंस्की, द वेरायटीज़ ऑफ़ आर्बोरियल एक्सपीरियंस मैथ इंटेलिजेंसर 4 (1982), नहीं। 4, 182-189; वेबलेन पदानुक्रम का अनौपचारिक विवरण सम्मिलित है।
• हार्टले रोजर्स जूनियर, पुनरावर्ती फलन का सिद्धांत और प्रभावी संगणनीयता मैकग्रा-हिल (1967) ISBN 0-262-68052-1 (पुनरावर्ती क्रमसूचक्स और चर्च-क्लीन क्रमसूचक का वर्णन करता है)
• लैरी डब्ल्यू मिलर, नॉर्मल फलन एंड कंस्ट्रक्टिव क्रमसूचक अंकन्स, प्रतीकात्मक नियम का जर्नल, वॉल्यूम 41, नंबर 2, जून 1976, पेज 439 से 459, JSTOR 2272243,
• हिल्बर्ट लेविट्ज़, परिमित क्रमसूचक्स एंड देयर अंकन्स: फॉर द अनिनिशिएटेड, एक्सपोजिटरी आर्टिकल (8 पेज, परिशिष्ट भाग में)
• हरमन रूज जर्वेल, ट्रुथ एंड प्रोविबिलिटी, पांडुलिपि प्रगति पर है।

पुनरावर्ती क्रमसूचकों से भिन्न

• Barwise, Jon (1976). स्वीकार्य सेट और संरचनाएं: निश्चितता सिद्धांत के लिए एक दृष्टिकोण. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-07451-1.
• हिनमैन,, पीटर जी (1978). पुनरावर्तन-सैद्धांतिक पदानुक्रम. गणितीय तर्क में परिप्रेक्ष्य।. स्प्रिंगर-वर्लाग।.{{cite book}}: CS1 maint: extra punctuation (link)

पुनरावर्ती और गैर-पुनरावर्ती क्रम दोनों

• माइकल राथजेन, क्रमसूचक विश्लेषण का क्षेत्र एस. बैरी कूपर और जॉन ट्रस (संपा):समुच्चय और प्रमाण (कैम्ब्रिज यूनिवर्सिटी प्रेस, 1999) 219-279। पोस्टस्क्रिप्ट फ़ाइल पर।

इनलाइन संदर्भ

श्रेणी:क्रमिक संख्या श्रेणी:प्रमाण सिद्धांत