उपगणनीयता

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

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

जहाँ $f\colon I\twoheadrightarrow X$ दर्शाता है $f$ विशेषण फलन होते है $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$ और ओमेगा गणनीयता गुण धर्म अनिवार्य रूप से सबसमुच्चय के संदर्भ में परिभाषित की गई है $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$ कहा जाता है ओमेगा रचनात्मक और उत्पादक अगर, जब भी इसका कोई उपसमुच्चय $W\subset X$ जो किसी फलन का वह कार्यक्षेत्र होता है जिस पर कोई आंशिक फलन ${\mathbb {N} }$, के रूप में होता है वहाँ अधिकांशतः $d\in X\setminus W$ तत्व उपस्थित होता है, जो उस सीमा के पूरक में रहता है।

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

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

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

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

रचनात्मक रूप से पढ़ें, यह किसी आंशिक फलन को जोड़ता है $w$ तत्व के साथ $d$ उस फलन सीमा में नहीं होता है। यह गुण धर्म की असंगति पर जोर देती है ओमेगा समुच्चय $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}$. सबकाउंटेबिलिटी पोस्टुलेट्स द्वारा सीजेडएफ सिद्धांत के गैर-मौलिक विस्तार के लिए मॉडल का निर्माण किया गया है। इस तरह के गैर-रचनात्मक स्वयंसिद्धों के सिद्धांतों के रूप में देखा जाता है जो, चूँकि क्रमिक विश्लेषण सिद्धांतों की प्रमाण-सैद्धांतिक ताकत को बहुत अधिक नहीं बढ़ाते हैं।

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

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

यह भी देखें

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