उपगणनीयता: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{more footnotes|date=September 2020}}
{{more footnotes|date=September 2020}}
[[रचनात्मक गणित]] में, [[प्राकृतिक संख्या|प्राकृतिक संख्याओं]]  से आंशिक फलन प्रक्षेपण के रूप में उपस्थित होते है।  सर्जेन्ट के साथ संग्रह <math>X</math> उपगणनीय होते है। इसे इस रूप में व्यक्त किया जा सकता है
[[रचनात्मक गणित]] में, [[प्राकृतिक संख्या|प्राकृतिक संख्याओं]]  से आंशिक फलन प्रक्षेपण के रूप में उपस्थित होते है।  सर्जेन्ट के साथ संग्रह <math>X</math> सबकाउंटेबल होते है। इसे इस रूप में व्यक्त किया जा सकता है
<math display="block">\exists (I\subseteq{\mathbb N}).\, \exists f.\, (f\colon I\twoheadrightarrow X),</math>
<math display="block">\exists (I\subseteq{\mathbb N}).\, \exists f.\, (f\colon I\twoheadrightarrow X),</math>




जहाँ <math>f\colon I\twoheadrightarrow X</math> दर्शाता है <math>f</math>  विशेषण फलन होते है <math>I</math> पर <math>X</math>. अनुमान का सदस्य  <math>{\mathbb N}\rightharpoonup X</math> है और यहाँ उपवर्ग <math>I</math> का <math>{\mathbb N}</math> समुच्चय होता है। दूसरे शब्दों में,  उपगणनीय संग्रह के सभी तत्व <math>X</math> गणना संख्याओं के अनुक्रमण समुच्चय की छवि में कार्यात्मक रूप से होता है <math>I\subseteq{\mathbb N}</math> और इस प्रकार समुच्चय <math>X</math> गणनीय समुच्चय <math>{\mathbb N}</math>.के प्रभुत्व के रूप में समझा जा सकता है।
जहाँ <math>f\colon I\twoheadrightarrow X</math> दर्शाता है <math>f</math>  विशेषण फलन होते है <math>I</math> पर <math>X</math>. अनुमान का सदस्य  <math>{\mathbb N}\rightharpoonup X</math> है और यहाँ उपवर्ग <math>I</math> का <math>{\mathbb N}</math> समुच्चय होता है। दूसरे शब्दों में,  सबकाउंटेबल संग्रह के सभी तत्व <math>X</math> गणना संख्याओं के अनुक्रमण समुच्चय की छवि में कार्यात्मक रूप से होता है <math>I\subseteq{\mathbb N}</math> और इस प्रकार समुच्चय <math>X</math> गणनीय समुच्चय <math>{\mathbb N}</math>.के प्रभुत्व के रूप में समझा जा सकता है।


ध्यान दें कि गणनीयता और परिमितता गुणों का नामकरण ऐतिहासिक रूप से बहुत भिन्न होता है। यहां वाद-विवाद प्रश्न में समुच्चय अनुमानों के संदर्भ में परिभाषित लक्षण से संबंधित होता है।  
ध्यान दें कि गणनीयता और परिमितता गुणों का नामकरण ऐतिहासिक रूप से बहुत भिन्न होता है। यहां वाद-विवाद प्रश्न में समुच्चय अनुमानों के संदर्भ में परिभाषित लक्षण से संबंधित होता है।  
Line 11: Line 11:


=== उदाहरण ===
=== उदाहरण ===
महत्वपूर्ण स्थितियो है <math>X</math> कम्प्यूटेबिलिटी सिद्धांत में अध्ययन के अनुसार कार्यों के  बड़े वर्ग के कुछ उपवर्ग को दर्शाता है।
महत्वपूर्ण स्थितिया वह है जहां <math>X</math> अभिकलनीयता सिद्धांत में अध्ययन के अनुसार फलनों के  बड़े वर्ग के कुछ उपवर्ग को दर्शाता है।


कुल संगणनीय कार्यों पर विचार करें और ध्यान दें कि कुल होना  [[निर्णायकता (तर्क)]] संपत्ति नहीं है, अर्थात  कुल कार्यों और प्राकृतिक संख्याओं के बीच रचनात्मक आपत्ति नहीं हो सकती है।चूँकि , सभी संभावित आंशिक संगणनीय कार्यों (जो गैर-समाप्ति कार्यक्रमों को भी अनुमति देता है) के गोडेल नंबरिंग की गणना के माध्यम से, उन के सबसेट, जैसे कि कुल फ़ंक्शन, को सबकाउंटेबल समुच्चय के रूप में देखा जाता है। ध्यान दें कि इंडेक्स समुच्चय (रिकर्सन थ्योरी) पर राइस के प्रमेय द्वारा, अधिकांश डोमेन <math>I</math> रिकर्सिव नहीं हैं। दरअसल, सभी गिनती संख्याओं के बीच कोई प्रभावी मानचित्र नहीं है <math>{\mathbb N}</math> और अनंत (गैर-सीमित) अनुक्रमण समुच्चय <math>I</math> यहाँ जोर दिया गया है, केवल उपसमुच्चय संबंध <math>I\subseteq{\mathbb N}</math>. संख्याओं के रचनात्मक रूप से गैर-गणनीय समुच्चय का प्रभुत्व होना <math>I</math>, नाम उपगणनीय इस प्रकार प्रस्तुत है कि असंख्य समुच्चय <math>X</math> से बड़ा नहीं है <math>{\mathbb N}</math>.
कुल संगणनीय फलनों पर विचार करें और ध्यान दें कि कुल होना  [[निर्णायकता (तर्क)|निर्णायक]] गुण धर्म  नहीं है अर्थात  कुल फलनों और प्राकृतिक संख्याओं के बीच रचनात्मक अवरोध नहीं हो सकती है। चूँकि, सभी संभावित आंशिक संगणनीय फलनों के कोडों की गणना के माध्यम से उनके सबसेट, जो गैर-समाप्ति वाले फलनों को अनुमति देता है जैसे कि कुल फलनों को सबकाउंटेबल समुच्चय के रूप में देखा जाता है। ध्यान दें कि इंडेक्स समुच्चय रिकर्सन थ्योरी पर राइस के प्रमेय द्वारा, अधिकांश डोमेन सेट किए जाते हैं  <math>I</math> पुनरावर्ती नहीं हैं दरअसल, सभी गिनती संख्याओं के बीच कोई प्रभावी मानचित्र नहीं है <math>{\mathbb N}</math> और अनंत गैर सीमित अनुक्रमण समुच्चय <math>I</math> पर बल दिया गया है, केवल उपसमुच्चय संबंध <math>I\subseteq{\mathbb N}</math>. संख्याओं के रचनात्मक रूप से गैर गणनीय समुच्चय का प्रभुत्व होता है <math>I</math>, नाम सबकाउंटेबल इस प्रकार प्रस्तुत करता है कि असंख्य समुच्चय <math>X</math> से बड़ा <math>{\mathbb N}</math>.नहीं होता है


प्रदर्शन कि <math>X</math> उपगणनीय है इसका तात्पर्य यह भी है कि यह मौलिक  रूप से (गैर-रचनात्मक रूप से) औपचारिक रूप से गणनीय है, लेकिन यह किसी भी प्रभावी गणना को प्रतिबिंबित नहीं करता है। दूसरे शब्दों में, तथ्य यह है कि अनुक्रम में सभी कुल कार्यों को सूचीबद्ध करने वाले एल्गोरिदम को कोडित नहीं किया जा सकता है, समुच्चय और फलन अस्तित्व के बारे में मौलिक  सिद्धांतों द्वारा कब्जा नहीं किया जाता है। हम देखते हैं किसिद्धांत के स्वयंसिद्धों के आधार पर, उप-गणना योग्यता की तुलना में सिद्ध होने की अधिक संभावना हो सकती है।
प्रदर्शन जिसमें <math>X</math> उप-गणना के रूप में है इसका तात्पर्य यह है कि यह मौलिक  रूप से गैर-रचनात्मक रूप से गणनीय होता है, लेकिन यह किसी भी प्रभावी गणना क्षमता को प्रतिबिंबित नहीं करता है। दूसरे शब्दों में, इसका तात्पर्य यह है कि अनुक्रम में सभी फलनों को सूचीबद्ध करने वाले कलन विधि को कोडित नहीं किया जाता है, समुच्चय और फलन अस्तित्व के बारे में मौलिक  स्वयंसिद्धि से अभिगृहीत नहीं किया गया है। हम देखते हैं कि किसी सिद्धांत के स्वयंसिद्धों के आधार पर, उप-गणना योग्यता की तुलना में सिद्ध होने की अधिक संभावना होती है।


=== बहिष्कृत मध्य === से संबंध
=== बहिष्कृत मध्य से संबंध ===
रचनात्मक लॉजिक्स और [[रचनात्मक सेट सिद्धांत|रचनात्मक समुच्चय सिद्धांत]] में निर्णायकता (तर्क) और संभवतः प्रभावी विधि के प्रश्नों के लिए अनंत (गैर-परिमित) समुच्चय के बीच  फलन के अस्तित्व को बाँधते हैं। वहां, सबकाउंटेबिलिटी प्रॉपर्टी काउंटेबिलिटी से अलग हो जाती है और इस तरह यह  निरर्थक धारणा नहीं है।
रचनात्मक लॉजिक्स और [[रचनात्मक सेट सिद्धांत|रचनात्मक समुच्चय सिद्धांत]] में निर्णायकता (तर्क) और संभवतः प्रभावी विधि के प्रश्नों के लिए अनंत (गैर-परिमित) समुच्चय के बीच  फलन के अस्तित्व को बाँधते हैं। वहां, सबकाउंटेबिलिटी प्रॉपर्टी काउंटेबिलिटी से अलग हो जाती है और इस तरह यह  निरर्थक धारणा नहीं है।
अनुक्रमण समुच्चय <math>I</math> प्राकृतिक संख्याओं का अस्तित्व माना जा सकता है, उदा। विशिष्टता के स्वयंसिद्ध स्कीमा जैसे समुच्चय सैद्धांतिक स्वयंसिद्धों के माध्यम से  सबसमुच्चय के रूप में। फिर की परिभाषा के द्वारा <math>I\subseteq{\mathbb N}</math>,
अनुक्रमण समुच्चय <math>I</math> प्राकृतिक संख्याओं का अस्तित्व माना जा सकता है, उदा। विशिष्टता के स्वयंसिद्ध स्कीमा जैसे समुच्चय सैद्धांतिक स्वयंसिद्धों के माध्यम से  सबसमुच्चय के रूप में। फिर की परिभाषा के द्वारा <math>I\subseteq{\mathbb N}</math>,
Line 25: Line 25:
इसे स्वयंसिद्ध माने बिना सिद्ध नहीं किया जा सकता है।
इसे स्वयंसिद्ध माने बिना सिद्ध नहीं किया जा सकता है।
सबकाउंटेबल समुच्चय को प्रभावी प्रारूप  से गिनने में कोई विफल हो सकता है <math>X</math> यदि कोई गिनती की संख्या को मैप करने में विफल रहता है <math>{\mathbb N}</math> अनुक्रमण समुच्चय में <math>I</math>, इस कारण से।
सबकाउंटेबल समुच्चय को प्रभावी प्रारूप  से गिनने में कोई विफल हो सकता है <math>X</math> यदि कोई गिनती की संख्या को मैप करने में विफल रहता है <math>{\mathbb N}</math> अनुक्रमण समुच्चय में <math>I</math>, इस कारण से।
गणनीय होने का अर्थ है उपगणनीय होना। लेकिन आम तौर पर बातचीत बहिष्कृत मध्य के कानून पर जोर देने के बिना नहीं होती है, अर्थात  सभी प्रस्तावों के लिए <math>\phi</math> रखती है <math>\phi\lor \neg \phi</math>.
गणनीय होने का अर्थ है सबकाउंटेबल होना। लेकिन आम तौर पर बातचीत बहिष्कृत मध्य के कानून पर जोर देने के बिना नहीं होती है, अर्थात  सभी प्रस्तावों के लिए <math>\phi</math> रखती है <math>\phi\lor \neg \phi</math>.


==== मौलिक  गणित में ====
==== मौलिक  गणित में ====
मौलिक  तर्क के सभी कानूनों पर जोर देते हुए, की वियोगात्मक संपत्ति <math>I</math> ऊपर चर्चा वास्तव में सभी सेटों के लिए है। फिर, गैर-खाली के लिए <math>X</math>, गुण संख्या (जो यहाँ मतलब होगा कि <math>X</math> में इंजेक्ट करता है <math>{\mathbb N}</math>), गणनीय (<math>{\mathbb N}</math> है <math>X</math> इसकी सीमा के रूप में), सबकाउंटेबल (का  सबसमुच्चय <math>{\mathbb N}</math> में डालता है <math>X</math>) और नहीं भी <math>\omega</math>-उत्पादक ( गणनीयता संपत्ति अनिवार्य रूप से सबसमुच्चय के संदर्भ में परिभाषित की गई है <math>X</math>) सभी समतुल्य हैं और व्यक्त करते हैं कि  समुच्चय परिमित समुच्चय या [[गणनीय रूप से अनंत]] है।
मौलिक  तर्क के सभी कानूनों पर जोर देते हुए, की वियोगात्मक गुण धर्म  <math>I</math> ऊपर चर्चा वास्तव में सभी सेटों के लिए है। फिर, गैर-खाली के लिए <math>X</math>, गुण संख्या (जो यहाँ मतलब होगा कि <math>X</math> में इंजेक्ट करता है <math>{\mathbb N}</math>), गणनीय (<math>{\mathbb N}</math> है <math>X</math> इसकी सीमा के रूप में), सबकाउंटेबल (का  सबसमुच्चय <math>{\mathbb N}</math> में डालता है <math>X</math>) और नहीं भी <math>\omega</math>-उत्पादक ( गणनीयता गुण धर्म  अनिवार्य रूप से सबसमुच्चय के संदर्भ में परिभाषित की गई है <math>X</math>) सभी समतुल्य हैं और व्यक्त करते हैं कि  समुच्चय परिमित समुच्चय या [[गणनीय रूप से अनंत]] है।


==== गैर-मौलिक  अभिकथन ====
==== गैर-मौलिक  अभिकथन ====
Line 34: Line 34:
ध्यान दें कि  रचनात्मक सेटिंग में, फलन स्थान के बारे में  काउंटेबिलिटी का दावा <math>{\mathbb N}^{\mathbb N}</math> पूरे समुच्चय से बाहर <math>{\mathbb N}</math>, के रूप में <math>{\mathbb N}\twoheadrightarrow{\mathbb N}^{\mathbb N}</math>, खंडन किया जा सकता है। लेकिन उपगणनीयता <math>I\twoheadrightarrow{\mathbb N}^{\mathbb N}</math>  असंख्य समुच्चय का <math>{\mathbb N}^{\mathbb N}</math>  समुच्चय द्वारा <math>I\subseteq{\mathbb N}</math> से प्रभावी रूप से अलग करने योग्य नहीं है <math>{\mathbb N}</math> अनुमति दी जा सकती है।
ध्यान दें कि  रचनात्मक सेटिंग में, फलन स्थान के बारे में  काउंटेबिलिटी का दावा <math>{\mathbb N}^{\mathbb N}</math> पूरे समुच्चय से बाहर <math>{\mathbb N}</math>, के रूप में <math>{\mathbb N}\twoheadrightarrow{\mathbb N}^{\mathbb N}</math>, खंडन किया जा सकता है। लेकिन उपगणनीयता <math>I\twoheadrightarrow{\mathbb N}^{\mathbb N}</math>  असंख्य समुच्चय का <math>{\mathbb N}^{\mathbb N}</math>  समुच्चय द्वारा <math>I\subseteq{\mathbb N}</math> से प्रभावी रूप से अलग करने योग्य नहीं है <math>{\mathbb N}</math> अनुमति दी जा सकती है।


जैसा <math>{\mathbb N}^{\mathbb N}</math> असंख्य है और मौलिक  रूप से उपगणनीय नहीं है, इसके बड़े फलन स्थान के साथ मौलिक  ढांचा चर्च की थीसिस (रचनात्मक गणित) के साथ असंगत है। रचनात्मक चर्च की थीसिस, रूसी रचनावाद का  स्वयंसिद्ध।
जैसा <math>{\mathbb N}^{\mathbb N}</math> असंख्य है और मौलिक  रूप से सबकाउंटेबल नहीं है, इसके बड़े फलन स्थान के साथ मौलिक  ढांचा चर्च की थीसिस (रचनात्मक गणित) के साथ असंगत है। रचनात्मक चर्च की थीसिस, रूसी रचनावाद का  स्वयंसिद्ध।


=== उपगणनीय और ω-उत्पादक परस्पर अनन्य === हैं
=== सबकाउंटेबल और ω-उत्पादक परस्पर अनन्य === हैं
समुच्चय <math>X</math> कहा जाएगा <math>\omega</math>[[रचनात्मक और उत्पादक सेट|रचनात्मक और उत्पादक]] समुच्चय अगर, जब भी इसका कोई सबसमुच्चय <math>W\subset X</math> किसी फलन का वह  कार्यक्षेत्र  है जिस पर कोई आंशिक फलन है <math>{\mathbb N}</math>, वहाँ हमेशा  तत्व उपस्थित होता है <math>d\in X\setminus W</math> जो उस सीमा के पूरक में रहता है।<ref>Gert Smolka, [https://cpb-us-w2.wpmucdn.com/u.osu.edu/dist/a/4597/files/2014/09/mccarty_tennant_jpl1987-1ncyai0.pdf ''Skolems paradox and constructivism''], Lecture Notes, Saarland University, Jan. 2015</ref> यदि कुछ पर कोई अनुमान उपस्थित है <math>X</math>, तो वर्णित अनुसार इसकी संबंधित प्रशंसा खाली समुच्चय के बराबर होगी <math>X\setminus X</math>, और इसलिए  सबकाउंटेबल समुच्चय कभी नहीं होता है <math>\omega</math>-उत्पादक।
समुच्चय <math>X</math> कहा जाएगा <math>\omega</math>[[रचनात्मक और उत्पादक सेट|रचनात्मक और उत्पादक]] समुच्चय अगर, जब भी इसका कोई सबसमुच्चय <math>W\subset X</math> किसी फलन का वह  कार्यक्षेत्र  है जिस पर कोई आंशिक फलन है <math>{\mathbb N}</math>, वहाँ हमेशा  तत्व उपस्थित होता है <math>d\in X\setminus W</math> जो उस सीमा के पूरक में रहता है।<ref>Gert Smolka, [https://cpb-us-w2.wpmucdn.com/u.osu.edu/dist/a/4597/files/2014/09/mccarty_tennant_jpl1987-1ncyai0.pdf ''Skolems paradox and constructivism''], Lecture Notes, Saarland University, Jan. 2015</ref> यदि कुछ पर कोई अनुमान उपस्थित है <math>X</math>, तो वर्णित अनुसार इसकी संबंधित प्रशंसा खाली समुच्चय के बराबर होगी <math>X\setminus X</math>, और इसलिए  सबकाउंटेबल समुच्चय कभी नहीं होता है <math>\omega</math>-उत्पादक।
जैसा कि ऊपर परिभाषित किया गया है, होने की संपत्ति <math>\omega</math>-उत्पादक सीमा को जोड़ता है <math>W</math> किसी विशेष मान के किसी भी आंशिक फलन का <math>d\in X</math> कार्यों की श्रेणी में नहीं। इस प्रकार, होना <math>\omega</math>-उत्पादक बोलता है कि सभी तत्वों को उत्पन्न करना कितना कठिन है <math>X</math>: उन्हें  ही फंक्शन का उपयोग करके उत्पन्न नहीं किया जा सकता है। <math>\omega</math>वें>-उत्पादकता संपत्ति उपगणनीयता में बाधा उत्पन्न करती है। जैसा कि यह बेशुमारता का भी अर्थ है, कैंटर के विकर्ण तर्क में  अधिकांशतः  यह धारणा सम्मिलित  होती है, स्पष्ट रूप से सत्तर के दशक के अंत से।
जैसा कि ऊपर परिभाषित किया गया है, होने की गुण धर्म  <math>\omega</math>-उत्पादक सीमा को जोड़ता है <math>W</math> किसी विशेष मान के किसी भी आंशिक फलन का <math>d\in X</math> फलनों की श्रेणी में नहीं। इस प्रकार, होना <math>\omega</math>-उत्पादक बोलता है कि सभी तत्वों को उत्पन्न करना कितना कठिन है <math>X</math>: उन्हें  ही फंक्शन का उपयोग करके उत्पन्न नहीं किया जा सकता है। <math>\omega</math>वें>-उत्पादकता गुण धर्म  उपगणनीयता में बाधा उत्पन्न करती है। जैसा कि यह बेशुमारता का भी अर्थ है, कैंटर के विकर्ण तर्क में  अधिकांशतः  यह धारणा सम्मिलित  होती है, स्पष्ट रूप से सत्तर के दशक के अंत से।


कोई गणना योग्य गणना की असंभवता स्थापित कर सकता है <math>X</math> केवल संगणनीय रूप से [[गणना योग्य]] सबसमुच्चय पर विचार करके <math>W</math> और किसी को सभी बाधाओं के समुच्चय की आवश्यकता हो सकती है <math>d</math>कुल पुनरावर्ती तथाकथित उत्पादन फलन की छवि होना चाहिए।
कोई गणना योग्य गणना की असंभवता स्थापित कर सकता है <math>X</math> केवल संगणनीय रूप से [[गणना योग्य]] सबसमुच्चय पर विचार करके <math>W</math> और किसी को सभी बाधाओं के समुच्चय की आवश्यकता हो सकती है <math>d</math>कुल पुनरावर्ती तथाकथित उत्पादन फलन की छवि होना चाहिए।


समुच्चय थ्योरी में, जहां आंशिक कार्यों को जोड़े, अंतरिक्ष के संग्रह के रूप में तैयार किया जाता है <math>{\mathbb N}\rightharpoonup X</math> के रूप में दिया गया <math>\cup_{I\subseteq{\mathbb N}} X^I</math> बिल्कुल सभी आंशिक कार्यों को चालू रखता है <math>{\mathbb N}</math> जिनकी सीमा के रूप में केवल उपसमुच्चय हैं <math>W</math> का <math>X</math>.
समुच्चय थ्योरी में, जहां आंशिक फलनों को जोड़े, अंतरिक्ष के संग्रह के रूप में तैयार किया जाता है <math>{\mathbb N}\rightharpoonup X</math> के रूप में दिया गया <math>\cup_{I\subseteq{\mathbb N}} X^I</math> बिल्कुल सभी आंशिक फलनों को चालू रखता है <math>{\mathbb N}</math> जिनकी सीमा के रूप में केवल उपसमुच्चय हैं <math>W</math> का <math>X</math>.
के लिए <math>\omega</math>-उत्पादक समुच्चय <math>X</math>  पाता है
के लिए <math>\omega</math>-उत्पादक समुच्चय <math>X</math>  पाता है
:<math>\forall (w\in({\mathbb N}\rightharpoonup X)). \exists (d\in X). \neg\exists(n\in{\mathbb N}). w(n) = d.</math>
:<math>\forall (w\in({\mathbb N}\rightharpoonup X)). \exists (d\in X). \neg\exists(n\in{\mathbb N}). w(n) = d.</math>
रचनात्मक रूप से पढ़ें, यह किसी आंशिक फलन को जोड़ता है <math>w</math>  तत्व के साथ <math>d</math> उस फलन सीमा में नहीं।
रचनात्मक रूप से पढ़ें, यह किसी आंशिक फलन को जोड़ता है <math>w</math>  तत्व के साथ <math>d</math> उस फलन सीमा में नहीं।
यह संपत्ति की असंगति पर जोर देती है <math>\omega</math>-उत्पादक समुच्चय <math>X</math> किसी विशेषण (संभवतः आंशिक) फलन के साथ। इसके नीचे सबकाउंटेबिलिटी मान्यताओं के अध्ययन में लागू किया गया है।
यह  गुण धर्म  की असंगति पर जोर देती है <math>\omega</math>-उत्पादक समुच्चय <math>X</math> किसी विशेषण (संभवतः आंशिक) फलन के साथ। इसके नीचे सबकाउंटेबिलिटी मान्यताओं के अध्ययन में लागू किया गया है।


== समुच्चय सिद्धांत ==
== समुच्चय सिद्धांत ==


=== भीलों के सबसमुच्चय पर कैंटोरियन तर्क ===
=== भीलों के सबसमुच्चय पर कैंटोरियन तर्क ===
संदर्भ सिद्धांत के रूप में हम रचनात्मक समुच्चय सिद्धांत CZF को देखते हैं, जिसमें [[प्रतिस्थापन की स्वयंसिद्ध स्कीमा]] है, [[विधेय पृथक्करण की स्वयंसिद्ध स्कीमा]], अनंत का मजबूत अभिगृहीत, शक्ति सेटों के अस्तित्व के प्रति अज्ञेयवादी है, लेकिन इसमें वह स्वयंसिद्ध भी सम्मिलित  है जो यह दावा करता है कि कोई भी फलन स्थान <math>Y^X</math> दिया गया है, दिया गया है <math>X, Y</math> समुच्चय भी हैं। इस सिद्धांत में, यह जोर देने के लिए भी संगत है कि प्रत्येक समुच्चय उपगणनीय है।
संदर्भ सिद्धांत के रूप में हम रचनात्मक समुच्चय सिद्धांत CZF को देखते हैं, जिसमें [[प्रतिस्थापन की स्वयंसिद्ध स्कीमा]] है, [[विधेय पृथक्करण की स्वयंसिद्ध स्कीमा]], अनंत का मजबूत अभिगृहीत, शक्ति सेटों के अस्तित्व के प्रति अज्ञेयवादी है, लेकिन इसमें वह स्वयंसिद्ध भी सम्मिलित  है जो यह दावा करता है कि कोई भी फलन स्थान <math>Y^X</math> दिया गया है, दिया गया है <math>X, Y</math> समुच्चय भी हैं। इस सिद्धांत में, यह जोर देने के लिए भी संगत है कि प्रत्येक समुच्चय सबकाउंटेबल है।
गिनती संख्याओं के अनंत समुच्चय पर संभावित अनुमानों के माध्यम से इस खंड में आगे के विभिन्न अभिगृहीतों की अनुकूलता पर चर्चा की गई है। <math>I\subseteq {\mathbb N}</math>. यहाँ <math>{\mathbb N}</math> मानक प्राकृतिक संख्याओं के  मॉडल को निरूपित करेगा।
गिनती संख्याओं के अनंत समुच्चय पर संभावित अनुमानों के माध्यम से इस खंड में आगे के विभिन्न अभिगृहीतों की अनुकूलता पर चर्चा की गई है। <math>I\subseteq {\mathbb N}</math>. यहाँ <math>{\mathbb N}</math> मानक प्राकृतिक संख्याओं के  मॉडल को निरूपित करेगा।


याद रखें कि कार्यों के लिए <math>g\colon X\to Y</math>, कुल कार्यक्षमता की परिभाषा के अनुसार, सभी मानों के लिए  अद्वितीय वापसी मान उपस्थित होता है <math>x\in X</math> डोमेन में,
याद रखें कि फलनों के लिए <math>g\colon X\to Y</math>, कुल कार्यक्षमता की परिभाषा के अनुसार, सभी मानों के लिए  अद्वितीय वापसी मान उपस्थित होता है <math>x\in X</math> डोमेन में,
:<math>\exists!(y\in Y). g(x)=y,</math>
:<math>\exists!(y\in Y). g(x)=y,</math>
और  सबकाउंटेबल समुच्चय के लिए, अनुमान अभी भी  सबसमुच्चय पर कुल है <math>{\mathbb N}</math>. रचनात्मक रूप से, मौलिक  रूप से कम ऐसे अस्तित्व संबंधी दावे सिद्ध होंगे।
और  सबकाउंटेबल समुच्चय के लिए, अनुमान अभी भी  सबसमुच्चय पर कुल है <math>{\mathbb N}</math>. रचनात्मक रूप से, मौलिक  रूप से कम ऐसे अस्तित्व संबंधी दावे सिद्ध होंगे।


नीचे चर्चा की गई स्थितियाँ - पॉवर क्लास बनाम ऑन फंक्शन स्पेस -  दूसरे से अलग हैं: सामान्य उपवर्ग को परिभाषित करने वाले विधेय और उनके सत्य मूल्यों के विपरीत (जरूरी नहीं कि केवल सही और गलत साबित हो),  फलन (जो प्रोग्रामिंग शब्दों में समाप्त हो रहा है) करता है अपने सभी उप डोमेन (के सबसेट) के लिए डेटा के बारे में सुलभ जानकारी बनाता है <math>X</math>). जब उनके उपसमुच्चय के लिए विशिष्ट फलन के रूप में, कार्य, उनके वापसी मूल्यों के माध्यम से, उपसमुच्चय सदस्यता तय करते हैं। जैसा कि आम तौर पर परिभाषित समुच्चय में सदस्यता जरूरी नहीं है, (कुल) फलन करता है <math>X\to\{0,1\}</math> के सभी उपसमुच्चयों के साथ स्वचालित रूप से आपत्ति में नहीं हैं <math>X</math>. तो रचनात्मक रूप से, उपसमुच्चय विशेषता कार्यों की तुलना में अधिक विस्तृत अवधारणा है। वास्तव में, सीजेडएफ के शीर्ष पर कुछ गैर-मौलिक  स्वयंसिद्धों के संदर्भ में, यहां तक ​​कि  सिंगलटन की शक्ति वर्ग, उदा। कक्षा <math>{\mathcal P}\{0\}</math> के सभी उपसमूहों में से <math>\{0\}</math>,  उचित वर्ग के रूप में दिखाया गया है।
नीचे चर्चा की गई स्थितियाँ - पॉवर क्लास बनाम ऑन फंक्शन स्पेस -  दूसरे से अलग हैं: सामान्य उपवर्ग को परिभाषित करने वाले विधेय और उनके सत्य मूल्यों के विपरीत (जरूरी नहीं कि केवल सही और गलत साबित हो),  फलन (जो प्रोग्रामिंग शब्दों में समाप्त हो रहा है) करता है अपने सभी उप डोमेन (के सबसेट) के लिए डेटा के बारे में सुलभ जानकारी बनाता है <math>X</math>). जब उनके उपसमुच्चय के लिए विशिष्ट फलन के रूप में, कार्य, उनके वापसी मूल्यों के माध्यम से, उपसमुच्चय सदस्यता तय करते हैं। जैसा कि आम तौर पर परिभाषित समुच्चय में सदस्यता जरूरी नहीं है, (कुल) फलन करता है <math>X\to\{0,1\}</math> के सभी उपसमुच्चयों के साथ स्वचालित रूप से आपत्ति में नहीं हैं <math>X</math>. तो रचनात्मक रूप से, उपसमुच्चय विशेषता फलनों की तुलना में अधिक विस्तृत अवधारणा है। वास्तव में, सीजेडएफ के शीर्ष पर कुछ गैर-मौलिक  स्वयंसिद्धों के संदर्भ में, यहां तक ​​कि  सिंगलटन की शक्ति वर्ग, उदा। कक्षा <math>{\mathcal P}\{0\}</math> के सभी उपसमूहों में से <math>\{0\}</math>,  उचित वर्ग के रूप में दिखाया गया है।


==== बिजली वर्गों पर ====
==== बिजली वर्गों पर ====
Line 75: Line 75:
हम यह निष्कर्ष निकालते हैं कि सबकाउंटेबिलिटी स्वयंसिद्ध, सभी सेटों पर जोर देने के साथ असंगत है <math>{\mathcal P}{\mathbb N}</math>  समुच्चय होने के नाते, जैसा निहित है उदा। पावर समुच्चय स्वयंसिद्ध द्वारा।
हम यह निष्कर्ष निकालते हैं कि सबकाउंटेबिलिटी स्वयंसिद्ध, सभी सेटों पर जोर देने के साथ असंगत है <math>{\mathcal P}{\mathbb N}</math>  समुच्चय होने के नाते, जैसा निहित है उदा। पावर समुच्चय स्वयंसिद्ध द्वारा।


पॉवरसमुच्चय या इसके किसी समकक्ष के बिना मौलिक  ZFC में, यह भी सुसंगत है कि वास्तविक के सभी उपवर्ग जो कि समुच्चय हैं, उपगणनीय हैं। उस संदर्भ में, यह इस कथन का अनुवाद करता है कि वास्तविक संख्याओं के सभी समुच्चय गणनीय हैं।<ref>{{citation|first=Victora|last=Gitman|arxiv=1110.2430|title=What is the theory ZFC without power set|year=2011}}</ref> बेशक, उस सिद्धांत में फलन स्पेस समुच्चय नहीं है <math>{\mathbb N}^{\mathbb N}</math>.
पॉवरसमुच्चय या इसके किसी समकक्ष के बिना मौलिक  ZFC में, यह भी सुसंगत है कि वास्तविक के सभी उपवर्ग जो कि समुच्चय हैं, सबकाउंटेबल हैं। उस संदर्भ में, यह इस कथन का अनुवाद करता है कि वास्तविक संख्याओं के सभी समुच्चय गणनीय हैं।<ref>{{citation|first=Victora|last=Gitman|arxiv=1110.2430|title=What is the theory ZFC without power set|year=2011}}</ref> बेशक, उस सिद्धांत में फलन स्पेस समुच्चय नहीं है <math>{\mathbb N}^{\mathbb N}</math>.


==== फंक्शन स्पेस पर ====
==== फंक्शन स्पेस पर ====
फलन रिक्त स्थान की परिभाषा के अनुसार, समुच्चय <math>{\mathbb N}^{\mathbb N}</math> समुच्चय के उन सबसमुच्चय को रखता है <math>{\mathbb N}\times{\mathbb N}</math> जो सिद्ध रूप से कुल और कार्यात्मक हैं।
फलन रिक्त स्थान की परिभाषा के अनुसार, समुच्चय <math>{\mathbb N}^{\mathbb N}</math> समुच्चय के उन सबसमुच्चय को रखता है <math>{\mathbb N}\times{\mathbb N}</math> जो सिद्ध रूप से कुल और कार्यात्मक हैं।
विशेष रूप से, सभी सेटों की अनुमत उपगणनीयता पर जोर देते हुए, <math>{\mathbb N}^{\mathbb N}</math>  उपगणनीय समुच्चय में।
विशेष रूप से, सभी सेटों की अनुमत उपगणनीयता पर जोर देते हुए, <math>{\mathbb N}^{\mathbb N}</math>  सबकाउंटेबल समुच्चय में।


तो यहाँ हम  विशेषण फलन पर विचार करते हैं <math>f\colon I\twoheadrightarrow{\mathbb N}^{\mathbb N}</math> और का उपसमुच्चय <math>{\mathbb N}\times{\mathbb N}</math> के रूप में अलग किया गया<ref>{{citation
तो यहाँ हम  विशेषण फलन पर विचार करते हैं <math>f\colon I\twoheadrightarrow{\mathbb N}^{\mathbb N}</math> और का उपसमुच्चय <math>{\mathbb N}\times{\mathbb N}</math> के रूप में अलग किया गया<ref>{{citation
Line 102: Line 102:
इस प्रकार, की उपगणनीयता <math>{\mathbb N}^{\mathbb N}</math> अनुमति है, और वास्तव में सिद्धांत के मॉडल उपस्थित हैं। फिर भी, CZF के स्थिति  में भी,  पूर्ण अनुमान का अस्तित्व <math>{\mathbb N}\twoheadrightarrow{\mathbb N}^{\mathbb N}</math>, डोमेन के साथ <math>{\mathbb N}</math>, वास्तव में विरोधाभासी है। की निर्णायक सदस्यता <math>I={\mathbb N}</math> समुच्चय को भी गणनीय बनाता है, अर्थात बेशुमार।
इस प्रकार, की उपगणनीयता <math>{\mathbb N}^{\mathbb N}</math> अनुमति है, और वास्तव में सिद्धांत के मॉडल उपस्थित हैं। फिर भी, CZF के स्थिति  में भी,  पूर्ण अनुमान का अस्तित्व <math>{\mathbb N}\twoheadrightarrow{\mathbb N}^{\mathbb N}</math>, डोमेन के साथ <math>{\mathbb N}</math>, वास्तव में विरोधाभासी है। की निर्णायक सदस्यता <math>I={\mathbb N}</math> समुच्चय को भी गणनीय बनाता है, अर्थात बेशुमार।


इन अवलोकनों से परे, यह भी ध्यान दें कि किसी गैर-शून्य संख्या के लिए <math>a</math>, फलन <math>i\mapsto f(i)(i)+a</math> में <math>I\to{\mathbb N}</math> अनुमान सम्मिलित  है <math>f</math> सभी तक नहीं बढ़ाया जा सकता है <math>{\mathbb N}</math> इसी तरह के विरोधाभासी तर्क से। इसे यह कहते हुए व्यक्त किया जा सकता है कि ऐसे आंशिक फलन हैं जिन्हें पूर्ण कार्यों तक नहीं बढ़ाया जा सकता है <math>{\mathbb N}\to{\mathbb N}</math>.
इन अवलोकनों से परे, यह भी ध्यान दें कि किसी गैर-शून्य संख्या के लिए <math>a</math>, फलन <math>i\mapsto f(i)(i)+a</math> में <math>I\to{\mathbb N}</math> अनुमान सम्मिलित  है <math>f</math> सभी तक नहीं बढ़ाया जा सकता है <math>{\mathbb N}</math> इसी तरह के विरोधाभासी तर्क से। इसे यह कहते हुए व्यक्त किया जा सकता है कि ऐसे आंशिक फलन हैं जिन्हें पूर्ण फलनों तक नहीं बढ़ाया जा सकता है <math>{\mathbb N}\to{\mathbb N}</math>.
ध्यान दें कि जब दिया जाता है <math>n\in{\mathbb N}</math>, कोई अनिवार्य रूप से यह तय नहीं कर सकता है कि क्या <math>n\in I</math>, और इसलिए कोई यह भी तय नहीं कर सकता है कि संभावित फलन एक्सटेंशन का मान चालू है या नहीं <math>n</math> पहले से वर्णित अनुमान के लिए पहले से ही निर्धारित है <math>f</math>.
ध्यान दें कि जब दिया जाता है <math>n\in{\mathbb N}</math>, कोई अनिवार्य रूप से यह तय नहीं कर सकता है कि क्या <math>n\in I</math>, और इसलिए कोई यह भी तय नहीं कर सकता है कि संभावित फलन एक्सटेंशन का मान चालू है या नहीं <math>n</math> पहले से वर्णित अनुमान के लिए पहले से ही निर्धारित है <math>f</math>.


Line 134: Line 134:
  | year = 1986| doi-access = free
  | year = 1986| doi-access = free
  }}</ref>
  }}</ref>
* CZF का  मॉडल है, उदाहरण के लिए, मार्टिन-लोफ टाइप थ्योरी <math>{\mathsf {ML_1V}}</math>. मौलिक  रूप से असंख्य फलन रिक्त स्थान के साथ इस रचनात्मक समुच्चय सिद्धांत में, यह वास्तव में उपगणनीयता स्वयंसिद्ध पर जोर देने के लिए संगत है, यह कहते हुए कि प्रत्येक समुच्चय उपगणनीय है। जैसा कि चर्चा की गई है, परिणामी सिद्धांत शक्ति समुच्चय के स्वयंसिद्ध और बहिष्कृत मध्य के कानून के विपरीत है।
* CZF का  मॉडल है, उदाहरण के लिए, मार्टिन-लोफ टाइप थ्योरी <math>{\mathsf {ML_1V}}</math>. मौलिक  रूप से असंख्य फलन रिक्त स्थान के साथ इस रचनात्मक समुच्चय सिद्धांत में, यह वास्तव में उपगणनीयता स्वयंसिद्ध पर जोर देने के लिए संगत है, यह कहते हुए कि प्रत्येक समुच्चय सबकाउंटेबल है। जैसा कि चर्चा की गई है, परिणामी सिद्धांत शक्ति समुच्चय के स्वयंसिद्ध और बहिष्कृत मध्य के कानून के विपरीत है।
* अभी तक अधिक मजबूत, क्रिपके-प्लेटेक समुच्चय सिद्धांत के कुछ मॉडल, फलन स्थान के बिना  सिद्धांत, यह भी मान्य करता है कि सभी समुच्चय गणनीय हैं।
* अभी तक अधिक मजबूत, क्रिपके-प्लेटेक समुच्चय सिद्धांत के कुछ मॉडल, फलन स्थान के बिना  सिद्धांत, यह भी मान्य करता है कि सभी समुच्चय गणनीय हैं।


=== आकार की धारणा ===
=== आकार की धारणा ===
जैसा कि कम्प्यूटेबिलिटी थ्योरी में माने जाने वाले फंक्शन स्पेस के उदाहरण में देखा गया है, न कि प्रत्येक अनंत उपसमुच्चय <math>{\mathbb N}</math> अनिवार्य रूप से रचनात्मक आपत्ति में है <math>{\mathbb N}</math>, इस प्रकार रचनात्मक संदर्भों में असंख्य सेटों के बीच अधिक परिष्कृत अंतर के लिए जगह बना रहा है। समारोह स्थान <math>{\mathbb N}^{\mathbb N}</math> (और भी <math> \{0,1\}^{\mathbb N} </math>) मध्यम रूप से समृद्ध समुच्चय सिद्धांत में हमेशा न तो परिमित पाया जाता है और न ही आपत्ति में <math> {\mathbb N} </math>, कैंटर के विकर्ण तर्क द्वारा। असंख्य होने का यही मतलब है। लेकिन यह तर्क कि उस समुच्चय की [[प्रमुखता]] इस प्रकार कुछ अर्थों में प्राकृतिक संख्या से अधिक होगी, केवल मौलिक  आकार की अवधारणा और कार्डिनैलिटी द्वारा समुच्चय के इसके प्रेरित क्रम पर प्रतिबंध पर निर्भर करती है। उपरोक्त वर्गों से प्रेरित, अनंत समुच्चय <math>{\mathbb N}^{\mathbb N}</math> वर्ग से छोटा माना जा सकता है <math>{\mathcal P}{\mathbb N}</math>. छोटे आकार के निर्णय के रूप में उपगणनीयता को कैंटोर द्वारा परिभाषित कार्डिनैलिटी संबंधों की मानक गणितीय परिभाषा के साथ नहीं जोड़ा जाएगा, छोटे कार्डिनैलिटी को इंजेक्शन के संदर्भ में परिभाषित किया जाएगा। <math>X</math> और कार्डिनैलिटी की समानता को आक्षेपों के संदर्भ में परिभाषित किया जा रहा है। इसके अलावा, ध्यान दें कि रचनात्मक रूप से,  आदेश <कार्डिनैलिटी की तरह अनिर्णीत हो सकता है।
जैसा कि अभिकलनीयता थ्योरी में माने जाने वाले फंक्शन स्पेस के उदाहरण में देखा गया है, न कि प्रत्येक अनंत उपसमुच्चय <math>{\mathbb N}</math> अनिवार्य रूप से रचनात्मक आपत्ति में है <math>{\mathbb N}</math>, इस प्रकार रचनात्मक संदर्भों में असंख्य सेटों के बीच अधिक परिष्कृत अंतर के लिए जगह बना रहा है। समारोह स्थान <math>{\mathbb N}^{\mathbb N}</math> (और भी <math> \{0,1\}^{\mathbb N} </math>) मध्यम रूप से समृद्ध समुच्चय सिद्धांत में हमेशा न तो परिमित पाया जाता है और न ही आपत्ति में <math> {\mathbb N} </math>, कैंटर के विकर्ण तर्क द्वारा। असंख्य होने का यही मतलब है। लेकिन यह तर्क कि उस समुच्चय की [[प्रमुखता]] इस प्रकार कुछ अर्थों में प्राकृतिक संख्या से अधिक होगी, केवल मौलिक  आकार की अवधारणा और कार्डिनैलिटी द्वारा समुच्चय के इसके प्रेरित क्रम पर प्रतिबंध पर निर्भर करती है। उपरोक्त वर्गों से प्रेरित, अनंत समुच्चय <math>{\mathbb N}^{\mathbb N}</math> वर्ग से छोटा माना जा सकता है <math>{\mathcal P}{\mathbb N}</math>. छोटे आकार के निर्णय के रूप में उपगणनीयता को कैंटोर द्वारा परिभाषित कार्डिनैलिटी संबंधों की मानक गणितीय परिभाषा के साथ नहीं जोड़ा जाएगा, छोटे कार्डिनैलिटी को इंजेक्शन के संदर्भ में परिभाषित किया जाएगा। <math>X</math> और कार्डिनैलिटी की समानता को आक्षेपों के संदर्भ में परिभाषित किया जा रहा है। इसके अलावा, ध्यान दें कि रचनात्मक रूप से,  आदेश <कार्डिनैलिटी की तरह अनिर्णीत हो सकता है।


== संबंधित गुण ==
== संबंधित गुण ==
उपगणनीयता के समान, अनुरूप धारणा उपस्थित है जिसमें<math>\exists(I\subseteq{\mathbb N})</math>परिभाषा में  समुच्चय के अस्तित्व द्वारा प्रतिस्थापित किया जाता है जो कि कुछ परिमित समुच्चय का सबसमुच्चय है। इस संपत्ति को विभिन्न रूप से सबफाइनली इंडेक्स कहा जाता है।
उपगणनीयता के समान, अनुरूप धारणा उपस्थित है जिसमें<math>\exists(I\subseteq{\mathbb N})</math>परिभाषा में  समुच्चय के अस्तित्व द्वारा प्रतिस्थापित किया जाता है जो कि कुछ परिमित समुच्चय का सबसमुच्चय है। इस गुण धर्म  को विभिन्न रूप से सबफाइनली इंडेक्स कहा जाता है।


[[श्रेणी सिद्धांत]] में ये धारणाएँ उपश्रेणियाँ हैं।
[[श्रेणी सिद्धांत]] में ये धारणाएँ उपश्रेणियाँ हैं।

Revision as of 22:46, 8 February 2023

रचनात्मक गणित में, प्राकृतिक संख्याओं से आंशिक फलन प्रक्षेपण के रूप में उपस्थित होते है। सर्जेन्ट के साथ संग्रह सबकाउंटेबल होते है। इसे इस रूप में व्यक्त किया जा सकता है


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

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

चर्चा

उदाहरण

महत्वपूर्ण स्थितिया वह है जहां अभिकलनीयता सिद्धांत में अध्ययन के अनुसार फलनों के बड़े वर्ग के कुछ उपवर्ग को दर्शाता है।

कुल संगणनीय फलनों पर विचार करें और ध्यान दें कि कुल होना निर्णायक गुण धर्म नहीं है अर्थात कुल फलनों और प्राकृतिक संख्याओं के बीच रचनात्मक अवरोध नहीं हो सकती है। चूँकि, सभी संभावित आंशिक संगणनीय फलनों के कोडों की गणना के माध्यम से उनके सबसेट, जो गैर-समाप्ति वाले फलनों को अनुमति देता है जैसे कि कुल फलनों को सबकाउंटेबल समुच्चय के रूप में देखा जाता है। ध्यान दें कि इंडेक्स समुच्चय रिकर्सन थ्योरी पर राइस के प्रमेय द्वारा, अधिकांश डोमेन सेट किए जाते हैं पुनरावर्ती नहीं हैं दरअसल, सभी गिनती संख्याओं के बीच कोई प्रभावी मानचित्र नहीं है और अनंत गैर सीमित अनुक्रमण समुच्चय पर बल दिया गया है, केवल उपसमुच्चय संबंध . संख्याओं के रचनात्मक रूप से गैर गणनीय समुच्चय का प्रभुत्व होता है , नाम सबकाउंटेबल इस प्रकार प्रस्तुत करता है कि असंख्य समुच्चय से बड़ा .नहीं होता है

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

बहिष्कृत मध्य से संबंध

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

लेकिन यह समुच्चय तब भी वियोज्य होने में विफल हो सकता है, इस अर्थ में कि
इसे स्वयंसिद्ध माने बिना सिद्ध नहीं किया जा सकता है। सबकाउंटेबल समुच्चय को प्रभावी प्रारूप से गिनने में कोई विफल हो सकता है यदि कोई गिनती की संख्या को मैप करने में विफल रहता है अनुक्रमण समुच्चय में , इस कारण से। गणनीय होने का अर्थ है सबकाउंटेबल होना। लेकिन आम तौर पर बातचीत बहिष्कृत मध्य के कानून पर जोर देने के बिना नहीं होती है, अर्थात सभी प्रस्तावों के लिए रखती है .

मौलिक गणित में

मौलिक तर्क के सभी कानूनों पर जोर देते हुए, की वियोगात्मक गुण धर्म ऊपर चर्चा वास्तव में सभी सेटों के लिए है। फिर, गैर-खाली के लिए , गुण संख्या (जो यहाँ मतलब होगा कि में इंजेक्ट करता है ), गणनीय ( है इसकी सीमा के रूप में), सबकाउंटेबल (का सबसमुच्चय में डालता है ) और नहीं भी -उत्पादक ( गणनीयता गुण धर्म अनिवार्य रूप से सबसमुच्चय के संदर्भ में परिभाषित की गई है ) सभी समतुल्य हैं और व्यक्त करते हैं कि समुच्चय परिमित समुच्चय या गणनीय रूप से अनंत है।

गैर-मौलिक अभिकथन

बहिष्कृत मध्य के कानून के बिना, यह उन सेटों की उपगणनीयता पर जोर देने के लिए संगत हो सकता है जो मौलिक रूप से (अर्थात गैर-रचनात्मक रूप से) प्राकृतिक संख्याओं की कार्डिनैलिटी से अधिक हो। ध्यान दें कि रचनात्मक सेटिंग में, फलन स्थान के बारे में काउंटेबिलिटी का दावा पूरे समुच्चय से बाहर , के रूप में , खंडन किया जा सकता है। लेकिन उपगणनीयता असंख्य समुच्चय का समुच्चय द्वारा से प्रभावी रूप से अलग करने योग्य नहीं है अनुमति दी जा सकती है।

जैसा असंख्य है और मौलिक रूप से सबकाउंटेबल नहीं है, इसके बड़े फलन स्थान के साथ मौलिक ढांचा चर्च की थीसिस (रचनात्मक गणित) के साथ असंगत है। रचनात्मक चर्च की थीसिस, रूसी रचनावाद का स्वयंसिद्ध।

=== सबकाउंटेबल और ω-उत्पादक परस्पर अनन्य === हैं समुच्चय कहा जाएगा रचनात्मक और उत्पादक समुच्चय अगर, जब भी इसका कोई सबसमुच्चय किसी फलन का वह कार्यक्षेत्र है जिस पर कोई आंशिक फलन है , वहाँ हमेशा तत्व उपस्थित होता है जो उस सीमा के पूरक में रहता है।[1] यदि कुछ पर कोई अनुमान उपस्थित है , तो वर्णित अनुसार इसकी संबंधित प्रशंसा खाली समुच्चय के बराबर होगी , और इसलिए सबकाउंटेबल समुच्चय कभी नहीं होता है -उत्पादक। जैसा कि ऊपर परिभाषित किया गया है, होने की गुण धर्म -उत्पादक सीमा को जोड़ता है किसी विशेष मान के किसी भी आंशिक फलन का फलनों की श्रेणी में नहीं। इस प्रकार, होना -उत्पादक बोलता है कि सभी तत्वों को उत्पन्न करना कितना कठिन है : उन्हें ही फंक्शन का उपयोग करके उत्पन्न नहीं किया जा सकता है। वें>-उत्पादकता गुण धर्म उपगणनीयता में बाधा उत्पन्न करती है। जैसा कि यह बेशुमारता का भी अर्थ है, कैंटर के विकर्ण तर्क में अधिकांशतः यह धारणा सम्मिलित होती है, स्पष्ट रूप से सत्तर के दशक के अंत से।

कोई गणना योग्य गणना की असंभवता स्थापित कर सकता है केवल संगणनीय रूप से गणना योग्य सबसमुच्चय पर विचार करके और किसी को सभी बाधाओं के समुच्चय की आवश्यकता हो सकती है कुल पुनरावर्ती तथाकथित उत्पादन फलन की छवि होना चाहिए।

समुच्चय थ्योरी में, जहां आंशिक फलनों को जोड़े, अंतरिक्ष के संग्रह के रूप में तैयार किया जाता है के रूप में दिया गया बिल्कुल सभी आंशिक फलनों को चालू रखता है जिनकी सीमा के रूप में केवल उपसमुच्चय हैं का . के लिए -उत्पादक समुच्चय पाता है

रचनात्मक रूप से पढ़ें, यह किसी आंशिक फलन को जोड़ता है तत्व के साथ उस फलन सीमा में नहीं। यह गुण धर्म की असंगति पर जोर देती है -उत्पादक समुच्चय किसी विशेषण (संभवतः आंशिक) फलन के साथ। इसके नीचे सबकाउंटेबिलिटी मान्यताओं के अध्ययन में लागू किया गया है।

समुच्चय सिद्धांत

भीलों के सबसमुच्चय पर कैंटोरियन तर्क

संदर्भ सिद्धांत के रूप में हम रचनात्मक समुच्चय सिद्धांत CZF को देखते हैं, जिसमें प्रतिस्थापन की स्वयंसिद्ध स्कीमा है, विधेय पृथक्करण की स्वयंसिद्ध स्कीमा, अनंत का मजबूत अभिगृहीत, शक्ति सेटों के अस्तित्व के प्रति अज्ञेयवादी है, लेकिन इसमें वह स्वयंसिद्ध भी सम्मिलित है जो यह दावा करता है कि कोई भी फलन स्थान दिया गया है, दिया गया है समुच्चय भी हैं। इस सिद्धांत में, यह जोर देने के लिए भी संगत है कि प्रत्येक समुच्चय सबकाउंटेबल है। गिनती संख्याओं के अनंत समुच्चय पर संभावित अनुमानों के माध्यम से इस खंड में आगे के विभिन्न अभिगृहीतों की अनुकूलता पर चर्चा की गई है। . यहाँ मानक प्राकृतिक संख्याओं के मॉडल को निरूपित करेगा।

याद रखें कि फलनों के लिए , कुल कार्यक्षमता की परिभाषा के अनुसार, सभी मानों के लिए अद्वितीय वापसी मान उपस्थित होता है डोमेन में,

और सबकाउंटेबल समुच्चय के लिए, अनुमान अभी भी सबसमुच्चय पर कुल है . रचनात्मक रूप से, मौलिक रूप से कम ऐसे अस्तित्व संबंधी दावे सिद्ध होंगे।

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

बिजली वर्गों पर

नीचे, इस तथ्य का उपयोग किया जाता है कि विशेष स्थितियो निषेध परिचय का तात्पर्य है कि विरोधाभासी है।

सरलता से तर्क के लिए, मान लीजिए समुच्चय है। फिर उपसमुच्चय पर विचार करें और समारोह . इसके अलावा, जैसा कि कैंटर के विकर्ण तर्क|कैंटोर के प्रमेय में शक्ति समुच्चय के बारे में है, परिभाषित करें[2]

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

हम यह निष्कर्ष निकालते हैं कि सबकाउंटेबिलिटी स्वयंसिद्ध, सभी सेटों पर जोर देने के साथ असंगत है समुच्चय होने के नाते, जैसा निहित है उदा। पावर समुच्चय स्वयंसिद्ध द्वारा।

पॉवरसमुच्चय या इसके किसी समकक्ष के बिना मौलिक ZFC में, यह भी सुसंगत है कि वास्तविक के सभी उपवर्ग जो कि समुच्चय हैं, सबकाउंटेबल हैं। उस संदर्भ में, यह इस कथन का अनुवाद करता है कि वास्तविक संख्याओं के सभी समुच्चय गणनीय हैं।[3] बेशक, उस सिद्धांत में फलन स्पेस समुच्चय नहीं है .

फंक्शन स्पेस पर

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

तो यहाँ हम विशेषण फलन पर विचार करते हैं और का उपसमुच्चय के रूप में अलग किया गया[4]

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

इस प्रकार, की उपगणनीयता अनुमति है, और वास्तव में सिद्धांत के मॉडल उपस्थित हैं। फिर भी, CZF के स्थिति में भी, पूर्ण अनुमान का अस्तित्व , डोमेन के साथ , वास्तव में विरोधाभासी है। की निर्णायक सदस्यता समुच्चय को भी गणनीय बनाता है, अर्थात बेशुमार।

इन अवलोकनों से परे, यह भी ध्यान दें कि किसी गैर-शून्य संख्या के लिए , फलन में अनुमान सम्मिलित है सभी तक नहीं बढ़ाया जा सकता है इसी तरह के विरोधाभासी तर्क से। इसे यह कहते हुए व्यक्त किया जा सकता है कि ऐसे आंशिक फलन हैं जिन्हें पूर्ण फलनों तक नहीं बढ़ाया जा सकता है . ध्यान दें कि जब दिया जाता है , कोई अनिवार्य रूप से यह तय नहीं कर सकता है कि क्या , और इसलिए कोई यह भी तय नहीं कर सकता है कि संभावित फलन एक्सटेंशन का मान चालू है या नहीं पहले से वर्णित अनुमान के लिए पहले से ही निर्धारित है .

सबकाउंटिबिलिटी स्वयंसिद्ध, सभी सेटों पर जोर देने योग्य है, किसी भी नए स्वयंसिद्ध बनाने के साथ असंगत है LEM सहित गणनीय।

मॉडल

उपरोक्त विश्लेषण के कोडिंग के औपचारिक गुणों को प्रभावित करता है . सबकाउंटेबिलिटी पोस्टुलेट्स द्वारा सीजेडएफ सिद्धांत के गैर-मौलिक विस्तार के लिए मॉडल का निर्माण किया गया है।[5] इस तरह के गैर-रचनात्मक स्वयंसिद्धों को पसंद के सिद्धांतों के रूप में देखा जा सकता है, जो,चूँकि , क्रमिक विश्लेषण | सिद्धांतों की प्रमाण-सैद्धांतिक ताकत को बहुत अधिक नहीं बढ़ाते हैं।

  • IZF के ऐसे मॉडल हैं जिनमें अलग-अलग संबंधों वाले सभी समुच्चय सबकाउंटेबल हैं।[6]
  • CZF का मॉडल है, उदाहरण के लिए, मार्टिन-लोफ टाइप थ्योरी . मौलिक रूप से असंख्य फलन रिक्त स्थान के साथ इस रचनात्मक समुच्चय सिद्धांत में, यह वास्तव में उपगणनीयता स्वयंसिद्ध पर जोर देने के लिए संगत है, यह कहते हुए कि प्रत्येक समुच्चय सबकाउंटेबल है। जैसा कि चर्चा की गई है, परिणामी सिद्धांत शक्ति समुच्चय के स्वयंसिद्ध और बहिष्कृत मध्य के कानून के विपरीत है।
  • अभी तक अधिक मजबूत, क्रिपके-प्लेटेक समुच्चय सिद्धांत के कुछ मॉडल, फलन स्थान के बिना सिद्धांत, यह भी मान्य करता है कि सभी समुच्चय गणनीय हैं।

आकार की धारणा

जैसा कि अभिकलनीयता थ्योरी में माने जाने वाले फंक्शन स्पेस के उदाहरण में देखा गया है, न कि प्रत्येक अनंत उपसमुच्चय अनिवार्य रूप से रचनात्मक आपत्ति में है , इस प्रकार रचनात्मक संदर्भों में असंख्य सेटों के बीच अधिक परिष्कृत अंतर के लिए जगह बना रहा है। समारोह स्थान (और भी ) मध्यम रूप से समृद्ध समुच्चय सिद्धांत में हमेशा न तो परिमित पाया जाता है और न ही आपत्ति में , कैंटर के विकर्ण तर्क द्वारा। असंख्य होने का यही मतलब है। लेकिन यह तर्क कि उस समुच्चय की प्रमुखता इस प्रकार कुछ अर्थों में प्राकृतिक संख्या से अधिक होगी, केवल मौलिक आकार की अवधारणा और कार्डिनैलिटी द्वारा समुच्चय के इसके प्रेरित क्रम पर प्रतिबंध पर निर्भर करती है। उपरोक्त वर्गों से प्रेरित, अनंत समुच्चय वर्ग से छोटा माना जा सकता है . छोटे आकार के निर्णय के रूप में उपगणनीयता को कैंटोर द्वारा परिभाषित कार्डिनैलिटी संबंधों की मानक गणितीय परिभाषा के साथ नहीं जोड़ा जाएगा, छोटे कार्डिनैलिटी को इंजेक्शन के संदर्भ में परिभाषित किया जाएगा। और कार्डिनैलिटी की समानता को आक्षेपों के संदर्भ में परिभाषित किया जा रहा है। इसके अलावा, ध्यान दें कि रचनात्मक रूप से, आदेश <कार्डिनैलिटी की तरह अनिर्णीत हो सकता है।

संबंधित गुण

उपगणनीयता के समान, अनुरूप धारणा उपस्थित है जिसमेंपरिभाषा में समुच्चय के अस्तित्व द्वारा प्रतिस्थापित किया जाता है जो कि कुछ परिमित समुच्चय का सबसमुच्चय है। इस गुण धर्म को विभिन्न रूप से सबफाइनली इंडेक्स कहा जाता है।

श्रेणी सिद्धांत में ये धारणाएँ उपश्रेणियाँ हैं।

यह भी देखें

संदर्भ

  1. Gert Smolka, Skolems paradox and constructivism, Lecture Notes, Saarland University, Jan. 2015
  2. Méhkeri, Daniel (2010), A simple computational interpretation of set theory, arXiv:1005.4380
  3. Gitman, Victora (2011), What is the theory ZFC without power set, arXiv:1110.2430
  4. 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
  5. 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
  6. McCarty, Charles (1986), "Subcountability under realizability", Notre Dame Journal of Formal Logic, 27 (2): 210–220, doi:10.1305/ndjfl/1093636613, MR 0842149