An ordinal notation is, generally, a method for systematically naming ordinals (usually countable ones). More specifically, it is a (primitive) recursive well-ordering on a recursive set of finite strings in a finite alphabet, although in practice the term is applied to more general cases than this. The primitive recursiveness is often loosened to be recursiveness, because it is known that the notion of a notation equipped with a recursive well-ordering is essentially equivalent to that of an ordinal notation. The well-ordering induces an injective function onto ordinals below the limit given as its ordinal type, and hence it actually names all ordinals below the limit.
On the other hand, a set \(T\) of finite strings in a finite alphabet equipped with a function \(o\) to ordinals is not derived from an ordinal notation unless the binary relation \(o(s) \in o(t)\) on \((s,t) \in T^2\) is verified to be (primitive) recursive and \(o\) is a bijection onto the least ordinal including th image if \(o\). Unfortunately, many googologists in this community confounded these distinct notions until p進大好きbot pointed out the common misconception,^{[1]} and hence there are many wrong descriptions in this wiki. Therefore we need to be very careful when they are talking about results on their own "ordinal notations".
Contents
Ordinal notation associated to iterated Cantor normal form
Cantor normal form (CNF) of basis \(\omega\) expresses an ordinal \(\alpha\) as a sum of a finite decreasing sequence of ordinals of the form \(\omega^\beta\). This allows us to correspond an ordinal \(\alpha\) below \(\varepsilon_0\) to a finite sequence of ordinals below \(\alpha\). By the well-foundedness of ordinals, the iteration of this correspondence gives a unique way to express an ordinal using \(0\), \(+\), and the exponentiation \(\alpha \mapsto \omega^{\alpha}\), which we call the "iterated Cantor normal form" (ICNF). It is known that the \(\in\)-relation can be encoded into a restriction of the lexicographic ordering to formal strings corresponding to ICNFs, which is a primitive recursive relation, and hence ICNF yields an ordinal notation whose order type is \(\varepsilon_0\). See Wainer hierarchy for fundamental sequences for ICNF.
Ordinal notation associated to Veblen's \(\varphi\)
Oswald Veblen's \(\varphi\) function is not only a portion of an early ordinal notation, but it could also be considered the first-ever array notation, preceding BEAF by more than 90 years.^{[2]} Due to the time when the paper was written, Veblen's definitions of the rules of his function are very cumbersome. Here, a conservative amount of modernization has been applied in the interest of brevity. Note that although Veblen used the dated convention where ordinals start with 1, we instead start ordinals with 0 and thus all letters (Greek or Latin) below are \(\geq 0\).
Before we can discuss the function itself, we first define a well-ordering \(\prec\) of arrays. An array is a function \(A : \eta \to \omega_1\) for some countable ordinal \(\eta\). Veblen denotes its arguments by using \(x_\alpha\) to indicate the value of \(A(\alpha)\), and, say, \(0_\alpha\) to indicate that \(A(\alpha) = 0\). We use \(\sup_\prec\) to denote a supremum under the ordering \(\prec\). It is very important to note that we are not defining ordinals, but an ordering of arrays.
- A. \(\varphi(0_0, 0_1, \ldots, 1_{\alpha + 1}) = \sup_\prec\{\varphi(0_0, 0_1, \ldots, x_\alpha): x \in \text{On}\}\).
- B. \(\varphi(0_0, 0_1, \ldots, 1_\alpha) = \sup_\prec\{\varphi(0_0, 0_1, \ldots, 1_\beta): \beta < \alpha\}\) where \(\alpha \in \text{Lim}\)
- C. \(\varphi((x + 1)_0, y_1, \ldots, z_\beta) \succ \varphi(x_0, \ldots, z_\beta)\), and there is no array between them
- D. \(\varphi(0_0, \ldots, (x + 1)_{\alpha + 1}, \ldots, y_\beta) = \sup_\prec\{\varphi(0_0, \ldots, (x + 1)_\alpha, x_{\alpha + 1}, \ldots, y_\beta)\}\)
- E. \(\varphi(0_0, \ldots, x_{\alpha + 1}, y_{\alpha + 2}, \ldots, z_\beta) = \sup_\prec\{\varphi(0_0, \ldots, w_{\alpha + 1}, y_{\alpha + 2}, \ldots, z_\beta) : w < x\}\) where \(x \in \text{Lim}\)
- F. \(\varphi(0_0, \ldots, (x + 1)_\alpha, \ldots, y_\beta) = \sup_\prec\{\varphi(0_0, \ldots, 1_\gamma, \ldots, x_\alpha, \ldots, y_\beta) : \gamma < \alpha\}\) where \(\alpha \in \text{Lim}\)
- G. \(\varphi(0_0, \ldots, x_\alpha, \ldots, y_\beta) = \sup_\prec\{\varphi(0_0, \ldots, z_\alpha, \ldots, y_\beta) : z < x\}\) where \(x, \alpha \in \text{Lim}\)
Now we can create an actual ordinal notation. Define \(\varphi(x)\) as a continuous (under the order topology) increasing function with \(\varphi(0) > 0\); conventionally this is chosen to be \(\varphi(\alpha) = \omega^\alpha\), although Veblen focused on the case \(\varphi(\alpha) = 1 + \alpha\). Then:
- \(\varphi(x_0, 0_1, \ldots, 1_\beta) = \) the \(x_0\)th element of the set \(\{y: \forall \gamma < \beta: \varphi(0_0, 0_1, \ldots, y_\gamma) = y\}\)
- for \(y > 1\), \(\varphi(x_0, 0_1, \ldots, y_\alpha, \ldots, z_\beta) = \) the \(x_0\)th element of the set \(\{v: \forall \gamma < \alpha: \forall w < y: \varphi(0_0, 0_1, \ldots, v_\gamma, 0_{\gamma+1}, \ldots, w_\alpha, z_{\alpha+1}, \ldots, z_\beta) = v\}\)
where "the \(x_0\)th element" is according to the ordering defined by the seven rules above.
The supremum of the range of Veblen's function is the large Veblen ordinal. If arrays are restricted to finite sizes (i.e. the domain of the array is \(< \omega\)), the supremum of the range is the small Veblen ordinal. The restriction of the Veblen's function to small Veblen ordinal gives an ordinal notation, because it is known that the ordering of formal strings corresponding to finite arrays of orginals restricted to a certain recursive subset of "normal forms" can be encoded into a primitive recursive relation.
Modern conventions
In practice, "Veblen \(\varphi\) function" typically refers to a far simpler two-argument form, defined as \(\varphi_0(\alpha) = \omega^\alpha\) (or some other normal function), and \(\varphi_\beta\) as the enumerating function for all the common fixed points of \(\varphi_\gamma\) for all \(\gamma < \beta\). More concisely, \(\varphi_\alpha\) is the \(\alpha\)'th derivative of \(\varphi_0\). The original is thus often called the "extended Veblen function."
Veblen's dated convention of starting ordinals at 1 is often corrected for in modern usage, so instead of, Veblen writing, say, \(\varphi(2, 1, 1)\), we would write \(\varphi(1, 0, 0)\); this modern convention is used in the above section. Using the zero-indexed version, we have the even simpler equality \(\varphi_\beta(\alpha) = \varphi(\alpha, \beta)\).
Caution
Since Veblen's \(\varphi\) is so complicated that many googologists do not understand the precise definition, there are several common mistakes. For example, \(\varphi(\omega,0)\) is often confounded with \(\Gamma_0\) although the latter one is strictly greater than the former one, and \(\varphi(\Gamma_0,\Gamma_0)\) is often confounded with \(\Gamma_0\) although the former one is strictly greater than the latter one.
Ordinal notation associated to ordinal collapsing function
- Main article: Ordinal collapsing function
There are many ordinal notations associated to ordinal collapsing functions. Be careful that an OCF itself can never be an ordinal notation. For more details, see the main article. Also note that some ordinal collapsing functions in the article, such as Madore's function, aren't currently known to admit an associated ordinal notation.
Taranovsky's C
- Main article: Taranovsky's C
Dmytro Taranovsky described in a self-published web page the following general frame work to construct a binary function \(C\) from a well-ordered set \((S,<)\) equipped with an additional structure \(D \subset S \times S\) satisfying a suitable condition explained later.^{[3]} Let \(0_S\) denote the least element of \((S,<)\). For an \(a \in S\), we put \(C_a := \{c \in S : (c,a) \in D\}\), \(a+1 := \min \{c \in S : a < c\}\) (assume the existence), and \((a) := \{c \in S : c < a\}\). For an \(S' \subset S\), we denote by \(\lim(S') \subset S\) the subset of limits of elements of \(S'\) in \((S,<)\). We say that \(D\) is a degree for \((S,<)\) if the following hold:
- \(C_{0_S} = S\)
- \(\forall a \in S: a \neq 0_S \Rightarrow 0_S \notin C_a\)
- \(\forall a \in \lim(S): C_a = \bigcup_{b < a} C_b\).
- \(\forall a \in S: C_{a+1} = \lim(C_a) \lor \exists d \in \lim(S) \cap (a+1) \land C_{a+1} = \lim(C_a) \cup (d+1)\)
If \(D\) is a degree for \((S,<)\), then set \(C(a,b) := \min\{c \in C_a : b < c\}\). In particular, this construction works for a limit ordinal \(\eta\) equipped with a degree \(D \subset \eta \times \eta\) for \((\eta,\in)\). Since \(D\) is not unique, the resulting function \(C\) heavily depends on the choice of \(D\). Taranovsky introduced several explicit examples of degrees.
Nonrecursive notations
The notations in this section are nonrecursive. Some authors do not consider them to be real ordinal notations.
Kleene's \(\mathcal{O}\)
See the article about Kleene's \(\mathcal{O}\).
Klev's notations
See the article about Klev's \(\mathcal{O}^+\) and \(\mathcal{O}^{++}\).
Table of conventions
Below is a table comparing the different conventions of ordinals and ordinal functions in this article and the article on ordinal collapsing functions. Note that ordinal collapsing functions in the table does not necessarily admit an ordinal notation.
Notation | Supremum of expressible countable ordinals |
---|---|
Cantor normal form | \(\varepsilon_0\) |
Veblen function (two arguments) | Feferman-Schütte ordinal \(\Gamma_0\) |
Veblen function (finitary) | Small Veblen ordinal |
Bird's \(\theta\) | Small Veblen ordinal |
Extended Veblen function (also called "Schutte Klammersymbolen") | Large Veblen ordinal |
Bachmann's \(\psi\) | Bachmann-Howard ordinal |
Madore's \(\psi\) | Bachmann-Howard ordinal |
Weiermann's \(\vartheta\) | Bachmann-Howard ordinal |
Feferman's \(\theta\) | Takeuti-Feferman-Buchholz ordinal |
Buchholz's \(\psi\) | Takeuti-Feferman-Buchholz ordinal |
Rathjen's \(\psi\) | > Rathjen's ordinal (proof-theoretic ordinal of KPM) |
Rathjen's \(\Psi\) | > proof-theoretic ordinal of KP+A certain Π_{3}-reflection schema |
Stegert's \(\Psi\) (first OCF) | \(\Psi^{\varepsilon_{\Xi+1} }_{(\omega^+;\mathsf P_0;\epsilon;\epsilon;0)}\)^{[4]} |
Stegert's \(\Psi\) (fifth OCF; note that three weaker OCFs are given as examples in the paper) | \(\Psi^{\varepsilon_{\Upsilon+1} }_{(\omega^+;\mathsf P_0;\epsilon;\epsilon;0)}\)^{[4]} |
Taranovsky's C | Unknown, but recursive and very large |
Kleene's \(\mathcal{O}\) | Church-Kleene ordinal \(\omega_1^\text{CK}\) |
Klev's \(\mathcal{O}^+\) | Supremum of writable ordinals \(\lambda\) |
Klev's \(\mathcal{O}^{++}\) | Supremum of eventually writable ordinals \(\zeta\) |
Sources
- ↑ p進大好きbot, Relation between an OCF and an Ordinal Notation, Googology Wiki user blog.
- ↑ Veblen, Oswald. "Continuous increasing functions of finite and transfinite ordinals". Retrieved 2014-10-11.
- ↑ Taranovsky, Dmytro. Ordinal Notation. Retrieved 2014-09-26.
- ↑ ^{4.0} ^{4.1} D. Madore, A Zoo of Ordinals (p.2)
See also
Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · ordinal notation · transfinite induction
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_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · gap ordinal · \(\lambda,\zeta,\Sigma,\gamma\) (ordinals on infinite time Turing machine) · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Madore's function · Feferman's theta function · Buchholz's function · Extended Buchholz's function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert'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: \(V\) · \(L\) · \(\textrm{On}\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)