A basic result of intuitive
recursion theory is that a set (of natural numbers) is decidable (recursive) ffl 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 order-preserving 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.
