Ordinal collapsing function: Difference between revisions

Revision as of 18:14, 22 July 2015

Revision as of 18:15, 22 July 2015

Line 146:

=== A terminating process ===

Start with any ordinal less or equal to the [[Bachmann-Howard ordinal]], and repeat the following process so long as it is not zero:

* if the ordinal is a successor, subtract one (that is, replace it with its predecessor),

* if it is a limit, replace it by some element of the canonical sequence defined for it.

Line 157:

Concerning the first statement, one could introduce, for any ordinal <math>\alpha</math> less or equal to the Bachmann-Howard ordinal <math>\psi(\varepsilon_{\Omega+1})</math>, the integer function <math>f_\alpha(n)</math> which counts the number of steps of the process before termination if one always selects the <math>n</math>'th element from the canonical sequence. Then <math>f_\alpha</math> can be a very fast growing function: already <math>f_{\omega^\omega}(n)</math> is essentially <math>n^n</math>, the function <math>f_{\psi(\Omega^\omega)}(n)</math> is comparable with the [[Ackermann function]] <math>A(n,n)</math>, and <math>f_{\psi(\varepsilon_{\Omega+1})}(n)</math> is quite unimaginable.

Concerning the second statement, a precise version is given by [[ordinal analysis]]: for example, [[Kripke-Platek set theory]] can prove<ref name="Rathjen-slides-part3">Rathjen, 2005 (Fischbachau slides)</ref> that the process terminates for any given <math>\alpha</math> less than the [[Bachmann-Howard ordinal]], but it cannot do this uniformly, i.e., it cannot prove the termination starting from the Bachmann-Howard ordinal. Some theories like [[Peano arithmetic]] are limited by much smaller ordinals (<math>\varepsilon_0</math> in the case of Peano arithmetic).

== Variations on the example ==