مجموعه جزئاً مرتب

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در ریاضیات بخصوص مبحث تئوری ترتیب، مجموعه مرتب جزیی (POSet)(Partialy Ordered Set) مجموعه‌ای است که بصورت کلی مفهوم ترتیب را می‌تواند بصورت فرمولی شده روی کاغذ پیاده کند. یک مجموعه مرتب جزیی شامل روابط باینری است بگونه‌ای که یک عضو بر عضو دیگر برتری می‌گیرد. چنین رابطه‌ای را ترتیب جزیی می‌نامیم.

diagram

تعریف[ویرایش]

یک مجموعه ترتیب جزیی یک رابطه باینری "≥" روی مجموعهٔ (بطور مثال) 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 است. عملگر دیگر که برای ایجاد این مجموعه به کار می‌رود، ترکیب موازی است.

منابع[ویرایش]

  • S. Abramsky, A. Jung (1994). "Domain theory" (PDF). In S. Abramsky, D. M. Gabbay, T. S. E. Maibaum, editors,. Handbook of Logic in Computer Science III. Oxford University Press. ISBN 0-19-853762-X. Retrieved 2007-10-13. 

جستارهای وابسته[ویرایش]