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

"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$-एक्ट को विपरीत अर्धसमूह पर बाएं एक्ट के रूप में व्याख्या किया जा सकता है, जिसमें S के समान अवयव हैं, लेकिन जहां गुणन को कारकों को उलट कर परिभाषित किया गया है,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$.

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

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

S-एक्ट और M-एक्ट

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

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

उदाहरण

• किसी भी अर्धसमूह $(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: रूपांतरण अर्धसमूह

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

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

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

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

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

Main article: अर्धस्वचालित

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

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

ट्रांजिशन फलन कहते हैं। सेमियाटोमेटा प्रारंभिक अवस्था और स्वीकृत अवस्थाओं के सेट की उपेक्षा करके नियतात्मक ऑटोमेटा से उत्पन्न होता है।

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

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

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

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

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

संदर्भ

• 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