Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-17T15:06:33.318Z Has data issue: false hasContentIssue false
  • English
  • Français

Σ 1 definitions with parameters

Published online by Cambridge University Press:  12 March 2014

T. A. Slaman
T. A. Slaman*
Affiliation:
Department of Mathematics, University of Chicago, Chicago, Illinois 60637
Get access Rights & Permissions [Opens in a new window]

Abstract

Let p be a set. A function Φ is uniformly Σ 1(p) in every admissible set if there is a Σ 1 formula ϕ in the parameter p so that ϕ defines Φ in every Σ 1-admissible set which includes p. A theorem of Van de Wiele states that if Φ is a total function from sets to sets then Φ is uniformly Σ 1 in every admissible set if and only if it is E-recursive. A function is ESp -recursive if it can be generated from the schemes for E-recursion together with a selection scheme over the transitive closure of p. The selection scheme is exactly what is needed to insure that the ESP -recursively enumerable predicates are closed under existential quantification over the transitive closure of p. Two theorems are established: a) If the transitive closure of p is countable then a total function on sets is ESp -recursive if and only if it is uniformly Σ 1(p) in every admissible set. b) For any p, if Φ is a function on the ordinal numbers then Φ is ESP -recursive if and only if it is uniformly Σ 1(p) in every admissible set.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 51 , Issue 2 , June 1986 , pp. 453 - 461
Copyright
Copyright © Association for Symbolic Logic 1986

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

The author was supported by NSF grant MCS-8404208.

References

REFERENCES

[Ga67] Gandy, R. O., Generalized recursive functionals of finite type and hierarchies of functions, Annales de la Faculté des Sciences de l'Université de Clermont-Ferrand, vol. 35, pp. 5–24.Google Scholar
[Ha73] Harrington, L. A., Contributions to recursion theory on higher types, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts.Google Scholar
[Ho82] Hoole, M. R. R., Recursion on sets, Ph.D. thesis, Wolfson College, Oxford.Google Scholar
[Ke75] Kechris, A. S., The theory of countable analytic sets, Transactions of the American Mathematical Society, vol. 202, pp. 259–297.CrossRefGoogle Scholar
[No78] Normann, D., Set recursion, Generalized recursion theory. 2 (Fenstad, J. E. et al., editors), North-Holland, Amsterdam, pp. 303–320.Google Scholar
[Sa77] Sacks, G. E., The k-section of a type n object, American Journal of Mathematics, vol. 99, pp. 901–917.CrossRefGoogle Scholar
[Sa82] Sacks, G. E., Post's problem in E-recursion, Recursion theory, Proceedings of Symposia in Pure Mathematics, vol. 42, American Mathematical Society, Providence, Rhode Island, 1985, pp. 177–193.CrossRefGoogle Scholar
[Sl85] Slaman, T. A., Reflection and forcing in E-recursion theory, Annals of Pure and Applied Logic, vol. 28, pp. 1–28.Google Scholar
[Va81] van de Wiele, J., Dilateurs récursifs et récursivités généralisées, Thèse du troisième cycle, Université Paris-VIII, Paris.Google Scholar