Veblen hierarchy: Difference between revisions
RhubarbJayde (talk | contribs) No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
The Veblen hierarchy is a sequence of ordinal-indexed functions \( \varphi_\alpha: \mathrm{Ord} \to \mathrm{Ord} \) which extend [[Cantor normal form]] by beginning with the base function \( \alpha \mapsto \omega^\alpha \) and iteratively taking fixed points at each next step. Formally, letting \( \mathrm{AP} := \{\omega^\alpha: \alpha \in \mathrm{Ord}\} \), we can define \( \varphi_\alpha(\beta) := \min\{\zeta \in \mathrm{AP}: \forall \gamma ((\gamma < \alpha \rightarrow \varphi_\gamma(\zeta) = \zeta) \land (\gamma < \beta \rightarrow \varphi_\alpha(\gamma) < \zeta))\} \). This is a definition by transfinite recursion, and is well-defined by the transfinite recursion theorem. Analogously to [[Cantor normal form]], every ordinal can be written in its Veblen normal form, as a sum \( \varphi_{\alpha_1}(\beta_1) + \varphi_{\alpha_2}(\beta_2) + \cdots + \varphi_{\alpha_n}(\beta_n) \). Like how the limit of hereditary CNF is \( \varepsilon_0 = \varphi_1(0) \), the limit of hereditary of hereditary VNF is known as \( \Gamma_0 \), aka the Feferman-Schütte ordinal. It is equal to a moderately powerful system of second-order arithmetic, containing a second-order analogue of Peano arithmetic known as arithmetical comprehension, with an additional axiom that allows one to do transfinite recursions. As such it has been described as the least truly impredicative ordinal - the least ordinal which truly can not described from below and any definition must involve some form of self-reference. However, this description has been challenged on multiple occassions. |
The Veblen hierarchy is a sequence of ordinal-indexed functions \( \varphi_\alpha: \mathrm{Ord} \to \mathrm{Ord} \) which extend [[Cantor normal form]] by beginning with the base function \( \alpha \mapsto \omega^\alpha \) and iteratively taking fixed points at each next step. Formally, letting \( \mathrm{AP} := \{\omega^\alpha: \alpha \in \mathrm{Ord}\} \), we can define \( \varphi_\alpha(\beta) := \min\{\zeta \in \mathrm{AP}: \forall \gamma ((\gamma < \alpha \rightarrow \varphi_\gamma(\zeta) = \zeta) \land (\gamma < \beta \rightarrow \varphi_\alpha(\gamma) < \zeta))\} \). This is a definition by transfinite recursion, and is well-defined by the transfinite recursion theorem. Analogously to [[Cantor normal form]], every ordinal can be written in its Veblen normal form, as a sum \( \varphi_{\alpha_1}(\beta_1) + \varphi_{\alpha_2}(\beta_2) + \cdots + \varphi_{\alpha_n}(\beta_n) \). Like how the limit of hereditary CNF is \( \varepsilon_0 = \varphi_1(0) \), the limit of hereditary of hereditary VNF is known as \( \Gamma_0 \), aka the Feferman-Schütte ordinal. It is equal to a moderately powerful system of second-order arithmetic, containing a second-order analogue of Peano arithmetic known as arithmetical comprehension, with an additional axiom that allows one to do transfinite recursions. As such it has been described as the least truly impredicative ordinal - the least ordinal which truly can not described from below and any definition must involve some form of self-reference. However, this description has been challenged on multiple occassions. |
||
Ordinals beyond \( \Gamma_0 \) can be written using an extension of the Veblen hierarchy. This extension takes the form of \(\varphi(...,\alpha_3,\alpha_2,\alpha_1,\alpha_0)\) for finite amounts of entries. This reaches the [[Small Veblen ordinal]], and can be extended, through transfinite amounts of entries, to the [[Large Veblen ordinal]], and through "rows" and "planes" of entries to reach the [[Bachmann-Howard ordinal]]. |
|||
Ordinals beyond \( \Gamma_0 \) can either be written using a variadic extension of the Veblen hierarchy (which can also be used to define the [[Small Veblen ordinal|SVO]] and [[Large Veblen ordinal|LVO]]), or using ordinal collapsing functions. Ordinals unreachable from below via Veblen normal form, the first of which is \( \Gamma_0 \), are typically known as gamma numbers or strongly critical ordinals. They are important in ordinal analysis due to the involvement of the Veblen function in cut-elimination. The enumeration function of the strongly critical ordinals is typically denoted \( \alpha \mapsto \Gamma_\alpha \), analogously to [[Epsilon numbers|\( \alpha \mapsto \varepsilon_\alpha \)]] or [[Epsilon numbers|\( \alpha \mapsto \zeta_\alpha \)]]. |
|||
The first stage of the Veblen hierarchy is just the function \( \alpha \mapsto \omega^\alpha \). Then the next stage, \( \varphi_1(\beta) \) (alternatively written \( \varphi(1,\beta) \)) enumerates the fixed points of the first stage - these are just the [[epsilon numbers]]. This continues to the zeta numbers, followed by the eta numbers, although this convention is rare. At the \( \omega \)th stage, since \( \omega - 1 \) doesn't exist, instead \( \varphi(\omega,\beta) \) enumerates the ordinals that are simultaneous fixed points of \( \alpha \mapsto \varphi(n,\beta) \) for all \( n < \omega \). |
|||
Revision as of 20:47, 30 August 2023
The Veblen hierarchy is a sequence of ordinal-indexed functions \( \varphi_\alpha: \mathrm{Ord} \to \mathrm{Ord} \) which extend Cantor normal form by beginning with the base function \( \alpha \mapsto \omega^\alpha \) and iteratively taking fixed points at each next step. Formally, letting \( \mathrm{AP} := \{\omega^\alpha: \alpha \in \mathrm{Ord}\} \), we can define \( \varphi_\alpha(\beta) := \min\{\zeta \in \mathrm{AP}: \forall \gamma ((\gamma < \alpha \rightarrow \varphi_\gamma(\zeta) = \zeta) \land (\gamma < \beta \rightarrow \varphi_\alpha(\gamma) < \zeta))\} \). This is a definition by transfinite recursion, and is well-defined by the transfinite recursion theorem. Analogously to Cantor normal form, every ordinal can be written in its Veblen normal form, as a sum \( \varphi_{\alpha_1}(\beta_1) + \varphi_{\alpha_2}(\beta_2) + \cdots + \varphi_{\alpha_n}(\beta_n) \). Like how the limit of hereditary CNF is \( \varepsilon_0 = \varphi_1(0) \), the limit of hereditary of hereditary VNF is known as \( \Gamma_0 \), aka the Feferman-Schütte ordinal. It is equal to a moderately powerful system of second-order arithmetic, containing a second-order analogue of Peano arithmetic known as arithmetical comprehension, with an additional axiom that allows one to do transfinite recursions. As such it has been described as the least truly impredicative ordinal - the least ordinal which truly can not described from below and any definition must involve some form of self-reference. However, this description has been challenged on multiple occassions.
Ordinals beyond \( \Gamma_0 \) can be written using an extension of the Veblen hierarchy. This extension takes the form of \(\varphi(...,\alpha_3,\alpha_2,\alpha_1,\alpha_0)\) for finite amounts of entries. This reaches the Small Veblen ordinal, and can be extended, through transfinite amounts of entries, to the Large Veblen ordinal, and through "rows" and "planes" of entries to reach the Bachmann-Howard ordinal.