Googology Wiki
Advertisement
Googology Wiki

Extended Buchholz's function is an extension of Buchholz's function by Googology Wiki user Denis Maksudov.[1] 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_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 OCF itself is not a computable function, we need to create an ordinal notaion \((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.[2] Later, 降下段階配列表記 is created by a Japanese Googology Wiki user mrna as an equivalent notation extending 段階配列表記.

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:

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]=\alpha-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[3] by the rule 6 in the definition of \([]\) in p.6 in Buchholz's another paper[4] 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]}\).

Extension

Since Extended Buchholz's function is deeply studied in Japanese googology, there are many extensions of Extended Buchholz's function or the ordinal notation associated to it. For example, the pioneer of those extensions is the \(3\)-ary function notation by a Japanese Googology Wiki user kanrokoti.[5] Later, mrna extended 降下段階配列表記 to 多変数段階配列表記. There are several trials in Japanese googology to even extend those extensions.

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

Sources

  1. Maksudov, Denis. The extension of Buchholz's functionTraveling To The Infinity. Retrieved 2017-05-18.
  2. p進大好きbot, Ordinal Notation Associated to Extended Buchholz's OCF, Googology Wiki user blog.
  3. W. Buchholz, A New System of Proof-Theoretic Ordinal Functions, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 195--207.
  4. W. Buchholz, Relating ordinals to proofs in a perspicuous way, Reflections on the foundations of mathematics (Stanford, CA, 1998) 15 (2017): 37--59.
  5. kanrokoti, 3 variables ψ which is larger than EBOCF, Googology Wiki user blog.

See also

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation
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_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\zeta,\Sigma,\gamma\) (ordinals on infinite time Turing machine) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Buchholz's function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert'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
Classes: \(V\) · \(L\) · \(\textrm{On}\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)

Advertisement