समुच्चय, संबंध और फलन

सारांश

यह पाठ वह भाषा स्थापित करता है जिसमें पाठ्यक्रम संख्याओं और फलनों की बात करता है, और परिमाणकों के तर्कशास्त्र का वह भाग जो अनिवार्य है। यह समावेश और समुच्चयों की संक्रियाओं को परिभाषित करता है, द्विपक्षीय समावेश से समुच्चयों की समता सिद्ध करता है, डी मॉर्गन के नियम सिद्ध करता है, क्रमित युग्म और उसका अभिलाक्षणिक गुण रचता है, और कार्तीय गुणनफल तथा संबंधों और उनके गुणों को परिभाषित करता है। यह सिद्ध करता है कि किसी तुल्यता संबंध के वर्ग एक खंडन बनाते हैं और प्रत्येक खंडन एक तुल्यता संबंध निर्धारित करता है, जिससे पूर्णांकों की रचना की तैयारी होती है; क्रम संबंधों का, उनके चरम अवयवों और परिबंधों सहित, अध्ययन करता है; फलनों को संबंधों के रूप में देखता है, और सिद्ध करता है कि संघटन साहचर्य है और एकैकीपन तथा आच्छादकता को बनाए रखता है, तथा कोई फलन एकैकी आच्छादक है यदि और केवल यदि उसका प्रतिलोम है, जो अद्वितीय होता है। प्रश्न तुल्यता संबंधों को गिनते हैं, प्राकृत संख्याओं को सम संख्याओं से युग्मित करते हैं, किसी तिथि का सप्ताह का दिन निकालते हैं, और किसी भी फलन को एक आच्छादक, एक एकैकी संगतता और एक एकैकी फलन के संघटन में विघटित करते हैं।

अधिगम उद्देश्य

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

पाठ्यक्रम की भाषा

अगला पाठ एक फलन, परवर्ती फलन, के द्वारा प्राकृत संख्याओं को परिभाषित करता है, जो एकैकी है और $1$ तक नहीं पहुँचता; अगली इकाई पूर्णांकों और परिमेय संख्याओं को एक तुल्यता संबंध के वर्गों के रूप में रचती है; संचय-सिद्धांत का पाठ अवयवों की संख्या को एकैकी संगतताओं से परिभाषित करता है; प्राकृत संख्याओं का क्रम एक क्रम संबंध है, और तीसरी इकाई वास्तविक फलनों का संघटन करती है और उनका प्रतिलोम लेती है। ये सभी शब्द एक ही भाषा के हैं, और उनका उपयोग करने से पहले उसे स्थिर कर लेना उचित है, उन पहले प्रमेयों के साथ जिनका पाठ्यक्रम आगे हवाला देगा।

यह स्पष्ट करना आवश्यक है कि क्या पहले से उपयोग किया जा रहा है। उदाहरणों में छोटी प्राकृत संख्याएँ और उनका क्रम, योग, गुणन, विभाज्यता और भाग का शेषफल वैसे ही उपयोग किए जाते हैं जैसे विद्यालय में सीखे गए थे। अगला पाठ पियानो के अभिगृहीतों से प्राकृत संख्याओं को परिभाषित करता है, और इस इकाई के पाठ इन संक्रियाओं को परिभाषित करते हैं और उनके गुण सिद्ध करते हैं, इस पाठ के किसी भी उदाहरण का उपयोग किए बिना; इसलिए कोई चक्रीय निर्भरता नहीं है। इस पाठ का कोई भी प्रमेय उदाहरणों पर निर्भर नहीं करता: संख्याएँ केवल यह देखने के लिए आती हैं कि प्रमेय कैसे काम करते हैं।

जो स्वीकार किया जाता है

समुच्चय वस्तुओं का एक संग्रह है, जिन्हें उसके अवयव कहते हैं; $a \in A$ लिखकर यह व्यक्त किया जाता है कि $a$ , $A$ का अवयव है, और $a \notin A$ लिखकर इसका निषेध किया जाता है। समुच्चय और सदस्यता परिभाषित नहीं किए जाते: वे आदिम धारणाएँ हैं, जैसे अंकगणित में $1$ और परवर्ती। फिर भी, हर गुण कोई समुच्चय निर्धारित नहीं करता। यदि उन सभी समुच्चयों का, जो स्वयं के अवयव नहीं हैं, एक समुच्चय $R$ होता, तो इस प्रश्न का कि “क्या $R$ , $R$ का अवयव है” कोई उत्तर न होता, क्योंकि $R$ की परिभाषा से $R \in R \leftrightarrow R \notin R$ प्राप्त होता। यह विरोधाभास रसेल ने 1901 में खोजा था, और यह समुच्चय बनाने के ढंग को सीमित करने पर बाध्य करता है: कोई गुण केवल पहले से दिए गए समुच्चय में से अवयव चुन सकता है।

बिना उपपत्ति स्वीकृत तथ्य (सहज समुच्चय सिद्धांत के नियम)। इस पाठ में प्रयुक्त सहज समुच्चय सिद्धांत के नियम बिना उपपत्ति स्वीकार किए जाते हैं: समान अवयवों वाले दो समुच्चय बराबर होते हैं; दिए गए समुच्चय $A$ और गुण $P$ से समुच्चय $\{ x \in A : P(x) \}$ बनाया जा सकता है, जो $A$ के उन अवयवों से बना है जो उस गुण को संतुष्ट करते हैं; और रिक्त समुच्चय, समुच्चय $\{a, b\}$ (जिसके अवयव केवल $a$ और $b$ हैं), समुच्चयों के किसी समुच्चय के अवयवों का सम्मिलन, और किसी समुच्चय के सभी उपसमुच्चयों का समुच्चय अस्तित्व में हैं। प्राकृत संख्याओं के समुच्चय के गुणों वाले समुच्चय का अस्तित्व अगले पाठ में स्वीकार किया जाता है।

ये नियम ज़र्मेलो और फ्रेंकेल के अभिगृहीतों से संबंधित हैं, जिनका अध्ययन समुच्चय सिद्धांत का विषय है और इस पाठ्यक्रम की सीमा से बाहर है; इसलिए यहाँ उन्हें स्वीकार किया जाता है और स्पष्ट रूप से गिनाया जाता है, ताकि ठीक-ठीक पता रहे कि किसका उपयोग हो रहा है।

परिमाणकों का तर्कशास्त्र

उपपत्तियाँ संयोजकों $\neg$ , $\wedge$ , $\vee$ , $\rightarrow$ और $\leftrightarrow$ से कथनों को जोड़ती हैं, जिनके नियम सहायक पाठ्यक्रम गणितीय तर्कशास्त्र I: प्रतिज्ञप्ति तर्कशास्त्र में, उसकी भाषा से आरंभ करके, पढ़े जाते हैं; यहाँ इतना याद करना पर्याप्त है कि सोपाधिक $p \rightarrow q$ केवल तब असत्य होता है जब $p$ सत्य हो और $q$ असत्य, कि वह अपने प्रतिपरिवर्तित कथन $\neg q \rightarrow \neg p$ के तुल्य है, और कि डी मॉर्गन के नियम संयोजन या वियोजन का निषेध देते हैं:

\neg \left( p \wedge q \right) \leftrightarrow \left( \neg p \vee \neg q \right), \qquad \neg \left( p \vee q \right) \leftrightarrow \left( \neg p \wedge \neg q \right)

फिर भी, समुच्चयों की बात करने के लिए सभी अवयवों के बारे में या किसी एक अवयव के बारे में कथनों की भी आवश्यकता होती है। यदि $P(x)$ , $A$ के अवयवों का एक गुण है, तो कथन $(\forall x \in A)\,P(x)$ को “प्रत्येक $x$ के लिए जो $A$ में है, $P(x)$ ” पढ़ा जाता है और यह दावा करता है कि $A$ के सभी अवयव उस गुण को संतुष्ट करते हैं; कथन $(\exists x \in A)\,P(x)$ को “कोई $x$ है जो $A$ में है, जिसके लिए $P(x)$ ” पढ़ा जाता है और यह दावा करता है कि कम से कम एक अवयव उसे संतुष्ट करता है; और $(\exists! x \in A)\,P(x)$ यह दावा करता है कि ठीक एक अवयव उसे संतुष्ट करता है। प्रतीकों $\forall$ और $\exists$ को परिमाणक कहते हैं, क्रमशः सार्वत्रिक और अस्तित्वात्मक।

बिना उपपत्ति स्वीकृत तथ्य (परिमाणकों का निषेध)। यह नकारना कि सभी अवयव किसी गुण को संतुष्ट करते हैं, यह दावा करना है कि कोई अवयव उसे संतुष्ट नहीं करता; और यह नकारना कि कोई अवयव उसे संतुष्ट करता है, यह दावा करना है कि कोई भी अवयव उसे संतुष्ट नहीं करता:

\neg (\forall x \in A)\,P(x) \leftrightarrow (\exists x \in A)\,\neg P(x), \qquad \neg (\exists x \in A)\,P(x) \leftrightarrow (\forall x \in A)\,\neg P(x)

ये नियम प्रथम कोटि के तर्कशास्त्र से संबंधित हैं, और यहाँ स्वीकार किए जाते हैं; ये डी मॉर्गन के नियमों का व्यापकीकरण हैं, क्योंकि यदि $A = \{a, b\}$ , तो सार्वत्रिक कथन $P(a) \wedge P(b)$ है और अस्तित्वात्मक कथन $P(a) \vee P(b)$ है। परिमाणकों का क्रम महत्त्वपूर्ण है: कथन $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$ कहता है कि प्रत्येक प्राकृत संख्या से बड़ी कोई दूसरी प्राकृत संख्या है, और यह सत्य है; कथन $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$ कहता है कि कोई प्राकृत संख्या सभी प्राकृत संख्याओं से बड़ी है, स्वयं से भी, और यह असत्य है।

किसी कथन का तार्किक रूप उसे सिद्ध करने का ढंग निर्धारित करता है। इस पाठ में प्रयुक्त युक्तियाँ ये हैं, और उनका तार्किक आधार निगमन की तकनीकों वाले पाठ में पढ़ा जाता है।

$(\forall x \in A)\,P(x)$ सिद्ध करने के लिए एक मनमाना अवयव $x$ लिया जाता है जो $A$ में है, इसके अतिरिक्त कुछ भी माने बिना कि वह $A$ का अवयव है, और $P(x)$ सिद्ध किया जाता है।
$(\exists x \in A)\,P(x)$ सिद्ध करने के लिए $A$ का एक ठोस अवयव दिखाया जाता है जो $P$ को संतुष्ट करता है; $(\forall x \in A)\,P(x)$ का खंडन करने के लिए एक प्रत्युदाहरण पर्याप्त है, अर्थात् एक अवयव जो उसे संतुष्ट नहीं करता।
$p \rightarrow q$ सिद्ध करने के लिए $p$ मानकर $q$ निगमित किया जाता है; या प्रतिपरिवर्तित कथन $\neg q \rightarrow \neg p$ सिद्ध किया जाता है; या $p \wedge \neg q$ मानकर विरोधाभास प्राप्त किया जाता है।
$p \leftrightarrow q$ सिद्ध करने के लिए दोनों सोपाधिक कथन $p \rightarrow q$ और $q \rightarrow p$ सिद्ध किए जाते हैं।

उदाहरणकिसी समुच्चय के परिबद्ध होने का निषेध

प्राकृत संख्याओं का समुच्चय $X$ ऊपर से परिबद्ध कहलाता है यदि कोई प्राकृत संख्या $c$ है जो उसके सभी अवयवों से बड़ी या उनके बराबर है। इस परिभाषा को परिमाणकों से लिखिए, और उसका निषेध चरण दर चरण लिखिए।

प्रमाण

$\dato{acot}{(\exists c \in \mathbb{N})(\forall x \in X)(x \leq c)}$
परिभाषा में अस्तित्वात्मक परिमाणक के बाद सार्वत्रिक परिमाणक आता है: वही $c$ सभी अवयवों के लिए काम करना चाहिए।
$\resaltar{\neg} (\exists c \in \mathbb{N})(\forall x \in X)(x \leq c)$
पूरे कथन का निषेध किया जाता है।
$(\resaltar{\forall} c \in \mathbb{N})\,\resaltar{\neg} (\forall x \in X)(x \leq c)$
अस्तित्वात्मक कथन का निषेध निषेधित सार्वत्रिक कथन है।
$(\forall c \in \mathbb{N})(\resaltar{\exists} x \in X)\,\resaltar{\neg} (x \leq c)$
सार्वत्रिक कथन का निषेध निषेधित अस्तित्वात्मक कथन है।
$(\forall c \in \mathbb{N})(\exists x \in X)(\resaltar{x > c})$
प्राकृत संख्याओं के क्रम की त्रिभाजिता से, $x \leq c$ का निषेध करना $x > c$ का दावा करना है: समुच्चय ऊपर से परिबद्ध नहीं है जब कोई भी प्राकृत संख्या उपरि परिबंध नहीं है, क्योंकि प्रत्येक उम्मीदवार से कोई अवयव आगे निकल जाता है।

समुच्चय

सदस्यता, समता और समावेश

किसी समुच्चय का वर्णन सूचीकरण से, अर्थात् कोष्ठकों में उसके अवयवों को गिनाकर, जैसे $\{1, 2, 3\}$ , या किसी गुण के द्वारा नियम रूप से, जैसे $\{ n \in \mathbb{N} : n \leq 3 \}$ , किया जा सकता है, और यह वही समुच्चय है। विस्तार का नियम कहता है कि कोई समुच्चय अपने अवयवों से निर्धारित होता है:

A = B \leftrightarrow (\forall x)(x \in A \leftrightarrow x \in B)

इससे यह निकलता है कि सूचीकरण में न क्रम मायने रखता है न पुनरावृत्ति: $\{1, 2, 2\}$ और $\{2, 1\}$ एक ही समुच्चय हैं, क्योंकि उनके अवयव समान हैं। यह भी निकलता है कि बिना अवयवों का समुच्चय केवल एक है, रिक्त समुच्चय $\emptyset$ : बिना अवयवों वाले दो समुच्चयों के अवयव समान हैं, अर्थात् किसी के भी कोई अवयव नहीं।

परिभाषा (समावेश)। समुच्चय $A$ समुच्चय $B$ में अंतर्विष्ट है, या $B$ का उपसमुच्चय है, यदि $A$ का प्रत्येक अवयव $B$ का अवयव है:

A \subseteq B \leftrightarrow (\forall x)(x \in A \rightarrow x \in B)

यदि इसके अतिरिक्त $A \neq B$ , तो $A$ को $B$ का उचित उपसमुच्चय कहते हैं।

रिक्त समुच्चय प्रत्येक समुच्चय $A$ में अंतर्विष्ट है, क्योंकि सोपाधिक $x \in \emptyset \rightarrow x \in A$ का पूर्वपद सदा असत्य है, और इसलिए वह सत्य है। सदस्यता और समावेश में भेद करना चाहिए: $1 \in \{1, 2\}$ और $\{1\} \subseteq \{1, 2\}$ सत्य हैं, पर $\{1\} \in \{1, 2\}$ असत्य है, क्योंकि $\{1, 2\}$ के अवयव केवल $1$ और $2$ हैं, और समुच्चय $\{1\}$ उनमें से किसी के बराबर नहीं है: $\{1\} \neq 1$ , क्योंकि वह समुच्चय जिसका एकमात्र अवयव $1$ है, $1$ से अलग है, और $\{1\} \neq 2$ ।

प्रमेयसमावेश के गुण

किन्हीं भी समुच्चयों $A$ , $B$ और $C$ के लिए, समावेश स्वतुल्य है, $A \subseteq A$ ; संक्रामक है, यदि $A \subseteq B$ और $B \subseteq C$ , तो $A \subseteq C$ ; और प्रतिसममित है, यदि $A \subseteq B$ और $B \subseteq A$ , तो $A = B$ । अंतिम गुण, अपने स्पष्ट विलोम के साथ, द्विपक्षीय समावेश की विधि है: दो समुच्चयों की समता सिद्ध करने के लिए यह सिद्ध किया जाता है कि प्रत्येक दूसरे में अंतर्विष्ट है।

A = B \leftrightarrow \left( A \subseteq B \wedge B \subseteq A \right)

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

प्रमाण

$(\forall x)(x \in A \rightarrow x \in A)$
स्वतुल्यता: किसी भी $x$ के लिए सोपाधिक $x \in A \rightarrow x \in A$ सत्य है, क्योंकि उसका उत्तरपद उसका पूर्वपद ही है।
$x \in A \rightarrow \dato{xb}{x \in B}$
संक्रामकता: मान लीजिए $x$ , $A$ का कोई मनमाना अवयव है। पहली परिकल्पना से $x$ , $B$ का अवयव है।
$\resaltar{x \in B} \rightarrow x \in C$
दूसरी परिकल्पना से $x$ , $C$ का अवयव है। चूँकि $x$ मनमाना था, $A \subseteq C$ ।
$(x \in A \rightarrow x \in B) \wedge (x \in B \rightarrow x \in A) \leftrightarrow \resaltar{(x \in A \leftrightarrow x \in B)}$
प्रतिसममितता: दोनों परिकल्पनाएँ प्रत्येक $x$ के लिए $x \in A$ और $x \in B$ के बीच दोनों सोपाधिक देती हैं, अर्थात् उनकी तुल्यता।
$A = B$
विस्तार के नियम से $A$ और $B$ बराबर हैं। विलोमतः, यदि $A = B$ , तो स्वतुल्यता से प्रत्येक दूसरे में अंतर्विष्ट है।

सम्मिलन, सर्वनिष्ठ और अंतर

परिभाषा (समुच्चयों की संक्रियाएँ)। $A$ और $B$ का सम्मिलन उन अवयवों का समुच्चय है जो कम से कम एक में हैं; सर्वनिष्ठ, उन अवयवों का जो दोनों में हैं; और अंतर $A \setminus B$ , उन अवयवों का जो $A$ में हैं और $B$ में नहीं:

x \in A \cup B \leftrightarrow x \in A \vee x \in B, \qquad x \in A \cap B \leftrightarrow x \in A \wedge x \in B, \qquad x \in A \setminus B \leftrightarrow x \in A \wedge x \notin B

यदि $B \subseteq A$ , तो अंतर $A \setminus B$ को $B$ का $A$ के सापेक्ष पूरक कहते हैं। दो समुच्चय असंयुक्त कहलाते हैं यदि उनका सर्वनिष्ठ रिक्त है।

प्रत्येक संक्रिया एक संयोजक के संगत है: सम्मिलन वियोजन के, सर्वनिष्ठ संयोजन के, और अंतर संयोजन और एक निषेध के। यदि ऐसा है, तो तर्कशास्त्र का प्रत्येक नियम समुच्चयों का एक नियम उत्पन्न करता है: सम्मिलन और सर्वनिष्ठ क्रमविनिमेय, साहचर्य और एक-दूसरे पर वितरणशील हैं, क्योंकि संयोजक ऐसे हैं, और ये सभी नियम नीचे के प्रमेय की तरह सिद्ध होते हैं। पूरक सदा किसी संदर्भ समुच्चय के सापेक्ष लिया जाता है, क्योंकि जो कुछ भी $B$ में नहीं है उस सबका समुच्चय फिर से रसेल का विरोधाभास उत्पन्न करेगा।

उदाहरण12 और 18 के भाजक

मान लीजिए $A = \{1, 2, 3, 4, 6, 12\}$ , $12$ के भाजकों का समुच्चय है और $B = \{1, 2, 3, 6, 9, 18\}$ , $18$ के भाजकों का समुच्चय है। सम्मिलन, सर्वनिष्ठ और दोनों अंतर निकालिए।

प्रमाण

$A \cap B = \dato{c}{\{1, 2, 3, 6\}}$
उभयनिष्ठ अवयव दोनों संख्याओं के उभयनिष्ठ भाजक हैं, अर्थात् $6$ के भाजक।
$A \setminus B = \{1, 2, 3, 4, 6, 12\} \setminus \resaltar{\{1, 2, 3, 6\}} = \{4, 12\}$
$A$ के वे अवयव जो $18$ के भाजक नहीं हैं, वे हैं जो $A$ में से उभयनिष्ठ अवयव हटाने पर बचते हैं।
$B \setminus A = \{9, 18\}$
इसी प्रकार, $18$ के वे भाजक जो $12$ के भाजक नहीं हैं।
$A \cup B = \left( A \setminus B \right) \cup \left( A \cap B \right) \cup \left( B \setminus A \right) = \{1, 2, 3, 4, 6, 9, 12, 18\}$
सम्मिलन तीन युग्मशः असंयुक्त भागों को मिलाता है: प्रत्येक अवयव एक ही बार आता है, और $4 + 2 + 2 = 8$ ।

प्रमेयसमुच्चयों के लिए डी मॉर्गन के नियम

किन्हीं भी समुच्चयों $A$ , $B$ और $C$ के लिए, $A$ के सापेक्ष सम्मिलन का पूरक पूरकों का सर्वनिष्ठ है, और सर्वनिष्ठ का पूरक पूरकों का सम्मिलन है:

A \setminus \left( B \cup C \right) = \left( A \setminus B \right) \cap \left( A \setminus C \right), \qquad A \setminus \left( B \cap C \right) = \left( A \setminus B \right) \cup \left( A \setminus C \right)

यह सिद्ध किया जाता है कि एक मनमाना अवयव बाएँ पक्ष में है यदि और केवल यदि वह दाएँ पक्ष में है, प्रत्येक संक्रिया का उसके संयोजक में अनुवाद करके। चित्र वेन आरेख पर संबंधित क्षेत्रों को छायांकित करता है।

प्रमाण

$x \in A \setminus \left( B \cup C \right) \leftrightarrow x \in A \wedge \resaltar{\neg} \left( x \in B \cup C \right)$
मान लीजिए $x$ मनमाना है। अंतर की परिभाषा से, बाएँ पक्ष में होना $A$ में होना और $B \cup C$ में न होना है।
$\leftrightarrow x \in A \wedge \neg \left( x \in B \resaltar{\vee} x \in C \right)$
सम्मिलन की परिभाषा से।
$\leftrightarrow x \in A \wedge \left( x \resaltar{\notin} B \resaltar{\wedge} x \resaltar{\notin} C \right)$
तर्कशास्त्र के डी मॉर्गन नियम से, वियोजन का निषेध निषेधों का संयोजन है।
$\leftrightarrow \left( \resaltar{x \in A} \wedge x \notin B \right) \wedge \left( \resaltar{x \in A} \wedge x \notin C \right)$
चूँकि $p$ , $p \wedge p$ के तुल्य है, शर्त $x \in A$ को दोहराया जाता है और संयोजन की साहचर्यता और क्रमविनिमेयता से पुनः समूहित किया जाता है।
$\leftrightarrow x \in \left( A \setminus B \right) \resaltar{\cap} \left( A \setminus C \right)$
अंतर और सर्वनिष्ठ की परिभाषा से, यह दाएँ पक्ष में होना है। विस्तार के नियम से पहला नियम सिद्ध होता है।
$x \in A \setminus \left( B \cap C \right) \leftrightarrow x \in A \wedge \left( x \notin B \resaltar{\vee} x \notin C \right) \leftrightarrow x \in \left( A \setminus B \right) \resaltar{\cup} \left( A \setminus C \right)$
दूसरा नियम तुल्यताओं की उसी शृंखला से सिद्ध होता है, सम्मिलन और सर्वनिष्ठ को, तथा वियोजन और संयोजन को, आपस में बदलकर; तब प्रयुक्त तार्किक नियम दूसरा डी मॉर्गन नियम होता है।

घात समुच्चय

किसी समुच्चय के उपसमुच्चय स्वयं एक समुच्चय बनाते हैं, जिसका अस्तित्व आरंभ में स्वीकार किया गया था। $A$ का घात समुच्चय, जिसे $\mathcal{P}(A)$ लिखते हैं, वह समुच्चय है जिसके अवयव $A$ के उपसमुच्चय हैं:

X \in \mathcal{P}(A) \leftrightarrow X \subseteq A

उदाहरण के लिए, $\{1, 2, 3\}$ के घात समुच्चय में आठ अवयव हैं: रिक्त समुच्चय, तीन एक-अवयवी समुच्चय, तीन दो-अवयवी समुच्चय और स्वयं $\{1, 2, 3\}$ ।

\mathcal{P}(\{1, 2, 3\}) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \}

किसी भी समुच्चय $A$ के लिए, रिक्त समुच्चय और स्वयं $A$ , $\mathcal{P}(A)$ के अवयव हैं, और प्रत्येक $a$ के लिए जो $A$ में है, $\{a\} \in \mathcal{P}(A)$ , जबकि $a$ सामान्यतः $\mathcal{P}(A)$ का अवयव नहीं है। संचय-सिद्धांत के पाठ में सिद्ध किया जाएगा कि $n$ अवयवों वाले समुच्चय के $2^n$ उपसमुच्चय होते हैं।

क्रमित युग्म और कार्तीय गुणनफल

समतल का एक बिंदु, एक भिन्न या कोई अभी न किया गया व्यवकलन, एक निश्चित क्रम में रखी दो वस्तुओं से वर्णित होते हैं: युग्म $(3, 5)$ , युग्म $(5, 3)$ नहीं है। समुच्चय $\{3, 5\}$ इसके काम नहीं आता, क्योंकि वह $\{5, 3\}$ के बराबर है। क्रमित युग्म से केवल एक बात माँगी जाती है, उसका अभिलाक्षणिक गुण: दो युग्म बराबर हैं यदि और केवल यदि उनके पहले घटक मेल खाते हैं और उनके दूसरे घटक मेल खाते हैं। कुराटोव्स्की ने 1921 में दिखाया कि इस गुण वाली वस्तु रचने के लिए समुच्चय की धारणा ही पर्याप्त है।

परिभाषा (क्रमित युग्म)। पहले घटक $a$ और दूसरे घटक $b$ वाला क्रमित युग्म यह समुच्चय है

(a, b) = \{ \{a\}, \{a, b\} \}

प्रमेयक्रमित युग्म का अभिलाक्षणिक गुण

किन्हीं भी $a$ , $b$ , $c$ और $d$ के लिए, युग्म $(a, b)$ और $(c, d)$ बराबर हैं यदि और केवल यदि $a = c$ और $b = d$ ।

(a, b) = (c, d) \leftrightarrow a = c \wedge b = d

यदि घटक बराबर हैं, तो दोनों युग्म एक ही समुच्चय हैं। विलोम के लिए, यह भेद किया जाता है कि $a$ और $b$ बराबर हैं या नहीं, और गिना जाता है कि संबंधित प्रत्येक समुच्चय में कितने अवयव हैं। चित्र प्रत्येक युग्म को दो समुच्चयों के समुच्चय के रूप में खींचता है।

प्रमाण

$\dato{ig}{\{ \{a\}, \{a, b\} \} = \{ \{c\}, \{c, d\} \}}$
मान लीजिए दोनों युग्म बराबर हैं। विस्तार के नियम से उनके अवयव समान हैं।
$\{c\} = \{a\}, \quad \{c, d\} = \{a\} \rightarrow c = a, \quad d = a = b$
पहली स्थिति, $a = b$ । तब $\{a, b\} = \{a\}$ , और बाएँ पक्ष का एकमात्र अवयव $\{a\}$ है; इसलिए दाएँ पक्ष के दोनों अवयव उसके बराबर हैं।
$\{c\} = \{a\} \rightarrow \dato{ca}{c = a}$
दूसरी स्थिति, $a \neq b$ । समुच्चय $\{c\}$ बाएँ पक्ष का अवयव है, इसलिए वह $\{a\}$ या $\{a, b\}$ है; वह $\{a, b\}$ नहीं हो सकता, जिसमें दो अवयव हैं, इसलिए वह $\{a\}$ है।
$\{c, d\} = \{a, b\}$
$\{c, d\}$ भी बाएँ पक्ष का अवयव है। यदि वह $\{a\}$ होता, तो $d = a = c$ , और दाएँ पक्ष का एकमात्र अवयव $\{a\}$ होता, जबकि बाएँ पक्ष में दो हैं: यह असंभव है। इसलिए $\{c, d\}$ , $\{a, b\}$ है।
$\{a, \resaltar{d}\} = \{a, \resaltar{b}\} \rightarrow b = d$
चूँकि $c = a$ , अवयव $b$ जो $\{a, b\} = \{a, d\}$ में है, $a$ या $d$ है; वह $a$ नहीं है, क्योंकि $a \neq b$ , और इसलिए वह $d$ है।
$(a, b) = (c, d) \rightarrow a = c \wedge b = d$
दोनों स्थितियों में घटक मेल खाते हैं।

अभिलाक्षणिक गुण सिद्ध हो जाने के बाद कुराटोव्स्की की रचना भुलाई जा सकती है: पाठ्यक्रम युग्मों के बारे में जो कुछ कहता है, वह सब इसी गुण से निकलता है।

परिभाषा (कार्तीय गुणनफल)। $A$ और $B$ का कार्तीय गुणनफल उन युग्मों का समुच्चय है जिनका पहला घटक $A$ में और दूसरा घटक $B$ में है:

A \times B = \{ (a, b) : a \in A \wedge b \in B \}

संकेतन $\{ (a, b) : a \in A \wedge b \in B \}$ स्वयं स्वीकृत नियमों में से एक नहीं है, जो केवल पहले से बने समुच्चयों में से अवयवों को अलग करने की अनुमति देते हैं। फिर भी, यह समुच्चय अस्तित्व में है: यदि $a \in A$ और $b \in B$ , तो समुच्चय $\{a\}$ और $\{a, b\}$ , $A \cup B$ में अंतर्विष्ट हैं, और इसलिए $\mathcal{P}(A \cup B)$ के अवयव हैं; इससे निकलता है कि युग्म $(a, b) = \{ \{a\}, \{a, b\} \}$ , $\mathcal{P}(A \cup B)$ में अंतर्विष्ट है, अर्थात् $\mathcal{P}(\mathcal{P}(A \cup B))$ का अवयव है। इसलिए गुणनफल उस समुच्चय के भीतर पृथक्करण से बनता है जिसका अस्तित्व स्वीकृत नियम सुनिश्चित करते हैं: $A \cup B$ , $\{A, B\}$ के अवयवों का सम्मिलन है, और उस पर दो बार घात समुच्चय लिया जाता है।

A \times B = \{ z \in \mathcal{P}(\mathcal{P}(A \cup B)) : (\exists a \in A)(\exists b \in B)\,(z = (a, b)) \}

यह नाम देकार्त की याद दिलाता है: वैश्लेषिक ज्यामिति का समतल $\mathbb{R} \times \mathbb{R}$ है। गुणनफल क्रमविनिमेय नहीं है: $\{1\} \times \{2\}$ में केवल $(1, 2)$ है, और $\{2\} \times \{1\}$ में केवल $(2, 1)$ , जो अभिलाक्षणिक गुण से उससे अलग है।

उदाहरणग्रिड के रूप में कार्तीय गुणनफल

गुणनफल $A \times B$ लिखिए, जहाँ $A = \{1, 2, 3\}$ और $B = \{1, 2\}$ , और उसके अवयवों की संख्या की तुलना दोनों गुणनखंडों के अवयवों की संख्या से कीजिए।

प्रमाण

$A = \{1, 2, 3\}, \quad B = \{1, 2\}$
$A$ के अवयवों को क्षैतिज अक्ष पर और $B$ के अवयवों को ऊर्ध्वाधर अक्ष पर रखा जाता है: प्रत्येक युग्म ग्रिड का एक बिंदु है।
$(1, 1), \ (2, 1), \ (3, 1)$
दूसरे घटक $1$ वाले युग्म पहली पंक्ति बनाते हैं।
$(1, 2), \ (2, 2), \ (3, 2)$
दूसरे घटक $2$ वाले युग्म दूसरी पंक्ति बनाते हैं।
$A \times B = \{ (1, 1), (2, 1), (3, 1), (1, 2), (2, 2), (3, 2) \}$
गुणनफल में $3 \cdot 2 = 6$ अवयव हैं: उतनी पंक्तियाँ जितने $B$ के अवयव हैं, और प्रत्येक पंक्ति में उतने युग्म जितने $A$ के अवयव हैं। संचय-सिद्धांत का गुणन सिद्धांत इस गणना का व्यापकीकरण करता है।

संबंध

यह कहना कि $2$ , $6$ को विभाजित करता है, कि $3$ , $5$ से छोटा है, या कि दो तिथियाँ सप्ताह के एक ही दिन पड़ती हैं, यह दावा करना है कि वस्तुओं के कुछ युग्म संबंधित हैं। यदि ऐसा है, तो कोई संबंध उन युग्मों से निर्धारित होता है जिन्हें वह जोड़ता है, और उसे युग्मों के समुच्चय के रूप में परिभाषित किया जा सकता है।

परिभाषा (संबंध)। $A$ से $B$ में एक संबंध एक उपसमुच्चय $R$ है जो गुणनफल $A \times B$ में अंतर्विष्ट है; $A$ पर संबंध $A$ से $A$ में एक संबंध है। यदि $(a, b) \in R$ , तो कहते हैं कि $a$ , $b$ से $R$ द्वारा संबंधित है।

उदाहरण के लिए, $\{1, 2, 3\}$ पर संबंध “से छोटा या बराबर” युग्मों का समुच्चय $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$ है। अक्सर प्रयुक्त संबंधों के लिए पदों के बीच एक चिह्न लिखा जाता है, जैसे $a \leq b$ या $a \mid b$ , $(a, b) \in R$ के स्थान पर। किसी समुच्चय पर संबंध के चार गुण पूरे पाठ्यक्रम में बार-बार आते हैं।

परिभाषा (संबंध के गुण)। संबंध $R$ जो $A$ पर है, स्वतुल्य, सममित, प्रतिसममित या संक्रामक कहलाता है यदि वह क्रमशः निम्न शर्तें पूरी करता है।

स्वतुल्य, यदि प्रत्येक अवयव स्वयं से संबंधित है: $(\forall a \in A)\,((a, a) \in R)$ ;
सममित, यदि $a$ का $b$ से संबंधित होना यह निहित करता है कि $b$ , $a$ से संबंधित है: $(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$ ;
प्रतिसममित, यदि दोनों दिशाओं में संबंधित दो अवयव बराबर हैं: $(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$ ;
संक्रामक, यदि $a$ का $b$ से संबंधित होना और $b$ का $c$ से संबंधित होना यह निहित करता है कि $a$ , $c$ से संबंधित है: $(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$ ।

$A \times A$ के ग्रिड में संबंध बिंदुओं का एक समुच्चय है। वह स्वतुल्य है यदि उसमें पूरा विकर्ण, युग्मों $(a, a)$ का विकर्ण, शामिल है; सममित है यदि उसका आकार विकर्ण के सापेक्ष सममित है; और प्रतिसममित है यदि विकर्ण से बाहर किसी भी बिंदु का सममित बिंदु संबंध में नहीं है। प्रतिसममित का अर्थ “सममित नहीं” नहीं है: समता संबंध दोनों है, और अभ्यास प्रश्न 1 ऐसा संबंध माँगता है जो दोनों में से कोई नहीं है।

उदाहरण1 से 6 तक के समुच्चय में विभाज्यता और समता-विषमता

$A = \{1, 2, 3, 4, 5, 6\}$ पर विभाज्यता संबंध $a \mid b$ और संबंध “समान सम-विषमता होना” पर विचार कीजिए। दोनों को $A \times A$ के ग्रिड में खींचिए, और तय कीजिए कि प्रत्येक चार गुणों में से कौन-से पूरे करता है।

प्रमाण

$\dato{div}{\{ (a, b) \in A \times A : a \mid b \}}$
विभाज्यता प्रत्येक संख्या को $A$ में उसके गुणजों से जोड़ती है: $1$ को सभी से, $2$ को $2$ , $4$ और $6$ से, $3$ को $3$ और $6$ से, और शेष प्रत्येक को स्वयं से। कुल $14$ युग्म हैं।
$a = 1 \cdot a \rightarrow \resaltar{a \mid a}$
यह स्वतुल्य है, क्योंकि प्रत्येक संख्या स्वयं को विभाजित करती है: विकर्ण पूरा है।
$2 \mid 4, \quad \neg (4 \mid 2)$
यह सममित नहीं है: एक प्रत्युदाहरण पर्याप्त है। परंतु यह प्रतिसममित है, क्योंकि यदि $a \mid b$ और $b \mid a$ , तो प्रत्येक दूसरे से छोटा या उसके बराबर है।
$a \mid b \wedge b \mid c \rightarrow \resaltar{a \mid c}$
यह संक्रामक है: यदि $b = ka$ और $c = lb$ , तो $c = (lk)a$ । उदाहरण के लिए, $1 \mid 2$ और $2 \mid 6$ से $1 \mid 6$ निकलता है।
$(1, 3) \in R \wedge (3, 1) \in R, \quad 1 \neq 3$
समान सम-विषमता विषम संख्याओं को आपस में और सम संख्याओं को आपस में जोड़ती है: $9 + 9 = 18$ युग्म, जो विकर्ण के सापेक्ष सममित दो पिंड बनाते हैं। यह स्वतुल्य, सममित और संक्रामक है, पर प्रतिसममित नहीं, क्योंकि यह $1$ और $3$ को जोड़ती है, जो अलग हैं।

तुल्यता संबंध

संबंध “समान सम-विषमता होना” एक आंशिक समता जैसा व्यवहार करता है: यह उन संख्याओं को एक मानता है जो एक पहलू में, सम-विषमता में, मेल खाती हैं, और बाकी की उपेक्षा करता है। जिन तीन गुणों के कारण यह ऐसा व्यवहार करता है, उनका एक नाम है।

परिभाषा (तुल्यता संबंध)। $A$ पर कोई संबंध तुल्यता संबंध है यदि वह स्वतुल्य, सममित और संक्रामक है। तब $a \sim b$ लिखा जाता है और कहा जाता है कि $a$ , $b$ के तुल्य है। $a$ का वर्ग उन अवयवों का समुच्चय है जो $a$ के तुल्य हैं, और उसका प्रत्येक अवयव उस वर्ग का एक प्रतिनिधि है:

C(a) = \{ x \in A : x \sim a \}

सभी वर्गों के समुच्चय को भागफल समुच्चय कहते हैं और $A/{\sim}$ लिखते हैं।

तुल्यता संबंधों के उदाहरण हैं: समता, जिसके प्रत्येक वर्ग में एक ही अवयव है; समान सम-विषमता होना, जिसके दो वर्ग हैं; $3$ से भाग देने पर समान शेषफल छोड़ना, जिसके तीन वर्ग हैं; और सप्ताह के एक ही दिन पड़ना, जिसके सात वर्ग हैं और जो हल किया गया प्रश्न 3 है। व्यापक रूप से, यदि $g$ कोई फलन है जो $A$ पर परिभाषित है, तो संबंध $g(x) = g(y)$ समता से उसके तीनों गुण विरासत में पाता है, और हल किया गया प्रश्न 5 दिखाता है कि प्रत्येक तुल्यता संबंध इसी रूप का है।

उपप्रमेयतुल्यता वर्ग

मान लीजिए $\sim$ , $A$ पर एक तुल्यता संबंध है। किन्हीं भी $a$ और $b$ के लिए जो $A$ में हैं: प्रत्येक अवयव अपने वर्ग में है; दो अवयव तुल्य हैं यदि और केवल यदि उनके वर्ग बराबर हैं; और उभयनिष्ठ अवयव वाले दो वर्ग बराबर हैं। प्रत्येक निष्कर्ष तुल्यता के तीन गुणों में से एक को किसी वर्ग के मनमाने अवयव पर लागू करने से निकलता है।

प्रमाण

$a \sim a \rightarrow \resaltar{a \in C(a)}$
स्वतुल्यता से $a \sim a$ , और वर्ग की परिभाषा से $a$ , $C(a)$ में है; इसलिए कोई भी वर्ग रिक्त नहीं है।
$x \sim a \wedge a \sim b \rightarrow \resaltar{x \sim b}$
मान लीजिए $a \sim b$ और $x$ , $C(a)$ में है। संक्रामकता से, $x \sim a$ और $a \sim b$ से $x \sim b$ निकलता है; इसलिए $C(a) \subseteq C(b)$ ।
$a \sim b \rightarrow \dato{eq}{C(a) = C(b)}$
सममितता से $b \sim a$ भी है, और वही युक्ति $C(b) \subseteq C(a)$ देती है। द्विपक्षीय समावेश से वर्ग बराबर हैं।
$a \in C(a) = C(b) \rightarrow a \sim b$
विलोमतः, यदि $C(a) = C(b)$ , तो अवयव $a$ , $C(a)$ में है, और इसलिए $C(b)$ में, अर्थात् $a \sim b$ ।
$x \in C(a) \cap C(b) \rightarrow C(a) = C(b)$
यदि $x$ , $C(a)$ में और $C(b)$ में है, तो सममितता और संक्रामकता से $a \sim x$ और $x \sim b$ से $a \sim b$ मिलता है, और पिछले निष्कर्ष से वर्ग बराबर हैं।

इसलिए वर्ग समुच्चय को बिना परस्पर अतिव्याप्ति वाले खंडों में बाँटते हैं। समुच्चय को बाँटने का यह ढंग अपनी अलग परिभाषा के योग्य है।

परिभाषा (खंडन)। समुच्चय $A$ का खंडन $A$ के उपसमुच्चयों का एक समुच्चय है, जिन्हें खंड कहते हैं, जो अरिक्त और युग्मशः असंयुक्त हैं और जिनका सम्मिलन $A$ है; तुल्य रूप से, $A$ का प्रत्येक अवयव ठीक एक खंड में है।

प्रमेयतुल्यता संबंध और खंडन

$A$ पर किसी तुल्यता संबंध के वर्ग $A$ का एक खंडन बनाते हैं। विलोमतः, यदि $\Pi$ , $A$ का खंडन है, तो संबंध “एक ही खंड में होना” एक तुल्यता संबंध है, जिसके वर्ग ठीक-ठीक $\Pi$ के खंड हैं। पहला भाग पिछली प्रमेयिका है; दूसरा इस शर्त से तीनों गुणों की जाँच करता है कि प्रत्येक अवयव एक ही खंड में है। चित्र संबंध “ $3$ से भाग देने पर समान शेषफल छोड़ना” को $1$ से $9$ तक की संख्याओं के समुच्चय पर अनुसरण करता है।

प्रमाण

$(\forall a \in A)\,(a \in \resaltar{C(a)})$
प्रमेयिका से कोई वर्ग रिक्त नहीं है और प्रत्येक अवयव अपने वर्ग में है, इसलिए वर्गों का सम्मिलन $A$ है।
$C(a) \neq C(b) \rightarrow C(a) \cap C(b) = \resaltar{\emptyset}$
प्रमेयिका से दो अलग वर्गों में कोई उभयनिष्ठ अवयव नहीं है। इसलिए वर्ग एक खंडन बनाते हैं।
$a \sim b \leftrightarrow (\exists X \in \Pi)(a \in X \wedge b \in X)$
विलोमतः, मान लीजिए $\Pi$ एक खंडन है, और $a \sim b$ लिखें जब $a$ और $b$ एक ही खंड में हों। प्रत्येक अवयव किसी खंड में है, और इसलिए स्वयं के साथ एक ही खंड में है: संबंध स्वतुल्य है। सममितता तुरंत स्पष्ट है, क्योंकि शर्त इस पर निर्भर नहीं करती कि $a$ और $b$ किस क्रम में कहे जाते हैं।
$b \in X \cap Y \rightarrow X = Y \rightarrow a \sim c$
संक्रामकता: यदि $a$ और $b$ खंड $X$ में हैं, और $b$ और $c$ खंड $Y$ में, तो $b$ , $X$ में भी है और $Y$ में भी; चूँकि प्रत्येक अवयव एक ही खंड में है, $X = Y$ , और $a$ और $c$ एक ही खंड में हैं।
$a \in X \rightarrow C(a) = \resaltar{X}$
अंत में, यदि $a$ खंड $X$ में है, तो $a$ का वर्ग उन अवयवों से बना है जो $a$ के साथ एक ही खंड में हैं, अर्थात् $X$ के अवयवों से: वर्ग खंड ही हैं।

इसलिए $A$ पर एक तुल्यता संबंध देना और $A$ का एक खंडन देना एक ही बात कहने के दो ढंग हैं; हल किया गया प्रश्न 4 इसका उपयोग तुल्यता संबंधों को गिनने में करता है। भागफल समुच्चय वह खंडन है जिसे एक नए समुच्चय के रूप में देखा जाए: $A$ से $A/{\sim}$ पर जाने पर तुल्य अवयव एक में मिल जाते हैं।

उदाहरणवह संबंध जिससे पूर्णांक रचे जाएँगे

प्राकृत संख्याओं के युग्मों के समुच्चय $\mathbb{N} \times \mathbb{N}$ में $(a, b) \sim (c, d)$ परिभाषित किया जाता है जब $a + d = b + c$ । यह एक तुल्यता संबंध है, जैसा कि पूर्णांकों वाले पाठ में सिद्ध किया जाता है। $(5, 2)$ , $(1, 1)$ और $(2, 5)$ के वर्गों के कुछ प्रतिनिधि निकालिए, और युग्मों के ग्रिड में वर्गों का वर्णन कीजिए।

प्रमाण

$(a, b) \sim (c, d) \leftrightarrow \resaltar{a + d = b + c}$
युग्म $(a, b)$ अभी न किए गए व्यवकलन $a - b$ को दर्शाता है, जो प्राकृत संख्याओं में संभवतः अस्तित्व में न हो; शर्त $a + d = b + c$ कहती है कि दोनों युग्म एक ही व्यवकलन दर्शाते हैं, कोई भी व्यवकलन लिखे बिना।
$C(5, 2) = \{ (4, 1), (5, 2), (6, 3), (7, 4), \ldots \}$
$(5, 2)$ के वर्ग में वे युग्म हैं जो अंतर $3$ का वर्णन करते हैं। उदाहरण के लिए $(4, 1)$ , क्योंकि $5 + 1 = 2 + 4$ ।
$C(1, 1) = \{ (1, 1), (2, 2), (3, 3), \ldots \}$
$(1, 1)$ का वर्ग बराबर घटकों वाले युग्मों से बना है, क्योंकि समता $1 + b = 1 + a$ के लिए $a = b$ आवश्यक है: यह ग्रिड का विकर्ण है।
$C(2, 5) = \{ (1, 4), (2, 5), (3, 6), \ldots \}$
$(2, 5)$ का वर्ग एक ऐसे अंतर का वर्णन करता है जो अभी अस्तित्व में नहीं है, भावी $-3$ ।
$\mathbb{Z} = \left( \mathbb{N} \times \mathbb{N} \right) / {\sim}$
प्रत्येक वर्ग विकर्ण के समांतर एक रेखा पर स्थित युग्मों का समुच्चय है, और प्रमेय से ये रेखाएँ ग्रिड का एक खंडन बनाती हैं। परिभाषा से, एक पूर्णांक इन वर्गों में से एक होगा: $\mathbb{Z}$ भागफल समुच्चय है।

इसी प्रकार, परिमेय संख्याओं वाले पाठ में दो भिन्न $(p, q)$ और $(r, s)$ तुल्य हैं जब $ps = qr$ , और एक परिमेय संख्या एक वर्ग है; और सर्वांगसमताओं वाले पाठ में मापांक $n$ के शेषफल वर्ग पूर्णांकों के बीच एक तुल्यता संबंध के वर्ग हैं।

क्रम संबंध

पिछले उदाहरण का विभाज्यता संबंध सममित नहीं था, बल्कि प्रतिसममित: यह अवयवों को एक नहीं मानता, बल्कि उन्हें क्रम में रखता है। ऐसे संबंधों का अपना नाम है।

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

क्रम के उदाहरण हैं: प्राकृत संख्याओं के बीच संबंध $\leq$ , जो प्राकृत संख्याओं की संक्रियाओं वाले पाठ में सिद्ध त्रिभाजिता से पूर्ण है; समावेश, जो अपने गुणों के प्रमेय से क्रम है और पूर्ण नहीं है, क्योंकि $\{1\}$ और $\{2\}$ तुलनीय नहीं हैं; और प्राकृत संख्याओं के बीच विभाज्यता, जिसकी प्रतिसममितता विभाज्यता वाले पाठ में सिद्ध की जाती है, और जो पूर्ण नहीं है, क्योंकि न $2 \mid 3$ है न $3 \mid 2$ । परिमित क्रम को हासे आरेख से खींचा जाता है: प्रत्येक अवयव के लिए एक बिंदु, $b$ को $a$ से ऊपर रखते हुए जब $a$ , $b$ से पूर्ववर्ती हो, और एक रेखाखंड जब दोनों के बीच कोई अन्य अवयव न हो; संक्रामकता के कारण शेष रेखाखंड छोड़े जा सकते हैं।

परिभाषा (परिबंध और चरम अवयव)। मान लीजिए $\preceq$ , $A$ पर एक क्रम है और $X$ , $A$ का उपसमुच्चय है। $X$ के परिबंध और चरम अवयव इस प्रकार परिभाषित हैं।

अवयव $c$ जो $A$ में है, $X$ का निम्न परिबंध है यदि वह $X$ के सभी अवयवों से पूर्ववर्ती है, और उपरि परिबंध है यदि $X$ के सभी अवयव उससे पूर्ववर्ती हैं।
$X$ का सबसे छोटा अवयव $X$ का वह निम्न परिबंध है जो $X$ में है, और सबसे बड़ा अवयव वह उपरि परिबंध है जो $X$ में है।
अवयव $m$ जो $X$ में है, अल्पिष्ठ है यदि $X$ का उससे अलग कोई भी अवयव उससे पूर्ववर्ती नहीं है, और उच्चिष्ठ है यदि वह $X$ के स्वयं से अलग किसी भी अवयव से पूर्ववर्ती नहीं है।
$X$ का महत्तम निम्न परिबंध उसके निम्न परिबंधों के समुच्चय का सबसे बड़ा अवयव है, और न्यूनतम उपरि परिबंध उसके उपरि परिबंधों के समुच्चय का सबसे छोटा अवयव है, यदि ये अस्तित्व में हों।

साध्यसबसे छोटा अवयव अद्वितीय है और एकमात्र अल्पिष्ठ अवयव है

यदि किसी क्रमित समुच्चय के उपसमुच्चय $X$ का सबसे छोटा अवयव है, तो वह अद्वितीय है और $X$ का एकमात्र अल्पिष्ठ अवयव है। यदि क्रम पूर्ण है, तो $X$ का प्रत्येक अल्पिष्ठ अवयव उसका सबसे छोटा अवयव है। सबसे बड़े अवयव और उच्चिष्ठ अवयवों के लिए भी यही सत्य है। अद्वितीयता प्रतिसममितता पर टिकी है, और अंतिम निष्कर्ष तुलनीयता पर।

प्रमाण

$m \preceq n \wedge n \preceq m \rightarrow \resaltar{m = n}$
यदि $m$ और $n$ दोनों $X$ के सबसे छोटे अवयव हैं, तो प्रत्येक $X$ में है और उसके सभी अवयवों से पूर्ववर्ती है; विशेष रूप से, प्रत्येक दूसरे से पूर्ववर्ती है, और प्रतिसममितता से वे बराबर हैं।
$x \preceq m \wedge m \preceq x \rightarrow x = m$
सबसे छोटा अवयव $m$ अल्पिष्ठ है: यदि $x$ जो $X$ में है, $m$ से पूर्ववर्ती है, तो चूँकि $m \preceq x$ भी है, प्रतिसममितता से $x = m$ ।
$m \preceq n \rightarrow m = n$
यदि $n$ अल्पिष्ठ है, तो चूँकि $m$ , $n$ से पूर्ववर्ती है और $X$ में है, अल्पिष्ठ की परिभाषा से $m = n$ होना ही चाहिए: कोई अन्य अल्पिष्ठ अवयव नहीं है।
$(\forall x \in X)\,(\resaltar{m \preceq x})$
यदि क्रम पूर्ण है और $m$ अल्पिष्ठ है, तो प्रत्येक $x$ के लिए जो $X$ में है, $m \preceq x$ या $x \preceq m$ ; दूसरी स्थिति में अल्पिष्ठता से $x = m$ । दोनों स्थितियों में $m \preceq x$ , इसलिए $m$ सबसे छोटा अवयव है।

उदाहरणविभाज्यता से क्रमित 12 के भाजक

समुच्चय $A = \{1, 2, 3, 4, 6, 12\}$ में, जो $12$ के भाजकों का समुच्चय है और विभाज्यता से क्रमित है, उपसमुच्चय $X = \{2, 3, 4, 6\}$ पर विचार कीजिए। हासे आरेख खींचिए, और $X$ के अल्पिष्ठ और उच्चिष्ठ अवयव, सबसे छोटा और सबसे बड़ा अवयव, उपरि और निम्न परिबंध, तथा महत्तम निम्न परिबंध और न्यूनतम उपरि परिबंध निर्धारित कीजिए।

प्रमाण

$1 \mid 2 \mid 4 \mid 12, \qquad 1 \mid 3 \mid 6 \mid 12$
आरेख में $1$ सबसे नीचे है, क्योंकि वह सभी को विभाजित करता है; उसके ऊपर $2$ और $3$ ; उनके ऊपर $4$ और $6$ ; और सबसे ऊपर $12$ । रेखाखंड जोड़ते हैं: $1$ को $2$ और $3$ से; $2$ को $4$ और $6$ से; $3$ को $6$ से; और $4$ तथा $6$ को $12$ से।
$\neg (2 \mid 3), \quad \neg (3 \mid 2)$
$X$ के अल्पिष्ठ अवयव $2$ और $3$ हैं: $X$ का कोई अन्य अवयव उन्हें विभाजित नहीं करता। चूँकि दो अल्पिष्ठ अवयव हैं, साध्य से $X$ का कोई सबसे छोटा अवयव नहीं है; क्रम पूर्ण नहीं है, क्योंकि $2$ और $3$ तुलनीय नहीं हैं।
$\neg (4 \mid 6), \quad \neg (6 \mid 4)$
उच्चिष्ठ अवयव $4$ और $6$ हैं, जो $X$ के किसी अन्य अवयव को विभाजित नहीं करते; सबसे बड़ा अवयव भी नहीं है।
$(\forall x \in X)\,(\resaltar{1} \mid x \wedge x \mid \resaltar{12})$
$X$ का $A$ में एकमात्र निम्न परिबंध $1$ है, जो इसलिए महत्तम निम्न परिबंध है; और एकमात्र उपरि परिबंध $12$ है, जो न्यूनतम उपरि परिबंध है। दोनों में से कोई $X$ में नहीं है।

इस प्रकार, सबसे छोटे और सबसे बड़े अवयव के बिना भी महत्तम निम्न परिबंध और न्यूनतम उपरि परिबंध हो सकते हैं। यह भेद वास्तविक संख्याओं की पहचान है: संख्या समुच्चयों वाले पाठ में पूर्णता के अभिगृहीत के रूप में स्वीकार किया जाता है कि वास्तविक संख्याओं के प्रत्येक अरिक्त, ऊपर से परिबद्ध समुच्चय का न्यूनतम उपरि परिबंध होता है, जो परिमेय संख्याओं के लिए सत्य नहीं है। दूसरी ओर, प्राकृत संख्याएँ सुक्रम सिद्धांत को संतुष्ट करती हैं, जो योग और आगमन वाले पाठ में सिद्ध किया जाता है: प्राकृत संख्याओं के प्रत्येक अरिक्त समुच्चय का सबसे छोटा अवयव होता है।

फलन

संबंध के रूप में फलन

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

परिभाषा (फलन)। एक फलन $f$ जो $A$ से $B$ में है, $A$ से $B$ में एक संबंध है जो $A$ के प्रत्येक अवयव को $B$ के ठीक एक अवयव से संबंधित करता है:

(\forall a \in A)(\exists! b \in B)\,((a, b) \in f)

उस एकमात्र अवयव को $a$ का प्रतिबिंब कहते हैं और $f(a)$ लिखते हैं; $f : A \to B$ लिखा जाता है, और कहा जाता है कि $A$ , $f$ का प्रांत है और $B$ उसका सहप्रांत।

दो फलन बराबर होते हैं जब उनका प्रांत समान हो, सहप्रांत समान हो और प्रत्येक अवयव पर प्रतिबिंब समान हो। $A$ का तत्समक फलन, जिसे $I_A$ लिखते हैं, प्रत्येक अवयव को उसी के स्थान पर रहने देता है: यह $A \times A$ का विकर्ण है, और $I_A(x) = x$ प्रत्येक $x$ के लिए जो $A$ में है।

परिभाषा (प्रतिबिंब और पूर्व-प्रतिबिंब)। मान लीजिए $f : A \to B$ । उपसमुच्चय $X$ का, जो $A$ में अंतर्विष्ट है, प्रतिबिंब उसके अवयवों के प्रतिबिंबों का समुच्चय है, और उपसमुच्चय $Y$ का, जो $B$ में अंतर्विष्ट है, पूर्व-प्रतिबिंब $A$ के उन अवयवों का समुच्चय है जिनका प्रतिबिंब $Y$ में है:

f(X) = \{ f(x) : x \in X \}, \qquad f^{-1}(Y) = \{ x \in A : f(x) \in Y \}

पूरे प्रांत का प्रतिबिंब, $f(A)$ , $f$ का परिसर कहलाता है और $\operatorname{ran}(f)$ लिखा जाता है।

पूर्व-प्रतिबिंब का संकेतन यह नहीं मानता कि $f$ का प्रतिलोम है: पूर्व-प्रतिबिंब किसी भी फलन के लिए अस्तित्व में है।

उदाहरणभाजकों की संख्या का फलन

मान लीजिए $f : \{1, 2, 3, 4, 5, 6\} \to \{1, 2, 3, 4\}$ वह फलन है जो प्रत्येक संख्या को उसके भाजकों की संख्या निर्दिष्ट करता है। उसके मान, उसका परिसर और $\{2\}$ का पूर्व-प्रतिबिंब निकालिए, और $f(X \cap Y)$ की तुलना $f(X) \cap f(Y)$ से कीजिए, जहाँ $X = \{2, 4\}$ और $Y = \{3, 4\}$ ।

प्रमाण

$f(1) = 1, \ f(2) = f(3) = f(5) = 2, \ f(4) = 3, \ f(6) = 4$
$1$ का एक भाजक है; $2$ , $3$ और $5$ के दो-दो; $4$ के तीन हैं, $1$ , $2$ और $4$ ; और $6$ के चार हैं, $1$ , $2$ , $3$ और $6$ ।
$\operatorname{ran}(f) = \{1, 2, 3, 4\}$
सहप्रांत का प्रत्येक अवयव किसी न किसी का प्रतिबिंब है: परिसर पूरा सहप्रांत है।
$f^{-1}(\{2\}) = \{2, 3, 5\}$
ठीक दो भाजकों वाली संख्याएँ प्रांत की अभाज्य संख्याएँ हैं।
$f(X \resaltar{\cap} Y) = f(\{4\}) = \{3\}$
$X$ और $Y$ का सर्वनिष्ठ $\{4\}$ है, जिसका प्रतिबिंब $\{3\}$ है।
$f(X) \resaltar{\cap} f(Y) = \{2, 3\} \neq \{3\}$
दूसरी ओर, $f(X) = f(Y) = \{2, 3\}$ , क्योंकि $2$ और $3$ का प्रतिबिंब समान है। व्यापक रूप से केवल समावेश $f(X \cap Y) \subseteq f(X) \cap f(Y)$ सत्य है, क्योंकि कोई $x$ जो $X \cap Y$ में है, दोनों प्रतिबिंबों के लिए साक्षी बनता है; समता तब विफल होती है जब साक्षी अलग हों, जैसे यहाँ $2$ और $3$ ।

संघटन

यदि $f : A \to B$ और $g : B \to C$ , तो प्रत्येक $x$ जो $A$ में है, उसका एक प्रतिबिंब $f(x)$ है जो $B$ में है, और उसका फिर $C$ में एक प्रतिबिंब है। $g$ का $f$ के साथ संघटन फलन $g \circ f : A \to C$ है, जो पहले $f$ और फिर $g$ लागू करता है:

\left( g \circ f \right)(x) = g(f(x))

यह एक फलन है, क्योंकि प्रत्येक $x$ के संगत एक ही $f(x)$ है और उसके संगत एक ही $g(f(x))$ । लिखने का क्रम लागू करने के क्रम का उलटा है: $g \circ f$ में पहले दाईं ओर का फलन काम करता है। संघटन क्रमविनिमेय नहीं है: यदि प्राकृत संख्याओं में $f(n) = 2n$ और $g(n) = n + 1$ , तो $(g \circ f)(n) = 2n + 1$ , जो विषम है, और $(f \circ g)(n) = 2n + 2$ , जो सम है। तत्समक फलन दोनों ओर उदासीन है, क्योंकि $f(I_A(x)) = f(x)$ और $I_B(f(x)) = f(x)$ :

f \circ I_A = f, \qquad I_B \circ f = f

प्रमेयसंघटन की साहचर्यता

यदि $f : A \to B$ , $g : B \to C$ और $h : C \to D$ , तो फलन $h \circ (g \circ f)$ और $(h \circ g) \circ f$ बराबर हैं। दोनों $A$ से $D$ में जाते हैं; यह जाँचना पर्याप्त है कि वे प्रत्येक अवयव पर एक ही मान लेते हैं, संघटन की परिभाषा को दो बार खोलकर। चित्र फलनों को चार स्तंभों के बीच तीरों के रूप में दर्शाता है।

प्रमाण

$\left( h \circ \left( g \circ f \right) \right)(x) = h\left( \resaltar{\left( g \circ f \right)(x)} \right)$
मान लीजिए $x$ , $A$ का कोई मनमाना अवयव है। संघटन की परिभाषा से, जो $h$ और $g \circ f$ पर लागू है।
$= h\left( \resaltar{g(f(x))} \right)$
फिर से परिभाषा से, अब $g \circ f$ पर लागू।
$\left( \left( h \circ g \right) \circ f \right)(x) = \left( h \circ g \right)\left( \resaltar{f(x)} \right)$
दूसरी ओर, $h \circ g$ और $f$ पर लागू परिभाषा से।
$= \resaltar{h(g(f(x)))}$
और $h \circ g$ पर, अवयव $f(x)$ पर, लागू परिभाषा से।
$h \circ \left( g \circ f \right) = \left( h \circ g \right) \circ f$
दोनों फलनों का प्रांत, सहप्रांत और मान समान हैं: वे बराबर हैं। इसलिए कोष्ठकों के बिना $h \circ g \circ f$ लिखा जाता है।

एकैकी, आच्छादक और एकैकी आच्छादक फलन

परिभाषा। कोई फलन $f : A \to B$ एकैकी है जब अलग अवयवों के प्रतिबिंब अलग हों, या, प्रतिपरिवर्तन से, जब प्रतिबिंबों की समता अवयवों की समता को निहित करे; आच्छादक है जब $B$ का प्रत्येक अवयव $A$ के किसी अवयव का प्रतिबिंब हो, अर्थात् जब $\operatorname{ran}(f) = B$ ; और एकैकी आच्छादक, या एक एकैकी संगतता, है जब वह एकैकी और आच्छादक हो:

(\forall x, y \in A)\,(f(x) = f(y) \rightarrow x = y), \qquad (\forall b \in B)(\exists x \in A)\,(f(x) = b)

उदाहरण का भाजकों की संख्या का फलन आच्छादक है और एकैकी नहीं है। प्राकृत संख्याओं से प्राकृत संख्याओं में फलन $n \mapsto 2n$ एकैकी है और आच्छादक नहीं है, क्योंकि $1$ किसी प्राकृत संख्या का दुगुना नहीं है। अगले पाठ का परवर्ती फलन, पियानो के चौथे अभिगृहीत से, $\mathbb{N}$ से $\mathbb{N}$ में एक एकैकी फलन है, और तीसरे अभिगृहीत से आच्छादक नहीं है, क्योंकि $1$ किसी प्राकृत संख्या का प्रतिबिंब नहीं है। आच्छादकता घोषित सहप्रांत पर निर्भर करती है। एकैकी संगतता दो समुच्चयों के अवयवों को बिना किसी को दोहराए या छोड़े युग्मित करती है; इसीलिए संचय-सिद्धांत का पाठ परिभाषित करता है कि $A$ के $n$ अवयव हैं जब $\{1, 2, \ldots, n\}$ से $A$ में एक एकैकी संगतता अस्तित्व में हो।

प्रमेयसंघटन एकैकीपन और आच्छादकता को बनाए रखता है

मान लीजिए $f : A \to B$ और $g : B \to C$ । यदि $f$ और $g$ एकैकी हैं, तो $g \circ f$ एकैकी है; यदि $f$ और $g$ आच्छादक हैं, तो $g \circ f$ आच्छादक है; और इसलिए, यदि दोनों एकैकी आच्छादक हैं, तो $g \circ f$ एकैकी आच्छादक है। एकैकीपन के लिए संघटन के क्रम में पीछे की ओर, $C$ से $A$ तक, चला जाता है; आच्छादकता के लिए भी, पर पूर्व-प्रतिबिंब खोजते हुए। चित्र तीनों स्तंभ दिखाता है।

प्रमाण

$g(f(x)) = g(f(y))$
एकैकीपन: मान लीजिए $x$ और $y$ , जो $A$ में हैं, का $g \circ f$ के अंतर्गत प्रतिबिंब समान है।
$\dato{fa}{f(x) = f(y)}$
चूँकि $g$ एकैकी है, अवयव $f(x)$ और $f(y)$ , जिनका $g$ के अंतर्गत प्रतिबिंब समान है, बराबर हैं।
$\resaltar{f(x) = f(y)} \rightarrow x = y$
चूँकि $f$ एकैकी है, $x = y$ । इसलिए $g \circ f$ एकैकी है।
$\dato{b}{g(b) = c}, \quad \dato{a}{f(a) = b}$
आच्छादकता: मान लीजिए $c$ जो $C$ में है। चूँकि $g$ आच्छादक है, कोई $b$ है जो $B$ में है, जिसके लिए $g(b) = c$ ; चूँकि $f$ आच्छादक है, कोई $a$ है जो $A$ में है, जिसके लिए $f(a) = b$ ।
$\left( g \circ f \right)(a) = g(\resaltar{f(a)}) = g(\resaltar{b}) = c$
वह $a$ संघटन के अंतर्गत $c$ का एक पूर्व-प्रतिबिंब है। इसलिए $g \circ f$ आच्छादक है, और यदि दोनों फलन एकैकी आच्छादक हैं, तो संघटन भी है।

प्रतिलोम फलन

कोई फलन $g : B \to A$ , $f : A \to B$ को पलटता है जब, $f$ के बाद लागू होने पर, वह प्रत्येक अवयव को उसके आरंभ बिंदु पर लौटा देता है, अर्थात् जब $g \circ f = I_A$ ; और $f$ बदले में $g$ को पलटता है जब $f \circ g = I_B$ । जो फलन दोनों समताओं को पूरा करता है, उसे $f$ का प्रतिलोम कहते हैं। अगला प्रमेय बताता है कि किन फलनों का प्रतिलोम होता है।

प्रमेयकोई फलन एकैकी आच्छादक है यदि और केवल यदि उसका प्रतिलोम है, और प्रतिलोम अद्वितीय है

कोई फलन $f : A \to B$ एकैकी आच्छादक है यदि और केवल यदि कोई फलन $g : B \to A$ है जिसके लिए $g \circ f = I_A$ और $f \circ g = I_B$ । वह फलन $g$ अद्वितीय है; उसे $f$ का प्रतिलोम फलन कहते हैं और $f^{-1}$ लिखते हैं। इसके अतिरिक्त, $f^{-1}$ एकैकी आच्छादक है और उसका प्रतिलोम $f$ है। प्रतिलोम रचने के लिए $f$ के युग्मों को उलटा जाता है; अद्वितीयता के लिए संघटन की साहचर्यता का उपयोग किया जाता है। चित्र चार-चार अवयवों वाले दो समुच्चयों के बीच एक एकैकी संगतता का अनुसरण करता है।

प्रमाण

$g = \{ (b, a) : (a, b) \in f \}, \quad \dato{g}{g(b) = a \leftrightarrow f(a) = b}$
मान लीजिए $f$ एकैकी आच्छादक है। प्रत्येक $b$ के लिए जो $B$ में है, कोई $a$ है जिसके लिए $f(a) = b$ , क्योंकि $f$ आच्छादक है, और केवल एक, क्योंकि $f$ एकैकी है। इसलिए $f$ के युग्मों को उलटकर प्राप्त संबंध $B$ से $A$ में एक फलन है।
$g(f(a)) = \resaltar{a}, \qquad f(g(b)) = \resaltar{b}$
$g$ की परिभाषा से, $f$ और फिर $g$ लागू करने पर प्रत्येक $a$ लौट आता है, और $g$ और फिर $f$ लागू करने पर प्रत्येक $b$ लौट आता है।
$x = g(f(x)) = g(\resaltar{f(y)}) = y$
विलोमतः, मान लीजिए $g$ अस्तित्व में है। यदि $f(x) = f(y)$ , तो $g$ लागू करने पर $x = y$ मिलता है: फलन $f$ एकैकी है।
$f(\resaltar{g(b)}) = b$
प्रत्येक $b$ के लिए जो $B$ में है, अवयव $g(b)$ , $b$ का एक पूर्व-प्रतिबिंब है: फलन $f$ आच्छादक है, और इसलिए एकैकी आच्छादक।
$g = g \circ I_B = g \circ \resaltar{\left( f \circ h \right)} = \resaltar{\left( g \circ f \right)} \circ h = I_A \circ h = h$
अद्वितीयता: यदि $g$ और $h$ दोनों समताओं को पूरा करते हैं, तो बीच में तत्समक फलन रखकर साहचर्यता से पुनः समूहित किया जाता है।
$f^{-1} \circ f = I_A, \qquad f \circ f^{-1} = I_B$
परिभाषा की दोनों समताएँ $f$ और $f^{-1}$ में सममित हैं: $f$ , $f^{-1}$ को दोनों दिशाओं में पलटता है। पहले सिद्ध भाग से $f^{-1}$ एकैकी आच्छादक है, और उसका प्रतिलोम $f$ है।

उपसिद्धांतएकैकी संगतता होना समुच्चयों के बीच एक तुल्यता है

किन्हीं भी समुच्चयों $A$ , $B$ और $C$ के लिए: $A$ से $A$ में एक एकैकी संगतता है; यदि $A$ से $B$ में एक एकैकी संगतता है, तो $B$ से $A$ में भी एक है; और यदि $A$ से $B$ में और $B$ से $C$ में एकैकी संगतताएँ हैं, तो $A$ से $C$ में भी एक है। विशेष रूप से, यदि $A$ के $n$ अवयव हैं और $A$ से $B$ में एक एकैकी संगतता है, तो $B$ के $n$ अवयव हैं। प्रत्येक कथन पिछले प्रमेयों में से एक है।

प्रमाण

$I_A \circ I_A = I_A$
तत्समक फलन एक एकैकी संगतता है, क्योंकि वह स्वयं अपना प्रतिलोम है।
$f : A \to B \rightarrow f^{-1} : B \to A$
एकैकी संगतता का प्रतिलोम एक एकैकी संगतता है, प्रतिलोम फलन के प्रमेय से।
$f : A \to B, \ g : B \to C \rightarrow g \circ f : A \to C$
दो एकैकी संगतताओं का संघटन एक एकैकी संगतता है, पिछले प्रमेय से।
$f \circ h : \{1, \ldots, n\} \to B$
यदि $h$ , $\{1, \ldots, n\}$ से $A$ में एक एकैकी संगतता है और $f$ , $A$ से $B$ में एक, तो संघटन $\{1, \ldots, n\}$ से $B$ में एक एकैकी संगतता है।

इसे तुल्यता संबंध नहीं कहा जाता, क्योंकि सभी समुच्चयों का कोई समुच्चय नहीं है जिस पर इसे परिभाषित किया जाए। फलनों की संक्रियाओं वाला पाठ इन परिणामों को वास्तविक फलनों पर लागू करेगा, और वहाँ प्रतिलोम का आलेख फलन के आलेख का विकर्ण के सापेक्ष सममित होगा, जो युग्मों को उलटने का ज्यामितीय रूप है।

हल प्रश्न

प्रश्न फलनों पर दो अभ्यासों से तुल्यताओं के तीन अनुप्रयोगों तक आगे बढ़ते हैं। दूसरा प्राकृत संख्याओं के गुणनफल और उसके विलोपन नियम का उपयोग करता है, जो प्राकृत संख्याओं की संक्रियाओं वाले पाठ में सिद्ध किया जाता है; तीसरा शेषफल सहित भाग का, जो विभाज्यता वाले पाठ में सिद्ध किया जाता है। इनमें से कोई भी परिणाम इस पाठ पर निर्भर नहीं करता।

हल किया गया प्रश्न 1संघटन अपने गुणनखंडों के बारे में क्या सिखाता है

मान लीजिए $f : A \to B$ और $g : B \to C$ । सिद्ध कीजिए कि यदि $g \circ f$ एकैकी है, तो $f$ एकैकी है, और यदि $g \circ f$ आच्छादक है, तो $g$ आच्छादक है। एक उदाहरण से दिखाइए कि $g \circ f$ एकैकी आच्छादक हो सकता है, जबकि न $g$ एकैकी हो और न $f$ आच्छादक।

हल

$f(x) = f(y) \rightarrow \resaltar{g(f(x)) = g(f(y))}$
मान लीजिए $x$ और $y$ , जो $A$ में हैं, के लिए $f(x) = f(y)$ । चूँकि $g$ एक फलन है, वह बराबर अवयवों को बराबर प्रतिबिंब निर्दिष्ट करता है।
$\left( g \circ f \right)(x) = \left( g \circ f \right)(y) \rightarrow x = y$
वह समता $g \circ f$ के अंतर्गत प्रतिबिंबों की समता है, जो एकैकी है: इसलिए $x = y$ , और $f$ एकैकी है।
$c = g(\resaltar{f(a)}) = g(b)$
मान लीजिए $c$ जो $C$ में है। चूँकि $g \circ f$ आच्छादक है, कोई $a$ है जिसके लिए $g(f(a)) = c$ ; अवयव $b = f(a)$ जो $B$ में है, $c$ का $g$ के अंतर्गत एक पूर्व-प्रतिबिंब है।
$\left( g \circ f \right)(1) = g(1) = 1$
उदाहरण के लिए, मान लीजिए $A = C = \{1\}$ और $B = \{1, 2\}$ , जहाँ $f(1) = 1$ और $g(1) = g(2) = 1$ । संघटन $\{1\}$ का तत्समक फलन है, जो एकैकी आच्छादक है।
$g(1) = g(2), \quad 2 \notin \operatorname{ran}(f)$
फिर भी, $g$ एकैकी नहीं है, क्योंकि $g(1) = g(2)$ , और $f$ आच्छादक नहीं है, क्योंकि $2$ किसी का प्रतिबिंब नहीं है। संघटन जो आगे पहुँचाता है वह पहले गुणनखंड का एकैकीपन और दूसरे की आच्छादकता है, और कुछ नहीं।

हल किया गया प्रश्न 2जितनी प्राकृत संख्याएँ, उतनी ही सम संख्याएँ

मान लीजिए $P = \{ m \in \mathbb{N} : (\exists k \in \mathbb{N})(m = 2k) \}$ सम संख्याओं का समुच्चय है। $\mathbb{N}$ से $P$ में एक एकैकी संगतता उसके प्रतिलोम सहित रचिए, और ध्यान दीजिए कि $P$ , $\mathbb{N}$ का उचित उपसमुच्चय है।

हल

$\dato{f}{f(n) = 2n} \in P$
हम दुगुना करने का प्रस्ताव करते हैं: $f(n) = 2n$ । यह $\mathbb{N}$ से $P$ में एक फलन है, क्योंकि $2n$ सम है, साक्षी $k = n$ के साथ।
$2n = 2m \rightarrow \resaltar{n = m}$
एकैकीपन: यदि $2n = 2m$ , तो प्राकृत संख्याओं के गुणनफल के विलोपन नियम से $n = m$ ।
$m = 2k = f(\resaltar{k})$
आच्छादकता: प्रत्येक $m$ जो $P$ में है, $2k$ के रूप का है जहाँ $k$ एक प्राकृत संख्या है, और इसलिए $k$ का प्रतिबिंब है।
$f^{-1}(m) = \frac{m}{2}, \qquad f^{-1}(f(n)) = \frac{2n}{2} = n$
प्रतिलोम फलन के प्रमेय से $f$ का प्रतिलोम है: वह जो प्रत्येक सम संख्या को उसका आधा निर्दिष्ट करता है, जो पिछले चरण की प्राकृत संख्या $k$ है, विलोपन नियम से अद्वितीय।
$1 \notin P, \qquad P \subseteq \mathbb{N}, \quad P \neq \mathbb{N}$
फिर भी, $P$ , $\mathbb{N}$ का उचित उपसमुच्चय है: $1$ सम नहीं है, क्योंकि $2k = k + k \geq 1 + 1 = 2$ प्रत्येक प्राकृत संख्या $k$ के लिए।

यह परिणाम इस अंतर्ज्ञान के विपरीत है कि भाग पूर्ण से छोटा होता है, जिसे गैलीलियो ने 1638 में ही प्राकृत संख्याओं को उनके वर्गों से युग्मित करते हुए देख लिया था। यह कि कोई भी परिमित समुच्चय अपने किसी उचित उपसमुच्चय के साथ एकैकी संगतता में नहीं होता, कपोत-कोटर सिद्धांत का एक रूप है, जिसे संचय-सिद्धांत का पाठ अवयवों की संख्या की अद्वितीयता के साथ बिना उपपत्ति स्वीकार करता है; यह सिद्धांत स्वीकार करने पर $\mathbb{N}$ परिमित नहीं है। डेडेकिंड ने ठीक इसी गुण को अनंत समुच्चय की परिभाषा के रूप में लिया, और पियानो के अभिगृहीतों वाला पाठ दिखाता है कि $\mathbb{N}$ इसे संतुष्ट करता है।

हल किया गया प्रश्न 3सप्ताह का दिन

1 जनवरी 2026 गुरुवार था। हम वर्ष 2026 के दिनों को $1$ से $365$ तक क्रमांकित करते हैं और कहते हैं कि दो दिन तुल्य हैं जब उनकी संख्याएँ $7$ से भाग देने पर समान शेषफल छोड़ती हैं। सिद्ध कीजिए कि यह एक तुल्यता संबंध है, उसके वर्गों का वर्णन कीजिए, और निर्धारित कीजिए कि 5 अक्टूबर 2026 को सप्ताह का कौन-सा दिन है और 5 अक्टूबर 2027 को कौन-सा दिन होगा।

हल

$n \sim m \leftrightarrow \resaltar{g(n) = g(m)}$
मान लीजिए $g(n)$ , $n$ को $7$ से भाग देने का शेषफल है, जो शेषफल सहित भाग के प्रमेय से अद्वितीय है। संबंध $g(n) = g(m)$ है, और यह समता से उसके तीनों गुण विरासत में पाता है: $g(n) = g(n)$ ; यदि $g(n) = g(m)$ , तो $g(m) = g(n)$ ; और यदि $g(n) = g(m)$ और $g(m) = g(p)$ , तो $g(n) = g(p)$ ।
$C(1) = \{1, 8, 15, \ldots, 365\}, \quad \ldots, \quad C(7) = \{7, 14, \ldots, 364\}$
संभावित शेषफल $0, 1, \ldots, 6$ हैं, और प्रत्येक प्राप्त होता है, इसलिए सात वर्ग हैं, सात स्तंभों वाले किसी कैलेंडर के सात स्तंभ। चूँकि सप्ताह हर सात दिनों में दोहराता है, दो तुल्य दिन सप्ताह के एक ही दिन पड़ते हैं।
$31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 5 = \dato{n}{278}$
5 अक्टूबर वर्ष का $278$ वाँ दिन है, क्योंकि पिछले नौ महीनों के दिनों का योग $273$ है।
$278 = 7 \cdot 39 + \resaltar{5} \rightarrow 278 \sim 5$
हम $7$ से भाग देते हैं: शेषफल $5$ है, इसलिए 5 अक्टूबर दिन $5$ , अर्थात् 5 जनवरी, के वर्ग में है।
$C(278) = C(5)$
दिन $1$ गुरुवार था, और इसलिए चार दिन बाद का दिन $5$ सोमवार था: 5 अक्टूबर 2026 सोमवार है।
$365 = 7 \cdot 52 + \resaltar{1}$
वर्ष 2026 में $365$ दिन हैं, और $365 = 7 \cdot 52 + 1$ : अगले वर्ष की वही तिथि $365$ दिन बाद पड़ती है, अर्थात् सप्ताह का एक दिन आगे। 5 अक्टूबर 2027 मंगलवार होगा।

हल किया गया प्रश्न 4चार अवयवों वाले समुच्चय के तुल्यता संबंध

समुच्चय $\{1, 2, 3, 4\}$ पर कितने तुल्यता संबंध हैं?

हल

$a \sim b \leftrightarrow (\exists X \in \Pi)(a \in X \wedge b \in X)$
तुल्यता संबंधों और खंडनों के प्रमेय से, प्रत्येक तुल्यता संबंध वर्गों में अपना खंडन निर्धारित करता है, और प्रत्येक खंडन $\Pi$ तुल्यता संबंध “एक ही खंड में होना” निर्धारित करता है, जिसके वर्ग खंड हैं; दोनों संगतियाँ एक-दूसरे को पलटती हैं। इसलिए खंडनों को गिनना पर्याप्त है, जिन्हें हम उनके खंडों के आकार के अनुसार वर्गीकृत करते हैं।
$\{1, 2, 3, 4\}$
चार अवयवों का एक ही खंड: एक खंडन, वह जिसका एक ही वर्ग है।
$\{2, 3, 4\}, \{1\}; \quad \{1, 3, 4\}, \{2\}; \quad \{1, 2, 4\}, \{3\}; \quad \{1, 2, 3\}, \{4\}$
तीन अवयवों का एक खंड और एक अवयव का एक: उतने जितने अकेले अवयव को चुनने के ढंग हैं, चार।
$\{1, 2\}, \{3, 4\}; \quad \{1, 3\}, \{2, 4\}; \quad \{1, 4\}, \{2, 3\}$
दो-दो अवयवों के दो खंड: खंडन $1$ के साथी से निर्धारित होता है, जो $2$ , $3$ या $4$ हो सकता है; तीन।
$\{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}$
दो अवयवों का एक खंड और एक-एक अवयव के दो: खंडन उस युग्म से निर्धारित होता है जो दो अवयवों का खंड बनाता है, और ऐसे छह युग्म हैं।
$1 + 4 + 3 + 6 + 1 = 15$
एक-एक अवयव के चार खंड: एक खंडन, समता का। पाँचों प्रकारों को जोड़ने पर तुल्यता संबंधों की संख्या मिलती है।

$1$ , $2$ , $3$ , $4$ , $5$ अवयवों वाले समुच्चय के खंडनों की संख्याएँ $1$ , $2$ , $5$ , $15$ , $52$ हैं; इन्हें बेल संख्याएँ कहते हैं, और अभ्यास प्रश्न 2 पाँचवीं संख्या निकालता है।

हल किया गया प्रश्न 5प्रत्येक फलन एक वर्गीकरण है

मान लीजिए $f : A \to B$ एक फलन है। सिद्ध कीजिए कि संबंध $x \sim y$ , जो $f(x) = f(y)$ से परिभाषित है, एक तुल्यता संबंध है, और कि $f$ तीन फलनों का संघटन है: आच्छादक फलन $g$ जो प्रत्येक अवयव को उसके वर्ग पर ले जाता है, एक एकैकी संगतता $h$ जो भागफल समुच्चय से $f$ के परिसर में है, और एकैकी फलन $J$ जो परिसर के प्रत्येक अवयव को $B$ के भीतर स्वयं पर ले जाता है। इसे उदाहरण के भाजकों की संख्या के फलन पर लागू कीजिए।

हल

$C(x) = f^{-1}(\{ f(x) \})$
संबंध $f(x) = f(y)$ एक तुल्यता संबंध है, हल किए गए प्रश्न 3 वाली युक्ति से। उसके वर्ग परिसर के अवयवों के पूर्व-प्रतिबिंब हैं: $x$ का वर्ग उन अवयवों को इकट्ठा करता है जिनका प्रतिबिंब उसी के समान है। उदाहरण में वे $\{1\}$ , $\{2, 3, 5\}$ , $\{4\}$ और $\{6\}$ हैं।
$g : A \to A/{\sim}, \quad g(x) = C(x)$
फलन $g(x) = C(x)$ , $A$ से $A/{\sim}$ में जाता है और आच्छादक है, क्योंकि प्रत्येक वर्ग अपने किसी अवयव का वर्ग है।
$C(x) = C(y) \rightarrow \resaltar{f(x) = f(y)}$
हम $h(C(x)) = f(x)$ परिभाषित करते हैं। चूँकि एक वर्ग के कई प्रतिनिधि होते हैं, यह जाँचना होगा कि मान चुने गए प्रतिनिधि पर निर्भर नहीं करता: यदि $C(x) = C(y)$ , तो $x \sim y$ , अर्थात् $f(x) = f(y)$ ।
$h(C(x)) = h(C(y)) \rightarrow C(x) = C(y)$
फलन $h$ एकैकी है, क्योंकि पिछला सोपाधिक उलटा जा सकता है: यदि $f(x) = f(y)$ , तो $x \sim y$ और $C(x) = C(y)$ । यह परिसर पर आच्छादक है, क्योंकि प्रत्येक $f(x)$ , $h(C(x))$ है।
$\left( J \circ h \circ g \right)(x) = J(h(C(x))) = f(x)$
समावेशन फलन $J(b) = b$ , जो परिसर से $B$ में है, एकैकी है, और संघटन $f$ लौटाता है। उदाहरण में चारों वर्ग $1$ , $2$ , $3$ और $4$ पर जाते हैं; फलन एकैकी नहीं है क्योंकि वर्ग $\{2, 3, 5\}$ में तीन अवयव हैं।

यह प्रश्न दिखाता है कि प्रत्येक फलन अपने प्रांत का वर्गीकरण करता है, और विलोमतः, वर्गों की प्रमेयिका से, कि प्रत्येक तुल्यता संबंध किसी फलन के अंतर्गत संबंध “समान प्रतिबिंब होना” है, वह फलन जो प्रत्येक अवयव को उसके वर्ग पर ले जाता है। इस प्रकार, अंकन की कोई प्रणाली छात्रों को उनके अंकों के अनुसार वर्गों में बाँटती है, डाक कोड पतों को उनके क्षेत्र के अनुसार बाँटता है, और शेषफल फलन संख्याओं को उनके शेषफल के अनुसार बाँटता है।

अभ्यास प्रश्न

प्रत्येक प्रश्न के साथ एक संकेत है, जिसे स्वयं प्रयास करने के बाद ही खोलना उचित है; अंतिम उत्तर संकेत के बाद दिखाया जाता है।

अभ्यास प्रश्न 1किसी समुच्चय को कोष्ठक से बाहर कब निकाला जा सकता है

सिद्ध कीजिए कि किन्हीं भी समुच्चयों $A$ , $B$ और $C$ के लिए

A \cap \left( B \cup C \right) = \left( A \cap B \right) \cup C \leftrightarrow C \subseteq A

इसके अतिरिक्त $\{1, 2, 3\}$ पर एक ऐसे संबंध का उदाहरण दीजिए जो न सममित हो न प्रतिसममित।

संकेत

दाईं ओर के सोपाधिक के लिए, $x$ लीजिए जो $C$ में है: वह दाएँ पक्ष में है, इसलिए बाएँ पक्ष में, इसलिए $A$ में। दूसरे के लिए, प्रत्येक $x$ के लिए यह भेद करते हुए कि वह $B$ में है या $C$ में, द्विपक्षीय समावेश सिद्ध कीजिए। संबंध के लिए, एक युग्म को उसके सममित युग्म के साथ, और एक अन्य युग्म को उसके बिना, मिलाइए।

उत्तर

यदि समता सत्य है, तो $C$ दाएँ पक्ष में अंतर्विष्ट है, जो बाएँ पक्ष के बराबर है, जो $A$ में अंतर्विष्ट है। यदि $C \subseteq A$ , तो $A$ का कोई अवयव जो $B$ या $C$ में है, $A \cap B$ या $C$ में है, और विलोमतः $C$ का कोई अवयव $A$ में और $B \cup C$ में है। एक संबंध जो न सममित है न प्रतिसममित, यह है

\{ (1, 2), (2, 1), (2, 3) \}

विस्तृत हल

हल

$x \in C \rightarrow x \in \left( A \cap B \right) \cup C = \resaltar{A} \cap \left( B \cup C \right) \rightarrow x \in A$
यदि समता सत्य है और $x$ , $C$ में है, तो $x$ दाएँ पक्ष में है, जिसमें $C$ अंतर्विष्ट है; समता से वह बाएँ पक्ष में है, और विशेष रूप से $A$ में। इसलिए $C \subseteq A$ ।
$x \in A \wedge \left( x \in B \vee x \in C \right) \rightarrow \resaltar{x \in A \cap B} \vee \resaltar{x \in C}$
विलोमतः, मान लीजिए $C \subseteq A$ और $x$ बाएँ पक्ष का अवयव है: वह $A$ में है, और साथ ही $B$ या $C$ में। पहली स्थिति में वह $A \cap B$ में है; दूसरी में, $C$ में। दोनों में वह दाएँ पक्ष में है।
$x \in C \rightarrow x \in \resaltar{A} \cap \left( B \cup C \right)$
अब मान लीजिए $x$ दाएँ पक्ष का अवयव है। यदि वह $A \cap B$ में है, तो वह $A$ में और $B \cup C$ में है; यदि वह $C$ में है, तो वह $B \cup C$ में है और, परिकल्पना $C \subseteq A$ से, $A$ में भी।
$C \subseteq A \rightarrow A \cap \left( B \cup C \right) = \left( A \cap B \right) \cup C$
द्विपक्षीय समावेश से दोनों पक्ष बराबर हैं जब $C \subseteq A$ ; पहले चरण के साथ तुल्यता सिद्ध होती है।
$(2, 3) \in R, \ (3, 2) \notin R; \qquad (1, 2), (2, 1) \in R$
प्रस्तावित संबंध में युग्म $(2, 3)$ है और उसका सममित $(3, 2)$ नहीं, इसलिए वह सममित नहीं है; युग्म $(1, 2)$ और $(2, 1)$ हैं, और $1 \neq 2$ , इसलिए वह प्रतिसममित नहीं है।

अभ्यास प्रश्न 2पाँच अवयवों के खंडन

समुच्चय $\{1, 2, 3, 4, 5\}$ के तुल्यता संबंध गिनिए, और यह भी कि उनमें से कितनों के ठीक दो वर्ग हैं।

संकेत

हल किए गए प्रश्न 4 की तरह खंडनों को उनके खंडों के आकार के अनुसार वर्गीकृत कीजिए: सात प्रकार हैं, $5$ से $1 + 1 + 1 + 1 + 1$ तक। तीन के एक खंड और दो के एक खंड के लिए दो वाला खंड चुनना पर्याप्त है; दो-दो के दो खंडों और एक के एक खंड के लिए पहले अकेला अवयव चुनिए।

उत्तर

प्रकारों के अनुसार, $1 + 5 + 10 + 10 + 15 + 10 + 1$ ; दो वर्गों वाले खंडन प्रकार $4 + 1$ और $3 + 2$ के हैं, जिनका योग $5 + 10 = 15$ है:

1 + 5 + 10 + 10 + 15 + 10 + 1 = 52

अभ्यास प्रश्न 3संघटन का प्रतिलोम

मान लीजिए $f : A \to B$ और $g : B \to C$ एकैकी आच्छादक हैं। सिद्ध कीजिए कि $g \circ f$ का प्रतिलोम $f^{-1} \circ g^{-1}$ है, इसी क्रम में। इसे कपड़े पहनने पर लागू कीजिए: यदि $f$ मोज़े पहनना है और $g$ जूते पहनना, तो यह क्रिया किस क्रम में पलटी जाती है?

संकेत

प्रतिलोम की अद्वितीयता से, यह जाँचना पर्याप्त है कि $f^{-1} \circ g^{-1}$ का $g \circ f$ के साथ संघटन, दोनों क्रमों में, तत्समक फलन देता है; साहचर्यता से पुनः समूहित कीजिए ताकि $g^{-1}$ का $g$ से और $f$ का $f^{-1}$ से मिलन हो।

उत्तर

साहचर्यता से बीच के गुणनखंड निरस्त हो जाते हैं; प्रतिलोम की अद्वितीयता से $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ । कपड़े उतारने के लिए पहले जूते उतारे जाते हैं और फिर मोज़े।

\left( f^{-1} \circ g^{-1} \right) \circ \left( g \circ f \right) = f^{-1} \circ \left( g^{-1} \circ g \right) \circ f = f^{-1} \circ f = I_A

विस्तृत हल

हल

$f^{-1} \circ g^{-1} : C \to A$
दो एकैकी संगतताओं का संघटन एकैकी आच्छादक है और इसलिए उसका एक ही प्रतिलोम है। यह जाँचना पर्याप्त है कि $f^{-1} \circ g^{-1}$ , जो $C$ से $A$ में जाता है, उसे दोनों क्रमों में पलटता है।
$\left( f^{-1} \circ g^{-1} \right) \circ \left( g \circ f \right) = f^{-1} \circ \resaltar{\left( g^{-1} \circ g \right)} \circ f = f^{-1} \circ f = I_A$
पहला क्रम: संघटन की साहचर्यता से $g^{-1}$ का $g$ से मिलन होता है, और उनका संघटन $B$ का तत्समक फलन है, जो $f$ को नहीं बदलता।
$\left( g \circ f \right) \circ \left( f^{-1} \circ g^{-1} \right) = g \circ \resaltar{\left( f \circ f^{-1} \right)} \circ g^{-1} = g \circ g^{-1} = I_C$
दूसरा क्रम: इसी प्रकार $f$ का $f^{-1}$ से मिलन होता है।
$\left( g \circ f \right)^{-1} = f^{-1} \circ g^{-1}$
प्रतिलोम की अद्वितीयता से $f^{-1} \circ g^{-1}$ , $g \circ f$ का प्रतिलोम है: गुणनखंड उलटे क्रम में प्रतिलोमित होते हैं।
$\left( g \circ f \right)^{-1} = \resaltar{f^{-1}} \circ \resaltar{g^{-1}}$
कपड़े पहनना $g \circ f$ है: पहले मोज़े और फिर जूते। इसे पलटना पहले $g^{-1}$ लागू करना है, जूते उतारना, और फिर $f^{-1}$ , मोज़े उतारना।

अभ्यास प्रश्न 4जितनी प्राकृत संख्याएँ, उतने ही प्राकृत संख्याओं के युग्म

सिद्ध कीजिए कि फलन $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ , जो इस प्रकार परिभाषित है

f(a, b) = 2^{a - 1} \left( 2b - 1 \right)

एक एकैकी संगतता है।

संकेत

प्रत्येक प्राकृत संख्या $n$ को केवल एक ढंग से $2$ की एक घात और एक विषम संख्या के गुणनफल के रूप में लिखा जा सकता है: जब तक संख्या सम है, $2$ से भाग दीजिए; प्रक्रिया समाप्त होती है क्योंकि भागफल घटते जाते हैं। अद्वितीयता के लिए, यदि $2^{j} u = 2^{k} v$ जहाँ $u$ और $v$ विषम हैं और $j < k$ , तो $2^{j}$ का विलोपन कीजिए और दोनों पक्षों की सम-विषमता की तुलना कीजिए।

उत्तर

फलन एकैकी आच्छादक है: $2$ का $n$ में घातांक $a$ देता है, और विषम भाग $2b - 1$ , $b$ देता है। पहले कुछ मान हैं

f(1, 1) = 1, \quad f(2, 1) = 2, \quad f(1, 2) = 3, \quad f(3, 1) = 4, \quad f(1, 3) = 5, \quad f(2, 2) = 6

विस्तृत हल

हल

$f(a, b) = 2^{a - 1} \left( 2b - 1 \right)$
फलन सुपरिभाषित है: $a - 1$ या तो $0$ है या एक प्राकृत संख्या, और पहली स्थिति में शून्य घातांक वाली घात की परिपाटी से $2^0 = 1$ , जिसे मूल संक्रियाओं वाला पाठ न्यायसंगत ठहराता है; इसके अतिरिक्त, $2b - 1$ विषम है। तालिका में पंक्ति $a$ में $2^{a - 1}$ के विषम संख्याओं के साथ गुणनफल हैं।
$n = 2^{j} u = 2^{j} \left( 2b - 1 \right) = f(\resaltar{j + 1}, \resaltar{b})$
आच्छादकता: $n$ दिया हो, तो जब तक संख्या सम है, $2$ से भाग दिया जाता है। भागफल घटते जाते हैं, और प्राकृत संख्याओं का निरंतर घटता अनुक्रम अनंत नहीं हो सकता (यह सुक्रम सिद्धांत है, जो योग और आगमन वाले पाठ में सिद्ध किया जाता है और यहाँ पहले से उपयोग किया जाता है): प्रक्रिया एक विषम संख्या $u$ पर $j$ भागों के बाद समाप्त होती है, और $u = 2b - 1$ जहाँ $b = \frac{u + 1}{2}$ ।
$2^{j} u = 2^{k} v, \ j < k \rightarrow u = \resaltar{2^{k - j}} v$
एकैकीपन: मान लीजिए $f(a, b) = f(a', b')$ , अर्थात् $2^{j} u = 2^{k} v$ जहाँ $j = a - 1$ , $k = a' - 1$ , $u = 2b - 1$ और $v = 2b' - 1$ , और $u$ तथा $v$ विषम हैं। यदि $j < k$ होता, तो $2^{j}$ का विलोपन करने पर एक विषम संख्या एक सम संख्या के बराबर रह जाती, जो असंभव है; इसी प्रकार यदि $k < j$ , और त्रिभाजिता से $j = k$ , अर्थात् $a = a'$ ।
$2^{j} u = 2^{j} v \rightarrow u = v \rightarrow 2b = 2b', \qquad a = a', \ b = b'$
$j = k$ होने पर गुणनफल का विलोपन नियम $u = v$ देता है; इससे $2b = u + 1 = v + 1 = 2b'$ निकलता है, और गुणनफल का विलोपन नियम $b = b'$ देता है: दोनों युग्म दोनों निर्देशांकों में मेल खाते हैं।
$f(3, 2) = 2^{2} \cdot 3 = 12$
इसलिए फलन $\mathbb{N} \times \mathbb{N}$ से $\mathbb{N}$ में एक एकैकी संगतता है। उदाहरण के लिए, $12 = 2^2 \cdot 3$ युग्म $(3, 2)$ का प्रतिबिंब है।

अभ्यास प्रश्न 5पाठ्यक्रमों का क्रम

एक छात्रा छह पाठ्यक्रमों $a$ , $b$ , $c$ , $d$ , $e$ और $f$ की योजना बनाती है, जिन्हें वह एक-एक करके लेगी। पाठ्यक्रम $a$ , $b$ और $c$ की पूर्वापेक्षा है; पाठ्यक्रम $b$ और $c$ , $d$ की पूर्वापेक्षाएँ हैं; और $e$ , $f$ की पूर्वापेक्षा है। $x \preceq y$ लिखते हुए जब $x = y$ हो या $x$ को $y$ से पहले लेना आवश्यक हो, प्रत्यक्ष या अप्रत्यक्ष रूप से, सिद्ध कीजिए कि $\preceq$ एक आंशिक क्रम है, उसके अल्पिष्ठ और उच्चिष्ठ अवयव निर्धारित कीजिए, और पूर्वापेक्षाओं का पालन करते हुए छह पाठ्यक्रमों को क्रमबद्ध करने के ढंग गिनिए।

संकेत

एक वैध क्रमबद्धता एक पूर्ण क्रम है जिसमें $\preceq$ समाहित है। पाठ्यक्रम $a$ , $b$ , $c$ और $d$ केवल दो क्रमों में लिए जा सकते हैं, इस पर निर्भर कि $b$ पहले आए या $c$ ; फिर $e$ और $f$ को, इसी क्रम में, अन्य चार के बीच डालना है: चुनिए कि वे छह स्थानों में से कौन-से दो घेरते हैं।

उत्तर

अल्पिष्ठ $a$ और $e$ हैं; उच्चिष्ठ $d$ और $f$ ; न सबसे छोटा अवयव है न सबसे बड़ा। $15$ ढंगों से छह में से $e$ और $f$ के स्थान चुने जा सकते हैं, और इसलिए

2 \cdot 15 = 30

विस्तृत हल

हल

$x \preceq y \wedge y \preceq z \rightarrow \resaltar{x \preceq z}$
संबंध परिभाषा से स्वतुल्य है, क्योंकि परिभाषा का पहला विकल्प, $x = y$ , तब पूरा होता है जब $y$ स्वयं $x$ हो। यह संक्रामक है: यदि $x$ , $y$ से पहले आता है और $y$ , $z$ से पहले, प्रत्यक्ष या अप्रत्यक्ष रूप से, तो $x$ , $z$ से पहले आता है।
$x \preceq y \wedge y \preceq x \rightarrow x = y$
यह प्रतिसममित है: यदि $x \preceq y$ और $y \preceq x$ हों जहाँ $x \neq y$ , तो पूर्वापेक्षाएँ एक चक्र बनातीं, और दोनों में से कोई भी पाठ्यक्रम पहले नहीं लिया जा सकता। चित्र में पूर्वापेक्षाओं के तीर सदा नीचे की ओर जाते हैं, और कोई चक्र नहीं है।
$\{ a, e \}, \qquad \{ d, f \}$
अल्पिष्ठ वे पाठ्यक्रम हैं जिनकी कोई पूर्वापेक्षा नहीं, $a$ और $e$ ; उच्चिष्ठ वे हैं जो किसी की पूर्वापेक्षा नहीं, $d$ और $f$ । चूँकि $a$ और $e$ तुलनीय नहीं हैं, न $d$ और $f$ , इसलिए न सबसे छोटा अवयव है न सबसे बड़ा।
$(a, b, c, d), \qquad (a, c, b, d)$
पाठ्यक्रम $a$ , $b$ , $c$ और $d$ केवल दो क्रम स्वीकार करते हैं: $a$ पहले, $d$ अंत में, और $b$ तथा $c$ उनके बीच दोनों में से किसी भी क्रम में।
$2 \cdot \resaltar{15} = 30$
बाकी है $e$ और $f$ को इसी क्रम में डालना: यह चुनना पर्याप्त है कि वे छह में से कौन-से दो स्थान घेरते हैं, और इसके $5 + 4 + 3 + 2 + 1 = 15$ ढंग हैं, जो $e$ के स्थान पर निर्भर करते हैं। दोनों क्रमों में से प्रत्येक इन चुनावों में से प्रत्येक के साथ जुड़ता है, और $30$ क्रमबद्धताएँ हैं।