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

روابط دوتایی ترایا
متقارن پادمتقارن کانکس خوش-بنیان $\vee$ دارد $\wedge$ دارد بازتابی غیربازتابی نامتقارن رابطه هم‌ارزی ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ پیش‌ترتییب (شبه‌ترتیب) ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ ترتیب جزئی ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✗ ✗ پیش-ترتیب کلی ✗ ✗ ✓ ✗ ✗ ✗ ✓ ✗ ✗ ترتیب کلی ✗ ✓ ✓ ✗ ✗ ✗ ✓ ✗ ✗ پیش-خوش‌ترتیب ✗ ✗ ✓ ✓ ✗ ✗ ✓ ✗ ✗ خوش-شبه-ترتیب ✗ ✗ ✗ ✓ ✗ ✗ ✓ ✗ ✗ خوش‌ترتیب ✗ ✓ ✓ ✓ ✗ ✗ ✓ ✗ ✗ مشبکه ✗ ✓ ✗ ✗ ✓ ✓ ✓ ✗ ✗ جوین-نیم-مشبکه ✗ ✓ ✗ ✗ ✓ ✗ ✓ ✗ ✗ میت-نیم-مشبکه ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✗ ✗ جزئی‌مرتب قطعی ✗ ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✓ مجوعه ضعیف‌مرتب ✗ ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✓ ترتیب کلی قطعی ✗ ✓ ✓ ✗ ✗ ✗ ✗ ✓ ✓ تعاریف: برای تمام $a$ و $b$ ها و $S\neq \varnothing$ : ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
علامت "✓" نشان‌دهنده آن است که ویژگی ستونی در تعریف آن سطر لازم است. برای مثال تعریف رابطه هم‌ارزی لازم دارد تا متقارن باشد. به صورت ضمنی همه این تعاریف ترایا و بازتابی می‌باشند. علامت "✗" نشان‌دهنده آن است که ویژگی به طور کلی تضمین نمی‌شود (می‌تواند برقرار باشد، یا نباشد). تمام روابط بالا مستلزم آن است که رابطه همگون $R$ ترایا باشد: برای تمام $a$ و $b$ و $c$ ها، اگر $aRb$ و $bRc$ آنگاه $aRc$.

مجموعه جزئی‌مرتب (به انگلیسی: partially ordered set) در ریاضیات و مخصوصاً نظریه ترتیب، «مفهوم شهودی یک ترتیب، پیاپی‌سازی، یا چینش عناصر یک مجموعه» را صوری‌سازی می‌کند و تعمیم می‌دهد. به مجموعه جزئی‌مرتب به صورت مخفف، پوسِت (به انگلیسی: poset) هم می‌گویند. یک پوسِت شامل یک «مجموعه» همراه با یک «رابطه دوتایی» است، که این رابطه بیانگر آن است که برای جفت عنصرهای خاصی در آن مجموعه، یکی از آن عناصر از نظر ترتیبی قبل از دیگری قرار دارد. به چنین رابطه‌ای، «رابطه جزئی‌مرتب» می‌گویند.

«نمودار هسه» که نمایش‌دهنده مجموعه شامل تمام زیرمجموعه‌های مجموعه سه عضوی {x, y, z} است، و توسط رابطه «شامل بودن» مرتب‌سازی شده‌است. مجموعه‌های مجزا در یک سطح افقی مشابه قابل مقایسه با هم نیستند. همچنین جفت‌های دیگری مثل {x} و {y,z} نیز غیرقابل مقایسه‌اند.

در اینجا واژه «جزئی» بیانگر آن است که «همه جفت عضوها نیاز به قابل مقایسه بودن ندارند». یعنی ممکن است در یک پوسِت جفت عضوی موجود باشد، که هیچ‌کدام از آن عناصر قبل از دیگری نیست. در واقع «مجموعه‌های جزئی‌مرتب» ویژگی‌های یک «مجموعه‌های کاملاً مرتب» (ترتیب کامل) را تعمیم می‌دهد. در مجموعه‌های کاملاً مرتب، همه جفت عنصرها قابل مقایسه‌اند.

تعریف

یک مجموعه ترتیب جزئی یک رابطه باینری "≥" روی مجموعهٔ (به‌طور مثال) P است که خواص بازتابی، تعدی و پادتقارنی داشته باشد.

a ≤ a (بازتابی).

if a ≤ b and b ≤ a, then a = b (پادتقارنی).

if a ≤ b and b ≤ c, then a ≤ c (تعدی).

مجموعه‌ای که دارای خاصیت ترتیب جزئی باشد را POSet می‌نامیم. برای اعضا a و b از مجموعهٔ POSet اگر a ≤ b یا b ≤ a آنگاه a و b را قابل قیاس می‌نامند و در غیر این صورت غیرقابل قیاس. در عکس بالا می‌توان دید که {x} و {x,y,z} قابل قیاس اند ولی {x} و {y} نیستند.

به مجموعه مرتبی که همه اعضا آن قابل قیاس باشد، ترتیب کامل (total order یا linear order) می‌گوییم. یک ترتیب کلی را زنجیر (chain) نیز می‌نامند.

اکسترمم

بزرگترین و کوچکترین عنصر

اگر عنصری همانند g در P باشد.. هنگامی بزرگترین عضو است که به ازای هر a عضو P, a ≤ g و به صورت مشابه برای کوچکترین عضو اگر عنصری همانند m عضو P را در نظر بگیریم m کوچکترین عضو است وقتی به ازای هر a, a ≥ m.

عضو بیشین و عضو کمین

عنصری مانند g از مجموعه p یک عنصر بیشین است. اگر هیچ عنصری همانند a از p نباشد که a> g. به صورت مشابه برای عضو کمین.. عنصری همانند m از P وجود نداشته باشد که g <m. عنصر بیشینه در صورتی وجود دارد که عنصر بیشین یکتا باشد (کمینه است در صورتی که عنصر کمین بکتا باشد).

کران بالا و کران پایین

به صورت مشابه برای کران پایین اگر a ≥ x برای هر عضو a از A. بزرگترین عضو مجموعه (ترتیب جزئی) P نیز کران بالا P است؛ و بهصورت مشابه برای کران پایین.

مثال

برای فهم بهتر مجموعه بخش پذیری روی ۲ را روی اعداد صحیح مثبت در نظر بگیرید. ۱ بر تمامی اعضا بخش پذیر است پس کران پایین است؛ و چون مجموعه نامتناهی است عنصری به عنوان کران بالا ندارد.

ترتیب جزئی در فضاهای توپولوژیک

اگر P یک مجموعه ترتیب جزئی باشد که یک ساختار فضایی به آن داده شده باشد. مرسوم است در نظر بگیریم {(a, b): a ≤ b} یک زیرمجموعه بسته از حاصل ضرب P*P است. با این فرض، ترتیب جزئی به‌طور کلی درست عمل می‌کنند به این معنا که اگر [a<-a[i و b[i]->b برای تمامی iها، a<=b

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

برای ترکیب دو POSet راه دیگر استفاده از جمع خطی است. Z = X ⊕ Y که تحت مجموعه X و Y تنها در صورتی قابل تعریف است که a, b ∈ X with a ≤X b, or a, b ∈ Y with a ≤Y b, or a∈ X and b ∈ Y. که دو مجموعه مرتب جزئی هر دو خوش ترتیب اند. عملیات جمع خطی یکی از عملگر هاییست که برای ایجاد series-parallel partial orders است. عملگر دیگر که برای ایجاد این مجموعه به کار می‌رود، ترکیب موازی است.

جستارهای وابسته

• ترتیب جزئی
• ترتیب کلی
• نمودار هسه

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Partially ordered set». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۸ ژوئن ۲۰۲۰.

• S. Abramsky, A. Jung (1994). "Domain theory" (PDF). In S. Abramsky, D. M. Gabbay, T. S. E. Maibaum (ed.). Handbook of Logic in Computer Science. Vol. III. Oxford University Press. ISBN 0-19-853762-X. Retrieved 2007-10-13.{{cite conference}}: نگهداری یادکرد:نام‌های متعدد:فهرست ویراستاران (link)