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 or permit fundamental sequences of length $\mathrm {\omega } _{1}$. The n^th element of the fundamental sequence of $\beta$ is commonly denoted $\alpha [n]$, although it may be denoted $\alpha _{n}$ or $\{\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 $\varphi _{\alpha }$, while the concept dates back to Hardy's 1904 attempt to construct a set of cardinality $\aleph _{1}$.

Definition

Given an ordinal $\alpha$, a fundamental sequence for $\alpha$ is a sequence $(\alpha [n])_{n\in \mathbb {N} }$ such that $\forall (n\in \mathbb {N} )(\alpha [n]<\alpha )$ and ${\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 $<\varepsilon _{0}$.

• $\omega ^{\alpha +1}[n]=\omega ^{\alpha }\cdot (n+1)$
• $\omega ^{\alpha }[n]=\omega ^{\alpha [n]}$ for limit ordinals $\alpha$
• $(\omega ^{\alpha _{1}}+\ldots +\omega ^{\alpha _{k}})[n]=\omega ^{\alpha _{1}}+\ldots +(\omega ^{\alpha _{k}}[n])$ for $\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 $\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 $\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 $\alpha$ is said to have the Bachmann property if for all ordinals $\alpha ,\beta$ in the domain of the system and for all $n\in \mathbb {N}$, $\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 $f_{\beta }$ eventually dominates $f_{\alpha }$ when $\alpha <\beta$.