Misplaced Pages

Fundamental sequence (set theory)

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

In set theory, a mathematical discipline, a fundamental sequence is a cofinal sequence of ordinals all below a given limit ordinal. Depending on author, fundamental sequences may be restricted to ω-sequences only or permit fundamental sequences of length ω 1 {\displaystyle \mathrm {\omega } _{1}} . The n th {\displaystyle n^{\text{th}}} element of the fundamental sequence of α {\displaystyle \alpha } is commonly denoted α [ n ] {\displaystyle \alpha } , although it may be denoted α n {\displaystyle \alpha _{n}} or { α } ( n ) {\displaystyle \{\alpha \}(n)} . Additionally, some authors may allow fundamental sequences to be defined on successor ordinals. The term dates back to (at the latest) Veblen's construction of normal functions φ α {\displaystyle \varphi _{\alpha }} , while the concept dates back to Hardy's 1904 attempt to construct a set of cardinality ℵ 1 {\displaystyle \aleph _{1}} .

Definition

Given an ordinal α {\displaystyle \alpha } , a fundamental sequence for α {\displaystyle \alpha } is a sequence ( α [ n ] ) n ∈ N {\displaystyle (\alpha )_{n\in \mathbb {N} }} such that ∀ ( n ∈ N ) ( α [ n ] < α ) {\displaystyle \forall (n\in \mathbb {N} )(\alpha <\alpha )} and sup { α [ n ] ∣ n ∈ N } = α {\displaystyle {\textrm {sup}}\{\alpha \mid n\in \mathbb {N} \}=\alpha } . An additional restriction may be that the sequence of ordinals must be strictly increasing.

Examples

The following is a common assignment of fundamental sequences to all limit ordinals less than ε 0 {\displaystyle \varepsilon _{0}} .

  • ω α + 1 [ n ] = ω α ⋅ ( n + 1 ) {\displaystyle \omega ^{\alpha +1}=\omega ^{\alpha }\cdot (n+1)}
  • ω α [ n ] = ω α [ n ] {\displaystyle \omega ^{\alpha }=\omega ^{\alpha }} for limit ordinals α {\displaystyle \alpha }
  • ( ω α 1 + … + ω α k ) [ n ] = ω α 1 + … + ( ω α k [ n ] ) {\displaystyle (\omega ^{\alpha _{1}}+\ldots +\omega ^{\alpha _{k}})=\omega ^{\alpha _{1}}+\ldots +(\omega ^{\alpha _{k}})} for α 1 ≥ ⋯ ≥ α k {\displaystyle \alpha _{1}\geq \dots \geq \alpha _{k}} .

This is very similar to the system used in the Wainer hierarchy.

Usage

Fundamental sequences arise in some settings of definitions of large countable ordinals, definitions of hierarchies of fast-growing functions, and proof theory. Bachmann defined a hierarchy of functions ϕ α {\displaystyle \phi _{\alpha }} in 1950, providing a system of names for ordinals up to what is now known as the Bachmann–Howard ordinal, by defining fundamental sequences for namable ordinals below ω 1 {\displaystyle \omega _{1}} . This system was subsequently simplified by Feferman and Aczel to reduce the reliance on fundamental sequences.

The fast-growing hierarchy, Hardy hierarchy, and slow-growing hierarchy of functions are all defined via a chosen system of fundamental sequences up to a given ordinal. The fast-growing hierarchy is closely related to the Hardy hierarchy, which is used in proof theory along with the slow-growing hierarchy to majorize the provably computable functions of a given theory.

Additional conditions

A system of fundamental sequences up to α {\displaystyle \alpha } is said to have the Bachmann property if for all ordinals α , β {\displaystyle \alpha ,\beta } in the domain of the system and for all n ∈ N {\displaystyle n\in \mathbb {N} } , α [ n ] < β < α ⟹ α [ n ] < β [ 0 ] {\displaystyle \alpha <\beta <\alpha \implies \alpha <\beta } . If a system of fundamental sequences has the Bachmann property, all the functions in its associated fast-growing hierarchy are monotone, and f β {\displaystyle f_{\beta }} eventually dominates f α {\displaystyle f_{\alpha }} when α < β {\displaystyle \alpha <\beta } .

References

  1. ^ M. Rathjen, The Art of Ordinal Analysis (2006), pp. 9–10. Accessed 8 May 2023.
  2. ^ W. Buchholz, A survey on ordinal notations around the Bachmann-Howard ordinal (2017), p.2. Accessed 8 May 2023.
  3. ^ W. Buchholz, S. Wainer, Provably Computable Functions and the Fast Growing Hierarchy (1987), Contemporary Mathematics, vol. 65 (pp. 180–181).
  4. ^ A. Freund, F. Pakhomov, Short Proofs for Slow Consistency (2020). Accessed 8 May 2023.
  5. W. Buchholz, A. Cichon, A. Weiermann, A Uniform Approach to Fundamental Sequences and Hierarchies (1994), Mathematical Logic Quarterly, vol. 40, pp.273–285.
  6. O. Veblen, Continuous Increasing Functions of Finite and Transfinite Ordinals (1908).
  7. ^ H. J. Prömel, W. Thumser, B. Voigt, "Fast growing functions and Ramsey theorems" (1991), Discrete Mathematics vol. 95, pp. 341–358.
  8. ^ A. Weiermann, Classifying the Provably Total Functions of PA (2006), Bulletin of Symbolic Logic vol. 12 no. 2, pp. 177–190.
  9. J. Bridge, A Simplification of the Bachmann Method for Generating Large Countable Ordinals
  10. S. Feferman, The proof theory of classical and constructive inductive definitions. A 40 year saga, 1968-2008. (2008). Accessed 8 May 2023.
  11. T. Arai, A slow-growing analogue to Buchholz's proof (1991), Annals of Pure and Applied Logic vol. 54, pp. 101–120.
Categories: