Feferman's theta function

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}\).W. Buchholz, A New System of Proof-Theoretic Ordinal Functions, Annals of Pure and Applied Logic, vol. 32, pp.195-207, (1986). 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 recursionThis "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.:
\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)\). 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 ==
== Sources ==
== See also ==
Category:Set theory
Category:Ordinal collapsing functions