Normal form

View full site to see MathJax equation

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.

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:

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 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

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.

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

Main article: Extended Weak Buchholz's function#Normal form

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:

1. The predicate \(\alpha =_{\textrm{NF}} 0\) on an ordinal \(\alpha\) in \(C_0(\Lambda)\) 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 \(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

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.

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

Main article: 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 it 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

Ordinals, ordinal analysis, and set theory

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 · Berkeley cardinal · (Club Berkeley cardinal · limit club Berkeley cardinal)
Classes: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)

Googology in Japan

Original numbers, functions, notations, and notions

By Aeton: Okojo numbers · N-growing hierarchy
By 新井 (Arai): Arai's psi function
By aster: White-aster notation · White-aster
By バシク (BashicuHyudora): Primitive sequence number · Pair sequence number · Bashicu matrix system 1/2/3/4 original idea
By ふぃっしゅ (Fish): Fish numbers (Fish number 1 · Fish number 2 · Fish number 3 · Fish number 4 · Fish number 5 · Fish number 6 · Fish number 7 · S map · SS map · s(n) map · m(n) map · m(m,n) map) · Bashicu matrix system 1/2/3/4 formalisation · TR function (I0 function)
By Gaoji: Weak Buchholz's function
By じぇいそん (Jason): Irrational arrow notation · δOCF · δφ · ε function
By 甘露東風 (Kanrokoti): KumaKuma ψ function
By koteitan: Bashicu matrix system 2.3
By mrna: 段階配列表記 · 降下段階配列表記 · 多変数段階配列表記 · SSAN · S-σ
By Naruyoko Naruyo: Y sequence formalisation · ω-Y sequence formalisation
By Nayuta Ito: N primitive · Flan numbers (Flan number 1 · Flan number 2 · Flan number 3 · Flan number 4 version 3 · Flan number 5 version 3) · Large Number Lying on the Boundary of the Rule of Touhou Large Number 4 · Googology Wiki can have an article with any gibberish if it's assigned to a number
By Okkuu: Extended Weak Buchholz's function
By p進大好きbot: Ordinal notation associated to Extended Weak Buchholz's function · Ordinal notation associated to Extended Buchholz's function · Naruyoko is the great · Large Number Garden Number
By たろう (Taro): Taro's multivariable Ackermann function
By ゆきと (Yukito): Hyper primitive sequence system · Y sequence original idea · YY sequence · Y function · ω-Y sequence original idea

Methodology

By バシク (BashicuHyudora): Bashicu matrix system as a notation template
By じぇいそん (Jason): Shifting definition
By mrna: Side nesting
By Nayuta Ito and ゆきと (Yukito): Difference sequence system

Implementation of existing works into programs

By ふぃっしゅ (Fish): Ackermann function
By koteitan: Ackermann function · Beklemishev's worms · KumaKuma ψ function
By Mitsuki1729: Ackermann function · Graham's number · Conway's Tetratri · Fish number 1 · Fish number 2 · Laver table
By みずどら: White-aster notation
By Naruyoko Naruyo: p進大好きbot's Translation map for pair sequence system and Buchholz's ordinal notation · KumaKuma ψ function · Naruyoko is the great
By 猫山にゃん太 (Nekoyama Nyanta): Flan number 4 version 3 · Fish number 5 · Laver table
By Okkuu: Fish number 1 · Fish number 2 · Fish number 3 · Fish number 5 · Fish number 6
By rpakr: p進大好きbot's ordinal notation associated to Extended Weak Buchholz's function · Standardness decision algorithm for Taranovsky's ordinal notation

Proofs, translation maps for analysis schema, and other mathematical contributions

By ふぃっしゅ (Fish): Computing last 100000 digits of mega · Approximation method for FGH using Arrow notation · Translation map for primitive sequence system and Cantor normal form
By Kihara: Proof of an estimation of TREE sequence · Proof of the incomparability of Busy Beaver function and FGH associated to Kleene's \(\mathcal{O}\)
By koteitan: Translation map for primitive sequence system and Cantor normal form
By Naruyoko Naruyo: Translation map for Extended Weak Buchholz's function and Extended Buchholz's function
By Nayuta Ito: Comparison of Steinhaus-Moser Notation and Ampersand Notation
By Okkuu: Verification of みずどら's computation program of White-aster notation
By p進大好きbot: Proof of the termination of Hyper primitive sequence system · Proof of the termination of Pair sequence number · Proof of the termination of segements of TR function in the base theory under the assumption of the \(\Sigma_1\)-soundness and the pointwise well-definedness of \(\textrm{TR}(T,n)\) for the case where \(T\) is the formalisation of the base theory

Entertainments

By 小林銅蟲 (Kobayashi Doom): Sushi Kokuu Hen
By koteitan: Dancing video of a Gijinka of Fukashigi · Dancing video of a Gijinka of 久界 · Storyteller's theotre video reading Large Number Garden Number aloud

See also: Template:Googology in Asia