Googology Wiki
Advertisement
Googology Wiki

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 FSes we refer to systems of FSes 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 system of FSes \(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\) or \(\{\alpha\}(n)\),[1] 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[citation needed] whether an ordinal hierarchy can be defined without using fundamental sequences. For \(\xi\in\textrm{Ord}\), let \(^{\mathbb N}\xi\) denote the set of functions mapping \(\mathbb N\) to \(\xi\). More explicitly, the problem concerns whether there is a model of ZF such that there exists an \(F : \)\(\,\,\omega_1\)\( \rightarrow (^{\mathbb{N}} \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}}(\omega_1))\) such that for all \(\alpha\), \(\sup(R) = \alpha\) where \(R\) is the range of \(S(\alpha)\).

Computable analogue

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 \(\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 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 \(\omega\). Examples of valid FS's are:

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

Expansion Rule

Not to be confused with Expansion.

As we clarified above, the notion of an expansion rule of a general notation does not admit an agreed-upon mathematical formulation. One typical mistake in googology is the confounding of a notation with an expansion rule with an ordinal notation. As a Japanese Googology Wiki user p進大好きbot has pointed out, those two notions are not equivalent at any rate.[5]

One important aspect of an ordinal notation is that every term canonically corresponds to the ordinal given as the order type. On the other hand, a term in a notation with an expansion rule does not necessarily correspond to an ordinal in a way compatible with the expansion. However, the correspondence is at least unique under a suitable formulation.

For example, the following is a formulation given by p進大好きbot.[6] Let \(T\) be a set. An expansion rule on \(T\) is a map \([] \colon T \times \mathbb{N} \to T\). Then the map \(o \colon T \to \omega_1\) satisfying the following is unique under mild assumptions:

  1. If \(t = t[n]\) for any \(n \in \mathbb{N}\), then \(o(t) = 0\).
  2. If \(t \neq t[0] = t[n]\) for any \(n \in \mathbb{N}\), then \(o(t) = o(t[0])+1\).
  3. Otherwise, then \(o(t) = \sup_{n \in \mathbb{N}} o(t[n])\).

We note that \(o\) is not even unique if we do not assume any mild assumptions. A similar chracterisation works also when we deal with an expansion rule formulated as a partial function \([] \colon T \times \mathbb{N} \to T\). For example, replace the conditions in the following way:

  1. If \((t,0)\) does not belong to the domain of \([]\), then \(o(t) = 0\).
  2. If \((t,n)\) belongs to the domain of \([]\) for any \(n \in \mathbb{N}\) and \(t[0] \neq t[1]\), then \(o(t) = \sup_{n \in \mathbb{N}} o(t[n])\).
  3. Otherwise, then \(o(t) = o(t[0])+1\).

It is also a typical mistake that \(o\) always exists, and there are many typical circular logics in googology on the termination of a given notation based on the wrong belief.[6][7]

Assuming the existence of \(o\) for a given notation, we can consider that a term "expresses" an ordinal. In that sense, we refer to "the corresponding ordinal" for a term in a notation which is not an ordinal notation, e.g. Bashicu matrix system.

See also

Sources

  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.
  5. p進大好きbot, Relation between an OCF and an Ordinal Notation/Notation with a System of Fundamental Sequences/Relation to an Ordinal Notation, Googology Wiki user blog.
  6. 6.0 6.1 p進大好きbot, Relation between an OCF and an Ordinal Notation/Notation with a System of Fundamental Sequences/Relation to a Notation with a Correspondence to Ordinals, Googology Wiki user blog.
  7. p進大好きbot, List of Common Failures in Googology/Circular Proof, Googology Wiki user blog.

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function)‎ · \(\omega_1^\mathfrak{Ch}\) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\zeta,\Sigma,\gamma\) (ordinals on infinite time Turing machine) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Buchholz's function · Jäger-Buchholz function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function
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}\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)

Advertisement