A fundamental sequence (FS for short) is an important concept in the study of ordinal hierarchies. If \(\alpha\) is a limit ordinal with cofinality \(\omega\), a fundamental sequence for \(\alpha\) is a monotonically increasing sequence of length \(\omega\) consisting of ordinals, supremum of which is equal to \(\alpha\). Due to poor standardization in set theory, definitions of valid FS's vary. Some authors use "least strict upper bound" instead of "supremum," some relax the monotonicity condition to only require nondecreasing sequences, and some even allow fundamental sequences for successor ordinals.

Typically when we speak of FS's we refer to systems of FS's that generate these sequences. Let \(\text{Lim}\) to be a class of all non-zero limit ordinals. For a limit ordinal \(\mu\) with cofinality \(\omega\), a fundamental sequence \(S\) is a function over \(\mu \cap \text{Lim}\) where each \(S(\alpha)\) is a fundamental sequence for \(\alpha\). If \(S\) has been established as the fundamental sequence we are using, we use \(\alpha[n]\) as an abbreviation for \(S(\alpha)(n)\). Sequences are always zero-indexed, so \(\alpha[0]\) is the first member of the sequence. Some authors have used \(\alpha_n\), but most modern papers use the square-bracket notation.

In ZF, it is impossible to show that there exists an FS system that works for all countable limit ordinals, although with the axiom of choice we can nonconstructively prove that such a system exists. Unfortunately, there is no such constructive proof. Indeed, axiom of choice is necessary for this.

It is an open problem whether an ordinal hierarchy can be defined without using fundamental sequences. More explicitly, the problem concerns whether there is a model of ZF such that there exists an \(F : \omega_1 \rightarrow (\mathbb{N} \rightarrow \mathbb{N})\) where for all \(\alpha > \beta\), \(F(\alpha)\) eventually outgrows \(F(\beta)\), but there does not exist an \(S: \omega_1 \cap \text{Lim} \rightarrow (\mathbb{N} \rightarrow \omega_1)\) such that for all \(\alpha\), \(\sup(R) = \alpha\) where \(R\) is the range of \(S(\alpha)\).

Examples of fundamental sequences

Fundamental sequences for limit ordinals \(\lambda \le \varepsilon_0\):

  • \(\omega[n] = n\),
  • \(\omega^{\alpha + 1}[n] = \omega^\alpha n\) (where \(\omega^\alpha n = \omega^\alpha + \omega^\alpha + \cdots + \omega^\alpha + \omega^\alpha\) with n \(\omega^\alpha\)'s),
  • \(\omega^{\alpha}[n] = \omega^{\alpha[n]}\) if and only if \(\alpha\) is a limit ordinal,
  • \((\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_{k - 1}} + \omega^{\alpha_k})[n] = \omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_{k - 1}} + \omega^{\alpha_k}[n]\), where \(\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_{k - 1} \geq \alpha_k\),
  • \(\varepsilon_0[0] = 0\) and \(\varepsilon_0[n + 1] = \omega^{\varepsilon_0[n]}\).

Fundamental sequences for the Veblen functions \(\varphi_\beta(\gamma)\):

  • \((\varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k))[n]=\varphi_{\beta_1}(\gamma_1) + \cdots + \varphi_{\beta_{k-1}}(\gamma_{k-1}) + (\varphi_{\beta_k}(\gamma_k) [n])\), where \(\varphi_{\beta_1}(\gamma_1) \ge \varphi_{\beta_2}(\gamma_2) \ge \cdots \ge \varphi_{\beta_k}(\gamma_k)\) and \(\gamma_m < \varphi_{\beta_m}(\gamma_m)\) for \(m \in \{1,2,...,k\}\),
  • \(\varphi_0(\gamma)=\omega^{\gamma}\) and \(\varphi_0(\gamma+1) [n] = \omega^{\gamma} n\),
  • \(\varphi_{\beta+1}(0) [0] = 0 \) and \(\varphi_{\beta+1}(0) [n+1] = \varphi_{\beta}(\varphi_{\beta+1}(0) [n]) \),
  • \(\varphi_{\beta+1}(\gamma+1) [0] = \varphi_{\beta+1}(\gamma)+1 \,\) and \(\varphi_{\beta+1}(\gamma+1) [n+1] = \varphi_{\beta} (\varphi_{\beta+1}(\gamma+1) [n]) \),
  • \(\varphi_{\beta}(\gamma) [n] = \varphi_{\beta}(\gamma [n])\) for a limit ordinal \(\gamma<\varphi_\beta(\gamma)\),
  • \(\varphi_{\beta}(0) [n] = \varphi_{\beta [n]}(0)\) for a limit ordinal \(\beta<\varphi_\beta(0)\),
  • \(\varphi_{\beta}(\gamma+1) [n] = \varphi_{\beta [n]}(\varphi_{\beta}(\gamma)+1)\) for a limit ordinal \(\beta\).

Veblen's function can be presented as a two-argument function \(\varphi_\beta(\gamma)=\varphi(\beta,\gamma)\).

Note: \(\varphi(0,\gamma)=\omega^\gamma\), \(\varphi(1,\gamma)=\varepsilon_\gamma\), \(\varphi(2,\gamma)=\zeta_\gamma\) and \(\varphi(3,\gamma)=\eta_\gamma\).

Fundamental sequences for the Γ function:

  • \(\Gamma_0 [0] = 0 \) and \(\Gamma_0 [n+1] = \varphi_{\Gamma_0 [n]} (0) \),
  • \(\Gamma_{\beta+1} [0] = \Gamma_{\beta} + 1 \) and \(\Gamma_{\beta+1} [n+1] = \varphi_{\Gamma_{\beta+1} [n]} (0) \),
  • \(\Gamma_{\beta} [n] = \Gamma_{\beta [n]} \) for a limit ordinal \(\beta < \Gamma_{\beta} \).

Fundamental sequences for theta-function:

  • \(\theta(\alpha+\Omega,0)[0] = \theta(\alpha,0)\),
  • \(\theta(\alpha+\Omega,\beta+1)[0] = \theta(\alpha+\Omega,\beta)\),
  • \(\theta(\alpha+\Omega,\beta)[n+1] = \theta(\alpha+\theta(\alpha+\Omega,\beta)[n],\beta)\),
  • \(\theta(\alpha \cdot \Omega,0)[0] = \theta(\alpha,0)\),
  • \(\theta(\alpha \cdot \Omega,\beta+1)[0] = \theta(\alpha \cdot \Omega,\beta)\),
  • \(\theta(\alpha \cdot \Omega,\beta)[n+1] = \theta(\alpha \cdot \theta(\alpha \cdot \Omega,\beta)[n],\beta)\),
  • \(\theta(\alpha^{\Omega},0)[0] = \theta(\alpha,0)\),
  • \(\theta(\alpha^{\Omega},\beta+1)[0] = \theta(\alpha^{\Omega},\beta)\),
  • \(\theta(\alpha^{\Omega},\beta)[n+1] = \theta(\alpha^{\theta(\alpha^{\Omega},\beta)[n]},\beta)\).

Note: The theta-function is shown in the two-argument version \(\theta(\alpha, \beta)=\theta_\alpha(\beta)\), if \(\beta=0\) it can be abbreviated as \(\theta(\alpha)=\theta(\alpha,0)\), the theta function is an extension of the two-argument Veblen function, for countable arguments theta-function is equal to Veblen function \(\theta(\alpha, \beta)=\varphi(\alpha, \beta)\) and has same fundamental sequences, \(\Omega\) is an uncountable ordinal and \(\theta(\Omega,0)=\Gamma_0\).

Fundamental sequences can be defined even for uncountable ordinals if they have cofinality \(\omega\). Examples of valid FS's are:

  • \((\omega_1+\omega)[n] = \omega_1+n\)
  • \((\omega_\omega)[n] = \omega_n\).

See also

Ordinals, ordinal analysis and set theory

Basics: cardinal numbers · normal function · ordinal notation · ordinal numbers · fundamental sequence · ordinal collapsing function · transfinite induction
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\Gamma_0\) · \(\vartheta(\Omega^3)\) · \(\vartheta(\Omega^\omega)\) · \(\vartheta(\Omega^\Omega)\) · \(\vartheta(\varepsilon_{\Omega + 1}) = \psi(\Omega_2)\) · \(\psi(\Omega_\omega)\) · \(\psi(\varepsilon_{\Omega_\omega + 1})\) · \(\psi(\psi_I(0))\)‎ · \(\omega_1^\mathfrak{Ch}\) · \(\omega_1^\text{CK}\) · \(\omega_\alpha^\text{CK}\) · \(\lambda,\zeta,\Sigma,\gamma\) · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal collapsing functions Madore · Buchholz · Jäger
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal
Classes: \(V\) · \(L\) · \(\textrm{On}\) · Class (set theory)
Other concepts: Veblen function · absolute infinity

Community content is available under CC-BY-SA unless otherwise noted.