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

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

Иерархия ВебленаПравить

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

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

ПримерыПравить

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

${\mathrm{\phi <!--\; \phi \; -->}}_0(3)[n]={\mathrm{\omega <!--\; \omega \; -->}}^2\cdot <!--\; \cdot \; -->n$$\varphi _{0}(3)[n]=\omega ^{2}\cdot n$  (правило 1)

${\mathrm{\phi <!--\; \phi \; -->}}_0({\mathrm{\phi <!--\; \phi \; -->}}_0(1))[n]={\mathrm{\phi <!--\; \phi \; -->}}_0({\mathrm{\phi <!--\; \phi \; -->}}_0(1)[n])={\mathrm{\omega <!--\; \omega \; -->}}^{\mathrm{\omega <!--\; \omega \; -->}[n]}={\mathrm{\omega <!--\; \omega \; -->}}^n$$\varphi _{0}(\varphi _{0}(1))[n]=\varphi _{0}(\varphi _{0}(1)[n])=\omega ^{\omega [n]}=\omega ^{n}$  (Правила 1 и 3)

${\mathrm{\phi <!--\; \phi \; -->}}_1(\mathrm{\omega <!--\; \omega \; -->})[n]={\mathrm{\phi <!--\; \phi \; -->}}_1(\mathrm{\omega <!--\; \omega \; -->}[n])={\mathrm{\phi <!--\; \phi \; -->}}_1(n)={\mathrm{\epsilon <!--\; \epsilon \; -->}}_n$$\varphi _{1}(\omega )[n]=\varphi _{1}(\omega [n])=\varphi _{1}(n)=\varepsilon _{n}$  (правило 3)

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

${\mathrm{\phi <!--\; \phi \; -->}}_{{\mathrm{\phi <!--\; \phi \; -->}}_0(1)}(0)[n]={\mathrm{\phi <!--\; \phi \; -->}}_{\mathrm{\omega <!--\; \omega \; -->}}(0)[n]={\mathrm{\phi <!--\; \phi \; -->}}_{\mathrm{\omega <!--\; \omega \; -->}[n]}(0)={\mathrm{\phi <!--\; \phi \; -->}}_n(0)$$\varphi _{\varphi _{0}(1)}(0)[n]=\varphi _{\omega }(0)[n]=\varphi _{\omega [n]}(0)=\varphi _{n}(0)$  (правила 1 и 4)

${\mathrm{\phi <!--\; \phi \; -->}}_{{\mathrm{\phi <!--\; \phi \; -->}}_1(0)}(0)[3]={\mathrm{\phi <!--\; \phi \; -->}}_{{\mathrm{\epsilon <!--\; \epsilon \; -->}}_0}(0)[3]={\mathrm{\phi <!--\; \phi \; -->}}_{{\mathrm{\epsilon <!--\; \epsilon \; -->}}_0[3]}(0)={\mathrm{\phi <!--\; \phi \; -->}}_{{\mathrm{\omega <!--\; \omega \; -->}}^{\mathrm{\omega <!--\; \omega \; -->}}}(0)$$\varphi _{\varphi _{1}(0)}(0)[3]=\varphi _{\varepsilon _{0}}(0)[3]=\varphi _{\varepsilon _{0}[3]}(0)=\varphi _{\omega ^{\omega }}(0)$  (правило 4)

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

$f_{{\mathrm{\phi <!--\; \phi \; -->}}_1(0)}(4)=f_{{\mathrm{\phi <!--\; \phi \; -->}}_1(0)[4]}(4)=f_{{\mathrm{\omega <!--\; \omega \; -->}}^{{\mathrm{\omega <!--\; \omega \; -->}}^{\mathrm{\omega <!--\; \omega \; -->}}}}(4)$$f_{\varphi _{1}(0)}(4)=f_{\varphi _{1}(0)[4]}(4)=f_{\omega ^{\omega ^{\omega }}}(4)$ 

$f_{{\mathrm{\phi <!--\; \phi \; -->}}_1(1)}(3)=f_{{\mathrm{\phi <!--\; \phi \; -->}}_1(1)[3]}(3)=f_{{\mathrm{\omega <!--\; \omega \; -->}}^{{\mathrm{\omega <!--\; \omega \; -->}}^{{\mathrm{\omega <!--\; \omega \; -->}}^{{\mathrm{\epsilon <!--\; \epsilon \; -->}}_0+1}}}}(3)$$f_{\varphi _{1}(1)}(3)=f_{\varphi _{1}(1)[3]}(3)=f_{\omega ^{\omega ^{\omega ^{\varepsilon _{0}+1}}}}(3)$ 

Г-функцияПравить

Функция Γ перечисляет ординалы $\mathrm{\alpha <!--\; \alpha \; -->},$$\alpha ,$  такие что ${\mathrm{\phi <!--\; \phi \; -->}}_{\mathrm{\alpha <!--\; \alpha \; -->}}(0)=\mathrm{\alpha <!--\; \alpha \; -->}.$$\varphi _{\alpha }(0)=\alpha .$  Наименьший ординал $\mathrm{\alpha <!--\; \alpha \; -->},$$\alpha ,$  для которого выполняется это условие, называется ординалом Фефермана^[en] ${\mathrm{\Gamma <!--\; \Gamma \; -->}}_0.$$\Gamma _{0}.$  Фундаментальная последовательность для него определяется следующими выражениями:

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

ОбобщениеПравить

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

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

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

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

СсылкиПравить

• Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Uninitiated, expository article (8 pages, in PostScript)
• Pohlers, Wolfram (1989), Proof theory, vol. 1407, Lecture Notes in Mathematics, Berlin: Springer-Verlag, ISBN 3-540-51842-8 
• Schütte, Kurt (1977), Proof theory, vol. 225, Grundlehren der Mathematischen Wissenschaften, Berlin-New York: Springer-Verlag, с. xii+299, ISBN 3-540-07911-4 
• Takeuti, Gaisi (1987), Proof theory, vol. 81 (Second ed.), Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland Publishing Co., ISBN 0-444-87943-9 
• Smorynski, C. (1982), The varieties of arboreal experience, Math. Intelligencer Т. 4 (4): 182–189, DOI 10.1007/BF03023553  contains an informal description of the Veblen hierarchy.
• Veblen, Oswald (1908), Continuous Increasing Functions of Finite and Transfinite Ordinals, Transactions of the American Mathematical Society Т. 9 (3): 280–292, DOI 10.2307/1988605 
• Miller, Larry W. (1976), Normal Functions and Constructive Ordinal Notations, The Journal of Symbolic Logic Т. 41 (2): 439–459, DOI 10.2307/2272243