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 . The nth element of the fundamental sequence of is commonly denoted , although it may be denoted or . 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 , while the concept dates back to Hardy's 1904 attempt to construct a set of cardinality .
Definition
Given an ordinal , a fundamental sequence for is a sequence such that and . 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 .
for limit ordinals
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 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 . 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 recursive functions of a given theory.
Additional conditions
A system of fundamental sequences up to is said to have the Bachmann property if for all ordinals in the domain of the system and for all , . If a system of fundamental sequences has the Bachmann property, all the functions in its associated fast-growing hierarchy are monotone, and eventually dominates when .