أحادي

في الجبر المجرد ، المونويد هو مجموعة مزودة بعملية ثنائية تجميعية وعنصر محايد . على سبيل المثال، تشكل الأعداد الطبيعية مع الجمع مونويد، وعنصرها المحايد هو 0 .

المونويدات هي أنصاف زمر ذات عنصر محايد. وتظهر هذه البنى الجبرية في العديد من فروع الرياضيات.

تشكل الدوال من مجموعة إلى نفسها شبه زمرة بالنسبة لتركيب الدوال. وبشكل أعم، في نظرية الفئات ، تشكل التشكلات من كائن إلى نفسه شبه زمرة، وعلى العكس، يمكن اعتبار شبه الزمرة فئة ذات كائن واحد.

في علوم الحاسوب وبرمجة الحاسوب ، تُعرف مجموعة السلاسل النصية المُنشأة من مجموعة معينة من الأحرف باسم أحادي حر . تُستخدم أحاديات الانتقال والأحاديات التركيبية في وصف آلات الحالة المحدودة . أما أحاديات التتبع وأحاديات التاريخ فتُشكل أساسًا لحسابات العمليات والحوسبة المتزامنة .

في علم الحاسوب النظري ، تعتبر دراسة المونويدات أساسية لنظرية الأوتوماتا ( نظرية كروهن-رودس )، ونظرية اللغة الرسمية ( مشكلة ارتفاع النجمة ).

انظر إلى شبه المجموعة للاطلاع على تاريخ الموضوع، وبعض الخصائص العامة الأخرى للمونيدات.

تُعتبر المجموعة S المزودة بعملية ثنائية S × S → S ، والتي سنرمز لها بـ • ، مجموعة أحادية إذا كانت تحقق البديهيتين التاليتين:

الترابط

بالنسبة لجميع a و b و c في S ، فإن المعادلة ( a • b ) • c = a • ( b • c ) صحيحة.

عنصر الهوية

يوجد عنصر e في S بحيث أنه لكل عنصر a في S ، تكون المتساويات e • a = a و a • e = a صحيحة.

بمعنى آخر، المونويد هو شبه زمرة له عنصر محايد . ويمكن اعتباره أيضًا كتلة صهارية ذات خاصية التجميع والعنصر المحايد. العنصر المحايد في المونويد فريد. ^{[ أ ]} لهذا السبب، يُعتبر العنصر المحايد ثابتًا ، أي عملية صفرية (أو عملية صفرية). وبالتالي، يتميز المونويد بتحديد الثلاثية ( S , •, e ) .

بحسب السياق، قد يُحذف رمز العملية الثنائية، بحيث يُشار إلى العملية بالتجاور ؛ على سبيل المثال، يمكن كتابة بديهيات المونويد على النحو التالي: ( ab ) c = a ( bc ) و ea = ae = a . لا يعني هذا الترميز بالضرورة أنه ضرب أعداد.

المجموعة هي حالة خاصة من المونويد حيث يكون لكل عنصر معكوس.

• من بين 16 عاملًا منطقيًا ثنائيًا ممكنًا ، أربعة منها لها عنصر محايد ثنائي الجانب، وهو أيضًا تبديلي وتجميعي. هذه العوامل الأربعة تجعل المجموعة {خطأ، صحيح} شبه زمرة تبديلية. وفقًا للتعريفات القياسية، فإن AND و XNOR لهما العنصر المحايد صحيح، بينما XOR و OR لهما العنصر المحايد خطأ . شبه الزمر الناتجة عن AND وOR هي شبه زمر متطابقة، بينما شبه الزمر الناتجة عن XOR وXNOR ليست كذلك.
• مجموعة الأعداد الطبيعية N = {0, 1, 2, ...} هي زمرة تبديلية أحادية تحت عملية الجمع (عنصرها المحايد 0 ) أو الضرب (عنصرها المحايد 1 ). تُسمى الزمرة الجزئية من N تحت عملية الجمع زمرة عددية أحادية .
• مجموعة الأعداد الصحيحة الموجبة N ∖ {0} هي مجموعة أحادية تبديلية تحت الضرب (عنصر الوحدة 1 ).
• بالنظر إلى مجموعة A ، فإن مجموعة المجموعات الجزئية من A هي مجموعة أحادية تبديلية تحت التقاطع (العنصر المحايد هو A نفسها).
• بالنظر إلى مجموعة A ، فإن مجموعة المجموعات الجزئية من A هي مجموعة أحادية تبديلية تحت الاتحاد (العنصر المحايد هو المجموعة الفارغة ).
• بتعميم المثال السابق، فإن كل شبه شبكة محدودة هي أحادي تبديلي متطابق .
  • على وجه الخصوص، يمكن تزويد أي شبكة محدودة ببنية أحادية من نوع " التقاطع " و " الوصل ". عناصر الوحدة هي قمة الشبكة وقاعدتها، على التوالي. وباعتبارها شبكات، فإن جبر هيتينغ والجبر البولياني مزودان بهذه البنى الأحادية.
• كل مجموعة أحادية { x } مغلقة تحت عملية ثنائية • تشكل الزمرة التافهة (ذات العنصر الواحد)، وهي أيضًا المجموعة التافهة .
• كل مجموعة هي مجموعة أحادية وكل مجموعة أبيلية هي مجموعة أحادية تبديلية.
• يمكن تحويل أي شبه زمرة S إلى أحادي ببساطة عن طريق إضافة عنصر e غير موجود في S وتعريف e • s = s = s • e لكل s ∈ S. يتم هذا التحويل لأي شبه زمرة إلى أحادي بواسطة الدالة الحرة بين فئة أنصاف الزمر وفئة الأحاديات. ^{[ 3 ]}
  • وبالتالي، يمكن تكوين أحادي متماثل (يُعرف أحيانًا باسم أحادي البحث أولاً ) عن طريق ضم عنصر محايد e إلى شبه المجموعة الصفرية اليسرى على مجموعة S. أما أحادي المقابل (يُسمى أحيانًا أحادي البحث أخيرًا ) فيتكون من شبه المجموعة الصفرية اليمنى على S.
    • أضف عنصرًا محايدًا e إلى شبه المجموعة الصفرية اليسرى التي تحتوي على عنصرين {lt, gt} . عندئذٍ، فإنّ شبه المجموعة المتساوية القوة الناتجة {lt, e , gt} تمثل الترتيب المعجمي لمتتالية معينة بمعرفة ترتيب عناصرها، حيث يمثل e المساواة.
• المجموعة الأساسية لأي حلقة ، مع الجمع أو الضرب كعملية. (بحسب التعريف، الحلقة لها عنصر محايد ضربي يساوي 1 ).
  • الأعداد الصحيحة ، والأعداد النسبية ، والأعداد الحقيقية ، والأعداد المركبة ، مع الجمع أو الضرب كعملية حسابية. ^{[ 4 ]}
  • مجموعة جميع المصفوفات من الرتبة n × n على حلقة معينة، مع جمع المصفوفات أو ضرب المصفوفات كعملية.
• تُشكّل مجموعة جميع السلاسل المنتهية على أبجدية ثابتة Σ شبه زمرة، حيث تكون عملية دمج السلاسل هي العملية الأساسية. وتُمثّل السلسلة الفارغة العنصر المحايد. يُرمز لهذه الشبه زمرة بالرمز Σ ^*، وتُسمى شبه الزمرة الحرة على Σ . وهي غير تبديلية إذا احتوت Σ على عنصرين على الأقل.
• بفرض أي أحادي M ، فإن الأحادي المقابل M ^op له نفس مجموعة الحامل وعنصر الوحدة مثل M ، ويتم تعريف عمليته بواسطة x • ^op y = y • x . أي أحادي تبديلي هو الأحادي المقابل لنفسه.
• _{إذا كان} لدينا مجموعتان M و N مزودتان ببنية أحادية (أو، بشكل عام، أي عدد محدود من الأحاديات، _{M1، ...، Mk} ) ، فإن حاصل ضربهما الديكارتي M × N ، مع تعريف العملية الثنائية وعنصر الوحدة على الإحداثيات المتناظرة، والذي يُسمى حاصل الضرب المباشر ، هو أيضًا أحادي (على التوالي، M1 _× ... × Mk ₎ . ^{[ 5 ]}
• لنفترض وجود أحادي 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 تكون منتهية أيضًا وتحتوي على ⁿ عنصرًا .
• بتعميم المثال السابق، لنفترض أن C فئة و X عنصر من C. تشكل مجموعة جميع التشكلات الداخلية لـ X ، والتي يُرمز لها _بـ EndC ( X ) ، شبه زمرة تحت تركيب التشكلات . لمزيد من المعلومات حول العلاقة بين نظرية الفئات وشبه الزمر، انظر أدناه.
• مجموعة فئات التشاكل الموضعي للأسطح المدمجة ذات المجموع المتصل . عنصرها الوحيد هو فئة الكرة العادية ثنائية الأبعاد. علاوة على ذلك، إذا رمزنا لفئة الطارة بـ a ، ولفئة المستوى الإسقاطي بـ b ، فإن لكل عنصر c من المجموعة الأحادية تعبيرًا فريدًا على الصورة c = na + mb، حيث n عدد صحيح موجب و m = 0 أو 1 أو 2. لدينا 3b = a + b .
• ليكن ⟨f⟩ أحاديًا دوريًا من الرتبة n ، أي ⟨f⟩ = {f₀, f₁, ..., fₙ₋₁}. عندئذٍ، fₙ = fₖ لبعض ⁰ ≤ ^k < n . كل k من ^هذه القيم يُعطي أحاديًا مختلفًا من الرتبة n ، وكل أحادي دوري متماثل مع أحد هذه الأحاديات. علاوة على ذلك، يمكن اعتبار f دالة على النقاط ^{{ 0, 1 , 2} , ..., n₋₁ } المعطاة بـ

$${\displaystyle {\begin{bmatrix}0&1&2&\cdots &n-2&n-1\\1&2&3&\cdots &n-1&k\end{bmatrix}}}$$أو ما يعادل ذلك$${\displaystyle f(i):={\begin{cases}i+1,&{\text{if }}0\leq i<n-1\\k,&{\text{if }}i=n-1.\end{cases}}}$$

يتم بعد ذلك حساب ضرب العناصر في ⟨ f ⟩ عن طريق تركيب الدوال.

عندما k = 0 فإن الدالة f هي تبديل لـ {0، 1، 2، ...، n −1} ، وتعطي المجموعة الدورية الفريدة من الرتبة n .

بحسب بديهيات المونويد، فإن العنصر المحايد e فريد، لأنه إذا كان e و f عنصرين محايدين في مونويد، فإن e = ef = f .

ليكن M أحاديًا، حيث يُرمز للعملية الثنائية بـ • وعنصر الوحدة بـ e . عندئذٍ، يكون الفعل الأيسر على M (أو الفعل الأيسر على M ) عبارة عن مجموعة X مع عملية ⋅  : M × X → X متوافقة مع بنية الأحادي كما يلي:

• لكل x في X : e ⋅ x = x ؛
• لكل a و b في M و x في X : a ⋅ ( b ⋅ x ) = ( a • b ) ⋅ x .

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

التشاكل بين شبهين ( M , *) و ( N , •) هو دالة f : M → N بحيث 

• f ( x * y ) = f ( x ) • f ( y ) لكل x و y في M
• f ( e _M ) = e _N ,

حيث يمثل e _{_M} و e_{_N} العنصرين المحايدين على M و N على التوالي. وتُسمى التشاكلات الأحادية أحيانًا ببساطة بالتشاكلات الأحادية .

ليس كل تشاكل شبه زمرة بين أحاديات هو تشاكل أحاديات، إذ قد لا يُسقط العنصر المحايد على العنصر المحايد للمونويد المستهدف، حتى وإن كان العنصر المحايد هو العنصر المحايد لصورة التشاكل. ^{[ د ]} على سبيل المثال، لنأخذ [ Z ] _ⁿ ، وهي مجموعة فئات البواقي modulo n المزودة بعملية الضرب. تحديدًا، [1] _ⁿ هو العنصر المحايد. الدالة f  : [ Z ] _³ → [ Z ] _⁶ المعطاة بـ [ k ] _³ ↦ [ 3k ] _⁶ هي تشاكل شبه زمرة، لأن [ 3k ⋅ 3l ] _⁶ = [ 9kl ] _⁶ = [ 3kl ] _⁶ . مع ذلك، f ([1] _³ ) = [3] _⁶ ≠ [1] _⁶ ، لذا فإن تشاكل الأحاديات هو تشاكل شبه زمرة بين أحاديات يُسقط العنصر المحايد للمونويد الأول على العنصر المحايد للمونويد الثاني، ولا يمكن إغفال الشرط الأخير.

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

يُطلق على التشاكل الأحادي التقابلي اسم تماثل أحادي . ويُقال إن اثنين من الأحاديات متماثلان إذا كان بينهما تماثل أحادي.

يمكن تمثيل المونويدات ، تمامًا كما يمكن تحديد الزمر من خلال تمثيل الزمرة . ويتم ذلك بتحديد مجموعة من المولدات Σ ، ومجموعة من العلاقات على المونويد الحر Σ ^* . ويتم ذلك بتوسيع العلاقات الثنائية (المنتهية) على Σ ^* إلى تطابقات المونويد، ثم بناء مونويد القسمة، كما سبق.

بفرض وجود علاقة ثنائية R ⊂ Σ ^∗ × Σ ^∗ ، يُعرَّف إغلاقها المتناظر على أنه R ∪ R ⁻¹ . ويمكن تعميم ذلك على علاقة متناظرة E ⊂ Σ ^∗ × Σ ^∗ بتعريف x ~ _E y إذا وفقط إذا كان x = sut و y = svt لبعض السلاسل u و v و s و t ∈ Σ ^∗ حيث ( u , v ) ∈ R ∪ R ⁻¹ . وأخيرًا، يُؤخذ الإغلاق الانعكاسي والمتعدي لـ E ، والذي يُصبح حينها تطابقًا أحاديًا.

في الحالة النموذجية، تُعطى العلاقة R ببساطة كمجموعة من المعادلات، بحيث تكون R = { u ₁ = v ₁ , ..., u _n = v _n } . وبالتالي، على سبيل المثال،

${\displaystyle \langle p,q\,\vert \;pq=1\rangle }$

يمثل هذا التمثيل المعادلة للوحدة الأحادية ثنائية الحلقة ، و

${\displaystyle \langle a,b\,\vert \;aba=baa,bba=bab\rangle }$

هي شبه زمرة لدنة من الدرجة الثانية (رتبتها لانهائية). يمكن كتابة عناصر هذه الشبه الزمرة اللدنة على النحو التالي:${\displaystyle a^{i}b^{j}(ba)^{k}}$بالنسبة للأعداد الصحيحة i و j و k ، كما توضح العلاقات أن ba يتبادل مع كل من a و b .

يمكن اعتبار المونويدات فئة خاصة من الفئات . في الواقع، فإن البديهيات المطلوبة لعملية المونويد هي نفسها المطلوبة لتركيب التشكلات عند تقييدها بمجموعة جميع التشكلات التي يكون مصدرها وهدفها كائنًا معينًا. ^{[ 8 ]} أي،

المونويد هو، في الأساس، نفس الشيء الذي تمثله الفئة ذات الكائن الواحد.

وبشكل أدق، إذا كان لدينا أحادي ( M ، •) ، فيمكننا إنشاء فئة صغيرة تحتوي على عنصر واحد فقط وتكون عناصرها من عناصر M. ويتم تحديد تركيب العناصر من خلال عملية الأحادي • . 

وبالمثل، فإنّ تماثلات المونويد هي مجرد دوال بين فئات الكائنات المفردة. ^{[ 8 ]} لذا، يُعطي هذا البناء تكافؤًا بين فئة المونويدات (الصغيرة) Mon وفئة فرعية كاملة من فئة الفئات (الصغيرة) Cat . وبالمثل، فإنّ فئة الزمر تُكافئ فئة فرعية كاملة أخرى من Cat .

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

تشكل المونويدات، مثلها مثل البنى الجبرية الأخرى، فئة خاصة بها، Mon ، والتي تكون عناصرها مونويدات وتكون مورفيزماتها مورفيزمات مونويدية. ^{[ 8 ]}

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

في علوم الحاسوب، يمكن تزويد العديد من أنواع البيانات المجردة ببنية أحادية. في نمط شائع، تُطوى أو تُجمع سلسلة من عناصر البنية الأحادية لإنتاج قيمة نهائية. على سبيل المثال، تحتاج العديد من الخوارزميات التكرارية إلى تحديث نوع من "المجموع التراكمي" في كل تكرار؛ ويمكن التعبير عن هذا النمط بشكل أنيق باستخدام عملية أحادية. بدلاً من ذلك، تضمن خاصية التجميع في العمليات الأحادية إمكانية موازاة العملية باستخدام مجموع بادئ أو خوارزمية مشابهة، وذلك للاستفادة من المعالجات المتعددة بكفاءة.

بالنظر إلى سلسلة من القيم من النوع M مع عنصر محايد ε وعملية تجميعية • ، يتم تعريف عملية الطي على النحو التالي: $${\displaystyle \mathrm {fold} :M^{*}\rightarrow M=\ell \mapsto {\begin{cases}\varepsilon &{\text{if }}\ell =\mathrm {nil} \\m\bullet \mathrm {fold} \,\ell '&{\text{if }}\ell =\mathrm {cons} \,m\,\ell '\end{cases}}}$$

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

يُعدّ نموذج برمجة MapReduce (انظر: ترميز MapReduce كنموذج أحادي مع طيّ يساري ) أحد تطبيقات المونيدات في علوم الحاسوب. يتألف MapReduce، في الحوسبة، من عمليتين أو ثلاث. عند إعطاء مجموعة بيانات، تتضمن عملية "Map" ربط البيانات العشوائية بعناصر نموذج أحادي مُحدد. أما عملية "Reduce" فتتضمن طيّ هذه العناصر، بحيث نحصل في النهاية على عنصر واحد فقط.

على سبيل المثال، إذا كان لدينا مجموعة متعددة ، فيُمكن تمثيلها في البرنامج كخريطة تربط العناصر بأرقامها. تُسمى العناصر في هذه الحالة بالمفاتيح. قد يكون عدد المفاتيح المميزة كبيرًا جدًا، وفي هذه الحالة، يتم تجزئة المجموعة المتعددة . ولإتمام عملية الاختزال بشكل صحيح، تُعيد مرحلة "الخلط" تجميع البيانات بين العُقد. إذا لم نكن بحاجة إلى هذه الخطوة، فإن عملية Map/Reduce بأكملها تتكون من عملية رسم الخرائط وعملية الاختزال؛ وكلا العمليتين قابلتان للتوازي، الأولى نظرًا لطبيعتها العنصرية، والثانية نظرًا لخاصية التجميع في المونويد.

المونويد الكامل هو مونويد تبديلي مزود بعملية جمع لانهائية${\displaystyle \Sigma _{I}}$لأي مجموعة فهارس I بحيث ^{[ 9 ] [ 10 ] [ 11 ] [ 12 ]}$${\displaystyle \sum _{i\in \emptyset }{m_{i}}=0;\quad \sum _{i\in \{j\}}{m_{i}}=m_{j};\quad \sum _{i\in \{j,k\}}{m_{i}}=m_{j}+m_{k}\quad {\text{ for }}j\neq k}$$ و $${\displaystyle \sum _{j\in J}{\sum _{i\in I_{j}}{m_{i}}}=\sum _{i\in I}m_{i}\quad {\text{ if }}\bigcup _{j\in J}I_{j}=I{\text{ and }}I_{j}\cap I_{j'}=\emptyset \quad {\text{ for }}j\neq j'}$$.

الزمرة التبادلية المرتبة هي زمرة تبادلية M مع ترتيب جزئي ≤ بحيث يكون a ≥ 0 لكل a ∈ M ، و a ≤ b يستلزم a + c ≤ b + c لجميع a و b و c ∈ M.

المونويد المستمر هو مونويد تبديلي مرتب ( M , ≤) حيث يكون لكل مجموعة فرعية موجهة حد أعلى أدنى ، وتكون هذه الحدود العليا الدنيا متوافقة مع عملية المونويد: $${\displaystyle a+\sup S=\sup(a+S)}$$ لكل عنصر a ∈ M ومجموعة فرعية موجهة S من M.

إذا كانت ( M , ≤) شبه زمرة متصلة، فإنه لأي مجموعة فهارس I ومجموعة من العناصر ( aᵢ _{) ᵢ ∈} I _، يمكن تعريف $${\displaystyle \sum _{I}a_{i}=\sup _{{\text{finite }}E\subset I}\;\sum _{E}a_{i},}$$ و M مع عملية الجمع اللانهائية هذه تشكل أحاديًا كاملًا. ^{[ 12 ]}

• أحادي ديكارتي
• علاقات غرين
• الموناد (البرمجة الوظيفية)
• شبه الحلقة وجبر كلين
• مشكلة ارتفاع النجوم
• المربع الفيدي
• فروبينيويد

• "Monoid" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
• وايسشتاين، إريك دبليو. "أحادي" . عالم الرياضيات .
• المونويد في بلانيت ماث .