क्रमिक विश्लेषण

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

इतिहास

क्रमसूचक विश्लेषण के क्षेत्र का निर्माण तब हुआ जब 1934 में गेरहार्ड जेंटजन ने आधुनिक शब्दों में यह साबित करने के लिए कटौती उन्मूलन का इस्तेमाल किया कि पीनो अंकगणित का प्रूफ-थ्योरिटिक ऑर्डिनल एप्सिलॉन संख्या (गणित) है|ε₀. जेंटजन का कंसिस्टेंसी प्रूफ देखें।

परिभाषा

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

ऐसे सिद्धांत का प्रमाण-सैद्धांतिक क्रम $T$ सभी क्रमसूचक संकेतन के क्रम प्रकारों का सर्वोच्च है (अनिवार्य रूप से पुनरावर्ती क्रमसूचक, अगला खंड देखें) जो सिद्धांत सिद्ध कर सकता है कि वे अच्छी तरह से स्थापित संबंध हैं - सभी क्रमसूचकों का सर्वोच्च $\alpha$ जिसके लिए एक क्लेन ओ|नोटेशन मौजूद है $o$ क्लेन के अर्थ में ऐसा है $T$ यह साबित करता है $o$ एक क्रमिक संकेतन है। समान रूप से, यह सभी अध्यादेशों का सर्वोच्च है $\alpha$ जैसे कि एक संगणनीय समारोह मौजूद है $R$ पर $\omega$ (प्राकृतिक संख्याओं का समुच्चय) जो इसे क्रमसूचक के साथ व्यवस्थित करता है $\alpha$ और ऐसा है $T$ के लिए अंकगणितीय कथनों का ट्रांसफिनिट इंडक्शन साबित करता है $R$.

साधारण अंकन

कुछ सिद्धांतों, जैसे कि दूसरे क्रम के अंकगणित के उप-प्रणालियों के पास ट्रांसफिनिट ऑर्डर के बारे में तर्क देने का कोई अवधारणा या तरीका नहीं है। उदाहरण के लिए, Z के सबसिस्टम के लिए इसका क्या अर्थ है, इसे औपचारिक रूप देने के लिए₂ $T$ साबित करना $\alpha$ सुव्यवस्थित , हम इसके बजाय एक क्रमसूचक संकेतन का निर्माण करते हैं $(A,{\tilde {<}})$ आदेश प्रकार के साथ $\alpha$. $T$ अब विभिन्न ट्रांसफिनिट इंडक्शन सिद्धांतों के साथ काम कर सकते हैं $(A,{\tilde {<}})$, जो सेट-सैद्धांतिक अध्यादेशों के बारे में तर्क के लिए स्थानापन्न करता है।

हालाँकि, कुछ पैथोलॉजिकल नोटेशन सिस्टम मौजूद हैं जिनके साथ काम करना अप्रत्याशित रूप से कठिन है। उदाहरण के लिए, राथजेन एक आदिम पुनरावर्ती संकेतन प्रणाली देता है $(\mathbb {N} ,<_{T})$ यह अच्छी तरह से स्थापित है अगर पीए सुसंगत है, आदेश प्रकार होने के बावजूद $\omega$ - पीए के क्रमिक विश्लेषण में इस तरह के अंकन को शामिल करने से झूठी समानता होगी ${\mathsf {PTO(PA)}}=\omega$.

ऊपरी बाध्य

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

उदाहरण

सिद्धांत-सिद्धांत क्रमसूचक ω के साथ सिद्धांत

• क्यू, रॉबिन्सन अंकगणित (हालांकि इस तरह के कमजोर सिद्धांतों के लिए सबूत-सैद्धांतिक क्रमसूचक की परिभाषा को बदलना होगा).
• कुंआ^– , एक विवेकपूर्ण रूप से आदेशित रिंग के गैर-नकारात्मक भाग का प्रथम-क्रम सिद्धांत।

सिद्धांत-सिद्धांत क्रमसूचक ω के साथ सिद्धांत²

• RFA, अल्पविकसित कार्य अंकगणित।
• मैं₀, Δ पर प्रेरण के साथ अंकगणित₀-बिना किसी स्वयंसिद्ध के भविष्यवाणी करता है कि घातांक कुल है।

सिद्धांत-सिद्धांत क्रमसूचक ω के साथ सिद्धांत³

• ईएफए, प्रारंभिक कार्य अंकगणित।
• मैं₀ + ऍक्स्प, Δ पर प्रेरण के साथ अंकगणित₀-एक एक्सिओम द्वारा संवर्धित विधेय जो यह दावा करता है कि घातांक कुल है।
• आरसीए^*
  ₀, ईएफए का दूसरा क्रम रूप कभी-कभी रिवर्स गणित में प्रयोग किया जाता है।
• डब्ल्यूकेएल^*
  ₀, ईएफए का दूसरा क्रम रूप कभी-कभी रिवर्स गणित में प्रयोग किया जाता है।

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

सिद्धांत-सिद्धांत क्रमसूचक ω के साथ सिद्धांतⁿ (n = 2, 3, ... ω के लिए)

• पहचान₀ या ईएफए एक स्वयंसिद्ध द्वारा संवर्धित है जो यह सुनिश्चित करता है कि एन-वें स्तर के प्रत्येक तत्व ${\mathcal {E}}^{n}$ ग्रेज़गोर्स्की पदानुक्रम कुल है।

सिद्धांत-सिद्धांत क्रमसूचक ω के साथ सिद्धांत^ओ

• आरसीए₀, दूसरे क्रम का अंकगणित # पुनरावर्ती समझ।
• डब्ल्यूकेएल₀, उलटा गणित#कमजोर कोनिग प्रमेयिका WKL0|कमजोर कोनिग प्रमेयिका।
• PRA, आदिम पुनरावर्ती अंकगणित।
• मैं₁, Σ पर प्रेरण के साथ अंकगणित₁-विधेय।

प्रमाण-सैद्धांतिक क्रमसूचक ε के साथ सिद्धांत₀

• पीए, पियानो अंकगणित (कट एलिमिनेशन का उपयोग करके लोग द्वारा जेंटज़ेन की स्थिरता प्रमाण)।
• एसीए₀, अंकगणितीय समझ।

प्रूफ-सैद्धांतिक क्रमसूचक के साथ सिद्धांत₀

• एटीआर₀, अंकगणितीय ट्रांसफिनिट रिकर्सन।
• मार्टिन-लोफ प्रकार का सिद्धांत मनमाने ढंग से कई परिमित स्तर के ब्रह्मांडों के साथ।

इस क्रमसूचक को कभी-कभी विधेयात्मक सिद्धांतों की ऊपरी सीमा माना जाता है।

प्रूफ-थ्योरिटिक ऑर्डिनल के साथ सिद्धांत बाचमन-हावर्ड ऑर्डिनल

• पहचान₁, पहला बुखोलज़ आईडी पदानुक्रम।
• केपी, कृप्के-प्लेटेक सेट थ्योरी विथ द इनफिनिटी ऑफ इनफिनिटी।
• CZF, Aczel का CZF|रचनात्मक ज़र्मेलो-फ्रेंकेल सेट सिद्धांत।
• ईओएन, सोलोमन फेफरमैन की स्पष्ट गणित प्रणाली टी का एक कमजोर संस्करण₀.

Kripke-Platek या CZF सेट सिद्धांत सभी उपसमुच्चयों के सेट के रूप में दिए गए पूर्ण पावरसेट के लिए सिद्धांतों के बिना कमजोर सेट सिद्धांत हैं। इसके बजाय, वे या तो प्रतिबंधित पृथक्करण और नए सेटों के गठन के स्वयंसिद्ध हैं, या वे उन्हें बड़े संबंधों से अलग करने के बजाय कुछ फ़ंक्शन रिक्त स्थान (घातांक) का अस्तित्व प्रदान करते हैं।

बड़े प्रमाण-सैद्धांतिक अध्यादेशों के साथ सिद्धांत

Unsolved problem in mathematics:

What is the proof-theoretic ordinal of full second-order arithmetic?

(more unsolved problems in mathematics)

• $\Pi _{1}^{1}{\mbox{-}}{\mathsf {CA}}_{0}$, दूसरा क्रम अंकगणित | Π₁¹ समझ में एक बड़ा प्रमाण-सैद्धांतिक क्रमसूचक है, जिसे ताकुती द्वारा क्रमसूचक आरेखों के संदर्भ में वर्णित किया गया था, और जो Psi0(Omega omega)|ψ से घिरा हुआ है₀(ओह_ω) बुखोल्ज़ के अंकन में। का भी क्रम है $ID_{<\omega }$, परिमित रूप से पुनरावृत्त आगमनात्मक परिभाषाओं का सिद्धांत। और अनुक्रमित W-प्रकार के साथ MLW, मार्टिन-लोफ प्रकार सिद्धांत का क्रम भी Setzer (2004).
• पहचान_ω, बुखोल्ज़ की आईडी पदानुक्रम | ω-पुनरावृत्त आगमनात्मक परिभाषाओं का सिद्धांत। इसका प्रमाण-सैद्धांतिक क्रमसूचक Takeuti-Feferman-Buchholz ordinal | Takeuti-Feferman-Buchholz ordinal के बराबर है।
• टी₀, फेफ़रमैन की स्पष्ट गणित की रचनात्मक प्रणाली में एक बड़ा प्रूफ-सैद्धांतिक क्रमसूचक है, जो KPi का प्रूफ-सैद्धांतिक क्रमसूचक भी है, क्रिप्के-प्लेटेक सेट सिद्धांत पुनरावृत्त स्वीकार्यता के साथ और $\Sigma _{2}^{1}{\mbox{-}}{\mathsf {AC}}+{\mathsf {BI}}$.
• केपीआई, एक स्वीकार्य क्रमसूचक पर आधारित क्रिप्के-प्लेटेक सेट सिद्धांत का एक विस्तार है, जिसमें एक बहुत बड़ा प्रमाण-सैद्धांतिक क्रमसूचक है $\psi (\varepsilon _{I+1})$ जैगर और पोहलर्स के 1983 के पेपर में वर्णित है, जहां I सबसे छोटा दुर्गम है। यह क्रमसूचक भी प्रमाण-सैद्धांतिक क्रमसूचक है $\Delta _{2}^{1}{\mbox{-}}{\mathsf {CA}}+{\mathsf {BI}}$.
• केपीएम, एक स्वीकार्य क्रमसूचक पर आधारित क्रिप्के-प्लेटेक सेट सिद्धांत का एक विस्तार है, जिसका एक बहुत बड़ा प्रमाण-सैद्धांतिक क्रमसूचक θ है, जिसे इसके द्वारा वर्णित किया गया था Rathjen (1990).
• एमएलएम, एक महलो-ब्रह्मांड द्वारा मार्टिन-लोफ प्रकार के सिद्धांत का एक विस्तार, एक और भी बड़ा प्रमाण-सैद्धांतिक क्रमसूचक ψ है_{Ω1</ उप> (ओहM + ω).}
• ${\mathsf {KP}}+\Pi _{3}-Ref$ के बराबर एक सबूत-सैद्धांतिक क्रमसूचक है $\Psi (\varepsilon _{K+1})$, कहाँ $K$ राथजेन के साई फ़ंक्शन का उपयोग करते हुए पहले कमजोर कॉम्पैक्ट को संदर्भित करता है
• ${\mathsf {KP}}+\Pi _{\omega }-Ref$ के बराबर एक सबूत-सैद्धांतिक क्रमसूचक है $\Psi _{X}^{\varepsilon _{\Xi +1}}$, कहाँ $\Xi$ पहले को संदर्भित करता है $\Pi _{0}^{2}$-अवर्णनीय और $\mathbb {X} =(\omega ^{+};P_{0};\epsilon ,\epsilon ,0)$, स्टीगर्ट के साई फ़ंक्शन का उपयोग करके।
• ${\mathsf {Stability}}$ के बराबर एक सबूत-सैद्धांतिक क्रमसूचक है $\Psi _{\mathbb {X} }^{\varepsilon _{\Upsilon +1}}$ कहाँ $\Upsilon$ कम से कम क्रमसूचक का एक कार्डिनल एनालॉग है $\alpha$ जो है $\alpha +\beta$- सभी के लिए स्थिर $\beta <\alpha$ और $\mathbb {X} =(\omega ^{+};P_{0};\epsilon ,\epsilon ,0)$, स्टीगर्ट के साई फ़ंक्शन का उपयोग करके।

प्राकृतिक संख्याओं के पावर सेट का वर्णन करने में सक्षम अधिकांश सिद्धांतों में सबूत-सैद्धांतिक अध्यादेश हैं जो इतने बड़े हैं कि अभी तक कोई स्पष्ट संयोजक विवरण नहीं दिया गया है। यह भी शामिल है $\Pi _{2}^{1}-CA_{0}$, पूरे दूसरे क्रम का अंकगणित ($\Pi _{\infty }^{1}-CA_{0}$) और ज़र्मेलो-फ्रेंकेल सेट थ्योरी और ZFC सहित पॉवरसेट के साथ सिद्धांतों को सेट करें। अंतर्ज्ञानवादी तर्क ZF (IZF) की ताकत ZF के बराबर है।

क्रमिक विश्लेषण की तालिका

Table of proof-theoretic ordinals

Ordinal	First-order arithmetic	Second-order arithmetic	Kripke-Platek set theory	Type theory	Constructive set theory	Explicit mathematics
$\omega$	${\mathsf {Q}}$, ${\mathsf {PA}}^{-}$
$\omega ^{2}$	${\mathsf {RFA}}$, ${\mathsf {I\Delta }}_{0}$
$\omega ^{3}$	${\mathsf {EFA}}$, ${\mathsf {I\Delta }}_{0}^{\mathsf {+}}$	${\mathsf {RCA}}_{0}^{*}$, ${\mathsf {WKL}}_{0}^{*}$
$\omega ^{n}$	${\mathsf {EFA}}^{\mathsf {n}}$, ${\mathsf {I\Delta }}_{0}^{\mathsf {n+}}$
$\omega ^{\omega }$	${\mathsf {PRA}}$, ${\mathsf {I\Sigma }}_{1}$	${\mathsf {RCA}}_{0}$, ${\mathsf {WKL}}_{0}$		${\mathsf {CPRC}}$
$\varepsilon _{0}$	${\mathsf {PA}}$	${\mathsf {ACA}}_{0}$, ${\mathsf {\Delta }}_{1}^{1}{\mathsf {-CA}}_{0}$, ${\mathsf {\Sigma }}_{1}^{1}{\mathsf {-AC}}_{0}$				${\mathsf {EM}}_{0}$
$\varepsilon _{\varepsilon _{0}}$		${\mathsf {ACA}}$
$\varphi (\omega ,0)$	${\mathsf {ID}}_{1}\#$	${\mathsf {\Delta }}_{1}^{1}{\mathsf {-CR}}$				${\mathsf {EM}}_{0}{\mathsf {+JR}}$
$\varphi (\varepsilon _{0},0)$	${\widehat {\mathsf {ID}}}_{1}$	${\mathsf {\Delta }}_{1}^{1}{\mathsf {-CA}}$, ${\mathsf {\Sigma }}_{1}^{1}{\mathsf {-AC}}$		${\mathsf {ML}}_{1}$		${\mathsf {EM}}_{0}{\mathsf {+J}}$
$\varphi ({\mathsf {<}}\Omega ,0)$	${\mathsf {Aut(ID\#)}}$
$\Gamma _{0}$	${\widehat {\mathsf {ID}}}_{<\omega }$, ${\mathsf {U(PA)}}$	${\mathsf {ATR}}_{0}$, ${\mathsf {\Delta }}_{1}^{1}{\mathsf {-CA+BR}}$	${\mathsf {KPi}}^{0}$	${\mathsf {ML}}_{<\omega }$, ${\mathsf {MLU}}$
$\Gamma _{\omega }$			${\mathsf {KPI}}^{0}{\mathsf {+\Sigma _{1}-I}}_{\omega }$
$\Gamma _{\varepsilon _{0}}$	${\widehat {\mathsf {ID}}}_{\omega }$	${\mathsf {ATR}}$	${\mathsf {KPI}}^{0}{\mathsf {+F-I}}_{\omega }$
$\varphi (1,\omega ,0)$	${\widehat {\mathsf {ID}}}_{<\omega ^{\omega }}$	${\mathsf {ATR}}_{0}+({\mathsf {\Sigma }}_{1}^{1}{\mathsf {-DC}})$	${\mathsf {KPi}}^{0}{\mathsf {+\Sigma _{1}-I}}_{\omega }$
$\varphi (1,\varepsilon _{0},0)$	${\widehat {\mathsf {ID}}}_{<\varepsilon _{0}}$	${\mathsf {ATR}}+({\mathsf {\Sigma }}_{1}^{1}{\mathsf {-DC}})$	${\mathsf {KPi}}^{0}{\mathsf {+F-I}}_{\omega }$
$\varphi (1,\Gamma _{0},0)$	${\widehat {\mathsf {ID}}}_{<\Gamma _{0}}$			${\mathsf {MLS}}$
$\varphi (2,0,0)$	${\mathsf {Aut({\widehat {ID}})}}$		${\mathsf {KPh}}^{0}$	${\mathsf {Aut(ML)}}$
$\varphi (\omega ,0,0)$			${\mathsf {KPM}}^{0}$
$\psi _{0}(\Omega _{2})$	${\mathsf {ID}}_{1}$		${\mathsf {KP}}$, ${\mathsf {KP\omega }}$	${\mathsf {ML}}_{1}{\mathsf {V}}$	${\mathsf {CZF}}$	${\mathsf {EON}}$
$\psi _{0}(\Gamma _{\Omega +1})$	${\mathsf {U(ID}}_{1}{\mathsf {)}}$
$\psi _{0}(\varphi ({\mathsf {<}}\Omega ,0,\Omega +1))$	${\mathsf {Aut(U(ID))}}$
$\psi _{0}(\Omega _{\omega })$	${\mathsf {ID}}_{<\omega }$	${\mathsf {\Pi }}_{1}^{1}{\mathsf {-CA}}_{0}$, ${\mathsf {\Delta }}_{2}^{1}{\mathsf {-CA}}_{0}$		${\mathsf {MLW}}$
$\psi _{0}(\Omega _{\omega }\varepsilon _{0})$	${\mathsf {W-ID}}_{\omega }$	${\mathsf {\Pi }}_{1}^{1}{\mathsf {-CA}}$	${\mathsf {W-KPI}}$
$\psi _{0}(\Omega _{\omega +1})$	${\mathsf {ID}}_{\omega }$	${\mathsf {\Pi }}_{1}^{1}{\mathsf {-CA+BI}}$	${\mathsf {KPI}}$
$\psi _{\Omega }(\varepsilon _{K+1})$			${\mathsf {KP\Pi }}_{3}$
$\psi _{0}(\Omega _{\omega ^{\omega }})$	${\mathsf {ID}}_{<\omega ^{\omega }}$	${\mathsf {\Delta }}_{2}^{1}{\mathsf {-CR}}$
$\psi _{0}(\Omega _{\varepsilon _{0}})$	${\mathsf {ID}}_{<\varepsilon _{0}}$	${\mathsf {\Delta }}_{2}^{1}{\mathsf {-CA}}$, ${\mathsf {\Sigma }}_{2}^{1}{\mathsf {-AC}}$	${\mathsf {W-KPi}}$
$\psi _{0}(\Omega _{\Omega })$	${\mathsf {Aut(ID)}}$
$\psi (\varepsilon _{I+1})$		${\mathsf {\Delta }}_{2}^{1}{\mathsf {-CA+BI}}$, ${\mathsf {\Sigma }}_{2}^{1}{\mathsf {-AC+BI}}$	${\mathsf {KPi}}$		${\mathsf {CZF+REA}}$	${\mathsf {T}}_{0}$
$\psi (\Omega _{I+\omega })$				${\mathsf {ML}}_{1}{\mathsf {W}}$
$\psi (\Omega _{L})$			${\mathsf {KPh}}$	${\mathsf {ML}}_{<\omega }{\mathsf {W}}$
$\psi (\Omega _{L^{*}})$				${\mathsf {Aut(MLW)}}$
$\psi _{\Omega }(\chi _{\varepsilon _{M+1}}(0))$		${\mathsf {\Delta }}_{2}^{1}{\mathsf {-CA+BI+(M)}}$	${\mathsf {KPM}}$		${\mathsf {CZFM}}$
$\psi (\Omega _{M+\omega })$			${\mathsf {KPM}}^{+}$	${\mathsf {MLM}}$
$\Psi (\varepsilon _{K+1})$			${\mathsf {KP+\Pi }}_{3}-{\mathsf {Ref}}$
$\Psi _{(\omega ^{+};P_{0},\epsilon ,\epsilon ,0)}^{\varepsilon _{\Xi +1}}$			${\mathsf {KP+\Pi }}_{\omega }-{\mathsf {Ref}}$
$\Psi _{(\omega ^{+};P_{0},\epsilon ,\epsilon ,0)}^{\varepsilon _{\Upsilon +1}}$			${\mathsf {Stability}}$
$\psi _{\omega _{1}^{CK}}(\varepsilon _{\mathbb {I} +1})$		$\Sigma _{3}^{1}{\mathsf {-DC+BI}}$	${\mathsf {KP+\Pi }}_{1}{\mathsf {-collection}}$

कुंजी

यह इस तालिका में प्रयुक्त प्रतीकों की एक सूची है:

• ψ Buchholz psi फ़ंक्शंस का प्रतिनिधित्व करता है | Buchholz का psi जब तक अन्यथा न कहा गया हो।
• Ψ या तो राथजेन या स्टीगर्ट के साई का प्रतिनिधित्व करता है।
• φ वेब्लेन के कार्य का प्रतिनिधित्व करता है।
• ω पहले ट्रांसफिनिट ऑर्डिनल का प्रतिनिधित्व करता है।
• ε_α एप्सिलॉन संख्या (गणित) का प्रतिनिधित्व करता है।
• जी_α गामा संख्या का प्रतिनिधित्व करता है (Γ₀ फ़ेफ़रमैन-शुट्टे क्रमसूचक है)
• Ω_α बेशुमार अध्यादेशों का प्रतिनिधित्व करते हैं (Ω₁, संक्षिप्त Ω, पहला बेशुमार क्रमसूचक है|ω₁).

यह इस तालिका में प्रयुक्त संक्षिप्त रूपों की एक सूची है:

• प्रथम क्रम अंकगणित
  • ${\mathsf {Q}}$ रॉबिन्सन अंकगणित है
  • ${\mathsf {PA}}^{-}$ विवेकपूर्ण रूप से आदेशित रिंग के गैर-नकारात्मक भाग का प्रथम-क्रम सिद्धांत है।
  • ${\mathsf {RFA}}$ जेन्सेन पदानुक्रम अंकगणित है।
  • ${\mathsf {I\Delta }}_{0}$ Δ तक सीमित प्रेरण के साथ अंकगणितीय है₀-बिना किसी स्वयंसिद्ध के भविष्यवाणी करता है कि घातांक कुल है।
  • ${\mathsf {EFA}}$ प्राथमिक कार्य अंकगणितीय है।
  • ${\mathsf {I\Delta }}_{0}^{\mathsf {+}}$ Δ तक सीमित प्रेरण के साथ अंकगणितीय है₀-एक एक्सिओम द्वारा संवर्धित विधेय जो यह दावा करता है कि घातांक कुल है।
  • ${\mathsf {EFA}}^{\mathsf {n}}$ प्राथमिक कार्य अंकगणित एक स्वयंसिद्ध द्वारा संवर्धित है जो यह सुनिश्चित करता है कि n-वें स्तर का प्रत्येक तत्व ${\mathcal {E}}^{n}$ ग्रेज़गोर्स्की पदानुक्रम कुल है।
  • ${\mathsf {I\Delta }}_{0}^{\mathsf {n+}}$ है ${\mathsf {I\Delta }}_{0}^{\mathsf {+}}$ एक स्वयंसिद्ध द्वारा संवर्धित यह सुनिश्चित करता है कि n-वें स्तर का प्रत्येक तत्व ${\mathcal {E}}^{n}$ ग्रेज़गोर्स्की पदानुक्रम कुल है।
  • ${\mathsf {PRA}}$ आदिम पुनरावर्ती अंकगणित है।
  • ${\mathsf {I\Sigma }}_{1}$ Σ तक सीमित प्रेरण के साथ अंकगणितीय है₁-विधेय।
  • ${\mathsf {PA}}$ पीआनो अभिगृहीत है।
  • ${\mathsf {ID}}_{\nu }\#$ है ${\widehat {\mathsf {ID}}}_{\nu }$ लेकिन केवल सकारात्मक सूत्रों के लिए प्रेरण के साथ।
  • ${\widehat {\mathsf {ID}}}_{\nu }$ मोनोटोन ऑपरेटरों के ν पुनरावृत्त निश्चित बिंदुओं द्वारा PA का विस्तार करता है।
  • ${\mathsf {U(PA)}}$ वास्तव में प्रथम-क्रम अंकगणितीय प्रणाली नहीं है, लेकिन प्राकृतिक संख्याओं के आधार पर भविष्यवाणिय तर्क द्वारा प्राप्त की जा सकने वाली चीज़ों को कैप्चर करता है।
  • ${\mathsf {Aut({\widehat {ID}})}}$ पर एक automorphism है ${\widehat {\mathsf {ID}}}_{\nu }$.
  • ${\mathsf {ID}}_{\nu }$ मोनोटोन ऑपरेटरों के ν पुनरावृत्त कम से कम निश्चित बिंदुओं द्वारा PA का विस्तार करता है।
  • ${\mathsf {U(ID}}_{\nu }{\mathsf {)}}$ वास्तव में एक प्रथम-क्रम अंकगणितीय प्रणाली नहीं है, लेकिन ν-बार पुनरावृत्त सामान्यीकृत आगमनात्मक परिभाषाओं के आधार पर विधेय तर्क द्वारा प्राप्त किया जा सकता है।
  • ${\mathsf {Aut(U(ID))}}$ पर एक ऑटोमोर्फिज्म है ${\mathsf {U(ID}}_{\nu }{\mathsf {)}}$.
  • ${\mathsf {W-ID}}_{\nu }$ का कमजोर संस्करण है ${\mathsf {ID}}_{\nu }$ डब्ल्यू प्रकार के आधार पर।
• दूसरे क्रम का अंकगणित
  • ${\mathsf {RCA}}_{0}^{*}$ का दूसरा क्रम रूप है ${\mathsf {EFA}}$ कभी-कभी रिवर्स गणित में प्रयोग किया जाता है।
  • ${\mathsf {WKL}}_{0}^{*}$ का दूसरा क्रम रूप है ${\mathsf {EFA}}$ कभी-कभी रिवर्स गणित में प्रयोग किया जाता है।
  • ${\mathsf {RCA}}_{0}$ दूसरे क्रम का अंकगणित # पुनरावर्ती समझ है।
  • ${\mathsf {WKL}}_{0}$ उलटा गणित है#कमजोर कोनिग प्रमेयिका WKL0|कमजोर कोनिग प्रमेयिका।
  • ${\mathsf {ACA}}_{0}$ द्वितीय क्रम अंकगणित # अंकगणितीय समझ है।
  • ${\mathsf {ACA}}$ है ${\mathsf {ACA}}_{0}$ साथ ही पूर्ण द्वितीय-क्रम प्रेरण योजना।
  • ${\mathsf {ATR}}_{0}$ उलटा गणित है #अंकगणितीय ट्रांसफिनिट रिकर्सन ATR0.
  • ${\mathsf {ATR}}$ है ${\mathsf {ATR}}_{0}$ साथ ही पूर्ण द्वितीय-क्रम प्रेरण योजना।
  • ${\mathsf {\Delta }}_{2}^{1}{\mathsf {-CA+BI+(M)}}$ है ${\mathsf {\Delta }}_{2}^{1}{\mathsf {-CA+BI}}$ साथ ही दावा हर सच है ${\mathsf {\Pi }}_{3}^{1}$-मानकों के साथ वाक्य एक (गणनीय कोडित) में होता है $\beta$-का मॉडल ${\mathsf {\Delta }}_{2}^{1}{\mathsf {-CA}}$.
• कृपके-प्लेटक समुच्चय सिद्धांत
  • ${\mathsf {KP}}$ Kripke-Platek सेट सिद्धांत है | अनंत के स्वयंसिद्ध के साथ Kripke-Platek सेट सिद्धांत।
  • ${\mathsf {KP\omega }}$ क्रिप्के-प्लेटेक समुच्चय सिद्धांत है, जिसका ब्रह्माण्ड एक स्वीकार्य समुच्चय है $\omega$.
  • ${\mathsf {W-KPI}}$ का कमजोर संस्करण है ${\mathsf {KPI}}$ डब्ल्यू प्रकार के आधार पर।
  • ${\mathsf {KPI}}$ दावा करता है कि ब्रह्मांड स्वीकार्य सेट की एक सीमा है।
  • ${\mathsf {W-KPi}}$ का कमजोर संस्करण है ${\mathsf {KPi}}$ डब्ल्यू प्रकार के आधार पर।
  • ${\mathsf {KPi}}$ दावा करता है कि ब्रह्मांड अप्राप्य सेट है।
  • ${\mathsf {KPh}}$ दावा करता है कि ब्रह्मांड अति दुर्गम है: एक दुर्गम सेट और दुर्गम सेट की एक सीमा।
  • ${\mathsf {KPM}}$ दावा करता है कि ब्रह्मांड एक महलो सेट है।
  • ${\mathsf {KP+\Pi }}_{\mathsf {n}}-{\mathsf {Ref}}$ है ${\mathsf {KP}}$ एक निश्चित प्रथम-क्रम प्रतिबिंब योजना द्वारा संवर्धित।
  • ${\mathsf {Stability}}$ KPi स्वयंसिद्ध द्वारा संवर्धित है $\forall \alpha \exists \kappa \geq \alpha (L_{\kappa }\preceq _{1}L_{\kappa +\alpha })$.
  • ${\mathsf {KPM}}^{+}$ क्या KPI को कम से कम एक पुनरावर्ती महलो क्रमसूचक अस्तित्व के दावे से संवर्धित किया गया है।

एक सुपरस्क्रिप्ट शून्य इंगित करता है कि $\in$-इंडक्शन को हटा दिया जाता है (सिद्धांत को काफी कमजोर बना दिया जाता है)।

• सिद्धांत टाइप करें
  • ${\mathsf {CPRC}}$ प्रिमिटिव रिकर्सिव कंस्ट्रक्शन का हर्बेलिन-पेटी कैलकुलस है।
  • ${\mathsf {ML}}_{\mathsf {n}}$ प्रकार सिद्धांत बिना डब्ल्यू-प्रकार और साथ है $n$ ब्रह्मांड।
  • ${\mathsf {ML}}_{<\omega }$ डब्ल्यू-टाइप के बिना टाइप थ्योरी है और बहुत सारे ब्रह्मांडों के साथ है।
  • ${\mathsf {MLU}}$ एक अगले ब्रह्मांड ऑपरेटर के साथ टाइप थ्योरी है।
  • ${\mathsf {MLS}}$ डब्ल्यू-प्रकार के बिना और एक सुपरयूनिवर्स के साथ टाइप थ्योरी है।
  • ${\mathsf {Aut(ML)}}$ डब्ल्यू-प्रकार के बिना टाइप थ्योरी पर एक ऑटोमोर्फिज्म है।
  • ${\mathsf {ML}}_{1}{\mathsf {V}}$ एक ब्रह्माण्ड वाला प्रकार सिद्धांत है और Aczel के पुनरावृत्त सेट का प्रकार है।
  • ${\mathsf {MLW}}$ इंडेक्स्ड W-टाइप्स के साथ टाइप थ्योरी है।
  • ${\mathsf {ML}}_{1}{\mathsf {W}}$ डब्ल्यू-प्रकार और एक ब्रह्मांड के साथ टाइप थ्योरी है।
  • ${\mathsf {ML}}_{<\omega }{\mathsf {W}}$ डब्ल्यू-प्रकार और अंततः कई ब्रह्मांडों के साथ प्रकार सिद्धांत है।
  • ${\mathsf {Aut(MLW)}}$ डब्ल्यू-प्रकार के साथ प्रकार सिद्धांत पर एक ऑटोमोर्फिज्म है।
  • ${\mathsf {MLM}}$ Mahlo ब्रह्मांड के साथ प्रकार सिद्धांत है।
• रचनात्मक सेट सिद्धांत
  • ${\mathsf {CZF}}$ Aczel का रचनात्मक समुच्चय सिद्धांत है।
  • ${\mathsf {CZF+REA}}$ है ${\mathsf {CZF}}$ प्लस नियमित विस्तार स्वयंसिद्ध।
  • ${\mathsf {CZF+REA+FZ}}_{2}$ है ${\mathsf {CZF+REA}}$ साथ ही फुल-सेकंड ऑर्डर इंडक्शन स्कीम।
  • ${\mathsf {CZFM}}$ है ${\mathsf {CZF}}$ महलो ब्रह्मांड के साथ।
• स्पष्ट गणित
  • ${\mathsf {EM}}_{0}$ बुनियादी स्पष्ट गणित और प्राथमिक समझ है
  • ${\mathsf {EM}}_{0}{\mathsf {+JR}}$ है ${\mathsf {EM}}_{0}$ प्लस नियम में शामिल हों
  • ${\mathsf {EM}}_{0}{\mathsf {+J}}$ है ${\mathsf {EM}}_{0}$ प्लस स्वयंसिद्धों में शामिल हों
  • ${\mathsf {EON}}$ सोलोमन फेफ़रमैन का एक कमजोर रूप है ${\mathsf {T}}_{0}$.
  • ${\mathsf {T}}_{0}$ है ${\mathsf {EM}}_{0}{\mathsf {+J+IG}}$, कहाँ ${\mathsf {IG}}$ आगमनात्मक पीढ़ी है।
  • ${\mathsf {T}}$ है ${\mathsf {EM}}_{0}{\mathsf {+J+IG+FZ}}_{2}$, कहाँ ${\mathsf {FZ}}_{2}$ पूर्ण द्वितीय क्रम प्रेरण योजना है।

यह भी देखें

• समानता
• बड़ी कार्डिनल संपत्ति
• फ़ेफ़रमैन-शुट्टे क्रमसूचक
• बछमन-हावर्ड ऑर्डिनल
• जटिलता वर्ग
• Gentzen's कंसिस्टेंसी प्रूफ

टिप्पणियाँ

1.^ For $1<n\leq \omega$

2.^ The Veblen function $\varphi$ with countably infinitely iterated least fixed points.

3.^ Can also be commonly written as $\psi (\varepsilon _{\Omega +1})$ in Madore's ψ.

4.^ Uses Madore's ψ rather than Buchholz's ψ.

5.^ Can also be commonly written as $\psi (\varepsilon _{\Omega _{\omega }+1})$ in Madore's ψ.

6.^ $K$ represents the first recursively weakly compact ordinal. Uses Arai's ψ rather than Buchholz's ψ.

7.^ Also the proof-theoretic ordinal of ${\mathsf {Aut(W-ID)}}$, as the amount of weakening given by the W-types is not enough.

8.^ $I$ represents the first inaccessible cardinal. Uses Jäger's ψ rather than Buchholz's ψ.

9.^ $L$ represents the limit of the $\omega$-inaccessible cardinals. Uses (presumably) Jäger's ψ.

10.^ $L^{*}$represents the limit of the $\Omega$-inaccessible cardinals. Uses (presumably) Jäger's ψ.

11.^ $M$ represents the first Mahlo cardinal. Uses Rathjen's ψ rather than Buchholz's ψ.

12.^ $K$ represents the first weakly compact cardinal. Uses Rathjen's Ψ rather than Buchholz's ψ.

13.^ $\Xi$ represents the first $\Pi _{0}^{2}$-indescribable cardinal. Uses Stegert's Ψ rather than Buchholz's ψ.

14.^ $Y$ is the smallest $\alpha$ such that $\forall \theta <Y\exists \kappa <Y($'$\kappa$ is $\theta$-indescribable') and $\forall \theta <Y\forall \kappa <Y($'$\kappa$ is $\theta$-indescribable $\rightarrow \theta <\kappa$'). Uses Stegert's Ψ rather than Buchholz's ψ.

15.^ $M$ represents the first Mahlo cardinal. Uses (presumably) Rathjen's ψ.

संदर्भ

• Buchholz, W.; Feferman, S.; Pohlers, W.; Sieg, W. (1981), Iterated inductive definitions and sub-systems of analysis, Lecture Notes in Math., vol. 897, Berlin: Springer-Verlag, doi:10.1007/BFb0091894, ISBN 978-3-540-11170-2
• Pohlers, Wolfram (1989), Proof theory, Lecture Notes in Mathematics, vol. 1407, Berlin: Springer-Verlag, doi:10.1007/978-3-540-46825-7, ISBN 3-540-51842-8, MR 1026933
• Pohlers, Wolfram (1998), "Set Theory and Second Order Number Theory", Handbook of Proof Theory, Studies in Logic and the Foundations of Mathematics, vol. 137, Amsterdam: Elsevier Science B. V., pp. 210–335, doi:10.1016/S0049-237X(98)80019-0, ISBN 0-444-89840-9, MR 1640328
• Rathjen, Michael (1990), "Ordinal notations based on a weakly Mahlo cardinal.", Arch. Math. Logic, 29 (4): 249–263, doi:10.1007/BF01651328, MR 1062729, S2CID 14125063
• Rathjen, Michael (2006), "The art of ordinal analysis" (PDF), International Congress of Mathematicians, vol. II, Zürich: Eur. Math. Soc., pp. 45–69, MR 2275588, archived from the original on 2009-12-22{{citation}}: CS1 maint: bot: original URL status unknown (link)
• Rose, H.E. (1984), Subrecursion. Functions and Hierarchies, Oxford logic guides, vol. 9, Oxford, New York: Clarendon Press, Oxford University Press
• Schütte, Kurt (1977), Proof theory, Grundlehren der Mathematischen Wissenschaften, vol. 225, Berlin-New York: Springer-Verlag, pp. xii+299, ISBN 3-540-07911-4, MR 0505313
• Setzer, Anton (2004), "Proof theory of Martin-Löf type theory. An Overview", Mathématiques et Sciences Humaines. Mathematics and Social Sciences (165): 59–99
• Takeuti, Gaisi (1987), Proof theory, Studies in Logic and the Foundations of Mathematics, vol. 81 (Second ed.), Amsterdam: North-Holland Publishing Co., ISBN 0-444-87943-9, MR 0882549