ترتیب کلی

در ریاضیات، یک ترتیب کلی (به انگلیسی: Total Order) (اسامی دیگر این رابطه: ترتیب ساده (به انگلیسی: Simple Order)^[۱]، ترتیب خطی (به انگلیسی: Linear Order)، ترتیب کانکس (به انگلیسی: Connex Order)^[۲]، ترتیب پر (به انگلیسی: Full Order)^[۳])، رابطه دوتایی روی مجموعه ای چون ${\displaystyle X}$ است که پاد-تقارنی، ترایایی و کانکس باشد. مجموعه مجهز به ترتیبی کلی را زنجیر (به انگلیسی: Chain)^[۴] یا مجموعه با ترتیب کلی^[۴] یا مجموعه با ترتیب ساده^[۱] یا مجموعه با ترتیب خطی^[۲][۴] (یا مخفف آن به صورت toset^[۵][۶]) یا توست (که مخفف Totally Ordered SET است) هم می گویند.

روابط دوتایی ترایا
متقارن پادمتقارن کانکس خوش-بنیان ${\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}$.

به طور صوری، یک رابطه دوتایی چون ${\displaystyle \leq }$ ترتیبی کلی روی مجموعه ای چون ${\displaystyle X}$ است به طوری که دو گزاره زیر برای تمام ${\displaystyle a}$ و ${\displaystyle b}$ و ${\displaystyle c}$ در ${\displaystyle X}$ برقرار باشند:

بازتابی : ${\displaystyle a\leq a}$

پادتقارنی: اگر ${\displaystyle a\leq b}$ و ${\displaystyle b\leq a}$ آنگاه ${\displaystyle a=b}$؛

ترایایی: اگر ${\displaystyle a\leq b}$ و ${\displaystyle b\leq c}$ آنگاه ${\displaystyle a\leq c}$؛

کانکسی: ${\displaystyle a\leq b}$ یا ${\displaystyle b\leq a}$

خاصیت پاد-تقارنی برخی از حالات نامطلوب مثل زمانی که هم ${\displaystyle a}$ بر ${\displaystyle b}$ تقدم داشته باشد و هم ${\displaystyle b}$ بر ${\displaystyle a}$ را حذف می کند.^[۷]: 325 رابطه ای که خاصیت کانکس بودن را داشته باشد، هر جفت از عناصر مجموعه آن تحت رابطه مورد نظر قابل مقایسه اند. همچنین کانکس بودن بدین معناست که چنین رابطه ای را می توان با کمک نمودار به صورت خطی از عناصر ترسیم کرد، به همین دلیل است که آن را خطی هم می نامند.^[۷]: 330 خاصیت کانکس همچنین بازتابی بودن را نیز نتیجه می دهد، یعنی برای هر عنصر ${\displaystyle a}$ نتیجه می شود ${\displaystyle a\leq a}$. لذا، ترتیب کلی حالت خاصی از یک ترتیب جزئی نیز است، چرا که اگر خاصیت کانکس بودن را در ترتیب کلی تضعیف کنیم به ترتیب جزئی میرسیم. یک توسیع از رابطه با ترتیب جزئی به رابطه با ترتیب کلی را توسیع خطی از آن رابطه ترتیب جزئی نیز می گویند.

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

• ترتیب جزئی
• خوش‌ترتیبی