हाइपरअरिथमेटिकल सिद्धांत: Difference between revisions

Latest revision as of 21:50, 9 February 2023

पुनरावर्तन सिद्धांत में, हाइपरअरिथमेटिक सिद्धांत ट्यूरिंग कम्प्यूटेबिलिटी का सामान्यीकरण है। इसका दूसरे क्रम के अंकगणित में निश्चितता के साथ घनिष्ठ संबंध है और क्रिपके-प्लेटक समुच्चय सिद्धांत जैसे समुच्चय सिद्धांत की कमजोर प्रणालियों के साथ है। प्रभावी वर्णनात्मक समुच्चय सिद्धांत में यह महत्वपूर्ण उपकरण है।^[1]

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

हाइपरअरिथमेटिकल समुच्चय और निश्चितता

हाइपरअरिथमेटिक समुच्चय की पहली परिभाषा विश्लेषणात्मक पदानुक्रम का उपयोग करती है।

प्राकृतिक संख्याओं के समूह को स्तर $\Sigma _{1}^{1}$ पर वर्गीकृत किया जाता है। इस पदानुक्रम के यदि यह दूसरे क्रम अंकगणितीय के सूत्र द्वारा परिभाषित किया जा सकता है, जिसमें केवल अस्तित्वगत समुच्चय क्वांटिफायर और कोई अन्य समुच्चय क्वांटिफायर नहीं है। समुच्चय को स्तर $\Pi _{1}^{1}$ पर वर्गीकृत किया जाता है और विश्लेषणात्मक पदानुक्रम की यदि यह केवल सार्वभौमिक समुच्चय क्वांटिफायर के साथ दूसरे क्रम अंकगणितीय के सूत्र द्वारा परिभाषित है और कोई अन्य समुच्चय क्वांटिफायर नहीं है। समुच्चय $\Delta _{1}^{1}$ है यदि यह $\Sigma _{1}^{1}$ और $\Pi _{1}^{1}$ दोनों है। हाइपरअरिथमेटिकल समुच्चय बिल्कुल $\Delta _{1}^{1}$ समुच्चय वही हैं।

हाइपरअरिथमेटिकल समुच्चय और पुनरावृत्त ट्यूरिंग जंप: हाइपरअरिथमेटिकल पदानुक्रम

हाइपरअरिथमेटिकल समुच्चय की परिभाषा $\Delta _{1}^{1}$ कम्प्यूटेबिलिटी परिणामों पर सीधे निर्भर नहीं करता है। दूसरी, समतुल्य, परिभाषा से पता चलता है कि हाइपरारिथमेटिकल समुच्चय को असीम रूप से पुनरावृत्त ट्यूरिंग कूदो का उपयोग करके परिभाषित किया जा सकता है। यह दूसरी परिभाषा यह भी दर्शाती है कि हाइपरअरिथमेटिकल समुच्चय को अंकगणितीय पदानुक्रम का विस्तार करने वाले पदानुक्रम में वर्गीकृत किया जा सकता है; हाइपरअरिथमेटिकल समुच्चय बिल्कुल ऐसे समुच्चय होते हैं, जिन्हें इस पदानुक्रम में रैंक दिया जाता है।

हाइपरअरिथमेटिकल पदानुक्रम के प्रत्येक स्तर को गणनीय क्रमिक संख्या (क्रमिक) द्वारा अनुक्रमित किया जाता है, किन्तु सभी गणनीय क्रमांक पदानुक्रम के स्तर के अनुरूप नहीं होते हैं। पदानुक्रम द्वारा उपयोग किए जाने वाले क्रमसूचक क्रमसूचक संकेतन वाले हैं, जो क्रमसूचक का ठोस, प्रभावी वर्णन है।

क्रमसूचक संकेतन प्राकृतिक संख्या द्वारा गणनीय क्रमसूचक का प्रभावी वर्णन है। हाइपरअरिथमेटिक पदानुक्रम को परिभाषित करने के लिए क्रमिक अंकन की प्रणाली की आवश्यकता होती है। मौलिक गुण क्रमसूचक संकेतन के पास होना चाहिए कि यह प्रभावी विधि से छोटे अध्यादेशों के संदर्भ में क्रमसूचक का वर्णन करता है। निम्नलिखित आगमनात्मक परिभाषा विशिष्ट है; यह युग्मन समारोह का उपयोग करता है $\langle \cdot ,\cdot \rangle$ .

संख्या 0 क्रमसूचक 0 के लिए अंकन है।
यदि n क्रमिक λ के लिए अंकन है तो $\langle 1,n\rangle$ λ + 1 के लिए अंकन है;
मान लीजिए कि δ सीमा क्रमसूचक है। δ के लिए अंकन रूप $\langle 2,e\rangle$ का संख्या है, जहां e कुल गणना योग्य फ़ंक्शन $\phi _{e}$ का सूचकांक है जैसे कि प्रत्येक n के लिए, $\phi _{e}(n)$ क्रमसूचक λ_n के लिए अंकन है δ से कम और δ समुच्चय $\{\lambda _{n}\mid n\in \mathbb {N} \}$ का सर्वोच्च है.

यह सीमा क्रमसूचकों के लिए केवल अंकन के अतिरिक्त सभी स्तरों पर प्रभावी जुड़ाव लेकर भी परिभाषित किया जा सकता है।^[2]

केवल गिने-चुने क्रमसूचक संकेतन हैं, क्योंकि प्रत्येक अंकन प्राकृतिक संख्या है; इस प्रकार गणनीय क्रमसूचक है जो अंकन वाले सभी अध्यादेशों का सर्वोच्च है। इस अध्यादेश को चर्च-क्लीन क्रमसूचक के रूप में जाना जाता है और इसे $\omega _{1}^{CK}$ निरूपित किया जाता है। ध्यान दें कि यह क्रम अभी भी गणनीय है, प्रतीक केवल पहले अनंत क्रमसूचक $\omega _{1}$ के साथ सादृश्य है, और सभी प्राकृतिक संख्याओं का समुच्चय जो क्रमसूचक संकेतन हैं, जिसे ${\mathcal {O}}$ निरूपित किया जाता है और क्लेन ${\mathcal {O}}$ के नाम से जाना जाता है।

पुनरावृत्त ट्यूरिंग कूदों को परिभाषित करने के लिए क्रमिक नोटेशन का उपयोग किया जाता है। पदानुक्रम को परिभाषित करने के लिए प्रयुक्त प्राकृतिक संख्याओं के समुच्चय हैं, $0^{(\delta )}$ प्रत्येक के लिए $\delta <\omega _{1}^{CK}$ . $0^{(\delta )}$ कभी-कभी $H(\delta )$ ,^[3] या $H_{e}$ अंकन के लिए $e$ के लिए $\delta$ द्वारा निरूपित भी किया जाता है।^[2] मान लीजिए कि δ का अंकन e है। इन समुच्चयों को सबसे पहले डेविस (1950) और मोस्टोव्स्की (1951) द्वारा परिभाषित किया गया था।^[2] समुच्चय $0^{(\delta )}$ e का उपयोग करके निम्नानुसार परिभाषित किया गया है।

यदि δ = 0 तो $0^{(\delta )}=0$ खाली समुच्चय है।
यदि δ = λ + 1 तब $0^{(\delta )}$ की ट्यूरिंग छलांग $0^{(\lambda )}$ है समुच्चय $0^{(1)}$ और $0^{(2)}$ क्रमश $0'$ और $0''$ हैं।
यदि δ सीमा क्रमसूचक है, तो $\langle \lambda _{n}\mid n\in \mathbb {N} \rangle$ संकेतन e द्वारा दिए गए δ से कम अध्यादेशों का क्रम हो। समुच्चय $0^{(\delta )}$ नियम $0^{(\delta )}=\{\langle n,i\rangle \mid i\in 0^{(\lambda _{n})}\}$ द्वारा दिया जाता है। यह समुच्चयों $0^{(\lambda _{n})}$ का प्रभावी जोड़ है।

चूंकि का निर्माण $0^{(\delta )}$ δ के लिए निश्चित अंकन होने पर निर्भर करता है, और प्रत्येक अनंत क्रमसूचक में कई अंकन होते हैं, स्पेक्टर के प्रमेय से पता चलता है कि ट्यूरिंग डिग्री डिग्री $0^{(\delta )}$ केवल δ पर निर्भर करता है, विशेष अंकन पर नहीं, और इस प्रकार $0^{(\delta )}$ ट्यूरिंग डिग्री तक अच्छी तरह से परिभाषित है।^[2]

हाइपरारिथमेटिकल पदानुक्रम को इन पुनरावृत्त ट्यूरिंग जंप से परिभाषित किया गया है। प्राकृतिक संख्याओं के समुच्चय X को $\delta <\omega _{1}^{CK}$ के लिए हाइपरारिथमेटिकल पदानुक्रम के स्तर δ पर वर्गीकृत किया गया है, यदि X $0^{(\delta )}$ के लिए ट्यूरिंग रिड्यूसिबल है। यदि कोई है तो हमेशा ऐसा कम से कम δ होगा; यह कम से कम δ है जो X की अगणनीयता के स्तर को मापता है।

हाइपरअरिथमेटिकल समुच्चय और उच्च प्रकार में रिकर्सन

हाइपरारिथमेटिकल समुच्चय का तीसरा लक्षण वर्णन, क्लेन के कारण, प्रकार सिद्धांत का उपयोग करता है। उच्च-प्रकार के कंप्यूटेबल फ़ंक्शंस। टाइप -2 कार्यात्मक ${}^{2}E\colon \mathbb {N} ^{\mathbb {N} }\to \mathbb {N}$ निम्नलिखित नियमों द्वारा परिभाषित किया गया है:

{}^{2}E(f)=1\quad

यदि कोई ऐसा i है कि f(i) > 0,

{}^{2}E(f)=0\quad

यदि ऐसा कोई i नहीं है कि f(i) > 0.

टाइप-2 कार्यात्मक के सापेक्ष कम्प्यूटेबिलिटी की त्रुटिहीन परिभाषा का उपयोग करते हुए, क्लेन ने दिखाया कि प्राकृतिक संख्याओं का समुच्चय हाइपरअरिथमेटिकल है यदि और केवल यदि यह ${}^{2}E$ के सापेक्ष गणना योग्य है।

उदाहरण: अंकगणित का सत्य समुच्चय

प्रत्येक अंकगणितीय समुच्चय हाइपरअरिथमेटिकल है, किन्तु कई अन्य हाइपररिथमेटिकल समुच्चय हैं। हाइपरअरिथमेटिकल, गैर-अंकगणितीय समुच्चय का उदाहरण पीनो सिद्धांतों के सूत्रों के गोडेल संख्याओं का समुच्चय है, जो मानक $\mathbb {N}$ प्राकृतिक संख्याओं में सत्य है। समुच्चय T समुच्चय में $0^{(\omega )}$ ट्यूरिंग कमी है, और इसलिए हाइपरअरिथमेटिकल पदानुक्रम में उच्च नहीं है, चूंकि यह तर्स्की की अनिश्चितता प्रमेय द्वारा अंकगणितीय रूप से निश्चित नहीं है।

मौलिक परिणाम

हाइपरअरिथमेटिक सिद्धांत के मौलिक परिणाम बताते हैं कि ऊपर दी गई तीन परिभाषाएँ प्राकृतिक संख्याओं के समुच्चय के समान संग्रह को परिभाषित करती हैं। ये समानताएं क्लेन के कारण हैं।

पूर्णता परिणाम भी सिद्धांत के लिए मौलिक हैं। प्राकृतिक संख्याओं $\Pi _{1}^{1}$ का समुच्चय है, यदि यह स्तर $\Pi _{1}^{1}$ पर है तो पूर्ण करें। विश्लेषणात्मक पदानुक्रम और हर $\Pi _{1}^{1}$ प्राकृत संख्याओं का समुच्चय अनेक-अपचयन है | अनेक-अपचयन योग्य है। a की परिभाषा $\Pi _{1}^{1}$ बायर स्थान का पूर्ण उपसमुच्चय ( $\mathbb {N} ^{\mathbb {N} }$ ) समान है। हाइपरअरिथमेटिक सिद्धांत से जुड़े कई समुच्चय $\Pi _{1}^{1}$ पूर्ण हैं:

क्लेन का ${\mathcal {O}}$ , प्राकृतिक संख्याओं का समुच्चय जो क्रमिक संख्याओं के लिए अंकन है।
प्राकृत संख्याओं का समुच्चय e ऐसा है कि संगणनीय फलन $\phi _{e}(x,y)$ प्राकृतिक संख्याओं के सुव्यवस्थित क्रम के अभिलाक्षणिक फलन की गणना करता है। ये पुनरावर्ती क्रमसूचक के सूचक हैं।
बेयर अंतरिक्ष के तत्वों का समुच्चय जो प्राकृतिक संख्याओं के सुव्यवस्थित क्रम के विशिष्ट कार्य (प्रभावी समरूपता $\mathbb {N} ^{\mathbb {N} }\cong \mathbb {N} ^{\mathbb {N} \times \mathbb {N} }$ का उपयोग करके) है।

इन पूर्णता परिणामों से परिणाम $\Sigma _{1}^{1}$ बाउंडिंग फॉलो के रूप में जाना जाता है। क्रमसूचक संकेतन किसी भी $\Sigma _{1}^{1}$ समुच्चय S के लिय, $\alpha <\omega _{1}^{CK}$ होता है जैसे कि S का प्रत्येक तत्व $\alpha$ क्रमसूचक से कम के लिए संकेतन होता है। किसी के लिए $\Sigma _{1}^{1}$ बायर स्पेस का सबसमुच्चय T केवल अच्छी तरह से ऑर्डरिंग के विशिष्ट कार्यों से युक्त है, $\alpha <\omega _{1}^{CK}$ है, जैसे कि T में $\alpha$ दर्शाया गया प्रत्येक क्रमांक इससे कम है।

रिलेटिवाइज़्ड हाइपरअरिथमेटिकिटी और हाइपरडिग्री

की परिभाषा ${\mathcal {O}}$ प्राकृतिक संख्याओं के समुच्चय X से सापेक्षित किया जा सकता है: क्रमसूचक संकेतन की परिभाषा में, सीमा अध्यादेशों के लिए खंड बदल दिया जाता है ताकि क्रमसूचक संकेतन के अनुक्रम की संगणनीय गणना को X को दैवज्ञ के रूप में उपयोग करने की अनुमति दी जा सके। संख्याओं का वह समूह जो X के सापेक्ष क्रमिक अंकन हैं, जिसे ${\mathcal {O}}^{X}$ द्वारा निरूपित किया जाता है, और ${\mathcal {O}}^{X}$ में दर्शाए गए अध्यादेशों के सर्वोच्च को $\omega _{1}^{X}$ द्वारा निरूपित किया जाता है; यह गणनीय क्रमसूचक है जो $\omega _{1}^{CK}$ इससे छोटा नहीं है।

$0^{(\delta )}$ को प्राकृतिक संख्याओं के स्वैच्छिक समुच्चय $X$ से भी जोड़ा जा सकता है। परिभाषा में केवल यही परिवर्तन है कि $X^{(0)}$ खाली समुच्चय के अतिरिक्त X के रूप में परिभाषित किया गया है, ताकि $X^{(1)}=X'$ X का ट्यूरिंग जंप है, और इसी तरह आगे भी होता है। $\omega _{1}^{CK}$ पर समाप्त होने के अतिरिक्त X के सापेक्ष पदानुक्रम $\omega _{1}^{X}$ सभी अध्यादेशों से कम चलता है।

हाइपरारिथमेटिकल रिड्यूसबिलिटी को परिभाषित करने के लिए सापेक्षित हाइपरअरिथमेटिकल पदानुक्रम का उपयोग किया जाता है। दिए गए समुच्चय X और Y, हम कहते हैं $X\leq _{HYP}Y$ यदि और केवल यदि वहाँ $\delta <\omega _{1}^{Y}$ है, जैसे कि X, $Y^{(\delta )}$ के लिय ट्यूरिंग रिड्यूसिबल है. यदि $X\leq _{HYP}Y$ और $Y\leq _{HYP}X$ फिर अंकन $X\equiv _{HYP}Y$ X और Y को निरुपित करने के लिए 'हाइपररिथमेटिकली समतुल्य' का प्रयोग किया जाता है। यह ट्यूरिंग रिडक्शन की तुलना में मोटे समकक्ष संबंध है; उदाहरण के लिए, प्राकृतिक संख्याओं का प्रत्येक समुच्चय हाइपरअरिथमेटिक रूप से इसके ट्यूरिंग जंप के बराबर है, किन्तु ट्यूरिंग इसके ट्यूरिंग जंप के बराबर नहीं है। हाइपरअरिथमेटिकल तुल्यता के तुल्यता वर्गों को 'हाइपरडिग्री' के रूप में जाना जाता है।

वह फ़ंक्शन जो समुच्चय X को ${\mathcal {O}}^{X}$ पर ले जाता है, और उसे ट्यूरिंग जंप के अनुरूप हाइपरजंप के रूप में जाना जाता है। हाइपरजंप और हाइपरडिग्री के कई गुण स्थापित किए गए हैं। विशेष रूप से, यह ज्ञात है कि हाइपरडिग्री के लिए पोस्ट की समस्या का सकारात्मक उत्तर है: प्राकृतिक संख्याओं के प्रत्येक समुच्चय X के लिए प्राकृतिक संख्याओं का समुच्चय Y होता है जैसे कि $X<_{HYP}Y<_{HYP}{\mathcal {O}}^{X}$ .

सामान्यीकरण

हाइपरअरिथमेटिकल सिद्धांत को अल्फा पुनरावर्तन सिद्धांत α-रिकर्सन सिद्धांत द्वारा सामान्यीकृत किया जाता है, जो स्वीकार्य अध्यादेशों के निश्चित उपसमुच्चय का अध्ययन है। हाइपरारिथमेटिकल सिद्धांत विशेष स्थिति है जिसमें α $\omega _{1}^{CK}$ है.

अन्य पदानुक्रमों से संबंध

Lightface		Boldface
Σ⁰ ₀ = Π⁰ ₀ = Δ⁰ ₀ (sometimes the same as Δ⁰ ₁)		Σ⁰ ₀ = Π⁰ ₀ = Δ⁰ ₀ (if defined)
Δ⁰ ₁ = recursive		Δ⁰ ₁ = clopen
Σ⁰ ₁ = recursively enumerable	Π⁰ ₁ = co-recursively enumerable	Σ⁰ ₁ = G = open	Π⁰ ₁ = F = closed
Δ⁰ ₂		Δ⁰ ₂
Σ⁰ ₂	Π⁰ ₂	Σ⁰ ₂ = F_σ	Π⁰ ₂ = G_δ
Δ⁰ ₃		Δ⁰ ₃
Σ⁰ ₃	Π⁰ ₃	Σ⁰ ₃ = G_δσ	Π⁰ ₃ = F_σδ
⋮		⋮
Σ⁰ _<ω = Π⁰ _<ω = Δ⁰ _<ω = Σ¹ ₀ = Π¹ ₀ = Δ¹ ₀ = arithmetical		Σ⁰ _<ω = Π⁰ _<ω = Δ⁰ _<ω = Σ¹ ₀ = Π¹ ₀ = Δ¹ ₀ = boldface arithmetical
⋮		⋮
Δ⁰ _α (α recursive)		Δ⁰ _α (α countable)
Σ⁰ _α	Π⁰ _α	Σ⁰ _α	Π⁰ _α
⋮		⋮
Σ⁰ _ω^CK ₁ = Π⁰ _ω^CK ₁ = Δ⁰ _ω^CK ₁ = Δ¹ ₁ = hyperarithmetical		Σ⁰ _ω₁ = Π⁰ _ω₁ = Δ⁰ _ω₁ = Δ¹ ₁ = B = Borel
Σ¹ ₁ = lightface analytic	Π¹ ₁ = lightface coanalytic	Σ¹ ₁ = A = analytic	Π¹ ₁ = CA = coanalytic
Δ¹ ₂		Δ¹ ₂
Σ¹ ₂	Π¹ ₂	Σ¹ ₂ = PCA	Π¹ ₂ = CPCA
Δ¹ ₃		Δ¹ ₃
Σ¹ ₃	Π¹ ₃	Σ¹ ₃ = PCPCA	Π¹ ₃ = CPCPCA
⋮		⋮
Σ¹ _<ω = Π¹ _<ω = Δ¹ _<ω = Σ² ₀ = Π² ₀ = Δ² ₀ = analytical		Σ¹ _<ω = Π¹ _<ω = Δ¹ _<ω = Σ² ₀ = Π² ₀ = Δ² ₀ = P = projective
⋮		⋮

संदर्भ

H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
G. Sacks, 1990. Higher Recursion Theory, Springer-Verlag. ISBN 3-540-19305-7
S. Simpson, 1999. Subsystems of Second Order Arithmetic, Springer-Verlag.
C. J. Ash, J. F. Knight, 2000. Computable Structures and the Hyperarithmetical Hierarchy, Elsevier. ISBN 0-444-50072-3

↑ https://www.uni-muenster.de/imperia/md/content/logik/Skripte/pohlers._computability_theory_of_hyperarithmetical_sets.pdf^{[bare URL PDF]}
↑ ^2.0 ^2.1 ^2.2 ^2.3 S. G. Simpson, The Hierarchy Based on the Jump Operator, pp.268--269. The Kleene Symposium (North-Holland, 1980)
↑ C. J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Studies in Logic and the Foundation of Mathematics, 2000), ch. 5

बाहरी संबंध

Descriptive set theory. Notes by David Marker, University of Illinois at Chicago. 2002.
Mathematical Logic II. Notes by Dag Normann, The University of Oslo. 2005.
Antonio Montalbán: University of California, Berkeley and YouTube content creator

[1] ttps://www.uni-muenster.de/imperia/md/content/logik/Skripte/pohlers._computability_theory_of_hyperarithmetical_sets.pdf^{[bare URL PDF]}

[Simpson80-2] 2.0 ^2.1 ^2.2 ^2.3 S. G. Simpson, The Hierarchy Based on the Jump Operator, pp.268--269. The Kleene Symposium (North-Holland, 1980)

[3] C. J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Studies in Logic and the Foundation of Mathematics, 2000), ch. 5

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
-[[पुनरावर्तन सिद्धांत]] में, हाइपरअरिथमेटिक सिद्धांत [[संगणनीय समारोह|ट्यूरिंग कम्प्यूटेबिलिटी]] का एक सामान्यीकरण है। इसका दूसरे क्रम के अंकगणित में निश्चितता के साथ घनिष्ठ संबंध है और क्रिपके-प्लेटक सेट सिद्धांत जैसे सेट सिद्धांत की कमजोर प्रणालियों के साथ है। [[प्रभावी वर्णनात्मक सेट सिद्धांत]] में यह एक महत्वपूर्ण उपकरण है।<ref>https://www.uni-muenster.de/imperia/md/content/logik/Skripte/pohlers._computability_theory_of_hyperarithmetical_sets.pdf {{Bare URL PDF|date=June 2022}}</ref>
+[[पुनरावर्तन सिद्धांत]] में, हाइपरअरिथमेटिक सिद्धांत [[संगणनीय समारोह|ट्यूरिंग कम्प्यूटेबिलिटी]] का सामान्यीकरण है। इसका दूसरे क्रम के अंकगणित में निश्चितता के साथ घनिष्ठ संबंध है और क्रिपके-प्लेटक समुच्चय सिद्धांत जैसे समुच्चय सिद्धांत की कमजोर प्रणालियों के साथ है। [[प्रभावी वर्णनात्मक सेट सिद्धांत|प्रभावी वर्णनात्मक समुच्चय सिद्धांत]] में यह महत्वपूर्ण उपकरण है।<ref>https://www.uni-muenster.de/imperia/md/content/logik/Skripte/pohlers._computability_theory_of_hyperarithmetical_sets.pdf {{Bare URL PDF|date=June 2022}}</ref>
-हाइपरअरिथमेटिक सिद्धांत का केंद्रीय ध्यान [[प्राकृतिक संख्या]]ओं का सेट है जिसे हाइपरअरिथमेटिक सेट के रूप में जाना जाता है। समुच्चयों के इस वर्ग को परिभाषित करने के तीन समतुल्य तरीके हैं; इन विभिन्न परिभाषाओं के बीच संबंधों का अध्ययन हाइपरअरिथमेटिकल सिद्धांत के अध्ययन के लिए एक प्रेरणा है।
+हाइपरअरिथमेटिक सिद्धांत का केंद्रीय ध्यान [[प्राकृतिक संख्या]]ओं का समुच्चय है जिसे हाइपरअरिथमेटिक समुच्चय के रूप में जाना जाता है। समुच्चयों के इस वर्ग को परिभाषित करने के तीन समतुल्य विधि हैं; इन विभिन्न परिभाषाओं के बीच संबंधों का अध्ययन हाइपरअरिथमेटिकल सिद्धांत के अध्ययन के लिए प्रेरणा है।
-== हाइपरअरिथमेटिकल सेट और निश्चितता ==
+== हाइपरअरिथमेटिकल समुच्चय और निश्चितता ==
-हाइपरअरिथमेटिक सेट की पहली परिभाषा [[विश्लेषणात्मक पदानुक्रम]] का उपयोग करती है।
+हाइपरअरिथमेटिक समुच्चय की पहली परिभाषा [[विश्लेषणात्मक पदानुक्रम]] का उपयोग करती है।
-प्राकृतिक संख्याओं के एक समूह को स्तर <math>\Sigma^1_1</math> पर वर्गीकृत किया जाता है  इस पदानुक्रम के अगर यह दूसरे क्रम अंकगणितीय के एक सूत्र द्वारा परिभाषित किया जा सकता है जिसमें केवल अस्तित्वगत सेट क्वांटिफायर और कोई अन्य सेट क्वांटिफायर नहीं है। एक सेट को स्तर <math>\Pi^1_1</math> पर वर्गीकृत किया जाता है और विश्लेषणात्मक पदानुक्रम की अगर यह केवल सार्वभौमिक सेट क्वांटिफायर के साथ दूसरे क्रम अंकगणितीय के सूत्र द्वारा परिभाषित है और कोई अन्य सेट क्वांटिफायर नहीं है। एक सेट <math>\Delta^1_1</math> है अगर यह <math>\Sigma^1_1</math> और <math>\Pi^1_1</math> दोनों है। हाइपरअरिथमेटिकल सेट बिल्कुल <math>\Delta^1_1</math> सेट वही हैं।
+प्राकृतिक संख्याओं के समूह को स्तर <math>\Sigma^1_1</math> पर वर्गीकृत किया जाता है। इस पदानुक्रम के यदि यह दूसरे क्रम अंकगणितीय के सूत्र द्वारा परिभाषित किया जा सकता है, जिसमें केवल अस्तित्वगत समुच्चय क्वांटिफायर और कोई अन्य समुच्चय क्वांटिफायर नहीं है। समुच्चय को स्तर <math>\Pi^1_1</math> पर वर्गीकृत किया जाता है और विश्लेषणात्मक पदानुक्रम की यदि यह केवल सार्वभौमिक समुच्चय क्वांटिफायर के साथ दूसरे क्रम अंकगणितीय के सूत्र द्वारा परिभाषित है और कोई अन्य समुच्चय क्वांटिफायर नहीं है। समुच्चय <math>\Delta^1_1</math> है यदि यह <math>\Sigma^1_1</math> और <math>\Pi^1_1</math> दोनों है। हाइपरअरिथमेटिकल समुच्चय बिल्कुल <math>\Delta^1_1</math> समुच्चय वही हैं।
-== हाइपरअरिथमेटिकल सेट और पुनरावृत्त ट्यूरिंग जंप: हाइपरअरिथमेटिकल पदानुक्रम ==
+== हाइपरअरिथमेटिकल समुच्चय और पुनरावृत्त ट्यूरिंग जंप: हाइपरअरिथमेटिकल पदानुक्रम ==
-हाइपरअरिथमेटिकल सेट की परिभाषा <math>\Delta^1_1</math> कम्प्यूटेबिलिटी परिणामों पर सीधे निर्भर नहीं करता है। एक दूसरी, समतुल्य, परिभाषा से पता चलता है कि हाइपरारिथमेटिकल सेट को असीम रूप से पुनरावृत्त [[ट्यूरिंग कूदो]] का उपयोग करके परिभाषित किया जा सकता है। यह दूसरी परिभाषा यह भी दर्शाती है कि हाइपरअरिथमेटिकल सेट को [[अंकगणितीय पदानुक्रम]] का विस्तार करने वाले पदानुक्रम में वर्गीकृत किया जा सकता है; हाइपरअरिथमेटिकल सेट बिल्कुल ऐसे सेट होते हैं जिन्हें इस पदानुक्रम में रैंक दिया जाता है।
+हाइपरअरिथमेटिकल समुच्चय की परिभाषा <math>\Delta^1_1</math> कम्प्यूटेबिलिटी परिणामों पर सीधे निर्भर नहीं करता है। दूसरी, समतुल्य, परिभाषा से पता चलता है कि हाइपरारिथमेटिकल समुच्चय को असीम रूप से पुनरावृत्त [[ट्यूरिंग कूदो]] का उपयोग करके परिभाषित किया जा सकता है। यह दूसरी परिभाषा यह भी दर्शाती है कि हाइपरअरिथमेटिकल समुच्चय को [[अंकगणितीय पदानुक्रम]] का विस्तार करने वाले पदानुक्रम में वर्गीकृत किया जा सकता है; हाइपरअरिथमेटिकल समुच्चय बिल्कुल ऐसे समुच्चय होते हैं, जिन्हें इस पदानुक्रम में रैंक दिया जाता है।
-हाइपरअरिथमेटिकल पदानुक्रम के प्रत्येक स्तर को एक गणनीय क्रमिक संख्या (क्रमिक) द्वारा अनुक्रमित किया जाता है, लेकिन सभी गणनीय क्रमांक पदानुक्रम के स्तर के अनुरूप नहीं होते हैं। पदानुक्रम द्वारा उपयोग किए जाने वाले क्रमसूचक [[क्रमसूचक संकेतन]] वाले हैं, जो क्रमसूचक का एक ठोस, प्रभावी वर्णन है।
+हाइपरअरिथमेटिकल पदानुक्रम के प्रत्येक स्तर को गणनीय क्रमिक संख्या (क्रमिक) द्वारा अनुक्रमित किया जाता है, किन्तु सभी गणनीय क्रमांक पदानुक्रम के स्तर के अनुरूप नहीं होते हैं। पदानुक्रम द्वारा उपयोग किए जाने वाले क्रमसूचक [[क्रमसूचक संकेतन]] वाले हैं, जो क्रमसूचक का ठोस, प्रभावी वर्णन है।
-एक क्रमसूचक संकेतन एक प्राकृतिक संख्या द्वारा एक गणनीय क्रमसूचक का एक प्रभावी वर्णन है। हाइपरअरिथमेटिक पदानुक्रम को परिभाषित करने के लिए क्रमिक अंकन की एक प्रणाली की आवश्यकता होती है। मौलिक गुण एक क्रमसूचक संकेतन के पास होना चाहिए कि यह एक प्रभावी तरीके से छोटे अध्यादेशों के संदर्भ में क्रमसूचक का वर्णन करता है। निम्नलिखित आगमनात्मक परिभाषा विशिष्ट है; यह एक [[युग्मन समारोह]] का उपयोग करता है <math>\langle \cdot , \cdot\rangle</math>.
+क्रमसूचक संकेतन प्राकृतिक संख्या द्वारा गणनीय क्रमसूचक का प्रभावी वर्णन है। हाइपरअरिथमेटिक पदानुक्रम को परिभाषित करने के लिए क्रमिक अंकन की प्रणाली की आवश्यकता होती है। मौलिक गुण क्रमसूचक संकेतन के पास होना चाहिए कि यह प्रभावी विधि से छोटे अध्यादेशों के संदर्भ में क्रमसूचक का वर्णन करता है। निम्नलिखित आगमनात्मक परिभाषा विशिष्ट है; यह [[युग्मन समारोह]] का उपयोग करता है <math>\langle \cdot , \cdot\rangle</math>.
-* संख्या 0 क्रमसूचक 0 के लिए एक अंकन है।
+* संख्या 0 क्रमसूचक 0 के लिए अंकन है।
-* यदि n एक क्रमिक λ के लिए एक अंकन है तो <math>\langle 1, n \rangle</math> λ + 1 के लिए एक अंकन है;
+* यदि n क्रमिक λ के लिए अंकन है तो <math>\langle 1, n \rangle</math> λ + 1 के लिए अंकन है;
-* मान लीजिए कि δ एक सीमा क्रमसूचक है। δ के लिए एक अंकन रूप <math>\langle 2, e\rangle</math> का एक नंबर है, जहां e कुल गणना योग्य फ़ंक्शन <math>\phi_e</math> का सूचकांक है जैसे कि प्रत्येक n के लिए, <math>\phi_e(n)</math> एक क्रमसूचक λ<sub>n</sub> के लिए एक अंकन है δ से कम और δ समुच्चय <math>\{ \lambda_n \mid n \in \mathbb{N}\}</math> का सर्वोच्च है .
+* मान लीजिए कि δ सीमा क्रमसूचक है। δ के लिए अंकन रूप <math>\langle 2, e\rangle</math> का संख्या है, जहां e कुल गणना योग्य फ़ंक्शन <math>\phi_e</math> का सूचकांक है जैसे कि प्रत्येक n के लिए, <math>\phi_e(n)</math> क्रमसूचक λ<sub>n</sub> के लिए अंकन है δ से कम और δ समुच्चय <math>\{ \lambda_n \mid n \in \mathbb{N}\}</math> का सर्वोच्च है.
-यह सीमा क्रमसूचकों के लिए केवल अंकन के बजाय सभी स्तरों पर प्रभावी जुड़ाव लेकर भी परिभाषित किया जा सकता है।<ref name="Simpson80">S. G. Simpson, [http://personal.psu.edu/t20/papers/jump-hierarchy-1980.pdf The Hierarchy Based on the Jump Operator], pp.268--269. ''The Kleene Symposium'' (North-Holland, 1980)</ref>
+यह सीमा क्रमसूचकों के लिए केवल अंकन के अतिरिक्त सभी स्तरों पर प्रभावी जुड़ाव लेकर भी परिभाषित किया जा सकता है।<ref name="Simpson80">S. G. Simpson, [http://personal.psu.edu/t20/papers/jump-hierarchy-1980.pdf The Hierarchy Based on the Jump Operator], pp.268--269. ''The Kleene Symposium'' (North-Holland, 1980)</ref>
-केवल गिने-चुने क्रमसूचक संकेतन हैं, क्योंकि प्रत्येक अंकन एक प्राकृतिक संख्या है; इस प्रकार एक गणनीय क्रमसूचक है जो एक अंकन वाले सभी अध्यादेशों का सर्वोच्च है। इस अध्यादेश को चर्च-क्लीन क्रमसूचक के रूप में जाना जाता है और इसे <math>\omega^{CK}_1</math> निरूपित किया जाता है। ध्यान दें कि यह क्रम अभी भी गणनीय है, प्रतीक केवल पहले बेशुमार क्रमसूचक <math>\omega_{1}</math> के साथ एक सादृश्य है, और सभी प्राकृतिक संख्याओं का समुच्चय जो क्रमसूचक संकेतन हैं जिसे <math>\mathcal{O}</math> निरूपित किया जाता है और क्लेन <math>\mathcal{O}</math> के नाम से जाना जाता है।
+केवल गिने-चुने क्रमसूचक संकेतन हैं, क्योंकि प्रत्येक अंकन प्राकृतिक संख्या है; इस प्रकार गणनीय क्रमसूचक है जो अंकन वाले सभी अध्यादेशों का सर्वोच्च है। इस अध्यादेश को चर्च-क्लीन क्रमसूचक के रूप में जाना जाता है और इसे <math>\omega^{CK}_1</math> निरूपित किया जाता है। ध्यान दें कि यह क्रम अभी भी गणनीय है, प्रतीक केवल पहले अनंत क्रमसूचक <math>\omega_{1}</math> के साथ सादृश्य है, और सभी प्राकृतिक संख्याओं का समुच्चय जो क्रमसूचक संकेतन हैं, जिसे <math>\mathcal{O}</math> निरूपित किया जाता है और क्लेन <math>\mathcal{O}</math> के नाम से जाना जाता है।
-पुनरावृत्त ट्यूरिंग कूदों को परिभाषित करने के लिए क्रमिक नोटेशन का उपयोग किया जाता है। पदानुक्रम को परिभाषित करने के लिए प्रयुक्त प्राकृतिक संख्याओं के समुच्चय हैं <math>0^{(\delta)}</math> प्रत्येक के लिए <math>\delta < \omega^{CK}_1</math>. <math>0^{(\delta)}</math> कभी-कभी <math>H(\delta)</math> निरूपित भी किया जाता है,<ref>C. J. Ash, J. Knight, ''Computable Structures and the Hyperarithmetical Hierarchy'' (Studies in Logic and the Foundation of Mathematics, 2000), ch. 5</ref> या <math>H_e</math> एक अंकन के लिए <math>e</math> के लिए <math>\delta</math>.<ref name="Simpson80" />मान लीजिए कि δ का अंकन e है। इन सेटों को सबसे पहले डेविस (1950) और मोस्टोव्स्की (1951) द्वारा परिभाषित किया गया था।<ref name="Simpson80" /> सेट <math>0^{(\delta)}</math> e का उपयोग करके निम्नानुसार परिभाषित किया गया है।
+पुनरावृत्त ट्यूरिंग कूदों को परिभाषित करने के लिए क्रमिक नोटेशन का उपयोग किया जाता है। पदानुक्रम को परिभाषित करने के लिए प्रयुक्त प्राकृतिक संख्याओं के समुच्चय हैं, <math>0^{(\delta)}</math> प्रत्येक के लिए <math>\delta < \omega^{CK}_1</math>. <math>0^{(\delta)}</math> कभी-कभी <math>H(\delta)</math>,<ref>C. J. Ash, J. Knight, ''Computable Structures and the Hyperarithmetical Hierarchy'' (Studies in Logic and the Foundation of Mathematics, 2000), ch. 5</ref> या <math>H_e</math> अंकन के लिए <math>e</math> के लिए <math>\delta</math> द्वारा निरूपित भी किया जाता है।<ref name="Simpson80" /> मान लीजिए कि δ का अंकन e है। इन समुच्चयों को सबसे पहले डेविस (1950) और मोस्टोव्स्की (1951) द्वारा परिभाषित किया गया था।<ref name="Simpson80" /> समुच्चय <math>0^{(\delta)}</math> e का उपयोग करके निम्नानुसार परिभाषित किया गया है।
-* यदि δ = 0 तो <math>0^{(\delta)}= 0</math> खाली सेट है।
+* यदि δ = 0 तो <math>0^{(\delta)}= 0</math> खाली समुच्चय है।
-* यदि δ = λ + 1 तब <math>0^{(\delta)}</math> की ट्यूरिंग छलांग <math>0^{(\lambda)}</math> है सेट <math>0^{(1)}</math> और <math>0^{(2)}</math> क्रमश <math>0'</math> और <math>0''</math>हैं।
+* यदि δ = λ + 1 तब <math>0^{(\delta)}</math> की ट्यूरिंग छलांग <math>0^{(\lambda)}</math> है समुच्चय <math>0^{(1)}</math> और <math>0^{(2)}</math> क्रमश <math>0'</math> और <math>0''</math>हैं।
-* यदि δ एक सीमा क्रमसूचक है, तो <math>\langle \lambda_n \mid n \in \mathbb{N}\rangle</math> संकेतन e द्वारा दिए गए δ से कम अध्यादेशों का क्रम हो। सेट <math>0^{(\delta)}</math> नियम <math>0^{(\delta)} = \{ \langle n,i\rangle \mid i \in 0^{(\lambda_n)}\}</math> द्वारा दिया जाता है. यह समुच्चयों <math>0^{(\lambda_n)}</math> का प्रभावी जोड़ है।
+* यदि δ सीमा क्रमसूचक है, तो <math>\langle \lambda_n \mid n \in \mathbb{N}\rangle</math> संकेतन e द्वारा दिए गए δ से कम अध्यादेशों का क्रम हो। समुच्चय <math>0^{(\delta)}</math> नियम <math>0^{(\delta)} = \{ \langle n,i\rangle \mid i \in 0^{(\lambda_n)}\}</math> द्वारा दिया जाता है। यह समुच्चयों <math>0^{(\lambda_n)}</math> का प्रभावी जोड़ है।
-हालांकि का निर्माण <math>0^{(\delta)}</math> δ के लिए एक निश्चित अंकन होने पर निर्भर करता है, और प्रत्येक अनंत क्रमसूचक में कई अंकन होते हैं, स्पेक्टर के एक प्रमेय से पता चलता है कि [[ट्यूरिंग डिग्री]] डिग्री <math>0^{(\delta)}</math> केवल δ पर निर्भर करता है, विशेष अंकन पर नहीं, और इस प्रकार <math>0^{(\delta)}</math> ट्यूरिंग डिग्री तक अच्छी तरह से परिभाषित है।<ref name="Simpson80" />
+चूंकि का निर्माण <math>0^{(\delta)}</math> δ के लिए निश्चित अंकन होने पर निर्भर करता है, और प्रत्येक अनंत क्रमसूचक में कई अंकन होते हैं, स्पेक्टर के प्रमेय से पता चलता है कि [[ट्यूरिंग डिग्री]] डिग्री <math>0^{(\delta)}</math> केवल δ पर निर्भर करता है, विशेष अंकन पर नहीं, और इस प्रकार <math>0^{(\delta)}</math> ट्यूरिंग डिग्री तक अच्छी तरह से परिभाषित है।<ref name="Simpson80" />
-हाइपरारिथमेटिकल पदानुक्रम को इन पुनरावृत्त ट्यूरिंग जंप से परिभाषित किया गया है। प्राकृतिक संख्याओं के एक सेट X को <math>\delta < \omega^{CK}_1</math> के लिए हाइपरारिथमेटिकल पदानुक्रम के स्तर δ पर वर्गीकृत किया गया है, अगर X <math>0^{(\delta)}</math> के लिए ट्यूरिंग रिड्यूसिबल है। यदि कोई है तो हमेशा ऐसा कम से कम δ होगा; यह कम से कम δ है जो X की अगणनीयता के स्तर को मापता है।
+हाइपरारिथमेटिकल पदानुक्रम को इन पुनरावृत्त ट्यूरिंग जंप से परिभाषित किया गया है। प्राकृतिक संख्याओं के समुच्चय X को <math>\delta < \omega^{CK}_1</math> के लिए हाइपरारिथमेटिकल पदानुक्रम के स्तर δ पर वर्गीकृत किया गया है, यदि X <math>0^{(\delta)}</math> के लिए ट्यूरिंग रिड्यूसिबल है। यदि कोई है तो हमेशा ऐसा कम से कम δ होगा; यह कम से कम δ है जो X की अगणनीयता के स्तर को मापता है।
-== हाइपरअरिथमेटिकल सेट और उच्च प्रकार में रिकर्सन ==
+== हाइपरअरिथमेटिकल समुच्चय और उच्च प्रकार में रिकर्सन ==
-हाइपरारिथमेटिकल सेट का तीसरा लक्षण वर्णन, क्लेन के कारण, [[प्रकार सिद्धांत]] का उपयोग करता है। उच्च-प्रकार के कंप्यूटेबल फ़ंक्शंस। टाइप -2 कार्यात्मक <math>{}^2E\colon \mathbb{N}^{\mathbb{N}} \to \mathbb{N}</math> निम्नलिखित नियमों द्वारा परिभाषित किया गया है:
+हाइपरारिथमेटिकल समुच्चय का तीसरा लक्षण वर्णन, क्लेन के कारण, [[प्रकार सिद्धांत]] का उपयोग करता है। उच्च-प्रकार के कंप्यूटेबल फ़ंक्शंस। टाइप -2 कार्यात्मक <math>{}^2E\colon \mathbb{N}^{\mathbb{N}} \to \mathbb{N}</math> निम्नलिखित नियमों द्वारा परिभाषित किया गया है:
 :<math>{}^2E(f) = 1 \quad</math> यदि कोई ऐसा i है कि f(i) > 0,
 :<math>{}^2E(f) = 0 \quad</math> यदि ऐसा कोई i नहीं है कि f(i) > 0.
-टाइप-2 कार्यात्मक के सापेक्ष कम्प्यूटेबिलिटी की एक सटीक परिभाषा का उपयोग करते हुए, क्लेन ने दिखाया कि प्राकृतिक संख्याओं का एक सेट हाइपरअरिथमेटिकल है यदि और केवल अगर यह <math>{}^2E</math> के सापेक्ष गणना योग्य है.
+टाइप-2 कार्यात्मक के सापेक्ष कम्प्यूटेबिलिटी की त्रुटिहीन परिभाषा का उपयोग करते हुए, क्लेन ने दिखाया कि प्राकृतिक संख्याओं का समुच्चय हाइपरअरिथमेटिकल है यदि और केवल यदि यह <math>{}^2E</math> के सापेक्ष गणना योग्य है।
-== उदाहरण: अंकगणित का सत्य सेट ==
+== उदाहरण: अंकगणित का सत्य समुच्चय ==
-प्रत्येक [[अंकगणितीय सेट]] हाइपरअरिथमेटिकल है, लेकिन कई अन्य हाइपररिथमेटिकल सेट हैं। हाइपरअरिथमेटिकल, गैर-अंकगणितीय सेट का एक उदाहरण पीनो सिद्धांतों के सूत्रों के गोडेल संख्याओं का सेट है जो मानक <math>\mathbb{N}</math> प्राकृतिक संख्याओं में सत्य हैं. सेट T सेट में <math>0^{(\omega)}</math> ट्यूरिंग कमी है, और इसलिए हाइपरअरिथमेटिकल पदानुक्रम में उच्च नहीं है, हालांकि यह तर्स्की की अनिश्चितता प्रमेय द्वारा अंकगणितीय रूप से निश्चित नहीं है।
+प्रत्येक [[अंकगणितीय सेट|अंकगणितीय समुच्चय]] हाइपरअरिथमेटिकल है, किन्तु कई अन्य हाइपररिथमेटिकल समुच्चय हैं। हाइपरअरिथमेटिकल, गैर-अंकगणितीय समुच्चय का उदाहरण पीनो सिद्धांतों के सूत्रों के गोडेल संख्याओं का समुच्चय है, जो मानक <math>\mathbb{N}</math> प्राकृतिक संख्याओं में सत्य है। समुच्चय T समुच्चय में <math>0^{(\omega)}</math> ट्यूरिंग कमी है, और इसलिए हाइपरअरिथमेटिकल पदानुक्रम में उच्च नहीं है, चूंकि यह तर्स्की की अनिश्चितता प्रमेय द्वारा अंकगणितीय रूप से निश्चित नहीं है।
 == मौलिक परिणाम ==
-हाइपरअरिथमेटिक सिद्धांत के मौलिक परिणाम बताते हैं कि ऊपर दी गई तीन परिभाषाएँ प्राकृतिक संख्याओं के सेट के समान संग्रह को परिभाषित करती हैं। ये समानताएं क्लेन के कारण हैं।
+हाइपरअरिथमेटिक सिद्धांत के मौलिक परिणाम बताते हैं कि ऊपर दी गई तीन परिभाषाएँ प्राकृतिक संख्याओं के समुच्चय के समान संग्रह को परिभाषित करती हैं। ये समानताएं क्लेन के कारण हैं।
-पूर्णता परिणाम भी सिद्धांत के लिए मौलिक हैं। प्राकृतिक संख्याओं <math>\Pi^1_1</math> का समुच्चय है, यदि यह स्तर <math>\Pi^1_1</math> पर है तो पूर्ण करें।  विश्लेषणात्मक पदानुक्रम और हर <math>\Pi^1_1</math> प्राकृत संख्याओं का समुच्चय अनेक-एक अपचयन है | अनेक-एक अपचयन योग्य है। a की परिभाषा <math>\Pi^1_1</math> बायर स्थान का पूर्ण उपसमुच्चय (<math>\mathbb{N}^\mathbb{N}</math>) समान है। हाइपरअरिथमेटिक सिद्धांत से जुड़े कई सेट <math>\Pi^1_1</math> पूर्ण हैं:
+पूर्णता परिणाम भी सिद्धांत के लिए मौलिक हैं। प्राकृतिक संख्याओं <math>\Pi^1_1</math> का समुच्चय है, यदि यह स्तर <math>\Pi^1_1</math> पर है तो पूर्ण करें।  विश्लेषणात्मक पदानुक्रम और हर <math>\Pi^1_1</math> प्राकृत संख्याओं का समुच्चय अनेक-अपचयन है | अनेक-अपचयन योग्य है। a की परिभाषा <math>\Pi^1_1</math> बायर स्थान का पूर्ण उपसमुच्चय (<math>\mathbb{N}^\mathbb{N}</math>) समान है। हाइपरअरिथमेटिक सिद्धांत से जुड़े कई समुच्चय <math>\Pi^1_1</math> पूर्ण हैं:
-* क्लेन का <math>\mathcal{O}</math>, प्राकृतिक संख्याओं का समुच्चय जो क्रमिक संख्याओं के लिए अंकन हैं
+* क्लेन का <math>\mathcal{O}</math>, प्राकृतिक संख्याओं का समुच्चय जो क्रमिक संख्याओं के लिए अंकन है।
 * प्राकृत संख्याओं का समुच्चय e ऐसा है कि संगणनीय फलन <math>\phi_e(x,y)</math> प्राकृतिक संख्याओं के सुव्यवस्थित क्रम के अभिलाक्षणिक फलन की गणना करता है। ये [[पुनरावर्ती क्रमसूचक]] के सूचक हैं।
-* [[बाहर की जगह]] के तत्वों का सेट जो प्राकृतिक संख्याओं के एक सुव्यवस्थित क्रम के विशिष्ट कार्य हैं (एक प्रभावी समरूपता <math>\mathbb{N}^\mathbb{N} \cong \mathbb{N}^{\mathbb{N}\times\mathbb{N}}</math> का उपयोग करके)
+* [[बाहर की जगह|बेयर अंतरिक्ष]] के तत्वों का समुच्चय जो प्राकृतिक संख्याओं के सुव्यवस्थित क्रम के विशिष्ट कार्य (प्रभावी समरूपता <math>\mathbb{N}^\mathbb{N} \cong \mathbb{N}^{\mathbb{N}\times\mathbb{N}}</math> का उपयोग करके) है।
-इन पूर्णता परिणामों से परिणाम <math>\Sigma^1_1</math> बाउंडिंग फॉलो के रूप में जाना जाता है। क्रमसूचक संकेतन किसी भी <math>\Sigma^1_1</math>  सेट S के लिय, एक <math>\alpha < \omega^{CK}_1</math> होता है जैसे कि S का प्रत्येक तत्व <math>\alpha</math> क्रमसूचक से कम के लिए एक संकेतन होता है। किसी के लिए <math>\Sigma^1_1</math> बायर स्पेस का सबसेट टी केवल अच्छी तरह से ऑर्डरिंग के विशिष्ट कार्यों से युक्त है, एक है <math>\alpha < \omega^{CK}_1</math> ऐसा है कि T में <math>\alpha</math> दर्शाया गया प्रत्येक क्रमांक इससे कम है.
+इन पूर्णता परिणामों से परिणाम <math>\Sigma^1_1</math> बाउंडिंग फॉलो के रूप में जाना जाता है। क्रमसूचक संकेतन किसी भी <math>\Sigma^1_1</math>  समुच्चय S के लिय, <math>\alpha < \omega^{CK}_1</math> होता है जैसे कि S का प्रत्येक तत्व <math>\alpha</math> क्रमसूचक से कम के लिए संकेतन होता है। किसी के लिए <math>\Sigma^1_1</math> बायर स्पेस का सबसमुच्चय T केवल अच्छी तरह से ऑर्डरिंग के विशिष्ट कार्यों से युक्त है, <math>\alpha < \omega^{CK}_1</math> है, जैसे कि T में <math>\alpha</math> दर्शाया गया प्रत्येक क्रमांक इससे कम है।
 == रिलेटिवाइज़्ड हाइपरअरिथमेटिकिटी और हाइपरडिग्री ==
-की परिभाषा <math>\mathcal{O}</math> प्राकृतिक संख्याओं के एक सेट X से सापेक्षित किया जा सकता है: एक क्रमसूचक संकेतन की परिभाषा में, सीमा अध्यादेशों के लिए खंड बदल दिया जाता है ताकि क्रमसूचक संकेतन के अनुक्रम की संगणनीय गणना को X को एक दैवज्ञ के रूप में उपयोग करने की अनुमति दी जा सके। संख्याओं का वह समूह जो X के सापेक्ष क्रमिक अंकन हैं, जिसे <math>\mathcal{O}^X</math> द्वारा निरूपित किया जाता है  <math>\mathcal{O}^X</math> में दर्शाए गए अध्यादेशों के सर्वोच्च को <math>\omega^{X}_1</math> द्वारा निरूपित किया जाता है; यह एक गणनीय क्रमसूचक है जो <math>\omega^{CK}_1</math>इससे छोटा नहीं है.
+की परिभाषा <math>\mathcal{O}</math> प्राकृतिक संख्याओं के समुच्चय X से सापेक्षित किया जा सकता है: क्रमसूचक संकेतन की परिभाषा में, सीमा अध्यादेशों के लिए खंड बदल दिया जाता है ताकि क्रमसूचक संकेतन के अनुक्रम की संगणनीय गणना को X को दैवज्ञ के रूप में उपयोग करने की अनुमति दी जा सके। संख्याओं का वह समूह जो X के सापेक्ष क्रमिक अंकन हैं, जिसे <math>\mathcal{O}^X</math> द्वारा निरूपित किया जाता है, और <math>\mathcal{O}^X</math> में दर्शाए गए अध्यादेशों के सर्वोच्च को <math>\omega^{X}_1</math> द्वारा निरूपित किया जाता है; यह गणनीय क्रमसूचक है जो <math>\omega^{CK}_1</math>इससे छोटा नहीं है।
-<math>0^{(\delta)}</math> को प्राकृतिक संख्याओं के मनमाने सेट <math>X</math> से भी जोड़ा जा सकता है। परिभाषा में केवल यही परिवर्तन है कि<math>X^{(0)}</math> खाली सेट के बजाय X के रूप में परिभाषित किया गया है, ताकि <math>X^{(1)} = X'</math> X का ट्यूरिंग जंप है, और इसी तरह आगे भी होता है। <math>\omega^{CK}_1</math> पर समाप्त होने के बजाय X के सापेक्ष पदानुक्रम <math>\omega^{X}_1</math> सभी अध्यादेशों से कम चलता है.
+<math>0^{(\delta)}</math> को प्राकृतिक संख्याओं के स्वैच्छिक समुच्चय <math>X</math> से भी जोड़ा जा सकता है। परिभाषा में केवल यही परिवर्तन है कि<math>X^{(0)}</math> खाली समुच्चय के अतिरिक्त X के रूप में परिभाषित किया गया है, ताकि <math>X^{(1)} = X'</math> X का ट्यूरिंग जंप है, और इसी तरह आगे भी होता है। <math>\omega^{CK}_1</math> पर समाप्त होने के अतिरिक्त X के सापेक्ष पदानुक्रम <math>\omega^{X}_1</math> सभी अध्यादेशों से कम चलता है।
-हाइपरारिथमेटिकल रिड्यूसबिलिटी को परिभाषित करने के लिए सापेक्षित हाइपरअरिथमेटिकल पदानुक्रम का उपयोग किया जाता है। दिए गए समुच्चय ''X'' और ''Y'', हम कहते हैं <math> X \leq_{HYP} Y</math> अगर और केवल अगर वहाँ है <math>\delta < \omega^Y_1</math> जैसे कि X, <math>Y^{(\delta)}</math>के लिय ट्यूरिंग रिड्यूसिबल है. अगर <math> X \leq_{HYP} Y</math> और <math> Y \leq_{HYP} X</math> फिर अंकन <math> X \equiv_{HYP} Y</math> X और Y को इंगित करने के लिए 'हाइपररिथमेटिकली समतुल्य' का प्रयोग किया जाता है। यह ट्यूरिंग रिडक्शन की तुलना में एक मोटे समकक्ष संबंध है; उदाहरण के लिए, प्राकृतिक संख्याओं का प्रत्येक सेट हाइपरअरिथमेटिक रूप से इसके ट्यूरिंग जंप के बराबर है लेकिन ट्यूरिंग इसके ट्यूरिंग जंप के बराबर नहीं है। हाइपरअरिथमेटिकल तुल्यता के तुल्यता वर्गों को 'हाइपरडिग्री' के रूप में जाना जाता है।
+हाइपरारिथमेटिकल रिड्यूसबिलिटी को परिभाषित करने के लिए सापेक्षित हाइपरअरिथमेटिकल पदानुक्रम का उपयोग किया जाता है। दिए गए समुच्चय ''X'' और ''Y'', हम कहते हैं <math> X \leq_{HYP} Y</math> यदि और केवल यदि वहाँ <math>\delta < \omega^Y_1</math> है, जैसे कि X, <math>Y^{(\delta)}</math>के लिय ट्यूरिंग रिड्यूसिबल है. यदि <math> X \leq_{HYP} Y</math> और <math> Y \leq_{HYP} X</math> फिर अंकन <math> X \equiv_{HYP} Y</math> X और Y को निरुपित करने के लिए 'हाइपररिथमेटिकली समतुल्य' का प्रयोग किया जाता है। यह ट्यूरिंग रिडक्शन की तुलना में मोटे समकक्ष संबंध है; उदाहरण के लिए, प्राकृतिक संख्याओं का प्रत्येक समुच्चय हाइपरअरिथमेटिक रूप से इसके ट्यूरिंग जंप के बराबर है, किन्तु ट्यूरिंग इसके ट्यूरिंग जंप के बराबर नहीं है। हाइपरअरिथमेटिकल तुल्यता के तुल्यता वर्गों को 'हाइपरडिग्री' के रूप में जाना जाता है।
-वह फ़ंक्शन जो एक सेट X को <math>\mathcal{O}^X</math> पर ले जाता है, और उसे ट्यूरिंग जंप के अनुरूप हाइपरजंप के रूप में जाना जाता है। हाइपरजंप और हाइपरडिग्री के कई गुण स्थापित किए गए हैं। विशेष रूप से, यह ज्ञात है कि Turing Degree#Post.27s समस्या और प्राथमिकता पद्धति | हाइपरडिग्री के लिए पोस्ट की समस्या का एक सकारात्मक उत्तर है: प्राकृतिक संख्याओं के प्रत्येक सेट 'X' के लिए प्राकृतिक का एक सेट 'Y' होता है ऐसी संख्याएँ <math>X <_{HYP} Y <_{HYP} \mathcal{O}^X</math>.
+वह फ़ंक्शन जो समुच्चय X को <math>\mathcal{O}^X</math> पर ले जाता है, और उसे ट्यूरिंग जंप के अनुरूप हाइपरजंप के रूप में जाना जाता है। हाइपरजंप और हाइपरडिग्री के कई गुण स्थापित किए गए हैं। विशेष रूप से, यह ज्ञात है कि हाइपरडिग्री के लिए पोस्ट की समस्या का सकारात्मक उत्तर है: प्राकृतिक संख्याओं के प्रत्येक समुच्चय X के लिए प्राकृतिक संख्याओं का समुच्चय Y होता है जैसे कि <math>X <_{HYP} Y <_{HYP} \mathcal{O}^X</math>.
 == सामान्यीकरण ==
-हाइपरअरिथमेटिकल सिद्धांत को अल्फा पुनरावर्तन सिद्धांत | α-रिकर्सन सिद्धांत द्वारा सामान्यीकृत किया जाता है, जो स्वीकार्य अध्यादेशों के निश्चित उपसमुच्चय का अध्ययन है। हाइपरारिथमेटिकल सिद्धांत विशेष मामला है जिसमें α है <math>\omega^{CK}_1</math>.
+हाइपरअरिथमेटिकल सिद्धांत को अल्फा पुनरावर्तन सिद्धांत α-रिकर्सन सिद्धांत द्वारा सामान्यीकृत किया जाता है, जो स्वीकार्य अध्यादेशों के निश्चित उपसमुच्चय का अध्ययन है। हाइपरारिथमेटिकल सिद्धांत विशेष स्थिति है जिसमें α <math>\omega^{CK}_1</math> है.
 == अन्य पदानुक्रमों से संबंध ==
@@ Line 86: / Line 86: @@
 * [http://folk.uio.no/dnormann/LogikkII.pdf Mathematical Logic II]. Notes by Dag Normann, The University of Oslo. 2005.
 *[https://math.berkeley.edu/~antonio/ Antonio Montalbán: University of California, Berkeley and YouTube content creator]
-[[Category: संगणनीयता सिद्धांत]] [[Category: पदानुक्रम]]
+[[Category:All articles with bare URLs for citations]]
+[[Category:Articles with PDF format bare URLs for citations]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with bare URLs for citations from June 2022]]
 [[Category:Created On 03/02/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:पदानुक्रम]]
+[[Category:संगणनीयता सिद्धांत]]

Anonymous

Search

हाइपरअरिथमेटिकल सिद्धांत: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 21:50, 9 February 2023

Contents

हाइपरअरिथमेटिकल समुच्चय और निश्चितता

हाइपरअरिथमेटिकल समुच्चय और पुनरावृत्त ट्यूरिंग जंप: हाइपरअरिथमेटिकल पदानुक्रम

हाइपरअरिथमेटिकल समुच्चय और उच्च प्रकार में रिकर्सन

उदाहरण: अंकगणित का सत्य समुच्चय

मौलिक परिणाम

रिलेटिवाइज़्ड हाइपरअरिथमेटिकिटी और हाइपरडिग्री

सामान्यीकरण

अन्य पदानुक्रमों से संबंध

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

हाइपरअरिथमेटिकल सिद्धांत: Difference between revisions

Latest revision as of 21:50, 9 February 2023

हाइपरअरिथमेटिकल समुच्चय और निश्चितता

हाइपरअरिथमेटिकल समुच्चय और पुनरावृत्त ट्यूरिंग जंप: हाइपरअरिथमेटिकल पदानुक्रम

हाइपरअरिथमेटिकल समुच्चय और उच्च प्रकार में रिकर्सन

उदाहरण: अंकगणित का सत्य समुच्चय

मौलिक परिणाम

रिलेटिवाइज़्ड हाइपरअरिथमेटिकिटी और हाइपरडिग्री

सामान्यीकरण

अन्य पदानुक्रमों से संबंध

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories