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 [math]\displaystyle{ \mathrm{\omega} 1 }[/math].[2] The nth element of the fundamental sequence of [math]\displaystyle{ \beta }[/math] is commonly denoted [math]\displaystyle{ \alpha[n] }[/math],[2] although it may be denoted [math]\displaystyle{ \alpha_n }[/math][3] or [math]\displaystyle{ \{\alpha\}(n) }[/math].[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 [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].[6]
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].[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 [math]\displaystyle{ \lt \varepsilon_0 }[/math].[8][4][3]
- [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.[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 [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].[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 [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].[7]
References
- ↑ 1.0 1.1 M. Rathjen, The Art of Ordinal Analysis (2006), pp. 9–10. Accessed 8 May 2023.
- ↑ 2.0 2.1 W. Buchholz, A survey on ordinal notations around the Bachmann-Howard ordinal (2017), p.2. Accessed 8 May 2023.
- ↑ 3.0 3.1 W. Buchholz, S. Wainer, Provably Computable Functions and the Fast Growing Hierarchy (1987), Contemporary Mathematics, vol. 65 (pp. 180–181).
- ↑ 4.0 4.1 A. Freund, F. Pakhomov, Short Proofs for Slow Consistency (2020). Accessed 8 May 2023.
- ↑ W. Buchholz, A. Cichon, A. Weiermann, A Uniform Approach to Fundamental Sequences and Hierarchies (1994), Mathematical Logic Quarterly, vol. 40, pp.273–285.
- ↑ O. Veblen, Continuous Increasing Functions of Finite and Transfinite Ordinals (1908).
- ↑ 7.0 7.1 7.2 H. J. Prömel, W. Thumser, B. Voigt, "Fast growing functions and Ramsey theorems" (1991), Discrete Mathematics vol. 95, pp. 341–358.
- ↑ 8.0 8.1 A. Weiermann, Classifying the Provably Total Functions of PA (2006), Bulletin of Symbolic Logic vol. 12 no. 2, pp. 177–190.
- ↑ J. Bridge, A Simplification of the Bachmann Method for Generating Large Countable Ordinals
- ↑ S. Feferman, The proof theory of classical and constructive inductive definitions. A 40 year saga, 1968-2008. (2008). Accessed 8 May 2023.
- ↑ T. Arai, A slow-growing analogue to Buchholz's proof (1991), Annals of Pure and Applied Logic vol. 54, pp. 101–120.
![]() | Original source: https://en.wikipedia.org/wiki/Fundamental sequence (set theory).
Read more |