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

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

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

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

पुनरावर्ती अध्यादेशों पर सामान्यता

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

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

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

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

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

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

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

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

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

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

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

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

विशिष्ट पुनरावर्ती अध्यादेश

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

Main article: Veblen function

हमने पहले ही उल्लेख किया है (क्रमिक अंकगणित#कैंटर सामान्य रूप देखें) क्रमसूचक एप्सिलॉन संख्या (गणित)|ε₀, जो समीकरण को संतुष्ट करने वाला सबसे छोटा है $\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 से बदलता है, जो हानिरहित है)। $\varphi _{\gamma }$ कहा जाता है $\gamma ^{th}$ Veblen फंक्शन(आधार के लिए $\omega$).

आदेश देना: $\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$ Feferman-Schütte ordinal के रूप में जाना जाता है और आम तौर पर लिखा जाता है $\Gamma _{0}$. इसे सभी अध्यादेशों के सेट के रूप में वर्णित किया जा सकता है, जिसे केवल वेब्लेन पदानुक्रम और जोड़ का उपयोग करके, शून्य से शुरू करके, परिमित भाव के रूप में लिखा जा सकता है। Feferman-Schütte ordinal महत्वपूर्ण है क्योंकि, एक अर्थ में जो सटीक बनाने के लिए जटिल है, यह सबसे छोटा (अनंत) क्रमसूचक है जिसे अल्प ordinals का उपयोग करके वर्णित नहीं किया जा सकता है। यह रिवर्स मैथमैटिक्स#अरिथमेटिकल ट्रांसफ़िनिट रिकर्सन ATR0 जैसी प्रणालियों की ताकत को मापता है।

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

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

इम्प्रिडिकेटिव क्रमसूचक्स

Main article: Ordinal collapsing function

फ़ेफ़रमैन-शुट्टे क्रमसूचक से बहुत आगे जाने के लिए, नए तरीकों को पेश करने की आवश्यकता है। दुर्भाग्य से ऐसा करने के लिए अभी तक कोई मानक तरीका नहीं है: ऐसा लगता है कि इस विषय में प्रत्येक लेखक ने अपनी स्वयं की अंकन प्रणाली का आविष्कार किया है, और विभिन्न प्रणालियों के बीच अनुवाद करना अधिक कठिन है। इस प्रकार की पहली प्रणाली 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}^{\mathrm {CK} }$ के बजाय $\omega _{1}$.

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

Main article: Admissible ordinal

चर्च-क्लेन क्रमसूचक फिर से क्रिपके-प्लेटक सेट सिद्धांत से संबंधित है, किन्तु अब एक भिन्न तरीके से: जबकि बाचमैन-हावर्ड क्रमसूचक (#Impredicative ordinals वर्णित) सबसे छोटा क्रमसूचक था जिसके लिए केपी ट्रांसफिनिट इंडक्शन साबित नहीं करता है, चर्च- क्लेन क्रमसूचक सबसे छोटा α है जैसे कि रचनात्मक ब्रह्मांड का निर्माण | गोडेल ब्रह्मांड, एल, चरण α तक, एक मॉडल उत्पन्न करता है $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}}$. एक क्रमसूचक जो पुनरावर्ती रूप से अप्राप्य दोनों है और पुनरावर्ती रूप से दुर्गम की सीमा को पुनरावर्ती रूप से अति दुर्गम कहा जाता है।इस प्रकार से बड़े अध्यादेशों का एक सिद्धांत मौजूद है जो कि (अल्प) बड़े कार्डिनल संपत्ति के समानांतर है। उदाहरण के लिए, हम पुनरावर्तीली Mahlo ordinals परिभाषित कर सकते हैं: ये हैं $\alpha$ ऐसा है कि हर $\alpha$-पुनरावर्ती क्लोज्ड अनबाउंड सबसेट ऑफ $\alpha$ एक स्वीकार्य क्रमसूचक (एक कार्डिनल आंखें की परिभाषा का एक पुनरावर्ती एनालॉग) शामिल है। किन्तु ध्यान दें कि हम अभी भी यहां संभवतः गणनीय अध्यादेशों के बारे में बात कर रहे हैं। (जबकि ज़र्मेलो-फ्रेंकेल सेट सिद्धांत में दुर्गम या महलो कार्डिनल्स के अस्तित्व को साबित नहीं किया जा सकता है, जो कि पुनरावर्ती रूप से दुर्गम या पुनरावर्ती महलो क्रमसूचक्स ZFC का एक प्रमेय है: वास्तव में, कोई भी नियमित कार्डिनल पुनरावर्तीली महलो और अधिक है, किन्तु भले ही हम सीमित हों संगणनीय अध्यादेश के लिए खुद, ZFC पुनरावर्तीली महलो क्रमसूचक्स के अस्तित्व को साबित करता है। चूंकि, वे क्रिपके-प्लेटेक सेट सिद्धांत की पहुंच से परे हैं।)

प्रतिबिंब

सूत्रों के एक सेट के लिए $\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: Minimal model (set theory)

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

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

स्थिर अध्यादेश

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

संदर्भ

Most books describing large countable ordinals are on proof theory, and unfortunately tend to be out of print.

पुनरावर्ती अध्यादेशों पर

• वोल्फ्राम पोहलर्स, प्रूफ थ्योरी, स्प्रिंगर 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.
• Hinman, Peter G. (1978). पुनरावर्तन-सैद्धांतिक पदानुक्रम. Perspectives in Mathematical Logic. Springer-Verlag.

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

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

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

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