Hostname: page-component-848d4c4894-75dct Total loading time: 0 Render date: 2024-05-08T16:50:13.423Z Has data issue: false hasContentIssue false
  • English
  • Français

Recursion, metarecursion, and inclusion

Published online by Cambridge University Press:  12 March 2014

James C. Owings Jr.
James C. Owings Jr.*
Affiliation:
Cornell University
Get access Rights & Permissions [Opens in a new window]

Extract

In this paper it will be shown that the ordering of the recursively enumerable (r.e.) sets under inclusion modulo finite differences (m.f.d.), the ordering of the II111 sets under inclusion m.f.d., and the ordering of the metarecursively enumerable (meta-r.e.) sets under inclusion m.f.d. are all distinct. In fact, it will be shown that the three orderings are pairwise elementarily inequivalent when interpreted in the obvious way in a first order language with one binary relation “≥.” Our result answers a question of Hartley Rogers, Jr. [3, p. 203]. All necessary background material may be found in [2] and [4].

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 32 , Issue 2 , August 1967 , pp. 173 - 179
Copyright
Copyright © Association for Symbolic Logic 1967

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.)

References

[1]Friedberg, R. M., Three theorems on recursive enumeration, this Journal, vol. 23 (1958), pp. 309–316.Google Scholar
[2]Kleene, S. C., Introduction to metamathematics, D. Van Nostrand, New York, 1952.Google Scholar
[3]Kreisel, G., Model-theoretic invariants; applications to recursive and hyperarithmetic operations, The theory of models; North-Holland, Amsterdam, 1965, pp. 190–205.Google Scholar
[4]Kreisel, G. and Sacks, G. E., Metarecursive sets, this Journal, vol. 30 (1965), pp. 318–338.Google Scholar
[5]Lachlan, A. H., On the lattice of recursively enumerable sets, Transactions of the American Mathematical Society (to appear).Google Scholar