Тип порядку

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

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

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

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

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

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

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

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

Доведення

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Посилання

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