Функция Веблена

Функции Веблена представляют собой иерархию нормальных функций $\varphi_\alpha: \textrm{Ord} \rightarrow \textrm{Ord}$ на $\textrm{Ord}$ , предложенная американским математиком Освальдом Вебленом в статье "Непрерывно возрастающие функции конечных и трансфинитных ординалов" в 1908 году.^[1] Это позволяет получать ординалы, выходящие за пределы нормальной формы Кантора. Ниже описана современная версия функции Веблена.

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

Более сложную формулировку с использованием вывода смотрите в разделе "пример" данной статьи. Иерархия определяется следующим образом:

1) $\varphi_0(\gamma)=\omega^\gamma$

2) Для $\alpha>0$ , $\varphi_\alpha(\gamma)=$ $1+\gamma$ -я общая/одновременная неподвижная точка функций $\varphi_\beta( \xi)=\xi$ для всех $\beta<\alpha$ .

Таким образом, $\varphi_1(\gamma)=\varepsilon_\gamma$ , $\varphi_2(\gamma)=\zeta_\gamma$ и так далее. $\varepsilon_\gamma$ перечисляет ординалы $\xi$ такие, что $\xi = \omega^\xi$ и $\zeta_\gamma$ перечисляет ординалы $\xi$ такие, что $\xi = \varepsilon_\xi$ .

Например: $\varphi_2(2)=\zeta_2$ является фиксированной точкой обеих функций $\varphi_0(\xi)=\xi$ и $\varphi_1(\xi)=\xi$ поскольку $\zeta_2=\omega^{\zeta_2}$ , а также $\zeta_2=\varepsilon_{\zeta_2}$ и это третья фиксированная точка, общая для этих функций после $\zeta_0$ и $\zeta_1$ .

Каждый ненулевой ординал $\alpha<\Gamma_0$ можно однозначно записать в нормальной форме для иерархии Веблена:

$\alpha=\varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k)$ ,

где

$\varphi_{\beta_1}(\gamma_1) \ge \varphi_{\beta_2}(\gamma_2) \ge \cdots \ge \varphi_{\beta_k}(\gamma_k)$
$\gamma_m < \varphi_{\beta_m}(\gamma_m)$ для $m \in \{1,...,k\}$

Примечание. $\Gamma_{0}$ — наименьший ординал $\alpha$ такой, что $\varphi_\alpha(0)=\alpha$ .

Фундаментальные последовательности для иерархии Веблена[]

Фундаментальная последовательность для предельного ординала $\alpha$ — строго возрастающая последовательность, пределом которой является ординал $\alpha$ . $\alpha[n]$ обозначает n-й элемент фундаментальной последовательности, присвоенный предельному ординалу $\alpha$ , где $n$ — неотрицательное целое число.

Фундаментальные последовательности иерархии Веблена определяются следующим образом:

Для предельных ординалов $\alpha<\Gamma_0$ , записанных в нормальной форме для иерархии Веблена:

1.1) $(\varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k))[n]=\varphi_{\beta_1 }(\gamma_1) + \cdots + \varphi_{\beta_{k-1}}(\gamma_{k-1}) + \varphi_{\beta_k}(\gamma_k) [n]$ ,

1.2) $\varphi_0(\gamma)=\omega^\gamma$ и $\varphi_0(\gamma+1) [n] = \omega^{\gamma} \cdot n$ ,

1.3) $\varphi_{\beta+1}(0)[n]=\varphi_{\beta}^n(0)$ ,

1.4) $\varphi_{\beta+1}(\gamma+1)[n]=\varphi_{\beta}^n(\varphi_{\beta+1}(\gamma)+1)$ ,

1.5) $\varphi_{\beta}(\gamma) [n] = \varphi_{\beta}(\gamma [n])$ для предельного ординала $\gamma<\varphi_\beta(\gamma)$ ,

1.6) $\varphi_{\beta}(0) [n] = \varphi_{\beta [n]}(0)$ для предельного ординала $\beta<\varphi_\beta(0)$ ,

1.7) $\varphi_{\beta}(\gamma+1) [n] = \varphi_{\beta [n]}(\varphi_{\beta}(\gamma)+1)$ для предельного ординала $\beta$ .

В правилах 1.3 и 1.4 $\varphi^n$ обозначает итерацию функции: $\varphi_{\beta}^0(\gamma)=\gamma$ и $\varphi_{\beta}^{m+ 1}(\gamma)=\varphi_{\beta}(\varphi_{\beta}^{m}(\gamma))$ .

Расширенная (конечная) функция Веблена[]

Для построения функции Веблена с произвольным количеством аргументов рассмотрим $\varphi_\alpha(\gamma)$ как бинарную функцию $\varphi(\alpha, \gamma)$ .

Пусть z будет пустой строкой или строкой с одним или несколькими нулями $0,0,...,0$ , а s будет пустой строкой или произвольной строкой ординальных переменных $\alpha_1,\alpha_2,...,\alpha_n$ с $\alpha_1>0$ . Бинарную функцию $\varphi(\alpha, \gamma)$ можно записать как $\varphi(s,\alpha, z,\gamma)$ , где и s, и z являются пустыми строками.

Расширенные функции Веблена определяются следующим образом:^[2]

$\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)$ обозначает $1+\gamma$ -ю общую/одновременную неподвижную точку функций $\xi \mapsto \varphi(s, \beta, \xi,z)$ для каждого $\beta<\alpha_{n+1}$ .

Каждый ненулевой ординал $\alpha$ , меньший, чем малый ординал Веблена (МОВ), может быть однозначно записан в нормальной форме для конечной функции Веблена:

$\alpha=\varphi(s_1)+\varphi(s_2)+\cdots+\varphi(s_k)$

где

$\varphi (s_1) \geq\varphi (s_2) \geq\cdots\geq\varphi (s_k)$ ,
$s_m$ — произвольная строка ординальных переменных $\alpha_{m,1}, \alpha_{m,2}, \cdots ,\alpha_{m,n_m}$ , где $m \in \{1,...,k\}$
$\alpha_{m,1}>0$ и $\alpha_{m,i}<\varphi(s_m)$ для $m \in \{1,...,k\}$ и $i \in \{1,..,n_m\}$ ,
$k, n_1,...,n_k$ — целые положительные числа.

Значения и анализ[]

Англоязычное сообщество полагало, что оценка пользователя Hyp cos про скорость роста функции в быстрорастущей иерархии, индексируемой конечной функцией Веблена, $f_{\begin{pmatrix} \omega \\ \omega \end{pmatrix}}(n)$ меньше или равна скорости роста функции $\textrm{TREE}(n)$ Харви Фридмана, но фактического подтверждения оценки нет. Смотрите также вопросы, связанные с анализом функции $\textrm{TREE}(n)$ .

Кроме того, это сообщество полагало, что функция в быстрорастущей иерархии, индексируемая большим ординалом Веблена, $f_{\text{БОВ}}(10)$ , по отношению к стандартной системе фундаментальных последовательностей близка к самой низкой оценке меамеамеалоккапуа-умпа Бауэрса, но хорошо известно, что число нечётко определено, тогда как $f_{\text{БОВ}}(10)$ чётко определено.

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

Ещё одно важное свойство функции Веблена, влияющее на анализ, заключается в том, что последняя запись не обязательно сохраняется при взятии супремумов. Например, $\textrm{sup} \{\varphi_n(\varphi_\omega(0)+1):n\in\mathbb N\}$ не является $\varphi_\omega(\varphi_\omega( 0)+1)$ , а вместо этого $\varphi_\omega(1)$ .