𝜔

$\omega$ (произносится как "омега") — первый трансфинитный ординал, наименьший ординал, больший, чем все положительные целые числа. В определении ординалов фон Неймана он равен множеству целых неотрицательных чисел $\mathbb{N}$.

В иерархии Вайнера фундаментальная последовательность $\omega$ равна $0,1,2,\ldots$. Используя эту иерархию, справедливо следующее:

• $f_\omega(n) \approx 2 \uparrow^{n-1} n$ (Быстрорастущая Иерархия) находится на одном уровне с функцией Аккермана и слабой функцией Гудштейна. Это первая функция в БРИ, которая не является примитивно-рекурсивной.
• $H_\omega(n) = 2n$ (Иерархия Харди), первая функция в иерархии Харди, которая не является трансляционной.
• $g_\omega(n) = n$ (Медленнорастущая Иерархия), первая функция в МРИ, которая не является константой.

Однако если мы не работаем в иерархии Вайнера, $f_{\omega }$ может быть сколь угодно быстрорастущей. Например, если $\omega[n] = \Sigma(n)$ (где $\Sigma(n)$ — функция занятого бобра), то $f_{\omega }$ невычислима.

В действительности фундаментальных последовательностей для $\omega$ (и для любого другого счётного ординала) столько же, сколько монотонно возрастающих функций $\mathbb{N} \to \mathbb{N}$, т.е. континуум $\mathfrak c$ из них.

$\omega$ — первый допустимый ординал. Это также первый трансфинитный регулярный ординал.

Внешние ссылки

• Вход на чердак Кантора

Смотрите также

• Ординал
• Первый неисчисляемый ординал
• 𝜀₀