You do not have permission to edit this page, for the following reasons:

This IP address has been blocked from editing Wikipedia.
This does not affect your ability to read Wikipedia pages.
Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

The IP address or range 18.208.0.0/16 has been blocked (disabled) by ‪ST47‬ for the following reason(s):

The IP address that you are currently using has been blocked because it is believed to be a web host provider. To prevent abuse, web hosts may be blocked from editing Wikipedia.
You will not be able to edit Wikipedia using a web host provider because it hides your IP address, much like a proxy or VPN.
We recommend that you attempt to use another connection to edit. For example, if you use a proxy or VPN to connect to the internet, turn it off when editing Wikipedia. If you edit using a mobile connection, try using a Wi-Fi connection, and vice versa. If you are using a corporate internet connection, switch to a different Wi-Fi network. If you have a Wikipedia account, please log in.
If you do not have any other way to edit Wikipedia, you will need to request an IP block exemption.

How to appeal if you are confident that your connection does not use a web host's IP address:
If you are confident that you are not using a web host, you may appeal this block by adding the following text on your talk page: ((unblock|reason=Caught by a web host block but this host or IP is not a web host. My IP address is _______. Place any further information here. ~~~~)). You must fill in the blank with your IP address for this block to be investigated. Your IP address can be determined here. Alternatively, if you wish to keep your IP address private you can use the unblock ticket request system. There are several reasons you might be editing using the IP address of a web host (such as if you are using VPN software or a business network); please use this method of appeal only if you think your IP address is in fact not a web host.

Administrators: The IP block exemption user right should only be applied to allow users to edit using web host in exceptional circumstances, and they should usually be directed to the functionaries team via email. If you intend to give the IPBE user right, a CheckUser needs to take a look at the account. This can be requested most easily at SPI Quick Checkuser Requests. Unblocking an IP or IP range with this template is highly discouraged without at least contacting the blocking administrator.

This block will expire on 01:01, 24 April 2026.

Even when blocked, you will usually still be able to edit your user talk page, as well as email administrators and other editors.

For information on how to proceed, please read the FAQ for blocked users and the guideline on block appeals. The guide to appealing blocks may also be helpful.

Other useful links: Blocking policy · Help:I have been blocked
Your IP address is in a range that has been blocked on all Wikimedia Foundation wikis. The block was made by ‪AntiCompositeNumber‬. The reason given is Open proxy/Webhost: See the help page if you are affected .
- Start of block: 15:08, 30 August 2023
- Expiry of block: 15:08, 30 August 2025
Your current IP address is 18.208.109.86. The blocked range is 18.208.0.0/16. Please include all above details in any queries you make. If you believe you were blocked by mistake, you can find additional information and instructions in the No open proxies global policy. Otherwise, to discuss the block please post a request for review on Meta-Wiki. You could also send an email to the stewards VRT queue at stewards@wikimedia.org including all above details.

You can view and copy the source of this page:

((Short description|Mathematical function on ordinals))
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 φ<sub>0</sub> is any normal function, then for any non-zero ordinal α, φ<sub>α</sub> is the function enumerating the common [[fixed point (mathematics)|fixed point]]s of φ<sub>β</sub> for β<α. These functions are all normal.

== Veblen hierarchy ==
In the special case when  φ<sub>0</sub>(α)=ω<sup>α</sup>
this family of functions is known as the '''Veblen hierarchy'''. 
The function φ<sub>1</sub> is the same as the [[Epsilon numbers (mathematics)|ε function]]: φ<sub>1</sub>(α)= ε<sub>α</sub>.<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.</ref> From this and the fact that φ<sub>β</sub> 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 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 [[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> = ω<sup>0</sup> = 1 because it does not have cofinality ω.

For <math>\varphi_0(\gamma+1) = \omega ^{\gamma+1} = \omega^ \gamma \cdot \omega \,,</math> we choose <math>\varphi_0(\gamma+1) [n] = \varphi_0(\gamma) \cdot n  = \omega^{\gamma} \cdot n \,.</math>

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

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>

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

Otherwise, the ordinal cannot be described in terms of smaller ordinals using <math>\varphi</math> and this scheme does not apply to it.

===The &Gamma; function===
The function Γ enumerates the ordinals α such that φ<sub>α</sub>(0) = α. 
Γ<sub>0</sub> is the [[Feferman–Schütte ordinal]], i.e. it is the smallest α such that φ<sub>α</sub>(0) = α.

For Γ<sub>0</sub>, 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>

For Γ<sub>β+1</sub>, 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 Γ<sub>β</sub> where <math>\beta < \Gamma_{\beta} </math> is a limit, let <math>\Gamma_{\beta} [n] = \Gamma_{\beta [n]} \,.</math>

==Generalizations==

===Finitely many variables===
To build the Veblen function of a finite number of arguments (finitary Veblen function), let the binary function <math>\varphi(\alpha, \gamma)</math> be <math>\varphi_\alpha(\gamma)</math> as defined above.

Let <math>z</math> be an empty string or a string consisting of one or more comma-separated zeros <math>0,0,...,0</math> and <math>s</math> be an empty string or a string consisting of one or more comma-separated ordinals <math>\alpha _{1},\alpha _{2},...,\alpha _{n}</math> with <math>\alpha _{1}>0</math>. The binary function <math>\varphi (\beta ,\gamma )</math> can be written as <math>\varphi (s,\beta ,z,\gamma )</math> where both <math>s</math> and <math>z</math> are empty strings.
The finitary Veblen functions are defined as follows:
* <math>\varphi (\gamma )=\omega ^{\gamma }</math>
* <math>\varphi (z,s,\gamma )=\varphi (s,\gamma )</math>
* if <math>\beta >0</math>, then <math>\varphi (s,\beta ,z,\gamma )</math> denotes the <math>(1+\gamma )</math>-th common fixed point of the functions <math>\xi \mapsto \varphi (s,\delta ,\xi ,z)</math> for each <math>\delta <\beta</math>

For example, <math>\varphi(1,0,\gamma)</math> is the <math>(1+\gamma)</math>-th fixed point of the functions <math>\xi\mapsto\varphi(\xi,0)</math>, namely <math>\Gamma_\gamma</math>; then <math>\varphi(1,1,\gamma)</math> enumerates the fixed points of that function, i.e., of the <math>\xi\mapsto\Gamma_\xi</math> function; and <math>\varphi(2,0,\gamma)</math> enumerates the fixed points of all the <math>\xi\mapsto\varphi(1,\xi,0)</math>.  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 <math>\varphi(1,0,0,0)</math> is sometimes known as the [[Ackermann ordinal]].  The limit of the <math>\varphi(1,0,...,0)</math> where the number of zeroes ranges over ω, is sometimes known as the [[Small Veblen ordinal|"small" Veblen ordinal]].

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

<math>\alpha =\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k})</math>

where
* <math>k</math> is a positive integer
* <math>\varphi (s_{1})\geq \varphi (s_{2})\geq \cdots \geq \varphi (s_{k})</math>
* <math>s_{m}</math> is a string consisting of one or more comma-separated ordinals <math>\alpha _{m,1},\alpha _{m,2},...,\alpha _{m,n_{m))</math> where <math>\alpha _{m,1}>0</math> and each <math>\alpha _{m,i}<\varphi (s_{m})</math>

=== Fundamental sequences for limit ordinals of finitary Veblen function ===

For limit ordinals <math>\alpha<SVO</math>, written in normal form for the finitary Veblen function:
* <math>(\varphi(s_1)+\varphi(s_2)+\cdots+\varphi(s_k))[n]=\varphi(s_1)+\varphi(s_2)+\cdots+\varphi(s_k)[n]</math>,
* <math>\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.
</math>,
* <math>\varphi(s,\beta,z,\gamma)[0]=0</math> and <math>\varphi(s,\beta,z,\gamma)[n+1]=\varphi(s,\beta-1,\varphi(s,\beta,z,\gamma)[n],z)</math> if <math>\gamma=0</math> and <math>\beta</math> is a successor ordinal,
* <math>\varphi(s,\beta,z,\gamma)[0]=\varphi(s,\beta,z,\gamma-1)+1</math> and <math>\varphi(s,\beta,z,\gamma)[n+1]=\varphi(s,\beta-1,\varphi(s,\beta,z,\gamma)[n],z)</math> if <math>\gamma</math> and <math>\beta</math> are successor ordinals,
* <math>\varphi(s,\beta,z,\gamma)[n]=\varphi(s,\beta,z,\gamma[n])</math> if <math>\gamma</math> is a limit ordinal,
* <math>\varphi(s,\beta,z,\gamma)[n]=\varphi(s,\beta[n],z,\gamma)</math> if <math>\gamma=0</math> and <math>\beta</math> is a limit ordinal,
* <math>\varphi(s,\beta,z,\gamma)[n]=\varphi(s,\beta[n],\varphi(s,\beta,z,\gamma-1)+1,z)</math> if <math>\gamma</math> is a successor ordinal and <math>\beta</math> is a limit ordinal.

===Transfinitely many variables===
More generally, Veblen showed that φ can be defined even for a transfinite sequence of ordinals α<sub>β</sub>, 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 κ<sup>κ</sup> (ordinal exponentiation). So one is defining a function φ from κ<sup>κ</sup> 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) ''which ends in zero'' (i.e., such that α<sub>0</sub>=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>[ζ@ι<sub>0</sub>,ξ@ι] meaning that for the smallest index ι<sub>0</sub> such that α<sub>ι<sub>0</sub></sub> is nonzero the latter has been replaced by some value ζ&lt;α<sub>ι<sub>0</sub></sub> and that for some smaller index ι&lt;ι<sub>0</sub>, the value α<sub>ι</sub>=0 has been replaced with ξ).

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

=== Further extensions ===
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 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 |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-Schutte 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 |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 |year=2023 |arxiv=2310.12832 |last2=Kwon |first2=Adrian Wang))
===Citations===
((Reflist))

[[Category:Ordinal numbers]]
[[Category:Proof theory]]
[[Category:Hierarchy of functions]]

Pages transcluded onto the current version of this page (help):

Veblen function (edit)
Template:Ambox (view source) (template editor protected)
Template:Citation (view source) (protected)
Template:Cite journal (view source) (protected)
Template:Harvard citation text (view source) (template editor protected)
Template:Harvtxt (view source) (template editor protected)
Template:Main other (view source) (protected)
Template:Pagetype (view source) (protected)
Template:Reflist (view source) (protected)
Template:Reflist/styles.css (view source) (protected)
Template:SDcat (view source) (protected)
Template:Short description (view source) (protected)
Template:Short description/lowercasecheck (view source) (protected)
Template:Unreferenced (view source) (template editor protected)
Template:Unreferenced section (view source) (template editor protected)
Template:Unsourced section (view source) (semi-protected)
Module:Arguments (view source) (protected)
Module:Category handler (view source) (protected)
Module:Category handler/blacklist (view source) (protected)
Module:Category handler/config (view source) (protected)
Module:Category handler/data (view source) (protected)
Module:Category handler/shared (view source) (protected)
Module:Check for unknown parameters (view source) (protected)
Module:Citation/CS1 (view source) (protected)
Module:Citation/CS1/COinS (view source) (protected)
Module:Citation/CS1/Configuration (view source) (protected)
Module:Citation/CS1/Date validation (view source) (protected)
Module:Citation/CS1/Identifiers (view source) (protected)
Module:Citation/CS1/Utilities (view source) (protected)
Module:Citation/CS1/Whitelist (view source) (protected)
Module:Citation/CS1/styles.css (view source) (protected)
Module:Disambiguation/templates (view source) (protected)
Module:Footnotes (view source) (template editor protected)
Module:Footnotes/anchor id list (view source) (template editor protected)
Module:Footnotes/anchor id list/data (view source) (template editor protected)
Module:Footnotes/whitelist (view source) (template editor protected)
Module:Message box (view source) (protected)
Module:Message box/ambox.css (view source) (protected)
Module:Message box/configuration (view source) (protected)
Module:Namespace detect/config (view source) (protected)
Module:Namespace detect/data (view source) (protected)
Module:Pagetype (view source) (protected)
Module:Pagetype/config (view source) (protected)
Module:Pagetype/disambiguation (view source) (protected)
Module:Pagetype/setindex (view source) (protected)
Module:Pagetype/softredirect (view source) (protected)
Module:SDcat (view source) (protected)
Module:String (view source) (protected)
Module:Unsubst (view source) (protected)
Module:Wikitext Parsing (view source) (protected)
Module:Yesno (view source) (protected)

Return to Veblen function.

Retrieved from "https://en.wikipedia.org/wiki/Veblen_function"