अमूर्त बीजगणित (Abstract Algebra) उन सेटों (sets) का अध्ययन है जिनमें उस सेट पर एक या अधिक ऑपरेटर होते हैं। हमारे उद्देश्यों के लिए, हम केवल उन सेटों की परवाह करते हैं जहाँ ऑपरेटर एक बाइनरी ऑपरेटर (binary operator) है।

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

गणितज्ञों के पास सेट पर बाइनरी ऑपरेटर के हर संभावित व्यवहार के लिए एक शब्दावली है। एप्लाइड प्रोग्रामर्स के रूप में, हमारी प्राथमिक चिंता विशेष रूप से Group (Group Theory से) है, लेकिन आइए हम धीरे-धीरे वहाँ तक पहुँचें। Group इस बड़े चिड़ियाघर में केवल एक प्रकार का जानवर है। इसलिए Group का अलग से अध्ययन करने के बजाय, आइए Group का अध्ययन संबंधित बीजगणितीय संरचनाओं (algebraic structures) (अर्थात बाइनरी ऑपरेटर वाले सेट) के बड़े संदर्भ में करें।

अमूर्त बीजगणित एक बहुत बड़ा क्षेत्र है, लेकिन यहाँ हमारा उद्देश्य स्पष्ट रूप से यह समझना है कि Group क्या है क्योंकि इसका उपयोग Zero Knowledge Proofs में हर जगह किया जाता है। हम अभी एक परिभाषा दे सकते हैं:

Group एक बाइनरी ऑपरेटर वाला ऐसा सेट है जो क्लोज्ड (closed) और एसोसिएटिव (associative) है, जिसमें एक आइडेंटिटी एलिमेंट (identity element) होता है, और जहाँ प्रत्येक एलिमेंट का एक इन्वर्स (inverse) होता है।

लेकिन यह संक्षिप्त परिभाषा बहुत ज्ञानवर्धक नहीं है। Groups को अमूर्त बीजगणित के बड़े क्षेत्र से जोड़कर समझना अधिक उपयोगी है।

Magma

Magma एक क्लोज्ड बाइनरी ऑपरेटर वाला सेट है। बस इतना ही।

एक प्रोग्रामर के रूप में आप सहज रूप से Magma को समझते हैं। अब आपके पास इसके लिए एक शब्द है।

उदाहरण के लिए, सभी धनात्मक पूर्णांकों (positive integers) के सेट पर विचार करें और मान लें कि हमारा बाइनरी ऑपरेटर $x^y$ है। ध्यान दें कि हम ऋणात्मक (negative) संख्याओं की अनुमति नहीं देते हैं क्योंकि यदि $y$ ऋणात्मक है, तो हमें एक भिन्न (fraction) मिलती है।

स्पष्ट है कि, आउटपुट पूर्णांकों के स्पेस में होगा। हमारा फंक्शन $(\mathbb{Z}\times\mathbb{Z})$ और $\mathbb{Z}$ के कार्टेशियन प्रोडक्ट (रिलेशन) का एक सबसेट (subset) है। विशेष रूप से, $x^y$ $(\mathbb{Z}\times\mathbb{Z})$ से $\mathbb{Z}$ तक का एक फंक्शन है।

दिलचस्प बात यह है कि यह उदाहरण कम्यूटेटिव (commutative) या एसोसिएटिव (associative) नहीं है। आप नीचे दिए गए Python कोड में a, b, और c के लिए मान चुनकर खुद को इस बात का यकीन दिला सकते हैं।

Copy
assert a ** (b ** c) != (a ** b) ** c
assert a ** b != b ** a

लेकिन हमें इससे कोई फर्क नहीं पड़ता। Magma सबसे कम प्रतिबंधात्मक बीजगणितीय संरचनाओं (algebraic structures) में से एक है। जो बात मायने रखती है वह यह है कि बाइनरी ऑपरेटर क्लोज्ड है। बाकी सब कुछ स्वीकार्य है।

एक बीजगणितीय संरचना एक सेट है जिसमें उस सेट पर ऑपरेशन्स का एक संग्रह होता है। हमारे उद्देश्यों के लिए, हम जिस एकमात्र ऑपरेशन की परवाह करते हैं वह बाइनरी ऑपरेटर है।

Semigroup

Semigroup एक ऐसा Magma है जहाँ बाइनरी ऑपरेटर का एसोसिएटिव होना अनिवार्य है।

सभी Semigroup, Magma होते हैं, लेकिन सभी Magma, Semigroup नहीं होते।

दूसरे शब्दों में, Semigroup एक ऐसा सेट है जिसका बाइनरी ऑपरेटर क्लोज्ड और एसोसिएटिव होता है।

मान लें कि हमारा (अनंत) सेट पारंपरिक वर्णमाला a, b, c,…, x, y, z से सभी संभावित गैर-रिक्त स्ट्रिंग्स (non-empty strings) का सेट है। उदाहरण के लिए, “az”, “programmer”, “zero”, “asdfghjk”, “foo”, और “bar” सभी इस सेट में हैं।

मान लें कि हमारा बाइनरी ऑपरेटर स्ट्रिंग्स का कॉन्सटेनेशन (concatenation) है। यह क्लोज्ड है, क्योंकि यह सेट में एक और स्ट्रिंग उत्पन्न करता है।

ध्यान दें कि यदि हम “foo” और “bar” को कम्यूट (commute) करते हैं, तो आउटपुट स्ट्रिंग समान नहीं होगी, अर्थात, “foobar” और “barfoo”। हालाँकि, उससे कोई फर्क नहीं पड़ता। “foobar” और “barfoo” दोनों सेट के सदस्य हैं, इसलिए बाइनरी ऑपरेटर “concatenate” क्लोज्ड है। चूँकि हमारे पास एक क्लोज्ड और एसोसिएटिव बाइनरी ऑपरेटर वाला एक सेट है, इसलिए कॉन्सटेनेशन के तहत सभी स्ट्रिंग्स का सेट एक Semigroup है।

अभ्यास: अपने लिए हल करें कि “foo”, “bar”, “baz” को उसी क्रम में कॉन्सटेनेट करना एसोसिएटिव है। याद रखें, एसोसिएटिव का अर्थ है $(A \square B) \square C = A \square (B \square C)$, जहाँ $\square$, Semigroup का बाइनरी ऑपरेटर है।

अभ्यास: Magma और Semigroup का एक उदाहरण दें। Magma, Semigroup नहीं होना चाहिए। ऊपर दिए गए उदाहरणों का उपयोग न करें। इसका मतलब है कि आपको एक ऐसे बाइनरी ऑपरेटर के बारे में सोचना चाहिए जो Magma के लिए क्लोज्ड तो है लेकिन एसोसिएटिव नहीं है, और Semigroup के लिए, बाइनरी ऑपरेटर क्लोज्ड और एसोसिएटिव होना चाहिए।

Monoid

Monoid एक ऐसा Semigroup है जिसमें एक आइडेंटिटी एलिमेंट (identity element) होता है।

हाँ, यह वही Monoid है जो “A monad is a monoid in the category of endofunctors.” में आता है।

यदि हम Scala के लिए Cats लाइब्रेरी में monoid documentation देखते हैं, तो हम इन परिभाषाओं को स्पष्ट रूप से देखते हैं:

Copy
trait Semigroup[A] {
    def combine(x: A, y: A): A
}

trait Monoid[A] extends Semigroup[A] {
    def empty: A
}

Cats लाइब्रेरी केवल “identity” को empty और बाइनरी ऑपरेटर को combine के रूप में संदर्भित करती है। तथ्य यह है कि Monoid, Semigroup को एक्सटेंड करता है, यह दर्शाता है कि Monoid एक Semigroup है जिसमें यह आवश्यकता होती है कि उसमें एक “empty” (आइडेंटिटी) हो।

ऊपर दिया गया स्निपेट इसे नहीं दिखाता है, लेकिन यह वास्तव में आवश्यक है कि combine एसोसिएटिव हो।

Semigroup में केवल एक बाइनरी ऑपरेटर होता है जिस पर कोई प्रतिबंध नहीं होता है सिवाय इसके कि यह इनपुट (x, और y) के समान प्रकार (A) को आउटपुट करता है।

उदाहरण के लिए, शून्य के बिना धनात्मक पूर्णांकों पर जोड़ (addition) एक Semigroup है, लेकिन यदि आप शून्य को शामिल करते हैं, तो यह एक Monoid बन जाता है।

एक आइडेंटिटी एलिमेंट का मतलब है कि यदि आप आइडेंटिटी एलिमेंट और एक अन्य एलिमेंट $a$ के साथ बाइनरी ऑपरेटर लागू करते हैं, तो आपको $a$ मिलता है। जोड़ के उदाहरण में $8 + 0 = 8$, जहाँ $0$ आइडेंटिटी एलिमेंट है। यदि आपका बाइनरी ऑपरेटर गुणा (multiplication) है, तो आइडेंटिटी एलिमेंट $1$ होगा, क्योंकि $1$ से गुणा करने पर वही संख्या वापस मिलती है।

यदि हमारा सेट सभी $2\times 2$ मैट्रिक्स का सेट है और हमारा बाइनरी ऑपरेटर मैट्रिक्स गुणा है, तो आइडेंटिटी एलिमेंट आइडेंटिटी मैट्रिक्स होगा

यूनियन (union) और इंटरसेक्शन (intersection) पर सेटों के सेट

सेटों के बारे में हमारी पिछली चर्चा से आश्चर्यजनक रूप से कुछ गायब था, वह था सेटों के यूनियन और इंटरसेक्शन का उल्लेख। ये बाइनरी ऑपरेटर हैं, और अब इन्हें पेश करने का एक अच्छा समय है।

यदि आप दो सेटों $\set{1,2,3,4}$ और $\set{3,4,5,6}$ का यूनियन लेते हैं, तो आपको $\set{1,2,3,4,5,6}$ मिलता है। यदि आप $\set{1,2,3,4}$ और $\set{3,4,5,6}$ का इंटरसेक्शन लेते हैं, तो आपको $\set{3, 4}$ मिलता है।

यह स्पष्ट होना चाहिए कि ये दोनों ऑपरेटर एसोसिएटिव हैं।

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

इस डोमेन में सेट यूनियन का एक आइडेंटिटी एलिमेंट है: खाली सेट (empty set) $\set{}$। किसी सेट का खाली सेट के साथ यूनियन लें और आपको मूल सेट मिल जाएगा, अर्थात $A \cup \set{} = A$।

इसलिए, यूनियन पर पूर्णांकों के सभी परिमित सेटों का सेट एक Monoid है।

हालाँकि, इंटरसेक्शन ($\cap$) के तहत पूर्णांकों के सभी संभावित परिमित सेटों का सेट, एक Semigroup है – कोई भी परिमित सेट आइडेंटिटी के रूप में काम नहीं करेगा। लेकिन यदि हम इस सेट का विस्तार करके इसमें $\mathbb{Z}$ को शामिल करते हैं – अर्थात, हमारा सेट इंटरसेक्शन के तहत $\{\text{पूर्णांकों के सभी परिमित सेट}\}\cup\mathbb{\{Z\}}$ है, तो यह एक Monoid बन जाता है, क्योंकि $\mathbb{Z}$ आइडेंटिटी एलिमेंट है।

अगर आपको लगता है कि हमने आइडेंटिटी एलिमेंट को “हैक (hack)” करके शामिल किया है, तो हाँ हमने ऐसा ही किया है।

हम बाद में देखेंगे कि एलिप्टिक कर्व्स (elliptic curves) इस तरह की एक तरकीब का उपयोग करते हैं और बीजगणितीय नियमों के साथ सुसंगत रहने के लिए “point at infinity” नामक एक विशेष बिंदु शामिल करते हैं। मुद्दा यह है कि हमें बहुत स्पष्ट होने की आवश्यकता है कि हमारा आइडेंटिटी एलिमेंट क्या है यदि हम कहते हैं कि कोई सेट किसी बाइनरी ऑपरेटर पर एक Monoid है।

एक अन्य उदाहरण के रूप में, हम कह सकते हैं कि हमारा सेट जोड़ के तहत सभी धनात्मक पूर्णांक हैं, जिसमें अतिरिक्त एलिमेंट $\text{mug}$ है। हम $\text{mug} + x = x$ और $x + \text{mug} = x$ परिभाषित करते हैं। सिस्टम के आर्किटेक्ट्स के रूप में, हमें अपने सेट को अपनी पसंद की किसी भी चीज़ से बनाने की अनुमति है, और बाइनरी ऑपरेटर हमारी पसंद के अनुसार व्यवहार कर सकता है। हालाँकि, उस बीजगणितीय डेटा संरचना को Monoid होने के लिए बाइनरी ऑपरेटर का क्लोज्ड, एसोसिएटिव होना और सेट में एक आइडेंटिटी एलिमेंट का होना आवश्यक है।

यदि हम डोमेन को $\set{0,1,2,3,4,5}$ के सभी सबसेट (subsets) तक सीमित करते हैं, तो इंटरसेक्शन स्पष्ट रूप से एक Monoid बन जाता है क्योंकि आइडेंटिटी एलिमेंट $\set{0,1,2,3,4,5}$ होगा, क्योंकि आप इसके साथ किसी भी पूर्णांक के सेट का इंटरसेक्शन करेंगे तो वह दूसरा सेट उत्पन्न करेगा, अर्थात, $A \cap \set{0,1,2,3,4,5} = A$। उदाहरण के लिए, $\set{1,3,4} \cap \set{0,1,2,3,4,5} = \set{1,3,4}$।

इस बिंदु पर यह स्पष्ट होना चाहिए कि किसी दिए गए बाइनरी ऑपरेटर के लिए बीजगणितीय संरचना की श्रेणी (category) सेट के डोमेन के प्रति बहुत संवेदनशील है।

अभ्यास: मान लें कि हमारा बाइनरी ऑपरेटर पूर्णांकों पर min(a,b) फंक्शन है। क्या यह एक Magma, Semigroup, या Monoid है? क्या होगा यदि हम डोमेन को धनात्मक पूर्णांकों (शून्य या अधिक) तक सीमित कर दें? उन दो डोमेन पर बाइनरी ऑपरेटर max(a,b) के बारे में क्या ख्याल है?

अभ्यास: मान लें कि हमारा सेट सभी 3 बिट बाइनरी नंबर (8 की कार्डिनैलिटी वाला एक सेट) है। मान लें कि हमारे संभावित बाइनरी ऑपरेटर बिट-वाइज़ and, बिट-वाइज़ or, बिट-वाइज़ xor, बिट-वाइज़ nor, बिट-वाइज़ xnor और बिट-वाइज़ nand हैं। स्पष्ट रूप से यह क्लोज्ड है क्योंकि आउटपुट एक 3 बिट बाइनरी नंबर है। प्रत्येक बाइनरी ऑपरेटर के लिए, निर्धारित करें कि उस बाइनरी ऑपरेटर के तहत सेट एक Magma, Semigroup, या Monoid है या नहीं।

Group - शो का मुख्य आकर्षण

Group एक ऐसा Monoid है जिसमें प्रत्येक एलिमेंट का एक इन्वर्स (inverse) होता है।

या स्पष्ट रूप से कहें तो, यह चार गुणों वाला एक सेट है:

1. बाइनरी ऑपरेटर क्लोज्ड है (Magma)
2. बाइनरी ऑपरेटर एसोसिएटिव है (Semigroup)
3. सेट में एक आइडेंटिटी एलिमेंट है (Monoid)
4. प्रत्येक एलिमेंट का एक इन्वर्स (inverse) होता है

अर्थात्, सेट $A$ में किसी भी एलिमेंट $a$ के लिए, एक $a'$ मौजूद होता है जिससे कि $a \square a' = i$ जहाँ $i$ आइडेंटिटी एलिमेंट है और $\square$ बाइनरी ऑपरेटर है। अधिक गणितीय भाषा में कहें तो, यह होगा:

यहाँ, $\square$ सेट का बाइनरी ऑपरेटर है।

यह कहना काफी गलत है कि “सेट का एक इन्वर्स है।” सटीक रूप से कहें तो, सेट में हर एलिमेंट का एक और एलिमेंट होता है जो उस एलिमेंट का इन्वर्स होता है।

जोड़ (addition) के साथ पूर्णांकों का उपयोग करते हुए, आइडेंटिटी एलिमेंट शून्य है (क्योंकि आप शून्य जोड़ते हैं, तो आपको वही संख्या वापस मिलती है), और किसी पूर्णांक का इन्वर्स वह पूर्णांक होता है जिसका चिह्न (sign) पलट दिया गया हो (जैसे $5$ का इन्वर्स $-5$ है और $-7$ का इन्वर्स $7$ है)।

डोमेन संवेदनशीलता पर वापस जाते हुए, धनात्मक पूर्णांकों पर जोड़ एक Group नहीं है क्योंकि इसमें कोई इन्वर्स एलिमेंट नहीं हो सकते हैं।

इस बात को स्पष्ट करने के लिए यहाँ एक तालिका दी गई है:

ध्यान दें कि यदि सेट में कोई आइडेंटिटी नहीं है तो “इन्वर्स” का कोई अर्थ नहीं है। परिभाषा के अनुसार, किसी एलिमेंट और उस एलिमेंट के इन्वर्स पर बाइनरी ऑपरेटर लागू करने से आइडेंटिटी एलिमेंट प्राप्त होता है।

अभ्यास: कॉन्सटेनेशन के तहत स्ट्रिंग्स एक Group क्यों नहीं हो सकते?

अभ्यास: जोड़ के तहत पॉलिनॉमियल्स (Polynomials) एक Group की प्रॉपर्टी को संतुष्ट करते हैं। यह प्रदर्शित करें कि यह स्थिति उन सभी गुणों से मेल खाती है जो एक Group को परिभाषित करते हैं।

दुर्भाग्य से, हमारा ट्यूटोरियल यहाँ समाप्त होना चाहिए, क्योंकि प्रारंभिक Group Theory एक अन्य अध्याय का विषय है।

लेकिन अब आपके पास यह समझने के लिए बहुत सारा संदर्भ (context) है कि Group क्या है, भले ही हमने यहाँ इस पर मुश्किल से चर्चा की है!

कम्यूटेटिविटी (commutativity) के बारे में एक बात

उपरोक्त किसी भी बीजगणितीय डेटा संरचना के कम्यूटेटिव होने की आवश्यकता नहीं है। यदि वे हैं, तो हम कहते हैं कि वे अपने बाइनरी ऑपरेटर पर एबेलियन (abelian) हैं। इस संदर्भ में, “एबेलियन” का अर्थ है कि बाइनरी ऑपरेटर कम्यूटेटिव है, जिसका अर्थ है कि ऑपरेंड्स (operands) का क्रम परिणाम को प्रभावित नहीं करता है।

एबेलियन का मतलब है कि बाइनरी ऑपरेटर कम्यूटेटिव है।

लेकिन एबेलियन कहें, तो आप अधिक स्मार्ट लगेंगे।

तकनीकी बात यह है कि हम आम तौर पर “addition is abelian” नहीं कहते हैं बल्कि “the group is abelian over addition” कहते हैं।

फिर से सबसेट्स (Subsets)

आइए इस सब को वापस उसी से जोड़ें जो हमने शुरुआत में सीखा था। Magma, Semigroup, Monoid, और Group सभी ऐसे सेट हैं जिनमें एक क्लोज्ड बाइनरी ऑपरेटर होता है। एक बाइनरी ऑपरेटर सेट के खुद के साथ कार्टेशियन प्रोडक्ट के सभी ऑर्डर्ड पेयर्स (ordered pairs) से वापस उसी तक का एक मैप है।

Group, Monoid का एक सबसेट हैं, Monoid, Semigroup का एक सबसेट हैं, Semigroup, Magma का एक सबसेट हैं, और Magma सामान्य रूप से सेट का एक सबसेट हैं। हर Group एक Magma या सेट भी है, लेकिन एक Magma का Group होना ज़रूरी नहीं है।

“Sets” की कल्पना करना आसान है, लेकिन जब हम Group और अन्य बीजगणितीय संरचनाओं के बारे में बात करना शुरू करते हैं, तो खो जाना आसान होता है। क्रिप्टोग्राफी (cryptography) के हमारे अध्ययन में Group बहुत महत्वपूर्ण हैं। बस याद रखें:

Group बाइनरी ऑपरेटर वाले ऐसे सेट होते हैं जो चार नियमों का पालन करते हैं।

इसके अलावा, अब समय आ गया है कि आप अपने दिमाग को “जोड़” और “गुणा” को चीज़ों को मिलाने का प्राथमिक तरीका मानने से मुक्त करें।

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

गणित की शब्दावली से हमें डरने की ज़रूरत नहीं है

इस ट्यूटोरियल को शुरू करने से पहले, यह वाक्य:

“बाइनरी ऑपरेटर स्ट्रिंग कॉन्सटेनेशन पर स्ट्रिंग्स का सेट एक Semigroup या Monoid है जो सेट में खाली स्ट्रिंग की उपस्थिति या अनुपस्थिति पर निर्भर करता है”

शायद आपको समझ में नहीं आया होगा।

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

क्या मैं उस वाक्य को गणितीय शब्दों के बिना कह सकता हूँ? बिल्कुल कह सकता हूँ, लेकिन इसे स्पष्ट रूप से करने में मुझे कम से कम 500 शब्द लगेंगे। वास्तव में इन शर्तों (terms) का अर्थ समझना फायदेमंद है। इससे हमें लंबे समय में बहुत परेशानी से बचाव होगा।

जो बात इसे शानदार बनाती है वह यह है कि Groups के बारे में प्रचुर मात्रा में प्रमेय (theorems) हैं जो हमें Group के बारे में दावे करने की अनुमति देते हैं बिना यह समझे कि Group का बाइनरी ऑपरेटर आंतरिक रूप से (under the hood) कैसे काम करता है। यह कुछ हद तक ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग में पॉलीमोर्फिज्म (polymorphism) या फंक्शनल भाषाओं में ट्रेड्स (traits) के समान है। वे आपसे कार्यान्वयन के विवरण (implementation details) छिपाते हैं और आपको उच्च स्तर (high level) पर ध्यान केंद्रित करने देते हैं। यह शक्तिशाली है।

अगले अध्याय में, आप सीखेंगे कि होमियोमोर्फिज्म (homomorphisms) के माध्यम से Group एक दूसरे से कैसे “संबंधित” हो सकते हैं।

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

हमारी कम्युनिटी के साथ सीखने के लिए हमारा Zero Knowledge Course देखें।

हमारी ZK Book में इस सीरीज़ के बाकी ZK ट्यूटोरियल्स शामिल हैं।

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