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 [n]} , 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])_{n\in \mathbb {N} }} such that ∀ ( n ∈ N ) ( α [ n ] < α ) {\displaystyle \forall (n\in \mathbb {N} )(\alpha [n]<\alpha )} and sup { α [ n ] ∣ n ∈ N } = α {\displaystyle {\textrm {sup}}\{\alpha [n]\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}[n]=\omega ^{\alpha }\cdot (n+1)}
ω α [ n ] = ω α [ n ] {\displaystyle \omega ^{\alpha }[n]=\omega ^{\alpha [n]}} for limit ordinals α {\displaystyle \alpha }
( ω α 1 + … + ω α k ) [ n ] = ω α 1 + … + ( ω α k [ n ] ) {\displaystyle (\omega ^{\alpha _{1}}+\ldots +\omega ^{\alpha _{k}})[n]=\omega ^{\alpha _{1}}+\ldots +(\omega ^{\alpha _{k}}[n])} 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.
… excerpt ends here. Continue reading the full article.
