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

المجموعة المرتبة جزئيًا، أو poset، هي مجموعة مقترنة بعلاقة تعبر عن فكرة أن عنصرًا يسبق أو يقع أسفل عنصر آخر، دون اشتراط أن تكون جميع الأزواج قابلة للمقارنة.

Definition

المجموعة المرتبة جزئيًا هي مجموعة ذات علاقة ثنائية انعكاسية، وغير متماثلة، ومتعدية؛ وقد تكون العناصر قابلة للمقارنة أو غير قابلة للمقارنة بموجب هذه العلاقة.

Scope

يغطي هذا الموضوع بديهيات الترتيب الجزئي، ومخططات هاسه (Hasse diagrams)، والسلاسل والسلاسل المضادة (antichains)، والعناصر القصوى والدنيا، والخرائط الحافظة للترتيب والازدواجية، ونظريات البنية التوافقية لديلورث (Dilworth) وميرسكي (Mirsky). كما يقدم دالة موبيوس (Mobius function) للمجموعة المرتبة جزئيًا، وهي المحرك النظري للترتيب وراء مبدأ الشمول والإقصاء العام.

Core questions

• كيف يتم وضع بديهيات علاقة الأسبقية بين العناصر ورسمها؟
• كيف تُقسّم عناصر المجموعة المرتبة جزئيًا إلى سلاسل أو سلاسل مضادة؟
• ما هي أكبر سلسلة مضادة أو أطول سلسلة في المجموعة المرتبة جزئيًا؟
• كيف تعمم دالة موبيوس العد بمبدأ الشمول والإقصاء؟

Key concepts

• بديهيات الترتيب الجزئي
• مخطط هاسه
• السلاسل والسلاسل المضادة
• العناصر القصوى والدنيا
• نظرية ديلورث
• دالة موبيوس

Key theories

نظرية ديلورث

في أي مجموعة مرتبة جزئيًا محدودة، يساوي الحد الأدنى لعدد السلاسل اللازمة لتغطية جميع العناصر الحد الأقصى لحجم السلسلة المضادة، وهي ازدواجية أساسية للحد الأدنى-الأقصى ذات العديد من النتائج التوافقية.

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

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

Clinical relevance

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

History

لقد أحدثت نظرية السلسلة-السلسلة المضادة لديلورث عام 1950 وأسس روتا (Rota) لدوال موبيوس عام 1964 تحولًا في الدراسة التوافقية للمجموعات المرتبة إلى موضوع محوري في الرياضيات المتقطعة الحديثة.

Key figures

• Robert Dilworth
• Gian-Carlo Rota
• Richard P. Stanley

Seminal works

• davey2002
• stanley2011

Frequently asked questions

ما هو مخطط هاسه؟

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

ما هي السلسلة المضادة؟

السلسلة المضادة هي مجموعة من العناصر لا يوجد اثنان منها قابلان للمقارنة، مثل مجموعة من المجموعات الفرعية لا تحتوي أي منها على الأخرى.