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

"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-एक्ट', 'S-सेट', 'S-एक्शन', '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$, $X$ पर $S$ की एक अर्धसमूह क्रिया है यदि और केवल यदि $\operatorname {curry} (T)$, $S$ से $X$ के पूर्ण रूपांतरण मोनोइड के लिए एक अर्धसमूह समरूपता है।

S-समरूपता

मान लीजिए कि 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