Fundamental sequence (set theory)

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^[1] or permit fundamental sequences of length ${\displaystyle \mathrm {\omega } _{1}}$.^[2] The ${\displaystyle n^{\text{th}}}$ element of the fundamental sequence of ${\displaystyle \alpha }$ is commonly denoted ${\displaystyle \alpha [n]}$,^[2] although it may be denoted ${\displaystyle \alpha _{n}}$^[3] or ${\displaystyle \{\alpha \}(n)}$.^[4] Additionally, some authors may allow fundamental sequences to be defined on successor ordinals.^[5] 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 ${\displaystyle \aleph _{1}}$.^[6]

Definition

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

Examples

The following is a common assignment of fundamental sequences to all limit ordinals less than ${\displaystyle \varepsilon _{0}}$.^[8][4][3]

• ${\displaystyle \omega ^{\alpha +1}[n]=\omega ^{\alpha }\cdot (n+1)}$
• ${\displaystyle \omega ^{\alpha }[n]=\omega ^{\alpha [n]}}$ for limit ordinals ${\displaystyle \alpha }$
• ${\displaystyle (\omega ^{\alpha _{1}}+\ldots +\omega ^{\alpha _{k}})[n]=\omega ^{\alpha _{1}}+\ldots +(\omega ^{\alpha _{k}}[n])}$ for ${\displaystyle \alpha _{1}\geq \dots \geq \alpha _{k}}$.

This is very similar to the system used in the Wainer hierarchy.^[7]

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 ${\displaystyle \omega _{1}}$.^[9] This system was subsequently simplified by Feferman and Aczel to reduce the reliance on fundamental sequences.^[10]

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.^[8][11]

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 ${\displaystyle n\in \mathbb {N} }$, ${\displaystyle \alpha [n]<\beta <\alpha \implies \alpha [n]<\beta [0]}$. If a system of fundamental sequences has the Bachmann property, all the functions in its associated fast-growing hierarchy are monotone, and ${\displaystyle f_{\beta }}$ eventually dominates ${\displaystyle f_{\alpha }}$ when ${\displaystyle \alpha <\beta }$.^[7]