Veblen function

Summary

In mathematics, the Veblen functions are a hierarchy of normal functions (continuous strictly increasing functions from ordinals to ordinals), introduced by Oswald Veblen in Veblen (1908). 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.

Veblen hierarchy

edit

In the special case when φ0(α)=ωα this family of functions is known as the Veblen hierarchy. The function φ1 is the same as the ε function: φ1(α)= εα.[1] If   then  .[2] From this and the fact that φβ is strictly increasing we get the ordering:   if and only if either (  and  ) or (  and  ) or (  and  ).[2]

Fundamental sequences for the Veblen hierarchy

edit

The fundamental sequence for an ordinal with cofinality ω is a distinguished strictly increasing ω-sequence which has the ordinal as its limit. If one has fundamental sequences for α and all smaller limit ordinals, then one can create an explicit constructive bijection between ω and α, (i.e. one not using the axiom of choice). Here we will describe fundamental sequences for the Veblen hierarchy of ordinals. The image of n under the fundamental sequence for α will be indicated by α[n].

A variation of Cantor normal form used in connection with the Veblen hierarchy is — every nonzero ordinal number α can be uniquely written as  , where k>0 is a natural number and each term after the first is less than or equal to the previous term,   and each   If a fundamental sequence can be provided for the last term, then that term can be replaced by such a sequence to get  

For any β, if γ is a limit with   then let  

No such sequence can be provided for   = ω0 = 1 because it does not have cofinality ω.

For   we choose  

For   we use   and   i.e. 0,  ,  , etc..

For  , we use   and  

Now suppose that β is a limit:

If  , then let  

For  , use  

Otherwise, the ordinal cannot be described in terms of smaller ordinals using   and this scheme does not apply to it.

The Γ function

edit

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   and  

For Γβ+1, let   and  

For Γβ where   is a limit, let  

Generalizations

edit

Finitely many variables

edit

To build the Veblen function of a finite number of arguments (finitary Veblen function), let the binary function   be   as defined above.

Let   be an empty string or a string consisting of one or more comma-separated zeros   and   be an empty string or a string consisting of one or more comma-separated ordinals   with  . The binary function   can be written as   where both   and   are empty strings. The finitary Veblen functions are defined as follows:

  •  
  •  
  • if  , then   denotes the  -th common fixed point of the functions   for each  

For example,   is the  -th fixed point of the functions  , namely  ; then   enumerates the fixed points of that function, i.e., of the   function; and   enumerates the fixed points of all the  . 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 ordinal   is sometimes known as the Ackermann ordinal. The limit of the   where the number of zeroes ranges over ω, is sometimes known as the "small" Veblen ordinal.

Every non-zero ordinal   less than the small Veblen ordinal (SVO) can be uniquely written in normal form for the finitary Veblen function:

 

where

  •   is a positive integer
  •  
  •   is a string consisting of one or more comma-separated ordinals   where   and each  

Fundamental sequences for limit ordinals of finitary Veblen function

edit

For limit ordinals  , written in normal form for the finitary Veblen function:

  •  ,
  •  ,
  •   and   if   and   is a successor ordinal,
  •   and   if   and   are successor ordinals,
  •   if   is a limit ordinal,
  •   if   and   is a limit ordinal,
  •   if   is a successor ordinal and   is a limit ordinal.

Transfinitely many variables

edit

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) which 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 which 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 ζ<αι0 and that for some smaller index ι<ι0, the value αι=0 has been replaced with ξ).

For example, if α=(1@ω) 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., which 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.[3]

Further extensions

edit

In Massmann & Kwon (2023), the Veblen function was extended further to a somewhat technical system known as dimensional Veblen. In this, one may take fixed points or row numbers, meaning expressions such as φ(1@(1,0)) are valid (representing the large Veblen ordinal), visualised as multi-dimensional arrays. It was proven that all ordinals below the Bachmann–Howard ordinal could be represented in this system, and that the representations for all ordinals below the large Veblen ordinal were aesthetically the same as in the original system.

Values

edit

The function takes on several prominent values:

References

edit
  • 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, doi:10.1007/978-3-540-46825-7, ISBN 978-3-540-51842-6, MR 1026933
  • Schütte, Kurt (1977), Proof theory, Grundlehren der Mathematischen Wissenschaften, vol. 225, Berlin-New York: Springer-Verlag, pp. xii+299, ISBN 978-3-540-07911-8, 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 978-0-444-87943-1, 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
  • Massmann, Jayde Sylvie; Kwon, Adrian Wang (October 20, 2023), Extending the Veblen Function, arXiv:2310.12832{{citation}}: CS1 maint: date and year (link)

Citations

edit
  1. ^ Stephen G. Simpson, Subsystems of Second-order Arithmetic (2009, p.387)
  2. ^ a b M. Rathjen, Ordinal notations based on a weakly Mahlo cardinal, (1990, p.251). Accessed 16 August 2022.
  3. ^ M. Rathjen, "The Art of Ordinal Analysis" (2006), appearing in Proceedings of the International Congress of Mathematicians 2006.
  4. ^ N. Dershowitz, M. Okada, Proof Theoretic Techniques for Term Rewriting Theory (1988). p.105
  5. ^ Avigad, Jeremy (May 23, 2001). "An ordinal analysis of admissible set theory using recursion on ordinal notations" (PDF). Journal of Mathematical Logic. 2: 91--112. doi:10.1142/s0219061302000126.
  6. ^ D. Madore, "A Zoo of Ordinals" (2017). Accessed 02 November 2022.
  7. ^ Ranzi, Florian; Strahm, Thomas (2019). "A flexible type system for the small Veblen ordinal" (PDF). Archive for Mathematical Logic. 58 (5–6): 711–751. doi:10.1007/s00153-019-00658-x. S2CID 253675808.