मोनोइड
Algebraic structures |
---|
अमूर्त बीजगणित में, गणित की एक शाखा, एक मोनोइड एक सेट है जो एक साहचर्य बाइनरी ऑपरेशन और एक पहचान तत्व से सुसज्जित है। उदाहरण के लिए, जोड़ के साथ गैर-ऋणात्मक पूर्णांक एक मोनोइड बनाते हैं, पहचान तत्व 0 होता है।
मोनोइड्स पहचान के साथ अर्धसमूह हैं। ऐसी बीजगणितीय संरचनाएँ गणित की कई शाखाओं में पाई जाती हैं।
फ़ंक्शन रचना के संबंध में एक सेट से कार्य अपने आप में एक मोनोइड बनाते हैं। अधिक आम तौर पर, श्रेणी सिद्धांत में, किसी वस्तु (श्रेणी सिद्धांत) के morphisms स्वयं एक मोनोइड बनाते हैं, और इसके विपरीत, एक मोनोइड को एक वस्तु के साथ एक श्रेणी के रूप में देखा जा सकता है।
कंप्यूटर साइंस और कंप्यूटर प्रोग्रामिंग में, कैरेक्टर (कंप्यूटिंग) के दिए गए सेट से निर्मित स्ट्रिंग (कंप्यूटर साइंस) का सेट एक फ्री मोनोइड है। परिमित-राज्य मशीनों का वर्णन करने में संक्रमण मोनोइड्स और सिंटैक्टिक मोनोइड्स का उपयोग किया जाता है। ट्रेस मोनोइड्स और इतिहास मोनोइड्स प्रक्रिया गणना और समवर्ती कंप्यूटिंग के लिए नींव प्रदान करते हैं।
सैद्धांतिक कंप्यूटर विज्ञान में, मोनोइड्स का अध्ययन ऑटोमेटा सिद्धांत (क्रोहन-रोड्स सिद्धांत) और औपचारिक भाषा सिद्धांत (स्टार ऊंचाई समस्या) के लिए मौलिक है।
विषय के इतिहास और मोनोइड्स के कुछ अन्य सामान्य गुणों के लिए सेमीग्रुप देखें।
परिभाषा
एक सेट (गणित) एस एक बाइनरी ऑपरेशन से लैस है S × S → S, जिसे हम निरूपित करेंगे •, एक मोनोइड है यदि यह निम्नलिखित दो स्वयंसिद्धों को संतुष्ट करता है:
- साहचर्य
- सभी ए, बी और सी के लिए एस में समीकरण (a • b) • c = a • (b • c) रखती है।
- पहचान तत्व
- एस में एक तत्व ई मौजूद है जैसे कि एस में प्रत्येक तत्व के लिए समानताएं e • a = a तथा a • e = a पकड़।
दूसरे शब्दों में, एक मोनोइड एक पहचान तत्व वाला एक अर्धसमूह है। इसे सहयोगीता और पहचान के साथ मैग्मा (बीजगणित) के रूप में भी माना जा सकता है। एक मोनोइड का पहचान तत्व अद्वितीय है।[1] इस कारण से सर्वसमिका को एक स्थिरांक (गणित) माना जाता है, i. इ। 0-एरी (या शून्य) ऑपरेशन। इसलिए मोनोइड को टपल (एस, •, ई) के विनिर्देशन द्वारा चित्रित किया जाता है।
संदर्भ के आधार पर, बाइनरी ऑपरेशन के प्रतीक को छोड़ा जा सकता है, ताकि ऑपरेशन को जक्सटैप द्वारा निरूपित किया जा सके; उदाहरण के लिए, मोनॉइड स्वयंसिद्धों को लिखा जा सकता है (ab)c = a(bc) तथा ea = ae = a. इस अंकन का अर्थ यह नहीं है कि यह संख्याओं को गुणा किया जा रहा है।
एक मोनोइड जिसमें प्रत्येक तत्व में एक व्युत्क्रम तत्व होता है, एक समूह (गणित) होता है।
मोनोइड संरचनाएं
सबमोनोइड्स
एक मोनोइड का एक सबमोनॉयड (M, •) एम का एक सबसेट एन है जो मोनोइड ऑपरेशन के तहत बंद है और इसमें एम की पहचान तत्व ई शामिल है।[2][3] प्रतीकात्मक रूप से, N, M का एक सबमोनॉइड है यदि N ⊆ M, x • y ∈ N जब भी x, y ∈ N, तथा e ∈ N. इस मामले में, एम से विरासत में मिली बाइनरी ऑपरेशन के तहत एन एक मोनोइड है।
दूसरी ओर, यदि N एक मोनोइड का सबसेट है जो कि मोनोइड ऑपरेशन के तहत क्लोजर (गणित) है, और इस विरासत में मिले ऑपरेशन के लिए एक मोनोइड है, तो N हमेशा एक सबमोनॉइड नहीं होता है, क्योंकि पहचान तत्व भिन्न हो सकते हैं। उदाहरण के लिए, सिंगलटन सेट {0} गुणा के तहत बंद है, और गैर-नकारात्मक पूर्णांकों के (गुणात्मक) मोनोइड का एक सबमोनॉइड नहीं है।
जेनरेटर
M का एक उपसमुच्चय S, M उत्पन्न करने के लिए कहा जाता है यदि M युक्त S का सबसे छोटा सबमोनॉइड M है। यदि कोई परिमित सेट है जो M उत्पन्न करता है, तो M को 'परिमित रूप से उत्पन्न मोनोइड' कहा जाता है।
कम्यूटेटिव मोनोइड
एक मोनॉइड जिसका ऑपरेशन कम्यूटेटिव है उसे कम्यूटेटिव मोनोइड (या, कम सामान्यतः, एक एबेलियन मोनॉयड) कहा जाता है। क्रमविनिमेय मोनोइड्स अक्सर योगात्मक रूप से लिखे जाते हैं। कोई भी क्रमविनिमेय मोनॉइड अपने बीजगणितीय प्रीऑर्डरिंग से संपन्न है ≤, द्वारा परिभाषित x ≤ y अगर वहाँ z ऐसा मौजूद है x + z = y.[4] कम्यूटेटिव मोनॉइड एम की ऑर्डर-यूनिट एम का एक तत्व यू है जैसे एम के किसी भी तत्व एक्स के लिए, यू द्वारा उत्पन्न सेट में मौजूद है जैसे कि x ≤ v. यह अक्सर उस मामले में प्रयोग किया जाता है जब एम आंशिक रूप से आदेशित सेट एबेलियन ग्रुप जी का ऑर्डर समूह होता है, इस मामले में हम कहते हैं कि यू जी की ऑर्डर-यूनिट है।
आंशिक रूप से विनिमेय मोनोइड
एक मोनोइड जिसके लिए ऑपरेशन कुछ के लिए कम्यूटेटिव है, लेकिन सभी तत्व ट्रेस मोनोइड नहीं हैं; ट्रेस मोनोइड्स आमतौर पर समवर्ती संगणना के सिद्धांत में होते हैं।
उदाहरण
- सभी बाइनरी लॉजिकल ऑपरेटर्स के लिए 16 संभावित ट्रुथ टेबल # ट्रुथ टेबल में से चार की दो तरफा पहचान है जो कम्यूटेटिव और एसोसिएटिव भी है। ये चारों समुच्चय {False, True} को क्रमविनिमेय मोनॉइड बनाते हैं। मानक परिभाषाओं के तहत, लॉजिकल कंजंक्शन और लॉजिकल बायकंडिशनल की पहचान सही है जबकि एक्सक्लूसिव डिसजंक्शन और लॉजिकल डिसजंक्शन की पहचान गलत है। AND और OR के मोनोइड्स भी निष्काम हैं जबकि XOR और XNOR के मोनोइड्स नहीं हैं।
- प्राकृतिक संख्याओं का समुच्चय जोड़ (पहचान तत्व 0 (संख्या)) या गुणन (पहचान तत्व 1 (संख्या)) के तहत एक कम्यूटेटिव मोनोइड है। का एक सबमोनॉयड N अतिरिक्त के तहत एक संख्यात्मक मोनोइड कहा जाता है।
- धनात्मक पूर्णांकों का समुच्चय गुणन (पहचान तत्व 1) के तहत एक क्रमविनिमेय मोनॉइड है।
- एक सेट दिया A, के सबसेट का सेट A प्रतिच्छेदन के अंतर्गत एक क्रमविनिमेय मोनॉयड है (पहचान तत्व is A अपने आप)।
- एक सेट दिया A, के सबसेट का सेट A संघ के तहत एक क्रमविनिमेय मोनॉइड है (पहचान तत्व खाली सेट है)।
- पिछले उदाहरण का सामान्यीकरण करते हुए, प्रत्येक बंधी हुई अर्ध-जाल एक इम्पोटेंट कम्यूटेटिव मोनॉयड है।
- विशेष रूप से, किसी भी बंधे हुए जाली (आदेश) को जुड़ने और मिलने- और जुड़ने और मिलने-मोनॉयड संरचना दोनों के साथ संपन्न किया जा सकता है। पहचान तत्व क्रमशः जाली के ऊपर और उसके नीचे हैं। जाली होने के नाते, हेटिंग बीजगणित और बूलियन बीजगणित (संरचना) इन मोनॉइड संरचनाओं से संपन्न हैं।
- हर सिंगलटन सेट {x} एक बाइनरी ऑपरेशन के तहत बंद • तुच्छ (एक-तत्व) मोनोइड बनाता है, जो तुच्छ समूह भी है।
- प्रत्येक समूह (गणित) एक मोनोइड है और प्रत्येक एबेलियन समूह एक क्रमविनिमेय मोनोइड है।
- कोई भी अर्धसमूह S किसी तत्व को जोड़कर एक मोनोइड में बदल दिया जा सकता है e अंदर नही S और परिभाषित करना e • s = s = s • e सभी के लिए s ∈ S. किसी भी सेमीग्रुप को मोनॉइड में बदलने का काम सेमीग्रुप्स की श्रेणी और मोनॉयड्स की श्रेणी के बीच फ्री फ़ैक्टर द्वारा किया जाता है।[5]
- इस प्रकार, एक आइडमपोटेंट मोनोइड (कभी-कभी खोज-पहले के रूप में जाना जाता है) एक पहचान तत्व से सटे हुए बन सकते हैं e एक सेट पर बाईं ओर शून्य सेमीग्रुप S. विपरीत मोनॉइड (कभी-कभी फाइंड-लास्ट कहा जाता है) दाएं शून्य सेमीग्रुप ओवर से बनता है S.
- एक पहचान से जुड़ें e दो तत्वों के साथ बाएँ-शून्य सेमीग्रुप में {lt, gt}. फिर परिणामी idempotent monoid {lt, e, gt} समानता का प्रतिनिधित्व करने वाले ई के साथ, इसके तत्वों के क्रम दिए गए अनुक्रम के शब्दकोषीय क्रम को मॉडल करता है।
- इस प्रकार, एक आइडमपोटेंट मोनोइड (कभी-कभी खोज-पहले के रूप में जाना जाता है) एक पहचान तत्व से सटे हुए बन सकते हैं e एक सेट पर बाईं ओर शून्य सेमीग्रुप S. विपरीत मोनॉइड (कभी-कभी फाइंड-लास्ट कहा जाता है) दाएं शून्य सेमीग्रुप ओवर से बनता है S.
- ऑपरेशन के रूप में जोड़ या गुणा के साथ किसी भी अंगूठी (बीजगणित) का अंतर्निहित सेट। (परिभाषा के अनुसार, एक अंगूठी की गुणक पहचान 1 होती है।)
- संक्रिया के रूप में जोड़ या गुणा के साथ पूर्णांक, परिमेय संख्या, वास्तविक संख्या या सम्मिश्र संख्या।[6]
- सभी का सेट n द्वारा n किसी दिए गए रिंग पर मैट्रिक्स (गणित), ऑपरेशन के रूप में मैट्रिक्स जोड़ या मैट्रिक्स गुणन के साथ।
- कुछ निश्चित वर्णमाला पर सभी परिमित स्ट्रिंग (कंप्यूटर विज्ञान) का सेट Σ ऑपरेशन के रूप में स्ट्रिंग संघनन के साथ एक मोनॉइड बनाता है। खाली स्ट्रिंग पहचान तत्व के रूप में कार्य करती है। इस मोनोइड को निरूपित किया गया है Σ∗ और इसे फ्री मोनोइड ओवर कहा जाता है Σ. यह क्रमविनिमेय नहीं है यदि Σ कम से कम दो तत्व हैं।
- किसी भी मोनोइड को देखते हुए M, विपरीत मोनोइड Mop के समान वाहक समुच्चय और तत्समक अवयव है M, और इसके संचालन द्वारा परिभाषित किया गया है x •op y = y • x. कोई भी क्रमविनिमेय मोनॉइड अपने आप में विपरीत मोनोइड है।
- दो सेट दिए गए हैं M तथा N मोनोइड संरचना के साथ संपन्न (या, सामान्य तौर पर, किसी भी सीमित संख्या में मोनोइड्स, M1, ..., Mk), उनका कार्टेशियन उत्पाद M × N एक मोनोइड भी है (क्रमशः, M1 × ⋯ × Mk). साहचर्य संचालन और पहचान तत्व को जोड़ीदार रूप से परिभाषित किया गया है।[7]
- एक मोनोइड को ठीक करें M. किसी दिए गए सेट से सभी कार्यों का सेट M एक मोनोइड भी है। पहचान तत्व एक निरंतर कार्य है जो किसी भी मूल्य की पहचान के लिए मानचित्रण करता है M; साहचर्य संचालन बिंदुवार परिभाषित किया गया है।
- एक मोनोइड को ठीक करें M ऑपरेशन के साथ • और पहचान तत्व e, और इसके पावर सेट पर विचार करें P(M) के सभी उपसमुच्चयों से मिलकर बनता है M. ऐसे उपसमुच्चयों के लिए एक द्विआधारी संक्रिया को परिभाषित किया जा सकता है S • T = { s • t : s ∈ S, t ∈ T }. यह मुड़ता है P(M) पहचान तत्व के साथ एक मोनोइड में {e}. उसी तरह एक समूह का पावर सेट G समूह उपसमुच्चय के उत्पाद के तहत एक मोनॉइड है।
- होने देना S एक सेट हो। सभी कार्यों का सेट S → S फंक्शन कंपोजिशन के तहत एक मोनोइड बनाता है। पहचान सिर्फ पहचान कार्य है। इसे का पूर्ण परिवर्तन मोनोइड भी कहा जाता है S. यदि S के साथ परिमित है n तत्वों, पर कार्यों का मोनॉयड S के साथ परिमित है nn तत्व।
- पिछले उदाहरण का सामान्यीकरण, आइए C एक श्रेणी (गणित) हो और X की एक वस्तु C. के सभी एंडोमोर्फिज्म का सेट X, निरूपित EndC(X), आकारिकी की संरचना के तहत एक मोनोइड बनाता है। श्रेणी सिद्धांत और मोनोइड्स के बीच संबंध के बारे में अधिक जानने के लिए नीचे देखें।
- जुड़े योग के साथ कॉम्पैक्ट सतहों के होमोमोर्फिज्म क्लास (सेट सिद्धांत) का सेट। इसका इकाई तत्व साधारण 2-गोले का वर्ग है। इसके अलावा, अगर a टोरस के वर्ग को दर्शाता है, और बी प्रक्षेपी विमान के वर्ग को दर्शाता है, तो मोनॉइड के प्रत्येक तत्व सी में एक अनूठी अभिव्यक्ति होती है c = na + mb कहाँ पे n एक सकारात्मक पूर्णांक है और m = 0, 1, या 2. हमारे पास है 3b = a + b.
- होने देना आदेश का चक्रीय मोनोइड बनें n, वह है, . फिर कुछ के लिए . वास्तव में, प्रत्येक ऐसे k आदेश का एक अलग मोनोइड देता है n, और प्रत्येक चक्रीय मोनोइड इनमें से किसी एक के लिए समरूप है।
इसके अलावा, f बिंदुओं पर एक कार्य के रूप में माना जा सकता है के द्वारा दिया गयाया, समकक्षमें तत्वों का गुणन तब फ़ंक्शन संरचना द्वारा दिया जाता है। कब फिर समारोह f का क्रमपरिवर्तन है और क्रम का अद्वितीय चक्रीय समूह देता है n.
गुण
मोनॉइड स्वयंसिद्धों का अर्थ है कि पहचान तत्व e अद्वितीय है: यदि e तथा f एक मोनोइड के पहचान तत्व हैं, फिर e = ef = f.
उत्पाद और शक्तियाँ
प्रत्येक गैर-ऋणात्मक पूर्णांक के लिए n, कोई उत्पाद को परिभाषित कर सकता है किसी क्रम का का n पुनरावर्ती रूप से एक मोनॉइड के तत्व: चलो p0 = e और जाने pm = pm−1 • am के लिये 1 ≤ m ≤ n.
एक विशेष मामले के रूप में, कोई तत्व की गैर-नकारात्मक पूर्णांक शक्तियों को परिभाषित कर सकता है x एक मोनोइड का: x0 = 1 तथा xn = xn−1 • x के लिये n ≥ 1. फिर xm+n = xm • xn सभी के लिए m, n ≥ 0.
उलटा तत्व
एक तत्व x यदि कोई तत्व मौजूद है तो उसे उलटा तत्व कहा जाता है y ऐसा है कि x • y = e तथा y • x = e. तत्व y का प्रतिलोम कहा जाता है x. व्युत्क्रम, यदि वे मौजूद हैं, अद्वितीय हैं: यदि y तथा z का प्रतिलोम हैं x, फिर साहचर्य द्वारा y = ey = (zx)y = z(xy) = ze = z.[8] यदि x उलटा है, व्युत्क्रम के साथ कहते हैं y, तो कोई नकारात्मक शक्तियों को परिभाषित कर सकता है x व्यवस्थित करके x−n = yn प्रत्येक के लिए n ≥ 1; यह समीकरण बनाता है xm+n = xm • xn सभी के लिए पकड़ो m, n ∈ Z.
एक मोनोइड में सभी उल्टे तत्वों का सेट, ऑपरेशन • के साथ मिलकर एक समूह (गणित) बनाता है।
ग्रोथेंडिक समूह
हर मोनॉयड एक समूह के अंदर नहीं बैठता है। उदाहरण के लिए, एक मोनोइड होना पूरी तरह से संभव है जिसमें दो तत्व हों a तथा b ऐसे मौजूद हैं a • b = a हालांकि रखता है b पहचान तत्व नहीं है। इस तरह के एक मोनॉइड को एक समूह में एम्बेड नहीं किया जा सकता है, क्योंकि समूह में दोनों पक्षों को व्युत्क्रम से गुणा किया जाता है a वह मिल जाएगा b = e, जो सच नहीं है।
एक मोनोइड (M, •) रद्द करने की संपत्ति है (या रद्द करने योग्य है) यदि सभी के लिए a, b तथा c में M, समानता a • b = a • c तात्पर्य b = c, और समानता b • a = c • a तात्पर्य b = c.
कैंसिलेशन प्रॉपर्टी के साथ एक कम्यूटेटिव मोनॉयड को ग्रोथेंडिक ग्रुप कंस्ट्रक्शन के जरिए हमेशा ग्रुप में एम्बेड किया जा सकता है। इस प्रकार पूर्णांकों का योज्य समूह (ऑपरेशन + वाला एक समूह) प्राकृतिक संख्याओं के योज्य मोनोइड (संचालन + और रद्दीकरण संपत्ति के साथ एक कम्यूटेटिव मोनोइड) से निर्मित होता है। हालांकि, एक गैर-कम्यूटेटिव कैंसिलेटिव मोनॉयड को एक समूह में एम्बेड करने योग्य नहीं होना चाहिए।
यदि एक मोनॉइड में रद्द करने की संपत्ति है और परिमित है, तो यह वास्तव में एक समूह है।[9] एक मोनॉइड के दाएँ और बाएँ-निरस्त करने वाले तत्व बदले में एक सबमोनॉइड बनाते हैं (अर्थात ऑपरेशन के तहत बंद होते हैं और स्पष्ट रूप से पहचान शामिल करते हैं)। इसका मतलब यह है कि किसी भी क्रमविनिमेय मोनोइड के रद्द करने वाले तत्वों को एक समूह तक बढ़ाया जा सकता है।
ग्रोथेंडिक निर्माण करने के लिए एक मोनोइड में रद्द करने वाली संपत्ति आवश्यक नहीं है - कम्यूटेटिविटी पर्याप्त है। हालांकि, अगर एक कम्यूटेटिव मोनॉयड में रद्द करने की संपत्ति नहीं है, तो मोनॉयड के ग्रोथेंडिक समूह में होमोमोर्फिज्म इंजेक्शन नहीं है। अधिक सटीक, अगर a • b = a • c, फिर b तथा c ग्रोथेंडिक समूह में वही छवि है, भले ही b ≠ c. विशेष रूप से, यदि मोनोइड में एक अवशोषक तत्व होता है, तो इसका ग्रोथेंडिक समूह तुच्छ समूह होता है।
मोनोइड्स के प्रकार
एक उलटा मोनोइड एक मोनोइड है जहां एम में हर ए के लिए, एक अद्वितीय ए मौजूद होता है।-1 एम में ऐसा है कि a = a • a−1 • a तथा a−1 = a−1 • a • a−1. यदि एक व्युत्क्रम मोनोइड रद्दी है, तो यह एक समूह है।
विपरीत दिशा में, एक ज़ीरोसुमफ्री मोनॉयड एक योगात्मक रूप से लिखा हुआ मोनॉइड है जिसमें a + b = 0 इसका आशय है a = 0 तथा b = 0:[10] समतुल्य रूप से, कि शून्य के अलावा किसी भी तत्व का योगात्मक व्युत्क्रम नहीं होता है।
अधिनियम और ऑपरेटर मोनोइड्स
मान लीजिए कि M एक मोनोइड है, जिसमें बाइनरी ऑपरेशन को • और पहचान तत्व को e से दर्शाया गया है। फिर एक (बाएं) 'एम-एक्ट' (या एम पर लेफ्ट एक्ट) एक ऑपरेशन के साथ एक सेट एक्स है ⋅ : M × X → X जो निम्नानुसार मोनोइड संरचना के साथ संगत है:
- एक्स में सभी एक्स के लिए: e ⋅ x = x;
- एम में सभी ए, बी और एक्स में एक्स के लिए: a ⋅ (b ⋅ x) = (a • b) ⋅ x.
यह एक (बाएं) समूह क्रिया (गणित) के मोनोइड सिद्धांत का अनुरूप है। राइट एम-एक्ट्स को एक समान तरीके से परिभाषित किया गया है। एक अधिनियम के साथ एक मोनॉयड को ऑपरेटर मोनॉयड के रूप में भी जाना जाता है। महत्वपूर्ण उदाहरणों में सेमीआटोमेटा की संक्रमण प्रणाली शामिल है। पहचान परिवर्तन से सटे हुए एक परिवर्तन अर्धसमूह को एक ऑपरेटर मोनॉइड में बनाया जा सकता है।
मोनोइड समरूपता
दो मोनोइड्स के बीच एक समरूपता (M, ∗) तथा (N, •) एक कार्य है f : M → N ऐसा है कि
- f(x ∗ y) = f(x) • f(y) एम में सभी एक्स, वाई के लिए
- f(eM) = eN,
जहां ईM और ईN क्रमशः एम और एन पर पहचान हैं। मोनोइड होमोमोर्फिज्म को कभी-कभी 'मोनॉयड मॉर्फिज्म' कहा जाता है।
मोनॉइड्स के बीच प्रत्येक सेमीग्रुप होमोमोर्फिज्म एक मोनोइड समरूपता नहीं है, क्योंकि यह लक्ष्य मोनोइड की पहचान के लिए पहचान को मैप नहीं कर सकता है, भले ही पहचान होमोमोर्फिज्म की छवि की पहचान हो।[11] उदाहरण के लिए विचार करें , अवशेष वर्ग मॉड्यूलो का सेट गुणन से सुसज्जित। विशेष रूप से, का वर्ग पहचान है। समारोह के द्वारा दिया गया के रूप में एक अर्धसमूह समरूपता है में . हालांकि, , इसलिए एक मोनोइड होमोमोर्फिज्म मोनोइड्स के बीच एक सेमीग्रुप होमोमोर्फिज्म है जो पहले मोनोइड की पहचान को दूसरे मोनोइड की पहचान के लिए मैप करता है और बाद की स्थिति को छोड़ा नहीं जा सकता है।
इसके विपरीत, समूहों के बीच एक अर्धसमूह समरूपता हमेशा एक समूह समरूपता होती है, क्योंकि यह आवश्यक रूप से पहचान को संरक्षित करती है (क्योंकि, एक समूह में, पहचान ही एकमात्र ऐसा तत्व है जो x ⋅ x = x).
एक विशेषण मोनोइड समरूपता को एक मोनोइड समरूपता कहा जाता है। दो मोनोइड्स को आइसोमॉर्फिक कहा जाता है यदि उनके बीच एक मोनोइड आइसोमोर्फिज्म हो।
समान प्रस्तुति
मोनॉयड्स को एक प्रस्तुति दी जा सकती है, उसी तरह जैसे समूह को समूह प्रस्तुति के माध्यम से निर्दिष्ट किया जा सकता है। जनरेटर Σ का एक सेट निर्दिष्ट करके और मुक्त मोनोइड Σ पर संबंधों का एक सेट निर्दिष्ट करके ऐसा करता है∗. कोई इसे Σ पर (परिमित) बाइनरी संबंधों को विस्तारित करके करता है∗ मोनोइड सर्वांगसमता, और फिर भागफल मोनोइड का निर्माण, जैसा कि ऊपर है।
एक द्विआधारी संबंध दिया R ⊂ Σ∗ × Σ∗, इसके सममित समापन को परिभाषित करता है R ∪ R−1. इसे एक सममित संबंध तक बढ़ाया जा सकता है E ⊂ Σ∗ × Σ∗ परिभाषित करके x ~E y अगर और केवल अगर x = sut तथा y = svt कुछ तार के लिए u, v, s, t ∈ Σ∗ साथ (u,v) ∈ R ∪ R−1. अंत में, कोई E का स्वतुल्य और सकर्मक संवरण लेता है, जो तब एक मोनोइड सर्वांगसमता है।
विशिष्ट स्थिति में, संबंध R को केवल समीकरणों के एक सेट के रूप में दिया जाता है, ताकि . इस प्रकार, उदाहरण के लिए,
बाइसिकल मोनोइड के लिए समतुल्य प्रस्तुति है, और
डिग्री 2 का प्लैक्टिक मोनोइड है (इसमें अनंत क्रम है)। इस प्लैक्टिक मोनोइड के तत्वों को इस रूप में लिखा जा सकता है पूर्णांक i, j, k के लिए, जैसा कि संबंधों से पता चलता है कि ba a और b दोनों के साथ परिवर्तित होता है।
श्रेणी सिद्धांत से संबंध
Totalityα | Associativity | Identity | Inverse | Commutativity | |
---|---|---|---|---|---|
Semigroupoid | Unneeded | Required | Unneeded | Unneeded | Unneeded |
Small category | Unneeded | Required | Required | Unneeded | Unneeded |
Groupoid | Unneeded | Required | Required | Required | Unneeded |
Magma | Required | Unneeded | Unneeded | Unneeded | Unneeded |
Quasigroup | Required | Unneeded | Unneeded | Required | Unneeded |
Unital magma | Required | Unneeded | Required | Unneeded | Unneeded |
Semigroup | Required | Required | Unneeded | Unneeded | Unneeded |
Loop | Required | Unneeded | Required | Required | Unneeded |
Monoid | Required | Required | Required | Unneeded | Unneeded |
Group | Required | Required | Required | Required | Unneeded |
Commutative monoid | Required | Required | Required | Unneeded | Required |
Abelian group | Required | Required | Required | Required | Required |
^α The closure axiom, used by many sources and defined differently, is equivalent. |
मोनोइड्स को श्रेणी सिद्धांत के एक विशेष वर्ग के रूप में देखा जा सकता है। वास्तव में, एक मोनॉइड ऑपरेशन के लिए आवश्यक स्वयंसिद्ध वही हैं जो आकारिकी संरचना के लिए आवश्यक हैं, जब सभी आकारिकी के सेट तक सीमित होते हैं जिनके स्रोत और लक्ष्य एक दी गई वस्तु है।[12] वह है,
- एक मोनोइड अनिवार्य रूप से एक ही वस्तु के साथ एक श्रेणी के समान है।
अधिक सटीक, एक मोनोइड दिया (M, •), कोई केवल एक वस्तु के साथ एक छोटी श्रेणी का निर्माण कर सकता है और जिसका morphisms M के तत्व हैं। morphisms की संरचना मोनोइड ऑपरेशन • द्वारा दी गई है।
इसी तरह, मोनोइड होमोमोर्फिज्म एकल वस्तु श्रेणियों के बीच केवल कार्यवाहक हैं।[12] तो यह निर्माण मोनोइड्स की श्रेणी के बीच श्रेणियों की समानता देता है | (छोटे) मोनोइड्स सोम की श्रेणी और (छोटी) श्रेणियों कैट की श्रेणी की एक पूर्ण उपश्रेणी। इसी तरह, समूहों की श्रेणी कैट की एक और पूर्ण उपश्रेणी के बराबर है।
इस अर्थ में, श्रेणी सिद्धांत को एक मोनोइड की अवधारणा के विस्तार के रूप में माना जा सकता है। मोनोइड्स के बारे में कई परिभाषाओं और प्रमेयों को एक से अधिक वस्तुओं के साथ छोटी श्रेणियों में सामान्यीकृत किया जा सकता है। उदाहरण के लिए, एक वस्तु के साथ एक श्रेणी का भागफल केवल एक भागफल मोनोइड है।
मोनोइड्स, अन्य बीजगणितीय संरचनाओं की तरह, अपनी स्वयं की श्रेणी, मोन भी बनाते हैं, जिनकी वस्तुएँ मोनोइड्स हैं और जिनकी आकृतियाँ मोनोइड समरूपताएँ हैं।[12]
मोनोइड (श्रेणी सिद्धांत) की एक धारणा भी है जो एक श्रेणी में एक मोनोइड की एक अमूर्त परिभाषा है। सेट की श्रेणी में एक मोनॉयड ऑब्जेक्ट सिर्फ एक मोनॉयड है।
कंप्यूटर विज्ञान में मोनोइड्स
कंप्यूटर विज्ञान में, कई अमूर्त डेटा प्रकारों को एक मोनोइड संरचना से संपन्न किया जा सकता है। एक सामान्य पैटर्न में, एक मोनोइड के तत्वों का अनुक्रम गुना (उच्च-क्रम फ़ंक्शन) होता है या अंतिम मान उत्पन्न करने के लिए संचित होता है। उदाहरण के लिए, कई पुनरावृत्त एल्गोरिदम को प्रत्येक पुनरावृत्ति पर किसी प्रकार के रनिंग टोटल को अपडेट करने की आवश्यकता होती है; इस पैटर्न को एक मोनोइड ऑपरेशन द्वारा सुंदर ढंग से व्यक्त किया जा सकता है। वैकल्पिक रूप से, मोनॉइड संचालन की संबद्धता यह सुनिश्चित करती है कि कई कोर या प्रोसेसर का कुशलता से उपयोग करने के लिए एक उपसर्ग योग या समान एल्गोरिथ्म को नियोजित करके संचालन को समानांतर किया जा सकता है।
पहचान तत्व के साथ एम प्रकार के मूल्यों के अनुक्रम को देखते हुए और साहचर्य संचालन , फोल्ड ऑपरेशन को निम्नानुसार परिभाषित किया गया है:
इसके अलावा, किसी भी डेटा संरचना को उसी तरह से 'फोल्ड' किया जा सकता है, जिसे उसके तत्वों का क्रमांकन दिया गया हो। उदाहरण के लिए, बाइनरी ट्री को फोल्ड करने का परिणाम प्री-ऑर्डर बनाम पोस्ट-ऑर्डर ट्री ट्रैवर्सल के आधार पर भिन्न हो सकता है।
मॅपरेड्यूस
कंप्यूटर विज्ञान में मोनोइड्स का एक अनुप्रयोग तथाकथित मैपरेडस प्रोग्रामिंग मॉडल है (देखें मोनोइड/एन्कोडिंग मैप-रिड्यूस एज़ ए मोनोइड विथ लेफ्ट फोल्डिंग)। MapReduce, कंप्यूटिंग में, दो या तीन ऑपरेशन होते हैं। किसी डेटासेट को देखते हुए, मैप में एक विशिष्ट मोनॉइड के तत्वों के लिए मनमाने डेटा की मैपिंग होती है। कम करने में उन तत्वों को मोड़ना शामिल है, ताकि अंत में हम केवल एक तत्व का उत्पादन कर सकें।
उदाहरण के लिए, यदि हमारे पास एक मल्टीसेट है, तो एक प्रोग्राम में इसे तत्वों से लेकर उनकी संख्या तक के मानचित्र के रूप में दर्शाया जाता है। इस मामले में तत्वों को कुंजी कहा जाता है। विशिष्ट कुंजियों की संख्या बहुत बड़ी हो सकती है, और इस मामले में, मल्टीसेट को शार्ड किया जा रहा है। कटौती को ठीक से अंतिम रूप देने के लिए, शफलिंग चरण डेटा को नोड्स के बीच पुन: समूहित करता है। यदि हमें इस चरण की आवश्यकता नहीं है, तो पूरे मानचित्र/घटा में मानचित्रण और कम करना शामिल है; दोनों ऑपरेशन समानांतर हैं, पूर्व इसकी तत्व-वार प्रकृति के कारण, बाद में मोनोइड की सहचारिता के कारण।
पूर्ण मोनोइड्स
एक पूर्ण मोनॉइड एक परिमित मोनॉइड है जो एक परिमित योग ऑपरेशन से सुसज्जित है किसी भी इंडेक्स सेट के लिए I ऐसा है कि[13][14][15][16]
तथा
- .
क्रमविनिमेय मोनॉइड क्रमविनिमेय मोनॉइड है M एक साथ आंशिक आदेश के साथ ≤ ऐसा है कि a ≥ 0 हरएक के लिए a ∈ M, तथा a ≤ b तात्पर्य a + c ≤ b + c सभी के लिए a, b, c ∈ M.
एक निरंतर मोनॉइड एक आदेशित क्रमविनिमेय मोनॉइड है (M, ≤) जिसमें प्रत्येक निर्देशित सेट में कम से कम ऊपरी सीमा होती है, और ये कम से कम ऊपरी सीमाएँ मोनोइड ऑपरेशन के अनुकूल होती हैं:
हरएक के लिए a ∈ M और निर्देशित सबसेट S का M.
यदि (M,≤) एक सतत मोनोइड है, फिर किसी भी इंडेक्स सेट के लिए I और तत्वों का संग्रह (ai)i ∈ I परिभाषित कर सकते हैं
तथा M साथ में इस असीम योग ऑपरेशन के साथ एक पूर्ण मोनॉइड है।[16]
यह भी देखें
- ग्रीन के संबंध
- मोनाड (कार्यात्मक प्रोग्रामिंग)
- सेमिरिंग और क्लेन बीजगणित
- तारे की ऊँचाई की समस्या
- वैदिक चौराहा
- फ्रोबिनोइड
टिप्पणियाँ
- ↑ If both e1 and e2 satisfy the above equations, then e1 = e1 • e2 = e2.
- ↑ Jacobson 2009.
- ↑ Some authors omit the requirement that a submonoid must contain the identity element from its definition, requiring only that it have an identity element, which can be distinct from that of M.
- ↑ Gondran, Michel; Minoux, Michel (2008). रेखांकन, डायोड और सेमिरिंग्स: नए मॉडल और एल्गोरिदम. Operations Research/Computer Science Interfaces Series. Vol. 41. Dordrecht: Springer-Verlag. p. 13. ISBN 978-0-387-75450-5. Zbl 1201.16038.
- ↑ Rhodes, John; Steinberg, Benjamin (2009), The q-theory of Finite Semigroups: A New Approach, Springer Monographs in Mathematics, vol. 71, Springer, p. 22, ISBN 9780387097817.
- ↑ Jacobson 2009, p. 29, examples 1, 2, 4 & 5.
- ↑ Jacobson 2009, p. 35.
- ↑ Jacobson, I.5. p. 22
- ↑ Proof: Fix an element x in the monoid. Since the monoid is finite, xn = xm for some m > n > 0. But then, by cancellation we have that xm − n = e where e is the identity. Therefore, x • xm − n − 1 = e, so x has an inverse.
- ↑ Wehrung, Friedrich (1996). "प्रक्षेप के साथ संरचनाओं के टेंसर उत्पाद". Pacific Journal of Mathematics. 176 (1): 267–285. doi:10.2140/pjm.1996.176.267. Zbl 0865.06010.
- ↑ f(x)*f(eM) = f(x*eM) = f(x) for each x in M, when f is a semigroup homomorphism and eM is the identity of its domain monoid M.
- ↑ 12.0 12.1 12.2 Awodey, Steve (2006). श्रेणी सिद्धांत. Oxford Logic Guides. Vol. 49. Oxford University Press. p. 10. ISBN 0-19-856861-4. Zbl 1100.18001.
- ↑ Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. Handbook of Weighted Automata, 3–28. doi:10.1007/978-3-642-01492-5_1, pp. 7–10
- ↑ Hebisch, Udo (1992). "सेमीग्रुप्स और सेमीरिंग्स के अनुप्रयोगों के साथ अनंत योगों का एक बीजगणितीय सिद्धांत". Bayreuther Mathematische Schriften (in Deutsch). 40: 21–152. Zbl 0747.08005.
- ↑ Kuich, Werner (1990). "ω-continuous semirings, algebraic systems and pushdown automata". In Paterson, Michael S. (ed.). ऑटोमेटा, भाषाएँ और प्रोग्रामिंग: 17वां अंतर्राष्ट्रीय संवाद, वारविक विश्वविद्यालय, इंग्लैंड, जुलाई 16-20, 1990, कार्यवाही. Lecture Notes in Computer Science. Vol. 443. Springer-Verlag. pp. 103–110. ISBN 3-540-52826-1.
- ↑ 16.0 16.1 Kuich, Werner (2011). "Algebraic systems and pushdown automata". In Kuich, Werner (ed.). कंप्यूटर विज्ञान में बीजगणितीय नींव। सिमोन बोज़ापालिडिस को उनकी सेवानिवृत्ति के अवसर पर समर्पित निबंध. Lecture Notes in Computer Science. Vol. 7020. Berlin: Springer-Verlag. pp. 228–256. ISBN 978-3-642-24896-2. Zbl 1251.68135.
संदर्भ
- Howie, John M. (1995), Fundamentals of Semigroup Theory, London Mathematical Society Monographs. New Series, vol. 12, Oxford: Clarendon Press, ISBN 0-19-851194-9, Zbl 0835.20077
- Jacobson, Nathan (1951), Lectures in Abstract Algebra, vol. I, D. Van Nostrand Company, ISBN 0-387-90122-1
- Jacobson, Nathan (2009), Basic algebra, vol. 1 (2nd ed.), Dover, ISBN 978-0-486-47189-1
- Kilp, Mati; Knauer, Ulrich; Mikhalev, Alexander V. (2000), Monoids, acts and categories. With applications to wreath products and graphs. A handbook for students and researchers, de Gruyter Expositions in Mathematics, vol. 29, Berlin: Walter de Gruyter, ISBN 3-11-015248-7, Zbl 0945.20036
- Lothaire, M. (1997), Combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 17, Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (2nd ed.), Cambridge University Press, doi:10.1017/CBO9780511566097, ISBN 0-521-59924-5, MR 1475463, Zbl 0874.20040
इस पेज में लापता आंतरिक लिंक की सूची
बाहरी संबंध
- "Monoid", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- Weisstein, Eric W. "Monoid". MathWorld.
- Monoid at PlanetMath.