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

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

به ازای هر عدد صحیح a داریم a≤aa≤a

به ازای هر دو عدد صحیح a,b، اگر b≤ab≤a و a≤ba≤b آنگاه a=b.

به ازای هر سه عدد صحیح a وb وc، اگر b≤ab≤a و c≤bc≤b. آنگاه c≤ac≤a.

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

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

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

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

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

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

مجموعهٔ (&ge;≥,S) یک مجموعه خوش ترتیب است، اگر مجموعه‌ای مرتب باشد و هر زیر مجموعهٔ ناتهی از آن کوچکترین عضو داشته باشد.

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

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

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