समशक्तता, गणनीयता কী?

उदाहरण 1.7 (एक युग्मन फलन, कार्य करते हुए)

उपपत्ति में आया एकैकी आच्छादक प्रतिचित्रण $(p, q) \mapsto 2^p(2q + 1) - 1$ काम करते हुए देखने योग्य है। उसके पहले कुछ मान:

पंक्ति $p$ उन पूर्णांकों $n$ को इकट्ठा करती है जिनके लिए $n + 1$ ठीक $2^p$ से विभाज्य है: हर प्राकृत संख्या ठीक एक बार प्रकट होती है। विसंकेतन संकेतन जितना ही स्पष्ट है: $n = 43$ के लिए गुणनखंडन $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$ कीजिए, अतः $(p, q) = (2, 5)$। समापन दृष्टि: गणनीयता की उपपत्तियाँ प्रायः भेस बदले हुए कलनविधियाँ होती हैं — यहाँ, “दो के गुणनखंड बाहर निकालिए”।

उदाहरण 1.8 (बीजीय संख्याएँ गणनीय हैं)

कोई सम्मिश्र संख्या बीजीय कहलाती है जब वह परिमेय गुणांकों वाले किसी अशून्य बहुपद का मूल हो। बीजीय संख्याओं का समुच्चय $\overline\Q$ गणनीय है: $\Q$ पर घात $\leq d$ के बहुपद $\Q^{d+1}$ में एकैकी रूप से जाते हैं, जो गणनीय समुच्चयों का परिमित गुणन है (प्रतिज्ञप्ति 1.6 (2)); $d$ पर सम्मिलन लेने से अशून्य परिमेय बहुपदों की गणना $P_0, P_1, P_2, \dots$ के रूप में हो जाती है; प्रत्येक $P_k$ के मूल परिमित हैं; और

परिमित समुच्चयों का गणनीय सम्मिलन है (प्रतिज्ञप्ति 1.6 (3)), तथा अनंत है क्योंकि इसमें $\Q$ समाहित है। $\R$ की अगणनीयता (नीचे प्रमेय 1.9) के साथ मिलाकर यह सिद्ध करता है — एक भी उदाहरण दिखाए बिना — कि अबीजीय संख्याएँ विद्यमान हैं और अगणनीय बहुमत बनाती हैं: यही कैंटर का 1874 का गणना-तर्क है, केवल गणनसंख्या से अस्तित्व।

उदाहरण 1.11

$\intoo{0}{1}$ और $\intcc{0}{1}$ समशक्त हैं: एक दिशा में तत्समक एकैकी है, दूसरी दिशा में $x \mapsto \frac{x + 1}{3}$; और प्रमेय (अनिवार्यतः असंतत) एकैकी आच्छादक प्रतिचित्रण गढ़ देती है। इसी प्रकार $\R$, $\intoo{0}{1}$ ($\tanh$ प्रकार के एकैकी आच्छादक प्रतिचित्रणों से) तथा $\mathcal{P}(\N)$ (द्विआधारी प्रसार, अभ्यास 1.3) सब समशक्त हैं: यही “सांतत्यक की गणनसंख्या” है।