Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T11:38:58.459Z Has data issue: false hasContentIssue false

Recursion, metarecursion, and inclusion

Published online by Cambridge University Press:  12 March 2014

James C. Owings Jr.*
Affiliation:
Cornell University

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

Information

Type
Research Article
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.)

Article purchase

Temporarily unavailable