Googology Wiki
Advertisement
Googology Wiki

A normal form of an ordinal is a sort of an expression based on a predicate commonly written as \(=_{\textrm{NF}}\) depending on the context, which is used to uniquely express an ordinal by a fixed collection of constants and functions.[1][2][3]

Common misconceptions

Many googologists in this community confounded an ordinal and its expression, and hence frequently used ambiguous phrases like "An ordinal is in normal form" or "Every ordinal is normal form". Since being a normal form is a predicate on an expression (unlike the predicate including \(=_{\textrm{NF}} on ordinals\) including two or more ordinals rather than a single ordinal, such a phrase is meaningless.

Also, they often state that a normal form expression of an ordinal should not include an expression of ordinals which is not of normal form, but it is incorrect. Indeed, the predicate \(\varepsilon_0 =_{\textrm{NF}} \psi_0(1+\Omega)\) with respect to normal form in Buchholz's function is true, even though \(\varepsilon_0\) and \(1+\Omega\) are not expressed as normal forms. The confusion is perhaps partially due to the confusion of the use of a function symbol, as we will explain in #Example.


Notation

Given a set \(T\) of ordinals, a set \(FS\) of functions on ordinals in \(T\), and a subset \(CT \subset T\), we frequently define a family \(\textrm{NF}\) of predicates on ordinals in \(T\) expressed by a prefix-free notation by formal strings obtained as concatenations of elements in \(CT \cup FS\), parentheses (resp. braces, brackets), commas, and the symbol \(=_{\textrm{NF}}\) satisfying the following:

  1. The symbol \(=_{\textrm{NF}}\) occurs precisely once at an initial segment of the first separator. In particular, the first separator of a predicate in \(\textrm{NF}\) is of the form \(=_{\textrm{NF}} s_0\) for some formal string \(s_0\) given by concatenations of elements in \(CT \cup FS\), braces, and commas.
  2. For any predicate \(\alpha_0 =_{\textrm{NF}} s_0 \alpha_1 s_1 \cdots \alpha_n s_n\) in \(\textrm{NF}\) on ordinals \(\alpha_0,\alpha_1,\ldots,\alpha_n\) in \(T\) with a positive integer \(n\), \(s_0 \alpha_1 s_1 \cdots \alpha_n s_n\) is a well-formed expression in the sense that it is a term in the language \(CT \cup FS\) of first order logic, and its canonical interpretation coincides with \(\alpha_0\).
  3. For any ordinal \(\alpha\) in \(T\), there is precisely one tuple of ordinals \(\beta_1,\ldots,\beta_n\) in \(T\) with a positive integer \(n\) and a predicate \(\alpha_0 =_{\textrm{NF}} s_0 \alpha_1 s_1 \cdots \alpha s_n\) in \(\textrm{NF}\) on ordinals \(\alpha_0,\alpha_1,\ldots,\alpha_n\) in \(T\) such that \(\alpha =_{\textrm{NF}} s_0 \beta_1 s_1 \cdots \beta_n s_n\). We call the unique formal string \(s_0 \beta_1 s_1 \cdots \beta_n s_n\) the normal form expression of \(\alpha\).

In this way, the notion of a normal form heavily depends on \(T\), \(FS\), and \(CT\), which also depend on the context. Therefore insisting that a given expression is of normal form is meaningless unless we specify a definition of normal form in the context.


Example

Here, we explain basic examples of normal form.

Cantor normal form

We put \(T := \varepsilon_0\), and regard it as a set of ordinals as usual. We denote by \(FS\) the set of the addition \(+ \colon T^2 \to T\) and the omega power \(\omega^{\bullet} \colon T \to T\), and by \(CT\) the singleton of the constant \(0\).

We define a set \(\textrm{NF}\) of predicates on ordinals in \(T\) using formal strings in \(CT \cup FS\) in the following way:

  1. The predicate \(\alpha_0 =_{\textrm{NF}} 0\) on an ordinal \(\alpha_0\) in \(T\) defined as \(\alpha_0 = 0\) belongs to \(\textrm{NF}\).
  2. The predicate \(\alpha_0 =_{\textrm{NF}} \omega^{\alpha_1}\) (or formally \(\alpha_0 =_{\textrm{NF}} \omega \wedge \{ \alpha_1 \}\) if we avoid superscripts) on ordinals \(\alpha_0, \alpha_1\) in \(T\) defined as \(\alpha_0 = \omega^{\alpha_1}\) belongs to \(\textrm{NF}\).
  3. The predicate \(\alpha_0 =_{\textrm{NF}} \omega^{\alpha_1} + \cdots + \omega^{\alpha_n}\) (or formally \(\alpha_0 =_{\textrm{NF}} \omega \wedge \{ \alpha_1 \} + \cdots + \omega \wedge \{ \alpha_n \}\) if we avoid superscripts) on ordinals \(\alpha_0, \ldots, \alpha_n\) in \(T\) with an integer \(n > 1\) defined as \(\alpha_0 = \omega^{\alpha_1} + \cdots \omega^{\alpha_n}\) and \(\alpha_1 \geq \cdots \geq \alpha_n\) belongs to \(\textrm{NF}\).

Then the resulting set \(\textrm{NF}\) gives the definition of Cantor normal form of basis \(\omega\), which is one of the most famous formulations of normal form.

It is a little confising whether an occurrence of a function in \(FS\) is used as a function or a part of a separator. For example, let us consider the formula \(\omega^{\omega} =_{\textrm{NF}} \omega^{1 + \omega}\). It is a valid formula, which is true by \(\omega^{\omega} = \omega^{1 + \omega}\). We do not have to rewrite the formula as \(\omega^{\omega^{\omega^0}} =_{\textrm{NF}} \omega^{\omega^{\omega^0}}\) so that the "expressions" in both side should be "of normal form", as the definition of \(\textrm{NF}\) does not require how to express arguments of predicates. The double-quoted "expression" is a meta theoretic reference to an expression, and hence is irrelevant to the actual expression formalised in terms of formal strings introduced in this article. Although it might be confusing for readers who do not precisely understand the difference of an ordinal and its expression, a predicate on ordinals cannot require any restriction on "expressions" of arguments, even if the predicate eventually provides a way to define a canonical expression of an ordinal.

Instead, we can define a predicate using a notion of "iterated normal form", although the precise definition will be a little complicated. For example, there are many wrong (intuition-based) explanations of iterated Cantor normal form under confusion of an ordinal and its expression. See the main article on the ordinal notation for more details.

See also Wainer hierarchy for the application of Cantor normal form.

Normal form for Buchholz's function

Main article: Buchholz's function#Normal form

We put \(T := C_0(\varepsilon_{\Omega_{\omega}+1})\) using the \(C\) function in Buchholz's function. We denote by \(FS\) the set of the addition \(+ \colon T^2 \to T\) and Buchholz's \(\psi\) functions \(\psi_k \colon T \to T\) indexed by \(k \in \omega+1\), and by \(CT\) the singleton of the constant \(0\).

We define a set \(\textrm{NF}\) of predicates on ordinals in \(T\) using formal strings in \(CT \cup FS\) in the following way:

  1. The predicate \(\alpha =_{\textrm{NF}} 0\) on an ordinal \(\alpha\) in \(T\) defined as \(\alpha = 0\) belongs to \(\textrm{NF}\).
  2. The predicate \(\alpha_0 =_{\textrm{NF}} \psi_{k_1}(\alpha_1)\) on ordinals \(\alpha_0, \alpha_1\) in \(T\) with \(k_1 \in \omega+1\) defined as \(\alpha_0 = \psi_{k_1}(\alpha_1)\) and \(\alpha_1 \in C_{k_1}(\alpha_1)\) belongs to \(\textrm{NF}\).
  3. The predicate \(\alpha_0 =_{\textrm{NF}} \psi_{k_1}(\alpha_1) + \cdots + \psi_{k_n}(\alpha_n)\) on ordinals \(\alpha_0, \ldots, \alpha_n\) in \(T\) with an integer \(n > 1\) and \(k_1,\ldots,k_n \in \omega+1\) defined as \(\alpha_0 = \psi_{k_1}(\alpha_1) + \cdots + \psi_{k_n}(\alpha_n)\), \(\psi_{k_1}(\alpha_1) \geq \cdots \geq \psi_{k_n}(\alpha_n)\), and \(\alpha_1 \in C_{k_1}(\alpha_1), \ldots, \alpha_n \in C_{k_n}(\alpha_n)\) belongs to \(\textrm{NF}\).

For example, \(\psi_0(\varepsilon_1) =_{\textrm{NF}} \psi_0(1+\Omega)\) is a valid formula, which is true.

We note that a way to define the notion of normal form is not unique. For example, it is also possible to directly define a non-equivalent normal form as the pull-back of the structure of the ordinal notation associated to Buchholz's function. See #Standard form and the main article for more details.

Normal form for Extended Buchholz's function

Main article: Extended Buchholz's function#Normal form

We put \(T := C_0(\Phi_1(0))\) using the \(C\) function in Extended Buchholz's function and the least omega fixed point \(\Phi_1(0)\). We denote by \(FS\) the set of the addition \(+ \colon T^2 \to T\) and Extended Buchholz's \(\psi\) function \(\psi \colon T^2 \to T\), and by \(CT\) the singleton of the constant \(0\).

We define a set \(\textrm{NF}\) of predicates on ordinals in \(T\) using formal strings in \(CT \cup FS\) in the following way:

  1. The predicate \(\alpha =_{\textrm{NF}} 0\) on an ordinal \(\alpha\) in \(T\) defined as \(\alpha = 0\) belongs to \(\textrm{NF}\).
  2. The predicate \(\alpha_0 =_{\textrm{NF}} \psi_{\nu_1}(\alpha_1)\) on ordinals \(\alpha_0, \alpha_1, \nu_1\) in \(T\) defined as \(\alpha_0 = \psi_{\nu_1}(\alpha_1)\) and \(\alpha_1 \in C_{\nu_1}(\alpha_1)\) belongs to \(\textrm{NF}\).
  3. The predicate \(\alpha_0 =_{\textrm{NF}} \psi_{\nu_1}(\alpha_1) + \cdots + \psi_{\nu_k}(\alpha_k)\) on ordinals \(\alpha_0, \ldots, \alpha_k, \nu_1, \ldots, \nu_k\) in \(T\) with an integer \(k > 1\) defined as \(\alpha_0 = \psi_{\nu_1}(\alpha_1) + \cdots + \psi_{\nu_n}(\alpha_n)\), \(\psi_{\nu_1}(\alpha_1) \geq \cdots \geq \psi_{\nu_k}(\alpha_k)\), and \(\alpha_1 \in C_{\nu_1}(\alpha_1), \ldots, \alpha_k \in C_{\nu_k}(\alpha_k)\) belongs to \(\textrm{NF}\).

By the definition, it is an extension of the normal form for Buchholz's function explained above.


Applications

Normal form gives a unique way to express an ordinal, and hence is helpful to defined an ordinal notation associated to an ordinal collapsing function and a recursive system of fundamental sequences.


Standard form

An analogous notion called standard form is frequently introduced in googology. For a recursive notation \(T\), the subset of terms of standard form is denoted by \(OT\). Usually, it is expected that \(OT\) is well-founded, and hence the restriction of the recursive function associated to \(T\) to the subsystem given by \(OT\) is a total computable function, which can generate a computable large number.

In particular, when \(T\) is a notation system associated to an ordinal collapsing function, the notion of standard form is expected to precisely correspond to that of normal form through the canonical interpretation. In this case, the well-foundedness of ordinals actually ensure the well-foundedness of \(OT\). For example, the definition of normal form for Buchholz's function associated to standard form for the ordinal notation associated to it[4] is described in the article of Buchholz's function.

One typical way to define standard form for a given recursive notation \(T\) equipped with a recursive system of expansion rules is to define it as the set of all terms which can be obtained by repetition of applications of expansion rules to terms appearing in the definition of a limit function.


See also

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation
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 · \(\lambda,\zeta,\Sigma,\gamma\) (ordinals on infinite time Turing machine) · gap ordinal · 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 · Bachmann's function · Madore's function · Feferman's theta function · 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
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)

Sources

  1. M. Jäger, "ρ-inaccessible ordinals, collapsing functions and a recursive notation system", Archiv für mathematische Logik und Grundlagenforschung, volume 24 (1984), pp. 49--62.
  2. W. Buchholz, A simplified version of local predicativity, Proof Theory : A Selection of Papers from the Leeds Proof Theory Programme 1990 (1992), pp. 115--147.
  3. Rathjen, Michael. Ordinal Notations Based on a Weakly Mahlo Cardinal, Archive for Mathematical Logic 29 (1990) 249--263.
  4. W. Buchholz, A New System of Proof-Theoretic Ordinal Functions, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 195--207.
Advertisement