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

В математике функции Веблена — иерархия нормальных функций, строго возрастающих от ординала к ординалу, предложенная Освальдом Вебленом в 1908 году. Если ${\phi }_0$ — это какая-либо нормальная функция, тогда для любого ненулевого ординала $\alpha$ функция ${\phi }_{\alpha }$ перечисляет общие неподвижные точки всех ${\phi }_{\beta }$ для $\beta <\alpha .$ Все эти функции нормальные.

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

В частном случае, когда ${\phi }_0(\alpha )={\omega }^{\alpha }$, это семейство функций называется иерархией Веблена; ${\phi }_1(\alpha )={\epsilon }_{\alpha },{\phi }_2(\alpha )={\zeta }_{\alpha },{\phi }_3(\alpha )={\eta }_{\alpha }.$ В связи с иерархией Веблена применяется вариация нормальной формы Кантора — любой ненулевой ординал $\alpha$ может быть уникально записан как $\alpha ={\phi }_{{\beta }_1}({\gamma }_1)+{\phi }_{{\beta }_2}({\gamma }_2)+\cdots +{\phi }_{{\beta }_k}({\gamma }_k),$ где $k>0$ — некое натуральное число, ${\phi }_{{\beta }_m}({\gamma }_m)\ge {\phi }_{{\beta }_{m+1}}({\gamma }_{m+1})$ и ${\gamma }_m<{\phi }_{{\beta }_m}({\gamma }_m).$ Таким образом, фундаментальная последовательность для любого ненулевого ординала $\alpha$ может быть определена из выражения $\alpha [n]={\phi }_{{\beta }_1}({\gamma }_1)+\cdots +{\phi }_{{\beta }_{k-1}}({\gamma }_{k-1})+{\phi }_{{\beta }_k}({\gamma }_k)[n]$ с учётом следующих правил:

1. Если $\beta =0,$ тогда ${\phi }_0(\gamma +1)[n]={\omega }^{\gamma }\cdot n,$ поскольку ${\phi }_0(0)=1$ и ${\phi }_0(\gamma )={\omega }^{\gamma }.$
2. Если $\gamma =0,$ тогда ${\phi }_{\beta +1}(0)[0]=0$ и ${\phi }_{\beta +1}(0)[n+1]={\phi }_{\beta }({\phi }_{\beta +1}(0)[n]),$ то есть ${\phi }_{\beta +1}(0)[n]={\phi }_{\beta }^n(0).$
3. Если $\gamma$ — предельный ординал, тогда ${\phi }_{\beta }(\gamma )[n]={\phi }_{\beta }(\gamma [n]).$
4. Если $\beta$ — предельный ординал, тогда ${\phi }_{\beta }(0)[n]={\phi }_{\beta [n]}(0)$ и ${\phi }_{\beta }(\gamma +1)[n]={\phi }_{\beta [n]}({\phi }_{\beta }(\gamma )+1).$
5. Иначе ${\phi }_{\beta +1}(\gamma +1)[0]={\phi }_{\beta +1}(\gamma )+1$ и ${\phi }_{\beta +1}(\gamma +1)[n+1]={\phi }_{\beta }({\phi }_{\beta +1}(\gamma +1)[n]),$ то есть ${\phi }_{\beta +1}(\gamma +1)[n]={\phi }_{\beta }^n({\phi }_{\beta +1}(\gamma )+1).$

Примеры

применение правила 2	применение правила 5
${\phi }_1(0)[0]={\epsilon }_0[0]=0$	${\phi }_1(1)[0]={\phi }_1(0)+1={\epsilon }_0+1={\epsilon }_1[0]$
${\phi }_1(0)[1]={\phi }_0({\phi }_1(0)[0])={\phi }_0(0)={\omega }^0=1$	${\phi }_1(1)[1]={\phi }_0({\phi }_1(1)[0])={\epsilon }_1[1]={\omega }^{{\epsilon }_0+1}$
${\phi }_1(0)[2]={\phi }_0({\phi }_1(0)[1])={\omega }^1=\omega$	${\phi }_1(1)[2]={\phi }_0({\phi }_1(1)[1])={\epsilon }_1[2]={\omega }^{{\omega }^{{\epsilon }_0+1}}$
${\phi }_1(0)[3]={\phi }_0({\phi }_1(0)[2])={\omega }^{\omega }$	${\phi }_1(1)[3]={\phi }_0({\phi }_1(1)[2])={\epsilon }_1[3]={\omega }^{{\omega }^{{\omega }^{{\epsilon }_0+1}}}$
${\phi }_1(0)[4]={\phi }_0({\phi }_1(0)[3])={\omega }^{{\omega }^{\omega }}$	${\phi }_1(1)[4]={\phi }_0({\phi }_1(1)[3])={\epsilon }_1[4]={\omega }^{{\omega }^{{\omega }^{{\omega }^{{\epsilon }_0+1}}}}$
${\phi }_2(0)[4]={\phi }_1({\phi }_1({\phi }_1({\phi }_1(0))))={\epsilon }_{{\epsilon }_{{\epsilon }_{{\epsilon }_0}}}={\zeta }_0[4]$	${\phi }_2(1)[4]={\phi }_1({\phi }_1({\phi }_1({\phi }_1({\phi }_2(0)+1))))={\epsilon }_{{\epsilon }_{{\epsilon }_{{\epsilon }_{{\zeta }_0+1}}}}={\zeta }_1[4]$
${\phi }_3(0)[4]={\phi }_2({\phi }_2({\phi }_2({\phi }_2(0))))={\zeta }_{{\zeta }_{{\zeta }_{{\zeta }_0}}}={\eta }_0[4]$	${\phi }_3(1)[4]={\phi }_2({\phi }_2({\phi }_2({\phi }_2({\phi }_3(0)+1))))={\zeta }_{{\zeta }_{{\zeta }_{{\zeta }_{{\eta }_0+1}}}}={\eta }_1[4]$

${\phi }_0(3)[n]={\omega }^2\cdot n$ (правило 1)

${\phi }_0({\phi }_0(1))[n]={\phi }_0({\phi }_0(1)[n])={\omega }^{\omega [n]}={\omega }^n$ (Правила 1 и 3)

${\phi }_1(\omega )[n]={\phi }_1(\omega [n])={\phi }_1(n)={\epsilon }_n$ (правило 3)

${\phi }_1({\phi }_1(0))[n]={\phi }_1({\phi }_1(0)[n])={\phi }_1({\epsilon }_0[n])={\epsilon }_{\omega \uparrow \uparrow (n-1)}$ (правило 3)

${\phi }_{{\phi }_0(1)}(0)[n]={\phi }_{\omega }(0)[n]={\phi }_{\omega [n]}(0)={\phi }_n(0)$ (правила 1 и 4)

${\phi }_{{\phi }_1(0)}(0)[3]={\phi }_{{\epsilon }_0}(0)[3]={\phi }_{{\epsilon }_0[3]}(0)={\phi }_{{\omega }^{\omega }}(0)$ (правило 4)

Соответствующие примеры для быстрорастущей иерархии:

$f_{{\phi }_1(0)}(4)=f_{{\phi }_1(0)[4]}(4)=f_{{\omega }^{{\omega }^{\omega }}}(4)$

$f_{{\phi }_1(1)}(3)=f_{{\phi }_1(1)[3]}(3)=f_{{\omega }^{{\omega }^{{\omega }^{{\epsilon }_0+1}}}}(3)$

Г-функция

Функция Γ перечисляет ординалы $\alpha ,$ такие что ${\phi }_{\alpha }(0)=\alpha .$ Наименьший ординал $\alpha ,$ для которого выполняется это условие, называется Шаблон:Iw ${\mathrm{\Gamma }}_0.$ Фундаментальная последовательность для него определяется следующими выражениями:

• ${\mathrm{\Gamma }}_0[0]=0$ и ${\mathrm{\Gamma }}_0[n+1]={\phi }_{{\mathrm{\Gamma }}_0[n]}(0).$
• Для ${\mathrm{\Gamma }}_{\beta +1}$ верно ${\mathrm{\Gamma }}_{\beta +1}[0]={\mathrm{\Gamma }}_{\beta }+1$ и ${\mathrm{\Gamma }}_{\beta +1}[n+1]={\phi }_{{\mathrm{\Gamma }}_{\beta +1}[n]}(0).$
• Если $\beta$ — предельный ординал и $\beta <{\mathrm{\Gamma }}_{\beta },$ тогда ${\mathrm{\Gamma }}_{\beta }[n]={\mathrm{\Gamma }}_{\beta [n]}.$

Обобщение

Функция Веблена ${\phi }_{\alpha }(\beta )$ также может быть представлена в виде функции $\phi (\alpha ,\beta )$ двух аргументов. Веблен показал, как обобщить определение для того, чтобы получить функцию $\phi ({\alpha }_n,{\alpha }_{n-1},...,{\alpha }_0)$ для произвольного числа аргументов, а именно:

• $\phi (\alpha )={\omega }^{\alpha }$ для случая одной переменной,
• $\phi (0,{\alpha }_{n-1},...,{\alpha }_0)=\phi ({\alpha }_{n-1},...,{\alpha }_0),$ и
• для $\alpha >0,\gamma \mapsto \phi ({\alpha }_n,...,{\alpha }_{i+1},\alpha ,0,...,0,\gamma )$ — это функция, перечисляющая общие неподвижные точки функций $\xi \mapsto \phi ({\alpha }_n,...,{\alpha }_{i+1},\beta ,\xi ,0,...,0)$ для всех $\beta <\alpha .$

Например, $\phi (1,0,\gamma )$ — это $\gamma$-я неподвижная точка функций $\xi \mapsto \phi (0,\xi ,0)=\phi (\xi ,0),$ а именно ${\mathrm{\Gamma }}_{\gamma }.$

• $\phi (1,0,0)={\mathrm{\Gamma }}_0$ — ординал Фефермана.
• $\phi (1,0,0,0)$ — ординал Аккермана.
• Предел для $\phi (1,0,...,0,0)$ — малый ординал Веблена.

Ссылки

• Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Uninitiated, expository article (8 pages, in PostScript)
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation contains an informal description of the Veblen hierarchy.
• Шаблон:Citation
• Шаблон:Citation