11.2 Recursive ordinals

Recursive ordinals extend natural numbers into the transfinite realm, allowing us to represent and reason about infinite sequences. They're crucial in analyzing the complexity and termination of recursive functions, providing a framework for understanding infinite well-ordered sets.

These ordinals are defined using the successor function and include limit ordinals, which represent the supremum of infinite sequences. The Cantor normal form offers a unique representation, while various arithmetic operations like addition and multiplication are defined recursively, preserving well-ordering properties.

Definition of recursive ordinals

• Recursive ordinals are a generalization of the natural numbers that extend the concept of ordinal numbers into the transfinite realm
• They provide a way to represent and reason about infinite sequences and well-ordered sets in the context of recursive functions and computability theory
• Recursive ordinals are a fundamental concept in the study of the Theory of Recursive Functions, as they allow for the analysis of the complexity and termination properties of recursive functions

Ordinal numbers vs natural numbers

Top images from around the web for Ordinal numbers vs natural numbers

• 

  Number Sets View original

  Is this image relevant?

• 

  set theory - Visualizations of ordinal numbers - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  elementary set theory - In a Venn diagram, where are other number sets located? - Mathematics ... View original

  Is this image relevant?

• 

  Number Sets View original

  Is this image relevant?

• 

  set theory - Visualizations of ordinal numbers - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 3

Top images from around the web for Ordinal numbers vs natural numbers

• 

  Number Sets View original

  Is this image relevant?

• 

  set theory - Visualizations of ordinal numbers - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  elementary set theory - In a Venn diagram, where are other number sets located? - Mathematics ... View original

  Is this image relevant?

• 

  Number Sets View original

  Is this image relevant?

• 

  set theory - Visualizations of ordinal numbers - Mathematics Stack Exchange View original

  Is this image relevant?

1 of 3

• Ordinal numbers extend the concept of natural numbers to include transfinite numbers, which represent the order types of well-ordered sets
• While natural numbers represent finite quantities, ordinal numbers can represent both finite and infinite quantities
• Ordinal numbers maintain the well-ordering property, meaning that every non-empty set of ordinals has a least element (unlike the real numbers)

Recursive definition using successor function

• Recursive ordinals are defined using the successor function $S(\alpha) = \alpha + 1$, where $\alpha$ is an ordinal
• The successor function generates the next ordinal after $\alpha$ by adding one to it
• The recursive definition of ordinals starts with the base case $0$ and then applies the successor function to generate the next ordinal:
  • $0$ is an ordinal
  • If $\alpha$ is an ordinal, then $S(\alpha)$ is an ordinal

Limit ordinals and supremum

• Limit ordinals are ordinals that cannot be obtained by applying the successor function to any other ordinal
• They represent the supremum (least upper bound) of an infinite sequence of ordinals
• The first limit ordinal is $\omega$, which represents the order type of the natural numbers
• For any infinite sequence of ordinals $\alpha_1, \alpha_2, \alpha_3, \ldots$, there exists a limit ordinal $\lambda$ that is the supremum of the sequence, denoted as $\lambda = \sup\{\alpha_1, \alpha_2, \alpha_3, \ldots\}$

Representation of recursive ordinals

Cantor normal form

• The Cantor normal form is a unique representation of ordinals using a sum of powers of $\omega$
• Every ordinal $\alpha$ can be uniquely written as $\alpha = \omega^{\beta_1} \cdot k_1 + \omega^{\beta_2} \cdot k_2 + \ldots + \omega^{\beta_n} \cdot k_n$, where $\beta_1 > \beta_2 > \ldots > \beta_n$ are ordinals and $k_1, k_2, \ldots, k_n$ are natural numbers
• The Cantor normal form allows for the comparison and arithmetic of ordinals using their unique representations

Natural sum of ordinals

• The natural sum of ordinals, denoted by $\alpha \oplus \beta$, is a way to add ordinals that preserves the well-ordering property
• It is defined recursively as:
  • $\alpha \oplus 0 = \alpha$
  • $\alpha \oplus S(\beta) = S(\alpha \oplus \beta)$
  • $\alpha \oplus \lambda = \sup\{\alpha \oplus \gamma : \gamma < \lambda\}$ for limit ordinals $\lambda$
• The natural sum is commutative, associative, and compatible with the order relation on ordinals

Hessenberg sum of ordinals

• The Hessenberg sum, also known as the modified natural sum, is another way to add ordinals that preserves the well-ordering property
• It is denoted by $\alpha \boxplus \beta$ and is defined recursively as:
  • $\alpha \boxplus 0 = \alpha$
  • $\alpha \boxplus S(\beta) = S(\alpha) \boxplus \beta$
  • $\alpha \boxplus \lambda = \sup\{\alpha \boxplus \gamma : \gamma < \lambda\}$ for limit ordinals $\lambda$
• The Hessenberg sum is not commutative but is associative and compatible with the order relation on ordinals

Arithmetic of recursive ordinals

Ordinal addition

• Ordinal addition extends the concept of natural sum to all ordinals, including transfinite ones
• It is defined recursively using the natural sum:
  • $\alpha + 0 = \alpha$
  • $\alpha + S(\beta) = S(\alpha + \beta)$
  • $\alpha + \lambda = \sup\{\alpha + \gamma : \gamma < \lambda\}$ for limit ordinals $\lambda$
• Ordinal addition is associative and left-distributive over the natural sum, but not commutative in general

Ordinal multiplication

• Ordinal multiplication extends the concept of natural multiplication to all ordinals
• It is defined recursively as:
  • $\alpha \cdot 0 = 0$
  • $\alpha \cdot S(\beta) = \alpha \cdot \beta + \alpha$
  • $\alpha \cdot \lambda = \sup\{\alpha \cdot \gamma : \gamma < \lambda\}$ for limit ordinals $\lambda$
• Ordinal multiplication is associative, left-distributive over ordinal addition, and compatible with the order relation on ordinals, but not commutative in general

Ordinal exponentiation

• Ordinal exponentiation extends the concept of natural exponentiation to all ordinals
• It is defined recursively as:
  • $\alpha^0 = 1$
  • $\alpha^{S(\beta)} = \alpha^\beta \cdot \alpha$
  • $\alpha^\lambda = \sup\{\alpha^\gamma : \gamma < \lambda\}$ for limit ordinals $\lambda$
• Ordinal exponentiation is right-distributive over ordinal multiplication and compatible with the order relation on ordinals, but not associative or commutative in general

Properties of recursive ordinals

Well-ordering of recursive ordinals

• Recursive ordinals are well-ordered, meaning that every non-empty set of recursive ordinals has a least element
• The well-ordering property allows for the use of transfinite induction and recursion on ordinals
• The order relation on recursive ordinals is transitive, antisymmetric, and total, making it a linear order

Transfinite induction on recursive ordinals

• Transfinite induction is a proof technique that extends the principle of mathematical induction to well-ordered sets, including recursive ordinals
• To prove a property $P(\alpha)$ holds for all recursive ordinals $\alpha$, it suffices to show:
  • $P(0)$ holds (base case)
  • If $P(\beta)$ holds for all $\beta < \alpha$, then $P(\alpha)$ holds (inductive step)
• Transfinite induction is a powerful tool for proving properties of recursive ordinals and the functions defined on them

Fixed points of normal functions

• A normal function is a function $f$ from ordinals to ordinals that is strictly increasing and continuous (preserves suprema of increasing sequences)
• A fixed point of a normal function $f$ is an ordinal $\alpha$ such that $f(\alpha) = \alpha$
• Every normal function has arbitrarily large fixed points, a property known as the fixed-point theorem for normal functions
• The existence of fixed points of normal functions is a crucial property in the study of recursive ordinals and their applications in proof theory

Countable ordinals

Church-Kleene ordinal as least non-recursive ordinal

• The Church-Kleene ordinal, denoted by $\omega_1^{CK}$, is the least non-recursive ordinal
• It is the supremum of the set of recursive ordinals, which are ordinals that can be represented by a recursive well-ordering of the natural numbers
• The Church-Kleene ordinal represents the limit of the expressive power of recursive functions and is a key concept in the study of hyperarithmetical hierarchies and degrees of unsolvability

Recursive approximations of countable ordinals

• Countable ordinals are ordinals with cardinality less than or equal to $\aleph_0$ (the cardinality of the natural numbers)
• While not all countable ordinals are recursive, they can be approximated by recursive ordinals in the following sense:
  • For every countable ordinal $\alpha$, there exists a recursive ordinal $\gamma$ such that $\alpha \leq \gamma$
  • The set of recursive ordinals is cofinal in the set of countable ordinals
• Recursive approximations of countable ordinals play a role in the study of admissible ordinals and the constructible universe in set theory

Applications of recursive ordinals

Termination proofs using ordinal assignments

• Ordinal assignments are a technique for proving the termination of recursive functions or programs
• The idea is to assign an ordinal to each state of the computation in such a way that the ordinal decreases with each step of the computation
• If the ordinal assignment is well-founded (has no infinite descending sequences), then the computation must terminate
• Ordinal assignments provide a powerful tool for analyzing the termination properties of recursive functions and algorithms

Ordinal analysis of formal theories

• Ordinal analysis is a branch of proof theory that studies the strength of formal theories by assigning ordinals to their proof-theoretic properties
• The proof-theoretic ordinal of a theory is the least ordinal that cannot be proved to be well-ordered within the theory
• Ordinal analysis provides a way to compare the strength of different formal theories and to establish consistency results and independence proofs
• Recursive ordinals play a central role in ordinal analysis, as they are used to calibrate the strength of theories and to construct hierarchies of formal systems

Proof-theoretic ordinals of axiomatic systems

• The proof-theoretic ordinal of an axiomatic system is a measure of its strength in terms of the ordinals that can be proved to be well-ordered within the system
• Examples of proof-theoretic ordinals for some well-known axiomatic systems:
  • Peano Arithmetic (PA): $\varepsilon_0$
  • Kripke-Platek set theory (KP): $\Gamma_0$
  • Second-order arithmetic ($Z_2$): $\Gamma_0$
  • Zermelo-Fraenkel set theory (ZF): $\Psi_0(\Omega_\Omega)$
• The study of proof-theoretic ordinals provides insights into the relative consistency and independence of mathematical statements and the limits of formal reasoning