उपगणनीयता

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

$$\exists (I\subseteq {\mathbb {N} }).\,\exists f.\,(f\colon I\twoheadrightarrow X),$$

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

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

चर्चा

उदाहरण

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

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

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

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

$$\forall (i\in I).(i\in {\mathbb {N} }).$$

लेकिन यह समुच्चय तब भी वियोज्य होने में विफल हो सकता है, इस अर्थ में कि

$$\forall (n\in {\mathbb {N} }).{\big (}(n\in I)\lor \neg (n\in I){\big )}$$

इसे स्वयंसिद्ध माने बिना सिद्ध नहीं किया जा सकता है। सबकाउंटेबल समुच्चय को प्रभावी ढंग से गिनने में कोई विफल हो सकता है $X$ अगर कोई गिनती की संख्या को मैप करने में विफल रहता है ${\mathbb {N} }$ अनुक्रमण समुच्चय में $I$, इस कारण से। गणनीय होने का अर्थ है उपगणनीय होना। लेकिन आम तौर पर बातचीत बहिष्कृत मध्य के कानून पर जोर देने के बिना नहीं होती है, यानी सभी प्रस्तावों के लिए $\phi$ रखती है $\phi \lor \neg \phi$.

शास्त्रीय गणित में

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

गैर-शास्त्रीय अभिकथन

बहिष्कृत मध्य के कानून के बिना, यह उन सेटों की उपगणनीयता पर जोर देने के लिए संगत हो सकता है जो शास्त्रीय रूप से (यानी गैर-रचनात्मक रूप से) प्राकृतिक संख्याओं की कार्डिनैलिटी से अधिक हो। ध्यान दें कि एक रचनात्मक सेटिंग में, कार्य स्थान के बारे में एक काउंटेबिलिटी का दावा ${\mathbb {N} }^{\mathbb {N} }$ पूरे समुच्चय से बाहर ${\mathbb {N} }$, के रूप में ${\mathbb {N} }\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$, खंडन किया जा सकता है। लेकिन उपगणनीयता $I\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$ एक बेशुमार समुच्चय का ${\mathbb {N} }^{\mathbb {N} }$ एक समुच्चय द्वारा $I\subseteq {\mathbb {N} }$ से प्रभावी रूप से अलग करने योग्य नहीं है ${\mathbb {N} }$ अनुमति दी जा सकती है।

जैसा ${\mathbb {N} }^{\mathbb {N} }$ बेशुमार है और शास्त्रीय रूप से उपगणनीय नहीं है, इसके बड़े कार्य स्थान के साथ शास्त्रीय ढांचा चर्च की थीसिस (रचनात्मक गणित) के साथ असंगत है। रचनात्मक चर्च की थीसिस, रूसी रचनावाद का एक स्वयंसिद्ध।

=== उपगणनीय और ω-उत्पादक परस्पर अनन्य === हैं एक समुच्चय $X$ कहा जाएगा $\omega$रचनात्मक और उत्पादक समुच्चय अगर, जब भी इसका कोई सबसमुच्चय $W\subset X$ किसी फ़ंक्शन का वह दायरा है जिस पर कोई आंशिक फ़ंक्शन है ${\mathbb {N} }$, वहाँ हमेशा एक तत्व मौजूद होता है $d\in X\setminus W$ जो उस सीमा के पूरक में रहता है। अगर कुछ पर कोई अनुमान मौजूद है $X$, तो वर्णित अनुसार इसकी संबंधित प्रशंसा खाली समुच्चय के बराबर होगी $X\setminus X$, और इसलिए एक सबकाउंटेबल समुच्चय कभी नहीं होता है $\omega$-उत्पादक। जैसा कि ऊपर परिभाषित किया गया है, होने की संपत्ति $\omega$-उत्पादक सीमा को जोड़ता है $W$ किसी विशेष मान के किसी भी आंशिक कार्य का $d\in X$ कार्यों की श्रेणी में नहीं। इस प्रकार, होना $\omega$-उत्पादक बोलता है कि सभी तत्वों को उत्पन्न करना कितना कठिन है $X$: उन्हें एक ही फंक्शन का उपयोग करके उत्पन्न नहीं किया जा सकता है। $\omega$वें>-उत्पादकता संपत्ति उपगणनीयता में बाधा उत्पन्न करती है। जैसा कि यह बेशुमारता का भी अर्थ है, कैंटर के विकर्ण तर्क में अक्सर यह धारणा शामिल होती है, स्पष्ट रूप से सत्तर के दशक के अंत से।

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

समुच्चय थ्योरी में, जहां आंशिक कार्यों को जोड़े, अंतरिक्ष के संग्रह के रूप में तैयार किया जाता है ${\mathbb {N} }\rightharpoonup X$ के रूप में दिया गया $\cup _{I\subseteq {\mathbb {N} }}X^{I}$ बिल्कुल सभी आंशिक कार्यों को चालू रखता है ${\mathbb {N} }$ जिनकी सीमा के रूप में केवल उपसमुच्चय हैं $W$ का $X$. एक के लिए $\omega$-उत्पादक समुच्चय $X$ एक पाता है

$\forall (w\in ({\mathbb {N} }\rightharpoonup X)).\exists (d\in X).\neg \exists (n\in {\mathbb {N} }).w(n)=d.$

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

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

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

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

याद रखें कि कार्यों के लिए $g\colon X\to Y$, कुल कार्यक्षमता की परिभाषा के अनुसार, सभी मानों के लिए एक अद्वितीय वापसी मान मौजूद होता है $x\in X$ डोमेन में,

$\exists !(y\in Y).g(x)=y,$

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

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

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

नीचे, इस तथ्य का उपयोग किया जाता है कि विशेष मामला $(P\implies \neg P)\implies \neg P$ निषेध परिचय का तात्पर्य है कि $P\iff \neg P$ विरोधाभासी है।

सरलता से तर्क के लिए, मान लीजिए ${\mathcal {P}}{\mathbb {N} }$ एक समुच्चय है। फिर एक उपसमुच्चय पर विचार करें $I\subseteq {\mathbb {N} }$ और एक समारोह $w\colon I\to {\mathcal {P}}{\mathbb {N} }$. इसके अलावा, जैसा कि कैंटर के विकर्ण तर्क|कैंटोर के प्रमेय में शक्ति समुच्चय के बारे में है, परिभाषित करें

$$d=\{k\in {\mathbb {N} }\mid k\in I\land D(k)\}$$

कहाँ पे,

$$D(k)=\neg (k\in w(k)).$$

यह का एक उपवर्ग है ${\mathbb {N} }$ की निर्भरता में परिभाषित $w$ और इसे लिखा भी जा सकता है

$$d=\{k\in I\mid \neg (k\in w(k))\}.$$

यह पृथक्करण के माध्यम से सबसमुच्चय के रूप में मौजूद है। अब यह मानते हुए कि एक संख्या मौजूद है $n\in I$ साथ $w(n)=d$ विरोधाभास का तात्पर्य है

$$n\in d\iff \neg (n\in d).$$

तो एक समुच्चय के रूप में, कोई पाता है ${\mathcal {P}}{\mathbb {N} }$ है $\omega$-उत्पादक इसमें हम एक बाधा को परिभाषित कर सकते हैं $d$ किसी दिए गए अनुमान के लिए। ध्यान दें कि एक अनुमान का अस्तित्व $f\colon I\twoheadrightarrow {\mathcal {P}}{\mathbb {N} }$ स्वतः बना देगा ${\mathcal {P}}{\mathbb {N} }$ CZF में प्रतिस्थापन के माध्यम से एक समुच्चय में, और इसलिए यह कार्य अस्तित्व बिना शर्त असंभव है।

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

पॉवरसमुच्चय या इसके किसी समकक्ष के बिना शास्त्रीय ZFC में, यह भी सुसंगत है कि वास्तविक के सभी उपवर्ग जो कि समुच्चय हैं, उपगणनीय हैं। उस संदर्भ में, यह इस कथन का अनुवाद करता है कि वास्तविक संख्याओं के सभी समुच्चय गणनीय हैं। बेशक, उस सिद्धांत में फ़ंक्शन स्पेस समुच्चय नहीं है ${\mathbb {N} }^{\mathbb {N} }$.

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

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

तो यहाँ हम एक विशेषण फलन पर विचार करते हैं $f\colon I\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$ और का उपसमुच्चय ${\mathbb {N} }\times {\mathbb {N} }$ के रूप में अलग किया गया

$${\Big \{}\langle n,y\rangle \in {\mathbb {N} }\times {\mathbb {N} }\mid {\big (}n\in I\land D(n,y){\big )}\lor {\big (}\neg (n\in I)\land y=1{\big )}{\Big \}}$$

के रूप में परिभाषित विकर्ण विधेय के साथ

$$D(n,y)={\big (}\neg (f(n)(n)\geq 1)\land y=1{\big )}\lor {\big (}\neg (f(n)(n)=0)\land y=0{\big )}$$

जिसे हम बिना निषेध के वाक्यांश भी कह सकते हैं

$$D(n,y)={\big (}f(n)(n)=0\land y=1{\big )}\lor {\big (}f(n)(n)\geq 1\land y=0{\big )}.$$

यह समुच्चय शास्त्रीय रूप से एक कार्य है ${\mathbb {N} }^{\mathbb {N} }$, मूल्य लेने के लिए डिज़ाइन किया गया $y=0$ विशेष इनपुट के लिए $n$. और यह शास्त्रीय रूप से यह साबित करने के लिए इस्तेमाल किया जा सकता है कि का अस्तित्व $f$ एक अनुमान के रूप में वास्तव में विरोधाभासी है। हालांकि, रचनात्मक रूप से, जब तक कि प्रस्ताव $n\in I$ इसकी परिभाषा में निर्णायक है ताकि समुच्चय वास्तव में एक कार्यात्मक असाइनमेंट को परिभाषित कर सके, हम इस समुच्चय को फ़ंक्शन स्पेस के सदस्य के रूप में साबित नहीं कर सकते। और इसलिए हम शास्त्रीय निष्कर्ष नहीं निकाल सकते।

इस प्रकार, की उपगणनीयता ${\mathbb {N} }^{\mathbb {N} }$ अनुमति है, और वास्तव में सिद्धांत के मॉडल मौजूद हैं। फिर भी, CZF के मामले में भी, एक पूर्ण अनुमान का अस्तित्व ${\mathbb {N} }\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$, डोमेन के साथ ${\mathbb {N} }$, वास्तव में विरोधाभासी है। की निर्णायक सदस्यता $I={\mathbb {N} }$ समुच्चय को भी गणनीय बनाता है, अर्थात बेशुमार।

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

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

मॉडल

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

• IZF के ऐसे मॉडल हैं जिनमें अलग-अलग संबंधों वाले सभी समुच्चय सबकाउंटेबल हैं।
• CZF का एक मॉडल है, उदाहरण के लिए, मार्टिन-लोफ टाइप थ्योरी ${\mathsf {ML_{1}V}}$. शास्त्रीय रूप से बेशुमार फ़ंक्शन रिक्त स्थान के साथ इस रचनात्मक समुच्चय सिद्धांत में, यह वास्तव में उपगणनीयता स्वयंसिद्ध पर जोर देने के लिए संगत है, यह कहते हुए कि प्रत्येक समुच्चय उपगणनीय है। जैसा कि चर्चा की गई है, परिणामी सिद्धांत शक्ति समुच्चय के स्वयंसिद्ध और बहिष्कृत मध्य के कानून के विपरीत है।
• अभी तक अधिक मजबूत, क्रिपके-प्लेटेक समुच्चय सिद्धांत के कुछ मॉडल, कार्य स्थान के बिना एक सिद्धांत, यह भी मान्य करता है कि सभी समुच्चय गणनीय हैं।

आकार की धारणा

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

संबंधित गुण

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

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

यह भी देखें

• कैंटर का विकर्ण तर्क
• संगणनीय समारोह
• रचनात्मक समुच्चय सिद्धांत
• श्रोडर-बर्नस्टीन प्रमेय
• उपभाग
• कुल आदेश