Ordinal collapsing function: Difference between revisions

Revision as of 08:18, 29 March 2025

Revision as of 03:34, 16 May 2025

Line 67:

==== A note about base representations ====

Recall that if <math>\delta</math> is an ordinal which is a power of <math>\omega</math> (for example <math>\omega</math> itself, or <math>\varepsilon_0</math>, or <math>\Omega</math>), any ordinal <math>\alpha</math> can be uniquely expressed in the form <math>\delta^{\beta_1}\gamma_1 + \ldots + \delta^{\beta_k}\gamma_k</math>, where <math>k</math> is a [[natural number]], <math>\gamma_1,\ldots,\gamma_k</math> are non-zero ordinals less than <math>\delta</math>, and <math>\beta_1 > \beta_2 > \cdots > \beta_k</math> are ordinal numbers (we allow <math>\beta_k=0</math>). This "base <math>\delta</math> representation" is an obvious generalization of the [[Ordinal arithmetic#Cantor normal form|Cantor normal form]] (which is the case <math>\delta=\omega</math>). Of course, it may quite well be that the expression is uninteresting, i.e., <math>\alpha = \delta^\alpha</math>, but in any other case the <math>\beta_i</math> must all be less than <math>\alpha</math>; it may also be the case that the expression is trivial (i.e., <math>\alpha<\delta</math>, in which case <math>k\leq 1</math> and <math>\gamma_1 = \alpha</math>).

If <math>\alpha</math> is an ordinal less than <math>\varepsilon_{\Omega+1}</math>, then its base <math>\Omega</math> representation has coefficients <math>\gamma_i<\Omega</math> (by definition) and exponents <math>\beta_i<\alpha</math> (because of the assumption <math>\alpha < \varepsilon_{\Omega+1}</math>): hence one can rewrite these exponents in base <math>\Omega</math> and repeat the operation until the process terminates (any decreasing sequence of ordinals is finite). We call the resulting expression the ''iterated base <math>\Omega</math> representation'' of <math>\alpha</math> and the various coefficients involved (including as exponents) the ''pieces'' of the representation (they are all <math><\Omega</math>), or, for short, the <math>\Omega</math>-pieces of <math>\alpha</math>.

Line 101:

The notations thus defined have the property that whenever they nest <math>\psi</math> functions, the arguments of the "inner" <math>\psi</math> function are always less than those of the "outer" one (this is a consequence of the fact that the <math>\Omega</math>-pieces of <math>\alpha</math>, where <math>\alpha</math> is the largest possible such that <math>\psi(\alpha)=\delta</math> for some <math>\varepsilon</math>-number <math>\delta</math>, are all less than <math>\delta</math>, as we have shown above). For example, <math>\psi(\psi(\Omega)+1)</math> does not occur as a notation: it is a well-defined expression (and it is equal to <math>\psi(\Omega) = \zeta_0</math> since <math>\psi</math> is constant between <math>\zeta_0</math> and <math>\Omega</math>), but it is not a notation produced by the inductive algorithm we have outlined.

Canonicalness can be checked recursively: an expression is canonical [[if and only if]] it is either the iterated Cantor normal form of an ordinal less than <math>\varepsilon_0</math>, or an iterated base <math>\delta</math> representation all of whose pieces are canonical, for some <math>\delta=\psi(\alpha)</math> where <math>\alpha</math> is itself written in iterated base <math>\Omega</math> representation all of whose pieces are canonical and less than <math>\delta</math>. The order is checked by lexicographic verification at all levels (keeping in mind that <math>\Omega</math> is greater than any expression obtained by <math>\psi</math>, and for canonical values the greater <math>\psi</math> always trumps the lesser or even arbitrary sums, products and exponentials of the lesser).

For example, <math>\psi(\Omega^{\omega+1}\,\psi(\Omega) + \psi(\Omega^\omega)^{\psi(\Omega^2)}42)^{\psi(1729)\,\omega}</math> is a canonical notation for an ordinal which is less than the Feferman–Schütte ordinal: it can be written using the Veblen functions as <math>\varphi_1(\varphi_{\omega+1}(\varphi_2(0)) + \varphi_\omega(0)^{\varphi_3(0)}42)^{\varphi_1(1729)\,\omega}</math>.

Line 236:

* <math>\psi_\Omega(\alpha)</math> is the smallest countable ordinal ρ such that <math>C^\Omega(\alpha, \rho) \cap \Omega= \rho</math>

<math>\psi_\Omega(\varepsilon_{\Omega+1})</math> is the Bachmann–Howard ordinal, the proof-theoretic ordinal of Kripke–Platek set theory with the [[axiom of infinity]] (KP).

=== Buchholz's ''ψ'' ===