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

جز
ربات : جراحی پلاستیک
(برچسب)
جز (ربات : جراحی پلاستیک)
تعریف: رابطهٔ R روی مجموعهٔ S، مرتب جزئی نامیده می‌شود، اگر دارای خواص بازتابی، پادتقارنی و تعدی باشد. یک مجموعه (S) و رابطهٔ مرتب جزئی روی آن (R) را می‌توان به صورت (S,R) نشان داد.
 
مثال: رابطهٔ ≥ روی اعداد صحیح یک رابطهٔ مرتب جزئی است. چون
 
به ازای هر عدد صحیح 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={۱٬۲٬۳٬۴ را در نظر بگیرید اگر (p(A مجموعهٔ توانی A باشد در <math>(P(A),\subseteq)</math> نمی‌توان {۱٬۲} را به {۱٬۳}مربوط کرد. یعنی نه {۱٬۲} کوچکتر مساوی است با {۱٬۳} و نه {۱٬۳} کوچکتر مساوی است با {۱٬۲}.
 
تعریف: دو عضوa و b از یک مجموعه جزئی مرتب را قابل مقایسه می‌نامند اگر یا a&le;ba≤b یا b&le;ab≤a. اگر a و b اعضایی از s باشند که نه a&le;ba≤b و نه b&le;a،b≤a، آنگاه a و b غیر قابل مقایسه هستند.
 
برای مثال ۵ و ۷ در (|,N) غیر قابل مقایسه‌اند چون نه ۷|۵ و نه ۵|۷.
اگر هر دو عضو (S,R) قابل مقایسه باشند مجموعهٔ S را مجموعه مرتب (مرتب خطی) می‌نامند. به مجموعهٔ مرتب زنجیر (chain) نیز می‌گویند.
 
مثال: <sup>+</sup>Z نسبت به رابطهٔ &ge; مجموعهٔ مرتب است. چون به ازای هر دو عدد صحیح a وb یا a&le;ba≤b یا b&le;ab≤a.
 
----
مجموعهٔ (&ge;,S) یک مجموعه خوش ترتیب است، اگر مجموعه‌ای مرتب باشد و هر زیر مجموعهٔ ناتهی از آن کوچکترین عضو داشته باشد.
اصل استقرای ریاضی را می‌توان با استفاده از خوش ترتیبی اثبات کرد.
 
اصل استقرای ریاضی:
 
فرض کنید S یک مجموعهٔ خوش ترتیب باشد آنگاه (p(x برای هر x&isin;Sx∈S صحیح است، اگر:
 
مرحلهٔ پایه: (p(x<sub>۰</sub> صحیح است اگر x<sub>۰</sub> کوچکترین عضو 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<sub>۰</sub> باشد، چون با استفاده از مرحلهٔ پایه استقرا می‌دانیم (p(x<sub>۰</sub> صحیح است. چون a را کوچکترین عضو A گرفتیم، (p(x برای هر x&le;a،x≤a، صحیح است که این نتیجه می‌دهد که (p(a نیز صحیح است که این تناقض است.
۱۷۶٬۴۸۳

ویرایش