Recursion, metarecursion, and inclusion

Publisher Website
Google Scholar
Abstract
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].