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

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

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

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

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

प्राकृतिक संख्याओं के एक समूह को स्तर $\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$ नंबर है, जहां ई कुल गणना योग्य फ़ंक्शन $\phi _{e}$ का सूचकांक है ऐसा है कि प्रत्येक n के लिए, $\phi _{e}(n)$ एक क्रमसूचक λ_n के लिए एक अंकन है δ से कम और δ समुच्चय $\{\lambda _{n}\mid n\in \mathbb {N} \}$ का सर्वोच्च है .

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

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

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

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

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

हाइपरारिथमेटिकल पदानुक्रम को इन पुनरावृत्त ट्यूरिंग जंप से परिभाषित किया गया है। प्राकृतिक संख्याओं के एक सेट X को हाइपरारिथमेटिकल पदानुक्रम के स्तर δ पर वर्गीकृत किया गया है $\delta <\omega _{1}^{CK}$, अगर एक्स ट्यूरिंग में कमी है $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}$. सेट टी सेट में ट्यूरिंग कमी है $0^{(\omega )}$, और इसलिए हाइपरअरिथमेटिकल पदानुक्रम में उच्च नहीं है, हालांकि यह तर्स्की की अनिश्चितता प्रमेय द्वारा अंकगणितीय रूप से निश्चित नहीं है।

मौलिक परिणाम

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

पूर्णता परिणाम भी सिद्धांत के लिए मौलिक हैं। प्राकृतिक संख्याओं का समुच्चय है$\Pi _{1}^{1}$ यदि यह स्तर पर है तो पूर्ण करें $\Pi _{1}^{1}$ विश्लेषणात्मक पदानुक्रम और हर $\Pi _{1}^{1}$ प्राकृत संख्याओं का समुच्चय अनेक-एक अपचयन है | अनेक-एक अपचयन योग्य है। ए की परिभाषा $\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}$ क्रमसूचक संकेतन के सेट एस, वहाँ एक है $\alpha <\omega _{1}^{CK}$ ऐसा है कि S का प्रत्येक तत्व एक क्रमसूचक से कम के लिए एक संकेतन है $\alpha$. किसी के लिए $\Sigma _{1}^{1}$ बायर स्पेस का सबसेट टी केवल अच्छी तरह से ऑर्डरिंग के विशिष्ट कार्यों से युक्त है, एक है $\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'$ एक्स का ट्यूरिंग जंप है, और इसी तरह। पर समाप्त होने के बजाय $\omega _{1}^{CK}$ X के सापेक्ष पदानुक्रम सभी अध्यादेशों से कम चलता है $\omega _{1}^{X}$.

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

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

सामान्यीकरण

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

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

Lightface		Boldface
Σ0 0 = Π0 0 = Δ0 0 (sometimes the same as Δ0 1)		Σ0 0 = Π0 0 = Δ0 0 (if defined)
Δ0 1 = recursive		Δ0 1 = clopen
Σ0 1 = recursively enumerable	Π0 1 = co-recursively enumerable	Σ0 1 = G = open	Π0 1 = F = closed
Δ0 2		Δ0 2
Σ0 2	Π0 2	Σ0 2 = Fσ	Π0 2 = Gδ
Δ0 3		Δ0 3
Σ0 3	Π0 3	Σ0 3 = Gδσ	Π0 3 = Fσδ
⋮		⋮
Σ0 <ω = Π0 <ω = Δ0 <ω = Σ1 0 = Π1 0 = Δ1 0 = arithmetical		Σ0 <ω = Π0 <ω = Δ0 <ω = Σ1 0 = Π1 0 = Δ1 0 = boldface arithmetical
⋮		⋮
Δ0 α (α recursive)		Δ0 α (α countable)
Σ0 α	Π0 α	Σ0 α	Π0 α
⋮		⋮
Σ0 ωCK 1 = Π0 ωCK 1 = Δ0 ωCK 1 = Δ1 1 = hyperarithmetical		Σ0 ω1 = Π0 ω1 = Δ0 ω1 = Δ1 1 = B = Borel
Σ1 1 = lightface analytic	Π1 1 = lightface coanalytic	Σ1 1 = A = analytic	Π1 1 = CA = coanalytic
Δ1 2		Δ1 2
Σ1 2	Π1 2	Σ1 2 = PCA	Π1 2 = CPCA
Δ1 3		Δ1 3
Σ1 3	Π1 3	Σ1 3 = PCPCA	Π1 3 = CPCPCA
⋮		⋮
Σ1 <ω = Π1 <ω = Δ1 <ω = Σ2 0 = Π2 0 = Δ2 0 = analytical		Σ1 <ω = Π1 <ω = Δ1 <ω = Σ2 0 = Π2 0 = Δ2 0 = 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

बाहरी संबंध

• 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