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[]
- ↑ 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.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 · 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
Classes: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)