11,578
pages

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. W. Buchholz, A New System of Proof-Theoretic Ordinal Functions, Annals of Pure and Applied Logic, vol. 32, pp.195-207, (1986).