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

جز
جز (ربات: ویرایش جزئی)
{{بدون منبع}}
 
یکی از موارد استفاده از رابطه‌ها مرتب کردن بعضی یا همهٔ اعضای یک مجموعه‌است. برای مثال ما برای مرتب کردن کلمات از رابطهٔ متشکل از زوج مرتب‌های (x,y) استفاده می‌کنیم، به شرطی که در ترتیب الفبایی x قبل از y باشد، یا مثلامثلاً می‌توان مجموعهٔ [[اعداد صحیح]] را با رابطهٔ متشکل از زوج‌های (x,y) مرتب کرد که x کوچکتر از y باشد. اگر به مثال آخر اعضای (x,x) را اضافه کنیم، به رابطه‌ای می‌رسیم که خواص بازتابی، پادتقارنی و تعدی را داراست.
 
این سه ویژگی، ویژگی‌های رابطه‌ای است که می‌توان بخش یا همهٔ اعضای آن را مرتب کرد.
 
مثلاً رابطهٔ ≥ روی اعداد صحیح یک رابطهٔ مرتب جزئی است. چون
* به ازای هر [[عدد صحیح]] a داریم a≤a
 
* به ازای هر عدد صحیح a داریم a≤a
* به ازای هر دو عدد صحیح a,b، اگر b≤a و a≤b آنگاه a=b.
 
* به ازای هر سه عدد صحیح a وb وc، اگر b≤a و c≤b. آنگاه c≤a.
 
اگر در مجموعهٔ جزئی مرتبی داشته باشیم a,b)∈R) می‌نویسیم a≤b می‌خوانیمa کوچکتر مساوی b.
 
این [[نشانه گذاری]] ناشی از علامت کوچکتر مساوی در اعداد است. چون رابطهٔ کوچکتر مساوی و اعداد صحیح نمونهٔ بارزی از مجموعه‌های جزئی مرتب است.
 
علامت ≥ به معنای کوچکتر مساوی بودن دو عضوaو b نیست وبرای هر رابطهٔ ترتیب دیگری نیز استفاده می‌شود.
ممکن است در رابطه‌ای مرتب نتوان همهٔ اعضای مجموعه را با هم مقایسه کرد.
 
مثلامثلاً مجموعهٔ {A={۱٬۲٬۳٬۴ را در نظر بگیرید اگر (p(A [[مجموعهٔ توانی]] A باشد در <math>(P(A),\subseteq)</math> نمی‌توان {۱٬۲} را به {۱٬۳}مربوط کرد. یعنی نه {۱٬۲} کوچکتر مساوی است با {۱٬۳} و نه {۱٬۳} کوچکتر مساوی است با {۱٬۲}.
 
== اعضای قابل مقایسه ==
 
== خوش ترتیبی ==
مجموعهٔ (≥,S) یک [[مجموعه خوش ترتیب]] است، اگر مجموعه‌ای مرتب باشد و هر زیر مجموعهٔ ناتهی از آن کوچکترین عضو داشته باشد.
اصل [[استقرای ریاضی]] را می‌توان با استفاده از [[خوش ترتیبی]] اثبات کرد.
 
=== اصل استقرای ریاضی ===
 
فرض کنید S یک مجموعهٔ [[خوش ترتیب]] باشد آنگاه (p(x برای هر x∈S صحیح است، اگر:
 
مرحلهٔ پایه: (p(x<sub>۰</sub> صحیح است اگر x<sub>۰</sub> کوچکترین عضو 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<sub>۰</sub> باشد، چون با استفاده از مرحلهٔ پایه استقرا می‌دانیم (p(x<sub>۰</sub> صحیح است. چون a را کوچکترین عضو A گرفتیم، (p(x برای هر x≤a، صحیح است که این نتیجه می‌دهد که (p(a نیز صحیح است که این تناقض است.
 
[[رده:ریاضیات پایه]]
[[رده:ویکی‌سازی رباتیک]]