- Not to be confused with ε function.
\(\varepsilon_0\) (pronounced "epsilon-zero", "epsilon-null" or "epsilon-nought") is a small countable ordinal, defined as the first fixed point of the function \(\alpha \mapsto \omega^\alpha\)[1].
Properties[]
The ordinal \(\varepsilon_0\) has several properties:
- Smallest ordinal not expressible in Cantor normal form using strictly smaller exponents. Equivalently, this is the least nonzero ordinal that is closed under addition and \(\lambda\alpha.\omega^\alpha\).
- In fact, \(\varepsilon_0\) is also the least nonzero ordinal closed under only \(\lambda\alpha.\omega^\alpha\).
- The proof-theoretic ordinal of Peano arithmetic and ACA0 (arithmetical comprehension, a subsystem of second-order arithmetic).[2]
- Informal visualizations: \(^\omega\omega\), \(\omega^{\omega^{\omega^\cdots}}\) or \(\omega \uparrow\uparrow \omega\)
- The second fixed point of \(x\mapsto2^x\).
- \(\varphi(1,0)\) using the Veblen function
- \(\psi_0(\Omega)\) using Buchholz's function
- \(\psi(0)\) using Madore's function
Appearance in googology[]
Using the Wainer hierarchy:
- \(f_{\varepsilon_0}(n) \approx X \uparrow\uparrow X\ \&\ n\) (fast-growing hierarchy)
- \(H_{\varepsilon_0}(n) \approx X \uparrow\uparrow X\ \&\ n\) (Hardy hierarchy)
- \(g_{\varepsilon_0}(n) = n \uparrow\uparrow n = n \uparrow\uparrow\uparrow 2\) (slow-growing hierarchy)
\(f_{\varepsilon_0}(n)\) with respect to the Wainer hierarchy is comparable to the Goodstein function, Beklevmishev's worm function \(\textrm{Worm}(n)\), and its variants.
Higher epsilon numbers and the Veblen hierarchy[]
The function \(\alpha \mapsto \varepsilon_\alpha\) enumerates the fixed points of the exponential map \(\alpha \mapsto \omega^\alpha\). Thus \(\varepsilon_1\) is the next fixed point of the exponential map after \(\varepsilon_0\). Formally:
- \(\varepsilon_0=\text{min}\{\alpha|\alpha=\omega^\alpha\}=\text{sup}\{0,1,\omega, \omega^\omega, \omega^{\omega^\omega},...\}\)
- \(\varepsilon_{\alpha+1}=\text{min}\{\beta|\beta=\omega^\beta\wedge\beta>\varepsilon_\alpha\}=\text{sup}\{\varepsilon_\alpha+1,\omega^{\varepsilon_\alpha+1}, \omega^{\omega^{\varepsilon_\alpha+1}},...\}\)
- \(\varepsilon_{\alpha}=\text{sup}\{\varepsilon_{\beta}|\beta<\alpha\}\) if \(\alpha\) is a limit ordinal.
This definition gives the following fundamental sequences for non-zero limit ordinals smaller than \(\zeta_0\) explained later:
- If \(\alpha=\beta_1+\cdots+\beta_{k-1}+\beta_k\), where \(k\) is a natural number greater than \(1\) and \(\beta_1,\ldots,\beta_{k-1},\beta_k\) are additive principal ordinals greater than \(1\) satisfying \(\beta_1 \geq \cdots \geq \beta_{k-1} \geq \beta_k\), then \(\alpha[n]=\beta_1+\cdots+\beta_{k-1}+(\beta_k[n])\)
- If \(\alpha=\omega^{\beta+1}\), then \(\alpha[n]=\omega^{\beta} \times n\)
- If \(\alpha=\omega^{\beta}\) and \(\beta\) is a non-zero limit ordinal which is not an epsilon number, then \(\alpha[n]=\omega^{\beta[n]}\)
- if \(\alpha=\varepsilon_0\), then \(\alpha[0]=0\) and \(\alpha[n+1]=\omega^{\alpha[n]}\)
- if \(\alpha=\varepsilon_{\beta+1}\), then \(\alpha[0]=\varepsilon_\beta+1\) and \(\alpha[n+1]=\omega^{\alpha[n]}\)
- if \(\alpha=\varepsilon_{\beta}\) and \(\beta\) is a non-zero limit ordinal, then \(\alpha[n]=\varepsilon_{\beta[n]}\)
The first fixed point of \(\alpha \mapsto \varepsilon_\alpha\) is called \(\zeta_0\) (zeta-zero) or Cantor's ordinal, and \(\zeta_\alpha\) enumerates the fixed points of \(\alpha \mapsto \varepsilon_\alpha\).
Since we do not have an infinite number of Greek letters, we generalize this using a series of functions that form the Veblen hierarchy. Each function enumerates the fixed points of the previous one. Formally:
- \(\varphi_0(\alpha) = \omega^\alpha\)
- \(\varphi_\beta(\alpha)\) is the \((1+\alpha)\)th fixed point of \(\varphi_\gamma\) for all \(\gamma < \beta\)
The first ordinal inaccessible through this two-argument Veblen hierarchy is the Feferman–Schütte ordinal.
Sources[]
- ↑ D. Madore, A Zoo of Ordinals (p.1). Accessed 2021-05-30.
- ↑ W. Pohlers, Proof theory: The first step into impredicativity, Springer, 2009.
See also[]
Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation · Absolute infinity
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function) · \(\omega_1^\mathfrak{Ch}\) (Omega one of chess) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\gamma,\zeta,\Sigma\) (Infinite time Turing machine ordinals) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Hardy hierarchy · Slow-growing hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Weak Buchholz's function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Weak Buchholz's function · Extended Buchholz's function · Jäger-Buchholz function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function · Arai's psi function
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal
Classes: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)