ترتیب جزئی: تفاوت میان نسخه‌ها
صفحهٔ جدید: ==ترتيب جزيی== يکي از موارد استفاده از رابطه ها استفاده از آنها براي مرتب کردن بعضي يا همه ي اعضاي ي... |
(بدون تفاوت)
|
نسخهٔ ۲۸ ژوئن ۲۰۰۸، ساعت ۱۸:۵۴
ترتيب جزيی
يکي از موارد استفاده از رابطه ها استفاده از آنها براي مرتب کردن بعضي يا همه ي اعضاي يک مجموعه است. براي مثال ما براي مرتب کردن کلمات از رابطه ي متشکل از زوج مرتب هاي (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={1,2,3,4 را در نظر بگيريد اگر (p(A مجموعه ي تواني A باشد در نمي توان {1,2} را به {1,3}مربوط کرد. يعني نه {1,2} کوچکتر مساوي است با {1,3} و نه {1,3} کوچکتر مساوي است با {1,2}.
تعريف: دو عضوa و b از يک مجموعه جزئي مرتب را قابل مقايسه مي نامند اگر يا a≤b يا b≤a . اگر a و b اعضايي از s باشند که نه a≤b و نه b≤a ، آنگاه a و b غير قابل مقايسه هستند.
براي مثال 5 و 7 در (|,N) غير قابل مقايسه اند چون نه 7|5 و نه 5|7 .
اگر هر دو عضو (S,R) قابل مقايسه باشند مجموعه ي S را مجموعه مرتب ( مرتب خطي) مي نامند. به مجموعه ي مرتب زنجير (chain) نيز مي گويند.
مثال: +Z نسبت به رابطه ی ≥ مجموعه ي مرتب است. چون به ازاي هر دو عدد صحيح a وb يا a≤b يا b≤a .
مجموعه ي (≥,S) يک مجموعه خوش ترتيب است، اگر مجموعه اي مرتب باشد و هر زير مجموعه ي ناتهي از آن کوچکترين عضو داشته باشد. اصل استقراي رياضي را مي توان با استفاده از خوش ترتيبي اثبات کرد.
اصل استقراي رياضي:
فرض کنيد S يک مجموعه ي خوش ترتيب باشد آنگاه (p(x براي هر x∈S صحيح است، اگر:
مرحله ي پايه: (p(x0 صحيح است اگر x0 کوچکترين عضو 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 نمي تواند x0 باشد، چون با استفاده از مرحله ي پايه استقرا مي دانيم (p(x0 صحيح است. چون a را کوچکترين عضو A گرفتيم، (p(x براي هر x≤a، صحيح است که اين نتيجه مي دهد که (p(a نيز صحيح است که اين تناقض است.