In Feferman's paper (located here (pg. 2 of the PDF)), he begins to outline various methods used for attacking the problem of classifying the computable functions by means of hierarchies. In particular, he discusses those hierarchies which are formed by a kind of primitive recursive majorizing function, and provides the following definition:

We write $g \ll f$ and say "$f$ majorizes $g$" if we have that $\exists y \forall x [y < x \implies g(x) < f(x)]$.

Feferman then goes on to claim, with this definition in mind, that there is a hierarchy of computable functions which can be formed by extending $\ll$ into the effective transfinite, and bases his claim on following proposition:

For any effectively enumerated class $E$ of computable functions, one can construct a computable function $f$ which majorizes every member $g$ contained in $E$. [italics mine]

My question is the following: Is there a complete proof for this statement in the literature? I imagine that there is a slick 2-line proof which requires little machinery (perhaps simply using diagonalization or a subtle application of the recursion theorem). But since the statement was given without proof, I feel as if I only have cheap, ad-hoc methods for solving related questions, such as how one might go about extending $\ll$, how to construct a computable $f$ for every $g \in E$, etc.

A reference or a quick proof would be greatly appreciated.

  • 5
    $\begingroup$ Are you looking for something more than the following? Let $E=\{f_0,f_1,\ldots\}$ be uniformly computable. Then the function $g$ defined by letting $g(n)=\textrm{max}\{f_i(n) : i<n\}+1$ majorizes every member of $E$. $\endgroup$ – Denis Hirschfeldt Apr 10 '17 at 18:40
  • $\begingroup$ And of course the $g$ defined in my previous comment is computable. $\endgroup$ – Denis Hirschfeldt Apr 10 '17 at 19:12
  • $\begingroup$ @DenisHirschfeldt Yes, this was exactly the sort of construction I was thinking of; thank you for the idea. I suppose that this really answers the bulk of my question, but maybe I should have added that I would be happy to have a reference (or again, a brief sketch) on how might one continue this construction through the computable ordinals. If you post your comment as an answer I will accept it. $\endgroup$ – cmn1 Apr 12 '17 at 14:19

Let $E=\{g_0,g_1\ldots\}$ be uniformly computable. Then the function $f$ defined by letting $f(n)=\textrm{max}\{g_i(n):i<n\}+1$ is computable and majorizes every member of $E$. As to continuing constructions of this kind through computable ordinals, you might want to look at fast-growing hierarchies (see e.g. https://en.wikipedia.org/wiki/Fast-growing_hierarchy). There the functions grow much faster than mere majorization, but the idea is similar.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.