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

از ویکی‌پدیا، دانشنامهٔ آزاد
محتوای حذف‌شده محتوای افزوده‌شده
جز ترتيب جزئی به ترتیب جزئی منتقل شد
برچسب
خط ۱: خط ۱:
{{تمیزکاری}}
{{ویکی‌سازی}}
{{ویکی‌سازی}}
{{بدون منبع}}
{{بدون منبع}}



==ترتیب جزیی==
==ترتیب جزیی==

نسخهٔ ‏۴ اوت ۲۰۰۸، ساعت ۰۷:۲۸

ترتیب جزیی

یکی از موارد استفاده از رابطه‌ها استفاده از آنها برای مرتب کردن بعضی یا همهٔ اعضای یک مجموعه‌است. برای مثال ما برای مرتب کردن کلمات از رابطهٔ متشکل از زوج مرتب‌های (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={۱٬۲٬۳٬۴ را در نظر بگیرید اگر (p(A مجموعهٔ توانی A باشد در نمی‌توان {۱٬۲} را به {۱٬۳}مربوط کرد. یعنی نه {۱٬۲} کوچکتر مساوی است با {۱٬۳} و نه {۱٬۳} کوچکتر مساوی است با {۱٬۲}.

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

برای مثال ۵ و ۷ در (|,N) غیر قابل مقایسه‌اند چون نه ۷|۵ و نه ۵|۷.

اگر هر دو عضو (S,R) قابل مقایسه باشند مجموعهٔ S را مجموعه مرتب (مرتب خطی) می‌نامند. به مجموعهٔ مرتب زنجیر (chain) نیز می‌گویند.

مثال: +Z نسبت به رابطهٔ ≥ مجموعهٔ مرتب است. چون به ازای هر دو عدد صحیح a وb یا a≤b یا b≤a.


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

اصل استقرای ریاضی:

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

مرحلهٔ پایه: (p(x۰ صحیح است اگر x۰ کوچکترین عضو 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۰ باشد، چون با استفاده از مرحلهٔ پایه استقرا می‌دانیم (p(x۰ صحیح است. چون a را کوچکترین عضو A گرفتیم، (p(x برای هر x≤a، صحیح است که این نتیجه می‌دهد که (p(a نیز صحیح است که این تناقض است.