عمل شبه جماعي

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 43 صور
الموسوعة الحرة

في الجبر وعلوم الحاسوب النظرية ، يُعرف فعل شبه المجموعة على مجموعة ما بأنه قاعدة تربط كل عنصر من عناصر شبه المجموعة بتحويل لتلك المجموعة ، بحيث يكون حاصل ضرب عنصرين من عناصر شبه المجموعة (باستخدام عملية شبه المجموعة ) مرتبطًا بمجموع التحويلين المناظرين. ويشير هذا المصطلح إلى أن عناصر شبه المجموعة تعمل كتحويلات للمجموعة. من منظور جبري ، يُعد فعل شبه المجموعة تعميمًا لمفهوم فعل المجموعة في نظرية المجموعات . أما من منظور علوم الحاسوب، فإن أفعال شبه المجموعة ترتبط ارتباطًا وثيقًا بالأوتوماتا : فالمجموعة تمثل حالة الأوتوماتا، والفعل يمثل تحويلات تلك الحالة استجابةً للمدخلات.

تُعدّ عملية المونويد حالةً خاصةً مهمة ، حيث يكون شبه المجموعة مونويدًا ، ويعمل العنصر المحايد للمونويد كتحويل محايد لمجموعة. من منظور نظرية الفئات ، المونويد فئةٌ ذات عنصر واحد، والعملية دالةٌ من تلك الفئة إلى فئة المجموعات . وهذا يُتيح تعميمًا مباشرًا لعمليات المونويد على عناصر في فئات أخرى غير فئة المجموعات.

ومن الحالات الخاصة المهمة الأخرى شبه المجموعة التحويلية . وهي شبه مجموعة من تحويلات مجموعة ما، وبالتالي لها تأثير تحصيلي على تلك المجموعة. ويرتبط هذا المفهوم بالمفهوم الأعم لشبه المجموعة من خلال نظير لنظرية كايلي .

(ملاحظة حول المصطلحات: تختلف المصطلحات المستخدمة في هذا المجال، وأحيانًا بشكل كبير، من مؤلف لآخر. انظر المقال لمزيد من التفاصيل.)

التعريفات الرسمية

لتكن S شبه زمرة. عندئذٍ، يكون تأثير شبه الزمرة (أو الفعل ) الأيسر لـ S عبارة عن مجموعة X مع عملية •  : S × X → X متوافقة مع عملية شبه الزمرة ∗ كما يلي:

  • لكل s و t في S و x في X ، s • ( t • x ) = ( s ∗ t ) • x .

هذا هو النظير في نظرية شبه الزمر لفعل الزمرة (اليسرى) ، وهو مكافئ لتشاكل شبه الزمرة إلى مجموعة الدوال على X. تُعرَّف أفعال شبه الزمر اليمنى بطريقة مماثلة باستخدام عملية •  : X × S → X التي تحقق ( x • a ) • b = x • ( a ∗ b ) .

إذا كانت M شبه زمرة، فإن فعل شبه الزمرة (أو الفعل ) (الأيسر) لـ M هو فعل شبه زمرة (أيسر) لـ M مع الخاصية الإضافية التالية:

  • لكل x في X : e • x = x

حيث e هو العنصر المحايد في M. وهذا بدوره يُعطي تشاكلًا أحاديًا. تُعرَّف تأثيرات الأحاديات اليمنى بطريقة مماثلة. يُطلق على الأحادي M الذي له تأثير على مجموعة اسم أحادي مؤثر .

يمكن تحويل فعل شبه المجموعة S على X إلى فعل أحادي عن طريق إلحاق عنصر محايد بشبه المجموعة واشتراط أن يعمل كتحويل محايد على X.

المصطلحات والرموز

إذا كانت S شبه زمرة أو أحاديًا، فإن المجموعة X التي تؤثر عليها S كما سبق (على اليسار، على سبيل المثال) تُعرف أيضًا باسم (يسار) تأثير S ، أو مجموعة S ، أو فعل S ، أو معامل S ، أو فعل يساري على S. لا يُميّز بعض المؤلفين بين تأثيرات شبه الزمرة وتأثيرات الأحاديات، إما باعتبار بديهية التطابق ( e • x = x ) فارغةً عندما لا يوجد عنصر تطابق، أو باستخدام مصطلح تأثير S الوحدوي لتأثير S الذي يحتوي على عنصر تطابق. [ 1 ]

تُشابه الخاصية المميزة للفعل خاصية التجميع في عملية شبه المجموعة، ما يعني إمكانية حذف جميع الأقواس. ومن الممارسات الشائعة، خاصةً في علوم الحاسوب، حذف العمليات أيضًا بحيث يُشار إلى كل من عملية شبه المجموعة والفعل من خلال التجاور. وبهذه الطريقة، تؤثر سلاسل الأحرف من المجموعة S على المجموعة X ، كما في التعبير stx حيث s و t في S و x في X.

من الشائع أيضًا العمل بالأفعال اليمنى بدلًا من الأفعال اليسرى. [ 2 ] مع ذلك، يمكن تفسير كل فعل يميني على المجموعة S كفعل يساري على شبه المجموعة المقابلة ، التي لها نفس عناصر المجموعة S، ولكن حيث يُعرَّف الضرب بعكس العوامل، s • t = t • s ، لذا فإن المفهومين متكافئان جوهريًا. هنا، نعتمد بشكل أساسي وجهة نظر الأفعال اليسرى.

أعمال وتحولات

غالباً ما يكون من الملائم (على سبيل المثال، إذا كان هناك أكثر من قانون قيد النظر) استخدام رسالة، مثلتي{\displaystyle T}، للدلالة على الدالة

تي:S×X→X{\displaystyle T\colon S\times X\to X}

تحديدS{\displaystyle S}-الفعل ومن ثم الكتابةتي(s،x){\displaystyle T(s,x)}بدلاً منs⋅x{\displaystyle s\cdot x}ثم لأيs{\displaystyle s}فيS{\displaystyle S}نرمز بـ

تيs:X→X{\displaystyle T_{s}\colon X\to X}

تحوّلX{\displaystyle X}محدد بواسطة

تيs(x)=تي(s،x).{\displaystyle T_{s}(x)=T(s,x).}

من خلال الخاصية المميزة لـS{\displaystyle S}-يمثل،تي{\displaystyle T}يرضي

تيs*ت=تيs∘تيت.{\displaystyle T_{s*t}=T_{s}\circ T_{t}.}

علاوة على ذلك، ضع في اعتبارك دالةs↦تيs{\displaystyle s\mapsto T_{s}}هو نفسهكاري⁡(تي):S→(X→X){\displaystyle \operatorname {curry} (T):S\to (X\to X)}(انظر الكاري ). لأنكاري{\displaystyle \operatorname {curry} }بما أن الدالة تقابلية، يمكن تعريف تأثيرات شبه المجموعة كدوال.S→(X→X){\displaystyle S\to (X\to X)}والتي ترضي

كاري⁡(تي)(s*ت)=كاري⁡(تي)(s)∘كاري⁡(تي)(ت).{\displaystyle \operatorname {curry} (T)(s*t)=\operatorname {curry} (T)(s)\circ \operatorname {curry} (T)(t).}

إنه،تي{\displaystyle T}هو فعل شبه جماعي لـS{\displaystyle S}علىX{\displaystyle X}إذا وفقط إذاكاري⁡(تي){\displaystyle \operatorname {curry} (T)}هو تماثل شبه مجموعة منS{\displaystyle S}إلى أحادي التحويل الكامل لـX{\displaystyle X}.

التشاكلات S

ليكن X و X ′ عمليتين على S. عندئذٍ، يكون التشاكل على S من X إلى X ′ تطبيقًا

F:X→X′{\displaystyle F\colon X\to X'}

بحيث

F(sx)=sF(x){\displaystyle F(sx)=sF(x)}للجميعs∈S{\displaystyle s\in S}وx∈X{\displaystyle x\in X}.

تُكتب مجموعة جميع هذه التشاكلات من النوع S عادةً على النحو التالي:حoمS(X،X′){\displaystyle \mathrm {Hom} _{S}(X,X')}.

يتم تعريف التشاكلات M- لـ M -acts، حيث M أحادي، بنفس الطريقة تمامًا.

قانون S وقانون M

بالنسبة لشبه زمرة ثابتة S ، فإنّ الأفعال اليسارية S هي عناصر فئة، يُرمز لها بـ S -Act، وتكون تشاكلاتها هي التشاكلات S- . ويُرمز أحيانًا للفئة المقابلة للأفعال اليمينية S بـ Act- S . (وهذا يُشابه الفئتين R - Mod و Mod- R للوحدات اليسارية واليمينية على حلقة ).

بالنسبة للوحدة M ، يتم تعريف الفئات M -Act و Act- M بنفس الطريقة.

أمثلة

  • أي شبه مجموعة(S،*){\displaystyle (S,*)}لديه إجراء بشأنS{\displaystyle S}، أين⋅=*{\displaystyle \cdot =*}تتحقق خاصية الفعل بسبب خاصية التجميع لـ*{\displaystyle *}.
  • وبشكل أعم، بالنسبة لأي تشاكل شبه مجموعةF:(S،*)→(تي،⊕){\displaystyle F\colon (S,*)\rightarrow (T,\oplus )}، شبه المجموعة(S،*){\displaystyle (S,*)}لديه إجراء بشأنتي{\displaystyle T}مقدم منs⋅ت=F(s)⊕ت{\displaystyle s\cdot t=F(s)\oplus t}.
  • لأي مجموعةX{\displaystyle X}، يتركX*{\displaystyle X^{*}}لتكن مجموعة متواليات عناصرX{\displaystyle X}شبه المجموعة(شمال،×){\displaystyle (\mathbb {N} ,\times )}لديه إجراء بشأنX*{\displaystyle X^{*}}مقدم منن⋅s=sن{\displaystyle n\cdot s=s^{n}}(أينsن{\displaystyle s^{n}}يشيرs{\displaystyle s}كررن{\displaystyle n}مرات).
  • شبه المجموعة(شمال،×){\displaystyle (\mathbb {N} ,\times )}له الحق في اتخاذ الإجراء الصحيح(شمال،⋅){\displaystyle (\mathbb {N} ,\cdot )}، مقدمة منx⋅y=xy{\displaystyle x\cdot y=x^{y}}.

أنصاف مجموعات التحويل

يُشرح أدناه التناظر بين أنصاف الزمر التحويلية وتأثيرات أنصاف الزمر. وإذا اقتصرنا على تأثيرات أنصاف الزمر الأمينة ، فإنه يتمتع بخصائص مميزة.

يمكن تحويل أي شبه زمرة تحويلية إلى فعل شبه زمرة من خلال البناء التالي. لأي شبه زمرة تحويليةS{\displaystyle S}لX{\displaystyle X}، تعريف فعل شبه المجموعةتي{\displaystyle T}لS{\displaystyle S}علىX{\displaystyle X}مثلتي(s،x)=s(x){\displaystyle T(s,x)=s(x)}لs∈S،x∈X{\displaystyle s\in S,x\in X}هذا الفعل يتسم بالإخلاص، وهو ما يعادلجuررy(تي){\displaystyle curry(T)}كونه حقني .

وعلى العكس من ذلك، بالنسبة لأي فعل شبه جماعيتي{\displaystyle T}لS{\displaystyle S}علىX{\displaystyle X}، تعريف شبه مجموعة تحويلS′={تيs|s∈S}{\displaystyle S'=\{T_{s}\mid s\in S\}}في هذا البناء "ننسى" المجموعةS{\displaystyle S}.S′{\displaystyle S'}يساوي صورة​جuررy(تي){\displaystyle curry(T)}لنرمز إلىجuررy(تي){\displaystyle curry(T)}مثلو{\displaystyle f}للاختصار. إذاو{\displaystyle f}إذا كانت دالة أحادية ، فإنها تكون تماثلًا شبه زمر منS{\displaystyle S}لS′{\displaystyle S'}بمعنى آخر، إذاتي{\displaystyle T}إذا كنا أوفياء، فلن ننسى شيئًا مهمًا. ويتضح هذا الادعاء من خلال الملاحظة التالية: إذا حوّلناS′{\displaystyle S'}العودة إلى العمل شبه الجماعيتي′{\displaystyle T'}لS′{\displaystyle S'}علىX{\displaystyle X}، ثمتي′(و(s)،x)=تي(s،x){\displaystyle T'(f(s),x)=T(s,x)}للجميعs∈S،x∈X{\displaystyle s\in S,x\in X}.تي{\displaystyle T}وتي′{\displaystyle T'}هي "متماثلة" عبرو{\displaystyle f}أي أننا تعافينا بشكل أساسيتي{\displaystyle T}وبالتالي، لا يرى بعض المؤلفين [ 3 ] أي فرق بين أفعال شبه المجموعة الأمينة وشبه مجموعات التحويل.

تطبيقات في علوم الحاسوب

شبه آلية

تُعدّ أنصاف الزمر التحويلية ذات أهمية جوهرية لنظرية بنية الآلات ذات الحالات المحدودة في نظرية الأوتوماتا . على وجه الخصوص، تُعرَّف شبه الأوتوماتا بأنها ثلاثية (Σ, X , T )، حيث Σ هي مجموعة غير فارغة تُسمى أبجدية الإدخال ، وX هي مجموعة غير فارغة تُسمى مجموعة الحالات ، و T هي دالة.

تي:Σ×X→X{\displaystyle T\colon \Sigma \times X\to X}

تُسمى دالة الانتقال . تنشأ الآلات شبه الآلية من الآلات الحتمية عن طريق تجاهل الحالة الأولية ومجموعة حالات القبول.

بفرض وجود آلة شبه آلية، ولتكن T a : X → X ، حيث a ∈ Σ، التحويل المعرف لـ X بالعلاقة T a ( x ) = T ( a , x ). عندئذٍ ، تُسمى شبه زمرة تحويلات X المولدة بواسطة { Ta : a ∈ Σ} شبه الزمرة المميزة أو نظام الانتقال لـ (Σ, X , T ). هذه شبه الزمرة هي أحادي، لذا يُسمى هذا الأحادي الأحادي المميز أو أحادي الانتقال . يُنظر إليه أحيانًا أيضًا على أنه تأثير Σ * على X ، حيث Σ * هو الأحادي الحر للسلاسل المولد بواسطة الأبجدية Σ، [ ملاحظة 1 ] ، ويمتد تأثير السلاسل إلى تأثير Σ عبر الخاصية 

تيvw=تيw∘تيv.{\displaystyle T_{vw}=T_{w}\circ T_{v}.}

نظرية كروهن-رودس

تُعطي نظرية كروهن-رودس، والتي تُسمى أحيانًا أيضًا نظرية الأوتوماتا الجبرية ، نتائج تفكيك قوية لمجموعات التحويل المحدودة عن طريق تسلسل المكونات الأبسط.

ملحوظات

  1. ↑ عملية المونويد هي عملية الربط؛ عنصر الهوية هو السلسلة الفارغة.

مراجع

  1. ^ كيلب وكناور وميخاليف، 2000، الصفحات 43-44.
  2. ^ كيلب، كناور وميخاليف، 2000.
  3. ↑ أربيب، مايكل أ.، محرر. (1968). النظرية الجبرية للآلات واللغات وشبه المجموعات . نيويورك ولندن: أكاديميك برس. ص  83.
  • أ. هـ. كليفورد وج . ب. بريستون (1961)، النظرية الجبرية لأنصاف الزمر ، المجلد 1. الجمعية الرياضية الأمريكية، رقم ISBN 978-0-8218-0272-4.
  • أ. هـ. كليفورد وج. ب. بريستون (1967)، النظرية الجبرية لأنصاف الزمر ، المجلد 2. الجمعية الرياضية الأمريكية، رقم ISBN 978-0-8218-0272-4.
  • ماتي كيلب، أولريش كناور، ألكسندر ف. ميخاليف (2000)، المونويدات، والأفعال، والفئات: مع تطبيقات على جداءات الإكليل والرسوم البيانية ، سلسلة عروض في الرياضيات 29 ، والتر دي جرويتر، برلين، ISBN 978-3-11-015248-7.
  • رودولف ليدل وجونتر بيلز، الجبر التجريدي التطبيقي (1998)، سبرينغر، ISBN 978-0-387-98290-8