एक और सेट थ्योरी ट्यूटोरियल क्यों?

इस लेख के लक्षित दर्शक वे लोग हैं जो एब्स्ट्रेक्ट मैथ (abstract math) की परवाह तब तक नहीं करते जब तक कि उन्हें इसका कोई सीधा उपयोग (use-case) न दिखाई दे। वे केवल आवश्यक हिस्से प्राप्त करना चाहते हैं और आगे बढ़ना चाहते हैं। यह लेख उन्हीं दर्शकों को ध्यान में रखकर बनाया गया है।

हमारा अंतिम लक्ष्य एब्स्ट्रेक्ट अलजेब्रा (abstract algebra) को समझना है क्योंकि एब्स्ट्रेक्ट अलजेब्रा में बहुत सी ऐसी अवधारणाएं हैं जिन्हें सही मायने में “उपयोगी” कहा जा सकता है, लेकिन एब्स्ट्रेक्ट अलजेब्रा काफी हद तक सेट थ्योरी पर निर्भर करता है।

हमारा लक्ष्य यहाँ सेट थ्योरी से एब्स्ट्रेक्ट अलजेब्रा तक का सबसे सीधा रास्ता अपनाना है ताकि हम उन सभी शब्दावली और अवधारणाओं को समझ सकें जिनसे हमारा सामना होगा।

इंजीनियर्स आमतौर पर एब्स्ट्रेक्शंस (abstractions) इकट्ठा करने या प्रमेयों (theorems) को सिद्ध करने में दिलचस्पी नहीं रखते हैं, वे चीजों को शिप करना चाहते हैं और साथ ही विषय की इतनी गहरी समझ रखना चाहते हैं कि वे अनजाने में बग या अक्षमताएं (inefficiencies) पैदा न करें। ऐसा ज्ञान प्राप्त करना जो इस लक्ष्य में सीधे तौर पर मदद नहीं करता, समय की बर्बादी माना जाता है।

इस लक्ष्य को अनुकूलित (optimize) करने के लिए, मैंने जानबूझकर सेट थ्योरी के किसी भी ऐसे पहलू को छोड़ दिया है जो एब्स्ट्रेक्ट अलजेब्रा के प्रासंगिक पहलुओं को समझने के लिए सीधे तौर पर उपयोगी नहीं है। नतीजतन, सेट थ्योरी पर यह संसाधन जानबूझकर व्यापक (comprehensive) नहीं बनाया गया है।

Zero Knowledge Proofs के लिए सेट थ्योरी की प्रेरणा

इस ट्यूटोरियल का उद्देश्य आपको इस बात की मजबूत समझ देना है कि सेट थ्योरी के संदर्भ में एक binary operator क्या होता है।

बाइनरी ऑपरेटर की अवधारणा Group Theory के मूल में है, और Group Theory का उपयोग Zero Knowledge Proofs में हर जगह किया जाता है।

हमारा दृष्टिकोण कठोर (rigorous) नहीं है

कुछ गणितज्ञ यह देखकर भयभीत हो सकते हैं कि मैं यहाँ सेट थ्योरी के स्वयंसिद्धों (axioms) पर चर्चा नहीं कर रहा हूँ। यह एक फीचर है, बग नहीं। यदि आप किसी चीज़ का प्रमाण चाहते हैं, तो Google या किसी चैटबॉट से पूछें (या इससे भी बेहतर, इसे खुद हल करें)। यहाँ चर्चा की गई अवधारणाओं को एक सदी से भी अधिक समय से कठोरता से सिद्ध किया जा चुका है।

सेट थ्योरी कठिन नहीं है (कम से कम यदि आप प्रमाण लिखने (proof writing) को छोड़ दें, पहली बार करते समय सेट थ्योरी के प्रमाण आश्चर्यजनक रूप से कठिन हो सकते हैं)। आप शायद सेट थ्योरी को पहले से ही सहज रूप से समझते हैं, और लगभग निश्चित रूप से अपने कोड में सेट का उपयोग किया होगा, शायद किसी ऐरे (array) में डुप्लिकेट को जल्दी से हटाने के लिए। हालाँकि, हमें इस सहज ज्ञान को एक भाषा देने और अपनी सहज समझ को स्पष्ट करने की आवश्यकता है।

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

यदि आप किसी विदेशी देश में एक दुकान में प्रवेश करते हैं और पूछते हैं “मेरे लिए खरीदने के लिए ब्रेड कहाँ?”, तो क्लर्क आपकी मदद कर सकता है, भले ही आपका व्याकरण बहुत खराब हो। लेकिन अगर आप व्याकरण में पारंगत हैं और शब्दावली नहीं जानते हैं, तो आपका ज्ञान बेकार हो जाता है। आप एक आदर्श वाक्य बना सकते हैं, लेकिन यदि आप संक्षेप में “ब्रेड” और “खरीदना” को संदर्भित नहीं कर सकते हैं, तो आपका दुकान का चक्कर सफल नहीं होगा (मैंने इस सादृश्य का आविष्कार नहीं किया है, हालाँकि मुझे याद नहीं आ रहा है कि मैंने इसे पहली बार कहाँ देखा था)।

इसलिए, हम व्याकरण (प्रमाण और प्रमेय) को मुश्किल से ही छुएंगे और एब्स्ट्रेक्ट मैथ की शब्दावली (जो इस विदेशी देश में नेविगेट करने में बहुत उपयोगी है) पर जोर देंगे।

कुछ प्रकार का ज्ञान केवल अनुभव से प्राप्त किया जा सकता है, स्पष्टीकरण से नहीं।

इसलिए, आपको इस पाठ में दिए गए अभ्यास (exercises) करने चाहिए। चिंता न करें, आप प्रमाण नहीं लिख रहे होंगे, बस यह सुनिश्चित करने के लिए कि आपने जो अभी पढ़ा है उसे वास्तव में आत्मसात कर लिया है।

इस पाठ की सापेक्ष संक्षिप्तता से मूर्ख मत बनिए। यदि आप वास्तव में अभ्यास करते हैं, तो इसे पूरा करने में कम से कम एक दोपहर (या दो, शायद तीन) का समय लगेगा। यदि कोई निश्चित अनुभाग समझ में नहीं आता है, तो उस उपविषय (subtopic) के वैकल्पिक स्पष्टीकरण के लिए इंटरनेट या चैटबॉट से परामर्श लें।

एक सेट (set) की परिभाषा

एक सेट वस्तुओं का एक सुपरिभाषित (well-defined) संग्रह है। ये वस्तुएं कुछ भी हो सकती हैं और सेट थ्योरी से हम जो नियम सीखते हैं वे उन पर लागू होते हैं।

पूर्णांक (Integers), परिमेय संख्याएँ (rational numbers), वास्तविक संख्याएँ (real numbers), सम्मिश्र संख्याएँ (complex numbers), मैट्रिसेस (matrices), बहुपद (polynomials), बहुभुज (polygons), और कई अन्य चीजों में एक बात समान है: वे सभी सेट हैं।

एक सुपरिभाषित नियम है जो यह तय करता है कि कोई वस्तु सेट का सदस्य है या नहीं। हम इसमें गहराई तक नहीं जाएंगे, लेकिन यह स्पष्ट है कि एक बहुभुज, बहुपद नहीं है, और एक बहुपद, मैट्रिक्स नहीं है, आदि।

सेट खाली (empty) भी हो सकते हैं। हम इसे empty set कहते हैं।

परिभाषा के अनुसार, सेट में डुप्लिकेट आइटम नहीं होते हैं। उदाहरण के लिए, $\set{a, a, b}$ वास्तव में केवल $\set{a, b}$ है।

Exercise: मान लें कि आपके पास पूर्णांकों के लिए एक उचित परिभाषा है। परिमेय संख्याओं का एक सुपरिभाषित सेट बनाएं।

सुपरसेट (Superset) और सबसेट (subsets)

जब हम पूर्णांकों और परिमेय संख्याओं को देखते हैं, तो उनमें से कुछ के बीच एक संबंध प्रतीत होता है। विशेष रूप से, सभी पूर्णांक परिमेय संख्याएँ हैं, लेकिन सभी परिमेय संख्याएँ पूर्णांक नहीं हैं। उनके बीच का संबंध यह है कि पूर्णांक परिमेय संख्याओं का एक subset (उपसमुच्चय) हैं। दूसरी ओर, परिमेय संख्याएँ पूर्णांकों का एक सुपरसेट हैं।

एक सबसेट का उस सेट से सख्ती से छोटा होना आवश्यक नहीं है जिससे वह संबंधित है। उदाहरण के लिए, यह कहना पूरी तरह से वैध है कि पूर्णांकों का सेट स्वयं का एक सबसेट है।

पूर्णांकों और परिमेय संख्याओं के बीच संबंध की सटीक परिभाषा एक proper subset (उचित उपसमुच्चय) है, अर्थात, ऐसी परिमेय संख्याएँ मौजूद हैं जो पूर्णांक नहीं हैं।

Exercise: पूर्णांकों, परिमेय संख्याओं, वास्तविक संख्याओं और सम्मिश्र संख्याओं के बीच सबसेट संबंध को परिभाषित करें।

Exercise: ट्रांसेंडेंटल नंबर्स (transcendental numbers) के सेट और सम्मिश्र संख्याओं (complex numbers) के सेट के बीच सबसेट के संदर्भ में संबंध को परिभाषित करें। क्या यह एक प्रॉपर सबसेट है?

सेट की समानता (Set equality)

सेट को समान (equal) परिभाषित किया जाता है यदि उनमें समान तत्व (elements) होते हैं, भले ही वे तत्व किसी भी क्रम में दिखाई दें। उदाहरण के लिए, $\{4, 2, 5\}$ वही सेट है जो $\{2, 5, 4\}$ है। जब हम सेट के लिए औपचारिक प्रमाण (formal proofs) करते हैं, तो हम कहते हैं कि यदि $A$, $B$ का सबसेट है और $B$, $A$ का सबसेट है, तो $A = B$। या अधिक गणितीय संकेतन (notation) में: $A = B \iff A \subseteq B$ और $B \subseteq A$। इसे इस प्रकार पढ़ा जाता है कि $A = B$ यदि और केवल यदि $A$, $B$ का सबसेट है और $B$, $A$ का सबसेट है।

कार्डिनैलिटी (Cardinality)

हमारे उपरोक्त कुछ उदाहरणों में, पूर्णांकों, परिमेय संख्याओं और अन्य समान सेटों की अनंत (infinite) संख्या है। हालाँकि, हम सेटों को सीमित (finite) तरीके से भी परिभाषित कर सकते हैं, जैसे संख्याएँ $\set{0,1,2,3,4,5,6,7,8,9,10}$। पिछले सेट की कार्डिनैलिटी $11$ है। यदि $A = \set{5,9,10}$ है, तो $|A| = 3$, जहाँ A के चारों ओर दो ऊर्ध्वाधर पट्टियों (vertical bars) का अर्थ कार्डिनैलिटी है।

सेट थ्योरी में अनंत के विभिन्न स्तर (levels of infinity) होते हैं। उदाहरण के लिए, पूर्णांकों की तुलना में वास्तविक संख्याएँ असीम रूप से अधिक हैं। विशेष रूप से, हम कहते हैं कि पूर्णांक गणनीय रूप से अनंत (countably infinite) हैं क्योंकि आप सचमुच उन्हें गिन सकते हैं। लेकिन वास्तविक संख्याओं को गिनना शुरू करने का कोई तरीका नहीं है जो कि अगणनीय रूप से अनंत (uncountably infinite) हैं।

Exercise: ऊपर दी गई समानता की औपचारिक परिभाषा का उपयोग करते हुए, तर्क दें कि यदि दो परिमित (finite) सेटों की कार्डिनैलिटी अलग-अलग है, तो वे समान नहीं हो सकते। (अनंत सेटों के लिए इसे प्रदर्शित करना थोड़ा पेचीदा है, इसलिए हम उसे छोड़ देते हैं)।

फैंसी ब्लैकबोर्ड अक्षर

चूंकि “एक सेट के रूप में पूर्णांक” और “एक सेट के रूप में वास्तविक संख्याएँ” का अक्सर उपयोग किया जाता है, इसलिए इसके लिए एक डरावना दिखने वाला गणितीय आशुलिपि (mathematical shorthand) है।

• प्रतीक $\mathbb{N}$ प्राकृतिक संख्याओं $(1,2,3,…)$ का सेट है। इसमें निश्चित रूप से ऋणात्मक संख्याएँ (negative numbers) शामिल नहीं हैं, लेकिन इसमें शून्य शामिल है या नहीं, यह इस बात पर निर्भर करता है कि आप किससे बात कर रहे हैं।
• प्रतीक $\mathbb{Z}$ सभी पूर्णांकों का सेट है (क्योंकि जर्मन में “zahlen” का अर्थ पूर्णांक है)।
• प्रतीक $\mathbb{Q}$ सभी परिमेय संख्याओं का सेट है। परिमेय संख्याएँ वे संख्याएँ हैं जिन्हें दो पूर्णांकों (एक अंश $p$ और एक गैर-शून्य हर $q$) के भागफल (quotient) या भिन्न (fraction) के रूप में $\frac{p}{q}$ दर्शाया जा सकता है। इस परिभाषा से, यह देखना आसान है कि $\mathbb{Q}$ प्रतीक कहाँ से आता है।
• प्रतीक $\mathbb{R}$ सभी वास्तविक संख्याओं (real numbers) का सेट है, क्योंकि R का अर्थ Real है। ज़ाहिर है।
• प्रतीक $\mathbb{C}$ समान स्पष्ट कारणों से सभी सम्मिश्र संख्याओं (complex numbers) का सेट है।

कभी-कभी लोग $\mathbb{R}^2$ को दो वास्तविक संख्याओं के वेक्टर के रूप में लिखते हैं, इसलिए $a \in \mathbb{R}^2$ का अर्थ है कि $a$ एक 2D वेक्टर है। मैं इसे दूसरे तरीके से लिखने की सलाह देता हूं क्योंकि यह अधिक संक्षिप्त है, और आपको अधिक स्मार्ट भी दिखाता है।

क्रमित युग्म (Ordered pairs)

यद्यपि सेटों का कोई अंतर्निहित क्रम (inherent order) नहीं होता है, लेकिन सेटों के सेट से एक नए प्रकार का डेटा स्ट्रक्चर उभर सकता है जिसे ordered pair कहा जाता है। उदाहरण के लिए, $(a, b)$ एक क्रमित युग्म (ordered pair) है जबकि $\{a, b\}$ एक सेट है।

हम प्रोग्रामर आमतौर पर एक क्रमित युग्म को एक टपल (tuple) के रूप में सोचते हैं। हम कहते हैं कि दो क्रमित युग्म उसी अर्थ में समान हैं जिस अर्थ में हम कहते हैं कि दो टपल समान हैं।

हम किसी ऐसी चीज़ से क्रम कैसे बनाते हैं जो स्वाभाविक रूप से अक्रमित (unordered) है?

मुख्य कार्यान्वयन विवरण (implementation detail) यह है कि हम $(a, b)$ को एक सेट फॉर्म में $\set{a, \set{b}}$ के रूप में दर्शाते हैं। हम ऐसा इसलिए कर सकते हैं क्योंकि हम अपने सेट को या तो अक्षरों वाले या एक की कार्डिनैलिटी वाले सेट के रूप में परिभाषित कर सकते हैं जिसमें एक अक्षर होता है। यही कारण है कि हम कह सकते हैं कि $(a, b) \neq (b, a)$ क्योंकि $\set{a, \set{b}} \neq \set{b, \set{a}}$। हम इस कार्यान्वयन विवरण की और चिंता नहीं करेंगे।

अन्य प्रोग्रामिंग भाषाओं की तरह ही, हमारा क्रमित युग्म मनमाने ढंग से लंबा हो सकता है; उदाहरण के लिए, $(a,b,c,d)$ वैध है। हम एक क्रमित युग्म को एन्कोड भी कर सकते हैं जिसमें एक क्रमित युग्म $((a, b), c)$ के रूप में हो, जो बाद में उपयोगी होगा।

कार्टेशियन गुणनफल (Cartesian product)

चूँकि सेट सुपरिभाषित (well-defined) होते हैं, हम एक सेट को इस तरह से परिभाषित कर सकते हैं कि एक सेट का प्रत्येक तत्व दूसरे सेट के तत्व के साथ क्रमित युग्म का एक हिस्सा हो। उदाहरण के लिए, यदि $A = {1,2,3}$ और $B = {x, y, z}$ है, तो कार्टेशियन गुणनफल $A \times B$, सेट $\{(1, x), (1, y), (1, z), (2, x), …, (3, z)\}$ है। इसे एक टेबल के रूप में भी दर्शाया जा सकता है:

कार्टेशियन गुणनफल क्रमविनिमेय (commutative) नहीं होते हैं, जैसा कि निम्नलिखित अभ्यास प्रदर्शित करेगा। सामान्य मामले में क्रमविनिमेय का अर्थ है $B \times A = A \times B$।

Exercise: उपरोक्त परिभाषाओं का उपयोग करके $B \times A$ के कार्टेशियन गुणनफल की गणना करें।

कार्टेशियन गुणनफल के सबसेट एक फ़ंक्शन बनाते हैं

क्या हो अगर हम कहना चाहें कि हमारे पास एक फ़ंक्शन है

(मैंने इस आउट-ऑफ-ऑर्डर उदाहरण को थोड़ा अधिक रोचक बनाने के लिए चुना है)।

हम एक सेट को परिभाषित कर सकते हैं जो इस मैपिंग को परिभाषित करता है। हम केवल अपने उपरोक्त कार्टेशियन गुणनफल का एक सबसेट लेते हैं जिसमें $(1, y)$, $(2, z)$, और $(3, x)$ शामिल हैं।

सेट-सिद्धांत के संदर्भ में, एक फ़ंक्शन डोमेन सेट (domain set) और कोडोमेन सेट (codomain set) के कार्टेशियन गुणनफल का एक सबसेट है।

$1$ की $y$ पर, $2$ की $z$ पर, और $3$ की $x$ पर मैपिंग के हमारे उदाहरण के लिए, कार्टेशियन गुणनफल का सबसेट नीचे बोल्ड में दिखाया गया है:

इसलिए, हमारा फ़ंक्शन सेट $\{(1, y), (2, z), (3, x)\}$ द्वारा परिभाषित किया गया है।

एक फ़ंक्शन को परिभाषित करने के लिए, हमें उस सेट की आवश्यकता होती है जहाँ से हम शुरू करते हैं और वह सेट जहाँ हम समाप्त होते हैं। हम इन दो सेटों का कार्टेशियन गुणनफल लेते हैं, जिसके परिणामस्वरूप इनपुट सेट से आउटपुट सेट तक हर संभावित असाइनमेंट (assignment) प्राप्त होता है। फिर हम अपनी पसंद के अनुसार फ़ंक्शन को परिभाषित करने के लिए कार्टेशियन गुणनफल का सबसेट लेते हैं। जब हम पूर्णांकों जैसे अनंत सेटों (infinite sets) से निपटते हैं, तो हमें इस बात की परेशानी नहीं होती कि हम सभी क्रमित बिंदुओं (ordered points) को स्पष्ट रूप से नहीं गिन सकते।

फ़ंक्शंस का कंप्यूट करने योग्य (computable) होना आवश्यक नहीं है

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

यहीं पर प्रोग्रामर्स कभी-कभी उलझ जाते हैं। वे अक्सर फ़ंक्शंस को केवल एक ऐसी चीज़ के रूप में सोचते हैं जिसकी कोड की लाइनों के साथ कुशलतापूर्वक गणना की जा सकती है। यद्यपि उपयोगी है, लेकिन यह फ़ंक्शंस के सामान्य गुणों की हमारी समझ को सीमित करता है।

मैं इस बात पर इसलिए ज़ोर दे रहा हूँ क्योंकि Zero Knowledge Proofs में, हम ऐसे फ़ंक्शंस से निपटने जा रहे हैं जो किसी फ़ंक्शन में तर्क (argument) डालने और रिटर्न वैल्यू प्राप्त करने की तुलना में बहुत “उच्च स्तर (higher level)” के होते हैं। हमें फ़ंक्शंस की “बड़ी तस्वीर (big picture)” को सराहने में सक्षम होने की आवश्यकता है। वे एक सेट से दूसरे सेट में एक मैपिंग हैं। और सेटों के बीच एक मैपिंग उनके कार्टेशियन गुणनफल का एक सबसेट लेने से आती है।

असमान डोमेन और कोडोमेन वाले फ़ंक्शंस

विशेष रूप से, हम पूर्णांकों (integers), बहुपदों (polynomials), मैट्रिसेस (matrices), एक आयाम में एलिप्टिक कर्व्स (elliptic curves in one dimension), फिर दूसरे आयाम में एलिप्टिक कर्व्स, और इसी तरह आगे छलांग लगाने (jumping) वाले हैं।

इसकी संकल्पना (conceptualize) करने की कोशिश में आपको बहुत चक्कर आएंगे जब तक कि आप मूलभूत स्तर पर यह नहीं समझ लेते कि, सेट थ्योरी के अनुसार, हमें जैसे चाहें छलांग को परिभाषित करने की अनुमति है!

बेशक, हम छलांग को कैसे मैप करते हैं, इसका इसकी उपयोगिता पर गहरा प्रभाव पड़ेगा, यदि हम सब कुछ शून्य (zero) पर मैप करते हैं, तो यह एक वैध मैप है, लेकिन बहुत उपयोगी नहीं है।

मैं चाहता हूं कि आप जल्दी समझ लें कि जब हम इस तरह से ब्रह्मांडों के बीच ताना-बाना (warp) बुनते हैं तो हम कुछ भी अजीब नहीं कर रहे हैं।

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

चॉइस का स्वयंसिद्ध (Axiom of Choice)

यदि आप सोच रहे हैं “अरे रुको, क्या मैं बस एक सबसेट चुन सकता हूँ और अपनी पसंद के अनुसार फ़ंक्शन को परिभाषित कर सकता हूँ?” तो आप यह सोचने वाले अकेले नहीं हैं। यदि आप गहराई में जाना चाहते हैं, तो हम वास्तव में इस पूरे समय axiom of choice पर चर्चा कर रहे हैं, और यह विवाद का विषय रहा है जबकि परिभाषा गैर-विवादास्पद लगती है:

गैर-रिक्त सेटों (non-empty sets) के संग्रह का कार्टेशियन गुणनफल गैर-रिक्त (non-empty) होता है।

कार्टेशियन गुणनफल के सबसेट एक फ़ंक्शन बनाते हैं: उदाहरण

आइए फ्लोर फ़ंक्शन (floor function) का उपयोग करके गैर-ऋणात्मक वास्तविक संख्याओं (शून्य या अधिक) और गैर-ऋणात्मक पूर्णांकों (शून्य या अधिक) के बीच एक मैपिंग को परिभाषित करें। फ्लोर फ़ंक्शन बस एक संख्या के दशमलव भाग (decimal portion) को हटा देता है। हम सभी वास्तविक संख्याएँ (या पूर्णांक) नहीं दिखा सकते हैं, लेकिन हम एक खाका (sketch) बना सकते हैं।

जब हम $\mathbb{R}\times\mathbb{Z}$ करते हैं और एक सबसेट लेते हैं, तो हम बस वे क्रमित युग्म चुनते हैं जो वास्तविक संख्याओं से तत्व का फ्लोर लेने के अनुरूप होते हैं। जो क्रमित युग्म हम तालिका में नहीं दिखाते हैं, वे क्रमित युग्म हैं जो हमारे सबसेट में नहीं हैं जो मैपिंग को परिभाषित करते हैं। उदाहरण के लिए, $2$, $500.3$ का फ्लोर नहीं है इसलिए वह क्रमित युग्म $(500.3, 2)$ शामिल नहीं है।

Exercise: पूर्णांकों $\{1,2,3,4,5,6\}$ से सेट $\{\text{even}, \text{odd}\}$ तक एक मैपिंग (फ़ंक्शन) परिभाषित करें।

Exercise: बहुभुजों $\{\text{triangle}, \text{square}, \text{pentagon}, \text{hexagon}, \text{heptagon}, \text{octagon}\}$ और पूर्णांकों के सेट $\{0,1,2,…,8\}$ का कार्टेशियन गुणनफल लें। एक मैपिंग को इस तरह परिभाषित करें कि बहुभुज भुजाओं की संख्या दर्शाने वाले पूर्णांक से मैप हो जाए। उदाहरण के लिए, क्रमित युग्म $(\Box, 4)$ सबसेट में होना चाहिए, लेकिन $(\bigtriangleup, 7)$ कार्टेशियन गुणनफल के सबसेट में नहीं होना चाहिए।

Exercise: धनात्मक पूर्णांकों (positive integers) और धनात्मक परिमेय संख्याओं (positive rational numbers) के बीच एक मैपिंग परिभाषित करें (पूरी तरह से नहीं, जाहिर है)। पूर्णांकों को परिमेय संख्याओं में पूरी तरह से मैप करना संभव है। संकेत: परिमेय संख्याओं के निर्माण के लिए एक तालिका बनाएं जहाँ कॉलम अंश (numerators) हों और पंक्तियाँ हर (denominators) हों। उत्तर देखने से पहले कम से कम 15 मिनट तक इससे जूझें।

कार्टेशियन गुणनफल के वैध (Valid) और अवैध (invalid) सबसेट।

हम अपना सबसेट कैसे चुनते हैं, इस पर एक महत्वपूर्ण प्रतिबंध है। उदाहरण के लिए, कार्टेशियन गुणनफल $\{1,2,3\}$, $\{p,q,r\}$ का निम्नलिखित सबसेट वैध नहीं है क्योंकि $1$, $p$ पर मैप करता है और $1$, $q$ पर मैप करता है। कार्टेशियन गुणनफल के साथ फ़ंक्शन को परिभाषित करते समय, एक ही डोमेन तत्व (domain element) दो अलग-अलग कोडोमेन तत्वों (codomain elements) पर मैप नहीं कर सकता है।

एक सेट का स्वयं के साथ कार्टेशियन गुणनफल

इसमें कोई आश्चर्य नहीं होना चाहिए कि $A$ और $B$ के बीच कार्टेशियन गुणनफल करने के बजाय, आप $A$ और $A$ के बीच कार्टेशियन गुणनफल कर सकते हैं। यह सिर्फ एक सेट को खुद पर मैप करना है।

यह उस चीज़ का पहला कदम है जिसे हम पारंपरिक रूप से पूर्णांकों पर फ़ंक्शंस के रूप में अधिक अमूर्त रूप में सोचते हैं।

उदाहरण के लिए, $y=x^2$ (धनात्मक पूर्णांकों पर) को सेट थ्योरी के संदर्भ में $\mathbb{Z}\times\mathbb{Z}$ के सबसेट के रूप में देखा जा सकता है:

सेट संबंध (Set relations)

“कार्टेशियन गुणनफल का सबसेट लेना” वाक्यांश इतना आम है कि हमारे पास इसके लिए एक शब्द है। यह एक relation (संबंध) है।

एक संबंध एक सेट के स्वयं के साथ या एक सेट के दूसरे सेट के साथ कार्टेशियन गुणनफल से हो सकता है। यदि हमारे पास दो सेट $A$ और $B$ हैं ($B$ सामान्यता के नुकसान के बिना $A$ के बराबर हो सकता है या नहीं भी हो सकता है), और हम $A \times B$ का एक सबसेट लेते हैं, तो हम कहते हैं कि $A$ का एक तत्व $a$, $B$ के एक तत्व $b$ से संबंधित है यदि $A \times B$ के सबसेट में एक क्रमित युग्म $(a, b)$ है।

$y=x^2$ उदाहरण में, $X$ से $2$, $Y$ से $4$ से संबंधित है, लेकिन $X$ में $3$, $Y$ से $6$ से संबंधित नहीं है।

सेट सिद्धांत के संदर्भ में एक “बाइनरी ऑपरेटर (binary operator)”

एक बाइनरी ऑपरेटर $A \times A \rightarrow A$ से एक फ़ंक्शन है। मूल रूप से, हम $A \times A$ ($A$ का स्वयं के साथ कार्टेशियन गुणनफल) से हर संभावित जोड़ी (pair) लेते हैं और इसे $A$ में एक तत्व पर मैप करते हैं। दूसरे शब्दों में, यह $A \times A$ और $A$ के बीच एक सेट संबंध (set relation) है।

यहाँ बाइनरी ऑपरेटर्स के कुछ बुनियादी उदाहरण दिए गए हैं:

• पूर्णांकों का जोड़ (addition of integers) सेट पूर्णांकों से कोई भी दो तत्व लें और उन्हें एक साथ जोड़ें, आपको पूर्णांकों के सेट से एक और तत्व मिलता है। यहाँ, हमने पूर्णांकों की एक जोड़ी को दूसरे पूर्णांक पर मैप किया है। उदाहरण के लिए, $(1, 3)$, $4$ पर मैप होता है।
• परिमेय संख्याओं का गुणा (multiplication of rational numbers) कोई भी दो परिमेय संख्याएँ लें, उन्हें एक साथ गुणा करें, आपको एक और परिमेय संख्या मिलती है। उदाहरण के लिए, $(3.5, 2.0)$, $7.0$ पर मैप होता है।
• स्ट्रिंग्स का कॉन्कैटिनेशन (concatenation of strings) स्ट्रिंग्स के सेट से स्ट्रिंग्स की कोई भी जोड़ी लें, उन्हें जोड़ें (concatenate), और परिणाम एक और स्ट्रिंग है। उदाहरण के लिए, $(\text{Rare},\text{Skills})$, $\text{RareSkills}$ पर मैप होता है। उपरोक्त दो उदाहरणों के विपरीत, जोड़ी में स्ट्रिंग्स का क्रम उस अंतिम स्ट्रिंग को बदल देता है जिस पर जोड़ी को मैप किया जाता है। उदाहरण के लिए, $(\text{Rare},\text{Skills})$ स्ट्रिंग $\text{RareSkills}$ पर मैप होता है लेकिन $(\text{Skills},\text{Rare})$ स्ट्रिंग $\text{SkillsRare}$ पर मैप होता है।

एक सेट-थ्योरेटिक बाइनरी ऑपरेटर का निर्माण

आइए एडिशन मॉड्यूलो (addition modulo) $3$ वाले बाइनरी ऑपरेटर के साथ सेट $\set{0,1,2}$ के एक उदाहरण का उपयोग करें। सबसे पहले हम सेट का खुद के साथ कार्टेशियन गुणनफल लेते हैं (यानी $A \times A$):

फिर हम मूल सेट के साथ जोड़ियों के इस नए सेट का कार्टेशियन गुणनफल लेते हैं

और फिर उसका सबसेट लें जो हमारे बाइनरी ऑपरेटर एडिशन मॉड्यूलो $3$ को परिभाषित करता है:

ध्यान दें कि यदि हम “आंतरिक टपल (inner tuple)” के अंदर के मानों को मॉड्यूलो $3$ में जोड़ते हैं तो हमें टपल में तीसरा नंबर मिलता है। उदाहरण के लिए, सबसे नीचे की पंक्ति में, हम देखते हैं कि $2 + 2 = 1 \pmod 3$।

फ़ंक्शंस आमतौर पर “मौजूद” होते हैं – लेकिन कंप्यूटिबिलिटी एक अलग कहानी है

फ़ंक्शंस को कार्टेशियन गुणनफल के सबसेट के रूप में सोचना शुरू में थोड़ा अजीब हो सकता है – खासकर इसलिए क्योंकि ऐसी परिभाषाएं आसानी से कोड में अनुवादित नहीं होती हैं।

लेकिन ZK गणितज्ञ परिभाषाओं से काफी प्रभावित है, इसलिए इस शब्दावली को अपनी जानकारी में रखना मददगार होता है।

फ़ंक्शंस को एक मैप के रूप में संकल्पना (conceptualize) करना मददगार है जो एक सेट से एक तत्व लेता है और दूसरे सेट में एक तत्व लौटाता है।

Exercise: क्रमित युग्मों (ordered pairs) का एक सबसेट चुनें जो $a \times b \pmod 3$ को परिभाषित करता हो।

Exercise: हमारे सेट $A$ को संख्याएँ $\set{0,1,2,3,4}$ और हमारे बाइनरी ऑपरेटर को घटाव मॉड्यूलो $5$ (subtraction modulo 5) के रूप में परिभाषित करें। एक तालिका में $A \times A$ के सभी क्रमित युग्मों को परिभाषित करें, फिर क्रमित युग्मों के उस सेट को $A$ पर मैप करें।

एक closed बाइनरी ऑपरेटर एक सेट के किन्हीं भी दो तत्वों को लेता है, और उसी सेट से एक अन्य तत्व को आउटपुट करता है। क्लोज्ड (closed) वाला हिस्सा महत्वपूर्ण है, क्योंकि यह आउटपुट को उसी सेट में होने तक सीमित करता है।

विशेष रूप से, एक सेट $A$ से शुरू करें और एक बाइनरी ऑपरेटर का निर्माण इस प्रकार करें:

एक सेट का स्वयं के साथ कार्टेशियन गुणनफल लें, $A \times A$ और क्रमित युग्मों के इस सेट को $P$ कहें।

$P$ का $A$ के साथ कार्टेशियन गुणनफल लें और उसका एक सबसेट इस प्रकार लें कि $P\times A$ सुपरिभाषित (well defined) हो।

पूर्णांकों पर भाग (Division over integers) एक बाइनरी ऑपरेटर नहीं है क्योंकि वास्तव में जो होता है वह यह है कि हम $P = (\mathbb{Z} \times \mathbb{Z})$ करते हैं और फिर अपना संबंध प्राप्त करने के लिए $P \times \mathbb{Q}$ का एक सबसेट लेते हैं। पूर्णांकों पर भाग क्लोज्ड नहीं है क्योंकि यह परिमेय संख्याएँ (rational numbers) उत्पन्न कर सकता है।

हम एलिप्टिक कर्व्स (elliptic curves), पूर्णांकों, बहुपदों, मैट्रिसेस आदि पर बाइनरी ऑपरेटर्स से बहुत निपटने वाले हैं।

जब हम भरोसा कर सकते हैं कि बाइनरी ऑपरेटर में कुछ गुण होंगे, तो हम कार्यान्वयन विवरण (implementation detail) को काफी हद तक एब्स्ट्रेक्ट (abstract) कर सकते हैं।

उदाहरण के लिए, एलिप्टिक कर्व बिंदुओं को “जोड़ना (adding)” बिल्कुल भी मामूली (trivial) बात नहीं है, और शुरुआत से ही गणित स्पष्ट नहीं होता है।

हालाँकि, यदि आप जानते हैं कि बाइनरी ऑपरेटर क्लोज्ड है, और कुछ नियमों का पालन करता है, तो “जोड़ (addition)” को कैसे लागू किया जाता है, इससे कोई फर्क नहीं पड़ता! यह एक मैप है जो कुछ नियमों का पालन करता है!

आइए कुछ अधिक प्रासंगिक उदाहरण का उपयोग करें। यदि आप डिटरमिनेंट (determinant) $1$ वाले दो स्क्वायर मैट्रिसेस (square matrices) को एक साथ गुणा करते हैं, तो गुणनफल मैट्रिक्स का डिटरमिनेंट भी $1$ होगा। यह प्रमाण ऐसी चीज़ नहीं है जिसे आप जल्दी से अपने दिमाग में हल कर सकें। लेकिन यदि आप इसे “डिटरमिनेंट $1$ वाले $3\times 3$ मैट्रिसेस के सेट और बाइनरी ऑपरेटर गुणा, और गुणा क्लोज्ड है” के रूप में मॉडल करते हैं, तो आपके पास अचानक उस सिस्टम का बहुत सारा कार्यात्मक ज्ञान आ जाता है जिसके कार्यान्वयन विवरण के बारे में आप नहीं जानते हैं। आप जानते हैं कि आप चाहे कुछ भी करें, आपको बिना यह जाने कि ऐसा क्यों है, डिटरमिनेंट $1$ मैट्रिक्स ही मिलेगा।

एक बाइनरी ऑपरेटर को “क्लोज्ड (closed)” के रूप में वर्णित करने की भाषा होने से आप एक उच्च स्तर पर काम कर सकते हैं और परिवर्तनों (transformations) की बड़ी तस्वीर को समझ सकते हैं और कार्यान्वयन विवरणों में उलझने से बच सकते हैं।

आप ऑपरेशन्स के बारे में यह समझे बिना तर्क कर सकते हैं कि वे कैसे काम करते हैं! जब Elliptic curve bilinear pairings जैसे बहुत ही गूढ़ गणित से निपटने की बात आती है तो यह अत्यंत उपयोगी होता है।

वैध बाइनरी ऑपरेशन्स का निर्माण

जब बाइनरी ऑपरेटर्स की बात आती है, तो हमें उसे $A$ पर मैप करने से पहले $A \times A$ का सबसेट लेने की अनुमति नहीं है। बाइनरी ऑपरेटर्स को सेट $A$ के सभी सदस्यों को अपने इनपुट के रूप में स्वीकार करना चाहिए। हमें निश्चित रूप से $A \times A$ और $A$ के बीच क्रमित युग्मों (ordered pairs) का एक सबसेट लेना चाहिए क्योंकि $A \times A$ की प्रत्येक जोड़ी को ठीक एक $A$ पर मैप करना चाहिए। बाइनरी ऑपरेशन का परिणाम एक असंदिग्ध (unambiguous) उत्तर होना चाहिए।

RareSkills के साथ और जानें

एब्स्ट्रेक्ट अलजेब्रा से शब्दावली की उपयोगिता ही कारण है कि हमारा zero knowledge course गणित से कतराता नहीं है। हम बस यह सुनिश्चित करते हैं कि इसका उपयोग शुरू करने से पहले हमारे पास हमारी आवश्यक शब्दावली तैयार हो।

मूल रूप से 25 जुलाई, 2023 को प्रकाशित