الاكتمال (نظرية الترتيب)

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

ينبع الدافع وراء النظر في خصائص الاكتمال من الأهمية الكبيرة للقيم العليا (الحدود العليا الدنيا، والوصلات ، "${\displaystyle \vee }$") و infima (أكبر الحدود الدنيا، يلتقي ، "${\displaystyle \wedge }$تُعدّ نظرية الترتيب الجزئي ذات أهمية بالغة. فإيجاد الحد الأعلى يعني اختيار أصغر عنصر مميز من مجموعة الحدود العليا. من جهة، غالبًا ما تُجسّد هذه العناصر الخاصة خصائص ملموسة تُعدّ مهمة للتطبيق المُحدد (مثل كونها المضاعف المشترك الأصغر لمجموعة من الأعداد أو اتحاد مجموعة من المجموعات). ومن جهة أخرى، فإن معرفة أن أنواعًا معينة من المجموعات الجزئية تضمن وجود حدود عليا أو دنيا تُمكّننا من اعتبار تقييم هذه العناصر عمليات كلية على مجموعة مرتبة جزئيًا. لهذا السبب، غالبًا ما يمكن وصف المجموعات المرتبة جزئيًا ذات خصائص اكتمال معينة بأنها هياكل جبرية من نوع معين. إضافةً إلى ذلك، فإن دراسة خصائص العمليات المُستحدثة تُفضي إلى مواضيع أخرى مثيرة للاهتمام.

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

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

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

كما هو موضح أعلاه، يسمح وجود شروط اكتمال معينة باعتبار تكوين بعض القيم العليا والدنيا عمليات كلية لمجموعة مرتبة جزئيًا. ويتضح أنه في كثير من الحالات، يمكن تحديد الاكتمال بمجرد النظر في البنى الجبرية المناسبة بمعنى الجبر الشامل ، والتي تتضمن عمليات مثل${\displaystyle \vee }$أو${\displaystyle \wedge }$بفرض شروط إضافية (في صورة متطابقات مناسبة ) على هذه العمليات، يمكن استنتاج الترتيب الجزئي الأساسي حصريًا من هذه البنى الجبرية. يمكن الاطلاع على تفاصيل هذا التوصيف في المقالات المتعلقة بالبنى "الشبكية" التي يُنظر فيها عادةً: انظر شبه الشبكة ، والشبكة ، وجبر هيتينغ ، والجبر البولياني . تجدر الإشارة إلى أن البنيتين الأخيرتين توسعان نطاق تطبيق هذه المبادئ ليتجاوز متطلبات الاكتمال، وذلك بإدخال عملية نفي إضافية .

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

لنفترض مجموعة مرتبة جزئيًا ( X , ≤). كمثال بسيط أول، لنفترض أن 1 = {*} هي مجموعة محددة مكونة من عنصر واحد ولها الترتيب الجزئي الوحيد الممكن. يوجد تطبيق واضح j : X → 1 بحيث يكون j ( x ) = * لكل x في X. تحتوي X على أصغر عنصر إذا وفقط إذا كان للدالة j مُرافق سفلي j ^* : 1 → X. في الواقع، يُعطي تعريف اتصالات غالوا أنه في هذه الحالة يكون j ^* (*) ≤ x إذا وفقط إذا كان * ≤ j ( x )، حيث يتحقق الطرف الأيمن بشكل واضح لأي x . وبالمثل، فإن وجود مُرافق علوي لـ j يُكافئ وجود أكبر عنصر في X.

هناك دالة بسيطة أخرى هي الدالة q : X → X × X المعطاة بالعلاقة q ( x ) = ( x , x ). وبطبيعة الحال، فإن علاقة الترتيب المقصودة لـ X × X هي ترتيب الضرب المعتاد . يكون لـ q مُرافق سفلي q ^* إذا وفقط إذا كانت جميع عمليات الربط الثنائية في X موجودة. وعلى العكس من ذلك، فإن عملية الربط${\displaystyle \vee }$يمكن لعملية X × X → X أن توفر دائمًا المرافق السفلي (الفريد بالضرورة) لـ q . وبالمثل، تسمح q بوجود مرافق علوي إذا وفقط إذا كانت X تحتوي على جميع عمليات الالتقاء الثنائية. وبالتالي، فإن عملية الالتقاء${\displaystyle \wedge }$إذا وُجد، فهو دائمًا مُرافق علوي. إذا كان كلاهما${\displaystyle \vee }$و${\displaystyle \wedge }$موجود، بالإضافة إلى ذلك،${\displaystyle \wedge }$إذا كان أيضًا مرافقًا سفليًا، فإن المجموعة الجزئية X هي جبر هيتينغ - وهي فئة خاصة مهمة أخرى من الترتيبات الجزئية.

يمكن الحصول على مزيد من بيانات الاكتمال من خلال استغلال إجراءات الإكمال المناسبة . على سبيل المثال، من المعروف أن مجموعة جميع المجموعات الدنيا لمجموعة جزئية مرتبة X ، مرتبة حسب احتواء المجموعات الجزئية ، تُنتج شبكة كاملة D ( X ) (شبكة المجموعات الدنيا). علاوة على ذلك، يوجد تضمين واضح e : X → D ( X ) يُسقط كل عنصر x من X على مثاليه الرئيسي { y في X | y ≤ x }. يُظهر تأمل بسيط أن e له مُرافق سفلي إذا وفقط إذا كانت X شبكة كاملة. في الواقع، سيُسقط هذا المُرافق السفلي أي مجموعة دنيا من X على قيمتها العليا في X. بتركيب هذا المُرافق السفلي مع الدالة التي تُسقط أي مجموعة جزئية من X على إغلاقها السفلي (مرة أخرى، مُرافق لاحتواء المجموعات الدنيا في مجموعة القوى )، نحصل على خريطة القيمة العليا المعتادة من مجموعة القوى ^2X إلى X. كما في السابق، ثمة حالة مهمة أخرى تحدث عندما تكون هذه الخريطة العليا أيضًا خريطةً مُرافقةً علوية: في هذه الحالة، تكون الشبكة الكاملة X توزيعيةً تمامًا من الناحية البنائية . انظر أيضًا المقالات المتعلقة بالتوزيعية الكاملة والتوزيعية (نظرية الترتيب) .

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

• شبكة توزيعية بالكامل
• الطلب الكلي – الطلب الذي تكون جميع عناصره قابلة للمقارنة 

• جي. ماركوفسكي وبي كي روزن. قواعد لمجموعات جزئية كاملة السلسلة. مجلة آي بي إم للبحوث والتطوير. مارس 1976.
• ستيفن بلوم. أنواع الجبر المرتب. مجلة علوم الحاسوب والأنظمة. أكتوبر 1976.
• مايكل سميث. مجالات القوة . مجلة علوم الحاسوب والأنظمة. 1978.
• دانيال ليمان. حول جبر الرتبة. مجلة علوم الحاسوب والأنظمة. أغسطس 1980.