बोरेल पदानुक्रम

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

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

बोरेल सेट

Main article: Borel set

मनमाने ढंग से टोपोलॉजिकल स्पेस में बोरेल बीजगणित अंतरिक्ष के सबसेट का सबसे छोटा संग्रह है जिसमें खुले सेट होते हैं और काउंटेबल यूनियनों और सापेक्ष पूरक के तहत बंद होते हैं। यह दिखाया जा सकता है कि बोरेल बीजगणित गणनीय चौराहों के तहत भी बंद है।

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

बोल्डफेस बोरेल पदानुक्रम

अंतरिक्ष X पर बोरेल पदानुक्रम या बोल्डफेस बोरेल पदानुक्रम में कक्षाएं होती हैं $\mathbf {\Sigma } _{\alpha }^{0}$, $\mathbf {\Pi } _{\alpha }^{0}$, और $\mathbf {\Delta } _{\alpha }^{0}$ हर गणनीय अध्यादेश के लिए $\alpha$ शून्य से अधिक। इनमें से प्रत्येक वर्ग में X के उपसमुच्चय होते हैं। वर्गों को निम्नलिखित नियमों से आगमनात्मक रूप से परिभाषित किया गया है:

• एक सेट है $\mathbf {\Sigma } _{1}^{0}$ अगर और केवल अगर यह खुला है।
• एक सेट है $\mathbf {\Pi } _{\alpha }^{0}$ अगर और केवल अगर इसका पूरक अंदर है $\mathbf {\Sigma } _{\alpha }^{0}$.
• एक सेट $A$ में है $\mathbf {\Sigma } _{\alpha }^{0}$ के लिए $\alpha >1$ अगर और केवल अगर सेट का अनुक्रम है $A_{1},A_{2},\ldots$ ऐसा है कि प्रत्येक $A_{i}$ में है $\mathbf {\Pi } _{\alpha _{i}}^{0}$ कुछ के लिए $\alpha _{i}<\alpha$ और $A=\bigcup A_{i}$.
• एक सेट है $\mathbf {\Delta } _{\alpha }^{0}$ अगर और केवल अगर यह दोनों में है $\mathbf {\Sigma } _{\alpha }^{0}$ और में $\mathbf {\Pi } _{\alpha }^{0}$.

पदानुक्रम के लिए प्रेरणा उस तरीके का पालन करना है जिसमें पूरक और गणनीय संघों का उपयोग करके खुले सेट से एक बोरेल सेट का निर्माण किया जा सकता है। कहा जाता है कि एक बोरेल सेट में परिमित रैंक होती है $\mathbf {\Sigma } _{\alpha }^{0}$ कुछ परिमित क्रमसूचक के लिए $\alpha$; अन्यथा इसकी अनंत रैंक है।

अगर $\mathbf {\Sigma } _{1}^{0}\subseteq \mathbf {\Sigma } _{2}^{0}$ तब पदानुक्रम को निम्नलिखित गुणों के लिए दिखाया जा सकता है:

• प्रत्येक α के लिए, $\mathbf {\Sigma } _{\alpha }^{0}\cup \mathbf {\Pi } _{\alpha }^{0}\subseteq \mathbf {\Delta } _{\alpha +1}^{0}$. इस प्रकार, एक बार एक सेट में है $\mathbf {\Sigma } _{\alpha }^{0}$ या $\mathbf {\Pi } _{\alpha }^{0}$, वह सेट पदानुक्रम में सभी वर्गों में α से अधिक अध्यादेशों के अनुरूप होगा
• $\bigcup _{\alpha <\omega _{1}}\mathbf {\Sigma } _{\alpha }^{0}=\bigcup _{\alpha <\omega _{1}}\mathbf {\Pi } _{\alpha }^{0}=\bigcup _{\alpha <\omega _{1}}\mathbf {\Delta } _{\alpha }^{0}$. इसके अलावा, एक सेट इस संघ में है अगर और केवल अगर यह बोरेल है।
• अगर $X$ एक बेशुमार पोलिश स्थान है, यह दिखाया जा सकता है $\mathbf {\Sigma } _{\alpha }^{0}$ में निहित नहीं है $\mathbf {\Pi } _{\alpha }^{0}$ किसी के लिए $\alpha <\omega _{1}$, और इस प्रकार पदानुक्रम का पतन नहीं होता है।

छोटे रैंक के बोरेल सेट

शास्त्रीय वर्णनात्मक सेट सिद्धांत में छोटे रैंक के वर्गों को वैकल्पिक नामों से जाना जाता है।

• $\mathbf {\Sigma } _{1}^{0}$ h> समुच्चय खुले समुच्चय होते हैं। $\mathbf {\Pi } _{1}^{0}$ h> समुच्चय बंद समुच्चय हैं।
• $\mathbf {\Sigma } _{2}^{0}$ h> समुच्चय बंद समुच्चयों के गणनीय संघ हैं, और इन्हें F-सिग्मा समुच्चय|F कहा जाता है_σ सेट। $\mathbf {\Pi } _{2}^{0}$ h> समुच्चय दोहरे वर्ग हैं, और खुले समुच्चयों के गणनीय प्रतिच्छेदन के रूप में लिखे जा सकते हैं। इन सेटों को जी-डेल्टा सेट कहा जाता है | जी_δ सेट।

लाइटफेस पदानुक्रम

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

लाइटफेस बोरेल पदानुक्रम को किसी भी प्रभावी पोलिश स्थान पर परिभाषित किया जा सकता है। इसमें कक्षाएं होती हैं $\Sigma _{\alpha }^{0}$, $\Pi _{\alpha }^{0}$ और $\Delta _{\alpha }^{0}$ प्रत्येक अशून्य गणनीय क्रमसूचक के लिए $\alpha$ पुनरावर्ती क्रमसूचक से कम|चर्च-क्लीन क्रमसूचक $\omega _{1}^{\mathrm {CK} }$. प्रत्येक वर्ग में अंतरिक्ष के सबसेट होते हैं। वर्ग, और वर्गों के तत्वों के लिए कोड, आगमनात्मक रूप से निम्नानुसार परिभाषित किए गए हैं:

• एक सेट है $\Sigma _{1}^{0}$ अगर और केवल अगर यह प्रभावी रूप से खुला है, जो कि एक खुला सेट है जो मूल खुले सेटों के एक गणना योग्य अनुक्रम का संघ है। ऐसे सेट के लिए एक कोड एक जोड़ी (0, ई) है, जहां ई बुनियादी खुले सेटों के अनुक्रम की गणना करने वाले प्रोग्राम की अनुक्रमणिका है।
• एक सेट है $\Pi _{\alpha }^{0}$ यदि और केवल यदि इसका पूरक है $\Sigma _{\alpha }^{0}$. इन सेटों में से एक के लिए एक कोड एक जोड़ी (1, सी) है जहां सी पूरक सेट के लिए एक कोड है।
• एक सेट है $\Sigma _{\alpha }^{0}$ यदि अनुक्रम के लिए कोडों का गणनात्मक रूप से गणना योग्य अनुक्रम है $A_{1},A_{2},\ldots$ सेट के ऐसे कि प्रत्येक $A_{i}$ है $\Pi _{\alpha _{i}}^{0}$ कुछ के लिए $\alpha _{i}<\alpha$ और $A=\bigcup A_{i}$. ए के लिए एक कोड $\Sigma _{\alpha }^{0}$ सेट एक जोड़ी (2, ई) है, जहां ई अनुक्रम के कोडों की गणना करने वाले प्रोग्राम का एक सूचकांक है $A_{i}$.

लाइटफेस बोरेल सेट के लिए एक कोड छोटे रैंक के सेट से सेट को पुनर्प्राप्त करने के तरीके के बारे में पूरी जानकारी देता है। यह बोल्डफेस पदानुक्रम के विपरीत है, जहां इस तरह की प्रभावशीलता की आवश्यकता नहीं है। प्रत्येक लाइटफेस बोरेल सेट में असीम रूप से कई अलग-अलग कोड होते हैं। अन्य कोडिंग सिस्टम संभव हैं; महत्वपूर्ण विचार यह है कि एक कोड को प्रभावी रूप से खुले सेट, पिछले कोड द्वारा दर्शाए गए सेट के पूरक और कोड के अनुक्रमों की गणना योग्य गणनाओं के बीच प्रभावी ढंग से अंतर करना चाहिए।

यह दिखाया जा सकता है कि प्रत्येक के लिए $\alpha <\omega _{1}^{\mathrm {CK} }$ में सेट हैं $\Sigma _{\alpha }^{0}\setminus \Pi _{\alpha }^{0}$, और इस प्रकार पदानुक्रम का पतन नहीं होता है। स्टेज पर कोई नया सेट नहीं जोड़ा जाएगा $\omega _{1}^{\mathrm {CK} }$, हालाँकि।

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

एक लाइटफेस बोरेल सेट 'ए' के ​​लिए कोड का उपयोग एक पेड़ को परिभाषित करने के लिए किया जा सकता है, जिसके नोड्स को कोड द्वारा लेबल किया जाता है। पेड़ की जड़ को 'ए' के ​​लिए कोड द्वारा लेबल किया गया है। यदि किसी नोड को (1,c) फॉर्म के कोड द्वारा लेबल किया जाता है तो उसके पास एक चाइल्ड नोड होता है जिसका कोड c होता है। यदि एक नोड को (2,e) फॉर्म के कोड द्वारा लेबल किया जाता है, तो उसके पास इंडेक्स e वाले प्रोग्राम द्वारा गणना किए गए प्रत्येक कोड के लिए एक चाइल्ड है। अगर एक नोड को (0,e) फॉर्म के कोड के साथ लेबल किया गया है तो इसमें कोई सन्तान नहीं है। यह पेड़ वर्णन करता है कि कैसे 'ए' छोटे रैंक के सेट से बनाया गया है। ए के निर्माण में उपयोग किए गए क्रमसूचक यह सुनिश्चित करते हैं कि इस पेड़ का कोई अनंत पथ नहीं है, क्योंकि पेड़ के माध्यम से किसी भी अनंत पथ में 2 से शुरू होने वाले असीम रूप से कई कोड शामिल होंगे, और इस प्रकार एक अनंत ह्रासमान होगा अध्यादेशों का क्रम। इसके विपरीत, यदि एक मनमाना सबट्री $\omega ^{<\omega }\,$ कोड द्वारा अपने नोड्स को एक सुसंगत तरीके से लेबल किया गया है, और पेड़ के पास कोई अनंत पथ नहीं है, तो पेड़ की जड़ में कोड लाइटफेस बोरेल सेट के लिए एक कोड है। इस सेट का रैंक क्लेन-ब्रूवर ऑर्डर में पेड़ के ऑर्डर प्रकार से घिरा है। क्योंकि पेड़ अंकगणितीय रूप से निश्चित है, यह रैंक इससे कम होना चाहिए $\omega _{1}^{\mathrm {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
⋮		⋮

स्रोत

• एलेक्जेंडर एस. केक्रिस|केक्रिस, एलेक्जेंडर। शास्त्रीय वर्णनात्मक सेट थ्योरी। गणित वी। 156, स्प्रिंगर-वर्लाग, 1995 में स्नातक ग्रंथ। ISBN 3-540-94374-9.
• थॉमस जेक|जेक, थॉमस। सेट थ्योरी, तीसरा संस्करण। स्प्रिंगर, 2003। ISBN 3-540-44085-2.

यह भी देखें

• वैज पदानुक्रम
• बड़े गणनीय अध्यादेश

श्रेणी:वर्णनात्मक सेट सिद्धांत श्रेणी:गणितीय तर्क पदानुक्रम