الجبر F

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

في الرياضيات ، وتحديداً في نظرية الفئات ، تعمم جبر F مفهوم البنية الجبرية . إن إعادة كتابة القوانين الجبرية بدلالة التشكلات يزيل جميع الإشارات إلى العناصر الكمية من البديهيات، ويمكن بعد ذلك ربط هذه القوانين الجبرية معاً بدلالة دالة واحدة F ، وهي التوقيع .

يمكن أيضًا استخدام الجبر F لتمثيل هياكل البيانات المستخدمة في البرمجة ، مثل القوائم والأشجار .

المفاهيم الرئيسية ذات الصلة هي الجبر الأولي F الذي يمكن أن يغلف مبدأ الاستقراء، والجبر المشترك F للبناء المزدوج .

تعريف

لوج{\displaystyle C}هي فئة ، وF:جج{\displaystyle F:C\rightarrow C}هو وظيفة داخلية لـج{\displaystyle C}ثمF{\displaystyle F}- الجبر عبارة عن مجموعة مرتبة(أ،α){\displaystyle (A,\alpha )}، أينأ{\displaystyle A}هو موضوعج{\displaystyle C}وα{\displaystyle \alpha }هوج{\displaystyle C}- التشكلF(أ)أ{\displaystyle F(A)\rightarrow A}الشيءأ{\displaystyle A}يُطلق عليه اسم حامل الجبر. وعندما يسمح السياق بذلك، يُشار إلى الجبر غالبًا بحامله فقط بدلاً من المجموعة المرتبة.

تماثل منF{\displaystyle F}-الجبر(أ،α){\displaystyle (A,\alpha )}إلىF{\displaystyle F}-الجبر(ب،β){\displaystyle (B,\beta )}هوج{\displaystyle C}-مورفيزمو:أب{\displaystyle f:A\rightarrow B}بحيثوα=βF(و){\displaystyle f\circ \alpha =\beta \circ F(f)}، وفقًا للمخطط التبادلي التالي :

مزودًا بهذه التشاكلات،F{\displaystyle F}تشكل الجبريات فئة.

البناء المزدوج هوF{\displaystyle F}الجبر المشترك، وهي كائناتأ*{\displaystyle A^{*}}بالإضافة إلى التشكلα*:أ*F(أ*){\displaystyle \alpha ^{*}:A^{*}\rightarrow F(A^{*})}.

أمثلة

المجموعات

تقليديًا، المجموعة هي مجموعةجي{\displaystyle G}مع قانون المجموعةم:جي×جيجي{\displaystyle m:G\times G\rightarrow G}، معم(x،y)=xy{\displaystyle m(x,y)=x\cdot y}، والتي تحقق ثلاثة بديهيات: وجود عنصر محايد، ووجود معكوس لكل عنصر من عناصر المجموعة، والترابطية.

لوضع هذا في إطار تصنيفي، عرّف أولاً المحايد والمعكوس كدوال (تشاكلات المجموعة).جي{\displaystyle G}) بواسطةهـ:1جي{\displaystyle e:1\rightarrow G}معهـ(*)=1{\displaystyle e(*)=1}، وأنا:جيجي{\displaystyle i:G\rightarrow G}معأنا(x)=x-1{\displaystyle i(x)=x^{-1}}. هنا1{\displaystyle 1}يشير إلى المجموعة التي تحتوي على عنصر واحد1={*}{\displaystyle 1=\left\{*\right\}}مما يسمح بتحديد العناصرxجي{\displaystyle x\in G}مع التشكلات1جي{\displaystyle 1\rightarrow G}.

عندئذٍ يصبح من الممكن كتابة بديهيات المجموعة بدلالة الدوال (لاحظ كيف أن المُكمِّم الوجودي غائب):

  • xجي،yجي،zجي،م(م(x،y)،z)=م(x،م(y،z)){\displaystyle \forall x\in G,\forall y\in G,\forall z\in G,m(m(x,y),z)=m(x,m(y,z))}،
  • xجي،م(هـ(*)،x)=م(x،هـ(*))=x{\displaystyle \forall x\in G,m(e(*),x)=m(x,e(*))=x}،
  • xجي،م(أنا(x)،x)=م(x،أنا(x))=هـ(*){\displaystyle \forall x\in G,m(i(x),x)=m(x,i(x))=e(*)}.

ويمكن التعبير عن ذلك باستخدام المخططات التبادلية: [ 1 ] [ 2 ]

مخطط تبادلي يوضح خاصية الارتباط.            مخطط تبادلي يوضح خاصية الانعكاس.            مخطط تبادلي يوضح خاصية العنصر المحايد.            

والآن استخدم الضرب المشترك ( الاتحاد المنفصل للمجموعات) لدمج التشاكلات الثلاثة في تشاكل واحد:α=هـ+أنا+م{\displaystyle \alpha =e+i+m}وفق

α:1+جي+جي×جيجي،*1،xx-1،(x،y)xy.{\displaystyle {\begin{matrix}\alpha :{1}+G+G\times G&\to &G,\\*&\mapsto &1,\\x&\mapsto &x^{-1},\\(x,y)&\mapsto &x\cdot y.\end{matrix}}}

وبالتالي فإن المجموعة هيF{\displaystyle F}-الجبر حيثF{\displaystyle F}الدالةF(جي)=1+جي+جي×جي{\displaystyle F(G)=1+G+G\times G}لكن العكس ليس صحيحاً بالضرورة. بعضF{\displaystyle F}-الجبر حيثF{\displaystyle F}الدالةF(جي)=1+جي+جي×جي{\displaystyle F(G)=1+G+G\times G}ليست مجموعات.

يُستخدم التركيب المذكور أعلاه لتعريف كائنات المجموعة على فئة عشوائية ذات منتجات منتهية وكائن نهائي1{\displaystyle 1}عندما تقبل الفئة نواتج مشتركة منتهية ، فإن عناصر المجموعة تكونF{\displaystyle F}الجبر - على سبيل المثال، المجموعات المنتهية هيF{\displaystyle F}الجبر - في فئة المجموعات المنتهية ومجموعات لي هيF{\displaystyle F}الجبر - في فئة المشعبات الملساء مع الخرائط الملساء .

البنى الجبرية

بالانتقال خطوةً إلى الأمام في الجبر الشامل ، فإن معظم البنى الجبرية هي جبر- F. على سبيل المثال، الزمر الأبيلية هي جبر- F لنفس الدالة F ( G ) = 1 + G + G × G كما هو الحال بالنسبة للزمر، مع بديهية إضافية للتبديل: mt = m ، حيث t ( x , y ) = ( y , x ) هي منقولة G × G.

المونويدات هي جبر F ذو إشارة F ( M ) = 1 + M × M. وبالمثل، فإن أنصاف الزمر هي جبر F ذو إشارة F ( S ) = S × S

تُعدّ الحلقات والمجالات والحقول أيضًا جبرًا من النوع ولها توقيع يتضمن قانونين: + و•: R × R R، وعنصر محايد جمعي 0: 1 R ، وعنصر محايد ضربي 1: 1 R ، ومعكوس جمعي لكل عنصر -: R R. وبما أن جميع هذه الدوال تشترك في نفس المجال المقابل فيمكن دمجها في دالة توقيع واحدة 1 + 1 + R + R × R + R × R R ، مع بديهيات للتعبير عن التجميعية والتوزيعية ، وما إلى ذلك. وهذا يجعل الحلقات جبرًا من النوع F على فئة المجموعات ذات التوقيع 1 + 1 + R + R × R + R × R.

بدلاً من ذلك، يمكننا النظر إلى الدالة F ( R ) = 1 + R × R في فئة الزمر الأبيلية . في هذا السياق، يكون الضرب تشاكلاً، أي أن m ( x + y , z ) = m ( x , z ) + m ( y , z ) و m ( x , y + z ) = m ( x , y ) + m ( x , z )، وهما شرطا التوزيع تحديداً. بالتالي، الحلقة هي جبر F ذو إشارة 1 + R × R على فئة الزمر الأبيلية، والذي يحقق بديهيتين (التجميعية والعنصر المحايد للضرب).

عندما نأتي إلى الفضاءات المتجهة والوحدات النمطية ، فإن دالة التوقيع تتضمن عملية ضرب قياسية k × E E ، ويتم تحديد التوقيع F ( E ) = 1 + E + k × E بواسطة k على فئة الحقول أو الحلقات.

يمكن اعتبار الجبر على حقل ما بمثابة جبر F ذي توقيع 1 + 1 + A + A × A + A × A + k × A على فئة المجموعات، وذي توقيع 1 + A × A على فئة الوحدات (وحدة ذات ضرب داخلي)، وذي توقيع k × A على فئة الحلقات (حلقة ذات ضرب قياسي)، عندما تكون تجميعية ووحدوية.

شعرية

ليست كل البنى الرياضية جبرًا من النوع F. على سبيل المثال، يمكن تعريف مجموعة جزئية مرتبة P باستخدام مصطلحات فئوية مع تشاكل s : P × P Ω، على مصنف كائنات فرعية (Ω = {0,1} في فئة المجموعات و s ( x , y ) = 1 تحديدًا عندما xy ). يمكن إعادة صياغة البديهيات التي تقيد التشاكل s لتعريف مجموعة جزئية مرتبة بدلالة التشاكلات. مع ذلك، بما أن المجال المقابل لـ s هو Ω وليس P ، فهو ليس جبرًا من النوع F.

مع ذلك، فإن الشبكات ، وهي ترتيبات جزئية يكون لكل عنصرين فيها حد أعلى وحد أدنى، وخاصة الترتيبات الكلية ، هي جبر F. وذلك لأنه يمكن تعريفها بشكل مكافئ بدلالة العمليات الجبرية: xy = inf( x , y ) و xy = sup( x , y )، مع مراعاة بعض البديهيات (التبديلية، والتجميعية، والامتصاص، والتماثل). وبالتالي فهي جبر F من النوع P x P + P x P. ويُقال غالبًا أن نظرية الشبكات تستند إلى كل من نظرية الترتيب والجبر الشامل.

تكرار

لنأخذ الدالة كمثالF:SهـتSهـت{\displaystyle F:\mathrm {\bf {Set}} \to \mathrm {\bf {Set}} }يرسل ذلك مجموعةX{\displaystyle X}ل1+X{\displaystyle 1+X}. هنا،Sهـت{\displaystyle \mathrm {\bf {Set}} }يشير إلى فئة المجموعات،+{\displaystyle +}يرمز إلى الناتج المشترك المعتاد الناتج عن الاتحاد المنفصل ، و1{\displaystyle 1}هو كائن نهائي (أي أي مجموعة أحادية ). ثم، المجموعة شمال{\displaystyle \mathbb {N} }الأعداد الطبيعية بالإضافة إلى الدالة[zهـرo،suجج]:1+شمالشمال{\displaystyle [\mathrm {zero} ,\mathrm {succ} ]:1+\mathbb {N} \to \mathbb {N} }—وهو الناتج الثانوي للوظائفzهـرo:10{\displaystyle \mathrm {zero} :1\mapsto 0}وsuجج:نن+1{\displaystyle \mathrm {succ} :n\mapsto n+1}— هو جبر F.

الجبر الأولي F

إذا كانت فئة الجبر F لدالة داخلية معينة F تحتوي على عنصر ابتدائي ، فإنها تسمى جبرًا ابتدائيًا .(شمال،[zهـرo،suجج]){\displaystyle (\mathbb {N} ,[\mathrm {zero} ,\mathrm {succ} ])}في المثال أعلاه، يمثل جبرًا أوليًا. يمكن الحصول على العديد من هياكل البيانات المحدودة المستخدمة في البرمجة ، مثل القوائم والأشجار ، كجبر أولي لوظائف داخلية محددة.

يمكن اعتبار الأنواع المعرفة باستخدام بنية النقطة الثابتة الصغرى مع الدالة F بمثابة جبر F أولي ، بشرط أن تتحقق خاصية المعلمات للنوع. [ 3 ]

انظر أيضًا الجبر الشامل .

الطرفية F - الجبر المشترك

توجد علاقة مماثلة بين مفهومي النقطة الثابتة العظمى والجبر المشترك النهائي F. يمكن استخدام هذين المفهومين للسماح بوجود كائنات لا نهائية محتملة مع الحفاظ على خاصية التطبيع القوي . [ 3 ] في لغة برمجة Charity ذات التطبيع القوي (أي أن كل برنامج ينتهي بها)، يمكن استخدام أنواع البيانات الاستقرائية المشتركة لتحقيق نتائج مذهلة، مما يتيح تعريف بنيات البحث لتنفيذ وظائف "قوية" مثل دالة أكرمان . [ 4 ]

انظر أيضاً

ملحوظات

  1. يجب أن تكون الأسهم الرأسية بدون تسميات في الرسم التخطيطي الثاني فريدة لأن * هو رمز طرفي.
  2. بالمعنى الدقيق للكلمة، فإن (i,id) و (id,i) يتم تسميتهما بشكل غير متسق مع المخططات الأخرى حيث أن هذه التشكلات "تقطر" أولاً.
  3. 1 2 فيليب وادلر: أنواع متكررة مجاناً! مؤرشف في 16-10-2007 في Wayback Machine جامعة غلاسكو، يونيو 1990. مسودة.
  4. روبن كوكت : أفكار خيرية ( ps مؤرشف بتاريخ 29-12-2020 في Wayback Machine و ps.gz مؤرشف بتاريخ 29-12-2020 في Wayback Machine )

مراجع

  • بيرس، بنجامين سي. (1991). " جبر- F ". نظرية الفئات الأساسية لعلماء الحاسوب . مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 0-262-66071-7.
  • بار، مايكل؛ ويلز، تشارلز (1990). نظرية الفئات لعلوم الحاسوب . نيويورك: برنتيس هول. ص  355. ISBN 0131204866. OCLC 19126000 .