उपगणनीयता

रचनात्मक गणित में, एक संग्रह $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} })$परिभाषा में एक सेट के अस्तित्व द्वारा प्रतिस्थापित किया जाता है जो कि कुछ परिमित सेट का सबसेट है। इस संपत्ति को विभिन्न रूप से सबफाइनली इंडेक्स कहा जाता है।

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

यह भी देखें

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