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 .[2] The
element of the fundamental sequence of
is commonly denoted
,[2] although it may be denoted
[3] or
.[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
, while the concept dates back to Hardy's 1904 attempt to construct a set of cardinality
.[6]
Given an ordinal , a fundamental sequence for
is a sequence
such that
and
.[1] An additional restriction may be that the sequence of ordinals must be strictly increasing.[7]
The following is a common assignment of fundamental sequences to all limit ordinals less than .[8][4][3]
This is very similar to the system used in the Wainer hierarchy.[7]
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
.[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]
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
.[7]