پرش به محتوا

ترتیب جزئی: تفاوت میان نسخه‌ها

جز
بدون خلاصۀ ویرایش
جز (←‏قرارداد: اصلاح فاصله مجازی + اصلاح نویسه، replaced: وبرای ← و برای با ویرایشگر خودکار فارسی)
جزبدون خلاصۀ ویرایش
{{بدون منبع}}
 
یکی از موارد استفاده از رابطه‌ها مرتب کردن بعضی یا همهٔ اعضای یک مجموعه‌است. برای مثال ما برای مرتب کردن کلمات از رابطهٔ متشکل از زوج مرتب‌های (x, y) استفاده می‌کنیم، به شرطی که در ترتیب الفبایی x قبل از y باشد، یا مثلاً می‌توان مجموعهٔ [[اعداد صحیح]] را با رابطهٔ متشکل از زوج‌های (x,y) مرتب کرد که x کوچکتر از y باشد. اگر به مثال آخر اعضای (x,x) را اضافه کنیم، به رابطه‌ای می‌رسیم که خواص بازتابی، پادتقارنی و تعدی را داراست.
 
این سه ویژگی، ویژگی‌های رابطه‌ای است که می‌توانمی‌تواند بخش یا همهٔ اعضای آن مجموعه را مرتب کردکند.
 
== تعریف ==
 
مثلاً رابطهٔ ≥ روی اعداد صحیح یک رابطهٔ مرتب جزئی است. چون
* به ازای هر [[عدد صحیح]] a داریم a≤a.
* به ازای هر دو عدد صحیح a,b، اگر b≤a و a≤b آنگاه a=b.
* به ازای هر سه عدد صحیح a وbو وc،b و c، اگر b≤a و c≤b. آنگاه c≤a.
 
اعداد صحیح و رابطه ≥ را می‌توان به صورت (≥,Z) نشان داد.
این [[نشانه گذاری]] ناشی از علامت کوچکتر مساوی در اعداد است. چون رابطهٔ کوچکتر مساوی و اعداد صحیح نمونهٔ بارزی از مجموعه‌های جزئی مرتب است.
 
علامت ≥ به معنای کوچکتر مساوی بودن دو عضوaوعضو aو b نیست و برای هر رابطهٔ ترتیب دیگری نیز استفاده می‌شود.
 
به همین ترتیب می‌نویسیم a<b (می خوانیم a کوچکتر از b) اگر a≤b وa≠bو a≠b.
 
ممکن است در رابطه‌اییک مرتبرابطه‌ مرتب، نتوان همهٔ اعضای مجموعه را با هم مقایسه کرد.
 
مثلاً مجموعهٔ {A={۱٬۲٬۳٬۴ را در نظر بگیرید اگر (p(A [[مجموعهٔ توانی]] A باشد در <math>(P(A),\subseteq)</math> نمی‌توان {۱٬۲} را به {۱٬۳}مربوط کرد. یعنی نه {۱٬۲} کوچکتر مساوی است با {۱٬۳} و نه {۱٬۳} کوچکتر مساوی است با {۱٬۲}.
 
== اعضای قابل مقایسه ==
دو عضوaعضو a و b از یک مجموعه جزئی مرتب را قابل مقایسه می‌نامند اگر یا a≤b یا b≤a. اگر a و b اعضایی از s باشند که نه a≤b و نه b≤a، آنگاه a و b غیر قابل مقایسه هستند.
 
برای مثال ۵ و ۷ در (|,N) غیر قابل مقایسه‌اند چون نه ۷|۵ و نه ۵|۷.
 
== مجموعه مرتب ==
اگر هر دو عضو (S, R) قابل مقایسه باشند مجموعهٔ S را مجموعه مرتب (مرتب خطی) می‌نامند. به مجموعهٔ مرتبمرتب، زنجیر (chain) نیز می‌گویند.
 
مثال: <sup>+</sup>Z نسبت به رابطهٔ ≥ مجموعهٔ مرتب است. چون به ازای هر دو عدد صحیح a وbو b یا a≤b یا b≤a.
 
== خوش ترتیبی ==