Talk:Veblen function

Where is the definition?

I hope someone improves this article so that it defines the Veblen function. Right now it simply seems to state a bunch of properties of this function, without asserting that some set of properties characterizes it. John Baez (talk) 06:08, 4 November 2012 (UTC)

In the lead it gives the general definition, "If φ₀ is any normal function, then for any non-zero ordinal α, φ_α is the function enumerating the common fixed points of φ_β for β<α.". In the first section, it defines "Veblen hierarchy" by specifying that "In the special case when φ₀(α)=ω^α, this family of functions is known as the Veblen hierarchy.". JRSpriggs (talk) 10:15, 4 November 2012 (UTC)

Formal definitions

For background see: First-order predicate calculus, Zermelo-Frankel set theory with the axiom of choice, Ordinal number#Von Neumann definition of ordinals, and Ordinal arithmetic.

For the binary Veblen hierarchy, a formal definition using recursion on α and β is:

$\phi _{\alpha }(\beta )=\gamma \,\Leftrightarrow \,\operatorname {Ord} (\alpha )\land \operatorname {Ord} (\beta )\land \operatorname {Ord} (\gamma )\land 0<\gamma \land \forall \delta <\gamma (\delta +\delta <\gamma )\land \forall \delta <\alpha (\phi _{\delta }(\gamma )=\gamma )\land \forall \delta <\beta (\phi _{\alpha }(\delta )<\gamma )\land \lnot \exists \rho <\gamma \left(0<\rho \land \forall \delta <\rho (\delta +\delta <\rho )\land \forall \delta <\alpha (\phi _{\delta }(\rho )=\rho )\land \forall \delta <\beta (\phi _{\alpha }(\delta )<\rho )\right)$.

OK? JRSpriggs (talk) 23:13, 15 July 2022 (UTC)

Assuming the previous definition, the Γ function may be defined by:

$\Gamma _{\alpha }=\gamma \,\Leftrightarrow \,\operatorname {Ord} (\alpha )\land \phi _{\gamma }(0)=\gamma \land \forall \delta <\alpha (\Gamma _{\delta }<\gamma )\land \lnot \exists \rho <\gamma (\phi _{\rho }(0)=\rho \land \forall \delta <\alpha (\Gamma _{\delta }<\rho ))$.

OK? JRSpriggs (talk) 07:15, 3 August 2022 (UTC)

If Κ is an uncountable regular cardinal, then the finitary Veblen hierarchy on Κ maps Κ^ω to Κ according to:

$\phi (\mu )=\nu \,\Leftrightarrow \,\mu <\mathrm {K} ^{\omega }\land \nu <\mathrm {K} \land \exists \alpha <\omega \,\exists \sigma <\mathrm {K} ^{\omega }\,\exists \beta <\mathrm {K} \,\exists \gamma <\mathrm {K} (\mu =\mathrm {K} ^{\alpha +2}\cdot \sigma +\mathrm {K} ^{\alpha +1}\cdot \beta +\gamma \land (0<\beta \lor (\alpha =0\land \sigma =0\land \beta =0))\land$

$0<\nu \land \forall \delta <\nu (\delta +\delta <\nu )\land \forall \delta <\beta (\phi (\mathrm {K} ^{\alpha +2}\cdot \sigma +\mathrm {K} ^{\alpha +1}\cdot \delta +\mathrm {K} ^{\alpha }\cdot \nu )=\nu )\land \forall \delta <\gamma (\phi (\mathrm {K} ^{\alpha +2}\cdot \sigma +\mathrm {K} ^{\alpha +1}\cdot \beta +\delta )<\nu )\land$

$\lnot \exists \rho <\nu \left(0<\rho \land \forall \delta <\rho (\delta +\delta <\rho )\land \forall \delta <\beta (\phi (\mathrm {K} ^{\alpha +2}\cdot \sigma +\mathrm {K} ^{\alpha +1}\cdot \delta +\mathrm {K} ^{\alpha }\cdot \rho )=\rho )\land \forall \delta <\gamma (\phi (\mathrm {K} ^{\alpha +2}\cdot \sigma +\mathrm {K} ^{\alpha +1}\cdot \beta +\delta )<\rho )\right))$.

OK? JRSpriggs (talk) 13:02, 5 August 2022 (UTC)

If Κ is an uncountable regular cardinal, then the transfinitary Veblen hierarchy on Κ maps Κ^Κ to Κ according to:

$\phi (\mu )=\nu \,\Leftrightarrow \,\mu <\mathrm {K} ^{\mathrm {K} }\land \nu <\mathrm {K} \land \exists \alpha <\mathrm {K} \,\exists \sigma <\mathrm {K} ^{\mathrm {K} }\,\exists \beta <\mathrm {K} \,\exists \gamma <\mathrm {K} (\mu =\mathrm {K} ^{\alpha +1}\cdot \sigma +\mathrm {K} ^{\alpha }\cdot \beta +\gamma \land ((0<\alpha \land 0<\beta )\lor (\alpha =1\land \sigma =0\land \beta =0))\land$

$0<\nu \land \forall \delta <\nu (\delta +\delta <\nu )\land \forall \delta <\beta \,\forall \eta <\alpha (\phi (\mathrm {K} ^{\alpha +1}\cdot \sigma +\mathrm {K} ^{\alpha }\cdot \delta +\mathrm {K} ^{\eta }\cdot \nu )=\nu )\land \forall \delta <\gamma (\phi (\mathrm {K} ^{\alpha +1}\cdot \sigma +\mathrm {K} ^{\alpha }\cdot \beta +\delta )<\nu )\land$

$\lnot \exists \rho <\nu \left(0<\rho \land \forall \delta <\rho (\delta +\delta <\rho )\land \forall \delta <\beta \,\forall \eta <\alpha (\phi (\mathrm {K} ^{\alpha +1}\cdot \sigma +\mathrm {K} ^{\alpha }\cdot \delta +\mathrm {K} ^{\eta }\cdot \rho )=\rho )\land \forall \delta <\gamma (\phi (\mathrm {K} ^{\alpha +1}\cdot \sigma +\mathrm {K} ^{\alpha }\cdot \beta +\delta )<\rho )\right))$.

OK? JRSpriggs (talk) 21:34, 6 August 2022 (UTC)

The small Veblen ordinal (SVO) is φ(Κ^ω) and the large Veblen ordinal (LVO) is $\sup\{\phi (\mathrm {K} ^{\omega }),\phi (\mathrm {K} ^{\phi (\mathrm {K} ^{\omega })}),\phi (\mathrm {K} ^{\phi (\mathrm {K} ^{\phi (\mathrm {K} ^{\omega })})}),\ldots \}$. JRSpriggs (talk) 21:54, 6 August 2022 (UTC)

The Feferman–Schütte ordinal, Γ₀, is the smallest nonzero ordinal which is neither the sum of smaller ordinals nor a value of the binary Veblen hierarchy applied to smaller ordinals. It contains ω and all finite ordinals. It is also closed under: multiplication, exponentiation, and the function enumerating the epsilon-numbers. Other values of Γ_α are also closed under the same functions.

SVO = Γ_SVO has those closure properties and is also closed under the mapping by the finitary Veblen hierarchy of functions of finite support from ω to SVO (regarded as elements of Κ^ω) to Κ.

LVO = Γ_LVO has the above closure properties and is also closed under the mapping by the transfinitary Veblen hierarchy of functions of finite support from LVO to LVO (regarded as elements of Κ^Κ) to Κ.

OK? JRSpriggs (talk) 21:39, 9 August 2022 (UTC)

The definitions given above are recursive, that is, they use the thing being defined to help define it. This raises the possibility that they may be invalid. So for some time I looked for a way to prove that they are valid without success. Now, I think that ZFC may be too weak to provide such proofs. Nonetheless, I am confident that at least the binary Veblen hierarchy is OK. See reverse mathematics, ordinal analysis, and proof theoretic ordinals. JRSpriggs (talk) 19:02, 3 September 2022 (UTC)

I haven't read the formula in full, but for n+2-ary φ, recursion on the lexicographic ordering of Kⁿ⁺² where K is an uncountable regular cardinal looks like enough. Here n+2-ary φ is defined as usual and it's claimed that this construction is well-defined by recursion on the lexicographic ordering of Kⁿ⁺². Since each lex ordering on Kⁿ⁺² is an initial segment of the lex ordering for Kⁿ⁺³, the full K^<ω ordering should be enough for all of finitary φ with inputs <K. C7XWiki (talk) 18:54, 3 November 2022 (UTC)

What is an ω-sequence?

In the Fundamental sequences section it says:

The fundamental sequence for an ordinal with cofinality ω is a distinguished strictly increasing ω-sequence which has the ordinal as its limit.

But what is an ω-sequence? Joao003 (talk) 20:17, 2 November 2023 (UTC)

In many contexts, it would just be called a sequence. But in set theory (which is more general), you need to specify the domain and range more precisely. An ω-sequence is a function (mathematics) whose domain is ω and whose range is (usually, but not necessarily) a set of ordinals. JRSpriggs (talk) 03:34, 3 November 2023 (UTC)

Transfinitary Veblen function on the class of all Ordinals

See Veblen function#Transfinitely many variables. We can extend this to use functions (of finite support) from the class of all ordinals to itself as input. Such functions can be encoded by a set (rather than a proper class) as follows:

• the set is a finite (possibly empty) set of ordered pairs of ordinals;
• no ordinal appears more than once as the first member of such an ordered pair, i.e. the encoded function is single-valued;
• the ordinal in the second position in an ordered pair is never zero, i.e. a value of zero is indicated by the absence of an ordered pair;
• when using the set as a function, the input ordinal is compared to the first members of the ordered pairs, if it matches one, then the second member is returned as the value; otherwise the value is zero.

Notations in this system begin with the zero-ary function 0, and use the binary function addition + to combine powers of ω which come from applying the transfinite Veblen function φ 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.

Formal definitions are:

$s<t\iff s(\alpha )<t(\alpha ){\text{ where }}\alpha =\max\{0,\beta \vert s(\beta )\neq t(\beta )\}$;

$D_{\phi }(s)=\max\{0,\alpha ,\beta \vert \langle \alpha ,\beta \rangle \in s\}$;

$\phi (s)=\inf \,\{\gamma \,\vert \,D_{\phi }(s)\leq \gamma \land 0<\gamma \land \forall \delta <\gamma (\delta +\delta <\gamma )\land \forall t<s(D_{\phi }(t)<\gamma \implies \phi (t)<\gamma )\}$.