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

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

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

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

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

اصل [[استقرای ریاضی]] را می‌توان با استفاده از [[خوش ترتیبی]] اثبات کرد.

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

فرض می‌کنیم چنین نباشد یعنی 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 نیز صحیح است که این تناقض است.