الجبر F

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

مزودًا بهذه التشاكلات،تشكل الجبريات فئة.
البناء المزدوج هوالجبر المشترك، وهي كائناتبالإضافة إلى التشكل.
أمثلة
المجموعات
تقليديًا، المجموعة هي مجموعةمع قانون المجموعة، مع، والتي تحقق ثلاثة بديهيات: وجود عنصر محايد، ووجود معكوس لكل عنصر من عناصر المجموعة، والترابطية.
لوضع هذا في إطار تصنيفي، عرّف أولاً المحايد والمعكوس كدوال (تشاكلات المجموعة).) بواسطةمع، ومع. هنايشير إلى المجموعة التي تحتوي على عنصر واحدمما يسمح بتحديد العناصرمع التشكلات.
عندئذٍ يصبح من الممكن كتابة بديهيات المجموعة بدلالة الدوال (لاحظ كيف أن المُكمِّم الوجودي غائب):
- ،
- ،
- .
ويمكن التعبير عن ذلك باستخدام المخططات التبادلية: [ 1 ] [ 2 ]
والآن استخدم الضرب المشترك ( الاتحاد المنفصل للمجموعات) لدمج التشاكلات الثلاثة في تشاكل واحد:وفق
- :{1}+G+G\times G&\to &G,\\*&\mapsto &1,\\x&\mapsto &x^{-1},\\(x,y)&\mapsto &x\cdot y.\end{matrix}}}
وبالتالي فإن المجموعة هي-الجبر حيثالدالةلكن العكس ليس صحيحاً بالضرورة. بعض-الجبر حيثالدالةليست مجموعات.
يُستخدم التركيب المذكور أعلاه لتعريف كائنات المجموعة على فئة عشوائية ذات منتجات منتهية وكائن نهائيعندما تقبل الفئة نواتج مشتركة منتهية ، فإن عناصر المجموعة تكونالجبر - على سبيل المثال، المجموعات المنتهية هيالجبر - في فئة المجموعات المنتهية ومجموعات لي هيالجبر - في فئة المشعبات الملساء مع الخرائط الملساء .
البنى الجبرية
بالانتقال خطوةً إلى الأمام في الجبر الشامل ، فإن معظم البنى الجبرية هي جبر- F. على سبيل المثال، الزمر الأبيلية هي جبر- F لنفس الدالة F ( G ) = 1 + G + G × G كما هو الحال بالنسبة للزمر، مع بديهية إضافية للتبديل: m ∘ t = m ، حيث t ( x , y ) = ( y , x ) هي منقولة G × G.
المونويدات هي جبر F ذو إشارة F ( M ) = 1 + M × M. وبالمثل، فإن أنصاف الزمر هي جبر F ذو إشارة F ( S ) = S × S
تُعدّ الحلقات والمجالات والحقول أيضًا جبرًا من النوع F، ولها توقيع يتضمن قانونين: + و•: R × R → R، وعنصر محايد جمعي 0: 1 → R ، وعنصر محايد ضربي 1: 1 → R ، ومعكوس جمعي لكل عنصر -: 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 تحديدًا عندما x ≤ y ). يمكن إعادة صياغة البديهيات التي تقيد التشاكل s لتعريف مجموعة جزئية مرتبة بدلالة التشاكلات. مع ذلك، بما أن المجال المقابل لـ s هو Ω وليس P ، فهو ليس جبرًا من النوع F.
مع ذلك، فإن الشبكات ، وهي ترتيبات جزئية يكون لكل عنصرين فيها حد أعلى وحد أدنى، وخاصة الترتيبات الكلية ، هي جبر F. وذلك لأنه يمكن تعريفها بشكل مكافئ بدلالة العمليات الجبرية: x ∨ y = inf( x , y ) و x ∧ y = sup( x , y )، مع مراعاة بعض البديهيات (التبديلية، والتجميعية، والامتصاص، والتماثل). وبالتالي فهي جبر F من النوع P x P + P x P. ويُقال غالبًا أن نظرية الشبكات تستند إلى كل من نظرية الترتيب والجبر الشامل.
تكرار
لنأخذ الدالة كمثاليرسل ذلك مجموعةل. هنا،يشير إلى فئة المجموعات،يرمز إلى الناتج المشترك المعتاد الناتج عن الاتحاد المنفصل ، وهو كائن نهائي (أي أي مجموعة أحادية ). ثم، المجموعة الأعداد الطبيعية بالإضافة إلى الدالة—وهو الناتج الثانوي للوظائفو— هو جبر F.
الجبر الأولي F
إذا كانت فئة الجبر F لدالة داخلية معينة F تحتوي على عنصر ابتدائي ، فإنها تسمى جبرًا ابتدائيًا .في المثال أعلاه، يمثل جبرًا أوليًا. يمكن الحصول على العديد من هياكل البيانات المحدودة المستخدمة في البرمجة ، مثل القوائم والأشجار ، كجبر أولي لوظائف داخلية محددة.
يمكن اعتبار الأنواع المعرفة باستخدام بنية النقطة الثابتة الصغرى مع الدالة F بمثابة جبر F أولي ، بشرط أن تتحقق خاصية المعلمات للنوع. [ 3 ]
انظر أيضًا الجبر الشامل .
الطرفية F - الجبر المشترك
توجد علاقة مماثلة بين مفهومي النقطة الثابتة العظمى والجبر المشترك النهائي F. يمكن استخدام هذين المفهومين للسماح بوجود كائنات لا نهائية محتملة مع الحفاظ على خاصية التطبيع القوي . [ 3 ] في لغة برمجة Charity ذات التطبيع القوي (أي أن كل برنامج ينتهي بها)، يمكن استخدام أنواع البيانات الاستقرائية المشتركة لتحقيق نتائج مذهلة، مما يتيح تعريف بنيات البحث لتنفيذ وظائف "قوية" مثل دالة أكرمان . [ 4 ]
انظر أيضاً
ملحوظات
- ↑ يجب أن تكون الأسهم الرأسية بدون تسميات في الرسم التخطيطي الثاني فريدة لأن * هو رمز طرفي.
- ↑ بالمعنى الدقيق للكلمة، فإن (i,id) و (id,i) يتم تسميتهما بشكل غير متسق مع المخططات الأخرى حيث أن هذه التشكلات "تقطر" أولاً.
- 1 2 فيليب وادلر: أنواع متكررة مجاناً! مؤرشف في 16-10-2007 في Wayback Machine جامعة غلاسكو، يونيو 1990. مسودة.
- ↑ روبن كوكت : أفكار خيرية ( 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 .
روابط خارجية
- البرمجة الفئوية مع الأنواع الاستقرائية والاستقرائية المشتركة ( مؤرشف بتاريخ 30 نوفمبر 2020 في Wayback Machine ) بقلم فارمو فيني
- فيليب وادلر: أنواع متكررة مجاناً! ( مؤرشف في 30-11-2020 في Wayback Machine ) جامعة غلاسكو، يونيو 1990. مسودة.
- الجبر والجبر المساعد ( مؤرشف بتاريخ 27 أبريل 2019 في أرشيف الإنترنت ) من كليكي
- ب. جاكوبس، ج. روتن: دليل تعليمي حول الجبر (المشترك) والاستقراء (المشترك). نشرة الرابطة الأوروبية لعلوم الحاسوب النظرية ، المجلد 62، 1997، مؤرشف في 12 فبراير 2021 على موقع Wayback Machine
- فهم جبر F ( مؤرشف بتاريخ 4 أغسطس 2020 في أرشيف الإنترنت ) بقلم بارتوش ميليفسكي
- نظرية الفئات
- البرمجة الوظيفية
