خوش‌ترتیب

در ریاضیات، یک رابطه خوش ترتیب (یا خوش ترتیبی) روی مجموعه S کاملاً مرتب، دارای این ویژگی است که هر زیر مجموعه ناتهی از آن داری کوچکترین عضو باشد. مجموعه داری ویژگی خوش ترتیبی، مجموعه خوش ترتیب نامیده می‌شود.

روابط دوتایی ترایا
متقارن پادمتقارن کانکس خوش-بنیان ${\displaystyle \vee }$ دارد ${\displaystyle \wedge }$ دارد بازتابی غیربازتابی نامتقارن رابطه هم‌ارزی ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ پیش‌ترتییب (شبه‌ترتیب) ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ ترتیب جزئی ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✗ ✗ پیش-ترتیب کلی ✗ ✗ ✓ ✗ ✗ ✗ ✓ ✗ ✗ ترتیب کلی ✗ ✓ ✓ ✗ ✗ ✗ ✓ ✗ ✗ پیش-خوش‌ترتیب ✗ ✗ ✓ ✓ ✗ ✗ ✓ ✗ ✗ خوش-شبه-ترتیب ✗ ✗ ✗ ✓ ✗ ✗ ✓ ✗ ✗ خوش‌ترتیب ✗ ✓ ✓ ✓ ✗ ✗ ✓ ✗ ✗ مشبکه ✗ ✓ ✗ ✗ ✓ ✓ ✓ ✗ ✗ جوین-نیم-مشبکه ✗ ✓ ✗ ✗ ✓ ✗ ✓ ✗ ✗ میت-نیم-مشبکه ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✗ ✗ جزئی‌مرتب قطعی ✗ ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✓ مجوعه ضعیف‌مرتب ✗ ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✓ ترتیب کلی قطعی ✗ ✓ ✓ ✗ ✗ ✗ ✗ ✓ ✓ تعاریف: برای تمام ${\displaystyle a}$ و ${\displaystyle b}$ ها و ${\displaystyle S\neq \varnothing }$ : ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{not }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}$
علامت "✓" نشان‌دهنده آن است که ویژگی ستونی در تعریف آن سطر لازم است. برای مثال تعریف رابطه هم‌ارزی لازم دارد تا متقارن باشد. به صورت ضمنی همه این تعاریف ترایا و بازتابی می‌باشند. علامت "✗" نشان‌دهنده آن است که ویژگی به طور کلی تضمین نمی‌شود (می‌تواند برقرار باشد، یا نباشد). تمام روابط بالا مستلزم آن است که رابطه همگون ${\displaystyle R}$ ترایا باشد: برای تمام ${\displaystyle a}$ و ${\displaystyle b}$ و ${\displaystyle c}$ ها، اگر ${\displaystyle aRb}$ و ${\displaystyle bRc}$ آنگاه ${\displaystyle aRc}$.

هر مجموعه ناتهی خوش ترتیب یک کوچکترین عضو دارد.هر عضو s از یک مجموعه خوش ترتیب، به جز بزرگترین عضو، یک جانشین یکتا دارد، به عبارت دیگر کوچکترین عضو از زیر مجموعه همه عناصر که از s بزرگتر است. در مجموعه خوش ترتیب S، هر زیرمجموعه Tی دارای کران بالا، کوچکترین کران بالا دارد؛ به عبارت دیگر کوچکترین عنصر از مجموعهٔ زیر مجموعه‌های کران بالای T در مجموعه S. اگر رابطه کوچکتر مساوی (≥) یک رابطه خوش ترتیبِ غیر مؤکد باشد، رابطه کوچکتری (>) یک رابطه خوش ترتیب مؤکد است.تفاوت روابط خوش ترتیب موکد و ناموکد در اغلب موارد نادیده گرفته می‌شود زیرا این دو به راحتی قابل تبدیل به یکدیگر هستند.

نظریه خوش ترتیبی معادل اصل موضوع انتخاب است، این‌گونه که هر مجموعه می‌تواند خوش ترتیب بشود. اگر یک مجموعه خوش ترتیب باشد، تکنیک اثبات استقرای ترامتناهی می‌تواند استفاده شود که برای تمام اعضای مجموعه درست است.

مشاهده می‌شود که اعداد طبیعی به واسطه ی اصل خوش ترتیبی، خوش ترتیب هستند.

اعداد ترتیبی

موقعیت هر عنصر در مجموعه مرتب به‌طور مشابه به وسیله اعداد ترتیبی (اعداد اردینال) نیز بدست می‌آید.

در مورد یک مجموعه متناهی، عملیات اساسی شمارش برای یافتن اعداد ترتیبی یک عضو خاص یا برای یافتن عضوی با ویژگی خاص اعداد ترتیبی، رابطه یک به یک اعداد طبیعی به اعضا اختصاص داده می‌شود. اندازه (تعداد اعضا، کاردینالیتی) یک مجموعه متناهی هم ارز یا برابر نوع ترتیب است. هربار شمارش نوعاً از یک شروع می‌شود، پس به هر عضو از بخش اولیه به همراه آخرین عنصر اختصاص می یابد.توجه داشته باشید که این اعداد با توجه به یک‌ریختی یکی بیشتر از اعداد مرتب هستند، چون برابر با اعضای قبل از آن هستند. بنابراین برای عدد معلوم و محدود n، اصطلاح "nاُمین عنصر" از یک مجموعه خوش ترتیب نیازمند دانستن این است که شمارش از یک شروع شده‌است یا صفر. همچنین "mاُمین عنصر" را در یک مجموعه که نامتناهی است میتوان از صفر شمرد. برای یک مجموعه نامتناهی نوع ترتیب، کاردینالیتی را مشخص میکند؛ ولی برعکس این موضوع صادق نیست. مجموعه‌های خوش ترتیب با کاردینالیتی مشخص ممکن است ترتیب مختلفی داشته باشد. برای یک مجموعه نامتناهی، مجموعه‌ای از انواع ترتیب می‌تواند حتی غیرقابل شمارش باشد.

مثال‌ها و مثال نقض‌ها

اعداد طبیعی

مرتب‌سازی استاندارد رابطه کوچکترمساوی (≥) اعداد طبیعی خوش ترتیب است و دارای این خاصیت است که هر عدد طبیعی غیرصفر یک عنصر پیشین یکتا دارد. یک خوش ترتیبی دیگر از اعداد طبیعی که از تعریف گرفته می‌شود این است که همه اعداد زوج از اعداد فرد بیشترند و برای مرتب‌سازی اعداد فرد و زوج داریم: 0 2 4 6 8 ... 1 3 5 7 9 ...

این یک مجموعه خوش ترتیب با نوع ترتیب ω + ω است. هر عنصر یک جانشین دارد (بزرگترین عنصر وجود ندارد). دو عنصر فاقد عنصر قبلی 0 و 1 هستند.

اعداد صحیح

برخلاف مرتب‌سازی استاندارد ≥ اعداد طبیعی، مرتب‌سازی استاندارد ≥ اعداد صحیح خوش ترتیب نیست، چون برای مثال مجموعه اعداد صحیح منفی کوچکترین عنصر ندارند.

رابطهٔ R برای مثال برای اعداد صحیح خوش ترتیب است، x با y رابطه دارد ( x R y)، اگر یکی از شرایط زیر اتفاق بی افتد:

1. x برابر صفر باشد

2. x مثبت و y منفی باشد

3. x و y هر دو مثبت باشند و x ≤ y

4. x و y هر دو منفی باشند و |y| ≤ |x|

رابطه R می‌تواند مانند زیر باشد:

0 1 2 3 4 ... -1 -2 -3 -4 ...

رابطه R هم ارز با اعداد مرتب ω + ω است.

یک رابطه خوش ترتیب دیگر اعداد صحیح به این صورت تعریف می‌شود: x ≤ y اگر و تنها اگر |x| <|y| یا |x| = |y| و x ≤ y. این رابطه می‌تواند به صورت زیر باشد:

0 -1 1 -2 +2 -3 +3 -4 +4 ...

این رابطه از نوع مرتب ω است.

اعداد حقیقی

مرتب‌سازی استاندارد رابطه کوچکترمساوی ≥ اعداد حقیقی مثبت، خوش ترتیب نیست، زیرا برای مثال، بازهٔ باز صفر تا یک شامل کوچکترین عنصر نیست. مجموعه اعداد اعداد طبیعی خوش ترتیب است.

مجموعه ${\displaystyle {1/n:n=1,2,3,...}}$ کوچکترین عنصر ندارد و بنابراین خوش ترتیب نیست.

مثالهایی از مجموعه‌های خوش ترتیب:

مجموعه اعداد زیر دارای نوع مرتب ω است:

o{ − 2⁻ⁿ | 0 ≤ n <ω }O

مجموعه اعداد زیر دارای نوع مرتب ω² است:

o{ − 2⁻ⁿ − 2^−m−n | 0 ≤ m,n <ω }o

مجموعه اعداد زیر هم دارای نوع مرتب 1+ω است:

o{ − 2⁻ⁿ | 0 ≤ n <ω } ∪ { 1 }o

فرمول‌های معادل

اگر یک مجموعه کاملاً مرتب باشد، جملات زیر معادل هم هستند:

1. مجموعه خوش ترتیب است. به این معنا که هر زیر مجموعه از آن داراری کوچکترین عضو است.
2. استقرای ترامتناهی برای مجموعه داخلی کار میکند.
3. هر کاهش دادن موکد از عناصر مجموعه باید پس از چند قدم متناهی خاتمه یابد.
4. هر زیرمرتب‌سازی هم ارز با بخش اولیه است.

جستارهای وابسته

• ترتیب کامل
• ترتیب جزئی
• قضیه خوش‌ترتیبی
• اصل خوش‌ترتیبی