В математике функции Веблена — иерархия нормальных функций, строго возрастающих от ординала к ординалу, предложенная Освальдом Вебленом в 1908 году. Если
φ ふぁい
0
{\displaystyle \varphi _{0}}
— это какая-либо нормальная функция, тогда для любого ненулевого ординала
α あるふぁ
{\displaystyle \alpha }
функция
φ ふぁい
α あるふぁ
{\displaystyle \varphi _{\alpha }}
перечисляет общие неподвижные точки всех
φ ふぁい
β べーた
{\displaystyle \varphi _{\beta }}
для
β べーた
<
α あるふぁ
.
{\displaystyle \beta <\alpha .}
Все эти функции нормальные.
В частном случае, когда
φ ふぁい
0
(
α あるふぁ
)
=
ω おめが
α あるふぁ
{\displaystyle \varphi _{0}(\alpha )=\omega ^{\alpha }}
, это семейство функций называется иерархией Веблена ;
φ ふぁい
1
(
α あるふぁ
)
=
ε いぷしろん
α あるふぁ
,
φ ふぁい
2
(
α あるふぁ
)
=
ζ ぜーた
α あるふぁ
,
φ ふぁい
3
(
α あるふぁ
)
=
η いーた
α あるふぁ
.
{\displaystyle \varphi _{1}(\alpha )=\varepsilon _{\alpha },\,\varphi _{2}(\alpha )=\zeta _{\alpha },\,\varphi _{3}(\alpha )=\eta _{\alpha }.}
В связи с иерархией Веблена применяется вариация нормальной формы Кантора — любой ненулевой ординал
α あるふぁ
{\displaystyle \alpha }
может быть уникально записан как
α あるふぁ
=
φ ふぁい
β べーた
1
(
γ がんま
1
)
+
φ ふぁい
β べーた
2
(
γ がんま
2
)
+
⋯
+
φ ふぁい
β べーた
k
(
γ がんま
k
)
,
{\displaystyle \alpha =\varphi _{\beta _{1}}(\gamma _{1})+\varphi _{\beta _{2}}(\gamma _{2})+\cdots +\varphi _{\beta _{k}}(\gamma _{k}),}
где
k
>
0
{\displaystyle k>0}
— некое натуральное число ,
φ ふぁい
β べーた
m
(
γ がんま
m
)
≥
φ ふぁい
β べーた
m
+
1
(
γ がんま
m
+
1
)
{\displaystyle \varphi _{\beta _{m}}(\gamma _{m})\geq \varphi _{\beta _{m+1}}(\gamma _{m+1})}
и
γ がんま
m
<
φ ふぁい
β べーた
m
(
γ がんま
m
)
.
{\displaystyle \gamma _{m}<\varphi _{\beta _{m}}(\gamma _{m}).}
Таким образом, фундаментальная последовательность для любого ненулевого ординала
α あるふぁ
{\displaystyle \alpha }
может быть определена из выражения
α あるふぁ
[
n
]
=
φ ふぁい
β べーた
1
(
γ がんま
1
)
+
⋯
+
φ ふぁい
β べーた
k
−
1
(
γ がんま
k
−
1
)
+
φ ふぁい
β べーた
k
(
γ がんま
k
)
[
n
]
{\displaystyle \alpha [n]=\varphi _{\beta _{1}}(\gamma _{1})+\cdots +\varphi _{\beta _{k-1}}(\gamma _{k-1})+\varphi _{\beta _{k}}(\gamma _{k})[n]}
с учётом следующих правил:
Если
β べーた
=
0
,
{\displaystyle \beta =0,}
тогда
φ ふぁい
0
(
γ がんま
+
1
)
[
n
]
=
ω おめが
γ がんま
⋅
n
,
{\displaystyle \varphi _{0}(\gamma +1)[n]=\omega ^{\gamma }\cdot n,}
поскольку
φ ふぁい
0
(
0
)
=
1
{\displaystyle \varphi _{0}(0)=1}
и
φ ふぁい
0
(
γ がんま
)
=
ω おめが
γ がんま
.
{\displaystyle \varphi _{0}(\gamma )=\omega ^{\gamma }.}
Если
γ がんま
=
0
,
{\displaystyle \gamma =0,}
тогда
φ ふぁい
β べーた
+
1
(
0
)
[
0
]
=
0
{\displaystyle \varphi _{\beta +1}(0)[0]=0}
и
φ ふぁい
β べーた
+
1
(
0
)
[
n
+
1
]
=
φ ふぁい
β べーた
(
φ ふぁい
β べーた
+
1
(
0
)
[
n
]
)
,
{\displaystyle \varphi _{\beta +1}(0)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(0)[n]),}
то есть
φ ふぁい
β べーた
+
1
(
0
)
[
n
]
=
φ ふぁい
β べーた
n
(
0
)
.
{\displaystyle \varphi _{\beta +1}(0)[n]=\varphi _{\beta }^{n}(0).}
Если
γ がんま
{\displaystyle \gamma }
— предельный ординал , тогда
φ ふぁい
β べーた
(
γ がんま
)
[
n
]
=
φ ふぁい
β べーた
(
γ がんま
[
n
]
)
.
{\displaystyle \varphi _{\beta }(\gamma )[n]=\varphi _{\beta }(\gamma [n]).}
Если
β べーた
{\displaystyle \beta }
— предельный ординал , тогда
φ ふぁい
β べーた
(
0
)
[
n
]
=
φ ふぁい
β べーた
[
n
]
(
0
)
{\displaystyle \varphi _{\beta }(0)[n]=\varphi _{\beta [n]}(0)}
и
φ ふぁい
β べーた
(
γ がんま
+
1
)
[
n
]
=
φ ふぁい
β べーた
[
n
]
(
φ ふぁい
β べーた
(
γ がんま
)
+
1
)
.
{\displaystyle \varphi _{\beta }(\gamma +1)[n]=\varphi _{\beta [n]}(\varphi _{\beta }(\gamma )+1).}
Иначе
φ ふぁい
β べーた
+
1
(
γ がんま
+
1
)
[
0
]
=
φ ふぁい
β べーた
+
1
(
γ がんま
)
+
1
{\displaystyle \varphi _{\beta +1}(\gamma +1)[0]=\varphi _{\beta +1}(\gamma )+1}
и
φ ふぁい
β べーた
+
1
(
γ がんま
+
1
)
[
n
+
1
]
=
φ ふぁい
β べーた
(
φ ふぁい
β べーた
+
1
(
γ がんま
+
1
)
[
n
]
)
,
{\displaystyle \varphi _{\beta +1}(\gamma +1)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(\gamma +1)[n]),}
то есть
φ ふぁい
β べーた
+
1
(
γ がんま
+
1
)
[
n
]
=
φ ふぁい
β べーた
n
(
φ ふぁい
β べーた
+
1
(
γ がんま
)
+
1
)
.
{\displaystyle \varphi _{\beta +1}(\gamma +1)[n]=\varphi _{\beta }^{n}(\varphi _{\beta +1}(\gamma )+1).}
применение правила 2
применение правила 5
φ ふぁい
1
(
0
)
[
0
]
=
ε いぷしろん
0
[
0
]
=
0
{\displaystyle \varphi _{1}(0)[0]=\varepsilon _{0}[0]=0}
φ ふぁい
1
(
1
)
[
0
]
=
φ ふぁい
1
(
0
)
+
1
=
ε いぷしろん
0
+
1
=
ε いぷしろん
1
[
0
]
{\displaystyle \varphi _{1}(1)[0]=\varphi _{1}(0)+1=\varepsilon _{0}+1=\varepsilon _{1}[0]}
φ ふぁい
1
(
0
)
[
1
]
=
φ ふぁい
0
(
φ ふぁい
1
(
0
)
[
0
]
)
=
φ ふぁい
0
(
0
)
=
ω おめが
0
=
1
{\displaystyle \varphi _{1}(0)[1]=\varphi _{0}(\varphi _{1}(0)[0])=\varphi _{0}(0)=\omega ^{0}=1}
φ ふぁい
1
(
1
)
[
1
]
=
φ ふぁい
0
(
φ ふぁい
1
(
1
)
[
0
]
)
=
ε いぷしろん
1
[
1
]
=
ω おめが
ε いぷしろん
0
+
1
{\displaystyle \varphi _{1}(1)[1]=\varphi _{0}(\varphi _{1}(1)[0])=\varepsilon _{1}[1]=\omega ^{\varepsilon _{0}+1}}
φ ふぁい
1
(
0
)
[
2
]
=
φ ふぁい
0
(
φ ふぁい
1
(
0
)
[
1
]
)
=
ω おめが
1
=
ω おめが
{\displaystyle \varphi _{1}(0)[2]=\varphi _{0}(\varphi _{1}(0)[1])=\omega ^{1}=\omega }
φ ふぁい
1
(
1
)
[
2
]
=
φ ふぁい
0
(
φ ふぁい
1
(
1
)
[
1
]
)
=
ε いぷしろん
1
[
2
]
=
ω おめが
ω おめが
ε いぷしろん
0
+
1
{\displaystyle \varphi _{1}(1)[2]=\varphi _{0}(\varphi _{1}(1)[1])=\varepsilon _{1}[2]=\omega ^{\omega ^{\varepsilon _{0}+1}}}
φ ふぁい
1
(
0
)
[
3
]
=
φ ふぁい
0
(
φ ふぁい
1
(
0
)
[
2
]
)
=
ω おめが
ω おめが
{\displaystyle \varphi _{1}(0)[3]=\varphi _{0}(\varphi _{1}(0)[2])=\omega ^{\omega }}
φ ふぁい
1
(
1
)
[
3
]
=
φ ふぁい
0
(
φ ふぁい
1
(
1
)
[
2
]
)
=
ε いぷしろん
1
[
3
]
=
ω おめが
ω おめが
ω おめが
ε いぷしろん
0
+
1
{\displaystyle \varphi _{1}(1)[3]=\varphi _{0}(\varphi _{1}(1)[2])=\varepsilon _{1}[3]=\omega ^{\omega ^{\omega ^{\varepsilon _{0}+1}}}}
φ ふぁい
1
(
0
)
[
4
]
=
φ ふぁい
0
(
φ ふぁい
1
(
0
)
[
3
]
)
=
ω おめが
ω おめが
ω おめが
{\displaystyle \varphi _{1}(0)[4]=\varphi _{0}(\varphi _{1}(0)[3])=\omega ^{\omega ^{\omega }}}
φ ふぁい
1
(
1
)
[
4
]
=
φ ふぁい
0
(
φ ふぁい
1
(
1
)
[
3
]
)
=
ε いぷしろん
1
[
4
]
=
ω おめが
ω おめが
ω おめが
ω おめが
ε いぷしろん
0
+
1
{\displaystyle \varphi _{1}(1)[4]=\varphi _{0}(\varphi _{1}(1)[3])=\varepsilon _{1}[4]=\omega ^{\omega ^{\omega ^{\omega ^{\varepsilon _{0}+1}}}}}
φ ふぁい
2
(
0
)
[
4
]
=
φ ふぁい
1
(
φ ふぁい
1
(
φ ふぁい
1
(
φ ふぁい
1
(
0
)
)
)
)
=
ε いぷしろん
ε いぷしろん
ε いぷしろん
ε いぷしろん
0
=
ζ ぜーた
0
[
4
]
{\displaystyle \varphi _{2}(0)[4]=\varphi _{1}(\varphi _{1}(\varphi _{1}(\varphi _{1}(0))))=\varepsilon _{\varepsilon _{\varepsilon _{\varepsilon _{0}}}}=\zeta _{0}[4]}
φ ふぁい
2
(
1
)
[
4
]
=
φ ふぁい
1
(
φ ふぁい
1
(
φ ふぁい
1
(
φ ふぁい
1
(
φ ふぁい
2
(
0
)
+
1
)
)
)
)
=
ε いぷしろん
ε いぷしろん
ε いぷしろん
ε いぷしろん
ζ ぜーた
0
+
1
=
ζ ぜーた
1
[
4
]
{\displaystyle \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]}
φ ふぁい
3
(
0
)
[
4
]
=
φ ふぁい
2
(
φ ふぁい
2
(
φ ふぁい
2
(
φ ふぁい
2
(
0
)
)
)
)
=
ζ ぜーた
ζ ぜーた
ζ ぜーた
ζ ぜーた
0
=
η いーた
0
[
4
]
{\displaystyle \varphi _{3}(0)[4]=\varphi _{2}(\varphi _{2}(\varphi _{2}(\varphi _{2}(0))))=\zeta _{\zeta _{\zeta _{\zeta _{0}}}}=\eta _{0}[4]}
φ ふぁい
3
(
1
)
[
4
]
=
φ ふぁい
2
(
φ ふぁい
2
(
φ ふぁい
2
(
φ ふぁい
2
(
φ ふぁい
3
(
0
)
+
1
)
)
)
)
=
ζ ぜーた
ζ ぜーた
ζ ぜーた
ζ ぜーた
η いーた
0
+
1
=
η いーた
1
[
4
]
{\displaystyle \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]}
φ ふぁい
0
(
3
)
[
n
]
=
ω おめが
2
⋅
n
{\displaystyle \varphi _{0}(3)[n]=\omega ^{2}\cdot n}
(правило 1)
φ ふぁい
0
(
φ ふぁい
0
(
1
)
)
[
n
]
=
φ ふぁい
0
(
φ ふぁい
0
(
1
)
[
n
]
)
=
ω おめが
ω おめが
[
n
]
=
ω おめが
n
{\displaystyle \varphi _{0}(\varphi _{0}(1))[n]=\varphi _{0}(\varphi _{0}(1)[n])=\omega ^{\omega [n]}=\omega ^{n}}
(Правила 1 и 3)
φ ふぁい
1
(
ω おめが
)
[
n
]
=
φ ふぁい
1
(
ω おめが
[
n
]
)
=
φ ふぁい
1
(
n
)
=
ε いぷしろん
n
{\displaystyle \varphi _{1}(\omega )[n]=\varphi _{1}(\omega [n])=\varphi _{1}(n)=\varepsilon _{n}}
(правило 3)
φ ふぁい
1
(
φ ふぁい
1
(
0
)
)
[
n
]
=
φ ふぁい
1
(
φ ふぁい
1
(
0
)
[
n
]
)
=
φ ふぁい
1
(
ε いぷしろん
0
[
n
]
)
=
ε いぷしろん
ω おめが
↑↑
(
n
−
1
)
{\displaystyle \varphi _{1}(\varphi _{1}(0))[n]=\varphi _{1}(\varphi _{1}(0)[n])=\varphi _{1}(\varepsilon _{0}[n])=\varepsilon _{\omega \uparrow \uparrow (n-1)}}
(правило 3)
φ ふぁい
φ ふぁい
0
(
1
)
(
0
)
[
n
]
=
φ ふぁい
ω おめが
(
0
)
[
n
]
=
φ ふぁい
ω おめが
[
n
]
(
0
)
=
φ ふぁい
n
(
0
)
{\displaystyle \varphi _{\varphi _{0}(1)}(0)[n]=\varphi _{\omega }(0)[n]=\varphi _{\omega [n]}(0)=\varphi _{n}(0)}
(правила 1 и 4)
φ ふぁい
φ ふぁい
1
(
0
)
(
0
)
[
3
]
=
φ ふぁい
ε いぷしろん
0
(
0
)
[
3
]
=
φ ふぁい
ε いぷしろん
0
[
3
]
(
0
)
=
φ ふぁい
ω おめが
ω おめが
(
0
)
{\displaystyle \varphi _{\varphi _{1}(0)}(0)[3]=\varphi _{\varepsilon _{0}}(0)[3]=\varphi _{\varepsilon _{0}[3]}(0)=\varphi _{\omega ^{\omega }}(0)}
(правило 4)
Соответствующие примеры для быстрорастущей иерархии :
f
φ ふぁい
1
(
0
)
(
4
)
=
f
φ ふぁい
1
(
0
)
[
4
]
(
4
)
=
f
ω おめが
ω おめが
ω おめが
(
4
)
{\displaystyle f_{\varphi _{1}(0)}(4)=f_{\varphi _{1}(0)[4]}(4)=f_{\omega ^{\omega ^{\omega }}}(4)}
f
φ ふぁい
1
(
1
)
(
3
)
=
f
φ ふぁい
1
(
1
)
[
3
]
(
3
)
=
f
ω おめが
ω おめが
ω おめが
ε いぷしろん
0
+
1
(
3
)
{\displaystyle f_{\varphi _{1}(1)}(3)=f_{\varphi _{1}(1)[3]}(3)=f_{\omega ^{\omega ^{\omega ^{\varepsilon _{0}+1}}}}(3)}
Функция Γ がんま перечисляет ординалы
α あるふぁ
,
{\displaystyle \alpha ,}
такие что
φ ふぁい
α あるふぁ
(
0
)
=
α あるふぁ
.
{\displaystyle \varphi _{\alpha }(0)=\alpha .}
Наименьший ординал
α あるふぁ
,
{\displaystyle \alpha ,}
для которого выполняется это условие, называется ординалом Фефермана [англ.]
Γ がんま
0
.
{\displaystyle \Gamma _{0}.}
Фундаментальная последовательность для него определяется следующими выражениями:
Γ がんま
0
[
0
]
=
0
{\displaystyle \Gamma _{0}[0]=0\,}
и
Γ がんま
0
[
n
+
1
]
=
φ ふぁい
Γ がんま
0
[
n
]
(
0
)
.
{\displaystyle \Gamma _{0}[n+1]=\varphi _{\Gamma _{0}[n]}(0).}
Для
Γ がんま
β べーた
+
1
{\displaystyle \Gamma _{\beta +1}}
верно
Γ がんま
β べーた
+
1
[
0
]
=
Γ がんま
β べーた
+
1
{\displaystyle \Gamma _{\beta +1}[0]=\Gamma _{\beta }+1}
и
Γ がんま
β べーた
+
1
[
n
+
1
]
=
φ ふぁい
Γ がんま
β べーた
+
1
[
n
]
(
0
)
.
{\displaystyle \Gamma _{\beta +1}[n+1]=\varphi _{\Gamma _{\beta +1}[n]}(0).}
Если
β べーた
{\displaystyle \beta }
— предельный ординал и
β べーた
<
Γ がんま
β べーた
,
{\displaystyle \beta <\Gamma _{\beta },}
тогда
Γ がんま
β べーた
[
n
]
=
Γ がんま
β べーた
[
n
]
.
{\displaystyle \Gamma _{\beta }[n]=\Gamma _{\beta [n]}.}
Функция Веблена
φ ふぁい
α あるふぁ
(
β べーた
)
{\displaystyle \varphi _{\alpha }(\beta )}
также может быть представлена в виде функции
φ ふぁい
(
α あるふぁ
,
β べーた
)
{\displaystyle \varphi (\alpha ,\beta )}
двух аргументов. Веблен показал, как обобщить определение для того, чтобы получить функцию
φ ふぁい
(
α あるふぁ
n
,
α あるふぁ
n
−
1
,
.
.
.
,
α あるふぁ
0
)
{\displaystyle \varphi (\alpha _{n},\alpha _{n-1},...,\alpha _{0})}
для произвольного числа аргументов, а именно:
φ ふぁい
(
α あるふぁ
)
=
ω おめが
α あるふぁ
{\displaystyle \varphi (\alpha )=\omega ^{\alpha }}
для случая одной переменной,
φ ふぁい
(
0
,
α あるふぁ
n
−
1
,
.
.
.
,
α あるふぁ
0
)
=
φ ふぁい
(
α あるふぁ
n
−
1
,
.
.
.
,
α あるふぁ
0
)
,
{\displaystyle \varphi (0,\alpha _{n-1},...,\alpha _{0})=\varphi (\alpha _{n-1},...,\alpha _{0}),}
и
для
α あるふぁ
>
0
,
γ がんま
↦
φ ふぁい
(
α あるふぁ
n
,
.
.
.
,
α あるふぁ
i
+
1
,
α あるふぁ
,
0
,
.
.
.
,
0
,
γ がんま
)
{\displaystyle \alpha >0,\,\gamma \mapsto \varphi (\alpha _{n},...,\alpha _{i+1},\alpha ,0,...,0,\gamma )}
— это функция, перечисляющая общие неподвижные точки функций
ξ くしー
↦
φ ふぁい
(
α あるふぁ
n
,
.
.
.
,
α あるふぁ
i
+
1
,
β べーた
,
ξ くしー
,
0
,
.
.
.
,
0
)
{\displaystyle \xi \mapsto \varphi (\alpha _{n},...,\alpha _{i+1},\beta ,\xi ,0,...,0)}
для всех
β べーた
<
α あるふぁ
.
{\displaystyle \beta <\alpha .}
Например,
φ ふぁい
(
1
,
0
,
γ がんま
)
{\displaystyle \varphi (1,0,\gamma )}
— это
γ がんま
{\displaystyle \gamma }
-я неподвижная точка функций
ξ くしー
↦
φ ふぁい
(
0
,
ξ くしー
,
0
)
=
φ ふぁい
(
ξ くしー
,
0
)
,
{\displaystyle \xi \mapsto \varphi (0,\xi ,0)=\varphi (\xi ,0),}
а именно
Γ がんま
γ がんま
.
{\displaystyle \Gamma _{\gamma }.}
φ ふぁい
(
1
,
0
,
0
)
=
Γ がんま
0
{\displaystyle \varphi (1,0,0)=\Gamma _{0}}
— ординал Фефермана.
φ ふぁい
(
1
,
0
,
0
,
0
)
{\displaystyle \varphi (1,0,0,0)}
— ординал Аккермана.
Предел для
φ ふぁい
(
1
,
0
,
.
.
.
,
0
,
0
)
{\displaystyle \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 , Lecture Notes in Mathematics, vol. 1407, Berlin: Springer-Verlag, ISBN 3-540-51842-8 , MR 1026933
Schütte, Kurt (1977), Proof theory , Grundlehren der Mathematischen Wissenschaften, vol. 225, Berlin-New York: Springer-Verlag, pp. xii+299, ISBN 3-540-07911-4 , MR 0505313
Takeuti, Gaisi (1987), Proof theory , Studies in Logic and the Foundations of Mathematics, vol. 81 (Second ed.), Amsterdam: North-Holland Publishing Co., ISBN 0-444-87943-9 , MR 0882549
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 , JSTOR 1988605
Miller, Larry W. (1976), "Normal Functions and Constructive Ordinal Notations", The Journal of Symbolic Logic , 41 (2): 439—459, doi :10.2307/2272243 , JSTOR 2272243
Числа Функции Нотации