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 [math]\displaystyle{ \mathrm{\omega} 1 }[/math]. The n^th element of the fundamental sequence of [math]\displaystyle{ \beta }[/math] is commonly denoted [math]\displaystyle{ \alpha[n] }[/math], although it may be denoted [math]\displaystyle{ \alpha_n }[/math] or [math]\displaystyle{ \{\alpha\}(n) }[/math]. 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 [math]\displaystyle{ \varphi_\alpha }[/math], while the concept dates back to Hardy's 1904 attempt to construct a set of cardinality [math]\displaystyle{ \aleph_1 }[/math].

Definition

Given an ordinal [math]\displaystyle{ \alpha }[/math], a fundamental sequence for [math]\displaystyle{ \alpha }[/math] is a sequence [math]\displaystyle{ (\alpha[n])_{n\in\mathbb N} }[/math] such that [math]\displaystyle{ \forall(n\in\mathbb N)(\alpha[n]\lt \alpha) }[/math] and [math]\displaystyle{ \textrm{sup}\{\alpha[n]\mid n\in\mathbb N\}=\alpha }[/math]. 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 [math]\displaystyle{ \lt \varepsilon_0 }[/math].

• [math]\displaystyle{ \omega^{\alpha+1}[n]=\omega^\alpha\cdot(n+1) }[/math]
• [math]\displaystyle{ \omega^\alpha[n]=\omega^{\alpha[n]} }[/math] for limit ordinals [math]\displaystyle{ \alpha }[/math]
• [math]\displaystyle{ (\omega^{\alpha_1}+\ldots+\omega^{\alpha_k})[n]=\omega^{\alpha_1}+\ldots+(\omega^{\alpha_k}[n]) }[/math] for [math]\displaystyle{ \alpha_1 \geq \dots \geq \alpha_k }[/math].

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 [math]\displaystyle{ \phi_\alpha }[/math] 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 [math]\displaystyle{ \omega_1 }[/math]. 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 [math]\displaystyle{ \alpha }[/math] is said to have the Bachmann property if for all ordinals [math]\displaystyle{ \alpha,\beta }[/math] in the domain of the system and for all [math]\displaystyle{ n\in\mathbb N }[/math], [math]\displaystyle{ \alpha[n]\lt \beta\lt \alpha\implies\alpha[n]\lt \beta[0] }[/math]. If a system of fundamental sequences has the Bachmann property, all the functions in its associated fast-growing hierarchy are monotone, and [math]\displaystyle{ f_\alpha }[/math] eventually dominates [math]\displaystyle{ f_\beta }[/math] when [math]\displaystyle{ \alpha\lt \beta }[/math].