Ординал

Ординалы (от англ. ordinal — порядковый) — класс чисел, описывающих тип порядка в вполне упорядоченных множествах. В большинстве случаев ординалы так же презентуются как продолжение для натуральных чисел дольше бесконечности. Ординалы используются для описания роста функций с помощью быстрорастущей иерархии и появляются на пересечении гугологии с теорией множеств.

Определение

Есть несколько методов введения в ординалы.

Как продолжение натуральных чисел

Самое простое и интуитивное из них это продолжение неотрицательных целых чисел за бесконечность. Мы так же имеем числа 0, 1, 2, 3, 4, 5..., однако мы вводим символ для бесконечности — $\omega$. $\omega$ это так же наименьший трансфинитный ординал (т. е. больший всех конечных чисел). С $\omega$ мы можем производить арифметические операции, например добавить 1, тогда мы получим $\omega+1$. Однако стоит заметить, что $\omega+1$ вовсе не то же самое, что и $1 + \omega$, второе в свою очередь равно просто $\omega$. Мы можем продолжить — $\omega+1$, $\omega+2$, $\omega+3$, $\omega+4$, $\omega + 5$...

Так мы придем к ординалу $\omega + \omega$, или $\omega \times 2$. Опять же стоит заметить, что $\omega \times 2$ отличается от $2 \times \omega$, второе в свою очередь равно просто $\omega$. Мы можем продолжить, $\omega \times 2 + \omega$ = $\omega \times 3$, $\omega \times 4$,$\omega \times 5$... $\omega \times \omega = \omega^2$. Мы можем продолжить умножать на $\omega$, $\omega^3$, $\omega^4$, $\omega^5$... $\omega^{\omega}$,$\omega^{\omega^{\omega}}$,$\omega^{\omega^{\omega^{\omega}}}$... Конечно, можно создавать и большие ординалы, но об этом мы поговорим немного далее.

Как типы порядка

Типы порядка — самый общий способ описания ординалов. Бинарное отношение $\le$ это вполне-упорядоченность множества $S$ тогда и только тогда когда для любых $a,b,c$ в $S$ верны все следующие утверждения:

• $a \leq b \or b \leq a$
• $a \leq b \and b \leq c \Rightarrow a \leq c$
• $a \leq b \and b \leq a \Rightarrow a = b$
• В каждом подмножестве S есть минимальный элемент.

Вполне упорядоченное множество состоит из множества $S$ и его вполне-упорядоченности $\leq_{S}$.

Порядковый изоморфизм между двумя вполне упорядоченными множествами $(S, \leq_{S})$ и $(T, \leq_{T})$ это биекция $f: S \rightarrow T$ такая что $\forall x, y \in S: x \leq_{S} y \Leftrightarrow f(x) \leq_{T} f(y)$. Два порядка изоморфны-по-порядку если между ними существует порядковый изоморфизм. Легко показать, что изоморфизм-по-порядку это отношение эквивалентности, и мы можем разделить все вполне упорядоченные множества по типу порядка и привязать к каждому типу порядка ординал.

По фон Нейману

Определение Джона фон Неймана дает нам специфичный способ репрезентации ординалов как реальные объекты теории множеств. По фон Нейману, ординал равен множеству всех меньших ординалов, или же более формально — ординал, это транзитивное множество, вполне упорядоченное с помощью ∈.

Однако, данное определение не всегда применяемо и использовать именно его не всегда хорошая идея. Оно удобно для применения прилагательных для множеств к ординалам без дополнительного объяснение, например рекурсивный ординал или счетный ординал.

Малые счетные ординалы

Мы можем определить ординал 0 как пустое множество $\{\}$, а следующий ординал $\alpha + 1 := \alpha \cup \{\alpha\}$. Мы получим $1 := \{0\} = \{\{\}\}$, $2 := \{0, 1\} = \{\{\}, \{\{\}\}\}$, $3 := \{0,1,2\} = \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}\}$ и так далее.

Множеству $\{0,1,2,3,4,5...\}$ будет соответствовать наименьший трансфинитный ординал, обозначаемый $\omega$ (омега). Дальше идет $\omega+1$, $\omega+2$, $\omega+3$, $\omega+4$... Супремум всех этих чисел это $\omega + \omega = \omega 2$. Дальше идет $\omega 2 + 1, \omega 2 + 2,... \omega 3, \omega 4, \omega 5...$ и, конечно, $\omega \times \omega = \omega^2$. Мы можем и продолжить: $\omega^3, \omega^4, \omega^5,... \omega^\omega, \omega^{\omega^\omega}...$ Хочу заметить, что мы не пропускаем и ординалы типа $\omega^{\omega^{\omega^{\omega2} + \omega^7 8 + 4} + \omega^{\omega^{23} 34 + 4} + \omega^{882828}2^{99}} + 7$, они так же существуют, просто мы не можем описать их все.

Однако есть и ординалы больше. Мы можем ввести числа эпсилон: $\varepsilon_\alpha$ это $\alpha$-тое решение уравнения $\varepsilon = \omega^{\varepsilon}$. Наименьшее число эпсилон, обозначаемое $\varepsilon_0$— это супремум множества $\{\omega, \omega^\omega, \omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}}...\}$, либо бесконечная степенная башня из омег — $^\omega \omega = \omega \uparrow \uparrow \omega$. Прошу заметить, что использование гипероператоров выше тетрации на ординалах не совсем верно. Следующие числа эпсилон можно получить таким образом: $\varepsilon_{\alpha + 1} = \text{sup}\{\varepsilon_\alpha + 1, \omega^{\varepsilon_\alpha + 1}, \omega^{\omega^{\varepsilon_\alpha + 1}}...\}.$ Однако так как:

$\omega^{\varepsilon_\alpha + 1} = \omega^{\varepsilon_\alpha}\omega = \varepsilon_\alpha \omega$

$\omega^{\varepsilon_\alpha \omega} = (\omega^{\varepsilon_\alpha})^\omega = \varepsilon_\alpha^\omega$

$\omega^{\varepsilon_\alpha^\omega} = \omega^{\varepsilon_\alpha^{1 + \omega}} = \omega^{\varepsilon_\alpha \varepsilon_\alpha^\omega} = (\omega^{\varepsilon_\alpha})^{\varepsilon_\alpha^\omega} = \varepsilon_\alpha^{\varepsilon_\alpha^\omega}$, и так далее, мы можем сказать так же что $\varepsilon_{\alpha + 1} = \text{sup}\{\varepsilon_\alpha, \varepsilon_\alpha^{\varepsilon_\alpha}, \varepsilon_\alpha^{\varepsilon_\alpha^{\varepsilon_\alpha}},...\}$, или $\varepsilon_\alpha^{\varepsilon_{\alpha + 1}} = \varepsilon_{\alpha + 1}$. Примеры чисел эпсилон: $\varepsilon_0, \varepsilon_1, \varepsilon_2,\varepsilon_\omega, \varepsilon_{\varepsilon_0}, \varepsilon_{\varepsilon_{\varepsilon_0}}...$

Однако, числа эпсилон по итогу кончаются. Именно для этого мы вводим числа зета (зета — следующая буква после эпсилон). $\zeta_{\alpha}$— $\alpha$-тое решение к уравнению $\zeta = \varepsilon_{\zeta}$. Можно продлить это и дальше, введя другую букву $\eta$ (эта). $\eta_{\alpha}$ — $\alpha$-тое решение к $\eta = \zeta_\eta$. Но греческих букв не бесконечность, нужен новый способ обобщения всех таких чисел.

Иерархия Веблена

Сама иерархия обозначается буквой $\varphi$ (фи). Мы можем определить $\varphi_0(\alpha)=\omega^{\alpha}$, а $\varphi_{\beta + 1}(\alpha)$ — $\alpha$-тое решение к $\varphi_\beta (\gamma) = \gamma$. Мы можем продлить это и для трансфинитных $\beta$, добавив случай для предельных $\beta$: $\varphi_\beta(\alpha)$ — $\alpha$-тое число такое, что для всех меньших ординалов $\gamma$ будет выполняться $\varphi_\gamma(\varphi_\beta(\alpha)) = \varphi_\beta(\alpha)$. Предел иерархии Веблена, это число $\Gamma_0 = \varphi_{\varphi_{\varphi_{\varphi_{...}(0)}(0)}(0)}(0)$, называемое ординалом Фефермана-Шютте. Это так же наименьшее число, для которого выполняется $\varphi_{\Gamma_0}(0) = \Gamma_0$.

После Иерархии Веблена

Есть несколько способов записи ординалов за пределами иерархии Веблена.

Расширенная функция Веблена

Это расширение иерархии Веблена на большее количество аргументов, чем 2.

Допустим что $s$ — строка состоящая из ординальных переменных $\alpha_1, \alpha_2, \alpha_3, \alpha_4,... \alpha_n$, где $\alpha_1 > 1$, а $z$ — строка, состоящая только из чисел 0

Она определена следующим образом:

• $\varphi(\gamma)=\omega^\gamma$
• $\varphi(z,s,\gamma)=\varphi(s,\gamma)$
• Если $\alpha_{n+1}>0$, где $n\geq 0$, тогда $\varphi(s,\alpha_{n+1}, z, \gamma)$ обозначает $\gamma$-тое решение уравнения $\xi = \varphi(s, \beta, \xi, z)$ для всех $\beta<\alpha_{n+1}$.

Функции коллапса ординалов

Основная идея функции коллапса ординалов — использование свойств больших ординалов (несчетные, недоступные и т.д.). Наиболее известный пример это функция Бухгольца.

Ординальные нотации

Существуют ординальные нотации, например, $\text{C}$ Тарановского или ординальные нотации Ратьена. Они основаны на рекурсивных множествах, сформулированные как строки или массивы, с использованием счетных алфавитов и рекурсивную вполне упорядоченность (зачастую ее называют <). Элементы ординальных нотаций — не обязательно ординалы, но они описывают ординалы, так как тип порядка элемента в вполне упорядоченном множестве это ординал.

Однако, не все понимают саму суть ординальных нотаций и приписывают это название чему попало, и про них появляется много дезинформации. Если кто-то определяет свои нотации на ординалах и называет их "ординальными нотациями", при этом не давая алгоритмы по вычислению рекурсивного множества, возможно они не совсем понимают определение и суть ординальных нотаций.

Именованные ординалы

$\omega$ — омега, наименьший трансфинитный ординал

$\varepsilon_0$ — эпсилон ноль

$\zeta_0$ — зета ноль, ординал Кантора

$\eta_0$ — эта ноль

$\Gamma_{0}$ — гамма ноль, ординал Фефермана-Шютте

$\varphi(1,0,0,0)$ — ординал Аккермана

$\psi(\Omega^{\Omega^\omega})$ — малый ординал Веблена

$\psi(\Omega^{\Omega^{\Omega}})$ — большой ординал Веблена

$\psi(\varepsilon_{\Omega + 1}) = \psi(\Omega_2)$ — ординал Бахманна-Говарда

$\psi(\Omega_\omega)$ — ординал Бухгольца

$\psi(\varepsilon_{\Omega_\omega + 1})$ — ординал Такеути-Фефермана-Бухгольца

$\psi(\Omega_{\Omega_{\Omega_{._{._.}}}})$ — расширенный ординал Бухгольца

Нерекурсивные ординалы

$\omega^{\mathfrak{Ch}}_1$ — омега первая для шахмат

$\omega_1^\text{CK}$ — ординал Чёрча-Клини