Veblen function

In mathematics, the Veblen functions are a hierarchy of normal functions (continuous strictly increasing functions from ordinals to ordinals), introduced by Oswald Veblen in . If φ 0 is any normal function, then for any non-zero ordinal α, φ α is the function enumerating the common fixed points of φ β for β<α. These functions are all normal.

In mathematics, the Veblen functions are a hierarchy of normal functions (continuous strictly increasing functions from ordinals to ordinals), introduced by Oswald Veblen in . If φ 0 is any normal function, then for any non-zero ordinal α, φ α is the function enumerating the common fixed points of φ β for β 0 (α)=ω α this family of functions is known as the Veblen hierarchy. The function φ 1 is the same as the ε function: φ 1 (α)= ε α . If \alpha then \varphi_{\alpha}(\varphi_{\beta}(\gamma)) = \varphi_{\beta}(\gamma) . From this and the fact that φ β is strictly increasing we get the ordering: \varphi_\alpha(\beta) if and only if either ( \alpha = \gamma and \beta ) or ( \alpha and \beta ) or ( \alpha > \gamma and \varphi_\alpha(\beta) ). A variation of Cantor normal form used in connection with the Veblen hierarchy is: every nonzero ordinal number α can be uniquely written as \alpha = \varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k) , where k > 0 is a natural number and each term after the first is less than or equal to the previous term, \varphi_{\beta_m}(\gamma_m) \geq \varphi_{\beta_{m+1}}(\gamma_{m+1}) \,, and each \gamma_m If a fundamental sequence can be provided for the last term, then that term can be replaced by such a sequence to get \alpha [n] = \varphi_{\beta_1}(\gamma_1) + \cdots + \varphi_{\beta_{k-1}}(\gamma_{k-1}) + (\varphi_{\beta_k}(\gamma_k) [n]) \,. For any β, if γ is a limit with \gamma then let \varphi_{\beta}(\gamma) [n] = \varphi_{\beta}(\gamma [n]) \,. No such sequence can be provided for \varphi_0(0) = ω 0 = 1 because it does not have cofinality ω. For \varphi_0(\gamma+1) = \omega ^{\gamma+1} = \omega^ \gamma \cdot \omega \,, we choose \varphi_0(\gamma+1) [n] = \varphi_0(\gamma) \cdot n = \omega^{\gamma} \cdot n \,. For \varphi_{\beta+1}(0) \,, we use \varphi_{\beta+1}(0) [0] = 0 and \varphi_{\beta+1}(0) [n+1] = \varphi_{\beta}(\varphi_{\beta+1}(0) [n]) \,, i.e. 0, \varphi_{\beta}(0) , \varphi_{\beta}(\varphi_{\beta}(0)) , etc.. For \varphi_{\beta+1}(\gamma+1) , we use \varphi_{\beta+1}(\gamma+1) [0] = \varphi_{\beta+1}(\gamma)+1 and \varphi_{\beta+1}(\gamma+1) [n+1] = \varphi_{\beta} (\varphi_{\beta+1}(\gamma+1) [n]) \,. Now suppose that β is a limit: If \beta , then let \varphi_{\beta}(0) [n] = \varphi_{\beta [n]}(0) \,. For \varphi_{\beta}(\gamma+1) , use \varphi_{\beta}(\gamma+1) [n] = \varphi_{\beta [n]}(\varphi_{\beta}(\gamma)+1) \,. Otherwise, the ordinal cannot be described in terms of smaller ordinals using \varphi and this scheme does not apply to it. ===The &Gamma; function=== The function Γ enumerates the ordinals α such that φ α (0) = α. Γ 0 is the Feferman–Schütte ordinal, i.e. it is the smallest α such that φ α (0) = α. For Γ 0 , a fundamental sequence could be chosen to be \Gamma_0 [0] = 0 and \Gamma_0 [n+1] = \varphi_{\Gamma_0 [n]} (0) \,. For Γ β+1 , let \Gamma_{\beta+1} [0] = \Gamma_{\beta} + 1 and \Gamma_{\beta+1} [n+1] = \varphi_{\Gamma_{\beta+1} [n]} (0) \,. For Γ β where \beta is a limit, let \Gamma_{\beta} [n] = \Gamma_{\beta [n]} \,. ==Generalizations== ===Finitely many variables=== To build the Veblen function of a finite number of arguments (finitary Veblen function), let the binary function \varphi(\alpha, \gamma) be \varphi_\alpha(\gamma) as defined above. Let z be an empty string or a string consisting of one or more comma-separated zeros 0,0,...,0 and s be an empty string or a string consisting of one or more comma-separated ordinals \alpha _{1},\alpha _{2},...,\alpha _{n} with \alpha _{1}>0 . The binary function \varphi (\beta ,\gamma ) can be written as \varphi (s,\beta ,z,\gamma ) where both s and z are empty strings. The finitary Veblen functions are defined as follows: \varphi (\gamma )=\omega ^{\gamma } \varphi (z,s,\gamma )=\varphi (s,\gamma ) if \beta >0 , then \varphi (s,\beta ,z,\gamma ) denotes the (1+\gamma ) -th common fixed point of the functions \xi \mapsto \varphi (s,\delta ,\xi ,z) for each \delta For example, \varphi(1,0,\gamma) is the (1+\gamma) -th fixed point of the functions \xi\mapsto\varphi(\xi,0) , namely \Gamma_\gamma ; then \varphi(1,1,\gamma) enumerates the fixed points of that function, i.e., of the \xi\mapsto\Gamma_\xi function; and \varphi(2,0,\gamma) enumerates the fixed points of all the \xi\mapsto\varphi(1,\xi,0) . Each instance of the generalized Veblen functions is continuous in the last nonzero variable (i.e., if one variable is made to vary and all later variables are kept constantly equal to zero). The limit of the \varphi(1,0,...,0) where the number of zeroes ranges over ω, is sometimes known as the "small" Veblen ordinal. Every non-zero ordinal \alpha less than the small Veblen ordinal (SVO) can be uniquely written in normal form for the finitary Veblen function: \alpha =\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k}) where k is a positive integer \varphi (s_{1})\geq \varphi (s_{2})\geq \cdots \geq \varphi (s_{k}) s_{m} is a string consisting of one or more comma-separated ordinals \alpha _{m,1},\alpha _{m,2},...,\alpha _{m,n_{m}} where \alpha _{m,1}>0 and each \alpha _{m,i} (\varphi(s_1)+\varphi(s_2)+\cdots+\varphi(s_k))[n]=\varphi(s_1)+\varphi(s_2)+\cdots+\varphi(s_k)[n] , \varphi(\gamma)[n]=\left\{\begin{array}{lcr} n \quad \text{if} \quad \gamma=1\\ \varphi(\gamma-1)\cdot n \quad \text{if} \quad \gamma \quad \text{is a successor ordinal}\\ \varphi(\gamma[n]) \quad \text{if} \quad \gamma \quad \text{is a limit ordinal}\\ \end{array}\right. , \varphi(s,\beta,z,\gamma)[0]=0 and \varphi(s,\beta,z,\gamma)[n+1]=\varphi(s,\beta-1,\varphi(s,\beta,z,\gamma)[n],z) if \gamma=0 and \beta is a successor ordinal, \varphi(s,\beta,z,\gamma)[0]=\varphi(s,\beta,z,\gamma-1)+1 and \varphi(s,\beta,z,\gamma)[n+1]=\varphi(s,\beta-1,\varphi(s,\beta,z,\gamma)[n],z) if \gamma and \beta are successor ordinals, \varphi(s,\beta,z,\gamma)[n]=\varphi(s,\beta,z,\gamma[n]) if \gamma is a limit ordinal, \varphi(s,\beta,z,\gamma)[n]=\varphi(s,\beta[n],z,\gamma) if \gamma=0 and \beta is a limit ordinal, \varphi(s,\beta,z,\gamma)[n]=\varphi(s,\beta[n],\varphi(s,\beta,z,\gamma-1)+1,z) if \gamma is a successor ordinal and \beta is a limit ordinal. ===Transfinitely many variables=== More generally, Veblen showed that φ can be defined even for a transfinite sequence of ordinals α β , provided that all but a finite number of them are zero. Notice that if such a sequence of ordinals is chosen from those less than an uncountable regular cardinal κ, then the sequence may be encoded as a single ordinal less than κ κ (ordinal exponentiation). So one is defining a function φ from κ κ into κ. The definition can be given as follows: let α be a transfinite sequence of ordinals (i.e., an ordinal function with finite support) that ends in zero (i.e., such that α 0 =0), and let α [γ@0] denote the same function where the final 0 has been replaced by γ. Then γ↦φ( α [γ@0]) is defined as the function enumerating the common fixed points of all functions ξ↦φ( β ) where β ranges over all sequences that are obtained by decreasing the smallest-indexed nonzero value of α and replacing some smaller-indexed value with the indeterminate ξ (i.e., β = α [ζ@ι 0 ,ξ@ι] meaning that for the smallest index ι 0 such that α ι 0 is nonzero the latter has been replaced by some value ζ&lt;α ι 0 and that for some smaller index ι&lt;ι 0 , the value α ι =0 has been replaced with ξ). For example, if α =(1@&omega;) denotes the transfinite sequence with value 1 at ω and 0 everywhere else, then φ(1@ω) is the smallest fixed point of all the functions ξ↦φ(ξ,0,...,0) with finitely many final zeroes (it is also the limit of the φ(1,0,...,0) with finitely many zeroes, the small Veblen ordinal). The smallest ordinal α such that α is greater than φ applied to any function with support in α (i.e., that cannot be reached "from below" using the Veblen function of transfinitely many variables) is sometimes known as the "large" Veblen ordinal, or "great" Veblen number. s ; D_\phi (s) = \max \{ 0, \alpha, \beta : \langle \alpha, \beta \rangle \in s \} ; \phi (s) = \inf\, \{ \gamma : D_\phi (s) \leq \gamma \land 0 . Notice that &gamma; is a power of &omega;. Notations in this system begin with the zero-ary function 0, and use the binary function addition + to combine powers of &omega; which come from applying the transfinite Veblen function &phi; to these set-coded functions. 1 = \omega^0 = \phi ( \{ \} ) ; 2 = 1 + 1 ; \omega = \omega^1 = \phi ( \{ \langle 0, 1 \rangle \} ) ; \omega^2 = \phi ( \{ \langle 0, 2 \rangle \} ) ; \epsilon_0 = \phi ( \{ \langle 1, 1 \rangle \} ) = \phi ( \{ \langle 0, \epsilon_0 \rangle \} ) a fixed point; \epsilon_1 = \phi ( \{ \langle 1, 1 \rangle , \langle 0, 1 \rangle \} ) ; \Gamma_0 = \phi ( \{ \langle 2, 1 \rangle \} ) ; \Gamma_1 = \phi ( \{ \langle 2, 1 \rangle , \langle 0, 1 \rangle \} ) ; SVO = \phi ( \{ \langle \omega, 1 \rangle \} ) = \phi ( \{ \langle 0, SVO \rangle \} ) Small Veblen Ordinal is an epsilon number; SVO \cdot 2 = SVO + SVO ; SVO^2 = \phi ( \{ \langle 0, SVO \cdot 2 \rangle \} ) . et cetera. How many times can &phi; take on some value? The values are always powers of &omega;. \omega^0 = 1 = \phi ( \{ \} ) ; 0 . So powers of &omega; are always values of &phi; at least once. Epsilon numbers are fixed points of that, so they are always values at least twice. Some ordinals are values of &phi; infinitely often. For example, &Omega; is a value an uncountable number of times. D_\phi (s) . So if D &phi; &phi; = &phi; is the norm for ordinals which are values more than once. D &phi; > &phi; never occurs. But \not \exists s ( D_\phi (s) and there are many other ordinals for which that is true. They are all very strong limits. The preferred form of s to produce a value of &phi; (s) is the one for which D &phi; (s) D_\phi (s) ; t \phi (s) \implies \phi (t) > \phi (s))) ; 0 ; \alpha + \beta . If &alpha; is an ordinal with no preferred form, then: D_\phi (s) ; \phi ( \{ \langle \alpha, 1 \rangle \} ) = \alpha ; \{ \langle \alpha, 1 \rangle \} ; D_\phi (s) ; t \neq \{\} \land \max \{ 0, \beta : \langle \beta, \delta \rangle \in t \} ; The ordering among epsilon numbers which do not have a preferred form depends on how those epsilon numbers are specified. To give us a way to talk about them, let np &alpha; be an enumeration of the epsilon numbers lacking a preferred form. Let us also define the complexity, X, of ordinals less than np &omega; as follows: X (0) = 0 \beta n The complexity is a (finite) natural number whenever it is defined. And for any natural number k there are only finitely many ordinals &alpha; for which X (&alpha;) takes the value k or less. The fundamental sequence of 0 is the empty sequence. The fundamental sequence of a successor ordinal is (&alpha;+1) [0] = &alpha;. For ordinals with cofinality ≥ &omega; written in normal form with length k > 1 and k (\varphi(s_1)+\varphi(s_2)+\cdots+\varphi(s_k)) \, [\alpha]=\varphi(s_1)+\varphi(s_2)+\cdots+ (\varphi(s_k) \,[\alpha]) . If &phi; (s) has a preferred form and is less than np &omega; , that is it must be strictly greater than D &phi; (s) : \exist t then we can define the fundamental sequence of &phi; (s) by (&phi; (s)) [n] = &rho; n where: \rho_0 = D_\phi (s) \rho_{n+1} = \sup \{ \mu : \exist t and \rho_\omega = \sup \{ \rho_n : n We will show that &phi; (s) = &rho; &omega; . First notice that this sequence is strictly increasing because ( \rho_n = 0 Thus D_\phi (s) = \rho_0 \delta \delta \delta t t t \phi (s) \leq \rho_\omega . On the other hand, \rho_0 = D_\phi (s) \leq \phi (s) but &phi; (s) ≠ 0, 1, or 2, since it has cofinality ≥ &omega; and &phi; (s) ≠ D &phi; (s) since it has a preferred form. Thus \rho_0 Now, let us use mathematical induction with the inductive hypothesis &rho; n \rho_n then \rho_n + \rho_n because &phi; (s) is a power of &omega; 1 t thus n \rho_\omega \leq \phi (s) . Otherwise, &phi; (s) lacks a preferred form and we can set: \rho_\alpha = \sup \{ \mu : \mu = 0 \lor \exist \beta via transfinite recursion. This sequence may be longer than &omega;, but that is unavoidable since the Veblen functions are unable to comprehend some of the more complex ways of forming cofinal sequences. That is, such ordinals include (and may be indistinguishable from) uncountable regular ordinals which do not have fundamental sequences of length &omega;. ==Values== The function takes on several prominent values: \varphi(1,0) = \varepsilon_0 is the proof-theoretic ordinal of Peano arithmetic and the limit of what ordinals can be represented in terms of Cantor normal form and smaller ordinals. \varphi(\omega,0) , a bound on the order types of the recursive path orderings with finitely many function symbols, and the smallest ordinal closed under primitive recursive ordinal functions. The Feferman–Schütte ordinal \Gamma_0 is equal to \varphi(1,0,0) . The small Veblen ordinal is equal to \varphi\begin{pmatrix}1 \\ \omega\end{pmatrix} . ==References== Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Uninitiated, expository article (8 pages, in PostScript) contains an informal description of the Veblen hierarchy. ===Citations===

Text derived from https://en.wikipedia.org/w/index.php?oldid=1343145317 under CC BY-SA 4.0; modifications have been made.