Тип порядку

У математиці, особливо в теорії множин, кажуть, що дві впорядковані множини X і Y мають однаковий тип порядку якщо вони порядково ізоморфні, тобто, якщо існує бієкція (кожен елемент відповідає рівно одному елементу з іншої множини) $f\colon X\to Y$ така, що і f, і обернена до неї монотонні (зберігають порядок елементів). В особливому випадку коли X лінійно впорядкована, монотонність f тягне за собою монотонність її обернення.

Наприклад, множина всіх цілих і множина парних цілих мають однаковий тип порядку, бо відображення $n\mapsto 2n$ це бієкція зі збереженням порядку. Але типи порядку множини цілих і множини раціональних (зі стандартним порядком) відрізняються, бо навіть незважаючи на те, що обидві множини мають однакову потужність (вони зліченно нескінченні), між ними не існує відображення зі збереженням порядку. Інший приклад множин із однаковим типом порядку може бути додатні цілі (мають найменший елемент) і від'ємні цілі (мають найбільший елемент). Відкритий інтервал (0, 1) раціональних чисел порядково ізоморфний всім раціональним (бо, наприклад, $f(x)={\tfrac {2x-1}{1-\vert {2x-1}\vert }}$ строго зростна бієкція з першої на другу множину).

Через те, що рівність порядків це відношення еквівалентності, вона розбиває клас всіх впорядкованих множин на класи еквівалентності.

Тип порядку цілковитих впорядкувань

Кожна цілком впорядкована множина порядково ізоморфна рівно одному порядковому числу (і цей ізоморфізм унікальний). Тепер ми готові дати таке означення:

Тип порядку цілком впорядкованої множини $(S,\leq )$ це унікальне порядкове число, яке порядково ізоморфно $(S,\leq ).$ Тип порядку часто позначають як $\operatorname {Ord} (S,\leq ).$

Кожна цілком впорядкована множина має тип порядку

Щоб довести, що кожна цілком впорядкована множина має тип порядку нам достатньо довести, що кожна цілком впорядкована множина порядково ізморфна деякому порядковому числу.

Доведення

Нехай $(S,\leq )$ буде цілком впорядкованою множиною. Ми почнемо з використання трансфінітної рекурсії для побудування послідовностей підмножин $(S,\leq )$.

• База: Нехай $S_{0}=\emptyset .$
• Перехід до наступного: Для всіх порядкових чисел $\alpha ,$ визначимо $x_{\alpha }$ як найменший елемент з $S\setminus S_{\alpha },$ за умови, що $S\setminus S_{\alpha }\neq \emptyset .$ Тоді $S_{\alpha +1}=S_{\alpha }\cup \{x_{\alpha }\}.$
• Перехід до границі: Для всіх граничних порядкових чисел $\lambda ,$ визначити $S_{\lambda }=\cup _{\alpha <\lambda }S_{\alpha }.$

Цей процес має завершитись на певному порядковому числі $\beta$ (де $S-S_{\beta }=\emptyset$). Якщо ні, тоді порядкові числа можна вкласти в $S,$ з чого випливає, що $S$ занадто велике, щоб бути множиною, що протирічить умові теореми.

Тепер покажемо, що для кожного $\alpha <\beta$ множина $S_{\alpha }$ порядково ізоморфна $\alpha .$

• База: $S_{0}=\emptyset$ порядково ізоморфна $0=\emptyset$ через порожню фукнцію, яка монотонна і єдина.
• Перехід до наступного: Припустимо, що $S_{\alpha }$ унікально порядково ізоморфна певному $\alpha$ для деякого порядкового числа $\alpha <\beta .$ Тобто, $f_{\alpha }:S_{\alpha }\rightarrow \alpha$ це унікальний ізоморфізм порядку.

Тепер, за визначенням, $S_{\alpha +1}=S_{\alpha }\cup \{x_{\alpha }\},$ де $x_{\alpha }$ це найменший елемент $S\setminus S_{\alpha }.$ Звідси видно, що $x_{\alpha }$ це найбільший елемент з $S_{\alpha +1}.$ Тому, ми визначимо функцію $f_{\alpha +1}:S_{\alpha +1}\rightarrow \alpha +1$ як $f_{\alpha +1}(x)=f_{\alpha }(x)$ для всіх $x\in S_{\alpha }$ і $f_{\alpha +1}(x_{\alpha })=\alpha .$

Очевидно, що $f_{\alpha +1}$ це порядковий ізоморфізм і він має бути унікальним, бо максимальні елементи відповідають один одному і $f_{\alpha }$ унікальна.

• Перехід до границі: Нехай $\lambda \leq \beta$ це граничне порядкове число і припустимо, що $f_{\alpha }:S_{\alpha }\rightarrow \alpha$ це унікальний ізоморфізм порядку для кожного $\alpha <\lambda .$ Зауважимо, що з того, що $S_{\gamma }\subset S_{\delta }$ при $\gamma <\delta$ випливає, що ці ізоморфізми порядку мають бути узгодженими, тобто, якщо $\gamma <\delta ,$ то $f_{\gamma +1}(x_{\gamma })=f_{\delta }(x_{\gamma }).$ Тепер, визначимо $f_{\lambda }:S_{\lambda }\rightarrow \lambda$ як $f_{\lambda }(x_{\alpha })=f_{\alpha +1}(x_{\alpha }).$

Нехай $f_{\lambda }(x_{\gamma })=f_{\lambda }(x_{\delta })$ для $\gamma \leq \delta <\lambda .$ За означенням, $f_{\lambda }(x_{\gamma })=f_{\gamma +1}(x_{\gamma })$ і $f_{\lambda }(x_{\delta })=f_{\delta +1}(x_{\delta }).$ Це дає рівність

$f_{\gamma +1}(x_{\gamma })=f_{\delta +1}(x_{\delta })$

Завдяки тому, що функції узгоджені, $f_{\gamma +1}(x_{\gamma })=f_{\delta +1}(x_{\gamma }).$ Тоді $f_{\delta +1}(x_{\gamma })=f_{\delta +1}(x_{\delta }),$ отже $x_{\gamma }=x_{\delta }$ і тому $f_{\lambda }$ ін'єктивна.

Тепер, нехай $\alpha \in \lambda$ через те, що $\lambda$ складається з усіх порядкових чисел менших ніж $\lambda$ маємо, що $\alpha <\lambda .$ А з того, що $\lambda$ це граничне порядкове число випливає, що $\alpha +1<\lambda .$ Отже, $f_{\lambda }(x_{\alpha })=f_{\alpha +1}(x_{\alpha })=\alpha ,$ і тому $f_{\lambda }$ сюр'єктивна.

Нехай $x_{\gamma }<x_{\delta }\in S_{\lambda }.$ Тоді $f_{\lambda }(x_{\lambda })=f_{\delta +1}(x_{\gamma })<f_{\delta +1}(x_{\delta }),$ отже $f$ зберігає порядок.

Насамкінець, за тією ж аргументацією, $f_{\lambda }$ унікальна (бо $f_{\lambda }$ це ізоморфізм порядку і його звуження до $S_{\alpha }$ мусить бути унікальним ізоморфізмом порядку з $\alpha$).

Отже, за допомогою трансфінітної індукції ми довели, що існує унікальний ізоморфізм порядку з $S_{\beta }$ на $\beta .$ Завдяки способу побудови очевидно, що існує ізоморфізм порядку з $(S,\leq )$ на $\beta ,$ а отже існує унікальний ізоморфізм порядку з $(S,\leq )$ на $\beta$ з чого випливає, що $(S,\leq )$ має тип порядку $\beta .$

Посилання

• Weisstein, Eric W. Тип порядку(англ.) на сайті Wolfram MathWorld.