---
title: "तर्क, समुच्चय और प्रतिचित्रण"
book: "विश्वविद्यालय गणित — स्नातक वर्ष 1"
subject: math
language: hi
chapter: 1
exercises: 12
source: https://one-course.com/books/math/3/hi/chapter/1-logic-sets-and-maps
---

# अध्याय 1 — तर्क, समुच्चय और प्रतिचित्रण

अब तक उपपत्तियाँ “सिद्ध करने” के एक अनौपचारिक किंतु ईमानदार बोध के सहारे लिखी जाती रही हैं। स्नातक गणित का यह पहला अध्याय खेल के नियमों को स्पष्ट कर देता है: गणितीय [कथन](#def-b1-logic-statement) क्या है, संयोजक और परिमाणक कथनों को कैसे जोड़ते हैं, उपपत्ति में कौन-सी चालें वैध हैं — और फिर इसी नींव पर गणित की दो सार्वभौमिक भाषाएँ खड़ी करता है: [समुच्चय](#def-b1-logic-sets) और [प्रतिचित्रण](#def-b1-logic-map)।

## 1.1 कथन और संयोजक

**परिभाषा 1.1 (कथन, संयोजक).**

*कथन* (या *प्रतिज्ञप्ति*) ऐसा वाक्य है जो या तो सत्य (स) है या असत्य (अ) — ठीक इनमें से एक। कथनों $P$ और $Q$ से बनते हैं:

- *निषेध* $\lnot P$ (“ $P$ नहीं”), जो ठीक तब सत्य है जब $P$ असत्य हो;
- *संयोजन* $P \land Q$ (“ $P$ और $Q$ ”), जो ठीक तब सत्य है जब दोनों सत्य हों;
- *वियोजन* $P \lor Q$ (“ $P$ या $Q$ ”), जो ठीक तब सत्य है जब कम से कम एक सत्य हो (यह “या” समावेशी है);
- *निहितार्थ* $P \implies Q$ , जो ठीक तब असत्य है जब $P$ सत्य हो और $Q$ असत्य;
- *तुल्यता* $P \iff Q$ , जो ठीक तब सत्य है जब $P$ और $Q$ का सत्य-मान समान हो।

**टिप्पणी 1.2.**

$P \implies Q$ की सत्य सारणी पर एक क्षण ठहरना चाहिए: जब $P$ असत्य हो, तब $P
\implies Q$ *सत्य* होता है, चाहे $Q$ कुछ भी हो। “यदि $2 < 1$ तो $0 =
5$” एक सत्य निहितार्थ है। निहितार्थ इस विषय में कुछ नहीं कहता कि उसकी परिकल्पना विफल होने पर क्या होता है।

**प्रतिज्ञप्ति 1.3 (कथनों पर संगणना के नियम).**

सभी कथनों $P$, $Q$, $R$ के लिए:

1. $\lnot(\lnot P) \iff P$ ;
2. डी मॉर्गन के नियम: $\lnot(P \land Q) \iff  (\lnot P) \lor (\lnot Q)$ तथा $\lnot(P \lor Q) \iff (\lnot P) \land (\lnot  Q)$ ;
3. $(P \implies Q) \iff \bigl((\lnot P) \lor Q\bigr)$ , अतः $\lnot(P  \implies Q) \iff P \land (\lnot Q)$ ;
4. प्रतिधनात्मकता: $(P \implies Q) \iff  \bigl((\lnot Q) \implies (\lnot P)\bigr)$ ;
5. $(P \iff Q) \iff \bigl((P \implies Q) \land (Q \implies  P)\bigr)$ ;
6. वितरणशीलता: $P \land (Q \lor R) \iff (P \land Q) \lor (P \land R)$ तथा $P \lor (Q \land R) \iff (P \lor Q) \land (P \lor R)$ ।

**उपपत्ति.** प्रत्येक तुल्यता सत्य सारणियों की तुलना से जाँची जाती है: $P$, $Q$, $R$ से बने दो संयुक्त [कथन](#def-b1-logic-statement) ठीक तब तुल्य हैं जब वे (चार या आठ) प्रत्येक स्थिति में एक ही सत्य-मान लेते हों। पहले डी मॉर्गन नियम के लिए एक सारणी पूरी लिखते हैं:

| $P$ | $Q$ | $P \land Q$ | $\lnot(P \land Q)$ | $\lnot P$ | $\lnot Q$ | $(\lnot P) \lor (\lnot Q)$ |
| --- | --- | --- | --- | --- | --- | --- |
| स | स | स | अ | अ | अ | अ |
| स | अ | अ | स | अ | स | स |
| अ | स | अ | स | स | अ | स |
| अ | अ | अ | स | स | स | स |

स्तंभ $4$ और $7$ मेल खाते हैं, जिससे नियम सिद्ध हो जाता है। प्रतिधनात्मकता के लिए एक शाब्दिक संक्षेप तेज़ पड़ता है: $P \implies Q$ ठीक उसी स्थिति में असत्य है जिसमें ($P$ सत्य, $Q$ असत्य), और $(\lnot Q) \implies (\lnot P)$ ठीक उसी स्थिति में असत्य है जिसमें ($\lnot Q$ सत्य, $\lnot P$ असत्य), अर्थात् ($Q$ असत्य, $P$ सत्य) — वही एकमात्र स्थिति, अतः दोनों निहितार्थों की सारणियाँ समान हैं। शेष नियम इसी प्रकार जाँचे जाते हैं; ध्यान दीजिए कि (3) प्रत्येक निहितार्थ को वियोजन में बदल देता है, जिससे (2) यंत्रवत् निषेध का नियम $\lnot(P \implies Q) \iff P \land (\lnot Q)$ दे देता है: किसी निहितार्थ का खंडन करने के लिए ऐसी स्थिति दिखानी पड़ती है जिसमें परिकल्पना सत्य हो और निष्कर्ष असत्य। ∎

## 1.2 परिमाणक

**परिभाषा 1.4 (परिमाणक).**

मान लीजिए $P(x)$ [समुच्चय](#def-b1-logic-sets) $E$ के किसी अवयव $x$ का कोई गुणधर्म है।

- $\forall x \in E,\ P(x)$ (“ $E$ के सभी $x$ के लिए $P(x)$ ”) तब सत्य है जब $E$ का प्रत्येक अवयव $P$ को संतुष्ट करता हो;
- $\exists x \in E,\ P(x)$ (“ $E$ में ऐसा $x$ है कि $P(x)$ ”) तब सत्य है जब $E$ का कम से कम एक अवयव $P$ को संतुष्ट करता हो।

“अद्वितीय रूप से एक ऐसा अवयव है” के लिए $\exists!$ लिखा जाता है।

**प्रतिज्ञप्ति 1.5 (परिमाणकों का निषेध).**

$$
\lnot\bigl(\forall x \in E,\ P(x)\bigr) \iff
\exists x \in E,\ \lnot P(x),
\qquad
\lnot\bigl(\exists x \in E,\ P(x)\bigr) \iff
\forall x \in E,\ \lnot P(x).
$$

**उपपत्ति.** पहली तुल्यता को दोनों दिशाओं में देखते हैं; दूसरी सममित है। यदि $\forall x
\in E,\ P(x)$ असत्य है, तो प्रत्येक अवयव $P$ को संतुष्ट नहीं करता: [समुच्चय](#def-b1-logic-sets) $A = \{x \in E : \lnot P(x)\}$ रिक्त नहीं हो सकता, और उसका कोई भी अवयव $\exists x \in E,\ \lnot P(x)$ का साक्षी है। विलोमतः, यदि कोई $x_0 \in E$ $\lnot P(x_0)$ को संतुष्ट करता है, तो $x_0$ एक प्रतिउदाहरण है और सार्वत्रिक [कथन](#def-b1-logic-statement) विफल हो जाता है। दूसरे नियम के लिए: “कोई $x$ $P$ को संतुष्ट नहीं करता” का अर्थ है कि [समुच्चय](#def-b1-logic-sets) $\{x : P(x)\}$ रिक्त है, अर्थात् प्रत्येक $x$ अपने पूरक $A$ में स्थित है। परिमाणकों की एक नेस्टेड श्रृंखला पर क्रमशः लगाने से ये दोनों नियम [उदाहरण 1.8](#ex-b1-logic-limit) की यांत्रिक प्रक्रिया देते हैं: निषेध बाएँ से दाएँ चलता है, प्रत्येक $\forall$ को $\exists$ में और प्रत्येक $\exists$ को $\forall$ में बदलता जाता है, और अंत में सबसे भीतरी विधेय का निषेध करता है। ∎

**उदाहरण 1.6 (रोज़मर्रा के गणितीय वाक्यों का निषेध).**

मान लीजिए $f \colon \R \to \R$। वाक्य “$f$ वर्धमान है” इस प्रकार पढ़ा जाता है

$$
\forall x \in \R,\ \forall y \in \R,\quad
x \leq y \implies f(x) \leq f(y) ,
$$

और [प्रतिज्ञप्ति 1.5](#prop-b1-logic-negquant) तथा नियम $\lnot(P \implies Q) \iff P \land
\lnot Q$ से इसका निषेध:

$$
\exists x \in \R,\ \exists y \in \R,\quad
x \leq y \ \text{ और }\ f(x) > f(y) :
$$

एक ही साक्षी युग्म पर्याप्त है। इसी प्रकार “$f$ परिबद्ध है” का अर्थ है $\exists M \in \R,\ \forall x \in \R,\ \abs{f(x)} \leq M$, जिसका निषेध

$$
\forall M \in \R,\ \exists x \in \R,\quad \abs{f(x)} > M :
$$

*कोई भी* परिबंध प्रस्तावित किया जाए, कोई-न-कोई बिंदु उससे आगे निकल जाता है। सार: सही निषेध में “नहीं” कभी किसी परिमाणित खंड पर नहीं लगता — वह एक नया धनात्मक [कथन](#def-b1-logic-statement) होता है, जिसमें भूमिकाएँ बदल जाती हैं: जो साक्षी पहले मिलते थे, अब उन्हें स्वयं प्रस्तुत करना पड़ता है।

**उदाहरण 1.7 (परिमाणकों का क्रम).**

भिन्न परिमाणकों का क्रम महत्त्व रखता है:

$$
\forall x \in \R,\ \exists y \in \R,\ y > x
\quad\text{सत्य है (लीजिए } y = x+1\text{),}
$$

$$
\exists y \in \R,\ \forall x \in \R,\ y > x
\quad\text{असत्य है (कोई वास्तविक संख्या सभी वास्तविक संख्याओं से बड़ी नहीं होती)।}
$$

पहले [कथन](#def-b1-logic-statement) में $y$ का $x$ पर निर्भर होना संभव है; दूसरे में एक ही $y$ को सभी $x$ के लिए काम करना होगा। दूसरी ओर, दो समान परिमाणक सदैव आपस में स्थान बदल सकते हैं।

**उदाहरण 1.8 (तीन परिमाणकों वाली परिभाषा पढ़ना).**

वाक्य “अनुक्रम $(u_n)$ का अभिसरण $\ell$ की ओर होता है” [अध्याय 11](https://one-course.com/books/math/3/hi/chapter/11-sequences#ch-b1-seq) में इस प्रकार लिखा जाएगा

$$
\forall \varepsilon > 0,\ \exists N \in \N,\ \forall n \geq N,\quad
\abs{u_n - \ell} \leq \varepsilon .
$$

[प्रतिज्ञप्ति 1.5](#prop-b1-logic-negquant) को तीन बार लगाने पर इसका निषेध है

$$
\exists \varepsilon > 0,\ \forall N \in \N,\ \exists n \geq N,\quad
\abs{u_n - \ell} > \varepsilon .
$$

ऐसे वाक्यों का, उनके अर्थ पर सोचे बिना, यंत्रवत् निषेध कर पाना एक वास्तविक कौशल है: यह तार्किक काम को गणितीय काम से अलग कर देता है।

## 1.3 उपपत्ति की विधियाँ

**विधि 1.9 (उपपत्ति के मानक प्रारूप).**

सिद्ध करने के लिए…

1. *निहितार्थ $P \implies Q$ को सीधे* : $P$ मान लीजिए, $Q$ निकालिए;
2. *प्रतिधनात्मकता द्वारा* : $\lnot Q$ मान लीजिए, $\lnot P$ निकालिए — [प्रतिज्ञप्ति 1.3](#prop-b1-logic-rules) (4) से वैध;
3. *विरोधाभास द्वारा* : [कथन](#def-b1-logic-statement) को असत्य मान लीजिए और विरोधाभास तक पहुँचिए;
4. *तुल्यता* : दोनों निहितार्थ अलग-अलग सिद्ध कीजिए (या ज्ञात तुल्यताओं की शृंखला बनाइए);
5. *“सभी के लिए” वाला [कथन](#def-b1-logic-statement)* : $E$ में एक *स्वेच्छ* $x$ चुनिए (“मान लीजिए $x \in E$ ”) और $P(x)$ सिद्ध कीजिए;
6. *“अस्तित्व है” वाला [कथन](#def-b1-logic-statement)* : एक साक्षी प्रस्तुत कीजिए, या अस्तित्व अप्रत्यक्ष रूप से सिद्ध कीजिए;
7. *आगमन द्वारा* : [प्रमेय 1.12](#thm-b1-logic-induction) देखिए।

किसी सुचयनित किंतु स्वेच्छ अवयव के विषय में [कथन](#def-b1-logic-statement) सिद्ध करते समय उस अवयव को कभी अतिरिक्त गुणधर्म मत दीजिए: “मान लीजिए $x \in \R$” के बाद “चूँकि $x >
0$…” ऋणात्मक $x$ के विषय में कुछ भी सिद्ध नहीं करता।

**टिप्पणी 1.10 (उपपत्तियों में सामान्य भूलें).**

चार चिरपरिचित जाल, जिन्हें एक बार नाम देकर पहचान लेना उचित है।

1. *प्रतिधनात्मक के स्थान पर विलोम।* $Q \implies P$ $P \implies Q$ के तुल्य *नहीं* है; केवल $\lnot Q \implies \lnot P$ तुल्य है। “यदि वर्षा होती है तो सड़क गीली होती है” से गीली सड़क देखकर वर्षा का निष्कर्ष निकालने का अधिकार नहीं मिलता।
2. *तुल्यता को एक ही निहितार्थ से सिद्ध करना।* “यदि और केवल यदि” का दावा दो प्रमेय है; घोषित कीजिए कि कौन-सी दिशा सिद्ध की जा रही है, और दोनों सिद्ध कीजिए। $\iff$ की शृंखलाएँ तभी वैध हैं जब *प्रत्येक* कड़ी सचमुच उत्क्रमणीय हो — उदाहरणतः समीकरण का वर्ग करना उत्क्रमणीय नहीं है।
3. *उलटी दिशा की उपपत्तियाँ।* अभीष्ट निष्कर्ष से आरंभ करके किसी सत्य [कथन](#def-b1-logic-statement) तक पहुँचना कुछ भी सिद्ध नहीं करता ( $-1 = 1$ से वर्ग करके सत्य $1  = 1$ निकल आता है)। कोई संगणना उलटी दिशा में *खोजी* भले जाए, पर उसे सीधी दिशा में, या स्पष्ट तुल्यताओं के साथ, *लिखना* पड़ता है।
4. *नियत साक्षी बनाम स्वेच्छ अवयव।* $\exists x,\ P(x)$ सिद्ध करने के लिए एक ही चतुराई से चुना हुआ $x$ प्रस्तुत किया जा सकता है; $\forall x,\  P(x)$ सिद्ध करने के लिए चुना हुआ $x$ स्वेच्छ बना रहना चाहिए। दोनों को मिला देना — सार्वत्रिक दावे को एक उदाहरण पर जाँच लेना — आरंभिक उत्तर-पुस्तिकाओं की सबसे आम भूल है।

**उदाहरण 1.11 (प्रतिधनात्मकता और विरोधाभास काम पर).**

*$n \in \N$ के लिए: यदि $n^2$ सम है तो $n$ सम है।* प्रतिधनात्मकता द्वारा: यदि $n$ विषम है, $n = 2k+1$, तो $n^2 = 4k^2 + 4k + 1$ विषम है।

*$\sqrt 2$ अपरिमेय है।* विरोधाभास द्वारा: मान लीजिए $\sqrt 2 = p/q$, जहाँ $p, q \in \N^*$ और भिन्न न्यूनतम पदों में है। तब $p^2 = 2q^2$ सम है, अतः $p$ सम है (पिछला बिंदु), $p = 2r$; तब $q^2 = 2r^2$ सम है, अतः $q$ सम है — जो न्यूनतम पदों का विरोध करता है।

**प्रमेय 1.12 (आगमन).**

मान लीजिए $P(n)$ पूर्णांक $n$ का कोई गुणधर्म है। यदि

1. $P(0)$ सत्य है, तथा
2. सभी $n \in \N$ के लिए $P(n) \implies P(n+1)$ ,

तो $P(n)$ सभी $n \in \N$ के लिए सत्य है।

*प्रबल आगमन:* यदि (2) के स्थान पर यह रखा जाए तो निष्कर्ष अपरिवर्तित रहता है: सभी $n$ के लिए $\bigl(P(0) \land \dots \land P(n)\bigr) \implies
P(n+1)$।

**उपपत्ति.** यह स्वयं $\N$ का गुणधर्म है, जो इसके तुल्य है: *$\N$ के प्रत्येक अरिक्त उपसमुच्चय में एक न्यूनतम अवयव होता है* (जिसे हम ज्ञात मान लेते हैं)। वस्तुतः, मान लीजिए (1) और (2) सत्य हैं तथा $A = \{n \in \N : P(n) \text{
असत्य}\}$ है। यदि $A \neq \emptyset$, तो उसमें एक न्यूनतम अवयव $m$ है; (1) से $m \neq 0$; तब $m - 1 \notin A$, अतः $P(m-1)$ सत्य है, और (2) से $P(m)$ मिलता है — विरोधाभास। अतः $A = \emptyset$। प्रबल आगमन के लिए वही तर्क लगाइए: $P(0), \dots, P(m-1)$ सभी सत्य हैं, क्योंकि $m$ $A$ का न्यूनतम अवयव है। ∎

**उदाहरण 1.13 (अद्वितीय अस्तित्व सिद्ध करना).**

[कथन](#def-b1-logic-statement) $\exists!\,x,\ P(x)$ वस्तुतः *दो* [कथन](#def-b1-logic-statement) हैं, जिन्हें अलग-अलग सिद्ध किया जाता है: अस्तित्व (कोई $x_0$ प्रस्तुत या निर्मित कीजिए जिसके लिए $P(x_0)$) और अद्वितीयता ($P(x)$ तथा $P(x')$ मानकर $x = x'$ निकालिए)। नमूना: *ऐसा अद्वितीय वास्तविक $x$ है जिसके लिए $x^3 + x = 2$।* अस्तित्व: $x_0
= 1$ काम करता है, क्योंकि $1 + 1 = 2$। अद्वितीयता: यदि $x^3 + x = x'^3 +
x'$, तो

$$
0 = (x^3 - x'^3) + (x - x')
= (x - x')\,\bigl(x^2 + xx' + x'^2 + 1\bigr),
$$

और दूसरा गुणनखंड धनात्मक है (वह $\bigl(x + \tfrac{x'}2\bigr)^2 + \tfrac34
x'^2 + 1 \geq 1$ के बराबर है), अतः $x = x'$। श्रम-विभाजन पर ध्यान दीजिए: अस्तित्व के लिए एक सौभाग्यपूर्ण अनुमान काम आया, जबकि अद्वितीयता के लिए *स्वेच्छ* हलों पर वैध बीजगणित। कोई भी तर्क दूसरे का काम नहीं करता, और एक हल मिल जाने के बाद दूसरे आधे को भूल जाना सदा बना रहने वाला प्रलोभन है।

**उदाहरण 1.14.**

सभी $n \in \N^*$ के लिए: $\;\sum_{k=1}^n k = \frac{n(n+1)}{2}$। आधार स्थिति $n = 1$: दोनों पक्ष $1$ के बराबर हैं। पद: $n$ के लिए सूत्र मानकर,

$$
\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + (n+1)
= (n+1)\Bigl(\frac n2 + 1\Bigr) = \frac{(n+1)(n+2)}{2}. \qedhere
$$

**उदाहरण 1.15 (प्रबल आगमन काम पर).**

*प्रत्येक पूर्णांक $n \geq 2$ अभाज्य संख्याओं का गुणनफल है* (यहाँ अभाज्य से तात्पर्य ऐसे पूर्णांक $\geq 2$ से है जिसके $\geq 1$ भाजक केवल $1$ और वह स्वयं हों; अभाज्य संख्याओं का अपने आप में अध्ययन [अध्याय 6](https://one-course.com/books/math/3/hi/chapter/6-integer-arithmetic#ch-b1-arith) में है)। साधारण आगमन यहाँ असहाय है: $95 = 5 \times 19$ का गुणनखंडन जानने से $96$ के विषय में कुछ नहीं मिलता। प्रबल आगमन ठीक बैठता है। आधार स्थिति: $2$ अभाज्य है, अतः (एक गुणनखंड वाला) अभाज्यों का गुणनफल है। पद: मान लीजिए $n
\geq 2$ और मान लीजिए कि $2 \leq m \leq n$ वाला प्रत्येक पूर्णांक $m$ अभाज्यों का गुणनफल है। यदि $n + 1$ अभाज्य है, तो काम पूरा। अन्यथा $n + 1 =
ab$, जहाँ $2 \leq a, b \leq n$; प्रबल परिकल्पना से $a$ और $b$ दोनों अभाज्यों के गुणनफल हैं, अतः $n + 1$ भी। सार: प्रबल आगमन ठीक तभी सही औज़ार है जब $P(n+1)$ का “कारण” किसी अप्रत्याशित पूर्ववर्ती कोटि पर हो, न कि कोटि $n$ पर।

## 1.4 समुच्चय

**परिभाषा 1.16 (समुच्चय पर संक्रियाएँ).**

हम *समुच्चय* की धारणा और सदस्यता संबंध $x \in E$ को मूलभूत मान लेते हैं। किसी परिवेशी समुच्चय $E$ के भीतर समुच्चयों $A, B$ के लिए:

- *अंतर्विष्टि* : $A \subseteq B$ तब जब $\forall x,\ x \in A  \implies x \in B$ ; समता $A = B$ तब जब $A \subseteq B$ और $B \subseteq A$ ;
- *सम्मिलन* $A \cup B$ , *प्रतिच्छेदन* $A \cap B$ , *अंतर* $A \setminus B = \{x \in A : x \notin B\}$ , *पूरक* $\overline{A} = E \setminus A$ ;
- *रिक्त समुच्चय* $\emptyset$ , जो प्रत्येक समुच्चय में अंतर्विष्ट है;
- *घात समुच्चय* $\mathcal{P}(E)$ : $E$ के सभी उपसमुच्चयों का समुच्चय;
- *कार्तीय गुणन* $E \times F$ : क्रमित युग्मों $(x, y)$ का समुच्चय, जहाँ $x \in E$ , $y \in F$ ।

**उदाहरण 1.17 (घात समुच्चय से परिचय).**

$E = \{a, b\}$ के लिए:

$$
\mathcal P(E) = \bigl\{\, \emptyset,\ \{a\},\ \{b\},\ \{a, b\}
\,\bigr\},
$$

चार अवयव — और प्रकार-अनुशासन पर ध्यान दीजिए: $a \in E$, किंतु $\{a\} \in
\mathcal P(E)$; [कथन](#def-b1-logic-statement) $a \in \mathcal P(E)$ और $\{a\} \subseteq \mathcal P(E)$ लिखे हुए रूप में असत्य हैं (दूसरे के लिए $a$ का $E$ का *उपसमुच्चय* होना आवश्यक होता)। शून्य से आरंभ करके दोहराने पर: $\mathcal P(\emptyset) =
\{\emptyset\}$ में एक अवयव है, $\mathcal P(\mathcal P(\emptyset)) =
\{\emptyset, \{\emptyset\}\}$ में दो, अगले में चार — समुच्चयों के [समुच्चय](#def-b1-logic-sets) भी साधारण [समुच्चय](#def-b1-logic-sets) ही हैं, और [अध्याय 2](https://one-course.com/books/math/3/hi/chapter/2-counting#ch-b1-counting) इस दुगुना होने के प्रतिरूप की पुष्टि करेगा: $\abs{\mathcal P(E)} = 2^{\abs E}$। स्तरों ($x$, $\{x\}$, $\{\{x\}\}$) को अलग-अलग बनाए रखना अभ्यास [1.11](#exo-b1-logic-11) और [1.12](#exo-b1-logic-12) जैसे अभ्यासों की आधी लड़ाई है।

**प्रतिज्ञप्ति 1.18 (समुच्चय बीजगणित).**

$E$ के उपसमुच्चयों $A, B, C$ के लिए:

1. $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ तथा $A \cup (B \cap  C) = (A \cup B) \cap (A \cup C)$ ;
2. डी मॉर्गन: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ तथा $\overline{A \cap B} = \overline{A} \cup \overline{B}$ ;
3. $A \subseteq B \iff \overline{B} \subseteq \overline{A}$ .

**उपपत्ति.** प्रत्येक सर्वसमिका [प्रतिज्ञप्ति 1.3](#prop-b1-logic-rules) के किसी नियम का अनुवाद है, इस शब्दकोश के द्वारा: ($\in A$ या नहीं) $\leftrightarrow$ ([कथन](#def-b1-logic-statement) सत्य या असत्य); उदाहरणार्थ $x \in \overline{A \cup B} \iff \lnot(x \in A \lor x \in B) \iff
(x \notin A) \land (x \notin B) \iff x \in \overline{A} \cap \overline{B}$। बिंदु (3) प्रतिधनात्मकता है। दूसरे नमूने के रूप में, पहला वितरण नियम पूरा:

$$
x \in A \cap (B \cup C)
\iff (x \in A) \land \bigl(x \in B \lor x \in C\bigr)
\iff \bigl(x \in A \land x \in B\bigr) \lor
\bigl(x \in A \land x \in C\bigr),
$$

[प्रतिज्ञप्ति 1.3](#prop-b1-logic-rules) (6) की वितरणशीलता से; और अंतिम [कथन](#def-b1-logic-statement) $x \in (A \cap
B) \cup (A \cap C)$ पढ़ा जाता है। इस प्रकार की प्रत्येक [समुच्चय](#def-b1-logic-sets) सर्वसमिका इसी एक यांत्रिक अनुवाद से सिद्ध हो जाती है — यही कारण है कि इनमें से किसी को कंठस्थ करने की आवश्यकता नहीं। ∎

**विधि 1.19 (समुच्चयों की समता सिद्ध करना).**

$A = B$ सिद्ध करने के लिए दोनों अंतर्विष्टियाँ सिद्ध कीजिए: मान लीजिए $x \in
A$, दिखाइए $x \in B$; फिर मान लीजिए $x \in B$, दिखाइए $x \in A$। वैकल्पिक रूप से, जब प्रत्येक पद सचमुच तुल्यता हो, तब तुल्यताओं की शृंखला $x \in A
\iff \dots \iff x \in B$ बनाइए।

![चित्रों में डी मॉर्गन के नियम: बाईं ओर छायांकित क्षेत्र A ∪ B = A ∩ B है (दोनों वृत्तों के बाहर का सब कुछ); दाईं ओर A ∩ B = A ∪ B है (मसूर के आकार के अतिव्यापन को छोड़कर सब कुछ)। आरेख उपपत्ति नहीं है, पर वह की अवयव-पीछा करने वाली उपपत्ति को भुलाना असंभव बना देता है।](https://one-course.com/images/onecourse/chapters/math-3/b1-logic/fig-5465323f1d10.svg)

*चित्रों में डी मॉर्गन के नियम: बाईं ओर छायांकित क्षेत्र $\overline{A
\cup B} = \overline A \cap \overline B$ है (दोनों वृत्तों के बाहर का सब कुछ); दाईं ओर $\overline{A \cap B} = \overline A \cup \overline B$ है (मसूर के आकार के अतिव्यापन को छोड़कर सब कुछ)। आरेख उपपत्ति नहीं है, पर वह [प्रतिज्ञप्ति 1.18](#prop-b1-logic-setalgebra) की अवयव-पीछा करने वाली उपपत्ति को भुलाना असंभव बना देता है।*

## 1.5 प्रतिचित्रण

**परिभाषा 1.20 (प्रतिचित्रण, प्रतिबिंब, पूर्वप्रतिबिंब).**

*प्रतिचित्रण* (या *फलन*) $f \colon E \to F$ [समुच्चय](#def-b1-logic-sets) $E$ (*प्रांत*) के प्रत्येक अवयव $x$ को [समुच्चय](#def-b1-logic-sets) $F$ (*सहप्रांत*) का ठीक एक अवयव $f(x)$ सौंपता है। $A \subseteq E$ और $B
\subseteq F$ के लिए:

$$
f(A) = \{f(x) : x \in A\} \subseteq F,
\qquad
f^{-1}(B) = \{x \in E : f(x) \in B\} \subseteq E
$$

क्रमशः $A$ का *अग्र प्रतिबिंब* और $B$ का *पूर्वप्रतिबिंब* कहलाते हैं। $f \colon E \to F$ और $g \colon F \to G$ का *संयोजन* $g \circ f \colon E \to G$ है, $x \mapsto g(f(x))$।

**टिप्पणी 1.21.**

संकेतन $f^{-1}(B)$ किसी प्रतिलोम [प्रतिचित्रण](#def-b1-logic-map) को *पूर्वमान्य नहीं* करता: $f^{-1}(B)$ प्रत्येक $f$ के लिए परिभाषित है। [पूर्वप्रतिबिंब](#def-b1-logic-map) प्रतिबिंबों की तुलना में अधिक सुव्यवहृत हैं: $f^{-1}$ सम्मिलन, प्रतिच्छेदन और पूरक को सुरक्षित रखता है, जबकि $f(A \cap A') \subseteq f(A) \cap f(A')$ कठोर हो सकता है ([अभ्यास 1.8](#exo-b1-logic-8))।

**उदाहरण 1.22 (प्रतिबिंब और पूर्वप्रतिबिंब की संगणना).**

मान लीजिए $f \colon \R \to \R$, $x \mapsto x^2$। तब:

$$
f\bigl(\intcc{-1}{2}\bigr) = \intcc04, \qquad
f^{-1}\bigl(\intcc14\bigr) = \intcc{-2}{-1} \cup \intcc12, \qquad
f^{-1}(\{-1\}) = \emptyset .
$$

पहले के लिए: प्रत्येक $x \in \intcc{-1}2$ के लिए $x^2 \in \intcc04$, और प्रत्येक $y \in \intcc04$ $y = (\sqrt y)^2$ के रूप में प्राप्त होता है, जहाँ $\sqrt y \in \intcc02 \subseteq \intcc{-1}2$ — ध्यान दीजिए कि प्रतिबिंब $\intcc14 = \{(-1)^2, 2^2\}$ *नहीं* है: अंतरालों के प्रतिबिंब केवल सिरों से नहीं निकाले जाते। दूसरे के लिए: $1 \leq x^2 \leq 4 \iff 1 \leq \abs
x \leq 2$, जो दो टुकड़ों में बँट जाता है। तीसरा दिखाता है कि [पूर्वप्रतिबिंब](#def-b1-logic-map) रिक्त भी हो सकता है — $f^{-1}(B)$ सदा अर्थपूर्ण है, चाहे $B$ का प्रतिबिंब से प्रतिच्छेदन कितना ही छोटा हो। अंत में इसी उदाहरण पर ऊपर की टिप्पणी वाली कठोरता की परिघटना देखिए: $A = \intcc{-1}0$ और $A' = \intcc01$ लेने पर $f(A
\cap A') = f(\{0\}) = \{0\}$ मिलता है, जबकि $f(A) \cap f(A') = \intcc01$।

**परिभाषा 1.23 (एकैकी, आच्छादक, एकैकी आच्छादक).**

[प्रतिचित्रण](#def-b1-logic-map) $f \colon E \to F$ है:

- *एकैकी* तब, जब भिन्न अवयवों के प्रतिबिंब भिन्न हों: $\forall x, x' \in E,\ f(x) = f(x') \implies x = x'$ ;
- *आच्छादक* तब, जब $F$ का प्रत्येक अवयव प्राप्त होता हो: $\forall y \in F,\ \exists x \in E,\ f(x) = y$ ;
- *एकैकी आच्छादक* तब, जब वह दोनों हो, अर्थात् प्रत्येक $y \in F$ का ठीक एक [पूर्वप्रतिबिंब](#def-b1-logic-map) हो।

**प्रमेय 1.24 (प्रतिलोम प्रतिचित्रण).**

[प्रतिचित्रण](#def-b1-logic-map) $f \colon E \to F$ [एकैकी आच्छादक](#def-b1-logic-inj) है यदि और केवल यदि ऐसा [प्रतिचित्रण](#def-b1-logic-map) $g \colon F \to E$ हो जिसके लिए $g \circ f = \mathrm{id}_E$ और $f \circ g = \mathrm{id}_F$। उस स्थिति में $g$ अद्वितीय होता है; उसे $f^{-1}$ लिखा जाता है और $f$ का *प्रतिलोम* कहा जाता है, और $f^{-1}$ स्वयं [एकैकी आच्छादक](#def-b1-logic-inj) है, जिसके लिए $(f^{-1})^{-1} = f$।

**उपपत्ति.** ($\Rightarrow$) यदि $f$ [एकैकी आच्छादक](#def-b1-logic-inj) है, तो प्रत्येक $y \in F$ का अद्वितीय [पूर्वप्रतिबिंब](#def-b1-logic-map) है; $g(y)$ को वही [पूर्वप्रतिबिंब](#def-b1-logic-map) परिभाषित कीजिए। तब रचना से $f(g(y)) = y$, और $g(f(x)) = x$, क्योंकि $x$ $f(x)$ का *एकमात्र* [पूर्वप्रतिबिंब](#def-b1-logic-map) है।

($\Leftarrow$) मान लीजिए ऐसा $g$ विद्यमान है। यदि $f(x) = f(x')$, तो $g$ लगाने पर $x = x'$: अर्थात् $f$ [एकैकी](#def-b1-logic-inj) है। $y \in F$ के लिए $x = g(y)$ $f(x) =
y$ को संतुष्ट करता है: अर्थात् $f$ [आच्छादक](#def-b1-logic-inj) है।

अद्वितीयता: यदि $g$ और $h$ दोनों काम करते हैं, तो $g = g \circ \mathrm{id}_F
= g \circ (f \circ h) = (g \circ f) \circ h = h$। अंत में, सर्वसमिकाओं का यह युग्म $f$ और $g$ में सममित है, अतः $g = f^{-1}$ [एकैकी आच्छादक](#def-b1-logic-inj) है और उसका प्रतिलोम $f$ है। ∎

**उदाहरण 1.25 (व्यवहार में प्रतिलोम की संगणना).**

मान लीजिए $f \colon \R \to \intoo0{+\infty}$, $f(x) = \eu^{2x+1}$। प्रतिलोम निकालने के लिए दिए हुए $y > 0$ के लिए $y = f(x)$ हल कीजिए:

$$
y = \eu^{2x+1} \iff \ln y = 2x + 1 \iff x = \frac{\ln y - 1}2 ,
$$

घोषित प्रांतों पर हर पद उत्क्रमणीय है। यह संगणना एक साथ सब कुछ दे देती है: सहप्रांत के प्रत्येक $y$ के लिए ठीक एक हल $x$ है, अतः $f$ [एकैकी आच्छादक](#def-b1-logic-inj) है, और

$$
f^{-1} \colon \intoo0{+\infty} \to \R,
\qquad
f^{-1}(y) = \frac{\ln y - 1}2 .
$$

दोनों संयोजनों की त्वरित जाँच ($f^{-1}(f(x)) = \frac{(2x+1) - 1}2 = x$ और $f(f^{-1}(y)) = \eu^{\ln y} = y$) [प्रमेय 1.24](#thm-b1-logic-inverse) की कसौटी की पुष्टि करती है। सार: “$x$ के लिए हल कीजिए और तुल्यताओं पर दृष्टि रखिए” एक ही साथ अस्तित्व की उपपत्ति, अद्वितीयता की उपपत्ति और सूत्र है — पर यह तभी काम करता है जब सहप्रांत सही घोषित किया गया हो ($f$ $\R$ पर [आच्छादक](#def-b1-logic-inj) *नहीं* है)।

**प्रतिज्ञप्ति 1.26 (संयोजन और तीनों गुणधर्म).**

मान लीजिए $f \colon E \to F$ और $g \colon F \to G$।

1. यदि $f$ और $g$ [एकैकी](#def-b1-logic-inj) (क्रमशः [आच्छादक](#def-b1-logic-inj) , [एकैकी आच्छादक](#def-b1-logic-inj) ) हैं, तो $g  \circ f$ भी वैसा ही है; और [एकैकी आच्छादक](#def-b1-logic-inj) स्थिति में $(g \circ f)^{-1} =  f^{-1} \circ g^{-1}$ ।
2. यदि $g \circ f$ [एकैकी](#def-b1-logic-inj) है, तो $f$ [एकैकी](#def-b1-logic-inj) है। यदि $g \circ f$ [आच्छादक](#def-b1-logic-inj) है, तो $g$ [आच्छादक](#def-b1-logic-inj) है।

**उपपत्ति.** (1) यदि $g(f(x)) = g(f(x'))$, तो $g$ की एकैकीयता से $f(x) = f(x')$ मिलता है, फिर $f$ की एकैकीयता से $x = x'$। यदि $z \in G$, तो $g$ की आच्छादकता से ऐसा $y$ मिलता है कि $g(y) = z$, फिर $f$ की आच्छादकता से ऐसा $x$ कि $f(x) = y$, अतः $g(f(x)) = z$। [एकैकी आच्छादक](#def-b1-logic-inj) स्थिति में सीधे जाँच लिया जाता है कि $f^{-1} \circ g^{-1}$ $g \circ f$ का द्विपक्षीय प्रतिलोम है, और [प्रमेय 1.24](#thm-b1-logic-inverse) की अद्वितीयता निष्कर्ष दे देती है।

(2) यदि $f(x) = f(x')$, तो $g(f(x)) = g(f(x'))$, और $g \circ f$ की एकैकीयता से $x = x'$। यदि $z \in G$, तो $g \circ f$ की आच्छादकता से ऐसा $x$ मिलता है कि $g(f(x)) = z$: तब $y = f(x)$ $g(y) = z$ को संतुष्ट करता है। ∎

**उदाहरण 1.27 (बिंदु (2) तीक्ष्ण है).**

[प्रतिज्ञप्ति 1.26](#prop-b1-logic-comp) (2) में निष्कर्षों को और आगे नहीं बढ़ाया जा सकता: $g \circ f$ का [एकैकी आच्छादक](#def-b1-logic-inj) होना $f$ को [आच्छादक](#def-b1-logic-inj) या $g$ को [एकैकी](#def-b1-logic-inj) होने के लिए बाध्य *नहीं* करता। लीजिए $E = G = \{1\}$, $F = \{1, 2\}$, जिनमें $f(1)
= 1$ और $g(1) = g(2) = 1$: तब $g \circ f = \mathrm{id}_E$ [एकैकी आच्छादक](#def-b1-logic-inj) है, फिर भी $f$ अवयव $2$ तक नहीं पहुँचता और $g$ दोनों अवयवों को एक में मिला देता है। इसका उपदेश एक सुनिश्चित लेखा-नियम है: संयोजन की सूचना एकैकीयता के लिए *भीतरी* [प्रतिचित्रण](#def-b1-logic-map) की ओर बहती है और आच्छादकता के लिए *बाहरी* [प्रतिचित्रण](#def-b1-logic-map) की ओर, कभी उलटी दिशा में नहीं। ([अभ्यास 1.9](#exo-b1-logic-9) इसी परिघटना को अनंत समुच्चयों के साथ बनाता है, जहाँ यही एकपक्षीय प्रतिलोमों का इंजन है।)

**उदाहरण 1.28.**

$f \colon \R \to \R$, $x \mapsto x^2$ न तो [एकैकी](#def-b1-logic-inj) है ($f(-1) = f(1)$) और न [आच्छादक](#def-b1-logic-inj) ($-1$ का कोई [पूर्वप्रतिबिंब](#def-b1-logic-map) नहीं)। प्रांत और सहप्रांत को सीमित करने पर $f \colon \R_+ \to \R_+$, $x \mapsto x^2$ [एकैकी आच्छादक](#def-b1-logic-inj) है, जिसका प्रतिलोम $y \mapsto \sqrt y$ है। किसी [प्रतिचित्रण](#def-b1-logic-map) की एकैकीयता या आच्छादकता घोषित प्रांत और सहप्रांत पर निर्भर करती है, केवल सूत्र पर नहीं।

## 1.6 संबंध

**परिभाषा 1.29 (तुल्यता संबंध).**

[समुच्चय](#def-b1-logic-sets) $E$ पर *द्विआधारी संबंध* $\mathcal{R}$ *तुल्यता संबंध* तब कहलाता है जब वह *स्वतुल्य* (सभी $x$ के लिए $x \mathbin{\mathcal{R}} x$), *सममित* ($x \mathbin{\mathcal{R}} y
\implies y \mathbin{\mathcal{R}} x$) और *संक्रमक* ($x
\mathbin{\mathcal{R}} y$ तथा $y \mathbin{\mathcal{R}} z$ से $x
\mathbin{\mathcal{R}} z$) हो। $x$ का *तुल्यता वर्ग* $\mathrm{cl}(x) =
\{y \in E : x \mathbin{\mathcal{R}} y\}$ है।

**उदाहरण 1.30 (तीनों अभिगृहीतों की जाँच).**

$\R$ पर $x \mathbin{\mathcal{R}} y$ तब घोषित कीजिए जब $x - y \in \Z$। *स्वतुल्य:* $x - x = 0 \in \Z$। *सममित:* यदि $x - y \in \Z$, तो $y
- x = -(x - y) \in \Z$। *संक्रमक:* यदि $x - y \in \Z$ और $y - z \in
\Z$, तो $x - z = (x - y) + (y - z) \in \Z$ (पूर्णांकों का योग)। अतः $\mathcal R$ एक [तुल्यता संबंध](#def-b1-logic-equiv) है, और $\mathrm{cl}(x) = x + \Z = \{x + k : k
\in \Z\}$: प्रत्येक वर्ग में $\intco01$ का ठीक एक प्रतिनिधि होता है, अर्थात् उसका *भिन्नात्मक भाग*। इसके विपरीत, $\R$ पर संबंध “$\abs{x - y} \leq
1$” स्वतुल्य और सममित है पर संक्रमक *नहीं* ($0 \mathbin{\mathcal R} 1$ और $1 \mathbin{\mathcal R} 2$, फिर भी $\abs{0 - 2} > 1$): निकटता का संचार नहीं होता, और वर्गों में कोई [विभाजन](#thm-b1-logic-partition) नहीं बनता — अभिगृहीतों की जाँच जब यंत्रवत् लगने लगे, तब स्मरण रखने योग्य एक उपयोगी प्रतिउदाहरण।

**प्रमेय 1.31 (वर्ग विभाजन बनाते हैं).**

मान लीजिए $\mathcal{R}$ $E$ पर एक [तुल्यता संबंध](#def-b1-logic-equiv) है। तब [तुल्यता वर्ग](#def-b1-logic-equiv) अरिक्त हैं, जोड़ों में असंयुक्त या समान हैं, और उनका सम्मिलन $E$ है: वे $E$ का एक *विभाजन* बनाते हैं। विलोमतः, $E$ का प्रत्येक [विभाजन](#thm-b1-logic-partition) ठीक एक [तुल्यता संबंध](#def-b1-logic-equiv) (“एक ही टुकड़े में होना”) से इसी प्रकार उत्पन्न होता है।

**उपपत्ति.** स्वतुल्यता से $x \in \mathrm{cl}(x)$, अतः वर्ग अरिक्त हैं और उनका सम्मिलन $E$ है। मान लीजिए $\mathrm{cl}(x) \cap \mathrm{cl}(y) \neq \emptyset$, और $z$ दोनों में स्थित है। तब $x \mathbin{\mathcal{R}} z$ और $y
\mathbin{\mathcal{R}} z$, अतः सममिति और संक्रमकता से $x
\mathbin{\mathcal{R}} y$। अब किसी भी $t \in \mathrm{cl}(y)$ के लिए संक्रमकता से $t \in \mathrm{cl}(x)$ मिलता है, और सममित रूप से भी: दोनों वर्ग समान हैं। विलोम के लिए, मान लीजिए $(E_i)_{i \in I}$ $E$ का एक [विभाजन](#thm-b1-logic-partition) है और $x
\mathbin{\mathcal S} y$ को “कोई टुकड़ा $x$ और $y$ दोनों को समेटता है” के अर्थ में परिभाषित कीजिए। *स्वतुल्य:* $x$ किसी टुकड़े में है, जो तब $x$ को दो बार समेटता है। *सममित:* परिभाषा की शर्त $x$ और $y$ में सममित है। *संक्रमक:* यदि $x, y \in E_i$ और $y, z \in E_j$, तो $y \in E_i \cap
E_j$, अतः $E_i = E_j$ (भिन्न टुकड़े असंयुक्त होते हैं) और $x, z$ एक ही टुकड़े में हैं। $x$ का $\mathcal S$-वर्ग ठीक वही टुकड़ा है जिसमें $x$ है, अतः वर्ग वही दिए हुए टुकड़े हैं। अंत में, संबंध अपने वर्गों से निर्धारित हो जाता है: समान वर्गों वाले दो [तुल्यता संबंध](#def-b1-logic-equiv) उन्हीं युग्मों को संबंधित करते हैं, क्योंकि प्रत्येक $x$ और $y$ को ठीक तब संबंधित करता है जब $y$ $x$ के वर्ग का सदस्य हो — यहीं से अद्वितीयता का दावा निकलता है। ∎

**उदाहरण 1.32.**

$\Z$ पर $n$ के सापेक्ष सर्वांगसमता ($x \equiv y \pmod n$ तब जब $n$ $x - y$ को विभाजित करता है) एक [तुल्यता संबंध](#def-b1-logic-equiv) है; उसके वर्ग $n$ से भाग देने पर एक दिए हुए शेषफल वाले पूर्णांकों के $n$ [समुच्चय](#def-b1-logic-sets) हैं। यही उदाहरण [अध्याय 7](https://one-course.com/books/math/3/hi/chapter/7-algebraic-structures#ch-b1-structures) में वलय $\Z/n\Z$ बन जाता है।

**परिभाषा 1.33 (क्रम संबंध).**

$E$ पर संबंध $\preceq$ *क्रम* तब कहलाता है जब वह स्वतुल्य, *प्रतिसममित* ($x \preceq y$ और $y \preceq x$ से $x = y$) और संक्रमक हो। क्रम *पूर्ण* तब कहलाता है जब कोई भी दो अवयव तुलनीय हों, अन्यथा *आंशिक*। अवयव $M \in A \subseteq E$ $A$ का *महत्तम अवयव* तब कहलाता है जब सभी $a \in A$ के लिए $a \preceq M$; महत्तम (और न्यूनतम) अवयव, जब विद्यमान हों, अद्वितीय होते हैं।

**उदाहरण 1.34.**

$(\R, \leq)$ पूर्णतः क्रमित है। $(\mathcal{P}(E), \subseteq)$ तभी आंशिक रूप से क्रमित हो जाता है जब $E$ में दो अवयव हों: $\{a\}$ और $\{b\}$ तुलनीय नहीं हैं। $\mathcal{P}(\{a,b\})$ के उपसमुच्चय $A = \{\{a\}, \{b\}\}$ का कोई महत्तम अवयव नहीं है, फिर भी उसका एक ऊपरी परिबंध $\{a, b\}$ है: महत्तम अवयवों और ऊपरी परिबंधों का यह भेद $\R$ के लिए [अध्याय 10](https://one-course.com/books/math/3/hi/chapter/10-real-numbers#ch-b1-reals) में लौटता है।

**उदाहरण 1.35 (जाली N2\N^2N2 पर दो क्रम).**

प्राकृत संख्याओं के युग्मों की घटक-दर-घटक तुलना कीजिए: $(a, b) \preceq (a',
b')$ तब जब $a \leq a'$ *और* $b \leq b'$ (*गुणन क्रम*)। यह एक क्रम है — प्रत्येक अभिगृहीत निर्देशांक-दर-निर्देशांक विरासत में मिलता है — पर आंशिक: $(1, 3)$ और $(2, 0)$ अतुलनीय हैं। अब शब्दकोश की तरह तुलना कीजिए: $(a,
b) \preceq_{\mathrm{lex}} (a', b')$ तब जब $a < a'$, या $a = a'$ और $b \leq
b'$ (*कोशीय क्रम*)। संक्रमकता के लिए दो स्थितियों की जाँच चाहिए पर वह सत्य है, और अब कोई भी दो युग्म तुलनीय हैं: यह क्रम पूर्ण है। दोनों क्रम एक ही [समुच्चय](#def-b1-logic-sets) को भिन्न प्रकार से क्रमित करते हैं — $(0, 100)
\preceq_{\mathrm{lex}} (1, 0)$, यद्यपि गुणन क्रम कुछ नहीं कहता — यह स्मरण दिलाता हुआ कि क्रम एक ऐसी संरचना है जिसे हम *चुनते* हैं, [समुच्चय](#def-b1-logic-sets) का गुणधर्म नहीं। कोशीय तुलना कई छँटाई-कसौटियों को एक में बदलने की मानक युक्ति भी है।

**टिप्पणी 1.36 (मध्यांतर: आकार माने एकैकी आच्छादन).**

इस अध्याय का एक मौन विषय प्रकाश में लाने योग्य है: [एकैकी आच्छादक](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) ही गणितज्ञ की “समान आकार” की धारणा हैं। परिमित समुच्चयों के लिए यह [अध्याय 2](https://one-course.com/books/math/3/hi/chapter/2-counting#ch-b1-counting) की गणना-कलन बन जाती है, जहाँ हर सूत्र गुप्त रूप से एक एकैकी आच्छादन है; अनंत समुच्चयों के लिए यह नीचे दी गई सप्ताहांत समस्या बन जाती है, जहाँ $\N$, $\Q$ और $\R$ के आकार सचमुच भिन्न निकलते हैं। यही शब्दकोश इस खंड में दो बार और, परिष्कृत रूपों में, लौटता है: अनुक्रम ([अध्याय 11](https://one-course.com/books/math/3/hi/chapter/11-sequences#ch-b1-seq)) और कुछ नहीं, [प्रतिचित्रण](#def-b1-logic-map) $\N \to \R$ ही हैं, अतः अनुक्रमों के विषय में [कथन](#def-b1-logic-statement) प्रतिचित्रणों के एक [समुच्चय](#def-b1-logic-sets) के विषय में [कथन](#def-b1-logic-statement) हैं; और रैखिक बीजगणित सदिश समष्टियों को एकैकी आच्छादनों से नहीं, बल्कि *रैखिक* एकैकी आच्छादनों से नापेगा, जिनका अस्तित्व एक ही संख्या — विमा ([अध्याय 19](https://one-course.com/books/math/3/hi/chapter/19-finite-dimension#ch-b1-findim)) — से नियंत्रित होता है। जब भी कोई नया “समानपन” प्रकट होता है — समशक्तता, समूहों की तुल्याकारिता ([अध्याय 7](https://one-course.com/books/math/3/hi/chapter/7-algebraic-structures#ch-b1-structures)), रैखिक तुल्याकारिता — [प्रमेय 1.24](#thm-b1-logic-inverse) का प्रतिरूप दुहराता है: समानपन एक उत्क्रमणीय, संरचना-संरक्षी [प्रतिचित्रण](#def-b1-logic-map) है।

**टिप्पणी 1.37 (यह अध्याय कहाँ काम आता है).**

सर्वत्र — पर कुछ स्थान विशेष रूप से चिह्नित करने योग्य हैं। [उदाहरण 1.8](#ex-b1-logic-limit) का तीन-परिमाणक व्यायाम अध्याय [11](https://one-course.com/books/math/3/hi/chapter/11-sequences#ch-b1-seq) और [13](https://one-course.com/books/math/3/hi/chapter/13-limits-and-continuity#ch-b1-continuity) की रोज़ की रोटी है: हर सीमा की उपपत्ति एक स्वेच्छ $\varepsilon$ के विरुद्ध खेला जाने वाला खेल है। [तुल्यता वर्ग](#def-b1-logic-equiv) [अध्याय 7](https://one-course.com/books/math/3/hi/chapter/7-algebraic-structures#ch-b1-structures) में $\Z/n\Z$ के सर्वांगसमता वर्गों के रूप में लौटते हैं, जहाँ [प्रमेय 1.31](#thm-b1-logic-partition) का [विभाजन](#thm-b1-logic-partition) अपनी एक बीजीय संरचना पा लेता है। [क्रम संबंध](#def-b1-logic-order), ऊपरी परिबंध और लघुतम ऊपरी परिबंध [अध्याय 10](https://one-course.com/books/math/3/hi/chapter/10-real-numbers#ch-b1-reals) में $\R$ के अभिगृहीतीय हृदय बन जाते हैं। [एकैकी](#def-b1-logic-inj), [आच्छादक](#def-b1-logic-inj) और [एकैकी आच्छादक](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) [अध्याय 20](https://one-course.com/books/math/3/hi/chapter/20-linear-maps#ch-b1-linmaps) के रैखिक प्रतिचित्रणों के रूप में लौटते हैं, जहाँ एकैकीयता की जाँच एक ही सदिश (अष्टि) पर की जा सकती है; और नीचे दी गई सप्ताहांत समस्या एकैकी आच्छादन की सादी धारणा को *अनंत समुच्चयों के आकारों* के सिद्धांत में बदल देती है, जिसके निष्कर्ष ($\Q$ की गणनीयता, $\R$ की अगणनीयता) अध्याय [10](https://one-course.com/books/math/3/hi/chapter/10-real-numbers#ch-b1-reals) और [12](https://one-course.com/books/math/3/hi/chapter/12-topology-of-the-real-line#ch-b1-topology) में फिर उभरते हैं।

## 1.7 अभ्यास

**अभ्यास 1.1 ★.**

प्रत्येक [कथन](#def-b1-logic-statement) का निषेध “नहीं” शब्द का प्रयोग किए बिना लिखिए:

1. $\forall x \in \R,\ \exists y \in \R,\ x + y > 0$ ;
2. $\exists x \in \R,\ \forall y \in \R,\ xy = 0$ ;
3. $\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in  \R,\ \abs{x} \leq \delta \implies \abs{f(x)} \leq \varepsilon$ (किसी नियत [प्रतिचित्रण](#def-b1-logic-map) $f \colon \R \to \R$ के लिए)।

फिर तय कीजिए कि [कथन](#def-b1-logic-statement) (1) और (2) सत्य हैं या नहीं।

**हल — अभ्यास 1.1.**

निषेध, प्रत्येक परिमाणक के भीतर से $\lnot$ को धकेलते हुए ([प्रतिज्ञप्ति 1.5](#prop-b1-logic-negquant)) और $\lnot(P \implies Q) \iff P \land \lnot
Q$ का प्रयोग करते हुए:

1. $\exists x \in \R,\ \forall y \in \R,\ x + y \leq 0$ ;
2. $\forall x \in \R,\ \exists y \in \R,\ xy \neq 0$ ;
3. $\exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x \in  \R,\ \abs{x} \leq \delta \text{ और } \abs{f(x)} >  \varepsilon$ .

[कथन](#def-b1-logic-statement) (1) सत्य है: $x$ दिया हो, तो $y = -x + 1$ लीजिए; तब $x + y = 1 > 0$। [कथन](#def-b1-logic-statement) (2) सत्य है: $x = 0$ सभी $y$ के लिए $xy = 0$ को संतुष्ट करता है।

**अभ्यास 1.2 ★.**

मान लीजिए $P, Q$ [कथन](#def-b1-logic-statement) हैं। सत्य सारणियों का प्रयोग करके सिद्ध कीजिए कि $\lnot(P \implies Q) \iff P \land (\lnot Q)$, और उससे इसका निषेध निकालिए: “यदि कोई फलन अवकलनीय है तो वह संतत है”।

**हल — अभ्यास 1.2.**

सत्य सारणी, चारों स्थितियों $(P, Q)$ के लिए स/अ लिखते हुए:

| $P$ | $Q$ | $P \implies Q$ | $\lnot(P \implies Q)$ | $\lnot Q$ | $P \land \lnot Q$ |
| --- | --- | --- | --- | --- | --- |
| स | स | स | अ | अ | अ |
| स | अ | अ | स | स | स |
| अ | स | स | अ | अ | अ |
| अ | अ | स | अ | स | अ |

स्तंभ $4$ और $6$ मेल खाते हैं, जिससे तुल्यता सिद्ध हो जाती है। अतः “यदि कोई फलन अवकलनीय है तो वह संतत है” का निषेध है: “ऐसा फलन है जो अवकलनीय है और संतत नहीं” (जो वस्तुतः असत्य [कथन](#def-b1-logic-statement) है: मूल निहितार्थ सत्य है, [अध्याय 14](https://one-course.com/books/math/3/hi/chapter/14-differentiation#ch-b1-derivative) देखिए)।

**अभ्यास 1.3 ★.**

प्रतिधनात्मकता द्वारा सिद्ध कीजिए: $x \in \R$ के लिए, यदि $x^3 + x \geq 2$ तो $x \geq 1$। फिर विरोधाभास द्वारा सिद्ध कीजिए: कोई लघुतम पूर्णतः धनात्मक वास्तविक संख्या नहीं है।

**हल — अभ्यास 1.3.**

*प्रतिधनात्मकता।* मान लीजिए $x < 1$। तब $x^3 < 1$ (घन फलन वर्धमान है) और $x < 1$, अतः $x^3 + x < 2$। इससे प्रतिधनात्मक [कथन](#def-b1-logic-statement) सिद्ध हो जाता है, और उसके साथ मूल [कथन](#def-b1-logic-statement) भी।

*विरोधाभास।* मान लीजिए $a > 0$ लघुतम पूर्णतः धनात्मक वास्तविक संख्या है। तब $a/2$ पूर्णतः धनात्मक है और $a/2 < a$ ($a > 0$ के कारण), जो लघुतमता का विरोध करता है। अतः ऐसा कोई $a$ नहीं है।

**अभ्यास 1.4 ★.**

आगमन द्वारा सिद्ध कीजिए कि सभी $n \in \N$ के लिए:

1. $\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$ ;
2. $4^n + 5$ $3$ से विभाज्य है।

**हल — अभ्यास 1.4.**

1. आधार स्थिति $n = 0$: $2^0 = 1 = 2^1 - 1$। पद: $n$ के लिए सर्वसमिका मानने पर, $$\sum_{k=0}^{n+1} 2^k = (2^{n+1} - 1) + 2^{n+1}  = 2 \cdot 2^{n+1} - 1 = 2^{n+2} - 1 .$$
2. आधार स्थिति $n = 0$: $4^0 + 5 = 6 = 3 \times 2$। पद: यदि $4^n + 5 =  3m$, तो $$4^{n+1} + 5 = 4(4^n + 5) - 15 = 3(4m - 5),$$ $3$ से विभाज्य

**अभ्यास 1.5 ★.**

निम्नलिखित “उपपत्ति” में दोष खोजिए, जो सिद्ध करती है कि सभी पेंसिलों का रंग एक ही है। *मान लीजिए $P(n)$: “$n$ पेंसिलों के प्रत्येक [समुच्चय](#def-b1-logic-sets) में सभी पेंसिलों का रंग एक ही है”। $P(1)$ स्पष्ट है। $P(n)$ मानकर $n+1$ पेंसिलें लीजिए; अंतिम पेंसिल हटाने पर पहली $n$ का रंग एक है; पहली पेंसिल हटाने पर अंतिम $n$ का रंग एक है; अतः सभी $n+1$ का रंग एक है।*

**हल — अभ्यास 1.5.**

आगमन पद चुपचाप यह मान लेता है कि दोनों समूह (“पहली $n$” और “अंतिम $n$”) अतिव्यापी हैं, जिससे साझा पेंसिलें रंग को एक समूह से दूसरे तक ले जाती हैं। $n + 1 = 2$ के लिए दोनों समूह $\{$पहली पेंसिल$\}$ और $\{$दूसरी पेंसिल$\}$ हैं: वे असंयुक्त हैं और तर्क टूट जाता है। अतः $P(1) \implies P(2)$ कभी सिद्ध ही नहीं हुआ और आगमन ढह जाता है — यद्यपि $P(n) \implies P(n+1)$ प्रत्येक $n
\geq 2$ के लिए वैध है।

**अभ्यास 1.6 ★.**

मान लीजिए $A, B, C$ $E$ के उपसमुच्चय हैं। सिद्ध कीजिए:

1. $A \setminus B = A \cap \overline{B}$ ;
2. $(A \cup B) \setminus C = (A \setminus C) \cup (B \setminus  C)$ ;
3. $A \subseteq B \iff A \cup B = B \iff A \cap B = A$ .

**हल — अभ्यास 1.6.**

1. $x \in A \setminus B \iff x \in A \land x \notin B \iff x \in  A \land x \in \overline{B} \iff x \in A \cap \overline{B}$ .
2. (1) और वितरणशीलता ( [प्रतिज्ञप्ति 1.18](#prop-b1-logic-setalgebra) ) का प्रयोग करते हुए: $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup (B \cap  \overline{C})$ ।
3. मान लीजिए $A \subseteq B$ । तब $A \cup B \subseteq B$ (दोनों टुकड़े $B$ में हैं) और $B \subseteq A \cup B$ सदा, अतः $A \cup B = B$ । मान लीजिए $A \cup B = B$ : तब $A \cap B \subseteq A$ सदा, और $A \subseteq A \cup B =  B$ से $A \subseteq A \cap B$ मिलता है, अतः $A \cap B = A$ । मान लीजिए $A  \cap B = A$ : तब $A = A \cap B \subseteq B$ । इस प्रकार तीनों शर्तें तुल्य हैं (हमने निहितार्थों का एक चक्र सिद्ध किया)।

**अभ्यास 1.7 ★★.**

प्रत्येक [प्रतिचित्रण](#def-b1-logic-map) के लिए (उपपत्ति सहित) तय कीजिए कि वह [एकैकी](#def-b1-logic-inj) है, [आच्छादक](#def-b1-logic-inj) है या [एकैकी आच्छादक](#def-b1-logic-inj):

1. $f \colon \N \to \N$ , $n \mapsto n + 1$ ;
2. $g \colon \Z \to \Z$ , $n \mapsto n + 1$ ;
3. $h \colon \R \setminus \{1\} \to \R$ , $x \mapsto  \frac{x+1}{x-1}$ .

$h$ के लिए सहप्रांत ऐसा समायोजित कीजिए कि वह [एकैकी आच्छादक](#def-b1-logic-inj) हो जाए, और प्रतिलोम की संगणना कीजिए।

**हल — अभ्यास 1.7.**

1. $f$ [एकैकी](#def-b1-logic-inj) है ( $n + 1 = m + 1 \implies n = m$ ) पर [आच्छादक](#def-b1-logic-inj) नहीं: $0$ का $\N$ में कोई [पूर्वप्रतिबिंब](#def-b1-logic-map) नहीं है।
2. $g$ [एकैकी आच्छादक](#def-b1-logic-inj) है: $n \mapsto n - 1$ $\Z$ पर द्विपक्षीय प्रतिलोम है।
3. $h$ [एकैकी](#def-b1-logic-inj) है: $\frac{x+1}{x-1} = \frac{x'+1}{x'-1}$ से $(x+1)(x'-1)  = (x'+1)(x-1)$ मिलता है, अर्थात् $xx' - x + x' - 1 = xx' - x' + x - 1$ , अतः $2x' = 2x$ । वह $\R$ पर [आच्छादक](#def-b1-logic-inj) नहीं है: $y = \frac{x+1}{x-1}$ हल करने पर $x(y - 1) = y + 1$ मिलता है, जिसका $y = 1$ होने पर कोई हल नहीं है (समीकरण $0 = 2$ हो जाता है)। सहप्रांत $\R \setminus \{1\}$ लेने पर वही संगणना अद्वितीय [पूर्वप्रतिबिंब](#def-b1-logic-map) $x = \frac{y+1}{y-1}$ देती है, अतः $h  \colon \R \setminus \{1\} \to \R \setminus \{1\}$ [एकैकी आच्छादक](#def-b1-logic-inj) है और $h^{-1}(y) = \frac{y+1}{y-1} = h(y)$ : $h$ अपना ही प्रतिलोम है।

**अभ्यास 1.8 ★★.**

मान लीजिए $f \colon E \to F$, तथा $A, A' \subseteq E$ और $B, B' \subseteq
F$।

1. सिद्ध कीजिए $f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')$ तथा $f(A  \cup A') = f(A) \cup f(A')$ ।
2. सिद्ध कीजिए $f(A \cap A') \subseteq f(A) \cap f(A')$ और ऐसा उदाहरण दीजिए जिसमें अंतर्विष्टि कठोर हो।
3. सिद्ध कीजिए: $f$ [एकैकी](#def-b1-logic-inj) है यदि और केवल यदि सभी $A, A'$ के लिए $f(A  \cap A') = f(A) \cap f(A')$ ।

**हल — अभ्यास 1.8.**

1. $x \in f^{-1}(B \cap B') \iff f(x) \in B \cap B' \iff f(x) \in B  \land f(x) \in B' \iff x \in f^{-1}(B) \cap f^{-1}(B')$ । प्रतिबिंबों के लिए: $y \in f(A \cup A')$ तभी जब $A$ या $A'$ के किसी $x$ के लिए $y =  f(x)$ , अर्थात् तभी जब $y \in f(A)$ या $y \in f(A')$ ।
2. यदि $y \in f(A \cap A')$ , तो $y = f(x)$ , जहाँ $x \in A$ और $x \in  A'$ , अतः $y \in f(A)$ और $y \in f(A')$ । कठोरता: $f \colon \R \to \R$ , $x  \mapsto x^2$ , $A = \{-1\}$ , $A' = \{1\}$ लीजिए: तब $f(A \cap A') =  f(\emptyset) = \emptyset$ , पर $f(A) \cap f(A') = \{1\}$ ।
3. ( $\Leftarrow$ ) $A = \{x\}$ लेने पर, $x \neq x'$ के लिए $A' =  \{x'\}$ : यदि $f(x) = f(x')$ , तो $f(A) \cap f(A') = \{f(x)\}$ जबकि $f(A  \cap A') = \emptyset$ , जो मानी हुई समता का विरोध करता है; अतः $f$ [एकैकी](#def-b1-logic-inj) है। ( $\Rightarrow$ ) मान लीजिए $f$ [एकैकी](#def-b1-logic-inj) है और $y \in f(A) \cap f(A')$ : $y  = f(x) = f(x')$ , जहाँ $x \in A$ , $x' \in A'$ ; एकैकीयता से $x = x' \in A  \cap A'$ मिलता है, अतः $y \in f(A \cap A')$ । (2) के साथ मिलाकर समता सिद्ध होती है।

**अभ्यास 1.9 ★★.**

मान लीजिए $f \colon E \to F$ और $g \colon F \to E$ $g \circ f =
\mathrm{id}_E$ को संतुष्ट करते हैं। सिद्ध कीजिए कि $f$ [एकैकी](#def-b1-logic-inj) है और $g$ [आच्छादक](#def-b1-logic-inj) है। ऐसा उदाहरण दीजिए जिसमें $f$ और $g$ में से कोई भी [एकैकी आच्छादक](#def-b1-logic-inj) न हो।

**हल — अभ्यास 1.9.**

$g \circ f = \mathrm{id}_E$ [एकैकी](#def-b1-logic-inj) और [आच्छादक](#def-b1-logic-inj) है, अतः [प्रतिज्ञप्ति 1.26](#prop-b1-logic-comp) (2) से $f$ [एकैकी](#def-b1-logic-inj) है और $g$ [आच्छादक](#def-b1-logic-inj) है। उदाहरण: $E
= \N$, $F = \Z$, $f$ अंतर्विष्टि $n \mapsto n$, तथा $g \colon \Z \to \N$, $n
\geq 0$ के लिए $g(n) = n$ और $n < 0$ के लिए $g(n) = 0$। तब सभी $n \in \N$ के लिए $g(f(n)) = n$, पर $f$ [आच्छादक](#def-b1-logic-inj) नहीं है और $g$ [एकैकी](#def-b1-logic-inj) नहीं है।

**अभ्यास 1.10 ★★.**

$\R$ पर $x \mathbin{\mathcal{R}} y \iff x^2 - y^2 = x - y$ परिभाषित कीजिए। सिद्ध कीजिए कि $\mathcal{R}$ एक [तुल्यता संबंध](#def-b1-logic-equiv) है और प्रत्येक वास्तविक $x$ के [तुल्यता वर्ग](#def-b1-logic-equiv) का वर्णन कीजिए। किन वर्गों में ठीक एक अवयव है?

**हल — अभ्यास 1.10.**

$x^2 - y^2 = x - y \iff (x - y)(x + y) = x - y \iff (x - y)(x + y - 1) = 0
\iff y = x$ या $y = 1 - x$। *स्वतुल्य:* $y = x$ काम करता है। *सममित:* शर्त “$y = x$ या $y = 1 - x$” $x$ और $y$ में सममित है (यदि $y = 1 - x$, तो $x = 1 - y$)। *संक्रमक:* मान लीजिए $x
\mathbin{\mathcal{R}} y$ और $y \mathbin{\mathcal{R}} z$; चारों स्थितियों से गुज़रने पर $z$ हर बार $x$ या $1 - x$ के बराबर निकलता है (उदाहरणार्थ $y = 1 -
x$ और $z = 1 - y$ से $z = x$ मिलता है)। अतः $\mathcal{R}$ एक [तुल्यता संबंध](#def-b1-logic-equiv) है और $\mathrm{cl}(x) = \{x,\, 1 - x\}$। इस वर्ग में ठीक एक अवयव तभी है जब $x = 1 - x$, अर्थात् $x = \frac12$ के लिए।

**अभ्यास 1.11 ★★★.**

(कैंटर) मान लीजिए $E$ एक [समुच्चय](#def-b1-logic-sets) है। सिद्ध कीजिए कि $E$ से $\mathcal{P}(E)$ पर कोई आच्छादन नहीं है। *संकेत: $f \colon E \to \mathcal{P}(E)$ दिया हो, तो $D = \{x \in E : x \notin f(x)\}$ पर विचार कीजिए।*

**हल — अभ्यास 1.11.**

मान लीजिए $f \colon E \to \mathcal{P}(E)$ कोई [प्रतिचित्रण](#def-b1-logic-map) है और $D = \{x \in
E : x \notin f(x)\} \in \mathcal{P}(E)$ रखिए। मान लीजिए किसी $a \in E$ के लिए $D = f(a)$। यदि $a \in D$, तो $D$ की परिभाषा से $a \notin f(a) = D$: विरोधाभास। यदि $a \notin D$, तो $a \notin f(a)$, अतः $D$ की परिभाषा से $a
\in D$: विरोधाभास। अतः $D$ $f$ के प्रतिबिंब में नहीं है, और $f$ [आच्छादक](#def-b1-logic-inj) नहीं है। (विशेष रूप से, कोई भी [समुच्चय](#def-b1-logic-sets) अपने [घात समुच्चय](#def-b1-logic-sets) के साथ एकैकी आच्छादन में नहीं है: $\N$ के उपसमुच्चय पूर्णांकों से “अधिक” हैं।)

**अभ्यास 1.12 ★★★.**

मान लीजिए $f \colon E \to F$ एक [प्रतिचित्रण](#def-b1-logic-map) है। $\Phi \colon \mathcal{P}(F)
\to \mathcal{P}(E)$ को $\Phi(B) = f^{-1}(B)$ द्वारा परिभाषित कीजिए।

1. सिद्ध कीजिए कि $f$ [आच्छादक](#def-b1-logic-inj) है यदि और केवल यदि $\Phi$ [एकैकी](#def-b1-logic-inj) है।
2. सिद्ध कीजिए कि $f$ [एकैकी](#def-b1-logic-inj) है यदि और केवल यदि $\Phi$ [आच्छादक](#def-b1-logic-inj) है।

**हल — अभ्यास 1.12.**

1. ( $\Rightarrow$ ) मान लीजिए $f$ [आच्छादक](#def-b1-logic-inj) है और $\Phi(B) = \Phi(B')$ । $y  \in B$ के लिए ऐसा $x$ चुनिए कि $f(x) = y$ ; तब $x \in f^{-1}(B) =  f^{-1}(B')$ , अतः $y = f(x) \in B'$ । अतः $B \subseteq B'$ , और सममित रूप से $B' \subseteq B$ : $\Phi$ [एकैकी](#def-b1-logic-inj) है। ( $\Leftarrow$ ) यदि $f$ [आच्छादक](#def-b1-logic-inj) नहीं है, तो प्रतिबिंब के बाहर कोई $y_0 \in F$ चुनिए; तब $f^{-1}(\{y_0\}) =  \emptyset = f^{-1}(\emptyset)$ , जहाँ $\{y_0\} \neq \emptyset$ , अतः $\Phi$ [एकैकी](#def-b1-logic-inj) नहीं है।
2. ( $\Rightarrow$ ) मान लीजिए $f$ [एकैकी](#def-b1-logic-inj) है और $A \subseteq E$ । $B =  f(A)$ रखिए; तब $f^{-1}(B) = \{x : f(x) \in f(A)\}$ , और एकैकीयता से $f(x)  \in f(A) \iff x \in A$ मिलता है, अतः $\Phi(B) = A$ : $\Phi$ [आच्छादक](#def-b1-logic-inj) है। ( $\Leftarrow$ ) यदि $f$ [एकैकी](#def-b1-logic-inj) नहीं है, तो $x \neq x'$ ऐसा लीजिए कि $f(x) =  f(x')$ । प्रत्येक [पूर्वप्रतिबिंब](#def-b1-logic-map) [समुच्चय](#def-b1-logic-sets) $f^{-1}(B)$ $x$ को तभी समेटता है जब वह $x'$ को समेटता हो; अतः $\{x\}$ $\Phi(B)$ के रूप का नहीं है, और $\Phi$ [आच्छादक](#def-b1-logic-inj) नहीं है।

## 1.8 समस्या: अनंतताओं की तुलना

**समस्या 1.1.**

दो समुच्चयों में “अवयवों की संख्या समान” कब होती है? कैंटर का उत्तर — जब उनके बीच एकैकी आच्छादन हो — अनंत समुच्चयों के लिए भी प्रयोग करने योग्य निकलता है, और वह अनंत को सचमुच भिन्न आकारों में बाँट देता है। यह समस्या इस अध्याय की सादी परिभाषाओं से पूरा औज़ार-संदूक खड़ा करती है: कैंटर–श्रोडर–बर्नस्टाइन प्रमेय (दो [एकैकी](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) मिलकर एक एकैकी आच्छादन गढ़ देते हैं), $\Q$ की गणनीयता, विकर्ण तर्क द्वारा $\R$ की अगणनीयता, और कैंटर का 1874 का चकित करने वाला निष्कर्ष: *अबीजीय संख्याएँ विद्यमान हैं, और वे प्रचुर मात्रा में हैं* — बिना एक भी संख्या प्रस्तुत किए। आगे सर्वत्र, समुच्चयों $E$ और $F$ के लिए $E \preceq F$ तब लिखिए जब $E$ से $F$ में कोई [एकैकी](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) हो, और $E \approx F$ (“$E$ और $F$ *समशक्त* हैं”) तब जब $E$ से $F$ पर कोई एकैकी आच्छादन हो।

**भाग I — तुलना की शब्दावली।**

1. दिखाइए कि $\approx$ [तुल्यता संबंध](#def-b1-logic-equiv) की भाँति व्यवहार करता है: $E  \approx E$ ; यदि $E \approx F$ तो $F \approx E$ ; यदि $E \approx F$ और $F  \approx G$ तो $E \approx G$ । ( [प्रमेय 1.24](#thm-b1-logic-inverse) और [प्रतिज्ञप्ति 1.26](#prop-b1-logic-comp) को ठीक-ठीक उद्धृत कीजिए।)
2. दिखाइए कि $\preceq$ संक्रमक है, और यह कि [एकैकी](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) $f \colon  E \to F$ सदा $E \approx f(E)$ प्रेरित करता है।
3. मान लीजिए $E \neq \emptyset$ । दिखाइए कि $E \preceq F$ यदि और केवल यदि $F$ से $E$ पर कोई आच्छादन विद्यमान हो।
4. सत्यापित कीजिए कि $n \mapsto n + 1$ $\N$ से $\N^* = \N \setminus  \{0\}$ पर एकैकी आच्छादन है, और यह कि $$\sigma(n) = \frac n2 \ \ (n \text{ सम}), \qquad  \sigma(n) = -\frac{n+1}2 \ \ (n \text{ विषम})$$ $\N$ से $\Z$ पर एकैकी आच्छादन है। अतः एक बिंदु हटा देने से, या ऋणात्मक पक्ष में दुगुना कर देने से, $\N$ का आकार नहीं बदलता।

**भाग II — कैंटर–श्रोडर–बर्नस्टाइन प्रमेय।** मान लीजिए $f \colon E \to F$ और $g \colon F \to E$ दो [एकैकी](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) हैं। परिभाषित कीजिए

$$
C_0 = E \setminus g(F), \qquad C_{n+1} = g\bigl(f(C_n)\bigr)
\ \ (n \in \N), \qquad C = \bigcup_{n \in \N} C_n,
$$

और मान लीजिए $h \colon E \to F$ $x \in C$ को $f(x)$ पर भेजता है तथा $x
\notin C$ को उस अद्वितीय $y \in F$ पर जिसके लिए $g(y) = x$।

5. जाँचिए कि $h$ सुपरिभाषित है: यदि $x \notin C$ , तो $x \in g(F)$ , और $g(y) = x$ वाला अवयव $y$ अद्वितीय है।
6. दिखाइए कि $g\bigl(f(C)\bigr) = \bigcup_{n \geq 1} C_n \subseteq C$ । (अग्र प्रतिबिंब सम्मिलन के साथ क्रम-विनिमेय हैं: [अभ्यास 1.8](#exo-b1-logic-8) ।)
7. दिखाइए कि $h$ [एकैकी](#def-b1-logic-inj) है। (तीन स्थितियाँ; मिश्रित स्थिति $x \in C$ , $x' \notin C$ में दिखाइए कि $h(x) = h(x')$ होने पर $x' \in g(f(C))  \subseteq C$ मानना पड़ेगा।)
8. दिखाइए कि $h$ [आच्छादक](#def-b1-logic-inj) है: $y \in F$ दिया हो, तो $g(y) \notin C$ और किसी $n \geq 1$ के लिए $g(y) \in C_n$ — इन दोनों स्थितियों में भेद कीजिए ( $g(y) \in C_0$ असंभव क्यों है?) — और हर स्थिति में $y$ का एक [पूर्वप्रतिबिंब](#def-b1-logic-map) प्रस्तुत कीजिए।
9. *कैंटर–श्रोडर–बर्नस्टाइन प्रमेय* के साथ निष्कर्ष निकालिए: यदि $E \preceq F$ और $F \preceq E$ , तो $E \approx F$ । एक वाक्य में टिप्पणी कीजिए कि इस [कथन](#def-b1-logic-statement) को अतुच्छ क्या बनाता है।
10. दो अनुप्रयोग। (क) दिखाइए $\intcc01 \approx \intoo01$ । (ख) दिखाइए कि $\varphi(p, q) = 2^p(2q + 1) - 1$ $\N \times \N$ से $\N$ पर एकैकी आच्छादन परिभाषित करता है — एकैकीयता सम-विषम तर्क से, आच्छादकता प्रबल आगमन ( [प्रमेय 1.12](#thm-b1-logic-induction) ) से। अतः $\N \times \N \approx \N$ : पूर्णांक बिंदुओं का समतल रेखा से बड़ा नहीं है।

**भाग III — [गणनीय समुच्चय](#pb-b1-logic-1)।** [समुच्चय](#def-b1-logic-sets) $E$ को *अधिकतम गणनीय* तब कहिए जब $E \preceq \N$, और *गणनीय* तब जब $E
\approx \N$।

11. दिखाइए कि $A \subseteq \N$ जैसा प्रत्येक अनंत उपसमुच्चय गणनीय है। ( $\varphi(n)$ को पुनरावर्ती रूप से $A \setminus \{\varphi(0), \dots,  \varphi(n-1)\}$ के न्यूनतम अवयव के रूप में परिभाषित कीजिए; दिखाइए कि $\varphi$ पूर्णतः वर्धमान है, $\varphi(n) \geq n$ को संतुष्ट करता है, और $A$ के प्रत्येक अवयव तक पहुँचता है।)
12. इससे निकालिए कि कोई [समुच्चय](#def-b1-logic-sets) अधिकतम गणनीय है यदि और केवल यदि वह परिमित या गणनीय हो, और देखिए कि प्रश्न 9 यह संक्षेप देता है: यदि $E  \preceq \N$ और $\N \preceq E$ , तो $E$ गणनीय है।
13. दिखाइए कि यदि $E$ और $F$ अधिकतम गणनीय हैं, तो $E \times F$ भी है। इससे निकालिए कि $\Z \times \N^*$ गणनीय है।
14. दिखाइए कि $\Q$ गणनीय है। (प्रत्येक परिमेय संख्या को धनात्मक हर के साथ न्यूनतम पदों में लिखकर $\Q$ को $\Z \times \N^*$ में [एकैकी](#def-b1-logic-inj) रूप से भेजिए — उस निरूपण की अद्वितीयता [अध्याय 6](https://one-course.com/books/math/3/hi/chapter/6-integer-arithmetic#ch-b1-arith) में सिद्ध है; फिर प्रश्न 12 लगाइए।)
15. दिखाइए कि अधिकतम गणनीय समुच्चयों का गणनीय सम्मिलन अधिकतम गणनीय होता है: यदि प्रत्येक $E_n$ ( $n \in \N$ ) अधिकतम गणनीय है, तो $\bigcup_{n \in  \N} E_n$ भी है। ( $x$ को युग्म $(n, f_n(x))$ पर भेजिए, जहाँ $n$ $x \in E_n$ वाला *न्यूनतम* सूचकांक है।)
16. दिखाइए कि $\N$ के *परिमित* उपसमुच्चयों का [समुच्चय](#def-b1-logic-sets) गणनीय है। (किसी परिमित उपसमुच्चय $F$ को $\sum_{i \in F} 2^i$ पर भेजिए; एकैकीयता के लिए उस बृहत्तम अवयव की तुलना कीजिए जहाँ दो परिमित [समुच्चय](#def-b1-logic-sets) भिन्न होते हैं, और [अभ्यास 1.4](#exo-b1-logic-4) का $\sum_{k=0}^{m-1} 2^k = 2^m - 1$ प्रयोग कीजिए।)

**भाग IV — विकर्णीकरण।** मान लीजिए $\{0,1\}^{\N}$ सभी प्रतिचित्रणों $u \colon \N \to \{0, 1\}$ का [समुच्चय](#def-b1-logic-sets) है, अर्थात् द्विआधारी अनुक्रमों का [समुच्चय](#def-b1-logic-sets)।

17. $\mathcal{P}(\N)$ और $\{0,1\}^{\N}$ के बीच एकैकी आच्छादन की रचना कीजिए (सूचक फलन)।
18. (विकर्ण तर्क) मान लीजिए $\Phi \colon \N \to \{0,1\}^{\N}$ कोई [प्रतिचित्रण](#def-b1-logic-map) है। $d(n) = 1 - \Phi(n)(n)$ से परिभाषित अनुक्रम $d$ पर विचार कीजिए। दिखाइए कि $d$ $\Phi$ के प्रतिबिंब में नहीं है, और निष्कर्ष निकालिए कि $\{0,1\}^{\N}$ अधिकतम गणनीय *नहीं* है। एक वाक्य में समझाइए कि प्रश्न 17 के रास्ते यह ठीक $E = \N$ के लिए कैंटर की प्रमेय ( [अभ्यास 1.11](#exo-b1-logic-11) ) क्यों है।
19. यह मान लीजिए — जो विद्यालय से परिचित है और [अध्याय 10](https://one-course.com/books/math/3/hi/chapter/10-real-numbers#ch-b1-reals) में कठोरता से स्थापित है — कि प्रत्येक $x \in \intco01$ का अद्वितीय *उचित* दशमलव प्रसार $x = 0.d_1 d_2 d_3\dots$ होता है (जो $9$ की अनंत माला पर समाप्त न होता हो)। $\intco01$ के अवयवों का कोई भी अनुक्रम $(x_n)_{n \geq 1}$ दिया हो, तो ऐसा $x \in \intco01$ रचिए कि सभी $n$ के लिए $x \neq x_n$ : उसका $n$ -वाँ अंक $5$ चुनिए यदि $x_n$ का $n$ -वाँ अंक $5$ से भिन्न हो, अन्यथा $6$ । सावधानी से न्यायसंगत कीजिए कि $x$ उचित है और प्रत्येक $x_n$ से बचता है, और निष्कर्ष निकालिए कि $\intco01$ अधिकतम गणनीय नहीं है।
20. इससे निकालिए कि $\R$ अगणनीय है, और यह कि अपरिमेय संख्याओं का [समुच्चय](#def-b1-logic-sets) $\R \setminus \Q$ भी अगणनीय है। किस सुनिश्चित अर्थ में “अधिकांश” वास्तविक संख्याएँ अपरिमेय हैं?

**भाग V — कैंटर की 1874 की प्रमेय: अबीजीय संख्याएँ विद्यमान हैं।** वास्तविक संख्या $x$ *बीजीय* तब कहलाती है जब पूर्णांक गुणांकों वाले किसी अशून्य बहुपद $P$ के लिए $P(x) = 0$ हो, और अन्यथा *अबीजीय*। इस भाग के लिए यह मान लीजिए — [अध्याय 8](https://one-course.com/books/math/3/hi/chapter/8-polynomials#ch-b1-poly) में यह सिद्ध है — कि घात $n$ के अशून्य बहुपद के अधिक से अधिक $n$ वास्तविक मूल होते हैं।

21. दिखाइए कि प्रत्येक परिमेय संख्या बीजीय है, और $\sqrt 2$ तथा $\sqrt 2  + \sqrt 3$ का विलोपन करने वाले पूर्णांक गुणांकों के स्पष्ट बहुपद खोजिए।
22. नियत $n \in \N$ के लिए दिखाइए कि पूर्णांक गुणांकों वाले, अधिकतम घात $n$ के बहुपदों का [समुच्चय](#def-b1-logic-sets) गणनीय है। (उसे $\Z^{n+1}$ में [एकैकी](#def-b1-logic-inj) रूप से भेजिए और प्रश्न 13 के साथ $n$ पर आगमन कीजिए।)
23. इससे निकालिए कि पूर्णांक गुणांकों वाले *सभी* बहुपदों का [समुच्चय](#def-b1-logic-sets) गणनीय है।
24. *बीजीय संख्याओं पर कैंटर की प्रमेय* सिद्ध कीजिए: बीजीय वास्तविक संख्याओं का [समुच्चय](#def-b1-logic-sets) $\mathcal{A}$ गणनीय है।
25. निष्कर्ष निकालिए: अबीजीय वास्तविक संख्याएँ विद्यमान हैं, और अबीजीय संख्याओं का [समुच्चय](#def-b1-logic-sets) अगणनीय है। फिर कुछ वाक्यों में पूरी समस्या का लेखा-जोखा लीजिए: शृंखला $\N \approx \Z \approx \Q \approx \mathcal{A}$ , $\R \approx$ तक की कठोर छलाँग, जो (मूलतः) $\mathcal{P}(\N)$ है, कहाँ कौन-सा औज़ार (कैंटर–श्रोडर–बर्नस्टाइन, गणनीय सम्मिलन, विकर्ण) निर्णायक रहा — और यह सिद्ध करने का दार्शनिक प्रहार कि अगणनीय रूप से अनेक अबीजीय संख्याएँ विद्यमान हैं, बिना एक का भी नाम लिए। (किसी *विशिष्ट* संख्या, जैसे $\pi$ , का अबीजीय होना सिद्ध करना कहीं कठिन है और इस खंड की सीमा से परे।)

**हल — समस्या 1.1.**

**1.** *स्वतुल्य:* $\mathrm{id}_E$ $E$ का स्वयं पर एकैकी आच्छादन है। *सममित:* यदि $f \colon E \to F$ [एकैकी आच्छादक](#def-b1-logic-inj) है, तो [प्रमेय 1.24](#thm-b1-logic-inverse) $f^{-1} \colon F \to E$ देता है, जो स्वयं [एकैकी आच्छादक](#def-b1-logic-inj) है। *संक्रमक:* यदि $f \colon E \to F$ और $g \colon F \to G$ एकैकी आच्छादन हैं, तो [प्रतिज्ञप्ति 1.26](#prop-b1-logic-comp) (1) कहता है कि $g \circ f
\colon E \to G$ एकैकी आच्छादन है। (यह केवल [तुल्यता संबंध](#def-b1-logic-equiv) “की भाँति” है: सभी समुच्चयों का संग्रह स्वयं [समुच्चय](#def-b1-logic-sets) नहीं है — उन्हीं विरोधाभासों के कारण जिनकी ओर [अभ्यास 1.11](#exo-b1-logic-11) संकेत करता है; महत्त्व तीनों गुणधर्मों का है।)

**2.** यदि $f \colon E \to F$ और $g \colon F \to G$ [एकैकी](#def-b1-logic-inj) हैं, तो [प्रतिज्ञप्ति 1.26](#prop-b1-logic-comp) (1) से $g \circ f$ [एकैकी](#def-b1-logic-inj) है: $E \preceq G$। दूसरे बिंदु के लिए $f$ को उसके प्रतिबिंब तक सहसीमित कीजिए: [प्रतिचित्रण](#def-b1-logic-map) $\tilde f
\colon E \to f(E)$, $x \mapsto f(x)$, $f(E)$ की रचना से [आच्छादक](#def-b1-logic-inj) है और $f$ के [एकैकी](#def-b1-logic-inj) होने से [एकैकी](#def-b1-logic-inj), अतः [एकैकी आच्छादक](#def-b1-logic-inj): $E \approx f(E)$।

**3.** ($\Rightarrow$) मान लीजिए $f \colon E \to F$ [एकैकी](#def-b1-logic-inj) है और $a \in
E$ ($E \neq \emptyset$) नियत कीजिए। $s \colon F \to E$ इस प्रकार परिभाषित कीजिए: $y \in f(E)$ होने पर $s(y)$ वह अद्वितीय $x$ है जिसके लिए $f(x) = y$ (अद्वितीयता एकैकीयता से), और अन्यथा $s(y) = a$। प्रत्येक $x \in E$ के लिए $s(f(x)) = x$, अतः प्रत्येक $x$ प्राप्त होता है: $s$ [आच्छादक](#def-b1-logic-inj) है। ($\Leftarrow$) मान लीजिए $s \colon F \to E$ [आच्छादक](#def-b1-logic-inj) है। प्रत्येक $x \in E$ के लिए ऐसा एक $y_x \in F$ चुनिए कि $s(y_x) = x$, और $u(x) = y_x$ रखिए। यदि $u(x) = u(x')$, तो $x = s(u(x)) = s(u(x')) = x'$: $u \colon E \to F$ [एकैकी](#def-b1-logic-inj) है।

**4.** $n \mapsto n + 1$ $\N$ को $\N^*$ में भेजता है, [एकैकी](#def-b1-logic-inj) है ($n + 1
= m + 1 \implies n = m$) और [आच्छादक](#def-b1-logic-inj) है (प्रत्येक $m \geq 1$ $m - 1 \in \N$ के साथ $(m - 1) + 1$ है)। $\sigma$ के लिए: वह सम संख्याओं $0, 2, 4, \dots$ को $0, 1, 2, \dots$ पर और विषम संख्याओं $1, 3, 5, \dots$ को $-1, -2, -3,
\dots$ पर भेजता है। एकैकीयता: सम निवेश $\N$ में गिरते हैं ($\sigma(n) = n/2
\geq 0$) और विषम निवेश पूर्णतः ऋणात्मक पूर्णांकों में ($\sigma(n) = -(n+1)/2
\leq -1$), अतः टक्कर एक ही सम-विषम वर्ग के भीतर ही हो सकती है, जहाँ $\sigma$ पूर्णतः एकदिष्ट है ($n/2 = m/2$ या $(n+1)/2 = (m+1)/2$ से $n = m$ आ जाता है)। आच्छादकता: $k \geq 0$ $\sigma(2k)$ है; $k \leq -1$ $\sigma(-2k - 1)$ है, जहाँ $-2k - 1 \geq 1$ विषम है। अतः $\N \approx \N^*$ और $\N \approx \Z$।

**5.** $C_0 = E \setminus g(F) \subseteq C$, अतः $x \notin C$ से $x
\notin C_0$ आता है, अर्थात् $x \in g(F)$: कोई $y \in F$ $g(y) = x$ को संतुष्ट करता है। यदि $g(y') = x$ भी हो, तो $g$ की एकैकीयता से $y' = y$। अतः $h$ की परिभाषा का दूसरा उपवाक्य एक अद्वितीय, सुपरिभाषित अवयव $g^{-1}(x)$ चुन लेता है।

**6.** अग्र प्रतिबिंब सम्मिलन के साथ क्रम-विनिमेय हैं ([अभ्यास 1.8](#exo-b1-logic-8) (1), पहले $f$ पर, फिर $g$ पर लगाकर):

$$
g\bigl(f(C)\bigr)
= g\Bigl(f\Bigl(\bigcup_{n \in \N} C_n\Bigr)\Bigr)
= \bigcup_{n \in \N} g\bigl(f(C_n)\bigr)
= \bigcup_{n \in \N} C_{n+1}
= \bigcup_{n \geq 1} C_n \subseteq C .
$$

**7.** मान लीजिए $E$ में $x \neq x'$। यदि दोनों $C$ में हों, तो $f$ की एकैकीयता से $h(x) = f(x) \neq f(x') = h(x')$। यदि कोई भी $C$ में न हो, तो $g(h(x)) = x \neq x' = g(h(x'))$, अतः $h(x) \neq h(x')$। यदि $x \in C$ और $x' \notin C$ (मिश्रित स्थिति, नाम बदलने तक): मान लीजिए $h(x) = h(x')$, अर्थात् $f(x) = g^{-1}(x')$। $g$ लगाने पर $x' = g(f(x)) \in g(f(C))$, और प्रश्न 6 से $x' \in C$ मिलता है — विरोधाभास। अतः सभी स्थितियों में $h(x)
\neq h(x')$: $h$ [एकैकी](#def-b1-logic-inj) है।

**8.** मान लीजिए $y \in F$। *स्थिति 1: $g(y) \notin C$।* तब $h(g(y)) = g^{-1}(g(y)) = y$: अवयव $g(y)$ एक [पूर्वप्रतिबिंब](#def-b1-logic-map) है। *स्थिति 2: $g(y) \in C$*, मान लीजिए $g(y) \in C_n$। चूँकि $g(y) \in g(F)$, अतः $g(y)
\notin C_0 = E \setminus g(F)$, इसलिए $n \geq 1$ और $g(y) \in C_n =
g(f(C_{n-1}))$: ऐसा $x \in C_{n-1}$ है कि $g(y) = g(f(x))$। $g$ की एकैकीयता से $y = f(x)$ मिलता है, और $x \in C_{n-1} \subseteq C$, अतः $h(x) = f(x) =
y$। दोनों स्थितियों में $y$ प्राप्त हो जाता है: $h$ [आच्छादक](#def-b1-logic-inj) है, अतः [एकैकी आच्छादक](#def-b1-logic-inj)।

**9.** यदि $E \preceq F$ और $F \preceq E$, तो [एकैकी](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) $f
\colon E \to F$ और $g \colon F \to E$ चुनिए; प्रश्न 5–8 एक एकैकी आच्छादन $h
\colon E \to F$ गढ़ देते हैं, अतः $E \approx F$। यह [कथन](#def-b1-logic-statement) इसलिए अतुच्छ है कि दिए हुए दोनों [एकैकी](#def-b1-logic-inj) प्रतिचित्रणों का आपस में कोई संबंध नहीं है — किसी का [आच्छादक](#def-b1-logic-inj) होना आवश्यक नहीं, और $f$ तथा $g$ को भोलेपन से मिलाने वाला कोई सूत्र [प्रतिचित्रण](#def-b1-logic-map) नहीं देता: सारी सामग्री $E$ के उस [विभाजन](#thm-b1-logic-partition) में है जो उसे क्षेत्र $C$ (जहाँ $f$ की नकल की जाती है) और उसके पूरक (जहाँ $g$ को उलटी दिशा में चलाया जाता है) में बाँटता है।

**10.** (क) अंतर्विष्टि $\intoo01 \to \intcc01$ [एकैकी](#def-b1-logic-inj) है; और $x \mapsto
\frac{x + 1}3$ $\intcc01$ को $\intcc{\frac13}{\frac23} \subseteq \intoo01$ में [एकैकी](#def-b1-logic-inj) रूप से भेजता है (वह अशून्य प्रवणता वाला ऐफ़ीन फलन है)। प्रश्न 9 से $\intcc01 \approx \intoo01$ — ऐसा एकैकी आच्छादन जिसे स्पष्ट रूप से लिखना काफ़ी अप्रिय है। (ख) *एकैकीयता।* मान लीजिए $2^p(2q + 1) = 2^{p'}(2q' +
1)$, जहाँ मान लीजिए $p \leq p'$। $2^p$ से भाग देने पर $2q + 1 = 2^{p' -
p}(2q' + 1)$। यदि $p' > p$, तो दायाँ पक्ष सम और बायाँ विषम होगा — असंभव; अतः $p = p'$, फिर $2q + 1 = 2q' + 1$ और $q = q'$। *आच्छादकता।* प्रबल आगमन से दिखाते हैं कि प्रत्येक पूर्णांक $m \geq 1$ $2^p(2q + 1)$ के रूप का है। $m = 1$ के लिए: $p = q = 0$। मान लीजिए $m \geq 1$ और $\intint1m$ के सभी पूर्णांकों के लिए दावा मान लीजिए। यदि $m + 1$ विषम है, तो $m + 1 = 2q + 1$, जहाँ $p = 0$। यदि $m + 1$ सम है, तो $m + 1 = 2m'$, जहाँ $1 \leq m' \leq m$; परिकल्पना से $m' = 2^p(2q + 1)$, अतः $m + 1 = 2^{p+1}(2q + 1)$। अतः $\varphi(p, q) = 2^p(2q + 1) - 1$ प्रत्येक $n \in \N$ तक पहुँचता है, और $\varphi$ एकैकी आच्छादन $\N \times \N \to \N$ है।

**11.** चूँकि $A$ अनंत है, $A \setminus \{\varphi(0), \dots, \varphi(n
- 1)\}$ कभी रिक्त नहीं होता, और $\N$ का न्यूनतम-अवयव गुणधर्म (जिससे [प्रमेय 1.12](#thm-b1-logic-induction) सिद्ध किया गया था) इस पुनरावर्ती परिभाषा को वैध बना देता है। *पूर्णतः वर्धमान:* $\varphi(n + 1)$ $A \setminus
\{\varphi(0), \dots, \varphi(n)\} \subseteq A \setminus \{\varphi(0), \dots,
\varphi(n - 1)\}$ का सदस्य है, जिसका न्यूनतम $\varphi(n)$ है; अतः $\varphi(n
+ 1) \geq \varphi(n)$, और समता संभव नहीं, जिससे $\varphi(n+1) > \varphi(n)$। *$\varphi(n) \geq n$:* आगमन से $\varphi(0) \geq 0$, और $\varphi(n + 1)
\geq \varphi(n) + 1 \geq n + 1$। *एकैकीयता* कठोर एकदिष्टता से निकलती है। *$A$ पर आच्छादकता:* मान लीजिए कोई $a \in A$ कभी प्राप्त नहीं होता। चूँकि $\varphi(a + 1) \geq a + 1 > a$, अतः $\varphi(n) > a$ वाले $n$ का [समुच्चय](#def-b1-logic-sets) अरिक्त है; मान लीजिए $n$ उसका न्यूनतम अवयव है। प्रत्येक $k < n$ के लिए $\varphi(k) \leq a$, अतः $\varphi(k) < a$ ($a$ प्राप्त नहीं होता)। तब $a$ $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ में है और $a <
\varphi(n)$, जो $\varphi(n)$ को परिभाषित करने वाली लघुतमता का विरोध करता है। अतः $\varphi$ एकैकी आच्छादन $\N \to A$ है, और $A$ गणनीय है।

**12.** मान लीजिए [एकैकी](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) $f$ के द्वारा $E \preceq \N$; तब $E
\approx f(E)$ (प्रश्न 2)। यदि $f(E)$ परिमित है, तो $E$ परिमित है; यदि $f(E)$ अनंत है, तो प्रश्न 11 से $f(E) \approx \N$ मिलता है, अतः संक्रमकता (प्रश्न 1) से $E \approx \N$। विलोमतः, परिमित [समुच्चय](#def-b1-logic-sets) और [गणनीय समुच्चय](#pb-b1-logic-1) स्पष्टतः $\N$ में [एकैकी](#def-b1-logic-inj) रूप से समा जाते हैं। संक्षेप: $E \preceq \N$ और $\N \preceq E$ से कैंटर–श्रोडर–बर्नस्टाइन द्वारा सीधे $E \approx \N$ मिल जाता है — किसी गणना-तर्क की आवश्यकता नहीं।

**13.** मान लीजिए $f \colon E \to \N$ और $g \colon F \to \N$ [एकैकी](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) हैं। तब $(x, y) \mapsto \varphi\bigl(f(x), g(y)\bigr)$ एक [एकैकी](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) $E \times F \to \N$ है: यदि प्रतिबिंब मेल खाएँ, तो $\varphi$ (प्रश्न 10) की एकैकीयता से $f(x) = f(x')$ और $g(y) = g(y')$ मिलते हैं, फिर $x = x'$, $y = y'$। $\Z \times \N^*$ के लिए: दोनों गुणनखंड गणनीय हैं (प्रश्न 4), अतः $\Z \times \N^* \preceq \N$; वह अनंत है (उसमें $\{0\} \times \N^*$ है), अतः प्रश्न 12 से गणनीय है।

**14.** प्रत्येक परिमेय $r$ का अद्वितीय निरूपण $r = p/q$ है, जहाँ $p
\in \Z$, $q \in \N^*$ और भिन्न न्यूनतम पदों में है (अद्वितीयता [अध्याय 6](https://one-course.com/books/math/3/hi/chapter/6-integer-arithmetic#ch-b1-arith) में सिद्ध है; $r = 0$ के लिए $0/1$ लीजिए)। तब [प्रतिचित्रण](#def-b1-logic-map) $r \mapsto (p, q)$ [एकैकी](#def-b1-logic-inj) है: युग्म $r = p/q$ को निर्धारित कर देता है। अतः प्रश्न 13 से $\Q \preceq \Z \times \N^* \preceq \N$। चूँकि $\N \subseteq \Q$ से $\N \preceq \Q$ मिलता है, प्रश्न 12 (या सीधे कैंटर–श्रोडर–बर्नस्टाइन) दिखाता है कि $\Q \approx \N$: परिमेय संख्याएँ गणनीय हैं।

**15.** प्रत्येक $n$ के लिए एक [एकैकी](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) $f_n \colon E_n \to
\N$ नियत कीजिए। $x \in \bigcup_n E_n$ के लिए मान लीजिए $n(x)$ वह *न्यूनतम* $n$ है जिसके लिए $x \in E_n$, और $u(x) = \varphi\bigl(n(x),
f_{n(x)}(x)\bigr) \in \N$ रखिए। यदि $u(x) = u(x')$, तो $\varphi$ की एकैकीयता से $n(x) = n(x') = n$ और $f_n(x) = f_n(x')$ मिलते हैं, अतः $f_n$ की एकैकीयता से $x = x'$। अतः सम्मिलन $\N$ में [एकैकी](#def-b1-logic-inj) रूप से समा जाता है: वह अधिकतम गणनीय है।

**16.** परिमित $F \subseteq \N$ ($\Psi(\emptyset) = 0$) के लिए $\Psi(F)
= \sum_{i \in F} 2^i$ रखिए। मान लीजिए $F \neq F'$ और $m$ वह बृहत्तम अवयव है जिस पर वे भिन्न हैं, मान लीजिए $m \in F \setminus F'$ (आवश्यकता हो तो नाम बदल लीजिए)। अवयव $> m$ या तो दोनों में हैं या किसी में नहीं, अतः वे दोनों योगों में समान योगदान देते हैं; अवयवों $\leq m$ के योगदानों की तुलना कीजिए:

$$
\sum_{i \in F,\, i \leq m} 2^i \geq 2^m
> 2^m - 1 = \sum_{k=0}^{m-1} 2^k
\geq \sum_{i \in F',\, i \leq m} 2^i ,
$$

जहाँ [अभ्यास 1.4](#exo-b1-logic-4) के गुणोत्तर योग का प्रयोग किया गया। अतः $\Psi(F)
\neq \Psi(F')$: $\Psi$ [एकैकी](#def-b1-logic-inj) है और $\N$ के परिमित उपसमुच्चयों का [समुच्चय](#def-b1-logic-sets) अधिकतम गणनीय है; वह अनंत है (उसमें सभी एकल [समुच्चय](#def-b1-logic-sets) हैं), अतः गणनीय है।

**17.** $A \subseteq \N$ को उसके सूचक $\mathbf 1_A \colon \N \to
\{0,1\}$ पर भेजिए, जहाँ $n \in A$ होने पर $\mathbf 1_A(n) = 1$ और अन्यथा $0$; और $u \in \{0,1\}^{\N}$ को $A_u = \{n \in \N : u(n) = 1\}$ पर भेजिए। दोनों [प्रतिचित्रण](#def-b1-logic-map) परस्पर प्रतिलोम हैं: $A_{\mathbf 1_A} = A$ और $\mathbf
1_{A_u} = u$ (प्रत्येक $n$ पर मान जाँचिए)। [प्रमेय 1.24](#thm-b1-logic-inverse) से प्रत्येक एकैकी आच्छादन है: $\mathcal{P}(\N) \approx \{0,1\}^{\N}$।

**18.** प्रत्येक $n$ के लिए $d(n) = 1 - \Phi(n)(n) \neq \Phi(n)(n)$, अतः अनुक्रम $d$ और $\Phi(n)$ सूचकांक $n$ पर भिन्न हैं: $d \neq \Phi(n)$। अतः कोई $\Phi$ [आच्छादक](#def-b1-logic-inj) नहीं है, और प्रश्न 3 से कोई [एकैकी](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) $\{0,1\}^{\N} \to \N$ भी नहीं है: $\{0,1\}^{\N}$ अधिकतम गणनीय नहीं है। प्रश्न 17 के शब्दकोश से, [प्रतिचित्रण](#def-b1-logic-map) $\Phi \colon \N \to \{0,1\}^{\N}$ वस्तुतः [प्रतिचित्रण](#def-b1-logic-map) $f \colon \N \to \mathcal{P}(\N)$ है, और $d$ [समुच्चय](#def-b1-logic-sets) $D
= \{n : n \notin f(n)\}$ के अनुरूप है (वस्तुतः $d(n) = 1 \iff \Phi(n)(n) = 0
\iff n \notin f(n)$): विकर्ण तर्क ही $E = \N$ के लिए [अभ्यास 1.11](#exo-b1-logic-11) की कैंटर वाली उपपत्ति *है*।

**19.** $x_n = 0.d_1(n)\,d_2(n)\,d_3(n)\dots$ को उचित रूप में लिखिए और $d_n(n) \neq 5$ होने पर $\delta_n = 5$, $d_n(n) = 5$ होने पर $\delta_n = 6$ परिभाषित कीजिए, फिर $x = 0.\delta_1\delta_2\delta_3\dots$। इस प्रसार में केवल अंक $5$ और $6$ आते हैं, अतः वह $9$ की माला पर समाप्त नहीं होता: यह किसी वास्तविक $x \in \intco01$ का उचित प्रसार है। प्रत्येक $n$ के लिए $x$ और $x_n$ के $n$-वें अंक भिन्न हैं (रचना से $\delta_n \neq d_n(n)$); और चूँकि उचित प्रसार अद्वितीय होते हैं, अतः $x \neq x_n$। इस प्रकार कोई अनुक्रम $\intco01$ को नहीं भरता: फिर से प्रश्न 3 से, $\intco01$ अधिकतम गणनीय नहीं है।

**20.** $\intco01 \subseteq \R$, अतः कोई [एकैकी](#def-b1-logic-inj) [प्रतिचित्रण](#def-b1-logic-map) $\R \to \N$ $\intco01$ पर सीमित होकर प्रश्न 19 का विरोध करेगा: $\R$ अगणनीय है। यदि $\R
\setminus \Q$ अधिकतम गणनीय होता, तो $\R = \Q \cup (\R \setminus \Q)$ दो अधिकतम गणनीय समुच्चयों का सम्मिलन होता, अतः प्रश्न 15 से अधिकतम गणनीय होता ($E_0 = \Q$, और $n \geq 1$ के लिए $E_n = \R \setminus \Q$ लीजिए) — विरोधाभास। अतः अपरिमेय संख्याएँ अगणनीय हैं। ठीक-ठीक कहें तो: $\R$ के भीतर परिमेय संख्याएँ एक [गणनीय समुच्चय](#pb-b1-logic-1) बनाती हैं जबकि उनका पूरक अगणनीय है; कोई एकैकी आच्छादन $\R \setminus \Q$ को $\Q$ से कभी मिला नहीं सकता — अपरिमेय संख्याएँ परिमेय संख्याओं से कठोर अर्थ में “अधिक” हैं, यद्यपि दोनों अनंत हैं और दोनों सघन हैं।

**21.** $p/q$ ($q \neq 0$ के साथ) $qX - p$ का मूल है, जो पूर्णांक गुणांकों वाला अशून्य बहुपद है। $\sqrt 2$ $X^2 - 2$ का मूल है। $x = \sqrt 2 +
\sqrt 3$ के लिए: $x^2 = 5 + 2\sqrt 6$, अतः $x^2 - 5 = 2\sqrt 6$ और $(x^2 -
5)^2 = 24$, अर्थात्

$$
x^4 - 10x^2 + 1 = 0 :
$$

$\sqrt 2 + \sqrt 3$ $X^4 - 10X^2 + 1$ का मूल है।

**22.** $P = a_0 + a_1X + \dots + a_nX^n$ (घात $\leq n$, पूर्णांक गुणांक) को $(a_0, \dots, a_n) \in \Z^{n+1}$ पर भेजिए: यह [एकैकी](#def-b1-logic-inj) है, क्योंकि बहुपद अपने गुणांकों से निर्धारित होता है। $n$ पर आगमन से: $\Z^1 = \Z$ गणनीय है (प्रश्न 4), और $\Z^{n+2} \approx \Z^{n+1} \times \Z$ प्रश्न 13 से अधिकतम गणनीय है। अतः परिबद्ध घात वाले पूर्णांक बहुपदों का प्रत्येक [समुच्चय](#def-b1-logic-sets) अधिकतम गणनीय है; वह अनंत है (उसमें अचर बहुपद हैं), अतः प्रश्न 12 से गणनीय है।

**23.** सभी पूर्णांक बहुपदों का [समुच्चय](#def-b1-logic-sets) $\bigcup_{n \in \N} \{P : \deg
P \leq n,\ P \text{ के पूर्णांक गुणांक हैं}\}$ है, जो गणनीय समुच्चयों का गणनीय सम्मिलन है: प्रश्न 15 से अधिकतम गणनीय, और अनंत, अतः गणनीय।

**24.** प्रत्येक अशून्य पूर्णांक बहुपद $P$ के लिए मूलों का [समुच्चय](#def-b1-logic-sets) $R_P
= \{x \in \R : P(x) = 0\}$ परिमित है (अधिक से अधिक $\deg P$ अवयव, स्वीकृत)। प्रश्न 23 से अशून्य पूर्णांक बहुपदों की गणना $P_0, P_1, P_2, \dots$ की जा सकती है; तब $\mathcal{A} = \bigcup_{n \in \N} R_{P_n}$ परिमित (अतः अधिकतम गणनीय) समुच्चयों का गणनीय सम्मिलन है: प्रश्न 15 से अधिकतम गणनीय। उसमें $\Q$ है (प्रश्न 21), अतः वह अनंत है: $\mathcal{A}$ गणनीय है।

**25.** यदि $\R \setminus \mathcal{A}$ अधिकतम गणनीय होता, तो $\R =
\mathcal{A} \cup (\R \setminus \mathcal{A})$ भी अधिकतम गणनीय होता (प्रश्न 15), जो प्रश्न 20 का विरोध करता है। अतः अबीजीय संख्याएँ विद्यमान हैं और वे तो अगणनीय [समुच्चय](#def-b1-logic-sets) तक बनाती हैं, जबकि बीजीय संख्याएँ — जिनमें पूर्णांकों से करणी द्वारा बनी हर संख्या आती है — $\R$ के भीतर मात्र एक गणनीय ढाँचा बनाती हैं। पूरी रचना का सारांश: प्रश्न 1–3 तुलना की भाषा खड़ी करते हैं; कैंटर–श्रोडर–बर्नस्टाइन (प्रश्न 5–9) एक चतुर एकैकी आच्छादन के बदले दो सरल [एकैकी](#def-b1-logic-inj) प्रतिचित्रणों से समशक्तता सिद्ध करने देता है, और उसका प्रयोग $\intcc01
\approx \intoo01$ के लिए, $\Q$ के लिए तथा पूरे भाग V में हुआ; युग्मन एकैकी आच्छादन (प्रश्न 10) ने गुणन और गणनीय सम्मिलनों (प्रश्न 13, 15) को शक्ति दी, जिन्होंने बदले में $\Q$, पूर्णांक बहुपदों और $\mathcal{A}$ को शक्ति दी; और विकर्ण तर्क (प्रश्न 18–19) ने वह एकमात्र कठोर असमिका $\N \prec \R$ दी जो पूरी कहानी को अतुच्छ बनाती है। कैंटर का निष्कर्ष दार्शनिक दृष्टि से चकित करने वाला है: उपपत्ति एक भी [अबीजीय संख्या](#pb-b1-logic-1) प्रस्तुत नहीं करती, फिर भी दिखा देती है कि समशक्तता के अर्थ में *लगभग हर* वास्तविक संख्या अबीजीय है। किसी एक विशिष्ट [अबीजीय संख्या](#pb-b1-logic-1) का नाम लेने — $\pi$ या $\eu$ — के लिए बिलकुल भिन्न गणित और कई दशकों का और परिश्रम चाहिए था।