Wiki Googologie
Advertisement

Une séquence fondamentale est un concept important dans l'étude des hiérarchies ordinales. Si α est un ordinal limite de cofinalité ω, une séquence fondamentale pour α est une séquence monotone croissante de longueur ω constituée d'ordinaux dont le supremum est égal à α. En raison de la faible normalisation en théorie des ensembles, les définitions des séquences fondamentales valides varient. Certains auteurs utilisent la "borne supérieure la moins stricte" au lieu du "supremum", certains relâchent la condition de monotonicité pour n'exiger que des séquences non décroissantes, et certains autorisent même les séquences fondamentales pour les ordinaux successeurs.

En général, lorsque nous parlons de séquences fondamentales, nous faisons référence à des "systèmes" de séquences fondamentales qui génèrent ces séquences. Soit Lim to une classe de tous les ordinaux limites non nuls. Pour un ordinal limite μ de cofinalité ω, un système de séquences fondamentales S est une fonction sur μ∩Lim où chaque S(α) est une séquence fondamentale pour α. Si S a été établie comme la séquence fondamentale que nous utilisons, nous utilisons α[n] comme abréviation de S(α)(n). Les séquences sont toujours à indexation zéro, ainsi α[0] est le premier membre de la séquence. Certains auteurs ont utilisé αn ou {α}(n),[1] mais la plupart des articles modernes utilisent la notation entre crochets.

Dans ZF, il est impossible de montrer qu'il existe un système de séquences fondamentales qui fonctionne pour tous les ordinaux limites dénombrables, bien qu'avec l'axiome du choix nous puissions prouver de manière non constructive qu'un tel système existe. Malheureusement, une telle preuve constructive n'existe pas. En effet, l'axiome du choix est nécessaire pour cela.

Analogue calculable

In computable googology, we cannot directly use ordinals because Turing machines do not accept transfinite ordinals as inputs. Instead, we consider an analogue of a fundamental sequence for terms in a recursive notation, which is called an expansion rule or also a fundamental sequence widely in googology. For example, the ordinal notations associated to Buchholz's function are equipped with three distinct systems of fundamental sequences.[2][3][4] The meaning of a fundamental sequence for a term in an ordinal notation is the completely same as that of an ordinal, except for the use of the given recursive well-ordering instead of \(\in\). On the other hand, the meaning of a fundamental sequence for a term in a general notation is quite ambiguous.

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 α 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 Feferman's 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 ω. Examples of valid fundamental sequence's are:

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

Références

  1. M. Rathjen, Slow Consistency (p.3). Retrieved 2021-06-16.
  2. W. Buchholz, A New System of Proof-Theoretic Ordinal Functions, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 195--207.
  3. W. Buchholz, Relating ordinals to proofs in a perspicuous way, Reflections on the foundations of mathematics (Stanford, CA, 1998) 15 (2017): 37--59.
  4. Maksudov, Denis. The extension of Buchholz's functionTraveling To The Infinity. Retrieved 2017-05-18.
Advertisement