उपगणनीयता: Difference between revisions
No edit summary |
No edit summary |
||
Line 18: | Line 18: | ||
=== बहिष्कृत मध्य से संबंध === | === बहिष्कृत मध्य से संबंध === | ||
रचनात्मक लॉजिक्स और [[रचनात्मक सेट सिद्धांत| | रचनात्मक लॉजिक्स और [[रचनात्मक सेट सिद्धांत|समुच्चय सिद्धांत]] में निर्णायकता (तर्क) और संभवतः प्रभावी विधि के प्रश्नों के लिए अनंत (गैर-परिमित) समुच्चय के बीच फलन के अस्तित्व को बाँधते हैं। वहां, सबकाउंटेबिलिटी प्रॉपर्टी काउंटेबिलिटी से अलग हो जाती है और इस तरह यह निरर्थक धारणा नहीं है। | ||
अनुक्रमण समुच्चय <math>I</math> प्राकृतिक संख्याओं का अस्तित्व माना जा सकता है, उदा। विशिष्टता के स्वयंसिद्ध स्कीमा जैसे समुच्चय सैद्धांतिक स्वयंसिद्धों के माध्यम से सबसमुच्चय के रूप में। फिर की परिभाषा के द्वारा <math>I\subseteq{\mathbb N}</math>, | अनुक्रमण समुच्चय <math>I</math> प्राकृतिक संख्याओं का अस्तित्व माना जा सकता है, उदा। विशिष्टता के स्वयंसिद्ध स्कीमा जैसे समुच्चय सैद्धांतिक स्वयंसिद्धों के माध्यम से सबसमुच्चय के रूप में। फिर की परिभाषा के द्वारा <math>I\subseteq{\mathbb N}</math>, | ||
<math display="block">\forall (i\in I). (i\in{\mathbb N}).</math> | <math display="block">\forall (i\in I). (i\in{\mathbb N}).</math> | ||
लेकिन यह समुच्चय तब भी वियोज्य होने में विफल हो सकता है, इस अर्थ में कि | लेकिन यह समुच्चय तब भी वियोज्य होने में विफल हो सकता है, इस अर्थ में कि |
Revision as of 22:50, 8 February 2023
This article includes a list of general references, but it lacks sufficient corresponding inline citations. (September 2020) (Learn how and when to remove this template message) |
रचनात्मक गणित में, प्राकृतिक संख्याओं से आंशिक फलन प्रक्षेपण के रूप में उपस्थित होते है। सर्जेन्ट के साथ संग्रह सबकाउंटेबल होते है। इसे इस रूप में व्यक्त किया जा सकता है
जहाँ दर्शाता है विशेषण फलन होते है पर . अनुमान का सदस्य है और यहाँ उपवर्ग का समुच्चय होता है। दूसरे शब्दों में, सबकाउंटेबल संग्रह के सभी तत्व गणना संख्याओं के अनुक्रमण समुच्चय की छवि में कार्यात्मक रूप से होता है और इस प्रकार समुच्चय गणनीय समुच्चय .के प्रभुत्व के रूप में समझा जा सकता है।
ध्यान दें कि गणनीयता और परिमितता गुणों का नामकरण ऐतिहासिक रूप से बहुत भिन्न होता है। यहां वाद-विवाद प्रश्न में समुच्चय अनुमानों के संदर्भ में परिभाषित लक्षण से संबंधित होता है।
चर्चा
उदाहरण
महत्वपूर्ण स्थितिया वह है जहां अभिकलनीयता सिद्धांत में अध्ययन के अनुसार फलनों के बड़े वर्ग के कुछ उपवर्ग को दर्शाता है।
कुल संगणनीय फलनों पर विचार करें और ध्यान दें कि कुल होना निर्णायक गुण धर्म नहीं है अर्थात कुल फलनों और प्राकृतिक संख्याओं के बीच रचनात्मक अवरोध नहीं हो सकती है। चूँकि, सभी संभावित आंशिक संगणनीय फलनों के कोडों की गणना के माध्यम से उनके सबसेट, जो गैर-समाप्ति वाले फलनों को अनुमति देता है जैसे कि कुल फलनों को सबकाउंटेबल समुच्चय के रूप में देखा जाता है। ध्यान दें कि इंडेक्स समुच्चय रिकर्सन थ्योरी पर राइस के प्रमेय द्वारा, अधिकांश डोमेन सेट किए जाते हैं पुनरावर्ती नहीं हैं दरअसल, सभी गिनती संख्याओं के बीच कोई प्रभावी मानचित्र नहीं है और अनंत गैर सीमित अनुक्रमण समुच्चय पर बल दिया गया है, केवल उपसमुच्चय संबंध . संख्याओं के रचनात्मक रूप से गैर गणनीय समुच्चय का प्रभुत्व होता है , नाम सबकाउंटेबल इस प्रकार प्रस्तुत करता है कि असंख्य समुच्चय से बड़ा .नहीं होता है
प्रदर्शन जिसमें उप-गणना के रूप में है इसका तात्पर्य यह है कि यह मौलिक रूप से गैर-रचनात्मक रूप से गणनीय होता है, लेकिन यह किसी भी प्रभावी गणना क्षमता को प्रतिबिंबित नहीं करता है। दूसरे शब्दों में, इसका तात्पर्य यह है कि अनुक्रम में सभी फलनों को सूचीबद्ध करने वाले कलन विधि को कोडित नहीं किया जाता है, समुच्चय और फलन अस्तित्व के बारे में मौलिक स्वयंसिद्धि से अभिगृहीत नहीं किया गया है। हम देखते हैं कि किसी सिद्धांत के स्वयंसिद्धों के आधार पर, उप-गणना योग्यता की तुलना में सिद्ध होने की अधिक संभावना होती है।
बहिष्कृत मध्य से संबंध
रचनात्मक लॉजिक्स और समुच्चय सिद्धांत में निर्णायकता (तर्क) और संभवतः प्रभावी विधि के प्रश्नों के लिए अनंत (गैर-परिमित) समुच्चय के बीच फलन के अस्तित्व को बाँधते हैं। वहां, सबकाउंटेबिलिटी प्रॉपर्टी काउंटेबिलिटी से अलग हो जाती है और इस तरह यह निरर्थक धारणा नहीं है। अनुक्रमण समुच्चय प्राकृतिक संख्याओं का अस्तित्व माना जा सकता है, उदा। विशिष्टता के स्वयंसिद्ध स्कीमा जैसे समुच्चय सैद्धांतिक स्वयंसिद्धों के माध्यम से सबसमुच्चय के रूप में। फिर की परिभाषा के द्वारा ,
मौलिक गणित में
मौलिक तर्क के सभी कानूनों पर जोर देते हुए, की वियोगात्मक गुण धर्म ऊपर चर्चा वास्तव में सभी सेटों के लिए है। फिर, गैर-खाली के लिए , गुण संख्या (जो यहाँ मतलब होगा कि में इंजेक्ट करता है ), गणनीय ( है इसकी सीमा के रूप में), सबकाउंटेबल (का सबसमुच्चय में डालता है ) और नहीं भी -उत्पादक ( गणनीयता गुण धर्म अनिवार्य रूप से सबसमुच्चय के संदर्भ में परिभाषित की गई है ) सभी समतुल्य हैं और व्यक्त करते हैं कि समुच्चय परिमित समुच्चय या गणनीय रूप से अनंत है।
गैर-मौलिक अभिकथन
बहिष्कृत मध्य के कानून के बिना, यह उन सेटों की उपगणनीयता पर जोर देने के लिए संगत हो सकता है जो मौलिक रूप से (अर्थात गैर-रचनात्मक रूप से) प्राकृतिक संख्याओं की कार्डिनैलिटी से अधिक हो। ध्यान दें कि रचनात्मक सेटिंग में, फलन स्थान के बारे में काउंटेबिलिटी का दावा पूरे समुच्चय से बाहर , के रूप में , खंडन किया जा सकता है। लेकिन उपगणनीयता असंख्य समुच्चय का समुच्चय द्वारा से प्रभावी रूप से अलग करने योग्य नहीं है अनुमति दी जा सकती है।
जैसा असंख्य है और मौलिक रूप से सबकाउंटेबल नहीं है, इसके बड़े फलन स्थान के साथ मौलिक ढांचा चर्च की थीसिस (रचनात्मक गणित) के साथ असंगत है। रचनात्मक चर्च की थीसिस, रूसी रचनावाद का स्वयंसिद्ध।
=== सबकाउंटेबल और ω-उत्पादक परस्पर अनन्य === हैं समुच्चय कहा जाएगा रचनात्मक और उत्पादक समुच्चय अगर, जब भी इसका कोई सबसमुच्चय किसी फलन का वह कार्यक्षेत्र है जिस पर कोई आंशिक फलन है , वहाँ हमेशा तत्व उपस्थित होता है जो उस सीमा के पूरक में रहता है।[1] यदि कुछ पर कोई अनुमान उपस्थित है , तो वर्णित अनुसार इसकी संबंधित प्रशंसा खाली समुच्चय के बराबर होगी , और इसलिए सबकाउंटेबल समुच्चय कभी नहीं होता है -उत्पादक। जैसा कि ऊपर परिभाषित किया गया है, होने की गुण धर्म -उत्पादक सीमा को जोड़ता है किसी विशेष मान के किसी भी आंशिक फलन का फलनों की श्रेणी में नहीं। इस प्रकार, होना -उत्पादक बोलता है कि सभी तत्वों को उत्पन्न करना कितना कठिन है : उन्हें ही फंक्शन का उपयोग करके उत्पन्न नहीं किया जा सकता है। वें>-उत्पादकता गुण धर्म उपगणनीयता में बाधा उत्पन्न करती है। जैसा कि यह बेशुमारता का भी अर्थ है, कैंटर के विकर्ण तर्क में अधिकांशतः यह धारणा सम्मिलित होती है, स्पष्ट रूप से सत्तर के दशक के अंत से।
कोई गणना योग्य गणना की असंभवता स्थापित कर सकता है केवल संगणनीय रूप से गणना योग्य सबसमुच्चय पर विचार करके और किसी को सभी बाधाओं के समुच्चय की आवश्यकता हो सकती है कुल पुनरावर्ती तथाकथित उत्पादन फलन की छवि होना चाहिए।
समुच्चय थ्योरी में, जहां आंशिक फलनों को जोड़े, अंतरिक्ष के संग्रह के रूप में तैयार किया जाता है के रूप में दिया गया बिल्कुल सभी आंशिक फलनों को चालू रखता है जिनकी सीमा के रूप में केवल उपसमुच्चय हैं का . के लिए -उत्पादक समुच्चय पाता है
रचनात्मक रूप से पढ़ें, यह किसी आंशिक फलन को जोड़ता है तत्व के साथ उस फलन सीमा में नहीं। यह गुण धर्म की असंगति पर जोर देती है -उत्पादक समुच्चय किसी विशेषण (संभवतः आंशिक) फलन के साथ। इसके नीचे सबकाउंटेबिलिटी मान्यताओं के अध्ययन में लागू किया गया है।
समुच्चय सिद्धांत
भीलों के सबसमुच्चय पर कैंटोरियन तर्क
संदर्भ सिद्धांत के रूप में हम रचनात्मक समुच्चय सिद्धांत CZF को देखते हैं, जिसमें प्रतिस्थापन की स्वयंसिद्ध स्कीमा है, विधेय पृथक्करण की स्वयंसिद्ध स्कीमा, अनंत का मजबूत अभिगृहीत, शक्ति सेटों के अस्तित्व के प्रति अज्ञेयवादी है, लेकिन इसमें वह स्वयंसिद्ध भी सम्मिलित है जो यह दावा करता है कि कोई भी फलन स्थान दिया गया है, दिया गया है समुच्चय भी हैं। इस सिद्धांत में, यह जोर देने के लिए भी संगत है कि प्रत्येक समुच्चय सबकाउंटेबल है। गिनती संख्याओं के अनंत समुच्चय पर संभावित अनुमानों के माध्यम से इस खंड में आगे के विभिन्न अभिगृहीतों की अनुकूलता पर चर्चा की गई है। . यहाँ मानक प्राकृतिक संख्याओं के मॉडल को निरूपित करेगा।
याद रखें कि फलनों के लिए , कुल कार्यक्षमता की परिभाषा के अनुसार, सभी मानों के लिए अद्वितीय वापसी मान उपस्थित होता है डोमेन में,
और सबकाउंटेबल समुच्चय के लिए, अनुमान अभी भी सबसमुच्चय पर कुल है . रचनात्मक रूप से, मौलिक रूप से कम ऐसे अस्तित्व संबंधी दावे सिद्ध होंगे।
नीचे चर्चा की गई स्थितियाँ - पॉवर क्लास बनाम ऑन फंक्शन स्पेस - दूसरे से अलग हैं: सामान्य उपवर्ग को परिभाषित करने वाले विधेय और उनके सत्य मूल्यों के विपरीत (जरूरी नहीं कि केवल सही और गलत साबित हो), फलन (जो प्रोग्रामिंग शब्दों में समाप्त हो रहा है) करता है अपने सभी उप डोमेन (के सबसेट) के लिए डेटा के बारे में सुलभ जानकारी बनाता है ). जब उनके उपसमुच्चय के लिए विशिष्ट फलन के रूप में, कार्य, उनके वापसी मूल्यों के माध्यम से, उपसमुच्चय सदस्यता तय करते हैं। जैसा कि आम तौर पर परिभाषित समुच्चय में सदस्यता जरूरी नहीं है, (कुल) फलन करता है के सभी उपसमुच्चयों के साथ स्वचालित रूप से आपत्ति में नहीं हैं . तो रचनात्मक रूप से, उपसमुच्चय विशेषता फलनों की तुलना में अधिक विस्तृत अवधारणा है। वास्तव में, सीजेडएफ के शीर्ष पर कुछ गैर-मौलिक स्वयंसिद्धों के संदर्भ में, यहां तक कि सिंगलटन की शक्ति वर्ग, उदा। कक्षा के सभी उपसमूहों में से , उचित वर्ग के रूप में दिखाया गया है।
बिजली वर्गों पर
नीचे, इस तथ्य का उपयोग किया जाता है कि विशेष स्थितियो निषेध परिचय का तात्पर्य है कि विरोधाभासी है।
सरलता से तर्क के लिए, मान लीजिए समुच्चय है। फिर उपसमुच्चय पर विचार करें और समारोह . इसके अलावा, जैसा कि कैंटर के विकर्ण तर्क|कैंटोर के प्रमेय में शक्ति समुच्चय के बारे में है, परिभाषित करें[2]
हम यह निष्कर्ष निकालते हैं कि सबकाउंटेबिलिटी स्वयंसिद्ध, सभी सेटों पर जोर देने के साथ असंगत है समुच्चय होने के नाते, जैसा निहित है उदा। पावर समुच्चय स्वयंसिद्ध द्वारा।
पॉवरसमुच्चय या इसके किसी समकक्ष के बिना मौलिक ZFC में, यह भी सुसंगत है कि वास्तविक के सभी उपवर्ग जो कि समुच्चय हैं, सबकाउंटेबल हैं। उस संदर्भ में, यह इस कथन का अनुवाद करता है कि वास्तविक संख्याओं के सभी समुच्चय गणनीय हैं।[3] बेशक, उस सिद्धांत में फलन स्पेस समुच्चय नहीं है .
फंक्शन स्पेस पर
फलन रिक्त स्थान की परिभाषा के अनुसार, समुच्चय समुच्चय के उन सबसमुच्चय को रखता है जो सिद्ध रूप से कुल और कार्यात्मक हैं। विशेष रूप से, सभी सेटों की अनुमत उपगणनीयता पर जोर देते हुए, सबकाउंटेबल समुच्चय में।
तो यहाँ हम विशेषण फलन पर विचार करते हैं और का उपसमुच्चय के रूप में अलग किया गया[4]
इस प्रकार, की उपगणनीयता अनुमति है, और वास्तव में सिद्धांत के मॉडल उपस्थित हैं। फिर भी, CZF के स्थिति में भी, पूर्ण अनुमान का अस्तित्व , डोमेन के साथ , वास्तव में विरोधाभासी है। की निर्णायक सदस्यता समुच्चय को भी गणनीय बनाता है, अर्थात बेशुमार।
इन अवलोकनों से परे, यह भी ध्यान दें कि किसी गैर-शून्य संख्या के लिए , फलन में अनुमान सम्मिलित है सभी तक नहीं बढ़ाया जा सकता है इसी तरह के विरोधाभासी तर्क से। इसे यह कहते हुए व्यक्त किया जा सकता है कि ऐसे आंशिक फलन हैं जिन्हें पूर्ण फलनों तक नहीं बढ़ाया जा सकता है . ध्यान दें कि जब दिया जाता है , कोई अनिवार्य रूप से यह तय नहीं कर सकता है कि क्या , और इसलिए कोई यह भी तय नहीं कर सकता है कि संभावित फलन एक्सटेंशन का मान चालू है या नहीं पहले से वर्णित अनुमान के लिए पहले से ही निर्धारित है .
सबकाउंटिबिलिटी स्वयंसिद्ध, सभी सेटों पर जोर देने योग्य है, किसी भी नए स्वयंसिद्ध बनाने के साथ असंगत है LEM सहित गणनीय।
मॉडल
उपरोक्त विश्लेषण के कोडिंग के औपचारिक गुणों को प्रभावित करता है . सबकाउंटेबिलिटी पोस्टुलेट्स द्वारा सीजेडएफ सिद्धांत के गैर-मौलिक विस्तार के लिए मॉडल का निर्माण किया गया है।[5] इस तरह के गैर-रचनात्मक स्वयंसिद्धों को पसंद के सिद्धांतों के रूप में देखा जा सकता है, जो,चूँकि , क्रमिक विश्लेषण | सिद्धांतों की प्रमाण-सैद्धांतिक ताकत को बहुत अधिक नहीं बढ़ाते हैं।
- IZF के ऐसे मॉडल हैं जिनमें अलग-अलग संबंधों वाले सभी समुच्चय सबकाउंटेबल हैं।[6]
- CZF का मॉडल है, उदाहरण के लिए, मार्टिन-लोफ टाइप थ्योरी . मौलिक रूप से असंख्य फलन रिक्त स्थान के साथ इस रचनात्मक समुच्चय सिद्धांत में, यह वास्तव में उपगणनीयता स्वयंसिद्ध पर जोर देने के लिए संगत है, यह कहते हुए कि प्रत्येक समुच्चय सबकाउंटेबल है। जैसा कि चर्चा की गई है, परिणामी सिद्धांत शक्ति समुच्चय के स्वयंसिद्ध और बहिष्कृत मध्य के कानून के विपरीत है।
- अभी तक अधिक मजबूत, क्रिपके-प्लेटेक समुच्चय सिद्धांत के कुछ मॉडल, फलन स्थान के बिना सिद्धांत, यह भी मान्य करता है कि सभी समुच्चय गणनीय हैं।
आकार की धारणा
जैसा कि अभिकलनीयता थ्योरी में माने जाने वाले फंक्शन स्पेस के उदाहरण में देखा गया है, न कि प्रत्येक अनंत उपसमुच्चय अनिवार्य रूप से रचनात्मक आपत्ति में है , इस प्रकार रचनात्मक संदर्भों में असंख्य सेटों के बीच अधिक परिष्कृत अंतर के लिए जगह बना रहा है। समारोह स्थान (और भी ) मध्यम रूप से समृद्ध समुच्चय सिद्धांत में हमेशा न तो परिमित पाया जाता है और न ही आपत्ति में , कैंटर के विकर्ण तर्क द्वारा। असंख्य होने का यही मतलब है। लेकिन यह तर्क कि उस समुच्चय की प्रमुखता इस प्रकार कुछ अर्थों में प्राकृतिक संख्या से अधिक होगी, केवल मौलिक आकार की अवधारणा और कार्डिनैलिटी द्वारा समुच्चय के इसके प्रेरित क्रम पर प्रतिबंध पर निर्भर करती है। उपरोक्त वर्गों से प्रेरित, अनंत समुच्चय वर्ग से छोटा माना जा सकता है . छोटे आकार के निर्णय के रूप में उपगणनीयता को कैंटोर द्वारा परिभाषित कार्डिनैलिटी संबंधों की मानक गणितीय परिभाषा के साथ नहीं जोड़ा जाएगा, छोटे कार्डिनैलिटी को इंजेक्शन के संदर्भ में परिभाषित किया जाएगा। और कार्डिनैलिटी की समानता को आक्षेपों के संदर्भ में परिभाषित किया जा रहा है। इसके अलावा, ध्यान दें कि रचनात्मक रूप से, आदेश <कार्डिनैलिटी की तरह अनिर्णीत हो सकता है।
संबंधित गुण
उपगणनीयता के समान, अनुरूप धारणा उपस्थित है जिसमेंपरिभाषा में समुच्चय के अस्तित्व द्वारा प्रतिस्थापित किया जाता है जो कि कुछ परिमित समुच्चय का सबसमुच्चय है। इस गुण धर्म को विभिन्न रूप से सबफाइनली इंडेक्स कहा जाता है।
श्रेणी सिद्धांत में ये धारणाएँ उपश्रेणियाँ हैं।
यह भी देखें
- कैंटर का विकर्ण तर्क
- संगणनीय समारोह
- रचनात्मक समुच्चय सिद्धांत
- श्रोडर-बर्नस्टीन प्रमेय
- उपभाग
- कुल आदेश
संदर्भ
- ↑ Gert Smolka, Skolems paradox and constructivism, Lecture Notes, Saarland University, Jan. 2015
- ↑ Méhkeri, Daniel (2010), A simple computational interpretation of set theory, arXiv:1005.4380
- ↑ Gitman, Victora (2011), What is the theory ZFC without power set, arXiv:1110.2430
- ↑ Bell, John L. (2004), "Russell's paradox and diagonalization in a constructive context" (PDF), in Link, Godehard (ed.), One hundred years of Russell's paradox, De Gruyter Series in Logic and its Applications, vol. 6, de Gruyter, Berlin, pp. 221–225, MR 2104745
- ↑ Rathjen, Michael (2006), "Choice principles in constructive and classical set theories" (PDF), in Chatzidakis, Zoé; Koepke, Peter; Pohlers, Wolfram (eds.), Logic Colloquium '02: Joint proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic and the Biannual Meeting of the German Association for Mathematical Logic and the Foundations of Exact Sciences (the Colloquium Logicum) held in Münster, August 3–11, 2002, Lecture Notes in Logic, vol. 27, La Jolla, CA: Association for Symbolic Logic, pp. 299–326, MR 2258712
- ↑ McCarty, Charles (1986), "Subcountability under realizability", Notre Dame Journal of Formal Logic, 27 (2): 210–220, doi:10.1305/ndjfl/1093636613, MR 0842149