Extended Weak 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.A conversation by Okkuu and Gaoji.A conversation by p進大好きbot and Gaoji. 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\).Gaoji, 弱ブーフホルツのψ関数, Japanese Googology Wiki user blog. 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,p進大好きbot, Extended Weak Buchholz's OCF in Programming Language Qp, Googology Wiki user blog. 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:
# 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 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:
#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\),
#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]}\),
#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])\),
#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:
# Extended Weak Buchholz's function has a formal definition.
# Nothing OCF is unformalised.
For the second point, there are two counterarguments:
# 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.
# The formulation by rpakrrpakr, Nothing OCF Analysis, a Googology Wiki user page. 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.A comment by p進大好きbot. Although CatIsFluffy himself or herself agreed that rpakr's formulation should have been an official formalisation of Nothing OCF,CatIsFluffy, NON Ordinal Notation?oldid=347672, an old version of a Googology Wiki user blog. he or she changed the opinion after the issue was pointed out.A comment by CatIsFluffy.
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.A comment by p進大好きbot.A comment by p進大好きbot. 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, Embedding EBOCF → EWBOCF, Github page. Retrieved (UTC) 18:23 May 26th, 2022. 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++)
== Sources ==
== See also ==
* Buchholz's function
* Extended Buchholz's function
Category:Buchholz's psi-functions
Category:Functions
Category:Transfinite ordinals
Category:Eponymous functions
Category:Ordinal collapsing functions
Category:Ordinal notations
Category:Googology in Japan