Ordinal collapsing function
In mathematical logic and set theory, an ordinal collapsing function is a technique for defining notations representing large countable ordinals by systematically "collapsing" larger uncountable ordinals—typically regular cardinals—into the countable domain, thereby extending beyond the limitations of traditional hierarchies like the Veblen functions.[1] These functions, often denoted as ψ or θ, operate through transfinite recursion, generating sequences closed under successor, addition, and the collapsing operation itself, which ensures the output remains a countable ordinal while encoding information from much larger structures.[2] The concept originated with Howard Bachmann's work in the 1950s, where he introduced collapsing mechanisms using functions like φ_α with indices exceeding the first uncountable ordinal Ω to reach ordinals around the Bachmann-Howard ordinal, marking a shift from multi-variable notations to more efficient single-variable systems.[1] Solomon Feferman later simplified and popularized the approach in the 1970s with his θ-functions, which collapse cardinals to enumerate ordinals up to the Takeuti–Feferman–Buchholz ordinal, providing a bridge to proof-theoretic applications.[1] Wilfried Buchholz advanced the framework significantly in 1986 with his ψ_v functions (for v ≥ ω), defined as the least ordinal γ not in the closure C_v(α) generated from base ordinals below a fixed cardinal κ_ω under addition and prior ψ applications, offering a streamlined system equivalent in strength to Feferman's but more amenable to computational and analytical use.[2] Ordinal collapsing functions are fundamental in ordinal analysis, a branch of proof theory that assigns ordinals to formal systems to measure their consistency strength and reveal unprovable statements, such as the well-foundedness of certain ordinal notations within systems like Kripke–Platek set theory or iterated inductive definitions.[2] For instance, Buchholz's ψ_0(ε_{Ω_ω + 1}) corresponds to the proof-theoretic ordinal of second-order arithmetic with Π¹₁-comprehension and bar induction (Π¹₁-CA + BI), demonstrating how these functions quantify the "size" of proofs in second-order arithmetic.[2][3] Extensions, such as Buchholz's Mahlo-variant OCFs from 1990, incorporate higher large cardinals like Mahlo cardinals to analyze stronger theories, including those with elementary embeddings.[1] Despite their power, all such functions produce only countable ordinals, as the notation systems remain recursive and thus limited to the countable hierarchy.[1]Fundamentals
Definition and Purpose
An ordinal collapsing function, often denoted as \psi(\kappa, \alpha), is a recursive function in set theory and proof theory that systematically maps uncountable ordinals or ordinals above a fixed regular cardinal \kappa (such as the first uncountable cardinal \Omega) to countable ordinals below \kappa. This process, known as "collapsing," constructs notations for large countable ordinals by projecting structures from higher cardinalities onto the countable level, enabling the representation of ordinals that surpass those definable by more primitive means like the Veblen hierarchy.[4][5] The primary purpose of such functions in proof theory is to facilitate ordinal analysis, where they assign proof-theoretic ordinals to formal systems, quantifying the system's consistency strength through the supremum of ordinals it can prove well-ordered. By providing a hierarchical framework for ordinal notations, OCFs allow researchers to embed impredicative definitions within predicative constructions, supporting relative consistency proofs and comparisons of theoretical strengths across subsystems of set theory or arithmetic.[4][6] Unlike direct ordinal arithmetic operations such as addition or exponentiation, which operate within fixed levels of the ordinal hierarchy, OCFs generate notations via iterative collapsing steps, producing a well-ordered system of countable ordinals that mimics the behavior of much larger cardinals. This distinction ensures that the resulting notations remain manageable for computability while capturing the expressive power needed for advanced proof-theoretic investigations.[5][4]Historical Context
The development of ordinal collapsing functions (OCFs) emerged from the broader field of ordinal analysis in proof theory, which originated in David Hilbert's program during the 1920s. Hilbert sought to secure the foundations of mathematics by proving the consistency of formal systems using finitistic methods, but Kurt Gödel's incompleteness theorems of 1931 revealed fundamental limitations, shifting emphasis toward relative consistency proofs via transfinite ordinals.[7] Gerhard Gentzen's 1936 consistency proof for Peano arithmetic, employing transfinite induction up to the ordinal ε₀, established ordinal analysis as a key tool for measuring proof-theoretic strength.[7] In the late 1930s, Alonzo Church and Stephen Kleene advanced this framework by constructing the Church-Kleene ordinal ω₁^CK, the supremum of all computable well-orderings, providing a foundational notation for hyperarithmetic sets and early ordinal hierarchies. By the 1960s, Solomon Feferman and Kurt Schütte identified the ordinal Γ₀ as the proof-theoretic bound for predicative analysis of second-order arithmetic, marking a milestone in handling impredicative definitions through extended notations.[8] The Bachmann-Howard ordinal, introduced by Heinz Bachmann in the 1950s and formalized by William Howard in the early 1970s, further expanded notations by incorporating uncountable cofinalities, enabling analysis of stronger impredicative systems. The first ordinal collapsing function, Bachmann's ψ, was introduced in this work to define notations reaching the Bachmann-Howard ordinal.[1] Wilfried Buchholz extended the framework in the late 1970s and 1980s with impredicative OCFs, such as his ψ-functions based on ρ-inaccessible ordinals, simplifying notations for subsystems like Π¹₁-comprehension arithmetic (Π¹₁-CA₀), whose proof-theoretic ordinal is the Bachmann-Howard ordinal.[9] These tools proved essential for ordinal analyses of set theory fragments, including Kripke-Platek set theory and related arithmetic systems. In the 1990s, Michael Rathjen generalized OCFs to incorporate large cardinals, developing collapsing functions from recursively large ordinals to analyze theories like Kripke-Platek set theory with a Mahlo cardinal (KPM), bridging proof theory with inner model theory and enabling proofs of well-foundedness for vast notation systems.[10] This evolution reflects OCFs' growing role in quantifying the consistency strength of formal systems beyond classical arithmetic.Standard Example Up to the Bachmann–Howard Ordinal
Formal Definition of the Example ψ
The standard example of an ordinal collapsing function ψ, used to construct notations up to the Bachmann–Howard ordinal, is defined inductively as follows: for each ordinal α, let C(α) be the smallest class of ordinals containing 0, 1, ω, and the first uncountable ordinal Ω, and closed under addition, multiplication, successor, the Veblen hierarchy functions φ_β(γ) for β < α and γ in the closure, and the application of ψ to arguments strictly less than α; then ψ(α) is the least ordinal not in C(α).[11][12] This definition ensures that ψ(α) is countable for all α, as it enumerates ordinals below Ω that cannot be reached from the base constants and prior ψ values using the permitted operations.[13] A more precise formulation, applicable for α < ε_{Ω+1}, expresses ψ(α) as the supremum of ordinals β < Ω such that β lies outside the closure of smaller ordinals under operations including the Ω-successor (γ ↦ Ω · γ), the Veblen hierarchy functions φ_β(γ) for β ≥ 0, and previous ψ values restricted to arguments below α.[12] Here, the Veblen hierarchy provides the backbone for countable ordinal arithmetic: for instance, the function φ_0(γ) = ω^γ, φ_1(γ) enumerates the ε numbers (fixed points of φ_0), and higher φ_β(γ) enumerate common fixed points of lower functions, with the hierarchy extended using fundamental sequences for limit ordinals.[11] This collapsing mechanism "projects" uncountable structures below Ω back into the countable ordinals, allowing ψ to surpass the limitations of the pure Veblen hierarchy.[13] The Bachmann–Howard ordinal is then given by ψ(ε_{Ω+1}), where ε_{Ω+1} is the least ordinal greater than all ε_β for β < Ω + 1 in the extended ε hierarchy (i.e., the supremum of the sequence ε_Ω, ε_{ε_Ω}, ε_{ε_{ε_Ω}}, ...).[11] This value ψ(ε_{Ω+1}) coincides with the least fixed point of the function mapping α to ε_{α + 1}, marking the boundary where the collapsing process incorporates impredicative definitions to reach the proof-theoretic ordinal of Kripke–Platek set theory.[12] The construction presupposes familiarity with the Veblen hierarchy and the use of fundamental sequences to define limits in ordinal notations.[13]Predicative Computations
The predicative computations of the ordinal collapsing function \psi form the foundational stage, where ordinals are constructed recursively from smaller ones using fundamental operations like addition, multiplication, and the Veblen hierarchy, without self-referential applications of \psi that would introduce impredicativity. This approach ensures that each value \psi(\alpha) depends only on previously defined ordinals, aligning with predicative methods in proof theory.[1] The process starts with the base cases: \psi(0) = \varepsilon_0 and \psi(1) = \varepsilon_1. For finite \alpha < \omega, \psi(\alpha) = \varepsilon_\alpha; for instance, \psi(2) = \varepsilon_2 and \psi(3) = \varepsilon_3. At the first limit ordinal, \psi(\omega) is the least upper bound of \{\psi(n) \mid n < \omega\}, yielding \zeta_0, the smallest ordinal satisfying \zeta_0 = \varepsilon_{\zeta_0}.[1] Building further along the Veblen hierarchy, \psi(\omega + 1) = \zeta_1, the successor in the \zeta-numbers, and more generally, \psi(\omega \cdot \beta) = \eta_{\beta - 1} for appropriate \beta. Progressing through higher exponents, \psi(\omega^2) = \varphi_2(0) and \psi(\omega^\omega) = \varphi_\omega(0), the least fixed point of the enumeration function \alpha \mapsto \varphi_\alpha(0). These steps replicate the structure of Veblen's normal functions up to the small Veblen ordinal.[1] This predicative phase culminates in the closure under these operations, generating all ordinals up to \varepsilon_{\Omega + 1}, where \Omega denotes a formal symbol for the first uncountable ordinal in the notation system. Beyond this point, computations transition to impredicative stages involving self-reference to \psi.[1]Initial Impredicative Values
The initial impredicative values of the ordinal collapsing function ψ represent the onset of self-referential definitions, where the construction of the set C(α) incorporates applications of ψ(γ) for γ < α, thereby extending the reach beyond the purely predicative computations derived from the Veblen hierarchy. This transition occurs as arguments approach Ω, with ψ(Ω) = Γ_0, the Feferman–Schütte ordinal.[2] Subsequent computations in this impredicative regime illustrate the collapsing effect; for instance, ψ(Ω · 2) continues the hierarchy beyond Γ_0. More specifically, for arguments α near Ω, the function produces values that initiate the collapse of larger structures.[2] The impredicative character arises fundamentally in the definition of C(α), which includes ordinals β < Ω such that Ω belongs to the order type otp(T_β) of terms T_β constructed using prior values of ψ. This self-reference ensures that ψ(α) enumerates ordinals not attainable through lower-level closures. The key defining equation is ψ(α) = \min { \xi < \Omega \mid \forall \gamma < \alpha , (\psi(\gamma) < \xi) \land \neg (\xi \text{ satisfies the collapsing condition}) }, where the collapsing condition prohibits ξ from being generated within C(α).[2]Computations Up to the Feferman–Schütte Ordinal
In the standard ordinal collapsing function ψ, computations proceed by defining ψ(α) as the least ordinal not in the collapsing set C(α), where C(α) consists of ordinals generated from smaller terms using addition, multiplication, the Veblen hierarchy, and previous ψ values, following rules to ensure monotonicity and closure under smaller cardinals like Ω.[2] Starting from basic epsilon numbers, ψ(ε_1) yields the first epsilon fixed point beyond ε_0, initiating the hierarchy.[12] Subsequent steps ascend through Veblen-like levels: ψ(Ω) = Γ_0, the least fixed point of α ↦ φ_α(0); ψ(Ω ⋅ 2) builds the next level, and ψ(Ω · ω) marks transitions to higher hyperoperations.[12] Further iterations, such as ψ(Ω^ω) corresponding to extensions beyond the small Veblen ordinal, build nested fixed points of the extended Veblen function φ_β(γ), where φ_0(γ) = ω^γ and higher φ_β enumerate common fixed points.[1] These computations culminate at ψ(Ω) = Γ_0, the Feferman–Schütte ordinal, defined impredicatively as the least fixed point of α ↦ φ_α(0) extended via ψ, resolving the hierarchy's closure.[2] Equivalently, Γ_0 = \sup { \psi(\phi_\beta(0)) \mid \beta < \Gamma_0 }, where the supremum captures the impredicative loop by enumerating all prior ψ-collapsed Veblen terms below itself.[12] Beyond this, ψ(Γ_0) collapses to the least θ such that θ = ψ(θ), forming the first Mahlo-like fixed point in the notation but remaining within the predicative limit at Γ_0.[1]Extensions Beyond the Feferman–Schütte Ordinal
To extend the ordinal collapsing function ψ beyond the Feferman–Schütte ordinal Γ₀, computations incorporate nested collapsing mechanisms that generate higher fixed points in the hierarchy, such as Γ₁, by applying ψ to arguments like ε_{Γ₀+1}. This process defines Γ₁ as the least ordinal greater than Γ₀ that is closed under the ε operation and subsequent ψ evaluations, enabling the construction of multiple Γ levels through recursive nesting.[1] The progression involves introducing auxiliary cardinals for deeper collapsing: Ω₁ is defined as ψ(Ω), representing the first collapse beyond the base uncountable Ω, followed by higher Ωₙ obtained via transfinite iteration of this process. Computations of ψ(α) then proceed for arguments α < ε_{Ω_ω+1}, where Ω_ω denotes the limit of the Ωₙ sequence, allowing the function to enumerate ordinals that surpass the initial Γ hierarchy by layering collapses at each level.[12] Reaching the Bachmann–Howard ordinal (BHO) requires applying ψ to ε_{Ω+1}, yielding ψ(ε_{Ω+1}) = BHO, which captures the limit of collapsing operations at progressively more refined, Mahlo-like cardinal structures. The BHO itself satisfies the fixed-point equation \text{BHO} = \sup \{ \varepsilon_{\psi(\alpha)+1} \mid \alpha < \text{BHO} \}, representing the least upper bound of the ε fixed points enumerated under the collapsing action of ψ. This structure ensures the notation remains well-founded while extending to the proof-theoretic strength associated with second-order arithmetic.[1]Ordinal Notations and Base Representations
Ordinal collapsing functions, exemplified by Buchholz's ψ, facilitate the representation of large countable ordinals through a structured notation system that integrates collapsing to extend beyond traditional hierarchies like the Veblen functions, reaching up to the Bachmann-Howard ordinal. This system employs terms incorporating the ψ function to map uncountable or large ordinal arguments to countable outputs, ensuring the notations remain well-founded by enumerating ordinals in a recursive manner without circularity.[1] In this notation framework, ordinals are expressed using extended forms that resemble the Cantor normal form but incorporate collapsing via ψ, such as notations of the type ω[ψ(α)], where the bracketed ψ(α) denotes the collapsed value serving as an exponent or index in the base structure. This allows for compact representation of ordinals like ω raised to a collapsed power, preventing the notation from exceeding the targeted ordinal bound through the function's definitional minimization.[12] Base representations in these systems rely on hierarchies akin to the Hardy hierarchy, where fundamental sequences define iterative growth, or more directly on functions like φ_b(α), with b as a base ordinal indexing a normal function in the Veblen-style hierarchy. Specifically, φ_α(β) is defined as θ_α(̂α + β), where θ_α enumerates normal functions and ̂α is the minimal η such that the closure under addition reaches θ_α(η), providing a base for decomposing ordinals into sums and products within the notation.[1] The extended Cantor normal form underpins these base representations, expressing ordinals as α = ω^{β_1} · k_1 + ⋯ + ω^{β_n} · k_n with β_i < α and k_i finite, but with exponents β_i potentially including ψ-collapsed terms to handle impredicative extensions. This form ensures additive and multiplicative closure while integrating ψ to collapse inaccessible-like structures into the countable realm.[1] The notations encode the collapsing property of ψ to maintain well-foundedness up to the Bachmann-Howard ordinal by restricting arguments to a club set of ordinals below ψ(Λ), where Λ is a large limit, thereby guaranteeing that each term denotes a unique, smaller ordinal in the hierarchy. Uniqueness is enforced through the collapsing rules, which use the minimal enumeration principle in ψ's definition—ψ_α = min{β ∈ X : ∀ξ < α (K_ξ < β ⇒ ψ_ξ < β)}—to eliminate ambiguities and ensure strict monotonicity in the represented order.[1]Key Properties of ψ
The ordinal collapsing function \psi, in the standard example based on Buchholz's construction up to the Bachmann–Howard ordinal, is a normal function on its domain, meaning it is both strictly increasing and continuous at limit ordinals. Specifically, for ordinals \alpha < \beta, it holds that \psi(\alpha) < \psi(\beta), ensuring that the function preserves the order structure of the arguments while generating progressively larger ordinals in its range.[12] Additionally, at limit ordinals \lambda = \sup_{\xi < \lambda} \xi, continuity is satisfied by \psi(\lambda) = \sup_{\xi < \lambda} \psi(\xi), which allows the function to handle suprema without gaps, a property derived directly from the recursive enumeration of ordinals excluded from the collapsing sets.[12] These traits make \psi suitable for defining hierarchical ordinal notations that extend beyond the Veblen hierarchy. Fixed points of \psi, where \psi(\alpha) = \alpha, occur at specific large ordinals that close under the collapsing process, such as the least \varepsilon-number exceeding the previous fixed points in the hierarchy. For instance, in the initial segments, \psi(0) = \varepsilon_0, and subsequent fixed points arise as the smallest solutions to \alpha = \psi(\beta) for some \beta < \alpha, marking the points where the function stabilizes relative to its own iterations.[12] These fixed points delineate the boundaries of the ordinal hierarchies generated by \psi, with the Bachmann–Howard ordinal itself serving as a global fixed point in the extended system.[1] A fundamental collapsing property, often referred to as the collapsing lemma, states that \psi(\alpha) < \kappa for all countable ordinals \alpha, where \kappa is the base regular cardinal (such as the first uncountable ordinal \Omega_0 = \omega_1 in the simplest case). This lemma ensures that the function maps countable arguments to ordinals strictly below the inaccessible base, effectively "collapsing" the uncountable structure into the countable realm without exceeding the cardinal's cofinality.[12] In Buchholz's multi-base extension, this generalizes to \psi_\nu(\alpha) < \Omega_\nu for each level \nu, preserving the separation between countable notations and the underlying large cardinals.[1] The normalization property of \psi implies that \psi(\psi(\alpha)) = \psi(\alpha) for \alpha in the appropriate ranges below the fixed points, preventing inflationary growth when the function is composed with itself. This idempotence arises because \psi(\alpha) already lies within the club sets closed under the collapsing operation, so reapplying \psi yields no new exclusions.[12] Such normalization is crucial for maintaining unique representations in ordinal notations and ensuring the function's output remains within the intended countable bounds without unnecessary escalation.[1]Canonical Notation Conditions
In the context of the standard ordinal collapsing function \psi, a notation \tau is considered canonical if it is expressed in normal form and adheres to specific collapsing constraints that prevent redundant applications of \psi. Normal form requires that \tau be constructed using base ordinals and \psi in a way that avoids unnecessary nesting, such as ensuring that \psi(\alpha) is only applied where \alpha cannot be represented more simply without collapse. This ensures unique representations for ordinals up to the Bachmann–Howard ordinal (BHO). The primary conditions for canonicity include constraints on the arguments of \psi. For a term of the form \omega[\psi(\alpha)], \alpha must satisfy \alpha < \Omega, where \Omega is the first uncountable ordinal used in the collapsing mechanism, and \alpha must be built-from-below relative to the target ordinal to avoid dependencies that exceed the collapse level. Additionally, the notation must preclude cycles in dependency by requiring that all subterms of \alpha are strictly less than the ordinal denoted by \psi(\alpha), thereby maintaining a hierarchical structure without loops. These bounds and avoidance mechanisms guarantee that the notation remains within the countable ordinals while simulating higher cardinal structures.[14] Verification of a notation's canonicity involves a recursive process to confirm that \psi(\tau) denotes the intended ordinal without violating collapse constraints. This is achieved through a polynomial-time comparison algorithm that evaluates the notation in postfix form, checking lexicographical order and ensuring no subterm introduces a redundancy or exceeds the built-from-below condition. If the evaluation yields a consistent ordinal value matching the notation's intent and all constraints hold, the notation is verified as canonical. The relation to well-foundedness is fundamental, as canonical notations ensure that the dependency tree of the notation terminates below the BHO. By enforcing built-from-below constructions and strict inequalities in arguments, the system prevents infinite descending sequences, with well-foundedness provable in subsystems of second-order arithmetic for the standard case up to BHO. This termination property underpins the overall consistency of the ordinal hierarchy generated by \psi.[14]Specific Examples of Notations
One concrete example of the ordinal collapsing function ψ in the standard notation system is the representation of the Feferman–Schütte ordinal Γ₀ as ψ(Ω). This ordinal is the least upper bound of the finite Veblen hierarchy, and in the collapsing framework, it arises as the supremum of terms built using addition, multiplication, exponentiation, and previous ψ values below Ω, where Ω denotes the least uncountable ordinal. Expanded in base ω with collapsing, Γ₀ can be expressed as the limit of expressions like ωψ(Ω · n) for finite n, where the bracket notation β denotes the Veblen-like function φ_β(γ), illustrating how the collapsing "projects" uncountable structures into countable notations.[15] The Bachmann–Howard ordinal (BHO), the proof-theoretic ordinal of Kripke–Platek set theory, is denoted as ψ(ε_{Ω+1}), where ε_{Ω+1} is the least fixed point of the ε function beyond Ω. This collapses the structure at ε_{Ω+1} to the supremum of all ordinals constructible from smaller terms using the allowed operations, yielding the least ordinal closed under the extended Veblen hierarchy φ_α(β) for α < ε_{Ω+1}. Equivalently, BHO is the limit of the sequence defined by iterated ε applications up to ψ(ε_{Ω+1}) + 1, satisfying ε_{BHO + 1} = BHO as a fixed point.[12] A key computation in this notation system is ψ(ω^Ω) = φ_ω(0), which equals Γ₀. Here, the term breakdown proceeds as follows: the set of ordinals below ψ(ω^Ω) includes all finite Veblen functions φ_n(0) for n < ω, such as φ_1(0) = ε₀, φ_2(0) = ζ₀, and φ_3(0) = η₀, with the supremum φ_ω(0) being the least ordinal not attainable from these without invoking the collapse at ω^Ω. This demonstrates the impredicative nature, as ψ(ω^Ω) enumerates the first regular ordinal beyond the Veblen hierarchy. The canonical conditions ensure this term is valid by verifying no smaller ordinal satisfies the collapsing enumeration.[15] The following table illustrates small notations using ψ, starting from predicative values and extending to impredicative ones, showing the progression in Cantor normal form equivalents:| α | ψ(α) | Equivalent Representation |
|---|---|---|
| 0 | ε₀ | sup{ω, ω^ω, ω^(ω^ω), ...} |
| 1 | ε₁ | sup{ε₀, ε₀^ε₀, ε₀^(ε₀^ε₀), ...} |
| 2 | ε₂ | sup{ε₁, ε₁^ε₁, ...} |
| 3 | ε₃ | sup{ε₂, ε₂^ε₂, ...} |
| ω | ζ₀ | sup{ε_n : n < ω} |
| Ω | Γ₀ | φ_ω(0) |
| ε_{Ω+1} | BHO | sup{φ_ε_Ω(0), φ_ε_Ω+1(0), ...} |