On orders of translations and enumerations

Abstract

A basic result of intuitive recursion theory is that a set (of natural numbers) is decidable (recursive) iff it can be effectively enumerated in its natural order (of increasing magnitude). The chief theorems of this paper give simple, but very basic facts relating to enumerations in natural order of magnitude and the extent to which translations must preserve the orders of the sets being enumerated. Under very general conditions for what constitutes a programming system for enumerating the recursively enumerable (r.e.) sets, we prove in Theorem 1 that not every recursive set is " best" enumerated in its natural order, and we later show that under these same general conditions, in every programming system, every recursive set is enumerable in its natural order. We accomplish the latter result by extending Rogers' Isomorphism Theorem to a result which asserts that under these same general conditions, every programming system can be effectively translated into any other in a manner which preserves the order of the sets being enumerated (Theorems 4 and 5). In fact, we show that for every translator, t, there is an order preserving pretranslator, p, such that t is orderpreserving modulo p; i.e., t p is an order preserving translator. In addition, the restriction of the original programming system to the recursive set {range p] is a standard programming system on which t is order-preserving. Along the way we establish the existence of sets best enumerated in their natural order and, for every r.e. set, the existence of bad orders for enumerating the set. All proofs are fairly straightforward.