This is a continuation of my previous blog post.
The constructible functions can be divided into 3 categories: the recursively constructible, defineable in L, and higher constructible.
Also, for the rest of this blog post, assume we are working in the Platonist universe (which is transitive and hence well-founded), and assume that 0# exists. Because of the second assumption, most of the things in this blog post will still work even if we work in a transitive model of set theory, provided that it contains all the ordinals which are countable in V. In fact, the constructible functions are absolute for transitive models of set theory containing all ordinals countable in V which satisfy 0# exists.
The recursively constructible functions are the functions which are
\(\omega_1 ^{CK}\) -constructible. This means that they are absolute in every well-founded model of KP set theory (this doesn't necessarily mean that KP can prove their existence; however, if we are only working in well-founded models, then they will exist in every well-founded model of KP, since for every recursive ordinal
\(\alpha\) ,
\(L_{\alpha}\) is in
\(L_{\omega_1 ^{CK}}\) .
It is easy to find variants of the Rayo function that can act as a measuring rod for the constructible functions, similar to the way FGH is a measuring rod for the computable functions. I would like it if someone could construct a class of functions not based off of the Rayo function that could at least provide a measuring rod for the recursively constructable functions.
The functions defineable in L are, well, the functions that are defineable in FOST with parameters in L. In fact, not all constructible functions are defineable in L if 0# exists, since there are many ordinals which are indiscernible in L. Since for each indiscernible
\(\delta\) \(L_{\delta}\) satisfies the same first order formulas as
\(L\) , the Rayo function evaluated in
\(L\) is
\(\delta + 1\) -constructible. For the functions defineable in
\(L\) , one possible measuring rod would be to use the smallest transitive model for a given set theory. Let
\(T\) be a recursive theory in the language of FOST which is satisfied by
\(L_{\alpha}\) for some ordinal
\(\alpha\) . Define
\(Rayo_T(n)\) as the Rayo function evaluated in
\(L_{\alpha}\) for the smallest ordinal
\(\alpha\) such that
\(L_{\alpha}\) is a model of
\(T\) . These functions can be used as a measuring rod for the functions defineable in L.
The best measuring rod that I can think of for the higher constructible functions are the functions in the Rayo hierarchy. Let
\(\delta_{\alpha}\) be the
\(\alpha\) th ordinal such that
\(L_{\alpha}\) satisfies the same first order formulas as L (where
\(\alpha\) starts at 0). Then
\(R_{\alpha + 1}\) evaluated in L is
\(\delta_{\alpha} + 1\) -constructible.