Normal form

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.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.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.Rathjen, Michael. Ordinal Notations Based on a Weakly Mahlo Cardinal, Archive for Mathematical Logic 29 (1990) 249--263.
== 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), so this 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:
# 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.
# 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\).
# 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:
# The predicate \(\alpha_0 =_{\textrm{NF}} 0\) on an ordinal \(\alpha_0\) in \(T\) defined as \(\alpha_0 = 0\) belongs to \(\textrm{NF}\).
# 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}\).
# 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 confusing 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.
The normality of an expression in standard formulations can be described in a recursive way with respect to the ordinal notation system explained above. For example, a Japanese Googology Wiki user Okkuu implemented Cantor normal form into C++ (cf. #External Links).
See also Wainer hierarchy for the application of Cantor normal form in googology.
=== Normal form for Weak Buchholz's function ===
Since normal form for Weak Buchholz's function is given by the restriction of that for Extended Weak Buchholz's function, see #Normal form for Extended Weak Buchholz's function.
=== Normal form for Buchholz's function ===
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:
# The predicate \(\alpha =_{\textrm{NF}} 0\) on an ordinal \(\alpha\) in \(T\) defined as \(\alpha = 0\) belongs to \(\textrm{NF}\).
# 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}\).
# 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.
At least, the normality of an expression in standard formulations can be described in a recursive way with respect to the corresponding ordinal notation system defined by Buchholz, by the definition of normal form using standard form (cf. Buchholz's function#Ordinal notation).
=== Normal form for Extended Weak Buchholz's function ===
We put \(T := C_0(\Phi_1(0))\) using the \(C\) function in Extended Weak 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 Weak 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:
the set \(\textrm{NF}\) of predicates on ordinals in \(C_0(\Lambda)\) is intended to be defined in the following way:
# The predicate \(\alpha =_{\textrm{NF}} 0\) on an ordinal \(\alpha\) in \(C_0(\Lambda)\) defined as \(\alpha = 0\) belongs to \(\textrm{NF}\).
# The predicate \(\alpha_0 =_{\textrm{NF}} \psi_{\nu_1}(\alpha_1)\) on ordinals \(\alpha_0, \alpha_1, \nu_1\) in \(C_0(\Lambda)\) defined as \(\alpha_0 = \psi_{\nu_1}(\alpha_1)\) and \(\alpha_1 \in C_{\nu_1}(\alpha_1)\) belongs to \(\textrm{NF}\).
Moreover, the normality of an expression can be described in a recursive way with respect to the corresponding ordinal notation system defined by p進大好きbot, by the definition of normal form using standard form (cf. Extended Weak Buchholz's function#Ordinal notation).
=== Normal form for Extended Buchholz's function ===
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:
# The predicate \(\alpha =_{\textrm{NF}} 0\) on an ordinal \(\alpha\) in \(T\) defined as \(\alpha = 0\) belongs to \(\textrm{NF}\).
# 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}\).
# 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.
Moreover, the normality of an expression can be described in a recursive way with respect to the corresponding ordinal notation system defined by p進大好きbot, by the definition of normal form using standard form (cf. Extended Buchholz's function#Ordinal notation).
=== Normal form for Jäger-Buchholz function ===
Since the definition is complicated, see :ja:イェーガー・ブーフホルツのψ関数#標準形 in Japanese Googology Wiki for details.
=== Normal form for Jäger's function ===
Since the definition is complicated, see the main article for details.
== 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 itW. Buchholz, A New System of Proof-Theoretic Ordinal Functions, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 195--207. 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.
== External Links ==
* Okkuu, 順序数電卓, c++ shell. (A c++ program for computing arithmetic and standardness with respect to Cantor normal form. A Japanese introduction is available here.)
== See also ==
== Sources ==
Category:Transfinite ordinals
Category:Notations
Category:Set theory