Veblen function: Difference between revisions

Revision as of 14:37, 28 December 2021

Latest revision as of 16:19, 15 May 2025

(22 intermediate revisions by 11 users not shown)

Line 1:

{{Short description|Mathematical function on ordinals}}

<math>\forall x \in \N \rightarrow \surd-x = ix</math>In [[mathematics]], the '''Veblen functions''' are a hierarchy of [[normal function]]s ([[continuous function (set theory)|continuous]] [[strictly increasing function|strictly increasing]] [[function (mathematics)|function]]s from [[ordinal number|ordinal]]s to ordinals), introduced by [[Oswald Veblen]] in {{harvtxt|Veblen|1908}}. If ''φ''₀ is any normal function, then for any non-zero ordinal ''α'', ''φ''_''α'' is the function enumerating the common [[fixed point (mathematics)|fixed point]]s of ''φ''_''β'' for ''β''<''α''. These functions are all normal.

== The Veblen hierarchy ==

In the special case when ''φ''₀(''α'')=ω^''α''

<math>\forall x \in \N \rightarrow \surd-x = ix</math>In [[mathematics]], the '''Veblen functions''' are a hierarchy of [[normal function]]s ([[continuous function (set theory)|continuous]] [[strictly increasing function|strictly increasing]] [[function (mathematics)|function]]s from [[ordinal number|ordinal]]s to ordinals), introduced by [[Oswald Veblen]] in {{harvtxt|Veblen|1908}}. If φ₀ is any normal function, then for any non-zero ordinal α, φ_α is the function enumerating the common [[fixed point (mathematics)|fixed point]]s of φ_β for β<α. These functions are all normal.

== The Veblen hierarchy ==

In the special case when φ₀(α)=ω^α

this family of functions is known as the '''Veblen hierarchy'''.

The function ''φ''₁ is the same as the [[Epsilon numbers (mathematics)|ε function]]: ''φ''₁(''α'')= ε_''α''.<ref>[[Stephen G. Simpson]], ''Subsystems of Second-order Arithmetic'' (2009, p.387)</ref> If <math>\alpha < \beta \,,</math> then <math>\varphi_{\alpha}(\varphi_{\beta}(\gamma)) = \varphi_{\beta}(\gamma)</math>.<ref \name="Rathjen90">M. Rathjen, [https://www1.maths.leeds.ac.uk/~rathjen/Ord_Notation_Weakly_Mahlo.pdf Ordinal notations based on a weakly Mahlo cardinal], (1990, p.251). Accessed 16 August 2022.</mathref> From this and the fact that φ_''β'' is strictly increasing we get the ordering: <math>\varphi_\alpha(\beta) < \varphi_\gamma(\delta) </math> if and only if either (<math>\alpha = \gamma </math> and <math>\beta < \delta </math>) or (<math>\alpha < \gamma </math> and <math>\beta < \varphi_\gamma(\delta) </math>) or (<math>\alpha > \gamma </math> and <math>\varphi_\alpha(\beta) < \delta </math>).<ref name="Rathjen90" />

=== Fundamental sequences for the Veblen hierarchy ===

{{unsourced section|date=May 2023}}

The fundamental sequence for an ordinal with [[cofinality]] ω is a distinguished strictly increasing ω-sequence whichthat 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 [[Ordinal arithmetic#Cantor normal form|Cantor normal form]] used in connection with the Veblen hierarchy is &mdash;: every nonzero ordinal number ''α'' can be uniquely written as <math>\alpha = \varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k)</math>, where ''k''>0 is a natural number and each term after the first is less than or equal to the previous term, <math>\varphi_{\beta_m}(\gamma_m) \geq \varphi_{\beta_{m+1}}(\gamma_{m+1}) \,,</math> and each <math>\gamma_m < \varphi_{\beta_m}(\gamma_m) \,.</math> If a fundamental sequence can be provided for the last term, then that term can be replaced by such a sequence to get <math>\alpha [n] = \varphi_{\beta_1}(\gamma_1) + \cdots + \varphi_{\beta_{k-1}}(\gamma_{k-1}) + (\varphi_{\beta_k}(\gamma_k) [n]) \,.</math>

For any ''β'', if ''γ'' is a limit with <math>\gamma < \varphi_{\beta} (\gamma) \,,</math> then let <math>\varphi_{\beta}(\gamma) [n] = \varphi_{\beta}(\gamma [n]) \,.</math>

No such sequence can be provided for <math>\varphi_0(0)</math> = ω⁰ = 1 because it does not have cofinality ω.

Line 25 ⟶ 23:

For <math>\varphi_{\beta+1}(\gamma+1)</math>, we use <math>\varphi_{\beta+1}(\gamma+1) [0] = \varphi_{\beta+1}(\gamma)+1 </math> and <math>\varphi_{\beta+1}(\gamma+1) [n+1] = \varphi_{\beta} (\varphi_{\beta+1}(\gamma+1) [n]) \,.</math>

Now suppose that ''β'' is a limit:

If <math>\beta < \varphi_{\beta}(0)</math>, then let <math>\varphi_{\beta}(0) [n] = \varphi_{\beta [n]}(0) \,.</math>

Line 34 ⟶ 32:

===The &Gamma; function===

The function Γ enumerates the ordinals ''α'' such that φ_''α''(0) = ''α''.

Γ₀ is the [[Feferman–Schütte ordinal]], i.e. it is the smallest ''α'' such that ''φ''_''α''(0) = ''α''.

For Γ₀, a fundamental sequence could be chosen to be <math>\Gamma_0 [0] = 0 </math> and <math>\Gamma_0 [n+1] = \varphi_{\Gamma_0 [n]} (0) \,.</math>

Line 41 ⟶ 39:

For Γ_β+1, let <math>\Gamma_{\beta+1} [0] = \Gamma_{\beta} + 1 </math> and <math>\Gamma_{\beta+1} [n+1] = \varphi_{\Gamma_{\beta+1} [n]} (0) \,.</math>

For Γ_''β'' where <math>\beta < \Gamma_{\beta} </math> is a limit, let <math>\Gamma_{\beta} [n] = \Gamma_{\beta [n]} \,.</math>

==Generalizations==

Line 84 ⟶ 82:

===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 <u>α</u> be a transfinite sequence of ordinals (i.e., an ordinal function with finite support) ''whichthat ends in zero'' (i.e., such that α₀=0), and let <u>α</u>[0↦γγ@0] denote the same function where the final 0 has been replaced by γ. Then γ↦φ(<u>α</u>[0↦γγ@0]) is defined as the function enumerating the common fixed points of all functions ξ↦φ(<u>β</u>) where <u>β</u> ranges over all sequences whichthat are obtained by decreasing the smallest-indexed nonzero value of <u>α</u> and replacing some smaller-indexed value with the indeterminate ξ (i.e., <u>β</u>=<u>α</u>[ζ@ι₀↦ζ,ι↦ξξ@ι] meaning that for the smallest index ι₀ such that α_ι₀ is nonzero the latter has been replaced by some value ζ&lt;α_ι₀ and that for some smaller index ι&lt;ι₀, the value α_ι=0 has been replaced with ξ).

For example, if <u>α</u>=(ω↦11@&omega;) denotes the transfinite sequence with value 1 at ω and 0 everywhere else, then φ(ω↦11@ω) 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., whichthat cannot be reached "from below" using the Veblen function of transfinitely many variables) is sometimes known as the [[Large Veblen ordinal|"large" Veblen ordinal]], or "great" Veblen number.<ref>M. Rathjen, "[https://www1.maths.leeds.ac.uk/~rathjen/ICMend.pdf The Art of Ordinal Analysis]" (2006), appearing in Proceedings of the International Congress of Mathematicians 2006.</ref>

The definition can be given as follows: let <u>α</u> be a transfinite sequence of ordinals (i.e., an ordinal function with finite support) ''which ends in zero'' (i.e., such that α₀=0), and let <u>α</u>[0↦γ] denote the same function where the final 0 has been replaced by γ. Then γ↦φ(<u>α</u>[0↦γ]) is defined as the function enumerating the common fixed points of all functions ξ↦φ(<u>β</u>) where <u>β</u> ranges over all sequences which are obtained by decreasing the smallest-indexed nonzero value of <u>α</u> and replacing some smaller-indexed value with the indeterminate ξ (i.e., <u>β</u>=<u>α</u>[ι₀↦ζ,ι↦ξ] meaning that for the smallest index ι₀ such that α_ι₀ is nonzero the latter has been replaced by some value ζ&lt;α_ι₀ and that for some smaller index ι&lt;ι₀, the value α_ι=0 has been replaced with ξ).

=== Further extensions ===

For example, if <u>α</u>=(ω↦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).

In {{harvtxt|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==

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|"large" Veblen ordinal]].

The function takes on several prominent values:

* <math>\varphi(1,0) = \varepsilon_0</math> is the [[Proof theoretic ordinal|proof-theoretic ordinal]] [[Gentzen's consistency proof|of]] [[Peano axioms|Peano arithmetic]] and the limit of what ordinals can be represented in terms of [[Cantor normal form]] and smaller ordinals.

* <math>\varphi(\omega,0)</math>, a bound on the order types of the [[Path ordering (term rewriting)|recursive path orderings]] with finitely many function symbols, and the smallest ordinal closed under [[Primitive recursive function|primitive recursive]] ordinal functions.<ref>N. Dershowitz, M. Okada, [https://www.cs.tau.ac.il/~nachumd/papers/ProofTheoretic.pdf Proof Theoretic Techniques for Term Rewriting Theory] (1988). p.105</ref><ref>{{Cite journal |last=Avigad |first=Jeremy |authorlink =

Jeremy Avigad|date=May 23, 2001 |title=An ordinal analysis of admissible set theory using recursion on ordinal notations |url=https://www.andrew.cmu.edu/user/avigad/Papers/admissible.pdf |journal=Journal of Mathematical Logic |volume=2 |pages=91--112 |doi=10.1142/s0219061302000126}}</ref>

* The [[Feferman–Schütte ordinal]] <math>\Gamma_0</math> is equal to <math>\varphi(1,0,0)</math>.<ref>D. Madore, "[http://www.madore.org/~david/math/ordinal-zoo.pdf A Zoo of Ordinals]" (2017). Accessed 02 November 2022.</ref>

* The [[small Veblen ordinal]] is equal to <math>\varphi\begin{pmatrix}1 \\ \omega\end{pmatrix}</math>.<ref>{{cite journal | url=https://link.springer.com/content/pdf/10.1007/s00153-019-00658-x.pdf | doi=10.1007/s00153-019-00658-x | title=A flexible type system for the small Veblen ordinal | year=2019 | last1=Ranzi | first1=Florian | last2=Strahm | first2=Thomas | journal=Archive for Mathematical Logic | volume=58 | issue=5–6 | pages=711–751 | s2cid=253675808 }}</ref>

==References==

* <!--Not considered reliable, according to a revert on [[Small Veblen ordinal]].-->Hilbert Levitz, ''[http://www.cs.fsu.edu/~levitz/ords.ps Transfinite Ordinals and Their Notations: For The Uninitiated]'', expository article (8 pages, in [[PostScript]])

*{{citation|last= Pohlers|first= Wolfram|title= Proof theory|mr= 1026933|series= Lecture Notes in Mathematics|volume= 1407|publisher= Springer-Verlag|place= Berlin|year= 1989|isbn= 978-3-540-51842-6|doi= 10.1007/978-3-540-46825-7|url-access= registration|url= https://archive.org/details/prooftheoryintro0000pohl}}

*{{citation|mr=0505313|last= Schütte|first= Kurt |title=Proof theory|series= Grundlehren der Mathematischen Wissenschaften|volume= 225|publisher= Springer-Verlag|place= Berlin-New York|year= 1977|pages= xii+299 | isbn= 978-3-540-07911-8}}

*{{citation|mr=0882549|last= Takeuti|first= Gaisi |authorlink = Gaisi Takeuti|title=Proof theory|edition= Second |series= Studies in Logic and the Foundations of Mathematics|volume= 81|publisher= North-Holland Publishing Co.|place= Amsterdam|year=1987| isbn= 978-0-444-87943-1}}

*{{citation |last=Smorynski |first=C. |year=1982 |title=The varieties of arboreal experience |journal=Math. Intelligencer |volume=4 |issue=4 |pages=182–189 |doi=10.1007/BF03023553}} contains an informal description of the Veblen hierarchy.

*{{citation|title= Continuous Increasing Functions of Finite and Transfinite Ordinals |first=Oswald |last=Veblen |journal= Transactions of the American Mathematical Society|volume= 9|issue= 3|year= 1908|pages=280–292 |doi= 10.2307/1988605|jstor=1988605|doi-access= free}}

*{{citation |jstor=2272243 |pages=439–459 |last1=Miller |first1=Larry W. |title=Normal Functions and Constructive Ordinal Notations |volume=41 |issue=2 |journal=The Journal of Symbolic Logic |year=1976 |doi=10.2307/2272243}}

*{{citation |last=Massmann |first=Jayde Sylvie |title=Extending the Veblen Function |date=October 20, 2023 |url=https://arxiv.org/abs/2310.12832 |arxiv=2310.12832 |last2=Kwon |first2=Adrian Wang}}

===Citations===

{{Reflist}}

[[Category:Ordinal numbers]]