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

This article is about the classification of sets. For making complex decisions, see Analytic hierarchy process.

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

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

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

प्राकृतिक संख्याओं के एक समूह को वर्गीकरण सौंपा गया है $\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.