В математике функции Веблена — иерархия нормальных функций, строго возрастающих от ординала к ординалу, предложенная Освальдом Вебленом в 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
Числа Функции Нотации