مجموعه‌های مرتب جزئی

مجموعه مرتب جزئی، یا پوزت (poset)، مجموعه‌ای است به همراه یک رابطه که مفهوم تقدم یا قرار گرفتن یک عنصر زیر عنصر دیگر را نشان می‌دهد، بدون اینکه لازم باشد همه جفت‌ها قابل مقایسه باشند.

Definition

مجموعه مرتب جزئی، مجموعه‌ای است با یک رابطه دوتایی که بازتابی (reflexive)، پادتقارنی (antisymmetric) و متعدی (transitive) است؛ عناصر ممکن است تحت این رابطه قابل مقایسه یا غیرقابل مقایسه باشند.

Scope

این موضوع شامل اصول موضوعه ترتیب جزئی، نمودارهای هاسه (Hasse)، زنجیره‌ها و پادزنجیره‌ها (antichains)، عناصر ماکسیمال و مینیمال، نگاشت‌های حافظ ترتیب و دوگانگی، و قضایای ساختار ترکیبیاتی دیلورث (Dilworth) و میرسکی (Mirsky) می‌شود. همچنین تابع موبیوس (Mobius) یک پوزت، که موتور نظریه ترتیب در پس اصل شمول و عدم شمول (inclusion-exclusion) عمومی است، معرفی می‌شود.

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

نمودار هاسه چیست؟

این یک ترسیم از یک پوزت متناهی است که در آن هر عنصر یک نقطه است که بالاتر از عناصری که پوشش می‌دهد قرار می‌گیرد، با یال‌هایی فقط بین جفت‌های پوشاننده، به طوری که ترتیب به سمت بالا خوانده می‌شود.

پادزنجیره چیست؟

پادزنجیره مجموعه‌ای از عناصر است که هیچ دو تای آنها قابل مقایسه نیستند، مانند مجموعه‌ای از زیرمجموعه‌ها که هیچ یک دیگری را شامل نمی‌شود.