परिबद्ध परिमाणक

This article is about bounded quantification in mathematical logic. For bounded quantification in type theory, see Bounded quantification.

गणितीय तर्क में औपचारिक सिद्धांतों के अध्ययन में, मानक क्वांटिफायर ∀ और ∃ के अलावा, बंधे हुए क्वांटिफायर (ए.के.ए. प्रतिबंधित क्वांटिफायर) को अक्सर औपचारिक भाषा में शामिल किया जाता है। परिबद्ध परिमाणक ∀ और ∃ से भिन्न होते हैं क्योंकि परिबद्ध परिमाणक परिमाणित चर की सीमा को सीमित करते हैं। परिबद्ध परिमाणकों का अध्ययन इस तथ्य से प्रेरित है कि यह निर्धारित करना कि केवल परिबद्ध परिमाणकों वाला एक वाक्य (गणितीय तर्क) सत्य है या नहीं, अक्सर उतना कठिन नहीं होता जितना यह निर्धारित करना कि एक मनमाना वाक्य सत्य है या नहीं।

उदाहरण

वास्तविक विश्लेषण के संदर्भ में परिबद्ध परिमाणकों के उदाहरणों में शामिल हैं:

• $\forall x>0$ - सभी x के लिए जहां x 0 से बड़ा है
• $\exists y<0$ - वहां एक y मौजूद है जहां y 0 से कम है
• $\forall x\in \mathbb {R}$ - सभी x के लिए जहां x एक वास्तविक संख्या है
• $\forall x>0\quad \exists y<0\quad (x=y^{2})$ - प्रत्येक धनात्मक संख्या एक ऋणात्मक संख्या का वर्ग होती है

अंकगणित में परिबद्ध परिमाणक

मान लीजिए कि एल पीनो अंकगणित की भाषा है (दूसरे क्रम के अंकगणित या सभी परिमित प्रकारों में अंकगणित की भाषा भी काम करेगी)। परिबद्ध परिमाणक दो प्रकार के होते हैं: $\forall n<t$ और $\exists n<t$. ये क्वांटिफायर संख्या चर n को बांधते हैं और इसमें एक संख्यात्मक शब्द t होता है जिसमें n का उल्लेख नहीं हो सकता है लेकिन जिसमें अन्य मुक्त चर हो सकते हैं। (यहाँ संख्यात्मक शब्दों का अर्थ 1 + 1, 2, 2 × 3, m + 3, आदि जैसे पद हैं।)

इन परिमाणकों को निम्नलिखित नियमों द्वारा परिभाषित किया गया है ($\phi$ सूत्रों को दर्शाता है):

$\exists n<t\,\phi \Leftrightarrow \exists n(n<t\land \phi )$

$\forall n<t\,\phi \Leftrightarrow \forall n(n<t\rightarrow \phi )$

इन परिमाणकों के लिए कई प्रेरणाएँ हैं।

• पुनरावर्तन सिद्धांत के लिए भाषा के अनुप्रयोगों में, जैसे कि अंकगणितीय पदानुक्रम, परिबद्ध परिमाणक कोई जटिलता नहीं जोड़ते हैं। अगर $\phi$ तब एक निर्णायकता (तर्क) विधेय है $\exists n<t\,\phi$ और $\forall n<t\,\phi$ निर्णय योग्य भी हैं.
• पीनो अंकगणित के अध्ययन के अनुप्रयोगों में, तथ्य यह है कि एक विशेष सेट को केवल बंधे हुए क्वांटिफायर के साथ परिभाषित किया जा सकता है, सेट की संगणना के लिए परिणाम हो सकते हैं। उदाहरण के लिए, केवल परिबद्ध परिमाणकों का उपयोग करके अभाज्य संख्या की एक परिभाषा है: एक संख्या n अभाज्य है यदि और केवल तभी जब n से पूरी तरह से कम दो संख्याएँ न हों जिनका गुणनफल n हो। भाषा में आदिमता की कोई परिमाण-मुक्त परिभाषा नहीं है $\langle 0,1,+,\times ,<,=\rangle$, हालाँकि। तथ्य यह है कि मौलिकता को परिभाषित करने वाला एक सीमित मात्रात्मक सूत्र है, यह दर्शाता है कि प्रत्येक संख्या की मौलिकता को गणनात्मक रूप से तय किया जा सकता है।

सामान्य तौर पर, प्राकृतिक संख्याओं पर एक संबंध एक बंधे हुए सूत्र द्वारा परिभाषित किया जा सकता है यदि और केवल यदि यह रैखिक-समय पदानुक्रम में गणना योग्य है, जिसे बहुपद पदानुक्रम के समान परिभाषित किया गया है, लेकिन बहुपद के बजाय रैखिक समय सीमा के साथ। नतीजतन, एक बंधे हुए सूत्र द्वारा परिभाषित सभी विधेय प्राथमिक|कल्मार प्राथमिक, संदर्भ-संवेदनशील व्याकरण|संदर्भ-संवेदनशील, और आदिम पुनरावर्ती हैं।

अंकगणितीय पदानुक्रम में, एक अंकगणितीय सूत्र जिसमें केवल परिबद्ध परिमाणक होते हैं, कहलाता है $\Sigma _{0}^{0}$, $\Delta _{0}^{0}$, और $\Pi _{0}^{0}$. सुपरस्क्रिप्ट 0 कभी-कभी छोड़ दिया जाता है।

समुच्चय सिद्धांत में परिबद्ध परिमाणक

मान लीजिए कि L भाषा है $\langle \in ,\ldots ,=\rangle$ ज़र्मेलो-फ्रेंकेल सेट सिद्धांत के अनुसार, जहां इलिप्सिस को टर्म-फॉर्मिंग ऑपरेशंस द्वारा प्रतिस्थापित किया जा सकता है जैसे कि सत्ता स्थापित ऑपरेशन के लिए एक प्रतीक। दो परिबद्ध परिमाणक हैं: $\forall x\in t$ और $\exists x\in t$. ये क्वांटिफायर सेट वेरिएबल x को बांधते हैं और इसमें एक शब्द t होता है जिसमें x का उल्लेख नहीं हो सकता है लेकिन जिसमें अन्य मुक्त चर हो सकते हैं।

इन परिमाणकों का शब्दार्थ निम्नलिखित नियमों द्वारा निर्धारित किया जाता है:

$\exists x\in t\ (\phi )\Leftrightarrow \exists x(x\in t\land \phi )$

$\forall x\in t\ (\phi )\Leftrightarrow \forall x(x\in t\rightarrow \phi )$

एक ZF सूत्र जिसमें केवल परिबद्ध परिमाणक होते हैं, कहलाता है $\Sigma _{0}$, $\Delta _{0}$, और $\Pi _{0}$. यह लेवी पदानुक्रम का आधार बनता है, जिसे अंकगणितीय पदानुक्रम के अनुरूप परिभाषित किया गया है।

क्रिपके-प्लेटक सेट सिद्धांत और रचनात्मक सेट सिद्धांत में बंधे हुए क्वांटिफायर महत्वपूर्ण हैं, जहां केवल विधेय पृथक्करण की स्वयंसिद्ध स्कीमा है|Δ₀ अलगाव शामिल है. अर्थात्, इसमें केवल परिबद्ध परिमाणकों वाले सूत्रों के लिए पृथक्करण शामिल है, लेकिन अन्य सूत्रों के लिए पृथक्करण शामिल नहीं है। केपी में प्रेरणा यह तथ्य है कि क्या एक सेट एक्स एक बंधे हुए क्वांटिफायर फॉर्मूला को संतुष्ट करता है या नहीं, यह केवल उन सेटों के संग्रह पर निर्भर करता है जो एक्स के रैंक के करीब हैं (क्योंकि पॉवरसेट ऑपरेशन को केवल एक शब्द बनाने के लिए कई बार लागू किया जा सकता है)। रचनात्मक समुच्चय सिद्धांत में, यह अव्यावहारिकता के आधार पर प्रेरित होता है।

यह भी देखें

• उपप्रकार - प्रकार सिद्धांत में सीमाबद्ध मात्रा का ठहराव
• सिस्टम एफ-उप|सिस्टम एफ_<:- एक सिस्टम एफ ने बाउंडेड क्वांटिफिकेशन के साथ लैम्ब्डा कैलकुलस टाइप किया

संदर्भ

• Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-56881-262-0.
• Kunen, K. (1980). Set theory: An introduction to independence proofs. Elsevier. ISBN 0-444-86839-9.