Veblen function

Veblen function

In mathematics, the Veblen functions are a hierarchy of functions from ordinals to ordinals, introduced by harvtxt|Veblen|1908. If &phi;0 is any continuous strictly increasing function from ordinals to ordinals, then for any non-zero ordinal α, &phi;α is the function enumerating the common fixed points of &phi;&beta; for &beta;<α. These functions are all continuous strictly increasing functions (i.e. normal functions) from ordinals to ordinals.

The Veblen hierarchy

In the special case when &phi;0(α)=&omega;αthis family of functions is known as the Veblen hierarchy. The function &phi;1 is the same as the &epsilon; function: &phi;1(α)= &epsilon;α.Ordering: varphi_alpha(eta) < varphi_gamma(delta) if and only if either (alpha = gamma and eta < delta) or (alpha < gamma and eta < varphi_gamma(delta)) or (alpha > gamma and varphi_alpha(eta) < delta).

Fundamental sequences for the Veblen hierarchy

The fundamental sequence of 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.

A variation of Cantor normal form used in connection with the Veblen hierarchy is -- every ordinal number α can be uniquely written as varphi_{eta_1}(gamma_1) + varphi_{eta_2}(gamma_2) + cdots + varphi_{eta_k}(gamma_k), where "k" is a natural number and each term after the first is less than or equal to the previous term and each gamma_j is not a fixed point of varphi_{eta_j}. If a fundamental sequence can be provided for the last term, then that term can be replaced by such a sequence to get a fundamental sequence for α.

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 the function which maps the natural number m to omega^gamma cdot m.

If γ is a limit which is not a fixed point of varphi_0, then for varphi_0(gamma), we replace γ by its fundamental sequence inside varphi_0.

For varphi_{eta+1}(0), we use 0, varphi_{eta}(0), varphi_{eta}(varphi_{eta}(0)), varphi_{eta}(varphi_{eta}(varphi_{eta}(0))), etc..

For varphi_{eta+1}(gamma+1), we use varphi_{eta+1}(gamma)+1, varphi_{eta}(varphi_{eta+1}(gamma)+1), varphi_{eta}(varphi_{eta}(varphi_{eta+1}(gamma)+1)), etc..

If γ is a limit which is not a fixed point of varphi_{eta+1}, then for varphi_{eta+1}(gamma), we replace γ by its fundamental sequence inside varphi_{eta+1}.

Now suppose that β is a limit:If eta < varphi_{eta}(0), then for varphi_{eta}(0), we replace β by its fundamental sequence.

For varphi_{eta}(gamma+1), use varphi_{eta_m}(varphi_{eta}(gamma)+1) where eta_m is the fundamental sequence for β.

If γ is a limit which is not a fixed point of varphi_{eta}, then for varphi_{eta}(gamma), we replace γ by its fundamental sequence inside varphi_{eta}.

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 &Gamma; enumerates the ordinals α such that &phi;α(0) = α. &Gamma;0 is the Feferman-Schutte ordinal, i.e. it is the smallest α such that &phi;α(0) = α.

Generalizations

In this section it is more convenient to think of &phi;α(&beta;) as a function &phi;(α,&beta;) of two variables. Veblen showed how to generalize the definition to produce a function &phi;(α"n", ...,α0) of several variables. More generally he showed that&phi; can be defined even for a transfinite sequence of ordinals α&beta;, provided that all but a finite number of them are zero.

References

* 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|id=MR|1026933
series= Lecture Notes in Mathematics|volume= 1407|publisher= Springer-Verlag|place= Berlin|year= 1989|ISBN= 3-540-51842-8

*citation|id=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= 3-540-07911-4
*citation|id=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= 0-444-87943-9
*Smorynski, C. "The varieties of arboreal experience" Math. Intelligencer 4 (1982), no. 4, 182-189; 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
url= http://links.jstor.org/sici?sici=0002-9947%28190807%299%3A3%3C280%3ACIFOFA%3E2.0.CO%3B2-1

* Larry W. Miller, [http://links.jstor.org/sici?sici=0022-4812%28197606%2941%3A2%3C439%3ANFACON%3E2.0.CO%3B2-E "Normal Functions and Constructive Ordinal Notations"] ,"The Journal of Symbolic Logic",volume 41,number 2,June 1976,pages 439 to 459.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Veblen good — In economics, Veblen goods are a theoretical group of commodities for which peoples preference for buying them increases as a direct function of their price, instead of decreasing according to the theory of supply and demand.It is claimed that… …   Wikipedia

  • Fonction de Veblen — En mathématiques, et plus précisément en théorie des ensembles, les fonctions de Veblen forment une suite de fonctions définies sur les ordinaux, introduite en 1908 par Oswald Veblen. Sommaire 1 Les fonctions de Veblen 2 La hiérarchie de Veblen …   Wikipédia en Français

  • Small Veblen ordinal — In mathematics, the small Veblen ordinal is a certain large countable ordinal, named after Oswald Veblen. It is occasionally called the Ackermann ordinal, though the Ackermann ordinal described by harvtxt|Ackermann|1951 is somewhat smaller than… …   Wikipedia

  • Large Veblen ordinal — In mathematics, the large Veblen ordinal is a certain large countable ordinal, named after Oswald Veblen. There is no standard notation for ordinals beyond the Feferman–Schütte ordinal Γ0. Most systems of notation use symbols such as psi;(α),… …   Wikipedia

  • Gamma function — For the gamma function of ordinals, see Veblen function. The gamma function along part of the real axis In mathematics, the gamma function (represented by the capital Greek letter Γ) is an extension of the factorial function, with its… …   Wikipedia

  • Ordinal collapsing function — In mathematical logic and set theory, an ordinal collapsing function (or projection function) is a technique for defining (notations for) certain recursive large countable ordinals, whose principle is to give names to certain ordinals much larger …   Wikipedia

  • Ordinal notation — In mathematical logic and set theory, an ordinal notation is a finite sequence of symbols from a finite alphabet which names an ordinal number according to some scheme which gives meaning to the language. There are many such schemes of ordinal… …   Wikipedia

  • Large countable ordinal — In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of… …   Wikipedia

  • Ackermann ordinal — In mathematics, the Ackermann ordinal is a certain large countable ordinal, named after Wilhelm Ackermann. The term Ackermann ordinal is also occasionally used for the small Veblen ordinal, a somewhat larger ordinal. Unfortunately there is no… …   Wikipedia

  • List of mathematics articles (V) — NOTOC Vac Vacuous truth Vague topology Valence of average numbers Valentin Vornicu Validity (statistics) Valuation (algebra) Valuation (logic) Valuation (mathematics) Valuation (measure theory) Valuation of options Valuation ring Valuative… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”