Extended Buchholz's function

View full site to see MathJax equation

Not to be confused with Buchholz's function or Extended Weak Buchholz's function or Jäger-Buchholz function.

Extended Buchholz's function is an extension of Buchholz's function by Googology Wiki user Denis Maksudov. The countable limit of Extended 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 \(\Lambda\) denotes the least omega fixed point, and is called Extended Buchholz's ordinal or EBO in Japanese Googology.

Definition

Denis Maksudov defined his functions as follows:

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

where

\(\Omega_\nu=\left\{\begin{array}{lcr} 1\text{ if }\nu=0 \\ \text{smallest ordinal with cardinality }\aleph_\nu \text{ if }\nu>0 \\ \end{array}\right.\)

There is only one little detail difference with original Buchholz definition: ordinal \(\mu\) is not limited by \(\omega\), now ordinal \(\mu\) belongs to previous set \(C_{\nu}^n\).

For example if \(C_0^0(1)=\{0\}\) then \(C_0^1(1)=\{0,\psi_0(0)=1\}\) and \(C_0^2(1)=\{0,...,\psi_1(0)=\Omega\}\) and \(C_0^3(1)=\{0,...,\psi_\Omega(0)=\Omega_\Omega\}\) and so on.

Ordinal notation

Since an ordinal collapsing function itself is not a computable function, we need to create an ordinal notation \((OT,<)\) associated to Extended 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 extending those for Buchholz's function are given by a Japanese Googology Wiki user p進大好きbot. See #External Links for a computation program by koteitan, which essentially supports p進大好きbot's ordinal notation because it deals with its extension KumaKuma ψ function explained in #Extensions section.

Later, 降下段階配列表記 is created by a Japanese Googology Wiki user mrna as an equivalent notation extending 段階配列表記. It also has an extension 多変数段階配列表記 explained in #Extensions section.

Normal form

Googology Wiki user Denis Maksudov also extended the second normal form explained in Buchholz's function#Normal form to ordinals in \(C_0(\Lambda)\) in the following way:

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 \(\alpha=\psi_{\nu_1}(\beta_1)+\psi_{\nu_2}(\beta_2)+\cdots+\psi_{\nu_k}(\beta_k)\) where \(k\) is a positive integer and \(\psi_{\nu_1}(\beta_1)\geq\psi_{\nu_2}(\beta_2)\geq\cdots\geq\psi_{\nu_k}(\beta_k)\) and each \(\nu_i\), \(\beta_i\) are ordinals satisfying \(\beta_i \in C_{\nu_i}(\beta_i)\). We note that since \(\beta_i\)'s are also ordinals 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 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}\).
3. The predicate \(\alpha_0 =_{\textrm{NF}} \psi_{\nu_1}(\alpha_1) + \cdots + \psi_{\nu_n}(\alpha_n)\) on ordinals \(\alpha_0, \ldots, \alpha_n, \nu_1, \ldots, \nu_k\) in \(C_0(\Lambda)\) with an integer \(k > 1\) defined as \(\alpha_0 = \psi_{\nu_1}(\alpha_1) + \cdots + \psi_{\nu_k}(\alpha_k)\), \(\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}\).

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.

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 in this community given by Denis. For nonzero ordinals \(\alpha<\Lambda\), written in normal form, fundamental sequences are defined as follows:

1. If \(\alpha=_{\textrm{NF}}\psi_{\nu_1}(\beta_1)+\psi_{\nu_2}(\beta_2)+\cdots+\psi_{\nu_k}(\beta_k)\) where \(k\geq2\) then \(\text{cof}(\alpha)=\text{cof}(\psi_{\nu_k}(\beta_k))\) and \(\alpha[\eta]=\psi_{\nu_1}(\beta_1)+\cdots+\psi_{\nu_{k-1}}(\beta_{k-1})+(\psi_{\nu_k}(\beta_k)[\eta])\),
2. If \(\alpha=_{\textrm{NF}}\psi_{0}(0)=1\), then \(\text{cof}(\alpha)=1\) and \(\alpha[0]=0\),
3. If \(\alpha=_{\textrm{NF}}\psi_{\nu+1}(0)\), then \(\text{cof}(\alpha)=\Omega_{\nu+1}\) and \(\alpha[\eta]=\Omega_{\nu+1}[\eta]=\eta\),
4. If \(\alpha=_{\textrm{NF}}\psi_{\nu}(0)\) and \(\text{cof}(\nu)\in\{\omega\}\cup\{\Omega_{\mu+1}|\mu\geq 0\}\), then \(\text{cof}(\alpha)=\text{cof}(\nu)\) and \(\alpha[\eta]=\psi_{\nu[\eta]}(0)=\Omega_{\nu[\eta]}\),
5. If \(\alpha=_{\textrm{NF}}\psi_{\nu}(\beta+1)\) then \(\text{cof}(\alpha)=\omega\) and \(\alpha[\eta]=\psi_{\nu}(\beta)\cdot \eta\) (and note: \(\psi_\nu(0)=\Omega_\nu\)),
6. If \(\alpha=_{\textrm{NF}}\psi_{\nu}(\beta)\) and \(\text{cof}(\beta)\in\{\omega\}\cup\{\Omega_{\mu+1}|\mu<\nu\}\) then \(\text{cof}(\alpha)=\text{cof}(\beta)\) and \(\alpha[\eta]=\psi_{\nu}(\beta[\eta])\),
7. If \(\alpha=_{\textrm{NF}}\psi_{\nu}(\beta)\) and \(\text{cof}(\beta) = \Omega_{\mu+1}\) for a \(\mu\geq\nu\) then \(\text{cof}(\alpha)=\omega\) and \(\alpha[\eta]=\psi_{\nu}(\beta[\gamma[\eta]])\) where \(\left\{\begin{array}{lcr} \gamma[0]=\Omega_\mu \\ \gamma[\eta+1]=\psi_\mu(\beta[\gamma[\eta]])\\ \end{array}\right.\).

It is an extension of the system of fundamental sequences up to \(\psi_0(\varepsilon_{\Omega_{\omega}+1})\) in Buchholz hierarchy given by modifying the rule ([].5) (ii) in recursive definition of the \(\textrm{dom}\) function and \([]\) in Buchholz's original paper by the rule 6 in the definition of \([]\) in p.6 in Buchholz's another paper applied to the convention \(\Omega_0 = 1\) except for the minor differences related to the difference \(\omega[n] = n+1\) in the original definition and \(\omega[n] = n\) in the definition here. (Please remember that \(\Omega_0\) is defined as \(1\) in the original paper, while it is defined as \(\omega\) in the other paper.) More precisely, the fundamental sequence of \(\psi_0(2) = \omega \times \omega\) is given as \(\omega \times \omega [n] = \omega \times (n+1)\) in the original definition while we have \(\omega \times \omega[n] = \omega \times n\) in the definition here, and the fundamental sequence of \(\psi_{\omega}(0) = \Omega_{\omega}\) is given as \(\Omega_{\omega}[n] = \Omega_{n+1}\) while we have \(\Omega_{\omega}[n] = \Omega_n\) in the definition here.

If \(\alpha=\Lambda\) then \(\text{cof}(\alpha)=\omega\) and \(\alpha[0]=0\) and \(\alpha[\eta+1]=\psi_{\alpha[\eta]}(0)=\Omega_{\alpha[\eta]}\).

Variants

Since the structure of Extended Buchholz's function is quite sophisticated and is deeply studied in Japanese googology, there are many variants of Extended Buchholz's function or the ordinal notation associated to it. Namely, it plays a role of the base of other notations, i.e. many variants are invented, in Japanese googology.

Extension

The pioneer of those extensions is the \(3\)-ary function notation by a Japanese Googology Wiki user kanrokoti. Later, mrna extended 降下段階配列表記 to 多変数段階配列表記. There are several trials in Japanese googology to even extend those extensions.

Simplification

Extended Buchholz's function is defined by using the closure with respect to the addition, while Extended Weak Buchholz's function is defined in the same way except that it does not use the closure with respect to the addition. Therefore the definitions directly imply that Extended Weak Buchholz's function is bounded by Extended Buchholz's function. One non-trivial expectation is that the two functions have the same countable limit, but it has not been proved yet.

Common misconceptions

Since there are so many misconceptions about Buchholz's function and Extended Buchholz's function, readers are strongly recommended to check Buchholz's function#Common misconceptions before talking about them.

External Links

• Buchholz ψ analyzer by Fish
• Online calculator for fast-growing hierarchy with Buchholz function by Denis Maksudov
• Online calculator for fast-growing hierarchy with Extended Buchholz function by Denis Maksudov
• ordex: Ordinal Expander in JavaScript by koteitan (Koteitan's online calculator for kanrokoti's \(3\)-ary extension of p進大好きbot's ordinal notation associated to Denis' extension of Buchholz's function. Therefore it essentially supports p進大好きbot's ordinal notation. A detailed explanation is available here.)

See also

• Buchholz's function
• Extended Weak 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