Extended Weak Buchholz's function

View full site to see MathJax equation

Not to be confused with Extended Buchholz's function.

Extended Weak Buchholz's function (Japanese: 拡張弱ブーフホルツ関数) is an extension of Weak Buchholz's function (Japanese: 弱ブーフホルツ関数), which is in turn a weakened variant of Buchholz's function. Weak Buchholz's function was defined by the Japanese Googology Wiki user Gaoji, and Extended Weak Buchholz's function was subsequently defined by the Japanese Googology Wiki user Okkuu. The countable limit of Extended Weak Buchholz's function is expressed as \(\psi_0(\Omega_{\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}}}) = \psi_0(\psi_{\psi_{\psi_{\cdots}(0)}(0)}(0)) = \psi_0(\Lambda)\), where \(\psi\) is Extended Weak Buchholz's function and \(\Lambda\) denotes the least omega fixed point, and is expected to coincide with the countable limit of Extended Buchholz's function although the coincidence has not been proved yet. For more details, see the #Analysis section.

Definition

All the variables \(\nu\), \(\alpha\), \(\beta\), \(\mu\), \(\eta\), and \(\gamma\) are intended to run through ordinals, and the variable \(n\) runs through natural numbers. Okkuu defined Extended Weak Buchholz's functions as follows:

• \(C_\nu^0(\alpha) = \Omega_{\nu}\),
• \(C_\nu^{n+1}(\alpha) = \{\beta,\psi_\mu(\eta) \mid \mu,\beta,\eta\in C_{\nu}^n(\alpha)\wedge\eta<\alpha\}\),
• \(C_\nu(\alpha) = \bigcup_{n < \omega} C_\nu^n (\alpha)\),
• \(\psi_\nu(\alpha) = \min\{\gamma \mid \gamma \notin C_\nu(\alpha)\}\),

where

\begin{eqnarray*} \Omega_\nu=\left\{\begin{array}{ll} 1 & \nu=0 \\ \aleph_\nu & \nu \neq 0 \end{array}\right. \end{eqnarray*}

There is only one small difference with original Weak Buchholz definition, which the ordinal \(\mu\) is not limited by \(\omega\), now the ordinal \(\mu\) instead belongs to the previous set \(C_{\nu}^n\). So, the relation between Buchholz's function and Extended Buchholz's function is quite similar to that of Weak Buchholz's function and Extended Weak Buchholz's function. Also, there is only one little detail difference with original Extended Buchholz definition, which is that addition is not used in the definition of \(C_\nu(\alpha)\).

Ordinal notation

Since an ordinal collapsing function itself is not a computable function, we need to create an ordinal notation \((OT,<)\) associated to Extended Weak Buchholz's function, i.e. a recursive interpretation of the comparison and the system of fundamental sequences of ordinals using formal expressions, in order to create a computable large number. Indeed, explicit algorithms to compute them and the associated fast-growing hierarchy are given by a Japanese Googology Wiki user p進大好きbot, who also invented the ordinal notation associated to Extended Buchholz's function. It uses the programming language \(\mathbb{Q}_p\), and has automatic interpretations into natural languages and C++. Another Japanese Googology Wiki user rpakr also implemented it into C++ (cf. #External Links).

Normal form

The predicate for normal form can be immediately derived from the definition of standard form, i.e. expressions in \(OT\).

Informally speaking, the normal form for \(0\) is \(0\). If \(\alpha\) is a nonzero ordinal number \(\alpha<\Lambda=\text{min}\{\beta|\psi_\beta(0)=\beta\}\) then the normal form for \(\alpha\) is intended to be \(\alpha=\psi_{\nu}(\beta)\) where \(\nu\) and \(\beta\) are ordinals satisfying \(\beta \in C_{\nu}(\beta)\). We note that since \(\beta\) is also an ordinal in \(C_0(\Lambda)\), it is possible to express them in normal form. It roughly means that every ordinal in \(C_0(\Lambda)\) is expressed in "iterated" normal form consisting of \(0\) and \(\psi\).

More formally, 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 extending the original ordinal notation system \((OT,<)\) explained above, by the definition of normal form using standard form.

Fundamental sequences

The fundamental sequence for an ordinal number \(\alpha\) with cofinality \(\text{cof}(\alpha)=\beta\) is a strictly increasing sequence \((\alpha[\eta])_{\eta<\beta}\) with length \(\beta\) and with limit \(\alpha\), where \(\alpha[\eta]\) is the \(\eta\)-th element of this sequence. If \(\alpha\) is a successor ordinal then \(\text{cof}(\alpha)=1\) and the fundamental sequence has only one element \(\alpha[0]\) satisfying \(\alpha=\alpha[0]+1\). If \(\alpha\) is a limit ordinal then \(\text{cof}(\alpha)\in\{\omega\}\cup\{\Omega_{\mu+1}|\mu\geq 0\}\).

Although a system of fundamental sequences is not unique, there is a canonical choice of fundamental sequences defined by p進大好きbot mentioned in #Ordinal notation. For nonzero ordinals \(\alpha<\Lambda\), written in normal form, fundamental sequences are intended to be defined as follows:

1. If \(\alpha=_{\textrm{NF}}\psi_{\nu}(0)\) for some \(\nu \in \Lambda\) with \(\text{cof}(\nu)\in\omega\), then \(\text{cof}(\alpha)=\alpha\) and \(\alpha[\eta]=\eta\),
2. If \(\alpha=_{\textrm{NF}}\psi_{\nu}(0)\) for some \(\nu \in \Lambda\) with \(\text{cof}(\nu)\notin\omega\), then \(\text{cof}(\alpha)=\text{cof}(\nu)\) and \(\alpha[\eta]=\psi_{\nu[\eta]}(0)=\Omega_{\nu[\eta]}\),
3. If \(\alpha=_{\textrm{NF}}\psi_{\nu}(\beta)\) for some \(\nu,\beta \in \Lambda\) with \(\beta \neq 0\) and \(\alpha \notin \text{cof}(\beta)\), then \(\text{cof}(\alpha)=\text{cof}(\beta)\) and \(\alpha[\eta]=\psi_{\nu}(\beta[\eta])\),
4. If \(\alpha=_{\textrm{NF}}\psi_{\nu}(\beta)\) for some \(\nu,\beta \in \Lambda\) with \(\beta \neq 0\) and \(\alpha \in \text{cof}(\beta)\), then \(\text{cof}(\alpha)=\omega\) and \(\alpha[\eta]=\psi_{\nu}(\beta[\psi_{\delta}(\epsilon)])\), where \(\delta,\epsilon \in \Lambda\) are the unique ordinals with \(\text{cof}(\beta) = \psi_{\delta+1}(0)\), \(\epsilon= 0\) if \(\eta = 0\), and \(\psi_{\nu}(\epsilon) = \alpha[\eta[0]]\) if \(\eta \neq 0\).

In addition, if \(\alpha=\Lambda\), then \(\text{cof}(\alpha)=\omega\) and a fundamental sequence \(\alpha[\eta]\) for \(\alpha\) can be defined as

\begin{eqnarray*} \alpha[\eta]=\left\{\begin{array}{ll} 0 & \eta=0 \\ \psi_{\alpha[\eta[0]]}(0) & \eta \neq 0 \end{array}\right. \end{eqnarray*}

Common misconceptions

Extended Weak Buchholz's function is frequently identified with Nothing OCF by Googology Wiki user CatIsFluffy, but they are completely different works by the following points:

1. Extended Weak Buchholz's function has a formal definition.
2. Nothing OCF is unformalised.

For the second point, there are two counterarguments:

1. Googologists in a discord community use Nothing OCF in their analyses, and hence it should be regarded as a well-defined function through the analyses.
2. The formulation by rpakr is widely regarded as an official formalisation of Nothing OCF, and hence it should be regarded as a well-defined function through the alternative formalisation.

For the first counterargument, the use of an unformalised notation in an informal analysis does not give any formalisation. Indeed, there are many ill-defined notations, e.g. BEAF beyond tetrational arrays and Dollar function, which appear in such analyses.

For the second counterargument, p進大好きbot pointed out that the analysis by rpakr is wrong, and hence does not match the explanation by CatIsFluffy. Although CatIsFluffy himself or herself agreed that rpakr's formulation should have been an official formalisation of Nothing OCF, he or she changed the opinion after the issue was pointed out.

In addition, CatIsFluffy insisted that Nothing OCF was intended to be identical to Extended Weak Buchholz's function, but p進大好きbot pointed out that the explanation of standard form for Nothing OCF does not seem to be directly compatible with that for Extended Weak Buchholz's function. Although the compatibility might be justified in some quite non-trivial way in the future, CatIsFluffy has not already replied to the last comment, and hence at least it has no current justification.

Therefore as a conclusion, there is no objective point of views which ensures that Nothing OCF has been appropriately formalised, and hence it should not be considered to be identical with Extended Weak Buchholz's function.

Analysis

As we explained in #Common misconceptions, people sometimes identify Nothing OCF and Extended Weak Buchholz's function, and hence refer to intuitive analyses of Nothing OCF, which do not make sense because of the ill-definedness, as if they were analysis of Extended Weak Buchholz's function. However, since the identification of an ill-defined function with Extended Weak Buchholz's function does not make sense, the claim that those analyses are applicable to Extended Weak Buchholz's function is inappropriate.

On the other hand, a Japanese googologist Naruyoko established a translation map following p進大好きbot's analysis schema, which are commonly used in Japanese googology communities. Naruyoko conjectured that the restriction of the translation map gives an injective order-preserving map from p進大好きbot's ordinal notation associated with Extended Weak Buchholz's function to p進大好きbot's ordinal notation associated to Extended Buchholz's function in ja:ユーザーブログ:Naruyoko/拡張ブーフホルツのψから拡張弱ブーフホルツのψへの順序保存写像.

If the conjecture is true, then it implies that the order type of the former one coincides with the order type of the latter one by Proposition 7 (4) in the analysis schema, because we already have another injective order-preserving map of the inverse direction. By also proving that all terms less than \(((0,0),0)\) in the former one is mapped to terms less than \(\langle \langle 0, 0 \rangle, 0 \rangle\) in the latter one and vise versa, it follows that the countable limit of Extended Weak Buchholz's function and the countable limit of Extended Buchholz's function are equal, under the assumption that the ordinal notations actually implement the two OCFs.

In conclusion, the comparison of the countable limits is reduced to those two conjectures. We note that this technique of analysis by the analysis schema does not provide a way to determine the correspondence between intermediate values. For the correspondence, see rpakr's conjectural analyses:

• ja:ユーザーブログ:Rpakr/拡張弱 Buchholz ψ 観察日記 (1)
• ja:ユーザーブログ:Rpakr/拡張弱 Buchholz ψ 観察日記 (2)
• ja:ユーザーブログ:Rpakr/拡張弱 Buchholz ψ 観察日記 (3)
• ja:ユーザーブログ:Rpakr/拡張弱 Buchholz ψ 観察日記 (4)

External Links

• p進大好きbot, プログラミング言語\(\mathbb{Q}_p\) (an introduction to programming language \(\mathbb{Q}_p\))
• rpakr, Weak Extended Buchholz.cpp, github. (an implementation of p進大好きbot's ordinal notation associated to Extended Weak Buchholz's function by C++)

See also

• Buchholz's function
• Extended Buchholz's function

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