Ordinal collapsing function

An ordinal collapsing function, typically abbreviated OCF, is a general method of constructing an ordinal representation system, by "collapsing" uncountable or nonrecursive ordinals such as \( \Omega \) or \( \omega_1^{\mathrm{CK}} \) to smaller, recursive ordinals such as the SVO. The primary idea is that, at the point of epsilon numbers and beyond, especially at the level of strongly critical ordinals, representation systems for ordinals require complex arrays and processes of fixed point-taking. Instead, one imbues a certain level of impredicativity into the definition and uses large ordinals that would normally be entirely unreachable from below and instead use them as "diagonalizers", with higher levels taking fixed points of lower levels.

The simplest application of this idea is Chris Bird's \( \theta \) function, which uses polynomials in \( \Omega \) to encode finitary Veblen arrays. For example, we have \( \theta(\Omega) = \varepsilon_0 \), \( \theta(\Omega 2) = \zeta_0 \), \( \theta(\Omega^2) = \Gamma_0 \), and so on. However, this isn't entirely formal, and its limit is the small Veblen ordinal, small comparatively to other ordinal collapsing functions. Most ordinal collapsing functions, both in the literature and apeirological circles, are instead defined using a construction which is typically referred to as a \( C \)-set construction or Skolem hull construction of all the ordinals that can be "predicatively" built up using available operations, with some restrictions, and then letting the collapse of an ordinal \( \alpha \) be the limit of those ordinals.

History

The first ordinal collapsing function in the literature was Bachmann's \( \psi \) function, which was regarded as novel at the time and was used to calibrate the size of the Bachmann-Howard ordinal. However, the definition is quite cumbersome. A modern "recast", proposed by Michael Rathjen, is that \( \psi_\Omega(\alpha)\) is the least countable \( \rho \) so that the countable ordinals constructible from \(\Omega\) and the set of ordinals below \( \max(1, \rho) \) using the following operations are all less than \(\rho\): addition, the map \( \xi \mapsto \omega^\xi \), and \( \psi_\Omega \) restricted to inputs less than \( \alpha \). Of course, this definition is condensed, and is usually written in terms of \( C \)-sets. Below is the more formal definition.

• Let \( \Omega = \aleph_1 \) and \( C_0^\Omega(\alpha, \beta) = \beta \cup \{0, \Omega\} \).
• For all \( n \), \( C_{n+1}^\Omega(\alpha,\beta) = \{\gamma+\delta, \omega^\gamma, \psi_\Omega(\eta): \gamma, \delta, \eta \in C_n^\Omega(\alpha, \beta) \land \eta < \alpha\} \)
• \( C^\Omega(\alpha,\beta) \) is the union of \( C_n^\Omega(\alpha,\beta) \) for all finite \( n \).
• \( \psi_\Omega(\alpha) \) is the least \( \rho < \Omega \) so that \( C^\Omega(\alpha, \rho) \cap \Omega = \rho \).

The limit of this notation is the Bachmann-Howard ordinal, \( \psi_\Omega(\varepsilon_{\Omega+1}) \). This definition has been relativized to more powerful ordinal collapsing functions, most using large cardinal axioms to "diagonalize" over lower levels, such as Buchholz's psi-functions, which collapse \( \aleph_\nu \) for \( \nu \leq \omega \), and even up to Michael Rathjen's most recent OCF, which collapses an analogue of a cardinal \( \kappa \) which is \( \delta \)-shrewd, where \( \delta \) is the next weakly inaccessible cardinal after \( \kappa \).

Remarks

Rathjen has remarked upon a small detail of various ordinal collapsing functions, which he calls pictorial collapse. In particular, he says that, in the OCF defined in the "History" section, \( \psi_\Omega(\alpha) \) can be viewed as the "\( \alpha \)th collapse of \( \Omega \)" since, as he puts it, the order-type of \( \Omega \) as viewed within \( C^\Omega(\alpha, \psi_\Omega(\alpha)) \) is actually \( \psi_\Omega(\alpha) \). The same property applies to Buchholz's psi-functions, Rathjen's OCF collapsing a weakly Mahlo cardinal, and Rathjen's OCF collapsing a weakly compact cardinal.

Use of nonrecursive countable ordinals

It may seem circular to use an OCF whose definition presumes existence of uncountable or large cardinals in the ordinal analysis of a theory much weaker than ZFC. However all instances of uncountable cardinals in the definition of the OCF may be replaced with nonrecursive countable ordinals, at the expense of much difficulty in proving the relevant theorems about the OCF.

The main technique for proving the relevant theorems about \( \psi_\pi(\alpha) \) (e.g. that \( \psi_\pi(\alpha)<\pi \)) becomes to use a \( \pi \)-recursive coding scheme to code the representable ordinals that are \( >\pi \) into members of \( L_\pi \). This coding must respect the ordering of the \( \psi_\kappa(\beta) \), which itself has not yet been verified. This is in contrast to the cardinal-based definition of \( \psi \), in which case these can be proven by simple arguments like cardinality arguments.

Quantifier complexity

The quantifier complexity of many OCFs seems to be \( \Sigma_1 \). This holds for Buchholz's and Bachmann's OCFs, and Arai's OCF for \( \Pi_n \)-reflection. The quantifier complexity of Arai's OCF for \( \textsf{KP}\ell^r+\exists M(\textrm{isTrans}(M)\land M\prec_{\Sigma_1}V) \) is \( \Delta_1 \), however the quantifier complexity of Arai's OCF for KP+\( \Pi_1 \)-collection is \( \Delta_1(St) \).

List

Following Bachmann's \( \psi \), there have been various generalizations and strengthenings. These include:

• Feferman's \( \theta \)-functions
• Buchholz's \( \psi \)-functions, a simplification of Feferman's \( \theta \)-functions
• Schütte and Simpson's addition-free versions of Buchholz's functions, denoted \( \pi_i \)^pp.20--23
• Gordeev's \( D_\nu \) functions^pp.2--3
• Maksudov's extended Buchholz \( \psi \)-functions, an extension of Buchholz's \( \psi \)-functions
• Madore's \( \psi \)-function, a further simplification of Buchholz's \( \psi \)-functions
• Bird's \( \theta \)-function
• Weiermann's \( \vartheta \), a variant of Buchholz's \( \psi \)-functions with nicer behaviour
• Wilken's \( \vartheta \), which does not need standard forms, & Wilken and Weiermann's \( \bar{\vartheta} \), variants of Weiermann's \( \vartheta \)
• Jäger's \( \psi \)-function, an extension of Bachmann's \( \psi \) to the level of weakly inaccessible cardinals
• The Jäger-Buchholz function, a simplification of Jäger's \( \psi \)-function
• Rathjen's \( \psi \) function, an extension of Jäger's \( \psi \)-function to the level of weakly Mahlo cardinals
• Rathjen's \( \Psi \) function, an extension of his \( \psi \)-function to the level of weakly compact cardinals
• Duchhardt's \( \Psi \) function, an extension of Rathjen's \( \Psi \)-function to the level of \( \Pi^1_2 \)-indescribable cardinals
• Stegert's \( \Psi \) functions, extensions of Duchhardt's \( \Psi \)-function to the level of \( \Pi^2_0 \)-indescribable cardinals and analogues of pseudo-\((\cdot 2)\)-stable ordinals
• Rathjen's \( \Psi \) functions, extensions of his \( \Psi \)-function to the level of analogues of pseudo-\((\cdot 2)\)-stable ordinals and analogues of \((\alpha^{+I})\)-stable ordinals
• Arai's first \( \psi \) function, a simplification of Stegert's first \( \Psi \)-function
• Arai's second \( \psi \) function, an extension of his first \( \psi \)-function to the level of analogues of nonprojectible ordinal