ترتيب جزئي كامل

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

مصطلح الترتيب الجزئي الكامل ، المختصر بـ cpo ، له عدة معانٍ محتملة حسب السياق.

تُسمى المجموعة المرتبة جزئيًا ترتيبًا جزئيًا موجهًا كاملًا ( dcpo ) إذا كان لكل مجموعة فرعية موجهة فيها حد أعلى . (تُسمى المجموعة الفرعية من الترتيب الجزئي موجهة إذا كانت غير فارغة وكان لكل زوج من العناصر حد أعلى في المجموعة الفرعية). في الأدبيات، تظهر مجموعات dcpo أحيانًا تحت مسمى المجموعة المرتبة جزئيًا الموجهة الكاملة .

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

ومن المفاهيم ذات الصلة مفهوم الترتيب الجزئي الكامل ω ( ω-cpo ). وهي عبارة عن مجموعات مرتبة جزئيًا يكون فيها كل سلسلة ω (${\displaystyle x_{1}\leq x_{2}\leq x_{3}\leq ...}$) لها قيمة عليا تنتمي إلى المجموعة المرتبة جزئياً. ويمكن تعميم المفهوم نفسه على أعداد أخرى من السلاسل. ^{[ 1 ]}

كل مجموعة متجهات موجهة مستمرة (dcpo) هي مجموعة متجهات موجهة مستمرة من نوع ω (ω-cpo)، لأن كل سلسلة ω هي مجموعة موجهة، ولكن العكس غير صحيح. مع ذلك، فإن كل مجموعة متجهات موجهة مستمرة من نوع ω (ω-cpo) ذات أساس هي أيضًا مجموعة متجهات موجهة مستمرة (dcpo) (بنفس الأساس). ^{[ 2 ]} تُسمى مجموعة متجهات موجهة مستمرة من نوع ω (dcpo) ذات أساس أيضًا مجموعة متجهات موجهة مستمرة من نوع ω (ω-cpo) (أو مجموعة متجهات موجهة مستمرة مستمرة من نوع ω-cpo).

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

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

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

قياساً على إكمال ديديكيند-ماكنيل لمجموعة مرتبة جزئياً، يمكن تمديد كل مجموعة مرتبة جزئياً بشكل فريد إلى مجموعة مرتبة جزئياً دنيا. ^{[ 1 ]}

• كل مجموعة جزئية منتهية تكون كاملة موجهة.
• جميع الشبكات الكاملة تكون أيضًا شبكات كاملة موجهة.
• لأي مجموعة جزئية مرتبة، تُشكّل مجموعة جميع المرشحات غير الفارغة ، مرتبةً حسب احتواء المجموعة الجزئية ، مجموعة جزئية مرتبة بشكل كامل. وتُشار إليها أيضًا مع المرشح الفارغ. إذا كان الترتيب يحتوي على تقاطعات ثنائية ، فإن هذا البناء (بما في ذلك المرشح الفارغ) يُنتج في الواقع شبكة كاملة .
• يمكن تحويل كل مجموعة S إلى مجموعة dcpo مدببة عن طريق إضافة أصغر عنصر ⊥ وإدخال ترتيب مسطح مع ⊥  ≤ s و s ≤ s لكل s في S وبدون علاقات ترتيب أخرى.   
• يمكن ترتيب مجموعة جميع الدوال الجزئية على مجموعة معينة S بتعريف f  ≤ g إذا وفقط إذا كانت g امتدادًا لـ f ، أي إذا كان مجال f مجموعة جزئية من مجال g ، وكانت قيم f و g متطابقة على جميع المدخلات التي تُعرَّف عليها كلتاهما. (وبصورة مكافئة، f ≤ g إذا وفقط إذا كانت f ⊆ g حيث تُعرَّف f و g برسوماتهما البيانية ). هذا الترتيب هو ترتيب كامل محدود، حيث يكون أصغر عنصر فيه هو الدالة الجزئية غير المعرفة في أي مكان (ذات المجال الفارغ). في الواقع، ≤ هو أيضًا ترتيب كامل محدود . يوضح هذا المثال أيضًا لماذا ليس من الطبيعي دائمًا وجود عنصر أكبر.     
• مجموعة جميع المجموعات الفرعية المستقلة خطيًا من فضاء متجهي V ، مرتبة حسب الاحتواء .
• مجموعة جميع دوال الاختيار الجزئي على مجموعة من المجموعات غير الفارغة ، مرتبة حسب التقييد.
• مجموعة جميع المُثُل الأولية للحلقة ، مرتبة حسب الاحتواء.
• ترتيب التخصص لأي مساحة هادئة هو dcpo.
• لنستخدم مصطلح " النظام الاستنتاجي " كمجموعة من الجمل المغلقة تحت الاستدلال (ولتعريف مفهوم الاستدلال، لنستخدم على سبيل المثال المنهج الجبري لألفريد تارسكي ^{[ 3 ] [ 4 ]} ). توجد نظريات مثيرة للاهتمام تتعلق بكون مجموعة من الأنظمة الاستنتاجية ترتيبًا جزئيًا موجهًا كاملًا. ^{[ 5 ] [ 3 ]} كذلك، يمكن اختيار مجموعة من الأنظمة الاستنتاجية بحيث تحتوي على أصغر عنصر بطريقة طبيعية (بحيث يمكن أن تكون أيضًا ترتيبًا جزئيًا موجهًا كاملًا)، لأن مجموعة جميع نتائج المجموعة الفارغة (أي "مجموعة الجمل القابلة للإثبات منطقيًا/الصحيحة منطقيًا") هي (1) نظام استنتاجي (2) مُحتواة من جميع الأنظمة الاستنتاجية.

( نظرية ماركوفسكي ) تكون المجموعة المرتبة dcpo إذا وفقط إذا كانت كاملة السلسلة؛ أي أن كل سلسلة غير فارغة لها قيمة عليا.

وكنتيجة لذلك، تكون المجموعة المرتبة مجموعة كاملة ذات نقاط إذا وفقط إذا كان لكل سلسلة (قد تكون فارغة) قيمة عليا، أي إذا وفقط إذا كانت كاملة السلسلة . ^{[ 1 ] [ 6 ] [ 7 ] [ 8 ]} وتعتمد البراهين على بديهية الاختيار .

أو بدلاً من ذلك، مجموعة مرتبة${\displaystyle P}$تكون دالة dcpo مدببة إذا وفقط إذا كان كل خريطة ذاتية تحافظ على الترتيب من${\displaystyle P}$يحتوي على نقطة ثابتة دنيا .

تُسمى الدالة f بين مجموعتين موجهتين P و Q (سكوت) متصلة إذا كانت تُحول المجموعات الموجهة إلى مجموعات موجهة مع الحفاظ على قيمها العليا:

• ${\displaystyle f(D)\subseteq Q}$موجه لكل موجه${\displaystyle D\subseteq P}$.
• ${\displaystyle f(\sup D)=\sup f(D)}$لكل موجه${\displaystyle D\subseteq P}$.

لاحظ أن كل دالة متصلة بين dcpos هي دالة رتيبة . هذا المفهوم للاتصالية مكافئ للاتصالية الطوبولوجية المستحثة بواسطة طوبولوجيا سكوت .

يُرمز إلى مجموعة جميع الدوال المتصلة بين مجموعتين جزئيتين كاملتين P و Q بالرمز [ P  → Q ] . وباستخدام الترتيب النقطي ، تُصبح هذه المجموعة أيضًا مجموعة جزئية كاملة، وتُشير إلى النقطة كلما كانت Q مُشارًا إليها. وبالتالي، تُشكل المجموعات الجزئية الكاملة ذات الدوال المتصلة وفقًا لسكوت فئةً مغلقةً ديكارتية . ^{[ 9 ]} 

كل دالة ذاتية تحافظ على الترتيب f لدالة dcpo ذات نقطة محددة ( P , ⊥) لها نقطة ثابتة صغرى. ^{[ 10 ]} إذا كانت f متصلة ^، فإن هذه النقطة الثابتة تساوي القيمة العليا للتكرارات ( ⊥, f (⊥), f ( f (⊥)), ... fn (⊥), ...) لـ ⊥ (انظر أيضًا نظرية كلين للنقطة الثابتة ).

نظرية أخرى للنقطة الثابتة هي نظرية بورباكي-ويت ، التي تنص على أنه إذا${\displaystyle f}$هي دالة من dcpo إلى نفسها ولها الخاصية التالية:${\displaystyle f(x)\geq x}$للجميع${\displaystyle x}$، ثم${\displaystyle f}$لها نقطة ثابتة. ويمكن استخدام هذه النظرية بدورها لإثبات أن لِمّة زورن هي نتيجة لبديهية الاختيار. ^{[ 11 ] [ 12 ]}

• المجموعات الجبرية المرتبة
• طوبولوجيا سكوت
• اكتمال
• نظرية ماركوفسكي

• ديفي، بكالوريوس؛ بريستلي، هـ. أ. (2002). مقدمة في الشبكات والنظام (الطبعة الثانية  ). مطبعة جامعة كامبريدج. رقم ISBN 0-521-78451-4.