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

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

चूंकि केवल बहुत से अंकन हैं, अंकन वाले सभी क्रमांक पूर्व अनगिनत क्रमसूचक ω₁ से अधिक नीचे समाप्त हो जाते हैं, उनके सर्वोच्च को चर्च-क्लीन ω₁ या ω^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$. कार्यों के इस परिवार को वेब्लेन पदानुक्रम के रूप में जाना जाता है (परिभाषा में अनावश्यक भिन्नताएं हैं, जैसे कि for $\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) उपरोक्त संकेतन के साथ) एक महत्वपूर्ण है, क्योंकि यह क्रिप्के-प्लेटेक सेट सिद्धांत के प्रमाण-सैद्धांतिक शक्ति का वर्णन करता है। वास्तव में, इन बड़े क्रमसूचकों का मुख्य महत्व, और उनका वर्णन करने का कारण, कुछ औपचारिक प्रणालियों से उनका संबंध है जैसा कि ऊपर बताया गया है। चूंकि, पूर्ण द्वितीय क्रम अंकगणित के रूप में इस प्रकार की शक्तिशाली औपचारिक प्रणालियां, जर्मेलो-फ्रेंकेल सेट सिद्धांत को अकेले त्याग दें, इस समय पहुंच से भिन्न प्रतीत होती हैं।

=== बचमन-हावर्ड क्रमसूचक === से भी भिन्न इसके अतिरिक्त, कई पुनरावर्ती क्रमसूचक हैं जो पिछले वाले के रूप में अच्छी प्रकार से ज्ञात नहीं हैं। इनमें से पहला है Ψ0(Ωω) | बुखोल्ज़ क्रमसूचक, इस रूप में परिभाषित $\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})$. यह बुखोल्ज़ के साई कार्यों की श्रेणी का सर्वोच्च है। इसका नाम सबसे पहले डेविड मैडोर ने रखा था।

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

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

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

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

अगला एक और अनाम क्रमसूचक है, जिसे डेविड मैडोर ने गणनीय पतन के रूप में संदर्भित किया है $\varepsilon _{M+1}$,कहाँ $M$ पहला महलो कार्डिनल है। यह केपीएम का प्रूफ-थ्योरिटिक क्रमसूचक है, क्रिप्के-प्लेटेक सेट थ्योरी का विस्तार है। कृपके-प्लेटेक सेट थ्योरी महलो कार्डिनल पर आधारित है। इसका मूल्य बराबर है $\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: स्वीकार्य अध्यादेश

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

गेराल्ड सैक्स के प्रमेय के अनुसार, गणनीय स्वीकार्य क्रमसूचक वास्तव में चर्च-क्लेन क्रमसूचक के समान प्रविधि से निर्मित होते हैं किन्तु ओरेकल मशीन के साथ ट्यूरिंग मशीनों के लिए कोई कभी-कभी $\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 }$ केपी + का $\Sigma _{1}$-भिन्नाव उत्पन्न करता है, चूंकि, $\Sigma _{1}$-स्वयं बल के पर (की उपस्थिति में नहीं $V=L$) असंभाव्यता को इंगित करने के लिए ठोस पर्याप्त स्वयंसिद्ध स्कीमा नहीं है, वास्तव में इसके सकर्मक मॉडल $KP$+$\Sigma _{1}$ हैं किसी भी गणनीय स्वीकार्य ऊंचाई का पृथक्करण $>\omega$ है।गैर-प्रोजेक्टिबल क्रमसूचक्स रोनाल्ड ब्योर्न जेन्सेन से जुड़े हुए हैं, प्रोजेक्टा पर जेन्सेन का कार्य करता है।

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

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

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

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

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

यहां तक ​​​​कि बड़े गणनीय क्रमसूचक, जिन्हें स्थिर क्रमसूचक कहा जाता है, को अवर्णनीयता की स्थिति या उन के रूप में परिभाषित किया जा सकता है $\alpha$ ऐसा है कि $L_{\alpha }$ का Σ₁ प्रारंभिक तुल्यता है, एल का प्राथमिक सबमॉडल; ZFC में इन क्रमसूचकों के अस्तित्व को सिद्ध किया जा सकता है, और वे मॉडल-सैद्धांतिक दृष्टिकोण से से गैर-प्रक्षेप्य क्रमसूचकों से निकटता से संबंधित हैं। गणनीय $\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 से अल्प कोई असंगति प्रमाण नहीं है। तत्पश्चात टी का क्लेन-ब्राउवर ऑर्डर पुनरावर्ती छद्मवेल ऑर्डरिंग है।

ऐसे किसी भी निर्माण में ऑर्डर टाइप होना चाहिए, $\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। पोस्टस्क्रिप्ट फ़ाइल पर।

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

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