\(\omega\) (pronounced "omega") is the first transfinite ordinal, the smallest ordinal greater than all the positive integers. In the von Neumann definition of ordinals, it is equal to the set of nonnegative integers \(\mathbb{N}\).
In the Wainer hierarchy, the fundamental sequence of \(\omega\) is \(0,1,2,\ldots\). Using this hierarchy, the following holds:
- \(f_\omega(n) \approx 2 \uparrow^{n-1} n\) (fast-growing hierarchy) is on par with Ackermann function and weak Goodstein function. It is the first function in FGH that is not primitive-recursive.
- \(H_\omega(n) = 2n\) (Hardy hierarchy), the first function in Hardy hierarchy which is not a translation.
- \(g_\omega(n) = n\) (slow-growing hierarchy), the first function in SGH which is not constant.
However, if we are not working in the Wainer hierarchy, \(f_\omega\) may be arbitrarily fast-growing. For example, letting \(\omega[n] = \Sigma(n)\) (where \(\Sigma(n)\) is a busy beaver function) makes \(f_\omega\) uncomputable.
In fact, there are as many fundamental sequences for \(\omega\) (and for any other countable ordinal), as the number of monotonically increasing \(\mathbb{N} \to \mathbb{N}\) functions, i.e. continuum \(\mathfrak c\) of them.
\(\omega\) is the first admissible ordinal. It is also the first transfinite regular ordinal.
External links[]
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)