Googology Wiki
Advertisement
Googology Wiki

Feferman's \(\theta\)-function is an ordinal collapsing function, which is a hierarchy of single-argument functions \(\theta_\alpha: \text{On} \to \text{On}\) for \(\alpha \in \text{On}\).[1] It is often considered a two-argument function with \(\theta_\alpha(\beta)\) written as \(\theta\alpha\beta\).

Definition

For any ordinals \(\alpha\) and \(\beta\), a family \((C_n(\alpha,\beta))_{n \in \omega}\) of sets of ordinals, a set \(C(\alpha,\beta)\) of ordinals, and an ordinal \(\theta_{\alpha}(\beta)\) are defined by the following mutual recursion[note 1]: \begin{eqnarray*} C_0(\alpha, \beta) &=& \beta \cup \{0, \omega_1, \omega_2, \ldots, \omega_\omega\}\\ C_{n+1}(\alpha, \beta) &=& \{\gamma + \delta, \theta_\xi(\eta) | \gamma, \delta, \xi, \eta \in C_n(\alpha, \beta)\land \xi < \alpha\} \\ C(\alpha, \beta) &=& \bigcup_{n < \omega} C_n (\alpha, \beta) \\ \theta_\alpha(\beta) &=& \min\{\gamma | \gamma \not\in C(\alpha, \gamma) \land\forall(\delta < \beta)(\theta_\alpha(\delta) < \gamma)\} \\ \end{eqnarray*}

Equivalently:

  • An ordinal \(\beta\) is considered \(\alpha\)-critical iff it cannot be constructed with the following elements:
    • all ordinals less than \(\beta\),
    • all ordinals in the set \(\{0, \omega_1, \omega_2, \ldots, \omega_\omega\}\),
    • the operation \(+\),
    • applications of \(\theta_\xi\) for \(\xi < \alpha\).
  • \(\theta_\alpha\) is the enumerating function for all \(\alpha\)-critical ordinals.


Ordinal notation

Unlike Buchholz's function, an associated ordinal notation is not known at least in this community.


Properties

The Feferman theta function is considered an extension of the two-argument Veblen function — for \(\alpha, \beta < \Gamma_0\), \(\theta_\alpha(\beta) = \varphi_\alpha(\beta)\). For this reason, \(\varphi\) may be used interchangeably with \(\theta\) for \(\alpha, \beta < \Gamma_0\). Because of the restriction of \(\xi \in C_n(\alpha, \beta)\) imposed in the definition of \(C_{n+1}(\alpha, \beta)\), which makes \(\theta_{\Gamma_0}\) never used in the calculation of \(C(\alpha, \beta)\) when \(\alpha < \omega_1\), \(\theta_{\alpha}(0)\) does not grow while \(\alpha < \omega_1\). This results in \(\theta_{\omega_1}(0) = \Gamma_0\) while \(\varphi_{\omega_1}(0) = \omega_1\). The value of \(\theta_{\omega_1}(0) = \Gamma_0\) can be used above \(\omega_1\) because of the definition of \(C_0\) which includes \(\omega_1\).

The supremum of the range of the function is the Takeuti-Feferman-Buchholz ordinal \(\theta_{\varepsilon_{\Omega_\omega + 1}}(0)\).[1] Theorem 3.7

Buchholz discusses a set he calls \(\theta(\omega + 1)\), which is the set of all ordinals describable with \(\{0, \omega_1, \omega_2, \ldots, \omega_\omega\}\) and finite applications of \(+\) and \(\theta\).


Footnotes

  1. This "recursion" does not mean the computability, but just means the self and mutual references of the objects through transfinite induction along a well-founded relation. Since it is a common mistake that an ordinal collapsing function is computable, the terminology of "recursion" should be carefully used here.

Sources

  1. 1.0 1.1 W. Buchholz, A New System of Proof-Theoretic Ordinal Functions, Annals of Pure and Applied Logic, vol. 32, pp.195-207, (1986).


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