अंकगणितीय पदानुक्रम

Not to be confused with Levy hierarchy.

पदानुक्रम के स्तर कैसे इंटरैक्ट करते हैं और इसके भीतर कुछ बुनियादी सेट श्रेणियां कहाँ स्थित हैं, इसका एक उदाहरण।

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

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

टार्स्की-कुराटोस्की एल्गोरिथम सूत्र को निर्दिष्ट वर्गीकरण और इसे परिभाषित करने वाले सेट पर ऊपरी सीमा प्राप्त करने का आसान तरीका प्रदान करता है।

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

गणितीय तर्क में, अंकगणितीय पदानुक्रम, अंकगणितीय पदानुक्रम या क्लेन-मोस्टोव्स्की पदानुक्रम (गणितज्ञों स्टीफन कोल क्लेन और आंद्रेज मोस्टोव्स्की के बाद) सूत्र (तर्क) की जटिलता के आधार पर कुछ सेट (गणित) को वर्गीकृत करता है जो उन्हें निर्धारित करता है।

सूत्रों का अंकगणितीय पदानुक्रम

अंकगणितीय पदानुक्रम पीनो सिद्धांतों की भाषा में सूत्रों को वर्गीकरण प्रदान करता है #अंकगणित का प्रथम-क्रम सिद्धांत|प्रथम-क्रम अंकगणित। वर्गीकरण निरूपित हैं $\Sigma _{n}^{0}$ और $\Pi _{n}^{0}$ प्राकृतिक संख्या n के लिए (0 सहित)। यहां ग्रीक अक्षर facebook प्रतीक हैं, जो इंगित करता है कि सूत्रों में सेट पैरामीटर नहीं हैं।

यदि सूत्र $\phi$ तार्किक रूप से परिमाणक (तर्क)तर्क) के बिना सूत्र के बराबर है, फिर $\phi$ वर्गीकरण सौंपा गया है $\Sigma _{0}^{0}$ और $\Pi _{0}^{0}$. चूंकि बंधे हुए क्वांटिफायर वाले किसी भी फॉर्मूले को परिबद्ध क्वांटिफायर वाले फॉर्मूले से बदला जा सकता है (उदाहरण के लिए, $\exists x<2\ \phi (x)$ के बराबर है $\phi (0)\vee \phi (1)$), हम भी अनुमति दे सकते हैं $\phi$ परिबद्ध परिमाणक होना।

वर्गीकरण $\Sigma _{n}^{0}$ और $\Pi _{n}^{0}$ निम्नलिखित नियमों का उपयोग करते हुए प्रत्येक प्राकृतिक संख्या n के लिए आगमनात्मक रूप से परिभाषित किया गया है:

• अगर $\phi$ तार्किक रूप से फॉर्म के सूत्र के बराबर है $\exists m_{1}\exists m_{2}\cdots \exists m_{k}\psi$, कहाँ $\psi$ है $\Pi _{n}^{0}$, तब $\phi$ वर्गीकरण दिया गया है $\Sigma _{n+1}^{0}$.
• अगर $\phi$ तार्किक रूप से फॉर्म के सूत्र के बराबर है $\forall m_{1}\forall m_{2}\cdots \forall m_{k}\psi$, कहाँ $\psi$ है $\Sigma _{n}^{0}$, तब $\phi$ वर्गीकरण दिया गया है $\Pi _{n+1}^{0}$.

ए $\Sigma _{n}^{0}$ सूत्र एक ऐसे सूत्र के समतुल्य है जो कुछ अस्तित्वगत परिमाणकों और विकल्पों के साथ शुरू होता है $n-1$ अस्तित्वगत और सार्वभौमिक क्वांटिफायर की श्रृंखला के बीच का समय; जबकि एक $\Pi _{n}^{0}$ सूत्र एक सूत्र के समतुल्य है जो कुछ सार्वभौमिक परिमाणकों से शुरू होता है और समान रूप से वैकल्पिक होता है।

क्योंकि प्रत्येक प्रथम-क्रम सूत्र का सामान्य रूप है, प्रत्येक सूत्र को कम से कम वर्गीकरण सौंपा गया है। क्योंकि निरर्थक क्वांटिफायर को किसी भी सूत्र में जोड़ा जा सकता है, एक बार सूत्र को वर्गीकरण सौंपे जाने के बाद $\Sigma _{n}^{0}$ या $\Pi _{n}^{0}$ इसे वर्गीकरण सौंपा जाएगा $\Sigma _{m}^{0}$ और $\Pi _{m}^{0}$ प्रत्येक एम > एन के लिए। इस प्रकार सूत्र को सौंपा गया एकमात्र प्रासंगिक वर्गीकरण सबसे कम एन वाला है; अन्य सभी वर्गीकरण इससे निर्धारित किए जा सकते हैं।

प्राकृतिक संख्याओं के समुच्चय का अंकगणितीय पदानुक्रम

प्राकृतिक संख्याओं का सेट एक्स को पीनो अंकगणित की भाषा में सूत्र φ द्वारा परिभाषित किया गया है (शून्य के लिए प्रतीक 0 के साथ पहली क्रम की भाषा, उत्तराधिकारी समारोह के लिए एस, + जोड़ के लिए, गुणा के लिए ×, और = समानता के लिए), यदि X के अवयव ठीक वही संख्याएँ हैं जो φ को संतुष्ट करती हैं। अर्थात, सभी प्राकृत संख्याओं n के लिए,

$n\in X\Leftrightarrow \mathbb {N} \models \varphi ({\underline {n}}),$

कहाँ ${\underline {n}}$ अंकगणित की भाषा में वह अंक है जिसके अनुरूप है $n$. प्रथम-क्रम अंकगणित में सेट निश्चित है यदि इसे पियानो अंकगणित की भाषा में किसी सूत्र द्वारा परिभाषित किया गया है।

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

ध्यान दें कि इसके बारे में बात करना शायद ही कभी समझ में आता है $\Delta _{n}^{0}$ सूत्र; सूत्र का पहला परिमाणक या तो अस्तित्वपरक या सार्वभौमिक होता है। तो ए $\Delta _{n}^{0}$ सेट अनिवार्य रूप से ए द्वारा परिभाषित नहीं है $\Delta _{n}^{0}$ सूत्र के अर्थ में सूत्र जो दोनों है $\Sigma _{n}^{0}$ और $\Pi _{n}^{0}$; बल्कि दोनों हैं $\Sigma _{n}^{0}$ और $\Pi _{n}^{0}$ सूत्र जो सेट को परिभाषित करते हैं। उदाहरण के लिए, विषम प्राकृतिक संख्याओं का समूह $n$ किसी के द्वारा परिभाषित किया जा सकता है $\forall k(n\neq 2\times k)$ या $\exists k(n=2\times k+1)$.

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

सापेक्ष अंकगणितीय पदानुक्रम

जिस तरह हम परिभाषित कर सकते हैं कि सेट एक्स के लिए दूसरे सेट वाई के सापेक्ष पुनरावर्ती सेट होने का क्या मतलब है, गणना को परिभाषित करने के लिए एक्स को ऑरेकल (कम्प्यूटेबिलिटी) के रूप में वाई से परामर्श करने की अनुमति देकर हम इस धारणा को पूरे अंकगणितीय पदानुक्रम तक बढ़ा सकते हैं और परिभाषित कर सकते हैं कि यह क्या है X के होने का मतलब है $\Sigma _{n}^{0}$, $\Delta _{n}^{0}$ या $\Pi _{n}^{0}$ वाई में, क्रमशः निरूपित $\Sigma _{n}^{0,Y}$, $\Delta _{n}^{0,Y}$ और $\Pi _{n}^{0,Y}$. ऐसा करने के लिए, प्राकृत संख्याओं Y का समुच्चय ठीक करें और Peano अंकगणित की भाषा में Y की सदस्यता के लिए विधेय (तर्क) जोड़ें। हम तब कहते हैं कि X अंदर है $\Sigma _{n}^{0,Y}$ अगर यह एक द्वारा परिभाषित किया गया है $\Sigma _{n}^{0}$ इस विस्तारित भाषा में सूत्र। दूसरे शब्दों में, X है $\Sigma _{n}^{0,Y}$ अगर यह द्वारा परिभाषित किया गया है $\Sigma _{n}^{0}$ Y की सदस्यता के बारे में प्रश्न पूछने के लिए सूत्र की अनुमति है। वैकल्पिक रूप से कोई भी देख सकता है $\Sigma _{n}^{0,Y}$ उन सेटों के रूप में सेट करता है जिन्हें Y में पुनरावर्ती सेट के साथ शुरू किया जा सकता है और वैकल्पिक रूप से इन सेटों के संघ (सेट सिद्धांत) और इंटरसेक्शन (सेट सिद्धांत) को n बार तक ले जा सकते हैं।

उदाहरण के लिए, मान लीजिए कि Y प्राकृत संख्याओं का समुच्चय है। X को Y के तत्व द्वारा विभाज्य संख्याओं का समूह होने दें। फिर X को सूत्र द्वारा परिभाषित किया गया है $\phi (n)=\exists m\exists t(Y(m)\land m\times t=n)$ तो एक्स अंदर है $\Sigma _{1}^{0,Y}$ (वास्तव में यह अंदर है $\Delta _{0}^{0,Y}$ साथ ही, चूंकि हम दोनों परिमाणकों को n द्वारा बाध्य कर सकते हैं)।

अंकगणित न्यूनीकरण और डिग्री

अंकगणितीय रिड्यूसिबिलिटी ट्यूरिंग न्यूनीकरण और हाइपरअरिथमेटिक रिड्यूसबिलिटी के बीच मध्यवर्ती धारणा है।

समुच्चय अंकगणितीय (अंकगणितीय और अंकगणितीय रूप से निश्चित भी) होता है यदि इसे पीनो अंकगणित की भाषा में किसी सूत्र द्वारा परिभाषित किया जाता है। समान रूप से X अंकगणितीय है यदि X है $\Sigma _{n}^{0}$ या $\Pi _{n}^{0}$ कुछ प्राकृतिक संख्या n के लिए। समुच्चय X 'अंकगणितीय है' समुच्चय Y, निरूपित $X\leq _{A}Y$, यदि एक्स को परिभाषित किया जा सकता है, तो पीनो अंकगणित की भाषा में कुछ सूत्र के रूप में वाई की सदस्यता के लिए विधेय द्वारा विस्तारित किया जाता है। $\Sigma _{n}^{0,Y}$ या $\Pi _{n}^{0,Y}$ कुछ प्राकृतिक संख्या n के लिए। का पर्यायवाची है $X\leq _{A}Y$ है: X, Y के लिए 'अंकगणितीय रूप से कम करने योग्य' है।

रिश्ता $X\leq _{A}Y$ प्रतिवर्त संबंध और सकर्मक संबंध है, और इस प्रकार संबंध $\equiv _{A}$ नियम द्वारा परिभाषित

$X\equiv _{A}Y\iff X\leq _{A}Y\land Y\leq _{A}X$

तुल्यता संबंध है। इस संबंध के तुल्यता वर्ग अंकगणितीय डिग्री कहलाते हैं; वे आंशिक रूप से के तहत आदेश दिए गए हैं $\leq _{A}$.

कैंटर और बायर स्पेस के सबसेट का अंकगणितीय पदानुक्रम

कैंटर स्पेस, निरूपित $2^{\omega }$, 0s और 1s के सभी अनंत क्रमों का समुच्चय है; बायर स्पेस (सेट थ्योरी), निरूपित $\omega ^{\omega }$ या ${\mathcal {N}}$, प्राकृतिक संख्याओं के सभी अनंत क्रमों का समुच्चय है। ध्यान दें कि कैंटर स्पेस के तत्वों को प्राकृतिक संख्याओं के सेट और बायर स्पेस के तत्वों को प्राकृतिक संख्याओं से प्राकृतिक संख्याओं के कार्यों के साथ पहचाना जा सकता है।

दूसरे क्रम के अंकगणित का सामान्य स्वयंसिद्ध सेट-आधारित भाषा का उपयोग करता है जिसमें सेट क्वांटिफायर को स्वाभाविक रूप से कैंटर स्पेस पर क्वांटिफाइंग के रूप में देखा जा सकता है। कैंटर स्पेस के सबसेट को वर्गीकरण सौंपा गया है $\Sigma _{n}^{0}$ अगर यह एक द्वारा निश्चित है $\Sigma _{n}^{0}$ सूत्र। सेट को वर्गीकरण सौंपा गया है $\Pi _{n}^{0}$ अगर यह एक द्वारा निश्चित है $\Pi _{n}^{0}$ सूत्र। अगर सेट दोनों है $\Sigma _{n}^{0}$ और $\Pi _{n}^{0}$ तो इसे अतिरिक्त वर्गीकरण दिया जाता है $\Delta _{n}^{0}$. उदाहरण के लिए, चलो $O\subset 2^{\omega }$ सभी अनंत बाइनरी स्ट्रिंग्स का सेट हो जो सभी 0 नहीं हैं (या समतुल्य रूप से प्राकृतिक संख्याओं के सभी गैर-रिक्त सेटों का सेट)। जैसा $O=\{X\in 2^{\omega }|\exists n(X(n)=1)\}$ हमने देखा कि $O$ ए द्वारा परिभाषित किया गया है $\Sigma _{1}^{0}$ सूत्र और इसलिए है $\Sigma _{1}^{0}$ तय करना।

ध्यान दें कि जबकि कैंटर स्पेस के दोनों तत्व (प्राकृतिक संख्याओं के सेट के रूप में माने जाते हैं) और कैंटर स्पेस के सबसेट को अंकगणितीय पदानुक्रम में वर्गीकृत किया गया है, ये समान पदानुक्रम नहीं हैं। वास्तव में दो पदानुक्रमों के बीच का संबंध दिलचस्प और गैर-तुच्छ है। उदाहरण के लिए $\Pi _{n}^{0}$ कैंटर स्पेस के तत्व (सामान्य रूप से) तत्वों के समान नहीं हैं $X$ कैंटर अंतरिक्ष की ताकि $\{X\}$ है $\Pi _{n}^{0}$ कैंटर स्पेस का सबसेट। हालाँकि, कई दिलचस्प परिणाम दो पदानुक्रमों से संबंधित हैं।

अंकगणितीय पदानुक्रम में बेयर स्थान के उपसमुच्चय को दो तरीकों से वर्गीकृत किया जा सकता है।

• बायर स्पेस के उपसमुच्चय में मैप के तहत कैंटर स्पेस का संबंधित उपसमुच्चय होता है जो प्रत्येक फ़ंक्शन से लेता है $\omega$ को $\omega$ इसके ग्राफ के सूचक समारोह के लिए। बेयर स्पेस के सबसेट को वर्गीकरण दिया गया है $\Sigma _{n}^{1}$, $\Pi _{n}^{1}$, या $\Delta _{n}^{1}$ अगर और केवल अगर कैंटर स्पेस के संबंधित उपसमुच्चय का ही वर्गीकरण है।
• दूसरे क्रम के अंकगणित के कार्यात्मक संस्करण का उपयोग करके सूत्रों के विश्लेषणात्मक पदानुक्रम को परिभाषित करके बेयर स्पेस पर विश्लेषणात्मक पदानुक्रम की समकक्ष परिभाषा दी गई है; फिर कैंटर स्पेस के सबसेट पर विश्लेषणात्मक पदानुक्रम को बेयर स्पेस पर पदानुक्रम से परिभाषित किया जा सकता है। यह वैकल्पिक परिभाषा पहली परिभाषा के समान ही वर्गीकरण देती है।

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

ध्यान दें कि हम प्राकृतिक संख्याओं के कुछ सेट के सापेक्ष कैंटर और बायर रिक्त स्थान के सबसेट के अंकगणितीय पदानुक्रम को भी परिभाषित कर सकते हैं। वास्तव में बोल्डफेस $\mathbf {\Sigma } _{n}^{0}$ का ही संघ है $\Sigma _{n}^{0,Y}$ प्राकृतिक संख्या वाई के सभी सेटों के लिए। ध्यान दें कि बोल्डफेस पदानुक्रम बोरेल पदानुक्रम का मानक पदानुक्रम है।

एक्सटेंशन और विविधताएं

प्रत्येक आदिम पुनरावर्ती कार्य के लिए फ़ंक्शन प्रतीक के साथ विस्तारित भाषा का उपयोग करके सूत्रों के अंकगणितीय पदानुक्रम को परिभाषित करना संभव है। यह भिन्नता के वर्गीकरण को थोड़ा बदल देती है $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}$, क्योंकि प्रिमिटिव रिकर्सिव फंक्शन # पहले क्रम के पीनो अंकगणित में उपयोग करें | पहले क्रम के पीनो अंकगणित में आदिम पुनरावर्ती कार्यों का उपयोग करने के लिए, सामान्य रूप से, असीम अस्तित्वगत क्वांटिफायर की आवश्यकता होती है, और इस प्रकार कुछ सेट जो अंदर होते हैं $\Sigma _{0}^{0}$ इस परिभाषा से हैं $\Sigma _{1}^{0}$ इस लेख की शुरुआत में दी गई परिभाषा के अनुसार। $\Sigma _{1}^{0}$ और इस प्रकार पदानुक्रम में सभी उच्च वर्ग अप्रभावित रहते हैं।

प्राकृतिक संख्याओं पर सभी परिमित संबंधों पर पदानुक्रम की अधिक शब्दार्थ भिन्नता को परिभाषित किया जा सकता है; निम्नलिखित परिभाषा का प्रयोग किया जाता है। हर संगणनीय संबंध को परिभाषित किया गया है $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}$. वर्गीकरण $\Sigma _{n}^{0}$ और $\Pi _{n}^{0}$ निम्नलिखित नियमों के साथ आगमनात्मक रूप से परिभाषित किया गया है।

• यदि संबंध $R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,$ है $\Sigma _{n}^{0}$ फिर संबंध $S(n_{1},\ldots ,n_{l})=\forall m_{1}\cdots \forall m_{k}R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})$ होना परिभाषित किया गया है $\Pi _{n+1}^{0}$
• यदि संबंध $R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,$ है $\Pi _{n}^{0}$ फिर संबंध $S(n_{1},\ldots ,n_{l})=\exists m_{1}\cdots \exists m_{k}R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})$ होना परिभाषित किया गया है $\Sigma _{n+1}^{0}$

यह भिन्नता कुछ सेटों के वर्गीकरण को थोड़ा बदल देती है। विशेष रूप से, $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}$सेट के वर्ग के रूप में (कक्षा में संबंधों द्वारा परिभाषित), के समान है $\Delta _{1}^{0}$ जैसा कि पहले परिभाषित किया गया था। इसे प्राकृतिक संख्याओं, बेयर स्पेस और कैंटर स्पेस पर सीमित संबंधों को कवर करने के लिए बढ़ाया जा सकता है।

संकेतन का अर्थ

सूत्रों पर अंकगणितीय पदानुक्रम के लिए संकेतन से निम्नलिखित अर्थ जोड़े जा सकते हैं।

सबस्क्रिप्ट $n$ प्रतीकों में $\Sigma _{n}^{0}$ और $\Pi _{n}^{0}$ सूत्र में उपयोग किए जाने वाले सार्वभौमिक और अस्तित्वगत संख्या क्वांटिफायर के ब्लॉक के विकल्पों की संख्या को इंगित करता है। इसके अलावा, सबसे बाहरी ब्लॉक अस्तित्व में है $\Sigma _{n}^{0}$ सूत्र और सार्वभौमिक $\Pi _{n}^{0}$ सूत्र।

सुपरस्क्रिप्ट $0$ प्रतीकों में $\Sigma _{n}^{0}$, $\Pi _{n}^{0}$, और $\Delta _{n}^{0}$ परिमाणित की जा रही वस्तुओं के प्रकार को इंगित करता है। प्रकार 0 वस्तुएँ प्राकृतिक संख्याएँ हैं, और प्रकार की वस्तुएँ हैं $i+1$ ऐसे कार्य हैं जो प्रकार की वस्तुओं के सेट को मैप करते हैं $i$ प्राकृतिक संख्या के लिए। उच्च प्रकार की वस्तुओं पर परिमाणीकरण, जैसे कि प्राकृतिक संख्याओं से प्राकृतिक संख्याओं तक के कार्य, को 0 से अधिक सुपरस्क्रिप्ट द्वारा वर्णित किया जाता है, जैसा कि विश्लेषणात्मक पदानुक्रम में है। सुपरस्क्रिप्ट 0 संख्याओं पर क्वांटिफ़ायर इंगित करता है, सुपरस्क्रिप्ट 1 संख्याओं से संख्याओं (टाइप 1 ऑब्जेक्ट्स) के कार्यों पर क्वांटिफिकेशन इंगित करेगा, सुपरस्क्रिप्ट 2 उन कार्यों पर क्वांटिफिकेशन के अनुरूप होगा जो टाइप 1 ऑब्जेक्ट लेते हैं और नंबर लौटाते हैं, और इसी तरह।

उदाहरण

• $\Sigma _{1}^{0}$ h> संख्याओं के समुच्चय वे हैं जिन्हें प्रपत्र के सूत्र द्वारा परिभाषित किया जा सकता है $\exists n_{1}\cdots \exists n_{k}\psi (n_{1},\ldots ,n_{k},m)$ कहाँ $\psi$ केवल परिबद्ध परिमाणक हैं। ये बिल्कुल पुनरावर्ती गणना योग्य सेट हैं।
• प्राकृतिक संख्याओं का सेट जो कुल कार्यों की गणना करने वाली ट्यूरिंग मशीनों के लिए सूचकांक हैं $\Pi _{2}^{0}$. सहज रूप से, एक index $e$ यदि और केवल यदि प्रत्येक के लिए इस सेट में आता है $m$ वहाँ है एक $s$ जैसे कि ट्यूरिंग मशीन index $e$ इनपुट पर रुक जाता है $m$ बाद $s$ कदम"। एक पूर्ण प्रमाण यह दिखाएगा कि पिछले वाक्य में उद्धरण चिह्नों में प्रदर्शित संपत्ति किसके द्वारा पीनो अंकगणित की भाषा में निश्चित है $\Sigma _{1}^{0}$ सूत्र।
• प्रत्येक $\Sigma _{1}^{0}$ बेयर स्पेस या कैंटर स्पेस का सबसेट स्पेस पर सामान्य टोपोलॉजी में खुला सेट है। इसके अलावा, ऐसे किसी भी सेट के लिए बुनियादी खुले सेटों के गोडेल नंबरों की संगणनीय गणना है जिसका संघ मूल सेट है। इस कारण से, $\Sigma _{1}^{0}$ सेट को कभी-कभी प्रभावी रूप से खुला कहा जाता है। इसी तरह, हर $\Pi _{1}^{0}$ सेट बंद है और $\Pi _{1}^{0}$ सेट को कभी-कभी प्रभावी रूप से बंद कहा जाता है।
• कैंटर स्पेस या बेयर स्पेस का हर अंकगणितीय उपसमुच्चय बोरेल सेट है। लाइटफेस बोरेल पदानुक्रम अतिरिक्त बोरेल सेटों को शामिल करने के लिए अंकगणितीय पदानुक्रम का विस्तार करता है। उदाहरण के लिए, हर $\Pi _{2}^{0}$ कैंटर या बेयर स्पेस का सबसेट है a $G_{\delta }$ सेट (यानी, सेट जो कई खुले सेटों के प्रतिच्छेदन के बराबर है)। इसके अलावा, इनमें से प्रत्येक खुला सेट है $\Sigma _{1}^{0}$ और इन खुले सेटों के गोडेल नंबरों की सूची में संगणनीय गणना है। अगर $\phi (X,n,m)$ है $\Sigma _{0}^{0}$ फ्री सेट वेरिएबल X और फ्री नंबर वेरिएबल्स के साथ फॉर्मूला $n,m$ फिर $\Pi _{2}^{0}$ तय करना $\{X\mid \forall n\exists m\phi (X,n,m)\}$ का चौराहा है $\Sigma _{1}^{0}$ फॉर्म के सेट $\{X\mid \exists m\phi (X,n,m)\}$ n के रूप में प्राकृतिक संख्याओं के सेट पर होता है।
• $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}$ h> सूत्रों को एक-एक करके सभी मामलों पर जाकर जाँच की जा सकती है, जो संभव है क्योंकि उनके सभी क्वांटिफायर बंधे हुए हैं। इसके लिए समय उनके तर्कों में बहुपद है (उदाहरण के लिए n में बहुपद $\varphi (n)$); इस प्रकार उनकी संबंधित निर्णय समस्याएं ई (जटिलता) में शामिल हैं (क्योंकि एन बिट्स की संख्या में घातीय है)। यह अब वैकल्पिक परिभाषाओं के तहत नहीं है $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}$, जो आदिम पुनरावर्ती कार्यों के उपयोग की अनुमति देता है, क्योंकि अब परिमाणक तर्कों के किसी भी आदिम पुनरावर्ती कार्य से बंधे हो सकते हैं।
• $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}$ h> वैकल्पिक परिभाषा के तहत सूत्र, जो परिबद्ध क्वांटिफायर के साथ आदिम पुनरावर्ती कार्यों के उपयोग की अनुमति देता है, प्रपत्र की प्राकृतिक संख्याओं के सेट के अनुरूप होता है $\{n:f(n)=0\}$ आदिम पुनरावर्ती क्रिया के लिए f. ऐसा इसलिए है क्योंकि परिबद्ध क्वांटिफायर की अनुमति परिभाषा में कुछ भी नहीं जोड़ती है: आदिम पुनरावर्ती f के लिए, $\forall k<n:f(k)=0$ वैसा ही है जैसा कि $f(0)+f(1)+...f(n)=0$, और $\exists k<n:f(k)=0$ वैसा ही है जैसा कि $f(0)*f(1)*...f(n)=0$; कोर्स-ऑफ़-वैल्यू रिकर्सन के साथ इनमें से प्रत्येक को आदिम रिकर्सन फ़ंक्शन द्वारा परिभाषित किया जा सकता है।

गुण

निम्नलिखित गुण प्राकृतिक संख्याओं के सेट के अंकगणितीय पदानुक्रम और कैंटर या बायर स्पेस के सबसेट के अंकगणितीय पदानुक्रम के लिए हैं।

• संग्रह $\Pi _{n}^{0}$ और $\Sigma _{n}^{0}$ उनके संबंधित तत्वों के परिमित संघ (सेट सिद्धांत) और परिमित चौराहे (सेट सिद्धांत) के तहत बंद हैं।
• सेट है $\Sigma _{n}^{0}$ यदि और केवल यदि इसका पूरक है $\Pi _{n}^{0}$. एक सेट है $\Delta _{n}^{0}$ अगर और केवल अगर सेट दोनों है $\Sigma _{n}^{0}$ और $\Pi _{n}^{0}$, ऐसे में इसका पूरक भी होगा $\Delta _{n}^{0}$.
• समावेशन $\Pi _{n}^{0}\subsetneq \Pi _{n+1}^{0}$ और $\Sigma _{n}^{0}\subsetneq \Sigma _{n+1}^{0}$ सभी के लिए पकड़ो $n$. इस प्रकार पदानुक्रम का पतन नहीं होता है। यह पोस्ट के प्रमेय का सीधा परिणाम है।
• समावेशन $\Delta _{n}^{0}\subsetneq \Pi _{n}^{0}$, $\Delta _{n}^{0}\subsetneq \Sigma _{n}^{0}$ और $\Sigma _{n}^{0}\cup \Pi _{n}^{0}\subsetneq \Delta _{n+1}^{0}$ इसके लिए रखें $n\geq 1$.

* उदाहरण के लिए, सार्वभौमिक ट्यूरिंग मशीन टी के लिए, जोड़े (एन, एम) का सेट ऐसा है कि टी एन पर रुकता है लेकिन एम पर नहीं, में है $\Delta _{2}^{0}$ (रोकथाम की समस्या के लिए दैवज्ञ के साथ संगणनीय होना) लेकिन अंदर नहीं $\Sigma _{1}^{0}\cup \Pi _{1}^{0}$, .

• $\Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}=\Sigma _{0}^{0}\cup \Pi _{0}^{0}\subset \Delta _{1}^{0}$. इस आलेख में दी गई परिभाषा से समावेश सख्त है, लेकिन पहचान के साथ $\Delta _{1}^{0}$ परिभाषा अंकगणितीय पदानुक्रम#विस्तार और विविधताओं में से एक के अंतर्गत रखती है।

ट्यूरिंग मशीनों से संबंध

See also: Post's theorem

संगणनीय सेट

यदि S संगणनीय फलन#कम्प्यूटेबल सेट और संबंध है, तो S और इसका पूरक (सेट सिद्धांत) दोनों पुनरावर्ती रूप से गणना योग्य हैं (यदि T ट्यूरिंग मशीन है जो S और 0 में इनपुट के लिए 1 दे रही है, तो हम ट्यूरिंग मशीन बना सकते हैं जो केवल रुकेगी पूर्व पर, और दूसरा केवल बाद वाले पर रुकता है)।

पोस्ट प्रमेय के अनुसार, S और इसका पूरक दोनों अंदर हैं $\Sigma _{1}^{0}$. इसका मतलब है कि S दोनों अंदर है $\Sigma _{1}^{0}$ और में $\Pi _{1}^{0}$, और इसलिए यह अंदर है $\Delta _{1}^{0}$.

इसी प्रकार, प्रत्येक समुच्चय के लिए S में $\Delta _{1}^{0}$, S और इसके पूरक दोनों अंदर हैं $\Sigma _{1}^{0}$ और इसलिए (पोस्ट के प्रमेय द्वारा) कुछ ट्यूरिंग मशीनों टी द्वारा पुनरावर्ती रूप से गणना योग्य हैं₁ और टी₂, क्रमश। प्रत्येक संख्या n के लिए, इनमें से ठीक एक रुकता है। इसलिए हम ट्यूरिंग मशीन T का निर्माण कर सकते हैं जो T के बीच वैकल्पिक है₁ और टी₂, रुकना और 1 लौटना जब पूर्व रुकता है या रुकता है और 0 लौटता है जब बाद वाला रुकता है। इस प्रकार T हर n पर रुकता है और लौटता है कि क्या यह S में है, तो S संगणनीय है।

मुख्य परिणामों का सारांश

प्राकृतिक संख्याओं के ट्यूरिंग कम्प्यूटेशनल सेट बिल्कुल स्तर पर सेट होते हैं $\Delta _{1}^{0}$ अंकगणितीय पदानुक्रम का। पुनरावर्ती गणना योग्य सेट बिल्कुल स्तर पर सेट होते हैं $\Sigma _{1}^{0}$.

कोई भी ओरेकल मशीन अपनी स्वयं की हॉल्टिंग समस्या को हल करने में सक्षम नहीं है (ट्यूरिंग के प्रमाण की भिन्नता लागू होती है)। ए के लिए रुकने की समस्या $\Delta _{n}^{0,Y}$ ऑरैकल वास्तव में बैठता है $\Sigma _{n+1}^{0,Y}$.

पोस्ट प्रमेय प्राकृतिक संख्याओं के समुच्चय के अंकगणितीय पदानुक्रम और ट्यूरिंग डिग्री के बीच घनिष्ठ संबंध स्थापित करता है। विशेष रूप से, यह सभी n ≥ 1 के लिए निम्नलिखित तथ्य स्थापित करता है:

• सेट $\emptyset ^{(n)}$ (खाली सेट का nवां ट्यूरिंग कूदो ) कई-एक कमी है। कई-एक पूर्ण $\Sigma _{n}^{0}$.
• सेट $\mathbb {N} \setminus \emptyset ^{(n)}$ अनेक-एक में पूर्ण है $\Pi _{n}^{0}$.
• सेट $\emptyset ^{(n-1)}$ ट्यूरिंग पूरा सेट है $\Delta _{n}^{0}$.

बहुपद पदानुक्रम अंकगणितीय पदानुक्रम का व्यवहार्य संसाधन-सीमित संस्करण है जिसमें शामिल संख्याओं पर बहुपद लंबाई सीमाएँ रखी जाती हैं (या, समतुल्य, बहुपद समय सीमा शामिल ट्यूरिंग मशीनों पर रखी जाती है)। यह प्राकृतिक संख्याओं के कुछ सेटों का बेहतर वर्गीकरण देता है जो स्तर पर हैं $\Delta _{1}^{0}$ अंकगणितीय पदानुक्रम का।

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

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
⋮		⋮

यह भी देखें

• विश्लेषणात्मक पदानुक्रम
• लेवी पदानुक्रम
• पदानुक्रम (गणित)
• व्याख्यात्मक तर्क
• बहुपद पदानुक्रम

संदर्भ

• Japaridze, Giorgie (1994), "The logic of arithmetical hierarchy", Annals of Pure and Applied Logic, 66 (2): 89–112, doi:10.1016/0168-0072(94)90063-9, Zbl 0804.03045.
• Moschovakis, Yiannis N. (1980), Descriptive Set Theory, Studies in Logic and the Foundations of Mathematics, vol. 100, North Holland, ISBN 0-444-70199-0, Zbl 0433.03025.
• Nies, André (2009), Computability and randomness, Oxford Logic Guides, vol. 51, Oxford: Oxford University Press, ISBN 978-0-19-923076-1, Zbl 1169.03034.
• Rogers, H., Jr. (1967), Theory of recursive functions and effective computability, Maidenhead: McGraw-Hill, Zbl 0183.01401{{citation}}: CS1 maint: multiple names: authors list (link).