अर्धसमूह क्रिया

"S-समुच्चय" redirects here. For संकीर्ण ट्रेन फ्लीट, see सिडनी ट्रेन S सेट.

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

एक महत्वपूर्ण विशेष मामला एक मोनोइड क्रिया या अधिनियम है, जिसमें सेमिग्रुप एक मोनोइड है और मोनोइड का तत्समक अवयव सेट के तत्समक रूपांतरण के रूप में कार्य करता है। एक श्रेणी-सैद्धांतिक दृष्टिकोण से, एक मोनॉयड एक वस्तु के साथ एक श्रेणी है, और एक अधिनियम उस श्रेणी से सेट की श्रेणी के लिए एक फ़ंक्टर है। यह तुरंत सेट की श्रेणी के अलावा अन्य श्रेणियों में वस्तुओं पर मोनॉइड क्रियाओं का सामान्यीकरण प्रदान करता है।

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

(शब्दावली पर एक नोट: इस क्षेत्र में प्रयुक्त शब्दावली कभी-कभी एक लेखक से दूसरे लेखक में भिन्न होती है। विवरण के लिए लेख देखें।)

औपचारिक परिभाषाएँ

मान लीजिए कि S एक अर्धसमूह है। तब S का एक (बायाँ) सेमीग्रुप एक्शन (या एक्ट) एक सेट X है जिसमें एक ऑपरेशन • : S × X → X है जो सेमीग्रुप ऑपरेशन के साथ संगत है ∗ निम्नानुसार है:

• सभी s, t in S और x in X, s • (t • x) = (s ∗ t) • x के लिए।

यह एक (बाएं) समूह क्रिया के सेमीग्रुप सिद्धांत में एनालॉग है और X पर कार्यों के सेट में एक सेमीग्रुप समरूपता के बराबर है। सही सेमीग्रुप क्रियाओं को एक ऑपरेशन का उपयोग करके इसी तरह परिभाषित किया गया है • : X × S → X समाधानप्रद (x • a) • b = x • (a ∗ b)।

यदि M एक मोनॉइड है, तो M का एक (बायाँ) मोनोइड एक्शन (या एक्ट) अतिरिक्त संपत्ति के साथ M का एक (बायाँ) सेमीग्रुप क्रिया है

• X में सभी x के लिए: X: e • x = x

जहाँ e, M का तत्समक अवयव है। यह तदनुरूप एक मोनोइड समरूपता देता है। सही मोनोइड क्रियाओं को एक समान तरीके से परिभाषित किया गया है। एक सेट पर क्रिया के साथ एक मोनॉयड M को एक ऑपरेटर मोनोइड भी कहा जाता है।

X पर S की एक सेमीग्रुप क्रिया को एक पहचान को सेमीग्रुप से जोड़कर और X पर तत्समक समरूपता के रूप में कार्य करने की आवश्यकता के द्वारा एक मोनोइड अधिनियम में बनाया जा सकता है।

शब्दावली और अंकन

यदि S एक सेमीग्रुप या मोनॉइड है, तो एक सेट X जिस पर S ऊपर के रूप में कार्य करता है (बाईं ओर, कहते हैं) को (बाएं) 'S-act', 'S-set', 'S-action' के रूप में भी जाना जाता है। , 'S-ऑपरेंड', या 'S के ऊपर लेफ्ट एक्ट'। कुछ लेखक पहचान स्वयंसिद्ध के संबंध में सेमीग्रुप और मोनोइड क्रियाओं के बीच अंतर नहीं करते हैं (e • x = x) खाली के रूप में जब कोई पहचान तत्व नहीं है, या एकात्मक S शब्द का उपयोग करके - एक S के लिए कार्य करें - एक पहचान के साथ कार्य करें। किसी अधिनियम की परिभाषित संपत्ति सेमीग्रुप ऑपरेशन की सहयोगीता के अनुरूप है, और इसका मतलब है कि सभी कोष्ठकों को छोड़ा जा सकता है। यह सामान्य अभ्यास है, विशेष रूप से कंप्यूटर विज्ञान में, संचालन को छोड़ने के लिए भी ताकि सेमीग्रुप ऑपरेशन और क्रिया दोनों को संसर्ग द्वारा इंगित किया जा सके। इस प्रकार S से अक्षरों का स्ट्रिंग (कंप्यूटर विज्ञान) X पर कार्य करता है, जैसा कि अभिव्यक्ति stx में s, t में S और x में X के लिए होता है।

बायीं क्रियाओं के बजाय सही क्रियाओं के साथ काम करना भी काफी सामान्य है। हालांकि, प्रत्येक सही एस-अधिनियम को विपरीत अर्धसमूह पर एक बाएं अधिनियम के रूप में व्याख्या किया जा सकता है, जिसमें एस के समान तत्व होते हैं, लेकिन जहां गुणा को कारकों को उलट कर परिभाषित किया जाता है, s • t = t • s, इसलिए दो धारणाएँ अनिवार्य रूप से समान हैं। यहाँ हम मुख्य रूप से वामपंथी कृत्यों के दृष्टिकोण को अपनाते हैं।

अधिनियम और परिवर्तन

एक पत्र का उपयोग करना अक्सर सुविधाजनक होता है (उदाहरण के लिए यदि एक से अधिक कार्य विचाराधीन हैं), जैसे कि $T$, फ़ंक्शन को निरूपित करने के लिए

$T\colon S\times X\to X$

को परिभाषित करना $S$-कार्रवाई और इसलिए लिखें $T(s,x)$ की जगह $s\cdot x$. फिर किसी के लिए $s$ में $S$, हम द्वारा निरूपित करते हैं

$T_{s}\colon X\to X$

का परिवर्तन $X$ द्वारा परिभाषित

$T_{s}(x)=T(s,x).$

एक की परिभाषित संपत्ति द्वारा $S$-कार्य, $T$ संतुष्ट

$T_{s*t}=T_{s}\circ T_{t}.$

इसके अलावा, एक समारोह पर विचार करें $s\mapsto T_{s}$. यह समान है $\operatorname {curry} (T):S\to (X\to X)$ (करींग देखें)। क्योंकि $\operatorname {curry}$ एक आक्षेप है, सेमीग्रुप क्रियाओं को कार्यों के रूप में परिभाषित किया जा सकता है $S\to (X\to X)$ जो संतुष्ट करता है

$\operatorname {curry} (T)(s*t)=\operatorname {curry} (T)(s)\circ \operatorname {curry} (T)(t).$

वह है, $T$ की एक अर्धसमूह क्रिया है $S$ पर $X$ अगर और केवल अगर $\operatorname {curry} (T)$ से एक अर्धसमूह समरूपता है $S$ के पूर्ण परिवर्तन मोनोइड के लिए $X$.

एस-समरूपता

मान लीजिए कि X और X' S-अधिनियम हैं। तब X से X' तक का S-समरूपता एक मानचित्र होता है

$F\colon X\to X'$

ऐसा है कि

$F(sx)=sF(x)$ सभी के लिए $s\in S$ और $x\in X$.

ऐसे सभी एस-समरूपताओं के समुच्चय को सामान्यतः इस प्रकार लिखा जाता है $\mathrm {Hom} _{S}(X,X')$.

एम-एक्ट के एम-होमोमोर्फिज्म, एम मोनोइड के लिए, ठीक उसी तरह परिभाषित किए गए हैं।

एस-एक्ट और एम-एक्ट

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

एक मोनोइड एम के लिए, एम-एक्ट और एक्ट-एम श्रेणियों को उसी तरह परिभाषित किया गया है।

उदाहरण

• कोई भी अर्धसमूह $(S,*)$ पर कार्रवाई है $S$, कहाँ $\cdot =*$. क्रिया गुण की साहचर्यता के कारण धारण करता है $*$.
• अधिक आम तौर पर, किसी भी अर्धसमूह समरूपता के लिए $F\colon (S,*)\rightarrow (T,\oplus )$, अर्धसमूह $(S,*)$ पर कार्रवाई है $T$ द्वारा दिए गए $s\cdot t=F(s)\oplus t$.
• किसी भी सेट के लिए $X$, होने देना $X^{*}$ के तत्वों के अनुक्रमों का समुच्चय हो $X$. अर्धसमूह $(\mathbb {N} ,\times )$ पर कार्रवाई है $X^{*}$ द्वारा दिए गए $n\cdot s=s^{n}$ (कहाँ $s^{n}$ अर्थ है $s$ दोहराया गया $n$ टाइम्स)।
• अर्धसमूह $(\mathbb {N} ,\times )$ सही कार्रवाई है $(\mathbb {N} ,\cdot )$, द्वारा दिए गए $x\cdot y=x^{y}$.

परिवर्तन अर्धसमूह

Main article: Transformation semigroup

ट्रांसफ़ॉर्मेशन सेमीग्रुप्स और सेमीग्रुप क्रियाओं के बीच एक पत्राचार नीचे वर्णित है। यदि हम इसे श्रद्धेय क्रिया सेमीग्रुप एक्शन तक सीमित रखते हैं, तो इसमें अच्छे गुण हैं।

किसी भी परिवर्तन अर्धसमूह को निम्नलिखित निर्माण द्वारा एक अर्धसमूह क्रिया में बदला जा सकता है। किसी भी परिवर्तन के लिए सेमीग्रुप $S$ का $X$, एक सेमीग्रुप क्रिया को परिभाषित करें $T$ का $S$ पर $X$ जैसा $T(s,x)=s(x)$ के लिए $s\in S,x\in X$. यह क्रिया श्रद्धेय है, जो तुल्य है $curry(T)$ इंजेक्शन होना।

इसके विपरीत, किसी भी अर्धसमूह कार्रवाई के लिए $T$ का $S$ पर $X$, एक परिवर्तन अर्धसमूह को परिभाषित करें $S'=\{T_{s}\mid s\in S\}$. इस निर्माण में हम समुच्चय को भूल जाते हैं $S$. $S'$ की छवि (गणित) के बराबर है $curry(T)$. आइए बताते हैं $curry(T)$ जैसा $f$ संक्षिप्तता के लिए। अगर $f$ इंजेक्शन है, तो यह एक सेमीग्रुप समाकृतिकता है $S$ को $S'$. दूसरे शब्दों में, अगर $T$ विश्वासयोग्य है, तो हम कोई महत्वपूर्ण बात नहीं भूलते। यह दावा निम्नलिखित अवलोकन द्वारा सटीक बनाया गया है: यदि हम मुड़ें $S'$ एक अर्धसमूह क्रिया में वापस $T'$ का $S'$ पर $X$, तब $T'(f(s),x)=T(s,x)$ सभी के लिए $s\in S,x\in X$. $T$ और $T'$ के माध्यम से आइसोमॉर्फिक हैं $f$, यानी, हम अनिवार्य रूप से ठीक हो गए $T$. इस प्रकार कुछ लेखक वफादार अर्धसमूह क्रियाओं और परिवर्तन अर्धसमूहों के बीच कोई अंतर नहीं देखें।

कंप्यूटर विज्ञान के लिए अनुप्रयोग

अर्ध-स्वचालित

Main article: Semiautomaton

ऑटोमेटा सिद्धांत में परिमित राज्य मशीनों के संरचना सिद्धांत के लिए परिवर्तन सेमिग्रुप आवश्यक महत्व के हैं। विशेष रूप से, एक सेमीऑटोमेटन एक ट्रिपल (Σ, एक्स, टी) है, जहां Σ एक गैर-खाली सेट है जिसे इनपुट वर्णमाला कहा जाता है, एक्स एक गैर-खाली सेट है जिसे राज्यों का सेट कहा जाता है और टी एक फ़ंक्शन है

$T\colon \Sigma \times X\to X$

संक्रमण समारोह कहा जाता है। सेमियाटोमेटा प्रारंभिक अवस्था और स्वीकृत राज्यों के सेट की अनदेखी करके नियतात्मक परिमित ऑटोमेटन से उत्पन्न होता है।

एक सेमीऑटोमेटन को देखते हुए, टी_a: X → X, ∈ Σ के लिए, T द्वारा परिभाषित X के परिवर्तन को निरूपित करता है_a(एक्स) = टी (ए, एक्स)। तब {T द्वारा उत्पन्न X के परिवर्तनों का अर्धसमूह_a : a ∈ Σ} को (Σ,X,T) का अभिलाक्षणिक अर्धसमूह या संक्रमण तंत्र कहा जाता है। यह सेमीग्रुप एक मोनोइड है, इसलिए इस मोनोइड को विशेषता या संक्रमण मोनोइड कहा जाता है। इसे कभी-कभी Σ के रूप में भी देखा जाता है^∗- X पर कार्य करें, जहां Σ^∗ वर्णमाला Σ द्वारा उत्पन्न स्ट्रिंग्स का मुक्त मोनोइड है, और स्ट्रिंग्स की कार्रवाई संपत्ति के माध्यम से Σ की कार्रवाई का विस्तार करती है

$T_{vw}=T_{w}\circ T_{v}.$

क्रोहन-रोड्स सिद्धांत

Main article: Krohn–Rhodes theory

क्रोहन-रोड्स सिद्धांत, जिसे कभी-कभी बीजगणितीय ऑटोमेटा सिद्धांत भी कहा जाता है, सरल घटकों को कैस्केडिंग करके परिमित परिवर्तन अर्धसमूहों के लिए शक्तिशाली अपघटन परिणाम देता है।

संदर्भ

• A. H. Clifford and G. B. Preston (1961), The Algebraic Theory of Semigroups, volume 1. American Mathematical Society, ISBN 978-0-8218-0272-4.
• A. H. Clifford and G. B. Preston (1967), The Algebraic Theory of Semigroups, volume 2. American Mathematical Society, ISBN 978-0-8218-0272-4.
• Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000), Monoids, Acts and Categories: with Applications to Wreath Products and Graphs, Expositions in Mathematics 29, Walter de Gruyter, Berlin, ISBN 978-3-11-015248-7.
• Rudolf Lidl and Günter Pilz, Applied Abstract Algebra (1998), Springer, ISBN 978-0-387-98290-8