From Wikipedia, the free encyclopedia
مجموعه جزئیمرتب[1] (به انگلیسی: partially ordered set) در ریاضیات و مخصوصاً نظریه ترتیب، «مفهوم شهودی یک ترتیب، پیاپیسازی، یا چینش عناصر یک مجموعه» را صوریسازی میکند و تعمیم میدهد. به مجموعه جزئیمرتب به صورت مخفف، پوسِت (به انگلیسی: poset) هم میگویند. یک پوسِت شامل یک «مجموعه» همراه با یک «رابطه دوتایی» است، که این رابطه بیانگر آن است که برای جفت عنصرهای خاصی در آن مجموعه، یکی از آن عناصر از نظر ترتیبی قبل از دیگری قرار دارد. به چنین رابطهای، «رابطه جزئیمرتب»[1] میگویند.
روابط دوتایی ترایا | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
علامت "✓" نشاندهنده آن است که ویژگی ستونی در تعریف آن سطر لازم است. تمام روابط بالا مستلزم آن است که رابطه همگون ترایا باشد: برای تمام و و ها، اگر و آنگاه . |
![]() |
در اینجا واژه «جزئی» بیانگر آن است که «همه جفت عضوها نیاز به قابل مقایسه بودن ندارند». یعنی ممکن است در یک پوسِت جفت عضوی موجود باشد، که هیچکدام از آن عناصر قبل از دیگری نیست. در واقع «مجموعههای جزئیمرتب» ویژگیهای یک «مجموعههای کاملاً مرتب» (ترتیب کامل) را تعمیم میدهد. در مجموعههای کاملاً مرتب، همه جفت عنصرها قابل مقایسهاند.
یک مجموعه ترتیب جزئی یک رابطه باینری "≥" روی مجموعهٔ (بهطور مثال) 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 است. عملگر دیگر که برای ایجاد این مجموعه به کار میرود، ترکیب موازی است.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.