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

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

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

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

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

अंकन $\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$ वर्गों को परिभाषित करती है |

Kuratowski और Tarski ने 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$ के रूप में समझा जाता है $Y$; के लिए समान परिभाषाएँ $\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}$. वास्तव में, यह समुच्चय नहीं है $\Sigma _{1}^{1,Y}$ किसी तत्व के लिए $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.