Ordinal collapsing function: Difference between revisions

Revision as of 08:53, 1 August 2022

Revision as of 04:37, 5 August 2022

Line 173:

=== Going beyond the Bachmann–Howard ordinal ===

We know that <math>\psi(\varepsilon_{\Omega+1})</math> is the Bachmann–Howard ordinal. The reason why <math>\psi(\varepsilon_{\Omega+1}+1)</math> is no larger, with our definitions, is that there is no notation for <math>\varepsilon_{\Omega+1}</math> (it does not belong to <math>C(\alpha)</math> for any <math>\alpha</math>, it is always the least upper bound of it). One could try to add the <math>\varepsilon</math> function (or the Veblen functions of so-many-variables) to the allowed primitives beyond addition, multiplication and exponentiation, but that does not get us very far. To create more systematic notations for countable ordinals, we need more systematic notations for uncountable ordinals: we cannot use the <math>\psi</math> function itself because it only yields countable ordinals (e.g., <math>\psi(\Omega+1)</math> is, <math>\varepsilon_{\phi_2varphi_2(0)+1}</math>, certainly not <math>\varepsilon_{\Omega+1}</math>), so the idea is to mimic its definition as follows:

:Let <math>\psi_1(\alpha)</math> be the smallest ordinal which cannot be expressed from all countable ordinals, <math>\Omega</math> and <math>\Omega_2</math> using sums, products, exponentials, and the <math>\psi_1</math> function itself (to previously constructed ordinals less than <math>\alpha</math>).

Line 179:

Here, <math>\Omega_2</math> is a new ordinal guaranteed to be greater than all the ordinals which will be constructed using <math>\psi_1</math>: again, letting <math>\Omega = \omega_1</math> and <math>\Omega_2 = \omega_2</math> works.

For example, <math>\psi_1(0) = \varepsilon_{\Omega+1}</math>, and more generally <math>\psi_1(\alpha) = \varepsilon_{\Omega+1+\alpha}</math> for all countable ordinals and even beyond (<math>\psi_1(\Omega) = \psi_1(\psi_1(0)) = \varepsilon_{\Omega 2}</math> and <math>\psi_1(\psi_1(01)) = \varepsilon_{\varepsilon_{\Omega+1}}</math>): this holds up to the first fixed point <math>\zeta_{\Omega+1}</math> beyond <math>\Omega</math> of the <math>\xi\mapsto\varepsilon_\xi</math> function, which is the limit of <math>\psi_1(0)</math>, <math>\psi_1(\psi_1(0))</math> and so forth. Beyond this, we have <math>\psi_1(\alpha) = \zeta_{\Omega+1}</math> and this remains true until <math>\Omega_2</math>: exactly as was the case for <math>\psi(\Omega)</math>, we have <math>\psi_1(\Omega_2) = \zeta_{\Omega+1}</math> and <math>\psi_1(\Omega_2+1) = \varepsilon_{\zeta_{\Omega+1}+1}</math>.

The <math>\psi_1</math> function gives us a system of notations (''assuming'' we can somehow write down all countable ordinals!) for the uncountable ordinals below <math>\psi_1(\varepsilon_{\Omega_2+1})</math>, which is the limit of <math>\psi_1(\Omega_2)</math>, <math>\psi_1({\Omega_2}^{\Omega_2})</math> and so forth.

Line 186:

:<math>\psi(\alpha)</math> is the smallest ordinal which cannot be expressed from <math>0</math>, <math>1</math>, <math>\omega</math>, <math>\Omega</math> and <math>\Omega_2</math> using sums, products, exponentials, the <math>\psi_1</math> function, and the <math>\psi</math> function itself (to previously constructed ordinals less than <math>\alpha</math>).

This modified function <math>\psi</math> coincides with the previous one up to (and including) <math>\psi(\psi_1(01))</math> &mdash; which is the Bachmann–Howard ordinal. But now we can get beyond this, and <math>\psi(\psi_1(01)+1)</math> is <math>\varepsilon_{\psi(\psi_1(01))+1}</math> (the next <math>\varepsilon</math>-number after the Bachmann–Howard ordinal). We have made our system ''doubly'' impredicative: to create notations for countable ordinals we use notations for certain ordinals between <math>\Omega</math> and <math>\Omega_2</math> which are themselves defined using certain ordinals beyond <math>\Omega_2</math>.

A variation on this scheme, which makes little difference when using just two (or finitely many) collapsing functions, but becomes important for infinitely many of them, is to define

Line 193 ⟶ 194:

Indeed, there is no reason to stop at two levels: using <math>\omega+1</math> new cardinals in this way, <math>\Omega_1,\Omega_2,\ldots,\Omega_\omega</math>, we get a system essentially equivalent to that introduced by Buchholz,<ref name="Buchholz"/> the inessential difference being that since Buchholz uses <math>\omega+1</math> ordinals from the start, he does not need to allow multiplication or exponentiation; also, Buchholz does not introduce the numbers <math>1</math> or <math>\omega</math> in the system as they will also be produced by the <math>\psi</math> functions: this makes the entire scheme much more elegant and more concise to define, albeit more difficult to understand. This system is also sensibly equivalent to the earlier (and much more difficult to grasp) "ordinal diagrams" of Takeuti<ref>Takeuti, 1967 (Ann. Math.)</ref> and <math>\theta</math> functions of Feferman: their range is the same (<math>\psi_0(\varepsilon_{\Omega_\omega+1})</math>, which could be called the Takeuti-Feferman–Buchholz ordinal, and which describes the [[ordinal analysis|strength]] of [[Second-order arithmetic#Stronger systems|<math>\Pi^1_1</math>-comprehension]] plus [[bar induction]]).

<!-- You can also have <math>\Omega</math> or more cardinals, in fact as many as nesting of the &psi; function allows:

:<math>\psi_\nu(\alpha)</math> is the smallest ordinal which cannot be expressed from <math>0</math>, <math>1</math>, <math>\omega</math>, and all ordinals smaller than <math>\Omega_\nu</math> using sums, products, exponentials, and the <math>\psi_\kappa</math> functions (for <math>\kappa</math> being a previously constructed ordinal) to previously constructed ordinals less than <math>\alpha</math>.

<math>\Omega_0</math> being 0 here.-->

=== A "normal" variant ===