\(\omega_1\) (also commonly denoted \(\Omega\)), called omega-one or the first uncountable ordinal, is the smallest uncountable ordinal. It has several equivalent definitions:
- Call an ordinal \(\alpha\) countable if there exists an injective map from \(\alpha\) to the set \(\mathbb{N}\) of natural numbers. \(\omega_1\) is the smallest ordinal that is not countable.
- \(\omega_1\) is the second smallest infinite ordinal whose cofinality is equal to itself. Note that there are ordinals beyond \(\omega_1\) that do have a cofinality of \(\omega\), e.g. \(\omega_1 \times \omega\) and \(\omega_\omega\).
- \(\omega_1\) is the supremum of all ordinals that can be mapped one-to-one onto the natural numbers.
- \(\omega_1\) is the set of all countable ordinals. As every ordinal, it is the set of all ordinals less than it.
- \(\omega_1\) is the smallest ordinal with a cardinality greater than \(\omega\): \(|\omega_1| = \aleph_1 > \aleph_0 = |\omega|\).
Note that \(\omega_n\) with \(n\in\mathbb N\) is also sometimes used to denote the power-tower \(\omega\uparrow\uparrow n\) of the ordinal \(\omega\)[1][2], or to denote the Church-Kleene ordinal[3].
The first uncountable ordinal is used in ordinal collapsing functions because 1) it is by default larger than any ordinal constructible in these notations, 2) we can conveniently use the word "countable." In such contexts it is usually denoted with a capital omega \(\Omega\), as in \(\psi(\Omega^\Omega)\).[4]
Fast-growing hierarchy[]
A common mistake in googology is to consider \(f_{\omega_1}\) without giving any reasonable formulation. The uncountable ordinal \(\omega_1\) has no fundamental sequence with length \(\omega\) and thus marks the limit of the fast-growing hierarchy and its relatives. Any fundamental sequence of countable ordinals is limited by a countable ordinal. Thus, \(f_{\omega_1}(n)\) is ill-defined according to three rules of FGH.
However, one might expect to artifically define \(f_{\omega_1}(n)\) as some function irrelevant to FGH and fundamental sequences that eventually dominates any \(f_\alpha(n)\) for \(\alpha < \omega_1\) if we fix some well-defined system of fundamental sequences assigned to all countable ordinals. Unfortunately, such systems cannot be created if we use ordinal notations with finite strings of finite alphabet as they can refer only to countably many ordinals. Moreover, the statement "for any system of fundamental sequences for all countable ordinals, there exists a function \(f_{\omega_1}(n)\) which dominates any \(f_\alpha(n)\) for \(\alpha < \omega_1\)" is known to be unprovable under ZFC as long as it is consistent, because \(f_{\omega}\) outgrows such an \(f_{\omega_1}\) with respect to a specific fundamental sequence for \(\omega\) defined by using \(f_{\omega_1}\) itself.
If we made \(f_{\omega_1}(n)\) well-defined in some way, then it would be possible to intuitively continue the hierarchy and define \(f_{\omega_1+1}(n) = f_{\omega_1}^n(n)\), \(f_{\omega_1+2}(n) = f_{\omega_1+1}^n(n)\), \(f_{\omega_1+\omega}(n) = f_{\omega_1+\omega[n]}(n)\), and generally \(f_{\omega_1+\alpha}(n) = f_{\omega_1+\alpha[n]}(n)\) for countables \(\alpha\) as long as we fix a well-defined system of fundamental sequences for all countable limit ordinals. Then we might define a function for \(f_{\omega_1 \times 2}(n)\) to be some function that eventually dominates \(f_{\omega_1+\alpha}(n)\) for countable ordinals \(\alpha\), but there is no canonical way to do so, as there is no canonical way to define \(f_{\omega_1}\) outgrowing \(f_{\alpha}\) for all countable ordinals \(\alpha\).
Cardinality[]
The continuum hypothesis states that \(\omega_1\) has the same cardinality as the real numbers; that is, the countable ordinals can be mapped one-to-one onto the real numbers. The continuum hypothesis was shown to be independent of ZFC as long as it is consistent, which means it cannot be proven or disproven.
The least ordinal with next cardinality after \(\omega_1\), which is denoted by \(\omega_2\), is called the second uncountable regular ordinal, and \(|\omega_2| = \aleph_2\) is called the second uncountable cardinal, not to be confused with the second uncountable ordinal \(\omega_1+1\).
Sources[]
- ↑ W. Carnielli, M. Rathjen, Hydrae and Subsystems of Arithmetic (p.1). Accessed 2021-06-16.
- ↑ I. Lepper, G. Moser, Why ordinals are good for you (p.19). Accessed 2021-06-16.
- ↑ W. Richter, P. Aczel, Inductive Definitions and Reflecting Properties of Admissible Ordinals (pp.1-2). Accessed 2021-06-17.
- ↑ D. Madore, A Zoo of Ordinals (p.2). Accessed 2021-06-02.
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)