🔄Theory of Recursive Functions Unit 11 – Recursive Ordinals and Notations

What are Recursive Ordinals?

• Recursive ordinals extend the concept of ordinal numbers beyond the finite and transfinite realms
• They are defined using recursive functions and notations, allowing for the representation of extremely large ordinals
• Recursive ordinals capture the idea of "infinite iteration" of ordinal operations, such as exponentiation and the Veblen hierarchy
• The class of recursive ordinals is closed under ordinal arithmetic operations and forms a proper class
• Recursive ordinals play a crucial role in proof theory and the study of formal systems
  • They are used to measure the strength and consistency of mathematical theories
  • Recursive ordinals provide a way to compare the proof-theoretic strength of different axiomatic systems

Fundamentals of Ordinal Notation

• Ordinal notations are symbolic representations used to denote specific ordinal numbers
• The most common ordinal notation is the Cantor normal form, which expresses an ordinal as a sum of powers of $\omega$
• Ordinal notations can be extended to represent recursive ordinals using various recursive functions and hierarchies
• The Church-Kleene ordinal $\omega_1^{CK}$ is the smallest non-recursive ordinal and marks the limit of recursive ordinal notations
• Fundamental sequences are used to assign notations to limit ordinals and define recursive hierarchies
  • A fundamental sequence for a limit ordinal $\alpha$ is a sequence $(\alpha[n])_{n<\omega}$ of ordinals converging to $\alpha$
• Recursive ordinal notations are well-founded, meaning there is no infinite descending sequence of ordinals

Cantor Normal Form

• The Cantor normal form represents an ordinal $\alpha$ as a sum of powers of $\omega$: $\alpha = \omega^{\beta_1} \cdot k_1 + \omega^{\beta_2} \cdot k_2 + \cdots + \omega^{\beta_n} \cdot k_n$
  • $\beta_1 > \beta_2 > \cdots > \beta_n$ are ordinals and $k_1, k_2, \ldots, k_n$ are positive integers
• Every ordinal has a unique Cantor normal form representation
• The Cantor normal form allows for the comparison and arithmetic manipulation of ordinals
• Ordinal exponentiation is a key operation in the Cantor normal form
  • $\omega^\alpha$ represents the $\alpha$-th infinite cardinal number
• The Cantor normal form can be extended to represent epsilon numbers $\varepsilon_\alpha$ using epsilon notation

Recursive Ordinal Arithmetic

• Recursive ordinal arithmetic extends the operations of addition, multiplication, and exponentiation to recursive ordinals
• Ordinal addition is defined as the concatenation of well-ordered sets
  • $\alpha + \beta$ represents the ordinal obtained by appending a copy of $\beta$ after $\alpha$
• Ordinal multiplication is defined as the lexicographic order on the Cartesian product of well-ordered sets
  • $\alpha \cdot \beta$ represents the ordinal obtained by replacing each element of $\beta$ with a copy of $\alpha$
• Ordinal exponentiation is defined recursively using the Cantor normal form and fundamental sequences
• The arithmetic operations on recursive ordinals satisfy the usual properties, such as associativity and distributivity
• Recursive ordinal arithmetic is used to define and manipulate large ordinal hierarchies and notations

Ordinal Hierarchies and Classification

• Ordinal hierarchies are families of recursive functions used to generate and classify large ordinals
• The Veblen hierarchy $\varphi_\alpha$ is a transfinite extension of the Cantor normal form
  • It is defined using a two-argument function $\varphi_\alpha(\beta)$ that enumerates the fixed points of the previous functions
• The Feferman-Schütte ordinal $\Gamma_0$ is the smallest ordinal that cannot be expressed using the Veblen hierarchy
• The Bachmann-Howard ordinal $\psi(\varepsilon_{\Omega+1})$ is a large countable ordinal obtained using the collapsing function $\psi$
• The extended Veblen hierarchy and the Buchholz hierarchy provide notations for even larger ordinals
• Ordinal hierarchies are used to measure the strength of formal theories and classify their proof-theoretic ordinals

Notations for Large Recursive Ordinals

• Various notations and naming schemes are used to represent and study large recursive ordinals
• The Madore naming scheme assigns names to large countable ordinals using a recursive system of abbreviations
  • It extends the Veblen hierarchy and provides names for ordinals up to the Bachmann-Howard ordinal and beyond
• The Takeuti-Feferman-Buchholz (TFB) ordinal notation system is based on the extended Veblen hierarchy
  • It uses a ternary Veblen function $\varphi_{\alpha}(\beta,\gamma)$ to generate large ordinals
• The Rathjen $\Psi$ function is a powerful notation system that extends the Buchholz hierarchy
  • It allows for the representation of extremely large ordinals and is used in the study of strong axiom systems
• Ordinal collapsing functions, such as the $\psi$ function and the $\theta$ function, are used to define large ordinal notations
  • They "collapse" a given ordinal notation to a smaller one while preserving its essential properties

Applications in Proof Theory

• Recursive ordinals and notations play a central role in proof theory and the study of formal systems
• The proof-theoretic ordinal of a theory is the smallest recursive ordinal that cannot be proved to be well-founded within the theory
  • It measures the strength and consistency of the theory
• Recursive ordinals are used to establish the consistency and independence of mathematical statements
  • Gentzen's consistency proof for Peano arithmetic uses transfinite induction up to the ordinal $\varepsilon_0$
• Ordinal analysis is a technique that assigns recursive ordinals to theories to compare their strength
  • It involves the use of ordinal notations and collapsing functions to extract ordinal information from proofs
• Recursive ordinals are used in the study of fast-growing hierarchies and the classification of computable functions
• Ordinal notations provide a way to define and study subrecursive hierarchies, such as the Hardy hierarchy and the Wainer hierarchy

Challenges and Open Problems

• The study of recursive ordinals and notations presents several challenges and open problems
• The continuum hypothesis and its relationship to recursive ordinals remain unresolved
  • It is unknown whether there exist recursive ordinals between $\omega_1^{CK}$ and $\omega_1$, the first uncountable ordinal
• The exact relationship between the Church-Kleene ordinal $\omega_1^{CK}$ and the proof-theoretic ordinals of certain theories is still being investigated
• Developing efficient algorithms and computational methods for working with large recursive ordinals is an ongoing challenge
• Extending ordinal notations and hierarchies to even larger ordinals and exploring their properties is an active area of research
• The role of recursive ordinals in the foundations of mathematics and the consistency of strong axiom systems continues to be a subject of study
  • The search for a "natural" axiomatization of the recursive ordinals is an open problem