10
$\begingroup$

The E-recursive functions are a particular generalization of classical recursion theory to the entire set-theoretic universe, $V$. They are defined via a schemes: see Sacks' $E$-recursive intuitions. It is easy to see that any $E$-recursive function is $\Sigma_1$-definable over $V$. However, the converse is not true.

Fortunately, there is a nice characterization of the $E$-recursive functions in terms of definability: this is shown by van de Wiele in Recursive Dilators and Generalized Recursion (in Proceedings of Herbrand Symposium, 1982), which states:

$f: V\rightarrow V$ is $E$-recursive iff $f$ is uniformly $\Sigma_1$: that is, iff there is a single $\Sigma_1$-formula $\varphi$ such that, for every admissible set $A$, $\varphi^A=f\upharpoonright A$.

See Sacks' book Higher Recursion Theory, chapter XIII page 325 (Project Euclid), for a proof (due to Slaman). See also

for the natural extension of the theorem to oracle $E$-recursion.

My question is about a natural weakening of this definition: what happens if we require $f$ to be uniformly $\Sigma_1$, not across all admissible sets, but only across some smaller family of "nice" sets?

Definition. For $n\in\omega$, a function $f: V\rightarrow V$ is (E, n)-recursive if $f$ is uniformly $\Sigma_1$ over the $n$-admissible sets: that is, iff there is a single $\Sigma_1$-formula $\varphi$ such that, for every $n$-admissible set $A$, $\varphi^A=f\upharpoonright A$.

(We can keep going past $\omega$, but here things get tricky - there's a few different things we can do, and it's not obvious to me what the right one is.)

On the one hand, we're not going too far afield here: all the functions we're looking at are still $\Sigma_1$ over $V$! On the other hand, looking at the proof of van de Wiele's theorem, it seems like we should be getting some extra power. So my question is, broadly: what is known about this method of "slicing" the $\Sigma_1$-on-$V$ functions? In particular:

  • Are there $(E, n+1)$-recursive functions which are not $(E, n)$-recursive? (Presumably the answer is yes, but I don't see how to construct them.)

  • How messy do things get? E.g., is there a reasonable description of the $(E, 2)$-recursive functions?

$\endgroup$
2
  • $\begingroup$ A note on tags: the "proof theory" tag is because the original proof of van de Wiele's theorem was via $\Pi^1_2$ logic, and proof theory might have something to say here. The "descriptive set theory" tag is a wild guess on my part. $\endgroup$ Oct 31, 2015 at 6:02
  • 1
    $\begingroup$ Have you considered the functions (parametrized by $n$) mapping $x$ to the least $\Sigma_n$-admissible containing $x$? They might distinguish between these classes. $\endgroup$ Oct 31, 2015 at 23:13

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.