نظرية النظام

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
📷 يحتوي على 7 صور
الموسوعة الحرة

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

الخلفية والدوافع

تُعدّ الترتيبات شائعة في الرياضيات والمجالات ذات الصلة، مثل علوم الحاسوب . أول ترتيب يُناقش غالبًا في المرحلة الابتدائية هو الترتيب القياسي للأعداد الطبيعية ، مثل: "2 أصغر من 3"، "10 أكبر من 5"، أو "هل لدى توم عدد أقل من الكعكات من سالي؟". يمكن توسيع هذا المفهوم البديهي ليشمل ترتيبات مجموعات أخرى من الأعداد ، مثل الأعداد الصحيحة والأعداد الحقيقية . فكرة كون عدد ما أكبر من أو أصغر من عدد آخر هي إحدى البديهيات الأساسية لأنظمة الأعداد عمومًا (مع أننا عادةً ما نهتم أيضًا بالفرق الفعلي بين عددين، وهو ما لا يُحدده الترتيب). من الأمثلة الشائعة الأخرى على الترتيبات: الترتيب الأبجدي للكلمات في القاموس، وخاصية النسب في النسب المباشر داخل مجموعة من الناس.

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

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

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

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

تاريخ

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

تم إدراج أسماء المساهمين في الهندسة المرتبة في كتاب مدرسي صدر عام 1961 :

كان باش في عام 1882 أول من أشار إلى إمكانية تطوير هندسة النظام دون الرجوع إلى القياس. وقد تم تحسين نظامه البديهي تدريجياً من قبل بيانو (1889) وهيلبرت (1899) وفيبلين (1904).

— إتش إس إم كوكسيتر ، مقدمة في الهندسة

في عام ١٩٠١، كتب برتراند راسل مقالًا بعنوان "حول مفهوم النظام" [ ١ ] ، مستكشفًا أسس الفكرة من خلال توليد المتسلسلات . ثم عاد إلى الموضوع في الجزء الرابع من كتابه "مبادئ الرياضيات " (١٩٠٣). لاحظ راسل أن العلاقة الثنائية aRb لها معنى ينتقل من a إلى b، بينما للعلاقة العكسية معنى معاكس، وأن المعنى "هو مصدر النظام والمتسلسلات" (ص ٩٥). وأقرّ راسل بأن إيمانويل كانط [ ٢ ] كان "مدركًا للفرق بين التضاد المنطقي وتضاد الإيجابي والسلبي". وكتب أن كانط يستحق التقدير لأنه "لفت الانتباه أولًا إلى الأهمية المنطقية للعلاقات غير المتناظرة".

يُنسب مصطلح " poset " كاختصار لـ "مجموعة مرتبة جزئياً" إلى غاريت بيركوف في الطبعة الثانية من كتابه المؤثر "نظرية الشبكة" . [ 3 ] [ 4 ]

التعريفات الأساسية

يقدم هذا القسم المجموعات المرتبة من خلال البناء على مفاهيم نظرية المجموعات والحساب والعلاقات الثنائية .

مجموعات مرتبة جزئياً

الترتيبات هي علاقات ثنائية خاصة. لنفترض أن P مجموعة وأن ≤ علاقة على P (يُقصد بـ "علاقة على مجموعة" العلاقة بين عناصرها، أي أن ≤ مجموعة جزئية من حاصل الضرب الديكارتي P × P ). عندئذٍ، يكون ≤ ترتيبًا جزئيًا إذا كان انعكاسيًا ، ومتناظرًا عكسيًا ، ومتعديًا ، أي إذا كان لكل a و b و c في P ، لدينا:

a ≤ a (انعكاسية)
إذا كان a ≤ b و b ≤ a فإن a = b (التناظر العكسي)
إذا كان a ≤ b و b ≤ c فإن a ≤ c (خاصية التعدي).

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

a ≤ b أو b ≤ a .

يُطلق على الترتيب الجزئي الذي يتمتع بهذه الخاصية اسم الترتيب الكلي . ويمكن تسمية هذه الترتيبات أيضًا بالترتيبات الخطية أو السلاسل . في حين أن العديد من الترتيبات المألوفة خطية، فإن ترتيب المجموعات الجزئية على المجموعات يُقدم مثالًا على عدم صحة ذلك. مثال آخر هو علاقة قابلية القسمة (أو "عامل من عوامل ") |. بالنسبة لعددين طبيعيين n و m ، نكتب n | m إذا كان n يقسم m بدون باقٍ. من السهل ملاحظة أن هذا يُنتج ترتيبًا جزئيًا. على سبيل المثال، لا يقسم 3 العدد 13 ولا يقسم 13 العدد 3، لذا فإن 3 و 13 ليسا عنصرين قابلين للمقارنة في علاقة قابلية القسمة على مجموعة الأعداد الصحيحة. علاقة التطابق = على أي مجموعة هي أيضًا ترتيب جزئي يكون فيه كل عنصرين مختلفين غير قابلين للمقارنة. وهي أيضًا العلاقة الوحيدة التي تُعد ترتيبًا جزئيًا وعلاقة تكافؤ في آنٍ واحد، لأنها تُحقق كلًا من خاصية التناظر العكسي للترتيبات الجزئية وخاصية التناظر لعلاقات التكافؤ. العديد من الخصائص المتقدمة للمجموعات المرتبة جزئيًا (POSTs) مثيرة للاهتمام بشكل أساسي للترتيبات غير الخطية.

تصور وضعية

مخطط هاس لمجموعة جميع قواسم العدد 60، مرتبة جزئيًا حسب قابلية القسمة

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

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

عناصر خاصة

في المجموعة المرتبة جزئيًا، قد تؤدي بعض العناصر دورًا خاصًا. أبسط مثال على ذلك هو أصغر عنصر في المجموعة المرتبة جزئيًا . على سبيل المثال، 1 هو أصغر عنصر في مجموعة الأعداد الصحيحة الموجبة، والمجموعة الفارغة هي أصغر مجموعة في ترتيب المجموعات الجزئية. رسميًا، يكون العنصر m أصغر عنصر إذا:

m ≤ a ، لجميع العناصر a من الرتبة.

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

قد لا توجد عناصر صغرى وكبرى ، كما يُبين مثال الأعداد الحقيقية. ولكن إن وُجدت، فهي دائمًا فريدة. في المقابل، لننظر إلى علاقة القسمة | على المجموعة {2، 3، 4، 5، 6}. على الرغم من أن هذه المجموعة ليس لها أعلى ولا أسفل، فإن العناصر 2 و3 و5 ليس لها عناصر أدنى منها، بينما 4 و5 و6 ليس لها عناصر أعلى منها. تُسمى هذه العناصر بالعناصر الصغرى والكبرى ، على التوالي. رسميًا، يكون العنصر m أصغر إذا:

a ≤ m يستلزم a = m ، لجميع العناصر a من الرتبة.

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

ترث المجموعات الجزئية من المجموعات المرتبة جزئيًا الترتيب. وقد طبقنا ذلك بالفعل من خلال النظر في المجموعة الجزئية {2، 3، 4، 5، 6} من الأعداد الطبيعية مع ترتيب قابلية القسمة المستحث. الآن، توجد أيضًا عناصر في المجموعة المرتبة جزئيًا تكون مميزة بالنسبة لمجموعة جزئية معينة من هذا الترتيب. وهذا يقودنا إلى تعريف الحدود العليا . بالنظر إلى مجموعة جزئية S من مجموعة مرتبة جزئيًا P ، فإن الحد الأعلى لـ S هو عنصر b من P يقع فوق جميع عناصر S. رسميًا، هذا يعني أن

s ≤ b ، لجميع قيم s في S.

تُحدد الحدود الدنيا مرة أخرى بعكس الترتيب. على سبيل المثال، -5 هو حد أدنى للأعداد الطبيعية كمجموعة جزئية من الأعداد الصحيحة. وبالنظر إلى مجموعة من المجموعات، فإن الحد الأعلى لهذه المجموعات، وفقًا لترتيب المجموعات الجزئية، يُعطى باتحادها . في الواقع، هذا الحد الأعلى مميز للغاية: فهو أصغر مجموعة تحتوي على جميع المجموعات. وبالتالي، نكون قد وجدنا أصغر حد أعلى لمجموعة من المجموعات. يُسمى هذا المفهوم أيضًا بالحد الأعلى أو الانضمام ، وبالنسبة لمجموعة S ، نكتب sup( S ) أو⋁S{\displaystyle \bigvee S}بالنسبة لأصغر حد أعلى لها. وعلى العكس من ذلك، يُعرف أكبر حد أدنى باسم الحد الأدنى أو التقارب ويُرمز له بـ inf( S ) أو⋀S{\displaystyle \bigwedge S}تلعب هذه المفاهيم دورًا هامًا في العديد من تطبيقات نظرية الترتيب. بالنسبة لعنصرين x و y ، يُكتب أيضًاx∨y{\displaystyle x\vee y}وx∧y{\displaystyle x\wedge y}بالنسبة لـ sup({ x , y }) و inf({ x , y })، على التوالي.

على سبيل المثال، 1 هو الحد الأدنى للأعداد الصحيحة الموجبة كمجموعة فرعية من الأعداد الصحيحة.

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

الازدواجية

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

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

إعداد طلبات جديدة

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

كل ترتيب جزئي ≤ يُنتج ما يُسمى بالترتيب الصارم <، وذلك بتعريف a < b إذا كان a ≤ b وليس b ≤ a . يمكن عكس هذا التحويل بجعل a ≤ b إذا كان a < b أو a = b . المفهومان متكافئان، مع أن أحدهما قد يكون أسهل استخدامًا من الآخر في بعض الحالات.

الوظائف بين الطلبات

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

التضمين الترتيبي هو دالة f بين ترتيبين، تحافظ على الترتيب وتعكسه في آنٍ واحد. ويمكن إيجاد أمثلة لهذه التعريفات بسهولة. على سبيل المثال، الدالة التي تربط عددًا طبيعيًا بالعدد التالي له هي دالة رتيبة بالنسبة للترتيب الطبيعي. وأي دالة من ترتيب منفصل، أي من مجموعة مرتبة حسب ترتيب العنصر المحايد، هي أيضًا دالة رتيبة. ويُعد ربط كل عدد طبيعي بالعدد الحقيقي المقابل له مثالًا على التضمين الترتيبي. أما متممة المجموعة على مجموعة القوى فهي مثال على دالة مضادة.

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

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

هناك نوع خاص آخر من التطبيقات الذاتية على مجموعة مرتبة جزئيًا، وهو عوامل الإغلاق ، التي لا تقتصر على كونها رتيبة فحسب، بل هي أيضًا متساوية القوة ، أي f ( x ) = f ( f ( x ))، وشاملة (أو تضخمية )، أي x ≤ f ( x ). ولها تطبيقات عديدة في جميع أنواع "الإغلاقات" التي تظهر في الرياضيات.

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

أخيرًا، يمكن عكس المنظور، والانتقال من دوال الرتب إلى رتب الدوال . في الواقع، يمكن ترتيب الدوال بين مجموعتين جزئيتين P و Q باستخدام الترتيب النقطي . بالنسبة لدالتين f و g ، يكون f ≤ g إذا كان f ( x ) ≤ g ( x ) لجميع عناصر x من P. يحدث هذا، على سبيل المثال، في نظرية المجال ، حيث تلعب فضاءات الدوال دورًا مهمًا.

أنواع خاصة من الطلبات

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

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

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

تنشأ أنواع أخرى كثيرة من الترتيبات عندما يكون وجود الحد الأدنى والحد الأعلى لمجموعات معينة مضمونًا. وبالتركيز على هذا الجانب، الذي يُشار إليه عادةً باكتمال الترتيبات، نحصل على ما يلي:

لكن يمكن المضي قدمًا: إذا وُجدت جميع القيم الدنيا المحدودة غير الفارغة، فيمكن اعتبار ∧ عملية ثنائية كلية بالمعنى الجبر الشامل . وبالتالي، في الشبكة، تتوفر عمليتان ∧ و∨، ويمكن تعريف خصائص جديدة بإعطاء متطابقات، مثل

x  ∧  ( y  ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z ), لجميع x و y و z .         

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

يُقدّم كلا البنيتين عملية جديدة تُسمى النفي . وتلعب كلتاهما دورًا في المنطق الرياضي ، ولا سيما الجبر البولياني الذي له تطبيقات واسعة في علوم الحاسوب . أخيرًا، تجمع بنيات رياضية متنوعة بين الترتيبات وعمليات جبرية أكثر تعقيدًا، كما في حالة الكميات ، مما يسمح بتعريف عملية الجمع.

توجد العديد من الخصائص المهمة الأخرى للمجموعات المرتبة جزئيًا. على سبيل المثال، تكون المجموعة المرتبة جزئيًا منتهية محليًا إذا كانت كل فترة مغلقة [ a , b ] فيها منتهية . وتؤدي المجموعات المرتبة جزئيًا المنتهية محليًا إلى جبر التداخل الذي يمكن استخدامه بدوره لتعريف خاصية أويلر للمجموعات المرتبة جزئيًا المحدودة.

مجموعات جزئية من المجموعات المرتبة

في المجموعة المرتبة، يمكن تعريف أنواع عديدة من المجموعات الجزئية الخاصة بناءً على الترتيب المُعطى. ومن الأمثلة البسيطة على ذلك المجموعات العليا ؛ أي المجموعات التي تحتوي على جميع العناصر التي تقع فوقها في الترتيب. رسميًا، يُعطى الإغلاق العلوي لمجموعة S في مجموعة مرتبة جزئيًا P بالمجموعة { x ∈ P | يوجد عنصر y ∈ S بحيث y ≤ x }. تُسمى المجموعة التي تساوي إغلاقها العلوي مجموعة عليا. وتُعرَّف المجموعات السفلى بشكل معاكس.

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

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

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

الجبر الشامل

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

الطوبولوجيا

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

في المقابل، في نظرية الترتيب، غالبًا ما تُستخدم النتائج الطوبولوجية. توجد طرقٌ عديدة لتعريف المجموعات الجزئية من ترتيبٍ ما، والتي يمكن اعتبارها مجموعاتٍ مفتوحة في طوبولوجيا معينة. عند النظر إلى الطوبولوجيات على مجموعة جزئية مرتبة ( X , ≤) والتي بدورها تُنتج ≤ كترتيب تخصيص لها، فإن أدق هذه الطوبولوجيات هي طوبولوجيا ألكسندروف ، والتي تُعرَّف بأخذ جميع المجموعات العليا كمجموعات مفتوحة. في المقابل، فإن أضعف طوبولوجيا تُنتج ترتيب التخصيص هي الطوبولوجيا العليا ، والتي تحتوي على مكملات المُثُل الرئيسية (أي المجموعات من الشكل { y في X | y ≤ x } لبعض x ) كأساسٍ فرعي . بالإضافة إلى ذلك، قد تكون الطوبولوجيا ذات ترتيب التخصيص ≤ متسقة ترتيبيًا ، مما يعني أن مجموعاتها المفتوحة "غير قابلة للوصول بواسطة المُثُل العليا الموجهة" (بالنسبة إلى ≤). أدق طوبولوجيا متسقة ترتيبيًا هي طوبولوجيا سكوت ، وهي أضعف من طوبولوجيا ألكسندروف. ومن الطوبولوجيات المهمة الأخرى في هذا السياق طوبولوجيا لوسون . توجد صلات وثيقة بين هذه الطوبولوجيات ومفاهيم نظرية الترتيب. على سبيل المثال، تحافظ الدالة على القيم العليا الموجهة إذا وفقط إذا كانت متصلة بالنسبة لطوبولوجيا سكوت (ولهذا السبب تُسمى هذه الخاصية في نظرية الترتيب أيضًا اتصال سكوت ).

نظرية الفئات

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

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

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

انظر أيضاً

ملحوظات

  1. ↑ برتراند راسل (1901) العقل 10(2)
  2. ^ إيمانويل كانط (1763) Ver such den Begriff der Negativen Grosse in die Weltweisheit einzufuhren
  3. ↑ بيركوف 1940 ، ص. 1.
  4. ↑ "أقدم الاستخدامات المعروفة لبعض مصطلحات الرياضيات (P)" . jeff560.tripod.com .
  5. ↑ رولر، مارتن أ. (1998)، مجموعات بوك، وجبر الوسيط، وتأثيرات الزمر. دراسة موسعة لبناء دنوودي ونظرية ساجيف (ملف PDF) ، أرشيف ساوثهامبتون للمطبوعات الأولية، مؤرشف من الأصل (ملف PDF) بتاريخ 4 مارس 2016 ، تم استرجاعه بتاريخ 18 يناير 2015

مراجع