Googology Wiki
Advertisement
Googology Wiki

A derivative in set theory is a fundamental notion to diagonalise a subclass of \(\textrm{On}\). Readers should not confound it with the derivation in calculus.

Definition

Normal functions are subject to an important property given by an extension of Kleene's fixed point theorem, which states that a normal function has arbitrarily large fixed points. The derivative \(f'\) of an ordinal function \(f\) is defined as the enumerating function of the fixed points of \(f\)[1], so we can say that every normal function has a derivative. Not only this, but the derivative of a normal function is itself a normal function — so every normal function also has a second derivative, third derivative, etc. Even further, the procedure can be iterated transfinitely (by taking the common fixed points of lower derivatives) and we will always have normal functions.

The enumeration function \(\text{enum}[X]\) of a subclass \(X \subset \text{On}\) is normal if and only \(X\) is a closed proper class, and every normal function is obtained in this way. For example, the base function \(\alpha \mapsto \omega^{\alpha}\) is the enueration function of the closed proper class \(\text{AP}\) of additive principal numbers, and the base function \(\alpha \mapsto \aleph_{1+\alpha}\) is the enumeration function of the closed proper class \(\text{Card}\) of uncountable cardinals.

Examples

The above two concepts form the basis of the Veblen hierarchy \(\varphi\), which is created from transfinite derivatives of the function \(\alpha \mapsto \omega^\alpha\). A quite similar variant used in Rathjen's ordinal collapsing function is the function \(\Phi\), which is created from in transfinite derivatives of the function \(\alpha \mapsto \aleph_{1+\alpha}\). For example, \(\Phi(1,0)\) is the least \(\Omega\)-fixed point.

The viewpoint from the derivation gives a quite simple description of the definitions of those functions. For example, \(\varphi \colon \text{On} \times \text{On} \to \text{On}\) is defined as \begin{eqnarray*} \varphi(\alpha,\beta) := \text{enum}[\{\gamma \in \text{AP} \mid \forall \alpha' \in \alpha, \varphi(\alpha',\gamma) = \gamma\}](\beta) \end{eqnarray*} by transfinite recursion on \(\alpha\) without derivation, but can be simply described as "\(\lambda\beta.\varphi(\alpha,\beta)\) is the \(\alpha\)th derivative of \(\lambda\beta.\omega^\beta\)" (with "0th derivative" being the identity functional for ordinal functions) using derivation.

Similarly, \(\Phi \colon \text{On} \times \text{On} \to \text{On}\) is defined as \begin{eqnarray*} \Phi(\alpha,\beta) := \text{enum}[\{\gamma \in \text{Card} \mid \forall \alpha' \in \alpha, \Phi(\alpha',\gamma) = \gamma\}](\beta) \end{eqnarray*} by transfinite recursion on \(\alpha\)[2] without using derivation, or described as "\(\lambda\beta.\Phi(\alpha,\beta)\) is the \(\alpha\)th derivative of \(\textrm{enum}(\textrm{Card})\)" using derivation.

Variant

A similar method is applicable to non-closed classes. For example, the class \(\textrm{Reg}\) of regular cardinals is not closed, but the higher regularlity such as weak inaccessibility, weak 1-inaccessibility, and weak hyper-inaccessiblity is defined by using the enumerations of the closures \(\text{cl}(X)\) of non-closed classes \(X\). For example, the class of weakly inaccessible cardinals can be characterised as the class of fixed points of the enumeration function of \(\textrm{Reg}\), or equivalently, the intersection of \(\textrm{Reg}\) and the derivative of the enumeration \(\alpha \mapsto \aleph_{\alpha}\) of the closure of \(\textrm{Reg}\), i.e. the class of infinite cardinals. The class of weakly 1-inaccessible cardinals can be characterised as the class of fixed points of the enumeration function of the class of weakly inaccessible cardinals, or equivalently, the intersection of \(\textrm{Reg}\) and the derivative of the enumeration \(\alpha \mapsto I_{\alpha}\) of the closure of the class of weakly inaccessible cardinals. Similarly to \(\varphi\) and \(\Phi\), the \(2\)-ary enumeration function \(I(\alpha,\beta)\) is defined as \begin{eqnarray*} I(\alpha,\beta) := \text{enum}[\text{cl}(\{\gamma \in \text{Reg} \mid \forall \alpha' \in \alpha, I(\alpha',\gamma) = \gamma\})](\beta) \end{eqnarray*} (or the variant given by replacing \(\text{Reg}\) by the class of weakly inaccessible cardinals depending on the convention of the index) by the transfinite recursion on \(\alpha\).


See also

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)

Sources

  1. M. Rathjen, Proof theory: From arithmetic to set theory (p.12). Retrieved 2021-06-19.
  2. M. Rathjen, Ordinal notations based on a weakly Mahlo cardinal. Archive for Mathematical Logic 29(4) 249-263 (1990).
Advertisement