User:Binary198/List of ordinal collapsing functions

This is a list of ordinal collapsing functions. Feel free to add any that you invented or others forgot to include to this list!

List

Bachmann's ψ

The first true OCF, Bachmann's $\psi$ was invented by Heinz Bachmann, somewhat cumbersome as it depends on fundamental sequences for all limit ordinals; yet the full definition has been lost over time. Michael Rathjen has suggested a "recast" of the system, which goes like so:

• Let $\Omega$ represent an uncountable ordinal such as $\omega _{1}$;
• Then define $C_{0}^{\Omega }(\alpha ,\beta )=\beta \cup \{0,\Omega \}$ and $C_{n+1}^{\Omega }(\alpha ,\beta )=\{\delta +\theta :\delta ,\theta \in C_{n}^{\Omega }(\alpha ,\beta )\}\cup \{\omega ^{\xi }:\xi \in C_{n}^{\Omega }(\alpha ,\beta )\}\cup \{\psi _{\Omega }(\xi ):\xi \in C_{n}^{\Omega }(\alpha ,\beta )\land \xi <\alpha \}$
• $C^{\Omega }(\alpha ,\beta )=\bigcup \limits _{n<\omega }C_{n}^{\Omega }(\alpha ,\beta )$
• $\psi _{\Omega }(\alpha )=min(\{\rho <\Omega :C^{\Omega }(\alpha ,\rho )\cap \Omega =\rho \})$

$\psi _{\Omega }(\varepsilon _{\Omega +1})$ is the Bachmann-Howard ordinal, the proof-theoretic ordinal of Kripke-Platek set theory with the axiom of infinity (KP). One can also generalize the definition like so:

• $C_{0}^{\gamma }(\alpha ,\beta )=\beta \cup \{0,\gamma \}$
• $C_{n+1}^{\gamma }(\alpha ,\beta )=\{\delta +\theta :\delta ,\theta \in C_{n}^{\gamma }(\alpha ,\beta )\}\cup \{\omega ^{\xi }:\xi \in C_{n}^{\gamma }(\alpha ,\beta )\}\cup \{\psi _{\gamma }(\xi ):\xi \in C_{n}^{\gamma }(\alpha ,\beta )\land \xi <\alpha \}$
• $C^{\gamma }(\alpha ,\beta )=\bigcup \limits _{n<\omega }C_{n}^{\gamma }(\alpha ,\beta )$
• $\psi _{\gamma }(\alpha )=min(\{\rho <\Omega :C^{\gamma }(\alpha ,\rho )\cap \Omega =\rho \})$

Feferman's θ

Feferman's $\theta$-functions constitute a hierarchy of single-argument functions $\theta _{\alpha }:{\mathsf {On}}\rightarrow {\mathsf {On}}$ for $\alpha \in {\mathsf {On}}$. It is often considered a two-argument function with $\theta _{\alpha }(\beta )$ occasionally written as $\theta \alpha \beta$. It is defined like so:

• $C_{0}(\alpha ,\beta )=\beta \cup \{0,\Omega ,\Omega _{2},...,\Omega _{\omega }\}$
• $C_{n+1}(\alpha ,\beta )=\{\gamma +\delta ,\theta _{\xi }(\eta )|\gamma ,\delta ,\xi ,\eta \in C_{n}(\alpha ,\beta );\xi <\alpha \}$
• $C(\alpha ,\beta )=\bigcup \limits _{n<\omega }C_{n}(\alpha ,\beta )$
• $\theta _{\alpha }(\beta )={\mathsf {min}}(\{\gamma |\gamma \notin C(\alpha ,\gamma \land \forall \delta <\beta :\theta _{\alpha }(\delta )<\gamma \})$

The supremum of countable ordinals that can be expressed with this function is the Takeuti-Feferman-Buchholz ordinal $\theta _{\varepsilon _{\Omega _{\omega }+1}}(0)$, but an ordinal notation associated to this function is unheard of or nonexistent, unlike for Buchholz's psi function.

Buchholz's ψ

Buchholz's $\psi$ is a hierarchy of single-argument functions $\psi _{\nu }:{\mathsf {On}}\rightarrow {\mathsf {On}}$, with $\psi _{\nu }(\alpha )$ occasionally abbreviated as $\psi _{\nu }\alpha$. This function is likely the most well known out of all OCFs. The definition is so:

• Define $\Omega _{0}=1$ and $\Omega _{\nu }=\aleph _{\nu }$ for $\nu >0$.
• Let $P(\alpha )$ be the set of distinct terms in the Cantor normal form of $\alpha$ (with each term of the form $\omega ^{\xi }$ for $\xi \in {\mathsf {On}}$)
• $C_{\nu }^{0}(\alpha )=\Omega _{\nu }$
• $C_{\nu }^{n+1}(\alpha )=C_{\nu }^{n}(\alpha )\cup \{\psi _{\nu }(\xi )|\xi \in \alpha \cap C_{\nu }^{n}(\alpha )\land \xi \in C_{u}(\xi )\land u\leq \omega \}$
• $C_{\nu }(\alpha )=\bigcup \limits _{n<\omega }C_{\nu }^{n}(\alpha )$
• $\psi _{\nu }(\alpha )=min(\{\gamma |\gamma \notin C_{\nu }(\alpha )\})$

The limit of this system is $\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$, the Takeuti-Feferman-Buchholz ordinal.

Extended Buchholz's ψ

This OCF is a sophisticated extension of Buchholz's $\psi$ by mathematician Denis Maksudov. The limit of this system is much greater, equal to $\psi _{0}(\Omega _{\Omega _{\Omega _{...}}})$ where $\Omega _{\Omega _{\Omega _{...}}}$ denotes the first omega fixed point, sometimes referred to as Extended Buchholz's ordinal. The function is defined as follows:

• Define $\Omega _{0}=1$ and $\Omega _{\nu }=\aleph _{\nu }$ for $\nu >0$.
• $C_{\nu }^{0}(\alpha )=\{\beta |\beta <\Omega _{\nu }\}$
• $C_{\nu }^{n+1}(\alpha )=\{\beta +\gamma ,\psi _{\mu }(\eta )|\mu ,\beta ,\gamma ,\eta \in C_{\nu }^{n}(\alpha )\land \eta <\alpha \}$
• $C_{\nu }(\alpha )=\bigcup \limits _{n<\omega }C_{\nu }^{n}(\alpha )$
• $\psi _{\nu }(\alpha )=min(\{\gamma |\gamma \notin C_{\nu }(\alpha )\})$

Madore's ψ

This OCF was the same as the ψ function previously used throughout this article; it is a simpler, more efficient version of Buchholz's ψ function defined by David Madore. Its use in this article lead to widespread use of the function.

• $C_{0}(\alpha )=\{0,1,\omega ,\Omega \}$
• $C_{n+1}(\alpha )=\{\gamma +\delta ,\gamma \delta ,\gamma ^{\delta },\psi (\eta )|\gamma ,\delta ,\eta \in C_{n}(\alpha );\eta <\alpha \}$
• $C(\alpha )=\bigcup \limits _{n<\omega }C_{n}(\alpha )$
• $\psi (\alpha )=min(\{\beta \in \Omega |\beta \notin C(\alpha )\})$

This function was used by Chris Bird, who also invented the next OCF.

Bird's θ

Chris Bird devised the following shorthand for the extended Veblen function $\varphi$:

• $\theta (\Omega ^{n-1}a_{n-1}+...+\Omega ^{2}a_{2}+\Omega a_{1}+a_{0},b)=\varphi (a_{n-1},...,a_{2},a_{1},a_{0},b)$
• $\theta (\alpha ,0)$ is abbreviated $\theta (\alpha )$

This function is only defined for arguments less than $\Omega ^{\omega }$, and its outputs are limited by the small Veblen ordinal.

Wilken's ϑ

Wilken's ϑ is more generic than other OCFs:

• Let $\Omega _{0}$ be either 1 or an epsilon number.
• Let $\Omega _{1}>\Omega _{0}$ be an uncountable regular cardinal.
• For $0<i<\omega$, let $\Omega _{i+1}$ be the successor cardinal to $\Omega _{i}$.
• For finite $n$ and $0\leq m<n$, define the following for $\beta <\Omega _{m+1}$:
  • $\Omega _{m}\cup \beta \subseteq C_{m}^{n}(\alpha ,\beta )$
  • $\xi ,\eta \in C_{m}^{n}(\alpha ,\beta )\Rightarrow \xi +\eta \in C_{m}^{n}(\alpha ,\beta )$
  • $\eta \in C_{m}^{n}(\alpha ,\beta )\cap \Omega _{k+2}\Rightarrow \vartheta _{k}^{n}\in C_{m}^{n}(\alpha ,\beta )$ for m < k < n
  • $\eta \in C_{m}^{n}(\alpha ,\beta )\cap \alpha \Rightarrow \vartheta _{m}^{n}\in C_{m}^{n}(\alpha ,\beta )$
  • $\vartheta _{m}^{n}(\alpha )=min(\{\xi <\Omega _{m+1}|C_{m}^{n}(\alpha ,\xi )\cap \Omega _{m+1}\subseteq \xi \land \alpha \in C_{m}^{n}(\alpha ,\xi )\}\cup \{\Omega _{m+1}\})$

n is needed to define the function, but n does not actually affect the function's behaviour. Therefore, one may safely eliminate n and simply write $\vartheta _{m}(\alpha )$.

Wilken and Weiermann's ϑ^–

Wilken and Weiermann's ϑ^– is closely related to Wilken's ϑ, and their paper closely analyzes the relationship between the two.

• As before, let $\Omega _{0}$ be either 1 or an epsilon number.
• Let $\Omega _{1}>\Omega _{0}$ be an uncountable regular cardinal.
• For $0<i<\omega$, let $\Omega _{i+1}$ be the successor cardinal to $\Omega _{i}$.
• Let $\Omega _{\omega }=sup_{i<\omega }\Omega _{i}$
• For all $\beta <\Omega _{i+1}$, define the following:
  • $\Omega _{i}\cup \beta \subseteq C_{i}^{-}(\alpha ,\beta )$
  • $\xi ,\eta \in C_{i}^{-}(\alpha ,\beta )\Rightarrow \xi +\eta \in C_{i}^{-}(\alpha ,\beta )$
  • $j\leq i<\omega \land C_{j}^{-}(\xi ,\omega _{j+1})\cap C_{i}^{-}(\alpha ,\beta )\cap \alpha \Rightarrow \vartheta _{j}^{-}(\xi )\in C_{i}^{-}(\alpha ,\beta )$
  • $\vartheta _{i}^{-}(\alpha )=min(\{\xi <\Omega _{m+1}|C_{m}^{n}(\alpha ,\xi )\cap \Omega _{m+1}\subseteq \xi \land \alpha \in C_{m}^{n}(\alpha ,\xi )\}\cup \{\Omega _{m+1}\})$

Weiermann's ϑ

This ϑ function has the advantage of having only a single argument, at the cost of some added complexity. This OCF is similar in some ways to Bachmann's ψ and its recast by Rathjen.

• $C_{0}(\alpha +\beta )=\beta \cup \{0,\Omega \}$
• $C_{n+1}(\alpha +\beta )=\{\gamma +\delta ,\omega ^{\gamma },\vartheta (\eta )|\gamma ,\delta ,\eta \in C_{n}(\alpha ,\beta );\eta <\alpha \}$
• $C(\alpha ,\beta )=\bigcup \limits _{n<\omega }C_{n}(\alpha ,\beta )$
• $\vartheta (\alpha )=min(\{\beta <\Omega |C(\alpha ,\beta )\cap \Omega \subseteq \beta \land \alpha \in C(\alpha ,\beta )\})$

Rathjen and Weiermann showed that $\vartheta (\alpha )$ is defined for all $\alpha <\varepsilon _{\Omega +1}$, but do not discuss higher values. ϑ follows the archetype of many ordinal collapsing functions — it is defined inductively with a "marriage" to the C function.

Jäger's ψ

Jäger's ψ is a hierarchy of single-argument ordinal functions ψ_κ indexed by uncountable regular cardinals κ smaller than the least weakly Mahlo cardinal M₀ introduced by German mathematician Gerhard Jäger in 1984. It was developed on the base of Buchholz's approach.

• If $\kappa =I_{\alpha }(0)$ for some α < κ, $\kappa ^{-}=0$.
• If $\kappa =I_{\alpha }(\beta +1)$ for some α, β < κ, $\kappa ^{-}=I_{\alpha }(\beta )$.
• $C_{\kappa }^{0}(\alpha )=\{\kappa ^{-}\}\cup \kappa ^{-}$
• For any finite n, $C_{\kappa }^{n+1}(\alpha )\subset M_{0}$ is the smallest set satisfying the following:
  • The sum of any finitely many ordinals in $C_{\kappa }^{n}(\alpha )\subset M_{0}$ belongs to $C_{\kappa }^{n+1}(\alpha )\subset M_{0}$.
  • For any $\beta ,\gamma \in C_{\kappa }^{n}(\alpha )$, $\varphi _{\beta }(\gamma )\in C_{\kappa }^{n+1}(\alpha )$.
  • For any $\beta ,\gamma \in C_{\kappa }^{n}(\alpha )$, $I_{\beta }(\gamma )\in C_{\kappa }^{n+1}(\alpha )$.
  • For any ordinal γ and uncountable regular cardinal $\pi \in C_{\kappa }^{n}(\alpha )$, $\gamma <\pi <\kappa \Rightarrow \gamma \in C_{\kappa }^{n+1}(\alpha )$.
  • For any $\gamma \in \alpha \cap C_{\kappa }^{n}(\alpha )$ and uncountable regular cardinal $\pi \in C_{\kappa }^{n}(\alpha )$, $\gamma \in C_{\pi }(\gamma )\Rightarrow \psi _{\pi }(\gamma )\in C_{\kappa }^{n+1}(\alpha )$.
• $C_{\kappa }(\alpha )=\bigcup \limits _{n<\omega }C_{\kappa }^{n}(\alpha )$
• $\psi _{\kappa }(\alpha )=min(\{\xi \in \kappa |\xi \notin C_{\kappa }(\alpha )\})$

Simplified Jäger's ψ

This is a sophisticated simplification of Jäger's ψ created by Denis Maksudov. An ordinal is α-weakly inaccessible if it is uncountable, regular and it is a limit of γ-weakly inaccessible cardinals for γ < α. Let I(α, 0) be the first α-weakly inaccessible cardinal, I(α, β + 1) be the first α-weakly inaccessible cardinal after I(α, β) and I(α, β) = $sup(\{I(\alpha ,\gamma )|\gamma <\beta \})$ for limit β. Restrict ρ and π to uncountable regular ordinals of the form I(α, 0) or I(α, β + 1). Then,

• $C_{0}(\alpha ,\beta )=\beta \cup \{0\}$
• $C_{n+1}(\alpha ,\beta )=\{\gamma +\delta |\gamma ,\delta \in C_{n}(\alpha ,\beta )\}\cup \{I(\gamma ,\delta )|\gamma ,\delta \in C_{n}(\alpha ,\beta )\}\cup \{\psi _{\pi }(\gamma )|\pi ,\gamma ,\in C_{n}(\alpha ,\beta )\land \gamma <\alpha \}$
• $C(\alpha ,\beta )=\bigcup \limits _{n<\omega }C_{n}(\alpha ,\beta )$
• $\psi _{\pi }(\alpha )=min(\{\beta <\pi |C(\alpha ,\beta )\cap \pi \subseteq \beta \})$

Rathjen's Ψ

Rathjen's Ψ function is based on the least weakly compact cardinal to create large countable ordinals. For a weakly compact cardinal K, the functions $M^{\alpha }$, $C(\alpha ,\pi )$, $\Xi (\alpha )$, and $\Psi _{\pi }^{\xi }(\alpha )$ are defined in mutual recursion in the following way:

• M⁰ = $K\cap {\mathsf {Lim}}$, where Lim denotes the class of limit ordinals.
• For α > 0, M^α is the set $\{\pi <K|C(\alpha ,\pi )\cap K=\pi \land \forall \xi \in C(\alpha ,\pi )\cap \alpha ,M^{\xi }{\mathsf {}}$ is stationary in $\pi \land \alpha \in C(\alpha ,\pi )\}$
• $C(\alpha ,\beta )$ is the closure of $\beta \cup \{0,K\}$ under addition, $(\xi ,\eta )\rightarrow \varphi (\xi ,\eta )$, $\xi \rightarrow \Omega _{\xi }$ given ξ < K, $\xi \rightarrow \Xi (\xi )$ given ξ < α, and $(\xi ,\pi ,\delta )\rightarrow \Psi _{\pi }^{\xi }(\delta )$ given $\xi \leq \delta <\alpha$.
• $\Xi (\alpha )=min(M^{\alpha }\cup \{K\})$.
• For $\xi \leq \alpha$, $\Psi _{\pi }^{\xi }(\alpha )=min(\{\rho \in M^{\xi }\cap \pi :C(\alpha ,\rho )\cap \pi =\rho \land \pi \land \alpha \in C(\alpha ,\rho )\}\cup \{\pi \})$.

Bachmann and Howard's ϑ

Note: This OCF does not seem to have an official name and the above is simply a nickname.

This OCF was introduced by "Emlightened" in an article on the Googology Wikia about ordinal collapsing functions. The definition is like so:

• Let $\Omega$ represent ω₁, the first uncountable ordinal.
• $C_{0}(\alpha ,\beta )=\beta \cup \{\Omega \}$
• $C_{n+1}(\alpha ,\beta )=\{\gamma +\delta :\gamma ,\delta \in C_{n}(\alpha ,\beta )\}\cup \{\omega ^{\gamma }:\gamma \in C_{n}(\alpha ,\beta )\land \gamma \geq \Omega \}\cup \{\vartheta (\gamma ):\gamma \in C_{n}(\alpha ,\beta )\land \gamma <\alpha \}$
• $C(\alpha ,\beta )=\bigcup \limits _{n<\omega }C_{n}(\alpha ,\beta )$
• $\vartheta (\alpha ,\beta )=min(\{\beta >0:\Omega \cap C(\alpha ,\beta )\subseteq \beta \})$

AndrasKovacs' ψ

This is a variant of Madore's ψ introduced by AndrasKovacs in a piece of code describing large countable ordinals in Agda. $\psi _{\alpha }(\beta )=\psi (\Omega _{\alpha }\cdot \beta )$