Subcountability
रचनात्मक गणित में, एक संग्रह उपगणनीय है यदि उस पर प्राकृतिक संख्याओं से आंशिक अधिगमन मौजूद है। इसे इस रूप में व्यक्त किया जा सकता है जहां यह दर्शाता है कि a से एक सर्जेक्टिव फ़ंक्शन है। उद्गम एक सदस्य है और यहाँ के उपवर्ग को एक समूह होना आवश्यक है। दूसरे शब्दों में, एक उपगणनीय संग्रह के सभी तत्व गणना संख्याओं के अनुक्रमण समूह की छवि में कार्यात्मक रूप से होते हैं और इस प्रकार सेट को गणना योग्य सेट द्वारा हावी होने के रूप में समझा जा सकता है। चर्चा नामकरण ध्यान दें कि गणना और परिमितता गुणों का नामकरण काफी हद तक भिन्न होता है-आंशिक रूप से क्योंकि उनमें से कई बहिष्कृत मध्य को मानते समय मेल खाते हैं। दोहराने के लिए, यहाँ चर्चा विशेषता वाले सेट पर अधिभार के संदर्भ में परिभाषित संपत्ति से संबंधित है। यहाँ की भाषा रचनात्मक सेट सिद्धांत ग्रंथों में आम है, लेकिन उपगणनीय नाम अन्यथा विशेषता वाले सेट से बाहर इंजेक्शन के संदर्भ में गुणों को भी दिया गया है। परिभाषा में सेट को अमूर्त भी किया जा सकता है, और अधिक सामान्य धारणा के संदर्भ में इसका उपांश कहा जा सकता है। उदाहरण महत्वपूर्ण मामले हैं जहां प्रश्न में सेट एक बड़े वर्ग के कार्यों का कुछ उपवर्ग है जैसा कि संगणना सिद्धांत में अध्ययन किया गया है। कुल संगणनीय कार्यों के समूह से एक संगणनीय अधिगमन नहीं हो सकता है, जैसा कि विकर्ण निर्माण से कार्य के माध्यम से प्रदर्शित किया गया है, जो इस तरह के अधिगमन छवि में कभी नहीं हो सकता है। हालांकि, सभी संभावित आंशिक संगणकीय कार्यों के कोड के माध्यम से, जो गैर-समाप्ति कार्यक्रमों की भी अनुमति देते हैं, कार्यों के ऐसे उपसमुच्चय, जैसे कि कुल कार्य, को उपगणनीय सेट के रूप में देखा जाता हैः कुल कार्य प्राकृतिक संख्याओं के कुछ सख्त उपसमुच्चय की सीमा हैं। एक असंकलनीय, और इतने रचनात्मक रूप से असंकलनीय, संख्याओं के समूह का प्रभुत्व होने के कारण, उपगणनीय नाम इस प्रकार बताता है कि रचनात्मक रूप से असंकलनीय समूह उससे बड़ा नहीं है। ध्यान दें कि सभी गणना संख्याओं और असीमित और गैर-अनंत अनुक्रमण समुच्चय के बीच कोई प्रभावी मानचित्र यहाँ नहीं है, केवल सबसेट संबंध। कुल होना प्रसिद्ध रूप से एक निर्णायक संपत्ति नहीं है। सूचकांक समुच्चय पर राइस के प्रमेय के अनुसार, सूचकांकों के अधिकांश क्षेत्र, वास्तव में, संगणनीय समुच्चय नहीं हैं। उपगणनीय प्रदर्शन का यह भी तात्पर्य है कि यह शास्त्रीय रूप से (गैर-रचनात्मक रूप से) औपचारिक रूप से गणना योग्य है, लेकिन यह किसी भी प्रभावी गणना को नहीं दर्शाता है। दूसरे शब्दों में, यह तथ्य कि अनुक्रम में सभी कुल कार्यों को सूचीबद्ध करने वाले एल्गोरिदम को कूटबद्ध नहीं किया जा सकता है, सेट और फ़ंक्शन अस्तित्व के संबंध में शास्त्रीय स्वयंसिद्धियों द्वारा नहीं लिया जाता है। हम देखते हैं कि, एक सिद्धांत के स्वयंसिद्धों के आधार पर, उपगणनीयता गणना की तुलना में सिद्ध होने की अधिक संभावना हो सकती है। बहिष्कृत मध्य से संबंध रचनात्मक तर्क और समुच्चय सिद्धांत अनंत (गैर-अनंत) समुच्चयों के बीच एक फलन के अस्तित्व को निर्णायकता और संभवतः प्रभावशीलता के प्रश्नों से जोड़ते हैं। वहाँ, उपगणनायोग्यता गुण गणनायोग्यता से अलग हो जाता है और इस प्रकार यह एक अनावश्यक धारणा नहीं है। प्राकृतिक संख्याओं के अनुक्रमण समूह को मौजूद माना जा सकता है, उदाहरण के लिए। पृथक्करण स्वयंसिद्ध योजना जैसे सेट सैद्धांतिक स्वयंसिद्धियों के माध्यम से एक सबसेट के रूप में। फिर परिभाषा के अनुसार, लेकिन यह सेट तब भी अलग करने योग्य होने में विफल हो सकता है, इस अर्थ में कि इसे एक स्वयंसिद्ध के रूप में माने बिना सिद्ध नहीं किया जा सकता है। यदि कोई गणना संख्या को अनुक्रमणिका सेट में मैप करने में विफल रहता है, तो इस कारण से कोई उपगणनीय सेट को प्रभावी ढंग से गिनने में विफल हो सकता है। गणना योग्य होने का अर्थ है उपगणना योग्य होना। मार्कोव के सिद्धांत के उपयुक्त संदर्भ में, विपरीत बहिष्कृत मध्य के नियम के बराबर है, अर्थात। जो सभी प्रस्तावों के लिए लागू होता है। विशेष रूप से, रचनात्मक रूप से यह विपरीत दिशा आम तौर पर नहीं होती है। शास्त्रीय गणित में शास्त्रीय तर्क के सभी नियमों का दावा करते हुए, ऊपर चर्चा की गई विसंगत संपत्ति वास्तव में सभी समुच्चयों के लिए लागू होती है। फिर, गैर-रिक्तता के लिए, संख्यात्मक गुण (जिसका यहाँ अर्थ होगा कि इसमें प्रवेश करता है), गणना योग्य (इसकी सीमा के रूप में है), उपगणनीय (में अधिशेषों का एक उपसमुच्चय) और गैर-उत्पादक (अनिवार्य रूप से उपसमुच्चय के संदर्भ में परिभाषित एक गणना गुण) सभी समतुल्य हैं और व्यक्त करते हैं कि एक समूह परिमित या गणना योग्य रूप से अनंत है। गैर-शास्त्रीय दावे बहिष्कृत मध्य के कानून के बिना, यह शास्त्रीय रूप से सेटों की उपगणनीयता पर जोर देने के लिए सुसंगत हो सकता है (यानी। गैर-रचनात्मक रूप से) प्राकृतिक संख्याओं की प्रधानता से अधिक है। ध्यान दें कि एक रचनात्मक सेटिंग में, पूर्ण सेट से बाहर फ़ंक्शन स्थान के बारे में एक गणना दावा, जैसा कि है, गलत हो सकता है। लेकिन एक सेट द्वारा एक अनगिनत सेट की उपगणनीयता जो प्रभावी रूप से अलग करने योग्य नहीं है, की अनुमति दी जा सकती है। जैसा कि अनगिनत और शास्त्रीय रूप से साबित करने के लिए उपगणनीय नहीं है, अपने बड़े कार्य स्थान के साथ शास्त्रीय ढांचा रचनात्मक चर्च की थीसिस के साथ असंगत है, जो रूसी रचनात्मकता का एक स्वयंसिद्ध सिद्धांत है। उपगणनीय और ω-उत्पादक पारस्परिक रूप से अनन्य हैं एक समूह को-उत्पादक कहा जाएगा यदि, जब भी इसका कोई भी उपसमुच्चय किसी आंशिक फलन की सीमा पर होता है, तो हमेशा एक तत्व मौजूद रहता है जो उस सीमा के पूरक में रहता है। यदि कुछ पर कोई अधिक्षेप मौजूद है, तो जैसा कि वर्णित है, इसके अनुरूप पूरक खाली समुच्चय के बराबर होगा, और इसलिए एक उपगणनीय समुच्चय कभी भी उत्पादक नहीं होता है। जैसा कि ऊपर परिभाषित किया गया है,-उत्पादक होने का गुण किसी भी आंशिक कार्य की सीमा को किसी विशेष मूल्य से जोड़ता है जो कार्य सीमा में नहीं है। इस तरह, एक समूह का उत्पादक होना बताता है कि इसके सभी तत्वों को उत्पन्न करना कितना कठिन हैः उन्हें एक ही कार्य का उपयोग करके प्राकृतिक से उत्पन्न नहीं किया जा सकता है। उत्पादकता गुण उपगणनीयता के लिए एक बाधा है। चूंकि यह भी अनगिनतता का संकेत देता है, विकर्ण तर्कों में अक्सर इस धारणा को शामिल किया जाता है, स्पष्ट रूप से सत्तर के दशक के अंत से। केवल गणना योग्य रूप से गणना योग्य उपसमुच्चय पर विचार करके गणना योग्य गणना की असंभवता को स्थापित किया जा सकता है और सभी बाधाओं के समूह को कुल पुनरावर्ती तथाकथित उत्पादन फलन की छवि होने की आवश्यकता हो सकती है। समुच्चय सिद्धांत में, जहां आंशिक कार्यों को जोड़े के संग्रह के रूप में मॉडल किया जाता है, दिए गए स्थान पर सभी आंशिक कार्य होते हैं, उनकी सीमा के रूप में, केवल उनके उपसमुच्चय होते हैं। एक-उत्पादक समुच्चय के लिए जिसे कोई रचनात्मक रूप से पढ़ता है, यह किसी भी आंशिक कार्य को उस तत्व के साथ जोड़ता है जो उस कार्य सीमा में नहीं है। यह गुण किसी भी सर्जेक्टिव (संभवतः आंशिक) कार्य के साथ एक-उत्पादक समूह की असंगतता पर जोर देता है। नीचे इसे उपगणनीयता मान्यताओं के अध्ययन में लागू किया गया है। संदर्भ सिद्धांत के रूप में हम रचनात्मक सेट सिद्धांत CZF को देखते हैं, जिसमें प्रतिस्थापन, सीमित पृथक्करण, मजबूत अनंतता है, जो शक्ति सेटों के अस्तित्व के प्रति अज्ञेयवादी है, लेकिन इसमें वह स्वयंसिद्ध शामिल है जो दावा करता है कि कोई भी कार्य स्थान सेट है, दिए गए सेट भी हैं। इस सिद्धांत में, यह दावा करना भी सुसंगत है कि प्रत्येक समूह उपगणनीय है। गणना संख्याओं के एक अनंत समूह पर संभावित अनुमानों के माध्यम से इस खंड में विभिन्न आगे के स्वयंसिद्धों की संगतता पर चर्चा की गई है। यहाँ मानक प्राकृतिक संख्याओं के एक मॉडल को दर्शाया जाएगा। याद रखें कि कार्यों के लिए, कुल कार्यक्षमता की परिभाषा के अनुसार, डोमेन में सभी मूल्यों के लिए एक अद्वितीय वापसी मूल्य मौजूद है, और एक उपगणनीय सेट के लिए, अधिक्षेप अभी भी के सबसेट पर कुल है। रचनात्मक रूप से, इस तरह के कम अस्तित्वगत दावे शास्त्रीय रूप से साबित होंगे। नीचे चर्चा की गई स्थितियाँ-पावर क्लास बनाम फंक्शन स्पेस पर-एक दूसरे से अलग हैंः सामान्य उपवर्ग को परिभाषित करने वाले विधेय और उनके सत्य मूल्यों (जरूरी नहीं कि केवल सही और गलत) के विपरीत, एक फ़ंक्शन (जो प्रोग्रामिंग के संदर्भ में समाप्त हो रहा है) अपने सभी उपडोमेन (के सबसेट) के लिए डेटा के बारे में सुलभ जानकारी बनाता है। जब उनके सबसेट, कार्यों के लिए विशिष्ट कार्यों के रूप में, उनके वापसी मूल्यों के माध्यम से, सबसेट सदस्यता तय करें। चूंकि आम तौर पर परिभाषित समूह में सदस्यता आवश्यक रूप से निर्णायक नहीं होती है, इसलिए (कुल) कार्य स्वचालित रूप से सभी उपसमुच्चय के साथ द्विभाजन में नहीं होते हैं। इसलिए रचनात्मक रूप से, उपसमुच्चय विशेषता कार्यों की तुलना में अधिक विस्तृत अवधारणा हैं। वास्तव में, सी. जेड. एफ. के शीर्ष पर कुछ गैर-शास्त्रीय स्वयंसिद्धियों के संदर्भ में, यहां तक कि एक सिंगलटन का शक्ति वर्ग, जैसे। के सभी उपसमुच्चय के वर्ग को एक उचित वर्ग के रूप में दिखाया गया है। नीचे शक्ति वर्गों के लिए, इस तथ्य का उपयोग किया जाता है कि निषेध परिचय कानून के विशेष मामले का तात्पर्य है कि यह विरोधाभासी है। सरलता से तर्क के लिए, मान लें कि यह एक समुच्चय है। फिर एक उपसमुच्चय और एक फलन पर विचार करें। इसके अलावा, जैसा कि शक्ति समुच्चय के बारे में कैंटर के प्रमेय में, परिभाषित करें कि यह निर्भरता में परिभाषित एक उपवर्ग है और इसे यह भी लिखा जा सकता है कि यह पृथक्करण के माध्यम से उपसमुच्चय के रूप में मौजूद है। अब यह मानते हुए कि एक संख्या मौजूद है जो विरोधाभास को दर्शाती है, इसलिए एक समूह के रूप में, हम किसी भी अधिगमन के लिए एक बाधा को परिभाषित कर सकते हैं। यह भी ध्यान दें कि सी. जेड. एफ. में प्रतिस्थापन के माध्यम से एक अधिक्षेप का अस्तित्व स्वचालित रूप से एक समूह में बदल जाएगा, और इसलिए यह कार्य अस्तित्व बिना शर्त असंभव है। हम निष्कर्ष निकालते हैं कि उपगणनीयता स्वयंसिद्ध, यह कहते हुए कि सभी समुच्चय उपगणनीय हैं, एक समुच्चय होने के साथ असंगत है, जैसा कि निहित है। शक्ति सेट स्वयंसिद्ध द्वारा। उपरोक्त प्रमाण का अनुसरण करने से यह स्पष्ट हो जाता है कि हम केवल दोनों में से किसी एक का मानचित्रण नहीं कर सकते। बाउंडेड सेपरेशन वास्तव में इंगित करता है कि कोई भी सेट मानचित्र पर नहीं है। संबंधित रूप से, किसी भी कार्य के लिए, इसकी सीमा के सबसेट का उपयोग करके एक समान विश्लेषण से पता चलता है कि यह एक इंजेक्शन नहीं हो सकता है। फंक्शन स्पेस के लिए स्थिति अधिक जटिल है। पावरसेट या इसके किसी भी समकक्ष के बिना शास्त्रीय जेडएफसी में, यह भी सुसंगत है कि वास्तविक के सभी उपवर्ग जो सेट हैं, उपगणनीय हैं। उस संदर्भ में, यह इस कथन का अनुवाद करता है कि वास्तविक संख्याओं के सभी समूह गणना योग्य हैं। बेशक, उस सिद्धांत में फंक्शन स्पेस सेट नहीं है। फंक्शन स्पेस की परिभाषा के अनुसार, सेट में सेट के वे सबसेट होते हैं जो कुल और कार्यात्मक होते हैं। सभी सेटों की अनुमत उपगणनीयता पर जोर देना, विशेष रूप से, एक उपगणनीय सेट में बदल जाता है। तो यहाँ हम एक सर्जेक्टिव फ़ंक्शन और अलग किए गए के सबसेट पर विचार करते हैं जैसा कि विकर्णकारी विधेय के साथ परिभाषित किया गया है जिसे हम नकारात्मकता के बिना भी वाक्यांश कर सकते हैं क्योंकि यह सेट शास्त्रीय रूप से एक फ़ंक्शन है, जिसे विशेष इनपुट के लिए मूल्य लेने के लिए डिज़ाइन किया गया है। और इसका उपयोग शास्त्रीय रूप से यह साबित करने के लिए किया जा सकता है कि एक अधिक्षेप के रूप में का अस्तित्व वास्तव में विरोधाभासी है। हालांकि, रचनात्मक रूप से, जब तक कि इसकी परिभाषा में प्रस्ताव निर्णायक नहीं है ताकि सेट वास्तव में एक कार्यात्मक असाइनमेंट को परिभाषित कर सके, हम इस सेट को फ़ंक्शन स्पेस का सदस्य साबित नहीं कर सकते। और इसलिए हम शास्त्रीय निष्कर्ष नहीं निकाल सकते हैं। इस तरह से, उपगणनीयता की अनुमति है, और वास्तव में सिद्धांत के मॉडल मौजूद हैं। फिर भी, सी. जेड. एफ. के मामले में भी, क्षेत्र के साथ एक पूर्ण अधिगमन का अस्तित्व वास्तव में विरोधाभासी है। की निर्णायक सदस्यता सेट को भी गणना योग्य नहीं बनाती है, अर्थात। अनगिनत। इन टिप्पणियों के अलावा, यह भी ध्यान दें कि किसी भी गैर-शून्य संख्या के लिए, अधिक्षेप को शामिल करने में कार्यों को एक समान विरोधाभास तर्क द्वारा सभी तक विस्तारित नहीं किया जा सकता है। इसे यह कहते हुए व्यक्त किया जा सकता है कि तब आंशिक कार्य होते हैं जिन्हें पूर्ण कार्यों तक विस्तारित नहीं किया जा सकता है। ध्यान दें कि जब ए दिया जाता है, तो कोई आवश्यक रूप से यह तय नहीं कर सकता है कि क्या, और इसलिए कोई यह भी तय नहीं कर सकता है कि क्या एक संभावित फ़ंक्शन एक्सटेंशन का मूल्य पहले से ही पहले की विशेषता वाले सर्जेक्शन के लिए निर्धारित किया गया है। उपगणनीयता स्वयंसिद्ध, यह कहते हुए कि सभी समुच्चय उपगणनीय हैं, एल. ई. एम. सहित गणना योग्य बनाने वाले किसी भी नए स्वयंसिद्ध के साथ असंगत है। मॉडल उपरोक्त विश्लेषण के कोडिंग के औपचारिक गुणों को प्रभावित करता है। उपगणनायोग्य अभिधारणा द्वारा सी. जेड. एफ. सिद्धांत के गैर-शास्त्रीय विस्तार के लिए मॉडल का निर्माण किया गया है। इस तरह के गैर-रचनात्मक स्वयंसिद्धों को विकल्प सिद्धांतों के रूप में देखा जा सकता है, जो, हालांकि, सिद्धांतों की प्रमाण-सैद्धांतिक ताकत को ज्यादा नहीं बढ़ाते हैं। आई. जेड. एफ. के मॉडल हैं जिनमें अलगाव संबंधों वाले सभी सेट उपगणनीय हैं। सी. जेड. एफ. का एक मॉडल है, उदाहरण के लिए, मार्टिन-लॉफ प्रकार सिद्धांत। शास्त्रीय रूप से अनगिनत फ़ंक्शन रिक्त स्थान के साथ इस रचनात्मक सेट सिद्धांत में, यह वास्तव में उपगणनीयता स्वयंसिद्ध का दावा करने के लिए सुसंगत है, यह कहते हुए कि प्रत्येक सेट उपगणनीय है। जैसा कि चर्चा की गई है, परिणामी सिद्धांत शक्ति सेट के स्वयंसिद्ध और बहिष्कृत मध्य के नियम के विपरीत है। अधिक मजबूत अभी तक, क्रिप्के-प्लेटेक सेट सिद्धांत के कुछ मॉडल, फ़ंक्शन स्पेस अभिधारणा के बिना एक सिद्धांत, यहां तक कि मान्य करते हैं कि सभी सेट गणना योग्य हैं। छोटे आकार के निर्णय के रूप में आकार की उपगणनीयता की धारणा को कैंटर द्वारा परिभाषित कार्डिनलिटी संबंधों की मानक गणितीय परिभाषा के साथ नहीं जोड़ा जाएगा, जिसमें छोटे कार्डिनलिटी को इंजेक्शन के संदर्भ में परिभाषित किया गया है और कार्डिनलिटी की समानता को बाइजेक्शन के संदर्भ में परिभाषित किया गया है। रचनात्मक रूप से, सेटों के वर्ग पर "प्रीऑर्डर" निर्णायक और विरोधी सममित होने में विफल रहता है। एक मध्यम समृद्ध समुच्चय सिद्धांत में फलन स्थान (और भी) हमेशा कैंटर के विकर्ण तर्क द्वारा न तो परिमित पाया जाता है और न ही द्विभाजन में पाया जाता है। अनगिनत होने का यही अर्थ है। लेकिन यह तर्क कि उस समूह की प्रधानता कुछ अर्थों में प्राकृतिक संख्याओं से अधिक होगी, केवल शास्त्रीय आकार की अवधारणा और मुख्यता द्वारा सेटों के इसके प्रेरित क्रम पर प्रतिबंध पर निर्भर करता है। जैसा कि कम्प्यूटेबिलिटी सिद्धांत में विचार किए गए फ़ंक्शन स्पेस के उदाहरण में देखा गया है, आवश्यक रूप से प्रत्येक अनंत सबसेट रचनात्मक बाइजेक्शन में नहीं है, इस प्रकार रचनात्मक संदर्भों में अनगिनत सेटों के बीच अधिक परिष्कृत अंतर के लिए जगह बनाता है। उपरोक्त खंडों से प्रेरित होकर, अनंत समुच्चय को वर्ग की तुलना में "छोटा" माना जा सकता है। संबंधित गुण एक उपगणनीय समुच्चय को वैकल्पिक रूप से उपगणनीय अनुक्रमित भी कहा जाता है। समान धारणा मौजूद है जिसमें परिभाषा में "" को एक समूह के अस्तित्व से प्रतिस्थापित किया जाता है जो कुछ परिमित समूह का एक उपसमुच्चय है। इस गुण को विभिन्न रूप से उप-अंतिम रूप से अनुक्रमित कहा जाता है। श्रेणी सिद्धांत में ये सभी धारणाएँ उप-संविदात्मक हैं। कैंटर का विकर्ण तर्क संगणकीय कार्य रचनात्मक समुच्चय सिद्धांत श्रोडर-बर्नस्टीन प्रमेय उपांश कुल क्रम संदर्भ रचनात्मकता (गणित) भी देखें।