ترتیب جزئی

یکی از موارد استفاده از رابطه‌ها مرتب کردن بعضی یا همهٔ اعضای یک مجموعه‌است. برای مثال ما برای مرتب کردن کلمات از رابطهٔ متشکل از زوج مرتب‌های (x, y) استفاده می‌کنیم، به شرطی که در ترتیب الفبایی x قبل از y باشد، یا مثلاً می‌توان مجموعهٔ اعداد صحیح را با رابطهٔ متشکل از زوج‌های (x,y) مرتب کرد که x کوچکتر از y باشد. اگر به مثال آخر اعضای (x,x) را اضافه کنیم، به رابطه‌ای می‌رسیم که خواص بازتابی، پادتقارنی و تعدی را داراست.

این سه ویژگی، ویژگی‌های رابطه‌ای است که می‌تواند بخش یا همهٔ اعضای آن مجموعه را مرتب کند.

تعریف

رابطهٔ R روی مجموعهٔ S، مرتب جزئی نامیده می‌شود، اگر دارای خواص بازتابی، پادتقارنی و تعدی باشد. یک مجموعه (S) و رابطهٔ مرتب جزئی روی آن (R) را می‌توان به صورت (S,R) نشان داد.

مثلاً رابطهٔ ≥ روی اعداد صحیح یک رابطهٔ مرتب جزئی است. چون

• به ازای هر عدد صحیح a داریم a≤a.
• به ازای هر دو عدد صحیح a,b، اگر b≤a و a≤b آنگاه a=b.
• به ازای هر سه عدد صحیح a و b و c، اگر b≤a و c≤b. آنگاه c≤a.

اعداد صحیح و رابطه ≥ را می‌توان به صورت (≥,Z) نشان داد.

قرارداد

اگر در مجموعهٔ جزئی مرتبی داشته باشیم a,b)∈R) می‌نویسیم a≤b می‌خوانیمa کوچکتر مساوی b.

این نشانه گذاری ناشی از علامت کوچکتر مساوی در اعداد است. چون رابطهٔ کوچکتر مساوی و اعداد صحیح نمونهٔ بارزی از مجموعه‌های جزئی مرتب است.

علامت ≥ به معنای کوچکتر مساوی بودن دو عضو aو b نیست و برای هر رابطهٔ ترتیب دیگری نیز استفاده می‌شود.

به همین ترتیب می‌نویسیم a<b (می خوانیم a کوچکتر از b) اگر a≤b و a≠b.

ممکن است در یک رابطه مرتب، نتوان همهٔ اعضای مجموعه را با هم مقایسه کرد.

مثلاً مجموعهٔ {A={۱٬۲٬۳٬۴ را در نظر بگیرید اگر (p(A مجموعهٔ توانی A باشد در $(P(A),\subseteq )$ نمی‌توان {۱٬۲} را به {۱٬۳}مربوط کرد. یعنی نه {۱٬۲} کوچکتر مساوی است با {۱٬۳} و نه {۱٬۳} کوچکتر مساوی است با {۱٬۲}.

اعضای قابل مقایسه

دو عضو a و b از یک مجموعه جزئی مرتب را قابل مقایسه می‌نامند اگر یا a≤b یا b≤a. اگر a و b اعضایی از s باشند که نه a≤b و نه b≤a، آنگاه a و b غیرقابل مقایسه هستند.

برای مثال ۵ و ۷ در (|,N) غیرقابل مقایسه‌اند چون نه ۷|۵ و نه ۵|۷.

مجموعه مرتب

اگر هر دو عضو (S, R) قابل مقایسه باشند مجموعهٔ S را مجموعه مرتب (مرتب خطی) می‌نامند. به مجموعهٔ مرتب، زنجیر (chain) نیز می‌گویند.

مثال: ⁺Z نسبت به رابطهٔ ≥ مجموعهٔ مرتب است. چون به ازای هر دو عدد صحیح a و b یا a≤b یا b≤a.

خوش ترتیبی

مجموعهٔ (≥,S) یک مجموعه خوش ترتیب است، اگر مجموعه‌ای مرتب باشد و هر زیر مجموعهٔ ناتهی از آن کوچکترین عضو داشته باشد. اصل استقرای ریاضی را می‌توان با استفاده از خوش ترتیبی اثبات کرد.

اصل استقرای ریاضی

فرض کنید S یک مجموعهٔ خوش ترتیب باشد آنگاه (p(x برای هر x∈S صحیح است، اگر:

مرحلهٔ پایه: (p(x_۰ صحیح است اگر x_۰ کوچکترین عضو S باشد.

مرحلهٔ استقرایی: برای هر y∈S اگر به ازای هر x عضو S که x<y و (P(x درست باشد آنگاه (p(y درست است.

فرض می‌کنیم چنین نباشد یعنی y ای عضو S وجود داشته باشد که (p(y صحیح نباشد. نتیجتاً مجموعهٔ {A={x∈S| P(x) is false تهی نیست و چون S مجموعه‌ای خوش ترتیب بود و A⊆S وA تهی نیست، پس کوچکترین عضو دارد. فرض می‌کنیم این کوچکتیرین عضو a باشد، a نمی‌تواند x_۰ باشد، چون با استفاده از مرحلهٔ پایه استقرا می‌دانیم (p(x_۰ صحیح است. چون a را کوچکترین عضو A گرفتیم، (p(x برای هر x≤a، صحیح است که این نتیجه می‌دهد که (p(a نیز صحیح است که این تناقض است.