У математиці, особливо в теорії множин, кажуть, що дві впорядковані множини X і Y мають однаковий тип порядку якщо вони порядково ізоморфні, тобто, якщо існує бієкція (кожен елемент відповідає рівно одному елементу з іншої множини)
така, що і f, і обернена до неї монотонні (зберігають порядок елементів). В особливому випадку коли X лінійно впорядкована, монотонність f тягне за собою монотонність її обернення.
Наприклад, множина всіх цілих і множина парних цілих мають однаковий тип порядку, бо відображення
це бієкція зі збереженням порядку. Але типи порядку множини цілих і множини раціональних (зі стандартним порядком) відрізняються, бо навіть незважаючи на те, що обидві множини мають однакову потужність (вони зліченно нескінченні), між ними не існує відображення зі збереженням порядку. Інший приклад множин із однаковим типом порядку може бути додатні цілі (мають найменший елемент) і від'ємні цілі (мають найбільший елемент). Відкритий інтервал (0, 1) раціональних чисел порядково ізоморфний всім раціональним (бо, наприклад,
строго зростна бієкція з першої на другу множину).
Через те, що рівність порядків це відношення еквівалентності, вона розбиває клас всіх впорядкованих множин на класи еквівалентності.
Кожна цілком впорядкована множина порядково ізоморфна рівно одному порядковому числу (і цей ізоморфізм унікальний). Тепер ми готові дати таке означення:
Тип порядку цілком впорядкованої множини
це унікальне порядкове число, яке порядково ізоморфно
Тип порядку часто позначають як
Кожна цілком впорядкована множина має тип порядку
[ред. | ред. код]
Щоб довести, що кожна цілком впорядкована множина має тип порядку нам достатньо довести, що кожна цілком впорядкована множина порядково ізморфна деякому порядковому числу.
Нехай
буде цілком впорядкованою множиною. Ми почнемо з використання трансфінітної рекурсії для побудування послідовностей підмножин
.
- База: Нехай
![{\displaystyle S_{0}=\emptyset .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/391c0a8af001ce786827ae34633b0910517a8e55)
- Перехід до наступного: Для всіх порядкових чисел
визначимо
як найменший елемент з
за умови, що
Тоді ![{\displaystyle S_{\alpha +1}=S_{\alpha }\cup \{x_{\alpha }\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e96ae6b423e406dedf5489f6a1e6fc607ab089fe)
- Перехід до границі: Для всіх граничних порядкових чисел
визначити ![{\displaystyle S_{\lambda }=\cup _{\alpha <\lambda }S_{\alpha }.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe60fd44e871971d95df1b296a9056a4024dc609)
Цей процес має завершитись на певному порядковому числі
(де
). Якщо ні, тоді порядкові числа можна вкласти в
з чого випливає, що
занадто велике, щоб бути множиною, що протирічить умові теореми.
Тепер покажемо, що для кожного
множина
порядково ізоморфна
- База:
порядково ізоморфна
через порожню фукнцію, яка монотонна і єдина.
- Перехід до наступного: Припустимо, що
унікально порядково ізоморфна певному
для деякого порядкового числа
Тобто,
це унікальний ізоморфізм порядку.
- Тепер, за визначенням,
де
це найменший елемент
Звідси видно, що
це найбільший елемент з
Тому, ми визначимо функцію
як
для всіх
і ![{\displaystyle f_{\alpha +1}(x_{\alpha })=\alpha .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b681399007afed69a10a55b4ce67471b9772d11)
- Очевидно, що
це порядковий ізоморфізм і він має бути унікальним, бо максимальні елементи відповідають один одному і
унікальна.
- Перехід до границі: Нехай
це граничне порядкове число і припустимо, що
це унікальний ізоморфізм порядку для кожного
Зауважимо, що з того, що
при
випливає, що ці ізоморфізми порядку мають бути узгодженими, тобто, якщо
то
Тепер, визначимо
як ![{\displaystyle f_{\lambda }(x_{\alpha })=f_{\alpha +1}(x_{\alpha }).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8ac2888f4b3ec3c0ee4da2b4841a345d370d8e7)
- Нехай
для
За означенням,
і
Це дає рівність
![{\displaystyle f_{\gamma +1}(x_{\gamma })=f_{\delta +1}(x_{\delta })}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8e4f232a92316d060d72cce049b2917a8ad3704)
- Завдяки тому, що функції узгоджені,
Тоді
отже
і тому
ін'єктивна.
- Тепер, нехай
через те, що
складається з усіх порядкових чисел менших ніж
маємо, що
А з того, що
це граничне порядкове число випливає, що
Отже,
і тому
сюр'єктивна.
- Нехай
Тоді
отже
зберігає порядок.
Насамкінець, за тією ж аргументацією,
унікальна (бо
це ізоморфізм порядку і його звуження до
мусить бути унікальним ізоморфізмом порядку з
).
Отже, за допомогою трансфінітної індукції ми довели, що існує унікальний ізоморфізм порядку з
на
Завдяки способу побудови очевидно, що існує ізоморфізм порядку з
на
а отже існує унікальний ізоморфізм порядку з
на
з чого випливає, що
має тип порядку