विश्लेषणात्मक पदानुक्रम

This article is about समुच्चय का वर्गीकरण. For जटिल निर्णय करना, see विश्लेषणात्मक पदानुक्रम प्रक्रिया.

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

सूत्रों का विश्लेषणात्मक पदानुक्रम

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

दूसरे क्रम के अंकगणित की भाषा में समुच्चय सूत्र को $\Sigma _{n+1}^{1}$ परिभाषित किया गया है | यदि यह प्रपत्र $\exists X_{1}\cdots \exists X_{k}\psi$ के सूत्र के लिए तार्किक तुल्यता है | जहाँ $\psi$ $\Pi _{n}^{1}$ समुच्चय सूत्र के $\Pi _{n+1}^{1}$ रूप में परिभाषित किया गया है | यदि यह सामान्यतः फॉर्म $\forall X_{1}\cdots \forall X_{k}\psi$ के सूत्र के सामान है | जहाँ $\psi$ है $\Sigma _{n}^{1}$.है | यह आगमनात्मक परिभाषा प्रत्येक प्राकृतिक संख्या के लिए . $\Sigma _{n}^{1}$ और $\Pi _{n}^{1}$ $n$ वर्गों को परिभाषित करती है |

कुराटोव्स्की और टारस्की ने 1931 में दिखाया कि दूसरे क्रम के अंकगणित की भाषा में हर सूत्र का समुच्चय सामान्य रूप है, और इसलिए $\Sigma _{n}^{1}$ या $\Pi _{n}^{1}$ कुछ के लिए $n$. क्योंकि अर्थहीन परिमाणक्स को किसी भी सूत्र में जोड़ा जा सकता है, एक बार सूत्र को वर्गीकरण दिए जाने के बाद $\Sigma _{n}^{1}$ या $\Pi _{n}^{1}$ कुछ के लिए $n$ इसे वर्गीकरण $\Sigma _{m}^{1}$ और $\Pi _{m}^{1}$ दिया जाएगा $n$ से बड़े सभी $m$ के लिए होता है | .

प्राकृतिक संख्याओं के समुच्चय का विश्लेषणात्मक पदानुक्रम

प्राकृतिक संख्याओं के समुच्चय समूह को $\Sigma _{n}^{1}$ वर्गीकरण आवंटित गया है यदि यह समुच्चय $\Sigma _{n}^{1}$ द्वारा निश्चित है समुच्चय को $\Pi _{n}^{1}$ वर्गीकरण आवंटित गया है यदि यह समुच्चय $\Pi _{n}^{1}$ द्वारा निश्चित है । यदि समुच्चय $\Sigma _{n}^{1}$ और $\Pi _{n}^{1}$दोनों है तो इसे अतिरिक्त वर्गीकरण दिया जाता है | समुच्चय $\Delta _{n}^{1}$. $\Delta _{1}^{1}$ h> को हाइपरअरिथमेटिकल कहा जाता है। पुनरावृत्त संगणनीय कार्यों के माध्यम से इन समुच्चयों का समुच्चय वैकल्पिक वर्गीकरण हाइपरारिथमेटिकल सिद्धांत द्वारा प्रदान किया जाता है।

कैंटर और बेयर अन्तरिक्ष के सबसमुच्चय पर विश्लेषणात्मक पदानुक्रम

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

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

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

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

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

विस्तार

अंकगणितीय पदानुक्रम के स्थिति में, विश्लेषणात्मक पदानुक्रम के सापेक्ष संस्करण को परिभाषित किया जा सकता है। समुच्चय स्थिर समुच्चय प्रतीक A को जोड़ने के लिए भाषा का विस्तार किया गया है। विस्तारित भाषा में समुच्चय सूत्र को $\Sigma _{n}^{1,A}$ या $\Pi _{n}^{1,A}$ आगमनात्मक रूप से परिभाषित किया गया है | उपरोक्त के समान आगमनात्मक परिभाषा का उपयोग करना है। समुच्चय $Y$ दिया गया है |, समुच्चय $\Sigma _{n}^{1,Y}$ के रूप में परिभाषित किया गया है यदि यह समुच्चय $\Sigma _{n}^{1,A}$ सूत्र द्वारा निश्चित है जिसमें प्रतीक $A$ की व्याख्या के रूप में समझा जाता है; $\Pi _{n}^{1,Y}$ और $\Delta _{n}^{1,Y}$ के लिए समान परिभाषाएँ प्रयुक्त होती है । किसी भी मापदंड वाई के लिए जो समुच्चय हैं $\Sigma _{n}^{1,Y}$ या $\Pi _{n}^{1,Y}$है | प्रक्षेपण पदानुक्रम में वर्गीकृत किया जाता है, और अधिकांशतः मापदंड के उपयोग को संकेत करने के लिए बोल्डफेस ग्रीक अक्षरों द्वारा चिह्नित किया जाता है।

उदाहरण

• $\prec$ $\mathbb {N} ^{2}$,पर सम्बन्ध $\prec$ कथन के लिए कथन $\mathbb {N}$ समुच्चय अच्छी व्यवस्था है | (समुच्चय $\Pi _{1}^{1}$ पर अच्छी तरह से स्थापित संबंधों के सामान्य स्थिति से भ्रमित न हों, लेवी पदानुक्रम देखें)
• सभी प्राकृतिक संख्याओं का समुच्चय जो संगणनीय क्रमसूचकों का सूचक है a $\Pi _{1}^{1}$ समुच्चय जो $\Sigma _{1}^{1}$ नहीं है .|
  • ये समुच्चय केवल $\omega _{1}^{CK}$$\omega$ के पुनरावर्ती-गणनीय सबसमुच्चय है | [Bar75, p. 168]
• समुच्चय समारोह $f:\mathbb {N} \to \mathbb {N}$ हर्ब्रांड के 1931 के समीकरणों के सिस्टम के औपचारिकतावाद $f$ हाइपरअरिथमेटिकल द्वारा परिभाषित किया जा सकता है।
• निरंतर कार्यों का समुच्चय $f:[0,1]\to \mathbb {[} 0,1]$ जिसका माध्य मान प्रमेय पदानुक्रम पर $\Delta _{2}^{1}$ से कम नहीं है।
• कैंटर अन्तरिक्ष के तत्वों का समुच्चय जो अच्छी तरह से व्यवस्थित करने के विशिष्ट कार्य हैं एक $\omega$$\Pi _{1}^{1}$ समुच्चय है समुच्चय जो $\Sigma _{1}^{1}$ नहीं है . वास्तव में, किसी तत्व $Y$ के लिए $\Sigma _{1}^{1,Y}$ बेयर अंतरिक्ष की नहीं है |
• यदि निर्माणशीलता का स्वयंसिद्ध धारण करता है तो बेयर अन्तरिक्ष के उत्पाद का समुच्चय उपसमुच्चय स्वयं के साथ होता है जो $\Delta _{2}^{1}$ है और बायर अंतरिक्ष के सुव्यवस्थित क्रम का ग्राफ है। यदि स्वयंसिद्ध धारण करता है तो एक $\Delta _{2}^{1}$ कैंटर अन्तरिक्ष का अच्छा क्रम भी है।

गुण

प्रत्येक के लिए $n$ हमारे पास निम्नलिखित सख्त नियंत्रण हैं:

$\Pi _{n}^{1}\subset \Sigma _{n+1}^{1}$,

$\Pi _{n}^{1}\subset \Pi _{n+1}^{1}$,

$\Sigma _{n}^{1}\subset \Pi _{n+1}^{1}$,

$\Sigma _{n}^{1}\subset \Sigma _{n+1}^{1}$.

समुच्चय समुच्चय जो $\Sigma _{n}^{1}$ अंदर है कुछ के लिए n को 'विश्लेषणात्मक' कहा जाता है। इस उपयोग को विश्लेषणात्मक समुच्चय शब्द से अलग करने के लिए देखभाल की आवश्यकता है जिसका एक अलग अर्थ है, अर्थात् ${\boldsymbol {\Sigma }}_{1}^{1}$ है |.

टेबल

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

यह भी देखें

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

संदर्भ

• Rogers, H. (1967). Theory of recursive functions and effective computability. McGraw-Hill.
• Kechris, A. (1995). Classical Descriptive Set Theory (Graduate Texts in Mathematics 156 ed.). Springer. ISBN 0-387-94374-9.

• विश्लेषणात्मक पदानुक्रम at PlanetMath.